elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996,1997,1998,1999,2000,2001 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 /* This is zero at program start to signal that the global scope map is
  43    allocated by rtld.  Later it keeps the size of the map.  It might be
  44    reset if in _dl_close if the last global object is removed.  */
  45 size_t _dl_global_scope_alloc;
  46
  47 extern size_t _dl_platformlen;
  48
  49 /* When loading auxiliary objects we must ignore errors.  It's ok if
  50    an object is missing.  */
  51 struct openaux_args
  52   {
  53     /* The arguments to openaux.  */
  54     struct link_map *map;
  55     int trace_mode;
  56     const char *strtab;
  57     const char *name;
  58
  59     /* The return value of openaux.  */
  60     struct link_map *aux;
  61   };
  62
  63 static void
  64 openaux (void *a)
  65 {
  66   struct openaux_args *args = (struct openaux_args *) a;
  67
  68   args->aux = _dl_map_object (args->map, args->name, 0,
  69                               (args->map->l_type == lt_executable
  70                                ? lt_library : args->map->l_type),
  71                               args->trace_mode, 0);
  72 }
  73
  74 static ptrdiff_t
  75 internal_function
  76 _dl_build_local_scope (struct link_map **list, struct link_map *map)
  77 {
  78   struct link_map **p = list;
  79   struct link_map **q;
  80
  81   *p++ = map;
  82   map->l_reserved = 1;
  83   if (map->l_initfini)
  84     for (q = map->l_initfini + 1; *q; ++q)
  85       if (! (*q)->l_reserved)
  86         p += _dl_build_local_scope (p, *q);
  87   return p - list;
  88 }
  89
  90
  91 /* We use a very special kind of list to track the path
  92    through the list of loaded shared objects.  We have to
  93    produce a flat list with unique members of all involved objects.
  94 */
  95 struct list
  96   {
  97     int done;                   /* Nonzero if this map was processed.  */
  98     struct link_map *map;       /* The data.  */
  99     struct list *next;  /* Elements for normal list.  */
 100   };
 101
 102
 103 /* Macro to expand DST.  It is an macro since we use `alloca'.  */
 104 #define expand_dst(l, str, fatal) \
 105   ({                                                                          \
 106     const char *__str = (str);                                                \
 107     const char *__result = __str;                                             \
 108     size_t __cnt = DL_DST_COUNT(__str, 0);                                    \
 109                                                                               \
 110     if (__cnt != 0)                                                           \
 111       {                                                                       \
 112         char *__newp;                                                         \
 113                                                                               \
 114         /* DST must not appear in SUID/SGID programs.  */                     \
 115         if (__libc_enable_secure)                                             \
 116           _dl_signal_error (0, __str, NULL,                                   \
 117                             N_("DST not allowed in SUID/SGID programs"));     \
 118                                                                               \
 119         __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str),  \
 120                                                    __cnt));                   \
 121                                                                               \
 122         __result = DL_DST_SUBSTITUTE (l, __str, __newp, 0);                   \
 123                                                                               \
 124         if (*__result == '\0')                                                \
 125           {                                                                   \
 126             /* The replacement for the DST is not known.  We can't            \
 127                processed.  */                                                 \
 128             if (fatal)                                                        \
 129               _dl_signal_error (0, __str, NULL, N_("\
 130 empty dynamics string token substitution"));                                  \
 131             else                                                              \
 132               {                                                               \
 133                 /* This is for DT_AUXILIARY.  */                              \
 134                 if (__builtin_expect (_dl_debug_mask & DL_DEBUG_LIBS, 0))     \
 135                   _dl_debug_printf ("cannot load auxiliary `%s' because of"   \
 136                                     "empty dynamic string token "             \
 137                                     "substitution\n", __str);                 \
 138                 continue;                                                     \
 139               }                                                               \
 140           }                                                                   \
 141       }                                                                       \
 142                                                                               \
 143     __result; })
 144
 145
 146 void
 147 internal_function
 148 _dl_map_object_deps (struct link_map *map,
 149                      struct link_map **preloads, unsigned int npreloads,
 150                      int trace_mode)
 151 {
 152   struct list known[1 + npreloads + 1];
 153   struct list *runp, *tail;
 154   unsigned int nlist, i;
 155   /* Object name.  */
 156   const char *name;
 157   int errno_saved;
 158   int errno_reason;
 159   const char *errstring;
 160   const char *objname;
 161
 162   auto inline void preload (struct link_map *map);
 163
 164   inline void preload (struct link_map *map)
 165     {
 166       known[nlist].done = 0;
 167       known[nlist].map = map;
 168       known[nlist].next = &known[nlist + 1];
 169
 170       ++nlist;
 171       /* We use `l_reserved' as a mark bit to detect objects we have
 172          already put in the search list and avoid adding duplicate
 173          elements later in the list.  */
 174       map->l_reserved = 1;
 175     }
 176
 177   /* No loaded object so far.  */
 178   nlist = 0;
 179
 180   /* First load MAP itself.  */
 181   preload (map);
 182
 183   /* Add the preloaded items after MAP but before any of its dependencies.  */
 184   for (i = 0; i < npreloads; ++i)
 185     preload (preloads[i]);
 186
 187   /* Terminate the lists.  */
 188   known[nlist - 1].next = NULL;
 189
 190   /* Pointer to last unique object.  */
 191   tail = &known[nlist - 1];
 192
 193   /* Process each element of the search list, loading each of its
 194      auxiliary objects and immediate dependencies.  Auxiliary objects
 195      will be added in the list before the object itself and
 196      dependencies will be appended to the list as we step through it.
 197      This produces a flat, ordered list that represents a
 198      breadth-first search of the dependency tree.
 199
 200      The whole process is complicated by the fact that we better
 201      should use alloca for the temporary list elements.  But using
 202      alloca means we cannot use recursive function calls.  */
 203   errno_saved = errno;
 204   errno_reason = 0;
 205   errstring = NULL;
 206   errno = 0;
 207   name = NULL;
 208   for (runp = known; runp; )
 209     {
 210       struct link_map *l = runp->map;
 211       struct link_map **needed = NULL;
 212       unsigned int nneeded = 0;
 213
 214       /* Unless otherwise stated, this object is handled.  */
 215       runp->done = 1;
 216
 217       /* Allocate a temporary record to contain the references to the
 218          dependencies of this object.  */
 219       if (l->l_searchlist.r_list == NULL && l->l_initfini == NULL
 220           && l != map && l->l_ldnum > 0)
 221         needed = (struct link_map **) alloca (l->l_ldnum
 222                                               * sizeof (struct link_map *));
 223
 224       if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 225         {
 226           const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);
 227           struct openaux_args args;
 228           struct list *orig;
 229           const ElfW(Dyn) *d;
 230
 231           args.strtab = strtab;
 232           args.map = l;
 233           args.trace_mode = trace_mode;
 234           orig = runp;
 235
 236           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 237             if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
 238               {
 239                 /* Map in the needed object.  */
 240                 struct link_map *dep;
 241                 int err;
 242
 243                 /* Recognize DSTs.  */
 244                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 245                 /* Store the tag in the argument structure.  */
 246                 args.name = name;
 247
 248                 err = _dl_catch_error (&objname, &errstring, openaux, &args);
 249                 if (__builtin_expect (errstring != NULL, 0))
 250                   {
 251                     if (err)
 252                       errno_reason = err;
 253                     else
 254                       errno_reason = -1;
 255                     goto out;
 256                   }
 257                 else
 258                   dep = args.aux;
 259
 260                 if (! dep->l_reserved)
 261                   {
 262                     /* Allocate new entry.  */
 263                     struct list *newp;
 264
 265                     newp = alloca (sizeof (struct list));
 266
 267                     /* Append DEP to the list.  */
 268                     newp->map = dep;
 269                     newp->done = 0;
 270                     newp->next = NULL;
 271                     tail->next = newp;
 272                     tail = newp;
 273                     ++nlist;
 274                     /* Set the mark bit that says it's already in the list.  */
 275                     dep->l_reserved = 1;
 276                   }
 277
 278                 /* Remember this dependency.  */
 279                 if (needed != NULL)
 280                   needed[nneeded++] = dep;
 281               }
 282             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 283               {
 284                 struct list *newp;
 285
 286                 /* Recognize DSTs.  */
 287                 name = expand_dst (l, strtab + d->d_un.d_val,
 288                                    d->d_tag == DT_AUXILIARY);
 289                 /* Store the tag in the argument structure.  */
 290                 args.name = name;
 291
 292                 if (d->d_tag == DT_AUXILIARY)
 293                   {
 294                     int err;
 295
 296                     /* Say that we are about to load an auxiliary library.  */
 297                     if (__builtin_expect (_dl_debug_mask & DL_DEBUG_LIBS, 0))
 298                       _dl_debug_printf ("load auxiliary object=%s"
 299                                         " requested by file=%s\n", name,
 300                                         l->l_name[0]
 301                                         ? l->l_name : _dl_argv[0]);
 302
 303                     /* We must be prepared that the addressed shared
 304                        object is not available.  */
 305                     err = _dl_catch_error (&objname, &errstring, openaux,
 306                                            &args);
 307                     if (__builtin_expect (errstring != NULL, 0))
 308                       {
 309                         /* We are not interested in the error message.  */
 310                         assert (errstring != NULL);
 311                         if (errstring != _dl_out_of_memory)
 312                           free ((char *) errstring);
 313
 314                         /* Simply ignore this error and continue the work.  */
 315                         continue;
 316                       }
 317                   }
 318                 else
 319                   {
 320                     int err;
 321
 322                     /* Say that we are about to load an auxiliary library.  */
 323                     if (__builtin_expect (_dl_debug_mask & DL_DEBUG_LIBS, 0))
 324                       _dl_debug_printf ("load filtered object=%s"
 325                                         " requested by file=%s\n", name,
 326                                         l->l_name[0]
 327                                         ? l->l_name : _dl_argv[0]);
 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 ((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         }
 464
 465       /* If we have no auxiliary objects just go on to the next map.  */
 466       if (runp->done)
 467         do
 468           runp = runp->next;
 469         while (runp != NULL && runp->done);
 470     }
 471
 472  out:
 473   if (errno == 0 && errno_saved != 0)
 474     __set_errno (errno_saved);
 475
 476   if (map->l_initfini != NULL && map->l_type == lt_loaded)
 477     {
 478       /* This object was previously loaded as a dependency and we have
 479          a separate l_initfini list.  We don't need it anymore.  */
 480       assert (map->l_searchlist.r_list == NULL);
 481       free (map->l_initfini);
 482     }
 483
 484   /* Store the search list we built in the object.  It will be used for
 485      searches in the scope of this object.  */
 486   map->l_initfini =
 487     (struct link_map **) malloc ((2 * nlist + 1)
 488                                  * sizeof (struct link_map *));
 489   if (map->l_initfini == NULL)
 490     _dl_signal_error (ENOMEM, map->l_name, NULL,
 491                       N_("cannot allocate symbol search list"));
 492
 493
 494   map->l_searchlist.r_list = &map->l_initfini[nlist + 1];
 495   map->l_searchlist.r_nlist = nlist;
 496
 497   for (nlist = 0, runp = known; runp; runp = runp->next)
 498     {
 499       if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)
 500         /* This can happen when we trace the loading.  */
 501         --map->l_searchlist.r_nlist;
 502       else
 503         map->l_searchlist.r_list[nlist++] = runp->map;
 504
 505       /* Now clear all the mark bits we set in the objects on the search list
 506          to avoid duplicates, so the next call starts fresh.  */
 507       runp->map->l_reserved = 0;
 508     }
 509
 510   if (__builtin_expect(_dl_debug_mask & DL_DEBUG_PRELINK, 0) != 0
 511       && map == _dl_loaded)
 512     {
 513       /* If we are to compute conflicts, we have to build local scope
 514          for each library, not just the ultimate loader.  */
 515       for (i = 0; i < nlist; ++i)
 516         {
 517           struct link_map *l = map->l_searchlist.r_list[i];
 518           unsigned int j, cnt;
 519
 520           /* The local scope has been already computed.  */
 521           if (l == map
 522               || (l->l_local_scope[0]
 523                   && l->l_local_scope[0]->r_nlist) != 0)
 524             continue;
 525
 526           if (l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 527             {
 528               /* As current DT_AUXILIARY/DT_FILTER implementation needs to be
 529                  rewritten, no need to bother with prelinking the old
 530                  implementation.  */
 531               _dl_signal_error (EINVAL, l->l_name, NULL, N_("\
 532 Filters not supported with LD_TRACE_PRELINKING"));
 533             }
 534
 535           cnt = _dl_build_local_scope (map->l_initfini, l);
 536           assert (cnt <= nlist);
 537           for (j = 0; j < cnt; j++)
 538             map->l_initfini[j]->l_reserved = 0;
 539
 540           l->l_local_scope[0] =
 541             (struct r_scope_elem *) malloc (sizeof (struct r_scope_elem)
 542                                             + (cnt
 543                                                * sizeof (struct link_map *)));
 544           if (l->l_local_scope[0] == NULL)
 545             _dl_signal_error (ENOMEM, map->l_name, NULL,
 546                               N_("cannot allocate symbol search list"));
 547           l->l_local_scope[0]->r_nlist = cnt;
 548           l->l_local_scope[0]->r_list =
 549             (struct link_map **) (l->l_local_scope[0] + 1);
 550           memcpy (l->l_local_scope[0]->r_list, map->l_initfini,
 551                   cnt * sizeof (struct link_map *));
 552         }
 553     }
 554
 555   /* Maybe we can remove some relocation dependencies now.  */
 556   assert (map->l_searchlist.r_list[0] == map);
 557   for (i = 0; i < map->l_reldepsact; ++i)
 558     {
 559       unsigned int j;
 560
 561       for (j = 1; j < nlist; ++j)
 562         if (map->l_searchlist.r_list[j] == map->l_reldeps[i])
 563           {
 564             /* A direct or transitive dependency is also on the list
 565                of relocation dependencies.  Remove the latter.  */
 566             --map->l_reldeps[i]->l_opencount;
 567
 568             for (j = i + 1; j < map->l_reldepsact; ++j)
 569               map->l_reldeps[j - 1] = map->l_reldeps[j];
 570
 571             --map->l_reldepsact;
 572
 573             /* Account for the '++i' performed by the 'for'.  */
 574             --i;
 575             break;
 576           }
 577     }
 578
 579   /* Now determine the order in which the initialization has to happen.  */
 580   memcpy (map->l_initfini, map->l_searchlist.r_list,
 581           nlist * sizeof (struct link_map *));
 582   /* We can skip looking for the binary itself which is at the front
 583      of the search list.  Look through the list backward so that circular
 584      dependencies are not changing the order.  */
 585   for (i = 1; i < nlist; ++i)
 586     {
 587       struct link_map *l = map->l_searchlist.r_list[i];
 588       unsigned int j;
 589       unsigned int k;
 590
 591       /* Find the place in the initfini list where the map is currently
 592          located.  */
 593       for (j = 1; map->l_initfini[j] != l; ++j)
 594         ;
 595
 596       /* Find all object for which the current one is a dependency and
 597          move the found object (if necessary) in front.  */
 598       for (k = j + 1; k < nlist; ++k)
 599         {
 600           struct link_map **runp;
 601
 602           runp = map->l_initfini[k]->l_initfini;
 603           if (runp != NULL)
 604             {
 605               while (*runp != NULL)
 606                 if (__builtin_expect (*runp++ == l, 0))
 607                   {
 608                     struct link_map *here = map->l_initfini[k];
 609
 610                     /* Move it now.  */
 611                     memmove (&map->l_initfini[j] + 1,
 612                              &map->l_initfini[j],
 613                              (k - j) * sizeof (struct link_map *));
 614                     map->l_initfini[j] = here;
 615
 616                     break;
 617                   }
 618             }
 619         }
 620     }
 621   /* Terminate the list of dependencies.  */
 622   map->l_initfini[nlist] = NULL;
 623
 624   if (errno_reason)
 625     _dl_signal_error (errno_reason == -1 ? 0 : errno_reason,
 626                       objname, NULL, errstring);
 627 }