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