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