From 7cd468a3d7dee7d6c92f69a0bb7061ae208ec727 Mon Sep 17 00:00:00 2001
From: Damjan Marion <damarion@cisco.com>
Date: Mon, 19 Dec 2016 23:05:39 +0100
Subject: Reorganize source tree to use single autotools instance

Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23
Signed-off-by: Damjan Marion <damarion@cisco.com>
---
 src/vppinfra/test_bihash_template.c | 297 ++++++++++++++++++++++++++++++++++++
 1 file changed, 297 insertions(+)
 create mode 100644 src/vppinfra/test_bihash_template.c

(limited to 'src/vppinfra/test_bihash_template.c')

diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c
new file mode 100644
index 00000000..c505bd83
--- /dev/null
+++ b/src/vppinfra/test_bihash_template.c
@@ -0,0 +1,297 @@
+/*
+ * Copyright (c) 2015 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <vppinfra/time.h>
+#include <vppinfra/cache.h>
+#include <vppinfra/error.h>
+
+#include <vppinfra/bihash_8_8.h>
+#include <vppinfra/bihash_template.h>
+
+#include <vppinfra/bihash_template.c>
+
+typedef struct
+{
+  u64 seed;
+  u32 nbuckets;
+  u32 nitems;
+  u32 search_iter;
+  int careful_delete_tests;
+  int verbose;
+  int non_random_keys;
+  uword *key_hash;
+  u64 *keys;
+    BVT (clib_bihash) hash;
+  clib_time_t clib_time;
+
+  unformat_input_t *input;
+
+} test_main_t;
+
+test_main_t test_main;
+
+uword
+vl (void *v)
+{
+  return vec_len (v);
+}
+
+static clib_error_t *
+test_bihash (test_main_t * tm)
+{
+  int i, j;
+  uword *p;
+  uword total_searches;
+  f64 before, delta;
+  BVT (clib_bihash) * h;
+  BVT (clib_bihash_kv) kv;
+
+  h = &tm->hash;
+
+  BV (clib_bihash_init) (h, "test", tm->nbuckets, 3ULL << 30);
+
+  fformat (stdout, "Pick %lld unique %s keys...\n",
+	   tm->nitems, tm->non_random_keys ? "non-random" : "random");
+
+  for (i = 0; i < tm->nitems; i++)
+    {
+      u64 rndkey;
+
+      if (tm->non_random_keys == 0)
+	{
+
+	again:
+	  rndkey = random_u64 (&tm->seed);
+
+	  p = hash_get (tm->key_hash, rndkey);
+	  if (p)
+	    goto again;
+	}
+      else
+	rndkey = (u64) (i + 1) << 16;
+
+      hash_set (tm->key_hash, rndkey, i + 1);
+      vec_add1 (tm->keys, rndkey);
+    }
+
+  fformat (stdout, "Add items...\n");
+  for (i = 0; i < tm->nitems; i++)
+    {
+      kv.key = tm->keys[i];
+      kv.value = i + 1;
+
+      BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
+
+      if (tm->verbose > 1)
+	{
+	  fformat (stdout, "--------------------\n");
+	  fformat (stdout, "After adding key %llu value %lld...\n",
+		   tm->keys[i], (u64) (i + 1));
+	  fformat (stdout, "%U", BV (format_bihash), h,
+		   2 /* very verbose */ );
+	}
+    }
+
+  fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
+
+  fformat (stdout, "Search for items %d times...\n", tm->search_iter);
+
+  before = clib_time_now (&tm->clib_time);
+
+  for (j = 0; j < tm->search_iter; j++)
+    {
+      u64 hash1 = clib_xxhash (tm->keys[0]);
+
+      for (i = 0; i < tm->nitems; i++)
+	{
+	  if (i < (tm->nitems - 3))
+	    {
+	      clib_bihash_bucket_t *b;
+	      BVT (clib_bihash_value) * v;
+	      u64 hash2 = clib_xxhash (tm->keys[i + 3]);
+	      u32 bucket_index = hash2 & (h->nbuckets - 1);
+	      b = &h->buckets[bucket_index];
+	      CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, LOAD);
+
+	      bucket_index = hash1 & (h->nbuckets - 1);
+	      b = &h->buckets[bucket_index];
+	      v = BV (clib_bihash_get_value) (h, b->offset);
+	      hash1 >>= h->log2_nbuckets;
+	      hash1 = hash1 & ((1 << b->log2_pages) - 1);
+	      v += hash1;
+	      CLIB_PREFETCH (v, CLIB_CACHE_LINE_BYTES, LOAD);
+
+	      hash1 = hash2;
+	    }
+
+	  kv.key = tm->keys[i];
+	  if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
+	    clib_warning ("search for key %lld failed unexpectedly\n",
+			  tm->keys[i]);
+	  if (kv.value != (u64) (i + 1))
+	    clib_warning ("search for key %lld returned %lld, not %lld\n",
+			  tm->keys, kv.value, (u64) (i + 1));
+	}
+    }
+
+  delta = clib_time_now (&tm->clib_time) - before;
+  total_searches = (uword) tm->search_iter * (uword) tm->nitems;
+
+  if (delta > 0)
+    fformat (stdout, "%.f searches per second\n",
+	     ((f64) total_searches) / delta);
+
+  fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
+
+  fformat (stdout, "Standard E-hash search for items %d times...\n",
+	   tm->search_iter);
+
+  before = clib_time_now (&tm->clib_time);
+
+  for (j = 0; j < tm->search_iter; j++)
+    {
+      for (i = 0; i < tm->nitems; i++)
+	{
+	  p = hash_get (tm->key_hash, tm->keys[i]);
+	  if (p == 0 || p[0] != (uword) (i + 1))
+	    clib_warning ("ugh, couldn't find %lld\n", tm->keys[i]);
+	}
+    }
+
+  delta = clib_time_now (&tm->clib_time) - before;
+  total_searches = (uword) tm->search_iter * (uword) tm->nitems;
+
+  fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
+
+  if (delta > 0)
+    fformat (stdout, "%.f searches per second\n",
+	     ((f64) total_searches) / delta);
+
+  fformat (stdout, "Delete items...\n");
+
+  for (i = 0; i < tm->nitems; i++)
+    {
+      int j;
+      int rv;
+
+      kv.key = tm->keys[i];
+      kv.value = (u64) (i + 1);
+      rv = BV (clib_bihash_add_del) (h, &kv, 0 /* is_add */ );
+
+      if (rv < 0)
+	clib_warning ("delete key %lld not ok but should be", tm->keys[i]);
+
+      if (tm->careful_delete_tests)
+	{
+	  for (j = 0; j < tm->nitems; j++)
+	    {
+	      kv.key = tm->keys[j];
+	      rv = BV (clib_bihash_search) (h, &kv, &kv);
+	      if (j <= i && rv >= 0)
+		{
+		  clib_warning
+		    ("i %d j %d search ok but should not be, value %lld",
+		     i, j, kv.value);
+		}
+	      if (j > i && rv < 0)
+		{
+		  clib_warning ("i %d j %d search not ok but should be",
+				i, j);
+		}
+	    }
+	}
+    }
+
+  fformat (stdout, "After deletions, should be empty...\n");
+
+  fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
+  return 0;
+}
+
+clib_error_t *
+test_bihash_main (test_main_t * tm)
+{
+  unformat_input_t *i = tm->input;
+  clib_error_t *error;
+
+  while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
+    {
+      if (unformat (i, "seed %u", &tm->seed))
+	;
+
+      else if (unformat (i, "nbuckets %d", &tm->nbuckets))
+	;
+      else if (unformat (i, "non-random-keys"))
+	tm->non_random_keys = 1;
+      else if (unformat (i, "nitems %d", &tm->nitems))
+	;
+      else if (unformat (i, "careful %d", &tm->careful_delete_tests))
+	;
+      else if (unformat (i, "verbose %d", &tm->verbose))
+	;
+      else if (unformat (i, "search %d", &tm->search_iter))
+	;
+      else if (unformat (i, "verbose"))
+	tm->verbose = 1;
+      else
+	return clib_error_return (0, "unknown input '%U'",
+				  format_unformat_error, i);
+    }
+
+  error = test_bihash (tm);
+
+  return error;
+}
+
+#ifdef CLIB_UNIX
+int
+main (int argc, char *argv[])
+{
+  unformat_input_t i;
+  clib_error_t *error;
+  test_main_t *tm = &test_main;
+
+  clib_mem_init (0, 3ULL << 30);
+
+  tm->input = &i;
+  tm->seed = 0xdeaddabe;
+
+  tm->nbuckets = 2;
+  tm->nitems = 5;
+  tm->verbose = 1;
+  tm->search_iter = 1;
+  tm->careful_delete_tests = 0;
+  tm->key_hash = hash_create (0, sizeof (uword));
+  clib_time_init (&tm->clib_time);
+
+  unformat_init_command_line (&i, argv);
+  error = test_bihash_main (tm);
+  unformat_free (&i);
+
+  if (error)
+    {
+      clib_error_report (error);
+      return 1;
+    }
+  return 0;
+}
+#endif /* CLIB_UNIX */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
-- 
cgit 1.2.3-korg


