/*
 * 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 <rtld/rtld.h>
#include <rtld/rtld_debug.h>
#include <rtld/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(const 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]; XXX Use to check HT range*/

	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(const 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) {
		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(const char *name, module_t *origin, module_t **mod)
{
	elf_symbol_t *s;

	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);
	}
}

void *symbol_get_addr(elf_symbol_t *sym, module_t *m)
{
	if (sym->st_shndx == SHN_ABS) {
		/* Do not add bias to absolute symbols */
		return (void *) sym->st_value;
	} else {
		return (void *) (sym->st_value + m->bias);
	}
}

/** @}
 */