Subversion Repositories HelenOS

Rev

Rev 4348 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2978 svoboda 1
/*
2
 * Copyright (c) 2008 Jiri Svoboda
3
 * All rights reserved.
4
 *
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
7
 * are met:
8
 *
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.
16
 *
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.
27
 */
28
 
29
/** @addtogroup rtld rtld
30
 * @brief
31
 * @{
32
 */
33
/**
34
 * @file
35
 */
36
 
37
#include <stdio.h>
38
#include <stdlib.h>
39
#include <string.h>
40
 
41
#include <rtld.h>
42
#include <symbol.h>
43
#include <elf.h>
44
 
2998 svoboda 45
/*
46
 * Hash tables are 32-bit (elf_word) even for 64-bit ELF files.
47
 */
48
static elf_word elf_hash(const unsigned char *name)
49
{
50
    elf_word h = 0, g;
51
 
52
    while (*name) {
53
        h = (h << 4) + *name++;
54
        g = h & 0xf0000000;
55
        if (g != 0) h ^= g >> 24;
56
        h &= ~g;
57
    }
58
 
59
    return h;
60
}
61
 
2980 svoboda 62
static elf_symbol_t *def_find_in_module(char *name, module_t *m)
2978 svoboda 63
{
64
    elf_symbol_t *sym_table;
2998 svoboda 65
    elf_symbol_t *s, *sym;
66
    elf_word nbucket;
2978 svoboda 67
    elf_word nchain;
2998 svoboda 68
    elf_word i;
2978 svoboda 69
    char *s_name;
2998 svoboda 70
    elf_word bucket;
2978 svoboda 71
 
3690 svoboda 72
    DPRINTF("def_find_in_module('%s', %s)\n", name, m->dyn.soname);
2978 svoboda 73
 
74
    sym_table = m->dyn.sym_tab;
2998 svoboda 75
    nbucket = m->dyn.hash[0];
2978 svoboda 76
    nchain = m->dyn.hash[1];
77
 
2998 svoboda 78
    bucket = elf_hash((unsigned char *)name) % nbucket;
79
    i = m->dyn.hash[2 + bucket];
80
 
81
    sym = NULL;
82
    while (i != STN_UNDEF) {
83
        s = &sym_table[i];
84
        s_name = m->dyn.str_tab + s->st_name;
85
 
4348 svoboda 86
        if (str_cmp(name, s_name) == 0) {
2998 svoboda 87
            sym = s;
88
            break;
2978 svoboda 89
        }
2998 svoboda 90
 
91
        i = m->dyn.hash[2 + nbucket + i];
2978 svoboda 92
    }
93
 
2998 svoboda 94
    if (!sym)
95
        return NULL;    /* Not found */
96
 
97
    if (sym->st_shndx == SHN_UNDEF) {
98
        /* Not a definition */
99
        return NULL;
100
    }
101
 
102
    return sym; /* Found */
2978 svoboda 103
}
104
 
3689 svoboda 105
/** Find the definition of a symbol in a module and its deps.
2999 svoboda 106
 *
3689 svoboda 107
 * Search the module dependency graph is breadth-first, beginning
108
 * from the module @a start. Thus, @start and all its dependencies
109
 * get searched.
2999 svoboda 110
 *
111
 * @param name      Name of the symbol to search for.
3689 svoboda 112
 * @param start     Module in which to start the search..
2999 svoboda 113
 * @param mod       (output) Will be filled with a pointer to the module
114
 *          that contains the symbol.
115
 */
