Add a bihash prefetchable bucket-level cache

According to Maciek, the easiest way to leverage the csit "performance
trend" job is to actually merge the patch once verified. Manual
testing indicates that the patch improves l2 path performance. Other
use-cases are TBD. It's possible that we'll need to back out the patch
depending on what happens.

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

11 files changed, 329 insertions, 44 deletions

diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c
index 527f9114..8fde6f9f 100644
--- a/src/vnet/fib/ip6_fib.c
+++ b/src/vnet/fib/ip6_fib.c
@@ -200,7 +200,7 @@ ip6_fib_table_lookup (u32 fib_index,
 		      const ip6_address_t *addr,
 		      u32 len)
 {
-    const ip6_fib_table_instance_t *table;
+    ip6_fib_table_instance_t *table;
     BVT(clib_bihash_kv) kv, value;
     int i, n_p, rv;
     u64 fib;
@@ -246,7 +246,7 @@ ip6_fib_table_lookup_exact_match (u32 fib_index,
 				  const ip6_address_t *addr,
 				  u32 len)
 {
-    const ip6_fib_table_instance_t *table;
+    ip6_fib_table_instance_t *table;
     BVT(clib_bihash_kv) kv, value;
     ip6_address_t *mask;
     u64 fib;
diff --git a/src/vnet/fib/ip6_fib.h b/src/vnet/fib/ip6_fib.h
index 9789da4f..aad8305c 100644
--- a/src/vnet/fib/ip6_fib.h
+++ b/src/vnet/fib/ip6_fib.h
@@ -68,7 +68,7 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im,
                              u32 fib_index,
                              const ip6_address_t * dst)
 {
-    const ip6_fib_table_instance_t *table;
+    ip6_fib_table_instance_t *table;
     int i, len;
     int rv;
     BVT(clib_bihash_kv) kv, value;
diff --git a/src/vnet/l2/l2_fib.c b/src/vnet/l2/l2_fib.c
index 4ed16987..7e59b098 100644
--- a/src/vnet/l2/l2_fib.c
+++ b/src/vnet/l2/l2_fib.c
@@ -66,7 +66,7 @@ l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
 {
   l2fib_main_t *msm = &l2fib_main;
   BVT (clib_bihash) * h = &msm->mac_table;
-  clib_bihash_bucket_t *b;
+  BVT (clib_bihash_bucket) * b;
   BVT (clib_bihash_value) * v;
   l2fib_entry_key_t key;
   l2fib_entry_result_t result;
@@ -108,7 +108,7 @@ show_l2fib (vlib_main_t * vm,
   l2fib_main_t *msm = &l2fib_main;
   l2_bridge_domain_t *bd_config;
   BVT (clib_bihash) * h = &msm->mac_table;
-  clib_bihash_bucket_t *b;
+  BVT (clib_bihash_bucket) * b;
   BVT (clib_bihash_value) * v;
   l2fib_entry_key_t key;
   l2fib_entry_result_t result;
@@ -961,7 +961,7 @@ l2fib_mac_age_scanner_process (vlib_main_t * vm, vlib_node_runtime_t * rt,
 
 	  if (i < (h->nbuckets - 3))
 	    {
-	      clib_bihash_bucket_t *b = &h->buckets[i + 3];
+	      BVT (clib_bihash_bucket) * b = &h->buckets[i + 3];
 	      CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, LOAD);
 	      b = &h->buckets[i + 1];
 	      if (b->offset)
@@ -972,7 +972,7 @@ l2fib_mac_age_scanner_process (vlib_main_t * vm, vlib_node_runtime_t * rt,
 		}
 	    }
 
-	  clib_bihash_bucket_t *b = &h->buckets[i];
+	  BVT (clib_bihash_bucket) * b = &h->buckets[i];
 	  if (b->offset == 0)
 	    continue;
 	  BVT (clib_bihash_value) * v =
diff --git a/src/vppinfra.am b/src/vppinfra.am
index 785445a6..533bacd6 100644
--- a/src/vppinfra.am
+++ b/src/vppinfra.am
@@ -42,6 +42,8 @@ TESTS  +=  test_bihash_template \
 	   test_zvec
 endif
 
+TESTS += test_bihash_template
+
 noinst_PROGRAMS = $(TESTS)
 check_PROGRAMS	= $(TESTS)
 
diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h
index 6b1b563e..361665be 100644
--- a/src/vppinfra/bihash_16_8.h
+++ b/src/vppinfra/bihash_16_8.h
@@ -13,9 +13,12 @@
  * limitations under the License.
  */
 #undef BIHASH_TYPE
+#undef BIHASH_KVP_CACHE_SIZE
+#undef BIHASH_KVP_PER_PAGE
 
 #define BIHASH_TYPE _16_8
 #define BIHASH_KVP_PER_PAGE 4
+#define BIHASH_KVP_CACHE_SIZE 5
 
 #ifndef __included_bihash_16_8_h__
 #define __included_bihash_16_8_h__
diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h
index db77daa4..d0be028c 100644
--- a/src/vppinfra/bihash_24_8.h
+++ b/src/vppinfra/bihash_24_8.h
@@ -13,9 +13,12 @@
  * limitations under the License.
  */
 #undef BIHASH_TYPE
+#undef BIHASH_KVP_CACHE_SIZE
+#undef BIHASH_KVP_PER_PAGE
 
 #define BIHASH_TYPE _24_8
 #define BIHASH_KVP_PER_PAGE 4
+#define BIHASH_KVP_CACHE_SIZE 3
 
 #ifndef __included_bihash_24_8_h__
 #define __included_bihash_24_8_h__
diff --git a/src/vppinfra/bihash_48_8.h b/src/vppinfra/bihash_48_8.h
index 48079e0a..107bcace 100644
--- a/src/vppinfra/bihash_48_8.h
+++ b/src/vppinfra/bihash_48_8.h
@@ -14,9 +14,12 @@
  */
 
 #undef BIHASH_TYPE
+#undef BIHASH_KVP_CACHE_SIZE
+#undef BIHASH_KVP_PER_PAGE
 
 #define BIHASH_TYPE _48_8
 #define BIHASH_KVP_PER_PAGE 4
+#define BIHASH_KVP_CACHE_SIZE 2
 
 #ifndef __included_bihash_48_8_h__
 #define __included_bihash_48_8_h__
diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h
index 68049351..f81002d6 100644
--- a/src/vppinfra/bihash_8_8.h
+++ b/src/vppinfra/bihash_8_8.h
@@ -13,9 +13,12 @@
  * limitations under the License.
  */
 #undef BIHASH_TYPE
+#undef BIHASH_KVP_CACHE_SIZE
+#undef BIHASH_KVP_PER_PAGE
 
 #define BIHASH_TYPE _8_8
 #define BIHASH_KVP_PER_PAGE 4
+#define BIHASH_KVP_CACHE_SIZE 5
 
 #ifndef __included_bihash_8_8_h__
 #define __included_bihash_8_8_h__
diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index 004e8a9a..e3a5759d 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -19,12 +19,15 @@ void BV (clib_bihash_init)
   (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
 {
   void *oldheap;
+  int i;
 
   nbuckets = 1 << (max_log2 (nbuckets));
 
   h->name = (u8 *) name;
   h->nbuckets = nbuckets;
   h->log2_nbuckets = max_log2 (nbuckets);
+  h->cache_hits = 0;
+  h->cache_misses = 0;
 
   h->mheap = mheap_alloc (0 /* use VM */ , memory_size);
 
@@ -33,6 +36,9 @@ void BV (clib_bihash_init)
   h->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES,
 					   CLIB_CACHE_LINE_BYTES);
 
+  for (i = 0; i < nbuckets; i++)
+    BV (clib_bihash_reset_cache) (h->buckets + i);
+
   clib_mem_set_heap (oldheap);
 }
 
@@ -87,10 +93,10 @@ BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
 }
 
 static inline void
-BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
+BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
 {
   BVT (clib_bihash_value) * v;
-  clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8)));
+  BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8)));
   void *oldheap;
   BVT (clib_bihash_value) * working_copy;
   u32 thread_index = os_get_thread_index ();
