elf/dl-deps.c

   1 /* Load the dependencies of a mapped object.
   2    Copyright (C) 1996-2018 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, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 #include <atomic.h>
  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     int open_mode;
  51     const char *strtab;
  52     const char *name;
  53
  54     /* The return value of openaux.  */
  55     struct link_map *aux;
  56   };
  57
  58 static void
  59 openaux (void *a)
  60 {
  61   struct openaux_args *args = (struct openaux_args *) a;
  62
  63   args->aux = _dl_map_object (args->map, args->name,
  64                               (args->map->l_type == lt_executable
  65                                ? lt_library : args->map->l_type),
  66                               args->trace_mode, args->open_mode,
  67                               args->map->l_ns);
  68 }
  69
  70 static ptrdiff_t
  71 _dl_build_local_scope (struct link_map **list, struct link_map *map)
  72 {
  73   struct link_map **p = list;
  74   struct link_map **q;
  75
  76   *p++ = map;
  77   map->l_reserved = 1;
  78   if (map->l_initfini)
  79     for (q = map->l_initfini + 1; *q; ++q)
  80       if (! (*q)->l_reserved)
  81         p += _dl_build_local_scope (p, *q);
  82   return p - list;
  83 }
  84
  85
  86 /* We use a very special kind of list to track the path
  87    through the list of loaded shared objects.  We have to
  88    produce a flat list with unique members of all involved objects.
  89 */
  90 struct list
  91   {
  92     int done;                   /* Nonzero if this map was processed.  */
  93     struct link_map *map;       /* The data.  */
  94     struct list *next;          /* Elements for normal list.  */
  95   };
  96
  97
  98 /* Macro to expand DST.  It is an macro since we use `alloca'.  */
  99 #define expand_dst(l, str, fatal) \
 100   ({                                                                          \
 101     const char *__str = (str);                                                \
 102     const char *__result = __str;                                             \
 103     size_t __dst_cnt = DL_DST_COUNT (__str);                                  \
 104                                                                               \
 105     if (__dst_cnt != 0)                                                       \
 106       {                                                                       \
 107         char *__newp;                                                         \
 108                                                                               \
 109         /* DST must not appear in SUID/SGID programs.  */                     \
 110         if (__libc_enable_secure)                                             \
 111           _dl_signal_error (0, __str, NULL, N_("\
 112 DST not allowed in SUID/SGID programs"));                                     \
 113                                                                               \
 114         __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str),  \
 115                                                    __dst_cnt));               \
 116                                                                               \
 117         __result = _dl_dst_substitute (l, __str, __newp);                     \
 118                                                                               \
 119         if (*__result == '\0')                                                \
 120           {                                                                   \
 121             /* The replacement for the DST is not known.  We can't            \
 122                processed.  */                                                 \
 123             if (fatal)                                                        \
 124               _dl_signal_error (0, __str, NULL, N_("\
 125 empty dynamic string token substitution"));                                   \
 126             else                                                              \
 127               {                                                               \
 128                 /* This is for DT_AUXILIARY.  */                              \
 129                 if (__glibc_unlikely (GLRO(dl_debug_mask) & DL_DEBUG_LIBS))   \
 130                   _dl_debug_printf (N_("\
 131 cannot load auxiliary `%s' because of empty dynamic string token "            \
 132                                             "substitution\n"), __str);        \
 133                 continue;                                                     \
 134               }                                                               \
 135           }                                                                   \
 136       }                                                                       \
 137                                                                               \
 138     __result; })
 139
 140 static void
 141 preload (struct list *known, unsigned int *nlist, struct link_map *map)
 142 {
 143   known[*nlist].done = 0;
 144   known[*nlist].map = map;
 145   known[*nlist].next = &known[*nlist + 1];
 146
 147   ++*nlist;
 148   /* We use `l_reserved' as a mark bit to detect objects we have
 149      already put in the search list and avoid adding duplicate
 150      elements later in the list.  */
 151   map->l_reserved = 1;
 152 }
 153
 154 void
 155 _dl_map_object_deps (struct link_map *map,
 156                      struct link_map **preloads, unsigned int npreloads,
 157                      int trace_mode, int open_mode)
 158 {
 159   struct list *known = __alloca (sizeof *known * (1 + npreloads + 1));
 160   struct list *runp, *tail;
 161   unsigned int nlist, i;
 162   /* Object name.  */
 163   const char *name;
 164   int errno_saved;
 165   int errno_reason;
 166   struct dl_exception exception;
 167
 168   /* No loaded object so far.  */
 169   nlist = 0;
 170
 171   /* First load MAP itself.  */
 172   preload (known, &nlist, map);
 173
 174   /* Add the preloaded items after MAP but before any of its dependencies.  */
 175   for (i = 0; i < npreloads; ++i)
 176     preload (known, &nlist, preloads[i]);
 177
 178   /* Terminate the lists.  */
 179   known[nlist - 1].next = NULL;
 180
 181   /* Pointer to last unique object.  */
 182   tail = &known[nlist - 1];
 183
 184   /* No alloca'd space yet.  */
 185   struct link_map **needed_space = NULL;
 186   size_t needed_space_bytes = 0;
 187
 188   /* Process each element of the search list, loading each of its
 189      auxiliary objects and immediate dependencies.  Auxiliary objects
 190      will be added in the list before the object itself and
 191      dependencies will be appended to the list as we step through it.
 192      This produces a flat, ordered list that represents a
 193      breadth-first search of the dependency tree.
 194
 195      The whole process is complicated by the fact that we better
 196      should use alloca for the temporary list elements.  But using
 197      alloca means we cannot use recursive function calls.  */
 198   errno_saved = errno;
 199   errno_reason = 0;
 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         {
 216           size_t new_size = l->l_ldnum * sizeof (struct link_map *);
 217
 218           if (new_size > needed_space_bytes)
 219             needed_space
 220               = extend_alloca (needed_space, needed_space_bytes, new_size);
 221
 222           needed = needed_space;
 223         }
 224
 225       if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 226         {
 227           const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);
 228           struct openaux_args args;
 229           struct list *orig;
 230           const ElfW(Dyn) *d;
 231
 232           args.strtab = strtab;
 233           args.map = l;
 234           args.trace_mode = trace_mode;
 235           args.open_mode = open_mode;
 236           orig = runp;
 237
 238           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 239             if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
 240               {
 241                 /* Map in the needed object.  */
 242                 struct link_map *dep;
 243
 244                 /* Recognize DSTs.  */
 245                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
 246                 /* Store the tag in the argument structure.  */
 247                 args.name = name;
 248
 249                 int err = _dl_catch_exception (&exception, openaux, &args);
 250                 if (__glibc_unlikely (exception.errstring != NULL))
 251                   {
 252                     if (err)
 253                       errno_reason = err;
 254                     else
 255                       errno_reason = -1;
 256                     goto out;
 257                   }
 258                 else
 259                   dep = args.aux;
 260
 261                 if (! dep->l_reserved)
 262                   {
 263                     /* Allocate new entry.  */
 264                     struct list *newp;
 265
 266                     newp = alloca (sizeof (struct list));
 267
 268                     /* Append DEP to the list.  */
 269                     newp->map = dep;
 270                     newp->done = 0;
 271                     newp->next = NULL;
 272                     tail->next = newp;
 273                     tail = newp;
 274                     ++nlist;
 275                     /* Set the mark bit that says it's already in the list.  */
 276                     dep->l_reserved = 1;
 277                   }
 278
 279                 /* Remember this dependency.  */
 280                 if (needed != NULL)
 281                   needed[nneeded++] = dep;
 282               }
 283             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
 284               {
 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                 /* Say that we are about to load an auxiliary library.  */
 294                 if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_LIBS,
 295                                       0))
 296                   _dl_debug_printf ("load auxiliary object=%s"
 297                                     " requested by file=%s\n",
 298                                     name,
 299                                     DSO_FILENAME (l->l_name));
 300
 301                 /* We must be prepared that the addressed shared
 302                    object is not available.  For filter objects the dependency
 303                    must be available.  */
 304                 int err = _dl_catch_exception (&exception, openaux, &args);
 305                 if (__glibc_unlikely (exception.errstring != NULL))
 306                   {
 307                     if (d->d_tag == DT_AUXILIARY)
 308                       {
 309                         /* We are not interested in the error message.  */
 310                         _dl_exception_free (&exception);
 311                         /* Simply ignore this error and continue the work.  */
 312                         continue;
 313                       }
 314                     else
 315                       {
 316                         if (err)
 317                           errno_reason = err;
 318                         else
 319                           errno_reason = -1;
 320                         goto out;
 321                       }
 322                   }
 323
 324                 /* The auxiliary object is actually available.
 325                    Incorporate the map in all the lists.  */
 326
 327                 /* Allocate new entry.  This always has to be done.  */
 328                 newp = alloca (sizeof (struct list));
 329
 330                 /* We want to insert the new map before the current one,
 331                    but we have no back links.  So we copy the contents of
 332                    the current entry over.  Note that ORIG and NEWP now
 333                    have switched their meanings.  */
 334                 memcpy (newp, orig, sizeof (*newp));
 335
 336                 /* Initialize new entry.  */
 337                 orig->done = 0;
 338                 orig->map = args.aux;
 339
 340                 /* Remember this dependency.  */
 341                 if (needed != NULL)
 342                   needed[nneeded++] = args.aux;
 343
 344                 /* We must handle two situations here: the map is new,
 345                    so we must add it in all three lists.  If the map
 346                    is already known, we have two further possibilities:
 347                    - if the object is before the current map in the
 348                    search list, we do nothing.  It is already found
 349                    early
 350                    - if the object is after the current one, we must
 351                    move it just before the current map to make sure
 352                    the symbols are found early enough
 353                 */
 354                 if (args.aux->l_reserved)
 355                   {
 356                     /* The object is already somewhere in the list.
 357                        Locate it first.  */
 358                     struct list *late;
 359
 360                     /* This object is already in the search list we
 361                        are building.  Don't add a duplicate pointer.
 362                        Just added by _dl_map_object.  */
 363                     for (late = newp; late->next != NULL; late = late->next)
 364                       if (late->next->map == args.aux)
 365                         break;
 366
 367                     if (late->next != NULL)
 368                       {
 369                         /* The object is somewhere behind the current
 370                            position in the search path.  We have to
 371                            move it to this earlier position.  */
 372                         orig->next = newp;
 373
 374                         /* Now remove the later entry from the list
 375                            and adjust the tail pointer.  */
 376                         if (tail == late->next)
 377                           tail = late;
 378                         late->next = late->next->next;
 379
 380                         /* We must move the object earlier in the chain.  */
 381                         if (args.aux->l_prev != NULL)
 382                           args.aux->l_prev->l_next = args.aux->l_next;
 383                         if (args.aux->l_next != NULL)
 384                           args.aux->l_next->l_prev = args.aux->l_prev;
 385
 386                         args.aux->l_prev = newp->map->l_prev;
 387                         newp->map->l_prev = args.aux;
 388                         if (args.aux->l_prev != NULL)
 389                           args.aux->l_prev->l_next = args.aux;
 390                         args.aux->l_next = newp->map;
 391                       }
 392                     else
 393                       {
 394                         /* The object must be somewhere earlier in the
 395                            list.  Undo to the current list element what
 396                            we did above.  */
 397                         memcpy (orig, newp, sizeof (*newp));
 398                         continue;
 399                       }
 400                   }
 401                 else
 402                   {
 403                     /* This is easy.  We just add the symbol right here.  */
 404                     orig->next = newp;
 405                     ++nlist;
 406                     /* Set the mark bit that says it's already in the list.  */
 407                     args.aux->l_reserved = 1;
 408
 409                     /* The only problem is that in the double linked
 410                        list of all objects we don't have this new
 411                        object at the correct place.  Correct this here.  */
 412                     if (args.aux->l_prev)
 413                       args.aux->l_prev->l_next = args.aux->l_next;
 414                     if (args.aux->l_next)
 415                       args.aux->l_next->l_prev = args.aux->l_prev;
 416
 417                     args.aux->l_prev = newp->map->l_prev;
 418                     newp->map->l_prev = args.aux;
 419                     if (args.aux->l_prev != NULL)
 420                       args.aux->l_prev->l_next = args.aux;
 421                     args.aux->l_next = newp->map;
 422                   }
 423
 424                 /* Move the tail pointer if necessary.  */
 425                 if (orig == tail)
 426                   tail = newp;
 427
 428                 /* Move on the insert point.  */
 429                 orig = newp;
 430               }
 431         }
 432
 433       /* Terminate the list of dependencies and store the array address.  */
 434       if (needed != NULL)
 435         {
 436           needed[nneeded++] = NULL;
 437
 438           struct link_map **l_initfini = (struct link_map **)
 439             malloc ((2 * nneeded + 1) * sizeof needed[0]);
 440           if (l_initfini == NULL)
 441             _dl_signal_error (ENOMEM, map->l_name, NULL,
 442                               N_("cannot allocate dependency list"));
 443           l_initfini[0] = l;
 444           memcpy (&l_initfini[1], needed, nneeded * sizeof needed[0]);
 445           memcpy (&l_initfini[nneeded + 1], l_initfini,
 446                   nneeded * sizeof needed[0]);
 447           atomic_write_barrier ();
 448           l->l_initfini = l_initfini;
 449           l->l_free_initfini = 1;
 450         }
 451
 452       /* If we have no auxiliary objects just go on to the next map.  */
 453       if (runp->done)
 454         do
 455           runp = runp->next;
 456         while (runp != NULL && runp->done);
 457     }
 458
 459  out:
 460   if (errno == 0 && errno_saved != 0)
 461     __set_errno (errno_saved);
 462
 463   struct link_map **old_l_initfini = NULL;
 464   if (map->l_initfini != NULL && map->l_type == lt_loaded)
 465     {
 466       /* This object was previously loaded as a dependency and we have
 467          a separate l_initfini list.  We don't need it anymore.  */
 468       assert (map->l_searchlist.r_list == NULL);
 469       old_l_initfini = map->l_initfini;
 470     }
 471
 472   /* Store the search list we built in the object.  It will be used for
 473      searches in the scope of this object.  */
 474   struct link_map **l_initfini =
 475     (struct link_map **) malloc ((2 * nlist + 1)
 476                                  * sizeof (struct link_map *));
 477   if (l_initfini == NULL)
 478     _dl_signal_error (ENOMEM, map->l_name, NULL,
 479                       N_("cannot allocate symbol search list"));
 480
 481
 482   map->l_searchlist.r_list = &l_initfini[nlist + 1];
 483   map->l_searchlist.r_nlist = nlist;
 484
 485   for (nlist = 0, runp = known; runp; runp = runp->next)
 486     {
 487       if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)
 488         /* This can happen when we trace the loading.  */
 489         --map->l_searchlist.r_nlist;
 490       else
 491         map->l_searchlist.r_list[nlist++] = runp->map;
 492
 493       /* Now clear all the mark bits we set in the objects on the search list
 494          to avoid duplicates, so the next call starts fresh.  */
 495       runp->map->l_reserved = 0;
 496     }
 497
 498   if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_PRELINK, 0) != 0
 499       && map == GL(dl_ns)[LM_ID_BASE]._ns_loaded)
 500     {
 501       /* If we are to compute conflicts, we have to build local scope
 502          for each library, not just the ultimate loader.  */
 503       for (i = 0; i < nlist; ++i)
 504         {
 505           struct link_map *l = map->l_searchlist.r_list[i];
 506           unsigned int j, cnt;
 507
 508           /* The local scope has been already computed.  */
 509           if (l == map
 510               || (l->l_local_scope[0]
 511                   && l->l_local_scope[0]->r_nlist) != 0)
 512             continue;
 513
 514           if (l->l_info[AUXTAG] || l->l_info[FILTERTAG])
 515             {
 516               /* As current DT_AUXILIARY/DT_FILTER implementation needs to be
 517                  rewritten, no need to bother with prelinking the old
 518                  implementation.  */
 519               _dl_signal_error (EINVAL, l->l_name, NULL, N_("\
 520 Filters not supported with LD_TRACE_PRELINKING"));
 521             }
 522
 523           cnt = _dl_build_local_scope (l_initfini, l);
 524           assert (cnt <= nlist);
 525           for (j = 0; j < cnt; j++)
 526             {
 527               l_initfini[j]->l_reserved = 0;
 528               if (j && __builtin_expect (l_initfini[j]->l_info[DT_SYMBOLIC]
 529                                          != NULL, 0))
 530                 l->l_symbolic_in_local_scope = true;
 531             }
 532
 533           l->l_local_scope[0] =
 534             (struct r_scope_elem *) malloc (sizeof (struct r_scope_elem)
 535                                             + (cnt
 536                                                * sizeof (struct link_map *)));
 537           if (l->l_local_scope[0] == NULL)
 538             _dl_signal_error (ENOMEM, map->l_name, NULL,
 539                               N_("cannot allocate symbol search list"));
 540           l->l_local_scope[0]->r_nlist = cnt;
 541           l->l_local_scope[0]->r_list =
 542             (struct link_map **) (l->l_local_scope[0] + 1);
 543           memcpy (l->l_local_scope[0]->r_list, l_initfini,
 544                   cnt * sizeof (struct link_map *));
 545         }
 546     }
 547
 548   /* Maybe we can remove some relocation dependencies now.  */
 549   assert (map->l_searchlist.r_list[0] == map);
 550   struct link_map_reldeps *l_reldeps = NULL;
 551   if (map->l_reldeps != NULL)
 552     {
 553       for (i = 1; i < nlist; ++i)
 554         map->l_searchlist.r_list[i]->l_reserved = 1;
 555
 556       struct link_map **list = &map->l_reldeps->list[0];
 557       for (i = 0; i < map->l_reldeps->act; ++i)
 558         if (list[i]->l_reserved)
 559           {
 560             /* Need to allocate new array of relocation dependencies.  */
 561             l_reldeps = malloc (sizeof (*l_reldeps)
 562                                 + map->l_reldepsmax
 563                                   * sizeof (struct link_map *));
 564             if (l_reldeps == NULL)
 565               /* Bad luck, keep the reldeps duplicated between
 566                  map->l_reldeps->list and map->l_initfini lists.  */
 567               ;
 568             else
 569               {
 570                 unsigned int j = i;
 571                 memcpy (&l_reldeps->list[0], &list[0],
 572                         i * sizeof (struct link_map *));
 573                 for (i = i + 1; i < map->l_reldeps->act; ++i)
 574                   if (!list[i]->l_reserved)
 575                     l_reldeps->list[j++] = list[i];
 576                 l_reldeps->act = j;
 577               }
 578           }
 579
 580       for (i = 1; i < nlist; ++i)
 581         map->l_searchlist.r_list[i]->l_reserved = 0;
 582     }
 583
 584   /* Sort the initializer list to take dependencies into account.  The binary
 585      itself will always be initialize last.  */
 586   memcpy (l_initfini, map->l_searchlist.r_list,
 587           nlist * sizeof (struct link_map *));
 588   /* We can skip looking for the binary itself which is at the front of
 589      the search list.  */
 590   _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false);
 591
 592   /* Terminate the list of dependencies.  */
 593   l_initfini[nlist] = NULL;
 594   atomic_write_barrier ();
 595   map->l_initfini = l_initfini;
 596   map->l_free_initfini = 1;
 597   if (l_reldeps != NULL)
 598     {
 599       atomic_write_barrier ();
 600       void *old_l_reldeps = map->l_reldeps;
 601       map->l_reldeps = l_reldeps;
 602       _dl_scope_free (old_l_reldeps);
 603     }
 604   if (old_l_initfini != NULL)
 605     _dl_scope_free (old_l_initfini);
 606
 607   if (errno_reason)
 608     _dl_signal_exception (errno_reason == -1 ? 0 : errno_reason,
 609                           &exception, NULL);
 610 }