ldso/ldso/dl-hash.c

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