elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996, 1997, 1998 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
  97   inline void preload (struct link_map *map)
  98     {
  99       known[nlist].done = 0;
 100       known[nlist].map = map;
 101
 102       known[nlist].unique = &known[nlist + 1];
 103       known[nlist].dup = &known[nlist + 1];
 104
 105       ++nlist;
 106       /* We use `l_reserved' as a mark bit to detect objects we have
 107          already put in the search list and avoid adding duplicate
 108          elements later in the list.  */
 109       map->l_reserved = 1;
 110     }
 111
 112   /* No loaded object so far.  */
 113   nlist = 0;
 114
 115   /* First load MAP itself.  */
 116   preload (map);
 117
 118   /* Add the preloaded items after MAP but before any of its dependencies.  */
 119   for (i = 0; i < npreloads; ++i)
 120     preload (preloads[i]);
 121
 122   /* Terminate the lists.  */
 123   known[nlist - 1].unique = NULL;
 124   known[nlist - 1].dup = NULL;
 125
 126   /* Pointer to last unique object.  */
 127   utail = &known[nlist - 1];
 128   /* Pointer to last loaded object.  */
 129   dtail = &known[nlist - 1];
 130
 131   /* Until now we have the same number of libraries in the normal and
 132      the list with duplicates.  */
 133   nduplist = nlist;
 134
 135   /* Process each element of the search list, loading each of its
 136      auxiliary objects and immediate dependencies.  Auxiliary objects
 137      will be added in the list before the object itself and
 138      dependencies will be appended to the list as we step through it.
 139      This produces a flat, ordered list that represents a
 140      breadth-first search of the dependency tree.
 141
 142      The whole process is complicated by the fact that we better
 143      should use alloca for the temporary list elements.  But using
 144      alloca means we cannot use recursive function calls.  */
 145   for (runp = known; runp; )
 146     {
 147       struct link_map *l = runp->map;
 148
 149       if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 150         {
 151           const char *strtab = ((void *) l->l_addr
 152                                 + 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       map->l_searchlist.r_list[nlist++] = runp->map;
 389
 390       /* Now clear all the mark bits we set in the objects on the search list
 391          to avoid duplicates, so the next call starts fresh.  */
 392       runp->map->l_reserved = 0;
 393     }
 394
 395   map->l_searchlist.r_nduplist = nduplist;
 396   if (nlist == nduplist)
 397     map->l_searchlist.r_duplist = map->l_searchlist.r_list;
 398   else
 399     {
 400       unsigned int cnt;
 401
 402       map->l_searchlist.r_duplist = malloc (nduplist
 403                                             * sizeof (struct link_map *));
 404       if (map->l_searchlist.r_duplist == NULL)
 405         _dl_signal_error (ENOMEM, map->l_name,
 406                           "cannot allocate symbol search list");
 407
 408       for (cnt = 0, runp = known; runp; runp = runp->dup)
 409         map->l_searchlist.r_duplist[cnt++] = runp->map;
 410     }
 411
 412   /* Now that all this succeeded put the objects in the global scope if
 413      this is necessary.  We put the original object and all the dependencies
 414      in the global scope.  If an object is already loaded and not in the
 415      global scope we promote it.  */
 416   if (global_scope)
 417     {
 418       unsigned int cnt;
 419       unsigned int to_add = 0;
 420       struct link_map **new_global;
 421
 422       /* Count the objects we have to put in the global scope.  */
 423       for (cnt = 0; cnt < nlist; ++cnt)
 424         if (map->l_searchlist.r_list[cnt]->l_global == 0)
 425           ++to_add;
 426
 427       /* The symbols of the new objects and its dependencies are to be
 428          introduced into the global scope that will be used to resolve
 429          references from other dynamically-loaded objects.
 430
 431          The global scope is the searchlist in the main link map.  We
 432          extend this list if necessary.  There is one problem though:
 433          since this structure was allocated very early (before the libc
 434          is loaded) the memory it uses is allocated by the malloc()-stub
 435          in the ld.so.  When we come here these functions are not used
 436          anymore.  Instead the malloc() implementation of the libc is
 437          used.  But this means the block from the main map cannot be used
 438          in an realloc() call.  Therefore we allocate a completely new
 439          array the first time we have to add something to the locale scope.  */
 440
 441       if (_dl_global_scope_alloc == 0)
 442         {
 443           /* This is the first dynamic object given global scope.  */
 444           _dl_global_scope_alloc = _dl_main_searchlist->r_nlist + to_add + 8;
 445           new_global = (struct link_map **)
 446             malloc (_dl_global_scope_alloc * sizeof (struct link_map *));
 447           if (new_global == NULL)
 448             {
 449               _dl_global_scope_alloc = 0;
 450             nomem:
 451               _dl_signal_error (ENOMEM, map->l_libname->name,
 452                                 "cannot extend global scope");
 453               return 0;
 454             }
 455
 456           /* Copy over the old entries.  */
 457           memcpy (new_global, _dl_main_searchlist->r_list,
 458                   (_dl_main_searchlist->r_nlist * sizeof (struct link_map *)));
 459
 460           _dl_main_searchlist->r_list = new_global;
 461         }
 462       else if (_dl_main_searchlist->r_nlist + to_add > _dl_global_scope_alloc)
 463         {
 464           /* We have to extend the existing array of link maps in the
 465              main map.  */
 466           new_global = (struct link_map **)
 467             realloc (_dl_main_searchlist->r_list,
 468                      ((_dl_global_scope_alloc + to_add + 8)
 469                       * sizeof (struct link_map *)));
 470           if (new_global == NULL)
 471             goto nomem;
 472
 473           _dl_global_scope_alloc += to_add + 8;
 474           _dl_main_searchlist->r_list = new_global;
 475         }
 476
 477       /* Now add the new entries.  */
 478       to_add = 0;
 479       for (cnt = 0; cnt < nlist; ++cnt)
 480         if (map->l_searchlist.r_list[cnt]->l_global == 0)
 481           {
 482             map->l_searchlist.r_list[cnt]->l_global = 1;
 483             _dl_main_searchlist->r_list[_dl_main_searchlist->r_nlist + to_add]
 484               = map->l_searchlist.r_list[cnt];
 485             ++to_add;
 486           }
 487
 488       /* XXX Do we have to add something to r_dupsearchlist???  --drepper */
 489
 490       return to_add;
 491     }
 492
 493   return 0;
 494 }