Subversion Repositories HelenOS

/*

 * 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;

    DPRINTF("def_find_in_module('%s', %s)\n", name, m->dyn.soname);

    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 (str_cmp(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 in a module and its deps.

 *

 * Search the module dependency graph is breadth-first, beginning

 * from the module @a start. Thus, @start and all its dependencies

 * get searched.

 *

 * @param name      Name of the symbol to search for.

 * @param start     Module in which to start the search..

 * @param mod       (output) Will be filled with a pointer to the module

 *          that contains the symbol.

 */

elf_symbol_t *symbol_bfs_find(char *name, module_t *start, module_t **mod)

{

    module_t *m, *dm;

    elf_symbol_t *sym, *s;

    link_t queue_head;

    size_t i;

    /*

     * 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 */ 

    modules_untag();

    /* Insert root (the program) into the queue and tag it */

    list_initialize(&queue_head);

    start->bfs_tag = true;

    list_append(&start->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);

        s = def_find_in_module(name, m);

        if (s != NULL) {

            /* Symbol found */

            sym = s;

            *mod = m;

            break;

        }

        /*

         * Insert m's untagged dependencies into the queue

         * and tag them.

         */

        for (i = 0; i < m->n_deps; ++i) {

            dm = m->deps[i];

            if (dm->bfs_tag == false) {

                dm->bfs_tag = true;

                list_append(&dm->queue_link, &queue_head);

            }

        }

    }

    /* 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);

        exit(1);

        return NULL; /* Not found */

    }

    return sym; /* Symbol 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, *dm;

    elf_symbol_t *sym, *s;

    link_t queue_head;

    size_t i;

    if (origin->dyn.symbolic) {

        /*

         * Origin module has a DT_SYMBOLIC flag.

         * Try this module first

         */

         s = def_find_in_module(name, origin);

         if (s != NULL) {

            /* Found */

            *mod = origin;

            return s;

         }

    }

    /* Not DT_SYMBOLIC or no match. Now try other locations. */

    if (runtime_env->program) {

        /* Program is dynamic -- start with program as root. */

        return symbol_bfs_find(name, runtime_env->program, mod);

    } else {   

        /* Program is static -- start with @a origin as root. */

        return symbol_bfs_find(name, origin, mod);

    }

}

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;

    }

}

/** @}

 */