2 * testcode/unitslabhash.c - unit test for slabhash table.
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
19 * Neither the name of the NLNET LABS nor the names of its contributors may
20 * be used to endorse or promote products derived from this software without
21 * specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 * Tests the locking LRU keeping hash table implementation.
42 #include "testcode/unitmain.h"
44 #include "util/storage/slabhash.h"
46 /** use this type for the slabhash test key */
47 typedef struct slabhash_testkey testkey_type;
48 /** use this type for the slabhash test data */
49 typedef struct slabhash_testdata testdata_type;
52 static void delkey(struct slabhash_testkey* k) {
53 lock_rw_destroy(&k->entry.lock); free(k);}
55 /** hash func, very bad to improve collisions, both high and low bits */
56 static hashvalue_type myhash(int id) {
57 hashvalue_type h = (hashvalue_type)id & 0x0f;
62 /** allocate new key, fill in hash */
63 static testkey_type* newkey(int id) {
64 testkey_type* k = (testkey_type*)calloc(1, sizeof(testkey_type));
65 if(!k) fatal_exit("out of memory");
67 k->entry.hash = myhash(id);
69 lock_rw_init(&k->entry.lock);
73 static testdata_type* newdata(int val) {
74 testdata_type* d = (testdata_type*)calloc(1,
75 sizeof(testdata_type));
76 if(!d) fatal_exit("out of memory");
81 /** test hashtable using short sequence */
83 test_short_table(struct slabhash* table)
85 testkey_type* k = newkey(12);
86 testkey_type* k2 = newkey(14);
87 testdata_type* d = newdata(128);
88 testdata_type* d2 = newdata(129);
93 slabhash_insert(table, myhash(12), &k->entry, d, NULL);
94 slabhash_insert(table, myhash(14), &k2->entry, d2, NULL);
96 unit_assert( slabhash_lookup(table, myhash(12), k, 0) == &k->entry);
97 lock_rw_unlock( &k->entry.lock );
98 unit_assert( slabhash_lookup(table, myhash(14), k2, 0) == &k2->entry);
99 lock_rw_unlock( &k2->entry.lock );
100 slabhash_remove(table, myhash(12), k);
101 slabhash_remove(table, myhash(14), k2);
104 /** number of hash test max */
105 #define HASHTESTMAX 32
107 /** test adding a random element */
109 testadd(struct slabhash* table, testdata_type* ref[])
111 int numtoadd = random() % HASHTESTMAX;
112 testdata_type* data = newdata(numtoadd);
113 testkey_type* key = newkey(numtoadd);
114 key->entry.data = data;
115 slabhash_insert(table, myhash(numtoadd), &key->entry, data, NULL);
116 ref[numtoadd] = data;
119 /** test adding a random element */
121 testremove(struct slabhash* table, testdata_type* ref[])
123 int num = random() % HASHTESTMAX;
124 testkey_type* key = newkey(num);
125 slabhash_remove(table, myhash(num), key);
130 /** test adding a random element */
132 testlookup(struct slabhash* table, testdata_type* ref[])
134 int num = random() % HASHTESTMAX;
135 testkey_type* key = newkey(num);
136 struct lruhash_entry* en = slabhash_lookup(table, myhash(num), key, 0);
137 testdata_type* data = en? (testdata_type*)en->data : NULL;
139 unit_assert(en->key);
140 unit_assert(en->data);
142 if(0) log_info("lookup %d got %d, expect %d", num, en? data->data :-1,
143 ref[num]? ref[num]->data : -1);
144 unit_assert( data == ref[num] );
145 if(en) { lock_rw_unlock(&en->lock); }
149 /** check integrity of hash table */
151 check_lru_table(struct lruhash* table)
153 struct lruhash_entry* p;
155 lock_quick_lock(&table->lock);
156 unit_assert( table->num <= table->size);
157 unit_assert( table->size_mask == (int)table->size-1 );
158 unit_assert( (table->lru_start && table->lru_end) ||
159 (!table->lru_start && !table->lru_end) );
160 unit_assert( table->space_used <= table->space_max );
161 /* check lru list integrity */
163 unit_assert(table->lru_start->lru_prev == NULL);
165 unit_assert(table->lru_end->lru_next == NULL);
166 p = table->lru_start;
169 unit_assert(p->lru_prev->lru_next == p);
172 unit_assert(p->lru_next->lru_prev == p);
177 unit_assert(c == table->num);
179 /* this assertion is specific to the unit test */
180 unit_assert( table->space_used ==
181 table->num * test_slabhash_sizefunc(NULL, NULL) );
182 lock_quick_unlock(&table->lock);
185 /** check integrity of hash table */
187 check_table(struct slabhash* table)
190 for(i=0; i<table->size; i++)
191 check_lru_table(table->array[i]);
194 /** test adding a random element (unlimited range) */
196 testadd_unlim(struct slabhash* table, testdata_type** ref)
198 int numtoadd = random() % (HASHTESTMAX * 10);
199 testdata_type* data = newdata(numtoadd);
200 testkey_type* key = newkey(numtoadd);
201 key->entry.data = data;
202 slabhash_insert(table, myhash(numtoadd), &key->entry, data, NULL);
204 ref[numtoadd] = data;
207 /** test adding a random element (unlimited range) */
209 testremove_unlim(struct slabhash* table, testdata_type** ref)
211 int num = random() % (HASHTESTMAX*10);
212 testkey_type* key = newkey(num);
213 slabhash_remove(table, myhash(num), key);
219 /** test adding a random element (unlimited range) */
221 testlookup_unlim(struct slabhash* table, testdata_type** ref)
223 int num = random() % (HASHTESTMAX*10);
224 testkey_type* key = newkey(num);
225 struct lruhash_entry* en = slabhash_lookup(table, myhash(num), key, 0);
226 testdata_type* data = en? (testdata_type*)en->data : NULL;
228 unit_assert(en->key);
229 unit_assert(en->data);
231 if(0 && ref) log_info("lookup unlim %d got %d, expect %d", num, en ?
232 data->data :-1, ref[num] ? ref[num]->data : -1);
234 /* its okay for !data, it fell off the lru */
235 unit_assert( data == ref[num] );
237 if(en) { lock_rw_unlock(&en->lock); }
241 /** test with long sequence of adds, removes and updates, and lookups */
243 test_long_table(struct slabhash* table)
245 /* assuming it all fits in the hashtable, this check will work */
246 testdata_type* ref[HASHTESTMAX * 100];
248 memset(ref, 0, sizeof(ref));
249 /* test assumption */
250 if(0) slabhash_status(table, "unit test", 1);
252 for(i=0; i<1000; i++) {
255 slabhash_clear(table);
256 memset(ref, 0, sizeof(ref));
259 switch(random() % 4) {
265 testremove(table, ref);
268 testlookup(table, ref);
273 if(0) slabhash_status(table, "unit test", 1);
277 /* test more, but 'ref' assumption does not hold anymore */
278 for(i=0; i<1000; i++) {
280 switch(random() % 4) {
283 testadd_unlim(table, ref);
286 testremove_unlim(table, ref);
289 testlookup_unlim(table, ref);
294 if(0) slabhash_status(table, "unlim", 1);
299 /** structure to threaded test the lru hash table */
300 struct slab_test_thr {
301 /** thread num, first entry. */
306 struct slabhash* table;
309 /** main routine for threaded hash table test */
311 test_thr_main(void* arg)
313 struct slab_test_thr* t = (struct slab_test_thr*)arg;
315 log_thread_set(&t->num);
316 for(i=0; i<1000; i++) {
317 switch(random() % 4) {
320 testadd_unlim(t->table, NULL);
323 testremove_unlim(t->table, NULL);
326 testlookup_unlim(t->table, NULL);
331 if(0) slabhash_status(t->table, "hashtest", 1);
332 if(i % 100 == 0) /* because of locking, not all the time */
333 check_table(t->table);
335 check_table(t->table);
339 /** test hash table access by multiple threads */
341 test_threaded_table(struct slabhash* table)
344 struct slab_test_thr t[100];
347 for(i=1; i<numth; i++) {
350 ub_thread_create(&t[i].id, test_thr_main, &t[i]);
353 for(i=1; i<numth; i++) {
354 ub_thread_join(t[i].id);
356 if(0) slabhash_status(table, "hashtest", 1);
359 void slabhash_test(void)
361 /* start very very small array, so it can do lots of table_grow() */
362 /* also small in size so that reclaim has to be done quickly. */
363 struct slabhash* table;
364 unit_show_feature("slabhash");
365 table = slabhash_create(4, 2, 10400,
366 test_slabhash_sizefunc, test_slabhash_compfunc,
367 test_slabhash_delkey, test_slabhash_deldata, NULL);
368 test_short_table(table);
369 test_long_table(table);
370 slabhash_delete(table);
371 table = slabhash_create(4, 2, 10400,
372 test_slabhash_sizefunc, test_slabhash_compfunc,
373 test_slabhash_delkey, test_slabhash_deldata, NULL);
374 test_threaded_table(table);
375 slabhash_delete(table);