From 5e6b9580f202188cbe158368bdbe35c3f39973d7 Mon Sep 17 00:00:00 2001
From: Dave Barach <dave@barachs.net>
Date: Mon, 12 Dec 2016 15:37:29 -0500
Subject: Handle execessive hash collisions, VPP-555

Change-Id: I55dad7b5cfb3d38c22b1105f7d2d61e7449410ea
Signed-off-by: Dave Barach <dave@barachs.net>
---
 src/vppinfra/bihash_8_8.h           |   1 +
 src/vppinfra/bihash_template.c      | 166 ++++++++++++++++++++++++++----------
 src/vppinfra/bihash_template.h      |  31 ++++---
 src/vppinfra/test_bihash_template.c |  32 ++-----
 4 files changed, 146 insertions(+), 84 deletions(-)

(limited to 'src/vppinfra/test_bihash_template.c')

diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h
index a0d6df2e..d70da596 100644
--- a/src/vppinfra/bihash_8_8.h
+++ b/src/vppinfra/bihash_8_8.h
@@ -53,6 +53,7 @@ clib_bihash_is_free_8_8 (clib_bihash_kv_8_8_t * v)
 static inline u64
 clib_bihash_hash_8_8 (clib_bihash_kv_8_8_t * v)
 {
+  /* Note: to torture-test linear scan, make this fn return a constant */
 #if __SSE4_2__
   return _mm_crc32_u64 (0, v->key);
 #else
diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index 4b0b4257..7c817a20 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -141,43 +141,83 @@ BV (split_and_rehash)
   (BVT (clib_bihash) * h,
    BVT (clib_bihash_value) * old_values, u32 new_log2_pages)
 {
-  BVT (clib_bihash_value) * new_values, *v, *new_v;
-  int i, j, k;
+  BVT (clib_bihash_value) * new_values, *new_v;
+  int i, j, length;
 
   new_values = BV (value_alloc) (h, new_log2_pages);
+  length = vec_len (old_values) * BIHASH_KVP_PER_PAGE;
 
-  v = old_values;
-  for (i = 0; i < vec_len (old_values); i++)
+  for (i = 0; i < length; i++)
     {
       u64 new_hash;
 
+      /* Entry not in use? Forget it */
+      if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
+	continue;
+
+      /* rehash the item onto its new home-page */
+      new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
+      new_hash >>= h->log2_nbuckets;
+      new_hash &= (1 << new_log2_pages) - 1;
+      new_v = &new_values[new_hash];
+
+      /* Across the new home-page */
       for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 	{
-	  if (BV (clib_bihash_is_free) (&(v->kvp[j])) == 0)
+	  /* Empty slot */
+	  if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
 	    {
-	      new_hash = BV (clib_bihash_hash) (&(v->kvp[j]));
-	      new_hash >>= h->log2_nbuckets;
-	      new_hash &= (1 << new_log2_pages) - 1;
+	      clib_memcpy (&(new_v->kvp[j]), &(old_values->kvp[i]),
+			   sizeof (new_v->kvp[j]));
+	      goto doublebreak;
+	    }
+	}
+      /* Crap. Tell caller to try again */
+      BV (value_free) (h, new_values);
+      return 0;
+    doublebreak:;
+    }
+  return new_values;
+}
 
-	      new_v = &new_values[new_hash];
+static
+BVT (clib_bihash_value) *
+BV (split_and_rehash_linear)
+  (BVT (clib_bihash) * h,
+   BVT (clib_bihash_value) * old_values, u32 new_log2_pages)
+{
+  BVT (clib_bihash_value) * new_values;
+  int i, j, new_length;
 
-	      for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
-		{
-		  if (BV (clib_bihash_is_free) (&(new_v->kvp[k])))
-		    {
-		      clib_memcpy (&(new_v->kvp[k]), &(v->kvp[j]),
-				   sizeof (new_v->kvp[k]));
-		      goto doublebreak;
-		    }
-		}
-	      /* Crap. Tell caller to try again */
-	      BV (value_free) (h, new_values);
-	      return 0;
+  new_values = BV (value_alloc) (h, new_log2_pages);
+  new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
+
+  j = 0;
+  /* Across the old value array */
+  for (i = 0; i < vec_len (old_values) * BIHASH_KVP_PER_PAGE; i++)
+    {
+      /* Find a free slot in the new linear scan bucket */
+      for (; j < new_length; j++)
+	{
+	  /* Old value in use? Forget it. */
+	  if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
+	    goto doublebreak;
+
+	  /* New value should never be in use */
+	  if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
+	    {
+	      /* Copy the old value and move along */
+	      clib_memcpy (&(new_values->kvp[j]), &(old_values->kvp[i]),
+			   sizeof (new_values->kvp[j]));
+	      j++;
+	      goto doublebreak;
 	    }
-	doublebreak:
-	  ;
+	  /* This should never happen... */
+	  clib_warning ("BUG: linear rehash failed!");
+	  BV (value_free) (h, new_values);
+	  return 0;
 	}
-      v++;
+    doublebreak:;
     }
   return new_values;
 }
@@ -188,12 +228,13 @@ int BV (clib_bihash_add_del)
   u32 bucket_index;
   clib_bihash_bucket_t *b, tmp_b;
   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
-  u32 value_index;
   int rv = 0;
-  int i;
+  int i, limit;
   u64 hash, new_hash;
   u32 new_log2_pages;
   u32 cpu_number = os_get_cpu_number ();
+  int mark_bucket_linear;
+  int resplit_once;
 
   hash = BV (clib_bihash_hash) (add_v);
 
@@ -226,8 +267,11 @@ int BV (clib_bihash_add_del)
   BV (make_working_copy) (h, b);
 
   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
-  value_index = hash & ((1 << h->saved_bucket.log2_pages) - 1);
-  v += value_index;
+
+  limit = BIHASH_KVP_PER_PAGE;
+  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
+  if (b->linear_search)
+    limit <<= b->log2_pages;
 
   if (is_add)
     {
@@ -235,7 +279,7 @@ int BV (clib_bihash_add_del)
        * For obvious (in hindsight) reasons, see if we're supposed to
        * replace an existing key, then look for an empty slot.
        */
-      for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+      for (i = 0; i < limit; i++)
 	{
 	  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 	    {
@@ -246,7 +290,7 @@ int BV (clib_bihash_add_del)
 	      goto unlock;
 	    }
 	}
-      for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+      for (i = 0; i < limit; i++)
 	{
 	  if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 	    {
@@ -260,7 +304,7 @@ int BV (clib_bihash_add_del)
     }
   else
     {
-      for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+      for (i = 0; i < limit; i++)
 	{
 	  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 	    {
@@ -276,24 +320,41 @@ int BV (clib_bihash_add_del)
     }
 
   new_log2_pages = h->saved_bucket.log2_pages + 1;
+  mark_bucket_linear = 0;
 
-expand_again:
   working_copy = h->working_copies[cpu_number];
+  resplit_once = 0;
+
   new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
   if (new_v == 0)
     {
+    try_resplit:
+      resplit_once = 1;
       new_log2_pages++;
-      goto expand_again;
+      /* Try re-splitting. If that fails, fall back to linear search */
+      new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
+      if (new_v == 0)
+	{
+	mark_linear:
+	  new_log2_pages--;
+	  /* pinned collisions, use linear search */
+	  new_v =
+	    BV (split_and_rehash_linear) (h, working_copy, new_log2_pages);
+	  mark_bucket_linear = 1;
+	}
     }
 
   /* Try to add the new entry */
   save_new_v = new_v;
   new_hash = BV (clib_bihash_hash) (add_v);
+  limit = BIHASH_KVP_PER_PAGE;
+  if (mark_bucket_linear)
+    limit <<= new_log2_pages;
   new_hash >>= h->log2_nbuckets;
-  new_hash &= (1 << min_log2 (vec_len (new_v))) - 1;
-  new_v += new_hash;
+  new_hash &= (1 << new_log2_pages) - 1;
+  new_v += mark_bucket_linear ? 0 : new_hash;
 
-  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+  for (i = 0; i < limit; i++)
     {
       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 	{
@@ -302,13 +363,24 @@ expand_again:
 	}
     }
   /* Crap. Try again */
-  new_log2_pages++;
   BV (value_free) (h, save_new_v);
-  goto expand_again;
+  /*
+   * If we've already doubled the size of the bucket once,
+   * fall back to linear search now.
+   */
+  if (resplit_once)
+    goto mark_linear;
+  else
+    goto try_resplit;
 
 expand_ok:
-  tmp_b.log2_pages = min_log2 (vec_len (save_new_v));
+  /* Keep track of the number of linear-scan buckets */
+  if (tmp_b.linear_search ^ mark_bucket_linear)
+    h->linear_buckets += (mark_bucket_linear == 1) ? 1 : -1;
+
+  tmp_b.log2_pages = new_log2_pages;
   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
+  tmp_b.linear_search = mark_bucket_linear;
   CLIB_MEMORY_BARRIER ();
   b->as_u64 = tmp_b.as_u64;
   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
@@ -326,10 +398,9 @@ int BV (clib_bihash_search)
 {
   u64 hash;
   u32 bucket_index;
-  uword value_index;
   BVT (clib_bihash_value) * v;
   clib_bihash_bucket_t *b;
-  int i;
+  int i, limit;
 
   ASSERT (valuep);
 
@@ -344,10 +415,12 @@ int BV (clib_bihash_search)
   hash >>= h->log2_nbuckets;
 
   v = BV (clib_bihash_get_value) (h, b->offset);
-  value_index = hash & ((1 << b->log2_pages) - 1);
-  v += value_index;
+  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;
 
-  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+  for (i = 0; i < limit; i++)
     {
       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 	{
@@ -381,8 +454,8 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
 
       if (verbose)
 	{
-	  s = format (s, "[%d]: heap offset %d, len %d\n", i,
-		      b->offset, (1 << b->log2_pages));
+	  s = format (s, "[%d]: heap offset %d, len %d, linear %d\n", i,
+		      b->offset, (1 << b->log2_pages), b->linear_search);
 	}
 
       v = BV (clib_bihash_get_value) (h, b->offset);
@@ -411,6 +484,7 @@ 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);
 
   return s;
 }
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index f70190c6..a0a7844c 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -61,7 +61,8 @@ typedef struct
     struct
     {
       u32 offset;
-      u8 pad[3];
+      u8 linear_search;
+      u8 pad[2];
       u8 log2_pages;
     };
     u64 as_u64;
@@ -80,6 +81,7 @@ typedef struct
 
   u32 nbuckets;
   u32 log2_nbuckets;
+  u32 linear_buckets;
   u8 *name;
 
     BVT (clib_bihash_value) ** freelists;
@@ -132,10 +134,9 @@ static inline int BV (clib_bihash_search_inline)
 {
   u64 hash;
   u32 bucket_index;
-  uword value_index;
   BVT (clib_bihash_value) * v;
   clib_bihash_bucket_t *b;
-  int i;
+  int i, limit;
 
   hash = BV (clib_bihash_hash) (kvp);
 
@@ -148,10 +149,14 @@ static inline int BV (clib_bihash_search_inline)
   hash >>= h->log2_nbuckets;
 
   v = BV (clib_bihash_get_value) (h, b->offset);
-  value_index = hash & ((1 << b->log2_pages) - 1);
-  v += value_index;
 
-  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+  /* 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;
+
+  for (i = 0; i < limit; i++)
     {
       if (BV (clib_bihash_key_compare) (v->kvp[i].key, kvp->key))
 	{
@@ -168,10 +173,9 @@ static inline int BV (clib_bihash_search_inline_2)
 {
   u64 hash;
   u32 bucket_index;
-  uword value_index;
   BVT (clib_bihash_value) * v;
   clib_bihash_bucket_t *b;
-  int i;
+  int i, limit;
 
   ASSERT (valuep);
 
@@ -184,12 +188,15 @@ static inline int BV (clib_bihash_search_inline_2)
     return -1;
 
   hash >>= h->log2_nbuckets;
-
   v = BV (clib_bihash_get_value) (h, b->offset);
-  value_index = hash & ((1 << b->log2_pages) - 1);
-  v += value_index;
 
-  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+  /* 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;
+
+  for (i = 0; i < limit; i++)
     {
       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 	{
diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c
index c505bd83..ef03f565 100644
--- a/src/vppinfra/test_bihash_template.c
+++ b/src/vppinfra/test_bihash_template.c
@@ -111,37 +111,17 @@ test_bihash (test_main_t * tm)
 
   for (j = 0; j < tm->search_iter; j++)
     {
-      u64 hash1 = clib_xxhash (tm->keys[0]);
-
       for (i = 0; i < tm->nitems; i++)
 	{
-	  if (i < (tm->nitems - 3))
-	    {
-	      clib_bihash_bucket_t *b;
-	      BVT (clib_bihash_value) * v;
-	      u64 hash2 = clib_xxhash (tm->keys[i + 3]);
-	      u32 bucket_index = hash2 & (h->nbuckets - 1);
-	      b = &h->buckets[bucket_index];
-	      CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, LOAD);
-
-	      bucket_index = hash1 & (h->nbuckets - 1);
-	      b = &h->buckets[bucket_index];
-	      v = BV (clib_bihash_get_value) (h, b->offset);
-	      hash1 >>= h->log2_nbuckets;
-	      hash1 = hash1 & ((1 << b->log2_pages) - 1);
-	      v += hash1;
-	      CLIB_PREFETCH (v, CLIB_CACHE_LINE_BYTES, LOAD);
-
-	      hash1 = hash2;
-	    }
-
 	  kv.key = tm->keys[i];
 	  if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
-	    clib_warning ("search for key %lld failed unexpectedly\n",
-			  tm->keys[i]);
+	    if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
+	      clib_warning ("[%d] search for key %lld failed unexpectedly\n",
+			    i, tm->keys[i]);
 	  if (kv.value != (u64) (i + 1))
-	    clib_warning ("search for key %lld returned %lld, not %lld\n",
-			  tm->keys, kv.value, (u64) (i + 1));
+	    clib_warning
+	      ("[%d] search for key %lld returned %lld, not %lld\n", i,
+	       tm->keys, kv.value, (u64) (i + 1));
 	}
     }
 
-- 
cgit 1.2.3-korg


From ba7ddfe9b77771c47f99df5475e6e92b8d80816e Mon Sep 17 00:00:00 2001
From: Dave Barach <dave@barachs.net>
Date: Wed, 17 May 2017 20:20:50 -0400
Subject: VPP-847: improve bihash template memory allocator performance

Particularly in the DCLIB_VEC64=1 case, using vectors vs. raw
clib_mem_alloc'ed memory causes abysmal memory allocator performance.

Change-Id: I07a4dec0cd69ca357445385e2671cdf23c59b95d
Signed-off-by: Dave Barach <dave@barachs.net>
---
 src/vppinfra/bihash_template.c      | 70 +++++++++++++++++++++++--------------
 src/vppinfra/bihash_template.h      |  1 +
 src/vppinfra/mheap.c                | 28 ++++++---------
 src/vppinfra/mheap_bootstrap.h      | 24 ++++++-------
 src/vppinfra/test_bihash_template.c | 45 +++++++++++++++++++++++-
 5 files changed, 111 insertions(+), 57 deletions(-)

(limited to 'src/vppinfra/test_bihash_template.c')

diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index 51fadeb8..7e4216bd 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -55,7 +55,8 @@ BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
       oldheap = clib_mem_set_heap (h->mheap);
 
       vec_validate (h->freelists, log2_pages);
-      vec_validate_aligned (rv, (1 << log2_pages) - 1, CLIB_CACHE_LINE_BYTES);
+      rv = clib_mem_alloc_aligned ((sizeof (*rv) * (1 << log2_pages)),
+				   CLIB_CACHE_LINE_BYTES);
       clib_mem_set_heap (oldheap);
       goto initialize;
     }
@@ -64,7 +65,6 @@ BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
 
 initialize:
   ASSERT (rv);
-  ASSERT (vec_len (rv) == (1 << log2_pages));
   /*
    * Latest gcc complains that the length arg is zero
    * if we replace (1<<log2_pages) with vec_len(rv).
@@ -75,14 +75,11 @@ initialize:
 }
 
 static void
-BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v)
+BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
+		 u32 log2_pages)
 {
-  u32 log2_pages;
-
   ASSERT (h->writer_lock[0]);
 
-  log2_pages = min_log2 (vec_len (v));
-
   ASSERT (vec_len (h->freelists) > log2_pages);
 
   v->next_free = h->freelists[log2_pages];
@@ -97,11 +94,14 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
   void *oldheap;
   BVT (clib_bihash_value) * working_copy;
   u32 thread_index = os_get_thread_index ();
+  int log2_working_copy_length;
 
   if (thread_index >= vec_len (h->working_copies))
     {
       oldheap = clib_mem_set_heap (h->mheap);
       vec_validate (h->working_copies, thread_index);
+      vec_validate (h->working_copy_lengths, thread_index);
+      h->working_copy_lengths[thread_index] = -1;
       clib_mem_set_heap (oldheap);
     }
 
@@ -111,18 +111,23 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
    * lookup failures.
    */
   working_copy = h->working_copies[thread_index];
+  log2_working_copy_length = h->working_copy_lengths[thread_index];
 
   h->saved_bucket.as_u64 = b->as_u64;
   oldheap = clib_mem_set_heap (h->mheap);
 
-  if ((1 << b->log2_pages) > vec_len (working_copy))
+  if (b->log2_pages > log2_working_copy_length)
     {
-      vec_validate_aligned (working_copy, (1 << b->log2_pages) - 1,
-			    sizeof (u64));
+      if (working_copy)
+	clib_mem_free (working_copy);
+
+      working_copy = clib_mem_alloc_aligned
+	(sizeof (working_copy[0]) * (1 << b->log2_pages),
+	 CLIB_CACHE_LINE_BYTES);
+      h->working_copy_lengths[thread_index] = b->log2_pages;
       h->working_copies[thread_index] = working_copy;
     }
 
-  _vec_len (working_copy) = 1 << b->log2_pages;
   clib_mem_set_heap (oldheap);
 
   v = BV (clib_bihash_get_value) (h, b->offset);
@@ -139,15 +144,16 @@ static
 BVT (clib_bihash_value) *
 BV (split_and_rehash)
   (BVT (clib_bihash) * h,
-   BVT (clib_bihash_value) * old_values, u32 new_log2_pages)
+   BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
+   u32 new_log2_pages)
 {
   BVT (clib_bihash_value) * new_values, *new_v;
-  int i, j, length;
+  int i, j, length_in_kvs;
 
   new_values = BV (value_alloc) (h, new_log2_pages);
-  length = vec_len (old_values) * BIHASH_KVP_PER_PAGE;
+  length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 
-  for (i = 0; i < length; i++)
+  for (i = 0; i < length_in_kvs; i++)
     {
       u64 new_hash;
 
@@ -173,10 +179,11 @@ BV (split_and_rehash)
 	    }
 	}
       /* Crap. Tell caller to try again */
-      BV (value_free) (h, new_values);
+      BV (value_free) (h, new_values, new_log2_pages);
       return 0;
     doublebreak:;
     }
+
   return new_values;
 }
 
@@ -184,17 +191,19 @@ static
 BVT (clib_bihash_value) *
 BV (split_and_rehash_linear)
   (BVT (clib_bihash) * h,
-   BVT (clib_bihash_value) * old_values, u32 new_log2_pages)
+   BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
+   u32 new_log2_pages)
 {
   BVT (clib_bihash_value) * new_values;
-  int i, j, new_length;
+  int i, j, new_length, old_length;
 
   new_values = BV (value_alloc) (h, new_log2_pages);
   new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
+  old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 
   j = 0;
   /* Across the old value array */
-  for (i = 0; i < vec_len (old_values) * BIHASH_KVP_PER_PAGE; i++)
+  for (i = 0; i < old_length; i++)
     {
       /* Find a free slot in the new linear scan bucket */
       for (; j < new_length; j++)
@@ -215,7 +224,7 @@ BV (split_and_rehash_linear)
 	}
       /* This should never happen... */
       clib_warning ("BUG: linear rehash failed!");
-      BV (value_free) (h, new_values);
+      BV (value_free) (h, new_values, new_log2_pages);
       return 0;
 
     doublebreak:;
@@ -232,7 +241,7 @@ int BV (clib_bihash_add_del)
   int rv = 0;
   int i, limit;
   u64 hash, new_hash;
-  u32 new_log2_pages;
+  u32 new_log2_pages, old_log2_pages;
   u32 thread_index = os_get_thread_index ();
   int mark_bucket_linear;
   int resplit_once;
@@ -257,6 +266,7 @@ int BV (clib_bihash_add_del)
 	}
 
       v = BV (value_alloc) (h, 0);
+
       *v->kvp = *add_v;
       tmp_b.as_u64 = 0;
       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
@@ -320,27 +330,31 @@ int BV (clib_bihash_add_del)
       goto unlock;
     }
 
-  new_log2_pages = h->saved_bucket.log2_pages + 1;
+  old_log2_pages = h->saved_bucket.log2_pages;
+  new_log2_pages = old_log2_pages + 1;
   mark_bucket_linear = 0;
 
   working_copy = h->working_copies[thread_index];
   resplit_once = 0;
 
-  new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
+  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
+				 new_log2_pages);
   if (new_v == 0)
     {
     try_resplit:
       resplit_once = 1;
       new_log2_pages++;
       /* Try re-splitting. If that fails, fall back to linear search */
-      new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
+      new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
+				     new_log2_pages);
       if (new_v == 0)
 	{
 	mark_linear:
 	  new_log2_pages--;
 	  /* pinned collisions, use linear search */
 	  new_v =
-	    BV (split_and_rehash_linear) (h, working_copy, new_log2_pages);
+	    BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
+					  new_log2_pages);
 	  mark_bucket_linear = 1;
 	}
     }
