elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996, 1997 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 <link.h>
  21 #include <errno.h>
  22 #include <dlfcn.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <assert.h>
  26
  27 /* Whether an shared object references one or more auxiliary objects
  28    is signaled by the AUXTAG entry in l_info.  */
  29 #define AUXTAG  (DT_NUM + DT_PROCNUM + DT_VERSIONTAGNUM \
  30                  + DT_EXTRATAGIDX (DT_AUXILIARY))
  31
  32
  33 /* When loading auxiliary objects we must ignore errors.  It's ok if
  34    an object is missing.  */
  35 struct openaux_args
  36   {
  37     /* The arguments to openaux.  */
  38     struct link_map *map;
  39     int trace_mode;
  40     const char *strtab;
  41     const ElfW(Dyn) *d;
  42
  43     /* The return value of openaux.  */
  44     struct link_map *aux;
  45   };
  46
  47 static void
  48 openaux (void *a)
  49 {
  50   struct openaux_args *args = (struct openaux_args *) a;
  51
  52   args->aux = _dl_map_object (args->map, args->strtab + args->d->d_un.d_val,
  53                               (args->map->l_type == lt_executable
  54                                ? lt_library : args->map->l_type),
  55                               args->trace_mode);
  56 }
  57
  58
  59
  60 /* We use a very special kind of list to track the two kinds paths
  61    through the list of loaded shared objects.  We have to
  62
  63    - produce a flat list with unique members of all involved objects
  64
  65    - produce a flat list of all shared objects.
  66 */
  67 struct list
  68   {
  69     int done;                   /* Nonzero if this map was processed.  */
  70     struct link_map *map;       /* The data.  */
  71
  72     struct list *unique;        /* Elements for normal list.  */
  73     struct list *dup;           /* Elements in complete list.  */
  74   };
  75
  76
  77 void
  78 _dl_map_object_deps (struct link_map *map,
  79                      struct link_map **preloads, unsigned int npreloads,
  80                      int trace_mode)
  81 {
  82   struct list known[1 + npreloads + 1];
  83   struct list *runp, *head, *utail, *dtail;
  84   unsigned int nlist, nduplist, i;
  85
  86   inline void preload (struct link_map *map)
  87     {
  88       known[nlist].done = 0;
  89       known[nlist].map = map;
  90
  91       known[nlist].unique = &known[nlist + 1];
  92       known[nlist].dup = &known[nlist + 1];
  93
  94       ++nlist;
  95       /* We use `l_reserved' as a mark bit to detect objects we have
  96          already put in the search list and avoid adding duplicate
  97          elements later in the list.  */
  98       map->l_reserved = 1;
  99     }
 100
 101   /* No loaded object so far.  */
 102   nlist = 0;
 103
 104   /* First load MAP itself.  */
 105   preload (map);
 106
 107   /* Add the preloaded items after MAP but before any of its dependencies.  */
 108   for (i = 0; i < npreloads; ++i)
 109     preload (preloads[i]);
 110
 111   /* Terminate the lists.  */
 112   known[nlist - 1].unique = NULL;
 113   known[nlist - 1].dup = NULL;
 114
 115   /* Pointer to the first member of the unique and duplicate list.  */
 116   head = known;
 117
 118   /* Pointer to last unique object.  */
 119   utail = &known[nlist - 1];
 120   /* Pointer to last loaded object.  */
 121   dtail = &known[nlist - 1];
 122
 123   /* Until now we have the same number of libraries in the normal and
 124      the list with duplicates.  */
 125   nduplist = nlist;
 126
 127   /* Process each element of the search list, loading each of its
 128      auxiliary objects and immediate dependencies.  Auxiliary objects
 129      will be added in the list before the object itself and
 130      dependencies will be appended to the list as we step through it.
 131      This produces a flat, ordered list that represents a
 132      breadth-first search of the dependency tree.
 133
 134      The whole process is complicated by the fact that we better
 135      should use alloca for the temporary list elements.  But using
 136      alloca means we cannot use recursive function calls.  */
 137   for (runp = known; runp; )
 138     {
 139       struct link_map *l = runp->map;
 140
 141       if (l->l_info[AUXTAG] || l->l_info[DT_NEEDED])
 142         {
 143           const char *strtab = ((void *) l->l_addr
 144                                 + l->l_info[DT_STRTAB]->d_un.d_ptr);
 145           struct openaux_args args;
 146           struct list *orig;
 147           const ElfW(Dyn) *d;
 148
 149           /* Mark map as processed.  */
 150           runp->done = 1;
 151
 152           args.strtab = strtab;
 153           args.map = l;
 154           args.trace_mode = trace_mode;
 155           orig = runp;
 156
 157           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 158             if (d->d_tag == DT_NEEDED)
 159               {
 160                 /* Map in the needed object.  */
 161                 struct link_map *dep
 162                   = _dl_map_object (l, strtab + d->d_un.d_val,
 163                                     l->l_type == lt_executable ? lt_library :
 164                                     l->l_type, trace_mode);
 165                 /* Allocate new entry.  */
 166                 struct list *newp = alloca (sizeof (struct list));
 167
 168                 /* Add it in any case to the duplicate list.  */
 169                 newp->map = dep;
 170                 newp->dup = NULL;
 171                 dtail->dup = newp;
 172                 dtail = newp;
 173                 ++nduplist;
 174
 175                 if (dep->l_reserved)
 176                   /* This object is already in the search list we are
 177                      building.  Don't add a duplicate pointer.
 178                      Release the reference just added by
 179                      _dl_map_object.  */
 180                   --dep->l_opencount;
 181                 else
 182                   {
 183                     /* Append DEP to the unique list.  */
 184                     newp->done = 0;
 185                     newp->unique = NULL;
 186                     utail->unique = newp;
 187                     utail = newp;
 188                     ++nlist;
 189                     /* Set the mark bit that says it's already in the list.  */
 190                     dep->l_reserved = 1;
 191                   }
 192               }
 193             else if (d->d_tag == DT_AUXILIARY)
 194               {
 195                 char *errstring;
 196                 const char *objname;
 197
 198                 /* Store the tag in the argument structure.  */
 199                 args.d = d;
 200
 201                 if (_dl_catch_error (&errstring, &objname, openaux, &args))
 202                   {
 203                     /* We are not interested in the error message.  */
 204                     assert (errstring != NULL);
 205                     free (errstring);
 206                   }
 207                 else
 208                   {
 209                     /* The auxiliary object is actually available.
 210                        Incorporate the map in all the lists.  */
 211
 212                     /* Allocate new entry.  This always has to be done.  */
 213                     struct list *newp = alloca (sizeof (struct list));
 214
 215                     /* Copy the content of the current entry over.  */
 216                     memcpy (newp, orig, sizeof (*newp));
 217
 218                     /* Initialize new entry.  */
 219                     orig->done = 0;
 220                     orig->map = args.aux;
 221                     orig->dup = newp;
 222
 223                     /* We must handle two situations here: the map is new,
 224                        so we must add it in all three lists.  If the map
 225                        is already known, we have two further possibilities:
 226                        - if the object is before the current map in the
 227                          search list, we do nothing.  It is already found
 228                          early
 229                        - if the object is after the current one, we must
 230                          move it just before the current map to make sure
 231                          the symbols are found early enough
 232                     */
 233                     if (args.aux->l_reserved)
 234                       {
 235                         /* The object is already somewhere in the
 236                            list.  Locate it first.  */
 237                         struct list *late;
 238
 239                         /* This object is already in the search list
 240                            we are building.  Don't add a duplicate
 241                            pointer.  Release the reference just added
 242                            by _dl_map_object.  */
 243                         --args.aux->l_opencount;
 244
 245                         for (late = orig; late->unique; late = late->unique)
 246                           if (late->unique->map == args.aux)
 247                             break;
 248
 249                         if (late->unique)
 250                           {
 251                             /* The object is somewhere behind the current
 252                                position in the search path.  We have to
 253                                move it to this earlier position.  */
 254                             orig->unique = newp;
 255
 256                             /* Now remove the later entry from the unique
 257                                list.  */
 258                             late->unique = late->unique->unique;
 259
 260                             /* We must move the earlier in the chain.  */
 261                             if (args.aux->l_prev)
 262                               args.aux->l_prev->l_next = args.aux->l_next;
 263                             if (args.aux->l_next)
 264                               args.aux->l_next->l_prev = args.aux->l_prev;
 265
 266                             args.aux->l_prev = newp->map->l_prev;
 267                             newp->map->l_prev = args.aux;
 268                             if (args.aux->l_prev != NULL)
 269                               args.aux->l_prev->l_next = args.aux;
 270                             args.aux->l_next = newp->map;
 271                           }
 272                         else
 273                           {
 274                             /* The object must be somewhere earlier in
 275                                the list.  That's good, we only have to
 276                                insert an entry for the duplicate list.  */
 277                             orig->unique = NULL;        /* Never used.  */
 278
 279                             /* Now we have a problem.  The element pointing
 280                                to ORIG in the unique list must point to
 281                                NEWP now.  This is the only place where we
 282                                need this backreference and this situation
 283                                is really not that frequent.  So we don't
 284                                use a double-linked list but instead search
 285                                for the preceding element.  */
 286                             late = head;
 287                             while (late->unique != orig)
 288                               late = late->unique;
 289                             late->unique = newp;
 290                           }
 291                       }
 292                     else
 293                       {
 294                         /* This is easy.  We just add the symbol right
 295                            here.  */
 296                         orig->unique = newp;
 297                         ++nlist;
 298                         /* Set the mark bit that says it's already in
 299                            the list.  */
 300                         args.aux->l_reserved = 1;
 301
 302                         /* The only problem is that in the double linked
 303                            list of all objects we don't have this new
 304                            object at the correct place.  Correct this
 305                            here.  */
 306                         if (args.aux->l_prev)
 307                           args.aux->l_prev->l_next = args.aux->l_next;
 308                         if (args.aux->l_next)
 309                           args.aux->l_next->l_prev = args.aux->l_prev;
 310
 311                         args.aux->l_prev = newp->map->l_prev;
 312                         newp->map->l_prev = args.aux;
 313                         if (args.aux->l_prev != NULL)
 314                           args.aux->l_prev->l_next = args.aux;
 315                         args.aux->l_next = newp->map;
 316                       }
 317
 318                     /* Move the tail pointers if necessary.  */
 319                     if (orig == utail)
 320                       utail = newp;
 321                     if (orig == dtail)
 322                       dtail = newp;
 323
 324                     /* Move on the insert point.  */
 325                     orig = newp;
 326
 327                     /* We always add an entry to the duplicate list.  */
 328                     ++nduplist;
 329                   }
 330               }
 331         }
 332       else
 333         /* Mark as processed.  */
 334         runp->done = 1;
 335
 336       /* If we have no auxiliary objects just go on to the next map.  */
 337       if (runp->done)
 338         do
 339           runp = runp->unique;
 340         while (runp && runp->done);
 341     }
 342
 343   /* Store the search list we built in the object.  It will be used for
 344      searches in the scope of this object.  */
 345   map->l_searchlist = malloc (nlist * sizeof (struct link_map *));
 346   if (map->l_searchlist == NULL)
 347     _dl_signal_error (ENOMEM, map->l_name,
 348                       "cannot allocate symbol search list");
 349   map->l_nsearchlist = nlist;
 350
 351   for (nlist = 0, runp = head; runp; runp = runp->unique)
 352     {
 353       map->l_searchlist[nlist++] = runp->map;
 354
 355       /* Now clear all the mark bits we set in the objects on the search list
 356          to avoid duplicates, so the next call starts fresh.  */
 357       runp->map->l_reserved = 0;
 358     }
 359
 360   map->l_ndupsearchlist = nduplist;
 361   if (nlist == nduplist)
 362     map->l_dupsearchlist = map->l_searchlist;
 363   else
 364     {
 365       map->l_dupsearchlist = malloc (nduplist * sizeof (struct link_map *));
 366       if (map->l_dupsearchlist == NULL)
 367         _dl_signal_error (ENOMEM, map->l_name,
 368                           "cannot allocate symbol search list");
 369
 370       for (nlist = 0, runp = head; runp; runp = runp->dup)
 371         map->l_dupsearchlist[nlist++] = runp->map;
 372     }
 373 }