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 <dave@barachs.net>
Change-Id: I6a1aa8a2c30bc70bec4b696ce7b17c2839927065
diff --git a/src/vppinfra/bihash_12_4.h b/src/vppinfra/bihash_12_4.h
index fe050e1..3fdf184 100644
--- a/src/vppinfra/bihash_12_4.h
+++ b/src/vppinfra/bihash_12_4.h
@@ -36,11 +36,16 @@
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 6b116bc..67aa678 100644
--- a/src/vppinfra/bihash_16_8.h
+++ b/src/vppinfra/bihash_16_8.h
@@ -43,11 +43,16 @@
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 9453f88..d899253 100644
--- a/src/vppinfra/bihash_16_8_32.h
+++ b/src/vppinfra/bihash_16_8_32.h
@@ -43,11 +43,16 @@
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 b9279a8..b421ab1 100644
--- a/src/vppinfra/bihash_24_16.h
+++ b/src/vppinfra/bihash_24_16.h
@@ -43,11 +43,16 @@
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 e834374..14e5225 100644
--- a/src/vppinfra/bihash_24_8.h
+++ b/src/vppinfra/bihash_24_8.h
@@ -43,11 +43,16 @@
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 52a1835..8139a0e 100644
--- a/src/vppinfra/bihash_32_8.h
+++ b/src/vppinfra/bihash_32_8.h
@@ -43,11 +43,16 @@
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 f64784f..27207a3 100644
--- a/src/vppinfra/bihash_40_8.h
+++ b/src/vppinfra/bihash_40_8.h
@@ -44,11 +44,16 @@
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 928b102..dbc92c3 100644
--- a/src/vppinfra/bihash_48_8.h
+++ b/src/vppinfra/bihash_48_8.h
@@ -42,11 +42,16 @@
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 a17bddb..36ddda7 100644
--- a/src/vppinfra/bihash_8_16.h
+++ b/src/vppinfra/bihash_8_16.h
@@ -44,13 +44,19 @@
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 2fdd2ed..2471871 100644
--- a/src/vppinfra/bihash_8_8.h
+++ b/src/vppinfra/bihash_8_8.h
@@ -44,13 +44,19 @@
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 2237a0d..14702df 100644
--- a/src/vppinfra/bihash_8_8_stats.h
+++ b/src/vppinfra/bihash_8_8_stats.h
@@ -45,13 +45,19 @@
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 4883050..38354a1 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -165,19 +165,23 @@
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 @@
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 @@
initialize:
ASSERT (rv);
- /*
- * Latest gcc complains that the length arg is zero
- * if we replace (1<<log2_pages) with vec_len(rv).
- * No clue.
- */
- clib_memset_u8 (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
+
+ BVT (clib_bihash_kv) * v;
+ v = (BVT (clib_bihash_kv) *) rv;
+
+ for (i = 0; i < BIHASH_KVP_PER_PAGE * (1 << log2_pages); i++)
+ {
+ BV (clib_bihash_mark_free) (v);
+ v++;
+ }
return rv;
}
@@ -713,6 +721,12 @@
ASSERT (h->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 @@
*/
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 @@
{
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 @@
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 c4e120e..e8a2c01 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -410,6 +410,7 @@
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 @@
{
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 @@
(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 @@
{
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 15c6d8c..822f1bc 100644
--- a/src/vppinfra/bihash_vec8_8.h
+++ b/src/vppinfra/bihash_vec8_8.h
@@ -42,13 +42,19 @@
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 155b8bd..af3ebb2 100644
--- a/src/vppinfra/test_bihash_template.c
+++ b/src/vppinfra/test_bihash_template.c
@@ -247,6 +247,59 @@
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 @@
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 @@
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?");
}