@@ -363,8 +377,9 @@ int BV (clib_bihash_add_del)
 	  goto expand_ok;
 	}
     }
+
   /* Crap. Try again */
-  BV (value_free) (h, save_new_v);
+  BV (value_free) (h, save_new_v, new_log2_pages);
   /*
    * If we've already doubled the size of the bucket once,
    * fall back to linear search now.
@@ -382,10 +397,11 @@ expand_ok:
   tmp_b.log2_pages = new_log2_pages;
   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
   tmp_b.linear_search = mark_bucket_linear;
+
   CLIB_MEMORY_BARRIER ();
   b->as_u64 = tmp_b.as_u64;
   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
-  BV (value_free) (h, v);
+  BV (value_free) (h, v, old_log2_pages);
 
 unlock:
   CLIB_MEMORY_BARRIER ();
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index a0a7844c..4ea14ff0 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -77,6 +77,7 @@ typedef struct
   volatile u32 *writer_lock;
 
     BVT (clib_bihash_value) ** working_copies;
+  int *working_copy_lengths;
   clib_bihash_bucket_t saved_bucket;
 
   u32 nbuckets;
diff --git a/src/vppinfra/mheap.c b/src/vppinfra/mheap.c
index d4010ceb..5bbbc65f 100644
--- a/src/vppinfra/mheap.c
+++ b/src/vppinfra/mheap.c
@@ -549,23 +549,17 @@ mheap_get_search_free_list (void *v,
 	non_empty_bin_mask &= ~pow2_mask (bin % BITS (uword));
 
       /* Search each occupied free bin which is large enough. */
