elf/dl-lookup.c

   1 /* Look up a symbol in the loaded objects.
   2    Copyright (C) 1995-2019 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 <alloca.h>
  20 #include <libintl.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <unistd.h>
  24 #include <ldsodefs.h>
  25 #include <dl-hash.h>
  26 #include <dl-machine.h>
  27 #include <sysdep-cancel.h>
  28 #include <libc-lock.h>
  29 #include <tls.h>
  30 #include <atomic.h>
  31
  32 #include <assert.h>
  33
  34 /* Return nonzero if check_match should consider SYM to fail to match a
  35    symbol reference for some machine-specific reason.  */
  36 #ifndef ELF_MACHINE_SYM_NO_MATCH
  37 # define ELF_MACHINE_SYM_NO_MATCH(sym) 0
  38 #endif
  39
  40 #define VERSTAG(tag)    (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGIDX (tag))
  41
  42
  43 struct sym_val
  44   {
  45     const ElfW(Sym) *s;
  46     struct link_map *m;
  47   };
  48
  49
  50 /* Statistics function.  */
  51 #ifdef SHARED
  52 # define bump_num_relocations() ++GL(dl_num_relocations)
  53 #else
  54 # define bump_num_relocations() ((void) 0)
  55 #endif
  56
  57 /* Utility function for do_lookup_x. The caller is called with undef_name,
  58    ref, version, flags and type_class, and those are passed as the first
  59    five arguments. The caller then computes sym, symidx, strtab, and map
  60    and passes them as the next four arguments. Lastly the caller passes in
  61    versioned_sym and num_versions which are modified by check_match during
  62    the checking process.  */
  63 static const ElfW(Sym) *
  64 check_match (const char *const undef_name,
  65              const ElfW(Sym) *const ref,
  66              const struct r_found_version *const version,
  67              const int flags,
  68              const int type_class,
  69              const ElfW(Sym) *const sym,
  70              const Elf_Symndx symidx,
  71              const char *const strtab,
  72              const struct link_map *const map,
  73              const ElfW(Sym) **const versioned_sym,
  74              int *const num_versions)
  75 {
  76   unsigned int stt = ELFW(ST_TYPE) (sym->st_info);
  77   assert (ELF_RTYPE_CLASS_PLT == 1);
  78   if (__glibc_unlikely ((sym->st_value == 0 /* No value.  */
  79                          && sym->st_shndx != SHN_ABS
  80                          && stt != STT_TLS)
  81                         || ELF_MACHINE_SYM_NO_MATCH (sym)
  82                         || (type_class & (sym->st_shndx == SHN_UNDEF))))
  83     return NULL;
  84
  85   /* Ignore all but STT_NOTYPE, STT_OBJECT, STT_FUNC,
  86      STT_COMMON, STT_TLS, and STT_GNU_IFUNC since these are no
  87      code/data definitions.  */
  88 #define ALLOWED_STT \
  89   ((1 << STT_NOTYPE) | (1 << STT_OBJECT) | (1 << STT_FUNC) \
  90    | (1 << STT_COMMON) | (1 << STT_TLS) | (1 << STT_GNU_IFUNC))
  91   if (__glibc_unlikely (((1 << stt) & ALLOWED_STT) == 0))
  92     return NULL;
  93
  94   if (sym != ref && strcmp (strtab + sym->st_name, undef_name))
  95     /* Not the symbol we are looking for.  */
  96     return NULL;
  97
  98   const ElfW(Half) *verstab = map->l_versyms;
  99   if (version != NULL)
 100     {
 101       if (__glibc_unlikely (verstab == NULL))
 102         {
 103           /* We need a versioned symbol but haven't found any.  If
 104              this is the object which is referenced in the verneed
 105              entry it is a bug in the library since a symbol must
 106              not simply disappear.
 107
 108              It would also be a bug in the object since it means that
 109              the list of required versions is incomplete and so the
 110              tests in dl-version.c haven't found a problem.*/
 111           assert (version->filename == NULL
 112                   || ! _dl_name_match_p (version->filename, map));
 113
 114           /* Otherwise we accept the symbol.  */
 115         }
 116       else
 117         {
 118           /* We can match the version information or use the
 119              default one if it is not hidden.  */
 120           ElfW(Half) ndx = verstab[symidx] & 0x7fff;
 121           if ((map->l_versions[ndx].hash != version->hash
 122                || strcmp (map->l_versions[ndx].name, version->name))
 123               && (version->hidden || map->l_versions[ndx].hash
 124                   || (verstab[symidx] & 0x8000)))
 125             /* It's not the version we want.  */
 126             return NULL;
 127         }
 128     }
 129   else
 130     {
 131       /* No specific version is selected.  There are two ways we
 132          can got here:
 133
 134          - a binary which does not include versioning information
 135          is loaded
 136
 137          - dlsym() instead of dlvsym() is used to get a symbol which
 138          might exist in more than one form
 139
 140          If the library does not provide symbol version information
 141          there is no problem at all: we simply use the symbol if it
 142          is defined.
 143
 144          These two lookups need to be handled differently if the
 145          library defines versions.  In the case of the old
 146          unversioned application the oldest (default) version
 147          should be used.  In case of a dlsym() call the latest and
 148          public interface should be returned.  */
 149       if (verstab != NULL)
 150         {
 151           if ((verstab[symidx] & 0x7fff)
 152               >= ((flags & DL_LOOKUP_RETURN_NEWEST) ? 2 : 3))
 153             {
 154               /* Don't accept hidden symbols.  */
 155               if ((verstab[symidx] & 0x8000) == 0
 156                   && (*num_versions)++ == 0)
 157                 /* No version so far.  */
 158                 *versioned_sym = sym;
 159
 160               return NULL;
 161             }
 162         }
 163     }
 164
 165   /* There cannot be another entry for this symbol so stop here.  */
 166   return sym;
 167 }
 168
 169 /* Utility function for do_lookup_unique.  Add a symbol to TABLE.  */
 170 static void
 171 enter_unique_sym (struct unique_sym *table, size_t size,
 172                   unsigned int hash, const char *name,
 173                   const ElfW(Sym) *sym, const struct link_map *map)
 174 {
 175   size_t idx = hash % size;
 176   size_t hash2 = 1 + hash % (size - 2);
 177   while (table[idx].name != NULL)
 178     {
 179       idx += hash2;
 180       if (idx >= size)
 181         idx -= size;
 182     }
 183
 184   table[idx].hashval = hash;
 185   table[idx].name = name;
 186   table[idx].sym = sym;
 187   table[idx].map = map;
 188 }
 189
 190 /* Utility function for do_lookup_x. Lookup an STB_GNU_UNIQUE symbol
 191    in the unique symbol table, creating a new entry if necessary.
 192    Return the matching symbol in RESULT.  */
 193 static void
 194 do_lookup_unique (const char *undef_name, uint_fast32_t new_hash,
 195                   const struct link_map *map, struct sym_val *result,
 196                   int type_class, const ElfW(Sym) *sym, const char *strtab,
 197                   const ElfW(Sym) *ref, const struct link_map *undef_map)
 198 {
 199   /* We have to determine whether we already found a symbol with this
 200      name before.  If not then we have to add it to the search table.
 201      If we already found a definition we have to use it.  */
 202
 203   struct unique_sym_table *tab
 204     = &GL(dl_ns)[map->l_ns]._ns_unique_sym_table;
 205
 206   __rtld_lock_lock_recursive (tab->lock);
 207
 208   struct unique_sym *entries = tab->entries;
 209   size_t size = tab->size;
 210   if (entries != NULL)
 211     {
 212       size_t idx = new_hash % size;
 213       size_t hash2 = 1 + new_hash % (size - 2);
 214       while (1)
 215         {
 216           if (entries[idx].hashval == new_hash
 217               && strcmp (entries[idx].name, undef_name) == 0)
 218             {
 219               if ((type_class & ELF_RTYPE_CLASS_COPY) != 0)
 220                 {
 221                   /* We possibly have to initialize the central
 222                      copy from the copy addressed through the
 223                      relocation.  */
 224                   result->s = sym;
 225                   result->m = (struct link_map *) map;
 226                 }
 227               else
 228                 {
 229                   result->s = entries[idx].sym;
 230                   result->m = (struct link_map *) entries[idx].map;
 231                 }
 232               __rtld_lock_unlock_recursive (tab->lock);
 233               return;
 234             }
 235
 236           if (entries[idx].name == NULL)
 237             break;
 238
 239           idx += hash2;
 240           if (idx >= size)
 241             idx -= size;
 242         }
 243
 244       if (size * 3 <= tab->n_elements * 4)
 245         {
 246           /* Expand the table.  */
 247 #ifdef RTLD_CHECK_FOREIGN_CALL
 248           /* This must not happen during runtime relocations.  */
 249           assert (!RTLD_CHECK_FOREIGN_CALL);
 250 #endif
 251           size_t newsize = _dl_higher_prime_number (size + 1);
 252           struct unique_sym *newentries
 253             = calloc (sizeof (struct unique_sym), newsize);
 254           if (newentries == NULL)
 255             {
 256             nomem:
 257               __rtld_lock_unlock_recursive (tab->lock);
 258               _dl_fatal_printf ("out of memory\n");
 259             }
 260
 261           for (idx = 0; idx < size; ++idx)
 262             if (entries[idx].name != NULL)
 263               enter_unique_sym (newentries, newsize, entries[idx].hashval,
 264                                 entries[idx].name, entries[idx].sym,
 265                                 entries[idx].map);
 266
 267           tab->free (entries);
 268           tab->size = newsize;
 269           size = newsize;
 270           entries = tab->entries = newentries;
 271           tab->free = free;
 272         }
 273     }
 274   else
 275     {
 276 #ifdef RTLD_CHECK_FOREIGN_CALL
 277       /* This must not happen during runtime relocations.  */
 278       assert (!RTLD_CHECK_FOREIGN_CALL);
 279 #endif
 280
 281 #ifdef SHARED
 282       /* If tab->entries is NULL, but tab->size is not, it means
 283          this is the second, conflict finding, lookup for
 284          LD_TRACE_PRELINKING in _dl_debug_bindings.  Don't
 285          allocate anything and don't enter anything into the
 286          hash table.  */
 287       if (__glibc_unlikely (tab->size))
 288         {
 289           assert (GLRO(dl_debug_mask) & DL_DEBUG_PRELINK);
 290           goto success;
 291         }
 292 #endif
 293
 294 #define INITIAL_NUNIQUE_SYM_TABLE 31
 295       size = INITIAL_NUNIQUE_SYM_TABLE;
 296       entries = calloc (sizeof (struct unique_sym), size);
 297       if (entries == NULL)
 298         goto nomem;
 299
 300       tab->entries = entries;
 301       tab->size = size;
 302       tab->free = free;
 303     }
 304
 305   if ((type_class & ELF_RTYPE_CLASS_COPY) != 0)
 306     enter_unique_sym (entries, size, new_hash, strtab + sym->st_name, ref,
 307            undef_map);
 308   else
 309     {
 310       enter_unique_sym (entries, size,
 311                         new_hash, strtab + sym->st_name, sym, map);
 312
 313       if (map->l_type == lt_loaded)
 314         /* Make sure we don't unload this object by
 315            setting the appropriate flag.  */
 316         ((struct link_map *) map)->l_flags_1 |= DF_1_NODELETE;
 317     }
 318   ++tab->n_elements;
 319
 320 #ifdef SHARED
 321  success:
 322 #endif
 323   __rtld_lock_unlock_recursive (tab->lock);
 324
 325   result->s = sym;
 326   result->m = (struct link_map *) map;
 327 }
 328
 329 /* Inner part of the lookup functions.  We return a value > 0 if we
 330    found the symbol, the value 0 if nothing is found and < 0 if
 331    something bad happened.  */
 332 static int
 333 __attribute_noinline__
 334 do_lookup_x (const char *undef_name, uint_fast32_t new_hash,
 335              unsigned long int *old_hash, const ElfW(Sym) *ref,
 336              struct sym_val *result, struct r_scope_elem *scope, size_t i,
 337              const struct r_found_version *const version, int flags,
 338              struct link_map *skip, int type_class, struct link_map *undef_map)
 339 {
 340   size_t n = scope->r_nlist;
 341   /* Make sure we read the value before proceeding.  Otherwise we
 342      might use r_list pointing to the initial scope and r_nlist being
 343      the value after a resize.  That is the only path in dl-open.c not
 344      protected by GSCOPE.  A read barrier here might be to expensive.  */
 345   __asm volatile ("" : "+r" (n), "+m" (scope->r_list));
 346   struct link_map **list = scope->r_list;
 347
 348   do
 349     {
 350       const struct link_map *map = list[i]->l_real;
 351
 352       /* Here come the extra test needed for `_dl_lookup_symbol_skip'.  */
 353       if (map == skip)
 354         continue;
 355
 356       /* Don't search the executable when resolving a copy reloc.  */
 357       if ((type_class & ELF_RTYPE_CLASS_COPY) && map->l_type == lt_executable)
 358         continue;
 359
 360       /* Do not look into objects which are going to be removed.  */
 361       if (map->l_removed)
 362         continue;
 363
 364       /* Print some debugging info if wanted.  */
 365       if (__glibc_unlikely (GLRO(dl_debug_mask) & DL_DEBUG_SYMBOLS))
 366         _dl_debug_printf ("symbol=%s;  lookup in file=%s [%lu]\n",
 367                           undef_name, DSO_FILENAME (map->l_name),
 368                           map->l_ns);
 369
 370       /* If the hash table is empty there is nothing to do here.  */
 371       if (map->l_nbuckets == 0)
 372         continue;
 373
 374       Elf_Symndx symidx;
 375       int num_versions = 0;
 376       const ElfW(Sym) *versioned_sym = NULL;
 377
 378       /* The tables for this map.  */
 379       const ElfW(Sym) *symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]);
 380       const char *strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]);
 381
 382       const ElfW(Sym) *sym;
 383       const ElfW(Addr) *bitmask = map->l_gnu_bitmask;
 384       if (__glibc_likely (bitmask != NULL))
 385         {
 386           ElfW(Addr) bitmask_word
 387             = bitmask[(new_hash / __ELF_NATIVE_CLASS)
 388                       & map->l_gnu_bitmask_idxbits];
 389
 390           unsigned int hashbit1 = new_hash & (__ELF_NATIVE_CLASS - 1);
 391           unsigned int hashbit2 = ((new_hash >> map->l_gnu_shift)
 392                                    & (__ELF_NATIVE_CLASS - 1));
 393
 394           if (__glibc_unlikely ((bitmask_word >> hashbit1)
 395                                 & (bitmask_word >> hashbit2) & 1))
 396             {
 397               Elf32_Word bucket = map->l_gnu_buckets[new_hash
 398                                                      % map->l_nbuckets];
 399               if (bucket != 0)
 400                 {
 401                   const Elf32_Word *hasharr = &map->l_gnu_chain_zero[bucket];
 402
 403                   do
 404                     if (((*hasharr ^ new_hash) >> 1) == 0)
 405                       {
 406                         symidx = ELF_MACHINE_HASH_SYMIDX (map, hasharr);
 407                         sym = check_match (undef_name, ref, version, flags,
 408                                            type_class, &symtab[symidx], symidx,
 409                                            strtab, map, &versioned_sym,
 410                                            &num_versions);
 411                         if (sym != NULL)
 412                           goto found_it;
 413                       }
 414                   while ((*hasharr++ & 1u) == 0);
 415                 }
 416             }
 417           /* No symbol found.  */
 418           symidx = SHN_UNDEF;
 419         }
 420       else
 421         {
 422           if (*old_hash == 0xffffffff)
 423             *old_hash = _dl_elf_hash (undef_name);
 424
 425           /* Use the old SysV-style hash table.  Search the appropriate
 426              hash bucket in this object's symbol table for a definition
 427              for the same symbol name.  */
 428           for (symidx = map->l_buckets[*old_hash % map->l_nbuckets];
 429                symidx != STN_UNDEF;
 430                symidx = map->l_chain[symidx])
 431             {
 432               sym = check_match (undef_name, ref, version, flags,
 433                                  type_class, &symtab[symidx], symidx,
 434                                  strtab, map, &versioned_sym,
 435                                  &num_versions);
 436               if (sym != NULL)
 437                 goto found_it;
 438             }
 439         }
 440
 441       /* If we have seen exactly one versioned symbol while we are
 442          looking for an unversioned symbol and the version is not the
 443          default version we still accept this symbol since there are
 444          no possible ambiguities.  */
 445       sym = num_versions == 1 ? versioned_sym : NULL;
 446
 447       if (sym != NULL)
 448         {
 449         found_it:
 450           /* When UNDEF_MAP is NULL, which indicates we are called from
 451              do_lookup_x on relocation against protected data, we skip
 452              the data definion in the executable from copy reloc.  */
 453           if (ELF_RTYPE_CLASS_EXTERN_PROTECTED_DATA
 454               && undef_map == NULL
 455               && map->l_type == lt_executable
 456               && type_class == ELF_RTYPE_CLASS_EXTERN_PROTECTED_DATA)
 457             {
 458               const ElfW(Sym) *s;
 459               unsigned int i;
 460
 461 #if ! ELF_MACHINE_NO_RELA
 462               if (map->l_info[DT_RELA] != NULL
 463                   && map->l_info[DT_RELASZ] != NULL
 464                   && map->l_info[DT_RELASZ]->d_un.d_val != 0)
 465                 {
 466                   const ElfW(Rela) *rela
 467                     = (const ElfW(Rela) *) D_PTR (map, l_info[DT_RELA]);
 468                   unsigned int rela_count
 469                     = map->l_info[DT_RELASZ]->d_un.d_val / sizeof (*rela);
 470
 471                   for (i = 0; i < rela_count; i++, rela++)
 472                     if (elf_machine_type_class (ELFW(R_TYPE) (rela->r_info))
 473                         == ELF_RTYPE_CLASS_COPY)
 474                       {
 475                         s = &symtab[ELFW(R_SYM) (rela->r_info)];
 476                         if (!strcmp (strtab + s->st_name, undef_name))
 477                           goto skip;
 478                       }
 479                 }
 480 #endif
 481 #if ! ELF_MACHINE_NO_REL
 482               if (map->l_info[DT_REL] != NULL
 483                   && map->l_info[DT_RELSZ] != NULL
 484                   && map->l_info[DT_RELSZ]->d_un.d_val != 0)
 485                 {
 486                   const ElfW(Rel) *rel
 487                     = (const ElfW(Rel) *) D_PTR (map, l_info[DT_REL]);
 488                   unsigned int rel_count
 489                     = map->l_info[DT_RELSZ]->d_un.d_val / sizeof (*rel);
 490
 491                   for (i = 0; i < rel_count; i++, rel++)
 492                     if (elf_machine_type_class (ELFW(R_TYPE) (rel->r_info))
 493                         == ELF_RTYPE_CLASS_COPY)
 494                       {
 495                         s = &symtab[ELFW(R_SYM) (rel->r_info)];
 496                         if (!strcmp (strtab + s->st_name, undef_name))
 497                           goto skip;
 498                       }
 499                 }
 500 #endif
 501             }
 502
 503           /* Hidden and internal symbols are local, ignore them.  */
 504           if (__glibc_unlikely (dl_symbol_visibility_binds_local_p (sym)))
 505             goto skip;
 506
 507           switch (ELFW(ST_BIND) (sym->st_info))
 508             {
 509             case STB_WEAK:
 510               /* Weak definition.  Use this value if we don't find another.  */
 511               if (__glibc_unlikely (GLRO(dl_dynamic_weak)))
 512                 {
 513                   if (! result->s)
 514                     {
 515                       result->s = sym;
 516                       result->m = (struct link_map *) map;
 517                     }
 518                   break;
 519                 }
 520               /* FALLTHROUGH */
 521             case STB_GLOBAL:
 522               /* Global definition.  Just what we need.  */
 523               result->s = sym;
 524               result->m = (struct link_map *) map;
 525               return 1;
 526
 527             case STB_GNU_UNIQUE:;
 528               do_lookup_unique (undef_name, new_hash, map, result, type_class,
 529                                 sym, strtab, ref, undef_map);
 530               return 1;
 531
 532             default:
 533               /* Local symbols are ignored.  */
 534               break;
 535             }
 536         }
 537
 538 skip:
 539       ;
 540     }
 541   while (++i < n);
 542
 543   /* We have not found anything until now.  */
 544   return 0;
 545 }
 546
 547
 548 static uint_fast32_t
 549 dl_new_hash (const char *s)
 550 {
 551   uint_fast32_t h = 5381;
 552   for (unsigned char c = *s; c != '\0'; c = *++s)
 553     h = h * 33 + c;
 554   return h & 0xffffffff;
 555 }
 556
 557
 558 /* Add extra dependency on MAP to UNDEF_MAP.  */
 559 static int
 560 add_dependency (struct link_map *undef_map, struct link_map *map, int flags)
 561 {
 562   struct link_map *runp;
 563   unsigned int i;
 564   int result = 0;
 565
 566   /* Avoid self-references and references to objects which cannot be
 567      unloaded anyway.  */
 568   if (undef_map == map)
 569     return 0;
 570
 571   /* Avoid references to objects which cannot be unloaded anyway.  */
 572   assert (map->l_type == lt_loaded);
 573   if ((map->l_flags_1 & DF_1_NODELETE) != 0)
 574     return 0;
 575
 576   struct link_map_reldeps *l_reldeps
 577     = atomic_forced_read (undef_map->l_reldeps);
 578
 579   /* Make sure l_reldeps is read before l_initfini.  */
 580   atomic_read_barrier ();
 581
 582   /* Determine whether UNDEF_MAP already has a reference to MAP.  First
 583      look in the normal dependencies.  */
 584   struct link_map **l_initfini = atomic_forced_read (undef_map->l_initfini);
 585   if (l_initfini != NULL)
 586     {
 587       for (i = 0; l_initfini[i] != NULL; ++i)
 588         if (l_initfini[i] == map)
 589           return 0;
 590     }
 591
 592   /* No normal dependency.  See whether we already had to add it
 593      to the special list of dynamic dependencies.  */
 594   unsigned int l_reldepsact = 0;
 595   if (l_reldeps != NULL)
 596     {
 597       struct link_map **list = &l_reldeps->list[0];
 598       l_reldepsact = l_reldeps->act;
 599       for (i = 0; i < l_reldepsact; ++i)
 600         if (list[i] == map)
 601           return 0;
 602     }
 603
 604   /* Save serial number of the target MAP.  */
 605   unsigned long long serial = map->l_serial;
 606
 607   /* Make sure nobody can unload the object while we are at it.  */
 608   if (__glibc_unlikely (flags & DL_LOOKUP_GSCOPE_LOCK))
 609     {
 610       /* We can't just call __rtld_lock_lock_recursive (GL(dl_load_lock))
 611          here, that can result in ABBA deadlock.  */
 612       THREAD_GSCOPE_RESET_FLAG ();
 613       __rtld_lock_lock_recursive (GL(dl_load_lock));
 614       /* While MAP value won't change, after THREAD_GSCOPE_RESET_FLAG ()
 615          it can e.g. point to unallocated memory.  So avoid the optimizer
 616          treating the above read from MAP->l_serial as ensurance it
 617          can safely dereference it.  */
 618       map = atomic_forced_read (map);
 619
 620       /* From this point on it is unsafe to dereference MAP, until it
 621          has been found in one of the lists.  */
 622
 623       /* Redo the l_initfini check in case undef_map's l_initfini
 624          changed in the mean time.  */
 625       if (undef_map->l_initfini != l_initfini
 626           && undef_map->l_initfini != NULL)
 627         {
 628           l_initfini = undef_map->l_initfini;
 629           for (i = 0; l_initfini[i] != NULL; ++i)
 630             if (l_initfini[i] == map)
 631               goto out_check;
 632         }
 633
 634       /* Redo the l_reldeps check if undef_map's l_reldeps changed in
 635          the mean time.  */
 636       if (undef_map->l_reldeps != NULL)
 637         {
 638           if (undef_map->l_reldeps != l_reldeps)
 639             {
 640               struct link_map **list = &undef_map->l_reldeps->list[0];
 641               l_reldepsact = undef_map->l_reldeps->act;
 642               for (i = 0; i < l_reldepsact; ++i)
 643                 if (list[i] == map)
 644                   goto out_check;
 645             }
 646           else if (undef_map->l_reldeps->act > l_reldepsact)
 647             {
 648               struct link_map **list
 649                 = &undef_map->l_reldeps->list[0];
 650               i = l_reldepsact;
 651               l_reldepsact = undef_map->l_reldeps->act;
 652               for (; i < l_reldepsact; ++i)
 653                 if (list[i] == map)
 654                   goto out_check;
 655             }
 656         }
 657     }
 658   else
 659     __rtld_lock_lock_recursive (GL(dl_load_lock));
 660
 661   /* The object is not yet in the dependency list.  Before we add
 662      it make sure just one more time the object we are about to
 663      reference is still available.  There is a brief period in
 664      which the object could have been removed since we found the
 665      definition.  */
 666   runp = GL(dl_ns)[undef_map->l_ns]._ns_loaded;
 667   while (runp != NULL && runp != map)
 668     runp = runp->l_next;
 669
 670   if (runp != NULL)
 671     {
 672       /* The object is still available.  */
 673
 674       /* MAP could have been dlclosed, freed and then some other dlopened
 675          library could have the same link_map pointer.  */
 676       if (map->l_serial != serial)
 677         goto out_check;
 678
 679       /* Redo the NODELETE check, as when dl_load_lock wasn't held
 680          yet this could have changed.  */
 681       if ((map->l_flags_1 & DF_1_NODELETE) != 0)
 682         goto out;
 683
 684       /* If the object with the undefined reference cannot be removed ever
 685          just make sure the same is true for the object which contains the
 686          definition.  */
 687       if (undef_map->l_type != lt_loaded
 688           || (undef_map->l_flags_1 & DF_1_NODELETE) != 0)
 689         {
 690           map->l_flags_1 |= DF_1_NODELETE;
 691           goto out;
 692         }
 693
 694       /* Add the reference now.  */
 695       if (__glibc_unlikely (l_reldepsact >= undef_map->l_reldepsmax))
 696         {
 697           /* Allocate more memory for the dependency list.  Since this
 698              can never happen during the startup phase we can use
 699              `realloc'.  */
 700           struct link_map_reldeps *newp;
 701           unsigned int max
 702             = undef_map->l_reldepsmax ? undef_map->l_reldepsmax * 2 : 10;
 703
 704 #ifdef RTLD_PREPARE_FOREIGN_CALL
 705           RTLD_PREPARE_FOREIGN_CALL;
 706 #endif
 707
 708           newp = malloc (sizeof (*newp) + max * sizeof (struct link_map *));
 709           if (newp == NULL)
 710             {
 711               /* If we didn't manage to allocate memory for the list this is
 712                  no fatal problem.  We simply make sure the referenced object
 713                  cannot be unloaded.  This is semantically the correct
 714                  behavior.  */
 715               map->l_flags_1 |= DF_1_NODELETE;
 716               goto out;
 717             }
 718           else
 719             {
 720               if (l_reldepsact)
 721                 memcpy (&newp->list[0], &undef_map->l_reldeps->list[0],
 722                         l_reldepsact * sizeof (struct link_map *));
 723               newp->list[l_reldepsact] = map;
 724               newp->act = l_reldepsact + 1;
 725               atomic_write_barrier ();
 726               void *old = undef_map->l_reldeps;
 727               undef_map->l_reldeps = newp;
 728               undef_map->l_reldepsmax = max;
 729               if (old)
 730                 _dl_scope_free (old);
 731             }
 732         }
 733       else
 734         {
 735           undef_map->l_reldeps->list[l_reldepsact] = map;
 736           atomic_write_barrier ();
 737           undef_map->l_reldeps->act = l_reldepsact + 1;
 738         }
 739
 740       /* Display information if we are debugging.  */
 741       if (__glibc_unlikely (GLRO(dl_debug_mask) & DL_DEBUG_FILES))
 742         _dl_debug_printf ("\
 743 \nfile=%s [%lu];  needed by %s [%lu] (relocation dependency)\n\n",
 744                           DSO_FILENAME (map->l_name),
 745                           map->l_ns,
 746                           DSO_FILENAME (undef_map->l_name),
 747                           undef_map->l_ns);
 748     }
 749   else
 750     /* Whoa, that was bad luck.  We have to search again.  */
 751     result = -1;
 752
 753  out:
 754   /* Release the lock.  */
 755   __rtld_lock_unlock_recursive (GL(dl_load_lock));
 756
 757   if (__glibc_unlikely (flags & DL_LOOKUP_GSCOPE_LOCK))
 758     THREAD_GSCOPE_SET_FLAG ();
 759
 760   return result;
 761
 762  out_check:
 763   if (map->l_serial != serial)
 764     result = -1;
 765   goto out;
 766 }
 767
 768 static void
 769 _dl_debug_bindings (const char *undef_name, struct link_map *undef_map,
 770                     const ElfW(Sym) **ref, struct sym_val *value,
 771                     const struct r_found_version *version, int type_class,
 772                     int protected);
 773
 774
 775 /* Search loaded objects' symbol tables for a definition of the symbol
 776    UNDEF_NAME, perhaps with a requested version for the symbol.
 777
 778    We must never have calls to the audit functions inside this function
 779    or in any function which gets called.  If this would happen the audit
 780    code might create a thread which can throw off all the scope locking.  */
 781 lookup_t
 782 _dl_lookup_symbol_x (const char *undef_name, struct link_map *undef_map,
 783                      const ElfW(Sym) **ref,
 784                      struct r_scope_elem *symbol_scope[],
 785                      const struct r_found_version *version,
 786                      int type_class, int flags, struct link_map *skip_map)
 787 {
 788   const uint_fast32_t new_hash = dl_new_hash (undef_name);
 789   unsigned long int old_hash = 0xffffffff;
 790   struct sym_val current_value = { NULL, NULL };
 791   struct r_scope_elem **scope = symbol_scope;
 792
 793   bump_num_relocations ();
 794
 795   /* DL_LOOKUP_RETURN_NEWEST does not make sense for versioned
 796      lookups.  */
 797   assert (version == NULL || !(flags & DL_LOOKUP_RETURN_NEWEST));
 798
 799   size_t i = 0;
 800   if (__glibc_unlikely (skip_map != NULL))
 801     /* Search the relevant loaded objects for a definition.  */
 802     while ((*scope)->r_list[i] != skip_map)
 803       ++i;
 804
 805   /* Search the relevant loaded objects for a definition.  */
 806   for (size_t start = i; *scope != NULL; start = 0, ++scope)
 807     if (do_lookup_x (undef_name, new_hash, &old_hash, *ref,
 808                      &current_value, *scope, start, version, flags,
 809                      skip_map, type_class, undef_map) != 0)
 810       break;
 811
 812   if (__glibc_unlikely (current_value.s == NULL))
 813     {
 814       if ((*ref == NULL || ELFW(ST_BIND) ((*ref)->st_info) != STB_WEAK)
 815           && !(GLRO(dl_debug_mask) & DL_DEBUG_UNUSED))
 816         {
 817           /* We could find no value for a strong reference.  */
 818           const char *reference_name = undef_map ? undef_map->l_name : "";
 819           const char *versionstr = version ? ", version " : "";
 820           const char *versionname = (version && version->name
 821                                      ? version->name : "");
 822           struct dl_exception exception;
 823           /* XXX We cannot translate the message.  */
 824           _dl_exception_create_format
 825             (&exception, DSO_FILENAME (reference_name),
 826              "undefined symbol: %s%s%s",
 827              undef_name, versionstr, versionname);
 828           _dl_signal_cexception (0, &exception, N_("symbol lookup error"));
 829           _dl_exception_free (&exception);
 830         }
 831       *ref = NULL;
 832       return 0;
 833     }
 834
 835   int protected = (*ref
 836                    && ELFW(ST_VISIBILITY) ((*ref)->st_other) == STV_PROTECTED);
 837   if (__glibc_unlikely (protected != 0))
 838     {
 839       /* It is very tricky.  We need to figure out what value to
 840          return for the protected symbol.  */
 841       if (type_class == ELF_RTYPE_CLASS_PLT)
 842         {
 843           if (current_value.s != NULL && current_value.m != undef_map)
 844             {
 845               current_value.s = *ref;
 846               current_value.m = undef_map;
 847             }
 848         }
 849       else
 850         {
 851           struct sym_val protected_value = { NULL, NULL };
 852
 853           for (scope = symbol_scope; *scope != NULL; i = 0, ++scope)
 854             if (do_lookup_x (undef_name, new_hash, &old_hash, *ref,
 855                              &protected_value, *scope, i, version, flags,
 856                              skip_map,
 857                              (ELF_RTYPE_CLASS_EXTERN_PROTECTED_DATA
 858                               && ELFW(ST_TYPE) ((*ref)->st_info) == STT_OBJECT
 859                               && type_class == ELF_RTYPE_CLASS_EXTERN_PROTECTED_DATA)
 860                              ? ELF_RTYPE_CLASS_EXTERN_PROTECTED_DATA
 861                              : ELF_RTYPE_CLASS_PLT, NULL) != 0)
 862               break;
 863
 864           if (protected_value.s != NULL && protected_value.m != undef_map)
 865             {
 866               current_value.s = *ref;
 867               current_value.m = undef_map;
 868             }
 869         }
 870     }
 871
 872   /* We have to check whether this would bind UNDEF_MAP to an object
 873      in the global scope which was dynamically loaded.  In this case
 874      we have to prevent the latter from being unloaded unless the
 875      UNDEF_MAP object is also unloaded.  */
 876   if (__glibc_unlikely (current_value.m->l_type == lt_loaded)
 877       /* Don't do this for explicit lookups as opposed to implicit
 878          runtime lookups.  */
 879       && (flags & DL_LOOKUP_ADD_DEPENDENCY) != 0
 880       /* Add UNDEF_MAP to the dependencies.  */
 881       && add_dependency (undef_map, current_value.m, flags) < 0)
 882       /* Something went wrong.  Perhaps the object we tried to reference
 883          was just removed.  Try finding another definition.  */
 884       return _dl_lookup_symbol_x (undef_name, undef_map, ref,
 885                                   (flags & DL_LOOKUP_GSCOPE_LOCK)
 886                                   ? undef_map->l_scope : symbol_scope,
 887                                   version, type_class, flags, skip_map);
 888
 889   /* The object is used.  */
 890   if (__glibc_unlikely (current_value.m->l_used == 0))
 891     current_value.m->l_used = 1;
 892
 893   if (__glibc_unlikely (GLRO(dl_debug_mask)
 894                         & (DL_DEBUG_BINDINGS|DL_DEBUG_PRELINK)))
 895     _dl_debug_bindings (undef_name, undef_map, ref,
 896                         &current_value, version, type_class, protected);
 897
 898   *ref = current_value.s;
 899   return LOOKUP_VALUE (current_value.m);
 900 }
 901
 902
 903 /* Cache the location of MAP's hash table.  */
 904
 905 void
 906 _dl_setup_hash (struct link_map *map)
 907 {
 908   Elf_Symndx *hash;
 909
 910   if (__glibc_likely (map->l_info[ELF_MACHINE_GNU_HASH_ADDRIDX] != NULL))
 911     {
 912       Elf32_Word *hash32
 913         = (void *) D_PTR (map, l_info[ELF_MACHINE_GNU_HASH_ADDRIDX]);
 914       map->l_nbuckets = *hash32++;
 915       Elf32_Word symbias = *hash32++;
 916       Elf32_Word bitmask_nwords = *hash32++;
 917       /* Must be a power of two.  */
 918       assert ((bitmask_nwords & (bitmask_nwords - 1)) == 0);
 919       map->l_gnu_bitmask_idxbits = bitmask_nwords - 1;
 920       map->l_gnu_shift = *hash32++;
 921
 922       map->l_gnu_bitmask = (ElfW(Addr) *) hash32;
 923       hash32 += __ELF_NATIVE_CLASS / 32 * bitmask_nwords;
 924
 925       map->l_gnu_buckets = hash32;
 926       hash32 += map->l_nbuckets;
 927       map->l_gnu_chain_zero = hash32 - symbias;
 928
 929       /* Initialize MIPS xhash translation table.  */
 930       ELF_MACHINE_XHASH_SETUP (hash32, symbias, map);
 931
 932       return;
 933     }
 934
 935   if (!map->l_info[DT_HASH])
 936     return;
 937   hash = (void *) D_PTR (map, l_info[DT_HASH]);
 938
 939   map->l_nbuckets = *hash++;
 940   /* Skip nchain.  */
 941   hash++;
 942   map->l_buckets = hash;
 943   hash += map->l_nbuckets;
 944   map->l_chain = hash;
 945 }
 946
 947
 948 static void
 949 _dl_debug_bindings (const char *undef_name, struct link_map *undef_map,
 950                     const ElfW(Sym) **ref, struct sym_val *value,
 951                     const struct r_found_version *version, int type_class,
 952                     int protected)
 953 {
 954   const char *reference_name = undef_map->l_name;
 955
 956   if (GLRO(dl_debug_mask) & DL_DEBUG_BINDINGS)
 957     {
 958       _dl_debug_printf ("binding file %s [%lu] to %s [%lu]: %s symbol `%s'",
 959                         DSO_FILENAME (reference_name),
 960                         undef_map->l_ns,
 961                         DSO_FILENAME (value->m->l_name),
 962                         value->m->l_ns,
 963                         protected ? "protected" : "normal", undef_name);
 964       if (version)
 965         _dl_debug_printf_c (" [%s]\n", version->name);
 966       else
 967         _dl_debug_printf_c ("\n");
 968     }
 969 #ifdef SHARED
 970   if (GLRO(dl_debug_mask) & DL_DEBUG_PRELINK)
 971     {
 972 /* ELF_RTYPE_CLASS_XXX must match RTYPE_CLASS_XXX used by prelink with
 973    LD_TRACE_PRELINKING.  */
 974 #define RTYPE_CLASS_VALID       8
 975 #define RTYPE_CLASS_PLT         (8|1)
 976 #define RTYPE_CLASS_COPY        (8|2)
 977 #define RTYPE_CLASS_TLS         (8|4)
 978 #if ELF_RTYPE_CLASS_PLT != 0 && ELF_RTYPE_CLASS_PLT != 1
 979 # error ELF_RTYPE_CLASS_PLT must be 0 or 1!
 980 #endif
 981 #if ELF_RTYPE_CLASS_COPY != 0 && ELF_RTYPE_CLASS_COPY != 2
 982 # error ELF_RTYPE_CLASS_COPY must be 0 or 2!
 983 #endif
 984       int conflict = 0;
 985       struct sym_val val = { NULL, NULL };
 986
 987       if ((GLRO(dl_trace_prelink_map) == NULL
 988            || GLRO(dl_trace_prelink_map) == GL(dl_ns)[LM_ID_BASE]._ns_loaded)
 989           && undef_map != GL(dl_ns)[LM_ID_BASE]._ns_loaded)
 990         {
 991           const uint_fast32_t new_hash = dl_new_hash (undef_name);
 992           unsigned long int old_hash = 0xffffffff;
 993           struct unique_sym *saved_entries
 994             = GL(dl_ns)[LM_ID_BASE]._ns_unique_sym_table.entries;
 995
 996           GL(dl_ns)[LM_ID_BASE]._ns_unique_sym_table.entries = NULL;
 997           do_lookup_x (undef_name, new_hash, &old_hash, *ref, &val,
 998                        undef_map->l_local_scope[0], 0, version, 0, NULL,
 999                        type_class, undef_map);
1000           if (val.s != value->s || val.m != value->m)
1001             conflict = 1;
1002           else if (__glibc_unlikely (undef_map->l_symbolic_in_local_scope)
1003                    && val.s
1004                    && __glibc_unlikely (ELFW(ST_BIND) (val.s->st_info)
1005                                         == STB_GNU_UNIQUE))
1006             {
1007               /* If it is STB_GNU_UNIQUE and undef_map's l_local_scope
1008                  contains any DT_SYMBOLIC libraries, unfortunately there
1009                  can be conflicts even if the above is equal.  As symbol
1010                  resolution goes from the last library to the first and
1011                  if a STB_GNU_UNIQUE symbol is found in some late DT_SYMBOLIC
1012                  library, it would be the one that is looked up.  */
1013               struct sym_val val2 = { NULL, NULL };
1014               size_t n;
1015               struct r_scope_elem *scope = undef_map->l_local_scope[0];
1016
1017               for (n = 0; n < scope->r_nlist; n++)
1018                 if (scope->r_list[n] == val.m)
1019                   break;
1020
1021               for (n++; n < scope->r_nlist; n++)
1022                 if (scope->r_list[n]->l_info[DT_SYMBOLIC] != NULL
1023                     && do_lookup_x (undef_name, new_hash, &old_hash, *ref,
1024                                     &val2,
1025                                     &scope->r_list[n]->l_symbolic_searchlist,
1026                                     0, version, 0, NULL, type_class,
1027                                     undef_map) > 0)
1028                   {
1029                     conflict = 1;
1030                     val = val2;
1031                     break;
1032                   }
1033             }
1034           GL(dl_ns)[LM_ID_BASE]._ns_unique_sym_table.entries = saved_entries;
1035         }
1036
1037       if (value->s)
1038         {
1039           /* Keep only ELF_RTYPE_CLASS_PLT and ELF_RTYPE_CLASS_COPY
1040              bits since since prelink only uses them.  */
1041           type_class &= ELF_RTYPE_CLASS_PLT | ELF_RTYPE_CLASS_COPY;
1042           if (__glibc_unlikely (ELFW(ST_TYPE) (value->s->st_info)
1043                                 == STT_TLS))
1044             /* Clear the RTYPE_CLASS_VALID bit in RTYPE_CLASS_TLS.  */
1045             type_class = RTYPE_CLASS_TLS & ~RTYPE_CLASS_VALID;
1046           else if (__glibc_unlikely (ELFW(ST_TYPE) (value->s->st_info)
1047                                      == STT_GNU_IFUNC))
1048             /* Set the RTYPE_CLASS_VALID bit.  */
1049             type_class |= RTYPE_CLASS_VALID;
1050         }
1051
1052       if (conflict
1053           || GLRO(dl_trace_prelink_map) == undef_map
1054           || GLRO(dl_trace_prelink_map) == NULL
1055           || type_class >= 4)
1056         {
1057           _dl_printf ("%s 0x%0*Zx 0x%0*Zx -> 0x%0*Zx 0x%0*Zx ",
1058                       conflict ? "conflict" : "lookup",
1059                       (int) sizeof (ElfW(Addr)) * 2,
1060                       (size_t) undef_map->l_map_start,
1061                       (int) sizeof (ElfW(Addr)) * 2,
1062                       (size_t) (((ElfW(Addr)) *ref) - undef_map->l_map_start),
1063                       (int) sizeof (ElfW(Addr)) * 2,
1064                       (size_t) (value->s ? value->m->l_map_start : 0),
1065                       (int) sizeof (ElfW(Addr)) * 2,
1066                       (size_t) (value->s ? value->s->st_value : 0));
1067
1068           if (conflict)
1069             _dl_printf ("x 0x%0*Zx 0x%0*Zx ",
1070                         (int) sizeof (ElfW(Addr)) * 2,
1071                         (size_t) (val.s ? val.m->l_map_start : 0),
1072                         (int) sizeof (ElfW(Addr)) * 2,
1073                         (size_t) (val.s ? val.s->st_value : 0));
1074
1075           _dl_printf ("/%x %s\n", type_class, undef_name);
1076         }
1077     }
1078 #endif
1079 }