Subversion Repositories HelenOS

Rev

Rev 4354 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  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.  
  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.  
  62. static elf_symbol_t *def_find_in_module(char *name, module_t *m)
  63. {
  64.     elf_symbol_t *sym_table;
  65.     elf_symbol_t *s, *sym;
  66.     elf_word nbucket;
  67.     elf_word nchain;
  68.     elf_word i;
  69.     char *s_name;
  70.     elf_word bucket;
  71.  
  72.     DPRINTF("def_find_in_module('%s', %s)\n", name, m->dyn.soname);
  73.  
  74.     sym_table = m->dyn.sym_tab;
  75.     nbucket = m->dyn.hash[0];
  76.     nchain = m->dyn.hash[1];
  77.  
  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.  
  86.         if (str_cmp(name, s_name) == 0) {
  87.             sym = s;
  88.             break;
  89.         }
  90.  
  91.         i = m->dyn.hash[2 + nbucket + i];
  92.     }
  93.  
  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 */
  103. }
  104.  
  105. /** Find the definition of a symbol in a module and its deps.
  106.  *
  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.
  110.  *
  111.  * @param name      Name of the symbol to search for.
  112.  * @param start     Module in which to start the search..
  113.  * @param mod       (output) Will be filled with a pointer to the module
  114.  *          that contains the symbol.
  115.  */
  116. elf_symbol_t *symbol_bfs_find(char *name, module_t *start, module_t **mod)
  117. {
  118.     module_t *m, *dm;
  119.     elf_symbol_t *sym, *s;
  120.     link_t queue_head;
  121.     size_t i;
  122.  
  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);
  135.     start->bfs_tag = true;
  136.     list_append(&start->queue_link, &queue_head);
  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;
  151.             *mod = m;
  152.             break;
  153.         }
  154.  
  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];
  161.  
  162.             if (dm->bfs_tag == false) {
  163.                 dm->bfs_tag = true;
  164.                 list_append(&dm->queue_link, &queue_head);
  165.             }
  166.         }
  167.     }
  168.  
  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.         return NULL; /* Not found */
  175.     }
  176.  
  177.     return sym; /* Symbol found */
  178. }
  179.  
  180.  
  181. /** Find the definition of a symbol..
  182.  *
  183.  * By definition in System V ABI, if module origin has the flag DT_SYMBOLIC,
  184.  * origin is searched first. Otherwise, or if the symbol hasn't been found,
  185.  * the module dependency graph is searched breadth-first, beginning
  186.  * from the executable program.
  187.  *
  188.  * @param name      Name of the symbol to search for.
  189.  * @param origin    Module in which the dependency originates.
  190.  * @param mod       (output) Will be filled with a pointer to the module
  191.  *          that contains the symbol.
  192.  */
  193. elf_symbol_t *symbol_def_find(char *name, module_t *origin, module_t **mod)
  194. {
  195.     module_t *m, *dm;
  196.     elf_symbol_t *sym, *s;
  197.     link_t queue_head;
  198.     size_t i;
  199.  
  200.     if (origin->dyn.symbolic) {
  201.         /*
  202.          * Origin module has a DT_SYMBOLIC flag.
  203.          * Try this module first
  204.          */
  205.          s = def_find_in_module(name, origin);
  206.          if (s != NULL) {
  207.             /* Found */
  208.             *mod = origin;
  209.             return s;
  210.          }
  211.     }
  212.  
  213.     /* Not DT_SYMBOLIC or no match. Now try other locations. */
  214.  
  215.     if (runtime_env->program) {
  216.         /* Program is dynamic -- start with program as root. */
  217.         return symbol_bfs_find(name, runtime_env->program, mod);
  218.     } else {   
  219.         /* Program is static -- start with @a origin as root. */
  220.         return symbol_bfs_find(name, origin, mod);
  221.     }
  222. }
  223.  
  224. uintptr_t symbol_get_addr(elf_symbol_t *sym, module_t *m)
  225. {
  226.     if (sym->st_shndx == SHN_ABS) {
  227.         /* Do not add bias to absolute symbols */
  228.         return sym->st_value;
  229.     } else {
  230.         return sym->st_value + m->bias;
  231.     }
  232. }
  233.  
  234. /** @}
  235.  */
  236.