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 */ 53 static void delkey(struct slabhash_testkey* k) { 54 lock_rw_destroy(&k->entry.lock); free(k);} 55 /** delete data */ 56 static void deldata(struct slabhash_testdata* d) {free(d);} 57 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"); 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 */ 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 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) == 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) == 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) == NULL ); 110 111 /* find, hash OK, and cmp too */ 112 unit_assert( bin_find_entry(table, &bin, h, k, NULL) == &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) == 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) == 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) == NULL ); 135 136 /* find, hash OK, and cmp too */ 137 unit_assert( bin_find_entry(table, &bin, h, k, NULL) == &k->entry ); 138 139 /* remove middle element */ 140 unit_assert( bin_find_entry(table, &bin, k4->entry.hash, k4, NULL) 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) == 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) == 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 */ 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 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 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 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 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 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 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 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 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 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* 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 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 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