diff options
| -rw-r--r-- | src/vppinfra/bihash_doc.h | 49 | ||||
| -rw-r--r-- | src/vppinfra/bihash_template.h | 53 |
2 files changed, 90 insertions, 12 deletions
diff --git a/src/vppinfra/bihash_doc.h b/src/vppinfra/bihash_doc.h index e6ab9db6d30..a7e70e9695c 100644 --- a/src/vppinfra/bihash_doc.h +++ b/src/vppinfra/bihash_doc.h @@ -78,7 +78,9 @@ typedef struct u8 *name; /**< hash table name */ BVT (clib_bihash_value) ** freelists; /**< power of two freelist vector */ - void *mheap; /**< clib memory heap */ + uword alloc_arena; /**< memory allocation arena */ + uword alloc_arena_next; /**< first available mem chunk */ + uword alloc_arena_size; /**< size of the arena */ } clib_bihash_t; /** Get pointer to value page given its clib mheap offset */ @@ -117,16 +119,51 @@ void clib_bihash_free (clib_bihash * h); int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add); +/** Search a bi-hash table, use supplied hash code + + @param h - the bi-hash table to search + @param hash - the hash code + @param in_out_kv - (key,value) pair containing the search key + @returns 0 on success (with in_out_kv set), < 0 on error +*/ +int clib_bihash_search_inline_with_hash + (clib_bihash * h, u64 hash, clib_bihash_kv * in_out_kv); + /** Search a bi-hash table @param h - the bi-hash table to search - @param search_v - (key,value) pair containing the search key - @param return_v - (key,value) pair which matches search_v.key - @returns 0 on success (with return_v set), < 0 on error + @param in_out_kv - (key,value) pair containing the search key + @returns 0 on success (with in_out_kv set), < 0 on error +*/ +int clib_bihash_search_inline (clib_bihash * h, clib_bihash_kv * in_out_kv); + +/** Prefetch a bi-hash bucket given a hash code + + @param h - the bi-hash table to search + @param hash - the hash code + @note see also clib_bihash_hash to compute the code */ -int clib_bihash_search (clib_bihash * h, - clib_bihash_kv * search_v, clib_bihash_kv * return_v); +void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash); +/** Prefetch bi-hash (key,value) data given a hash code + + @param h - the bi-hash table to search + @param hash - the hash code + @note assumes that the bucket has been prefetched, see + clib_bihash_prefetch_bucket +*/ +void clib_bihash_prefetch_data (clib_bihash * h, u64 hash); + +/** Search a bi-hash table + + @param h - the bi-hash table to search + @param search_key - (key,value) pair containing the search key + @param valuep - (key,value) set to search result + @returns 0 on success (with valuep set), < 0 on error + @note used in situations where key modification is not desired +*/ +int clib_bihash_search_inline_2 + (clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep); /** Visit active (key,value) pairs in a bi-hash table diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 81d9ffad41e..2101d44defe 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -26,6 +26,7 @@ #include <vppinfra/heap.h> #include <vppinfra/format.h> #include <vppinfra/pool.h> +#include <vppinfra/cache.h> #ifndef BIHASH_TYPE #error BIHASH_TYPE not defined @@ -91,7 +92,7 @@ typedef struct BVT (clib_bihash_value) ** freelists; /* - * Backing store allocation. Since bihash mananges its own + * Backing store allocation. Since bihash manages its own * freelists, we simple dole out memory at alloc_arena_next. */ uword alloc_arena; @@ -269,10 +270,9 @@ format_function_t BV (format_bihash); format_function_t BV (format_bihash_kvp); format_function_t BV (format_bihash_lru); -static inline int BV (clib_bihash_search_inline) - (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result) +static inline int BV (clib_bihash_search_inline_with_hash) + (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * key_result) { - u64 hash; u32 bucket_index; BVT (clib_bihash_value) * v; BVT (clib_bihash_bucket) * b; @@ -281,8 +281,6 @@ static inline int BV (clib_bihash_search_inline) #endif int i, limit; - hash = BV (clib_bihash_hash) (key_result); - bucket_index = hash & (h->nbuckets - 1); b = &h->buckets[bucket_index]; @@ -343,6 +341,49 @@ static inline int BV (clib_bihash_search_inline) return -1; } +static inline int BV (clib_bihash_search_inline) + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result) +{ + u64 hash; + + hash = BV (clib_bihash_hash) (key_result); + + return BV (clib_bihash_search_inline_with_hash) (h, hash, key_result); +} + +static inline void BV (clib_bihash_prefetch_bucket) + (BVT (clib_bihash) * h, u64 hash) +{ + u32 bucket_index; + BVT (clib_bihash_bucket) * b; + + bucket_index = hash & (h->nbuckets - 1); + b = &h->buckets[bucket_index]; + + CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, READ); +} + +static inline void BV (clib_bihash_prefetch_data) + (BVT (clib_bihash) * h, u64 hash) +{ + u32 bucket_index; + BVT (clib_bihash_value) * v; + BVT (clib_bihash_bucket) * b; + + bucket_index = hash & (h->nbuckets - 1); + b = &h->buckets[bucket_index]; + + if (PREDICT_FALSE (b->offset == 0)) + 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; + + CLIB_PREFETCH (v, CLIB_CACHE_LINE_BYTES, READ); +} + static inline int BV (clib_bihash_search_inline_2) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) |