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 || usize > 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 > 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 *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(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 = hash;
 396         ckh->keycomp = keycomp;
 397
 398         usize = sz_sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE);
 399         if (unlikely(usize == 0 || usize > 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 }