ckh.c revision 0657f12acd43eb2082a71230341449eca648bc9b
1/* 2 ******************************************************************************* 3 * Implementation of (2^1+,2) cuckoo hashing, where 2^1+ indicates that each 4 * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash 5 * functions are employed. The original cuckoo hashing algorithm was described 6 * in: 7 * 8 * Pagh, R., F.F. Rodler (2004) Cuckoo Hashing. Journal of Algorithms 9 * 51(2):122-144. 10 * 11 * Generalization of cuckoo hashing was discussed in: 12 * 13 * Erlingsson, U., M. Manasse, F. McSherry (2006) A cool and practical 14 * alternative to traditional hash tables. In Proceedings of the 7th 15 * Workshop on Distributed Data and Structures (WDAS'06), Santa Clara, CA, 16 * January 2006. 17 * 18 * This implementation uses precisely two hash functions because that is the 19 * fewest that can work, and supporting multiple hashes is an implementation 20 * burden. Here is a reproduction of Figure 1 from Erlingsson et al. (2006) 21 * that shows approximate expected maximum load factors for various 22 * configurations: 23 * 24 * | #cells/bucket | 25 * #hashes | 1 | 2 | 4 | 8 | 26 * --------+-------+-------+-------+-------+ 27 * 1 | 0.006 | 0.006 | 0.03 | 0.12 | 28 * 2 | 0.49 | 0.86 |>0.93< |>0.96< | 29 * 3 | 0.91 | 0.97 | 0.98 | 0.999 | 30 * 4 | 0.97 | 0.99 | 0.999 | | 31 * 32 * The number of cells per bucket is chosen such that a bucket fits in one cache 33 * line. So, on 32- and 64-bit systems, we use (8,2) and (4,2) cuckoo hashing, 34 * respectively. 35 * 36 ******************************************************************************/ 37#define JEMALLOC_CKH_C_ 38#include "jemalloc/internal/jemalloc_internal.h" 39 40/******************************************************************************/ 41/* Function prototypes for non-inline static functions. */ 42 43static bool ckh_grow(ckh_t *ckh); 44static void ckh_shrink(ckh_t *ckh); 45 46/******************************************************************************/ 47 48/* 49 * Search bucket for key and return the cell number if found; SIZE_T_MAX 50 * otherwise. 51 */ 52JEMALLOC_INLINE size_t 53ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key) 54{ 55 ckhc_t *cell; 56 unsigned i; 57 58 for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 59 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 60 if (cell->key != NULL && ckh->keycomp(key, cell->key)) 61 return ((bucket << LG_CKH_BUCKET_CELLS) + i); 62 } 63 64 return (SIZE_T_MAX); 65} 66 67/* 68 * Search table for key and return cell number if found; SIZE_T_MAX otherwise. 69 */ 70JEMALLOC_INLINE size_t 71ckh_isearch(ckh_t *ckh, const void *key) 72{ 73 size_t hash1, hash2, bucket, cell; 74 75 assert(ckh != NULL); 76 dassert(ckh->magic == CKH_MAGIC); 77 78 ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 79 80 /* Search primary bucket. */ 81 bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 82 cell = ckh_bucket_search(ckh, bucket, key); 83 if (cell != SIZE_T_MAX) 84 return (cell); 85 86 /* Search secondary bucket. */ 87 bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 88 cell = ckh_bucket_search(ckh, bucket, key); 89 return (cell); 90} 91 92JEMALLOC_INLINE bool 93ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, 94 const void *data) 95{ 96 ckhc_t *cell; 97 unsigned offset, i; 98 99 /* 100 * Cycle through the cells in the bucket, starting at a random position. 101 * The randomness avoids worst-case search overhead as buckets fill up. 102 */ 103 prn32(offset, LG_CKH_BUCKET_CELLS, ckh->prn_state, CKH_A, CKH_C); 104 for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 105 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + 106 ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))]; 107 if (cell->key == NULL) { 108 cell->key = key; 109 cell->data = data; 110 ckh->count++; 111 return (false); 112 } 113 } 114 115 return (true); 116} 117 118/* 119 * No space is available in bucket. Randomly evict an item, then try to find an 120 * alternate location for that item. Iteratively repeat this 121 * eviction/relocation procedure until either success or detection of an 122 * eviction/relocation bucket cycle. 123 */ 124JEMALLOC_INLINE bool 125ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, 126 void const **argdata) 127{ 128 const void *key, *data, *tkey, *tdata; 129 ckhc_t *cell; 130 size_t hash1, hash2, bucket, tbucket; 131 unsigned i; 132 133 bucket = argbucket; 134 key = *argkey; 135 data = *argdata; 136 while (true) { 137 /* 138 * Choose a random item within the bucket to evict. This is 139 * critical to correct function, because without (eventually) 140 * evicting all items within a bucket during iteration, it 141 * would be possible to get stuck in an infinite loop if there 142 * were an item for which both hashes indicated the same 143 * bucket. 144 */ 145 prn32(i, LG_CKH_BUCKET_CELLS, ckh->prn_state, CKH_A, CKH_C); 146 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 147 assert(cell->key != NULL); 148 149 /* Swap cell->{key,data} and {key,data} (evict). */ 150 tkey = cell->key; tdata = cell->data; 151 cell->key = key; cell->data = data; 152 key = tkey; data = tdata; 153 154#ifdef CKH_COUNT 155 ckh->nrelocs++; 156#endif 157 158 /* Find the alternate bucket for the evicted item. */ 159 ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 160 tbucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 161 if (tbucket == bucket) { 162 tbucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 163 /* 164 * It may be that (tbucket == bucket) still, if the 165 * item's hashes both indicate this bucket. However, 166 * we are guaranteed to eventually escape this bucket 167 * during iteration, assuming pseudo-random item 168 * selection (true randomness would make infinite 169 * looping a remote possibility). The reason we can 170 * never get trapped forever is that there are two 171 * cases: 172 * 173 * 1) This bucket == argbucket, so we will quickly 174 * detect an eviction cycle and terminate. 175 * 2) An item was evicted to this bucket from another, 176 * which means that at least one item in this bucket 177 * has hashes that indicate distinct buckets. 178 */ 179 } 180 /* Check for a cycle. */ 181 if (tbucket == argbucket) { 182 *argkey = key; 183 *argdata = data; 184 return (true); 185 } 186 187 bucket = tbucket; 188 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 189 return (false); 190 } 191} 192 193JEMALLOC_INLINE bool 194ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) 195{ 196 size_t hash1, hash2, bucket; 197 const void *key = *argkey; 198 const void *data = *argdata; 199 200 ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 201 202 /* Try to insert in primary bucket. */ 203 bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 204 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 205 return (false); 206 207 /* Try to insert in secondary bucket. */ 208 bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 209 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 210 return (false); 211 212 /* 213 * Try to find a place for this item via iterative eviction/relocation. 214 */ 215 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); 216} 217 218/* 219 * Try to rebuild the hash table from scratch by inserting all items from the 220 * old table into the new. 221 */ 222JEMALLOC_INLINE bool 223ckh_rebuild(ckh_t *ckh, ckhc_t *aTab) 224{ 225 size_t count, i, nins; 226 const void *key, *data; 227 228 count = ckh->count; 229 ckh->count = 0; 230 for (i = nins = 0; nins < count; i++) { 231 if (aTab[i].key != NULL) { 232 key = aTab[i].key; 233 data = aTab[i].data; 234 if (ckh_try_insert(ckh, &key, &data)) { 235 ckh->count = count; 236 return (true); 237 } 238 nins++; 239 } 240 } 241 242 return (false); 243} 244 245static bool 246ckh_grow(ckh_t *ckh) 247{ 248 bool ret; 249 ckhc_t *tab, *ttab; 250 size_t lg_curcells; 251 unsigned lg_prevbuckets; 252 253#ifdef CKH_COUNT 254 ckh->ngrows++; 255#endif 256 257 /* 258 * It is possible (though unlikely, given well behaved hashes) that the 259 * table will have to be doubled more than once in order to create a 260 * usable table. 261 */ 262 lg_prevbuckets = ckh->lg_curbuckets; 263 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; 264 while (true) { 265 lg_curcells++; 266 tab = (ckhc_t *)ipalloc(sizeof(ckhc_t) << lg_curcells, 267 ZU(1) << LG_CACHELINE, true); 268 if (tab == NULL) { 269 ret = true; 270 goto RETURN; 271 } 272 /* Swap in new table. */ 273 ttab = ckh->tab; 274 ckh->tab = tab; 275 tab = ttab; 276 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 277 278 if (ckh_rebuild(ckh, tab) == false) { 279 idalloc(tab); 280 break; 281 } 282 283 /* Rebuilding failed, so back out partially rebuilt table. */ 284 idalloc(ckh->tab); 285 ckh->tab = tab; 286 ckh->lg_curbuckets = lg_prevbuckets; 287 } 288 289 ret = false; 290RETURN: 291 return (ret); 292} 293 294static void 295ckh_shrink(ckh_t *ckh) 296{ 297 ckhc_t *tab, *ttab; 298 size_t lg_curcells; 299 unsigned lg_prevbuckets; 300 301 /* 302 * It is possible (though unlikely, given well behaved hashes) that the 303 * table rebuild will fail. 304 */ 305 lg_prevbuckets = ckh->lg_curbuckets; 306 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; 307 tab = (ckhc_t *)ipalloc(sizeof(ckhc_t) << lg_curcells, 308 ZU(1) << LG_CACHELINE, true); 309 if (tab == NULL) { 310 /* 311 * An OOM error isn't worth propagating, since it doesn't 312 * prevent this or future operations from proceeding. 313 */ 314 return; 315 } 316 /* Swap in new table. */ 317 ttab = ckh->tab; 318 ckh->tab = tab; 319 tab = ttab; 320 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 321 322 if (ckh_rebuild(ckh, tab) == false) { 323 idalloc(tab); 324#ifdef CKH_COUNT 325 ckh->nshrinks++; 326#endif 327 return; 328 } 329 330 /* Rebuilding failed, so back out partially rebuilt table. */ 331 idalloc(ckh->tab); 332 ckh->tab = tab; 333 ckh->lg_curbuckets = lg_prevbuckets; 334#ifdef CKH_COUNT 335 ckh->nshrinkfails++; 336#endif 337} 338 339bool 340ckh_new(ckh_t *ckh, size_t minitems, ckh_hash_t *hash, ckh_keycomp_t *keycomp) 341{ 342 bool ret; 343 size_t mincells; 344 unsigned lg_mincells; 345 346 assert(minitems > 0); 347 assert(hash != NULL); 348 assert(keycomp != NULL); 349 350#ifdef CKH_COUNT 351 ckh->ngrows = 0; 352 ckh->nshrinks = 0; 353 ckh->nshrinkfails = 0; 354 ckh->ninserts = 0; 355 ckh->nrelocs = 0; 356#endif 357 ckh->prn_state = 42; /* Value doesn't really matter. */ 358 ckh->count = 0; 359 360 /* 361 * Find the minimum power of 2 that is large enough to fit aBaseCount 362 * entries. We are using (2+,2) cuckoo hashing, which has an expected 363 * maximum load factor of at least ~0.86, so 0.75 is a conservative load 364 * factor that will typically allow 2^aLgMinItems to fit without ever 365 * growing the table. 366 */ 367 assert(LG_CKH_BUCKET_CELLS > 0); 368 mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; 369 for (lg_mincells = LG_CKH_BUCKET_CELLS; 370 (ZU(1) << lg_mincells) < mincells; 371 lg_mincells++) 372 ; /* Do nothing. */ 373 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 374 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 375 ckh->hash = hash; 376 ckh->keycomp = keycomp; 377 378 ckh->tab = (ckhc_t *)ipalloc(sizeof(ckhc_t) << lg_mincells, 379 (ZU(1) << LG_CACHELINE), true); 380 if (ckh->tab == NULL) { 381 ret = true; 382 goto RETURN; 383 } 384 385#ifdef JEMALLOC_DEBUG 386 ckh->magic = CKH_MAGIC; 387#endif 388 389 ret = false; 390RETURN: 391 return (ret); 392} 393 394void 395ckh_delete(ckh_t *ckh) 396{ 397 398 assert(ckh != NULL); 399 dassert(ckh->magic == CKH_MAGIC); 400 401#ifdef CKH_VERBOSE 402 malloc_printf( 403 "%s(%p): ngrows: %"PRIu64", nshrinks: %"PRIu64"," 404 " nshrinkfails: %"PRIu64", ninserts: %"PRIu64"," 405 " nrelocs: %"PRIu64"\n", __func__, ckh, 406 (unsigned long long)ckh->ngrows, 407 (unsigned long long)ckh->nshrinks, 408 (unsigned long long)ckh->nshrinkfails, 409 (unsigned long long)ckh->ninserts, 410 (unsigned long long)ckh->nrelocs); 411#endif 412 413 idalloc(ckh->tab); 414#ifdef JEMALLOC_DEBUG 415 memset(ckh, 0x5a, sizeof(ckh_t)); 416#endif 417} 418 419size_t 420ckh_count(ckh_t *ckh) 421{ 422 423 assert(ckh != NULL); 424 dassert(ckh->magic == CKH_MAGIC); 425 426 return (ckh->count); 427} 428 429bool 430ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) 431{ 432 size_t i, ncells; 433 434 for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + 435 LG_CKH_BUCKET_CELLS)); i < ncells; i++) { 436 if (ckh->tab[i].key != NULL) { 437 if (key != NULL) 438 *key = (void *)ckh->tab[i].key; 439 if (data != NULL) 440 *data = (void *)ckh->tab[i].data; 441 *tabind = i + 1; 442 return (false); 443 } 444 } 445 446 return (true); 447} 448 449bool 450ckh_insert(ckh_t *ckh, const void *key, const void *data) 451{ 452 bool ret; 453 454 assert(ckh != NULL); 455 dassert(ckh->magic == CKH_MAGIC); 456 assert(ckh_search(ckh, key, NULL, NULL)); 457 458#ifdef CKH_COUNT 459 ckh->ninserts++; 460#endif 461 462 while (ckh_try_insert(ckh, &key, &data)) { 463 if (ckh_grow(ckh)) { 464 ret = true; 465 goto RETURN; 466 } 467 } 468 469 ret = false; 470RETURN: 471 return (ret); 472} 473 474bool 475ckh_remove(ckh_t *ckh, const void *searchkey, void **key, void **data) 476{ 477 size_t cell; 478 479 assert(ckh != NULL); 480 dassert(ckh->magic == CKH_MAGIC); 481 482 cell = ckh_isearch(ckh, searchkey); 483 if (cell != SIZE_T_MAX) { 484 if (key != NULL) 485 *key = (void *)ckh->tab[cell].key; 486 if (data != NULL) 487 *data = (void *)ckh->tab[cell].data; 488 ckh->tab[cell].key = NULL; 489 ckh->tab[cell].data = NULL; /* Not necessary. */ 490 491 ckh->count--; 492 /* Try to halve the table if it is less than 1/4 full. */ 493 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets 494 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets 495 > ckh->lg_minbuckets) { 496 /* Ignore error due to OOM. */ 497 ckh_shrink(ckh); 498 } 499 500 return (false); 501 } 502 503 return (true); 504} 505 506bool 507ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) 508{ 509 size_t cell; 510 511 assert(ckh != NULL); 512 dassert(ckh->magic == CKH_MAGIC); 513 514 cell = ckh_isearch(ckh, searchkey); 515 if (cell != SIZE_T_MAX) { 516 if (key != NULL) 517 *key = (void *)ckh->tab[cell].key; 518 if (data != NULL) 519 *data = (void *)ckh->tab[cell].data; 520 return (false); 521 } 522 523 return (true); 524} 525 526void 527ckh_string_hash(const void *key, unsigned minbits, size_t *hash1, size_t *hash2) 528{ 529 size_t ret1, ret2; 530 uint64_t h; 531 532 assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64)); 533 assert(hash1 != NULL); 534 assert(hash2 != NULL); 535 536 h = hash(key, strlen((const char *)key), 0x94122f335b332aeaLLU); 537 if (minbits <= 32) { 538 /* 539 * Avoid doing multiple hashes, since a single hash provides 540 * enough bits. 541 */ 542 ret1 = h & ZU(0xffffffffU); 543 ret2 = h >> 32; 544 } else { 545 ret1 = h; 546 ret2 = hash(key, strlen((const char *)key), 547 0x8432a476666bbc13U); 548 } 549 550 *hash1 = ret1; 551 *hash2 = ret2; 552} 553 554bool 555ckh_string_keycomp(const void *k1, const void *k2) 556{ 557 558 assert(k1 != NULL); 559 assert(k2 != NULL); 560 561 return (strcmp((char *)k1, (char *)k2) ? false : true); 562} 563 564void 565ckh_pointer_hash(const void *key, unsigned minbits, size_t *hash1, 566 size_t *hash2) 567{ 568 size_t ret1, ret2; 569 uint64_t h; 570 union { 571 const void *v; 572 uint64_t i; 573 } u; 574 575 assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64)); 576 assert(hash1 != NULL); 577 assert(hash2 != NULL); 578 579 assert(sizeof(u.v) == sizeof(u.i)); 580#if (LG_SIZEOF_PTR != LG_SIZEOF_INT) 581 u.i = 0; 582#endif 583 u.v = key; 584 h = hash(&u.i, sizeof(u.i), 0xd983396e68886082LLU); 585 if (minbits <= 32) { 586 /* 587 * Avoid doing multiple hashes, since a single hash provides 588 * enough bits. 589 */ 590 ret1 = h & ZU(0xffffffffU); 591 ret2 = h >> 32; 592 } else { 593 assert(SIZEOF_PTR == 8); 594 ret1 = h; 595 ret2 = hash(&u.i, sizeof(u.i), 0x5e2be9aff8709a5dLLU); 596 } 597 598 *hash1 = ret1; 599 *hash2 = ret2; 600} 601 602bool 603ckh_pointer_keycomp(const void *k1, const void *k2) 604{ 605 606 return ((k1 == k2) ? true : false); 607} 608