@@ -129,6 +135,9 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
 
   clib_mem_set_heap (oldheap);
 
+  /* Turn off the cache */
+  BV (clib_bihash_cache_enable_disable) (b, 0);
+
   v = BV (clib_bihash_get_value) (h, b->offset);
 
   clib_memcpy (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
@@ -235,7 +244,7 @@ int BV (clib_bihash_add_del)
   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 {
   u32 bucket_index;
-  clib_bihash_bucket_t *b, tmp_b;
+  BVT (clib_bihash_bucket) * b, tmp_b;
   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
   int rv = 0;
   int i, limit;
@@ -276,6 +285,7 @@ int BV (clib_bihash_add_del)
       goto unlock;
     }
 
+  /* Note: this leaves the cache disabled */
   BV (make_working_copy) (h, b);
 
   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
@@ -405,19 +415,22 @@ expand_ok:
   BV (value_free) (h, v, old_log2_pages);
 
 unlock:
+  BV (clib_bihash_reset_cache) (b);
+  BV (clib_bihash_cache_enable_disable) (b, 1 /* enable */ );
   CLIB_MEMORY_BARRIER ();
   h->writer_lock[0] = 0;
   return rv;
 }
 
 int BV (clib_bihash_search)
-  (const BVT (clib_bihash) * h,
+  (BVT (clib_bihash) * h,
    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 {
   u64 hash;
   u32 bucket_index;
   BVT (clib_bihash_value) * v;
-  clib_bihash_bucket_t *b;
+  BVT (clib_bihash_kv) * kvp;
+  BVT (clib_bihash_bucket) * b;
   int i, limit;
 
   ASSERT (valuep);
@@ -430,6 +443,22 @@ int BV (clib_bihash_search)
   if (b->offset == 0)
     return -1;
 
+  /* Check the cache, if currently enabled */
+  if (PREDICT_TRUE (b->cache_lru & (1 << 15)))
+    {
+      limit = BIHASH_KVP_CACHE_SIZE;
+      kvp = b->cache;
+      for (i = 0; i < limit; i++)
+	{
+	  if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key))
+	    {
+	      *valuep = kvp[i];
+	      h->cache_hits++;
+	      return 0;
+	    }
+	}
+    }
+
   hash >>= h->log2_nbuckets;
 
   v = BV (clib_bihash_get_value) (h, b->offset);
@@ -442,18 +471,50 @@ int BV (clib_bihash_search)
     {
       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 	{
+	  u8 cache_slot;
 	  *valuep = v->kvp[i];
+
+	  /* Shut off the cache */
+	  BV (clib_bihash_cache_enable_disable) (b, 0);
+	  CLIB_MEMORY_BARRIER ();
+
+	  cache_slot = BV (clib_bihash_get_lru) (b);
+	  b->cache[cache_slot] = v->kvp[i];
+	  BV (clib_bihash_update_lru) (b, cache_slot);
+
+	  /* Reenable the cache */
+	  BV (clib_bihash_cache_enable_disable) (b, 1);
+	  h->cache_misses++;
 	  return 0;
 	}
     }
   return -1;
 }
 
