symbol.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 2008 Jiri Svoboda
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  *   notice, this list of conditions and the following disclaimer.
00011  * - Redistributions in binary form must reproduce the above copyright
00012  *   notice, this list of conditions and the following disclaimer in the
00013  *   documentation and/or other materials provided with the distribution.
00014  * - The name of the author may not be used to endorse or promote products
00015  *   derived from this software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00018  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00019  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00021  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00022  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00023  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00024  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  */
00028 
00037 #include <stdio.h>
00038 #include <stdlib.h>
00039 
00040 #include <rtld/rtld.h>
00041 #include <rtld/rtld_debug.h>
00042 #include <rtld/symbol.h>
00043 #include <elf.h>
00044 
00045 /*
00046  * Hash tables are 32-bit (elf_word) even for 64-bit ELF files.
00047  */
00048 static elf_word elf_hash(const unsigned char *name)
00049 {
00050         elf_word h = 0, g;
00051 
00052         while (*name) {
00053                 h = (h << 4) + *name++;
00054                 g = h & 0xf0000000;
00055                 if (g != 0) h ^= g >> 24;
00056                 h &= ~g;
00057         }
00058 
00059         return h;
00060 }
00061 
00062 static elf_symbol_t *def_find_in_module(const char *name, module_t *m)
00063 {
00064         elf_symbol_t *sym_table;
00065         elf_symbol_t *s, *sym;
00066         elf_word nbucket;
00067         /*elf_word nchain;*/
00068         elf_word i;
00069         char *s_name;
00070         elf_word bucket;
00071 
00072         DPRINTF("def_find_in_module('%s', %s)\n", name, m->dyn.soname);
00073 
00074         sym_table = m->dyn.sym_tab;
00075         nbucket = m->dyn.hash[0];
00076         /*nchain = m->dyn.hash[1]; XXX Use to check HT range*/
00077 
00078         bucket = elf_hash((unsigned char *)name) % nbucket;
00079         i = m->dyn.hash[2 + bucket];
00080 
00081         sym = NULL;
00082         while (i != STN_UNDEF) {
00083                 s = &sym_table[i];
00084                 s_name = m->dyn.str_tab + s->st_name;
00085 
00086                 if (str_cmp(name, s_name) == 0) {
00087                         sym = s;
00088                         break;
00089                 }
00090 
00091                 i = m->dyn.hash[2 + nbucket + i];
00092         }
00093 
00094         if (!sym)
00095                 return NULL;    /* Not found */
00096 
00097         if (sym->st_shndx == SHN_UNDEF) {
00098                 /* Not a definition */
00099                 return NULL;
00100         }
00101 
00102         return sym; /* Found */
00103 }
00104 
00116 elf_symbol_t *symbol_bfs_find(const char *name, module_t *start, module_t **mod)
00117 {
00118         module_t *m, *dm;
00119         elf_symbol_t *sym, *s;
00120         link_t queue_head;
00121         size_t i;
00122 
00123         /*
00124          * Do a BFS using the queue_link and bfs_tag fields.
00125          * Vertices (modules) are tagged the moment they are inserted
00126          * into the queue. This prevents from visiting the same vertex
00127          * more times in case of circular dependencies.
00128          */
00129 
00130         /* Mark all vertices (modules) as unvisited */  
00131         modules_untag();
00132 
00133         /* Insert root (the program) into the queue and tag it */
00134         list_initialize(&queue_head);
00135         start->bfs_tag = true;
00136         list_append(&start->queue_link, &queue_head);
00137 
00138         /* If the symbol is found, it will be stored in 'sym' */
00139         sym = NULL;
00140 
00141         /* While queue is not empty */
00142         while (!list_empty(&queue_head)) {
00143                 /* Pop first element from the queue */
00144                 m = list_get_instance(queue_head.next, module_t, queue_link);
00145                 list_remove(&m->queue_link);
00146 
00147                 s = def_find_in_module(name, m);
00148                 if (s != NULL) {
00149                         /* Symbol found */
00150                         sym = s;
00151                         *mod = m;
00152                         break;
00153                 }
00154 
00155                 /*
00156                  * Insert m's untagged dependencies into the queue
00157                  * and tag them.
00158                  */
00159                 for (i = 0; i < m->n_deps; ++i) {
00160                         dm = m->deps[i];
00161 
00162                         if (dm->bfs_tag == false) {
00163                                 dm->bfs_tag = true;
00164                                 list_append(&dm->queue_link, &queue_head);
00165                         }
00166                 }
00167         }
00168 
00169         /* Empty the queue so that we leave it in a clean state */
00170         while (!list_empty(&queue_head))
00171                 list_remove(queue_head.next);
00172 
00173         if (!sym) {
00174                 return NULL; /* Not found */
00175         }
00176 
00177         return sym; /* Symbol found */
00178 }
00179 
00180 
00193 elf_symbol_t *symbol_def_find(const char *name, module_t *origin, module_t **mod)
00194 {
00195         elf_symbol_t *s;
00196 
00197         if (origin->dyn.symbolic) {
00198                 /* 
00199                  * Origin module has a DT_SYMBOLIC flag.
00200                  * Try this module first
00201                  */
00202                  s = def_find_in_module(name, origin);
00203                  if (s != NULL) {
00204                         /* Found */
00205                         *mod = origin;
00206                         return s;
00207                  }
00208         }
00209 
00210         /* Not DT_SYMBOLIC or no match. Now try other locations. */
00211 
00212         if (runtime_env->program) {
00213                 /* Program is dynamic -- start with program as root. */
00214                 return symbol_bfs_find(name, runtime_env->program, mod);
00215         } else {
00216                 /* Program is static -- start with @a origin as root. */
00217                 return symbol_bfs_find(name, origin, mod);
00218         }
00219 }
00220 
00221 void *symbol_get_addr(elf_symbol_t *sym, module_t *m)
00222 {
00223         if (sym->st_shndx == SHN_ABS) {
00224                 /* Do not add bias to absolute symbols */
00225                 return (void *) sym->st_value;
00226         } else {
00227                 return (void *) (sym->st_value + m->bias);
00228         }
00229 }
00230 

Generated on Thu Jun 2 07:45:43 2011 for HelenOS/USB by  doxygen 1.4.7