vppinfra: add new bihash exports

This adds two new exported functions
for the clib_bihash

* clib_bihash_add_with_overwrite_cb allowing
to pass a callback to be called on overwriting
a key with bucket lock held.
* clib_bihash_add_del_with_hash doing an add_del
with a precomputed hash.

Type: feature

Change-Id: I1590c933fa7cf21e6a8ada89b3456a60c4988244
Signed-off-by: Nathan Skrzypczak <nathan.skrzypczak@gmail.com>

3 files changed, 185 insertions, 69 deletions

diff --git a/src/vppinfra/bihash_doc.h b/src/vppinfra/bihash_doc.h
index 7c7e5179961..f6d32ce0b56 100644
--- a/src/vppinfra/bihash_doc.h
+++ b/src/vppinfra/bihash_doc.h
@@ -90,83 +90,172 @@ static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
 /** Get clib mheap offset given a pointer */
 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
 
-/** initialize a bounded index extensible hash table
-
-    @param h - the bi-hash table to initialize
-    @param name - name of the hash table
-    @param nbuckets - the number of buckets, will be rounded up to
-a power of two
-    @param memory_size - clib mheap size, in bytes
-*/
-
+/**
+ * initialize a bounded index extensible hash table
+ *
+ * @param h - the bi-hash table to initialize
+ * @param name - name of the hash table
+ * @param nbuckets - the number of buckets, will be rounded up to
+ * a power of two
+ * @param memory_size - clib mheap size, in bytes
+ */
 void clib_bihash_init
   (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
 
-/** Destroy a bounded index extensible hash table
-    @param h - the bi-hash table to free
-*/
+/**
+ * initialize a bounded index extensible hash table with arguments passed as
+ * a struct
+ *
+ * @param a - initialization parameters
+ *   h - the bi-hash table to initialize;
+ *   name - name of the hash table
+ *   nbuckets - the number of buckets, will be rounded up to a power of two
+ *   memory_size - clib mheap size, in bytes
+ *   format_function_t - format function for the bihash kv pairs
+ *   instantiate_immediately - allocate memory right away
+ *   dont_add_to_all_bihash_list - dont mention in 'show bihash'
+ */
+void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a);
 
-void clib_bihash_free (clib_bihash * h);
+/**
+ * Set the formating function for the bihash
+ *
+ * @param h - the bi-hash table
+ * @param kvp_fmt_fn - the format function
+ */
+void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
+					 format_function_t *kvp_fmt_fn);
 
-/** Add or delete a (key,value) pair from a bi-hash table
+/**
+ * Destroy a bounded index extensible hash table
+ *
+ * @param h - the bi-hash table to free
+ */
+void clib_bihash_free (clib_bihash *h);
 
-    @param h - the bi-hash table to search
-    @param add_v - the (key,value) pair to add
-    @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
-    @returns 0 on success, < 0 on error
-    @note This function will replace an existing (key,value) pair if the
-    new key matches an existing key
-*/
+/**
+ * Add or delete a (key,value) pair from a bi-hash table
+ *
+ * @param h - the bi-hash table to search
+ * @param add_v - the (key,value) pair to add
+ * @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
+ * @returns 0 on success, < 0 on error
+ * @note This function will replace an existing (key,value) pair if the
+ * new key matches an existing key
+ */
 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
 
+/**
+ * Add or delete a (key,value) pair from a bi-hash table, using a pre-computed
+ * hash
+ *
+ * @param h - the bi-hash table to search
+ * @param add_v - the (key,value) pair to add
+ * @param hash - the precomputed hash of the key
+ * @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
+ * @returns 0 on success, < 0 on error
+ * @note This function will replace an existing (key,value) pair if the
+ * new key matches an existing key
+ */
+int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h,
+					BVT (clib_bihash_kv) * add_v, u64 hash,
+					int is_add);
 
-/** Search a bi-hash table, use supplied hash code
+/**
+ * Add a (key,value) pair to a bi-hash table, and tries to free stale entries
+ * on collisions with passed filter.
+ *
+ * @param h - the bi-hash table to search
+ * @param add_v - the (key,value) pair to add
+ * @param is_stale_cb - callback receiving a kv pair, returning 1 if the kv is
+ * stale and can be overwriten. This will be called on adding a kv in a full
+ * page before trying to split & rehash its bucket.
+ * @param arg - opaque arguement passed to is_stale_cb
+ * @returns 0 on success, < 0 on error
+ * @note This function will replace an existing (key,value) pair if the
+ * new key matches an existing key
+ */
+int BV (clib_bihash_add_or_overwrite_stale) (
+  BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
+  int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg);
 
-    @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);
+/**
+ * Add a (key,value) pair to a bi-hash table, calling a callback on overwrite
+ * with the bucket lock held.
+ *
+ * @param h - the bi-hash table to search
+ * @param add_v - the (key,value) pair to add
+ * @param overwrite_cb - callback called when overwriting a key, allowing
+ * you to cleanup the value with the bucket lock held.
+ * @param arg - opaque arguement passed to overwrite_cb
+ * @returns 0 on success, < 0 on error
+ * @note This function will replace an existing (key,value) pair if the
+ * new key matches an existing key
+ */
+int BV (clib_bihash_add_with_overwrite_cb) (
+  BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
+  void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *arg);
 
