vppinfra: fix minor cuckoo bugs and add cuckoo_16_8

Type: improvement

Change-Id: If1164d2eb81e9d4748436cb1bb8b164857d70565
Signed-off-by: Klement Sekera <ksekera@cisco.com>

5 files changed, 170 insertions, 26 deletions

diff --git a/src/vppinfra/CMakeLists.txt b/src/vppinfra/CMakeLists.txt
index 7723e6bad5d..3e396e35371 100644
--- a/src/vppinfra/CMakeLists.txt
+++ b/src/vppinfra/CMakeLists.txt
@@ -43,7 +43,6 @@ set(VPPINFRA_SRCS
   backtrace.c
   bihash_all_vector.c
   cpu.c
-  cuckoo_template.c
   dlmalloc.c
   elf.c
   elog.c
@@ -109,6 +108,10 @@ set(VPPINFRA_HEADERS
   clib.h
   cpu.h
   crc32.h
+  cuckoo_8_8.h
+  cuckoo_16_8.h
+  cuckoo_template.h
+  cuckoo_template.c
   dlist.h
   dlmalloc.h
   elf_clib.h
diff --git a/src/vppinfra/cuckoo_16_8.h b/src/vppinfra/cuckoo_16_8.h
new file mode 100644
index 00000000000..0cc7b57bee0
--- /dev/null
+++ b/src/vppinfra/cuckoo_16_8.h
@@ -0,0 +1,130 @@
+/*
+ * Copyright (c) 2017 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#undef CLIB_CUCKOO_TYPE
+
+#define CLIB_CUCKOO_TYPE _16_8
+#define CLIB_CUCKOO_KVP_PER_BUCKET (4)
+#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET (2)
+#define CLIB_CUCKOO_BFS_MAX_STEPS (2000)
+#define CLIB_CUCKOO_BFS_MAX_PATH_LENGTH (8)
+
+#ifndef __included_cuckoo_16_8_h__
+#define __included_cuckoo_16_8_h__
+
+#include <vppinfra/heap.h>
+#include <vppinfra/format.h>
+#include <vppinfra/pool.h>
+#include <vppinfra/xxhash.h>
+#include <vppinfra/cuckoo_debug.h>
+#include <vppinfra/cuckoo_common.h>
+
+#undef CLIB_CUCKOO_OPTIMIZE_PREFETCH
+#undef CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH
+#undef CLIB_CUCKOO_OPTIMIZE_UNROLL
+#undef CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
+#define CLIB_CUCKOO_OPTIMIZE_PREFETCH 1
+#define CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH 1
+#define CLIB_CUCKOO_OPTIMIZE_UNROLL 1
+#define CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH 1
+
+#if __SSE4_2__ && !defined (__i386__)
+#include <x86intrin.h>
+#endif
+
+/** 8 octet key, 8 octet key value pair */
+typedef struct
+{
+  u64 key[2];	/**< the key */
+  u64 value; /**< the value */
+} clib_cuckoo_kv_16_8_t;
+
+/** Decide if a clib_cuckoo_kv_16_8_t instance is free
+    @param v- pointer to the (key,value) pair
+*/
+always_inline int
+clib_cuckoo_kv_is_free_16_8 (const clib_cuckoo_kv_16_8_t * v)
+{
+  if (v->key[0] == ~0ULL && v->value == ~0ULL)
+    return 1;
+  return 0;
+}
+
+always_inline void
+clib_cuckoo_kv_set_free_16_8 (clib_cuckoo_kv_16_8_t * v)
+{
+  clib_memset (v, 0xff, sizeof (*v));
+}
+
+/** Format a clib_cuckoo_kv_16_8_t instance
+    @param s - u8 * vector under construction
+    @param args (vararg) - the (key,value) pair to format
+    @return s - the u8 * vector under construction
+*/
+always_inline u8 *
+format_cuckoo_kvp_16_8 (u8 * s, va_list * args)
+{
+  clib_cuckoo_kv_16_8_t *v = va_arg (*args, clib_cuckoo_kv_16_8_t *);
+
+  if (clib_cuckoo_kv_is_free_16_8 (v))
+    {
+      s = format (s, " -- empty -- ");
+    }
+  else
+    {
+      s =
+	format (s, "key %llu%llu value %llu", v->key[0], v->key[1], v->value);
+    }
+  return s;
+}
+
+always_inline u64
+clib_cuckoo_hash_16_8 (clib_cuckoo_kv_16_8_t * v)
+{
+#ifdef clib_crc32c_uses_intrinsics
+  return clib_crc32c ((u8 *) v->key, 16);
+#else
+  u64 tmp = v->key[0] ^ v->key[1];
+  return clib_xxhash (tmp);
+#endif
+}
+
+/** Compare two clib_cuckoo_kv_16_8_t instances
+    @param a - first key
+    @param b - second key
+*/
+always_inline int
+clib_cuckoo_key_compare_16_8 (u64 * a, u64 * b)
+{
+#if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
+  u64x2 v;
+  v = u64x2_load_unaligned (a) ^ u64x2_load_unaligned (b);
+  return u64x2_is_all_zero (v);
+#else
+  return ((a[0] ^ b[0]) | (a[1] ^ b[1])) == 0;
+#endif
+}
+
+#undef __included_cuckoo_template_h__
+#include <vppinfra/cuckoo_template.h>
+
+#endif /* __included_cuckoo_16_8_h__ */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/cuckoo_8_8.h b/src/vppinfra/cuckoo_8_8.h
index a3d07c870eb..ace535b58f6 100644
--- a/src/vppinfra/cuckoo_8_8.h
+++ b/src/vppinfra/cuckoo_8_8.h
@@ -79,7 +79,7 @@ format_cuckoo_kvp_8_8 (u8 * s, va_list * args)
 
   if (clib_cuckoo_kv_is_free_8_8 (v))
     {
-      s = format (s, " -- empty -- ", v->key, v->value);
+      s = format (s, " -- empty -- ");
     }
   else
     {
@@ -108,10 +108,8 @@ clib_cuckoo_key_compare_8_8 (u64 a, u64 b)
   return a == b;
 }
 
-#if 0
 #undef __included_cuckoo_template_h__
 #include <vppinfra/cuckoo_template.h>
-#endif
 
 #endif /* __included_cuckoo_8_8_h__ */
 
diff --git a/src/vppinfra/cuckoo_template.c b/src/vppinfra/cuckoo_template.c
index c48032a319c..8cd2a2be2b5 100644
--- a/src/vppinfra/cuckoo_template.c
+++ b/src/vppinfra/cuckoo_template.c
@@ -21,7 +21,6 @@
  */
 
 #include <vppinfra/vec.h>
-#include <vppinfra/cuckoo_template.h>
 
 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
 			     CVT (clib_cuckoo_kv) * search_v,
@@ -100,8 +99,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
   CVT (clib_cuckoo_bucket) * bucket;
   uword bucket_idx = 0;
   /* *INDENT-OFF* */
-  clib_cuckoo_foreach_bucket (bucket, h)
-  {
+  clib_cuckoo_foreach_bucket (bucket, h, {
     int i = 0;
     int used = 0;
     clib_cuckoo_bucket_foreach_idx (i)
@@ -110,8 +108,8 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
       if (!CV (clib_cuckoo_kv_is_free) (elt))
         {
           u64 hash = CV (clib_cuckoo_hash) (elt);
-          clib_cuckoo_lookup_info_t lookup = CV (clib_cuckoo_calc_lookup) (
-              CV (clib_cuckoo_get_snapshot) (h), hash);
+          clib_cuckoo_lookup_info_t lookup =
+              CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
           CVT (clib_cuckoo_kv) kv = *elt;
           int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
           if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
@@ -121,7 +119,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
                                bucket->reduced_hashes[i]);
               CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
             }
-          ASSERT (aux.bucket1 == bucket_idx || aux.bucket2 == bucket_idx);
+          ASSERT (lookup.bucket1 == bucket_idx || lookup.bucket2 == bucket_idx);
           ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
           ++used;
         }
@@ -129,7 +127,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
     clib_cuckoo_bucket_aux_t aux = bucket->aux;
     ASSERT (used == clib_cuckoo_bucket_aux_get_use_count (aux));
     ++bucket_idx;
-  }
+  });
   /* *INDENT-ON* */
   // CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h);
 }