+u8 *BV (format_bihash_lru) (u8 * s, va_list * args)
+{
+  int i;
+  BVT (clib_bihash_bucket) * b = va_arg (*args, BVT (clib_bihash_bucket) *);
+  u16 cache_lru = b->cache_lru;
+
+  s = format (s, "cache %s, order ", cache_lru & (1 << 15) ? "on" : "off");
+
+  for (i = 0; i < BIHASH_KVP_CACHE_SIZE; i++)
+    s = format (s, "[%d] ", ((cache_lru >> (3 * i)) & 7));
+  return (s);
+}
+
+void
+BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b, u8 slot)
+{
+  BV (clib_bihash_update_lru) (b, slot);
+}
+
 u8 *BV (format_bihash) (u8 * s, va_list * args)
 {
   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
   int verbose = va_arg (*args, int);
-  clib_bihash_bucket_t *b;
+  BVT (clib_bihash_bucket) * b;
   BVT (clib_bihash_value) * v;
   int i, j, k;
   u64 active_elements = 0;
@@ -503,7 +564,8 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
   s = format (s, "    %lld active elements\n", active_elements);
   s = format (s, "    %d free lists\n", vec_len (h->freelists));
   s = format (s, "    %d linear search buckets\n", h->linear_buckets);
-
+  s = format (s, "    %lld cache hits, %lld cache misses\n",
+	      h->cache_hits, h->cache_misses);
   return s;
 }
 
@@ -511,7 +573,7 @@ void BV (clib_bihash_foreach_key_value_pair)
   (BVT (clib_bihash) * h, void *callback, void *arg)
 {
   int i, j, k;
-  clib_bihash_bucket_t *b;
+  BVT (clib_bihash_bucket) * b;
   BVT (clib_bihash_value) * v;
   void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
 
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index 4ea14ff0..feb6fb68 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -48,12 +48,10 @@ typedef struct BV (clib_bihash_value)
   };
 } BVT (clib_bihash_value);
 
