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 || 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;
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 > 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 *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;
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