elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996, 1997, 1998, 1999, 2000 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 two kinds paths
  76    through the list of loaded shared objects.  We have to
  77
  78    - produce a flat list with unique members of all involved objects
  79
  80    - produce a flat list of all shared objects.
  81 */
  82 struct list
  83   {
  84     int done;                   /* Nonzero if this map was processed.  */
  85     struct link_map *map;       /* The data.  */
  86
  87     struct list *unique;        /* Elements for normal list.  */
  88     struct list *dup;           /* Elements in complete list.  */
  89   };
  90
  91
  92 /* Macro to expand DST.  It is an macro since we use `alloca'.  */
  93 #define expand_dst(l, str, fatal) \
  94   ({                                                                          \
  95     const char *__str = (str);                                                \
  96     const char *__result = __str;                                             \
  97     size_t __cnt = DL_DST_COUNT(__str, 0);                                    \
  98                                                                               \
  99     if (__cnt != 0)                                                           \
 100       {                                                                       \
 101         char *__newp;                                                         \
 102                                                                               \
 103         /* DST must not appear in SUID/SGID programs.  */                     \
 104         if (__libc_enable_secure)                                             \
 105           _dl_signal_error (0, __str,                                         \
 106                             N_("DST not allowed in SUID/SGID programs"));     \
 107                                                                               \
 108         __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str),  \
 109                                                    __cnt));                   \
 110                                                                               \
 111         __result = DL_DST_SUBSTITUTE (l, __str, __newp, 0);                   \
 112                                                                               \
 113         if (*__result == '\0')                                                \
 114           {                                                                   \
 115             /* The replacement for the DST is not known.  We can't            \
 116                processed.  */                                                 \
 117             if (fatal)                                                        \
 118               _dl_signal_error (0, __str, N_("\
 119 empty dynamics string token substitution"));                                  \
 120             else                                                              \
 121               {                                                               \
 122                 /* This is for DT_AUXILIARY.  */                              \
 123                 if (__builtin_expect (_dl_debug_libs, 0))                     \
 124                   _dl_debug_message (1, "cannot load auxiliary `", __str,     \
 125                                      "' because of empty dynamic string"      \
 126                                      " token substitution\n", NULL);          \
 127                 continue;                                                     \
 128               }                                                               \
 129           }                                                                   \
 130       }                                                                       \
 131                                                                               \
 132     __result; })
 133
 134
 135 void
 136 internal_function
 137 _dl_map_object_deps (struct link_map *map,
 138                      struct link_map **preloads, unsigned int npreloads,
 139                      int trace_mode)
 140 {
 141   struct list known[1 + npreloads + 1];
 142   struct list *runp, *utail, *dtail;
 143   unsigned int nlist, nduplist, i;
 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
 152       known[nlist].unique = &known[nlist + 1];
 153       known[nlist].dup = &known[nlist + 1];
 154
 155       ++nlist;
 156       /* We use `l_reserved' as a mark bit to detect objects we have
 157          already put in the search list and avoid adding duplicate
 158          elements later in the list.  */
 159       map->l_reserved = 1;
 160     }
 161
 162   /* No loaded object so far.  */
 163   nlist = 0;
 164
 165   /* First load MAP itself.  */
 166   preload (map);
 167
 168   /* Add the preloaded items after MAP but before any of its dependencies.  */
 169   for (i = 0; i < npreloads; ++i)
 170     preload (preloads[i]);
 171
 172   /* Terminate the lists.  */
 173   known[nlist - 1].unique = NULL;
 174   known[nlist - 1].dup = NULL;
 175
 176   /* Pointer to last unique object.  */
 177   utail = &known[nlist - 1];
 178   /* Pointer to last loaded object.  */
 179   dtail = &known[nlist - 1];
 180
 181   /* Until now we have the same number of libraries in the normal and
 182      the list with duplicates.  */
 183   nduplist = nlist;
 184
 185   /* Process each element of the search list, loading each of its
 186      auxiliary objects and immediate dependencies.  Auxiliary objects
 187      will be added in the list before the object itself and
 188      dependencies will be appended to the list as we step through it.
 189      This produces a flat, ordered list that represents a
 190      breadth-first search of the dependency tree.
 191
 192      The whole process is complicated by the fact that we better
 193      should use alloca for the temporary list elements.  But using
 194      alloca means we cannot use recursive function calls.  */
 195   for (runp = known; runp; )
 196     {
 197       struct link_map *l = runp->map;
 198       struct link_map **needed = NULL;
 199       unsigned int nneeded = 0;
 200
 201       /* Unless otherwise stated, this object is handled.  */
 202       runp->done = 1;
 203
 204       /* Allocate a temporary record to contain the references to the
 205          dependencies of this object.  */
 206       if (l->l_searchlist.r_list == NULL && l->l_initfini == NULL
 207           && l != map && l->l_ldnum > 0)
 208         needed = (struct link_map **) alloca (l->l_ldnum
 209                                               * sizeof (struct link_map *));
 210
 211       if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 212         {
 213           const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);
 214           struct openaux_args args;
 215           struct list *orig;
 216           const ElfW(Dyn) *d;
 217
 218           args.strtab = strtab;
 219           args.map = l;
 220           args.trace_mode = trace_mode;
 221           orig = runp;
 222
 223           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 224             if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
 225               {
 226                 /* Map in the needed object.  */
 227                 struct link_map *dep;
 228                 /* Allocate new entry.  */
 229                 struct list *newp;
 230                 /* Object name.  */
 231                 const char *name;
 232
 233                 /* Recognize DSTs.  */
 234                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 235
 236                 dep = _dl_map_object (l, name, 0,
 237                                       l->l_type == lt_executable ? lt_library :
 238                                       l->l_type, trace_mode, 0);
 239
 240                 /* Add it in any case to the duplicate list.  */
 241                 newp = alloca (sizeof (struct list));
 242                 newp->map = dep;
 243                 newp->dup = NULL;
 244                 dtail->dup = newp;
 245                 dtail = newp;
 246                 ++nduplist;
 247
 248                 if (! dep->l_reserved)
 249                   {
 250                     /* Append DEP to the unique list.  */
 251                     newp->done = 0;
 252                     newp->unique = NULL;
 253                     utail->unique = newp;
 254                     utail = 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                 const char *errstring;
 268                 struct list *newp;
 269                 /* Object name.  */
 270                 const char *name;
 271
 272                 /* Recognize DSTs.  */
 273                 name = expand_dst (l, strtab + d->d_un.d_val,
 274                                    d->d_tag == DT_AUXILIARY);
 275
 276                 if (d->d_tag == DT_AUXILIARY)
 277                   {
 278                     /* Store the tag in the argument structure.  */
 279                     args.name = name;
 280
 281                     /* Say that we are about to load an auxiliary library.  */
 282                     if (__builtin_expect (_dl_debug_libs, 0))
 283                       _dl_debug_message (1, "load auxiliary object=",
 284                                          name, " requested by file=",
 285                                          l->l_name[0]
 286                                          ? l->l_name : _dl_argv[0],
 287                                          "\n", NULL);
 288
 289                     /* We must be prepared that the addressed shared
 290                        object is not available.  */
 291                     if (_dl_catch_error (&objname, &errstring, openaux, &args))
 292                       {
 293                         /* We are not interested in the error message.  */
 294                         assert (errstring != NULL);
 295                         if (errstring != _dl_out_of_memory)
 296                           free ((char *) errstring);
 297
 298                         /* Simply ignore this error and continue the work.  */
 299                         continue;
 300                       }
 301                   }
 302                 else
 303                   {
 304                     /* Say that we are about to load an auxiliary library.  */
 305                     if (__builtin_expect (_dl_debug_libs, 0))
 306                       _dl_debug_message (1, "load filtered object=", name,
 307                                          " requested by file=",
 308                                          l->l_name[0]
 309                                          ? l->l_name : _dl_argv[0],
 310                                          "\n", NULL);
 311
 312                     /* For filter objects the dependency must be available.  */
 313                     args.aux = _dl_map_object (l, name, 0,
 314                                                (l->l_type == lt_executable
 315                                                 ? lt_library : l->l_type),
 316                                                trace_mode, 0);
 317                   }
 318
 319                 /* The auxiliary object is actually available.
 320                    Incorporate the map in all the lists.  */
 321
 322                 /* Allocate new entry.  This always has to be done.  */
 323                 newp = alloca (sizeof (struct list));
 324
 325                 /* We want to insert the new map before the current one,
 326                    but we have no back links.  So we copy the contents of
 327                    the current entry over.  Note that ORIG and NEWP now
 328                    have switched their meanings.  */
 329                 orig->dup = memcpy (newp, orig, sizeof (*newp));
 330
 331                 /* Initialize new entry.  */
 332                 orig->done = 0;
 333                 orig->map = args.aux;
 334
 335                 /* Remember this dependency.  */
 336                 if (needed != NULL)
 337                   needed[nneeded++] = args.aux;
 338
 339                 /* We must handle two situations here: the map is new,
 340                    so we must add it in all three lists.  If the map
 341                    is already known, we have two further possibilities:
 342                    - if the object is before the current map in the
 343                    search list, we do nothing.  It is already found
 344                    early
 345                    - if the object is after the current one, we must
 346                    move it just before the current map to make sure
 347                    the symbols are found early enough
 348                 */
 349                 if (args.aux->l_reserved)
 350                   {
 351                     /* The object is already somewhere in the list.
 352                        Locate it first.  */
 353                     struct list *late;
 354
 355                     /* This object is already in the search list we
 356                        are building.  Don't add a duplicate pointer.
 357                        Just added by _dl_map_object.  */
 358                     for (late = newp; late->unique; late = late->unique)
 359                       if (late->unique->map == args.aux)
 360                         break;
 361
 362                     if (late->unique)
 363                       {
 364                         /* The object is somewhere behind the current
 365                            position in the search path.  We have to
 366                            move it to this earlier position.  */
 367                         orig->unique = newp;
 368
 369                         /* Now remove the later entry from the unique list
 370                            and adjust the tail pointer.  */
 371                         if (utail == late->unique)
 372                           utail = late;
 373                         late->unique = late->unique->unique;
 374
 375                         /* We must move the object earlier in the chain.  */
 376                         if (args.aux->l_prev)
 377                           args.aux->l_prev->l_next = args.aux->l_next;
 378                         if (args.aux->l_next)
 379                           args.aux->l_next->l_prev = args.aux->l_prev;
 380
 381                         args.aux->l_prev = newp->map->l_prev;
 382                         newp->map->l_prev = args.aux;
 383                         if (args.aux->l_prev != NULL)
 384                           args.aux->l_prev->l_next = args.aux;
 385                         args.aux->l_next = newp->map;
 386                       }
 387                     else
 388                       {
 389                         /* The object must be somewhere earlier in the
 390                            list.  That's good, we only have to insert
 391                            an entry for the duplicate list.  */
 392                         orig->unique = NULL;    /* Never used.  */
 393
 394                         /* Now we have a problem.  The element
 395                            pointing to ORIG in the unique list must
 396                            point to NEWP now.  This is the only place
 397                            where we need this backreference and this
 398                            situation is really not that frequent.  So
 399                            we don't use a double-linked list but
 400                            instead search for the preceding element.  */
 401                         late = known;
 402                         while (late->unique != orig)
 403                           late = late->unique;
 404                         late->unique = newp;
 405                       }
 406                   }
 407                 else
 408                   {
 409                     /* This is easy.  We just add the symbol right here.  */
 410                     orig->unique = newp;
 411                     ++nlist;
 412                     /* Set the mark bit that says it's already in the list.  */
 413                     args.aux->l_reserved = 1;
 414
 415                     /* The only problem is that in the double linked
 416                        list of all objects we don't have this new
 417                        object at the correct place.  Correct this here.  */
 418                     if (args.aux->l_prev)
 419                       args.aux->l_prev->l_next = args.aux->l_next;
 420                     if (args.aux->l_next)
 421                       args.aux->l_next->l_prev = args.aux->l_prev;
 422
 423                     args.aux->l_prev = newp->map->l_prev;
 424                     newp->map->l_prev = args.aux;
 425                     if (args.aux->l_prev != NULL)
 426                       args.aux->l_prev->l_next = args.aux;
 427                     args.aux->l_next = newp->map;
 428                   }
 429
 430                 /* Move the tail pointers if necessary.  */
 431                 if (orig == utail)
 432                   utail = newp;
 433                 if (orig == dtail)
 434                   dtail = newp;
 435
 436                 /* Move on the insert point.  */
 437                 orig = newp;
 438
 439                 /* We always add an entry to the duplicate list.  */
 440                 ++nduplist;
 441               }
 442         }
 443
 444       /* Terminate the list of dependencies and store the array address.  */
 445       if (needed != NULL)
 446         {
 447           needed[nneeded++] = NULL;
 448
 449           l->l_initfini = malloc (nneeded * sizeof needed[0]);
 450           if (l->l_initfini == NULL)
 451             _dl_signal_error (ENOMEM, map->l_name,
 452                               N_("cannot allocate dependency list"));
 453           memcpy (l->l_initfini, needed, nneeded * sizeof needed[0]);
 454         }
 455
 456       /* If we have no auxiliary objects just go on to the next map.  */
 457       if (runp->done)
 458         do
 459           runp = runp->unique;
 460         while (runp != NULL && runp->done);
 461     }
 462
 463   if (map->l_initfini != NULL && map->l_type == lt_loaded)
 464     {
 465       /* This object was previously loaded as a dependency and we have
 466          a separate l_initfini list.  We don't need it anymore.  */
 467       assert (map->l_searchlist.r_list == NULL);
 468       free (map->l_initfini);
 469     }
 470
 471   /* Store the search list we built in the object.  It will be used for
 472      searches in the scope of this object.  */
 473   map->l_initfini =
 474     (struct link_map **) malloc ((2 * nlist + 1
 475                                   + (nlist == nduplist ? 0 : nduplist))
 476                                  * sizeof (struct link_map *));
 477   if (map->l_initfini == NULL)
 478     _dl_signal_error (ENOMEM, map->l_name,
 479                       N_("cannot allocate symbol search list"));
 480
 481
 482   map->l_searchlist.r_list = &map->l_initfini[nlist + 1];
 483   map->l_searchlist.r_nlist = nlist;
 484
 485   for (nlist = 0, runp = known; runp; runp = runp->unique)
 486     {
 487       if (trace_mode && runp->map->l_faked)
 488         /* This can happen when we trace the loading.  */
 489         --map->l_searchlist.r_nlist;
 490       else
 491         map->l_searchlist.r_list[nlist++] = runp->map;
 492
 493       /* Now clear all the mark bits we set in the objects on the search list
 494          to avoid duplicates, so the next call starts fresh.  */
 495       runp->map->l_reserved = 0;
 496     }
 497
 498   map->l_searchlist.r_nduplist = nduplist;
 499   if (nlist == nduplist)
 500     map->l_searchlist.r_duplist = map->l_searchlist.r_list;
 501   else
 502     {
 503       unsigned int cnt;
 504
 505       map->l_searchlist.r_duplist = map->l_searchlist.r_list + nlist;
 506
 507       for (cnt = 0, runp = known; runp; runp = runp->dup)
 508         if (trace_mode && runp->map->l_faked)
 509           /* This can happen when we trace the loading.  */
 510           --map->l_searchlist.r_nduplist;
 511         else
 512           map->l_searchlist.r_duplist[cnt++] = runp->map;
 513     }
 514
 515   /* Now determine the order in which the initialization has to happen.  */
 516   memcpy (map->l_initfini, map->l_searchlist.r_list,
 517           nlist * sizeof (struct link_map *));
 518   /* We can skip looking for the binary itself which is at the front
 519      of the search list.  Look through the list backward so that circular
 520      dependencies are not changing the order.  */
 521   for (i = 1; i < nlist; ++i)
 522     {
 523       struct link_map *l = map->l_searchlist.r_list[i];
 524       unsigned int j;
 525       unsigned int k;
 526
 527       /* Find the place in the initfini list where the map is currently
 528          located.  */
 529       for (j = 1; map->l_initfini[j] != l; ++j)
 530         ;
 531
 532       /* Find all object for which the current one is a dependency and
 533          move the found object (if necessary) in front.  */
 534       for (k = j + 1; k < nlist; ++k)
 535         {
 536           struct link_map **runp;
 537
 538           runp = map->l_initfini[k]->l_initfini;
 539           if (runp != NULL)
 540             {
 541               while (*runp != NULL)
 542                 if (*runp == l)
 543                   {
 544                     struct link_map *here = map->l_initfini[k];
 545
 546                     /* Move it now.  */
 547                     memmove (&map->l_initfini[j] + 1,
 548                              &map->l_initfini[j],
 549                              (k - j) * sizeof (struct link_map *));
 550                     map->l_initfini[j] = here;
 551
 552                     break;
 553                   }
 554                 else
 555                   ++runp;
 556             }
 557         }
 558     }
 559   /* Terminate the list of dependencies.  */
 560   map->l_initfini[nlist] = NULL;
 561 }