STATIC_ASSERT_SIZEOF (BVT (clib_bihash_shared_header), 8 * sizeof (u64));
+typedef
+BVS (clib_bihash_alloc_chunk)
+{
+ CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
+
+ /* chunk size */
+ uword size;
+
+ /* pointer to the next allocation */
+ u8 *next_alloc;
+
+ /* number of bytes left in this chunk */
+ uword bytes_left;
+
+ /* doubly linked list of heap allocated chunks */
+ BVS (clib_bihash_alloc_chunk) * prev, *next;
+
+} BVT (clib_bihash_alloc_chunk);
+
typedef
BVS (clib_bihash)
{
u32 log2_nbuckets;
u64 memory_size;
u8 *name;
+ format_function_t *fmt_fn;
+ void *heap;
+ BVT (clib_bihash_alloc_chunk) * chunks;
u64 *freelists;
/**
* A custom format function to print the Key and Value of bihash_key instead of default hexdump
*/
- format_function_t *fmt_fn;
+ format_function_t *kvp_fmt_fn;
/** Optional statistics-gathering callback */
#if BIHASH_ENABLE_STATS
char *name;
u32 nbuckets;
uword memory_size;
- format_function_t *fmt_fn;
+ format_function_t *kvp_fmt_fn;
u8 instantiate_immediately;
u8 dont_add_to_all_bihash_list;
} BVT (clib_bihash_init2_args);
return vp - hp;
}
+#define BIHASH_ADD 1
+#define BIHASH_DEL 0
+
void BV (clib_bihash_init)
(BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size);
void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a);
#if BIHASH_32_64_SVM
-void BV (clib_bihash_master_init_svm)
+void BV (clib_bihash_initiator_init_svm)
(BVT (clib_bihash) * h, char *name, u32 nbuckets, u64 memory_size);
-void BV (clib_bihash_slave_init_svm)
+void BV (clib_bihash_responder_init_svm)
(BVT (clib_bihash) * h, char *name, int fd);
#endif
void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
- format_function_t * fmt_fn);
+ format_function_t * kvp_fmt_fn);
void BV (clib_bihash_free) (BVT (clib_bihash) * h);
BVT (clib_bihash_kv) * search_v,
BVT (clib_bihash_kv) * return_v);
+int BV (clib_bihash_is_initialised) (const BVT (clib_bihash) * h);
+
#define BIHASH_WALK_STOP 0
#define BIHASH_WALK_CONTINUE 1
offset = offset * (sizeof (BVT (clib_bihash_bucket))
+ (BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv))));
return ((BVT (clib_bihash_bucket) *) (((u8 *) h->buckets) + offset));
-#endif
-
+#else
return h->buckets + (hash & (h->nbuckets - 1));
+#endif
}
static inline int BV (clib_bihash_search_inline_with_hash)
BVT (clib_bihash_bucket) * b;
int i, limit;
+ /* *INDENT-OFF* */
+ static const BVT (clib_bihash_bucket) mask = {
+ .linear_search = 1,
+ .log2_pages = -1
+ };
+ /* *INDENT-ON* */
+
#if BIHASH_LAZY_INSTANTIATE
- if (PREDICT_FALSE (alloc_arena (h) == 0))
+ if (PREDICT_FALSE (h->instantiated == 0))
return -1;
#endif
CLIB_PAUSE ();
}
- hash >>= h->log2_nbuckets;
-
v = BV (clib_bihash_get_value) (h, b->offset);
/* If the bucket has unresolvable collisions, use linear search */
limit = BIHASH_KVP_PER_PAGE;
- v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
- if (PREDICT_FALSE (b->linear_search))
- limit <<= b->log2_pages;
+
+ if (PREDICT_FALSE (b->as_u64 & mask.as_u64))
+ {
+ if (PREDICT_FALSE (b->linear_search))
+ limit <<= b->log2_pages;
+ else
+ v += extract_bits (hash, h->log2_nbuckets, b->log2_pages);
+ }
for (i = 0; i < limit; i++)
{
BVT (clib_bihash_bucket) * b;
#if BIHASH_LAZY_INSTANTIATE
- if (PREDICT_FALSE (alloc_arena (h) == 0))
+ if (PREDICT_FALSE (h->instantiated == 0))
return;
#endif
if (PREDICT_FALSE (BV (clib_bihash_bucket_is_empty) (b)))
return;
- hash >>= h->log2_nbuckets;
v = BV (clib_bihash_get_value) (h, b->offset);
- v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
+ if (PREDICT_FALSE (b->log2_pages && b->linear_search == 0))
+ v += extract_bits (hash, h->log2_nbuckets, b->log2_pages);
- clib_prefetch_load (v);
+ CLIB_PREFETCH (v, BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv)),
+ LOAD);
}
static inline int BV (clib_bihash_search_inline_2_with_hash)
BVT (clib_bihash_bucket) * b;
int i, limit;
+/* *INDENT-OFF* */
+ static const BVT (clib_bihash_bucket) mask = {
+ .linear_search = 1,
+ .log2_pages = -1
+ };
+/* *INDENT-ON* */
+
ASSERT (valuep);
#if BIHASH_LAZY_INSTANTIATE
- if (PREDICT_FALSE (alloc_arena (h) == 0))
+ if (PREDICT_FALSE (h->instantiated == 0))
return -1;
#endif
CLIB_PAUSE ();
}
- hash >>= h->log2_nbuckets;
v = BV (clib_bihash_get_value) (h, b->offset);
/* If the bucket has unresolvable collisions, use linear search */
limit = BIHASH_KVP_PER_PAGE;
- v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
- if (PREDICT_FALSE (b->linear_search))
- limit <<= b->log2_pages;
+
+ if (PREDICT_FALSE (b->as_u64 & mask.as_u64))
+ {
+ if (PREDICT_FALSE (b->linear_search))
+ limit <<= b->log2_pages;
+ else
+ v += extract_bits (hash, h->log2_nbuckets, b->log2_pages);
+ }
for (i = 0; i < limit; i++)
{