23 #ifndef __included_bihash_template_h__ 24 #define __included_bihash_template_h__ 33 #error BIHASH_TYPE not defined 36 #ifdef BIHASH_32_64_SVM 37 #undef HAVE_MEMFD_CREATE 40 #define F_LINUX_SPECIFIC_BASE 1024 41 #define F_ADD_SEALS (F_LINUX_SPECIFIC_BASE + 9) 42 #define F_SEAL_SHRINK (2) 44 #define BIHASH_FREELIST_LENGTH 17 48 #ifndef BIHASH_LOG2_HUGEPAGE_SIZE 49 #define BIHASH_LOG2_HUGEPAGE_SIZE 21 53 #define __bv(a,b) _bv(a,b) 54 #define BV(a) __bv(a,BIHASH_TYPE) 56 #define _bvt(a,b) a##b##_t 57 #define __bvt(a,b) _bvt(a,b) 58 #define BVT(a) __bvt(a,BIHASH_TYPE) 60 #define _bvs(a,b) struct a##b 61 #define __bvs(a,b) _bvs(a,b) 62 #define BVS(a) __bvs(a,BIHASH_TYPE) 65 #define OVERFLOW_ASSERT(x) ASSERT(((x) & 0xFFFFFFFF00000000ULL) == 0) 66 #define u64_to_pointer(x) (void *)(u32)((x)) 67 #define pointer_to_u64(x) (u64)(u32)((x)) 69 #define OVERFLOW_ASSERT(x) 70 #define u64_to_pointer(x) (void *)((x)) 71 #define pointer_to_u64(x) (u64)((x)) 74 typedef struct BV (clib_bihash_value)
83 #define BIHASH_BUCKET_OFFSET_BITS 36 99 }
BVT (clib_bihash_bucket);
109 u64 alloc_arena_next;
110 u64 alloc_arena_size;
111 u64 alloc_arena_mapped;
113 u64 alloc_lock_as_u64;
116 u64 freelists_as_u64;
121 })
BVT (clib_bihash_shared_header);
129 BVT (clib_bihash_bucket) * buckets;
130 volatile u32 *alloc_lock;
133 int *working_copy_lengths;
134 BVT (clib_bihash_bucket) saved_bucket;
144 BVT (clib_bihash_shared_header) * sh;
147 BVT (clib_bihash_shared_header) sh;
151 volatile u8 instantiated;
159 #if BIHASH_ENABLE_STATS 160 void (*inc_stats_callback) (BVS (clib_bihash) *,
int stat_id,
u64 count);
163 void *inc_stats_context;
170 BVT (clib_bihash) *
h;
175 u8 instantiate_immediately;
176 u8 dont_add_to_all_bihash_list;
177 }
BVT (clib_bihash_init2_args);
182 #undef alloc_arena_next 183 #undef alloc_arena_size 184 #undef alloc_arena_mapped 186 #undef CLIB_BIHASH_READY_MAGIC 187 #define alloc_arena_next(h) (((h)->sh)->alloc_arena_next) 188 #define alloc_arena_size(h) (((h)->sh)->alloc_arena_size) 189 #define alloc_arena_mapped(h) (((h)->sh)->alloc_arena_mapped) 190 #define alloc_arena(h) ((h)->alloc_arena) 191 #define CLIB_BIHASH_READY_MAGIC 0xFEEDFACE 193 #undef alloc_arena_next 194 #undef alloc_arena_size 195 #undef alloc_arena_mapped 197 #undef CLIB_BIHASH_READY_MAGIC 198 #define alloc_arena_next(h) ((h)->sh.alloc_arena_next) 199 #define alloc_arena_size(h) ((h)->sh.alloc_arena_size) 200 #define alloc_arena_mapped(h) ((h)->sh.alloc_arena_mapped) 201 #define alloc_arena(h) ((h)->alloc_arena) 202 #define CLIB_BIHASH_READY_MAGIC 0 205 #ifndef BIHASH_STAT_IDS 206 #define BIHASH_STAT_IDS 1 208 #define foreach_bihash_stat \ 218 _(working_copy_lost) \ 223 #define _(a) BIHASH_STAT_##a, 227 }
BVT (clib_bihash_stat_id);
230 static inline void BV (clib_bihash_increment_stat) (
BVT (clib_bihash) *
h,
233 #if BIHASH_ENABLE_STATS 235 h->inc_stats_callback (h, stat_id,
count);
239 #if BIHASH_ENABLE_STATS 240 static inline void BV (clib_bihash_set_stats_callback)
241 (
BVT (clib_bihash) *
h, void (*cb) (
BVT (clib_bihash) *, int,
u64),
244 h->inc_stats_callback = cb;
245 h->inc_stats_context =
ctx;
250 static inline void BV (clib_bihash_alloc_lock) (
BVT (clib_bihash) *
h)
252 while (__atomic_test_and_set (h->alloc_lock, __ATOMIC_ACQUIRE))
256 static inline void BV (clib_bihash_alloc_unlock) (
BVT (clib_bihash) *
h)
258 __atomic_clear (h->alloc_lock, __ATOMIC_RELEASE);
261 static inline void BV (clib_bihash_lock_bucket) (
BVT (clib_bihash_bucket) * b)
264 BVT (clib_bihash_bucket) mask = { .lock = 1 };
279 static inline void BV (clib_bihash_unlock_bucket)
280 (
BVT (clib_bihash_bucket) * b)
294 static inline int BV (clib_bihash_bucket_is_empty)
295 (
BVT (clib_bihash_bucket) * b)
299 return b->offset == 0;
301 return (b->log2_pages == 0 && b->refcnt == 1);
309 hp = (
u8 *) (
uword) alloc_arena (h);
318 void BV (clib_bihash_init2) (
BVT (clib_bihash_init2_args) *
a);
321 void BV (clib_bihash_master_init_svm)
323 void BV (clib_bihash_slave_init_svm)
324 (
BVT (clib_bihash) *
h,
char *
name,
int fd);
327 void BV (clib_bihash_set_kvp_format_fn) (
BVT (clib_bihash) *
h,
333 BVT (clib_bihash_kv) * add_v,
int is_add);
334 int BV (clib_bihash_add_or_overwrite_stale) (
BVT (clib_bihash) *
h,
335 BVT (clib_bihash_kv) * add_v,
336 int (*is_stale_cb) (
BVT 340 int BV (clib_bihash_search) (
BVT (clib_bihash) *
h,
341 BVT (clib_bihash_kv) * search_v,
342 BVT (clib_bihash_kv) * return_v);
344 #define BIHASH_WALK_STOP 0 345 #define BIHASH_WALK_CONTINUE 1 362 BVT (clib_bihash_bucket) *
363 BV (clib_bihash_get_bucket) (
BVT (clib_bihash) *
h,
u64 hash)
365 #if BIHASH_KVP_AT_BUCKET_LEVEL 367 offset = (hash & (h->nbuckets - 1));
368 offset = offset * (
sizeof (
BVT (clib_bihash_bucket))
370 return ((
BVT (clib_bihash_bucket) *) (((
u8 *) h->buckets) + offset));
373 return h->buckets + (hash & (h->nbuckets - 1));
377 (
BVT (clib_bihash) *
h,
u64 hash,
BVT (clib_bihash_kv) * key_result)
380 BVT (clib_bihash_bucket) * b;
384 static const BVT (clib_bihash_bucket) mask = {
390 #if BIHASH_LAZY_INSTANTIATE 395 b = BV (clib_bihash_get_bucket) (
h, hash);
402 volatile BVT (clib_bihash_bucket) * bv = b;
415 limit <<= b->log2_pages;
417 v +=
extract_bits (hash, h->log2_nbuckets, b->log2_pages);
420 for (i = 0; i < limit; i++)
422 if (BV (clib_bihash_key_compare) (v->kvp[
i].key, key_result->key))
424 *key_result = v->kvp[
i];
432 (
BVT (clib_bihash) *
h,
BVT (clib_bihash_kv) * key_result)
436 hash = BV (clib_bihash_hash) (key_result);
442 (
BVT (clib_bihash) *
h,
u64 hash)
450 (
BVT (clib_bihash) *
h,
u64 hash)
453 BVT (clib_bihash_bucket) * b;
455 #if BIHASH_LAZY_INSTANTIATE 460 b = BV (clib_bihash_get_bucket) (
h, hash);
468 v +=
extract_bits (hash, h->log2_nbuckets, b->log2_pages);
474 static inline int BV (clib_bihash_search_inline_2_with_hash)
475 (
BVT (clib_bihash) *
h,
476 u64 hash,
BVT (clib_bihash_kv) * search_key,
BVT (clib_bihash_kv) * valuep)
479 BVT (clib_bihash_bucket) * b;
483 static const BVT (clib_bihash_bucket) mask = {
491 #if BIHASH_LAZY_INSTANTIATE 496 b = BV (clib_bihash_get_bucket) (
h, hash);
503 volatile BVT (clib_bihash_bucket) * bv = b;
516 limit <<= b->log2_pages;
518 v +=
extract_bits (hash, h->log2_nbuckets, b->log2_pages);
521 for (i = 0; i < limit; i++)
523 if (BV (clib_bihash_key_compare) (v->kvp[
i].key, search_key->key))
533 (
BVT (clib_bihash) *
h,
534 BVT (clib_bihash_kv) * search_key,
BVT (clib_bihash_kv) * valuep)
538 hash = BV (clib_bihash_hash) (search_key);
540 return BV (clib_bihash_search_inline_2_with_hash) (
h, hash, search_key,
int clib_bihash_search_inline_with_hash(clib_bihash *h, u64 hash, clib_bihash_kv *in_out_kv)
Search a bi-hash table, use supplied hash code.
u8 pad[3]
log2 (size of the packing page block)
#define BIHASH_KVP_PER_PAGE
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
Fixed length block allocator.
int clib_bihash_add_del(clib_bihash *h, clib_bihash_kv *add_v, int is_add)
Add or delete a (key,value) pair from a bi-hash table.
#define clib_atomic_fetch_or(a, b)
static uword clib_bihash_get_offset(clib_bihash *h, void *v)
Get clib mheap offset given a pointer.
int(* clib_bihash_foreach_key_value_pair_cb)(clib_bihash_kv *kv, void *ctx)
void clib_bihash_foreach_key_value_pair(clib_bihash *h, clib_bihash_foreach_key_value_pair_cb *callback, void *arg)
Visit active (key,value) pairs in a bi-hash table.
int clib_bihash_search_inline(clib_bihash *h, clib_bihash_kv *in_out_kv)
Search a bi-hash table.
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
void clib_bihash_prefetch_bucket(clib_bihash *h, u64 hash)
Prefetch a bi-hash bucket given a hash code.
#define BIHASH_KVP_AT_BUCKET_LEVEL
#define CLIB_PREFETCH(addr, size, type)
sll srl srl sll sra u16x4 i
void clib_bihash_prefetch_data(clib_bihash *h, u64 hash)
Prefetch bi-hash (key,value) data given a hash code.
int clib_bihash_search_inline_2(clib_bihash *h, clib_bihash_kv *search_key, clib_bihash_kv *valuep)
Search a bi-hash table.
#define BIHASH_BUCKET_PREFETCH_CACHE_LINES
static uword extract_bits(uword x, int start, int count)
void clib_bihash_copied(void *dst, void *src)
template key/value backing page structure
struct clib_bihash_value offset
template key/value backing page structure
static void * clib_bihash_get_value(clib_bihash *h, uword offset)
Get pointer to value page given its clib mheap offset.
void ** clib_all_bihashes
#define CLIB_CACHE_LINE_BYTES
void * clib_all_bihash_set_heap(void)
#define STATIC_ASSERT_SIZEOF(d, s)