-      foreach_set_bit (bi, non_empty_bin_mask, (
-						 {
-						 uword r =
-						 mheap_get_search_free_bin (v,
-									    bi
-									    +
-									    i
-									    *
-									    BITS
-									    (uword),
-									    n_user_bytes_arg,
-									    align,
-									    align_offset);
-						 if (r !=
-						     MHEAP_GROUNDED) return
-						 r;}
-		       ));
+      /* *INDENT-OFF* */
+      foreach_set_bit (bi, non_empty_bin_mask,
+      ({
+        uword r =
+          mheap_get_search_free_bin (v, bi + i * BITS (uword),
+                                     n_user_bytes_arg,
+                                     align,
+                                     align_offset);
+        if (r != MHEAP_GROUNDED) return r;
+      }));
+      /* *INDENT-ON* */
     }
 
   return MHEAP_GROUNDED;
diff --git a/src/vppinfra/mheap_bootstrap.h b/src/vppinfra/mheap_bootstrap.h
index 4b21051b..38f0ac84 100644
--- a/src/vppinfra/mheap_bootstrap.h
+++ b/src/vppinfra/mheap_bootstrap.h
@@ -160,11 +160,23 @@ typedef struct
   uword *trace_index_by_offset;
 } mheap_trace_main_t;
 
