1 files changed, 0 insertions, 631 deletions

diff --git a/external/unbound/util/storage/lruhash.c b/external/unbound/util/storage/lruhash.c
deleted file mode 100644
index 0003ff491..000000000
--- a/external/unbound/util/storage/lruhash.c
+++ /dev/null
@@ -1,631 +0,0 @@
-/*
- * util/storage/lruhash.c - hashtable, hash function, LRU keeping.
- *
- * Copyright (c) 2007, NLnet Labs. All rights reserved.
- *
- * This software is open source.
- * 
- * 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.
- * 
- * Neither the name of the NLNET LABS nor the names of its contributors may
- * be used to endorse or promote products derived from this software without
- * specific prior written permission.
- * 
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT
- * HOLDER 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.
- */
-
-/**
- * \file
- *
- * This file contains a hashtable with LRU keeping of entries.
- *
- */
-
-#include "config.h"
-#include "util/storage/lruhash.h"
-#include "util/fptr_wlist.h"
-
-void
-bin_init(struct lruhash_bin* array, size_t size)
-{
-	size_t i;
-#ifdef THREADS_DISABLED
-	(void)array;
-#endif
-	for(i=0; i<size; i++) {
-		lock_quick_init(&array[i].lock);
-		lock_protect(&array[i].lock, &array[i], 
-			sizeof(struct lruhash_bin));
-	}
-}
-
-struct lruhash* 
-lruhash_create(size_t start_size, size_t maxmem,
-	lruhash_sizefunc_type sizefunc, lruhash_compfunc_type compfunc,
-	lruhash_delkeyfunc_type delkeyfunc,
-	lruhash_deldatafunc_type deldatafunc, void* arg)
-{
-	struct lruhash* table = (struct lruhash*)calloc(1, 
-		sizeof(struct lruhash));
-	if(!table)
-		return NULL;
-	lock_quick_init(&table->lock);
-	table->sizefunc = sizefunc;
-	table->compfunc = compfunc;
-	table->delkeyfunc = delkeyfunc;
-	table->deldatafunc = deldatafunc;
-	table->cb_arg = arg;
-	table->size = start_size;
-	table->size_mask = (int)(start_size-1);
-	table->lru_start = NULL;
-	table->lru_end = NULL;
-	table->num = 0;
-	table->space_used = 0;
-	table->space_max = maxmem;
-	table->array = calloc(table->size, sizeof(struct lruhash_bin));
-	if(!table->array) {
-		lock_quick_destroy(&table->lock);
-		free(table);
-		return NULL;
-	}
-	bin_init(table->array, table->size);
-	lock_protect(&table->lock, table, sizeof(*table));
-	lock_protect(&table->lock, table->array, 
-		table->size*sizeof(struct lruhash_bin));
-	return table;
-}
-
-void 
-bin_delete(struct lruhash* table, struct lruhash_bin* bin)
-{
-	struct lruhash_entry* p, *np;
-	void *d;
-	if(!bin)
-		return;
-	lock_quick_destroy(&bin->lock);
-	p = bin->overflow_list;
-	bin->overflow_list = NULL;
-	while(p) {
-		np = p->overflow_next;
-		d = p->data;
-		(*table->delkeyfunc)(p->key, table->cb_arg);
-		(*table->deldatafunc)(d, table->cb_arg);
-		p = np;
-	}
-}
-
-void 
-bin_split(struct lruhash* table, struct lruhash_bin* newa, 
-	int newmask)
-{
-	size_t i;
-	struct lruhash_entry *p, *np;
-	struct lruhash_bin* newbin;
-	/* move entries to new table. Notice that since hash x is mapped to
-	 * bin x & mask, and new mask uses one more bit, so all entries in
-	 * one bin will go into the old bin or bin | newbit */
-#ifndef THREADS_DISABLED
-	int newbit = newmask - table->size_mask;
-#endif
-	/* so, really, this task could also be threaded, per bin. */
-	/* LRU list is not changed */
-	for(i=0; i<table->size; i++)
-	{
-		lock_quick_lock(&table->array[i].lock);
-		p = table->array[i].overflow_list;
-		/* lock both destination bins */
-		lock_quick_lock(&newa[i].lock);
-		lock_quick_lock(&newa[newbit|i].lock);
-		while(p) {
-			np = p->overflow_next;
-			/* link into correct new bin */
-			newbin = &newa[p->hash & newmask];
-			p->overflow_next = newbin->overflow_list;
-			newbin->overflow_list = p;
-			p=np;
-		}
-		lock_quick_unlock(&newa[i].lock);
-		lock_quick_unlock(&newa[newbit|i].lock);
-		lock_quick_unlock(&table->array[i].lock);
-	}
-}
-
-void 
-lruhash_delete(struct lruhash* table)
-{
-	size_t i;
-	if(!table)
-		return;
-	/* delete lock on hashtable to force check its OK */
-	lock_quick_destroy(&table->lock);
-	for(i=0; i<table->size; i++)
-		bin_delete(table, &table->array[i]);
-	free(table->array);
-	free(table);
-}
-
-void 
-bin_overflow_remove(struct lruhash_bin* bin, struct lruhash_entry* entry)
-{
-	struct lruhash_entry* p = bin->overflow_list;
-	struct lruhash_entry** prevp = &bin->overflow_list;
-	while(p) {
-		if(p == entry) {
-			*prevp = p->overflow_next;
-			return;
-		}
-		prevp = &p->overflow_next;
-		p = p->overflow_next;
-	}
-}
-
-void 
-reclaim_space(struct lruhash* table, struct lruhash_entry** list)
-{
-	struct lruhash_entry* d;
-	struct lruhash_bin* bin;
-	log_assert(table);
-	/* does not delete MRU entry, so table will not be empty. */
-	while(table->num > 1 && table->space_used > table->space_max) {
-		/* notice that since we hold the hashtable lock, nobody
-		   can change the lru chain. So it cannot be deleted underneath
-		   us. We still need the hashbin and entry write lock to make 
-		   sure we flush all users away from the entry. 
-		   which is unlikely, since it is LRU, if someone got a rdlock
-		   it would be moved to front, but to be sure. */
-		d = table->lru_end;
-		/* specialised, delete from end of double linked list,
-		   and we know num>1, so there is a previous lru entry. */
-		log_assert(d && d->lru_prev);
-		table->lru_end = d->lru_prev;
-		d->lru_prev->lru_next = NULL;
-		/* schedule entry for deletion */
-		bin = &table->array[d->hash & table->size_mask];
-		table->num --;
-		lock_quick_lock(&bin->lock);
-		bin_overflow_remove(bin, d);
-		d->overflow_next = *list;
-		*list = d;
-		lock_rw_wrlock(&d->lock);
-		table->space_used -= table->sizefunc(d->key, d->data);
-		if(table->markdelfunc)
-			(*table->markdelfunc)(d->key);
-		lock_rw_unlock(&d->lock);
-		lock_quick_unlock(&bin->lock);
-	}
-}
-
-struct lruhash_entry* 
-bin_find_entry(struct lruhash* table, 
-	struct lruhash_bin* bin, hashvalue_type hash, void* key)
-{
-	struct lruhash_entry* p = bin->overflow_list;
-	while(p) {
-		if(p->hash == hash && table->compfunc(p->key, key) == 0)
-			return p;
-		p = p->overflow_next;
-	}
-	return NULL;
-}
-
-void 
-table_grow(struct lruhash* table)
-{
-	struct lruhash_bin* newa;
-	int newmask;
-	size_t i;
-	if(table->size_mask == (int)(((size_t)-1)>>1)) {
-		log_err("hash array malloc: size_t too small");
-		return;
-	}
-	/* try to allocate new array, if not fail */
-	newa = calloc(table->size*2, sizeof(struct lruhash_bin));
-	if(!newa) {
-		log_err("hash grow: malloc failed");
-		/* continue with smaller array. Though its slower. */
-		return;
-	}
-	bin_init(newa, table->size*2);
-	newmask = (table->size_mask << 1) | 1;
-	bin_split(table, newa, newmask);
-	/* delete the old bins */
-	lock_unprotect(&table->lock, table->array);
-	for(i=0; i<table->size; i++) {
-		lock_quick_destroy(&table->array[i].lock);
-	}
-	free(table->array);
-	
-	table->size *= 2;
-	table->size_mask = newmask;
-	table->array = newa;
-	lock_protect(&table->lock, table->array, 
-		table->size*sizeof(struct lruhash_bin));
-	return;
-}
-
-void 
-lru_front(struct lruhash* table, struct lruhash_entry* entry)
-{
-	entry->lru_prev = NULL;
-	entry->lru_next = table->lru_start;
-	if(!table->lru_start)
-		table->lru_end = entry;
-	else	table->lru_start->lru_prev = entry;
-	table->lru_start = entry;
-}
-
-void 
-lru_remove(struct lruhash* table, struct lruhash_entry* entry)
-{
-	if(entry->lru_prev)
-		entry->lru_prev->lru_next = entry->lru_next;
-	else	table->lru_start = entry->lru_next;
-	if(entry->lru_next)
-		entry->lru_next->lru_prev = entry->lru_prev;
-	else	table->lru_end = entry->lru_prev;
-}
-
-void 
-lru_touch(struct lruhash* table, struct lruhash_entry* entry)
-{
-	log_assert(table && entry);
-	if(entry == table->lru_start)
-		return; /* nothing to do */
-	/* remove from current lru position */
-	lru_remove(table, entry);
-	/* add at front */
-	lru_front(table, entry);
-}
-
-void 
-lruhash_insert(struct lruhash* table, hashvalue_type hash,
-        struct lruhash_entry* entry, void* data, void* cb_arg)
-{
-	struct lruhash_bin* bin;
-	struct lruhash_entry* found, *reclaimlist=NULL;
-	size_t need_size;
-	fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
-	fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
-	fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
-	fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
-	fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
-	need_size = table->sizefunc(entry->key, data);
-	if(cb_arg == NULL) cb_arg = table->cb_arg;
-
-	/* find bin */
-	lock_quick_lock(&table->lock);
-	bin = &table->array[hash & table->size_mask];
-	lock_quick_lock(&bin->lock);
-
-	/* see if entry exists already */
-	if(!(found=bin_find_entry(table, bin, hash, entry->key))) {
-		/* if not: add to bin */
-		entry->overflow_next = bin->overflow_list;
-		bin->overflow_list = entry;
-		lru_front(table, entry);
-		table->num++;
-		table->space_used += need_size;
-	} else {
-		/* if so: update data - needs a writelock */
-		table->space_used += need_size -
-			(*table->sizefunc)(found->key, found->data);
-		(*table->delkeyfunc)(entry->key, cb_arg);
-		lru_touch(table, found);
-		lock_rw_wrlock(&found->lock);
-		(*table->deldatafunc)(found->data, cb_arg);
-		found->data = data;
-		lock_rw_unlock(&found->lock);
-	}
-	lock_quick_unlock(&bin->lock);
-	if(table->space_used > table->space_max)
-		reclaim_space(table, &reclaimlist);
-	if(table->num >= table->size)
-		table_grow(table);
-	lock_quick_unlock(&table->lock);
-
-	/* finish reclaim if any (outside of critical region) */
-	while(reclaimlist) {
-		struct lruhash_entry* n = reclaimlist->overflow_next;
-		void* d = reclaimlist->data;
-		(*table->delkeyfunc)(reclaimlist->key, cb_arg);
-		(*table->deldatafunc)(d, cb_arg);
-		reclaimlist = n;
-	}
-}
-
-struct lruhash_entry* 
-lruhash_lookup(struct lruhash* table, hashvalue_type hash, void* key, int wr)
-{
-	struct lruhash_entry* entry;
-	struct lruhash_bin* bin;
-	fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
-
-	lock_quick_lock(&table->lock);
-	bin = &table->array[hash & table->size_mask];
-	lock_quick_lock(&bin->lock);
-	if((entry=bin_find_entry(table, bin, hash, key)))
-		lru_touch(table, entry);
-	lock_quick_unlock(&table->lock);
-
-	if(entry) {
-		if(wr)	{ lock_rw_wrlock(&entry->lock); }
-		else	{ lock_rw_rdlock(&entry->lock); }
-	}
-	lock_quick_unlock(&bin->lock);
-	return entry;
-}
-
-void 
-lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key)
-{
-	struct lruhash_entry* entry;
-	struct lruhash_bin* bin;
-	void *d;
-	fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
-	fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
-	fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
-	fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
-	fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
-
-	lock_quick_lock(&table->lock);
-	bin = &table->array[hash & table->size_mask];
-	lock_quick_lock(&bin->lock);
-	if((entry=bin_find_entry(table, bin, hash, key))) {
-		bin_overflow_remove(bin, entry);
-		lru_remove(table, entry);
-	} else {
-		lock_quick_unlock(&table->lock);
-		lock_quick_unlock(&bin->lock);
-		return;
-	}
-	table->num--;
-	table->space_used -= (*table->sizefunc)(entry->key, entry->data);
-	lock_quick_unlock(&table->lock);
-	lock_rw_wrlock(&entry->lock);
-	if(table->markdelfunc)
-		(*table->markdelfunc)(entry->key);
-	lock_rw_unlock(&entry->lock);
-	lock_quick_unlock(&bin->lock);
-	/* finish removal */
-	d = entry->data;
-	(*table->delkeyfunc)(entry->key, table->cb_arg);
-	(*table->deldatafunc)(d, table->cb_arg);
-}
-
-/** clear bin, respecting locks, does not do space, LRU */
-static void
-bin_clear(struct lruhash* table, struct lruhash_bin* bin)
-{
-	struct lruhash_entry* p, *np;
-	void *d;
-	lock_quick_lock(&bin->lock);
-	p = bin->overflow_list; 
-	while(p) {
-		lock_rw_wrlock(&p->lock);
-		np = p->overflow_next;
-		d = p->data;
-		if(table->markdelfunc)
-			(*table->markdelfunc)(p->key);
-		lock_rw_unlock(&p->lock);
-		(*table->delkeyfunc)(p->key, table->cb_arg);
-		(*table->deldatafunc)(d, table->cb_arg);
-		p = np;
-	}
-	bin->overflow_list = NULL;
-	lock_quick_unlock(&bin->lock);
-}
-
-void
-lruhash_clear(struct lruhash* table)
-{
-	size_t i;
-	if(!table)
-		return;
-	fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
-	fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
-	fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
-
-	lock_quick_lock(&table->lock);
-	for(i=0; i<table->size; i++) {
-		bin_clear(table, &table->array[i]);
-	}
-	table->lru_start = NULL;
-	table->lru_end = NULL;
-	table->num = 0;
-	table->space_used = 0;
-	lock_quick_unlock(&table->lock);
-}
-
-void 
-lruhash_status(struct lruhash* table, const char* id, int extended)
-{
-	lock_quick_lock(&table->lock);
-	log_info("%s: %u entries, memory %u / %u",
-		id, (unsigned)table->num, (unsigned)table->space_used,
-		(unsigned)table->space_max);
-	log_info("  itemsize %u, array %u, mask %d",
-		(unsigned)(table->num? table->space_used/table->num : 0),
-		(unsigned)table->size, table->size_mask);
-	if(extended) {
-		size_t i;
-		int min=(int)table->size*2, max=-2;
-		for(i=0; i<table->size; i++) {
-			int here = 0;
-			struct lruhash_entry *en;
-			lock_quick_lock(&table->array[i].lock);
-			en = table->array[i].overflow_list;
-			while(en) {
-				here ++;
-				en = en->overflow_next;
-			}
-			lock_quick_unlock(&table->array[i].lock);
-			if(extended >= 2)
-				log_info("bin[%d] %d", (int)i, here);
-			if(here > max) max = here;
-			if(here < min) min = here;
-		}
-		log_info("  bin min %d, avg %.2lf, max %d", min, 
-			(double)table->num/(double)table->size, max);
-	}
-	lock_quick_unlock(&table->lock);
-}
-
-size_t
-lruhash_get_mem(struct lruhash* table)
-{
-	size_t s;
-	lock_quick_lock(&table->lock);
-	s = sizeof(struct lruhash) + table->space_used;
-#ifdef USE_THREAD_DEBUG
-	if(table->size != 0) {
-		size_t i;
-		for(i=0; i<table->size; i++)
-			s += sizeof(struct lruhash_bin) + 
-				lock_get_mem(&table->array[i].lock);
-	}
-#else /* no THREAD_DEBUG */
-	if(table->size != 0)
-		s += (table->size)*(sizeof(struct lruhash_bin) + 
-			lock_get_mem(&table->array[0].lock));
-#endif
-	lock_quick_unlock(&table->lock);
-	s += lock_get_mem(&table->lock);
-	return s;
-}
-
-void 
-lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_type md)
-{
-	lock_quick_lock(&table->lock);
-	table->markdelfunc = md;
-	lock_quick_unlock(&table->lock);
-}
-
-void 
-lruhash_traverse(struct lruhash* h, int wr, 
-	void (*func)(struct lruhash_entry*, void*), void* arg)
-{
-	size_t i;
-	struct lruhash_entry* e;
-
-	lock_quick_lock(&h->lock);
-	for(i=0; i<h->size; i++) {
-		lock_quick_lock(&h->array[i].lock);
-		for(e = h->array[i].overflow_list; e; e = e->overflow_next) {
-			if(wr) {
-				lock_rw_wrlock(&e->lock);
-			} else {
-				lock_rw_rdlock(&e->lock);
-			}
-			(*func)(e, arg);
-			lock_rw_unlock(&e->lock);
-		}
-		lock_quick_unlock(&h->array[i].lock);
-	}
-	lock_quick_unlock(&h->lock);
-}
-
-/*
- * Demote: the opposite of touch, move an entry to the bottom
- * of the LRU pile.
- */
-
-void
-lru_demote(struct lruhash* table, struct lruhash_entry* entry)
-{
-	log_assert(table && entry);
-	if (entry == table->lru_end)
-		return; /* nothing to do */
-	/* remove from current lru position */
-	lru_remove(table, entry);
-	/* add at end */
-	entry->lru_next = NULL;
-	entry->lru_prev = table->lru_end;
-
-	if (table->lru_end == NULL)
-	{
-		table->lru_start = entry;
-	}
-	else
-	{
-		table->lru_end->lru_next = entry;
-	}
-	table->lru_end = entry;
-}
-
-struct lruhash_entry*
-lruhash_insert_or_retrieve(struct lruhash* table, hashvalue_type hash,
-	struct lruhash_entry* entry, void* data, void* cb_arg)
-{
-	struct lruhash_bin* bin;
-	struct lruhash_entry* found, *reclaimlist = NULL;
-	size_t need_size;
-	fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
-	fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
-	fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
-	fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
-	fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
-	need_size = table->sizefunc(entry->key, data);
-	if (cb_arg == NULL) cb_arg = table->cb_arg;
-
-	/* find bin */
-	lock_quick_lock(&table->lock);
-	bin = &table->array[hash & table->size_mask];
-	lock_quick_lock(&bin->lock);
-
-	/* see if entry exists already */
-	if ((found = bin_find_entry(table, bin, hash, entry->key)) != NULL) {
-		/* if so: keep the existing data - acquire a writelock */
-		lock_rw_wrlock(&found->lock);
-	}
-	else
-	{
-		/* if not: add to bin */
-		entry->overflow_next = bin->overflow_list;
-		bin->overflow_list = entry;
-		lru_front(table, entry);
-		table->num++;
-		table->space_used += need_size;
-		/* return the entry that was presented, and lock it */
-		found = entry;
-		lock_rw_wrlock(&found->lock);
-	}
-	lock_quick_unlock(&bin->lock);
-	if (table->space_used > table->space_max)
-		reclaim_space(table, &reclaimlist);
-	if (table->num >= table->size)
-		table_grow(table);
-	lock_quick_unlock(&table->lock);
-
-	/* finish reclaim if any (outside of critical region) */
-	while (reclaimlist) {
-		struct lruhash_entry* n = reclaimlist->overflow_next;
-		void* d = reclaimlist->data;
-		(*table->delkeyfunc)(reclaimlist->key, cb_arg);
-		(*table->deldatafunc)(d, cb_arg);
-		reclaimlist = n;
-	}
-
-	/* return the entry that was selected */
-	return found;
-}
-