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/plugins/cnat/cnat_bihash.h b/src/plugins/cnat/cnat_bihash.h
index c488e61..75099f6 100644 (file)
--- 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 fa04de6..ea34d91 100644 (file)
--- 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 d9d6710..ad301af 100644 (file)
--- 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 fe050e1..3fdf184 100644 (file)
--- 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 6b116bc..67aa678 100644 (file)
--- 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 9453f88..d899253 100644 (file)
--- 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 b9279a8..b421ab1 100644 (file)
--- 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 e834374..14e5225 100644 (file)
--- 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 52a1835..8139a0e 100644 (file)
--- 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 f64784f..27207a3 100644 (file)
--- 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 928b102..dbc92c3 100644 (file)
--- 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 a17bddb..36ddda7 100644 (file)
--- 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 2fdd2ed..2471871 100644 (file)
--- 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 2237a0d..14702df 100644 (file)
--- 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 4883050..38354a1 100644 (file)
--- 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 c4e120e..e8a2c01 100644 (file)
--- 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 15c6d8c..822f1bc 100644 (file)
--- 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 155b8bd..af3ebb2 100644 (file)
--- 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?");
     }