2 * Copyright (c) 2008 Jiri Svoboda
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
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
15 * derived from this software without specific prior written permission.
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
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
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
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
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 /** @addtogroup rtld rtld
42 #include <rtld/module.h>
43 #include <rtld/rtld.h>
44 #include <rtld/rtld_debug.h>
45 #include <rtld/symbol.h>
48 * Hash tables are 32-bit (elf_word) even for 64-bit ELF files.
50 static elf_word
elf_hash(const unsigned char *name
)
55 h
= (h
<< 4) + *name
++;
57 if (g
!= 0) h
^= g
>> 24;
64 static elf_symbol_t
*def_find_in_module(const char *name
, module_t
*m
)
66 elf_symbol_t
*sym_table
;
67 elf_symbol_t
*s
, *sym
;
74 DPRINTF("def_find_in_module('%s', %s)\n", name
, m
->dyn
.soname
);
76 sym_table
= m
->dyn
.sym_tab
;
77 nbucket
= m
->dyn
.hash
[0];
78 /*nchain = m->dyn.hash[1]; XXX Use to check HT range*/
80 bucket
= elf_hash((unsigned char *)name
) % nbucket
;
81 i
= m
->dyn
.hash
[2 + bucket
];
84 while (i
!= STN_UNDEF
) {
86 s_name
= m
->dyn
.str_tab
+ s
->st_name
;
88 if (str_cmp(name
, s_name
) == 0) {
93 i
= m
->dyn
.hash
[2 + nbucket
+ i
];
97 return NULL
; /* Not found */
99 if (sym
->st_shndx
== SHN_UNDEF
) {
100 /* Not a definition */
104 return sym
; /* Found */
107 /** Find the definition of a symbol in a module and its deps.
109 * Search the module dependency graph is breadth-first, beginning
110 * from the module @a start. Thus, @start and all its dependencies
113 * @param name Name of the symbol to search for.
114 * @param start Module in which to start the search..
115 * @param mod (output) Will be filled with a pointer to the module
116 * that contains the symbol.
118 elf_symbol_t
*symbol_bfs_find(const char *name
, module_t
*start
,
122 elf_symbol_t
*sym
, *s
;
127 * Do a BFS using the queue_link and bfs_tag fields.
128 * Vertices (modules) are tagged the moment they are inserted
129 * into the queue. This prevents from visiting the same vertex
130 * more times in case of circular dependencies.
133 /* Mark all vertices (modules) as unvisited */
134 modules_untag(start
->rtld
);
136 /* Insert root (the program) into the queue and tag it */
137 list_initialize(&queue
);
138 start
->bfs_tag
= true;
139 list_append(&start
->queue_link
, &queue
);
141 /* If the symbol is found, it will be stored in 'sym' */
144 /* While queue is not empty */
145 while (!list_empty(&queue
)) {
146 /* Pop first element from the queue */
147 m
= list_get_instance(list_first(&queue
), module_t
, queue_link
);
148 list_remove(&m
->queue_link
);
150 /* If ssf_noroot is specified, do not look in start module */
151 s
= def_find_in_module(name
, m
);
160 * Insert m's untagged dependencies into the queue
163 for (i
= 0; i
< m
->n_deps
; ++i
) {
166 if (dm
->bfs_tag
== false) {
168 list_append(&dm
->queue_link
, &queue
);
173 /* Empty the queue so that we leave it in a clean state */
174 while (!list_empty(&queue
))
175 list_remove(list_first(&queue
));
178 return NULL
; /* Not found */
181 return sym
; /* Symbol found */
185 /** Find the definition of a symbol.
187 * By definition in System V ABI, if module origin has the flag DT_SYMBOLIC,
188 * origin is searched first. Otherwise, search global modules in the default
191 * @param name Name of the symbol to search for.
192 * @param origin Module in which the dependency originates.
193 * @param flags @c ssf_none or @c ssf_noexec to not look for the symbol
194 * in the executable program.
195 * @param mod (output) Will be filled with a pointer to the module
196 * that contains the symbol.
198 elf_symbol_t
*symbol_def_find(const char *name
, module_t
*origin
,
199 symbol_search_flags_t flags
, module_t
**mod
)
203 DPRINTF("symbol_def_find('%s', origin='%s'\n",
204 name
, origin
->dyn
.soname
);
205 if (origin
->dyn
.symbolic
&& (!origin
->exec
|| (flags
& ssf_noexec
) == 0)) {
206 DPRINTF("symbolic->find '%s' in module '%s'\n", name
, origin
->dyn
.soname
);
208 * Origin module has a DT_SYMBOLIC flag.
209 * Try this module first
211 s
= def_find_in_module(name
, origin
);
219 /* Not DT_SYMBOLIC or no match. Now try other locations. */
221 list_foreach(origin
->rtld
->modules
, modules_link
, module_t
, m
) {
222 DPRINTF("module '%s' local?\n", m
->dyn
.soname
);
223 if (!m
->local
&& (!m
->exec
|| (flags
& ssf_noexec
) == 0)) {
224 DPRINTF("!local->find '%s' in module '%s'\n", name
, m
->dyn
.soname
);
225 s
= def_find_in_module(name
, m
);
234 /* Finally, try origin. */
236 DPRINTF("try finding '%s' in origin '%s'\n", name
,
239 if (!origin
->exec
|| (flags
& ssf_noexec
) == 0) {
240 s
= def_find_in_module(name
, origin
);
248 DPRINTF("'%s' not found\n", name
);
252 /** Get symbol address.
255 * @param m Module contaning the symbol
256 * @param tcb TCB of the thread whose thread-local variable instance should
257 * be returned. If @a tcb is @c NULL then @c NULL is returned for
258 * thread-local variables.
260 * @return Symbol address
262 void *symbol_get_addr(elf_symbol_t
*sym
, module_t
*m
, tcb_t
*tcb
)
264 if (ELF_ST_TYPE(sym
->st_info
) == STT_TLS
) {
267 return rtld_tls_get_addr(m
->rtld
, tcb
, m
->id
, sym
->st_value
);
268 } else if (sym
->st_shndx
== SHN_ABS
) {
269 /* Do not add bias to absolute symbols */
270 return (void *) sym
->st_value
;
272 return (void *) (sym
->st_value
+ m
->bias
);