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 #include <vppinfra/linux/syscall.h> 39 #define F_LINUX_SPECIFIC_BASE 1024 40 #define F_ADD_SEALS (F_LINUX_SPECIFIC_BASE + 9) 41 #define F_SEAL_SHRINK (2) 43 #define BIHASH_FREELIST_LENGTH 17 47 #ifndef BIHASH_LOG2_HUGEPAGE_SIZE 48 #define BIHASH_LOG2_HUGEPAGE_SIZE 21 52 #define __bv(a,b) _bv(a,b) 53 #define BV(a) __bv(a,BIHASH_TYPE) 55 #define _bvt(a,b) a##b##_t 56 #define __bvt(a,b) _bvt(a,b) 57 #define BVT(a) __bvt(a,BIHASH_TYPE) 59 #define _bvs(a,b) struct a##b 60 #define __bvs(a,b) _bvs(a,b) 61 #define BVS(a) __bvs(a,BIHASH_TYPE) 64 #define OVERFLOW_ASSERT(x) ASSERT(((x) & 0xFFFFFFFF00000000ULL) == 0) 65 #define u64_to_pointer(x) (void *)(u32)((x)) 66 #define pointer_to_u64(x) (u64)(u32)((x)) 68 #define OVERFLOW_ASSERT(x) 69 #define u64_to_pointer(x) (void *)((x)) 70 #define pointer_to_u64(x) (u64)((x)) 73 typedef struct BV (clib_bihash_value)
82 #define BIHASH_BUCKET_OFFSET_BITS 36 98 }
BVT (clib_bihash_bucket);
108 u64 alloc_arena_next;
109 u64 alloc_arena_size;
110 u64 alloc_arena_mapped;
112 u64 alloc_lock_as_u64;
115 u64 freelists_as_u64;
120 })
BVT (clib_bihash_shared_header);
126 BVS (clib_bihash_alloc_chunk)
140 BVS (clib_bihash_alloc_chunk) * prev, *
next;
142 }
BVT (clib_bihash_alloc_chunk);
147 BVT (clib_bihash_bucket) * buckets;
148 volatile u32 *alloc_lock;
151 int *working_copy_lengths;
152 BVT (clib_bihash_bucket) saved_bucket;
160 BVT (clib_bihash_alloc_chunk) * chunks;
165 BVT (clib_bihash_shared_header) * sh;
168 BVT (clib_bihash_shared_header) sh;
172 volatile u8 instantiated;
180 #if BIHASH_ENABLE_STATS 181 void (*inc_stats_callback) (BVS (clib_bihash) *,
int stat_id,
u64 count);
184 void *inc_stats_context;
191 BVT (clib_bihash) *
h;
196 u8 instantiate_immediately;
197 u8 dont_add_to_all_bihash_list;
198 }
BVT (clib_bihash_init2_args);
203 #undef alloc_arena_next 204 #undef alloc_arena_size 205 #undef alloc_arena_mapped 207 #undef CLIB_BIHASH_READY_MAGIC 208 #define alloc_arena_next(h) (((h)->sh)->alloc_arena_next) 209 #define alloc_arena_size(h) (((h)->sh)->alloc_arena_size) 210 #define alloc_arena_mapped(h) (((h)->sh)->alloc_arena_mapped) 211 #define alloc_arena(h) ((h)->alloc_arena) 212 #define CLIB_BIHASH_READY_MAGIC 0xFEEDFACE 214 #undef alloc_arena_next 215 #undef alloc_arena_size 216 #undef alloc_arena_mapped 218 #undef CLIB_BIHASH_READY_MAGIC 219 #define alloc_arena_next(h) ((h)->sh.alloc_arena_next) 220 #define alloc_arena_size(h) ((h)->sh.alloc_arena_size) 221 #define alloc_arena_mapped(h) ((h)->sh.alloc_arena_mapped) 222 #define alloc_arena(h) ((h)->alloc_arena) 223 #define CLIB_BIHASH_READY_MAGIC 0 226 #ifndef BIHASH_STAT_IDS 227 #define BIHASH_STAT_IDS 1 229 #define foreach_bihash_stat \ 239 _(working_copy_lost) \ 244 #define _(a) BIHASH_STAT_##a, 248 }
BVT (clib_bihash_stat_id);
251 static inline void BV (clib_bihash_increment_stat) (
BVT (clib_bihash) *
h,
254 #if BIHASH_ENABLE_STATS 256 h->inc_stats_callback (h, stat_id,
count);
260 #if BIHASH_ENABLE_STATS 261 static inline void BV (clib_bihash_set_stats_callback)
262 (
BVT (clib_bihash) *
h, void (*cb) (
BVT (clib_bihash) *, int,
u64),
265 h->inc_stats_callback = cb;
266 h->inc_stats_context =
ctx;
271 static inline void BV (clib_bihash_alloc_lock) (
BVT (clib_bihash) *
h)
273 while (__atomic_test_and_set (h->alloc_lock, __ATOMIC_ACQUIRE))
277 static inline void BV (clib_bihash_alloc_unlock) (
BVT (clib_bihash) *
h)
279 __atomic_clear (h->alloc_lock, __ATOMIC_RELEASE);
282 static inline void BV (clib_bihash_lock_bucket) (
BVT (clib_bihash_bucket) *
b)
285 BVT (clib_bihash_bucket)
mask = { .lock = 1 };
300 static inline void BV (clib_bihash_unlock_bucket)
301 (
BVT (clib_bihash_bucket) *
b)
315 static inline int BV (clib_bihash_bucket_is_empty)
316 (
BVT (clib_bihash_bucket) *
b)
320 return b->offset == 0;
322 return (
b->log2_pages == 0 &&
b->refcnt == 1);
330 hp = (
u8 *) (
uword) alloc_arena (h);
342 void BV (clib_bihash_init2) (
BVT (clib_bihash_init2_args) *
a);
345 void BV (clib_bihash_initiator_init_svm)
347 void BV (clib_bihash_responder_init_svm)
348 (
BVT (clib_bihash) *
h,
char *
name,
int fd);
351 void BV (clib_bihash_set_kvp_format_fn) (
BVT (clib_bihash) *
h,
357 BVT (clib_bihash_kv) * add_v,
int is_add);
358 int BV (clib_bihash_add_or_overwrite_stale) (
BVT (clib_bihash) *
h,
359 BVT (clib_bihash_kv) * add_v,
360 int (*is_stale_cb) (
BVT 364 int BV (clib_bihash_search) (
BVT (clib_bihash) *
h,
365 BVT (clib_bihash_kv) * search_v,
366 BVT (clib_bihash_kv) * return_v);
368 int BV (clib_bihash_is_initialised) (
const BVT (clib_bihash) *
h);
370 #define BIHASH_WALK_STOP 0 371 #define BIHASH_WALK_CONTINUE 1 388 BVT (clib_bihash_bucket) *
389 BV (clib_bihash_get_bucket) (
BVT (clib_bihash) *
h,
u64 hash)
391 #if BIHASH_KVP_AT_BUCKET_LEVEL 393 offset = (hash & (h->nbuckets - 1));
394 offset = offset * (
sizeof (
BVT (clib_bihash_bucket))
396 return ((
BVT (clib_bihash_bucket) *) (((
u8 *) h->buckets) + offset));
398 return h->buckets + (hash & (h->nbuckets - 1));
403 (
BVT (clib_bihash) *
h,
u64 hash,
BVT (clib_bihash_kv) * key_result)
406 BVT (clib_bihash_bucket) *
b;
410 static const BVT (clib_bihash_bucket)
mask = {
416 #if BIHASH_LAZY_INSTANTIATE 421 b = BV (clib_bihash_get_bucket) (
h, hash);
428 volatile BVT (clib_bihash_bucket) * bv =
b;
441 limit <<=
b->log2_pages;
446 for (i = 0; i < limit; i++)
448 if (BV (clib_bihash_key_compare) (v->kvp[
i].key, key_result->key))
450 *key_result = v->kvp[
i];
458 (
BVT (clib_bihash) *
h,
BVT (clib_bihash_kv) * key_result)
462 hash = BV (clib_bihash_hash) (key_result);
468 (
BVT (clib_bihash) *
h,
u64 hash)
476 (
BVT (clib_bihash) *
h,
u64 hash)
479 BVT (clib_bihash_bucket) *
b;
481 #if BIHASH_LAZY_INSTANTIATE 486 b = BV (clib_bihash_get_bucket) (
h, hash);
500 static inline int BV (clib_bihash_search_inline_2_with_hash)
501 (
BVT (clib_bihash) *
h,
502 u64 hash,
BVT (clib_bihash_kv) * search_key,
BVT (clib_bihash_kv) * valuep)
505 BVT (clib_bihash_bucket) *
b;
509 static const BVT (clib_bihash_bucket)
mask = {
517 #if BIHASH_LAZY_INSTANTIATE 522 b = BV (clib_bihash_get_bucket) (
h, hash);
529 volatile BVT (clib_bihash_bucket) * bv =
b;
542 limit <<=
b->log2_pages;
547 for (i = 0; i < limit; i++)
549 if (BV (clib_bihash_key_compare) (v->kvp[
i].key, search_key->key))
559 (
BVT (clib_bihash) *
h,
560 BVT (clib_bihash_kv) * search_key,
BVT (clib_bihash_kv) * valuep)
564 hash = BV (clib_bihash_hash) (search_key);
566 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 CLIB_CACHE_LINE_ALIGN_MARK(mark)
#define BIHASH_KVP_PER_PAGE
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
Fixed length block allocator.
__clib_export void ** clib_all_bihashes
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.
BVT(clib_bihash)
The table of adjacencies indexed by the rewrite string.
#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.
__clib_export void clib_bihash_copied(void *dst, void *src)
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)
template key/value backing page structure
struct clib_bihash_value offset
template key/value backing page structure
__clib_export clib_mem_heap_t * clib_all_bihash_set_heap(void)
static void * clib_bihash_get_value(clib_bihash *h, uword offset)
Get pointer to value page given its clib mheap offset.
#define CLIB_CACHE_LINE_BYTES
#define STATIC_ASSERT_SIZEOF(d, s)