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