uspace/lib/c/generic/rtld/symbol.c

   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 <str.h>
  40
  41 #include <elf/elf.h>
  42 #include <rtld/module.h>
  43 #include <rtld/rtld.h>
  44 #include <rtld/rtld_debug.h>
  45 #include <rtld/symbol.h>
  46
  47 /*
  48  * Hash tables are 32-bit (elf_word) even for 64-bit ELF files.
  49  */
  50 static elf_word elf_hash(const unsigned char *name)
  51 {
  52         elf_word h = 0, g;
  53
  54         while (*name) {
  55                 h = (h << 4) + *name++;
  56                 g = h & 0xf0000000;
  57                 if (g != 0) h ^= g >> 24;
  58                 h &= ~g;
  59         }
  60
  61         return h;
  62 }
  63
  64 static elf_symbol_t *def_find_in_module(const char *name, module_t *m)
  65 {
  66         elf_symbol_t *sym_table;
  67         elf_symbol_t *s, *sym;
  68         elf_word nbucket;
  69         /*elf_word nchain;*/
  70         elf_word i;
  71         char *s_name;
  72         elf_word bucket;
  73
  74         DPRINTF("def_find_in_module('%s', %s)\n", name, m->dyn.soname);
  75
  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*/
  79
  80         bucket = elf_hash((unsigned char *)name) % nbucket;
  81         i = m->dyn.hash[2 + bucket];
  82
  83         sym = NULL;
  84         while (i != STN_UNDEF) {
  85                 s = &sym_table[i];
  86                 s_name = m->dyn.str_tab + s->st_name;
  87
  88                 if (str_cmp(name, s_name) == 0) {
  89                         sym = s;
  90                         break;
  91                 }
  92
  93                 i = m->dyn.hash[2 + nbucket + i];
  94         }
  95
  96         if (!sym)
  97                 return NULL;    /* Not found */
  98
  99         if (sym->st_shndx == SHN_UNDEF) {
 100                 /* Not a definition */
 101                 return NULL;
 102         }
 103
 104         return sym; /* Found */
 105 }
 106
 107 /** Find the definition of a symbol in a module and its deps.
 108  *
 109  * Search the module dependency graph is breadth-first, beginning
 110  * from the module @a start. Thus, @start and all its dependencies
 111  * get searched.
 112  *
 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.
 117  */
 118 elf_symbol_t *symbol_bfs_find(const char *name, module_t *start,
 119     module_t **mod)
 120 {
 121         module_t *m, *dm;
 122         elf_symbol_t *sym, *s;
 123         list_t queue;
 124         size_t i;
 125
 126         /*
 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.
 131          */
 132
 133         /* Mark all vertices (modules) as unvisited */
 134         modules_untag(start->rtld);
 135
 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);
 140
 141         /* If the symbol is found, it will be stored in 'sym' */
 142         sym = NULL;
 143
 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);
 149
 150                 /* If ssf_noroot is specified, do not look in start module */
 151                 s = def_find_in_module(name, m);
 152                 if (s != NULL) {
 153                         /* Symbol found */
 154                         sym = s;
 155                         *mod = m;
 156                         break;
 157                 }
 158
 159                 /*
 160                  * Insert m's untagged dependencies into the queue
 161                  * and tag them.
 162                  */
 163                 for (i = 0; i < m->n_deps; ++i) {
 164                         dm = m->deps[i];
 165
 166                         if (dm->bfs_tag == false) {
 167                                 dm->bfs_tag = true;
 168                                 list_append(&dm->queue_link, &queue);
 169                         }
 170                 }
 171         }
 172
 173         /* Empty the queue so that we leave it in a clean state */
 174         while (!list_empty(&queue))
 175                 list_remove(list_first(&queue));
 176
 177         if (!sym) {
 178                 return NULL; /* Not found */
 179         }
 180
 181         return sym; /* Symbol found */
 182 }
 183
 184
 185 /** Find the definition of a symbol.
 186  *
 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
 189  * order.
 190  *
 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.
 197  */
 198 elf_symbol_t *symbol_def_find(const char *name, module_t *origin,
 199     symbol_search_flags_t flags, module_t **mod)
 200 {
 201         elf_symbol_t *s;
 202
 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);
 207                 /*
 208                  * Origin module has a DT_SYMBOLIC flag.
 209                  * Try this module first
 210                  */
 211                 s = def_find_in_module(name, origin);
 212                 if (s != NULL) {
 213                         /* Found */
 214                         *mod = origin;
 215                         return s;
 216                 }
 217         }
 218
 219         /* Not DT_SYMBOLIC or no match. Now try other locations. */
 220
 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);
 226                         if (s != NULL) {
 227                                 /* Found */
 228                                 *mod = m;
 229                                 return s;
 230                         }
 231                 }
 232         }
 233
 234         /* Finally, try origin. */
 235
 236         DPRINTF("try finding '%s' in origin '%s'\n", name,
 237             origin->dyn.soname);
 238
 239         if (!origin->exec || (flags & ssf_noexec) == 0) {
 240                 s = def_find_in_module(name, origin);
 241                 if (s != NULL) {
 242                         /* Found */
 243                         *mod = origin;
 244                         return s;
 245                 }
 246         }
 247
 248         DPRINTF("'%s' not found\n", name);
 249         return NULL;
 250 }
 251
 252 /** Get symbol address.
 253  *
 254  * @param sym Symbol
 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.
 259  *
 260  * @return Symbol address
 261  */
 262 void *symbol_get_addr(elf_symbol_t *sym, module_t *m, tcb_t *tcb)
 263 {
 264         if (ELF_ST_TYPE(sym->st_info) == STT_TLS) {
 265                 if (tcb == NULL)
 266                         return NULL;
 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;
 271         } else {
 272                 return (void *) (sym->st_value + m->bias);
 273         }
 274 }
 275
 276 /** @}
 277  */