testcode/unitlruhash.c

   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_t;
  49 /** use this type for the lruhash test data */
  50 typedef struct slabhash_testdata testdata_t;
  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_t myhash(int id) {return (hashvalue_t)id & 0x0f;}
  60 /** allocate new key, fill in hash */
  61 static testkey_t* newkey(int id) {
  62         testkey_t* k = (testkey_t*)calloc(1, sizeof(testkey_t));
  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_t* newdata(int val) {
  72         testdata_t* d = (testdata_t*)calloc(1,
  73                 sizeof(testdata_t));
  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_t* k = newkey(12);
  84         testdata_t* d = newdata(128);
  85         testkey_t* k2 = newkey(12 + 1024);
  86         testkey_t* k3 = newkey(14);
  87         testkey_t* k4 = newkey(12 + 1024*2);
  88         hashvalue_t 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 */
 162 static void test_lru(struct lruhash* table)
 163 {
 164         testkey_t* k = newkey(12);
 165         testkey_t* 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_t* k = newkey(12);
 212         testkey_t* k2 = newkey(14);
 213         testdata_t* d = newdata(128);
 214         testdata_t* 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_t* ref[])
 236 {
 237         int numtoadd = random() % HASHTESTMAX;
 238         testdata_t* data = newdata(numtoadd);
 239         testkey_t* 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_t* ref[])
 248 {
 249         int num = random() % HASHTESTMAX;
 250         testkey_t* 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_t* ref[])
 259 {
 260         int num = random() % HASHTESTMAX;
 261         testkey_t* key = newkey(num);
 262         struct lruhash_entry* en = lruhash_lookup(table, myhash(num), key, 0);
 263         testdata_t* data = en? (testdata_t*)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_t** ref)
 314 {
 315         int numtoadd = random() % (HASHTESTMAX * 10);
 316         testdata_t* data = newdata(numtoadd);
 317         testkey_t* 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_t** ref)
 327 {
 328         int num = random() % (HASHTESTMAX*10);
 329         testkey_t* 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_t** ref)
 339 {
 340         int num = random() % (HASHTESTMAX*10);
 341         testkey_t* key = newkey(num);
 342         struct lruhash_entry* en = lruhash_lookup(table, myhash(num), key, 0);
 343         testdata_t* data = en? (testdata_t*)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 hastable, this check will work */
 363         testdata_t* 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_t 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 }