-/*
- * This is shared across all uses of the template, so it needs
- * a "personal" #include recursion block
- */
-#ifndef __defined_clib_bihash_bucket_t__
-#define __defined_clib_bihash_bucket_t__
+#if BIHASH_KVP_CACHE_SIZE > 5
+#error Requested KVP cache LRU data exceeds 16 bits
+#endif
+
 typedef struct
 {
   union
@@ -62,36 +60,139 @@ typedef struct
     {
       u32 offset;
       u8 linear_search;
-      u8 pad[2];
       u8 log2_pages;
+      u16 cache_lru;
     };
     u64 as_u64;
   };
-} clib_bihash_bucket_t;
-#endif /* __defined_clib_bihash_bucket_t__ */
+    BVT (clib_bihash_kv) cache[BIHASH_KVP_CACHE_SIZE];
+} BVT (clib_bihash_bucket);
 
 typedef struct
 {
   BVT (clib_bihash_value) * values;
-  clib_bihash_bucket_t *buckets;
+  BVT (clib_bihash_bucket) * buckets;
   volatile u32 *writer_lock;
 
     BVT (clib_bihash_value) ** working_copies;
   int *working_copy_lengths;
-  clib_bihash_bucket_t saved_bucket;
+    BVT (clib_bihash_bucket) saved_bucket;
 
   u32 nbuckets;
   u32 log2_nbuckets;
   u32 linear_buckets;
   u8 *name;
 
+  u64 cache_hits;
+  u64 cache_misses;
+
     BVT (clib_bihash_value) ** freelists;
   void *mheap;
 
 } BVT (clib_bihash);
 
 
-static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h,
+static inline void
+BV (clib_bihash_update_lru) (BVT (clib_bihash_bucket) * b, u8 slot)
+{
+  u16 value, tmp, mask;
+  u8 found_lru_pos;
+  u16 save_hi;
+
+  if (BIHASH_KVP_CACHE_SIZE < 2)
+    return;
+
+  ASSERT (slot < BIHASH_KVP_CACHE_SIZE);
+
+  /* First, find the slot in cache_lru */
+  mask = slot;
+  if (BIHASH_KVP_CACHE_SIZE > 1)
+    mask |= slot << 3;
+  if (BIHASH_KVP_CACHE_SIZE > 2)
+    mask |= slot << 6;
+  if (BIHASH_KVP_CACHE_SIZE > 3)
+    mask |= slot << 9;
+  if (BIHASH_KVP_CACHE_SIZE > 4)
+    mask |= slot << 12;
+
+  value = b->cache_lru;
+  tmp = value ^ mask;
+
+  /* Already the most-recently used? */
+  if ((tmp & 7) == 0)
+    return;
+
+  found_lru_pos = ((tmp & (7 << 3)) == 0) ? 1 : 0;
+  if (BIHASH_KVP_CACHE_SIZE > 2)
+    found_lru_pos = ((tmp & (7 << 6)) == 0) ? 2 : found_lru_pos;
+  if (BIHASH_KVP_CACHE_SIZE > 3)
+    found_lru_pos = ((tmp & (7 << 9)) == 0) ? 3 : found_lru_pos;
+  if (BIHASH_KVP_CACHE_SIZE > 4)
+    found_lru_pos = ((tmp & (7 << 12)) == 0) ? 4 : found_lru_pos;
+
+  ASSERT (found_lru_pos);
+
+  /* create a mask to kill bits in or above slot */
+  mask = 0xFFFF << found_lru_pos;
+  mask <<= found_lru_pos;
+  mask <<= found_lru_pos;
+  mask ^= 0xFFFF;
+  tmp = value & mask;
+
+  /* Save bits above slot */
+  mask ^= 0xFFFF;
+  mask <<= 3;
+  save_hi = value & mask;
+
+  value = save_hi | (tmp << 3) | slot;
+
+  b->cache_lru = value;
+}
+
+void
+BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b,
+					u8 slot);
+
+static inline u8 BV (clib_bihash_get_lru) (BVT (clib_bihash_bucket) * b)
+{
+  return (b->cache_lru >> (3 * (BIHASH_KVP_CACHE_SIZE - 1))) & 7;
+}
+
+static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b)
+{
+  u16 initial_lru_value;
+
+  memset (b->cache, 0xff, sizeof (b->cache));
+
+  /*
+   * We'll want the cache to be loaded from slot 0 -> slot N, so
+   * the initial LRU order is reverse index order.
+   */
+  if (BIHASH_KVP_CACHE_SIZE == 1)
+    initial_lru_value = 0;
+  else if (BIHASH_KVP_CACHE_SIZE == 2)
+    initial_lru_value = (0 << 3) | (1 << 0);
+  else if (BIHASH_KVP_CACHE_SIZE == 3)
+    initial_lru_value = (0 << 6) | (1 << 3) | (2 << 0);
+  else if (BIHASH_KVP_CACHE_SIZE == 4)
+    initial_lru_value = (0 << 9) | (1 << 6) | (2 << 3) | (3 << 0);
+  else if (BIHASH_KVP_CACHE_SIZE == 5)
+    initial_lru_value = (0 << 12) | (1 << 9) | (2 << 6) | (3 << 3) | (4 << 0);
+
+  b->cache_lru = initial_lru_value;
+}
+
+static inline void BV (clib_bihash_cache_enable_disable)
+  (BVT (clib_bihash_bucket) * b, u8 enable)
+{
+  BVT (clib_bihash_bucket) tmp_b;
+  tmp_b.as_u64 = b->as_u64;
+  tmp_b.cache_lru &= 0x7FFF;
+  tmp_b.cache_lru |= enable << 15;
+  b->as_u64 = tmp_b.as_u64;
+}
+
+static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h,
 						uword offset)
 {
   u8 *hp = h->mheap;
@@ -100,7 +201,7 @@ static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h,
   return (void *) vp;
 }
 
