X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;ds=inline;f=src%2Fvppinfra%2Fbihash_template.h;h=2a5c5861d88ac4965a85163f0f37978498a89941;hb=a8c720e301f3576506b2b284fe925b055398b638;hp=50b4af6571092bdc98b1618397be56eb5dd3d425;hpb=74ee18b0b33aad974705ae16739a86c48f3b966b;p=vpp.git diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 50b4af65710..2a5c5861d88 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -34,7 +34,6 @@ #endif #ifdef BIHASH_32_64_SVM -#undef HAVE_MEMFD_CREATE #include #include #define F_LINUX_SPECIFIC_BASE 1024 @@ -123,6 +122,25 @@ typedef CLIB_PACKED (struct { 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) { @@ -137,6 +155,9 @@ 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; @@ -149,11 +170,12 @@ BVS (clib_bihash) u64 alloc_arena; /* Base of the allocation arena */ volatile u8 instantiated; + u8 dont_add_to_all_bihash_list; /** * 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 @@ -171,7 +193,7 @@ typedef struct 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); @@ -312,20 +334,23 @@ static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h, 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); @@ -341,6 +366,8 @@ int BV (clib_bihash_search) (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 @@ -368,9 +395,9 @@ BV (clib_bihash_get_bucket) (BVT (clib_bihash) * h, u64 hash) 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) @@ -380,8 +407,15 @@ 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 @@ -397,15 +431,18 @@ static inline int BV (clib_bihash_search_inline_with_hash) 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++) { @@ -443,7 +480,7 @@ static inline void BV (clib_bihash_prefetch_data) BVT (clib_bihash_bucket) * b; #if BIHASH_LAZY_INSTANTIATE - if (PREDICT_FALSE (alloc_arena (h) == 0)) + if (PREDICT_FALSE (h->instantiated == 0)) return; #endif @@ -452,12 +489,13 @@ static inline void BV (clib_bihash_prefetch_data) 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) @@ -468,10 +506,17 @@ 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 @@ -487,14 +532,18 @@ static inline int BV (clib_bihash_search_inline_2_with_hash) 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++) {