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/plugins/cnat/cnat_bihash.h | 9 +++-- src/plugins/cnat/cnat_session.c | 2 +- src/vnet/l2/l2_fib.c | 2 +- src/vppinfra/bihash_12_4.h | 9 +++-- src/vppinfra/bihash_16_8.h | 9 +++-- src/vppinfra/bihash_16_8_32.h | 9 +++-- src/vppinfra/bihash_24_16.h | 9 +++-- src/vppinfra/bihash_24_8.h | 9 +++-- src/vppinfra/bihash_32_8.h | 9 +++-- src/vppinfra/bihash_40_8.h | 9 +++-- src/vppinfra/bihash_48_8.h | 9 +++-- src/vppinfra/bihash_8_16.h | 8 ++++- src/vppinfra/bihash_8_8.h | 8 ++++- src/vppinfra/bihash_8_8_stats.h | 8 ++++- src/vppinfra/bihash_template.c | 50 ++++++++++++++++++++-------- src/vppinfra/bihash_template.h | 12 +++++-- src/vppinfra/bihash_vec8_8.h | 8 ++++- src/vppinfra/test_bihash_template.c | 65 +++++++++++++++++++++++++++++++++++++ 18 files changed, 205 insertions(+), 39 deletions(-) diff --git a/src/plugins/cnat/cnat_bihash.h b/src/plugins/cnat/cnat_bihash.h index c488e61a07d..75099f6bfdb 100644 --- a/src/plugins/cnat/cnat_bihash.h +++ b/src/plugins/cnat/cnat_bihash.h @@ -44,11 +44,16 @@ typedef struct u64 value[7]; } clib_bihash_kv_40_56_t; +static inline void +clib_bihash_mark_free_40_56 (clib_bihash_kv_40_56_t *v) +{ + v->value[0] = 0xFEEDFACE8BADF00DULL; +} + static inline int clib_bihash_is_free_40_56 (const clib_bihash_kv_40_56_t *v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->key[0] == ~0ULL && v->value[0] == ~0ULL) + if (v->value[0] == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/plugins/cnat/cnat_session.c b/src/plugins/cnat/cnat_session.c index fa04de602b4..ea34d913217 100644 --- a/src/plugins/cnat/cnat_session.c +++ b/src/plugins/cnat/cnat_session.c @@ -238,7 +238,7 @@ cnat_session_scan (vlib_main_t * vm, f64 start_time, int i) { for (k = 0; k < BIHASH_KVP_PER_PAGE; k++) { - if (v->kvp[k].key[0] == ~0ULL && v->kvp[k].value[0] == ~0ULL) + if (BV (clib_bihash_is_free) (&v->kvp[k])) continue; cnat_session_t *session = (cnat_session_t *) & v->kvp[k]; diff --git a/src/vnet/l2/l2_fib.c b/src/vnet/l2/l2_fib.c index d9d6710fd15..ad301af78f4 100644 --- a/src/vnet/l2/l2_fib.c +++ b/src/vnet/l2/l2_fib.c @@ -1149,7 +1149,7 @@ l2fib_scan (vlib_main_t * vm, f64 start_time, u8 event_only) { for (k = 0; k < BIHASH_KVP_PER_PAGE; k++) { - if (v->kvp[k].key == ~0ULL && v->kvp[k].value == ~0ULL) + if (BV (clib_bihash_is_free) (&v->kvp[k])) continue; l2fib_entry_key_t key = {.raw = v->kvp[k].key }; diff --git a/src/vppinfra/bihash_12_4.h b/src/vppinfra/bihash_12_4.h index fe050e15924..3fdf1847861 100644 --- a/src/vppinfra/bihash_12_4.h +++ b/src/vppinfra/bihash_12_4.h @@ -36,11 +36,16 @@ typedef union u64 as_u64[2]; } clib_bihash_kv_12_4_t; +static inline void +clib_bihash_mark_free_12_4 (clib_bihash_kv_12_4_t *v) +{ + v->value = 0xFEEDFACE; +} + static inline int clib_bihash_is_free_12_4 (const clib_bihash_kv_12_4_t *v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->as_u64[0] == ~0ULL && v->value == ~0) + if (v->value == 0xFEEDFACE) return 1; return 0; } diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h index 6b116bcf3e4..67aa678efa9 100644 --- a/src/vppinfra/bihash_16_8.h +++ b/src/vppinfra/bihash_16_8.h @@ -43,11 +43,16 @@ typedef struct u64 value; } clib_bihash_kv_16_8_t; +static inline void +clib_bihash_mark_free_16_8 (clib_bihash_kv_16_8_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + static inline int clib_bihash_is_free_16_8 (clib_bihash_kv_16_8_t * v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->key[0] == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_16_8_32.h b/src/vppinfra/bihash_16_8_32.h index 9453f88ace7..d899253302c 100644 --- a/src/vppinfra/bihash_16_8_32.h +++ b/src/vppinfra/bihash_16_8_32.h @@ -43,11 +43,16 @@ typedef struct u64 value; } clib_bihash_kv_16_8_32_t; +static inline void +clib_bihash_mark_free_16_8_32 (clib_bihash_kv_16_8_32_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + static inline int clib_bihash_is_free_16_8_32 (clib_bihash_kv_16_8_32_t * v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->key[0] == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_24_16.h b/src/vppinfra/bihash_24_16.h index b9279a88fab..b421ab12edc 100644 --- a/src/vppinfra/bihash_24_16.h +++ b/src/vppinfra/bihash_24_16.h @@ -43,11 +43,16 @@ typedef struct u64 value[2]; } clib_bihash_kv_24_16_t; +static inline void +clib_bihash_mark_free_24_16 (clib_bihash_kv_24_16_t *v) +{ + v->value[0] = 0xFEEDFACE8BADF00DULL; +} + static inline int clib_bihash_is_free_24_16 (const clib_bihash_kv_24_16_t * v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->key[0] == ~0ULL && v->value[0] == ~0ULL && v->value[1] == ~0ULL) + if (v->value[0] == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h index e83437439d1..14e5225ccfd 100644 --- a/src/vppinfra/bihash_24_8.h +++ b/src/vppinfra/bihash_24_8.h @@ -43,11 +43,16 @@ typedef struct u64 value; } clib_bihash_kv_24_8_t; +static inline void +clib_bihash_mark_free_24_8 (clib_bihash_kv_24_8_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + static inline int clib_bihash_is_free_24_8 (const clib_bihash_kv_24_8_t * v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->key[0] == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_32_8.h b/src/vppinfra/bihash_32_8.h index 52a18352d71..8139a0eab62 100644 --- a/src/vppinfra/bihash_32_8.h +++ b/src/vppinfra/bihash_32_8.h @@ -43,11 +43,16 @@ typedef struct u64 value; } clib_bihash_kv_32_8_t; +static inline void +clib_bihash_mark_free_32_8 (clib_bihash_kv_32_8_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + static inline int clib_bihash_is_free_32_8 (const clib_bihash_kv_32_8_t *v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->key[0] == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_40_8.h b/src/vppinfra/bihash_40_8.h index f64784f0488..27207a3a69c 100644 --- a/src/vppinfra/bihash_40_8.h +++ b/src/vppinfra/bihash_40_8.h @@ -44,11 +44,16 @@ typedef struct u64 value; } clib_bihash_kv_40_8_t; +static inline void +clib_bihash_mark_free_40_8 (clib_bihash_kv_40_8_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + static inline int clib_bihash_is_free_40_8 (const clib_bihash_kv_40_8_t * v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->key[0] == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_48_8.h b/src/vppinfra/bihash_48_8.h index 928b10217ec..dbc92c3df1d 100644 --- a/src/vppinfra/bihash_48_8.h +++ b/src/vppinfra/bihash_48_8.h @@ -42,11 +42,16 @@ typedef struct u64 value; } clib_bihash_kv_48_8_t; +static inline void +clib_bihash_mark_free_48_8 (clib_bihash_kv_48_8_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + static inline int clib_bihash_is_free_48_8 (const clib_bihash_kv_48_8_t * v) { - /* Free values are clib_memset to 0xff, check a bit... */ - if (v->key[0] == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_8_16.h b/src/vppinfra/bihash_8_16.h index a17bddb92c2..36ddda7149b 100644 --- a/src/vppinfra/bihash_8_16.h +++ b/src/vppinfra/bihash_8_16.h @@ -44,13 +44,19 @@ typedef struct u64 value[2]; /**< the value */ } clib_bihash_kv_8_16_t; +static inline void +clib_bihash_mark_free_8_16 (clib_bihash_kv_8_16_t *v) +{ + v->value[0] = 0xFEEDFACE8BADF00DULL; +} + /** Decide if a clib_bihash_kv_8_16_t instance is free @param v- pointer to the (key,value) pair */ static inline int clib_bihash_is_free_8_16 (clib_bihash_kv_8_16_t * v) { - if (v->key == ~0ULL && v->value[0] == ~0ULL && v->value[1] == ~0ULL) + if (v->value[0] == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h index 2fdd2ed7aef..2471871fc81 100644 --- a/src/vppinfra/bihash_8_8.h +++ b/src/vppinfra/bihash_8_8.h @@ -44,13 +44,19 @@ typedef struct u64 value; /**< the value */ } clib_bihash_kv_8_8_t; +static inline void +clib_bihash_mark_free_8_8 (clib_bihash_kv_8_8_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + /** Decide if a clib_bihash_kv_8_8_t instance is free @param v- pointer to the (key,value) pair */ static inline int clib_bihash_is_free_8_8 (clib_bihash_kv_8_8_t * v) { - if (v->key == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/bihash_8_8_stats.h b/src/vppinfra/bihash_8_8_stats.h index 2237a0d624f..14702dfd782 100644 --- a/src/vppinfra/bihash_8_8_stats.h +++ b/src/vppinfra/bihash_8_8_stats.h @@ -45,13 +45,19 @@ typedef struct u64 value; /**< the value */ } clib_bihash_kv_8_8_stats_t; +static inline void +clib_bihash_mark_free_8_8_stats (clib_bihash_kv_8_8_stats_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + /** Decide if a clib_bihash_kv_8_8_t instance is free @param v- pointer to the (key,value) pair */ static inline int clib_bihash_is_free_8_8_stats (clib_bihash_kv_8_8_stats_t * v) { - if (v->key == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } 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); diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index c4e120e4a1f..e8a2c01cece 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -410,6 +410,7 @@ BV (clib_bihash_get_bucket) (BVT (clib_bihash) * h, u64 hash) static inline int BV (clib_bihash_search_inline_with_hash) (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * key_result) { + BVT (clib_bihash_kv) rv; BVT (clib_bihash_value) * v; BVT (clib_bihash_bucket) * b; int i, limit; @@ -455,7 +456,10 @@ static inline int BV (clib_bihash_search_inline_with_hash) { if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key)) { - *key_result = v->kvp[i]; + rv = v->kvp[i]; + if (BV (clib_bihash_is_free) (&rv)) + return -1; + *key_result = rv; return 0; } } @@ -509,6 +513,7 @@ static inline int BV (clib_bihash_search_inline_2_with_hash) (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) { + BVT (clib_bihash_kv) rv; BVT (clib_bihash_value) * v; BVT (clib_bihash_bucket) * b; int i, limit; @@ -556,7 +561,10 @@ static inline int BV (clib_bihash_search_inline_2_with_hash) { if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key)) { - *valuep = v->kvp[i]; + rv = v->kvp[i]; + if (BV (clib_bihash_is_free) (&rv)) + return -1; + *valuep = rv; return 0; } } diff --git a/src/vppinfra/bihash_vec8_8.h b/src/vppinfra/bihash_vec8_8.h index 15c6d8cebff..822f1bcc51f 100644 --- a/src/vppinfra/bihash_vec8_8.h +++ b/src/vppinfra/bihash_vec8_8.h @@ -42,13 +42,19 @@ typedef struct u64 value; /**< the value */ } clib_bihash_kv_vec8_8_t; +static inline void +clib_bihash_mark_free_vec8_8 (clib_bihash_kv_vec8_8_t *v) +{ + v->value = 0xFEEDFACE8BADF00DULL; +} + /** Decide if a clib_bihash_kv_vec8_8_t instance is free @param v- pointer to the (key,value) pair */ static inline int clib_bihash_is_free_vec8_8 (clib_bihash_kv_vec8_8_t * v) { - if (v->key == ~0ULL && v->value == ~0ULL) + if (v->value == 0xFEEDFACE8BADF00DULL) return 1; return 0; } diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c index 155b8bd408d..af3ebb2ef0e 100644 --- a/src/vppinfra/test_bihash_template.c +++ b/src/vppinfra/test_bihash_template.c @@ -247,6 +247,59 @@ test_bihash_threads (test_main_t * tm) return 0; } +static clib_error_t * +test_bihash_vanilla_overwrite (test_main_t *tm) +{ + int i; + BVT (clib_bihash) * h; + BVT (clib_bihash_kv) kv; + + h = &tm->hash; + +#if BIHASH_32_64_SVM + BV (clib_bihash_initiator_init_svm) + (h, "test", tm->nbuckets, 0x30000000 /* base_addr */, tm->hash_memory_size); +#else + BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); +#endif + + for (i = 0; i < 100; i++) + { + kv.key = 12345; + kv.value = i; + + BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */); + } + + fformat (stdout, "End of run, should one item...\n"); + fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */); + BV (clib_bihash_free) (h); + return 0; +} + +static clib_error_t * +test_bihash_value_assert (test_main_t *tm) +{ + BVT (clib_bihash) * h; + BVT (clib_bihash_kv) kv; + + h = &tm->hash; + +#if BIHASH_32_64_SVM + BV (clib_bihash_initiator_init_svm) + (h, "test", tm->nbuckets, 0x30000000 /* base_addr */, tm->hash_memory_size); +#else + BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); +#endif + + kv.key = 12345; + kv.value = 0xFEEDFACE8BADF00DULL; + + fformat (stderr, "The following add should ASSERT...\n"); + BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */); + + return 0; +} static clib_error_t * test_bihash (test_main_t * tm) @@ -514,6 +567,10 @@ test_bihash_main (test_main_t * tm) tm->verbose = 1; else if (unformat (i, "stale-overwrite")) which = 3; + else if (unformat (i, "overwrite")) + which = 4; + else if (unformat (i, "value-assert")) + which = 5; else return clib_error_return (0, "unknown input '%U'", format_unformat_error, i); @@ -542,6 +599,14 @@ test_bihash_main (test_main_t * tm) error = test_bihash_stale_overwrite (tm); break; + case 4: + error = test_bihash_vanilla_overwrite (tm); + break; + + case 5: + error = test_bihash_value_assert (tm); + break; + default: return clib_error_return (0, "no such test?"); } -- cgit 1.2.3-korg