26 CVT (clib_cuckoo_kv) * search_v,
27 CVT (clib_cuckoo_kv) * return_v)
29 CVT (clib_cuckoo_kv) tmp = *search_v;
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)
52 CVT (clib_cuckoo_kv) * e)
55 ASSERT (e <= &b->elts[
sizeof (b->elts) / sizeof (b->elts[0]) - 1]);
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,
77 CVT (clib_cuckoo_bucket) * bucket =
78 va_arg (*args,
CVT (clib_cuckoo_bucket) *);
84 CVT (clib_cuckoo_kv) *elt = bucket->elts +
i;
85 s =
format (s,
"bucket %p, offset %d: %U\n", bucket, i,
90 s =
format (s,
"version: %lld, use count: %d\n",
97 static void CV (clib_cuckoo_deep_self_check) (
CVT (clib_cuckoo) *
h)
99 CVT (clib_cuckoo_bucket) * bucket;
100 uword bucket_idx = 0;
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);
113 CVT (clib_cuckoo_kv) kv = *elt;
115 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
119 bucket->reduced_hashes[i]);
123 ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
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) 165 void (*garbage_callback) (
CVT (clib_cuckoo) *,
170 nbuckets = 1ULL << (log2_nbuckets);
172 CVT (clib_cuckoo_bucket) * buckets = NULL;
175 h->buckets = buckets;
178 CVT (clib_cuckoo_bucket) * bucket;
181 bucket, h, {
clib_memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
184 h->garbage_callback = garbage_callback;
185 h->garbage_ctx = garbage_ctx;
200 ASSERT (0 == writer_flag);
212 ASSERT (1 == writer_flag);
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);
229 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL 238 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL 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,
274 uword new_path_idx = new_path - h->paths;
279 new_path->
bucket = bucket;
280 #if CLIB_CUCKOO_DEBUG_PATH 282 new_path_idx,
CV (format_cuckoo_path), h, new_path_idx);
299 CV (clib_cuckoo_bucket_find_empty) (
CVT (clib_cuckoo_bucket) * bucket)
305 return bucket->elts + use_count;
327 for (i = path->
length; i > 0; --i)
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]);
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) *);
357 s =
format (s,
"%wu[%wu]->", buckets[
i], offsets[i]);
361 s =
format (s,
"%wu[%wu]", buckets[0], offsets[0]);
375 uword * found_bucket,
376 CVT (clib_cuckoo_kv) *
383 int rv = CLIB_CUCKOO_ERROR_AGAIN;
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);
401 tail[
i] = path - h->paths;
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);
422 #if CLIB_CUCKOO_DEBUG_PATH 424 CV (format_cuckoo_path), h, path_idx);
429 CVT (clib_cuckoo_bucket) * bucket =
430 CV (clib_cuckoo_bucket_at_index) (
h, path->
bucket);
434 bucket->reduced_hashes[offset]);
436 (
"Path ends in bucket %wu, offset #%wu, other bucket is %wu",
439 if (path->
bucket != other_bucket)
442 CV (clib_cuckoo_bucket_find_empty) (
CV 443 (clib_cuckoo_bucket_at_index)
447 *found_bucket = other_bucket;
448 *path_idx_out = path_idx;
449 rv = CLIB_CUCKOO_ERROR_SUCCESS;
450 #if CLIB_CUCKOO_DEBUG_PATH 453 CV (clib_cuckoo_bucket_at_index) (h,
464 vec_add2 (h->bfs_search_queue, tail,
465 CLIB_CUCKOO_KVP_PER_BUCKET);
471 tail[
i] = new_path_idx;
491 CVT (clib_cuckoo_kv) kv;
493 clib_memcpy (b->elts + e1, b->elts + e2, 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;
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)
539 CVT (clib_cuckoo_kv) * elt)
544 int offset = elt - b->elts;
545 ASSERT (offset < use_count);
547 if (offset != use_count - 1)
556 CVT (clib_cuckoo_kv) * elt,
557 CVT (clib_cuckoo_kv) * kvp,
562 b->reduced_hashes[
offset] = reduced_hash;
568 CVT (clib_cuckoo_kv) * elt,
569 CVT (clib_cuckoo_kv) * kvp,
579 CVT (clib_cuckoo_kv) * kvp,
584 uword empty_bucket_idx;
585 CVT (clib_cuckoo_kv) * empty_elt;
589 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
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)
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];
611 (empty_bucket, empty_elt, elt, b->reduced_hashes[elt - b->elts]);
612 if (i == path->
length - 1)
635 #if CLIB_CUCKOO_DEBUG_COUNTERS 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)))
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))))
679 #if CLIB_CUCKOO_DEBUG_COUNTERS 682 return CLIB_CUCKOO_ERROR_SUCCESS;
684 return CLIB_CUCKOO_ERROR_AGAIN;
697 CVT (clib_cuckoo_bucket) * *b;
701 if (*b == h->buckets)
705 #if CLIB_CUCKOO_DEBUG_GC 706 fformat (stdout,
"gc: free %p\n", *b);
723 CVT (clib_cuckoo_bucket) * old = h->buckets;
725 uword new_nbuckets = 2 * old_nbuckets;
726 CVT (clib_cuckoo_bucket) *
new =
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));
743 uword old_bucket_idx;
744 for (old_bucket_idx = 0; old_bucket_idx < old_nbuckets; ++old_bucket_idx)
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;
755 CVT (clib_cuckoo_kv) * elt = old_bucket->elts +
i;
756 u64 hash =
CV (clib_cuckoo_hash) (elt);
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))
767 CVT (clib_cuckoo_kv) * empty_elt = new_bucket->elts + moved;
770 (new_bucket, empty_elt, elt, old_bucket->reduced_hashes[
i]);
780 clib_cuckoo_bucket_aux_get_use_count
782 old_bucket->aux = aux;
783 aux = new_bucket->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);
800 CVT (clib_cuckoo_kv) *
802 CVT (clib_cuckoo_kv) *
805 CVT (clib_cuckoo_bucket) * b =
CV (clib_cuckoo_bucket_at_index) (
h, bucket);
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;
821 CVT (clib_cuckoo_kv) * kvp,
int is_add,
827 u64 hash =
CV (clib_cuckoo_hash) (kvp);
832 CVT (clib_cuckoo_bucket) * b =
833 CV (clib_cuckoo_bucket_at_index) (
h, lookup.
bucket1);
834 CVT (clib_cuckoo_kv) * 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);
844 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
852 b->reduced_hashes[found - b->elts]);
853 rv = CLIB_CUCKOO_ERROR_AGAIN;
860 clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
862 found, b->reduced_hashes[found - b->elts]);
864 rv = CLIB_CUCKOO_ERROR_SUCCESS;
870 rv = CLIB_CUCKOO_ERROR_SUCCESS;
879 rv = CLIB_CUCKOO_ERROR_NOT_FOUND;
883 ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
887 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
890 (
"Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U",
892 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1),
894 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2));
898 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
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;
935 CVT (clib_cuckoo_kv) *elt = &b->elts[
i];
936 if (
CV (clib_cuckoo_kv_is_free) (elt))
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);
973 CVT (clib_cuckoo_bucket) * bucket;
979 CVT (clib_cuckoo_kv) *elt = bucket->elts +
i;
981 if (!
CV (clib_cuckoo_kv_is_free) (elt))
989 return (
float) nonfree / (float) all;
void CV() clib_cuckoo_garbage_collect(CVT(clib_cuckoo) *h)
perform garbage collection
#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body)
static_always_inline void clib_spinlock_unlock(clib_spinlock_t *p)
static_always_inline void clib_spinlock_lock(clib_spinlock_t *p)
u8 *CV() format_cuckoo_bucket(u8 *s, va_list *args)
static CVT(clib_cuckoo_bucket)
u64 start
bucket where this path begins
u8 length
length of the path
u64 clib_cuckoo_bucket_aux_t
#define clib_cuckoo_foreach_bucket(var, h, body)
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
static clib_cuckoo_path_t *CV() clib_cuckoo_path_get(CVT(clib_cuckoo) *h)
u8 *CV() format_cuckoo_elt(u8 *s, va_list *args)
#define CLIB_CUCKOO_KVP_PER_BUCKET
void CV() clib_cuckoo_init(CVT(clib_cuckoo) *h, const char *name, uword nbuckets, void(*garbage_callback)(CVT(clib_cuckoo) *, void *), void *garbage_ctx)
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
static u64 clib_cuckoo_get_other_bucket(u64 nbuckets, u64 bucket, u8 reduced_hash)
static void clib_cuckoo_path_walk(CVT(clib_cuckoo) *h, uword path_idx, uword *buckets, uword *offsets)
walk the cuckoo path two ways, first backwards, extracting offsets, then forward, extracting buckets ...
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
static void CV() clib_cuckoo_free_locked_elt(CVT(clib_cuckoo_kv) *elt)
#define vec_validate_aligned(V, I, A)
Make sure vector is long enough for given index (no header, specified alignment)
static void CV() clib_cuckoo_swap_elts_in_bucket(CVT(clib_cuckoo_bucket) *b, uword e1, uword e2)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
#define CLIB_CUCKOO_DEEP_SELF_CHECK(h)
static u8 clib_cuckoo_reduce_hash(u64 hash)
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
#define clib_memcpy(d, s, n)
static void CV() clib_cuckoo_rehash(CVT(clib_cuckoo) *h)
expand and rehash a cuckoo hash
#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
static void CV() clib_cuckoo_set_elt(CVT(clib_cuckoo_bucket) *b, CVT(clib_cuckoo_kv) *elt, CVT(clib_cuckoo_kv) *kvp, u8 reduced_hash)
static clib_cuckoo_path_t *CV() clib_cuckoo_path_begin(CVT(clib_cuckoo) *h, uword bucket, uword next_offset)
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_use_count(clib_cuckoo_bucket_aux_t aux, int use_count)
static void CV() clib_cuckoo_bucket_tidy(CVT(clib_cuckoo_bucket) *b)
#define vec_end(v)
End (last data address) of vector.
static void CV() clib_cuckoo_path_put(CVT(clib_cuckoo) *h, uword path_idx)
#define CLIB_CUCKOO_BFS_MAX_PATH_LENGTH
static int CV() clib_cuckoo_bucket_search_internal(CVT(clib_cuckoo) *h, uword bucket, CVT(clib_cuckoo_kv) *kvp, CVT(clib_cuckoo_kv) **found)
static uword CV() clib_cuckoo_get_nbuckets(CVT(clib_cuckoo) *h)
static void clib_spinlock_init(clib_spinlock_t *p)
#define pool_flush(VAR, POOL, BODY)
Remove all elements from a pool in a safe way.
static u64 clib_cuckoo_bucket_aux_get_version(clib_cuckoo_bucket_aux_t aux)
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
static void CV() clib_cuckoo_bucket_unlock(CVT(clib_cuckoo_bucket) *b, clib_cuckoo_bucket_aux_t aux)
u64 bucket
bucket at end of path
static void CV() clib_cuckoo_set_locked_elt(CVT(clib_cuckoo_bucket) *b, CVT(clib_cuckoo_kv) *elt, CVT(clib_cuckoo_kv) *kvp, u8 reduced_hash)
#define pool_put(P, E)
Free an object E in pool P.
static clib_cuckoo_bucket_aux_t CV() clib_cuckoo_bucket_version_bump_and_lock(CVT(clib_cuckoo_bucket) *b)
static int CV() clib_cuckoo_add_fast(CVT(clib_cuckoo) *h, clib_cuckoo_lookup_info_t *lookup, CVT(clib_cuckoo_kv) *kvp, u8 reduced_hash)
#define CLIB_CUCKOO_DBG(...)
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
int CV() clib_cuckoo_add_del(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *kvp, int is_add, int dont_overwrite)
#define clib_cuckoo_bucket_foreach_idx(var)
sll srl srl sll sra u16x4 i
#define vec_free(V)
Free vector's memory (no header).
static int clib_cuckoo_bucket_aux_get_use_count(clib_cuckoo_bucket_aux_t aux)
u8 *CV() format_cuckoo(u8 *s, va_list *args)
int CV() clib_cuckoo_search(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *search_v, CVT(clib_cuckoo_kv) *return_v)
static void CV() clib_cuckoo_free_elt_in_bucket(CVT(clib_cuckoo_bucket) *b, CVT(clib_cuckoo_kv) *elt)
static int CV() clib_cuckoo_find_empty_slot_bfs(CVT(clib_cuckoo) *h, clib_cuckoo_lookup_info_t *lookup, uword *path_idx_out, uword *found_bucket, CVT(clib_cuckoo_kv) **found_elt)
static clib_cuckoo_lookup_info_t CV() clib_cuckoo_calc_lookup(CVT(clib_cuckoo_bucket) *buckets, u64 hash)
#define vec_elt(v, i)
Get vector value at index i.
static int CV() clib_cuckoo_search_inline(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *kvp)
template key/value backing page structure
#define vec_dup_aligned(V, A)
Return copy of vector (no header, alignment specified).
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static uword max_log2(uword x)
void CV() clib_cuckoo_free(CVT(clib_cuckoo) *h)
struct clib_bihash_value offset
template key/value backing page structure
static uword CV() clib_cuckoo_elt_in_bucket_to_offset(CVT(clib_cuckoo_bucket) *b, CVT(clib_cuckoo_kv) *e)
path_data_t data
holds compressed offsets in buckets along path
#define vec_foreach(var, vec)
Vector iterator.
#define CLIB_MEMORY_BARRIER()
#define CLIB_CUCKOO_BFS_MAX_STEPS
static uword CV() clib_cuckoo_path_peek_offset(const clib_cuckoo_path_t *path)
return the offset of the last element in the path
static uword CV() clib_cuckoo_path_extend(CVT(clib_cuckoo) *h, uword path_idx, uword bucket, unsigned offset)
create a new path based on existing path extended by adding a bucket and offset
float CV() clib_cuckoo_calculate_load_factor(CVT(clib_cuckoo) *h)
#define CLIB_CACHE_LINE_BYTES
static int clib_cuckoo_bucket_aux_get_writer_flag(clib_cuckoo_bucket_aux_t aux)
static int CV() clib_cuckoo_add_slow(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *kvp, clib_cuckoo_lookup_info_t *lookup, u8 reduced_hash)
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_pack(u64 version, int use_count, int writer_flag)
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".