elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996,1997,1998,1999,2000,2001 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Library General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Library General Public License for more details.
  14
  15    You should have received a copy of the GNU Library General Public
  16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18    Boston, MA 02111-1307, USA.  */
  19
  20 #include <assert.h>
  21 #include <dlfcn.h>
  22 #include <errno.h>
  23 #include <libintl.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <unistd.h>
  27 #include <sys/param.h>
  28 #include <ldsodefs.h>
  29
  30 #include <dl-dst.h>
  31
  32 /* Whether an shared object references one or more auxiliary objects
  33    is signaled by the AUXTAG entry in l_info.  */
  34 #define AUXTAG  (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
  35                  + DT_EXTRATAGIDX (DT_AUXILIARY))
  36 /* Whether an shared object references one or more auxiliary objects
  37    is signaled by the AUXTAG entry in l_info.  */
  38 #define FILTERTAG (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
  39                    + DT_EXTRATAGIDX (DT_FILTER))
  40
  41 /* This is zero at program start to signal that the global scope map is
  42    allocated by rtld.  Later it keeps the size of the map.  It might be
  43    reset if in _dl_close if the last global object is removed.  */
  44 size_t _dl_global_scope_alloc;
  45
  46 extern size_t _dl_platformlen;
  47
  48 /* When loading auxiliary objects we must ignore errors.  It's ok if
  49    an object is missing.  */
  50 struct openaux_args
  51   {
  52     /* The arguments to openaux.  */
  53     struct link_map *map;
  54     int trace_mode;
  55     const char *strtab;
  56     const char *name;
  57
  58     /* The return value of openaux.  */
  59     struct link_map *aux;
  60   };
  61
  62 static void
  63 openaux (void *a)
  64 {
  65   struct openaux_args *args = (struct openaux_args *) a;
  66
  67   args->aux = _dl_map_object (args->map, args->name, 0,
  68                               (args->map->l_type == lt_executable
  69                                ? lt_library : args->map->l_type),
  70                               args->trace_mode, 0);
  71 }
  72
  73
  74
  75 /* We use a very special kind of list to track the path
  76    through the list of loaded shared objects.  We have to
  77    produce a flat list with unique members of all involved objects.
  78 */
  79 struct list
  80   {
  81     int done;                   /* Nonzero if this map was processed.  */
  82     struct link_map *map;       /* The data.  */
  83     struct list *next;  /* Elements for normal list.  */
  84   };
  85
  86
  87 /* Macro to expand DST.  It is an macro since we use `alloca'.  */
  88 #define expand_dst(l, str, fatal) \
  89   ({                                                                          \
  90     const char *__str = (str);                                                \
  91     const char *__result = __str;                                             \
  92     size_t __cnt = DL_DST_COUNT(__str, 0);                                    \
  93                                                                               \
  94     if (__cnt != 0)                                                           \
  95       {                                                                       \
  96         char *__newp;                                                         \
  97                                                                               \
  98         /* DST must not appear in SUID/SGID programs.  */                     \
  99         if (__libc_enable_secure)                                             \
 100           _dl_signal_error (0, __str,                                         \
 101                             N_("DST not allowed in SUID/SGID programs"));     \
 102                                                                               \
 103         __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str),  \
 104                                                    __cnt));                   \
 105                                                                               \
 106         __result = DL_DST_SUBSTITUTE (l, __str, __newp, 0);                   \
 107                                                                               \
 108         if (*__result == '\0')                                                \
 109           {                                                                   \
 110             /* The replacement for the DST is not known.  We can't            \
 111                processed.  */                                                 \
 112             if (fatal)                                                        \
 113               _dl_signal_error (0, __str, N_("\
 114 empty dynamics string token substitution"));                                  \
 115             else                                                              \
 116               {                                                               \
 117                 /* This is for DT_AUXILIARY.  */                              \
 118                 if (__builtin_expect (_dl_debug_mask & DL_DEBUG_LIBS, 0))     \
 119                   _dl_debug_printf ("cannot load auxiliary `%s' because of"   \
 120                                     "empty dynamic string token "             \
 121                                     "substitution\n", __str);                 \
 122                 continue;                                                     \
 123               }                                                               \
 124           }                                                                   \
 125       }                                                                       \
 126                                                                               \
 127     __result; })
 128
 129
 130 void
 131 internal_function
 132 _dl_map_object_deps (struct link_map *map,
 133                      struct link_map **preloads, unsigned int npreloads,
 134                      int trace_mode)
 135 {
 136   struct list known[1 + npreloads + 1];
 137   struct list *runp, *tail;
 138   unsigned int nlist, i;
 139   /* Object name.  */
 140   const char *name;
 141   int errno_saved;
 142   int errno_reason;
 143   const char *errstring;
 144
 145   auto inline void preload (struct link_map *map);
 146
 147   inline void preload (struct link_map *map)
 148     {
 149       known[nlist].done = 0;
 150       known[nlist].map = map;
 151       known[nlist].next = &known[nlist + 1];
 152
 153       ++nlist;
 154       /* We use `l_reserved' as a mark bit to detect objects we have
 155          already put in the search list and avoid adding duplicate
 156          elements later in the list.  */
 157       map->l_reserved = 1;
 158     }
 159
 160   /* No loaded object so far.  */
 161   nlist = 0;
 162
 163   /* First load MAP itself.  */
 164   preload (map);
 165
 166   /* Add the preloaded items after MAP but before any of its dependencies.  */
 167   for (i = 0; i < npreloads; ++i)
 168     preload (preloads[i]);
 169
 170   /* Terminate the lists.  */
 171   known[nlist - 1].next = NULL;
 172
 173   /* Pointer to last unique object.  */
 174   tail = &known[nlist - 1];
 175
 176   /* Process each element of the search list, loading each of its
 177      auxiliary objects and immediate dependencies.  Auxiliary objects
 178      will be added in the list before the object itself and
 179      dependencies will be appended to the list as we step through it.
 180      This produces a flat, ordered list that represents a
 181      breadth-first search of the dependency tree.
 182
 183      The whole process is complicated by the fact that we better
 184      should use alloca for the temporary list elements.  But using
 185      alloca means we cannot use recursive function calls.  */
 186   errno_saved = errno;
 187   errno_reason = 0;
 188   errstring = NULL;
 189   errno = 0;
 190   name = NULL;
 191   for (runp = known; runp; )
 192     {
 193       struct link_map *l = runp->map;
 194       struct link_map **needed = NULL;
 195       unsigned int nneeded = 0;
 196
 197       /* Unless otherwise stated, this object is handled.  */
 198       runp->done = 1;
 199
 200       /* Allocate a temporary record to contain the references to the
 201          dependencies of this object.  */
 202       if (l->l_searchlist.r_list == NULL && l->l_initfini == NULL
 203           && l != map && l->l_ldnum > 0)
 204         needed = (struct link_map **) alloca (l->l_ldnum
 205                                               * sizeof (struct link_map *));
 206
 207       if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 208         {
 209           const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);
 210           struct openaux_args args;
 211           struct list *orig;
 212           const ElfW(Dyn) *d;
 213
 214           args.strtab = strtab;
 215           args.map = l;
 216           args.trace_mode = trace_mode;
 217           orig = runp;
 218
 219           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 220             if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
 221               {
 222                 /* Map in the needed object.  */
 223                 struct link_map *dep;
 224                 const char *objname;
 225
 226                 /* Recognize DSTs.  */
 227                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 228                 /* Store the tag in the argument structure.  */
 229                 args.name = name;
 230
 231                 if (_dl_catch_error (&objname, &errstring, openaux, &args))
 232                   {
 233                     if (errno)
 234                       errno_reason = errno;
 235                     else
 236                       errno_reason = -1;
 237                     goto out;
 238                   }
 239                 else
 240                   dep = args.aux;
 241
 242                 if (! dep->l_reserved)
 243                   {
 244                     /* Allocate new entry.  */
 245                     struct list *newp;
 246
 247                     newp = alloca (sizeof (struct list));
 248
 249                     /* Append DEP to the list.  */
 250                     newp->map = dep;
 251                     newp->done = 0;
 252                     newp->next = NULL;
 253                     tail->next = newp;
 254                     tail = newp;
 255                     ++nlist;
 256                     /* Set the mark bit that says it's already in the list.  */
 257                     dep->l_reserved = 1;
 258                   }
 259
 260                 /* Remember this dependency.  */
 261                 if (needed != NULL)
 262                   needed[nneeded++] = dep;
 263               }
 264             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 265               {
 266                 const char *objname;
 267                 struct list *newp;
 268
 269                 /* Recognize DSTs.  */
 270                 name = expand_dst (l, strtab + d->d_un.d_val,
 271                                    d->d_tag == DT_AUXILIARY);
 272                 /* Store the tag in the argument structure.  */
 273                 args.name = name;
 274
 275                 if (d->d_tag == DT_AUXILIARY)
 276                   {
 277                     /* Say that we are about to load an auxiliary library.  */
 278                     if (__builtin_expect (_dl_debug_mask & DL_DEBUG_LIBS, 0))
 279                       _dl_debug_printf ("load auxiliary object=%s"
 280                                         " requested by file=%s\n", name,
 281                                         l->l_name[0]
 282                                         ? l->l_name : _dl_argv[0]);
 283
 284                     /* We must be prepared that the addressed shared
 285                        object is not available.  */
 286                     if (_dl_catch_error (&objname, &errstring, openaux, &args))
 287                       {
 288                         /* We are not interested in the error message.  */
 289                         assert (errstring != NULL);
 290                         if (errstring != _dl_out_of_memory)
 291                           free ((char *) errstring);
 292                         errstring = NULL;
 293
 294                         /* Simply ignore this error and continue the work.  */
 295                         continue;
 296                       }
 297                   }
 298                 else
 299                   {
 300                     /* Say that we are about to load an auxiliary library.  */
 301                     if (__builtin_expect (_dl_debug_mask & DL_DEBUG_LIBS, 0))
 302                       _dl_debug_printf ("load filtered object=%s"
 303                                         " requested by file=%s\n", name,
 304                                         l->l_name[0]
 305                                         ? l->l_name : _dl_argv[0]);
 306
 307                     /* For filter objects the dependency must be available.  */
 308                     if (_dl_catch_error (&objname, &errstring, openaux, &args))
 309                       {
 310                         if (errno)
 311                           errno_reason = errno;
 312                         else
 313                           errno_reason = -1;
 314                         goto out;
 315                       }
 316                   }
 317
 318                 /* The auxiliary object is actually available.
 319                    Incorporate the map in all the lists.  */
 320
 321                 /* Allocate new entry.  This always has to be done.  */
 322                 newp = alloca (sizeof (struct list));
 323
 324                 /* We want to insert the new map before the current one,
 325                    but we have no back links.  So we copy the contents of
 326                    the current entry over.  Note that ORIG and NEWP now
 327                    have switched their meanings.  */
 328                 memcpy (newp, orig, sizeof (*newp));
 329
 330                 /* Initialize new entry.  */
 331                 orig->done = 0;
 332                 orig->map = args.aux;
 333
 334                 /* Remember this dependency.  */
 335                 if (needed != NULL)
 336                   needed[nneeded++] = args.aux;
 337
 338                 /* We must handle two situations here: the map is new,
 339                    so we must add it in all three lists.  If the map
 340                    is already known, we have two further possibilities:
 341                    - if the object is before the current map in the
 342                    search list, we do nothing.  It is already found
 343                    early
 344                    - if the object is after the current one, we must
 345                    move it just before the current map to make sure
 346                    the symbols are found early enough
 347                 */
 348                 if (args.aux->l_reserved)
 349                   {
 350                     /* The object is already somewhere in the list.
 351                        Locate it first.  */
 352                     struct list *late;
 353
 354                     /* This object is already in the search list we
 355                        are building.  Don't add a duplicate pointer.
 356                        Just added by _dl_map_object.  */
 357                     for (late = newp; late->next; late = late->next)
 358                       if (late->next->map == args.aux)
 359                         break;
 360
 361                     if (late->next)
 362                       {
 363                         /* The object is somewhere behind the current
 364                            position in the search path.  We have to
 365                            move it to this earlier position.  */
 366                         orig->next = newp;
 367
 368                         /* Now remove the later entry from the list
 369                            and adjust the tail pointer.  */
 370                         if (tail == late->next)
 371                           tail = late;
 372                         late->next = late->next->next;
 373
 374                         /* We must move the object earlier in the chain.  */
 375                         if (args.aux->l_prev)
 376                           args.aux->l_prev->l_next = args.aux->l_next;
 377                         if (args.aux->l_next)
 378                           args.aux->l_next->l_prev = args.aux->l_prev;
 379
 380                         args.aux->l_prev = newp->map->l_prev;
 381                         newp->map->l_prev = args.aux;
 382                         if (args.aux->l_prev != NULL)
 383                           args.aux->l_prev->l_next = args.aux;
 384                         args.aux->l_next = newp->map;
 385                       }
 386                     else
 387                       {
 388                         /* The object must be somewhere earlier in the
 389                            list.  That's good, we only have to insert
 390                            an entry for the duplicate list.  */
 391                         orig->next = NULL;      /* Never used.  */
 392
 393                         /* Now we have a problem.  The element
 394                            pointing to ORIG in the list must
 395                            point to NEWP now.  This is the only place
 396                            where we need this backreference and this
 397                            situation is really not that frequent.  So
 398                            we don't use a double-linked list but
 399                            instead search for the preceding element.  */
 400                         late = known;
 401                         while (late->next != orig)
 402                           late = late->next;
 403                         late->next = newp;
 404                       }
 405                   }
 406                 else
 407                   {
 408                     /* This is easy.  We just add the symbol right here.  */
 409                     orig->next = newp;
 410                     ++nlist;
 411                     /* Set the mark bit that says it's already in the list.  */
 412                     args.aux->l_reserved = 1;
 413
 414                     /* The only problem is that in the double linked
 415                        list of all objects we don't have this new
 416                        object at the correct place.  Correct this here.  */
 417                     if (args.aux->l_prev)
 418                       args.aux->l_prev->l_next = args.aux->l_next;
 419                     if (args.aux->l_next)
 420                       args.aux->l_next->l_prev = args.aux->l_prev;
 421
 422                     args.aux->l_prev = newp->map->l_prev;
 423                     newp->map->l_prev = args.aux;
 424                     if (args.aux->l_prev != NULL)
 425                       args.aux->l_prev->l_next = args.aux;
 426                     args.aux->l_next = newp->map;
 427                   }
 428
 429                 /* Move the tail pointer if necessary.  */
 430                 if (orig == tail)
 431                   tail = newp;
 432
 433                 /* Move on the insert point.  */
 434                 orig = newp;
 435               }
 436         }
 437
 438       /* Terminate the list of dependencies and store the array address.  */
 439       if (needed != NULL)
 440         {
 441           needed[nneeded++] = NULL;
 442
 443           l->l_initfini = malloc (nneeded * sizeof needed[0]);
 444           if (l->l_initfini == NULL)
 445             _dl_signal_error (ENOMEM, map->l_name,
 446                               N_("cannot allocate dependency list"));
 447           memcpy (l->l_initfini, needed, nneeded * sizeof needed[0]);
 448         }
 449
 450       /* If we have no auxiliary objects just go on to the next map.  */
 451       if (runp->done)
 452         do
 453           runp = runp->next;
 454         while (runp != NULL && runp->done);
 455     }
 456
 457 out:
 458   if (errno == 0 && errno_saved != 0)
 459     __set_errno (errno_saved);
 460
 461   if (map->l_initfini != NULL && map->l_type == lt_loaded)
 462     {
 463       /* This object was previously loaded as a dependency and we have
 464          a separate l_initfini list.  We don't need it anymore.  */
 465       assert (map->l_searchlist.r_list == NULL);
 466       free (map->l_initfini);
 467     }
 468
 469   /* Store the search list we built in the object.  It will be used for
 470      searches in the scope of this object.  */
 471   map->l_initfini =
 472     (struct link_map **) malloc ((2 * nlist + 1)
 473                                  * sizeof (struct link_map *));
 474   if (map->l_initfini == NULL)
 475     _dl_signal_error (ENOMEM, map->l_name,
 476                       N_("cannot allocate symbol search list"));
 477
 478
 479   map->l_searchlist.r_list = &map->l_initfini[nlist + 1];
 480   map->l_searchlist.r_nlist = nlist;
 481
 482   for (nlist = 0, runp = known; runp; runp = runp->next)
 483     {
 484       if (trace_mode && runp->map->l_faked)
 485         /* This can happen when we trace the loading.  */
 486         --map->l_searchlist.r_nlist;
 487       else
 488         map->l_searchlist.r_list[nlist++] = runp->map;
 489
 490       /* Now clear all the mark bits we set in the objects on the search list
 491          to avoid duplicates, so the next call starts fresh.  */
 492       runp->map->l_reserved = 0;
 493     }
 494
 495   /* Now determine the order in which the initialization has to happen.  */
 496   memcpy (map->l_initfini, map->l_searchlist.r_list,
 497           nlist * sizeof (struct link_map *));
 498   /* We can skip looking for the binary itself which is at the front
 499      of the search list.  Look through the list backward so that circular
 500      dependencies are not changing the order.  */
 501   for (i = 1; i < nlist; ++i)
 502     {
 503       struct link_map *l = map->l_searchlist.r_list[i];
 504       unsigned int j;
 505       unsigned int k;
 506
 507       /* Find the place in the initfini list where the map is currently
 508          located.  */
 509       for (j = 1; map->l_initfini[j] != l; ++j)
 510         ;
 511
 512       /* Find all object for which the current one is a dependency and
 513          move the found object (if necessary) in front.  */
 514       for (k = j + 1; k < nlist; ++k)
 515         {
 516           struct link_map **runp;
 517
 518           runp = map->l_initfini[k]->l_initfini;
 519           if (runp != NULL)
 520             {
 521               while (*runp != NULL)
 522                 if (*runp == l)
 523                   {
 524                     struct link_map *here = map->l_initfini[k];
 525
 526                     /* Move it now.  */
 527                     memmove (&map->l_initfini[j] + 1,
 528                              &map->l_initfini[j],
 529                              (k - j) * sizeof (struct link_map *));
 530                     map->l_initfini[j] = here;
 531
 532                     break;
 533                   }
 534                 else
 535                   ++runp;
 536             }
 537         }
 538     }
 539   /* Terminate the list of dependencies.  */
 540   map->l_initfini[nlist] = NULL;
 541
 542   if (errno_reason)
 543     _dl_signal_error (errno_reason == -1 ? 0 : errno_reason,
 544                       errstring ?: "", N_("cannot load shared object file"));
 545 }