-static inline uword BV (clib_bihash_get_offset) (const BVT (clib_bihash) * h,
+static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h,
 						 void *v)
 {
   u8 *hp, *vp;
@@ -119,7 +220,7 @@ 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_search) (const BVT (clib_bihash) * h,
+int BV (clib_bihash_search) (BVT (clib_bihash) * h,
 			     BVT (clib_bihash_kv) * search_v,
 			     BVT (clib_bihash_kv) * return_v);
 
@@ -128,18 +229,19 @@ void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h,
 
 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)
-  (const BVT (clib_bihash) * h, BVT (clib_bihash_kv) * kvp)
+  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result)
 {
   u64 hash;
   u32 bucket_index;
   BVT (clib_bihash_value) * v;
-  clib_bihash_bucket_t *b;
+  BVT (clib_bihash_bucket) * b;
+  BVT (clib_bihash_kv) * kvp;
   int i, limit;
 
-  hash = BV (clib_bihash_hash) (kvp);
+  hash = BV (clib_bihash_hash) (key_result);
 
   bucket_index = hash & (h->nbuckets - 1);
   b = &h->buckets[bucket_index];
@@ -147,6 +249,22 @@ static inline int BV (clib_bihash_search_inline)
   if (b->offset == 0)
     return -1;
 
+  /* Check the cache, if currently enabled */
+  if (PREDICT_TRUE (b->cache_lru & (1 << 15)))
+    {
+      limit = BIHASH_KVP_CACHE_SIZE;
+      kvp = b->cache;
+      for (i = 0; i < limit; i++)
+	{
+	  if (BV (clib_bihash_key_compare) (kvp[i].key, key_result->key))
+	    {
+	      *key_result = kvp[i];
+	      h->cache_hits++;
+	      return 0;
+	    }
+	}
+    }
+
   hash >>= h->log2_nbuckets;
 
   v = BV (clib_bihash_get_value) (h, b->offset);
@@ -159,9 +277,22 @@ static inline int BV (clib_bihash_search_inline)
 
   for (i = 0; i < limit; i++)
     {
-      if (BV (clib_bihash_key_compare) (v->kvp[i].key, kvp->key))
+      if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key))
 	{
-	  *kvp = v->kvp[i];
+	  u8 cache_slot;
+	  *key_result = v->kvp[i];
+
+	  /* Shut off the cache */
+	  BV (clib_bihash_cache_enable_disable) (b, 0);
+	  CLIB_MEMORY_BARRIER ();
+
+	  cache_slot = BV (clib_bihash_get_lru) (b);
+	  b->cache[cache_slot] = v->kvp[i];
+	  BV (clib_bihash_update_lru) (b, cache_slot);
+
+	  /* Reenable the cache */
+	  BV (clib_bihash_cache_enable_disable) (b, 1);
+	  h->cache_misses++;
 	  return 0;
 	}
     }
@@ -169,13 +300,14 @@ static inline int BV (clib_bihash_search_inline)
 }
 
 static inline int BV (clib_bihash_search_inline_2)
