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                 int err;
 226
 227                 /* Recognize DSTs.  */
 228                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 229                 /* Store the tag in the argument structure.  */
 230                 args.name = name;
 231
 232                 err = _dl_catch_error (&objname, &errstring, openaux, &args);
 233                 if (__builtin_expect (errstring != NULL, 0))
 234                   {
 235                     if (err)
 236                       errno_reason = err;
 237                     else
 238                       errno_reason = -1;
 239                     goto out;
 240                   }
 241                 else
 242                   dep = args.aux;
 243
 244                 if (! dep->l_reserved)
 245                   {
 246                     /* Allocate new entry.  */
 247                     struct list *newp;
 248
 249                     newp = alloca (sizeof (struct list));
 250
 251                     /* Append DEP to the list.  */
 252                     newp->map = dep;
 253                     newp->done = 0;
 254                     newp->next = NULL;
 255                     tail->next = newp;
 256                     tail = newp;
 257                     ++nlist;
 258                     /* Set the mark bit that says it's already in the list.  */
 259                     dep->l_reserved = 1;
 260                   }
 261
 262                 /* Remember this dependency.  */
 263                 if (needed != NULL)
 264                   needed[nneeded++] = dep;
 265               }
 266             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 267               {
 268                 struct list *newp;
 269
 270                 /* Recognize DSTs.  */
 271                 name = expand_dst (l, strtab + d->d_un.d_val,
 272                                    d->d_tag == DT_AUXILIARY);
 273                 /* Store the tag in the argument structure.  */
 274                 args.name = name;
 275
 276                 if (d->d_tag == DT_AUXILIARY)
 277                   {
 278                     int err;
 279
 280                     /* Say that we are about to load an auxiliary library.  */
 281                     if (__builtin_expect (_dl_debug_mask & DL_DEBUG_LIBS, 0))
 282                       _dl_debug_printf ("load auxiliary object=%s"
 283                                         " requested by file=%s\n", name,
 284                                         l->l_name[0]
 285                                         ? l->l_name : _dl_argv[0]);
 286
 287                     /* We must be prepared that the addressed shared
 288                        object is not available.  */
 289                     err = _dl_catch_error (&objname, &errstring, openaux,
 290                                            &args);
 291                     if (__builtin_expect (errstring != NULL, 0))
 292                       {
 293                         /* We are not interested in the error message.  */
 294                         assert (errstring != NULL);
 295                         if (errstring != _dl_out_of_memory)
 296                           free ((char *) errstring);
 297
 298                         /* Simply ignore this error and continue the work.  */
 299                         continue;
 300                       }
 301                   }
 302                 else
 303                   {
 304                     int err;
 305
 306                     /* Say that we are about to load an auxiliary library.  */
 307                     if (__builtin_expect (_dl_debug_mask & DL_DEBUG_LIBS, 0))
 308                       _dl_debug_printf ("load filtered object=%s"
 309                                         " requested by file=%s\n", name,
 310                                         l->l_name[0]
 311                                         ? l->l_name : _dl_argv[0]);
 312
 313                     /* For filter objects the dependency must be available.  */
 314                     err = _dl_catch_error (&objname, &errstring, openaux,
 315                                            &args);
 316                     if (__builtin_expect (errstring != NULL, 0))
 317                       {
 318                         if (err)
 319                           errno_reason = err;
 320                         else
 321                           errno_reason = -1;
 322                         goto out;
 323                       }
 324                   }
 325
 326                 /* The auxiliary object is actually available.
 327                    Incorporate the map in all the lists.  */
 328
 329                 /* Allocate new entry.  This always has to be done.  */
 330                 newp = alloca (sizeof (struct list));
 331
 332                 /* We want to insert the new map before the current one,
 333                    but we have no back links.  So we copy the contents of
 334                    the current entry over.  Note that ORIG and NEWP now
 335                    have switched their meanings.  */
 336                 memcpy (newp, orig, sizeof (*newp));
 337
 338                 /* Initialize new entry.  */
 339                 orig->done = 0;
 340                 orig->map = args.aux;
 341
 342                 /* Remember this dependency.  */
 343                 if (needed != NULL)
 344                   needed[nneeded++] = args.aux;
 345
 346                 /* We must handle two situations here: the map is new,
 347                    so we must add it in all three lists.  If the map
 348                    is already known, we have two further possibilities:
 349                    - if the object is before the current map in the
 350                    search list, we do nothing.  It is already found
 351                    early
 352                    - if the object is after the current one, we must
 353                    move it just before the current map to make sure
 354                    the symbols are found early enough
 355                 */
 356                 if (args.aux->l_reserved)
 357                   {
 358                     /* The object is already somewhere in the list.
 359                        Locate it first.  */
 360                     struct list *late;
 361
 362                     /* This object is already in the search list we
 363                        are building.  Don't add a duplicate pointer.
 364                        Just added by _dl_map_object.  */
 365                     for (late = newp; late->next; late = late->next)
 366                       if (late->next->map == args.aux)
 367                         break;
 368
 369                     if (late->next)
 370                       {
 371                         /* The object is somewhere behind the current
 372                            position in the search path.  We have to
 373                            move it to this earlier position.  */
 374                         orig->next = newp;
 375
 376                         /* Now remove the later entry from the list
 377                            and adjust the tail pointer.  */
 378                         if (tail == late->next)
 379                           tail = late;
 380                         late->next = late->next->next;
 381
 382                         /* We must move the object earlier in the chain.  */
 383                         if (args.aux->l_prev)
 384                           args.aux->l_prev->l_next = args.aux->l_next;
 385                         if (args.aux->l_next)
 386                           args.aux->l_next->l_prev = args.aux->l_prev;
 387
 388                         args.aux->l_prev = newp->map->l_prev;
 389                         newp->map->l_prev = args.aux;
 390                         if (args.aux->l_prev != NULL)
 391                           args.aux->l_prev->l_next = args.aux;
 392                         args.aux->l_next = newp->map;
 393                       }
 394                     else
 395                       {
 396                         /* The object must be somewhere earlier in the
 397                            list.  That's good, we only have to insert
 398                            an entry for the duplicate list.  */
 399                         orig->next = NULL;      /* Never used.  */
 400
 401                         /* Now we have a problem.  The element
 402                            pointing to ORIG in the list must
 403                            point to NEWP now.  This is the only place
 404                            where we need this backreference and this
 405                            situation is really not that frequent.  So
 406                            we don't use a double-linked list but
 407                            instead search for the preceding element.  */
 408                         late = known;
 409                         while (late->next != orig)
 410                           late = late->next;
 411                         late->next = newp;
 412                       }
 413                   }
 414                 else
 415                   {
 416                     /* This is easy.  We just add the symbol right here.  */
 417                     orig->next = newp;
 418                     ++nlist;
 419                     /* Set the mark bit that says it's already in the list.  */
 420                     args.aux->l_reserved = 1;
 421
 422                     /* The only problem is that in the double linked
 423                        list of all objects we don't have this new
 424                        object at the correct place.  Correct this here.  */
 425                     if (args.aux->l_prev)
 426                       args.aux->l_prev->l_next = args.aux->l_next;
 427                     if (args.aux->l_next)
 428                       args.aux->l_next->l_prev = args.aux->l_prev;
 429
 430                     args.aux->l_prev = newp->map->l_prev;
 431                     newp->map->l_prev = args.aux;
 432                     if (args.aux->l_prev != NULL)
 433                       args.aux->l_prev->l_next = args.aux;
 434                     args.aux->l_next = newp->map;
 435                   }
 436
 437                 /* Move the tail pointer if necessary.  */
 438                 if (orig == tail)
 439                   tail = newp;
 440
 441                 /* Move on the insert point.  */
 442                 orig = newp;
 443               }
 444         }
 445
 446       /* Terminate the list of dependencies and store the array address.  */
 447       if (needed != NULL)
 448         {
 449           needed[nneeded++] = NULL;
 450
 451           l->l_initfini = malloc (nneeded * sizeof needed[0]);
 452           if (l->l_initfini == NULL)
 453             _dl_signal_error (ENOMEM, map->l_name,
 454                               N_("cannot allocate dependency list"));
 455           memcpy (l->l_initfini, needed, nneeded * sizeof needed[0]);
 456         }
 457
 458       /* If we have no auxiliary objects just go on to the next map.  */
 459       if (runp->done)
 460         do
 461           runp = runp->next;
 462         while (runp != NULL && runp->done);
 463     }
 464
 465 out:
 466   if (errno == 0 && errno_saved != 0)
 467     __set_errno (errno_saved);
 468
 469   if (map->l_initfini != NULL && map->l_type == lt_loaded)
 470     {
 471       /* This object was previously loaded as a dependency and we have
 472          a separate l_initfini list.  We don't need it anymore.  */
 473       assert (map->l_searchlist.r_list == NULL);
 474       free (map->l_initfini);
 475     }
 476
 477   /* Store the search list we built in the object.  It will be used for
 478      searches in the scope of this object.  */
 479   map->l_initfini =
 480     (struct link_map **) malloc ((2 * nlist + 1)
 481                                  * sizeof (struct link_map *));
 482   if (map->l_initfini == NULL)
 483     _dl_signal_error (ENOMEM, map->l_name,
 484                       N_("cannot allocate symbol search list"));
 485
 486
 487   map->l_searchlist.r_list = &map->l_initfini[nlist + 1];
 488   map->l_searchlist.r_nlist = nlist;
 489
 490   for (nlist = 0, runp = known; runp; runp = runp->next)
 491     {
 492       if (trace_mode && runp->map->l_faked)
 493         /* This can happen when we trace the loading.  */
 494         --map->l_searchlist.r_nlist;
 495       else
 496         map->l_searchlist.r_list[nlist++] = runp->map;
 497
 498       /* Now clear all the mark bits we set in the objects on the search list
 499          to avoid duplicates, so the next call starts fresh.  */
 500       runp->map->l_reserved = 0;
 501     }
 502
 503   /* Now determine the order in which the initialization has to happen.  */
 504   memcpy (map->l_initfini, map->l_searchlist.r_list,
 505           nlist * sizeof (struct link_map *));
 506   /* We can skip looking for the binary itself which is at the front
 507      of the search list.  Look through the list backward so that circular
 508      dependencies are not changing the order.  */
 509   for (i = 1; i < nlist; ++i)
 510     {
 511       struct link_map *l = map->l_searchlist.r_list[i];
 512       unsigned int j;
 513       unsigned int k;
 514
 515       /* Find the place in the initfini list where the map is currently
 516          located.  */
 517       for (j = 1; map->l_initfini[j] != l; ++j)
 518         ;
 519
 520       /* Find all object for which the current one is a dependency and
 521          move the found object (if necessary) in front.  */
 522       for (k = j + 1; k < nlist; ++k)
 523         {
 524           struct link_map **runp;
 525
 526           runp = map->l_initfini[k]->l_initfini;
 527           if (runp != NULL)
 528             {
 529               while (*runp != NULL)
 530                 if (*runp == l)
 531                   {
 532                     struct link_map *here = map->l_initfini[k];
 533
 534                     /* Move it now.  */
 535                     memmove (&map->l_initfini[j] + 1,
 536                              &map->l_initfini[j],
 537                              (k - j) * sizeof (struct link_map *));
 538                     map->l_initfini[j] = here;
 539
 540                     break;
 541                   }
 542                 else
 543                   ++runp;
 544             }
 545         }
 546     }
 547   /* Terminate the list of dependencies.  */
 548   map->l_initfini[nlist] = NULL;
 549
 550   if (errno_reason)
 551     _dl_signal_error (errno_reason == -1 ? 0 : errno_reason,
 552                       objname, errstring);
 553 }