elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996-2003, 2004, 2005, 2006 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 __dst_cnt = DL_DST_COUNT (__str, 0);                               \
 105                                                                               \
 106     if (__dst_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                                                    __dst_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
 239                 /* Recognize DSTs.  */
 240                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 241                 /* Store the tag in the argument structure.  */
 242                 args.name = name;
 243
 244                 bool malloced;
 245                 int err = _dl_catch_error (&objname, &errstring, &malloced,
 246                                            openaux, &args);
 247                 if (__builtin_expect (errstring != NULL, 0))
 248                   {
 249                     char *new_errstring = strdupa (errstring);
 250                     objname = strdupa (objname);
 251                     if (malloced)
 252                       free ((char *) errstring);
 253                     errstring = new_errstring;
 254
 255                     if (err)
 256                       errno_reason = err;
 257                     else
 258                       errno_reason = -1;
 259                     goto out;
 260                   }
 261                 else
 262                   dep = args.aux;
 263
 264                 if (! dep->l_reserved)
 265                   {
 266                     /* Allocate new entry.  */
 267                     struct list *newp;
 268
 269                     newp = alloca (sizeof (struct list));
 270
 271                     /* Append DEP to the list.  */
 272                     newp->map = dep;
 273                     newp->done = 0;
 274                     newp->next = NULL;
 275                     tail->next = newp;
 276                     tail = newp;
 277                     ++nlist;
 278                     /* Set the mark bit that says it's already in the list.  */
 279                     dep->l_reserved = 1;
 280                   }
 281
 282                 /* Remember this dependency.  */
 283                 if (needed != NULL)
 284                   needed[nneeded++] = dep;
 285               }
 286             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 287               {
 288                 struct list *newp;
 289
 290                 /* Recognize DSTs.  */
 291                 name = expand_dst (l, strtab + d->d_un.d_val,
 292                                    d->d_tag == DT_AUXILIARY);
 293                 /* Store the tag in the argument structure.  */
 294                 args.name = name;
 295
 296                 if (d->d_tag == DT_AUXILIARY)
 297                   {
 298                     /* Say that we are about to load an auxiliary library.  */
 299                     if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_LIBS,
 300                                           0))
 301                       _dl_debug_printf ("load auxiliary object=%s"
 302                                         " requested by file=%s\n",
 303                                         name,
 304                                         l->l_name[0]
 305                                         ? l->l_name : rtld_progname);
 306
 307                     /* We must be prepared that the addressed shared
 308                        object is not available.  */
 309                     bool malloced;
 310                     (void) _dl_catch_error (&objname, &errstring, &malloced,
 311                                             openaux, &args);
 312                     if (__builtin_expect (errstring != NULL, 0))
 313                       {
 314                         /* We are not interested in the error message.  */
 315                         assert (errstring != NULL);
 316                         if (malloced)
 317                           free ((char *) errstring);
 318
 319                         /* Simply ignore this error and continue the work.  */
 320                         continue;
 321                       }
 322                   }
 323                 else
 324                   {
 325                     /* Say that we are about to load an auxiliary library.  */
 326                     if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_LIBS,
 327                                           0))
 328                       _dl_debug_printf ("load filtered object=%s"
 329                                         " requested by file=%s\n",
 330                                         name,
 331                                         l->l_name[0]
 332                                         ? l->l_name : rtld_progname);
 333
 334                     /* For filter objects the dependency must be available.  */
 335                     bool malloced;
 336                     int err = _dl_catch_error (&objname, &errstring, &malloced,
 337                                                openaux, &args);
 338                     if (__builtin_expect (errstring != NULL, 0))
 339                       {
 340                         char *new_errstring = strdupa (errstring);
 341                         objname = strdupa (objname);
 342                         if (malloced)
 343                           free ((char *) errstring);
 344                         errstring = new_errstring;
 345
 346                         if (err)
 347                           errno_reason = err;
 348                         else
 349                           errno_reason = -1;
 350                         goto out;
 351                       }
 352                   }
 353
 354                 /* The auxiliary object is actually available.
 355                    Incorporate the map in all the lists.  */
 356
 357                 /* Allocate new entry.  This always has to be done.  */
 358                 newp = alloca (sizeof (struct list));
 359
 360                 /* We want to insert the new map before the current one,
 361                    but we have no back links.  So we copy the contents of
 362                    the current entry over.  Note that ORIG and NEWP now
 363                    have switched their meanings.  */
 364                 memcpy (newp, orig, sizeof (*newp));
 365
 366                 /* Initialize new entry.  */
 367                 orig->done = 0;
 368                 orig->map = args.aux;
 369
 370                 /* Remember this dependency.  */
 371                 if (needed != NULL)
 372                   needed[nneeded++] = args.aux;
 373
 374                 /* We must handle two situations here: the map is new,
 375                    so we must add it in all three lists.  If the map
 376                    is already known, we have two further possibilities:
 377                    - if the object is before the current map in the
 378                    search list, we do nothing.  It is already found
 379                    early
 380                    - if the object is after the current one, we must
 381                    move it just before the current map to make sure
 382                    the symbols are found early enough
 383                 */
 384                 if (args.aux->l_reserved)
 385                   {
 386                     /* The object is already somewhere in the list.
 387                        Locate it first.  */
 388                     struct list *late;
 389
 390                     /* This object is already in the search list we
 391                        are building.  Don't add a duplicate pointer.
 392                        Just added by _dl_map_object.  */
 393                     for (late = newp; late->next != NULL; late = late->next)
 394                       if (late->next->map == args.aux)
 395                         break;
 396
 397                     if (late->next != NULL)
 398                       {
 399                         /* The object is somewhere behind the current
 400                            position in the search path.  We have to
 401                            move it to this earlier position.  */
 402                         orig->next = newp;
 403
 404                         /* Now remove the later entry from the list
 405                            and adjust the tail pointer.  */
 406                         if (tail == late->next)
 407                           tail = late;
 408                         late->next = late->next->next;
 409
 410                         /* We must move the object earlier in the chain.  */
 411                         if (args.aux->l_prev != NULL)
 412                           args.aux->l_prev->l_next = args.aux->l_next;
 413                         if (args.aux->l_next != NULL)
 414                           args.aux->l_next->l_prev = args.aux->l_prev;
 415
 416                         args.aux->l_prev = newp->map->l_prev;
 417                         newp->map->l_prev = args.aux;
 418                         if (args.aux->l_prev != NULL)
 419                           args.aux->l_prev->l_next = args.aux;
 420                         args.aux->l_next = newp->map;
 421                       }
 422                     else
 423                       {
 424                         /* The object must be somewhere earlier in the
 425                            list.  Undo to the current list element what
 426                            we did above.  */
 427                         memcpy (orig, newp, sizeof (*newp));
 428                         continue;
 429                       }
 430                   }
 431                 else
 432                   {
 433                     /* This is easy.  We just add the symbol right here.  */
 434                     orig->next = newp;
 435                     ++nlist;
 436                     /* Set the mark bit that says it's already in the list.  */
 437                     args.aux->l_reserved = 1;
 438
 439                     /* The only problem is that in the double linked
 440                        list of all objects we don't have this new
 441                        object at the correct place.  Correct this here.  */
 442                     if (args.aux->l_prev)
 443                       args.aux->l_prev->l_next = args.aux->l_next;
 444                     if (args.aux->l_next)
 445                       args.aux->l_next->l_prev = args.aux->l_prev;
 446
 447                     args.aux->l_prev = newp->map->l_prev;
 448                     newp->map->l_prev = args.aux;
 449                     if (args.aux->l_prev != NULL)
 450                       args.aux->l_prev->l_next = args.aux;
 451                     args.aux->l_next = newp->map;
 452                   }
 453
 454                 /* Move the tail pointer if necessary.  */
 455                 if (orig == tail)
 456                   tail = newp;
 457
 458                 /* Move on the insert point.  */
 459                 orig = newp;
 460               }
 461         }
 462
 463       /* Terminate the list of dependencies and store the array address.  */
 464       if (needed != NULL)
 465         {
 466           needed[nneeded++] = NULL;
 467
 468           l->l_initfini = (struct link_map **)
 469             malloc ((2 * nneeded + 1) * sizeof needed[0]);
 470           if (l->l_initfini == NULL)
 471             _dl_signal_error (ENOMEM, map->l_name, NULL,
 472                               N_("cannot allocate dependency list"));
 473           l->l_initfini[0] = l;
 474           memcpy (&l->l_initfini[1], needed, nneeded * sizeof needed[0]);
 475           memcpy (&l->l_initfini[nneeded + 1], l->l_initfini,
 476                   nneeded * sizeof needed[0]);
 477         }
 478
 479       /* If we have no auxiliary objects just go on to the next map.  */
 480       if (runp->done)
 481         do
 482           runp = runp->next;
 483         while (runp != NULL && runp->done);
 484     }
 485
 486  out:
 487   if (errno == 0 && errno_saved != 0)
 488     __set_errno (errno_saved);
 489
 490   if (map->l_initfini != NULL && map->l_type == lt_loaded)
 491     {
 492       /* This object was previously loaded as a dependency and we have
 493          a separate l_initfini list.  We don't need it anymore.  */
 494       assert (map->l_searchlist.r_list == NULL);
 495       free (map->l_initfini);
 496     }
 497
 498   /* Store the search list we built in the object.  It will be used for
 499      searches in the scope of this object.  */
 500   map->l_initfini =
 501     (struct link_map **) malloc ((2 * nlist + 1)
 502                                  * sizeof (struct link_map *));
 503   if (map->l_initfini == NULL)
 504     _dl_signal_error (ENOMEM, map->l_name, NULL,
 505                       N_("cannot allocate symbol search list"));
 506
 507
 508   map->l_searchlist.r_list = &map->l_initfini[nlist + 1];
 509   map->l_searchlist.r_nlist = nlist;
 510
 511   for (nlist = 0, runp = known; runp; runp = runp->next)
 512     {
 513       if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)
 514         /* This can happen when we trace the loading.  */
 515         --map->l_searchlist.r_nlist;
 516       else
 517         map->l_searchlist.r_list[nlist++] = runp->map;
 518
 519       /* Now clear all the mark bits we set in the objects on the search list
 520          to avoid duplicates, so the next call starts fresh.  */
 521       runp->map->l_reserved = 0;
 522     }
 523
 524   if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_PRELINK, 0) != 0
 525       && map == GL(dl_ns)[LM_ID_BASE]._ns_loaded)
 526     {
 527       /* If we are to compute conflicts, we have to build local scope
 528          for each library, not just the ultimate loader.  */
 529       for (i = 0; i < nlist; ++i)
 530         {
 531           struct link_map *l = map->l_searchlist.r_list[i];
 532           unsigned int j, cnt;
 533
 534           /* The local scope has been already computed.  */
 535           if (l == map
 536               || (l->l_local_scope[0]
 537                   && l->l_local_scope[0]->r_nlist) != 0)
 538             continue;
 539
 540           if (l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 541             {
 542               /* As current DT_AUXILIARY/DT_FILTER implementation needs to be
 543                  rewritten, no need to bother with prelinking the old
 544                  implementation.  */
 545               _dl_signal_error (EINVAL, l->l_name, NULL, N_("\
 546 Filters not supported with LD_TRACE_PRELINKING"));
 547             }
 548
 549           cnt = _dl_build_local_scope (map->l_initfini, l);
 550           assert (cnt <= nlist);
 551           for (j = 0; j < cnt; j++)
 552             map->l_initfini[j]->l_reserved = 0;
 553
 554           l->l_local_scope[0] =
 555             (struct r_scope_elem *) malloc (sizeof (struct r_scope_elem)
 556                                             + (cnt
 557                                                * sizeof (struct link_map *)));
 558           if (l->l_local_scope[0] == NULL)
 559             _dl_signal_error (ENOMEM, map->l_name, NULL,
 560                               N_("cannot allocate symbol search list"));
 561           l->l_local_scope[0]->r_nlist = cnt;
 562           l->l_local_scope[0]->r_list =
 563             (struct link_map **) (l->l_local_scope[0] + 1);
 564           memcpy (l->l_local_scope[0]->r_list, map->l_initfini,
 565                   cnt * sizeof (struct link_map *));
 566         }
 567     }
 568
 569   /* Maybe we can remove some relocation dependencies now.  */
 570   assert (map->l_searchlist.r_list[0] == map);
 571   for (i = 0; i < map->l_reldepsact; ++i)
 572     {
 573       unsigned int j;
 574
 575       for (j = 1; j < nlist; ++j)
 576         if (map->l_searchlist.r_list[j] == map->l_reldeps[i])
 577           {
 578             /* A direct or transitive dependency is also on the list
 579                of relocation dependencies.  Remove the latter.  */
 580             for (j = i + 1; j < map->l_reldepsact; ++j)
 581               map->l_reldeps[j - 1] = map->l_reldeps[j];
 582
 583             --map->l_reldepsact;
 584
 585             /* Account for the '++i' performed by the 'for'.  */
 586             --i;
 587             break;
 588           }
 589     }
 590
 591   /* Now determine the order in which the initialization has to happen.  */
 592   memcpy (map->l_initfini, map->l_searchlist.r_list,
 593           nlist * sizeof (struct link_map *));
 594   /* We can skip looking for the binary itself which is at the front
 595      of the search list.  Look through the list backward so that circular
 596      dependencies are not changing the order.  */
 597   for (i = 1; i < nlist; ++i)
 598     {
 599       struct link_map *l = map->l_searchlist.r_list[i];
 600       unsigned int j;
 601       unsigned int k;
 602
 603       /* Find the place in the initfini list where the map is currently
 604          located.  */
 605       for (j = 1; map->l_initfini[j] != l; ++j)
 606         ;
 607
 608       /* Find all object for which the current one is a dependency and
 609          move the found object (if necessary) in front.  */
 610       for (k = j + 1; k < nlist; ++k)
 611         {
 612           struct link_map **runp;
 613
 614           runp = map->l_initfini[k]->l_initfini;
 615           if (runp != NULL)
 616             {
 617               while (*runp != NULL)
 618                 if (__builtin_expect (*runp++ == l, 0))
 619                   {
 620                     struct link_map *here = map->l_initfini[k];
 621
 622                     /* Move it now.  */
 623                     memmove (&map->l_initfini[j] + 1,
 624                              &map->l_initfini[j],
 625                              (k - j) * sizeof (struct link_map *));
 626                     map->l_initfini[j] = here;
 627
 628                     /* Don't insert further matches before the last
 629                        entry moved to the front.  */
 630                     ++j;
 631
 632                     break;
 633                   }
 634             }
 635         }
 636     }
 637   /* Terminate the list of dependencies.  */
 638   map->l_initfini[nlist] = NULL;
 639
 640   if (errno_reason)
 641     _dl_signal_error (errno_reason == -1 ? 0 : errno_reason, objname,
 642                       NULL, errstring);
 643 }