xref: /haiku/src/system/runtime_loader/elf_symbol_lookup.cpp (revision a5c0d1a80e18f50987966fda2005210092d7671b)
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
34 equals_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 
47 uint32
48 elf_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 
66 void
67 patch_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 
80 void
81 patch_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 
96 static bool
97 is_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 
107 elf_sym*
108 find_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)) {
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 
227 status_t
228 find_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 
247 status_t
248 find_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 
307 elf_sym*
308 find_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 
347 elf_sym*
348 find_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 
394 elf_sym*
395 find_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 
478 int
479 resolve_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 	else if (sym->Type() == STT_OBJECT)
499 		type = B_SYMBOL_TYPE_DATA;
500 
501 	if (sym->Bind() == STB_LOCAL) {
502 		// Local symbols references are always resolved to the given symbol.
503 		sharedImage = image;
504 		sharedSym = sym;
505 	} else {
506 		// get the version info
507 		const elf_version_info* versionInfo = NULL;
508 		if (image->symbol_versions != NULL) {
509 			uint32 versionIndex = VER_NDX(image->symbol_versions[index]);
510 			if (versionIndex >= VER_NDX_INITIAL)
511 				versionInfo = image->versions + versionIndex;
512 		}
513 
514 		// search the symbol
515 		sharedSym = rootImage->find_undefined_symbol(rootImage, image,
516 			SymbolLookupInfo(symName, type, versionInfo, 0, sym), &sharedImage);
517 	}
518 
519 	enum {
520 		SUCCESS,
521 		ERROR_NO_SYMBOL,
522 		ERROR_WRONG_TYPE,
523 		ERROR_NOT_EXPORTED,
524 		ERROR_UNPATCHED
525 	};
526 	uint32 lookupError = ERROR_UNPATCHED;
527 
528 	bool tlsSymbol = sym->Type() == STT_TLS;
529 	void* location = NULL;
530 	if (sharedSym == NULL) {
531 		// symbol not found at all
532 		if (sym->Bind() == STB_WEAK) {
533 			// weak symbol: treat as NULL
534 			location = sharedImage = NULL;
535 		} else {
536 			lookupError = ERROR_NO_SYMBOL;
537 			sharedImage = NULL;
538 		}
539 	} else if (sym->Type() != STT_NOTYPE
540 		&& sym->Type() != sharedSym->Type()) {
541 		// symbol not of the requested type
542 		lookupError = ERROR_WRONG_TYPE;
543 		sharedImage = NULL;
544 	} else if (sharedSym->Bind() != STB_GLOBAL
545 		&& sharedSym->Bind() != STB_WEAK) {
546 		// symbol not exported
547 		lookupError = ERROR_NOT_EXPORTED;
548 		sharedImage = NULL;
549 	} else {
550 		// symbol is fine, get its location
551 		location = (void*)sharedSym->st_value;
552 		if (!tlsSymbol) {
553 			location
554 				= (void*)((addr_t)location + sharedImage->regions[0].delta);
555 		} else
556 			lookupError = SUCCESS;
557 	}
558 
559 	if (!tlsSymbol) {
560 		patch_undefined_symbol(rootImage, image, symName, &sharedImage,
561 			&location, &type);
562 	}
563 
564 	if (type == 0 || (location == NULL && sym->Bind() != STB_WEAK && lookupError != SUCCESS)) {
565 		switch (lookupError) {
566 			case ERROR_NO_SYMBOL:
567 				FATAL("%s: Could not resolve symbol '%s'\n",
568 					image->path, symName);
569 				break;
570 			case ERROR_WRONG_TYPE:
571 				FATAL("%s: Found symbol '%s' in shared image but wrong "
572 					"type\n", image->path, symName);
573 				break;
574 			case ERROR_NOT_EXPORTED:
575 				FATAL("%s: Found symbol '%s', but not exported\n",
576 					image->path, symName);
577 				break;
578 			case ERROR_UNPATCHED:
579 				FATAL("%s: Found symbol '%s', but was hidden by symbol "
580 					"patchers\n", image->path, symName);
581 				break;
582 		}
583 
584 		if (report_errors())
585 			gErrorMessage.AddString("missing symbol", symName);
586 
587 		return B_MISSING_SYMBOL;
588 	}
589 
590 	cache->SetSymbolValueAt(index, (addr_t)location, sharedImage);
591 
592 	if (symbolImage)
593 		*symbolImage = sharedImage;
594 	*symAddress = (addr_t)location;
595 	return B_OK;
596 }
597