+/* Without vector instructions don't bother with small object cache. */
+#ifdef CLIB_HAVE_VEC128
+#define MHEAP_HAVE_SMALL_OBJECT_CACHE 1
+#else
+#define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
+#endif
+
   /* Small object bin i is for objects with
      user_size >  sizeof (mheap_elt_t) + sizeof (mheap_elt_t) * (i - 1)
      user_size <= sizeof (mheap_elt_t) + sizeof (mheap_size_t) * i. */
+#if MHEAP_HAVE_SMALL_OBJECT_CACHE > 0
 #define MHEAP_LOG2_N_SMALL_OBJECT_BINS 8
 #define MHEAP_N_SMALL_OBJECT_BINS (1 << MHEAP_LOG2_N_SMALL_OBJECT_BINS)
+#else
+#define MHEAP_LOG2_N_SMALL_OBJECT_BINS 0
+#define MHEAP_N_SMALL_OBJECT_BINS 0
+#endif
 
 #define MHEAP_N_BINS							\
   (MHEAP_N_SMALL_OBJECT_BINS						\
@@ -188,18 +200,6 @@ typedef struct
   u64 n_clocks_get, n_clocks_put;
 } mheap_stats_t;
 
-/* Without vector instructions don't bother with small object cache. */
-#ifdef CLIB_HAVE_VEC128
-#define MHEAP_HAVE_SMALL_OBJECT_CACHE 1
-#else
-#define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
-#endif
-
-#if CLIB_VEC64 > 0
-#undef MHEAP_HAVE_SMALL_OBJECT_CACHE
-#define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
-#endif
-
 /* For objects with align == 4 and align_offset == 0 (e.g. vector strings). */
 typedef struct
 {
diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c
index ef03f565..1e262430 100644
--- a/src/vppinfra/test_bihash_template.c
+++ b/src/vppinfra/test_bihash_template.c
@@ -47,6 +47,43 @@ vl (void *v)
   return vec_len (v);
 }
 
