aboutsummaryrefslogtreecommitdiffstats
path: root/src/vppinfra/cuckoo_template.c
diff options
context:
space:
mode:
authorKlement Sekera <ksekera@cisco.com>2020-02-20 11:39:58 +0000
committerDamjan Marion <dmarion@me.com>2020-03-21 12:14:31 +0000
commit39d0285fca412ea2921fe1ae98a231894cd193cf (patch)
tree75d579caf2f7b5f1adc26e4a1d62e260e095a30d /src/vppinfra/cuckoo_template.c
parentdd73bd321e2718dd9afced36dad53bd624af4f32 (diff)
vppinfra: fix minor cuckoo bugs and add cuckoo_16_8
Type: improvement Change-Id: If1164d2eb81e9d4748436cb1bb8b164857d70565 Signed-off-by: Klement Sekera <ksekera@cisco.com>
Diffstat (limited to 'src/vppinfra/cuckoo_template.c')
-rw-r--r--src/vppinfra/cuckoo_template.c53
1 files changed, 33 insertions, 20 deletions
diff --git a/src/vppinfra/cuckoo_template.c b/src/vppinfra/cuckoo_template.c
index c48032a319c..8cd2a2be2b5 100644
--- a/src/vppinfra/cuckoo_template.c
+++ b/src/vppinfra/cuckoo_template.c
@@ -21,7 +21,6 @@
*/
#include <vppinfra/vec.h>
-#include <vppinfra/cuckoo_template.h>
int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
CVT (clib_cuckoo_kv) * search_v,
@@ -100,8 +99,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
CVT (clib_cuckoo_bucket) * bucket;
uword bucket_idx = 0;
/* *INDENT-OFF* */
- clib_cuckoo_foreach_bucket (bucket, h)
- {
+ clib_cuckoo_foreach_bucket (bucket, h, {
int i = 0;
int used = 0;
clib_cuckoo_bucket_foreach_idx (i)
@@ -110,8 +108,8 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
if (!CV (clib_cuckoo_kv_is_free) (elt))
{
u64 hash = CV (clib_cuckoo_hash) (elt);
- clib_cuckoo_lookup_info_t lookup = CV (clib_cuckoo_calc_lookup) (
- CV (clib_cuckoo_get_snapshot) (h), hash);
+ clib_cuckoo_lookup_info_t lookup =
+ CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
CVT (clib_cuckoo_kv) kv = *elt;
int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
@@ -121,7 +119,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
bucket->reduced_hashes[i]);
CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
}
- ASSERT (aux.bucket1 == bucket_idx || aux.bucket2 == bucket_idx);
+ ASSERT (lookup.bucket1 == bucket_idx || lookup.bucket2 == bucket_idx);
ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
++used;
}
@@ -129,7 +127,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
clib_cuckoo_bucket_aux_t aux = bucket->aux;
ASSERT (used == clib_cuckoo_bucket_aux_get_use_count (aux));
++bucket_idx;
- }
+ });
/* *INDENT-ON* */
// CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h);
}
@@ -820,14 +818,15 @@ static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h,
}
int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
- CVT (clib_cuckoo_kv) * kvp, int is_add)
+ CVT (clib_cuckoo_kv) * kvp, int is_add,
+ int dont_overwrite)
{
CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp),
kvp);
clib_cuckoo_lookup_info_t lookup;
u64 hash = CV (clib_cuckoo_hash) (kvp);
- clib_spinlock_lock (&h->writer_lock);
u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
+ clib_spinlock_lock (&h->writer_lock);
restart:
lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
CVT (clib_cuckoo_bucket) * b =
@@ -846,19 +845,30 @@ restart:
{
if (is_add)
{
- /* prevent readers reading this bucket while we switch the values */
- clib_cuckoo_bucket_aux_t aux =
- CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
- clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
- CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
- found, b->reduced_hashes[found - b->elts]);
- CV (clib_cuckoo_bucket_unlock) (b, aux);
+ if (dont_overwrite)
+ {
+ CLIB_CUCKOO_DBG ("Refused replacing existing %U",
+ CV (format_cuckoo_elt), found,
+ b->reduced_hashes[found - b->elts]);
+ rv = CLIB_CUCKOO_ERROR_AGAIN;
+ }
+ else
+ {
+ /* prevent readers reading this bucket while we switch the values */
+ clib_cuckoo_bucket_aux_t aux =
+ CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
+ clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
+ CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
+ found, b->reduced_hashes[found - b->elts]);
+ CV (clib_cuckoo_bucket_unlock) (b, aux);
+ rv = CLIB_CUCKOO_ERROR_SUCCESS;
+ }
}
else
{
CV (clib_cuckoo_free_elt_in_bucket) (b, found);
+ rv = CLIB_CUCKOO_ERROR_SUCCESS;
}
- rv = CLIB_CUCKOO_ERROR_SUCCESS;
CLIB_CUCKOO_DEEP_SELF_CHECK (h);
goto unlock;
}
@@ -876,9 +886,12 @@ restart:
CLIB_CUCKOO_DEEP_SELF_CHECK (h);
if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
{
- CLIB_CUCKOO_DBG ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U", aux.bucket1, aux.bucket2, CV (format_cuckoo_bucket), CV (clib_cuckoo_bucindent: Standaindent: Standard input: 903: Error: Unmatched 'else' rd input: 865: Error:Unmatched 'else' ket_at_index) (h, aux.bucket1),
- CV (format_cuckoo_bucket),
- CV (clib_cuckoo_bucket_at_index) (h, aux.bucket2));
+ CLIB_CUCKOO_DBG
+ ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U",
+ lookup.bucket1, lookup.bucket2, CV (format_cuckoo_bucket),
+ CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1),
+ CV (format_cuckoo_bucket),
+ CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2));
/* slow path */
rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
CLIB_CUCKOO_DEEP_SELF_CHECK (h);