/*-
 * Copyright (c) 2012 Kai Wang
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. 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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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.
 */

#include "ld.h"
#include "ld_hash.h"
#include "ld_layout.h"
#include "ld_output.h"
#include "ld_symbols.h"

ELFTC_VCSID("$Id: ld_hash.c 2917 2013-02-16 07:16:02Z kaiwang27 $");

/*
 * The number of buckets to use for a certain number of symbols.
 * If there are less than 3 symbols, 1 bucket will be used. If
 * there are less than 17 symbols, 3 buckets will be used, and so
 * forth. The bucket numbers are defined by GNU ld. We use the
 * same rules here so we generate hash sections with the same
 * size as those generated by GNU ld.
 */
static unsigned hash_buckets[] = {
	1, 3, 17, 37, 67, 97, 131, 197, 263, 521, 1031,	2053, 4099, 8209,
	16411, 32771, 65537, 131101, 262147
};

void
ld_hash_create_svr4_hash_section(struct ld *ld)
{
	struct ld_output *lo;
	struct ld_output_section *os;
	struct ld_output_data_buffer *odb;
	struct ld_symbol *lsb;
	char hash_name[] = ".hash";
	uint32_t *buf, *buckets, *chains, nbuckets, nchains;
	int i, j;

	lo = ld->ld_output;
	assert(lo != NULL);

	HASH_FIND_STR(lo->lo_ostbl, hash_name, os);
	if (os == NULL)
		os = ld_layout_insert_output_section(ld, hash_name, SHF_ALLOC);
	os->os_type = SHT_HASH;
	os->os_flags = SHF_ALLOC;
	os->os_entsize = 4;
	if (lo->lo_ec == ELFCLASS32)
		os->os_align = 4;
	else
		os->os_align = 8;

	if ((os->os_link = strdup(".dynsym")) == NULL)
		ld_fatal_std(ld, "strdup");

	lo->lo_hash = os;

	assert(ld->ld_dynsym != NULL && ld->ld_dynsym->sy_size > 0);

	nchains = ld->ld_dynsym->sy_size;
	nbuckets = 0;
	for (i = 1;
	    (size_t) i < sizeof(hash_buckets) / sizeof(hash_buckets[0]);
	    i++) {
		if (nchains < hash_buckets[i]) {
			nbuckets = hash_buckets[i - 1];
			break;
		}
	}
	if (nbuckets == 0)
		nbuckets = hash_buckets[i - 1];

	if ((buf = calloc(nbuckets + nchains + 2, sizeof(uint32_t))) == NULL)
		ld_fatal_std(ld, "calloc");

	buf[0] = nbuckets;
	buf[1] = nchains;
	buckets = &buf[2];
	chains = &buf[2 + nbuckets];

	assert(ld->ld_dyn_symbols != NULL);

	i = 1;
	STAILQ_FOREACH(lsb, ld->ld_dyn_symbols, lsb_dyn) {
		if (lsb->lsb_name == NULL) {
			i++;
			continue;
		}

		j = elf_hash(lsb->lsb_name) % nbuckets;
		chains[i] = buckets[j];
		buckets[j] = i;
		i++;
	}

	if ((odb = calloc(1, sizeof(*odb))) == NULL)
		ld_fatal_std(ld, "calloc");

	odb->odb_buf = (void *) buf;
	odb->odb_size = (nbuckets + nchains + 2) * sizeof(uint32_t);
	odb->odb_align = os->os_align;
	odb->odb_type = ELF_T_WORD; /* enable libelf translation */

	(void) ld_output_create_section_element(ld, os, OET_DATA_BUFFER,
	    odb, NULL);
}