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
53static bool ckh_grow(tsd_t *tsd, ckh_t *ckh);
54static 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 */
62static size_t
63ckh_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 */
80static size_t
81ckh_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
101static bool
102ckh_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 */
133static bool
134ckh_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
204static bool
205ckh_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 */
234static bool
235ckh_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
256static bool
257ckh_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;
307label_return:
308 return ret;
309}
310
311static void
312ckh_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
359bool
360ckh_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;
412label_return:
413 return ret;
414}
415
416void
417ckh_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
438size_t
439ckh_count(ckh_t *ckh) {
440 assert(ckh != NULL);
441
442 return ckh->count;
443}
444
445bool
446ckh_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
466bool
467ckh_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;
485label_return:
486 return ret;
487}
488
489bool
490ckh_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
522bool
523ckh_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
542void
543ckh_string_hash(const void *key, size_t r_hash[2]) {
544 hash(key, strlen((const char *)key), 0x94122f33U, r_hash);
545}
546
547bool
548ckh_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
555void
556ckh_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
567bool
568ckh_pointer_keycomp(const void *k1, const void *k2) {
569 return (k1 == k2);
570}
571