@@ -820,14 +818,15 @@ static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h,
 }
 
 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
-			      CVT (clib_cuckoo_kv) * kvp, int is_add)
+			      CVT (clib_cuckoo_kv) * kvp, int is_add,
+			      int dont_overwrite)
 {
   CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp),
 		   kvp);
   clib_cuckoo_lookup_info_t lookup;
   u64 hash = CV (clib_cuckoo_hash) (kvp);
-  clib_spinlock_lock (&h->writer_lock);
   u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
+  clib_spinlock_lock (&h->writer_lock);
 restart:
   lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
   CVT (clib_cuckoo_bucket) * b =
@@ -846,19 +845,30 @@ restart:
     {
       if (is_add)
 	{
-	  /* prevent readers reading this bucket while we switch the values */
-	  clib_cuckoo_bucket_aux_t aux =
-	    CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
-	  clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
-	  CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
-			   found, b->reduced_hashes[found - b->elts]);
-	  CV (clib_cuckoo_bucket_unlock) (b, aux);
+	  if (dont_overwrite)
+	    {
+	      CLIB_CUCKOO_DBG ("Refused replacing existing %U",
+			       CV (format_cuckoo_elt), found,
+			       b->reduced_hashes[found - b->elts]);
+	      rv = CLIB_CUCKOO_ERROR_AGAIN;
+	    }
+	  else
+	    {
+	      /* prevent readers reading this bucket while we switch the values */
+	      clib_cuckoo_bucket_aux_t aux =
+		CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
+	      clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
+	      CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
+			       found, b->reduced_hashes[found - b->elts]);
+	      CV (clib_cuckoo_bucket_unlock) (b, aux);
+	      rv = CLIB_CUCKOO_ERROR_SUCCESS;
+	    }
 	}
       else
 	{
 	  CV (clib_cuckoo_free_elt_in_bucket) (b, found);
+	  rv = CLIB_CUCKOO_ERROR_SUCCESS;
 	}
