Add prefetch inlines, update bi-hash doc tags

Change-Id: I2e9d01ccba5288e89b886464436097d3cb7d2d18
Signed-off-by: Dave Barach <dave@barachs.net>

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)