summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-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?");
}