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, 30 insertions, 2 deletions

diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index 41d7c7ce1d6..18d74d9ea2f 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -269,8 +269,9 @@ BV (split_and_rehash_linear)
   return new_values;
 }
 
-int BV (clib_bihash_add_del)
-  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
+static inline int BV (clib_bihash_add_del_inline)
+  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add,
+   int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
 {
   u32 bucket_index;
   BVT (clib_bihash_bucket) * b, tmp_b;
@@ -366,6 +367,20 @@ int BV (clib_bihash_add_del)
 	      return (0);
 	    }
 	}
+      /* look for stale data to overwrite */
+      if (is_stale_cb)
+	{
+	  for (i = 0; i < limit; i++)
+	    {
+	      if (is_stale_cb (&(v->kvp[i]), arg))
+		{
+		  CLIB_MEMORY_BARRIER ();
+		  clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
+		  BV (clib_bihash_unlock_bucket) (b);
+		  return (0);
+		}
+	    }
+	}
       /* Out of space in this bucket, split the bucket... */
     }
   else				/* delete case */
@@ -484,6 +499,19 @@ expand_ok:
   return (0);
 }
 
+int BV (clib_bihash_add_del)
+  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
+{
+  return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
+}
+
+int BV (clib_bihash_add_or_overwrite_stale)
+  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
+   int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
+{
+  return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
+}
+
 int BV (clib_bihash_search)
   (BVT (clib_bihash) * h,
    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)