2 * testcode/unitlruhash.c - unit test for lruhash 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/lruhash.h"
45 #include "util/storage/slabhash.h" /* for the test structures */
47 /** use this type for the lruhash test key */
48 typedef struct slabhash_testkey testkey_type;
49 /** use this type for the lruhash test data */
50 typedef struct slabhash_testdata testdata_type;
53 static void delkey(struct slabhash_testkey* k) {
54 lock_rw_destroy(&k->entry.lock); free(k);}
56 static void deldata(struct slabhash_testdata* d) {free(d);}
58 /** hash func, very bad to improve collisions */
59 static hashvalue_type myhash(int id) {return (hashvalue_type)id & 0x0f;}
60 /** allocate new key, fill in hash */
61 static testkey_type* newkey(int id) {
62 testkey_type* k = (testkey_type*)calloc(1, sizeof(testkey_type));
63 if(!k) fatal_exit("out of memory");
65 k->entry.hash = myhash(id);
67 lock_rw_init(&k->entry.lock);
71 static testdata_type* newdata(int val) {
72 testdata_type* d = (testdata_type*)calloc(1,
73 sizeof(testdata_type));
74 if(!d) fatal_exit("out of memory");
79 /** test bin_find_entry function and bin_overflow_remove */
81 test_bin_find_entry(struct lruhash* table)
83 testkey_type* k = newkey(12);
84 testdata_type* d = newdata(128);
85 testkey_type* k2 = newkey(12 + 1024);
86 testkey_type* k3 = newkey(14);
87 testkey_type* k4 = newkey(12 + 1024*2);
88 hashvalue_type h = myhash(12);
89 struct lruhash_bin bin;
90 memset(&bin, 0, sizeof(bin));
93 /* remove from empty list */
94 bin_overflow_remove(&bin, &k->entry);
96 /* find in empty list */
97 unit_assert( bin_find_entry(table, &bin, h, k) == NULL );
100 lock_quick_lock(&bin.lock);
101 bin.overflow_list = &k->entry;
102 lock_quick_unlock(&bin.lock);
104 /* find, hash not OK. */
105 unit_assert( bin_find_entry(table, &bin, myhash(13), k) == NULL );
107 /* find, hash OK, but cmp not */
108 unit_assert( k->entry.hash == k2->entry.hash );
109 unit_assert( bin_find_entry(table, &bin, h, k2) == NULL );
111 /* find, hash OK, and cmp too */
112 unit_assert( bin_find_entry(table, &bin, h, k) == &k->entry );
114 /* remove the element */
115 lock_quick_lock(&bin.lock);
116 bin_overflow_remove(&bin, &k->entry);
117 lock_quick_unlock(&bin.lock);
118 unit_assert( bin_find_entry(table, &bin, h, k) == NULL );
120 /* prepend two different elements; so the list is long */
121 /* one has the same hash, but different cmp */
122 lock_quick_lock(&bin.lock);
123 unit_assert( k->entry.hash == k4->entry.hash );
124 k4->entry.overflow_next = &k->entry;
125 k3->entry.overflow_next = &k4->entry;
126 bin.overflow_list = &k3->entry;
127 lock_quick_unlock(&bin.lock);
129 /* find, hash not OK. */
130 unit_assert( bin_find_entry(table, &bin, myhash(13), k) == NULL );
132 /* find, hash OK, but cmp not */
133 unit_assert( k->entry.hash == k2->entry.hash );
134 unit_assert( bin_find_entry(table, &bin, h, k2) == NULL );
136 /* find, hash OK, and cmp too */
137 unit_assert( bin_find_entry(table, &bin, h, k) == &k->entry );
139 /* remove middle element */
140 unit_assert( bin_find_entry(table, &bin, k4->entry.hash, k4)
142 lock_quick_lock(&bin.lock);
143 bin_overflow_remove(&bin, &k4->entry);
144 lock_quick_unlock(&bin.lock);
145 unit_assert( bin_find_entry(table, &bin, k4->entry.hash, k4) == NULL);
147 /* remove last element */
148 lock_quick_lock(&bin.lock);
149 bin_overflow_remove(&bin, &k->entry);
150 lock_quick_unlock(&bin.lock);
151 unit_assert( bin_find_entry(table, &bin, h, k) == NULL );
153 lock_quick_destroy(&bin.lock);
161 /** test lru_front lru_remove */
162 static void test_lru(struct lruhash* table)
164 testkey_type* k = newkey(12);
165 testkey_type* k2 = newkey(14);
166 lock_quick_lock(&table->lock);
168 unit_assert( table->lru_start == NULL && table->lru_end == NULL);
169 lru_remove(table, &k->entry);
170 unit_assert( table->lru_start == NULL && table->lru_end == NULL);
173 lru_front(table, &k->entry);
174 unit_assert( table->lru_start == &k->entry &&
175 table->lru_end == &k->entry);
177 lru_remove(table, &k->entry);
178 unit_assert( table->lru_start == NULL && table->lru_end == NULL);
181 lru_front(table, &k->entry);
182 unit_assert( table->lru_start == &k->entry &&
183 table->lru_end == &k->entry);
184 lru_front(table, &k2->entry);
185 unit_assert( table->lru_start == &k2->entry &&
186 table->lru_end == &k->entry);
187 /* remove first in list */
188 lru_remove(table, &k2->entry);
189 unit_assert( table->lru_start == &k->entry &&
190 table->lru_end == &k->entry);
191 lru_front(table, &k2->entry);
192 unit_assert( table->lru_start == &k2->entry &&
193 table->lru_end == &k->entry);
194 /* remove last in list */
195 lru_remove(table, &k->entry);
196 unit_assert( table->lru_start == &k2->entry &&
197 table->lru_end == &k2->entry);
200 lru_remove(table, &k2->entry);
201 unit_assert( table->lru_start == NULL && table->lru_end == NULL);
202 lock_quick_unlock(&table->lock);
207 /** test hashtable using short sequence */
209 test_short_table(struct lruhash* table)
211 testkey_type* k = newkey(12);
212 testkey_type* k2 = newkey(14);
213 testdata_type* d = newdata(128);
214 testdata_type* d2 = newdata(129);
219 lruhash_insert(table, myhash(12), &k->entry, d, NULL);
220 lruhash_insert(table, myhash(14), &k2->entry, d2, NULL);
222 unit_assert( lruhash_lookup(table, myhash(12), k, 0) == &k->entry);
223 lock_rw_unlock( &k->entry.lock );
224 unit_assert( lruhash_lookup(table, myhash(14), k2, 0) == &k2->entry);
225 lock_rw_unlock( &k2->entry.lock );
226 lruhash_remove(table, myhash(12), k);
227 lruhash_remove(table, myhash(14), k2);
230 /** number of hash test max */
231 #define HASHTESTMAX 25
233 /** test adding a random element */
235 testadd(struct lruhash* table, testdata_type* ref[])
237 int numtoadd = random() % HASHTESTMAX;
238 testdata_type* data = newdata(numtoadd);
239 testkey_type* key = newkey(numtoadd);
240 key->entry.data = data;
241 lruhash_insert(table, myhash(numtoadd), &key->entry, data, NULL);
242 ref[numtoadd] = data;
245 /** test adding a random element */
247 testremove(struct lruhash* table, testdata_type* ref[])
249 int num = random() % HASHTESTMAX;
250 testkey_type* key = newkey(num);
251 lruhash_remove(table, myhash(num), key);
256 /** test adding a random element */
258 testlookup(struct lruhash* table, testdata_type* ref[])
260 int num = random() % HASHTESTMAX;
261 testkey_type* key = newkey(num);
262 struct lruhash_entry* en = lruhash_lookup(table, myhash(num), key, 0);
263 testdata_type* data = en? (testdata_type*)en->data : NULL;
265 unit_assert(en->key);
266 unit_assert(en->data);
268 if(0) log_info("lookup %d got %d, expect %d", num, en? data->data :-1,
269 ref[num]? ref[num]->data : -1);
270 unit_assert( data == ref[num] );
271 if(en) { lock_rw_unlock(&en->lock); }
275 /** check integrity of hash table */
277 check_table(struct lruhash* table)
279 struct lruhash_entry* p;
281 lock_quick_lock(&table->lock);
282 unit_assert( table->num <= table->size);
283 unit_assert( table->size_mask == (int)table->size-1 );
284 unit_assert( (table->lru_start && table->lru_end) ||
285 (!table->lru_start && !table->lru_end) );
286 unit_assert( table->space_used <= table->space_max );
287 /* check lru list integrity */
289 unit_assert(table->lru_start->lru_prev == NULL);
291 unit_assert(table->lru_end->lru_next == NULL);
292 p = table->lru_start;
295 unit_assert(p->lru_prev->lru_next == p);
298 unit_assert(p->lru_next->lru_prev == p);
303 unit_assert(c == table->num);
305 /* this assertion is specific to the unit test */
306 unit_assert( table->space_used ==
307 table->num * test_slabhash_sizefunc(NULL, NULL) );
308 lock_quick_unlock(&table->lock);
311 /** test adding a random element (unlimited range) */
313 testadd_unlim(struct lruhash* table, testdata_type** ref)
315 int numtoadd = random() % (HASHTESTMAX * 10);
316 testdata_type* data = newdata(numtoadd);
317 testkey_type* key = newkey(numtoadd);
318 key->entry.data = data;
319 lruhash_insert(table, myhash(numtoadd), &key->entry, data, NULL);
321 ref[numtoadd] = data;
324 /** test adding a random element (unlimited range) */
326 testremove_unlim(struct lruhash* table, testdata_type** ref)
328 int num = random() % (HASHTESTMAX*10);
329 testkey_type* key = newkey(num);
330 lruhash_remove(table, myhash(num), key);
336 /** test adding a random element (unlimited range) */
338 testlookup_unlim(struct lruhash* table, testdata_type** ref)
340 int num = random() % (HASHTESTMAX*10);
341 testkey_type* key = newkey(num);
342 struct lruhash_entry* en = lruhash_lookup(table, myhash(num), key, 0);
343 testdata_type* data = en? (testdata_type*)en->data : NULL;
345 unit_assert(en->key);
346 unit_assert(en->data);
348 if(0 && ref) log_info("lookup unlim %d got %d, expect %d", num, en ?
349 data->data :-1, ref[num] ? ref[num]->data : -1);
351 /* its okay for !data, it fell off the lru */
352 unit_assert( data == ref[num] );
354 if(en) { lock_rw_unlock(&en->lock); }
358 /** test with long sequence of adds, removes and updates, and lookups */
360 test_long_table(struct lruhash* table)
362 /* assuming it all fits in the hashtable, this check will work */
363 testdata_type* ref[HASHTESTMAX * 100];
365 memset(ref, 0, sizeof(ref));
366 /* test assumption */
367 if(0) log_info(" size %d x %d < %d", (int)test_slabhash_sizefunc(NULL, NULL),
368 (int)HASHTESTMAX, (int)table->space_max);
369 unit_assert( test_slabhash_sizefunc(NULL, NULL)*HASHTESTMAX < table->space_max);
370 if(0) lruhash_status(table, "unit test", 1);
372 for(i=0; i<1000; i++) {
375 lruhash_clear(table);
376 memset(ref, 0, sizeof(ref));
379 switch(random() % 4) {
385 testremove(table, ref);
388 testlookup(table, ref);
393 if(0) lruhash_status(table, "unit test", 1);
395 unit_assert( table->num <= HASHTESTMAX );
398 /* test more, but 'ref' assumption does not hold anymore */
399 for(i=0; i<1000; i++) {
401 switch(random() % 4) {
404 testadd_unlim(table, ref);
407 testremove_unlim(table, ref);
410 testlookup_unlim(table, ref);
415 if(0) lruhash_status(table, "unlim", 1);
420 /** structure to threaded test the lru hash table */
422 /** thread num, first entry. */
427 struct lruhash* table;
430 /** main routine for threaded hash table test */
432 test_thr_main(void* arg)
434 struct test_thr* t = (struct test_thr*)arg;
436 log_thread_set(&t->num);
437 for(i=0; i<1000; i++) {
438 switch(random() % 4) {
441 testadd_unlim(t->table, NULL);
444 testremove_unlim(t->table, NULL);
447 testlookup_unlim(t->table, NULL);
452 if(0) lruhash_status(t->table, "hashtest", 1);
453 if(i % 100 == 0) /* because of locking, not all the time */
454 check_table(t->table);
456 check_table(t->table);
460 /** test hash table access by multiple threads */
462 test_threaded_table(struct lruhash* table)
465 struct test_thr t[100];
468 for(i=1; i<numth; i++) {
471 ub_thread_create(&t[i].id, test_thr_main, &t[i]);
474 for(i=1; i<numth; i++) {
475 ub_thread_join(t[i].id);
477 if(0) lruhash_status(table, "hashtest", 1);
480 void lruhash_test(void)
482 /* start very very small array, so it can do lots of table_grow() */
483 /* also small in size so that reclaim has to be done quickly. */
484 struct lruhash* table ;
485 unit_show_feature("lruhash");
486 table = lruhash_create(2, 8192,
487 test_slabhash_sizefunc, test_slabhash_compfunc,
488 test_slabhash_delkey, test_slabhash_deldata, NULL);
489 test_bin_find_entry(table);
491 test_short_table(table);
492 test_long_table(table);
493 lruhash_delete(table);
494 table = lruhash_create(2, 8192,
495 test_slabhash_sizefunc, test_slabhash_compfunc,
496 test_slabhash_delkey, test_slabhash_deldata, NULL);
497 test_threaded_table(table);
498 lruhash_delete(table);