elf/dl-deps.c

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