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 43 static bool ckh_grow(tsd_t *tsd, ckh_t *ckh); 44 static void ckh_shrink(tsd_t *tsd, 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 */ 52 JEMALLOC_INLINE_C size_t 53 ckh_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 */ 70 JEMALLOC_INLINE_C size_t 71 ckh_isearch(ckh_t *ckh, const void *key) 72 { 73 size_t hashes[2], bucket, cell; 74 75 assert(ckh != NULL); 76 77 ckh->hash(key, hashes); 78 79 /* Search primary bucket. */ 80 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); 81 cell = ckh_bucket_search(ckh, bucket, key); 82 if (cell != SIZE_T_MAX) 83 return (cell); 84 85 /* Search secondary bucket. */ 86 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 87 cell = ckh_bucket_search(ckh, bucket, key); 88 return (cell); 89 } 90 91 JEMALLOC_INLINE_C bool 92 ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, 93 const void *data) 94 { 95 ckhc_t *cell; 96 unsigned offset, i; 97 98 /* 99 * Cycle through the cells in the bucket, starting at a random position. 100 * The randomness avoids worst-case search overhead as buckets fill up. 101 */ 102 offset = (unsigned)prng_lg_range_u64(&ckh->prng_state, 103 LG_CKH_BUCKET_CELLS); 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 */ 124 JEMALLOC_INLINE_C bool 125 ckh_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 hashes[2], 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 i = (unsigned)prng_lg_range_u64(&ckh->prng_state, 146 LG_CKH_BUCKET_CELLS); 147 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 148 assert(cell->key != NULL); 149 150 /* Swap cell->{key,data} and {key,data} (evict). */ 151 tkey = cell->key; tdata = cell->data; 152 cell->key = key; cell->data = data; 153 key = tkey; data = tdata; 154 155 #ifdef CKH_COUNT 156 ckh->nrelocs++; 157 #endif 158 159 /* Find the alternate bucket for the evicted item. */ 160 ckh->hash(key, hashes); 161 tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 162 if (tbucket == bucket) { 163 tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) 164 - 1); 165 /* 166 * It may be that (tbucket == bucket) still, if the 167 * item's hashes both indicate this bucket. However, 168 * we are guaranteed to eventually escape this bucket 169 * during iteration, assuming pseudo-random item 170 * selection (true randomness would make infinite 171 * looping a remote possibility). The reason we can 172 * never get trapped forever is that there are two 173 * cases: 174 * 175 * 1) This bucket == argbucket, so we will quickly 176 * detect an eviction cycle and terminate. 177 * 2) An item was evicted to this bucket from another, 178 * which means that at least one item in this bucket 179 * has hashes that indicate distinct buckets. 180 */ 181 } 182 /* Check for a cycle. */ 183 if (tbucket == argbucket) { 184 *argkey = key; 185 *argdata = data; 186 return (true); 187 } 188 189 bucket = tbucket; 190 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) 191 return (false); 192 } 193 } 194 195 JEMALLOC_INLINE_C bool 196 ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) 197 { 198 size_t hashes[2], bucket; 199 const void *key = *argkey; 200 const void *data = *argdata; 201 202 ckh->hash(key, hashes); 203 204 /* Try to insert in primary bucket. */ 205 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); 206 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) 207 return (false); 208 209 /* Try to insert in secondary bucket. */ 210 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 211 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) 212 return (false); 213 214 /* 215 * Try to find a place for this item via iterative eviction/relocation. 216 */ 217 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); 218 } 219 220 /* 221 * Try to rebuild the hash table from scratch by inserting all items from the 222 * old table into the new. 223 */ 224 JEMALLOC_INLINE_C bool 225 ckh_rebuild(ckh_t *ckh, ckhc_t *aTab) 226 { 227 size_t count, i, nins; 228 const void *key, *data; 229 230 count = ckh->count; 231 ckh->count = 0; 232 for (i = nins = 0; nins < count; i++) { 233 if (aTab[i].key != NULL) { 234 key = aTab[i].key; 235 data = aTab[i].data; 236 if (ckh_try_insert(ckh, &key, &data)) { 237 ckh->count = count; 238 return (true); 239 } 240 nins++; 241 } 242 } 243 244 return (false); 245 } 246 247 static bool 248 ckh_grow(tsd_t *tsd, ckh_t *ckh) 249 { 250 bool ret; 251 ckhc_t *tab, *ttab; 252 unsigned lg_prevbuckets, lg_curcells; 253 254 #ifdef CKH_COUNT 255 ckh->ngrows++; 256 #endif 257 258 /* 259 * It is possible (though unlikely, given well behaved hashes) that the 260 * table will have to be doubled more than once in order to create a 261 * usable table. 262 */ 263 lg_prevbuckets = ckh->lg_curbuckets; 264 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; 265 while (true) { 266 size_t usize; 267 268 lg_curcells++; 269 usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 270 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) { 271 ret = true; 272 goto label_return; 273 } 274 tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, 275 true, NULL, true, arena_ichoose(tsd, NULL)); 276 if (tab == NULL) { 277 ret = true; 278 goto label_return; 279 } 280 /* Swap in new table. */ 281 ttab = ckh->tab; 282 ckh->tab = tab; 283 tab = ttab; 284 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 285 286 if (!ckh_rebuild(ckh, tab)) { 287 idalloctm(tsd_tsdn(tsd), tab, NULL, true, true); 288 break; 289 } 290 291 /* Rebuilding failed, so back out partially rebuilt table. */ 292 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); 293 ckh->tab = tab; 294 ckh->lg_curbuckets = lg_prevbuckets; 295 } 296 297 ret = false; 298 label_return: 299 return (ret); 300 } 301 302 static void 303 ckh_shrink(tsd_t *tsd, ckh_t *ckh) 304 { 305 ckhc_t *tab, *ttab; 306 size_t usize; 307 unsigned lg_prevbuckets, lg_curcells; 308 309 /* 310 * It is possible (though unlikely, given well behaved hashes) that the 311 * table rebuild will fail. 312 */ 313 lg_prevbuckets = ckh->lg_curbuckets; 314 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; 315 usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 316 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) 317 return; 318 tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, NULL, 319 true, arena_ichoose(tsd, NULL)); 320 if (tab == NULL) { 321 /* 322 * An OOM error isn't worth propagating, since it doesn't 323 * prevent this or future operations from proceeding. 324 */ 325 return; 326 } 327 /* Swap in new table. */ 328 ttab = ckh->tab; 329 ckh->tab = tab; 330 tab = ttab; 331 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 332 333 if (!ckh_rebuild(ckh, tab)) { 334 idalloctm(tsd_tsdn(tsd), tab, NULL, true, true); 335 #ifdef CKH_COUNT 336 ckh->nshrinks++; 337 #endif 338 return; 339 } 340 341 /* Rebuilding failed, so back out partially rebuilt table. */ 342 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); 343 ckh->tab = tab; 344 ckh->lg_curbuckets = lg_prevbuckets; 345 #ifdef CKH_COUNT 346 ckh->nshrinkfails++; 347 #endif 348 } 349 350 bool 351 ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, 352 ckh_keycomp_t *keycomp) 353 { 354 bool ret; 355 size_t mincells, usize; 356 unsigned lg_mincells; 357 358 assert(minitems > 0); 359 assert(hash != NULL); 360 assert(keycomp != NULL); 361 362 #ifdef CKH_COUNT 363 ckh->ngrows = 0; 364 ckh->nshrinks = 0; 365 ckh->nshrinkfails = 0; 366 ckh->ninserts = 0; 367 ckh->nrelocs = 0; 368 #endif 369 ckh->prng_state = 42; /* Value doesn't really matter. */ 370 ckh->count = 0; 371 372 /* 373 * Find the minimum power of 2 that is large enough to fit minitems 374 * entries. We are using (2+,2) cuckoo hashing, which has an expected 375 * maximum load factor of at least ~0.86, so 0.75 is a conservative load 376 * factor that will typically allow mincells items to fit without ever 377 * growing the table. 378 */ 379 assert(LG_CKH_BUCKET_CELLS > 0); 380 mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; 381 for (lg_mincells = LG_CKH_BUCKET_CELLS; 382 (ZU(1) << lg_mincells) < mincells; 383 lg_mincells++) 384 ; /* Do nothing. */ 385 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 386 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 387 ckh->hash = hash; 388 ckh->keycomp = keycomp; 389 390 usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE); 391 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) { 392 ret = true; 393 goto label_return; 394 } 395 ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, 396 NULL, true, arena_ichoose(tsd, NULL)); 397 if (ckh->tab == NULL) { 398 ret = true; 399 goto label_return; 400 } 401 402 ret = false; 403 label_return: 404 return (ret); 405 } 406 407 void 408 ckh_delete(tsd_t *tsd, ckh_t *ckh) 409 { 410 411 assert(ckh != NULL); 412 413 #ifdef CKH_VERBOSE 414 malloc_printf( 415 "%s(%p): ngrows: %"FMTu64", nshrinks: %"FMTu64"," 416 " nshrinkfails: %"FMTu64", ninserts: %"FMTu64"," 417 " nrelocs: %"FMTu64"\n", __func__, ckh, 418 (unsigned long long)ckh->ngrows, 419 (unsigned long long)ckh->nshrinks, 420 (unsigned long long)ckh->nshrinkfails, 421 (unsigned long long)ckh->ninserts, 422 (unsigned long long)ckh->nrelocs); 423 #endif 424 425 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); 426 if (config_debug) 427 memset(ckh, JEMALLOC_FREE_JUNK, sizeof(ckh_t)); 428 } 429 430 size_t 431 ckh_count(ckh_t *ckh) 432 { 433 434 assert(ckh != NULL); 435 436 return (ckh->count); 437 } 438 439 bool 440 ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) 441 { 442 size_t i, ncells; 443 444 for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + 445 LG_CKH_BUCKET_CELLS)); i < ncells; i++) { 446 if (ckh->tab[i].key != NULL) { 447 if (key != NULL) 448 *key = (void *)ckh->tab[i].key; 449 if (data != NULL) 450 *data = (void *)ckh->tab[i].data; 451 *tabind = i + 1; 452 return (false); 453 } 454 } 455 456 return (true); 457 } 458 459 bool 460 ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data) 461 { 462 bool ret; 463 464 assert(ckh != NULL); 465 assert(ckh_search(ckh, key, NULL, NULL)); 466 467 #ifdef CKH_COUNT 468 ckh->ninserts++; 469 #endif 470 471 while (ckh_try_insert(ckh, &key, &data)) { 472 if (ckh_grow(tsd, ckh)) { 473 ret = true; 474 goto label_return; 475 } 476 } 477 478 ret = false; 479 label_return: 480 return (ret); 481 } 482 483 bool 484 ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, 485 void **data) 486 { 487 size_t cell; 488 489 assert(ckh != NULL); 490 491 cell = ckh_isearch(ckh, searchkey); 492 if (cell != SIZE_T_MAX) { 493 if (key != NULL) 494 *key = (void *)ckh->tab[cell].key; 495 if (data != NULL) 496 *data = (void *)ckh->tab[cell].data; 497 ckh->tab[cell].key = NULL; 498 ckh->tab[cell].data = NULL; /* Not necessary. */ 499 500 ckh->count--; 501 /* Try to halve the table if it is less than 1/4 full. */ 502 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets 503 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets 504 > ckh->lg_minbuckets) { 505 /* Ignore error due to OOM. */ 506 ckh_shrink(tsd, ckh); 507 } 508 509 return (false); 510 } 511 512 return (true); 513 } 514 515 bool 516 ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) 517 { 518 size_t cell; 519 520 assert(ckh != NULL); 521 522 cell = ckh_isearch(ckh, searchkey); 523 if (cell != SIZE_T_MAX) { 524 if (key != NULL) 525 *key = (void *)ckh->tab[cell].key; 526 if (data != NULL) 527 *data = (void *)ckh->tab[cell].data; 528 return (false); 529 } 530 531 return (true); 532 } 533 534 void 535 ckh_string_hash(const void *key, size_t r_hash[2]) 536 { 537 538 hash(key, strlen((const char *)key), 0x94122f33U, r_hash); 539 } 540 541 bool 542 ckh_string_keycomp(const void *k1, const void *k2) 543 { 544 545 assert(k1 != NULL); 546 assert(k2 != NULL); 547 548 return (strcmp((char *)k1, (char *)k2) ? false : true); 549 } 550 551 void 552 ckh_pointer_hash(const void *key, size_t r_hash[2]) 553 { 554 union { 555 const void *v; 556 size_t i; 557 } u; 558 559 assert(sizeof(u.v) == sizeof(u.i)); 560 u.v = key; 561 hash(&u.i, sizeof(u.i), 0xd983396eU, r_hash); 562 } 563 564 bool 565 ckh_pointer_keycomp(const void *k1, const void *k2) 566 { 567 568 return ((k1 == k2) ? true : false); 569 } 570