diff options
Diffstat (limited to 'external/unbound/testcode/unitslabhash.c')
m--------- | external/unbound | 0 | ||||
-rw-r--r-- | external/unbound/testcode/unitslabhash.c | 376 |
2 files changed, 0 insertions, 376 deletions
diff --git a/external/unbound b/external/unbound new file mode 160000 +Subproject 193bdc4ee3fe2b0d17e547e86512528c2614483 diff --git a/external/unbound/testcode/unitslabhash.c b/external/unbound/testcode/unitslabhash.c deleted file mode 100644 index 565d36139..000000000 --- a/external/unbound/testcode/unitslabhash.c +++ /dev/null @@ -1,376 +0,0 @@ -/* - * testcode/unitslabhash.c - unit test for slabhash table. - * - * 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 - * Tests the locking LRU keeping hash table implementation. - */ - -#include "config.h" -#include "testcode/unitmain.h" -#include "util/log.h" -#include "util/storage/slabhash.h" - -/** use this type for the slabhash test key */ -typedef struct slabhash_testkey testkey_type; -/** use this type for the slabhash test data */ -typedef struct slabhash_testdata testdata_type; - -/** delete key */ -static void delkey(struct slabhash_testkey* k) { - lock_rw_destroy(&k->entry.lock); free(k);} - -/** hash func, very bad to improve collisions, both high and low bits */ -static hashvalue_type myhash(int id) { - hashvalue_type h = (hashvalue_type)id & 0x0f; - h |= (h << 28); - return h; -} - -/** allocate new key, fill in hash */ -static testkey_type* newkey(int id) { - testkey_type* k = (testkey_type*)calloc(1, sizeof(testkey_type)); - if(!k) fatal_exit("out of memory"); - k->id = id; - k->entry.hash = myhash(id); - k->entry.key = k; - lock_rw_init(&k->entry.lock); - return k; -} -/** new data el */ -static testdata_type* newdata(int val) { - testdata_type* d = (testdata_type*)calloc(1, - sizeof(testdata_type)); - if(!d) fatal_exit("out of memory"); - d->data = val; - return d; -} - -/** test hashtable using short sequence */ -static void -test_short_table(struct slabhash* table) -{ - testkey_type* k = newkey(12); - testkey_type* k2 = newkey(14); - testdata_type* d = newdata(128); - testdata_type* d2 = newdata(129); - - k->entry.data = d; - k2->entry.data = d2; - - slabhash_insert(table, myhash(12), &k->entry, d, NULL); - slabhash_insert(table, myhash(14), &k2->entry, d2, NULL); - - unit_assert( slabhash_lookup(table, myhash(12), k, 0) == &k->entry); - lock_rw_unlock( &k->entry.lock ); - unit_assert( slabhash_lookup(table, myhash(14), k2, 0) == &k2->entry); - lock_rw_unlock( &k2->entry.lock ); - slabhash_remove(table, myhash(12), k); - slabhash_remove(table, myhash(14), k2); -} - -/** number of hash test max */ -#define HASHTESTMAX 32 - -/** test adding a random element */ -static void -testadd(struct slabhash* table, testdata_type* ref[]) -{ - int numtoadd = random() % HASHTESTMAX; - testdata_type* data = newdata(numtoadd); - testkey_type* key = newkey(numtoadd); - key->entry.data = data; - slabhash_insert(table, myhash(numtoadd), &key->entry, data, NULL); - ref[numtoadd] = data; -} - -/** test adding a random element */ -static void -testremove(struct slabhash* table, testdata_type* ref[]) -{ - int num = random() % HASHTESTMAX; - testkey_type* key = newkey(num); - slabhash_remove(table, myhash(num), key); - ref[num] = NULL; - delkey(key); -} - -/** test adding a random element */ -static void -testlookup(struct slabhash* table, testdata_type* ref[]) -{ - int num = random() % HASHTESTMAX; - testkey_type* key = newkey(num); - struct lruhash_entry* en = slabhash_lookup(table, myhash(num), key, 0); - testdata_type* data = en? (testdata_type*)en->data : NULL; - if(en) { - unit_assert(en->key); - unit_assert(en->data); - } - if(0) log_info("lookup %d got %d, expect %d", num, en? data->data :-1, - ref[num]? ref[num]->data : -1); - unit_assert( data == ref[num] ); - if(en) { lock_rw_unlock(&en->lock); } - delkey(key); -} - -/** check integrity of hash table */ -static void -check_lru_table(struct lruhash* table) -{ - struct lruhash_entry* p; - size_t c = 0; - lock_quick_lock(&table->lock); - unit_assert( table->num <= table->size); - unit_assert( table->size_mask == (int)table->size-1 ); - unit_assert( (table->lru_start && table->lru_end) || - (!table->lru_start && !table->lru_end) ); - unit_assert( table->space_used <= table->space_max ); - /* check lru list integrity */ - if(table->lru_start) - unit_assert(table->lru_start->lru_prev == NULL); - if(table->lru_end) - unit_assert(table->lru_end->lru_next == NULL); - p = table->lru_start; - while(p) { - if(p->lru_prev) { - unit_assert(p->lru_prev->lru_next == p); - } - if(p->lru_next) { - unit_assert(p->lru_next->lru_prev == p); - } - c++; - p = p->lru_next; - } - unit_assert(c == table->num); - - /* this assertion is specific to the unit test */ - unit_assert( table->space_used == - table->num * test_slabhash_sizefunc(NULL, NULL) ); - lock_quick_unlock(&table->lock); -} - -/** check integrity of hash table */ -static void -check_table(struct slabhash* table) -{ - size_t i; - for(i=0; i<table->size; i++) - check_lru_table(table->array[i]); -} - -/** test adding a random element (unlimited range) */ -static void -testadd_unlim(struct slabhash* table, testdata_type** ref) -{ - int numtoadd = random() % (HASHTESTMAX * 10); - testdata_type* data = newdata(numtoadd); - testkey_type* key = newkey(numtoadd); - key->entry.data = data; - slabhash_insert(table, myhash(numtoadd), &key->entry, data, NULL); - if(ref) - ref[numtoadd] = data; -} - -/** test adding a random element (unlimited range) */ -static void -testremove_unlim(struct slabhash* table, testdata_type** ref) -{ - int num = random() % (HASHTESTMAX*10); - testkey_type* key = newkey(num); - slabhash_remove(table, myhash(num), key); - if(ref) - ref[num] = NULL; - delkey(key); -} - -/** test adding a random element (unlimited range) */ -static void -testlookup_unlim(struct slabhash* table, testdata_type** ref) -{ - int num = random() % (HASHTESTMAX*10); - testkey_type* key = newkey(num); - struct lruhash_entry* en = slabhash_lookup(table, myhash(num), key, 0); - testdata_type* data = en? (testdata_type*)en->data : NULL; - if(en) { - unit_assert(en->key); - unit_assert(en->data); - } - if(0 && ref) log_info("lookup unlim %d got %d, expect %d", num, en ? - data->data :-1, ref[num] ? ref[num]->data : -1); - if(data && ref) { - /* its okay for !data, it fell off the lru */ - unit_assert( data == ref[num] ); - } - if(en) { lock_rw_unlock(&en->lock); } - delkey(key); -} - -/** test with long sequence of adds, removes and updates, and lookups */ -static void -test_long_table(struct slabhash* table) -{ - /* assuming it all fits in the hashtable, this check will work */ - testdata_type* ref[HASHTESTMAX * 100]; - size_t i; - memset(ref, 0, sizeof(ref)); - /* test assumption */ - if(0) slabhash_status(table, "unit test", 1); - srandom(48); - for(i=0; i<1000; i++) { - /* what to do? */ - if(i == 500) { - slabhash_clear(table); - memset(ref, 0, sizeof(ref)); - continue; - } - switch(random() % 4) { - case 0: - case 3: - testadd(table, ref); - break; - case 1: - testremove(table, ref); - break; - case 2: - testlookup(table, ref); - break; - default: - unit_assert(0); - } - if(0) slabhash_status(table, "unit test", 1); - check_table(table); - } - - /* test more, but 'ref' assumption does not hold anymore */ - for(i=0; i<1000; i++) { - /* what to do? */ - switch(random() % 4) { - case 0: - case 3: - testadd_unlim(table, ref); - break; - case 1: - testremove_unlim(table, ref); - break; - case 2: - testlookup_unlim(table, ref); - break; - default: - unit_assert(0); - } - if(0) slabhash_status(table, "unlim", 1); - check_table(table); - } -} - -/** structure to threaded test the lru hash table */ -struct slab_test_thr { - /** thread num, first entry. */ - int num; - /** id */ - ub_thread_type id; - /** hash table */ - struct slabhash* table; -}; - -/** main routine for threaded hash table test */ -static void* -test_thr_main(void* arg) -{ - struct slab_test_thr* t = (struct slab_test_thr*)arg; - int i; - log_thread_set(&t->num); - for(i=0; i<1000; i++) { - switch(random() % 4) { - case 0: - case 3: - testadd_unlim(t->table, NULL); - break; - case 1: - testremove_unlim(t->table, NULL); - break; - case 2: - testlookup_unlim(t->table, NULL); - break; - default: - unit_assert(0); - } - if(0) slabhash_status(t->table, "hashtest", 1); - if(i % 100 == 0) /* because of locking, not all the time */ - check_table(t->table); - } - check_table(t->table); - return NULL; -} - -/** test hash table access by multiple threads */ -static void -test_threaded_table(struct slabhash* table) -{ - int numth = 10; - struct slab_test_thr t[100]; - int i; - - for(i=1; i<numth; i++) { - t[i].num = i; - t[i].table = table; - ub_thread_create(&t[i].id, test_thr_main, &t[i]); - } - - for(i=1; i<numth; i++) { - ub_thread_join(t[i].id); - } - if(0) slabhash_status(table, "hashtest", 1); -} - -void slabhash_test(void) -{ - /* start very very small array, so it can do lots of table_grow() */ - /* also small in size so that reclaim has to be done quickly. */ - struct slabhash* table; - unit_show_feature("slabhash"); - table = slabhash_create(4, 2, 10400, - test_slabhash_sizefunc, test_slabhash_compfunc, - test_slabhash_delkey, test_slabhash_deldata, NULL); - test_short_table(table); - test_long_table(table); - slabhash_delete(table); - table = slabhash_create(4, 2, 10400, - test_slabhash_sizefunc, test_slabhash_compfunc, - test_slabhash_delkey, test_slabhash_deldata, NULL); - test_threaded_table(table); - slabhash_delete(table); -} |