1 /*
2 * Copyright 2008-2011, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Copyright 2003-2008, Axel Dörfler, axeld@pinc-software.de.
4 * Distributed under the terms of the MIT License.
5 *
6 * Copyright 2002, Manuel J. Petit. All rights reserved.
7 * Copyright 2001, Travis Geiselbrecht. All rights reserved.
8 * Distributed under the terms of the NewOS License.
9 */
10
11 #include "elf_symbol_lookup.h"
12
13 #include <dlfcn.h>
14 #include <stdio.h>
15 #include <string.h>
16
17 #include "add_ons.h"
18 #include "errors.h"
19 #include "images.h"
20 #include "runtime_loader_private.h"
21
22
23 /*! Checks whether \a name matches the name of \a image.
24
25 It is expected that \a name does not contain directory components. It is
26 compared with the base name of \a image's name.
27
28 \param image The image.
29 \param name The name to check against. Can be NULL, in which case \c false
30 is returned.
31 \return \c true, iff \a name is non-NULL and matches the name of \a image.
32 */
33 static bool
equals_image_name(const image_t * image,const char * name)34 equals_image_name(const image_t* image, const char* name)
35 {
36 if (name == NULL)
37 return false;
38
39 const char* lastSlash = strrchr(name, '/');
40 return strcmp(image->name, lastSlash != NULL ? lastSlash + 1 : name) == 0;
41 }
42
43
44 // #pragma mark -
45
46
47 uint32
elf_hash(const char * _name)48 elf_hash(const char* _name)
49 {
50 const uint8* name = (const uint8*)_name;
51
52 uint32 h = 0;
53 while (*name != '\0') {
54 h = (h << 4) + *name++;
55 h ^= (h >> 24) & 0xf0;
56 }
57 return (h & 0x0fffffff);
58 }
59
60
61 uint32
elf_gnuhash(const char * _name)62 elf_gnuhash(const char* _name)
63 {
64 const uint8* name = (const uint8*)_name;
65
66 uint32 h = 5381;
67 for (uint8 c = *name; c != '\0'; c = *++name)
68 h = (h * 33) + c;
69
70 return h;
71 }
72
73
74 struct match_result {
75 elf_sym* symbol;
76 elf_sym* versioned_symbol;
77 uint32 versioned_symbol_count;
78
match_resultmatch_result79 match_result() : symbol(NULL), versioned_symbol(NULL), versioned_symbol_count(0) {}
80 };
81
82
83 static bool
match_symbol(const image_t * image,const SymbolLookupInfo & lookupInfo,uint32 symIdx,match_result & result)84 match_symbol(const image_t* image, const SymbolLookupInfo& lookupInfo, uint32 symIdx,
85 match_result& result)
86 {
87 elf_sym* symbol = &image->syms[symIdx];
88 if (symbol->st_shndx == SHN_UNDEF)
89 return false;
90 if (symbol->Bind() != STB_GLOBAL && symbol->Bind() != STB_WEAK)
91 return false;
92
93 // check if the type matches
94 uint32 type = symbol->Type();
95 if ((lookupInfo.type == B_SYMBOL_TYPE_TEXT && type != STT_FUNC)
96 || (lookupInfo.type == B_SYMBOL_TYPE_DATA
97 && type != STT_OBJECT && type != STT_FUNC)) {
98 return false;
99 }
100
101 // check the symbol name
102 if (strcmp(SYMNAME(image, symbol), lookupInfo.name) != 0)
103 return false;
104
105 // check the version
106
107 // Handle the simple cases -- the image doesn't have version
108 // information -- first.
109 if (image->symbol_versions == NULL) {
110 if (lookupInfo.version == NULL) {
111 // No specific symbol version was requested either, so the
112 // symbol is just fine.
113 result.symbol = symbol;
114 return true;
115 }
116
117 // A specific version is requested. If it's the dependency
118 // referred to by the requested version, it's apparently an
119 // older version of the dependency and we're not happy.
120 if (equals_image_name(image, lookupInfo.version->file_name)) {
121 // TODO: That should actually be kind of fatal!
122 return false;
123 }
124
125 // This is some other image. We accept the symbol.
126 result.symbol = symbol;
127 return true;
128 }
129
130 // The image has version information. Let's see what we've got.
131 uint32 versionID = image->symbol_versions[symIdx];
132 uint32 versionIndex = VER_NDX(versionID);
133 elf_version_info& version = image->versions[versionIndex];
134
135 // skip local versions
136 if (versionIndex == VER_NDX_LOCAL)
137 return false;
138
139 if (lookupInfo.version != NULL) {
140 // a specific version is requested
141
142 // compare the versions
143 if (version.hash == lookupInfo.version->hash
144 && strcmp(version.name, lookupInfo.version->name) == 0) {
145 // versions match
146 result.symbol = symbol;
147 return true;
148 }
149
150 // The versions don't match. We're still fine with the
151 // base version, if it is public and we're not looking for
152 // the default version.
153 if ((versionID & VER_NDX_FLAG_HIDDEN) == 0
154 && versionIndex == VER_NDX_GLOBAL
155 && (lookupInfo.flags & LOOKUP_FLAG_DEFAULT_VERSION)
156 == 0) {
157 // TODO: Revise the default version case! That's how
158 // FreeBSD implements it, but glibc doesn't handle it
159 // specially.
160 result.symbol = symbol;
161 return true;
162 }
163 } else {
164 // No specific version requested, but the image has version
165 // information. This can happen in either of these cases:
166 //
167 // * The dependent object was linked against an older version
168 // of the now versioned dependency.
169 // * The symbol is looked up via find_image_symbol() or dlsym().
170 //
171 // In the first case we return the base version of the symbol
172 // (VER_NDX_GLOBAL or VER_NDX_INITIAL), or, if that doesn't
173 // exist, the unique, non-hidden versioned symbol.
174 //
175 // In the second case we want to return the public default
176 // version of the symbol. The handling is pretty similar to the
177 // first case, with the exception that we treat VER_NDX_INITIAL
178 // as regular version.
179
180 // VER_NDX_GLOBAL is always good, VER_NDX_INITIAL is fine, if
181 // we don't look for the default version.
182 if (versionIndex == VER_NDX_GLOBAL
183 || ((lookupInfo.flags & LOOKUP_FLAG_DEFAULT_VERSION) == 0
184 && versionIndex == VER_NDX_INITIAL)) {
185 result.symbol = symbol;
186 return true;
187 }
188
189 // If not hidden, remember the version -- we'll return it, if
190 // it is the only one.
191 if ((versionID & VER_NDX_FLAG_HIDDEN) == 0) {
192 result.versioned_symbol_count++;
193 result.versioned_symbol = symbol;
194 }
195 }
196 return false;
197 }
198
199
200 static elf_sym*
find_symbol_gnuhash(const image_t * image,const SymbolLookupInfo & lookupInfo)201 find_symbol_gnuhash(const image_t* image, const SymbolLookupInfo& lookupInfo)
202 {
203 // Test against the Bloom filter.
204 const uint32 wordSize = sizeof(elf_addr) * 8;
205 const uint32 firstHash = lookupInfo.gnuhash & (wordSize - 1);
206 const uint32 secondHash = lookupInfo.gnuhash >> image->gnuhash.shift2;
207 const uint32 index = (lookupInfo.gnuhash / wordSize) & image->gnuhash.mask_words_count_mask;
208 const elf_addr bloomWord = image->gnuhash.bloom[index];
209 if (((bloomWord >> firstHash) & (bloomWord >> secondHash) & 1) == 0)
210 return NULL;
211
212 // Locate hash chain and corresponding value element.
213 const uint32 bucket = image->gnuhash.buckets[lookupInfo.gnuhash % image->gnuhash.bucket_count];
214 if (bucket == 0)
215 return NULL;
216
217 match_result result;
218 const uint32* chain0 = image->gnuhash.chain0;
219 const uint32* hashValue = &chain0[bucket];
220 do {
221 if (((*hashValue ^ lookupInfo.gnuhash) >> 1) != 0)
222 continue;
223
224 uint32 symIndex = hashValue - chain0;
225 if (match_symbol(image, lookupInfo, symIndex, result))
226 return result.symbol;
227 } while ((*hashValue++ & 1) == 0);
228
229 if (result.versioned_symbol_count == 1)
230 return result.versioned_symbol;
231 return NULL;
232 }
233
234
235 static elf_sym*
find_symbol_sysv(const image_t * image,const SymbolLookupInfo & lookupInfo)236 find_symbol_sysv(const image_t* image, const SymbolLookupInfo& lookupInfo)
237 {
238 if (image->dynamic_ptr == 0)
239 return NULL;
240
241 match_result result;
242
243 uint32 bucket = lookupInfo.hash % HASHTABSIZE(image);
244 for (uint32 symIndex = HASHBUCKETS(image)[bucket]; symIndex != STN_UNDEF;
245 symIndex = HASHCHAINS(image)[symIndex]) {
246 if (match_symbol(image, lookupInfo, symIndex, result))
247 return result.symbol;
248 }
249
250 if (result.versioned_symbol_count == 1)
251 return result.versioned_symbol;
252 return NULL;
253 }
254
255
256 elf_sym*
find_symbol(image_t * image,const SymbolLookupInfo & lookupInfo)257 find_symbol(image_t* image, const SymbolLookupInfo& lookupInfo)
258 {
259 if (image->gnuhash.buckets != NULL) {
260 if (lookupInfo.gnuhash == 0)
261 const_cast<uint32&>(lookupInfo.gnuhash) = elf_gnuhash(lookupInfo.name);
262 return find_symbol_gnuhash(image, lookupInfo);
263 }
264
265 if (lookupInfo.hash == 0)
266 const_cast<uint32&>(lookupInfo.hash) = elf_hash(lookupInfo.name);
267 return find_symbol_sysv(image, lookupInfo);
268 }
269
270
271 void
patch_defined_symbol(image_t * image,const char * name,void ** symbol,int32 * type)272 patch_defined_symbol(image_t* image, const char* name, void** symbol,
273 int32* type)
274 {
275 RuntimeLoaderSymbolPatcher* patcher = image->defined_symbol_patchers;
276 while (patcher != NULL && *symbol != 0) {
277 image_t* inImage = image;
278 patcher->patcher(patcher->cookie, NULL, image, name, &inImage,
279 symbol, type);
280 patcher = patcher->next;
281 }
282 }
283
284
285 void
patch_undefined_symbol(image_t * rootImage,image_t * image,const char * name,image_t ** foundInImage,void ** symbol,int32 * type)286 patch_undefined_symbol(image_t* rootImage, image_t* image, const char* name,
287 image_t** foundInImage, void** symbol, int32* type)
288 {
289 if (*foundInImage != NULL)
290 patch_defined_symbol(*foundInImage, name, symbol, type);
291
292 RuntimeLoaderSymbolPatcher* patcher = image->undefined_symbol_patchers;
293 while (patcher != NULL) {
294 patcher->patcher(patcher->cookie, rootImage, image, name, foundInImage,
295 symbol, type);
296 patcher = patcher->next;
297 }
298 }
299
300
301 status_t
find_symbol(image_t * image,const SymbolLookupInfo & lookupInfo,void ** _location)302 find_symbol(image_t* image, const SymbolLookupInfo& lookupInfo,
303 void **_location)
304 {
305 // get the symbol in the image
306 elf_sym* symbol = find_symbol(image, lookupInfo);
307 if (symbol == NULL)
308 return B_ENTRY_NOT_FOUND;
309
310 void* location = (void*)(symbol->st_value + image->regions[0].delta);
311 int32 symbolType = lookupInfo.type;
312 patch_defined_symbol(image, lookupInfo.name, &location, &symbolType);
313
314 if (_location != NULL)
315 *_location = location;
316
317 return B_OK;
318 }
319
320
321 status_t
find_symbol_breadth_first(image_t * image,const SymbolLookupInfo & lookupInfo,image_t ** _foundInImage,void ** _location)322 find_symbol_breadth_first(image_t* image, const SymbolLookupInfo& lookupInfo,
323 image_t** _foundInImage, void** _location)
324 {
325 image_t* queue[count_loaded_images()];
326 uint32 count = 0;
327 uint32 index = 0;
328 queue[count++] = image;
329 image->flags |= RFLAG_VISITED;
330
331 elf_sym* candidateSymbol = NULL;
332 image_t* candidateImage = NULL;
333
334 while (index < count) {
335 // pop next image
336 image = queue[index++];
337
338 elf_sym* symbol = find_symbol(image, lookupInfo);
339 if (symbol != NULL) {
340 bool isWeak = symbol->Bind() == STB_WEAK;
341 if (candidateImage == NULL || !isWeak) {
342 candidateSymbol = symbol;
343 candidateImage = image;
344
345 if (!isWeak)
346 break;
347 }
348 }
349
350 // push needed images
351 for (uint32 i = 0; i < image->num_needed; i++) {
352 image_t* needed = image->needed[i];
353 if ((needed->flags & RFLAG_VISITED) == 0) {
354 queue[count++] = needed;
355 needed->flags |= RFLAG_VISITED;
356 }
357 }
358 }
359
360 // clear visited flags
361 for (uint32 i = 0; i < count; i++)
362 queue[i]->flags &= ~RFLAG_VISITED;
363
364 if (candidateSymbol == NULL)
365 return B_ENTRY_NOT_FOUND;
366
367 // compute the symbol location
368 *_location = (void*)(candidateSymbol->st_value
369 + candidateImage->regions[0].delta);
370 int32 symbolType = lookupInfo.type;
371 patch_defined_symbol(candidateImage, lookupInfo.name, _location,
372 &symbolType);
373
374 if (_foundInImage != NULL)
375 *_foundInImage = candidateImage;
376
377 return B_OK;
378 }
379
380
381 elf_sym*
find_undefined_symbol_beos(image_t * rootImage,image_t * image,const SymbolLookupInfo & lookupInfo,image_t ** foundInImage)382 find_undefined_symbol_beos(image_t* rootImage, image_t* image,
383 const SymbolLookupInfo& lookupInfo, image_t** foundInImage)
384 {
385 // BeOS style symbol resolution: It is sufficient to check the image itself
386 // and its direct dependencies. The linker would have complained, if the
387 // symbol wasn't there. First we check whether the requesting symbol is
388 // defined already -- then we can simply return it, since, due to symbolic
389 // linking, that's the one we'd find anyway.
390 if (elf_sym* symbol = lookupInfo.requestingSymbol) {
391 if (symbol->st_shndx != SHN_UNDEF
392 && ((symbol->Bind() == STB_GLOBAL)
393 || (symbol->Bind() == STB_WEAK))) {
394 *foundInImage = image;
395 return symbol;
396 }
397 }
398
399 // lookup in image
400 elf_sym* symbol = find_symbol(image, lookupInfo);
401 if (symbol != NULL) {
402 *foundInImage = image;
403 return symbol;
404 }
405
406 // lookup in dependencies
407 for (uint32 i = 0; i < image->num_needed; i++) {
408 if (image->needed[i]->dynamic_ptr) {
409 symbol = find_symbol(image->needed[i], lookupInfo);
410 if (symbol != NULL) {
411 *foundInImage = image->needed[i];
412 return symbol;
413 }
414 }
415 }
416
417 return NULL;
418 }
419
420
421 elf_sym*
find_undefined_symbol_global(image_t * rootImage,image_t * image,const SymbolLookupInfo & lookupInfo,image_t ** _foundInImage)422 find_undefined_symbol_global(image_t* rootImage, image_t* image,
423 const SymbolLookupInfo& lookupInfo, image_t** _foundInImage)
424 {
425 // Global load order symbol resolution: All loaded images are searched for
426 // the symbol in the order they have been loaded. We skip add-on images and
427 // RTLD_LOCAL images though.
428 image_t* candidateImage = NULL;
429 elf_sym* candidateSymbol = NULL;
430
431 // If the requesting image is linked symbolically, look up the symbol there
432 // first.
433 bool symbolic = (image->flags & RFLAG_SYMBOLIC) != 0;
434 if (symbolic) {
435 candidateSymbol = find_symbol(image, lookupInfo);
436 if (candidateSymbol != NULL) {
437 if (candidateSymbol->Bind() != STB_WEAK) {
438 *_foundInImage = image;
439 return candidateSymbol;
440 }
441
442 candidateImage = image;
443 }
444 }
445
446 image_t* otherImage = get_loaded_images().head;
447 while (otherImage != NULL) {
448 if (otherImage == rootImage
449 ? !symbolic
450 : (otherImage->type != B_ADD_ON_IMAGE
451 && (otherImage->flags
452 & (RTLD_GLOBAL | RFLAG_USE_FOR_RESOLVING)) != 0)) {
453 if (elf_sym* symbol = find_symbol(otherImage, lookupInfo)) {
454 *_foundInImage = otherImage;
455 return symbol;
456 }
457 }
458 otherImage = otherImage->next;
459 }
460
461 if (candidateSymbol != NULL)
462 *_foundInImage = candidateImage;
463
464 return candidateSymbol;
465 }
466
467
468 elf_sym*
find_undefined_symbol_add_on(image_t * rootImage,image_t * image,const SymbolLookupInfo & lookupInfo,image_t ** _foundInImage)469 find_undefined_symbol_add_on(image_t* rootImage, image_t* image,
470 const SymbolLookupInfo& lookupInfo, image_t** _foundInImage)
471 {
472 // Similar to global load order symbol resolution: All loaded images are
473 // searched for the symbol in the order they have been loaded. We skip
474 // add-on images and RTLD_LOCAL images though. The root image (i.e. the
475 // add-on image) is skipped, too, but for the add-on itself we look up
476 // a symbol that hasn't been found anywhere else in the add-on image.
477 // The reason for skipping the add-on image is that we must not resolve
478 // library symbol references to symbol definitions in the add-on, as
479 // libraries can be shared between different add-ons and we must not
480 // introduce connections between add-ons.
481
482 // For the add-on image itself resolve non-weak symbols defined in the
483 // add-on to themselves. This makes the symbol resolution order inconsistent
484 // for those symbols, but avoids clashes of global symbols defined in the
485 // add-on with symbols defined e.g. in the application. There's really the
486 // same problem for weak symbols, but we don't have any way to discriminate
487 // weak symbols that must be resolved globally from those that should be
488 // resolved within the add-on.
489 if (rootImage == image) {
490 if (elf_sym* symbol = lookupInfo.requestingSymbol) {
491 if (symbol->st_shndx != SHN_UNDEF
492 && (symbol->Bind() == STB_GLOBAL)) {
493 *_foundInImage = image;
494 return symbol;
495 }
496 }
497 }
498
499 image_t* candidateImage = NULL;
500 elf_sym* candidateSymbol = NULL;
501
502 // If the requesting image is linked symbolically, look up the symbol there
503 // first.
504 bool symbolic = (image->flags & RFLAG_SYMBOLIC) != 0;
505 if (symbolic) {
506 candidateSymbol = find_symbol(image, lookupInfo);
507 if (candidateSymbol != NULL) {
508 if (candidateSymbol->Bind() != STB_WEAK) {
509 *_foundInImage = image;
510 return candidateSymbol;
511 }
512
513 candidateImage = image;
514 }
515 }
516
517 image_t* otherImage = get_loaded_images().head;
518 while (otherImage != NULL) {
519 if (otherImage != rootImage
520 && otherImage->type != B_ADD_ON_IMAGE
521 && (otherImage->flags
522 & (RTLD_GLOBAL | RFLAG_USE_FOR_RESOLVING)) != 0) {
523 if (elf_sym* symbol = find_symbol(otherImage, lookupInfo)) {
524 if (symbol->Bind() != STB_WEAK) {
525 *_foundInImage = otherImage;
526 return symbol;
527 }
528
529 if (candidateSymbol == NULL) {
530 candidateSymbol = symbol;
531 candidateImage = otherImage;
532 }
533 }
534 }
535 otherImage = otherImage->next;
536 }
537
538 // If the symbol has not been found and we're trying to resolve a reference
539 // in the add-on image, we also try to look it up there.
540 if (!symbolic && candidateSymbol == NULL && image == rootImage) {
541 candidateSymbol = find_symbol(image, lookupInfo);
542 candidateImage = image;
543 }
544
545 if (candidateSymbol != NULL)
546 *_foundInImage = candidateImage;
547
548 return candidateSymbol;
549 }
550
551
552 int
resolve_symbol(image_t * rootImage,image_t * image,elf_sym * sym,SymbolLookupCache * cache,addr_t * symAddress,image_t ** symbolImage)553 resolve_symbol(image_t* rootImage, image_t* image, elf_sym* sym,
554 SymbolLookupCache* cache, addr_t* symAddress, image_t** symbolImage)
555 {
556 uint32 index = sym - image->syms;
557
558 // check the cache first
559 if (cache->IsSymbolValueCached(index)) {
560 *symAddress = cache->SymbolValueAt(index, symbolImage);
561 return B_OK;
562 }
563
564 elf_sym* sharedSym;
565 image_t* sharedImage;
566 const char* symName = SYMNAME(image, sym);
567
568 // get the symbol type
569 int32 type = B_SYMBOL_TYPE_ANY;
570 if (sym->Type() == STT_FUNC)
571 type = B_SYMBOL_TYPE_TEXT;
572
573 if (sym->Bind() == STB_LOCAL) {
574 // Local symbols references are always resolved to the given symbol.
575 sharedImage = image;
576 sharedSym = sym;
577 } else {
578 // get the version info
579 const elf_version_info* versionInfo = NULL;
580 if (image->symbol_versions != NULL) {
581 uint32 versionIndex = VER_NDX(image->symbol_versions[index]);
582 if (versionIndex >= VER_NDX_INITIAL)
583 versionInfo = image->versions + versionIndex;
584 }
585
586 // search the symbol
587 sharedSym = rootImage->find_undefined_symbol(rootImage, image,
588 SymbolLookupInfo(symName, type, versionInfo, 0, sym), &sharedImage);
589 }
590
591 enum {
592 SUCCESS,
593 ERROR_NO_SYMBOL,
594 ERROR_WRONG_TYPE,
595 ERROR_NOT_EXPORTED,
596 ERROR_UNPATCHED
597 };
598 uint32 lookupError = ERROR_UNPATCHED;
599
600 bool tlsSymbol = sym->Type() == STT_TLS;
601 void* location = NULL;
602 if (sharedSym == NULL) {
603 // symbol not found at all
604 if (sym->Bind() == STB_WEAK) {
605 // weak symbol: treat as NULL
606 location = sharedImage = NULL;
607 } else {
608 lookupError = ERROR_NO_SYMBOL;
609 sharedImage = NULL;
610 }
611 } else if (sym->Type() != STT_NOTYPE
612 && sym->Type() != sharedSym->Type()
613 && (sym->Type() != STT_OBJECT || sharedSym->Type() != STT_FUNC)) {
614 // symbol not of the requested type, except object which can match function
615 lookupError = ERROR_WRONG_TYPE;
616 sharedImage = NULL;
617 } else if (sharedSym->Bind() != STB_GLOBAL
618 && sharedSym->Bind() != STB_WEAK) {
619 // symbol not exported
620 lookupError = ERROR_NOT_EXPORTED;
621 sharedImage = NULL;
622 } else {
623 // symbol is fine, get its location
624 location = (void*)sharedSym->st_value;
625 if (!tlsSymbol) {
626 location
627 = (void*)((addr_t)location + sharedImage->regions[0].delta);
628 } else
629 lookupError = SUCCESS;
630 }
631
632 if (!tlsSymbol) {
633 patch_undefined_symbol(rootImage, image, symName, &sharedImage,
634 &location, &type);
635 }
636
637 if (type == 0 || (location == NULL && sym->Bind() != STB_WEAK && lookupError != SUCCESS)) {
638 switch (lookupError) {
639 case ERROR_NO_SYMBOL:
640 FATAL("%s: Could not resolve symbol '%s'\n",
641 image->path, symName);
642 break;
643 case ERROR_WRONG_TYPE:
644 FATAL("%s: Found symbol '%s' in shared image but wrong "
645 "type\n", image->path, symName);
646 break;
647 case ERROR_NOT_EXPORTED:
648 FATAL("%s: Found symbol '%s', but not exported\n",
649 image->path, symName);
650 break;
651 case ERROR_UNPATCHED:
652 FATAL("%s: Found symbol '%s', but was hidden by symbol "
653 "patchers\n", image->path, symName);
654 break;
655 }
656
657 if (report_errors())
658 gErrorMessage.AddString("missing symbol", symName);
659
660 return B_MISSING_SYMBOL;
661 }
662
663 cache->SetSymbolValueAt(index, (addr_t)location, sharedImage);
664
665 if (symbolImage)
666 *symbolImage = sharedImage;
667 *symAddress = (addr_t)location;
668 return B_OK;
669 }
670