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 <stdlib.h>
  24 #include <string.h>
  25 #include <unistd.h>
  26 #include <sys/param.h>
  27 #include <ldsodefs.h>
  28
  29 #include <dl-dst.h>
  30
  31 /* Whether an shared object references one or more auxiliary objects
  32    is signaled by the AUXTAG entry in l_info.  */
  33 #define AUXTAG  (DT_NUM + DT_PROCNUM + DT_VERSIONTAGNUM \
  34                  + DT_EXTRATAGIDX (DT_AUXILIARY))
  35 /* Whether an shared object references one or more auxiliary objects
  36    is signaled by the AUXTAG entry in l_info.  */
  37 #define FILTERTAG (DT_NUM + DT_PROCNUM + DT_VERSIONTAGNUM \
  38                    + DT_EXTRATAGIDX (DT_FILTER))
  39
  40 /* This is zero at program start to signal that the global scope map is
  41    allocated by rtld.  Later it keeps the size of the map.  It might be
  42    reset if in _dl_close if the last global object is removed.  */
  43 size_t _dl_global_scope_alloc;
  44
  45 extern size_t _dl_platformlen;
  46
  47 /* When loading auxiliary objects we must ignore errors.  It's ok if
  48    an object is missing.  */
  49 struct openaux_args
  50   {
  51     /* The arguments to openaux.  */
  52     struct link_map *map;
  53     int trace_mode;
  54     const char *strtab;
  55     const char *name;
  56
  57     /* The return value of openaux.  */
  58     struct link_map *aux;
  59   };
  60
  61 static void
  62 openaux (void *a)
  63 {
  64   struct openaux_args *args = (struct openaux_args *) a;
  65
  66   args->aux = _dl_map_object (args->map, args->name, 0,
  67                               (args->map->l_type == lt_executable
  68                                ? lt_library : args->map->l_type),
  69                               args->trace_mode);
  70 }
  71
  72
  73
  74 /* We use a very special kind of list to track the two kinds paths
  75    through the list of loaded shared objects.  We have to
  76
  77    - produce a flat list with unique members of all involved objects
  78
  79    - produce a flat list of all shared objects.
  80 */
  81 struct list
  82   {
  83     int done;                   /* Nonzero if this map was processed.  */
  84     struct link_map *map;       /* The data.  */
  85
  86     struct list *unique;        /* Elements for normal list.  */
  87     struct list *dup;           /* Elements in complete list.  */
  88   };
  89
  90
  91 /* Macro to expand DST.  It is an macro since we use `alloca'.  */
  92 #define expand_dst(l, str, fatal) \
  93   ({                                                                          \
  94     const char *__str = (str);                                                \
  95     const char *__result = __str;                                             \
  96     size_t __cnt = DL_DST_COUNT(__str, 0);                                    \
  97                                                                               \
  98     if (__cnt != 0)                                                           \
  99       {                                                                       \
 100         char *__newp;                                                         \
 101                                                                               \
 102         /* DST must not appear in SUID/SGID programs.  */                     \
 103         if (__libc_enable_secure)                                             \
 104           _dl_signal_error (0, __str,                                         \
 105                             "DST not allowed in SUID/SGID programs");         \
 106                                                                               \
 107         __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str),  \
 108                                                    __cnt));                   \
 109                                                                               \
 110         __result = DL_DST_SUBSTITUTE (l, __str, __newp, 0);                   \
 111                                                                               \
 112         if (*__result == '\0')                                                \
 113           {                                                                   \
 114             /* The replacement for the DST is not known.  We can't            \
 115                processed.  */                                                 \
 116             if (fatal)                                                        \
 117               _dl_signal_error (0, __str,                                     \
 118                                 "empty dynamics string token substitution");  \
 119             else                                                              \
 120               {                                                               \
 121                 /* This is for DT_AUXILIARY.  */                              \
 122                 if (__builtin_expect (_dl_debug_libs, 0))                     \
 123                   _dl_debug_message (1, "cannot load auxiliary `", __str,     \
 124                                      "' because of empty dynamic string"      \
 125                                      " token substitution\n", NULL);          \
 126                 continue;                                                     \
 127               }                                                               \
 128           }                                                                   \
 129       }                                                                       \
 130                                                                               \
 131     __result; })
 132
 133
 134 void
 135 internal_function
 136 _dl_map_object_deps (struct link_map *map,
 137                      struct link_map **preloads, unsigned int npreloads,
 138                      int trace_mode)
 139 {
 140   struct list known[1 + npreloads + 1];
 141   struct list *runp, *utail, *dtail;
 142   unsigned int nlist, nduplist, i;
 143
 144   inline void preload (struct link_map *map)
 145     {
 146       known[nlist].done = 0;
 147       known[nlist].map = map;
 148
 149       known[nlist].unique = &known[nlist + 1];
 150       known[nlist].dup = &known[nlist + 1];
 151
 152       ++nlist;
 153       /* We use `l_reserved' as a mark bit to detect objects we have
 154          already put in the search list and avoid adding duplicate
 155          elements later in the list.  */
 156       map->l_reserved = 1;
 157     }
 158
 159   /* No loaded object so far.  */
 160   nlist = 0;
 161
 162   /* First load MAP itself.  */
 163   preload (map);
 164
 165   /* Add the preloaded items after MAP but before any of its dependencies.  */
 166   for (i = 0; i < npreloads; ++i)
 167     preload (preloads[i]);
 168
 169   /* Terminate the lists.  */
 170   known[nlist - 1].unique = NULL;
 171   known[nlist - 1].dup = NULL;
 172
 173   /* Pointer to last unique object.  */
 174   utail = &known[nlist - 1];
 175   /* Pointer to last loaded object.  */
 176   dtail = &known[nlist - 1];
 177
 178   /* Until now we have the same number of libraries in the normal and
 179      the list with duplicates.  */
 180   nduplist = nlist;
 181
 182   /* Process each element of the search list, loading each of its
 183      auxiliary objects and immediate dependencies.  Auxiliary objects
 184      will be added in the list before the object itself and
 185      dependencies will be appended to the list as we step through it.
 186      This produces a flat, ordered list that represents a
 187      breadth-first search of the dependency tree.
 188
 189      The whole process is complicated by the fact that we better
 190      should use alloca for the temporary list elements.  But using
 191      alloca means we cannot use recursive function calls.  */
 192   for (runp = known; runp; )
 193     {
 194       struct link_map *l = runp->map;
 195       struct link_map **needed = NULL;
 196       unsigned int nneeded = 0;
 197
 198       /* Unless otherwise stated, this object is handled.  */
 199       runp->done = 1;
 200
 201       /* Allocate a temporary record to contain the references to the
 202          dependencies of this object.  */
 203       if (l->l_searchlist.r_list == NULL && 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                 /* Allocate new entry.  */
 225                 struct list *newp;
 226                 /* Object name.  */
 227                 const char *name;
 228
 229                 /* Recognize DSTs.  */
 230                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 231
 232                 dep = _dl_map_object (l, name, 0,
 233                                       l->l_type == lt_executable ? lt_library :
 234                                       l->l_type, trace_mode);
 235
 236                 /* Add it in any case to the duplicate list.  */
 237                 newp = alloca (sizeof (struct list));
 238                 newp->map = dep;
 239                 newp->dup = NULL;
 240                 dtail->dup = newp;
 241                 dtail = newp;
 242                 ++nduplist;
 243
 244                 if (dep->l_reserved)
 245                   /* This object is already in the search list we are
 246                      building.  Don't add a duplicate pointer.
 247                      Release the reference just added by
 248                      _dl_map_object.  */
 249                   --dep->l_opencount;
 250                 else
 251                   {
 252                     /* Append DEP to the unique list.  */
 253                     newp->done = 0;
 254                     newp->unique = NULL;
 255                     utail->unique = newp;
 256                     utail = newp;
 257                     ++nlist;
 258                     /* Set the mark bit that says it's already in the list.  */
 259                     dep->l_reserved = 1;
 260                   }
 261
 262                 /* Remember this dependency.  */
 263                 if (needed != NULL)
 264                   needed[nneeded++] = dep;
 265               }
 266             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 267               {
 268                 char *errstring;
 269                 struct list *newp;
 270                 /* Object name.  */
 271                 const char *name;
 272
 273                 /* Recognize DSTs.  */
 274                 name = expand_dst (l, strtab + d->d_un.d_val,
 275                                    d->d_tag == DT_AUXILIARY);
 276
 277                 if (d->d_tag == DT_AUXILIARY)
 278                   {
 279                     /* Store the tag in the argument structure.  */
 280                     args.name = name;
 281
 282                     /* Say that we are about to load an auxiliary library.  */
 283                     if (__builtin_expect (_dl_debug_libs, 0))
 284                       _dl_debug_message (1, "load auxiliary object=",
 285                                          name, " requested by file=",
 286                                          l->l_name[0]
 287                                          ? l->l_name : _dl_argv[0],
 288                                          "\n", NULL);
 289
 290                     /* We must be prepared that the addressed shared
 291                        object is not available.  */
 292                     if (_dl_catch_error (&errstring, openaux, &args))
 293                       {
 294                         /* We are not interested in the error message.  */
 295                         assert (errstring != NULL);
 296                         free (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);
 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                        Release the reference just added by
 358                        _dl_map_object.  */
 359                     --args.aux->l_opencount;
 360
 361                     for (late = newp; late->unique; late = late->unique)
 362                       if (late->unique->map == args.aux)
 363                         break;
 364
 365                     if (late->unique)
 366                       {
 367                         /* The object is somewhere behind the current
 368                            position in the search path.  We have to
 369                            move it to this earlier position.  */
 370                         orig->unique = newp;
 371
 372                         /* Now remove the later entry from the unique list
 373                            and adjust the tail pointer.  */
 374                         if (utail == late->unique)
 375                           utail = late;
 376                         late->unique = late->unique->unique;
 377
 378                         /* We must move the object earlier in the chain.  */
 379                         if (args.aux->l_prev)
 380                           args.aux->l_prev->l_next = args.aux->l_next;
 381                         if (args.aux->l_next)
 382                           args.aux->l_next->l_prev = args.aux->l_prev;
 383
 384                         args.aux->l_prev = newp->map->l_prev;
 385                         newp->map->l_prev = args.aux;
 386                         if (args.aux->l_prev != NULL)
 387                           args.aux->l_prev->l_next = args.aux;
 388                         args.aux->l_next = newp->map;
 389                       }
 390                     else
 391                       {
 392                         /* The object must be somewhere earlier in the
 393                            list.  That's good, we only have to insert
 394                            an entry for the duplicate list.  */
 395                         orig->unique = NULL;    /* Never used.  */
 396
 397                         /* Now we have a problem.  The element
 398                            pointing to ORIG in the unique list must
 399                            point to NEWP now.  This is the only place
 400                            where we need this backreference and this
 401                            situation is really not that frequent.  So
 402                            we don't use a double-linked list but
 403                            instead search for the preceding element.  */
 404                         late = known;
 405                         while (late->unique != orig)
 406                           late = late->unique;
 407                         late->unique = newp;
 408                       }
 409                   }
 410                 else
 411                   {
 412                     /* This is easy.  We just add the symbol right here.  */
 413                     orig->unique = newp;
 414                     ++nlist;
 415                     /* Set the mark bit that says it's already in the list.  */
 416                     args.aux->l_reserved = 1;
 417
 418                     /* The only problem is that in the double linked
 419                        list of all objects we don't have this new
 420                        object at the correct place.  Correct this here.  */
 421                     if (args.aux->l_prev)
 422                       args.aux->l_prev->l_next = args.aux->l_next;
 423                     if (args.aux->l_next)
 424                       args.aux->l_next->l_prev = args.aux->l_prev;
 425
 426                     args.aux->l_prev = newp->map->l_prev;
 427                     newp->map->l_prev = args.aux;
 428                     if (args.aux->l_prev != NULL)
 429                       args.aux->l_prev->l_next = args.aux;
 430                     args.aux->l_next = newp->map;
 431                   }
 432
 433                 /* Move the tail pointers if necessary.  */
 434                 if (orig == utail)
 435                   utail = newp;
 436                 if (orig == dtail)
 437                   dtail = newp;
 438
 439                 /* Move on the insert point.  */
 440                 orig = newp;
 441
 442                 /* We always add an entry to the duplicate list.  */
 443                 ++nduplist;
 444               }
 445         }
 446
 447       /* Terminate the list of dependencies and store the array address.  */
 448       if (needed != NULL)
 449         {
 450           needed[nneeded++] = NULL;
 451
 452           l->l_initfini = malloc (nneeded * sizeof needed[0]);
 453           if (l->l_initfini == NULL)
 454             _dl_signal_error (ENOMEM, map->l_name,
 455                               "cannot allocate dependency list");
 456           memcpy (l->l_initfini, needed, nneeded * sizeof needed[0]);
 457         }
 458
 459       /* If we have no auxiliary objects just go on to the next map.  */
 460       if (runp->done)
 461         do
 462           runp = runp->unique;
 463         while (runp != NULL && runp->done);
 464     }
 465
 466   /* Store the search list we built in the object.  It will be used for
 467      searches in the scope of this object.  */
 468   map->l_searchlist.r_list = malloc ((2 * nlist
 469                                       + (nlist == nduplist ? 0 : nduplist))
 470                                      * sizeof (struct link_map *));
 471   if (map->l_searchlist.r_list == NULL)
 472     _dl_signal_error (ENOMEM, map->l_name,
 473                       "cannot allocate symbol search list");
 474   map->l_searchlist.r_nlist = nlist;
 475
 476   for (nlist = 0, runp = known; runp; runp = runp->unique)
 477     {
 478       if (trace_mode && runp->map->l_opencount == 0)
 479         /* This can happen when we trace the loading.  */
 480         --map->l_searchlist.r_nlist;
 481       else
 482         map->l_searchlist.r_list[nlist++] = runp->map;
 483
 484       /* Now clear all the mark bits we set in the objects on the search list
 485          to avoid duplicates, so the next call starts fresh.  */
 486       runp->map->l_reserved = 0;
 487     }
 488
 489   map->l_searchlist.r_nduplist = nduplist;
 490   if (nlist == nduplist)
 491     map->l_searchlist.r_duplist = map->l_searchlist.r_list;
 492   else
 493     {
 494       unsigned int cnt;
 495
 496       map->l_searchlist.r_duplist = map->l_searchlist.r_list + nlist;
 497
 498       for (cnt = 0, runp = known; runp; runp = runp->dup)
 499         if (trace_mode && runp->map->l_opencount == 0)
 500           /* This can happen when we trace the loading.  */
 501           --map->l_searchlist.r_nduplist;
 502         else
 503           map->l_searchlist.r_duplist[cnt++] = runp->map;
 504     }
 505
 506   /* Now determine the order in which the initialization has to happen.  */
 507   map->l_initfini =
 508     (struct link_map **) memcpy (map->l_searchlist.r_duplist + nduplist,
 509                                  map->l_searchlist.r_list,
 510                                  nlist * sizeof (struct link_map *));
 511   /* We can skip looking for the binary itself which is at the front
 512      of the search list.  Look through the list backward so that circular
 513      dependencies are not changing the order.  */
 514   for (i = 1; i < nlist; ++i)
 515     {
 516       struct link_map *l = map->l_searchlist.r_list[i];
 517       unsigned int j;
 518       unsigned int k;
 519
 520       /* Find the place in the initfini list where the map is currently
 521          located.  */
 522       for (j = 1; map->l_initfini[j] != l; ++j)
 523         ;
 524
 525       /* Find all object for which the current one is a dependency and
 526          move the found object (if necessary) in front.  */
 527       for (k = j + 1; k < nlist; ++k)
 528         {
 529           struct link_map **runp;
 530
 531           runp = map->l_initfini[k]->l_initfini;
 532           if (runp != NULL)
 533             {
 534               while (*runp != NULL)
 535                 if (*runp == l)
 536                   {
 537                     struct link_map *here = map->l_initfini[k];
 538
 539                     /* Move it now.  */
 540                     memmove (&map->l_initfini[j] + 1,
 541                              &map->l_initfini[j],
 542                              (k - j) * sizeof (struct link_map *));
 543                     map->l_initfini[j] = here;
 544
 545                     break;
 546                   }
 547                 else
 548                   ++runp;
 549             }
 550         }
 551     }
 552 }