WebSVN – HelenOS – Diff – /branches/dynload/uspace/lib/rtld/symbol.c

 /*
  * Copyright (c) 2008 Jiri Svoboda
  * All rights reserved.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
+ *
  * - Redistributions of source code must retain the above copyright
  *   notice, this list of conditions and the following disclaimer.
  * - Redistributions in binary form must reproduce the above copyright
  *   notice, this list of conditions and the following disclaimer in the
  *   documentation and/or other materials provided with the distribution.
  * - The name of the author may not be used to endorse or promote products
  *   derived from this software without specific prior written permission.
+ *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 /** @addtogroup rtld rtld
  * @brief
  * @{
  */
 /**
  * @file
  */
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <rtld.h>
 #include <symbol.h>
 #include <elf.h>
 /*
  * Hash tables are 32-bit (elf_word) even for 64-bit ELF files.
  */
 static elf_word elf_hash(const unsigned char *name)
+{
     elf_word h = 0, g;
     while (*name) {
         h = (h << 4) + *name++;
         g = h & 0xf0000000;
         if (g != 0) h ^= g >> 24;
         h &= ~g;
+    }
     return h;
+}
 static elf_symbol_t *def_find_in_module(char *name, module_t *m)
+{
     elf_symbol_t *sym_table;
     elf_symbol_t *s, *sym;
     elf_word nbucket;
     elf_word nchain;
     elf_word i;
     char *s_name;
     elf_word bucket;
 //  module_name = m->dyn.soname;
 //  printf("def_find_in_module('%s', %s)\n", name, module_name);
     sym_table = m->dyn.sym_tab;
     nbucket = m->dyn.hash[0];
     nchain = m->dyn.hash[1];
     bucket = elf_hash((unsigned char *)name) % nbucket;
     i = m->dyn.hash[2 + bucket];
     sym = NULL;
     while (i != STN_UNDEF) {
         s = &sym_table[i];
         s_name = m->dyn.str_tab + s->st_name;
         if (strcmp(name, s_name) == 0) {
             sym = s;
             break;
+        }
         i = m->dyn.hash[2 + nbucket + i];
+    }
     if (!sym)
         return NULL;    /* Not found */
     if (sym->st_shndx == SHN_UNDEF) {
         /* Not a definition */
         return NULL;
+    }
     return sym; /* Found */
+}
 /** Find the definition of a symbol.
+ *
  * By definition in System V ABI, if module origin has the flag DT_SYMBOLIC,
  * origin is searched first. Otherwise, or if the symbol hasn't been found,
  * the module dependency graph is searched breadth-first, beginning
  * from the executable program.
+ *
  * @param name      Name of the symbol to search for.
  * @param origin    Module in which the dependency originates.
  * @param mod       (output) Will be filled with a pointer to the module
  *          that contains the symbol.
  */
 elf_symbol_t *symbol_def_find(char *name, module_t *origin, module_t **mod)
+{
-    module_t *m;
+    module_t *m, *dm;
-    elf_symbol_t *sym;
+    elf_symbol_t *sym, *s;
+    link_t queue_head;
+    size_t i;
+    if (origin->dyn.symbolic) {
+        /*
-    /* FIXME: support DT_SYMBOLIC */
+         * Origin module has a DT_SYMBOLIC flag.
+         * Try this module first
+         */
+         s = def_find_in_module(name, origin);
+         if (s != NULL) {
+            /* Found */
-    //m = origin;
+            *mod = origin;
+            return s;
+         }
+    }
-    /* Start in the executable program */
+    /* Otherwise start in the executable program */
-    m = runtime_env.program;
+    /*
+     * Do a BFS using the queue_link and bfs_tag fields.
+     * Vertices (modules) are tagged the moment they are inserted
+     * into the queue. This prevents from visiting the same vertex
+     * more times in case of circular dependencies.
+     */
+    /* Mark all vertices (modules) as unvisited */
-    while (true) {
+    modules_untag();
+    /* Insert root (the program) into the queue and tag it */
+    list_initialize(&queue_head);
+    runtime_env.program->bfs_tag = true;
+    list_append(&runtime_env.program->queue_link, &queue_head);
+    /* If the symbol is found, it will be stored in 'sym' */
+    sym = NULL;
+    /* While queue is not empty */
+    while (!list_empty(&queue_head)) {
+        /* Pop first element from the queue */
+        m = list_get_instance(queue_head.next, module_t, queue_link);
+        list_remove(&m->queue_link);
-        sym = def_find_in_module(name, m);
+        s = def_find_in_module(name, m);
-        if (sym != NULL) {
+        if (s != NULL) {
+            /* Symbol found */
+            sym = s;
             *mod = m;
-            return sym;
+            break;
+        }
+        /*
+         * Insert m's untagged dependencies into the queue
+         * and tag them.
+         */
+        for (i = 0; i < m->n_deps; ++i) {
-        if (m->n_deps < 1) break;
+            dm = m->deps[i];
-        /* FIXME: support branching */
+            if (dm->bfs_tag == false) {
-        if (m->n_deps > 1) {
+                dm->bfs_tag = true;
-            printf("error: BFS unimplemented\n");
+                list_append(&dm->queue_link, &queue_head);
-            exit(1);
+            }
+        }
+    }
+    /* Empty the queue so that we leave it in a clean state */
+    while (!list_empty(&queue_head))
+        list_remove(queue_head.next);
+    if (!sym) {
+        printf("Error, symbol '%s' not found anywhere\n", name);
-        m = m->deps[0];
+        exit(1);
+        return NULL; /* Not found */
+    }
-    printf("Error, symbol '%s' not found anywhere\n", name);
-    exit(1);
-    return NULL; /* Not found */
+    return sym; /* Symbol found */
+}
 uintptr_t symbol_get_addr(elf_symbol_t *sym, module_t *m)
+{
     if (sym->st_shndx == SHN_ABS) {
         /* Do not add bias to absolute symbols */
         return sym->st_value;
     } else {
         return sym->st_value + m->bias;
+    }
+}
 /** @}
  */

Subversion Repositories HelenOS

(root)/branches/dynload/uspace/lib/rtld/symbol.c @ 3404 – Rev 2999 → 3000