-  (const BVT (clib_bihash) * h,
+  (BVT (clib_bihash) * h,
    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 {
   u64 hash;
   u32 bucket_index;
   BVT (clib_bihash_value) * v;
-  clib_bihash_bucket_t *b;
+  BVT (clib_bihash_bucket) * b;
+  BVT (clib_bihash_kv) * kvp;
   int i, limit;
 
   ASSERT (valuep);
@@ -188,6 +320,22 @@ static inline int BV (clib_bihash_search_inline_2)
   if (b->offset == 0)
     return -1;
 
+  /* Check the cache, if currently enabled */
+  if (PREDICT_TRUE (b->cache_lru & (1 << 15)))
+    {
+      limit = BIHASH_KVP_CACHE_SIZE;
+      kvp = b->cache;
+      for (i = 0; i < limit; i++)
+	{
+	  if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key))
+	    {
+	      *valuep = kvp[i];
+	      h->cache_hits++;
+	      return 0;
+	    }
+	}
+    }
+
   hash >>= h->log2_nbuckets;
   v = BV (clib_bihash_get_value) (h, b->offset);
 
@@ -201,14 +349,26 @@ static inline int BV (clib_bihash_search_inline_2)
     {
       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 	{
+	  u8 cache_slot;
 	  *valuep = v->kvp[i];
+
+	  /* Shut off the cache */
+	  BV (clib_bihash_cache_enable_disable) (b, 0);
+	  CLIB_MEMORY_BARRIER ();
+
+	  cache_slot = BV (clib_bihash_get_lru) (b);
+	  b->cache[cache_slot] = v->kvp[i];
+	  BV (clib_bihash_update_lru) (b, cache_slot);
+
+	  /* Reenable the cache */
+	  BV (clib_bihash_cache_enable_disable) (b, 1);
+	  h->cache_misses++;
 	  return 0;
 	}
     }
   return -1;
 }
 
-
 #endif /* __included_bihash_template_h__ */
 
 /** @endcond */
diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c
index 1e262430..589c815d 100644
--- a/src/vppinfra/test_bihash_template.c
+++ b/src/vppinfra/test_bihash_template.c
@@ -237,11 +237,44 @@ test_bihash (test_main_t * tm)
 }
 
 clib_error_t *
+test_bihash_cache (test_main_t * tm)
+{
+  u32 lru;
+  BVT (clib_bihash_bucket) _b, *b = &_b;
+
+  BV (clib_bihash_reset_cache) (b);
+
+  fformat (stdout, "Initial LRU config: %U\n", BV (format_bihash_lru), b);
+
+  BV (clib_bihash_update_lru_not_inline) (b, 3);
+
+  fformat (stdout, "use slot 3, LRU config: %U\n", BV (format_bihash_lru), b);
+
+  BV (clib_bihash_update_lru) (b, 1);
+
+  fformat (stdout, "use slot 1 LRU config: %U\n", BV (format_bihash_lru), b);
+
+  lru = BV (clib_bihash_get_lru) (b);
+
+  fformat (stdout, "least-recently-used is %d\n", lru);
+
+  BV (clib_bihash_update_lru) (b, 4);
+
+  fformat (stdout, "use slot 4 LRU config: %U\n", BV (format_bihash_lru), b);
+
+  lru = BV (clib_bihash_get_lru) (b);
+
+  fformat (stdout, "least-recently-used is %d\n", lru);
+
+  return 0;
+}
+
+clib_error_t *
 test_bihash_main (test_main_t * tm)
 {
   unformat_input_t *i = tm->input;
   clib_error_t *error;
-  int test_vec64 = 0;
+  int which = 0;
 
   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
     {
@@ -261,7 +294,10 @@ test_bihash_main (test_main_t * tm)
       else if (unformat (i, "search %d", &tm->search_iter))
 	;
       else if (unformat (i, "vec64"))
-	test_vec64 = 1;
+	which = 1;
+      else if (unformat (i, "cache"))
+	which = 2;
+
       else if (unformat (i, "verbose"))
 	tm->verbose = 1;
       else
@@ -269,10 +305,23 @@ test_bihash_main (test_main_t * tm)
 				  format_unformat_error, i);
     }
 
-  if (test_vec64)
-    error = test_bihash_vec64 (tm);
-  else
-    error = test_bihash (tm);
+  switch (which)
+    {
+    case 0:
+      error = test_bihash (tm);
+      break;
+
+    case 1:
+      error = test_bihash_vec64 (tm);
+      break;
+
+    case 2:
+      error = test_bihash_cache (tm);
+      break;
+
+    default:
+      return clib_error_return (0, "no such test?");
+    }
 
   return error;
 }