xref: /freebsd/contrib/jemalloc/src/ckh.c (revision 63d1fd5970ec814904aa0f4580b10a0d302d08b2)
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_internal.h"
39 
40 /******************************************************************************/
41 /* Function prototypes for non-inline static functions. */
42 
43 static bool	ckh_grow(tsd_t *tsd, ckh_t *ckh);
44 static void	ckh_shrink(tsd_t *tsd, ckh_t *ckh);
45 
46 /******************************************************************************/
47 
48 /*
49  * Search bucket for key and return the cell number if found; SIZE_T_MAX
50  * otherwise.
51  */
52 JEMALLOC_INLINE_C size_t
53 ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key)
54 {
55 	ckhc_t *cell;
56 	unsigned i;
57 
58 	for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) {
59 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
60 		if (cell->key != NULL && ckh->keycomp(key, cell->key))
61 			return ((bucket << LG_CKH_BUCKET_CELLS) + i);
62 	}
63 
64 	return (SIZE_T_MAX);
65 }
66 
67 /*
68  * Search table for key and return cell number if found; SIZE_T_MAX otherwise.
69  */
70 JEMALLOC_INLINE_C size_t
71 ckh_isearch(ckh_t *ckh, const void *key)
72 {
73 	size_t hashes[2], bucket, cell;
74 
75 	assert(ckh != NULL);
76 
77 	ckh->hash(key, hashes);
78 
79 	/* Search primary bucket. */
80 	bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
81 	cell = ckh_bucket_search(ckh, bucket, key);
82 	if (cell != SIZE_T_MAX)
83 		return (cell);
84 
85 	/* Search secondary bucket. */
86 	bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
87 	cell = ckh_bucket_search(ckh, bucket, key);
88 	return (cell);
89 }
90 
91 JEMALLOC_INLINE_C bool
92 ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key,
93     const void *data)
94 {
95 	ckhc_t *cell;
96 	unsigned offset, i;
97 
98 	/*
99 	 * Cycle through the cells in the bucket, starting at a random position.
100 	 * The randomness avoids worst-case search overhead as buckets fill up.
101 	 */
102 	offset = (unsigned)prng_lg_range_u64(&ckh->prng_state,
103 	    LG_CKH_BUCKET_CELLS);
104 	for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) {
105 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) +
106 		    ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))];
107 		if (cell->key == NULL) {
108 			cell->key = key;
109 			cell->data = data;
110 			ckh->count++;
111 			return (false);
112 		}
113 	}
114 
115 	return (true);
116 }
117 
118 /*
119  * No space is available in bucket.  Randomly evict an item, then try to find an
120  * alternate location for that item.  Iteratively repeat this
121  * eviction/relocation procedure until either success or detection of an
122  * eviction/relocation bucket cycle.
123  */
124 JEMALLOC_INLINE_C bool
125 ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey,
126     void const **argdata)
127 {
128 	const void *key, *data, *tkey, *tdata;
129 	ckhc_t *cell;
130 	size_t hashes[2], bucket, tbucket;
131 	unsigned i;
132 
133 	bucket = argbucket;
134 	key = *argkey;
135 	data = *argdata;
136 	while (true) {
137 		/*
138 		 * Choose a random item within the bucket to evict.  This is
139 		 * critical to correct function, because without (eventually)
140 		 * evicting all items within a bucket during iteration, it
141 		 * would be possible to get stuck in an infinite loop if there
142 		 * were an item for which both hashes indicated the same
143 		 * bucket.
144 		 */
145 		i = (unsigned)prng_lg_range_u64(&ckh->prng_state,
146 		    LG_CKH_BUCKET_CELLS);
147 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
148 		assert(cell->key != NULL);
149 
150 		/* Swap cell->{key,data} and {key,data} (evict). */
151 		tkey = cell->key; tdata = cell->data;
152 		cell->key = key; cell->data = data;
153 		key = tkey; data = tdata;
154 
155 #ifdef CKH_COUNT
156 		ckh->nrelocs++;
157 #endif
158 
159 		/* Find the alternate bucket for the evicted item. */
160 		ckh->hash(key, hashes);
161 		tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
162 		if (tbucket == bucket) {
163 			tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets)
164 			    - 1);
165 			/*
166 			 * It may be that (tbucket == bucket) still, if the
167 			 * item's hashes both indicate this bucket.  However,
168 			 * we are guaranteed to eventually escape this bucket
169 			 * during iteration, assuming pseudo-random item
170 			 * selection (true randomness would make infinite
171 			 * looping a remote possibility).  The reason we can
172 			 * never get trapped forever is that there are two
173 			 * cases:
174 			 *
175 			 * 1) This bucket == argbucket, so we will quickly
176 			 *    detect an eviction cycle and terminate.
177 			 * 2) An item was evicted to this bucket from another,
178 			 *    which means that at least one item in this bucket
179 			 *    has hashes that indicate distinct buckets.
180 			 */
181 		}
182 		/* Check for a cycle. */
183 		if (tbucket == argbucket) {
184 			*argkey = key;
185 			*argdata = data;
186 			return (true);
187 		}
188 
189 		bucket = tbucket;
190 		if (!ckh_try_bucket_insert(ckh, bucket, key, data))
191 			return (false);
192 	}
193 }
194 
195 JEMALLOC_INLINE_C bool
196 ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata)
197 {
198 	size_t hashes[2], bucket;
199 	const void *key = *argkey;
200 	const void *data = *argdata;
201 
202 	ckh->hash(key, hashes);
203 
204 	/* Try to insert in primary bucket. */
205 	bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
206 	if (!ckh_try_bucket_insert(ckh, bucket, key, data))
207 		return (false);
208 
209 	/* Try to insert in secondary bucket. */
210 	bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
211 	if (!ckh_try_bucket_insert(ckh, bucket, key, data))
212 		return (false);
213 
214 	/*
215 	 * Try to find a place for this item via iterative eviction/relocation.
216 	 */
217 	return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata));
218 }
219 
220 /*
221  * Try to rebuild the hash table from scratch by inserting all items from the
222  * old table into the new.
223  */
224 JEMALLOC_INLINE_C bool
225 ckh_rebuild(ckh_t *ckh, ckhc_t *aTab)
226 {
227 	size_t count, i, nins;
228 	const void *key, *data;
229 
230 	count = ckh->count;
231 	ckh->count = 0;
232 	for (i = nins = 0; nins < count; i++) {
233 		if (aTab[i].key != NULL) {
234 			key = aTab[i].key;
235 			data = aTab[i].data;
236 			if (ckh_try_insert(ckh, &key, &data)) {
237 				ckh->count = count;
238 				return (true);
239 			}
240 			nins++;
241 		}
242 	}
243 
244 	return (false);
245 }
246 
247 static bool
248 ckh_grow(tsd_t *tsd, ckh_t *ckh)
249 {
250 	bool ret;
251 	ckhc_t *tab, *ttab;
252 	unsigned lg_prevbuckets, lg_curcells;
253 
254 #ifdef CKH_COUNT
255 	ckh->ngrows++;
256 #endif
257 
258 	/*
259 	 * It is possible (though unlikely, given well behaved hashes) that the
260 	 * table will have to be doubled more than once in order to create a
261 	 * usable table.
262 	 */
263 	lg_prevbuckets = ckh->lg_curbuckets;
264 	lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS;
265 	while (true) {
266 		size_t usize;
267 
268 		lg_curcells++;
269 		usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE);
270 		if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) {
271 			ret = true;
272 			goto label_return;
273 		}
274 		tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE,
275 		    true, NULL, true, arena_ichoose(tsd, NULL));
276 		if (tab == NULL) {
277 			ret = true;
278 			goto label_return;
279 		}
280 		/* Swap in new table. */
281 		ttab = ckh->tab;
282 		ckh->tab = tab;
283 		tab = ttab;
284 		ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;
285 
286 		if (!ckh_rebuild(ckh, tab)) {
287 			idalloctm(tsd_tsdn(tsd), tab, NULL, true, true);
288 			break;
289 		}
290 
291 		/* Rebuilding failed, so back out partially rebuilt table. */
292 		idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true);
293 		ckh->tab = tab;
294 		ckh->lg_curbuckets = lg_prevbuckets;
295 	}
296 
297 	ret = false;
298 label_return:
299 	return (ret);
300 }
301 
302 static void
303 ckh_shrink(tsd_t *tsd, ckh_t *ckh)
304 {
305 	ckhc_t *tab, *ttab;
306 	size_t usize;
307 	unsigned lg_prevbuckets, lg_curcells;
308 
309 	/*
310 	 * It is possible (though unlikely, given well behaved hashes) that the
311 	 * table rebuild will fail.
312 	 */
313 	lg_prevbuckets = ckh->lg_curbuckets;
314 	lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1;
315 	usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE);
316 	if (unlikely(usize == 0 || usize > HUGE_MAXCLASS))
317 		return;
318 	tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, NULL,
319 	    true, arena_ichoose(tsd, NULL));
320 	if (tab == NULL) {
321 		/*
322 		 * An OOM error isn't worth propagating, since it doesn't
323 		 * prevent this or future operations from proceeding.
324 		 */
325 		return;
326 	}
327 	/* Swap in new table. */
328 	ttab = ckh->tab;
329 	ckh->tab = tab;
330 	tab = ttab;
331 	ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;
332 
333 	if (!ckh_rebuild(ckh, tab)) {
334 		idalloctm(tsd_tsdn(tsd), tab, NULL, true, true);
335 #ifdef CKH_COUNT
336 		ckh->nshrinks++;
337 #endif
338 		return;
339 	}
340 
341 	/* Rebuilding failed, so back out partially rebuilt table. */
342 	idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true);
343 	ckh->tab = tab;
344 	ckh->lg_curbuckets = lg_prevbuckets;
345 #ifdef CKH_COUNT
346 	ckh->nshrinkfails++;
347 #endif
348 }
349 
350 bool
351 ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
352     ckh_keycomp_t *keycomp)
353 {
354 	bool ret;
355 	size_t mincells, usize;
356 	unsigned lg_mincells;
357 
358 	assert(minitems > 0);
359 	assert(hash != NULL);
360 	assert(keycomp != NULL);
361 
362 #ifdef CKH_COUNT
363 	ckh->ngrows = 0;
364 	ckh->nshrinks = 0;
365 	ckh->nshrinkfails = 0;
366 	ckh->ninserts = 0;
367 	ckh->nrelocs = 0;
368 #endif
369 	ckh->prng_state = 42; /* Value doesn't really matter. */
370 	ckh->count = 0;
371 
372 	/*
373 	 * Find the minimum power of 2 that is large enough to fit minitems
374 	 * entries.  We are using (2+,2) cuckoo hashing, which has an expected
375 	 * maximum load factor of at least ~0.86, so 0.75 is a conservative load
376 	 * factor that will typically allow mincells items to fit without ever
377 	 * growing the table.
378 	 */
379 	assert(LG_CKH_BUCKET_CELLS > 0);
380 	mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2;
381 	for (lg_mincells = LG_CKH_BUCKET_CELLS;
382 	    (ZU(1) << lg_mincells) < mincells;
383 	    lg_mincells++)
384 		; /* Do nothing. */
385 	ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;
386 	ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;
387 	ckh->hash = hash;
388 	ckh->keycomp = keycomp;
389 
390 	usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE);
391 	if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) {
392 		ret = true;
393 		goto label_return;
394 	}
395 	ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true,
396 	    NULL, true, arena_ichoose(tsd, NULL));
397 	if (ckh->tab == NULL) {
398 		ret = true;
399 		goto label_return;
400 	}
401 
402 	ret = false;
403 label_return:
404 	return (ret);
405 }
406 
407 void
408 ckh_delete(tsd_t *tsd, ckh_t *ckh)
409 {
410 
411 	assert(ckh != NULL);
412 
413 #ifdef CKH_VERBOSE
414 	malloc_printf(
415 	    "%s(%p): ngrows: %"FMTu64", nshrinks: %"FMTu64","
416 	    " nshrinkfails: %"FMTu64", ninserts: %"FMTu64","
417 	    " nrelocs: %"FMTu64"\n", __func__, ckh,
418 	    (unsigned long long)ckh->ngrows,
419 	    (unsigned long long)ckh->nshrinks,
420 	    (unsigned long long)ckh->nshrinkfails,
421 	    (unsigned long long)ckh->ninserts,
422 	    (unsigned long long)ckh->nrelocs);
423 #endif
424 
425 	idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true);
426 	if (config_debug)
427 		memset(ckh, JEMALLOC_FREE_JUNK, sizeof(ckh_t));
428 }
429 
430 size_t
431 ckh_count(ckh_t *ckh)
432 {
433 
434 	assert(ckh != NULL);
435 
436 	return (ckh->count);
437 }
438 
439 bool
440 ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data)
441 {
442 	size_t i, ncells;
443 
444 	for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets +
445 	    LG_CKH_BUCKET_CELLS)); i < ncells; i++) {
446 		if (ckh->tab[i].key != NULL) {
447 			if (key != NULL)
448 				*key = (void *)ckh->tab[i].key;
449 			if (data != NULL)
450 				*data = (void *)ckh->tab[i].data;
451 			*tabind = i + 1;
452 			return (false);
453 		}
454 	}
455 
456 	return (true);
457 }
458 
459 bool
460 ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data)
461 {
462 	bool ret;
463 
464 	assert(ckh != NULL);
465 	assert(ckh_search(ckh, key, NULL, NULL));
466 
467 #ifdef CKH_COUNT
468 	ckh->ninserts++;
469 #endif
470 
471 	while (ckh_try_insert(ckh, &key, &data)) {
472 		if (ckh_grow(tsd, ckh)) {
473 			ret = true;
474 			goto label_return;
475 		}
476 	}
477 
478 	ret = false;
479 label_return:
480 	return (ret);
481 }
482 
483 bool
484 ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key,
485     void **data)
486 {
487 	size_t cell;
488 
489 	assert(ckh != NULL);
490 
491 	cell = ckh_isearch(ckh, searchkey);
492 	if (cell != SIZE_T_MAX) {
493 		if (key != NULL)
494 			*key = (void *)ckh->tab[cell].key;
495 		if (data != NULL)
496 			*data = (void *)ckh->tab[cell].data;
497 		ckh->tab[cell].key = NULL;
498 		ckh->tab[cell].data = NULL; /* Not necessary. */
499 
500 		ckh->count--;
501 		/* Try to halve the table if it is less than 1/4 full. */
502 		if (ckh->count < (ZU(1) << (ckh->lg_curbuckets
503 		    + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets
504 		    > ckh->lg_minbuckets) {
505 			/* Ignore error due to OOM. */
506 			ckh_shrink(tsd, ckh);
507 		}
508 
509 		return (false);
510 	}
511 
512 	return (true);
513 }
514 
515 bool
516 ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data)
517 {
518 	size_t cell;
519 
520 	assert(ckh != NULL);
521 
522 	cell = ckh_isearch(ckh, searchkey);
523 	if (cell != SIZE_T_MAX) {
524 		if (key != NULL)
525 			*key = (void *)ckh->tab[cell].key;
526 		if (data != NULL)
527 			*data = (void *)ckh->tab[cell].data;
528 		return (false);
529 	}
530 
531 	return (true);
532 }
533 
534 void
535 ckh_string_hash(const void *key, size_t r_hash[2])
536 {
537 
538 	hash(key, strlen((const char *)key), 0x94122f33U, r_hash);
539 }
540 
541 bool
542 ckh_string_keycomp(const void *k1, const void *k2)
543 {
544 
545     assert(k1 != NULL);
546     assert(k2 != NULL);
547 
548     return (strcmp((char *)k1, (char *)k2) ? false : true);
549 }
550 
551 void
552 ckh_pointer_hash(const void *key, size_t r_hash[2])
553 {
554 	union {
555 		const void	*v;
556 		size_t		i;
557 	} u;
558 
559 	assert(sizeof(u.v) == sizeof(u.i));
560 	u.v = key;
561 	hash(&u.i, sizeof(u.i), 0xd983396eU, r_hash);
562 }
563 
564 bool
565 ckh_pointer_keycomp(const void *k1, const void *k2)
566 {
567 
568 	return ((k1 == k2) ? true : false);
569 }
570