2 * Copyright (c) 2017 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
17 * cuckoo hash implementation based on paper
18 * 'Algorithmic Improvements for Fast Concurrent Cuckoo Hashing'
19 * by Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman
20 * and their libcuckoo implementation (https://github.com/efficient/libcuckoo)
23 #include <vppinfra/vec.h>
25 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
26 CVT (clib_cuckoo_kv) * search_v,
27 CVT (clib_cuckoo_kv) * return_v)
29 CVT (clib_cuckoo_kv) tmp = *search_v;
30 int rv = CV (clib_cuckoo_search_inline) (h, &tmp);
31 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
39 CVT (clib_cuckoo_bucket) *
40 CV (clib_cuckoo_bucket_at_index) (CVT (clib_cuckoo) * h, uword bucket)
42 return vec_elt_at_index (h->buckets, bucket);
45 static uword CV (clib_cuckoo_get_nbuckets) (CVT (clib_cuckoo) * h)
47 return vec_len (h->buckets);
51 CV (clib_cuckoo_elt_in_bucket_to_offset) (CVT (clib_cuckoo_bucket) * b,
52 CVT (clib_cuckoo_kv) * e)
54 ASSERT (e >= b->elts);
55 ASSERT (e <= &b->elts[sizeof (b->elts) / sizeof (b->elts[0]) - 1]);
59 u8 *CV (format_cuckoo_elt) (u8 * s, va_list * args)
61 CVT (clib_cuckoo_kv) * elt = va_arg (*args, CVT (clib_cuckoo_kv) *);
62 unsigned reduced_hash = va_arg (*args, unsigned);
63 if (CV (clib_cuckoo_kv_is_free) (elt))
65 s = format (s, "[ -- empty -- ]");
69 s = format (s, "[%U, reduced hash: %u]", CV (format_cuckoo_kvp), elt,
75 u8 *CV (format_cuckoo_bucket) (u8 * s, va_list * args)
77 CVT (clib_cuckoo_bucket) * bucket =
78 va_arg (*args, CVT (clib_cuckoo_bucket) *);
82 clib_cuckoo_bucket_foreach_idx (i)
84 CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
85 s = format (s, "bucket %p, offset %d: %U\n", bucket, i,
86 CV (format_cuckoo_elt), elt, bucket->reduced_hashes[i]);
89 clib_cuckoo_bucket_aux_t aux = bucket->aux;
90 s = format (s, "version: %lld, use count: %d\n",
91 clib_cuckoo_bucket_aux_get_version (aux),
92 clib_cuckoo_bucket_aux_get_use_count (aux));
97 static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
99 CVT (clib_cuckoo_bucket) * bucket;
100 uword bucket_idx = 0;
102 clib_cuckoo_foreach_bucket (bucket, h, {
105 clib_cuckoo_bucket_foreach_idx (i)
107 CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
108 if (!CV (clib_cuckoo_kv_is_free) (elt))
110 u64 hash = CV (clib_cuckoo_hash) (elt);
111 clib_cuckoo_lookup_info_t lookup =
112 CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
113 CVT (clib_cuckoo_kv) kv = *elt;
114 int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
115 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
117 CLIB_CUCKOO_DBG ("Search for elt `%U' failed!",
118 CV (format_cuckoo_elt), elt,
119 bucket->reduced_hashes[i]);
120 CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
122 ASSERT (lookup.bucket1 == bucket_idx || lookup.bucket2 == bucket_idx);
123 ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
127 clib_cuckoo_bucket_aux_t aux = bucket->aux;
128 ASSERT (used == clib_cuckoo_bucket_aux_get_use_count (aux));
132 // CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h);
135 #define CLIB_CUCKOO_DEEP_SELF_CHECK(h) CV (clib_cuckoo_deep_self_check) (h)
136 #define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b) \
140 int min_free = CLIB_CUCKOO_KVP_PER_BUCKET; \
142 clib_cuckoo_bucket_foreach_idx (i) \
144 if (!CV (clib_cuckoo_kv_is_free) (b->elts + i)) \
148 if (CV (clib_cuckoo_kv_is_free) (b->elts + \
149 (CLIB_CUCKOO_KVP_PER_BUCKET - i))) \
154 ASSERT (min_free > max_used); \
159 #define CLIB_CUCKOO_DEEP_SELF_CHECK(h)
160 #define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b)
163 void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
165 void (*garbage_callback) (CVT (clib_cuckoo) *,
169 uword log2_nbuckets = max_log2 (nbuckets);
170 nbuckets = 1ULL << (log2_nbuckets);
171 CLIB_CUCKOO_DBG ("New cuckoo, adjusted nbuckets %wu", nbuckets);
172 CVT (clib_cuckoo_bucket) * buckets = NULL;
173 vec_validate_aligned (buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
174 ASSERT (nbuckets == vec_len (buckets));
175 h->buckets = buckets;
176 clib_spinlock_init (&h->writer_lock);
177 /* mark all elements free ... */
178 CVT (clib_cuckoo_bucket) * bucket;
180 clib_cuckoo_foreach_bucket (
181 bucket, h, { clib_memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
184 h->garbage_callback = garbage_callback;
185 h->garbage_ctx = garbage_ctx;
188 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h)
190 clib_memset (h, 0, sizeof (*h));
193 static clib_cuckoo_bucket_aux_t
194 CV (clib_cuckoo_bucket_version_bump_and_lock) (CVT (clib_cuckoo_bucket) * b)
196 clib_cuckoo_bucket_aux_t aux = b->aux;
197 u64 version = clib_cuckoo_bucket_aux_get_version (aux);
198 u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
199 u8 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
200 ASSERT (0 == writer_flag);
201 aux = clib_cuckoo_bucket_aux_pack (version + 1, use_count, 1);
206 static void CV (clib_cuckoo_bucket_unlock) (CVT (clib_cuckoo_bucket) * b,
207 clib_cuckoo_bucket_aux_t aux)
209 u64 version = clib_cuckoo_bucket_aux_get_version (aux);
210 u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
211 u8 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
212 ASSERT (1 == writer_flag);
213 aux = clib_cuckoo_bucket_aux_pack (version, use_count, 0);
217 #define CLIB_CUCKOO_DEBUG_PATH (1)
218 #define CLIB_CUCKOO_DEBUG_PATH_DETAIL (0)
220 #if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH
221 static u8 *CV (format_cuckoo_path) (u8 * s, va_list * args);
224 static clib_cuckoo_path_t *CV (clib_cuckoo_path_get) (CVT (clib_cuckoo) * h)
226 clib_cuckoo_path_t *path;
227 pool_get (h->paths, path);
228 clib_memset (path, 0, sizeof (*path));
229 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL
230 CLIB_CUCKOO_DBG ("Get path @%lu", (long unsigned) (path - h->paths));
235 static void CV (clib_cuckoo_path_put) (CVT (clib_cuckoo) * h, uword path_idx)
237 clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
238 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL
239 CLIB_CUCKOO_DBG ("Put path @%lu", (long unsigned) (path - h->paths));
241 pool_put (h->paths, path);
244 static clib_cuckoo_path_t *CV (clib_cuckoo_path_begin) (CVT (clib_cuckoo) * h,
248 ASSERT (next_offset < CLIB_CUCKOO_KVP_PER_BUCKET);
249 clib_cuckoo_path_t *new_path = CV (clib_cuckoo_path_get) (h);
250 new_path->length = 1;
251 new_path->data = next_offset;
252 new_path->start = bucket;
253 new_path->bucket = bucket;
254 #if CLIB_CUCKOO_DEBUG_PATH
255 CLIB_CUCKOO_DBG ("Create new path @%wu, length: %u data: %llu bucket: %wu "
257 new_path - h->paths, new_path->length,
258 (long long unsigned) new_path->data, new_path->bucket,
265 * create a new path based on existing path extended by adding a bucket
268 static uword CV (clib_cuckoo_path_extend) (CVT (clib_cuckoo) * h,
269 uword path_idx, uword bucket,
272 ASSERT (offset < CLIB_CUCKOO_KVP_PER_BUCKET);
273 clib_cuckoo_path_t *new_path = CV (clib_cuckoo_path_get) (h);
274 uword new_path_idx = new_path - h->paths;
275 clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
276 new_path->start = path->start;
277 new_path->length = path->length + 1;
278 new_path->data = (path->data << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) + offset;
279 new_path->bucket = bucket;
280 #if CLIB_CUCKOO_DEBUG_PATH
281 CLIB_CUCKOO_DBG ("Extend path @%wu, new path @%wu, %U", path_idx,
282 new_path_idx, CV (format_cuckoo_path), h, new_path_idx);
287 /** return the offset of the last element in the path */
288 static uword CV (clib_cuckoo_path_peek_offset) (const clib_cuckoo_path_t *
291 ASSERT (path->length > 0);
292 uword mask = (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) - 1;
293 uword offset = path->data & mask;
298 CVT (clib_cuckoo_kv) *
299 CV (clib_cuckoo_bucket_find_empty) (CVT (clib_cuckoo_bucket) * bucket)
301 clib_cuckoo_bucket_aux_t aux = bucket->aux;
302 u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
303 if (use_count < CLIB_CUCKOO_KVP_PER_BUCKET)
305 return bucket->elts + use_count;
311 * walk the cuckoo path two ways,
312 * first backwards, extracting offsets,
313 * then forward, extracting buckets
315 * buckets and offsets are arrays filled with elements extracted from path
316 * the arrays must be able to contain CLIB_CUCKOO_BFS_MAX_PATH_LENGTH elements
319 clib_cuckoo_path_walk (CVT (clib_cuckoo) * h, uword path_idx,
320 uword * buckets, uword * offsets)
322 clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
323 ASSERT (path->length > 0);
324 u64 data = path->data;
325 uword mask = (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) - 1;
327 for (i = path->length; i > 0; --i)
329 uword offset = data & mask;
330 offsets[i - 1] = offset;
331 data >>= CLIB_CUCKOO_LOG2_KVP_PER_BUCKET;
333 buckets[0] = path->start;
334 for (i = 1; i < path->length; ++i)
336 CVT (clib_cuckoo_bucket) * b =
337 CV (clib_cuckoo_bucket_at_index) (h, buckets[i - 1]);
339 clib_cuckoo_get_other_bucket (CV (clib_cuckoo_get_nbuckets) (h),
341 b->reduced_hashes[offsets[i - 1]]);
345 #if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH
346 static u8 *CV (format_cuckoo_path) (u8 * s, va_list * args)
348 CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
349 uword path_idx = va_arg (*args, uword);
350 clib_cuckoo_path_t *p = pool_elt_at_index (h->paths, path_idx);
351 uword buckets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
352 uword offsets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
353 clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
354 s = format (s, "length %u: ", p->length);
355 for (uword i = p->length - 1; i > 0; --i)
357 s = format (s, "%wu[%wu]->", buckets[i], offsets[i]);
361 s = format (s, "%wu[%wu]", buckets[0], offsets[0]);
368 * perform breadth-first search in the cuckoo hash, finding the closest
369 * empty slot, i.e. one which requires minimum swaps to move it
370 * to one of the buckets provided
372 static int CV (clib_cuckoo_find_empty_slot_bfs) (CVT (clib_cuckoo) * h,
373 clib_cuckoo_lookup_info_t *
374 lookup, uword * path_idx_out,
375 uword * found_bucket,
376 CVT (clib_cuckoo_kv) *
380 ASSERT (!vec_len (h->bfs_search_queue));
381 clib_cuckoo_path_t *tmp;
382 pool_flush (tmp, h->paths,);
383 int rv = CLIB_CUCKOO_ERROR_AGAIN;
385 /* start by creating paths starting in each of the buckets ... */
386 vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
388 for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
390 clib_cuckoo_path_t *path =
391 CV (clib_cuckoo_path_begin) (h, lookup->bucket1, i);
392 tail[i] = path - h->paths;
394 if (lookup->bucket1 != lookup->bucket2)
396 vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
397 for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
399 clib_cuckoo_path_t *path =
400 CV (clib_cuckoo_path_begin) (h, lookup->bucket2, i);
401 tail[i] = path - h->paths;
406 if (counter >= CLIB_CUCKOO_BFS_MAX_STEPS)
408 #if CLIB_CUCKOO_DEBUG_COUNTERS
413 if (counter >= vec_len (h->bfs_search_queue))
415 #if CLIB_CUCKOO_DEBUG_COUNTERS
416 ++h->bfs_queue_emptied;
420 const uword path_idx = vec_elt (h->bfs_search_queue, counter);
421 const clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
422 #if CLIB_CUCKOO_DEBUG_PATH
423 CLIB_CUCKOO_DBG ("Examine path @%wu: %U", path_idx,
424 CV (format_cuckoo_path), h, path_idx);
426 /* TODO prefetch ? */
427 /* search the alternative bucket for free space */
428 int offset = CV (clib_cuckoo_path_peek_offset) (path);
429 CVT (clib_cuckoo_bucket) * bucket =
430 CV (clib_cuckoo_bucket_at_index) (h, path->bucket);
432 clib_cuckoo_get_other_bucket (CV (clib_cuckoo_get_nbuckets) (h),
434 bucket->reduced_hashes[offset]);
436 ("Path ends in bucket %wu, offset #%wu, other bucket is %wu",
437 path->bucket, CV (clib_cuckoo_path_peek_offset) (path),
439 if (path->bucket != other_bucket)
442 CV (clib_cuckoo_bucket_find_empty) (CV
443 (clib_cuckoo_bucket_at_index)
446 /* found empty element */
447 *found_bucket = other_bucket;
448 *path_idx_out = path_idx;
449 rv = CLIB_CUCKOO_ERROR_SUCCESS;
450 #if CLIB_CUCKOO_DEBUG_PATH
451 CLIB_CUCKOO_DBG ("Bucket with empty slot:\n%U",
452 CV (format_cuckoo_bucket),
453 CV (clib_cuckoo_bucket_at_index) (h,
458 /* extend the current path with possible next buckets and add to
460 if (path->length < CLIB_CUCKOO_BFS_MAX_PATH_LENGTH &&
461 vec_len (h->bfs_search_queue) < CLIB_CUCKOO_BFS_MAX_STEPS)
464 vec_add2 (h->bfs_search_queue, tail,
465 CLIB_CUCKOO_KVP_PER_BUCKET);
466 for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
469 CV (clib_cuckoo_path_extend) (h, path_idx, other_bucket,
471 tail[i] = new_path_idx;
477 CLIB_CUCKOO_DBG ("Discard path @%wu, loop detected", path_idx);
479 /* done with this path - put back to pool for later reuse */
480 CV (clib_cuckoo_path_put) (h, path_idx);
484 vec_reset_length (h->bfs_search_queue);
488 static void CV (clib_cuckoo_swap_elts_in_bucket) (CVT (clib_cuckoo_bucket) *
489 b, uword e1, uword e2)
491 CVT (clib_cuckoo_kv) kv;
492 clib_memcpy (&kv, b->elts + e1, sizeof (kv));
493 clib_memcpy (b->elts + e1, b->elts + e2, sizeof (kv));
494 clib_memcpy (b->elts + e2, &kv, sizeof (kv));
495 u8 reduced_hash = b->reduced_hashes[e1];
496 b->reduced_hashes[e1] = b->reduced_hashes[e2];
497 b->reduced_hashes[e2] = reduced_hash;
500 static void CV (clib_cuckoo_bucket_tidy) (CVT (clib_cuckoo_bucket) * b)
503 int j = CLIB_CUCKOO_KVP_PER_BUCKET - 1;
508 while (!CV (clib_cuckoo_kv_is_free) (&b->elts[min_free]))
512 while (CV (clib_cuckoo_kv_is_free) (&b->elts[max_used]))
516 if (min_free < max_used)
518 CV (clib_cuckoo_swap_elts_in_bucket) (b, min_free, max_used);
529 static void CV (clib_cuckoo_free_locked_elt) (CVT (clib_cuckoo_kv) * elt)
532 * FIXME - improve performance by getting rid of this clib_memset - make all
533 * functions in this file not rely on clib_cuckoo_kv_is_free but instead
534 * take use_count into account */
535 clib_memset (elt, 0xff, sizeof (*elt));
538 static void CV (clib_cuckoo_free_elt_in_bucket) (CVT (clib_cuckoo_bucket) * b,
539 CVT (clib_cuckoo_kv) * elt)
541 clib_cuckoo_bucket_aux_t aux =
542 CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
543 int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
544 int offset = elt - b->elts;
545 ASSERT (offset < use_count);
546 CV (clib_cuckoo_free_locked_elt) (elt);
547 if (offset != use_count - 1)
549 CV (clib_cuckoo_bucket_tidy) (b);
551 aux = clib_cuckoo_bucket_aux_set_use_count (aux, use_count - 1);
552 CV (clib_cuckoo_bucket_unlock) (b, aux);
555 static void CV (clib_cuckoo_set_locked_elt) (CVT (clib_cuckoo_bucket) * b,
556 CVT (clib_cuckoo_kv) * elt,
557 CVT (clib_cuckoo_kv) * kvp,
560 int offset = CV (clib_cuckoo_elt_in_bucket_to_offset) (b, elt);
561 clib_memcpy (elt, kvp, sizeof (*elt));
562 b->reduced_hashes[offset] = reduced_hash;
563 CLIB_CUCKOO_DBG ("Set bucket %p, offset %d, %U", b, offset,
564 CV (format_cuckoo_elt), elt, b->reduced_hashes[offset]);
567 static void CV (clib_cuckoo_set_elt) (CVT (clib_cuckoo_bucket) * b,
568 CVT (clib_cuckoo_kv) * elt,
569 CVT (clib_cuckoo_kv) * kvp,
572 clib_cuckoo_bucket_aux_t aux =
573 CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
574 CV (clib_cuckoo_set_locked_elt) (b, elt, kvp, reduced_hash);
575 CV (clib_cuckoo_bucket_unlock) (b, aux);
578 static int CV (clib_cuckoo_add_slow) (CVT (clib_cuckoo) * h,
579 CVT (clib_cuckoo_kv) * kvp,
580 clib_cuckoo_lookup_info_t * lookup,
584 uword empty_bucket_idx;
585 CVT (clib_cuckoo_kv) * empty_elt;
586 int rv = CV (clib_cuckoo_find_empty_slot_bfs) (h, lookup, &path_idx,
589 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
591 uword buckets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
592 uword offsets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
593 clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
595 * walk back the path, moving the free element forward to one of our
598 clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
599 CVT (clib_cuckoo_bucket) * empty_bucket =
600 CV (clib_cuckoo_bucket_at_index) (h, empty_bucket_idx);
602 for (i = path->length - 1; i >= 0; --i)
604 /* copy the key-value in path to the bucket with empty element */
605 CVT (clib_cuckoo_bucket) * b =
606 CV (clib_cuckoo_bucket_at_index) (h, buckets[i]);
607 CVT (clib_cuckoo_kv) * elt = b->elts + offsets[i];
608 clib_cuckoo_bucket_aux_t empty_aux =
609 CV (clib_cuckoo_bucket_version_bump_and_lock) (empty_bucket);
610 CV (clib_cuckoo_set_locked_elt)
611 (empty_bucket, empty_elt, elt, b->reduced_hashes[elt - b->elts]);
612 if (i == path->length - 1)
614 /* we only need to increase the use count for the bucket with
615 * free element - all other buckets' use counts won't change */
616 empty_aux = clib_cuckoo_bucket_aux_set_use_count (empty_aux,
617 clib_cuckoo_bucket_aux_get_use_count
621 CV (clib_cuckoo_bucket_unlock) (empty_bucket, empty_aux);
623 * the element now exists in both places - in the previously empty
624 * element and in its original bucket - we can now safely overwrite
625 * the element in the original bucket with previous element in path
626 * without loosing data (and we don't need to modify the use count)
631 /* now we have a place to put the kvp in ... */
632 CV (clib_cuckoo_set_elt) (empty_bucket, empty_elt, kvp, reduced_hash);
633 CLIB_CUCKOO_DBG ("Slow insert success, bucket: %p\n%U", empty_bucket,
634 CV (format_cuckoo_bucket), empty_bucket);
635 #if CLIB_CUCKOO_DEBUG_COUNTERS
642 static int CV (clib_cuckoo_add_fast) (CVT (clib_cuckoo) * h,
643 clib_cuckoo_lookup_info_t * lookup,
644 CVT (clib_cuckoo_kv) * kvp,
647 CVT (clib_cuckoo_kv) * elt;
648 CVT (clib_cuckoo_bucket) * bucket1 =
649 CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket1);
650 if ((elt = CV (clib_cuckoo_bucket_find_empty) (bucket1)))
652 clib_cuckoo_bucket_aux_t aux =
653 CV (clib_cuckoo_bucket_version_bump_and_lock) (bucket1);
654 CV (clib_cuckoo_set_locked_elt) (bucket1, elt, kvp, reduced_hash);
656 clib_cuckoo_bucket_aux_set_use_count (aux,
657 clib_cuckoo_bucket_aux_get_use_count
659 CV (clib_cuckoo_bucket_unlock) (bucket1, aux);
660 #if CLIB_CUCKOO_DEBUG_COUNTERS
663 return CLIB_CUCKOO_ERROR_SUCCESS;
665 CVT (clib_cuckoo_bucket) * bucket2 =
666 CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket2);
668 CV (clib_cuckoo_bucket_find_empty) (CV (clib_cuckoo_bucket_at_index)
669 (h, lookup->bucket2))))
671 clib_cuckoo_bucket_aux_t aux =
672 CV (clib_cuckoo_bucket_version_bump_and_lock) (bucket2);
673 CV (clib_cuckoo_set_locked_elt) (bucket2, elt, kvp, reduced_hash);
675 clib_cuckoo_bucket_aux_set_use_count (aux,
676 clib_cuckoo_bucket_aux_get_use_count
678 CV (clib_cuckoo_bucket_unlock) (bucket2, aux);
679 #if CLIB_CUCKOO_DEBUG_COUNTERS
682 return CLIB_CUCKOO_ERROR_SUCCESS;
684 return CLIB_CUCKOO_ERROR_AGAIN;
688 * perform garbage collection
690 * this function assumes there is no other thread touching the cuckoo hash,
691 * not even a reader, it's meant to be called from main thread
692 * in a stop-the-world situation
694 void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h)
696 CLIB_MEMORY_BARRIER ();
697 CVT (clib_cuckoo_bucket) * *b;
699 vec_foreach (b, h->to_be_freed)
701 if (*b == h->buckets)
705 #if CLIB_CUCKOO_DEBUG_GC
706 fformat (stdout, "gc: free %p\n", *b);
711 vec_free (h->to_be_freed);
712 CLIB_MEMORY_BARRIER ();
716 * expand and rehash a cuckoo hash
718 * 1. double the size of the hash table
719 * 2. move items to new locations derived from the new size
721 static void CV (clib_cuckoo_rehash) (CVT (clib_cuckoo) * h)
723 CVT (clib_cuckoo_bucket) * old = h->buckets;
724 uword old_nbuckets = vec_len (old);
725 uword new_nbuckets = 2 * old_nbuckets;
726 CVT (clib_cuckoo_bucket) * new =
727 vec_dup_aligned (old, CLIB_CACHE_LINE_BYTES);
729 vec_validate_aligned (new, new_nbuckets - 1, CLIB_CACHE_LINE_BYTES);
730 ASSERT (new_nbuckets == vec_len (new));
731 /* store old pointer in to-be-freed list */
732 vec_add1 (h->to_be_freed, old);
733 /* mark new elements as free */
734 CVT (clib_cuckoo_bucket) * bucket;
735 for (bucket = new + old_nbuckets; bucket < vec_end (new); ++bucket)
737 clib_memset (bucket->elts, 0xff, sizeof (bucket->elts));
740 * this for loop manipulates the new (unseen) memory, so no locks
743 uword old_bucket_idx;
744 for (old_bucket_idx = 0; old_bucket_idx < old_nbuckets; ++old_bucket_idx)
746 /* items in old bucket might be moved to new bucket */
747 uword new_bucket_idx = old_bucket_idx + old_nbuckets;
748 CVT (clib_cuckoo_bucket) * old_bucket = new + old_bucket_idx;
749 CVT (clib_cuckoo_bucket) * new_bucket = new + new_bucket_idx;
752 clib_cuckoo_bucket_aux_t aux = old_bucket->aux;
753 for (i = 0; i < clib_cuckoo_bucket_aux_get_use_count (aux); ++i)
755 CVT (clib_cuckoo_kv) * elt = old_bucket->elts + i;
756 u64 hash = CV (clib_cuckoo_hash) (elt);
757 clib_cuckoo_lookup_info_t old_lookup =
758 CV (clib_cuckoo_calc_lookup) (old, hash);
759 clib_cuckoo_lookup_info_t new_lookup =
760 CV (clib_cuckoo_calc_lookup) (new, hash);
761 if ((old_bucket_idx == old_lookup.bucket1 &&
762 new_bucket_idx == new_lookup.bucket1) ||
763 (old_bucket_idx == old_lookup.bucket2 &&
764 new_bucket_idx == new_lookup.bucket2))
766 /* move the item to new bucket */
767 CVT (clib_cuckoo_kv) * empty_elt = new_bucket->elts + moved;
769 CV (clib_cuckoo_set_locked_elt)
770 (new_bucket, empty_elt, elt, old_bucket->reduced_hashes[i]);
771 CV (clib_cuckoo_free_locked_elt) (elt);
777 CV (clib_cuckoo_bucket_tidy) (old_bucket);
779 clib_cuckoo_bucket_aux_set_use_count (aux,
780 clib_cuckoo_bucket_aux_get_use_count
782 old_bucket->aux = aux;
783 aux = new_bucket->aux;
785 clib_cuckoo_bucket_aux_set_use_count (aux,
786 clib_cuckoo_bucket_aux_get_use_count
788 new_bucket->aux = aux;
792 #if CLIB_CUCKOO_DEBUG_COUNTERS
795 h->garbage_callback (h, h->garbage_ctx);
798 static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h,
800 CVT (clib_cuckoo_kv) *
802 CVT (clib_cuckoo_kv) *
805 CVT (clib_cuckoo_bucket) * b = CV (clib_cuckoo_bucket_at_index) (h, bucket);
808 clib_cuckoo_bucket_foreach_idx_unrolled (i, {
809 CVT (clib_cuckoo_kv) *elt = &b->elts[i];
810 if (CV (clib_cuckoo_key_compare) (elt->key, kvp->key))
813 return CLIB_CUCKOO_ERROR_SUCCESS;
817 return CLIB_CUCKOO_ERROR_NOT_FOUND;
820 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
821 CVT (clib_cuckoo_kv) * kvp, int is_add,
824 CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp),
826 clib_cuckoo_lookup_info_t lookup;
827 u64 hash = CV (clib_cuckoo_hash) (kvp);
828 u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
829 clib_spinlock_lock (&h->writer_lock);
831 lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
832 CVT (clib_cuckoo_bucket) * b =
833 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1);
834 CVT (clib_cuckoo_kv) * found;
836 CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket1, kvp, &found);
837 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
839 ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
840 b = CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2);
841 rv = CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket2, kvp,
844 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
850 CLIB_CUCKOO_DBG ("Refused replacing existing %U",
851 CV (format_cuckoo_elt), found,
852 b->reduced_hashes[found - b->elts]);
853 rv = CLIB_CUCKOO_ERROR_AGAIN;
857 /* prevent readers reading this bucket while we switch the values */
858 clib_cuckoo_bucket_aux_t aux =
859 CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
860 clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
861 CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
862 found, b->reduced_hashes[found - b->elts]);
863 CV (clib_cuckoo_bucket_unlock) (b, aux);
864 rv = CLIB_CUCKOO_ERROR_SUCCESS;
869 CV (clib_cuckoo_free_elt_in_bucket) (b, found);
870 rv = CLIB_CUCKOO_ERROR_SUCCESS;
872 CLIB_CUCKOO_DEEP_SELF_CHECK (h);
877 CLIB_CUCKOO_DBG ("%U not present in table", CV (format_cuckoo_kvp),
879 rv = CLIB_CUCKOO_ERROR_NOT_FOUND;
882 /* from this point on, it's add code only */
883 ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
884 /* fast path: try to search for unoccupied slot in one of the buckets */
885 rv = CV (clib_cuckoo_add_fast) (h, &lookup, kvp, reduced_hash);
886 CLIB_CUCKOO_DEEP_SELF_CHECK (h);
887 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
890 ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U",
891 lookup.bucket1, lookup.bucket2, CV (format_cuckoo_bucket),
892 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1),
893 CV (format_cuckoo_bucket),
894 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2));
896 rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
897 CLIB_CUCKOO_DEEP_SELF_CHECK (h);
898 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
900 CLIB_CUCKOO_DBG ("Slow insert failed, rehash required:\n%U",
901 CV (format_cuckoo), h, 1);
902 /* ultra slow path */
903 CV (clib_cuckoo_rehash) (h);
904 CLIB_CUCKOO_DEEP_SELF_CHECK (h);
905 CLIB_CUCKOO_DBG ("Restarting add after rehash...");
910 clib_spinlock_unlock (&h->writer_lock);
914 u8 *CV (format_cuckoo) (u8 * s, va_list * args)
916 CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
917 int verbose = va_arg (*args, int);
919 s = format (s, "Hash table %s\n", h->name ? h->name : "(unnamed)");
923 uword use_count_total = 0;
925 CVT (clib_cuckoo_bucket) * b;
927 clib_cuckoo_foreach_bucket (b, h, {
930 s = format (s, "%U", CV (format_cuckoo_bucket), b);
933 clib_cuckoo_bucket_foreach_idx (i)
935 CVT (clib_cuckoo_kv) *elt = &b->elts[i];
936 if (CV (clib_cuckoo_kv_is_free) (elt))
945 clib_cuckoo_bucket_aux_t aux = b->aux;
946 use_count_total += clib_cuckoo_bucket_aux_get_use_count (aux);
949 s = format (s, "Used slots: %wu\n", used);
950 s = format (s, "Use count total: %wu\n", use_count_total);
951 s = format (s, "Free slots: %wu\n", free);
952 if (free + used != 0)
953 load_factor = ((float) used) / ((float) (free + used));
956 s = format (s, "Load factor: %.2f\n", load_factor);
957 #if CLIB_CUCKOO_DEBUG_COUNTERS
958 s = format (s, "BFS attempts limited by max steps: %lld\n",
960 s = format (s, "BFS cutoffs due to empty queue: %lld\n",
961 h->bfs_queue_emptied);
962 s = format (s, "Fast adds: %lld\n", h->fast_adds);
963 s = format (s, "Slow adds: %lld\n", h->slow_adds);
964 s = format (s, "Rehashes: %lld\n", h->rehashes);
969 float CV (clib_cuckoo_calculate_load_factor) (CVT (clib_cuckoo) * h)
973 CVT (clib_cuckoo_bucket) * bucket;
975 clib_cuckoo_foreach_bucket (bucket, h, {
977 clib_cuckoo_bucket_foreach_idx (i)
979 CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
981 if (!CV (clib_cuckoo_kv_is_free) (elt))
989 return (float) nonfree / (float) all;
997 * fd.io coding-style-patch-verification: ON
1000 * eval: (c-set-style "gnu")