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,