elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996-2001, 2002 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 Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the 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    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, write to the Free
  17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  18    02111-1307 USA.  */
  19
  20 #include <assert.h>
  21 #include <dlfcn.h>
  22 #include <errno.h>
  23 #include <libintl.h>
  24 #include <stddef.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <unistd.h>
  28 #include <sys/param.h>
  29 #include <ldsodefs.h>
  30
  31 #include <dl-dst.h>
  32
  33 /* Whether an shared object references one or more auxiliary objects
  34    is signaled by the AUXTAG entry in l_info.  */
  35 #define AUXTAG  (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
  36                  + DT_EXTRATAGIDX (DT_AUXILIARY))
  37 /* Whether an shared object references one or more auxiliary objects
  38    is signaled by the AUXTAG entry in l_info.  */
  39 #define FILTERTAG (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
  40                    + DT_EXTRATAGIDX (DT_FILTER))
  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 char *name;
  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->name, 0,
  63                               (args->map->l_type == lt_executable
  64                                ? lt_library : args->map->l_type),
  65                               args->trace_mode, 0);
  66 }
  67
  68 static ptrdiff_t
  69 internal_function
  70 _dl_build_local_scope (struct link_map **list, struct link_map *map)
  71 {
  72   struct link_map **p = list;
  73   struct link_map **q;
  74
  75   *p++ = map;
  76   map->l_reserved = 1;
  77   if (map->l_initfini)
  78     for (q = map->l_initfini + 1; *q; ++q)
  79       if (! (*q)->l_reserved)
  80         p += _dl_build_local_scope (p, *q);
  81   return p - list;
  82 }
  83
  84
  85 /* We use a very special kind of list to track the path
  86    through the list of loaded shared objects.  We have to
  87    produce a flat list with unique members of all involved objects.
  88 */
  89 struct list
  90   {
  91     int done;                   /* Nonzero if this map was processed.  */
  92     struct link_map *map;       /* The data.  */
  93     struct list *next;  /* Elements for normal list.  */
  94   };
  95
  96
  97 /* Macro to expand DST.  It is an macro since we use `alloca'.  */
  98 #define expand_dst(l, str, fatal) \
  99   ({                                                                          \
 100     const char *__str = (str);                                                \
 101     const char *__result = __str;                                             \
 102     size_t __cnt = DL_DST_COUNT(__str, 0);                                    \
 103                                                                               \
 104     if (__cnt != 0)                                                           \
 105       {                                                                       \
 106         char *__newp;                                                         \
 107                                                                               \
 108         /* DST must not appear in SUID/SGID programs.  */                     \
 109         if (__libc_enable_secure)                                             \
 110           _dl_signal_error (0, __str, NULL,                                   \
 111                             N_("DST not allowed in SUID/SGID programs"));     \
 112                                                                               \
 113         __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str),  \
 114                                                    __cnt));                   \
 115                                                                               \
 116         __result = DL_DST_SUBSTITUTE (l, __str, __newp, 0);                   \
 117                                                                               \
 118         if (*__result == '\0')                                                \
 119           {                                                                   \
 120             /* The replacement for the DST is not known.  We can't            \
 121                processed.  */                                                 \
 122             if (fatal)                                                        \
 123               _dl_signal_error (0, __str, NULL, N_("\
 124 empty dynamics string token substitution"));                                  \
 125             else                                                              \
 126               {                                                               \
 127                 /* This is for DT_AUXILIARY.  */                              \
 128                 if (__builtin_expect (GL(dl_debug_mask) & DL_DEBUG_LIBS, 0))  \
 129                   _dl_debug_printf ("cannot load auxiliary `%s' because of"   \
 130                                     "empty dynamic string token "             \
 131                                     "substitution\n", __str);                 \
 132                 continue;                                                     \
 133               }                                                               \
 134           }                                                                   \
 135       }                                                                       \
 136                                                                               \
 137     __result; })
 138
 139
 140 void
 141 internal_function
 142 _dl_map_object_deps (struct link_map *map,
 143                      struct link_map **preloads, unsigned int npreloads,
 144                      int trace_mode)
 145 {
 146   struct list known[1 + npreloads + 1];
 147   struct list *runp, *tail;
 148   unsigned int nlist, i;
 149   /* Object name.  */
 150   const char *name;
 151   int errno_saved;
 152   int errno_reason;
 153   const char *errstring;
 154   const char *objname;
 155
 156   auto inline void preload (struct link_map *map);
 157
 158   inline void preload (struct link_map *map)
 159     {
 160       known[nlist].done = 0;
 161       known[nlist].map = map;
 162       known[nlist].next = &known[nlist + 1];
 163
 164       ++nlist;
 165       /* We use `l_reserved' as a mark bit to detect objects we have
 166          already put in the search list and avoid adding duplicate
 167          elements later in the list.  */
 168       map->l_reserved = 1;
 169     }
 170
 171   /* No loaded object so far.  */
 172   nlist = 0;
 173
 174   /* First load MAP itself.  */
 175   preload (map);
 176
 177   /* Add the preloaded items after MAP but before any of its dependencies.  */
 178   for (i = 0; i < npreloads; ++i)
 179     preload (preloads[i]);
 180
 181   /* Terminate the lists.  */
 182   known[nlist - 1].next = NULL;
 183
 184   /* Pointer to last unique object.  */
 185   tail = &known[nlist - 1];
 186
 187   /* Process each element of the search list, loading each of its
 188      auxiliary objects and immediate dependencies.  Auxiliary objects
 189      will be added in the list before the object itself and
 190      dependencies will be appended to the list as we step through it.
 191      This produces a flat, ordered list that represents a
 192      breadth-first search of the dependency tree.
 193
 194      The whole process is complicated by the fact that we better
 195      should use alloca for the temporary list elements.  But using
 196      alloca means we cannot use recursive function calls.  */
 197   errno_saved = errno;
 198   errno_reason = 0;
 199   errstring = NULL;
 200   errno = 0;
 201   name = NULL;
 202   for (runp = known; runp; )
 203     {
 204       struct link_map *l = runp->map;
 205       struct link_map **needed = NULL;
 206       unsigned int nneeded = 0;
 207
 208       /* Unless otherwise stated, this object is handled.  */
 209       runp->done = 1;
 210
 211       /* Allocate a temporary record to contain the references to the
 212          dependencies of this object.  */
 213       if (l->l_searchlist.r_list == NULL && l->l_initfini == NULL
 214           && l != map && l->l_ldnum > 0)
 215         needed = (struct link_map **) alloca (l->l_ldnum
 216                                               * sizeof (struct link_map *));
 217
 218       if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 219         {
 220           const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);
 221           struct openaux_args args;
 222           struct list *orig;
 223           const ElfW(Dyn) *d;
 224
 225           args.strtab = strtab;
 226           args.map = l;
 227           args.trace_mode = trace_mode;
 228           orig = runp;
 229
 230           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 231             if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
 232               {
 233                 /* Map in the needed object.  */
 234                 struct link_map *dep;
 235                 int err;
 236
 237                 /* Recognize DSTs.  */
 238                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 239                 /* Store the tag in the argument structure.  */
 240                 args.name = name;
 241
 242                 err = _dl_catch_error (&objname, &errstring, openaux, &args);
 243                 if (__builtin_expect (errstring != NULL, 0))
 244                   {
 245                     if (err)
 246                       errno_reason = err;
 247                     else
 248                       errno_reason = -1;
 249                     goto out;
 250                   }
 251                 else
 252                   dep = args.aux;
 253
 254                 if (! dep->l_reserved)
 255                   {
 256                     /* Allocate new entry.  */
 257                     struct list *newp;
 258
 259                     newp = alloca (sizeof (struct list));
 260
 261                     /* Append DEP to the list.  */
 262                     newp->map = dep;
 263                     newp->done = 0;
 264                     newp->next = NULL;
 265                     tail->next = newp;
 266                     tail = newp;
 267                     ++nlist;
 268                     /* Set the mark bit that says it's already in the list.  */
 269                     dep->l_reserved = 1;
 270                   }
 271
 272                 /* Remember this dependency.  */
 273                 if (needed != NULL)
 274                   needed[nneeded++] = dep;
 275               }
 276             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 277               {
 278                 struct list *newp;
 279
 280                 /* Recognize DSTs.  */
 281                 name = expand_dst (l, strtab + d->d_un.d_val,
 282                                    d->d_tag == DT_AUXILIARY);
 283                 /* Store the tag in the argument structure.  */
 284                 args.name = name;
 285
 286                 if (d->d_tag == DT_AUXILIARY)
 287                   {
 288                     int err;
 289
 290                     /* Say that we are about to load an auxiliary library.  */
 291                     if (__builtin_expect (GL(dl_debug_mask) & DL_DEBUG_LIBS,
 292                                           0))
 293                       _dl_debug_printf ("load auxiliary object=%s"
 294                                         " requested by file=%s\n", name,
 295                                         l->l_name[0]
 296                                         ? l->l_name : _dl_argv[0]);
 297
 298                     /* We must be prepared that the addressed shared
 299                        object is not available.  */
 300                     err = _dl_catch_error (&objname, &errstring, openaux,
 301                                            &args);
 302                     if (__builtin_expect (errstring != NULL, 0))
 303                       {
 304                         /* We are not interested in the error message.  */
 305                         assert (errstring != NULL);
 306                         if (errstring != _dl_out_of_memory)
 307                           free ((char *) errstring);
 308
 309                         /* Simply ignore this error and continue the work.  */
 310                         continue;
 311                       }
 312                   }
 313                 else
 314                   {
 315                     int err;
 316
 317                     /* Say that we are about to load an auxiliary library.  */
 318                     if (__builtin_expect (GL(dl_debug_mask) & DL_DEBUG_LIBS,
 319                                           0))
 320                       _dl_debug_printf ("load filtered object=%s"
 321                                         " requested by file=%s\n", name,
 322                                         l->l_name[0]
 323                                         ? l->l_name : _dl_argv[0]);
 324
 325                     /* For filter objects the dependency must be available.  */
 326                     err = _dl_catch_error (&objname, &errstring, openaux,
 327                                            &args);
 328                     if (__builtin_expect (errstring != NULL, 0))
 329                       {
 330                         if (err)
 331                           errno_reason = err;
 332                         else
 333                           errno_reason = -1;
 334                         goto out;
 335                       }
 336                   }
 337
 338                 /* The auxiliary object is actually available.
 339                    Incorporate the map in all the lists.  */
 340
 341                 /* Allocate new entry.  This always has to be done.  */
 342                 newp = alloca (sizeof (struct list));
 343
 344                 /* We want to insert the new map before the current one,
 345                    but we have no back links.  So we copy the contents of
 346                    the current entry over.  Note that ORIG and NEWP now
 347                    have switched their meanings.  */
 348                 memcpy (newp, orig, sizeof (*newp));
 349
 350                 /* Initialize new entry.  */
 351                 orig->done = 0;
 352                 orig->map = args.aux;
 353
 354                 /* Remember this dependency.  */
 355                 if (needed != NULL)
 356                   needed[nneeded++] = args.aux;
 357
 358                 /* We must handle two situations here: the map is new,
 359                    so we must add it in all three lists.  If the map
 360                    is already known, we have two further possibilities:
 361                    - if the object is before the current map in the
 362                    search list, we do nothing.  It is already found
 363                    early
 364                    - if the object is after the current one, we must
 365                    move it just before the current map to make sure
 366                    the symbols are found early enough
 367                 */
 368                 if (args.aux->l_reserved)
 369                   {
 370                     /* The object is already somewhere in the list.
 371                        Locate it first.  */
 372                     struct list *late;
 373
 374                     /* This object is already in the search list we
 375                        are building.  Don't add a duplicate pointer.
 376                        Just added by _dl_map_object.  */
 377                     for (late = newp; late->next != NULL; late = late->next)
 378                       if (late->next->map == args.aux)
 379                         break;
 380
 381                     if (late->next != NULL)
 382                       {
 383                         /* The object is somewhere behind the current
 384                            position in the search path.  We have to
 385                            move it to this earlier position.  */
 386                         orig->next = newp;
 387
 388                         /* Now remove the later entry from the list
 389                            and adjust the tail pointer.  */
 390                         if (tail == late->next)
 391                           tail = late;
 392                         late->next = late->next->next;
 393
 394                         /* We must move the object earlier in the chain.  */
 395                         if (args.aux->l_prev != NULL)
 396                           args.aux->l_prev->l_next = args.aux->l_next;
 397                         if (args.aux->l_next != NULL)
 398                           args.aux->l_next->l_prev = args.aux->l_prev;
 399
 400                         args.aux->l_prev = newp->map->l_prev;
 401                         newp->map->l_prev = args.aux;
 402                         if (args.aux->l_prev != NULL)
 403                           args.aux->l_prev->l_next = args.aux;
 404                         args.aux->l_next = newp->map;
 405                       }
 406                     else
 407                       {
 408                         /* The object must be somewhere earlier in the
 409                            list.  Undo to the current list element what
 410                            we did above.  */
 411                         memcpy (orig, newp, sizeof (*newp));
 412                         continue;
 413                       }
 414                   }
 415                 else
 416                   {
 417                     /* This is easy.  We just add the symbol right here.  */
 418                     orig->next = newp;
 419                     ++nlist;
 420                     /* Set the mark bit that says it's already in the list.  */
 421                     args.aux->l_reserved = 1;
 422
 423                     /* The only problem is that in the double linked
 424                        list of all objects we don't have this new
 425                        object at the correct place.  Correct this here.  */
 426                     if (args.aux->l_prev)
 427                       args.aux->l_prev->l_next = args.aux->l_next;
 428                     if (args.aux->l_next)
 429                       args.aux->l_next->l_prev = args.aux->l_prev;
 430
 431                     args.aux->l_prev = newp->map->l_prev;
 432                     newp->map->l_prev = args.aux;
 433                     if (args.aux->l_prev != NULL)
 434                       args.aux->l_prev->l_next = args.aux;
 435                     args.aux->l_next = newp->map;
 436                   }
 437
 438                 /* Move the tail pointer if necessary.  */
 439                 if (orig == tail)
 440                   tail = newp;
 441
 442                 /* Move on the insert point.  */
 443                 orig = newp;
 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 = (struct link_map **)
 453             malloc ((nneeded + 1) * sizeof needed[0]);
 454           if (l->l_initfini == NULL)
 455             _dl_signal_error (ENOMEM, map->l_name, NULL,
 456                               N_("cannot allocate dependency list"));
 457           l->l_initfini[0] = l;
 458           memcpy (&l->l_initfini[1], needed, nneeded * sizeof needed[0]);
 459         }
 460
 461       /* If we have no auxiliary objects just go on to the next map.  */
 462       if (runp->done)
 463         do
 464           runp = runp->next;
 465         while (runp != NULL && runp->done);
 466     }
 467
 468  out:
 469   if (errno == 0 && errno_saved != 0)
 470     __set_errno (errno_saved);
 471
 472   if (map->l_initfini != NULL && map->l_type == lt_loaded)
 473     {
 474       /* This object was previously loaded as a dependency and we have
 475          a separate l_initfini list.  We don't need it anymore.  */
 476       assert (map->l_searchlist.r_list == NULL);
 477       free (map->l_initfini);
 478     }
 479
 480   /* Store the search list we built in the object.  It will be used for
 481      searches in the scope of this object.  */
 482   map->l_initfini =
 483     (struct link_map **) malloc ((2 * nlist + 1)
 484                                  * sizeof (struct link_map *));
 485   if (map->l_initfini == NULL)
 486     _dl_signal_error (ENOMEM, map->l_name, NULL,
 487                       N_("cannot allocate symbol search list"));
 488
 489
 490   map->l_searchlist.r_list = &map->l_initfini[nlist + 1];
 491   map->l_searchlist.r_nlist = nlist;
 492
 493   for (nlist = 0, runp = known; runp; runp = runp->next)
 494     {
 495       if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)
 496         /* This can happen when we trace the loading.  */
 497         --map->l_searchlist.r_nlist;
 498       else
 499         map->l_searchlist.r_list[nlist++] = runp->map;
 500
 501       /* Now clear all the mark bits we set in the objects on the search list
 502          to avoid duplicates, so the next call starts fresh.  */
 503       runp->map->l_reserved = 0;
 504     }
 505
 506   if (__builtin_expect(GL(dl_debug_mask) & DL_DEBUG_PRELINK, 0) != 0
 507       && map == GL(dl_loaded))
 508     {
 509       /* If we are to compute conflicts, we have to build local scope
 510          for each library, not just the ultimate loader.  */
 511       for (i = 0; i < nlist; ++i)
 512         {
 513           struct link_map *l = map->l_searchlist.r_list[i];
 514           unsigned int j, cnt;
 515
 516           /* The local scope has been already computed.  */
 517           if (l == map
 518               || (l->l_local_scope[0]
 519                   && l->l_local_scope[0]->r_nlist) != 0)
 520             continue;
 521
 522           if (l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 523             {
 524               /* As current DT_AUXILIARY/DT_FILTER implementation needs to be
 525                  rewritten, no need to bother with prelinking the old
 526                  implementation.  */
 527               _dl_signal_error (EINVAL, l->l_name, NULL, N_("\
 528 Filters not supported with LD_TRACE_PRELINKING"));
 529             }
 530
 531           cnt = _dl_build_local_scope (map->l_initfini, l);
 532           assert (cnt <= nlist);
 533           for (j = 0; j < cnt; j++)
 534             map->l_initfini[j]->l_reserved = 0;
 535
 536           l->l_local_scope[0] =
 537             (struct r_scope_elem *) malloc (sizeof (struct r_scope_elem)
 538                                             + (cnt
 539                                                * sizeof (struct link_map *)));
 540           if (l->l_local_scope[0] == NULL)
 541             _dl_signal_error (ENOMEM, map->l_name, NULL,
 542                               N_("cannot allocate symbol search list"));
 543           l->l_local_scope[0]->r_nlist = cnt;
 544           l->l_local_scope[0]->r_list =
 545             (struct link_map **) (l->l_local_scope[0] + 1);
 546           memcpy (l->l_local_scope[0]->r_list, map->l_initfini,
 547                   cnt * sizeof (struct link_map *));
 548         }
 549     }
 550
 551   /* Maybe we can remove some relocation dependencies now.  */
 552   assert (map->l_searchlist.r_list[0] == map);
 553   for (i = 0; i < map->l_reldepsact; ++i)
 554     {
 555       unsigned int j;
 556
 557       for (j = 1; j < nlist; ++j)
 558         if (map->l_searchlist.r_list[j] == map->l_reldeps[i])
 559           {
 560             /* A direct or transitive dependency is also on the list
 561                of relocation dependencies.  Remove the latter.  */
 562             --map->l_reldeps[i]->l_opencount;
 563
 564             for (j = i + 1; j < map->l_reldepsact; ++j)
 565               map->l_reldeps[j - 1] = map->l_reldeps[j];
 566
 567             --map->l_reldepsact;
 568
 569             /* Account for the '++i' performed by the 'for'.  */
 570             --i;
 571             break;
 572           }
 573     }
 574
 575   /* Now determine the order in which the initialization has to happen.  */
 576   memcpy (map->l_initfini, map->l_searchlist.r_list,
 577           nlist * sizeof (struct link_map *));
 578   /* We can skip looking for the binary itself which is at the front
 579      of the search list.  Look through the list backward so that circular
 580      dependencies are not changing the order.  */
 581   for (i = 1; i < nlist; ++i)
 582     {
 583       struct link_map *l = map->l_searchlist.r_list[i];
 584       unsigned int j;
 585       unsigned int k;
 586
 587       /* Find the place in the initfini list where the map is currently
 588          located.  */
 589       for (j = 1; map->l_initfini[j] != l; ++j)
 590         ;
 591
 592       /* Find all object for which the current one is a dependency and
 593          move the found object (if necessary) in front.  */
 594       for (k = j + 1; k < nlist; ++k)
 595         {
 596           struct link_map **runp;
 597
 598           runp = map->l_initfini[k]->l_initfini;
 599           if (runp != NULL)
 600             {
 601               while (*runp != NULL)
 602                 if (__builtin_expect (*runp++ == l, 0))
 603                   {
 604                     struct link_map *here = map->l_initfini[k];
 605
 606                     /* Move it now.  */
 607                     memmove (&map->l_initfini[j] + 1,
 608                              &map->l_initfini[j],
 609                              (k - j) * sizeof (struct link_map *));
 610                     map->l_initfini[j] = here;
 611
 612                     break;
 613                   }
 614             }
 615         }
 616     }
 617   /* Terminate the list of dependencies.  */
 618   map->l_initfini[nlist] = NULL;
 619
 620   if (errno_reason)
 621     _dl_signal_error (errno_reason == -1 ? 0 : errno_reason,
 622                       objname, NULL, errstring);
 623 }