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