bihash: add support for reuse of expired entry when bucket is full (VPP-1272)

Applications such as NAT that dynamically create entries require these entries to expire after some time.
Bihash user can now lazily delete expired entries. When inserting and bucket is full, expired entry is overwritten.

Change-Id: I6852305df399b546159407f1729c856afde5a634
Signed-off-by: Matus Fabian <matfabia@cisco.com>

1 files changed, 45 insertions, 0 deletions

diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c
index 80e11511f62..e52f2740b3b 100644
--- a/src/vppinfra/test_bihash_template.c
+++ b/src/vppinfra/test_bihash_template.c
@@ -35,6 +35,7 @@ typedef struct
   u32 ncycles;
   u32 report_every_n;
   u32 search_iter;
+  u32 noverwritten;
   int careful_delete_tests;
   int verbose;
   int non_random_keys;
@@ -95,6 +96,44 @@ test_bihash_vec64 (test_main_t * tm)
   return 0;
 }
 
+static int
+stale_cb (BVT (clib_bihash_kv) * kv, void *ctx)
+{
+  test_main_t *tm = ctx;
+
+  tm->noverwritten++;
+
+  return 1;
+}
+
+static clib_error_t *
+test_bihash_stale_overwrite (test_main_t * tm)
+{
+  BVT (clib_bihash) * h;
+  BVT (clib_bihash_kv) kv;
+  int i;
+  tm->noverwritten = 0;
+
+  h = &tm->hash;
+
+  BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size);
+
+  fformat (stdout, "Add %d items to %d buckets\n", tm->nitems, tm->nbuckets);
+
+  for (i = 0; i < tm->nitems; i++)
+    {
+      kv.key = i;
+      kv.value = 1;
+
+      BV (clib_bihash_add_or_overwrite_stale) (h, &kv, stale_cb, tm);
+    }
+
+  fformat (stdout, "%d items overwritten\n", tm->noverwritten);
+  fformat (stdout, "%U", BV (format_bihash), h, 0);
+
+  return 0;
+}
+
 void *
 test_bihash_thread_fn (void *arg)
 {
@@ -424,6 +463,8 @@ test_bihash_main (test_main_t * tm)
 	which = 2;
       else if (unformat (i, "verbose"))
 	tm->verbose = 1;
+      else if (unformat (i, "stale-overwrite"))
+	which = 3;
       else
 	return clib_error_return (0, "unknown input '%U'",
 				  format_unformat_error, i);
@@ -449,6 +490,10 @@ test_bihash_main (test_main_t * tm)
       error = test_bihash_threads (tm);
       break;
 
+    case 3:
+      error = test_bihash_stale_overwrite (tm);
+      break;
+
     default:
       return clib_error_return (0, "no such test?");
     }