/*
* Copyright (c) 2008 Jiri Svoboda
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/** @addtogroup rtld rtld
* @brief
* @{
*/
/**
* @file
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <rtld.h>
#include <symbol.h>
#include <elf.h>
/*
* Hash tables are 32-bit (elf_word) even for 64-bit ELF files.
*/
static elf_word elf_hash(const unsigned char *name)
{
elf_word h = 0, g;
while (*name) {
h = (h << 4) + *name++;
g = h & 0xf0000000;
if (g != 0) h ^= g >> 24;
h &= ~g;
}
return h;
}
static elf_symbol_t *def_find_in_module(char *name, module_t *m)
{
elf_symbol_t *sym_table;
elf_symbol_t *s, *sym;
elf_word nbucket;
elf_word nchain;
elf_word i;
char *s_name;
elf_word bucket;
DPRINTF("def_find_in_module('%s', %s)\n", name, m->dyn.soname);
sym_table = m->dyn.sym_tab;
nbucket = m->dyn.hash[0];
nchain = m->dyn.hash[1];
bucket = elf_hash((unsigned char *)name) % nbucket;
i = m->dyn.hash[2 + bucket];
sym = NULL;
while (i != STN_UNDEF) {
s = &sym_table[i];
s_name = m->dyn.str_tab + s->st_name;
if (str_cmp(name, s_name) == 0) {
sym = s;
break;
}
i = m->dyn.hash[2 + nbucket + i];
}
if (!sym)
return NULL; /* Not found */
if (sym->st_shndx == SHN_UNDEF) {
/* Not a definition */
return NULL;
}
return sym; /* Found */
}
/** Find the definition of a symbol in a module and its deps.
*
* Search the module dependency graph is breadth-first, beginning
* from the module @a start. Thus, @start and all its dependencies
* get searched.
*
* @param name Name of the symbol to search for.
* @param start Module in which to start the search..
* @param mod (output) Will be filled with a pointer to the module
* that contains the symbol.
*/
elf_symbol_t *symbol_bfs_find(char *name, module_t *start, module_t **mod)
{
module_t *m, *dm;
elf_symbol_t *sym, *s;
link_t queue_head;
size_t i;
/*
* Do a BFS using the queue_link and bfs_tag fields.
* Vertices (modules) are tagged the moment they are inserted
* into the queue. This prevents from visiting the same vertex
* more times in case of circular dependencies.
*/
/* Mark all vertices (modules) as unvisited */
modules_untag();
/* Insert root (the program) into the queue and tag it */
list_initialize(&queue_head);
start->bfs_tag = true;
list_append(&start->queue_link, &queue_head);
/* If the symbol is found, it will be stored in 'sym' */
sym = NULL;
/* While queue is not empty */
while (!list_empty(&queue_head)) {
/* Pop first element from the queue */
m = list_get_instance(queue_head.next, module_t, queue_link);
list_remove(&m->queue_link);
s = def_find_in_module(name, m);
if (s != NULL) {
/* Symbol found */
sym = s;
*mod = m;
break;
}
/*
* Insert m's untagged dependencies into the queue
* and tag them.
*/
for (i = 0; i < m->n_deps; ++i) {
dm = m->deps[i];
if (dm->bfs_tag == false) {
dm->bfs_tag = true;
list_append(&dm->queue_link, &queue_head);
}
}
}
/* Empty the queue so that we leave it in a clean state */
while (!list_empty(&queue_head))
list_remove(queue_head.next);
if (!sym) {
printf("Error, symbol '%s' not found anywhere\n", name
); return NULL; /* Not found */
}
return sym; /* Symbol found */
}
/** Find the definition of a symbol..
*
* By definition in System V ABI, if module origin has the flag DT_SYMBOLIC,
* origin is searched first. Otherwise, or if the symbol hasn't been found,
* the module dependency graph is searched breadth-first, beginning
* from the executable program.
*
* @param name Name of the symbol to search for.
* @param origin Module in which the dependency originates.
* @param mod (output) Will be filled with a pointer to the module
* that contains the symbol.
*/
elf_symbol_t *symbol_def_find(char *name, module_t *origin, module_t **mod)
{
module_t *m, *dm;
elf_symbol_t *sym, *s;
link_t queue_head;
size_t i;
if (origin->dyn.symbolic) {
/*
* Origin module has a DT_SYMBOLIC flag.
* Try this module first
*/
s = def_find_in_module(name, origin);
if (s != NULL) {
/* Found */
*mod = origin;
return s;
}
}
/* Not DT_SYMBOLIC or no match. Now try other locations. */
if (runtime_env->program) {
/* Program is dynamic -- start with program as root. */
return symbol_bfs_find(name, runtime_env->program, mod);
} else {
/* Program is static -- start with @a origin as root. */
return symbol_bfs_find(name, origin, mod);
}
}
uintptr_t symbol_get_addr(elf_symbol_t *sym, module_t *m)
{
if (sym->st_shndx == SHN_ABS) {
/* Do not add bias to absolute symbols */
return sym->st_value;
} else {
return sym->st_value + m->bias;
}
}
/** @}
*/