aboutsummaryrefslogtreecommitdiffstats
path: root/src/vppinfra
diff options
context:
space:
mode:
authorMatus Fabian <matfabia@cisco.com>2018-08-21 03:15:50 -0700
committerDave Barach <openvpp@barachs.net>2018-08-22 15:14:29 +0000
commit828d27ea0edb97280a0164041a286973fa74b5a2 (patch)
tree00c318426c5ccd916bbe1da1a8814a2d7ccc48fe /src/vppinfra
parent69ce30d6ab7c6afba475b25bb32542b1e955b91d (diff)
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>
Diffstat (limited to 'src/vppinfra')
-rw-r--r--src/vppinfra/bihash_template.c32
-rw-r--r--src/vppinfra/bihash_template.h6
-rw-r--r--src/vppinfra/test_bihash_template.c45
3 files changed, 81 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)
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index 9bf4737cd84..cfb8ceac69e 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -176,6 +176,12 @@ 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_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_search) (BVT (clib_bihash) * h,
BVT (clib_bihash_kv) * search_v,
BVT (clib_bihash_kv) * return_v);
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?");
}