aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorNathan Skrzypczak <nathan.skrzypczak@gmail.com>2021-12-02 14:40:06 +0100
committerDamjan Marion <dmarion@me.com>2022-03-21 11:27:29 +0000
commit17ecd853e9efc40023185ecdf38c37d23dd8a0ce (patch)
tree6782299c2349ffb932eeef5773230182a469791d /src
parentd0d4b43374f6cb873ef189d91cab4482753e0f38 (diff)
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>
Diffstat (limited to 'src')
-rw-r--r--src/vppinfra/bihash_doc.h216
-rw-r--r--src/vppinfra/bihash_template.c31
-rw-r--r--src/vppinfra/bihash_template.h7
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);