elf/dl-deps.c

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