unbound/testcode/unitslabhash.c

   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_t;
  48 /** use this type for the slabhash test data */
  49 typedef struct slabhash_testdata testdata_t;
  50
  51 /** delete key */
  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 */
  56 static hashvalue_t myhash(int id) {
  57         hashvalue_t h = (hashvalue_t)id & 0x0f;
  58         h |= (h << 28);
  59         return h;
  60 }
  61
  62 /** allocate new key, fill in hash */
  63 static testkey_t* newkey(int id) {
  64         testkey_t* k = (testkey_t*)calloc(1, sizeof(testkey_t));
  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 */
  73 static testdata_t* newdata(int val) {
  74         testdata_t* d = (testdata_t*)calloc(1,
  75                 sizeof(testdata_t));
  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
  83 test_short_table(struct slabhash* table)
  84 {
  85         testkey_t* k = newkey(12);
  86         testkey_t* k2 = newkey(14);
  87         testdata_t* d = newdata(128);
  88         testdata_t* 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
 109 testadd(struct slabhash* table, testdata_t* ref[])
 110 {
 111         int numtoadd = random() % HASHTESTMAX;
 112         testdata_t* data = newdata(numtoadd);
 113         testkey_t* 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
 121 testremove(struct slabhash* table, testdata_t* ref[])
 122 {
 123         int num = random() % HASHTESTMAX;
 124         testkey_t* 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
 132 testlookup(struct slabhash* table, testdata_t* ref[])
 133 {
 134         int num = random() % HASHTESTMAX;
 135         testkey_t* key = newkey(num);
 136         struct lruhash_entry* en = slabhash_lookup(table, myhash(num), key, 0);
 137         testdata_t* data = en? (testdata_t*)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
 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
 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
 196 testadd_unlim(struct slabhash* table, testdata_t** ref)
 197 {
 198         int numtoadd = random() % (HASHTESTMAX * 10);
 199         testdata_t* data = newdata(numtoadd);
 200         testkey_t* 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
 209 testremove_unlim(struct slabhash* table, testdata_t** ref)
 210 {
 211         int num = random() % (HASHTESTMAX*10);
 212         testkey_t* 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
 221 testlookup_unlim(struct slabhash* table, testdata_t** ref)
 222 {
 223         int num = random() % (HASHTESTMAX*10);
 224         testkey_t* key = newkey(num);
 225         struct lruhash_entry* en = slabhash_lookup(table, myhash(num), key, 0);
 226         testdata_t* data = en? (testdata_t*)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
 243 test_long_table(struct slabhash* table)
 244 {
 245         /* assuming it all fits in the hastable, this check will work */
 246         testdata_t* 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_t id;
 305         /** hash table */
 306         struct slabhash* table;
 307 };
 308
 309 /** main routine for threaded hash table test */
 310 static void*
 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
 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
 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 }