+static clib_error_t *
+test_bihash_vec64 (test_main_t * tm)
+{
+  u32 user_buckets = 1228800;
+  u32 user_memory_size = 209715200;
+  BVT (clib_bihash_kv) kv;
+  int i, j;
+  f64 before;
+  f64 *cum_times = 0;
+  BVT (clib_bihash) * h;
+
+  h = &tm->hash;
+
+  BV (clib_bihash_init) (h, "test", user_buckets, user_memory_size);
+
+  before = clib_time_now (&tm->clib_time);
+
+  for (j = 0; j < 10; j++)
+    {
+      for (i = 1; i <= j * 1000 + 1; i++)
+	{
+	  kv.key = i;
+	  kv.value = 1;
+
+	  BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
+	}
+
+      vec_add1 (cum_times, clib_time_now (&tm->clib_time) - before);
+    }
+
+  for (j = 0; j < vec_len (cum_times); j++)
+    fformat (stdout, "Cum time for %d: %.4f (us)\n", (j + 1) * 1000,
+	     cum_times[j] * 1e6);
+
+  return 0;
+}
+
 static clib_error_t *
 test_bihash (test_main_t * tm)
 {
@@ -204,6 +241,7 @@ test_bihash_main (test_main_t * tm)
 {
   unformat_input_t *i = tm->input;
   clib_error_t *error;
+  int test_vec64 = 0;
 
   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
     {
@@ -222,6 +260,8 @@ test_bihash_main (test_main_t * tm)
 	;
       else if (unformat (i, "search %d", &tm->search_iter))
 	;
+      else if (unformat (i, "vec64"))
+	test_vec64 = 1;
       else if (unformat (i, "verbose"))
 	tm->verbose = 1;
       else
@@ -229,7 +269,10 @@ test_bihash_main (test_main_t * tm)
 				  format_unformat_error, i);
     }
 
-  error = test_bihash (tm);
+  if (test_vec64)
+    error = test_bihash_vec64 (tm);
+  else
+    error = test_bihash (tm);
 
   return error;
 }