3689 svoboda 116
elf_symbol_t *symbol_bfs_find(char *name, module_t *start, module_t **mod)
2980 svoboda 117
{
3000 svoboda 118
    module_t *m, *dm;
119
    elf_symbol_t *sym, *s;
120
    link_t queue_head;
121
    size_t i;
2980 svoboda 122
 
3000 svoboda 123
    /*
124
     * Do a BFS using the queue_link and bfs_tag fields.
125
     * Vertices (modules) are tagged the moment they are inserted
126
     * into the queue. This prevents from visiting the same vertex
127
     * more times in case of circular dependencies.
128
     */
129
 
130
    /* Mark all vertices (modules) as unvisited */ 
131
    modules_untag();
132
 
133
    /* Insert root (the program) into the queue and tag it */
134
    list_initialize(&queue_head);
3689 svoboda 135
    start->bfs_tag = true;
136
    list_append(&start->queue_link, &queue_head);
3000 svoboda 137
 
138
    /* If the symbol is found, it will be stored in 'sym' */
139
    sym = NULL;
140
 
141
    /* While queue is not empty */
142
    while (!list_empty(&queue_head)) {
143
        /* Pop first element from the queue */
144
        m = list_get_instance(queue_head.next, module_t, queue_link);
145
        list_remove(&m->queue_link);
146
 
147
        s = def_find_in_module(name, m);
148
        if (s != NULL) {
149
            /* Symbol found */
150
            sym = s;
2999 svoboda 151
            *mod = m;
3000 svoboda 152
            break;
2999 svoboda 153
        }
2980 svoboda 154
 
3000 svoboda 155
        /*
156
         * Insert m's untagged dependencies into the queue
157
         * and tag them.
158
         */
159
        for (i = 0; i < m->n_deps; ++i) {
160
            dm = m->deps[i];
2999 svoboda 161
 
3000 svoboda 162
            if (dm->bfs_tag == false) {
163
                dm->bfs_tag = true;
164
                list_append(&dm->queue_link, &queue_head);
165
            }
2999 svoboda 166
        }
3000 svoboda 167
    }
2999 svoboda 168
 
3000 svoboda 169
    /* Empty the queue so that we leave it in a clean state */
170
    while (!list_empty(&queue_head))
171
        list_remove(queue_head.next);
172
 
173
    if (!sym) {
174
        printf("Error, symbol '%s' not found anywhere\n", name);
175
        exit(1);
176
        return NULL; /* Not found */
2999 svoboda 177
    }
178
 
3000 svoboda 179
    return sym; /* Symbol found */
2980 svoboda 180
}
181
 
3689 svoboda 182
 
183
/** Find the definition of a symbol..
184
 *
185
 * By definition in System V ABI, if module origin has the flag DT_SYMBOLIC,
186
 * origin is searched first. Otherwise, or if the symbol hasn't been found,
187
 * the module dependency graph is searched breadth-first, beginning
188
 * from the executable program.
189
 *
190
 * @param name      Name of the symbol to search for.
191
 * @param origin    Module in which the dependency originates.
192
 * @param mod       (output) Will be filled with a pointer to the module
193
 *          that contains the symbol.
194
 */
195
elf_symbol_t *symbol_def_find(char *name, module_t *origin, module_t **mod)
196
{
197
    module_t *m, *dm;
198
    elf_symbol_t *sym, *s;
199
    link_t queue_head;
200
    size_t i;
201
 
202
    if (origin->dyn.symbolic) {
203
        /*
204
         * Origin module has a DT_SYMBOLIC flag.
205
         * Try this module first
206
         */
207
         s = def_find_in_module(name, origin);
208
         if (s != NULL) {
209
            /* Found */
210
            *mod = origin;
211
            return s;
212
         }
213
    }
214
 
3772 svoboda 215
    /* Not DT_SYMBOLIC or no match. Now try other locations. */
216
 
217
    if (runtime_env->program) {
218
        /* Program is dynamic -- start with program as root. */
219
        return symbol_bfs_find(name, runtime_env->program, mod);
220
    } else {   
221
        /* Program is static -- start with @a origin as root. */
222
        return symbol_bfs_find(name, origin, mod);
223
    }
3689 svoboda 224
}
225
 
2998 svoboda 226
uintptr_t symbol_get_addr(elf_symbol_t *sym, module_t *m)
227
{
228
    if (sym->st_shndx == SHN_ABS) {
229
        /* Do not add bias to absolute symbols */
230
        return sym->st_value;
231
    } else {
232
        return sym->st_value + m->bias;
233
    }
234
}
235
 
2978 svoboda 236
/** @}
237
 */