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 */ 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_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 */ 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 */ 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 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 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 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 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 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_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 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 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 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* 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 } 377