From b9c8c57e983246ec034bc9059b1740558c951d51 Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Thu, 16 Mar 2023 13:03:47 -0400 Subject: vppinfra: fix corner-cases in bihash lookup In a case where one pounds on a single kvp in a KVP_AT_BUCKET_LEVEL table, the code would sporadically return a transitional value (junk) from a half-deleted kvp. At most, 64-bits worth of the kvp will be written atomically, so using memset(...) to smear 0xFF's across a kvp to free it left a lot to be desired. Performance impact: very mild positive, thanks to FC for doing a multi-thread host stack perf/scale test. Added an ASSERT to catch attempts to add a (key,value) pair which contains the magic "free kvp" value. Type: fix Signed-off-by: Dave Barach Change-Id: I6a1aa8a2c30bc70bec4b696ce7b17c2839927065 --- src/vppinfra/bihash_template.c | 50 +++++++++++++++++++++++++++++++----------- 1 file changed, 37 insertions(+), 13 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 48830508114..38354a12992 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -165,19 +165,23 @@ static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h) if (BIHASH_KVP_AT_BUCKET_LEVEL) { - int i; + int i, j; BVT (clib_bihash_bucket) * b; b = h->buckets; for (i = 0; i < h->nbuckets; i++) { + BVT (clib_bihash_kv) * v; b->offset = BV (clib_bihash_get_offset) (h, (void *) (b + 1)); b->refcnt = 1; /* Mark all elements free */ - clib_memset_u8 ((b + 1), 0xff, BIHASH_KVP_PER_PAGE * - sizeof (BVT (clib_bihash_kv))); - + v = (void *) (b + 1); + for (j = 0; j < BIHASH_KVP_PER_PAGE; j++) + { + BV (clib_bihash_mark_free) (v); + v++; + } /* Compute next bucket start address */ b = (void *) (((uword) b) + sizeof (*b) + (BIHASH_KVP_PER_PAGE * @@ -459,6 +463,7 @@ static BVT (clib_bihash_value) * BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages) { + int i; BVT (clib_bihash_value) * rv = 0; ASSERT (h->alloc_lock[0]); @@ -478,12 +483,15 @@ BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages) initialize: ASSERT (rv); - /* - * Latest gcc complains that the length arg is zero - * if we replace (1<instantiated != 0); #endif + /* + * Debug image: make sure that an item being added doesn't accidentally + * look like a free item. + */ + ASSERT ((is_add && BV (clib_bihash_is_free) (add_v)) == 0); + b = BV (clib_bihash_get_bucket) (h, hash); BV (clib_bihash_lock_bucket) (b); @@ -769,6 +783,8 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) ( */ for (i = 0; i < limit; i++) { + if (BV (clib_bihash_is_free) (&(v->kvp[i]))) + continue; if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key)) { /* Add but do not overwrite? */ @@ -830,10 +846,13 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) ( { for (i = 0; i < limit; i++) { + /* no sense even looking at this one */ + if (BV (clib_bihash_is_free) (&(v->kvp[i]))) + continue; /* Found the key? Kill it... */ if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key)) { - clib_memset_u8 (&(v->kvp[i]), 0xff, sizeof (*(add_v))); + BV (clib_bihash_mark_free) (&(v->kvp[i])); /* Is the bucket empty? */ if (PREDICT_TRUE (b->refcnt > 1)) { @@ -848,8 +867,13 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) ( b->linear_search = 0; b->log2_pages = 0; /* Clean up the bucket-level kvp array */ - clib_memset_u8 ((b + 1), 0xff, BIHASH_KVP_PER_PAGE * - sizeof (BVT (clib_bihash_kv))); + BVT (clib_bihash_kv) *v = (void *) (b + 1); + int j; + for (j = 0; j < BIHASH_KVP_PER_PAGE; j++) + { + BV (clib_bihash_mark_free) (v); + v++; + } CLIB_MEMORY_STORE_BARRIER (); BV (clib_bihash_unlock_bucket) (b); BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1); -- cgit 1.2.3-korg