-/** Search a bi-hash table
+/**
+ * Tells if the bihash was initialised (i.e. mem allocated by first add)
+ *
+ * @param h - the bi-hash table to search
+ */
+int BV (clib_bihash_is_initialised) (const BVT (clib_bihash) * h);
 
-    @param h - the bi-hash table to search
-    @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);
+/**
+ * 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);
 
-/** Prefetch a bi-hash bucket given a hash code
+/**
+ * Search a bi-hash table
+ *
+ * @param h - the bi-hash table to search
+ * @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);
 
-    @param h - the bi-hash table to search
-    @param hash - the hash code
-    @note see also clib_bihash_hash to compute the code
-*/
+/**
+ * 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
+ */
 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
-*/
+/**
+ * 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
-*/
+/**
+ * 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);
 
-/* Calback function for walking a bihash table
+/**
+ * Calback function for walking a bihash table
  *
  * @param kv - KV pair visited
  * @param ctx - Context passed to the walk
@@ -175,13 +264,14 @@ int clib_bihash_search_inline_2
 typedef int (*clib_bihash_foreach_key_value_pair_cb) (clib_bihash_kv * kv,
 						      void *ctx);
 
-/** Visit active (key,value) pairs in a bi-hash table
-
-    @param h - the bi-hash table to search
-    @param callback - function to call with each active (key,value) pair
-    @param arg - arbitrary second argument passed to the callback function
-    First argument is the (key,value) pair to visit
-*/
+/**
+ * Visit active (key,value) pairs in a bi-hash table
+ *
+ * @param h - the bi-hash table to search
+ * @param callback - function to call with each active (key,value) pair
+ * @param arg - arbitrary second argument passed to the callback function
+ * First argument is the (key,value) pair to visit
+ */
 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
 					 clib_bihash_foreach_key_value_pair_cb
 					 * callback, void *arg);
diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index 1c9f3b8708a..48830508114 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -672,9 +672,10 @@ BV (split_and_rehash_linear)
   return new_values;
 }
 
-static_always_inline int BV (clib_bihash_add_del_inline_with_hash)
-  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, u64 hash, int is_add,
-   int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
+static_always_inline int BV (clib_bihash_add_del_inline_with_hash) (
+  BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, u64 hash, int is_add,
+  int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *is_stale_arg,
+  void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *overwrite_arg)
 {
   BVT (clib_bihash_bucket) * b, tmp_b;
   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
@@ -776,7 +777,8 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash)
 		  BV (clib_bihash_unlock_bucket) (b);
 		  return (-2);
 		}
-
+	      if (overwrite_cb)
+		overwrite_cb (&(v->kvp[i]), overwrite_arg);
 	      clib_memcpy_fast (&(v->kvp[i].value),
 				&add_v->value, sizeof (add_v->value));
 	      BV (clib_bihash_unlock_bucket) (b);
@@ -812,7 +814,7 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash)
 	{
 	  for (i = 0; i < limit; i++)
 	    {
-	      if (is_stale_cb (&(v->kvp[i]), arg))
+	      if (is_stale_cb (&(v->kvp[i]), is_stale_arg))
 		{
 		  clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
 		  CLIB_MEMORY_STORE_BARRIER ();
@@ -994,7 +996,15 @@ static_always_inline int BV (clib_bihash_add_del_inline)
 {
   u64 hash = BV (clib_bihash_hash) (add_v);
   return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add,
-						    is_stale_cb, arg);
+						    is_stale_cb, arg, 0, 0);
+}
+
+int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h,
+					BVT (clib_bihash_kv) * add_v, u64 hash,
+					int is_add)
+{
+  return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add, 0,
+						    0, 0, 0);
 }
 
 int BV (clib_bihash_add_del)
@@ -1010,6 +1020,15 @@ int BV (clib_bihash_add_or_overwrite_stale)
   return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
 }
 
+int BV (clib_bihash_add_with_overwrite_cb) (
+  BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
+  void (overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
+{
+  u64 hash = BV (clib_bihash_hash) (add_v);
+  return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, 1, 0, 0,
+						    overwrite_cb, arg);
+}
+
 int BV (clib_bihash_search)
   (BVT (clib_bihash) * h,
    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index 2a5c5861d88..c4e120e4a1f 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -356,12 +356,19 @@ 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_add_del_with_hash) (BVT (clib_bihash) * h,
+					BVT (clib_bihash_kv) * add_v, u64 hash,
+					int is_add);
 int BV (clib_bihash_add_or_overwrite_stale) (BVT (clib_bihash) * h,
 					     BVT (clib_bihash_kv) * add_v,
 					     int (*is_stale_cb) (BVT
 								 (clib_bihash_kv)
 								 *, void *),
 					     void *arg);
+int BV (clib_bihash_add_with_overwrite_cb) (
+  BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
+  void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *arg);
 int BV (clib_bihash_search) (BVT (clib_bihash) * h,
 			     BVT (clib_bihash_kv) * search_v,
 			     BVT (clib_bihash_kv) * return_v);