X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Fbihash_template.h;h=e8a2c01cecedb3be1a6c9f038e93253f2733beb1;hb=21bc900c3498599a2ff1bd83a8482cf0682914d6;hp=b8e0a239013c0f5b8f3cd4bf2d39ad08730d9a95;hpb=801ec2a080d9414b3fab80906333bdb94b5d4043;p=vpp.git diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index b8e0a239013..e8a2c01cece 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); @@ -260,21 +282,19 @@ static inline void BV (clib_bihash_alloc_unlock) (BVT (clib_bihash) * h) static inline void BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b) { - BVT (clib_bihash_bucket) unlocked_bucket, locked_bucket; + /* *INDENT-OFF* */ + BVT (clib_bihash_bucket) mask = { .lock = 1 }; + /* *INDENT-ON* */ + u64 old; - locked_bucket.as_u64 = unlocked_bucket.as_u64 = b->as_u64; - unlocked_bucket.lock = 0; - locked_bucket.lock = 1; +try_again: + old = clib_atomic_fetch_or (&b->as_u64, mask.as_u64); - while (__atomic_compare_exchange_n (&b->as_u64, &unlocked_bucket.as_u64, - locked_bucket.as_u64, 1 /* weak */ , - __ATOMIC_ACQUIRE, - __ATOMIC_ACQUIRE) == 0) + if (PREDICT_FALSE (old & mask.as_u64)) { + /* somebody else flipped the bit, try again */ CLIB_PAUSE (); - locked_bucket.as_u64 = unlocked_bucket.as_u64 = b->as_u64; - unlocked_bucket.lock = 0; - locked_bucket.lock = 1; + goto try_again; } } @@ -314,35 +334,47 @@ 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); int BV (clib_bihash_add_del) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add); + +int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h, + BVT (clib_bihash_kv) * add_v, u64 hash, + int is_add); int BV (clib_bihash_add_or_overwrite_stale) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg); +int BV (clib_bihash_add_with_overwrite_cb) ( + BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, + void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *arg); 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 @@ -370,20 +402,28 @@ 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) (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * key_result) { + BVT (clib_bihash_kv) rv; BVT (clib_bihash_value) * v; 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 @@ -399,21 +439,27 @@ 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++) { if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key)) { - *key_result = v->kvp[i]; + rv = v->kvp[i]; + if (BV (clib_bihash_is_free) (&rv)) + return -1; + *key_result = rv; return 0; } } @@ -445,7 +491,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 @@ -454,26 +500,35 @@ 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) (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) { + BVT (clib_bihash_kv) rv; BVT (clib_bihash_value) * v; 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 @@ -489,20 +544,27 @@ 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++) { if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key)) { - *valuep = v->kvp[i]; + rv = v->kvp[i]; + if (BV (clib_bihash_is_free) (&rv)) + return -1; + *valuep = rv; return 0; } }