elf/dl-deps.c

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