-- 
cgit 1.2.3-korg


From 908a5ea6e247b4a15f0ec7e8ee8ebff799abdc4f Mon Sep 17 00:00:00 2001
From: Dave Barach <dave@barachs.net>
Date: Fri, 14 Jul 2017 12:42:21 -0400
Subject: 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>
---
 src/vnet/fib/ip6_fib.c              |   4 +-
 src/vnet/fib/ip6_fib.h              |   2 +-
 src/vnet/l2/l2_fib.c                |   8 +-
 src/vppinfra.am                     |   2 +
 src/vppinfra/bihash_16_8.h          |   3 +
 src/vppinfra/bihash_24_8.h          |   3 +
 src/vppinfra/bihash_48_8.h          |   3 +
 src/vppinfra/bihash_8_8.h           |   3 +
 src/vppinfra/bihash_template.c      |  78 ++++++++++++--
 src/vppinfra/bihash_template.h      | 206 ++++++++++++++++++++++++++++++++----
 src/vppinfra/test_bihash_template.c |  61 +++++++++--
 11 files changed, 329 insertions(+), 44 deletions(-)

(limited to 'src/vppinfra/test_bihash_template.c')

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
@@ -236,12 +236,45 @@ test_bihash (test_main_t * tm)
   return 0;
 }
 
+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;
 }
-- 
cgit 1.2.3-korg