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