1 /*
2 * testcode/unitlruhash.c - unit test for lruhash table.
3 *
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 *
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.
18 *
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.
22 *
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.
34 *
35 */
36 /**
37 * \file
38 * Tests the locking LRU keeping hash table implementation.
39 */
40
41 #include "config.h"
42 #include "testcode/unitmain.h"
43 #include "util/log.h"
44 #include "util/storage/lruhash.h"
45 #include "util/storage/slabhash.h" /* for the test structures */
46
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;
51
52 /** delete key */
delkey(struct slabhash_testkey * k)53 static void delkey(struct slabhash_testkey* k) {
54 lock_rw_destroy(&k->entry.lock); free(k);}
55 /** delete data */
deldata(struct slabhash_testdata * d)56 static void deldata(struct slabhash_testdata* d) {free(d);}
57
58 /** hash func, very bad to improve collisions */
myhash(int id)59 static hashvalue_type myhash(int id) {return (hashvalue_type)id & 0x0f;}
60 /** allocate new key, fill in hash */
newkey(int id)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");
64 k->id = id;
65 k->entry.hash = myhash(id);
66 k->entry.key = k;
67 lock_rw_init(&k->entry.lock);
68 return k;
69 }
70 /** new data el */
newdata(int val)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");
75 d->data = val;
76 return d;
77 }
78
79 /** test bin_find_entry function and bin_overflow_remove */
80 static void
test_bin_find_entry(struct lruhash * table)81 test_bin_find_entry(struct lruhash* table)
82 {
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));
91 bin_init(&bin, 1);
92
93 /* remove from empty list */
94 bin_overflow_remove(&bin, &k->entry);
95
96 /* find in empty list */
97 unit_assert( bin_find_entry(table, &bin, h, k) == NULL );
98
99 /* insert */
100 lock_quick_lock(&bin.lock);
101 bin.overflow_list = &k->entry;
102 lock_quick_unlock(&bin.lock);
103
104 /* find, hash not OK. */
105 unit_assert( bin_find_entry(table, &bin, myhash(13), k) == NULL );
106
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 );
110
111 /* find, hash OK, and cmp too */
112 unit_assert( bin_find_entry(table, &bin, h, k) == &k->entry );
113
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 );
119
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);
128
129 /* find, hash not OK. */
130 unit_assert( bin_find_entry(table, &bin, myhash(13), k) == NULL );
131
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 );
135
136 /* find, hash OK, and cmp too */
137 unit_assert( bin_find_entry(table, &bin, h, k) == &k->entry );
138
139 /* remove middle element */
140 unit_assert( bin_find_entry(table, &bin, k4->entry.hash, k4)
141 == &k4->entry );
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);
146
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 );
152
153 lock_quick_destroy(&bin.lock);
154 delkey(k);
155 delkey(k2);
156 delkey(k3);
157 delkey(k4);
158 deldata(d);
159 }
160
161 /** test lru_front lru_remove */
test_lru(struct lruhash * table)162 static void test_lru(struct lruhash* table)
163 {
164 testkey_type* k = newkey(12);
165 testkey_type* k2 = newkey(14);
166 lock_quick_lock(&table->lock);
167
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);
171
172 /* add one */
173 lru_front(table, &k->entry);
174 unit_assert( table->lru_start == &k->entry &&
175 table->lru_end == &k->entry);
176 /* remove it */
177 lru_remove(table, &k->entry);
178 unit_assert( table->lru_start == NULL && table->lru_end == NULL);
179
180 /* add two */
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);
198
199 /* empty the list */
200 lru_remove(table, &k2->entry);
201 unit_assert( table->lru_start == NULL && table->lru_end == NULL);
202 lock_quick_unlock(&table->lock);
203 delkey(k);
204 delkey(k2);
205 }
206
207 /** test hashtable using short sequence */
208 static void
test_short_table(struct lruhash * table)209 test_short_table(struct lruhash* table)
210 {
211 testkey_type* k = newkey(12);
212 testkey_type* k2 = newkey(14);
213 testdata_type* d = newdata(128);
214 testdata_type* d2 = newdata(129);
215
216 k->entry.data = d;
217 k2->entry.data = d2;
218
219 lruhash_insert(table, myhash(12), &k->entry, d, NULL);
220 lruhash_insert(table, myhash(14), &k2->entry, d2, NULL);
221
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);
228 }
229
230 /** number of hash test max */
231 #define HASHTESTMAX 25
232
233 /** test adding a random element */
234 static void
testadd(struct lruhash * table,testdata_type * ref[])235 testadd(struct lruhash* table, testdata_type* ref[])
236 {
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;
243 }
244
245 /** test adding a random element */
246 static void
testremove(struct lruhash * table,testdata_type * ref[])247 testremove(struct lruhash* table, testdata_type* ref[])
248 {
249 int num = random() % HASHTESTMAX;
250 testkey_type* key = newkey(num);
251 lruhash_remove(table, myhash(num), key);
252 ref[num] = NULL;
253 delkey(key);
254 }
255
256 /** test adding a random element */
257 static void
testlookup(struct lruhash * table,testdata_type * ref[])258 testlookup(struct lruhash* table, testdata_type* ref[])
259 {
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;
264 if(en) {
265 unit_assert(en->key);
266 unit_assert(en->data);
267 }
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); }
272 delkey(key);
273 }
274
275 /** check integrity of hash table */
276 static void
check_table(struct lruhash * table)277 check_table(struct lruhash* table)
278 {
279 struct lruhash_entry* p;
280 size_t c = 0;
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 */
288 if(table->lru_start)
289 unit_assert(table->lru_start->lru_prev == NULL);
290 if(table->lru_end)
291 unit_assert(table->lru_end->lru_next == NULL);
292 p = table->lru_start;
293 while(p) {
294 if(p->lru_prev) {
295 unit_assert(p->lru_prev->lru_next == p);
296 }
297 if(p->lru_next) {
298 unit_assert(p->lru_next->lru_prev == p);
299 }
300 c++;
301 p = p->lru_next;
302 }
303 unit_assert(c == table->num);
304
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);
309 }
310
311 /** test adding a random element (unlimited range) */
312 static void
testadd_unlim(struct lruhash * table,testdata_type ** ref)313 testadd_unlim(struct lruhash* table, testdata_type** ref)
314 {
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);
320 if(ref)
321 ref[numtoadd] = data;
322 }
323
324 /** test adding a random element (unlimited range) */
325 static void
testremove_unlim(struct lruhash * table,testdata_type ** ref)326 testremove_unlim(struct lruhash* table, testdata_type** ref)
327 {
328 int num = random() % (HASHTESTMAX*10);
329 testkey_type* key = newkey(num);
330 lruhash_remove(table, myhash(num), key);
331 if(ref)
332 ref[num] = NULL;
333 delkey(key);
334 }
335
336 /** test adding a random element (unlimited range) */
337 static void
testlookup_unlim(struct lruhash * table,testdata_type ** ref)338 testlookup_unlim(struct lruhash* table, testdata_type** ref)
339 {
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;
344 if(en) {
345 unit_assert(en->key);
346 unit_assert(en->data);
347 }
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);
350 if(data && ref) {
351 /* its okay for !data, it fell off the lru */
352 unit_assert( data == ref[num] );
353 }
354 if(en) { lock_rw_unlock(&en->lock); }
355 delkey(key);
356 }
357
358 /** test with long sequence of adds, removes and updates, and lookups */
359 static void
test_long_table(struct lruhash * table)360 test_long_table(struct lruhash* table)
361 {
362 /* assuming it all fits in the hashtable, this check will work */
363 testdata_type* ref[HASHTESTMAX * 100];
364 size_t i;
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);
371 srandom(48);
372 for(i=0; i<1000; i++) {
373 /* what to do? */
374 if(i == 500) {
375 lruhash_clear(table);
376 memset(ref, 0, sizeof(ref));
377 continue;
378 }
379 switch(random() % 4) {
380 case 0:
381 case 3:
382 testadd(table, ref);
383 break;
384 case 1:
385 testremove(table, ref);
386 break;
387 case 2:
388 testlookup(table, ref);
389 break;
390 default:
391 unit_assert(0);
392 }
393 if(0) lruhash_status(table, "unit test", 1);
394 check_table(table);
395 unit_assert( table->num <= HASHTESTMAX );
396 }
397
398 /* test more, but 'ref' assumption does not hold anymore */
399 for(i=0; i<1000; i++) {
400 /* what to do? */
401 switch(random() % 4) {
402 case 0:
403 case 3:
404 testadd_unlim(table, ref);
405 break;
406 case 1:
407 testremove_unlim(table, ref);
408 break;
409 case 2:
410 testlookup_unlim(table, ref);
411 break;
412 default:
413 unit_assert(0);
414 }
415 if(0) lruhash_status(table, "unlim", 1);
416 check_table(table);
417 }
418 }
419
420 /** structure to threaded test the lru hash table */
421 struct test_thr {
422 /** thread num, first entry. */
423 int num;
424 /** id */
425 ub_thread_type id;
426 /** hash table */
427 struct lruhash* table;
428 };
429
430 /** main routine for threaded hash table test */
431 static void*
test_thr_main(void * arg)432 test_thr_main(void* arg)
433 {
434 struct test_thr* t = (struct test_thr*)arg;
435 int i;
436 log_thread_set(&t->num);
437 for(i=0; i<1000; i++) {
438 switch(random() % 4) {
439 case 0:
440 case 3:
441 testadd_unlim(t->table, NULL);
442 break;
443 case 1:
444 testremove_unlim(t->table, NULL);
445 break;
446 case 2:
447 testlookup_unlim(t->table, NULL);
448 break;
449 default:
450 unit_assert(0);
451 }
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);
455 }
456 check_table(t->table);
457 return NULL;
458 }
459
460 /** test hash table access by multiple threads */
461 static void
test_threaded_table(struct lruhash * table)462 test_threaded_table(struct lruhash* table)
463 {
464 int numth = 10;
465 struct test_thr t[100];
466 int i;
467
468 for(i=1; i<numth; i++) {
469 t[i].num = i;
470 t[i].table = table;
471 ub_thread_create(&t[i].id, test_thr_main, &t[i]);
472 }
473
474 for(i=1; i<numth; i++) {
475 ub_thread_join(t[i].id);
476 }
477 if(0) lruhash_status(table, "hashtest", 1);
478 }
479
lruhash_test(void)480 void lruhash_test(void)
481 {
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);
490 test_lru(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);
499 }
500