ldso/ldso/dl-hash.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * Program to load an ELF binary on a linux system, and run it
   4  * after resolving ELF shared library symbols
   5  *
   6  * Copyright (C) 2004 by Joakim Tjernlund <joakim.tjernlund@lumentis.se>
   7  * Copyright (C) 2000-2006 by Erik Andersen <andersen@codepoet.org>
   8  * Copyright (c) 1994-2000 Eric Youngdale, Peter MacDonald,
   9  *                              David Engel, Hongjiu Lu and Mitch D'Souza
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. The name of the above contributors may not be
  17  *    used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33
  34 /* Various symbol table handling functions, including symbol lookup */
  35 /*
  36  * This is the list of modules that are loaded when the image is first
  37  * started.  As we add more via dlopen, they get added into other
  38  * chains.
  39  */
  40 struct dyn_elf *_dl_symbol_tables = NULL;
  41
  42 /*
  43  * This is the list of modules that are loaded via dlopen.  We may need
  44  * to search these for RTLD_GLOBAL files.
  45  */
  46 struct dyn_elf *_dl_handles = NULL;
  47
  48 #ifdef __LDSO_GNU_HASH_SUPPORT__
  49 /* This is the new hash function that is used by the ELF linker to generate the
  50  * GNU hash table that each executable and library will have if --hash-style=[gnu,both]
  51  * is passed to the linker. We need it to decode the GNU hash table.  */
  52 static __inline__ Elf_Symndx _dl_gnu_hash (const unsigned char *name)
  53 {
  54   unsigned long h = 5381;
  55   unsigned char c;
  56   for (c = *name; c != '\0'; c = *++name)
  57     h = h * 33 + c;
  58   return h & 0xffffffff;
  59 }
  60 #endif
  61
  62 /* This is the hash function that is used by the ELF linker to generate the
  63  * hash table that each executable and library is required to have.  We need
  64  * it to decode the hash table.  */
  65 static __inline__ Elf_Symndx _dl_elf_hash(const unsigned char *name)
  66 {
  67         unsigned long hash=0;
  68         unsigned long tmp;
  69
  70         while (*name) {
  71                 hash = (hash << 4) + *name++;
  72                 tmp = hash & 0xf0000000;
  73                 /* The algorithm specified in the ELF ABI is as follows:
  74                    if (tmp != 0)
  75                        hash ^= tmp >> 24;
  76                    hash &= ~tmp;
  77                    But the following is equivalent and a lot
  78                    faster, especially on modern processors. */
  79                 hash ^= tmp;
  80                 hash ^= tmp >> 24;
  81         }
  82         return hash;
  83 }
  84
  85 /*
  86  * We call this function when we have just read an ELF library or executable.
  87  * We add the relevant info to the symbol chain, so that we can resolve all
  88  * externals properly.
  89  */
  90 struct elf_resolve *_dl_add_elf_hash_table(const char *libname,
  91         DL_LOADADDR_TYPE loadaddr, unsigned long *dynamic_info, unsigned long dynamic_addr,
  92         attribute_unused unsigned long dynamic_size)
  93 {
  94         Elf_Symndx *hash_addr;
  95         struct elf_resolve *tpnt;
  96         int i;
  97
  98         tpnt = _dl_malloc(sizeof(struct elf_resolve));
  99         _dl_memset(tpnt, 0, sizeof(struct elf_resolve));
 100
 101         if (!_dl_loaded_modules)
 102                 _dl_loaded_modules = tpnt;
 103         else {
 104                 struct elf_resolve *t = _dl_loaded_modules;
 105                 while (t->next)
 106                         t = t->next;
 107                 t->next = tpnt;
 108                 t->next->prev = t;
 109                 tpnt = t->next;
 110         }
 111
 112         tpnt->next = NULL;
 113         tpnt->init_flag = 0;
 114         tpnt->libname = _dl_strdup(libname);
 115         tpnt->dynamic_addr = (ElfW(Dyn) *)dynamic_addr;
 116         tpnt->libtype = loaded_file;
 117
 118 #ifdef __LDSO_GNU_HASH_SUPPORT__
 119         if (dynamic_info[DT_GNU_HASH_IDX] != 0) {
 120                 Elf32_Word *hash32 = (Elf_Symndx*)dynamic_info[DT_GNU_HASH_IDX];
 121
 122                 tpnt->nbucket = *hash32++;
 123                 Elf32_Word symbias = *hash32++;
 124                 Elf32_Word bitmask_nwords = *hash32++;
 125                 /* Must be a power of two.  */
 126                 _dl_assert ((bitmask_nwords & (bitmask_nwords - 1)) == 0);
 127                 tpnt->l_gnu_bitmask_idxbits = bitmask_nwords - 1;
 128                 tpnt->l_gnu_shift = *hash32++;
 129
 130                 tpnt->l_gnu_bitmask = (ElfW(Addr) *) hash32;
 131                 hash32 += __ELF_NATIVE_CLASS / 32 * bitmask_nwords;
 132
 133                 tpnt->l_gnu_buckets = hash32;
 134                 hash32 += tpnt->nbucket;
 135                 tpnt->l_gnu_chain_zero = hash32 - symbias;
 136         } else
 137         /* Fall using old SysV hash table if GNU hash is not present */
 138 #endif
 139
 140         if (dynamic_info[DT_HASH] != 0) {
 141                 hash_addr = (Elf_Symndx*)dynamic_info[DT_HASH];
 142                 tpnt->nbucket = *hash_addr++;
 143                 tpnt->nchain = *hash_addr++;
 144                 tpnt->elf_buckets = hash_addr;
 145                 hash_addr += tpnt->nbucket;
 146                 tpnt->chains = hash_addr;
 147         }
 148         tpnt->loadaddr = loadaddr;
 149         tpnt->mapaddr = DL_RELOC_ADDR(loadaddr, 0);
 150         for (i = 0; i < DYNAMIC_SIZE; i++)
 151                 tpnt->dynamic_info[i] = dynamic_info[i];
 152         return tpnt;
 153 }
 154
 155
 156 /* Routine to check whether the symbol matches.  */
 157 static __attribute_noinline__ const ElfW(Sym) *
 158 check_match (const ElfW(Sym) *sym, char *strtab, const char* undef_name, int type_class)
 159 {
 160
 161 #if defined(USE_TLS) && USE_TLS
 162         if ((sym->st_value == 0 && (ELF_ST_TYPE(sym->st_info) != STT_TLS))
 163                       || (type_class & (sym->st_shndx == SHN_UNDEF)))
 164                 /* No value or undefined symbol itself */
 165                 return NULL;
 166
 167         if (ELF_ST_TYPE(sym->st_info) > STT_FUNC
 168                 && ELF_ST_TYPE(sym->st_info) != STT_COMMON
 169                 && ELF_ST_TYPE(sym->st_info) != STT_TLS)
 170                 /* Ignore all but STT_NOTYPE, STT_OBJECT, STT_FUNC and STT_COMMON
 171                  * entries (and STT_TLS if TLS is supported) since these
 172                  * are no code/data definitions.
 173                  */
 174                 return NULL;
 175 #else
 176         if (type_class & (sym->st_shndx == SHN_UNDEF))
 177                 /* undefined symbol itself */
 178                 return NULL;
 179
 180         if (sym->st_value == 0)
 181                 /* No value */
 182                 return NULL;
 183
 184         if (ELF_ST_TYPE(sym->st_info) > STT_FUNC
 185                 && ELF_ST_TYPE(sym->st_info) != STT_COMMON)
 186                 /* Ignore all but STT_NOTYPE, STT_OBJECT, STT_FUNC
 187                  * and STT_COMMON entries since these are no
 188                  * code/data definitions
 189                  */
 190                 return NULL;
 191 #endif
 192         if (_dl_strcmp(strtab + sym->st_name, undef_name) != 0)
 193                 return NULL;
 194
 195         /* This is the matching symbol */
 196         return sym;
 197 }
 198
 199
 200 #ifdef __LDSO_GNU_HASH_SUPPORT__
 201
 202 static __always_inline const ElfW(Sym) *
 203 _dl_lookup_gnu_hash(struct elf_resolve *tpnt, ElfW(Sym) *symtab, unsigned long hash,
 204                                         const char* undef_name, int type_class)
 205 {
 206         Elf_Symndx symidx;
 207         const ElfW(Sym) *sym;
 208         char *strtab;
 209
 210         const ElfW(Addr) *bitmask = tpnt->l_gnu_bitmask;
 211
 212         ElfW(Addr) bitmask_word = bitmask[(hash / __ELF_NATIVE_CLASS) & tpnt->l_gnu_bitmask_idxbits];
 213
 214         unsigned int hashbit1 = hash & (__ELF_NATIVE_CLASS - 1);
 215         unsigned int hashbit2 = ((hash >> tpnt->l_gnu_shift) & (__ELF_NATIVE_CLASS - 1));
 216         _dl_assert (bitmask != NULL);
 217
 218         if (unlikely((bitmask_word >> hashbit1) & (bitmask_word >> hashbit2) & 1)) {
 219                 unsigned long rem;
 220                 Elf32_Word bucket;
 221
 222                 do_rem (rem, hash, tpnt->nbucket);
 223                 bucket = tpnt->l_gnu_buckets[rem];
 224
 225                 if (bucket != 0) {
 226                         const Elf32_Word *hasharr = &tpnt->l_gnu_chain_zero[bucket];
 227                         do {
 228                                 if (((*hasharr ^ hash) >> 1) == 0) {
 229                                         symidx = hasharr - tpnt->l_gnu_chain_zero;
 230                                         strtab = (char *) (tpnt->dynamic_info[DT_STRTAB]);
 231                                         sym = check_match (&symtab[symidx], strtab, undef_name, type_class);
 232                                         if (sym != NULL)
 233                                                 return sym;
 234                                 }
 235                         } while ((*hasharr++ & 1u) == 0);
 236                 }
 237         }
 238         /* No symbol found.  */
 239         return NULL;
 240 }
 241 #endif
 242
 243 static __always_inline const ElfW(Sym) *
 244 _dl_lookup_sysv_hash(struct elf_resolve *tpnt, ElfW(Sym) *symtab, unsigned long hash,  const char* undef_name, int type_class)
 245 {
 246         unsigned long hn;
 247         char *strtab;
 248         const ElfW(Sym) *sym;
 249         Elf_Symndx symidx;
 250
 251         /* Avoid calling .urem here. */
 252         do_rem(hn, hash, tpnt->nbucket);
 253         strtab = (char *) (tpnt->dynamic_info[DT_STRTAB]);
 254
 255         _dl_assert(tpnt->elf_buckets != NULL);
 256
 257         for (symidx = tpnt->elf_buckets[hn]; symidx != STN_UNDEF; symidx = tpnt->chains[symidx]) {
 258                 sym = check_match (&symtab[symidx], strtab, undef_name, type_class);
 259                 if (sym != NULL)
 260                         /* At this point the symbol is that we are looking for */
 261                         return sym;
 262         }
 263         /* No symbol found into the current module*/
 264         return NULL;
 265 }
 266
 267 /*
 268  * This function resolves externals, and this is either called when we process
 269  * relocations or when we call an entry in the PLT table for the first time.
 270  */
 271 char *_dl_find_hash(const char *name, struct dyn_elf *rpnt, struct elf_resolve *mytpnt,
 272         int type_class, struct symbol_ref *sym_ref)
 273 {
 274         struct elf_resolve *tpnt = NULL;
 275         ElfW(Sym) *symtab;
 276
 277         unsigned long elf_hash_number = 0xffffffff;
 278         const ElfW(Sym) *sym = NULL;
 279
 280         char *weak_result = NULL;
 281
 282 #ifdef __LDSO_GNU_HASH_SUPPORT__
 283         unsigned long gnu_hash_number = _dl_gnu_hash((const unsigned char *)name);
 284 #endif
 285
 286         if ((sym_ref) && (sym_ref->sym) && (ELF32_ST_VISIBILITY(sym_ref->sym->st_other) == STV_PROTECTED)) {
 287                         sym = sym_ref->sym;
 288                 if (mytpnt)
 289                         tpnt = mytpnt;
 290         } else
 291         for (; rpnt; rpnt = rpnt->next) {
 292                 tpnt = rpnt->dyn;
 293
 294                 if (!(tpnt->rtld_flags & RTLD_GLOBAL) && mytpnt) {
 295                         if (mytpnt == tpnt)
 296                                 ;
 297                         else {
 298                                 struct init_fini_list *tmp;
 299
 300                                 for (tmp = mytpnt->rtld_local; tmp; tmp = tmp->next) {
 301                                         if (tmp->tpnt == tpnt)
 302                                                 break;
 303                                 }
 304                                 if (!tmp)
 305                                         continue;
 306                         }
 307                 }
 308                 /* Don't search the executable when resolving a copy reloc. */
 309                 if ((type_class &  ELF_RTYPE_CLASS_COPY) && tpnt->libtype == elf_executable)
 310                         continue;
 311
 312                 /* If the hash table is empty there is nothing to do here.  */
 313                 if (tpnt->nbucket == 0)
 314                         continue;
 315
 316                 symtab = (ElfW(Sym) *) (intptr_t) (tpnt->dynamic_info[DT_SYMTAB]);
 317
 318 #ifdef __LDSO_GNU_HASH_SUPPORT__
 319                 /* Prefer GNU hash style, if any */
 320                 if (tpnt->l_gnu_bitmask) {
 321                         sym = _dl_lookup_gnu_hash(tpnt, symtab, gnu_hash_number, name, type_class);
 322                         if (sym != NULL)
 323                                 /* If sym has been found, do not search further */
 324                                 break;
 325                 } else {
 326 #endif
 327                 /* Use the old SysV-style hash table */
 328
 329                 /* Calculate the old sysv hash number only once */
 330                 if (elf_hash_number == 0xffffffff)
 331                         elf_hash_number = _dl_elf_hash((const unsigned char *)name);
 332
 333                 sym = _dl_lookup_sysv_hash(tpnt, symtab, elf_hash_number, name, type_class);
 334                 if (sym != NULL)
 335                         break;
 336 #ifdef __LDSO_GNU_HASH_SUPPORT__
 337                 }
 338 #endif
 339         } /* end of for (; rpnt; rpnt = rpnt->next) { */
 340
 341         if (sym) {
 342                 /* At this point we have found the requested symbol, do binding */
 343 #if defined(USE_TLS) && USE_TLS
 344                 if (ELF_ST_TYPE(sym->st_info) == STT_TLS) {
 345                         _dl_assert(sym_ref != NULL);
 346                         sym_ref->tpnt = tpnt;
 347                         return (char *)sym->st_value;
 348                 }
 349 #endif
 350
 351                 switch (ELF_ST_BIND(sym->st_info)) {
 352                         case STB_WEAK:
 353 #if 0
 354         /* Perhaps we should support old style weak symbol handling
 355         * per what glibc does when you export LD_DYNAMIC_WEAK */
 356                                 if (!weak_result)
 357                                         weak_result = (char *)DL_FIND_HASH_VALUE(tpnt, type_class, sym);
 358                                 break;
 359 #endif
 360                         case STB_GLOBAL:
 361 #ifdef __FDPIC__
 362                         if (sym_ref)
 363                                 sym_ref->tpnt = tpnt;
 364 #endif
 365                                 return (char *)DL_FIND_HASH_VALUE(tpnt, type_class, sym);
 366                         default:        /* Local symbols not handled here */
 367                                 break;
 368                 }
 369         }
 370 #ifdef __FDPIC__
 371         if (sym_ref)
 372                 sym_ref->tpnt = tpnt;
 373 #endif
 374         return weak_result;
 375 }