elf/dl-lookup.c

   1 /* Look up a symbol in the loaded objects.
   2    Copyright (C) 1995-2005, 2006, 2007 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, write to the Free
  17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  18    02111-1307 USA.  */
  19
  20 #include <alloca.h>
  21 #include <libintl.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <unistd.h>
  25 #include <ldsodefs.h>
  26 #include <dl-hash.h>
  27 #include <dl-machine.h>
  28 #include <sysdep-cancel.h>
  29 #include <bits/libc-lock.h>
  30 #include <tls.h>
  31
  32 #include <assert.h>
  33
  34 #define VERSTAG(tag)    (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGIDX (tag))
  35
  36 /* We need this string more than once.  */
  37 static const char undefined_msg[] = "undefined symbol: ";
  38
  39
  40 struct sym_val
  41   {
  42     const ElfW(Sym) *s;
  43     struct link_map *m;
  44   };
  45
  46
  47 #define make_string(string, rest...) \
  48   ({                                                                          \
  49     const char *all[] = { string, ## rest };                                  \
  50     size_t len, cnt;                                                          \
  51     char *result, *cp;                                                        \
  52                                                                               \
  53     len = 1;                                                                  \
  54     for (cnt = 0; cnt < sizeof (all) / sizeof (all[0]); ++cnt)                \
  55       len += strlen (all[cnt]);                                               \
  56                                                                               \
  57     cp = result = alloca (len);                                               \
  58     for (cnt = 0; cnt < sizeof (all) / sizeof (all[0]); ++cnt)                \
  59       cp = __stpcpy (cp, all[cnt]);                                           \
  60                                                                               \
  61     result;                                                                   \
  62   })
  63
  64 /* Statistics function.  */
  65 #ifdef SHARED
  66 # define bump_num_relocations() ++GL(dl_num_relocations)
  67 #else
  68 # define bump_num_relocations() ((void) 0)
  69 #endif
  70
  71
  72 /* The actual lookup code.  */
  73 #include "do-lookup.h"
  74
  75
  76 static uint_fast32_t
  77 dl_new_hash (const char *s)
  78 {
  79   uint_fast32_t h = 5381;
  80   for (unsigned char c = *s; c != '\0'; c = *++s)
  81     h = h * 33 + c;
  82   return h & 0xffffffff;
  83 }
  84
  85
  86 /* Add extra dependency on MAP to UNDEF_MAP.  */
  87 static int
  88 internal_function
  89 add_dependency (struct link_map *undef_map, struct link_map *map, int flags)
  90 {
  91   struct link_map *runp;
  92   unsigned int i;
  93   int result = 0;
  94
  95   /* Avoid self-references and references to objects which cannot be
  96      unloaded anyway.  */
  97   if (undef_map == map)
  98     return 0;
  99
 100   /* Avoid references to objects which cannot be unloaded anyway.  */
 101   assert (map->l_type == lt_loaded);
 102   if ((map->l_flags_1 & DF_1_NODELETE) != 0)
 103     return 0;
 104
 105   struct link_map_reldeps *l_reldeps
 106     = atomic_forced_read (undef_map->l_reldeps);
 107
 108   /* Make sure l_reldeps is read before l_initfini.  */
 109   atomic_read_barrier ();
 110
 111   /* Determine whether UNDEF_MAP already has a reference to MAP.  First
 112      look in the normal dependencies.  */
 113   struct link_map **l_initfini = atomic_forced_read (undef_map->l_initfini);
 114   if (l_initfini != NULL)
 115     {
 116       for (i = 0; l_initfini[i] != NULL; ++i)
 117         if (l_initfini[i] == map)
 118           return 0;
 119     }
 120
 121   /* No normal dependency.  See whether we already had to add it
 122      to the special list of dynamic dependencies.  */
 123   unsigned int l_reldepsact = 0;
 124   if (l_reldeps != NULL)
 125     {
 126       struct link_map **list = &l_reldeps->list[0];
 127       l_reldepsact = l_reldeps->act;
 128       for (i = 0; i < l_reldepsact; ++i)
 129         if (list[i] == map)
 130           return 0;
 131     }
 132
 133   /* Save serial number of the target MAP.  */
 134   unsigned long long serial = map->l_serial;
 135
 136   /* Make sure nobody can unload the object while we are at it.  */
 137   if (__builtin_expect (flags & DL_LOOKUP_GSCOPE_LOCK, 0))
 138     {
 139       /* We can't just call __rtld_lock_lock_recursive (GL(dl_load_lock))
 140          here, that can result in ABBA deadlock.  */
 141       THREAD_GSCOPE_RESET_FLAG ();
 142       __rtld_lock_lock_recursive (GL(dl_load_lock));
 143       /* While MAP value won't change, after THREAD_GSCOPE_RESET_FLAG ()
 144          it can e.g. point to unallocated memory.  So avoid the optimizer
 145          treating the above read from MAP->l_serial as ensurance it
 146          can safely dereference it.  */
 147       map = atomic_forced_read (map);
 148
 149       /* From this point on it is unsafe to dereference MAP, until it
 150          has been found in one of the lists.  */
 151
 152       /* Redo the l_initfini check in case undef_map's l_initfini
 153          changed in the mean time.  */
 154       if (undef_map->l_initfini != l_initfini
 155           && undef_map->l_initfini != NULL)
 156         {
 157           l_initfini = undef_map->l_initfini;
 158           for (i = 0; l_initfini[i] != NULL; ++i)
 159             if (l_initfini[i] == map)
 160               goto out_check;
 161         }
 162
 163       /* Redo the l_reldeps check if undef_map's l_reldeps changed in
 164          the mean time.  */
 165       if (undef_map->l_reldeps != NULL)
 166         {
 167           if (undef_map->l_reldeps != l_reldeps)
 168             {
 169               struct link_map **list = &undef_map->l_reldeps->list[0];
 170               l_reldepsact = undef_map->l_reldeps->act;
 171               for (i = 0; i < l_reldepsact; ++i)
 172                 if (list[i] == map)
 173                   goto out_check;
 174             }
 175           else if (undef_map->l_reldeps->act > l_reldepsact)
 176             {
 177               struct link_map **list
 178                 = &undef_map->l_reldeps->list[0];
 179               i = l_reldepsact;
 180               l_reldepsact = undef_map->l_reldeps->act;
 181               for (; i < l_reldepsact; ++i)
 182                 if (list[i] == map)
 183                   goto out_check;
 184             }
 185         }
 186     }
 187   else
 188     __rtld_lock_lock_recursive (GL(dl_load_lock));
 189
 190   /* The object is not yet in the dependency list.  Before we add
 191      it make sure just one more time the object we are about to
 192      reference is still available.  There is a brief period in
 193      which the object could have been removed since we found the
 194      definition.  */
 195   runp = GL(dl_ns)[undef_map->l_ns]._ns_loaded;
 196   while (runp != NULL && runp != map)
 197     runp = runp->l_next;
 198
 199   if (runp != NULL)
 200     {
 201       /* The object is still available.  */
 202
 203       /* MAP could have been dlclosed, freed and then some other dlopened
 204          library could have the same link_map pointer.  */
 205       if (map->l_serial != serial)
 206         goto out_check;
 207
 208       /* Redo the NODELETE check, as when dl_load_lock wasn't held
 209          yet this could have changed.  */
 210       if ((map->l_flags_1 & DF_1_NODELETE) != 0)
 211         goto out;
 212
 213       /* If the object with the undefined reference cannot be removed ever
 214          just make sure the same is true for the object which contains the
 215          definition.  */
 216       if (undef_map->l_type != lt_loaded
 217           || (undef_map->l_flags_1 & DF_1_NODELETE) != 0)
 218         {
 219           map->l_flags_1 |= DF_1_NODELETE;
 220           goto out;
 221         }
 222
 223       /* Add the reference now.  */
 224       if (__builtin_expect (l_reldepsact >= undef_map->l_reldepsmax, 0))
 225         {
 226           /* Allocate more memory for the dependency list.  Since this
 227              can never happen during the startup phase we can use
 228              `realloc'.  */
 229           struct link_map_reldeps *newp;
 230           unsigned int max
 231             = undef_map->l_reldepsmax ? undef_map->l_reldepsmax * 2 : 10;
 232
 233           newp = malloc (sizeof (*newp) + max * sizeof (struct link_map *));
 234           if (newp == NULL)
 235             {
 236               /* If we didn't manage to allocate memory for the list this is
 237                  no fatal problem.  We simply make sure the referenced object
 238                  cannot be unloaded.  This is semantically the correct
 239                  behavior.  */
 240               map->l_flags_1 |= DF_1_NODELETE;
 241               goto out;
 242             }
 243           else
 244             {
 245               if (l_reldepsact)
 246                 memcpy (&newp->list[0], &undef_map->l_reldeps->list[0],
 247                         l_reldepsact * sizeof (struct link_map *));
 248               newp->list[l_reldepsact] = map;
 249               newp->act = l_reldepsact + 1;
 250               atomic_write_barrier ();
 251               void *old = undef_map->l_reldeps;
 252               undef_map->l_reldeps = newp;
 253               undef_map->l_reldepsmax = max;
 254               if (old)
 255                 _dl_scope_free (old);
 256             }
 257         }
 258       else
 259         {
 260           undef_map->l_reldeps->list[l_reldepsact] = map;
 261           atomic_write_barrier ();
 262           undef_map->l_reldeps->act = l_reldepsact + 1;
 263         }
 264
 265       /* Display information if we are debugging.  */
 266       if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_FILES, 0))
 267         _dl_debug_printf ("\
 268 \nfile=%s [%lu];  needed by %s [%lu] (relocation dependency)\n\n",
 269                           map->l_name[0] ? map->l_name : rtld_progname,
 270                           map->l_ns,
 271                           undef_map->l_name[0]
 272                           ? undef_map->l_name : rtld_progname,
 273                           undef_map->l_ns);
 274     }
 275   else
 276     /* Whoa, that was bad luck.  We have to search again.  */
 277     result = -1;
 278
 279  out:
 280   /* Release the lock.  */
 281   __rtld_lock_unlock_recursive (GL(dl_load_lock));
 282
 283   if (__builtin_expect (flags & DL_LOOKUP_GSCOPE_LOCK, 0))
 284     THREAD_GSCOPE_SET_FLAG ();
 285
 286   return result;
 287
 288  out_check:
 289   if (map->l_serial != serial)
 290     result = -1;
 291   goto out;
 292 }
 293
 294 static void
 295 internal_function
 296 _dl_debug_bindings (const char *undef_name, struct link_map *undef_map,
 297                     const ElfW(Sym) **ref, struct sym_val *value,
 298                     const struct r_found_version *version, int type_class,
 299                     int protected);
 300
 301
 302 /* Search loaded objects' symbol tables for a definition of the symbol
 303    UNDEF_NAME, perhaps with a requested version for the symbol.
 304
 305    We must never have calls to the audit functions inside this function
 306    or in any function which gets called.  If this would happen the audit
 307    code might create a thread which can throw off all the scope locking.  */
 308 lookup_t
 309 internal_function
 310 _dl_lookup_symbol_x (const char *undef_name, struct link_map *undef_map,
 311                      const ElfW(Sym) **ref,
 312                      struct r_scope_elem *symbol_scope[],
 313                      const struct r_found_version *version,
 314                      int type_class, int flags, struct link_map *skip_map)
 315 {
 316   const uint_fast32_t new_hash = dl_new_hash (undef_name);
 317   unsigned long int old_hash = 0xffffffff;
 318   struct sym_val current_value = { NULL, NULL };
 319   struct r_scope_elem **scope = symbol_scope;
 320
 321   bump_num_relocations ();
 322
 323   /* No other flag than DL_LOOKUP_ADD_DEPENDENCY or DL_LOOKUP_GSCOPE_LOCK
 324      is allowed if we look up a versioned symbol.  */
 325   assert (version == NULL
 326           || (flags & ~(DL_LOOKUP_ADD_DEPENDENCY | DL_LOOKUP_GSCOPE_LOCK))
 327              == 0);
 328
 329   size_t i = 0;
 330   if (__builtin_expect (skip_map != NULL, 0))
 331     /* Search the relevant loaded objects for a definition.  */
 332     while ((*scope)->r_list[i] != skip_map)
 333       ++i;
 334
 335   /* Search the relevant loaded objects for a definition.  */
 336   for (size_t start = i; *scope != NULL; start = 0, ++scope)
 337     {
 338       int res = do_lookup_x (undef_name, new_hash, &old_hash, *ref,
 339                              &current_value, *scope, start, version, flags,
 340                              skip_map, type_class);
 341       if (res > 0)
 342         break;
 343
 344       if (__builtin_expect (res, 0) < 0 && skip_map == NULL)
 345         {
 346           /* Oh, oh.  The file named in the relocation entry does not
 347              contain the needed symbol.  This code is never reached
 348              for unversioned lookups.  */
 349           assert (version != NULL);
 350           const char *reference_name = undef_map ? undef_map->l_name : NULL;
 351
 352           /* XXX We cannot translate the message.  */
 353           _dl_signal_cerror (0, (reference_name[0]
 354                                  ? reference_name
 355                                  : (rtld_progname ?: "<main program>")),
 356                              N_("relocation error"),
 357                              make_string ("symbol ", undef_name, ", version ",
 358                                           version->name,
 359                                           " not defined in file ",
 360                                           version->filename,
 361                                           " with link time reference",
 362                                           res == -2
 363                                           ? " (no version symbols)" : ""));
 364           *ref = NULL;
 365           return 0;
 366         }
 367     }
 368
 369   if (__builtin_expect (current_value.s == NULL, 0))
 370     {
 371       if ((*ref == NULL || ELFW(ST_BIND) ((*ref)->st_info) != STB_WEAK)
 372           && skip_map == NULL)
 373         {
 374           /* We could find no value for a strong reference.  */
 375           const char *reference_name = undef_map ? undef_map->l_name : "";
 376           const char *versionstr = version ? ", version " : "";
 377           const char *versionname = (version && version->name
 378                                      ? version->name : "");
 379
 380           /* XXX We cannot translate the message.  */
 381           _dl_signal_cerror (0, (reference_name[0]
 382                                  ? reference_name
 383                                  : (rtld_progname ?: "<main program>")),
 384                              N_("symbol lookup error"),
 385                              make_string (undefined_msg, undef_name,
 386                                           versionstr, versionname));
 387         }
 388       *ref = NULL;
 389       return 0;
 390     }
 391
 392   int protected = (*ref
 393                    && ELFW(ST_VISIBILITY) ((*ref)->st_other) == STV_PROTECTED);
 394   if (__builtin_expect (protected != 0, 0))
 395     {
 396       /* It is very tricky.  We need to figure out what value to
 397          return for the protected symbol.  */
 398       if (type_class == ELF_RTYPE_CLASS_PLT)
 399         {
 400           if (current_value.s != NULL && current_value.m != undef_map)
 401             {
 402               current_value.s = *ref;
 403               current_value.m = undef_map;
 404             }
 405         }
 406       else
 407         {
 408           struct sym_val protected_value = { NULL, NULL };
 409
 410           for (scope = symbol_scope; *scope != NULL; i = 0, ++scope)
 411             if (do_lookup_x (undef_name, new_hash, &old_hash, *ref,
 412                              &protected_value, *scope, i, version, flags,
 413                              skip_map, ELF_RTYPE_CLASS_PLT) != 0)
 414               break;
 415
 416           if (protected_value.s != NULL && protected_value.m != undef_map)
 417             {
 418               current_value.s = *ref;
 419               current_value.m = undef_map;
 420             }
 421         }
 422     }
 423
 424   /* We have to check whether this would bind UNDEF_MAP to an object
 425      in the global scope which was dynamically loaded.  In this case
 426      we have to prevent the latter from being unloaded unless the
 427      UNDEF_MAP object is also unloaded.  */
 428   if (__builtin_expect (current_value.m->l_type == lt_loaded, 0)
 429       /* Don't do this for explicit lookups as opposed to implicit
 430          runtime lookups.  */
 431       && (flags & DL_LOOKUP_ADD_DEPENDENCY) != 0
 432       /* Add UNDEF_MAP to the dependencies.  */
 433       && add_dependency (undef_map, current_value.m, flags) < 0)
 434       /* Something went wrong.  Perhaps the object we tried to reference
 435          was just removed.  Try finding another definition.  */
 436       return _dl_lookup_symbol_x (undef_name, undef_map, ref,
 437                                   (flags & DL_LOOKUP_GSCOPE_LOCK)
 438                                   ? undef_map->l_scope : symbol_scope,
 439                                   version, type_class, flags, skip_map);
 440
 441   /* The object is used.  */
 442   current_value.m->l_used = 1;
 443
 444   if (__builtin_expect (GLRO(dl_debug_mask)
 445                         & (DL_DEBUG_BINDINGS|DL_DEBUG_PRELINK), 0))
 446     _dl_debug_bindings (undef_name, undef_map, ref,
 447                         &current_value, version, type_class, protected);
 448
 449   *ref = current_value.s;
 450   return LOOKUP_VALUE (current_value.m);
 451 }
 452
 453
 454 /* Cache the location of MAP's hash table.  */
 455
 456 void
 457 internal_function
 458 _dl_setup_hash (struct link_map *map)
 459 {
 460   Elf_Symndx *hash;
 461   Elf_Symndx nchain;
 462
 463   if (__builtin_expect (map->l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM
 464                                     + DT_THISPROCNUM + DT_VERSIONTAGNUM
 465                                     + DT_EXTRANUM + DT_VALNUM] != NULL, 1))
 466     {
 467       Elf32_Word *hash32
 468         = (void *) D_PTR (map, l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM
 469                                       + DT_THISPROCNUM + DT_VERSIONTAGNUM
 470                                       + DT_EXTRANUM + DT_VALNUM]);
 471       map->l_nbuckets = *hash32++;
 472       Elf32_Word symbias = *hash32++;
 473       Elf32_Word bitmask_nwords = *hash32++;
 474       /* Must be a power of two.  */
 475       assert ((bitmask_nwords & (bitmask_nwords - 1)) == 0);
 476       map->l_gnu_bitmask_idxbits = bitmask_nwords - 1;
 477       map->l_gnu_shift = *hash32++;
 478
 479       map->l_gnu_bitmask = (ElfW(Addr) *) hash32;
 480       hash32 += __ELF_NATIVE_CLASS / 32 * bitmask_nwords;
 481
 482       map->l_gnu_buckets = hash32;
 483       hash32 += map->l_nbuckets;
 484       map->l_gnu_chain_zero = hash32 - symbias;
 485       return;
 486     }
 487
 488   if (!map->l_info[DT_HASH])
 489     return;
 490   hash = (void *) D_PTR (map, l_info[DT_HASH]);
 491
 492   map->l_nbuckets = *hash++;
 493   nchain = *hash++;
 494   map->l_buckets = hash;
 495   hash += map->l_nbuckets;
 496   map->l_chain = hash;
 497 }
 498
 499
 500 static void
 501 internal_function
 502 _dl_debug_bindings (const char *undef_name, struct link_map *undef_map,
 503                     const ElfW(Sym) **ref, struct sym_val *value,
 504                     const struct r_found_version *version, int type_class,
 505                     int protected)
 506 {
 507   const char *reference_name = undef_map->l_name;
 508
 509   if (GLRO(dl_debug_mask) & DL_DEBUG_BINDINGS)
 510     {
 511       _dl_debug_printf ("binding file %s [%lu] to %s [%lu]: %s symbol `%s'",
 512                         (reference_name[0]
 513                          ? reference_name
 514                          : (rtld_progname ?: "<main program>")),
 515                         undef_map->l_ns,
 516                         value->m->l_name[0] ? value->m->l_name : rtld_progname,
 517                         value->m->l_ns,
 518                         protected ? "protected" : "normal", undef_name);
 519       if (version)
 520         _dl_debug_printf_c (" [%s]\n", version->name);
 521       else
 522         _dl_debug_printf_c ("\n");
 523     }
 524 #ifdef SHARED
 525   if (GLRO(dl_debug_mask) & DL_DEBUG_PRELINK)
 526     {
 527       int conflict = 0;
 528       struct sym_val val = { NULL, NULL };
 529
 530       if ((GLRO(dl_trace_prelink_map) == NULL
 531            || GLRO(dl_trace_prelink_map) == GL(dl_ns)[LM_ID_BASE]._ns_loaded)
 532           && undef_map != GL(dl_ns)[LM_ID_BASE]._ns_loaded)
 533         {
 534           const uint_fast32_t new_hash = dl_new_hash (undef_name);
 535           unsigned long int old_hash = 0xffffffff;
 536
 537           do_lookup_x (undef_name, new_hash, &old_hash, *ref, &val,
 538                        undef_map->l_local_scope[0], 0, version, 0, NULL,
 539                        type_class);
 540
 541           if (val.s != value->s || val.m != value->m)
 542             conflict = 1;
 543         }
 544
 545       if (value->s
 546           && (__builtin_expect (ELFW(ST_TYPE) (value->s->st_info)
 547                                 == STT_TLS, 0)))
 548         type_class = 4;
 549
 550       if (conflict
 551           || GLRO(dl_trace_prelink_map) == undef_map
 552           || GLRO(dl_trace_prelink_map) == NULL
 553           || type_class == 4)
 554         {
 555           _dl_printf ("%s 0x%0*Zx 0x%0*Zx -> 0x%0*Zx 0x%0*Zx ",
 556                       conflict ? "conflict" : "lookup",
 557                       (int) sizeof (ElfW(Addr)) * 2,
 558                       (size_t) undef_map->l_map_start,
 559                       (int) sizeof (ElfW(Addr)) * 2,
 560                       (size_t) (((ElfW(Addr)) *ref) - undef_map->l_map_start),
 561                       (int) sizeof (ElfW(Addr)) * 2,
 562                       (size_t) (value->s ? value->m->l_map_start : 0),
 563                       (int) sizeof (ElfW(Addr)) * 2,
 564                       (size_t) (value->s ? value->s->st_value : 0));
 565
 566           if (conflict)
 567             _dl_printf ("x 0x%0*Zx 0x%0*Zx ",
 568                         (int) sizeof (ElfW(Addr)) * 2,
 569                         (size_t) (val.s ? val.m->l_map_start : 0),
 570                         (int) sizeof (ElfW(Addr)) * 2,
 571                         (size_t) (val.s ? val.s->st_value : 0));
 572
 573           _dl_printf ("/%x %s\n", type_class, undef_name);
 574         }
 575     }
 576 #endif
 577 }