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

15 files changed, 196 insertions, 35 deletions

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<<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 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) (
   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 @@ 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?");
     }