27 CVT (clib_cuckoo_kv) * search_v,
28 CVT (clib_cuckoo_kv) * return_v)
30 CVT (clib_cuckoo_kv) tmp = *search_v;
32 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
40 CVT (clib_cuckoo_bucket) *
41 CV (clib_cuckoo_bucket_at_index) (
CVT (clib_cuckoo) *
h,
uword bucket)
53 CVT (clib_cuckoo_kv) * e)
56 ASSERT (e <= &b->elts[
sizeof (b->elts) / sizeof (b->elts[0]) - 1]);
62 CVT (clib_cuckoo_kv) * elt = va_arg (*args,
CVT (clib_cuckoo_kv) *);
63 unsigned reduced_hash = va_arg (*args,
unsigned);
64 if (
CV (clib_cuckoo_kv_is_free) (elt))
66 s =
format (s,
"[ -- empty -- ]");
70 s =
format (s,
"[%U, reduced hash: %u]",
CV (format_cuckoo_kvp), elt,
78 CVT (clib_cuckoo_bucket) * bucket =
79 va_arg (*args,
CVT (clib_cuckoo_bucket) *);
85 CVT (clib_cuckoo_kv) *elt = bucket->elts +
i;
86 s =
format (s,
"bucket %p, offset %d: %U\n", bucket, i,
91 s =
format (s,
"version: %lld, use count: %d\n",
98 static void CV (clib_cuckoo_deep_self_check) (
CVT (clib_cuckoo) *
h)
100 CVT (clib_cuckoo_bucket) * bucket;
101 uword bucket_idx = 0;
109 CVT (clib_cuckoo_kv) *elt = bucket->elts +
i;
110 if (!
CV (clib_cuckoo_kv_is_free) (elt))
112 u64 hash =
CV (clib_cuckoo_hash) (elt);
114 CV (clib_cuckoo_get_snapshot) (
h), hash);
115 CVT (clib_cuckoo_kv) kv = *elt;
117 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
121 bucket->reduced_hashes[i]);
124 ASSERT (aux.bucket1 == bucket_idx || aux.bucket2 == bucket_idx);
125 ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
137 #define CLIB_CUCKOO_DEEP_SELF_CHECK(h) CV (clib_cuckoo_deep_self_check) (h) 138 #define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b) \ 142 int min_free = CLIB_CUCKOO_KVP_PER_BUCKET; \ 144 clib_cuckoo_bucket_foreach_idx (i) \ 146 if (!CV (clib_cuckoo_kv_is_free) (b->elts + i)) \ 150 if (CV (clib_cuckoo_kv_is_free) (b->elts + \ 151 (CLIB_CUCKOO_KVP_PER_BUCKET - i))) \ 156 ASSERT (min_free > max_used); \ 161 #define CLIB_CUCKOO_DEEP_SELF_CHECK(h) 162 #define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b) 167 void (*garbage_callback) (
CVT (clib_cuckoo) *,
172 nbuckets = 1 << (log2_nbuckets);
174 CVT (clib_cuckoo_bucket) * buckets =
NULL;
177 h->buckets = buckets;
180 CVT (clib_cuckoo_bucket) * bucket;
183 bucket, h, { memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
186 h->garbage_callback = garbage_callback;
187 h->garbage_ctx = garbage_ctx;
192 memset (h, 0,
sizeof (*h));
202 ASSERT (0 == writer_flag);
214 ASSERT (1 == writer_flag);
219 #define CLIB_CUCKOO_DEBUG_PATH (1) 220 #define CLIB_CUCKOO_DEBUG_PATH_DETAIL (0) 222 #if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH 223 static u8 *
CV (format_cuckoo_path) (
u8 * s, va_list * args);
230 memset (path, 0,
sizeof (*path));
231 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL 240 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL 253 new_path->
data = next_offset;
254 new_path->
start = bucket;
255 new_path->
bucket = bucket;
256 #if CLIB_CUCKOO_DEBUG_PATH 257 CLIB_CUCKOO_DBG (
"Create new path @%wu, length: %u data: %llu bucket: %wu " 259 new_path - h->paths, new_path->
length,
260 (
long long unsigned) new_path->
data, new_path->
bucket,
276 uword new_path_idx = new_path - h->paths;
281 new_path->
bucket = bucket;
282 #if CLIB_CUCKOO_DEBUG_PATH 284 new_path_idx,
CV (format_cuckoo_path), h, new_path_idx);
293 ASSERT (path->length > 0);
301 CV (clib_cuckoo_bucket_find_empty) (
CVT (clib_cuckoo_bucket) * bucket)
307 return bucket->elts + use_count;
329 for (i = path->
length; i > 0; --i)
335 buckets[0] = path->
start;
336 for (i = 1; i < path->
length; ++
i)
338 CVT (clib_cuckoo_bucket) * b =
339 CV (clib_cuckoo_bucket_at_index) (
h, buckets[i - 1]);
343 b->reduced_hashes[offsets[i - 1]]);
347 #if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH 348 static u8 *
CV (format_cuckoo_path) (
u8 * s, va_list * args)
350 CVT (clib_cuckoo) * h = va_arg (*args,
CVT (clib_cuckoo) *);
359 s =
format (s,
"%wu[%wu]->", buckets[
i], offsets[i]);
363 s =
format (s,
"%wu[%wu]", buckets[0], offsets[0]);
377 uword * found_bucket,
378 CVT (clib_cuckoo_kv) *
385 int rv = CLIB_CUCKOO_ERROR_AGAIN;
394 tail[
i] = path - h->paths;
396 if (lookup->bucket1 != lookup->bucket2)
398 vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
403 tail[
i] = path - h->paths;
410 #if CLIB_CUCKOO_DEBUG_COUNTERS 415 if (counter >=
vec_len (h->bfs_search_queue))
417 #if CLIB_CUCKOO_DEBUG_COUNTERS 418 ++h->bfs_queue_emptied;
422 const uword path_idx =
vec_elt (h->bfs_search_queue, counter);
424 #if CLIB_CUCKOO_DEBUG_PATH 426 CV (format_cuckoo_path), h, path_idx);
431 CVT (clib_cuckoo_bucket) * bucket =
432 CV (clib_cuckoo_bucket_at_index) (
h, path->
bucket);
436 bucket->reduced_hashes[offset]);
438 (
"Path ends in bucket %wu, offset #%wu, other bucket is %wu",
441 if (path->
bucket != other_bucket)
444 CV (clib_cuckoo_bucket_find_empty) (
CV 445 (clib_cuckoo_bucket_at_index)
449 *found_bucket = other_bucket;
450 *path_idx_out = path_idx;
451 rv = CLIB_CUCKOO_ERROR_SUCCESS;
452 #if CLIB_CUCKOO_DEBUG_PATH 455 CV (clib_cuckoo_bucket_at_index) (h,
466 vec_add2 (h->bfs_search_queue, tail,
467 CLIB_CUCKOO_KVP_PER_BUCKET);
473 tail[
i] = new_path_idx;
493 CVT (clib_cuckoo_kv) kv;
495 clib_memcpy (b->elts + e1, b->elts + e2, sizeof (kv));
497 u8 reduced_hash = b->reduced_hashes[e1];
498 b->reduced_hashes[e1] = b->reduced_hashes[e2];
499 b->reduced_hashes[e2] = reduced_hash;
510 while (!
CV (clib_cuckoo_kv_is_free) (&b->elts[min_free]))
514 while (
CV (clib_cuckoo_kv_is_free) (&b->elts[max_used]))
518 if (min_free < max_used)
537 memset (elt, 0xff,
sizeof (*elt));
541 CVT (clib_cuckoo_kv) * elt)
546 int offset = elt - b->elts;
547 ASSERT (offset < use_count);
549 if (offset != use_count - 1)
558 CVT (clib_cuckoo_kv) * elt,
559 CVT (clib_cuckoo_kv) * kvp,
564 b->reduced_hashes[
offset] = reduced_hash;
570 CVT (clib_cuckoo_kv) * elt,
571 CVT (clib_cuckoo_kv) * kvp,
581 CVT (clib_cuckoo_kv) * kvp,
586 uword empty_bucket_idx;
587 CVT (clib_cuckoo_kv) * empty_elt;
591 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
601 CVT (clib_cuckoo_bucket) * empty_bucket =
602 CV (clib_cuckoo_bucket_at_index) (
h, empty_bucket_idx);
604 for (i = path->
length - 1; i >= 0; --i)
607 CVT (clib_cuckoo_bucket) * b =
608 CV (clib_cuckoo_bucket_at_index) (
h, buckets[
i]);
609 CVT (clib_cuckoo_kv) * elt = b->elts + offsets[
i];
613 (empty_bucket, empty_elt, elt, b->reduced_hashes[elt - b->elts]);
614 if (i == path->
length - 1)
637 #if CLIB_CUCKOO_DEBUG_COUNTERS 646 CVT (clib_cuckoo_kv) * kvp,
649 CVT (clib_cuckoo_kv) * elt;
650 CVT (clib_cuckoo_bucket) * bucket1 =
651 CV (clib_cuckoo_bucket_at_index) (
h, lookup->bucket1);
652 if ((elt =
CV (clib_cuckoo_bucket_find_empty) (bucket1)))
662 #if CLIB_CUCKOO_DEBUG_COUNTERS 665 return CLIB_CUCKOO_ERROR_SUCCESS;
667 CVT (clib_cuckoo_bucket) * bucket2 =
668 CV (clib_cuckoo_bucket_at_index) (
h, lookup->bucket2);
670 CV (clib_cuckoo_bucket_find_empty) (
CV (clib_cuckoo_bucket_at_index)
671 (h, lookup->bucket2))))
681 #if CLIB_CUCKOO_DEBUG_COUNTERS 684 return CLIB_CUCKOO_ERROR_SUCCESS;
686 return CLIB_CUCKOO_ERROR_AGAIN;
699 CVT (clib_cuckoo_bucket) * *b;
703 if (*b == h->buckets)
707 #if CLIB_CUCKOO_DEBUG_GC 708 fformat (stdout,
"gc: free %p\n", *b);
725 CVT (clib_cuckoo_bucket) * old = h->buckets;
727 uword new_nbuckets = 2 * old_nbuckets;
728 CVT (clib_cuckoo_bucket) *
new =
736 CVT (clib_cuckoo_bucket) * bucket;
737 for (bucket =
new + old_nbuckets; bucket <
vec_end (
new); ++bucket)
739 memset (bucket->elts, 0xff, sizeof (bucket->elts));
745 uword old_bucket_idx;
746 for (old_bucket_idx = 0; old_bucket_idx < old_nbuckets; ++old_bucket_idx)
749 uword new_bucket_idx = old_bucket_idx + old_nbuckets;
750 CVT (clib_cuckoo_bucket) * old_bucket =
new + old_bucket_idx;
751 CVT (clib_cuckoo_bucket) * new_bucket =
new + new_bucket_idx;
757 CVT (clib_cuckoo_kv) * elt = old_bucket->elts +
i;
758 u64 hash =
CV (clib_cuckoo_hash) (elt);
763 if ((old_bucket_idx == old_lookup.
bucket1 &&
764 new_bucket_idx == new_lookup.
bucket1) ||
765 (old_bucket_idx == old_lookup.
bucket2 &&
766 new_bucket_idx == new_lookup.
bucket2))
769 CVT (clib_cuckoo_kv) * empty_elt = new_bucket->elts + moved;
772 (new_bucket, empty_elt, elt, old_bucket->reduced_hashes[
i]);
782 clib_cuckoo_bucket_aux_get_use_count
784 old_bucket->aux = aux;
785 aux = new_bucket->aux;
788 clib_cuckoo_bucket_aux_get_use_count
790 new_bucket->aux = aux;
794 #if CLIB_CUCKOO_DEBUG_COUNTERS 797 h->garbage_callback (h, h->garbage_ctx);
802 CVT (clib_cuckoo_kv) *
804 CVT (clib_cuckoo_kv) *
807 CVT (clib_cuckoo_bucket) * b =
CV (clib_cuckoo_bucket_at_index) (
h, bucket);
811 CVT (clib_cuckoo_kv) *elt = &b->elts[
i];
812 if (
CV (clib_cuckoo_key_compare) (elt->key, kvp->key))
815 return CLIB_CUCKOO_ERROR_SUCCESS;
819 return CLIB_CUCKOO_ERROR_NOT_FOUND;
823 CVT (clib_cuckoo_kv) * kvp,
int is_add)
828 u64 hash =
CV (clib_cuckoo_hash) (kvp);
833 CVT (clib_cuckoo_bucket) * b =
834 CV (clib_cuckoo_bucket_at_index) (
h, lookup.
bucket1);
835 CVT (clib_cuckoo_kv) * found;
838 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
840 ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
841 b =
CV (clib_cuckoo_bucket_at_index) (
h, lookup.
bucket2);
845 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
852 clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
854 found, b->reduced_hashes[found - b->elts]);
861 rv = CLIB_CUCKOO_ERROR_SUCCESS;
869 rv = CLIB_CUCKOO_ERROR_NOT_FOUND;
873 ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
877 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
879 CLIB_CUCKOO_DBG (
"Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U", aux.bucket1, aux.bucket2,
CV (
format_cuckoo_bucket),
CV (clib_cuckoo_bucindent: Standaindent: Standard input: 903: Error: Unmatched
'else' rd input: 865: Error:Unmatched
'else' ket_at_index) (h, aux.bucket1),
881 CV (clib_cuckoo_bucket_at_index) (h, aux.bucket2));
885 if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
903 CVT (clib_cuckoo) * h = va_arg (*args,
CVT (clib_cuckoo) *);
904 int verbose = va_arg (*args,
int);
906 s =
format (s,
"Hash table %s\n", h->name ? h->name :
"(unnamed)");
910 uword use_count_total = 0;
911 CVT (clib_cuckoo_bucket) * b;
921 CVT (clib_cuckoo_kv) *elt = &b->elts[
i];
922 if (
CV (clib_cuckoo_kv_is_free) (elt))
935 s =
format (s,
"Used slots: %wu\n", used);
936 s =
format (s,
"Use count total: %wu\n", use_count_total);
937 s =
format (s,
"Free slots: %wu\n", free);
939 format (s,
"Load factor: %.2f\n", (
float) (used) / (
float) (free + used));
940 #if CLIB_CUCKOO_DEBUG_COUNTERS 941 s =
format (s,
"BFS attempts limited by max steps: %lld\n",
943 s =
format (s,
"BFS cutoffs due to empty queue: %lld\n",
944 h->bfs_queue_emptied);
945 s =
format (s,
"Fast adds: %lld\n", h->fast_adds);
946 s =
format (s,
"Slow adds: %lld\n", h->slow_adds);
947 s =
format (s,
"Rehashes: %lld\n", h->rehashes);
956 CVT (clib_cuckoo_bucket) * bucket;
962 CVT (clib_cuckoo_kv) *elt = bucket->elts +
i;
964 if (!
CV (clib_cuckoo_kv_is_free) (elt))
971 return (
float) nonfree / (float) all;
static void CV() clib_cuckoo_free_elt_in_bucket(CVT(clib_cuckoo_bucket)*b, CVT(clib_cuckoo_kv)*elt)
#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body)
sll srl srl sll sra u16x4 i
static_always_inline void clib_spinlock_unlock(clib_spinlock_t *p)
static_always_inline void clib_spinlock_lock(clib_spinlock_t *p)
static clib_cuckoo_path_t *CV() clib_cuckoo_path_get(CVT(clib_cuckoo)*h)
u8 *CV() format_cuckoo_bucket(u8 *s, va_list *args)
static CVT(clib_cuckoo_bucket)
static clib_cuckoo_bucket_aux_t CV() clib_cuckoo_bucket_version_bump_and_lock(CVT(clib_cuckoo_bucket)*b)
static uword CV() clib_cuckoo_get_nbuckets(CVT(clib_cuckoo)*h)
u64 start
bucket where this path begins
static clib_cuckoo_lookup_info_t CV() clib_cuckoo_calc_lookup(CVT(clib_cuckoo_bucket)*buckets, u64 hash)
u8 length
length of the path
int CV() clib_cuckoo_add_del(CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*kvp, int is_add)
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)
u64 clib_cuckoo_bucket_aux_t
#define clib_cuckoo_foreach_bucket(var, h, body)
u8 *CV() format_cuckoo_elt(u8 *s, va_list *args)
#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)
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
int CV() clib_cuckoo_search(CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*search_v, CVT(clib_cuckoo_kv)*return_v)
void CV() clib_cuckoo_garbage_collect(CVT(clib_cuckoo)*h)
perform garbage collection
static clib_cuckoo_path_t *CV() clib_cuckoo_path_begin(CVT(clib_cuckoo)*h, uword bucket, uword next_offset)
#define vec_validate_aligned(V, I, A)
Make sure vector is long enough for given index (no header, specified alignment)
#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.
float CV() clib_cuckoo_calculate_load_factor(CVT(clib_cuckoo)*h)
#define CLIB_CUCKOO_BFS_MAX_PATH_LENGTH
#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)
#define vec_end(v)
End (last data address) of vector.
static void clib_spinlock_init(clib_spinlock_t *p)
static void CV() clib_cuckoo_path_put(CVT(clib_cuckoo)*h, uword path_idx)
#define pool_flush(VAR, POOL, BODY)
Remove all elemenets 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_rehash(CVT(clib_cuckoo)*h)
expand and rehash a cuckoo hash
u64 bucket
bucket at end of path
static uword CV() clib_cuckoo_elt_in_bucket_to_offset(CVT(clib_cuckoo_bucket)*b, CVT(clib_cuckoo_kv)*e)
void CV() clib_cuckoo_free(CVT(clib_cuckoo)*h)
#define pool_put(P, E)
Free an object E in pool P.
#define CLIB_CUCKOO_DBG(...)
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 CLIB_CUCKOO_KVP_PER_BUCKET
#define CLIB_CUCKOO_BFS_MAX_STEPS
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
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 clib_cuckoo_bucket_foreach_idx(var)
#define vec_free(V)
Free vector's memory (no header).
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 clib_memcpy(a, b, c)
static int clib_cuckoo_bucket_aux_get_use_count(clib_cuckoo_bucket_aux_t aux)
u8 *CV() format_cuckoo(u8 *s, va_list *args)
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)
static void CV() clib_cuckoo_bucket_unlock(CVT(clib_cuckoo_bucket)*b, clib_cuckoo_bucket_aux_t aux)
#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
static int CV() clib_cuckoo_search_inline(CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*kvp)
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 void CV() clib_cuckoo_swap_elts_in_bucket(CVT(clib_cuckoo_bucket)*b, uword e1, uword e2)
#define vec_elt(v, i)
Get vector value at index i.
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)
template key/value backing page structure
static void CV() clib_cuckoo_free_locked_elt(CVT(clib_cuckoo_kv)*elt)
#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)
struct clib_bihash_value offset
template key/value backing page structure
path_data_t data
holds compressed offsets in buckets along 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
#define vec_foreach(var, vec)
Vector iterator.
#define CLIB_MEMORY_BARRIER()
static uword CV() clib_cuckoo_path_peek_offset(const clib_cuckoo_path_t *path)
return the offset of the last element in the path
#define CLIB_CACHE_LINE_BYTES
static void CV() clib_cuckoo_bucket_tidy(CVT(clib_cuckoo_bucket)*b)
static int clib_cuckoo_bucket_aux_get_writer_flag(clib_cuckoo_bucket_aux_t aux)
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_pack(u64 version, int use_count, int writer_flag)
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)
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".