elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996, 1997, 1998, 1999 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 <dlfcn.h>
  21 #include <errno.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <elf/ldsodefs.h>
  25
  26 #include <assert.h>
  27
  28 /* Whether an shared object references one or more auxiliary objects
  29    is signaled by the AUXTAG entry in l_info.  */
  30 #define AUXTAG  (DT_NUM + DT_PROCNUM + DT_VERSIONTAGNUM \
  31                  + DT_EXTRATAGIDX (DT_AUXILIARY))
  32 /* Whether an shared object references one or more auxiliary objects
  33    is signaled by the AUXTAG entry in l_info.  */
  34 #define FILTERTAG (DT_NUM + DT_PROCNUM + DT_VERSIONTAGNUM \
  35                    + DT_EXTRATAGIDX (DT_FILTER))
  36
  37 /* This is zero at program start to signal that the global scope map is
  38    allocated by rtld.  Later it keeps the size of the map.  It might be
  39    reset if in _dl_close if the last global object is removed.  */
  40 size_t _dl_global_scope_alloc;
  41
  42
  43 /* When loading auxiliary objects we must ignore errors.  It's ok if
  44    an object is missing.  */
  45 struct openaux_args
  46   {
  47     /* The arguments to openaux.  */
  48     struct link_map *map;
  49     int trace_mode;
  50     const char *strtab;
  51     const ElfW(Dyn) *d;
  52
  53     /* The return value of openaux.  */
  54     struct link_map *aux;
  55   };
  56
  57 static void
  58 openaux (void *a)
  59 {
  60   struct openaux_args *args = (struct openaux_args *) a;
  61
  62   args->aux = _dl_map_object (args->map, args->strtab + args->d->d_un.d_val, 0,
  63                               (args->map->l_type == lt_executable
  64                                ? lt_library : args->map->l_type),
  65                               args->trace_mode);
  66 }
  67
  68
  69
  70 /* We use a very special kind of list to track the two kinds paths
  71    through the list of loaded shared objects.  We have to
  72
  73    - produce a flat list with unique members of all involved objects
  74
  75    - produce a flat list of all shared objects.
  76 */
  77 struct list
  78   {
  79     int done;                   /* Nonzero if this map was processed.  */
  80     struct link_map *map;       /* The data.  */
  81
  82     struct list *unique;        /* Elements for normal list.  */
  83     struct list *dup;           /* Elements in complete list.  */
  84   };
  85
  86
  87 unsigned int
  88 internal_function
  89 _dl_map_object_deps (struct link_map *map,
  90                      struct link_map **preloads, unsigned int npreloads,
  91                      int trace_mode, int global_scope)
  92 {
  93   struct list known[1 + npreloads + 1];
  94   struct list *runp, *utail, *dtail;
  95   unsigned int nlist, nduplist, i;
  96   unsigned int to_add = 0;
  97
  98   inline void preload (struct link_map *map)
  99     {
 100       known[nlist].done = 0;
 101       known[nlist].map = map;
 102
 103       known[nlist].unique = &known[nlist + 1];
 104       known[nlist].dup = &known[nlist + 1];
 105
 106       ++nlist;
 107       /* We use `l_reserved' as a mark bit to detect objects we have
 108          already put in the search list and avoid adding duplicate
 109          elements later in the list.  */
 110       map->l_reserved = 1;
 111     }
 112
 113   /* No loaded object so far.  */
 114   nlist = 0;
 115
 116   /* First load MAP itself.  */
 117   preload (map);
 118
 119   /* Add the preloaded items after MAP but before any of its dependencies.  */
 120   for (i = 0; i < npreloads; ++i)
 121     preload (preloads[i]);
 122
 123   /* Terminate the lists.  */
 124   known[nlist - 1].unique = NULL;
 125   known[nlist - 1].dup = NULL;
 126
 127   /* Pointer to last unique object.  */
 128   utail = &known[nlist - 1];
 129   /* Pointer to last loaded object.  */
 130   dtail = &known[nlist - 1];
 131
 132   /* Until now we have the same number of libraries in the normal and
 133      the list with duplicates.  */
 134   nduplist = nlist;
 135
 136   /* Process each element of the search list, loading each of its
 137      auxiliary objects and immediate dependencies.  Auxiliary objects
 138      will be added in the list before the object itself and
 139      dependencies will be appended to the list as we step through it.
 140      This produces a flat, ordered list that represents a
 141      breadth-first search of the dependency tree.
 142
 143      The whole process is complicated by the fact that we better
 144      should use alloca for the temporary list elements.  But using
 145      alloca means we cannot use recursive function calls.  */
 146   for (runp = known; runp; )
 147     {
 148       struct link_map *l = runp->map;
 149
 150       if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 151         {
 152           const char *strtab = (const void *) l->l_info[DT_STRTAB]->d_un.d_ptr;
 153           struct openaux_args args;
 154           struct list *orig;
 155           const ElfW(Dyn) *d;
 156
 157           /* Mark map as processed.  */
 158           runp->done = 1;
 159
 160           args.strtab = strtab;
 161           args.map = l;
 162           args.trace_mode = trace_mode;
 163           orig = runp;
 164
 165           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 166             if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
 167               {
 168                 /* Map in the needed object.  */
 169                 struct link_map *dep
 170                   = _dl_map_object (l, strtab + d->d_un.d_val, 0,
 171                                     l->l_type == lt_executable ? lt_library :
 172                                     l->l_type, trace_mode);
 173                 /* Allocate new entry.  */
 174                 struct list *newp = alloca (sizeof (struct list));
 175
 176                 /* Add it in any case to the duplicate list.  */
 177                 newp->map = dep;
 178                 newp->dup = NULL;
 179                 dtail->dup = newp;
 180                 dtail = newp;
 181                 ++nduplist;
 182
 183                 if (dep->l_reserved)
 184                   /* This object is already in the search list we are
 185                      building.  Don't add a duplicate pointer.
 186                      Release the reference just added by
 187                      _dl_map_object.  */
 188                   --dep->l_opencount;
 189                 else
 190                   {
 191                     /* Append DEP to the unique list.  */
 192                     newp->done = 0;
 193                     newp->unique = NULL;
 194                     utail->unique = newp;
 195                     utail = newp;
 196                     ++nlist;
 197                     /* Set the mark bit that says it's already in the list.  */
 198                     dep->l_reserved = 1;
 199                   }
 200               }
 201             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 202               {
 203                 char *errstring;
 204                 struct list *newp;
 205
 206                 if (d->d_tag == DT_AUXILIARY)
 207                   {
 208                     /* Store the tag in the argument structure.  */
 209                     args.d = d;
 210
 211                     /* Say that we are about to load an auxiliary library.  */
 212                     if (_dl_debug_libs)
 213                       _dl_debug_message (1, "load auxiliary object=",
 214                                          strtab + d->d_un.d_val,
 215                                          " requested by file=",
 216                                          l->l_name[0]
 217                                          ? l->l_name : _dl_argv[0],
 218                                          "\n", NULL);
 219
 220                     /* We must be prepared that the addressed shared
 221                        object is not available.  */
 222                     if (_dl_catch_error (&errstring, openaux, &args))
 223                       {
 224                         /* We are not interested in the error message.  */
 225                         assert (errstring != NULL);
 226                         free (errstring);
 227
 228                         /* Simply ignore this error and continue the work.  */
 229                         continue;
 230                       }
 231                   }
 232                 else
 233                   {
 234                     /* Say that we are about to load an auxiliary library.  */
 235                     if (_dl_debug_libs)
 236                       _dl_debug_message (1, "load filtered object=",
 237                                          strtab + d->d_un.d_val,
 238                                          " requested by file=",
 239                                          l->l_name[0]
 240                                          ? l->l_name : _dl_argv[0],
 241                                          "\n", NULL);
 242
 243                     /* For filter objects the dependency must be available.  */
 244                     args.aux = _dl_map_object (l, strtab + d->d_un.d_val, 0,
 245                                                (l->l_type == lt_executable
 246                                                 ? lt_library : l->l_type),
 247                                                trace_mode);
 248                   }
 249
 250                 /* The auxiliary object is actually available.
 251                    Incorporate the map in all the lists.  */
 252
 253                 /* Allocate new entry.  This always has to be done.  */
 254                 newp = alloca (sizeof (struct list));
 255
 256                 /* Copy the content of the current entry over.  */
 257                 orig->dup = memcpy (newp, orig, sizeof (*newp));
 258
 259                 /* Initialize new entry.  */
 260                 orig->done = 0;
 261                 orig->map = args.aux;
 262
 263                 /* We must handle two situations here: the map is new,
 264                    so we must add it in all three lists.  If the map
 265                    is already known, we have two further possibilities:
 266                    - if the object is before the current map in the
 267                    search list, we do nothing.  It is already found
 268                    early
 269                    - if the object is after the current one, we must
 270                    move it just before the current map to make sure
 271                    the symbols are found early enough
 272                 */
 273                 if (args.aux->l_reserved)
 274                   {
 275                     /* The object is already somewhere in the list.
 276                        Locate it first.  */
 277                     struct list *late;
 278
 279                     /* This object is already in the search list we
 280                        are building.  Don't add a duplicate pointer.
 281                        Release the reference just added by
 282                        _dl_map_object.  */
 283                     --args.aux->l_opencount;
 284
 285                     for (late = orig; late->unique; late = late->unique)
 286                       if (late->unique->map == args.aux)
 287                         break;
 288
 289                     if (late->unique)
 290                       {
 291                         /* The object is somewhere behind the current
 292                            position in the search path.  We have to
 293                            move it to this earlier position.  */
 294                         orig->unique = newp;
 295
 296                         /* Now remove the later entry from the unique list.  */
 297                         late->unique = late->unique->unique;
 298
 299                         /* We must move the earlier in the chain.  */
 300                         if (args.aux->l_prev)
 301                           args.aux->l_prev->l_next = args.aux->l_next;
 302                         if (args.aux->l_next)
 303                           args.aux->l_next->l_prev = args.aux->l_prev;
 304
 305                         args.aux->l_prev = newp->map->l_prev;
 306                         newp->map->l_prev = args.aux;
 307                         if (args.aux->l_prev != NULL)
 308                           args.aux->l_prev->l_next = args.aux;
 309                         args.aux->l_next = newp->map;
 310                       }
 311                     else
 312                       {
 313                         /* The object must be somewhere earlier in the
 314                            list.  That's good, we only have to insert
 315                            an entry for the duplicate list.  */
 316                         orig->unique = NULL;    /* Never used.  */
 317
 318                         /* Now we have a problem.  The element
 319                            pointing to ORIG in the unique list must
 320                            point to NEWP now.  This is the only place
 321                            where we need this backreference and this
 322                            situation is really not that frequent.  So
 323                            we don't use a double-linked list but
 324                            instead search for the preceding element.  */
 325                         late = known;
 326                         while (late->unique != orig)
 327                           late = late->unique;
 328                         late->unique = newp;
 329                       }
 330                   }
 331                 else
 332                   {
 333                     /* This is easy.  We just add the symbol right here.  */
 334                     orig->unique = newp;
 335                     ++nlist;
 336                     /* Set the mark bit that says it's already in the list.  */
 337                     args.aux->l_reserved = 1;
 338
 339                     /* The only problem is that in the double linked
 340                        list of all objects we don't have this new
 341                        object at the correct place.  Correct this here.  */
 342                     if (args.aux->l_prev)
 343                       args.aux->l_prev->l_next = args.aux->l_next;
 344                     if (args.aux->l_next)
 345                       args.aux->l_next->l_prev = args.aux->l_prev;
 346
 347                     args.aux->l_prev = newp->map->l_prev;
 348                     newp->map->l_prev = args.aux;
 349                     if (args.aux->l_prev != NULL)
 350                       args.aux->l_prev->l_next = args.aux;
 351                     args.aux->l_next = newp->map;
 352                   }
 353
 354                 /* Move the tail pointers if necessary.  */
 355                 if (orig == utail)
 356                   utail = newp;
 357                 if (orig == dtail)
 358                   dtail = newp;
 359
 360                 /* Move on the insert point.  */
 361                 orig = newp;
 362
 363                 /* We always add an entry to the duplicate list.  */
 364                 ++nduplist;
 365               }
 366         }
 367       else
 368         /* Mark as processed.  */
 369         runp->done = 1;
 370
 371       /* If we have no auxiliary objects just go on to the next map.  */
 372       if (runp->done)
 373         do
 374           runp = runp->unique;
 375         while (runp != NULL && runp->done);
 376     }
 377
 378   /* Store the search list we built in the object.  It will be used for
 379      searches in the scope of this object.  */
 380   map->l_searchlist.r_list = malloc (nlist * sizeof (struct link_map *));
 381   if (map->l_searchlist.r_list == NULL)
 382     _dl_signal_error (ENOMEM, map->l_name,
 383                       "cannot allocate symbol search list");
 384   map->l_searchlist.r_nlist = nlist;
 385
 386   for (nlist = 0, runp = known; runp; runp = runp->unique)
 387     {
 388       if (trace_mode && runp->map->l_opencount == 0)
 389         /* This can happen when we trace the loading.  */
 390         --map->l_searchlist.r_nlist;
 391       else
 392         map->l_searchlist.r_list[nlist++] = runp->map;
 393
 394       /* Now clear all the mark bits we set in the objects on the search list
 395          to avoid duplicates, so the next call starts fresh.  */
 396       runp->map->l_reserved = 0;
 397     }
 398
 399   map->l_searchlist.r_nduplist = nduplist;
 400   if (nlist == nduplist)
 401     map->l_searchlist.r_duplist = map->l_searchlist.r_list;
 402   else
 403     {
 404       unsigned int cnt;
 405
 406       map->l_searchlist.r_duplist = malloc (nduplist
 407                                             * sizeof (struct link_map *));
 408       if (map->l_searchlist.r_duplist == NULL)
 409         _dl_signal_error (ENOMEM, map->l_name,
 410                           "cannot allocate symbol search list");
 411
 412       for (cnt = 0, runp = known; runp; runp = runp->dup)
 413         if (trace_mode && runp->map->l_opencount == 0)
 414           /* This can happen when we trace the loading.  */
 415           --map->l_searchlist.r_nduplist;
 416         else
 417           map->l_searchlist.r_duplist[cnt++] = runp->map;
 418     }
 419
 420   /* Now that all this succeeded put the objects in the global scope if
 421      this is necessary.  We put the original object and all the dependencies
 422      in the global scope.  If an object is already loaded and not in the
 423      global scope we promote it.  */
 424   if (global_scope)
 425     {
 426       unsigned int cnt;
 427       struct link_map **new_global;
 428
 429       /* Count the objects we have to put in the global scope.  */
 430       for (cnt = 0; cnt < nlist; ++cnt)
 431         if (map->l_searchlist.r_list[cnt]->l_global == 0)
 432           ++to_add;
 433
 434       /* The symbols of the new objects and its dependencies are to be
 435          introduced into the global scope that will be used to resolve
 436          references from other dynamically-loaded objects.
 437
 438          The global scope is the searchlist in the main link map.  We
 439          extend this list if necessary.  There is one problem though:
 440          since this structure was allocated very early (before the libc
 441          is loaded) the memory it uses is allocated by the malloc()-stub
 442          in the ld.so.  When we come here these functions are not used
 443          anymore.  Instead the malloc() implementation of the libc is
 444          used.  But this means the block from the main map cannot be used
 445          in an realloc() call.  Therefore we allocate a completely new
 446          array the first time we have to add something to the locale scope.  */
 447
 448       if (_dl_global_scope_alloc == 0)
 449         {
 450           /* This is the first dynamic object given global scope.  */
 451           _dl_global_scope_alloc = _dl_main_searchlist->r_nlist + to_add + 8;
 452           new_global = (struct link_map **)
 453             malloc (_dl_global_scope_alloc * sizeof (struct link_map *));
 454           if (new_global == NULL)
 455             {
 456               _dl_global_scope_alloc = 0;
 457             nomem:
 458               _dl_signal_error (ENOMEM, map->l_libname->name,
 459                                 "cannot extend global scope");
 460               return 0;
 461             }
 462
 463           /* Copy over the old entries.  */
 464           memcpy (new_global, _dl_main_searchlist->r_list,
 465                   (_dl_main_searchlist->r_nlist * sizeof (struct link_map *)));
 466
 467           _dl_main_searchlist->r_list = new_global;
 468         }
 469       else if (_dl_main_searchlist->r_nlist + to_add > _dl_global_scope_alloc)
 470         {
 471           /* We have to extend the existing array of link maps in the
 472              main map.  */
 473           new_global = (struct link_map **)
 474             realloc (_dl_main_searchlist->r_list,
 475                      ((_dl_global_scope_alloc + to_add + 8)
 476                       * sizeof (struct link_map *)));
 477           if (new_global == NULL)
 478             goto nomem;
 479
 480           _dl_global_scope_alloc += to_add + 8;
 481           _dl_main_searchlist->r_list = new_global;
 482         }
 483
 484       /* Now add the new entries.  */
 485       to_add = 0;
 486       for (cnt = 0; cnt < nlist; ++cnt)
 487         if (map->l_searchlist.r_list[cnt]->l_global == 0)
 488           {
 489             _dl_main_searchlist->r_list[_dl_main_searchlist->r_nlist + to_add]
 490               = map->l_searchlist.r_list[cnt];
 491             ++to_add;
 492           }
 493
 494       /* XXX Do we have to add something to r_dupsearchlist???  --drepper */
 495     }
 496
 497   return to_add;
 498 }