1 /* $NetBSD: symbol.c,v 1.73 2020/02/29 18:45:20 kamil Exp $ */ 2 3 /* 4 * Copyright 1996 John D. Polstra. 5 * Copyright 1996 Matt Thomas <matt@3am-software.com> 6 * Copyright 2002 Charles M. Hannum <root@ihack.net> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. All advertising materials mentioning features or use of this software 18 * must display the following acknowledgement: 19 * This product includes software developed by John Polstra. 20 * 4. The name of the author may not be used to endorse or promote products 21 * derived from this software without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 24 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 25 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 26 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 28 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 32 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 33 */ 34 35 /* 36 * Dynamic linker for ELF. 37 * 38 * John Polstra <jdp@polstra.com>. 39 */ 40 41 #include <sys/cdefs.h> 42 #ifndef lint 43 __RCSID("$NetBSD: symbol.c,v 1.73 2020/02/29 18:45:20 kamil Exp $"); 44 #endif /* not lint */ 45 46 #include <err.h> 47 #include <errno.h> 48 #include <fcntl.h> 49 #include <stdarg.h> 50 #include <stdio.h> 51 #include <stdlib.h> 52 #include <string.h> 53 #include <unistd.h> 54 #include <sys/types.h> 55 #include <sys/mman.h> 56 #include <sys/bitops.h> 57 #include <dirent.h> 58 59 #include "debug.h" 60 #include "rtld.h" 61 62 /* 63 * If the given object is already in the donelist, return true. Otherwise 64 * add the object to the list and return false. 65 */ 66 static bool 67 _rtld_donelist_check(DoneList *dlp, const Obj_Entry *obj) 68 { 69 unsigned int i; 70 71 for (i = 0; i < dlp->num_used; i++) 72 if (dlp->objs[i] == obj) 73 return true; 74 /* 75 * Our donelist allocation may not always be sufficient as we're not 76 * thread safe. We'll handle it properly anyway. 77 */ 78 if (dlp->num_used < dlp->num_alloc) 79 dlp->objs[dlp->num_used++] = obj; 80 return false; 81 } 82 83 /* 84 * Hash function for symbol table lookup. Don't even think about changing 85 * this. It is specified by the System V ABI. 86 */ 87 unsigned long 88 _rtld_sysv_hash(const char *name) 89 { 90 const unsigned char *p = (const unsigned char *) name; 91 unsigned long h = 0; 92 unsigned long g; 93 unsigned long c; 94 95 for (; __predict_true((c = *p) != '\0'); p++) { 96 h <<= 4; 97 h += c; 98 if ((g = h & 0xf0000000) != 0) { 99 h ^= g; 100 h ^= g >> 24; 101 } 102 } 103 return (h); 104 } 105 106 /* 107 * Hash function for symbol table lookup. Don't even think about changing 108 * this. It is specified by the GNU toolchain ABI. 109 */ 110 unsigned long 111 _rtld_gnu_hash(const char *name) 112 { 113 const unsigned char *p = (const unsigned char *) name; 114 uint_fast32_t h = 5381; 115 unsigned char c; 116 117 for (c = *p; c != '\0'; c = *++p) 118 h = h * 33 + c; 119 return (unsigned long)h; 120 } 121 122 const Elf_Sym * 123 _rtld_symlook_list(const char *name, Elf_Hash *hash, const Objlist *objlist, 124 const Obj_Entry **defobj_out, u_int flags, const Ver_Entry *ventry, 125 DoneList *dlp) 126 { 127 const Elf_Sym *symp; 128 const Elf_Sym *def; 129 const Obj_Entry *defobj; 130 const Objlist_Entry *elm; 131 132 def = NULL; 133 defobj = NULL; 134 SIMPLEQ_FOREACH(elm, objlist, link) { 135 if (_rtld_donelist_check(dlp, elm->obj)) 136 continue; 137 rdbg(("search object %p (%s) for %s", elm->obj, elm->obj->path, 138 name)); 139 symp = _rtld_symlook_obj(name, hash, elm->obj, flags, ventry); 140 if (symp != NULL) { 141 if ((def == NULL) || 142 (ELF_ST_BIND(symp->st_info) != STB_WEAK)) { 143 def = symp; 144 defobj = elm->obj; 145 if (ELF_ST_BIND(def->st_info) != STB_WEAK) 146 break; 147 } 148 } 149 } 150 if (def != NULL) 151 *defobj_out = defobj; 152 return def; 153 } 154 155 /* 156 * Search the symbol table of a shared object and all objects needed by it for 157 * a symbol of the given name. Search order is breadth-first. Returns a pointer 158 * to the symbol, or NULL if no definition was found. 159 */ 160 const Elf_Sym * 161 _rtld_symlook_needed(const char *name, Elf_Hash *hash, 162 const Needed_Entry *needed, const Obj_Entry **defobj_out, u_int flags, 163 const Ver_Entry *ventry, DoneList *breadth, DoneList *depth) 164 { 165 const Elf_Sym *def, *def_w; 166 const Needed_Entry *n; 167 const Obj_Entry *obj, *defobj, *defobj1; 168 169 def = def_w = NULL; 170 defobj = NULL; 171 for (n = needed; n != NULL; n = n->next) { 172 if ((obj = n->obj) == NULL) 173 continue; 174 if (_rtld_donelist_check(breadth, obj)) 175 continue; 176 def = _rtld_symlook_obj(name, hash, obj, flags, ventry); 177 if (def == NULL) 178 continue; 179 defobj = obj; 180 if (ELF_ST_BIND(def->st_info) != STB_WEAK) { 181 *defobj_out = defobj; 182 183 return (def); 184 } 185 } 186 /* 187 * Either the symbol definition has not been found in directly needed 188 * objects, or the found symbol is weak. 189 */ 190 for (n = needed; n != NULL; n = n->next) { 191 if ((obj = n->obj) == NULL) 192 continue; 193 if (_rtld_donelist_check(depth, obj)) 194 continue; 195 def_w = _rtld_symlook_needed(name, hash, obj->needed, &defobj1, 196 flags, ventry, breadth, depth); 197 if (def_w == NULL) 198 continue; 199 if (def == NULL || ELF_ST_BIND(def_w->st_info) != STB_WEAK) { 200 def = def_w; 201 defobj = defobj1; 202 if (ELF_ST_BIND(def_w->st_info) != STB_WEAK) 203 break; 204 } 205 } 206 if (def != NULL) 207 *defobj_out = defobj; 208 209 return def; 210 } 211 212 static bool 213 _rtld_symlook_obj_matched_symbol(const char *name, 214 const Obj_Entry *obj, u_int flags, const Ver_Entry *ventry, 215 unsigned long symnum, const Elf_Sym **vsymp, int *vcount) 216 { 217 const Elf_Sym *symp; 218 const char *strp; 219 Elf_Half verndx; 220 221 symp = obj->symtab + symnum; 222 strp = obj->strtab + symp->st_name; 223 rdbg(("check \"%s\" vs \"%s\" in %s", name, strp, obj->path)); 224 if (name[1] != strp[1] || strcmp(name, strp)) 225 return false; 226 #if defined(__mips__) || defined(__vax__) 227 if (symp->st_shndx == SHN_UNDEF) 228 return false; 229 #else 230 /* 231 * XXX DANGER WILL ROBINSON! 232 * If we have a function pointer in the executable's 233 * data section, it points to the executable's PLT 234 * slot, and there is NO relocation emitted. To make 235 * the function pointer comparable to function pointers 236 * in shared libraries, we must resolve data references 237 * in the libraries to point to PLT slots in the 238 * executable, if they exist. 239 */ 240 if (symp->st_shndx == SHN_UNDEF && 241 ((flags & SYMLOOK_IN_PLT) || 242 symp->st_value == 0 || 243 ELF_ST_TYPE(symp->st_info) != STT_FUNC)) 244 return false; 245 #endif 246 247 if (ventry == NULL) { 248 if (obj->versyms != NULL) { 249 verndx = VER_NDX(obj->versyms[symnum].vs_vers); 250 if (verndx > obj->vertabnum) { 251 _rtld_error("%s: symbol %s references " 252 "wrong version %d", obj->path, 253 &obj->strtab[symnum], verndx); 254 return false; 255 } 256 257 /* 258 * If we are not called from dlsym (i.e. this 259 * is a normal relocation from unversioned 260 * binary), accept the symbol immediately 261 * if it happens to have first version after 262 * this shared object became versioned. 263 * Otherwise, if symbol is versioned and not 264 * hidden, remember it. If it is the only 265 * symbol with this name exported by the shared 266 * object, it will be returned as a match at the 267 * end of the function. If symbol is global 268 * (verndx < 2) accept it unconditionally. 269 */ 270 if (!(flags & SYMLOOK_DLSYM) && 271 verndx == VER_NDX_GIVEN) { 272 *vsymp = symp; 273 return true; 274 } else if (verndx >= VER_NDX_GIVEN) { 275 if (!(obj->versyms[symnum].vs_vers & VER_NDX_HIDDEN)) { 276 if (*vsymp == NULL) 277 *vsymp = symp; 278 (*vcount)++; 279 } 280 return false; 281 } 282 } 283 *vsymp = symp; 284 return true; 285 } else { 286 if (obj->versyms == NULL) { 287 if (_rtld_object_match_name(obj, ventry->name)){ 288 _rtld_error("%s: object %s should " 289 "provide version %s for symbol %s", 290 _rtld_objself.path, obj->path, 291 ventry->name, &obj->strtab[symnum]); 292 return false; 293 } 294 } else { 295 verndx = VER_NDX(obj->versyms[symnum].vs_vers); 296 if (verndx > obj->vertabnum) { 297 _rtld_error("%s: symbol %s references " 298 "wrong version %d", obj->path, 299 &obj->strtab[symnum], verndx); 300 return false; 301 } 302 if (obj->vertab[verndx].hash != ventry->hash || 303 strcmp(obj->vertab[verndx].name, ventry->name)) { 304 /* 305 * Version does not match. Look if this 306 * is a global symbol and if it is not 307 * hidden. If global symbol (verndx < 2) 308 * is available, use it. Do not return 309 * symbol if we are called by dlvsym, 310 * because dlvsym looks for a specific 311 * version and default one is not what 312 * dlvsym wants. 313 */ 314 if ((flags & SYMLOOK_DLSYM) || 315 (obj->versyms[symnum].vs_vers & VER_NDX_HIDDEN) || 316 (verndx >= VER_NDX_GIVEN)) 317 return false; 318 } 319 } 320 *vsymp = symp; 321 return true; 322 } 323 } 324 325 /* 326 * Search the symbol table of a single shared object for a symbol of 327 * the given name. Returns a pointer to the symbol, or NULL if no 328 * definition was found. 329 * 330 * SysV Hash version. 331 */ 332 static const Elf_Sym * 333 _rtld_symlook_obj_sysv(const char *name, unsigned long hash, 334 const Obj_Entry *obj, u_int flags, const Ver_Entry *ventry) 335 { 336 unsigned long symnum; 337 const Elf_Sym *vsymp = NULL; 338 int vcount = 0; 339 340 for (symnum = obj->buckets[fast_remainder32(hash, obj->nbuckets, 341 obj->nbuckets_m, obj->nbuckets_s1, obj->nbuckets_s2)]; 342 symnum != ELF_SYM_UNDEFINED; 343 symnum = obj->chains[symnum]) { 344 assert(symnum < obj->nchains); 345 346 if (_rtld_symlook_obj_matched_symbol(name, obj, flags, 347 ventry, symnum, &vsymp, &vcount)) { 348 return vsymp; 349 } 350 } 351 if (vcount == 1) 352 return vsymp; 353 return NULL; 354 } 355 356 /* 357 * Search the symbol table of a single shared object for a symbol of 358 * the given name. Returns a pointer to the symbol, or NULL if no 359 * definition was found. 360 * 361 * GNU Hash version. 362 */ 363 static const Elf_Sym * 364 _rtld_symlook_obj_gnu(const char *name, unsigned long hash, 365 const Obj_Entry *obj, u_int flags, const Ver_Entry *ventry) 366 { 367 unsigned long symnum; 368 const Elf_Sym *vsymp = NULL; 369 const Elf32_Word *hashval; 370 Elf_Addr bloom_word; 371 Elf32_Word bucket; 372 int vcount = 0; 373 unsigned int h1, h2; 374 375 /* Pick right bitmask word from Bloom filter array */ 376 bloom_word = obj->bloom_gnu[(hash / ELFSIZE) & obj->mask_bm_gnu]; 377 378 /* Calculate modulus word size of gnu hash and its derivative */ 379 h1 = hash & (ELFSIZE - 1); 380 h2 = ((hash >> obj->shift2_gnu) & (ELFSIZE - 1)); 381 382 /* Filter out the "definitely not in set" queries */ 383 if (((bloom_word >> h1) & (bloom_word >> h2) & 1) == 0) 384 return NULL; 385 386 /* Locate hash chain and corresponding value element*/ 387 bucket = obj->buckets_gnu[fast_remainder32(hash, obj->nbuckets_gnu, 388 obj->nbuckets_m_gnu, obj->nbuckets_s1_gnu, obj->nbuckets_s2_gnu)]; 389 if (bucket == 0) 390 return NULL; 391 392 hashval = &obj->chains_gnu[bucket]; 393 do { 394 if (((*hashval ^ hash) >> 1) == 0) { 395 symnum = hashval - obj->chains_gnu; 396 397 if (_rtld_symlook_obj_matched_symbol(name, obj, flags, 398 ventry, symnum, &vsymp, &vcount)) { 399 return vsymp; 400 } 401 } 402 } while ((*hashval++ & 1) == 0); 403 if (vcount == 1) 404 return vsymp; 405 return NULL; 406 } 407 408 /* 409 * Search the symbol table of a single shared object for a symbol of 410 * the given name. Returns a pointer to the symbol, or NULL if no 411 * definition was found. 412 * 413 * The symbol's hash value is passed in for efficiency reasons; that 414 * eliminates many recomputations of the hash value. 415 * 416 * Redirect to either GNU Hash (whenever available) or ELF Hash. 417 */ 418 const Elf_Sym * 419 _rtld_symlook_obj(const char *name, Elf_Hash *hash, 420 const Obj_Entry *obj, u_int flags, const Ver_Entry *ventry) 421 { 422 423 assert(obj->sysv_hash || obj->gnu_hash); 424 425 /* Always prefer the GNU Hash as it is faster. */ 426 if (obj->gnu_hash) 427 return _rtld_symlook_obj_gnu(name, hash->gnu, obj, flags, ventry); 428 else 429 return _rtld_symlook_obj_sysv(name, hash->sysv, obj, flags, ventry); 430 } 431 432 /* 433 * Given a symbol number in a referencing object, find the corresponding 434 * definition of the symbol. Returns a pointer to the symbol, or NULL if 435 * no definition was found. Returns a pointer to the Obj_Entry of the 436 * defining object via the reference parameter DEFOBJ_OUT. 437 */ 438 const Elf_Sym * 439 _rtld_find_symdef(unsigned long symnum, const Obj_Entry *refobj, 440 const Obj_Entry **defobj_out, u_int flags) 441 { 442 const Elf_Sym *ref; 443 const Elf_Sym *def; 444 const Obj_Entry *defobj; 445 const char *name; 446 Elf_Hash hash; 447 448 ref = refobj->symtab + symnum; 449 name = refobj->strtab + ref->st_name; 450 451 /* 452 * We don't have to do a full scale lookup if the symbol is local. 453 * We know it will bind to the instance in this load module; to 454 * which we already have a pointer (ie ref). 455 */ 456 if (ELF_ST_BIND(ref->st_info) != STB_LOCAL) { 457 if (ELF_ST_TYPE(ref->st_info) == STT_SECTION) { 458 _rtld_error("%s: Bogus symbol table entry %lu", 459 refobj->path, symnum); 460 } 461 462 hash.sysv = _rtld_sysv_hash(name); 463 hash.gnu = _rtld_gnu_hash(name); 464 defobj = NULL; 465 def = _rtld_symlook_default(name, &hash, refobj, &defobj, flags, 466 _rtld_fetch_ventry(refobj, symnum)); 467 } else { 468 rdbg(("STB_LOCAL symbol %s in %s", name, refobj->path)); 469 def = ref; 470 defobj = refobj; 471 } 472 473 /* 474 * If we found no definition and the reference is weak, treat the 475 * symbol as having the value zero. 476 */ 477 if (def == NULL && ELF_ST_BIND(ref->st_info) == STB_WEAK) { 478 rdbg((" returning _rtld_sym_zero@_rtld_objself")); 479 def = &_rtld_sym_zero; 480 defobj = &_rtld_objself; 481 } 482 483 if (def != NULL) { 484 *defobj_out = defobj; 485 } else { 486 rdbg(("lookup failed")); 487 _rtld_error("%s: Undefined %ssymbol \"%s\" (symnum = %ld)", 488 refobj->path, (flags & SYMLOOK_IN_PLT) ? "PLT " : "", 489 name, symnum); 490 } 491 return def; 492 } 493 494 const Elf_Sym * 495 _rtld_find_plt_symdef(unsigned long symnum, const Obj_Entry *obj, 496 const Obj_Entry **defobj, bool imm) 497 { 498 const Elf_Sym *def = _rtld_find_symdef(symnum, obj, defobj, 499 SYMLOOK_IN_PLT); 500 if (__predict_false(def == NULL)) 501 return NULL; 502 503 if (__predict_false(def == &_rtld_sym_zero)) { 504 /* tp is set during lazy binding. */ 505 if (imm) { 506 const Elf_Sym *ref = obj->symtab + symnum; 507 const char *name = obj->strtab + ref->st_name; 508 509 _rtld_error( 510 "%s: Trying to call undefined weak symbol `%s'", 511 obj->path, name); 512 return NULL; 513 } 514 } 515 return def; 516 } 517 518 /* 519 * Given a symbol name in a referencing object, find the corresponding 520 * definition of the symbol. Returns a pointer to the symbol, or NULL if 521 * no definition was found. Returns a pointer to the Obj_Entry of the 522 * defining object via the reference parameter DEFOBJ_OUT. 523 */ 524 const Elf_Sym * 525 _rtld_symlook_default(const char *name, Elf_Hash *hash, 526 const Obj_Entry *refobj, const Obj_Entry **defobj_out, u_int flags, 527 const Ver_Entry *ventry) 528 { 529 const Elf_Sym *def; 530 const Elf_Sym *symp; 531 const Obj_Entry *obj; 532 const Obj_Entry *defobj; 533 const Objlist_Entry *elm; 534 def = NULL; 535 defobj = NULL; 536 DoneList donelist; 537 538 _rtld_donelist_init(&donelist); 539 540 /* Look first in the referencing object if linked symbolically. */ 541 if (refobj->symbolic && !_rtld_donelist_check(&donelist, refobj)) { 542 rdbg(("search referencing object for %s", name)); 543 symp = _rtld_symlook_obj(name, hash, refobj, flags, ventry); 544 if (symp != NULL) { 545 def = symp; 546 defobj = refobj; 547 } 548 } 549 550 /* Search all objects loaded at program start up. */ 551 if (def == NULL || ELF_ST_BIND(def->st_info) == STB_WEAK) { 552 rdbg(("search _rtld_list_main for %s", name)); 553 symp = _rtld_symlook_list(name, hash, &_rtld_list_main, &obj, 554 flags, ventry, &donelist); 555 if (symp != NULL && 556 (def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) { 557 def = symp; 558 defobj = obj; 559 } 560 } 561 562 /* Search all RTLD_GLOBAL objects. */ 563 if (def == NULL || ELF_ST_BIND(def->st_info) == STB_WEAK) { 564 rdbg(("search _rtld_list_global for %s", name)); 565 symp = _rtld_symlook_list(name, hash, &_rtld_list_global, 566 &obj, flags, ventry, &donelist); 567 if (symp != NULL && 568 (def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) { 569 def = symp; 570 defobj = obj; 571 } 572 } 573 574 /* Search all dlopened DAGs containing the referencing object. */ 575 SIMPLEQ_FOREACH(elm, &refobj->dldags, link) { 576 if (def != NULL && ELF_ST_BIND(def->st_info) != STB_WEAK) 577 break; 578 rdbg(("search DAG with root %p (%s) for %s", elm->obj, 579 elm->obj->path, name)); 580 symp = _rtld_symlook_list(name, hash, &elm->obj->dagmembers, 581 &obj, flags, ventry, &donelist); 582 if (symp != NULL && 583 (def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) { 584 def = symp; 585 defobj = obj; 586 } 587 } 588 589 /* 590 * Finally, look in the referencing object if not linked symbolically. 591 * This is necessary for DF_1_NODELETE objects where the containing DAG 592 * has been unlinked, so local references are resolved properly. 593 */ 594 if ((def == NULL || ELF_ST_BIND(def->st_info) == STB_WEAK) && 595 !refobj->symbolic && !_rtld_donelist_check(&donelist, refobj)) { 596 rdbg(("search referencing object for %s", name)); 597 symp = _rtld_symlook_obj(name, hash, refobj, flags, ventry); 598 if (symp != NULL) { 599 def = symp; 600 defobj = refobj; 601 } 602 } 603 604 /* 605 * Search the dynamic linker itself, and possibly resolve the 606 * symbol from there. This is how the application links to 607 * dynamic linker services such as dlopen. 608 */ 609 if (def == NULL || ELF_ST_BIND(def->st_info) == STB_WEAK) { 610 rdbg(("Search the dynamic linker itself.")); 611 symp = _rtld_symlook_obj(name, hash, &_rtld_objself, flags, 612 ventry); 613 if (symp != NULL) { 614 def = symp; 615 defobj = &_rtld_objself; 616 } 617 } 618 619 if (def != NULL) 620 *defobj_out = defobj; 621 return def; 622 } 623