-      rv = CLIB_CUCKOO_ERROR_SUCCESS;
       CLIB_CUCKOO_DEEP_SELF_CHECK (h);
       goto unlock;
     }
@@ -876,9 +886,12 @@ restart:
   CLIB_CUCKOO_DEEP_SELF_CHECK (h);
   if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
     {
-    CLIB_CUCKOO_DBG ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U", aux.bucket1, aux.bucket2, CV (format_cuckoo_bucket), CV (clib_cuckoo_bucindent: Standaindent: Standard input: 903: Error: Unmatched 'else' rd input: 865: Error:Unmatched 'else' ket_at_index) (h, aux.bucket1),
-		       CV (format_cuckoo_bucket),
-		       CV (clib_cuckoo_bucket_at_index) (h, aux.bucket2));
+      CLIB_CUCKOO_DBG
+	("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U",
+	 lookup.bucket1, lookup.bucket2, CV (format_cuckoo_bucket),
+	 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1),
+	 CV (format_cuckoo_bucket),
+	 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2));
       /* slow path */
       rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
       CLIB_CUCKOO_DEEP_SELF_CHECK (h);
diff --git a/src/vppinfra/cuckoo_template.h b/src/vppinfra/cuckoo_template.h
index c3b2bc98aaa..06c4afdc79b 100644
--- a/src/vppinfra/cuckoo_template.h
+++ b/src/vppinfra/cuckoo_template.h
@@ -35,7 +35,6 @@
 #include <vppinfra/error.h>
 #include <vppinfra/hash.h>
 #include <vppinfra/cache.h>
-#include <vppinfra/cuckoo_8_8.h>
 
 #ifndef CLIB_CUCKOO_TYPE
 #error CLIB_CUCKOO_TYPE not defined
@@ -301,7 +300,8 @@ void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h);
 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h);
 
 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
-			      CVT (clib_cuckoo_kv) * add_v, int is_add);
+			      CVT (clib_cuckoo_kv) * add_v, int is_add,
+			      int dont_overwrite);
 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
 			     CVT (clib_cuckoo_kv) * search_v,
 			     CVT (clib_cuckoo_kv) * return_v);