contrib/jemalloc/src/ckh.c

   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 }