elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996, 1997, 1998, 1999, 2000 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 Library General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    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    Library General Public License for more details.
  14
  15    You should have received a copy of the GNU Library General Public
  16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18    Boston, MA 02111-1307, USA.  */
  19
  20 #include <assert.h>
  21 #include <dlfcn.h>
  22 #include <errno.h>
  23 #include <libintl.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <unistd.h>
  27 #include <sys/param.h>
  28 #include <ldsodefs.h>
  29
  30 #include <dl-dst.h>
  31
  32 /* Whether an shared object references one or more auxiliary objects
  33    is signaled by the AUXTAG entry in l_info.  */
  34 #define AUXTAG  (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
  35                  + DT_EXTRATAGIDX (DT_AUXILIARY))
  36 /* Whether an shared object references one or more auxiliary objects
  37    is signaled by the AUXTAG entry in l_info.  */
  38 #define FILTERTAG (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
  39                    + DT_EXTRATAGIDX (DT_FILTER))
  40
  41 /* This is zero at program start to signal that the global scope map is
  42    allocated by rtld.  Later it keeps the size of the map.  It might be
  43    reset if in _dl_close if the last global object is removed.  */
  44 size_t _dl_global_scope_alloc;
  45
  46 extern size_t _dl_platformlen;
  47
  48 /* When loading auxiliary objects we must ignore errors.  It's ok if
  49    an object is missing.  */
  50 struct openaux_args
  51   {
  52     /* The arguments to openaux.  */
  53     struct link_map *map;
  54     int trace_mode;
  55     const char *strtab;
  56     const char *name;
  57
  58     /* The return value of openaux.  */
  59     struct link_map *aux;
  60   };
  61
  62 static void
  63 openaux (void *a)
  64 {
  65   struct openaux_args *args = (struct openaux_args *) a;
  66
  67   args->aux = _dl_map_object (args->map, args->name, 0,
  68                               (args->map->l_type == lt_executable
  69                                ? lt_library : args->map->l_type),
  70                               args->trace_mode, 0);
  71 }
  72
  73
  74
  75 /* We use a very special kind of list to track the two kinds paths
  76    through the list of loaded shared objects.  We have to
  77
  78    - produce a flat list with unique members of all involved objects
  79
  80    - produce a flat list of all shared objects.
  81 */
  82 struct list
  83   {
  84     int done;                   /* Nonzero if this map was processed.  */
  85     struct link_map *map;       /* The data.  */
  86
  87     struct list *unique;        /* Elements for normal list.  */
  88     struct list *dup;           /* Elements in complete list.  */
  89   };
  90
  91
  92 /* Macro to expand DST.  It is an macro since we use `alloca'.  */
  93 #define expand_dst(l, str, fatal) \
  94   ({                                                                          \
  95     const char *__str = (str);                                                \
  96     const char *__result = __str;                                             \
  97     size_t __cnt = DL_DST_COUNT(__str, 0);                                    \
  98                                                                               \
  99     if (__cnt != 0)                                                           \
 100       {                                                                       \
 101         char *__newp;                                                         \
 102                                                                               \
 103         /* DST must not appear in SUID/SGID programs.  */                     \
 104         if (__libc_enable_secure)                                             \
 105           _dl_signal_error (0, __str,                                         \
 106                             N_("DST not allowed in SUID/SGID programs"));     \
 107                                                                               \
 108         __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str),  \
 109                                                    __cnt));                   \
 110                                                                               \
 111         __result = DL_DST_SUBSTITUTE (l, __str, __newp, 0);                   \
 112                                                                               \
 113         if (*__result == '\0')                                                \
 114           {                                                                   \
 115             /* The replacement for the DST is not known.  We can't            \
 116                processed.  */                                                 \
 117             if (fatal)                                                        \
 118               _dl_signal_error (0, __str, N_("\
 119 empty dynamics string token substitution"));                                  \
 120             else                                                              \
 121               {                                                               \
 122                 /* This is for DT_AUXILIARY.  */                              \
 123                 if (__builtin_expect (_dl_debug_libs, 0))                     \
 124                   _dl_debug_message (1, "cannot load auxiliary `", __str,     \
 125                                      "' because of empty dynamic string"      \
 126                                      " token substitution\n", NULL);          \
 127                 continue;                                                     \
 128               }                                                               \
 129           }                                                                   \
 130       }                                                                       \
 131                                                                               \
 132     __result; })
 133
 134
 135 void
 136 internal_function
 137 _dl_map_object_deps (struct link_map *map,
 138                      struct link_map **preloads, unsigned int npreloads,
 139                      int trace_mode)
 140 {
 141   struct list known[1 + npreloads + 1];
 142   struct list *runp, *utail, *dtail;
 143   unsigned int nlist, nduplist, i;
 144   /* Object name.  */
 145   const char *name;
 146   int errno_saved;
 147   int errno_reason;
 148
 149   auto inline void preload (struct link_map *map);
 150
 151   inline void preload (struct link_map *map)
 152     {
 153       known[nlist].done = 0;
 154       known[nlist].map = map;
 155
 156       known[nlist].unique = &known[nlist + 1];
 157       known[nlist].dup = &known[nlist + 1];
 158
 159       ++nlist;
 160       /* We use `l_reserved' as a mark bit to detect objects we have
 161          already put in the search list and avoid adding duplicate
 162          elements later in the list.  */
 163       map->l_reserved = 1;
 164     }
 165
 166   /* No loaded object so far.  */
 167   nlist = 0;
 168
 169   /* First load MAP itself.  */
 170   preload (map);
 171
 172   /* Add the preloaded items after MAP but before any of its dependencies.  */
 173   for (i = 0; i < npreloads; ++i)
 174     preload (preloads[i]);
 175
 176   /* Terminate the lists.  */
 177   known[nlist - 1].unique = NULL;
 178   known[nlist - 1].dup = NULL;
 179
 180   /* Pointer to last unique object.  */
 181   utail = &known[nlist - 1];
 182   /* Pointer to last loaded object.  */
 183   dtail = &known[nlist - 1];
 184
 185   /* Until now we have the same number of libraries in the normal and
 186      the list with duplicates.  */
 187   nduplist = nlist;
 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   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           orig = runp;
 230
 231           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 232             if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
 233               {
 234                 /* Map in the needed object.  */
 235                 struct link_map *dep;
 236                 /* Allocate new entry.  */
 237                 struct list *newp;
 238                 const char *objname;
 239                 const char *errstring;
 240
 241                 /* Recognize DSTs.  */
 242                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 243                 /* Store the tag in the argument structure.  */
 244                 args.name = name;
 245
 246                 if (_dl_catch_error (&objname, &errstring, openaux, &args))
 247                   {
 248                     if (errno)
 249                       errno_reason = errno;
 250                     else
 251                       errno_reason = -1;
 252                     goto out;
 253                   }
 254                 else
 255                   dep = args.aux;
 256
 257                 /* Add it in any case to the duplicate list.  */
 258                 newp = alloca (sizeof (struct list));
 259                 newp->map = dep;
 260                 newp->dup = NULL;
 261                 dtail->dup = newp;
 262                 dtail = newp;
 263                 ++nduplist;
 264
 265                 if (! dep->l_reserved)
 266                   {
 267                     /* Append DEP to the unique list.  */
 268                     newp->done = 0;
 269                     newp->unique = NULL;
 270                     utail->unique = newp;
 271                     utail = newp;
 272                     ++nlist;
 273                     /* Set the mark bit that says it's already in the list.  */
 274                     dep->l_reserved = 1;
 275                   }
 276
 277                 /* Remember this dependency.  */
 278                 if (needed != NULL)
 279                   needed[nneeded++] = dep;
 280               }
 281             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 282               {
 283                 const char *objname;
 284                 const char *errstring;
 285                 struct list *newp;
 286
 287                 /* Recognize DSTs.  */
 288                 name = expand_dst (l, strtab + d->d_un.d_val,
 289                                    d->d_tag == DT_AUXILIARY);
 290                 /* Store the tag in the argument structure.  */
 291                 args.name = name;
 292
 293                 if (d->d_tag == DT_AUXILIARY)
 294                   {
 295                     /* Say that we are about to load an auxiliary library.  */
 296                     if (__builtin_expect (_dl_debug_libs, 0))
 297                       _dl_debug_message (1, "load auxiliary object=",
 298                                          name, " requested by file=",
 299                                          l->l_name[0]
 300                                          ? l->l_name : _dl_argv[0],
 301                                          "\n", NULL);
 302
 303                     /* We must be prepared that the addressed shared
 304                        object is not available.  */
 305                     if (_dl_catch_error (&objname, &errstring, openaux, &args))
 306                       {
 307                         /* We are not interested in the error message.  */
 308                         assert (errstring != NULL);
 309                         if (errstring != _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                     /* Say that we are about to load an auxiliary library.  */
 319                     if (__builtin_expect (_dl_debug_libs, 0))
 320                       _dl_debug_message (1, "load filtered object=", name,
 321                                          " requested by file=",
 322                                          l->l_name[0]
 323                                          ? l->l_name : _dl_argv[0],
 324                                          "\n", NULL);
 325
 326                     /* For filter objects the dependency must be available.  */
 327                     if (_dl_catch_error (&objname, &errstring, openaux, &args))
 328                       {
 329                         if (errno)
 330                           errno_reason = errno;
 331                         else
 332                           errno_reason = -1;
 333                         goto out;
 334                       }
 335                   }
 336
 337                 /* The auxiliary object is actually available.
 338                    Incorporate the map in all the lists.  */
 339
 340                 /* Allocate new entry.  This always has to be done.  */
 341                 newp = alloca (sizeof (struct list));
 342
 343                 /* We want to insert the new map before the current one,
 344                    but we have no back links.  So we copy the contents of
 345                    the current entry over.  Note that ORIG and NEWP now
 346                    have switched their meanings.  */
 347                 orig->dup = memcpy (newp, orig, sizeof (*newp));
 348
 349                 /* Initialize new entry.  */
 350                 orig->done = 0;
 351                 orig->map = args.aux;
 352
 353                 /* Remember this dependency.  */
 354                 if (needed != NULL)
 355                   needed[nneeded++] = args.aux;
 356
 357                 /* We must handle two situations here: the map is new,
 358                    so we must add it in all three lists.  If the map
 359                    is already known, we have two further possibilities:
 360                    - if the object is before the current map in the
 361                    search list, we do nothing.  It is already found
 362                    early
 363                    - if the object is after the current one, we must
 364                    move it just before the current map to make sure
 365                    the symbols are found early enough
 366                 */
 367                 if (args.aux->l_reserved)
 368                   {
 369                     /* The object is already somewhere in the list.
 370                        Locate it first.  */
 371                     struct list *late;
 372
 373                     /* This object is already in the search list we
 374                        are building.  Don't add a duplicate pointer.
 375                        Just added by _dl_map_object.  */
 376                     for (late = newp; late->unique; late = late->unique)
 377                       if (late->unique->map == args.aux)
 378                         break;
 379
 380                     if (late->unique)
 381                       {
 382                         /* The object is somewhere behind the current
 383                            position in the search path.  We have to
 384                            move it to this earlier position.  */
 385                         orig->unique = newp;
 386
 387                         /* Now remove the later entry from the unique list
 388                            and adjust the tail pointer.  */
 389                         if (utail == late->unique)
 390                           utail = late;
 391                         late->unique = late->unique->unique;
 392
 393                         /* We must move the object earlier in the chain.  */
 394                         if (args.aux->l_prev)
 395                           args.aux->l_prev->l_next = args.aux->l_next;
 396                         if (args.aux->l_next)
 397                           args.aux->l_next->l_prev = args.aux->l_prev;
 398
 399                         args.aux->l_prev = newp->map->l_prev;
 400                         newp->map->l_prev = args.aux;
 401                         if (args.aux->l_prev != NULL)
 402                           args.aux->l_prev->l_next = args.aux;
 403                         args.aux->l_next = newp->map;
 404                       }
 405                     else
 406                       {
 407                         /* The object must be somewhere earlier in the
 408                            list.  That's good, we only have to insert
 409                            an entry for the duplicate list.  */
 410                         orig->unique = NULL;    /* Never used.  */
 411
 412                         /* Now we have a problem.  The element
 413                            pointing to ORIG in the unique list must
 414                            point to NEWP now.  This is the only place
 415                            where we need this backreference and this
 416                            situation is really not that frequent.  So
 417                            we don't use a double-linked list but
 418                            instead search for the preceding element.  */
 419                         late = known;
 420                         while (late->unique != orig)
 421                           late = late->unique;
 422                         late->unique = newp;
 423                       }
 424                   }
 425                 else
 426                   {
 427                     /* This is easy.  We just add the symbol right here.  */
 428                     orig->unique = newp;
 429                     ++nlist;
 430                     /* Set the mark bit that says it's already in the list.  */
 431                     args.aux->l_reserved = 1;
 432
 433                     /* The only problem is that in the double linked
 434                        list of all objects we don't have this new
 435                        object at the correct place.  Correct this here.  */
 436                     if (args.aux->l_prev)
 437                       args.aux->l_prev->l_next = args.aux->l_next;
 438                     if (args.aux->l_next)
 439                       args.aux->l_next->l_prev = args.aux->l_prev;
 440
 441                     args.aux->l_prev = newp->map->l_prev;
 442                     newp->map->l_prev = args.aux;
 443                     if (args.aux->l_prev != NULL)
 444                       args.aux->l_prev->l_next = args.aux;
 445                     args.aux->l_next = newp->map;
 446                   }
 447
 448                 /* Move the tail pointers if necessary.  */
 449                 if (orig == utail)
 450                   utail = newp;
 451                 if (orig == dtail)
 452                   dtail = newp;
 453
 454                 /* Move on the insert point.  */
 455                 orig = newp;
 456
 457                 /* We always add an entry to the duplicate list.  */
 458                 ++nduplist;
 459               }
 460         }
 461
 462       /* Terminate the list of dependencies and store the array address.  */
 463       if (needed != NULL)
 464         {
 465           needed[nneeded++] = NULL;
 466
 467           l->l_initfini = malloc (nneeded * sizeof needed[0]);
 468           if (l->l_initfini == NULL)
 469             _dl_signal_error (ENOMEM, map->l_name,
 470                               N_("cannot allocate dependency list"));
 471           memcpy (l->l_initfini, needed, nneeded * sizeof needed[0]);
 472         }
 473
 474       /* If we have no auxiliary objects just go on to the next map.  */
 475       if (runp->done)
 476         do
 477           runp = runp->unique;
 478         while (runp != NULL && runp->done);
 479     }
 480
 481 out:
 482   if (errno == 0 && errno_saved != 0)
 483     __set_errno (errno_saved);
 484
 485   if (map->l_initfini != NULL && map->l_type == lt_loaded)
 486     {
 487       /* This object was previously loaded as a dependency and we have
 488          a separate l_initfini list.  We don't need it anymore.  */
 489       assert (map->l_searchlist.r_list == NULL);
 490       free (map->l_initfini);
 491     }
 492
 493   /* Store the search list we built in the object.  It will be used for
 494      searches in the scope of this object.  */
 495   map->l_initfini =
 496     (struct link_map **) malloc ((2 * nlist + 1
 497                                   + (nlist == nduplist ? 0 : nduplist))
 498                                  * sizeof (struct link_map *));
 499   if (map->l_initfini == NULL)
 500     _dl_signal_error (ENOMEM, map->l_name,
 501                       N_("cannot allocate symbol search list"));
 502
 503
 504   map->l_searchlist.r_list = &map->l_initfini[nlist + 1];
 505   map->l_searchlist.r_nlist = nlist;
 506
 507   for (nlist = 0, runp = known; runp; runp = runp->unique)
 508     {
 509       if (trace_mode && runp->map->l_faked)
 510         /* This can happen when we trace the loading.  */
 511         --map->l_searchlist.r_nlist;
 512       else
 513         map->l_searchlist.r_list[nlist++] = runp->map;
 514
 515       /* Now clear all the mark bits we set in the objects on the search list
 516          to avoid duplicates, so the next call starts fresh.  */
 517       runp->map->l_reserved = 0;
 518     }
 519
 520   map->l_searchlist.r_nduplist = nduplist;
 521   if (nlist == nduplist)
 522     map->l_searchlist.r_duplist = map->l_searchlist.r_list;
 523   else
 524     {
 525       unsigned int cnt;
 526
 527       map->l_searchlist.r_duplist = map->l_searchlist.r_list + nlist;
 528
 529       for (cnt = 0, runp = known; runp; runp = runp->dup)
 530         if (trace_mode && runp->map->l_faked)
 531           /* This can happen when we trace the loading.  */
 532           --map->l_searchlist.r_nduplist;
 533         else
 534           map->l_searchlist.r_duplist[cnt++] = runp->map;
 535     }
 536
 537   /* Now determine the order in which the initialization has to happen.  */
 538   memcpy (map->l_initfini, map->l_searchlist.r_list,
 539           nlist * sizeof (struct link_map *));
 540   /* We can skip looking for the binary itself which is at the front
 541      of the search list.  Look through the list backward so that circular
 542      dependencies are not changing the order.  */
 543   for (i = 1; i < nlist; ++i)
 544     {
 545       struct link_map *l = map->l_searchlist.r_list[i];
 546       unsigned int j;
 547       unsigned int k;
 548
 549       /* Find the place in the initfini list where the map is currently
 550          located.  */
 551       for (j = 1; map->l_initfini[j] != l; ++j)
 552         ;
 553
 554       /* Find all object for which the current one is a dependency and
 555          move the found object (if necessary) in front.  */
 556       for (k = j + 1; k < nlist; ++k)
 557         {
 558           struct link_map **runp;
 559
 560           runp = map->l_initfini[k]->l_initfini;
 561           if (runp != NULL)
 562             {
 563               while (*runp != NULL)
 564                 if (*runp == l)
 565                   {
 566                     struct link_map *here = map->l_initfini[k];
 567
 568                     /* Move it now.  */
 569                     memmove (&map->l_initfini[j] + 1,
 570                              &map->l_initfini[j],
 571                              (k - j) * sizeof (struct link_map *));
 572                     map->l_initfini[j] = here;
 573
 574                     break;
 575                   }
 576                 else
 577                   ++runp;
 578             }
 579         }
 580     }
 581   /* Terminate the list of dependencies.  */
 582   map->l_initfini[nlist] = NULL;
 583
 584   if (errno_reason)
 585     _dl_signal_error (errno_reason == -1 ? 0 : errno_reason,
 586                       name ?: "", N_("cannot load shared object file"));
 587 }