1 /*
2 * testcode/unitslabhash.c - unit test for slabhash 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/slabhash.h"
45
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;
50
51 /** delete key */
delkey(struct slabhash_testkey * k)52 static void delkey(struct slabhash_testkey* k) {
53 lock_rw_destroy(&k->entry.lock); free(k);}
54
55 /** hash func, very bad to improve collisions, both high and low bits */
myhash(int id)56 static hashvalue_type myhash(int id) {
57 hashvalue_type h = (hashvalue_type)id & 0x0f;
58 h |= (h << 28);
59 return h;
60 }
61
62 /** allocate new key, fill in hash */
newkey(int id)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");
66 k->id = id;
67 k->entry.hash = myhash(id);
68 k->entry.key = k;
69 lock_rw_init(&k->entry.lock);
70 return k;
71 }
72 /** new data el */
newdata(int val)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");
77 d->data = val;
78 return d;
79 }
80
81 /** test hashtable using short sequence */
82 static void
test_short_table(struct slabhash * table)83 test_short_table(struct slabhash* table)
84 {
85 testkey_type* k = newkey(12);
86 testkey_type* k2 = newkey(14);
87 testdata_type* d = newdata(128);
88 testdata_type* d2 = newdata(129);
89
90 k->entry.data = d;
91 k2->entry.data = d2;
92
93 slabhash_insert(table, myhash(12), &k->entry, d, NULL);
94 slabhash_insert(table, myhash(14), &k2->entry, d2, NULL);
95
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);
102 }
103
104 /** number of hash test max */
105 #define HASHTESTMAX 32
106
107 /** test adding a random element */
108 static void
testadd(struct slabhash * table,testdata_type * ref[])109 testadd(struct slabhash* table, testdata_type* ref[])
110 {
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;
117 }
118
119 /** test adding a random element */
120 static void
testremove(struct slabhash * table,testdata_type * ref[])121 testremove(struct slabhash* table, testdata_type* ref[])
122 {
123 int num = random() % HASHTESTMAX;
124 testkey_type* key = newkey(num);
125 slabhash_remove(table, myhash(num), key);
126 ref[num] = NULL;
127 delkey(key);
128 }
129
130 /** test adding a random element */
131 static void
testlookup(struct slabhash * table,testdata_type * ref[])132 testlookup(struct slabhash* table, testdata_type* ref[])
133 {
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;
138 if(en) {
139 unit_assert(en->key);
140 unit_assert(en->data);
141 }
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); }
146 delkey(key);
147 }
148
149 /** check integrity of hash table */
150 static void
check_lru_table(struct lruhash * table)151 check_lru_table(struct lruhash* table)
152 {
153 struct lruhash_entry* p;
154 size_t c = 0;
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 */
162 if(table->lru_start)
163 unit_assert(table->lru_start->lru_prev == NULL);
164 if(table->lru_end)
165 unit_assert(table->lru_end->lru_next == NULL);
166 p = table->lru_start;
167 while(p) {
168 if(p->lru_prev) {
169 unit_assert(p->lru_prev->lru_next == p);
170 }
171 if(p->lru_next) {
172 unit_assert(p->lru_next->lru_prev == p);
173 }
174 c++;
175 p = p->lru_next;
176 }
177 unit_assert(c == table->num);
178
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);
183 }
184
185 /** check integrity of hash table */
186 static void
check_table(struct slabhash * table)187 check_table(struct slabhash* table)
188 {
189 size_t i;
190 for(i=0; i<table->size; i++)
191 check_lru_table(table->array[i]);
192 }
193
194 /** test adding a random element (unlimited range) */
195 static void
testadd_unlim(struct slabhash * table,testdata_type ** ref)196 testadd_unlim(struct slabhash* table, testdata_type** ref)
197 {
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);
203 if(ref)
204 ref[numtoadd] = data;
205 }
206
207 /** test adding a random element (unlimited range) */
208 static void
testremove_unlim(struct slabhash * table,testdata_type ** ref)209 testremove_unlim(struct slabhash* table, testdata_type** ref)
210 {
211 int num = random() % (HASHTESTMAX*10);
212 testkey_type* key = newkey(num);
213 slabhash_remove(table, myhash(num), key);
214 if(ref)
215 ref[num] = NULL;
216 delkey(key);
217 }
218
219 /** test adding a random element (unlimited range) */
220 static void
testlookup_unlim(struct slabhash * table,testdata_type ** ref)221 testlookup_unlim(struct slabhash* table, testdata_type** ref)
222 {
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;
227 if(en) {
228 unit_assert(en->key);
229 unit_assert(en->data);
230 }
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);
233 if(data && ref) {
234 /* its okay for !data, it fell off the lru */
235 unit_assert( data == ref[num] );
236 }
237 if(en) { lock_rw_unlock(&en->lock); }
238 delkey(key);
239 }
240
241 /** test with long sequence of adds, removes and updates, and lookups */
242 static void
test_long_table(struct slabhash * table)243 test_long_table(struct slabhash* table)
244 {
245 /* assuming it all fits in the hashtable, this check will work */
246 testdata_type* ref[HASHTESTMAX * 100];
247 size_t i;
248 memset(ref, 0, sizeof(ref));
249 /* test assumption */
250 if(0) slabhash_status(table, "unit test", 1);
251 srandom(48);
252 for(i=0; i<1000; i++) {
253 /* what to do? */
254 if(i == 500) {
255 slabhash_clear(table);
256 memset(ref, 0, sizeof(ref));
257 continue;
258 }
259 switch(random() % 4) {
260 case 0:
261 case 3:
262 testadd(table, ref);
263 break;
264 case 1:
265 testremove(table, ref);
266 break;
267 case 2:
268 testlookup(table, ref);
269 break;
270 default:
271 unit_assert(0);
272 }
273 if(0) slabhash_status(table, "unit test", 1);
274 check_table(table);
275 }
276
277 /* test more, but 'ref' assumption does not hold anymore */
278 for(i=0; i<1000; i++) {
279 /* what to do? */
280 switch(random() % 4) {
281 case 0:
282 case 3:
283 testadd_unlim(table, ref);
284 break;
285 case 1:
286 testremove_unlim(table, ref);
287 break;
288 case 2:
289 testlookup_unlim(table, ref);
290 break;
291 default:
292 unit_assert(0);
293 }
294 if(0) slabhash_status(table, "unlim", 1);
295 check_table(table);
296 }
297 }
298
299 /** structure to threaded test the lru hash table */
300 struct slab_test_thr {
301 /** thread num, first entry. */
302 int num;
303 /** id */
304 ub_thread_type id;
305 /** hash table */
306 struct slabhash* table;
307 };
308
309 /** main routine for threaded hash table test */
310 static void*
test_thr_main(void * arg)311 test_thr_main(void* arg)
312 {
313 struct slab_test_thr* t = (struct slab_test_thr*)arg;
314 int i;
315 log_thread_set(&t->num);
316 for(i=0; i<1000; i++) {
317 switch(random() % 4) {
318 case 0:
319 case 3:
320 testadd_unlim(t->table, NULL);
321 break;
322 case 1:
323 testremove_unlim(t->table, NULL);
324 break;
325 case 2:
326 testlookup_unlim(t->table, NULL);
327 break;
328 default:
329 unit_assert(0);
330 }
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);
334 }
335 check_table(t->table);
336 return NULL;
337 }
338
339 /** test hash table access by multiple threads */
340 static void
test_threaded_table(struct slabhash * table)341 test_threaded_table(struct slabhash* table)
342 {
343 int numth = 10;
344 struct slab_test_thr t[100];
345 int i;
346
347 for(i=1; i<numth; i++) {
348 t[i].num = i;
349 t[i].table = table;
350 ub_thread_create(&t[i].id, test_thr_main, &t[i]);
351 }
352
353 for(i=1; i<numth; i++) {
354 ub_thread_join(t[i].id);
355 }
356 if(0) slabhash_status(table, "hashtest", 1);
357 }
358
slabhash_test(void)359 void slabhash_test(void)
360 {
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);
376 }
377