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 /*
  37  * This is the start of the linked list that describes all of the files present
  38  * in the system with pointers to all of the symbol, string, and hash tables,
  39  * as well as all of the other good stuff in the binary.
  40  */
  41 struct elf_resolve *_dl_loaded_modules = NULL;
  42
  43 /*
  44  * This is the list of modules that are loaded when the image is first
  45  * started.  As we add more via dlopen, they get added into other
  46  * chains.
  47  */
  48 struct dyn_elf *_dl_symbol_tables = NULL;
  49
  50 /*
  51  * This is the list of modules that are loaded via dlopen.  We may need
  52  * to search these for RTLD_GLOBAL files.
  53  */
  54 struct dyn_elf *_dl_handles = NULL;
  55
  56 #ifdef __LDSO_GNU_HASH_SUPPORT__
  57 /* This is the new hash function that is used by the ELF linker to generate the
  58  * GNU hash table that each executable and library will have if --hash-style=[gnu,both]
  59  * is passed to the linker. We need it to decode the GNU hash table.  */
  60 static __inline__ Elf_Symndx _dl_gnu_hash (const unsigned char *name)
  61 {
  62   unsigned long h = 5381;
  63   unsigned char c;
  64   for (c = *name; c != '\0'; c = *++name)
  65     h = h * 33 + c;
  66   return h & 0xffffffff;
  67 }
  68 #endif
  69
  70 /* This is the hash function that is used by the ELF linker to generate the
  71  * hash table that each executable and library is required to have.  We need
  72  * it to decode the hash table.  */
  73 static __inline__ Elf_Symndx _dl_elf_hash(const unsigned char *name)
  74 {
  75         unsigned long hash=0;
  76         unsigned long tmp;
  77
  78         while (*name) {
  79                 hash = (hash << 4) + *name++;
  80                 tmp = hash & 0xf0000000;
  81                 /* The algorithm specified in the ELF ABI is as follows:
  82                    if (tmp != 0)
  83                        hash ^= tmp >> 24;
  84                    hash &= ~tmp;
  85                    But the following is equivalent and a lot
  86                    faster, especially on modern processors. */
  87                 hash ^= tmp;
  88                 hash ^= tmp >> 24;
  89         }
  90         return hash;
  91 }
  92
  93 /*
  94  * We call this function when we have just read an ELF library or executable.
  95  * We add the relevant info to the symbol chain, so that we can resolve all
  96  * externals properly.
  97  */
  98 struct elf_resolve *_dl_add_elf_hash_table(const char *libname,
  99         DL_LOADADDR_TYPE loadaddr, unsigned long *dynamic_info, unsigned long dynamic_addr,
 100         attribute_unused unsigned long dynamic_size)
 101 {
 102         Elf_Symndx *hash_addr;
 103         struct elf_resolve *tpnt;
 104         int i;
 105
 106         if (!_dl_loaded_modules) {
 107                 tpnt = _dl_loaded_modules = (struct elf_resolve *) _dl_malloc(sizeof(struct elf_resolve));
 108                 _dl_memset(tpnt, 0, sizeof(struct elf_resolve));
 109         } else {
 110                 tpnt = _dl_loaded_modules;
 111                 while (tpnt->next)
 112                         tpnt = tpnt->next;
 113                 tpnt->next = (struct elf_resolve *) _dl_malloc(sizeof(struct elf_resolve));
 114                 _dl_memset(tpnt->next, 0, sizeof(struct elf_resolve));
 115                 tpnt->next->prev = tpnt;
 116                 tpnt = tpnt->next;
 117         }
 118
 119         tpnt->next = NULL;
 120         tpnt->init_flag = 0;
 121         tpnt->libname = _dl_strdup(libname);
 122         tpnt->dynamic_addr = (ElfW(Dyn) *)dynamic_addr;
 123         tpnt->libtype = loaded_file;
 124
 125 #ifdef __LDSO_GNU_HASH_SUPPORT__
 126         if (dynamic_info[DT_GNU_HASH_IDX] != 0) {
 127                 Elf32_Word *hash32 = (Elf_Symndx*)dynamic_info[DT_GNU_HASH_IDX];
 128
 129                 tpnt->nbucket = *hash32++;
 130                 Elf32_Word symbias = *hash32++;
 131                 Elf32_Word bitmask_nwords = *hash32++;
 132                 /* Must be a power of two.  */
 133                 _dl_assert ((bitmask_nwords & (bitmask_nwords - 1)) == 0);
 134                 tpnt->l_gnu_bitmask_idxbits = bitmask_nwords - 1;
 135                 tpnt->l_gnu_shift = *hash32++;
 136
 137                 tpnt->l_gnu_bitmask = (ElfW(Addr) *) hash32;
 138                 hash32 += __ELF_NATIVE_CLASS / 32 * bitmask_nwords;
 139
 140                 tpnt->l_gnu_buckets = hash32;
 141                 hash32 += tpnt->nbucket;
 142                 tpnt->l_gnu_chain_zero = hash32 - symbias;
 143         } else
 144         /* Fall using old SysV hash table if GNU hash is not present */
 145 #endif
 146
 147         if (dynamic_info[DT_HASH] != 0) {
 148                 hash_addr = (Elf_Symndx*)dynamic_info[DT_HASH];
 149                 tpnt->nbucket = *hash_addr++;
 150                 tpnt->nchain = *hash_addr++;
 151                 tpnt->elf_buckets = hash_addr;
 152                 hash_addr += tpnt->nbucket;
 153                 tpnt->chains = hash_addr;
 154         }
 155         tpnt->loadaddr = loadaddr;
 156         tpnt->mapaddr = DL_RELOC_ADDR(loadaddr, 0);
 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         if (type_class & (sym->st_shndx == SHN_UNDEF))
 168                 /* undefined symbol itself */
 169                 return NULL;
 170
 171         if (sym->st_value == 0)
 172                 /* No value */
 173                 return NULL;
 174
 175         if (ELF_ST_TYPE(sym->st_info) > STT_FUNC
 176                 && ELF_ST_TYPE(sym->st_info) != STT_COMMON)
 177                 /* Ignore all but STT_NOTYPE, STT_OBJECT, STT_FUNC
 178                  * and STT_COMMON entries since these are no
 179                  * code/data definitions
 180                  */
 181                 return NULL;
 182
 183         if (_dl_strcmp(strtab + sym->st_name, undef_name) != 0)
 184                 return NULL;
 185
 186         /* This is the matching symbol */
 187         return sym;
 188 }
 189
 190
 191 #ifdef __LDSO_GNU_HASH_SUPPORT__
 192
 193 static __always_inline const ElfW(Sym) *
 194 _dl_lookup_gnu_hash(struct elf_resolve *tpnt, ElfW(Sym) *symtab, unsigned long hash,
 195                                         const char* undef_name, int type_class)
 196 {
 197         Elf_Symndx symidx;
 198         const ElfW(Sym) *sym;
 199         char *strtab;
 200
 201         const ElfW(Addr) *bitmask = tpnt->l_gnu_bitmask;
 202
 203         ElfW(Addr) bitmask_word = bitmask[(hash / __ELF_NATIVE_CLASS) & tpnt->l_gnu_bitmask_idxbits];
 204
 205         unsigned int hashbit1 = hash & (__ELF_NATIVE_CLASS - 1);
 206         unsigned int hashbit2 = ((hash >> tpnt->l_gnu_shift) & (__ELF_NATIVE_CLASS - 1));
 207         _dl_assert (bitmask != NULL);
 208
 209         if (unlikely((bitmask_word >> hashbit1) & (bitmask_word >> hashbit2) & 1)) {
 210                 unsigned long rem;
 211                 Elf32_Word bucket;
 212
 213                 do_rem (rem, hash, tpnt->nbucket);
 214                 bucket = tpnt->l_gnu_buckets[rem];
 215
 216                 if (bucket != 0) {
 217                         const Elf32_Word *hasharr = &tpnt->l_gnu_chain_zero[bucket];
 218                         do {
 219                                 if (((*hasharr ^ hash) >> 1) == 0) {
 220                                         symidx = hasharr - tpnt->l_gnu_chain_zero;
 221                                         strtab = (char *) (tpnt->dynamic_info[DT_STRTAB]);
 222                                         sym = check_match (&symtab[symidx], strtab, undef_name, type_class);
 223                                         if (sym != NULL)
 224                                                 return sym;
 225                                 }
 226                         } while ((*hasharr++ & 1u) == 0);
 227                 }
 228         }
 229         /* No symbol found.  */
 230         return NULL;
 231 }
 232 #endif
 233
 234 static __always_inline const ElfW(Sym) *
 235 _dl_lookup_sysv_hash(struct elf_resolve *tpnt, ElfW(Sym) *symtab, unsigned long hash,  const char* undef_name, int type_class)
 236 {
 237         unsigned long hn;
 238         char *strtab;
 239         const ElfW(Sym) *sym;
 240         Elf_Symndx symidx;
 241
 242         /* Avoid calling .urem here. */
 243         do_rem(hn, hash, tpnt->nbucket);
 244         strtab = (char *) (tpnt->dynamic_info[DT_STRTAB]);
 245
 246         _dl_assert(tpnt->elf_buckets != NULL);
 247
 248         for (symidx = tpnt->elf_buckets[hn]; symidx != STN_UNDEF; symidx = tpnt->chains[symidx]) {
 249                 sym = check_match (&symtab[symidx], strtab, undef_name, type_class);
 250                 if (sym != NULL)
 251                         /* At this point the symbol is that we are looking for */
 252                         return sym;
 253         }
 254         /* No symbol found into the current module*/
 255         return NULL;
 256 }
 257
 258 /*
 259  * This function resolves externals, and this is either called when we process
 260  * relocations or when we call an entry in the PLT table for the first time.
 261  */
 262 char *_dl_lookup_hash(const char *name, struct dyn_elf *rpnt,
 263                       struct elf_resolve *mytpnt, int type_class
 264 #ifdef __FDPIC__
 265                       , struct elf_resolve **tpntp
 266 #endif
 267                       )
 268 {
 269         struct elf_resolve *tpnt = NULL;
 270         ElfW(Sym) *symtab;
 271
 272         unsigned long elf_hash_number = 0xffffffff;
 273         const ElfW(Sym) *sym = NULL;
 274
 275         const ElfW(Sym) *weak_sym = 0;
 276         struct elf_resolve *weak_tpnt = 0;
 277
 278 #ifdef __LDSO_GNU_HASH_SUPPORT__
 279         unsigned long gnu_hash_number = _dl_gnu_hash((const unsigned char *)name);
 280 #endif
 281
 282         for (; rpnt; rpnt = rpnt->next) {
 283                 tpnt = rpnt->dyn;
 284
 285                 if (!(tpnt->rtld_flags & RTLD_GLOBAL) && mytpnt) {
 286                         if (mytpnt == tpnt)
 287                                 ;
 288                         else {
 289                                 struct init_fini_list *tmp;
 290
 291                                 for (tmp = mytpnt->rtld_local; tmp; tmp = tmp->next) {
 292                                         if (tmp->tpnt == tpnt)
 293                                                 break;
 294                                 }
 295                                 if (!tmp)
 296                                         continue;
 297                         }
 298                 }
 299                 /* Don't search the executable when resolving a copy reloc. */
 300                 if ((type_class &  ELF_RTYPE_CLASS_COPY) && tpnt->libtype == elf_executable)
 301                         continue;
 302
 303                 /* If the hash table is empty there is nothing to do here.  */
 304                 if (tpnt->nbucket == 0)
 305                         continue;
 306
 307                 symtab = (ElfW(Sym) *) (intptr_t) (tpnt->dynamic_info[DT_SYMTAB]);
 308
 309 #ifdef __LDSO_GNU_HASH_SUPPORT__
 310                 /* Prefer GNU hash style, if any */
 311                 if (tpnt->l_gnu_bitmask) {
 312                         sym = _dl_lookup_gnu_hash(tpnt, symtab, gnu_hash_number, name, type_class);
 313                         if (sym != NULL)
 314                                 /* If sym has been found, do not search further */
 315                                 break;
 316                 } else {
 317 #endif
 318                 /* Use the old SysV-style hash table */
 319
 320                 /* Calculate the old sysv hash number only once */
 321                 if (elf_hash_number == 0xffffffff)
 322                         elf_hash_number = _dl_elf_hash((const unsigned char *)name);
 323
 324                 sym = _dl_lookup_sysv_hash(tpnt, symtab, elf_hash_number, name, type_class);
 325                 if (sym != NULL)
 326                         break;
 327 #ifdef __LDSO_GNU_HASH_SUPPORT__
 328                 }
 329 #endif
 330         } /* end of for (; rpnt; rpnt = rpnt->next) { */
 331
 332         if (sym) {
 333                 /* At this point we have found the requested symbol, do binding */
 334                 switch (ELF_ST_BIND(sym->st_info)) {
 335                         case STB_WEAK:
 336 #if 0
 337 /* Perhaps we should support old style weak symbol handling
 338  * per what glibc does when you export LD_DYNAMIC_WEAK */
 339                                 if (!weak_sym) {
 340                                         weak_tpnt = tpnt;
 341                                         weak_sym = sym;
 342                                 }
 343                                 break;
 344 #endif
 345                         case STB_GLOBAL:
 346 #ifdef __FDPIC__
 347                                 if (tpntp)
 348                                         *tpntp = tpnt;
 349 #endif
 350                                 return (char *) DL_FIND_HASH_VALUE (tpnt, type_class, sym);
 351                         default:        /* Local symbols not handled here */
 352                                 break;
 353                 }
 354         }
 355         if (weak_sym) {
 356 #ifdef __FDPIC__
 357                 if (tpntp)
 358                         *tpntp = weak_tpnt;
 359 #endif
 360                 return (char *) DL_FIND_HASH_VALUE (weak_tpnt, type_class, weak_sym);
 361         }
 362 #ifdef __FDPIC__
 363         if (tpntp)
 364                 *tpntp = NULL;
 365 #endif
 366         return NULL;
 367 }