dl-hash.c 12 KB

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