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
52static bool ckh_grow(tsd_t *tsd, ckh_t *ckh);
53static 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 */
61static size_t
62ckh_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 */
79static size_t
80ckh_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
100static bool
101ckh_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 */
132static bool
133ckh_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
203static bool
204ckh_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 */
233static bool
234ckh_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
255static bool
256ckh_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;
306label_return:
307 return ret;
308}
309
310static void
311ckh_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
358bool
359ckh_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;
411label_return:
412 return ret;
413}
414
415void
416ckh_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
437size_t
438ckh_count(ckh_t *ckh) {
439 assert(ckh != NULL);
440
441 return ckh->count;
442}
443
444bool
445ckh_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
465bool
466ckh_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;
484label_return:
485 return ret;
486}
487
488bool
489ckh_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
521bool
522ckh_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
541void
542ckh_string_hash(const void *key, size_t r_hash[2]) {
543 hash(key, strlen((const char *)key), 0x94122f33U, r_hash);
544}
545
546bool
547ckh_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
554void
555ckh_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
566bool
567ckh_pointer_keycomp(const void *k1, const void *k2) {
568 return (k1 == k2);
569}
570