WebSVN – HelenOS – Diff – /branches/dynload/uspace/lib/rtld/symbol.c


/*
 * 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 (strcmp(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);
        exit(1);
        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;
         }
    }
 
    /* Otherwise start in the executable program */
    return symbol_bfs_find(name, runtime_env->program, 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;
    }
}
 
/** @}
 */
 

Rev 3689	Rev 3690
1	/*	1	/*
2	* Copyright (c) 2008 Jiri Svoboda	2	* Copyright (c) 2008 Jiri Svoboda
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	/** @addtogroup rtld rtld	29	/** @addtogroup rtld rtld
30	* @brief	30	* @brief
31	* @{	31	* @{
32	*/	32	*/
33	/**	33	/**
34	* @file	34	* @file
35	*/	35	*/
36		36
37	#include <stdio.h>	37	#include <stdio.h>
38	#include <stdlib.h>	38	#include <stdlib.h>
39	#include <string.h>	39	#include <string.h>
40		40
41	#include <rtld.h>	41	#include <rtld.h>
42	#include <symbol.h>	42	#include <symbol.h>
43	#include <elf.h>	43	#include <elf.h>
44		44
45	/*	45	/*
46	* Hash tables are 32-bit (elf_word) even for 64-bit ELF files.	46	* Hash tables are 32-bit (elf_word) even for 64-bit ELF files.
47	*/	47	*/
48	static elf_word elf_hash(const unsigned char *name)	48	static elf_word elf_hash(const unsigned char *name)
49	{	49	{
50	elf_word h = 0, g;	50	elf_word h = 0, g;
51		51
52	while (*name) {	52	while (*name) {
53	h = (h << 4) + *name++;	53	h = (h << 4) + *name++;
54	g = h & 0xf0000000;	54	g = h & 0xf0000000;
55	if (g != 0) h ^= g >> 24;	55	if (g != 0) h ^= g >> 24;
56	h &= ~g;	56	h &= ~g;
57	}	57	}
58		58
59	return h;	59	return h;
60	}	60	}
61		61
62	static elf_symbol_t def_find_in_module(char name, module_t *m)	62	static elf_symbol_t def_find_in_module(char name, module_t *m)
63	{	63	{
64	elf_symbol_t *sym_table;	64	elf_symbol_t *sym_table;
65	elf_symbol_t s, sym;	65	elf_symbol_t s, sym;
66	elf_word nbucket;	66	elf_word nbucket;
67	elf_word nchain;	67	elf_word nchain;
68	elf_word i;	68	elf_word i;
69	char *s_name;	69	char *s_name;
70	elf_word bucket;	70	elf_word bucket;
71		71
72	// module_name = m->dyn.soname;	-
73	DPRINTF("def_find_in_module('%s', %s)\n", name, module_name);	72	DPRINTF("def_find_in_module('%s', %s)\n", name, m->dyn.soname);
74		73
75	sym_table = m->dyn.sym_tab;	74	sym_table = m->dyn.sym_tab;
76	nbucket = m->dyn.hash[0];	75	nbucket = m->dyn.hash[0];
77	nchain = m->dyn.hash[1];	76	nchain = m->dyn.hash[1];
78		77
79	bucket = elf_hash((unsigned char *)name) % nbucket;	78	bucket = elf_hash((unsigned char *)name) % nbucket;
80	i = m->dyn.hash[2 + bucket];	79	i = m->dyn.hash[2 + bucket];
81		80
82	sym = NULL;	81	sym = NULL;
83	while (i != STN_UNDEF) {	82	while (i != STN_UNDEF) {
84	s = &sym_table[i];	83	s = &sym_table[i];
85	s_name = m->dyn.str_tab + s->st_name;	84	s_name = m->dyn.str_tab + s->st_name;
86		85
87	if (strcmp(name, s_name) == 0) {	86	if (strcmp(name, s_name) == 0) {
88	sym = s;	87	sym = s;
89	break;	88	break;
90	}	89	}
91		90
92	i = m->dyn.hash[2 + nbucket + i];	91	i = m->dyn.hash[2 + nbucket + i];
93	}	92	}
94		93
95	if (!sym)	94	if (!sym)
96	return NULL; /* Not found */	95	return NULL; /* Not found */
97		96
98	if (sym->st_shndx == SHN_UNDEF) {	97	if (sym->st_shndx == SHN_UNDEF) {
99	/* Not a definition */	98	/* Not a definition */
100	return NULL;	99	return NULL;
101	}	100	}
102		101
103	return sym; /* Found */	102	return sym; /* Found */
104	}	103	}
105		104
106	/** Find the definition of a symbol in a module and its deps.	105	/** Find the definition of a symbol in a module and its deps.
107	*	106	*
108	* Search the module dependency graph is breadth-first, beginning	107	* Search the module dependency graph is breadth-first, beginning
109	* from the module @a start. Thus, @start and all its dependencies	108	* from the module @a start. Thus, @start and all its dependencies
110	* get searched.	109	* get searched.
111	*	110	*
112	* @param name Name of the symbol to search for.	111	* @param name Name of the symbol to search for.
113	* @param start Module in which to start the search..	112	* @param start Module in which to start the search..
114	* @param mod (output) Will be filled with a pointer to the module	113	* @param mod (output) Will be filled with a pointer to the module
115	* that contains the symbol.	114	* that contains the symbol.
116	*/	115	*/
117	elf_symbol_t symbol_bfs_find(char name, module_t start, module_t *mod)	116	elf_symbol_t symbol_bfs_find(char name, module_t start, module_t *mod)
118	{	117	{
119	module_t m, dm;	118	module_t m, dm;
120	elf_symbol_t sym, s;	119	elf_symbol_t sym, s;
121	link_t queue_head;	120	link_t queue_head;
122	size_t i;	121	size_t i;
123		122
124	/*	123	/*
125	* Do a BFS using the queue_link and bfs_tag fields.	124	* Do a BFS using the queue_link and bfs_tag fields.
126	* Vertices (modules) are tagged the moment they are inserted	125	* Vertices (modules) are tagged the moment they are inserted
127	* into the queue. This prevents from visiting the same vertex	126	* into the queue. This prevents from visiting the same vertex
128	* more times in case of circular dependencies.	127	* more times in case of circular dependencies.
129	*/	128	*/
130		129
131	/* Mark all vertices (modules) as unvisited */	130	/* Mark all vertices (modules) as unvisited */
132	modules_untag();	131	modules_untag();
133		132
134	/* Insert root (the program) into the queue and tag it */	133	/* Insert root (the program) into the queue and tag it */
135	list_initialize(&queue_head);	134	list_initialize(&queue_head);
136	start->bfs_tag = true;	135	start->bfs_tag = true;
137	list_append(&start->queue_link, &queue_head);	136	list_append(&start->queue_link, &queue_head);
138		137
139	/* If the symbol is found, it will be stored in 'sym' */	138	/* If the symbol is found, it will be stored in 'sym' */
140	sym = NULL;	139	sym = NULL;
141		140
142	/* While queue is not empty */	141	/* While queue is not empty */
143	while (!list_empty(&queue_head)) {	142	while (!list_empty(&queue_head)) {
144	/* Pop first element from the queue */	143	/* Pop first element from the queue */
145	m = list_get_instance(queue_head.next, module_t, queue_link);	144	m = list_get_instance(queue_head.next, module_t, queue_link);
146	list_remove(&m->queue_link);	145	list_remove(&m->queue_link);
147		146
148	s = def_find_in_module(name, m);	147	s = def_find_in_module(name, m);
149	if (s != NULL) {	148	if (s != NULL) {
150	/* Symbol found */	149	/* Symbol found */
151	sym = s;	150	sym = s;
152	*mod = m;	151	*mod = m;
153	break;	152	break;
154	}	153	}
155		154
156	/*	155	/*
157	* Insert m's untagged dependencies into the queue	156	* Insert m's untagged dependencies into the queue
158	* and tag them.	157	* and tag them.
159	*/	158	*/
160	for (i = 0; i < m->n_deps; ++i) {	159	for (i = 0; i < m->n_deps; ++i) {
161	dm = m->deps[i];	160	dm = m->deps[i];
162		161
163	if (dm->bfs_tag == false) {	162	if (dm->bfs_tag == false) {
164	dm->bfs_tag = true;	163	dm->bfs_tag = true;
165	list_append(&dm->queue_link, &queue_head);	164	list_append(&dm->queue_link, &queue_head);
166	}	165	}
167	}	166	}
168	}	167	}
169		168
170	/* Empty the queue so that we leave it in a clean state */	169	/* Empty the queue so that we leave it in a clean state */
171	while (!list_empty(&queue_head))	170	while (!list_empty(&queue_head))
172	list_remove(queue_head.next);	171	list_remove(queue_head.next);
173		172
174	if (!sym) {	173	if (!sym) {
175	printf("Error, symbol '%s' not found anywhere\n", name);	174	printf("Error, symbol '%s' not found anywhere\n", name);
176	exit(1);	175	exit(1);
177	return NULL; /* Not found */	176	return NULL; /* Not found */
178	}	177	}
179		178
180	return sym; /* Symbol found */	179	return sym; /* Symbol found */
181	}	180	}
182		181
183		182
184	/** Find the definition of a symbol..	183	/** Find the definition of a symbol..
185	*	184	*
186	* By definition in System V ABI, if module origin has the flag DT_SYMBOLIC,	185	* By definition in System V ABI, if module origin has the flag DT_SYMBOLIC,
187	* origin is searched first. Otherwise, or if the symbol hasn't been found,	186	* origin is searched first. Otherwise, or if the symbol hasn't been found,
188	* the module dependency graph is searched breadth-first, beginning	187	* the module dependency graph is searched breadth-first, beginning
189	* from the executable program.	188	* from the executable program.
190	*	189	*
191	* @param name Name of the symbol to search for.	190	* @param name Name of the symbol to search for.
192	* @param origin Module in which the dependency originates.	191	* @param origin Module in which the dependency originates.
193	* @param mod (output) Will be filled with a pointer to the module	192	* @param mod (output) Will be filled with a pointer to the module
194	* that contains the symbol.	193	* that contains the symbol.
195	*/	194	*/
196	elf_symbol_t symbol_def_find(char name, module_t origin, module_t *mod)	195	elf_symbol_t symbol_def_find(char name, module_t origin, module_t *mod)
197	{	196	{
198	module_t m, dm;	197	module_t m, dm;
199	elf_symbol_t sym, s;	198	elf_symbol_t sym, s;
200	link_t queue_head;	199	link_t queue_head;
201	size_t i;	200	size_t i;
202		201
203	if (origin->dyn.symbolic) {	202	if (origin->dyn.symbolic) {
204	/*	203	/*
205	* Origin module has a DT_SYMBOLIC flag.	204	* Origin module has a DT_SYMBOLIC flag.
206	* Try this module first	205	* Try this module first
207	*/	206	*/
208	s = def_find_in_module(name, origin);	207	s = def_find_in_module(name, origin);
209	if (s != NULL) {	208	if (s != NULL) {
210	/* Found */	209	/* Found */
211	*mod = origin;	210	*mod = origin;
212	return s;	211	return s;
213	}	212	}
214	}	213	}
215		214
216	/* Otherwise start in the executable program */	215	/* Otherwise start in the executable program */
217	return symbol_bfs_find(name, runtime_env->program, mod);	216	return symbol_bfs_find(name, runtime_env->program, mod);
218	}	217	}
219		218
220	uintptr_t symbol_get_addr(elf_symbol_t sym, module_t m)	219	uintptr_t symbol_get_addr(elf_symbol_t sym, module_t m)
221	{	220	{
222	if (sym->st_shndx == SHN_ABS) {	221	if (sym->st_shndx == SHN_ABS) {
223	/* Do not add bias to absolute symbols */	222	/* Do not add bias to absolute symbols */
224	return sym->st_value;	223	return sym->st_value;
225	} else {	224	} else {
226	return sym->st_value + m->bias;	225	return sym->st_value + m->bias;
227	}	226	}
228	}	227	}
229		228
230	/** @}	229	/** @}
231	*/	230	*/
232		231

Subversion Repositories HelenOS

(root)/branches/dynload/uspace/lib/rtld/symbol.c @ 3690 – Rev 3689 → 3690