add cuckoo hash

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

8 files changed, 2483 insertions, 1 deletions

diff --git a/src/vppinfra.am b/src/vppinfra.am
index daca9954605..96766e8a757 100644
--- a/src/vppinfra.am
+++ b/src/vppinfra.am
@@ -13,7 +13,9 @@
 
 lib_LTLIBRARIES += libvppinfra.la
 
-TESTS =
+TESTS = test_cuckoo_template \
+        test_bihash_template \
+	test_cuckoo_bihash
 
 if ENABLE_TESTS
 TESTS  +=  test_bihash_template \
@@ -47,6 +49,8 @@ noinst_PROGRAMS = $(TESTS)
 check_PROGRAMS	= $(TESTS)
 
 test_bihash_template_SOURCES = vppinfra/test_bihash_template.c
+test_cuckoo_template_SOURCES = vppinfra/test_cuckoo_template.c
+test_cuckoo_bihash_SOURCES = vppinfra/test_cuckoo_bihash.c
 test_dlist_SOURCES = vppinfra/test_dlist.c
 test_elf_SOURCES = vppinfra/test_elf.c
 test_elog_SOURCES = vppinfra/test_elog.c
@@ -75,6 +79,8 @@ test_zvec_SOURCES = vppinfra/test_zvec.c
 # All unit tests use ASSERT for failure
 # So we'll need -DDEBUG to enable ASSERTs
 test_bihash_template_CPPFLAGS =	$(AM_CPPFLAGS) -DCLIB_DEBUG
+test_cuckoo_template_CPPFLAGS =	$(AM_CPPFLAGS) -DCLIB_DEBUG
+test_cuckoo_bihash_CPPFLAGS =	$(AM_CPPFLAGS) -DCLIB_DEBUG
 test_dlist_CPPFLAGS =	$(AM_CPPFLAGS) -DCLIB_DEBUG
 test_elf_CPPFLAGS =	$(AM_CPPFLAGS) -DCLIB_DEBUG
 test_elog_CPPFLAGS =	$(AM_CPPFLAGS) -DCLIB_DEBUG
@@ -101,6 +107,8 @@ test_vec_CPPFLAGS =	$(AM_CPPFLAGS) -DCLIB_DEBUG
 test_zvec_CPPFLAGS =	$(AM_CPPFLAGS) -DCLIB_DEBUG
 
 test_bihash_template_LDADD =	libvppinfra.la
+test_cuckoo_template_LDADD =	libvppinfra.la
+test_cuckoo_bihash_LDADD =	libvppinfra.la
 test_dlist_LDADD =	libvppinfra.la
 test_elf_LDADD =	libvppinfra.la
 test_elog_LDADD =	libvppinfra.la
@@ -127,6 +135,8 @@ test_vec_LDADD =	libvppinfra.la
 test_zvec_LDADD =	libvppinfra.la
 
 test_bihash_template_LDFLAGS = -static
+test_cuckoo_template_LDFLAGS = -static
+test_cuckoo_bihash_LDFLAGS = -static -lpthread
 test_dlist_LDFLAGS = -static
 test_elf_LDFLAGS = -static
 test_elog_LDFLAGS = -static
diff --git a/src/vppinfra/cuckoo_8_8.h b/src/vppinfra/cuckoo_8_8.h
new file mode 100644
index 00000000000..127e4e5b76d
--- /dev/null
+++ b/src/vppinfra/cuckoo_8_8.h
@@ -0,0 +1,122 @@
+/*
+ * 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 _8_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_8_8_h__
+#define __included_cuckoo_8_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
+
+#include <x86intrin.h>
+
+/** 8 octet key, 8 octet key value pair */
+typedef struct
+{
+  u64 key;   /**< the key */
+  u64 value; /**< the value */
+} clib_cuckoo_kv_8_8_t;
+
+/** Decide if a clib_cuckoo_kv_8_8_t instance is free
+    @param v- pointer to the (key,value) pair
+*/
+always_inline int
+clib_cuckoo_kv_is_free_8_8 (const clib_cuckoo_kv_8_8_t * v)
+{
+  if (v->key == ~0ULL && v->value == ~0ULL)
+    return 1;
+  return 0;
+}
+
+always_inline void
+clib_cuckoo_kv_set_free_8_8 (clib_cuckoo_kv_8_8_t * v)
+{
+  memset (v, 0xff, sizeof (*v));
+}
+
+/** Format a clib_cuckoo_kv_8_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_8_8 (u8 * s, va_list * args)
+{
+  clib_cuckoo_kv_8_8_t *v = va_arg (*args, clib_cuckoo_kv_8_8_t *);
+
+  if (clib_cuckoo_kv_is_free_8_8 (v))
+    {
+      s = format (s, " -- empty -- ", v->key, v->value);
+    }
+  else
+    {
+      s = format (s, "key %llu value %llu", v->key, v->value);
+    }
+  return s;
+}
+
+always_inline u64
+clib_cuckoo_hash_8_8 (clib_cuckoo_kv_8_8_t * v)
+{
+#if __SSE4_2__ && !defined (__i386__)
+  return _mm_crc32_u64 (0, v->key);
+#else
+  return clib_xxhash (v->key);
+#endif
+}
+
+/** Compare two clib_cuckoo_kv_8_8_t instances
+    @param a - first key
+    @param b - second key
+*/
+always_inline int
+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__ */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/cuckoo_common.h b/src/vppinfra/cuckoo_common.h
new file mode 100644
index 00000000000..8b7b27aec30
--- /dev/null
+++ b/src/vppinfra/cuckoo_common.h
@@ -0,0 +1,60 @@
+/*
+  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.
+*/
+
+/*
+ * Note: to instantiate the template multiple times in a single file,
+ * #undef __included_cuckoo_template_h__...
+ */
+#ifndef __included_cuckoo_common_h__
+#define __included_cuckoo_common_h__
+
+#include <vppinfra/types.h>
+
+#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
+
+#define foreach_clib_cuckoo_error(F)                \
+  F (CLIB_CUCKOO_ERROR_SUCCESS, 0, "success")             \
+  F (CLIB_CUCKOO_ERROR_NOT_FOUND, -1, "object not found") \
+  F (CLIB_CUCKOO_ERROR_AGAIN, -2, "object busy")
+
+typedef enum
+{
+#define F(n, v, s) n = v,
+  foreach_clib_cuckoo_error (F)
+#undef F
+} clib_cuckoo_error_e;
+
+typedef struct
+{
+  uword bucket1;
+  uword bucket2;
+  u8 reduced_hash;
+} clib_cuckoo_lookup_info_t;
+
+#endif /* __included_cuckoo_common_h__ */
+
+/** @endcond */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/cuckoo_debug.h b/src/vppinfra/cuckoo_debug.h
new file mode 100644
index 00000000000..eb236509935
--- /dev/null
+++ b/src/vppinfra/cuckoo_debug.h
@@ -0,0 +1,83 @@
+/*
+ * 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.
+ */
+/**
+ * @file
+ * @brief cuckoo debugs
+ */
+#ifndef __included_cuckoo_debug_h__
+#define __included_cuckoo_debug_h__
+
+/* controls debug counters */
+#define CLIB_CUCKOO_DEBUG_COUNTERS (0)
+
+/* controls debug prints */
+#define CLIB_CUCKOO_DEBUG (0)
+
+/* controls garbage collection related debug prints */
+#define CLIB_CUCKOO_DEBUG_GC (0)
+
+#if CLIB_CUCKOO_DEBUG
+#define CLIB_CUCKOO_DEBUG_FILE_DEF    \
+  static const char *__file = NULL;   \
+  {                                   \
+    __file = strrchr (__FILE__, '/'); \
+    if (__file)                       \
+      {                               \
+        ++__file;                     \
+      }                               \
+    else                              \
+      {                               \
+        __file = __FILE__;            \
+      }                               \
+  }
+
+#define CLIB_CUCKOO_DBG(fmt, ...)                                         \
+  do                                                                      \
+    {                                                                     \
+      CLIB_CUCKOO_DEBUG_FILE_DEF                                          \
+      static u8 *_s = NULL;                                               \
+      _s = format (_s, "DBG:%s:%d:%s():" fmt, __file, __LINE__, __func__, \
+                   ##__VA_ARGS__);                                        \
+      printf ("%.*s\n", vec_len (_s), _s);                                \
+      vec_reset_length (_s);                                              \
+    }                                                                     \
+  while (0);
+
+#define CLIB_CUCKOO_ERR(fmt, ...)                                         \
+  do                                                                      \
+    {                                                                     \
+      CLIB_CUCKOO_DEBUG_FILE_DEF                                          \
+      static u8 *_s = NULL;                                               \
+      _s = format (_s, "ERR:%s:%d:%s():" fmt, __file, __LINE__, __func__, \
+                   ##__VA_ARGS__);                                        \
+      printf ("%.*s\n", vec_len (_s), _s);                                \
+      vec_reset_length (_s);                                              \
+    }                                                                     \
+  while (0);
+
+#else
+#define CLIB_CUCKOO_DBG(...)
+#define CLIB_CUCKOO_ERR(...)
+#endif
+
+#endif /* __included_cuckoo_debug_h__ */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/cuckoo_template.c b/src/vppinfra/cuckoo_template.c
new file mode 100644
index 00000000000..16537f92b3e
--- /dev/null
+++ b/src/vppinfra/cuckoo_template.c
@@ -0,0 +1,982 @@
+/*
+ * 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.
+ */
+
+/*
+ * cuckoo hash implementation based on paper
+ * 'Algorithmic Improvements for Fast Concurrent Cuckoo Hashing'
+ * by Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman
+ * and their libcuckoo implementation (https://github.com/efficient/libcuckoo)
+ */
+
+#include <vppinfra/vec.h>
+#include <vppinfra/cuckoo_template.h>
+
+int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
+			     CVT (clib_cuckoo_kv) * search_v,
+			     CVT (clib_cuckoo_kv) * return_v)
+{
+  CVT (clib_cuckoo_kv) tmp = *search_v;
+  int rv = CV (clib_cuckoo_search_inline) (h, &tmp);
+  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
+    {
+      *return_v = tmp;
+    }
+  return rv;
+}
+
+static
+CVT (clib_cuckoo_bucket) *
+CV (clib_cuckoo_bucket_at_index) (CVT (clib_cuckoo) * h, uword bucket)
+{
+  return vec_elt_at_index (h->buckets, bucket);
+}
+
+static uword CV (clib_cuckoo_get_nbuckets) (CVT (clib_cuckoo) * h)
+{
+  return vec_len (h->buckets);
+}
+
+static inline uword
+CV (clib_cuckoo_elt_in_bucket_to_offset) (CVT (clib_cuckoo_bucket) * b,
+					  CVT (clib_cuckoo_kv) * e)
+{
+  ASSERT (e >= b->elts);
+  ASSERT (e <= &b->elts[sizeof (b->elts) / sizeof (b->elts[0]) - 1]);
+  return e - b->elts;
+}
+
+u8 *CV (format_cuckoo_elt) (u8 * s, va_list * args)
+{
+  CVT (clib_cuckoo_kv) * elt = va_arg (*args, CVT (clib_cuckoo_kv) *);
+  unsigned reduced_hash = va_arg (*args, unsigned);
+  if (CV (clib_cuckoo_kv_is_free) (elt))
+    {
+      s = format (s, "[ -- empty -- ]");
+    }
+  else
+    {
+      s = format (s, "[%U, reduced hash: %u]", CV (format_cuckoo_kvp), elt,
+		  reduced_hash);
+    }
+  return s;
+}
+
+u8 *CV (format_cuckoo_bucket) (u8 * s, va_list * args)
+{
+  CVT (clib_cuckoo_bucket) * bucket =
+    va_arg (*args, CVT (clib_cuckoo_bucket) *);
+  int i = 0;
+
+  /* *INDENT-OFF* */
+  clib_cuckoo_bucket_foreach_idx (i)
+  {
+    CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
+    s = format (s, "bucket %p, offset %d: %U\n", bucket, i,
+                CV (format_cuckoo_elt), elt, bucket->reduced_hashes[i]);
+  }
+  /* *INDENT-ON* */
+  clib_cuckoo_bucket_aux_t aux = bucket->aux;
+  s = format (s, "version: %lld, use count: %d\n",
+	      clib_cuckoo_bucket_aux_get_version (aux),
+	      clib_cuckoo_bucket_aux_get_use_count (aux));
+  return s;
+}
+
+#if CLIB_CUCKOO_DEBUG
+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)
+  {
+    int i = 0;
+    int used = 0;
+    clib_cuckoo_bucket_foreach_idx (i)
+    {
+      CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
+      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);
+          CVT (clib_cuckoo_kv) kv = *elt;
+          int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
+          if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
+            {
+              CLIB_CUCKOO_DBG ("Search for elt `%U' failed!",
+                               CV (format_cuckoo_elt), elt,
+                               bucket->reduced_hashes[i]);
+              CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
+            }
+          ASSERT (aux.bucket1 == bucket_idx || aux.bucket2 == bucket_idx);
+          ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
+          ++used;
+        }
+    }
+    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);
+}
+
+#define CLIB_CUCKOO_DEEP_SELF_CHECK(h) CV (clib_cuckoo_deep_self_check) (h)
+#define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b)                                 \
+  do                                                                        \
+    {                                                                       \
+      int i;                                                                \
+      int min_free = CLIB_CUCKOO_KVP_PER_BUCKET;                            \
+      int max_used = 0;                                                     \
+      clib_cuckoo_bucket_foreach_idx (i)                                    \
+      {                                                                     \
+        if (!CV (clib_cuckoo_kv_is_free) (b->elts + i))                     \
+          {                                                                 \
+            max_used = i;                                                   \
+          }                                                                 \
+        if (CV (clib_cuckoo_kv_is_free) (b->elts +                          \
+                                         (CLIB_CUCKOO_KVP_PER_BUCKET - i))) \
+          {                                                                 \
+            min_free = i;                                                   \
+          }                                                                 \
+      }                                                                     \
+      ASSERT (min_free > max_used);                                         \
+    }                                                                       \
+  while (0)
+
+#else
+#define CLIB_CUCKOO_DEEP_SELF_CHECK(h)
+#define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b)
+#endif
+
+void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
+			    uword nbuckets,
+			    void (*garbage_callback) (CVT (clib_cuckoo) *,
+						      void *),
+			    void *garbage_ctx)
+{
+  uword log2_nbuckets = max_log2 (nbuckets);
+  nbuckets = 1 << (log2_nbuckets);
+  CLIB_CUCKOO_DBG ("New cuckoo, adjusted nbuckets %wu", nbuckets);
+  CVT (clib_cuckoo_bucket) * buckets = NULL;
+  vec_validate_aligned (buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
+  ASSERT (nbuckets == vec_len (buckets));
+  h->buckets = buckets;
+  clib_spinlock_init (&h->writer_lock);
+  /* mark all elements free ... */
+  CVT (clib_cuckoo_bucket) * bucket;
+  /* *INDENT-OFF* */
+  clib_cuckoo_foreach_bucket (
+      bucket, h, { memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
+  /* *INDENT-ON* */
+  h->name = name;
+  h->garbage_callback = garbage_callback;
+  h->garbage_ctx = garbage_ctx;
+}
+
+void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h)
+{
+  memset (h, 0, sizeof (*h));
+}
+
+static clib_cuckoo_bucket_aux_t
+CV (clib_cuckoo_bucket_version_bump_and_lock) (CVT (clib_cuckoo_bucket) * b)
+{
+  clib_cuckoo_bucket_aux_t aux = b->aux;
+  u64 version = clib_cuckoo_bucket_aux_get_version (aux);
+  u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
+  u8 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
+  ASSERT (0 == writer_flag);
+  aux = clib_cuckoo_bucket_aux_pack (version + 1, use_count, 1);
+  b->aux = aux;
+  return aux;
+}
+
+static void CV (clib_cuckoo_bucket_unlock) (CVT (clib_cuckoo_bucket) * b,
+					    clib_cuckoo_bucket_aux_t aux)
+{
+  u64 version = clib_cuckoo_bucket_aux_get_version (aux);
+  u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
+  u8 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
+  ASSERT (1 == writer_flag);
+  aux = clib_cuckoo_bucket_aux_pack (version, use_count, 0);
+  b->aux = aux;
+}
+
+#define CLIB_CUCKOO_DEBUG_PATH (1)
+#define CLIB_CUCKOO_DEBUG_PATH_DETAIL (0)
+
+#if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH
+static u8 *CV (format_cuckoo_path) (u8 * s, va_list * args);
+#endif
+
+static clib_cuckoo_path_t *CV (clib_cuckoo_path_get) (CVT (clib_cuckoo) * h)
+{
+  clib_cuckoo_path_t *path;
+  pool_get (h->paths, path);
+  memset (path, 0, sizeof (*path));
+#if CLIB_CUCKOO_DEBUG_PATH_DETAIL
+  CLIB_CUCKOO_DBG ("Get path @%lu", (long unsigned) (path - h->paths));
+#endif
+  return path;
+}
+
+static void CV (clib_cuckoo_path_put) (CVT (clib_cuckoo) * h, uword path_idx)
+{
+  clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
+#if CLIB_CUCKOO_DEBUG_PATH_DETAIL
+  CLIB_CUCKOO_DBG ("Put path @%lu", (long unsigned) (path - h->paths));
+#endif
+  pool_put (h->paths, path);
+}
+
+static clib_cuckoo_path_t *CV (clib_cuckoo_path_begin) (CVT (clib_cuckoo) * h,
+							uword bucket,
+							uword next_offset)
+{
+  ASSERT (next_offset < CLIB_CUCKOO_KVP_PER_BUCKET);
+  clib_cuckoo_path_t *new_path = CV (clib_cuckoo_path_get) (h);
+  new_path->length = 1;
+  new_path->data = next_offset;
+  new_path->start = bucket;
+  new_path->bucket = bucket;
+#if CLIB_CUCKOO_DEBUG_PATH
+  CLIB_CUCKOO_DBG ("Create new path @%wu, length: %u data: %llu bucket: %wu "
+		   "next-offset: %wu",
+		   new_path - h->paths, new_path->length,
+		   (long long unsigned) new_path->data, new_path->bucket,
+		   next_offset);
+#endif
+  return new_path;
+}
+
+/**
+ * create a new path based on existing path extended by adding a bucket
+ * and offset
+ */
+static uword CV (clib_cuckoo_path_extend) (CVT (clib_cuckoo) * h,
+					   uword path_idx, uword bucket,
+					   unsigned offset)
+{
+  ASSERT (offset < CLIB_CUCKOO_KVP_PER_BUCKET);
+  clib_cuckoo_path_t *new_path = CV (clib_cuckoo_path_get) (h);
+  uword new_path_idx = new_path - h->paths;
+  clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
+  new_path->start = path->start;
+  new_path->length = path->length + 1;
+  new_path->data = (path->data << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) + offset;
+  new_path->bucket = bucket;
+#if CLIB_CUCKOO_DEBUG_PATH
+  CLIB_CUCKOO_DBG ("Extend path @%wu, new path @%wu, %U", path_idx,
+		   new_path_idx, CV (format_cuckoo_path), h, new_path_idx);
+#endif
+  return new_path_idx;
+}
+
+/** return the offset of the last element in the path */
+static uword CV (clib_cuckoo_path_peek_offset) (const clib_cuckoo_path_t *
+						path)
+{
+  ASSERT (path->length > 0);
+  uword mask = (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) - 1;
+  uword offset = path->data & mask;
+  return offset;
+}
+
+static
+CVT (clib_cuckoo_kv) *
+CV (clib_cuckoo_bucket_find_empty) (CVT (clib_cuckoo_bucket) * bucket)
+{
+  clib_cuckoo_bucket_aux_t aux = bucket->aux;
+  u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
+  if (use_count < CLIB_CUCKOO_KVP_PER_BUCKET)
+    {
+      return bucket->elts + use_count;
+    }
+  return NULL;
+}
+
+/**
+ * walk the cuckoo path two ways,
+ * first backwards, extracting offsets,
+ * then forward, extracting buckets
+ *
+ * buckets and offsets are arrays filled with elements extracted from path
+ * the arrays must be able to contain CLIB_CUCKOO_BFS_MAX_PATH_LENGTH elements
+ */
+static void
+clib_cuckoo_path_walk (CVT (clib_cuckoo) * h, uword path_idx,
+		       uword * buckets, uword * offsets)
+{
+  clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
+  ASSERT (path->length > 0);
+  u64 data = path->data;
+  uword mask = (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) - 1;
+  uword i;
+  for (i = path->length; i > 0; --i)
+    {
+      uword offset = data & mask;
+      offsets[i - 1] = offset;
+      data >>= CLIB_CUCKOO_LOG2_KVP_PER_BUCKET;
+    }
+  buckets[0] = path->start;
+  for (i = 1; i < path->length; ++i)
+    {
+      CVT (clib_cuckoo_bucket) * b =
+	CV (clib_cuckoo_bucket_at_index) (h, buckets[i - 1]);
+      buckets[i] =
+	clib_cuckoo_get_other_bucket (CV (clib_cuckoo_get_nbuckets) (h),
+				      buckets[i - 1],
+				      b->reduced_hashes[offsets[i - 1]]);
+    }
+}
+
+#if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH
+static u8 *CV (format_cuckoo_path) (u8 * s, va_list * args)
+{
+  CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
+  uword path_idx = va_arg (*args, uword);
+  clib_cuckoo_path_t *p = pool_elt_at_index (h->paths, path_idx);
+  uword buckets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
+  uword offsets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
+  clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
+  s = format (s, "length %u: ", p->length);
+  for (uword i = p->length - 1; i > 0; --i)
+    {
+      s = format (s, "%wu[%wu]->", buckets[i], offsets[i]);
+    }
+  if (p->length)
+    {
+      s = format (s, "%wu[%wu]", buckets[0], offsets[0]);
+    }
+  return s;
+}
+#endif
+
+/*
+ * perform breadth-first search in the cuckoo hash, finding the closest
+ * empty slot, i.e. one which requires minimum swaps to move it
+ * to one of the buckets provided
+ */
+static int CV (clib_cuckoo_find_empty_slot_bfs) (CVT (clib_cuckoo) * h,
+						 clib_cuckoo_lookup_info_t *
+						 lookup, uword * path_idx_out,
+						 uword * found_bucket,
+						 CVT (clib_cuckoo_kv) *
+						 *found_elt)
+{
+  uword *tail;
+  ASSERT (!vec_len (h->bfs_search_queue));
+  clib_cuckoo_path_t *tmp;
+  pool_flush (tmp, h->paths,);
+  int rv = CLIB_CUCKOO_ERROR_AGAIN;
+  int counter = 0;
+  /* start by creating paths starting in each of the buckets ... */
+  vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
+  int i;
+  for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
+    {
+      clib_cuckoo_path_t *path =
+	CV (clib_cuckoo_path_begin) (h, lookup->bucket1, i);
+      tail[i] = path - h->paths;
+    }
+  if (lookup->bucket1 != lookup->bucket2)
+    {
+      vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
+      for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
+	{
+	  clib_cuckoo_path_t *path =
+	    CV (clib_cuckoo_path_begin) (h, lookup->bucket2, i);
+	  tail[i] = path - h->paths;
+	}
+    }
+  while (1)
+    {
+      if (counter >= CLIB_CUCKOO_BFS_MAX_STEPS)
+	{
+#if CLIB_CUCKOO_DEBUG_COUNTERS
+	  ++h->steps_exceeded;
+#endif
+	  break;
+	}
+      if (counter >= vec_len (h->bfs_search_queue))
+	{
+#if CLIB_CUCKOO_DEBUG_COUNTERS
+	  ++h->bfs_queue_emptied;
+#endif
+	  break;
+	}
+      const uword path_idx = vec_elt (h->bfs_search_queue, counter);
+      const clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
+#if CLIB_CUCKOO_DEBUG_PATH
+      CLIB_CUCKOO_DBG ("Examine path @%wu: %U", path_idx,
+		       CV (format_cuckoo_path), h, path_idx);
+#endif
+      /* TODO prefetch ? */
+      /* search the alternative bucket for free space */
+      int offset = CV (clib_cuckoo_path_peek_offset) (path);
+      CVT (clib_cuckoo_bucket) * bucket =
+	CV (clib_cuckoo_bucket_at_index) (h, path->bucket);
+      uword other_bucket =
+	clib_cuckoo_get_other_bucket (CV (clib_cuckoo_get_nbuckets) (h),
+				      path->bucket,
+				      bucket->reduced_hashes[offset]);
+      CLIB_CUCKOO_DBG
+	("Path ends in bucket %wu, offset #%wu, other bucket is %wu",
+	 path->bucket, CV (clib_cuckoo_path_peek_offset) (path),
+	 other_bucket);
+      if (path->bucket != other_bucket)
+	{
+	  if ((*found_elt =
+	       CV (clib_cuckoo_bucket_find_empty) (CV
+						   (clib_cuckoo_bucket_at_index)
+						   (h, other_bucket))))
+	    {
+	      /* found empty element */
+	      *found_bucket = other_bucket;
+	      *path_idx_out = path_idx;
+	      rv = CLIB_CUCKOO_ERROR_SUCCESS;
+#if CLIB_CUCKOO_DEBUG_PATH
+	      CLIB_CUCKOO_DBG ("Bucket with empty slot:\n%U",
+			       CV (format_cuckoo_bucket),
+			       CV (clib_cuckoo_bucket_at_index) (h,
+								 other_bucket));
+#endif
+	      goto out;
+	    }
+	  /* extend the current path with possible next buckets and add to
+	   * queue */
+	  if (path->length < CLIB_CUCKOO_BFS_MAX_PATH_LENGTH &&
+	      vec_len (h->bfs_search_queue) < CLIB_CUCKOO_BFS_MAX_STEPS)
+	    {
+	      uword *tail;
+	      vec_add2 (h->bfs_search_queue, tail,
+			CLIB_CUCKOO_KVP_PER_BUCKET);
+	      for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
+		{
+		  uword new_path_idx =
+		    CV (clib_cuckoo_path_extend) (h, path_idx, other_bucket,
+						  i);
+		  tail[i] = new_path_idx;
+		}
+	    }
+	}
+      else
+	{
+	  CLIB_CUCKOO_DBG ("Discard path @%wu, loop detected", path_idx);
+	}
+      /* done with this path - put back to pool for later reuse */
+      CV (clib_cuckoo_path_put) (h, path_idx);
+      ++counter;
+    }
+out:
+  vec_reset_length (h->bfs_search_queue);
+  return rv;
+}
+
+static void CV (clib_cuckoo_swap_elts_in_bucket) (CVT (clib_cuckoo_bucket) *
+						  b, uword e1, uword e2)
+{
+  CVT (clib_cuckoo_kv) kv;
+  clib_memcpy (&kv, b->elts + e1, sizeof (kv));
+  clib_memcpy (b->elts + e1, b->elts + e2, sizeof (kv));
+  clib_memcpy (b->elts + e2, &kv, sizeof (kv));
+  u8 reduced_hash = b->reduced_hashes[e1];
+  b->reduced_hashes[e1] = b->reduced_hashes[e2];
+  b->reduced_hashes[e2] = reduced_hash;
+}
+
+static void CV (clib_cuckoo_bucket_tidy) (CVT (clib_cuckoo_bucket) * b)
+{
+  int i = 0;
+  int j = CLIB_CUCKOO_KVP_PER_BUCKET - 1;
+  while (i != j)
+    {
+      int min_free = i;
+      int max_used = j;
+      while (!CV (clib_cuckoo_kv_is_free) (&b->elts[min_free]))
+	{
+	  ++min_free;
+	}
+      while (CV (clib_cuckoo_kv_is_free) (&b->elts[max_used]))
+	{
+	  --max_used;
+	}
+      if (min_free < max_used)
+	{
+	  CV (clib_cuckoo_swap_elts_in_bucket) (b, min_free, max_used);
+	  i = min_free + 1;
+	  j = max_used - 1;
+	}
+      else
+	{
+	  break;
+	}
+    }
+}
+
+static void CV (clib_cuckoo_free_locked_elt) (CVT (clib_cuckoo_kv) * elt)
+{
+  /*
+   * FIXME - improve performance by getting rid of this memset - make all
+   * functions in this file not rely on clib_cuckoo_kv_is_free but instead
+   * take use_count into account */
+  memset (elt, 0xff, sizeof (*elt));
+}
+
+static void CV (clib_cuckoo_free_elt_in_bucket) (CVT (clib_cuckoo_bucket) * b,
+						 CVT (clib_cuckoo_kv) * elt)
+{
+  clib_cuckoo_bucket_aux_t aux =
+    CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
+  int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
+  int offset = elt - b->elts;
+  ASSERT (offset < use_count);
+  CV (clib_cuckoo_free_locked_elt) (elt);
+  if (offset != use_count - 1)
+    {
+      CV (clib_cuckoo_bucket_tidy) (b);
+    }
+  aux = clib_cuckoo_bucket_aux_set_use_count (aux, use_count - 1);
+  CV (clib_cuckoo_bucket_unlock) (b, aux);
+}
+
+static void CV (clib_cuckoo_set_locked_elt) (CVT (clib_cuckoo_bucket) * b,
+					     CVT (clib_cuckoo_kv) * elt,
+					     CVT (clib_cuckoo_kv) * kvp,
+					     u8 reduced_hash)
+{
+  int offset = CV (clib_cuckoo_elt_in_bucket_to_offset) (b, elt);
+  clib_memcpy (elt, kvp, sizeof (*elt));
+  b->reduced_hashes[offset] = reduced_hash;
+  CLIB_CUCKOO_DBG ("Set bucket %p, offset %d, %U", b, offset,
+		   CV (format_cuckoo_elt), elt, b->reduced_hashes[offset]);
+}
+
+static void CV (clib_cuckoo_set_elt) (CVT (clib_cuckoo_bucket) * b,
+				      CVT (clib_cuckoo_kv) * elt,
+				      CVT (clib_cuckoo_kv) * kvp,
+				      u8 reduced_hash)
+{
+  clib_cuckoo_bucket_aux_t aux =
+    CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
+  CV (clib_cuckoo_set_locked_elt) (b, elt, kvp, reduced_hash);
+  CV (clib_cuckoo_bucket_unlock) (b, aux);
+}
+
+static int CV (clib_cuckoo_add_slow) (CVT (clib_cuckoo) * h,
+				      CVT (clib_cuckoo_kv) * kvp,
+				      clib_cuckoo_lookup_info_t * lookup,
+				      u8 reduced_hash)
+{
+  uword path_idx;
+  uword empty_bucket_idx;
+  CVT (clib_cuckoo_kv) * empty_elt;
+  int rv = CV (clib_cuckoo_find_empty_slot_bfs) (h, lookup, &path_idx,
+						 &empty_bucket_idx,
+						 &empty_elt);
+  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
+    {
+      uword buckets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
+      uword offsets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
+      clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
+      /*
+       * walk back the path, moving the free element forward to one of our
+       * buckets ...
+       */
+      clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
+      CVT (clib_cuckoo_bucket) * empty_bucket =
+	CV (clib_cuckoo_bucket_at_index) (h, empty_bucket_idx);
+      int i;
+      for (i = path->length - 1; i >= 0; --i)
+	{
+	  /* copy the key-value in path to the bucket with empty element */
+	  CVT (clib_cuckoo_bucket) * b =
+	    CV (clib_cuckoo_bucket_at_index) (h, buckets[i]);
+	  CVT (clib_cuckoo_kv) * elt = b->elts + offsets[i];
+	  clib_cuckoo_bucket_aux_t empty_aux =
+	    CV (clib_cuckoo_bucket_version_bump_and_lock) (empty_bucket);
+	  CV (clib_cuckoo_set_locked_elt)
+	    (empty_bucket, empty_elt, elt, b->reduced_hashes[elt - b->elts]);
+	  if (i == path->length - 1)
+	    {
+	      /* we only need to increase the use count for the bucket with
+	       * free element - all other buckets' use counts won't change */
+	      empty_aux = clib_cuckoo_bucket_aux_set_use_count (empty_aux,
+								clib_cuckoo_bucket_aux_get_use_count
+								(empty_aux) +
+								1);
+	    }
+	  CV (clib_cuckoo_bucket_unlock) (empty_bucket, empty_aux);
+	  /*
+	   * the element now exists in both places - in the previously empty
+	   * element and in its original bucket - we can now safely overwrite
+	   * the element in the original bucket with previous element in path
+	   * without loosing data (and we don't need to modify the use count)
+	   */
+	  empty_bucket = b;
+	  empty_elt = elt;
+	}
+      /* now we have a place to put the kvp in ... */
+      CV (clib_cuckoo_set_elt) (empty_bucket, empty_elt, kvp, reduced_hash);
+      CLIB_CUCKOO_DBG ("Slow insert success, bucket: %p\n%U", empty_bucket,
+		       CV (format_cuckoo_bucket), empty_bucket);
+#if CLIB_CUCKOO_DEBUG_COUNTERS
+      ++h->slow_adds;
+#endif
+    }
+  return rv;
+}
+
+static int CV (clib_cuckoo_add_fast) (CVT (clib_cuckoo) * h,
+				      clib_cuckoo_lookup_info_t * lookup,
+				      CVT (clib_cuckoo_kv) * kvp,
+				      u8 reduced_hash)
+{
+  CVT (clib_cuckoo_kv) * elt;
+  CVT (clib_cuckoo_bucket) * bucket1 =
+    CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket1);
+  if ((elt = CV (clib_cuckoo_bucket_find_empty) (bucket1)))
+    {
+      clib_cuckoo_bucket_aux_t aux =
+	CV (clib_cuckoo_bucket_version_bump_and_lock) (bucket1);
+      CV (clib_cuckoo_set_locked_elt) (bucket1, elt, kvp, reduced_hash);
+      aux =
+	clib_cuckoo_bucket_aux_set_use_count (aux,
+					      clib_cuckoo_bucket_aux_get_use_count
+					      (aux) + 1);
+      CV (clib_cuckoo_bucket_unlock) (bucket1, aux);
+#if CLIB_CUCKOO_DEBUG_COUNTERS
+      ++h->fast_adds;
+#endif
+      return CLIB_CUCKOO_ERROR_SUCCESS;
+    }
+  CVT (clib_cuckoo_bucket) * bucket2 =
+    CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket2);
+  if ((elt =
+       CV (clib_cuckoo_bucket_find_empty) (CV (clib_cuckoo_bucket_at_index)
+					   (h, lookup->bucket2))))
+    {
+      clib_cuckoo_bucket_aux_t aux =
+	CV (clib_cuckoo_bucket_version_bump_and_lock) (bucket2);
+      CV (clib_cuckoo_set_locked_elt) (bucket2, elt, kvp, reduced_hash);
+      aux =
+	clib_cuckoo_bucket_aux_set_use_count (aux,
+					      clib_cuckoo_bucket_aux_get_use_count
+					      (aux) + 1);
+      CV (clib_cuckoo_bucket_unlock) (bucket2, aux);
+#if CLIB_CUCKOO_DEBUG_COUNTERS
+      ++h->fast_adds;
+#endif
+      return CLIB_CUCKOO_ERROR_SUCCESS;
+    }
+  return CLIB_CUCKOO_ERROR_AGAIN;
+}
+
+/**
+ * perform garbage collection
+ *
+ * this function assumes there is no other thread touching the cuckoo hash,
+ * not even a reader, it's meant to be called from main thread
+ * in a stop-the-world situation
+ */
+void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h)
+{
+  CLIB_MEMORY_BARRIER ();
+  CVT (clib_cuckoo_bucket) * *b;
+  /* *INDENT-OFF* */
+  vec_foreach (b, h->to_be_freed)
+  {
+    if (*b == h->buckets)
+      {
+        continue;
+      }
+#if CLIB_CUCKOO_DEBUG_GC
+    fformat (stdout, "gc: free %p\n", *b);
+#endif
+    vec_free (*b);
+  }
+  /* *INDENT-ON* */
+  vec_free (h->to_be_freed);
+  CLIB_MEMORY_BARRIER ();
+}
+
+/**
+ * expand and rehash a cuckoo hash
+ *
+ * 1. double the size of the hash table
+ * 2. move items to new locations derived from the new size
+ */
+static void CV (clib_cuckoo_rehash) (CVT (clib_cuckoo) * h)
+{
+  CVT (clib_cuckoo_bucket) * old = h->buckets;
+  uword old_nbuckets = vec_len (old);
+  uword new_nbuckets = 2 * old_nbuckets;
+  CVT (clib_cuckoo_bucket) * new =
+    vec_dup_aligned (old, CLIB_CACHE_LINE_BYTES);
+  /* allocate space */
+  vec_validate_aligned (new, new_nbuckets - 1, CLIB_CACHE_LINE_BYTES);
+  ASSERT (new_nbuckets == vec_len (new));
+  /* store old pointer in to-be-freed list */
+  vec_add1 (h->to_be_freed, old);
+  /* mark new elements as free */
+  CVT (clib_cuckoo_bucket) * bucket;
+  for (bucket = new + old_nbuckets; bucket < vec_end (new); ++bucket)
+    {
+      memset (bucket->elts, 0xff, sizeof (bucket->elts));
+    }
+  /*
+   * this for loop manipulates the new (unseen) memory, so no locks
+   * are required here
+   */
+  uword old_bucket_idx;
+  for (old_bucket_idx = 0; old_bucket_idx < old_nbuckets; ++old_bucket_idx)
+    {
+      /* items in old bucket might be moved to new bucket */
+      uword new_bucket_idx = old_bucket_idx + old_nbuckets;
+      CVT (clib_cuckoo_bucket) * old_bucket = new + old_bucket_idx;
+      CVT (clib_cuckoo_bucket) * new_bucket = new + new_bucket_idx;
+      int i = 0;
+      int moved = 0;
+      clib_cuckoo_bucket_aux_t aux = old_bucket->aux;
+      for (i = 0; i < clib_cuckoo_bucket_aux_get_use_count (aux); ++i)
+	{
+	  CVT (clib_cuckoo_kv) * elt = old_bucket->elts + i;
+	  u64 hash = CV (clib_cuckoo_hash) (elt);
+	  clib_cuckoo_lookup_info_t old_lookup =
+	    CV (clib_cuckoo_calc_lookup) (old, hash);
+	  clib_cuckoo_lookup_info_t new_lookup =
+	    CV (clib_cuckoo_calc_lookup) (new, hash);
+	  if ((old_bucket_idx == old_lookup.bucket1 &&
+	       new_bucket_idx == new_lookup.bucket1) ||
+	      (old_bucket_idx == old_lookup.bucket2 &&
+	       new_bucket_idx == new_lookup.bucket2))
+	    {
+	      /* move the item to new bucket */
+	      CVT (clib_cuckoo_kv) * empty_elt = new_bucket->elts + moved;
+	      ASSERT (empty_elt);
+	      CV (clib_cuckoo_set_locked_elt)
+		(new_bucket, empty_elt, elt, old_bucket->reduced_hashes[i]);
+	      CV (clib_cuckoo_free_locked_elt) (elt);
+	      ++moved;
+	    }
+	}
+      if (moved)
+	{
+	  CV (clib_cuckoo_bucket_tidy) (old_bucket);
+	  aux =
+	    clib_cuckoo_bucket_aux_set_use_count (aux,
+						  clib_cuckoo_bucket_aux_get_use_count
+						  (aux) - moved);
+	  old_bucket->aux = aux;
+	  aux = new_bucket->aux;
+	  aux =
+	    clib_cuckoo_bucket_aux_set_use_count (aux,
+						  clib_cuckoo_bucket_aux_get_use_count
+						  (aux) + moved);
+	  new_bucket->aux = aux;
+	}
+    }
+  h->buckets = new;
+#if CLIB_CUCKOO_DEBUG_COUNTERS
+  ++h->rehashes;
+#endif
+  h->garbage_callback (h, h->garbage_ctx);
+}
+
+static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h,
+						    uword bucket,
+						    CVT (clib_cuckoo_kv) *
+						    kvp,
+						    CVT (clib_cuckoo_kv) *
+						    *found)
+{
+  CVT (clib_cuckoo_bucket) * b = CV (clib_cuckoo_bucket_at_index) (h, bucket);
+  int i;
+  /* *INDENT-OFF* */
+  clib_cuckoo_bucket_foreach_idx_unrolled (i, {
+    CVT (clib_cuckoo_kv) *elt = &b->elts[i];
+    if (CV (clib_cuckoo_key_compare) (elt->key, kvp->key))
+      {
+        *found = elt;
+        return CLIB_CUCKOO_ERROR_SUCCESS;
+      }
+  });
+  /* *INDENT-ON* */
+  return CLIB_CUCKOO_ERROR_NOT_FOUND;
+}
+
+int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
+			      CVT (clib_cuckoo_kv) * kvp, int is_add)
+{
+  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);
+restart:
+  lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
+  CVT (clib_cuckoo_bucket) * b =
+    CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1);
+  CVT (clib_cuckoo_kv) * found;
+  int rv =
+    CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket1, kvp, &found);
+  if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
+    {
+      ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
+      b = CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2);
+      rv = CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket2, kvp,
+						    &found);
+    }
+  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
+    {
+      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);
+	}
+      else
+	{
+	  CV (clib_cuckoo_free_elt_in_bucket) (b, found);
+	}
+      rv = CLIB_CUCKOO_ERROR_SUCCESS;
+      CLIB_CUCKOO_DEEP_SELF_CHECK (h);
+      goto unlock;
+    }
+  if (!is_add)
+    {
+      CLIB_CUCKOO_DBG ("%U not present in table", CV (format_cuckoo_kvp),
+		       kvp);
+      rv = CLIB_CUCKOO_ERROR_NOT_FOUND;
+      goto unlock;
+    }
+  /* from this point on, it's add code only */
+  ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
+  /* fast path: try to search for unoccupied slot in one of the buckets */
+  rv = CV (clib_cuckoo_add_fast) (h, &lookup, kvp, reduced_hash);
+  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));
+      /* slow path */
+      rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
+      CLIB_CUCKOO_DEEP_SELF_CHECK (h);
+      if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
+	{
+	  CLIB_CUCKOO_DBG ("Slow insert failed, rehash required:\n%U",
+			   CV (format_cuckoo), h, 1);
+	  /* ultra slow path */
+	  CV (clib_cuckoo_rehash) (h);
+	  CLIB_CUCKOO_DEEP_SELF_CHECK (h);
+	  CLIB_CUCKOO_DBG ("Restarting add after rehash...");
+	  goto restart;
+	}
+    }
+unlock:
+  clib_spinlock_unlock (&h->writer_lock);
+  return rv;
+}
+
+u8 *CV (format_cuckoo) (u8 * s, va_list * args)
+{
+  CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
+  int verbose = va_arg (*args, int);
+
+  s = format (s, "Hash table %s\n", h->name ? h->name : "(unnamed)");
+
+  uword free = 0;
+  uword used = 0;
+  uword use_count_total = 0;
+  CVT (clib_cuckoo_bucket) * b;
+  /* *INDENT-OFF* */
+  clib_cuckoo_foreach_bucket (b, h, {
+    if (verbose)
+      {
+        s = format (s, "%U", CV (format_cuckoo_bucket), b);
+      }
+    int i;
+    clib_cuckoo_bucket_foreach_idx (i)
+    {
+      CVT (clib_cuckoo_kv) *elt = &b->elts[i];
+      if (CV (clib_cuckoo_kv_is_free) (elt))
+        {
+          ++free;
+        }
+      else
+        {
+          ++used;
+        }
+    }
+    clib_cuckoo_bucket_aux_t aux = b->aux;
+    use_count_total += clib_cuckoo_bucket_aux_get_use_count (aux);
+  });
+  /* *INDENT-ON* */
+  s = format (s, "Used slots: %wu\n", used);
+  s = format (s, "Use count total: %wu\n", use_count_total);
+  s = format (s, "Free slots: %wu\n", free);
+  s =
+    format (s, "Load factor: %.2f\n", (float) (used) / (float) (free + used));
+#if CLIB_CUCKOO_DEBUG_COUNTERS
+  s = format (s, "BFS attempts limited by max steps: %lld\n",
+	      h->steps_exceeded);
+  s = format (s, "BFS cutoffs due to empty queue: %lld\n",
+	      h->bfs_queue_emptied);
+  s = format (s, "Fast adds: %lld\n", h->fast_adds);
+  s = format (s, "Slow adds: %lld\n", h->slow_adds);
+  s = format (s, "Rehashes: %lld\n", h->rehashes);
+#endif
+  return s;
+}
+
+float CV (clib_cuckoo_calculate_load_factor) (CVT (clib_cuckoo) * h)
+{
+  uword nonfree = 0;
+  uword all = 0;
+  CVT (clib_cuckoo_bucket) * bucket;
+  /* *INDENT-OFF* */
+  clib_cuckoo_foreach_bucket (bucket, h, {
+    int i;
+    clib_cuckoo_bucket_foreach_idx (i)
+    {
+      CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
+      ++all;
+      if (!CV (clib_cuckoo_kv_is_free) (elt))
+        {
+          ++nonfree;
+        }
+    }
+  });
+  /* *INDENT-ON* */
+  return (float) nonfree / (float) all;
+}
+
+/** @endcond */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/cuckoo_template.h b/src/vppinfra/cuckoo_template.h
new file mode 100644
index 00000000000..b53a089771d
--- /dev/null
+++ b/src/vppinfra/cuckoo_template.h
@@ -0,0 +1,458 @@
+/*
+  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.
+*/
+
+/*
+ * cuckoo hash implementation based on paper
+ * 'Algorithmic Improvements for Fast Concurrent Cuckoo Hashing'
+ * by Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman
+ * and their libcuckoo implementation (https://github.com/efficient/libcuckoo)
+ */
+
+/*
+ * Note: to instantiate the template multiple times in a single file,
+ * #undef __included_cuckoo_template_h__...
+ */
+#ifndef __included_cuckoo_template_h__
+#define __included_cuckoo_template_h__
+
+#include <vppinfra/heap.h>
+#include <vppinfra/format.h>
+#include <vppinfra/pool.h>
+#include <vppinfra/lock.h>
+#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
+#endif
+
+#ifndef CLIB_CUCKOO_BFS_MAX_STEPS
+#error CLIB_CUCKOO_BFS_MAX_STEPS not defined
+#endif
+
+#ifndef CLIB_CUCKOO_KVP_PER_BUCKET
+#error CLIB_CUCKOO_KVP_PER_BUCKET not defined
+#endif
+
+#ifndef CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
+#error CLIB_CUCKOO_LOG2_KVP_PER_BUCKET not defined
+#endif
+
+#ifndef CLIB_CUCKOO_BFS_MAX_PATH_LENGTH
+#error CLIB_CUCKOO_BFS_MAX_PATH_LENGTH not defined
+#endif
+
+STATIC_ASSERT (CLIB_CUCKOO_KVP_PER_BUCKET ==
+	       (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET),
+	       "CLIB_CUCKOO_KVP_PER_BUCKET != (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET");
+
+#define _cv(a, b) a##b
+#define __cv(a, b) _cv (a, b)
+#define CV(a) __cv (a, CLIB_CUCKOO_TYPE)
+
+#define _cvt(a, b) a##b##_t
+#define __cvt(a, b) _cvt (a, b)
+#define CVT(a) __cvt (a, CLIB_CUCKOO_TYPE)
+
+typedef u64 clib_cuckoo_bucket_aux_t;
+
+#define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
+
+always_inline u64
+clib_cuckoo_bucket_aux_get_version (clib_cuckoo_bucket_aux_t aux)
+{
+  return aux >> (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH);
+}
+
+always_inline int
+clib_cuckoo_bucket_aux_get_use_count (clib_cuckoo_bucket_aux_t aux)
+{
+  u64 use_count_mask = (1 << CLIB_CUCKOO_USE_COUNT_BIT_WIDTH) - 1;
+  return (aux >> 1) & use_count_mask;
+}
+
+always_inline int
+clib_cuckoo_bucket_aux_get_writer_flag (clib_cuckoo_bucket_aux_t aux)
+{
+  return aux & 1;
+}
+
+always_inline clib_cuckoo_bucket_aux_t
+clib_cuckoo_bucket_aux_pack (u64 version, int use_count, int writer_flag)
+{
+  return (version << (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH)) +
+    (use_count << 1) + writer_flag;
+}
+
+always_inline clib_cuckoo_bucket_aux_t
+clib_cuckoo_bucket_aux_set_version (clib_cuckoo_bucket_aux_t aux, u64 version)
+{
+  int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
+  int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
+  return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
+}
+
+always_inline clib_cuckoo_bucket_aux_t
+clib_cuckoo_bucket_aux_set_use_count (clib_cuckoo_bucket_aux_t aux,
+				      int use_count)
+{
+  u64 version = clib_cuckoo_bucket_aux_get_version (aux);
+  int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
+  return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
+}
+
+always_inline clib_cuckoo_bucket_aux_t
+clib_cuckoo_bucket_aux_set_writer_flag (clib_cuckoo_bucket_aux_t aux,
+					int writer_flag)
+{
+  u64 version = clib_cuckoo_bucket_aux_get_version (aux);
+  int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
+  return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
+}
+
+#define PATH_BITS_REQ \
+  (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
+
+#if PATH_BITS_REQ <= 8
+typedef u8 path_data_t;
+#elif PATH_BITS_REQ <= 16
+typedef u16 path_data_t;
+#elif PATH_BITS_REQ <= 32
+typedef u32 path_data_t;
+#elif PATH_BITS_REQ <= 64
+typedef u64 path_data_t;
+#else
+#error no suitable datatype for path storage...
+#endif
+
+typedef struct
+{
+  /** bucket where this path begins */
+  u64 start;
+  /** bucket at end of path */
+  u64 bucket;
+  /** length of the path */
+  u8 length;
+  /** holds compressed offsets in buckets along path */
+  path_data_t data;
+} clib_cuckoo_path_t;
+
+typedef struct
+{
+  /** reduced hashes corresponding to elements */
+  u8 reduced_hashes[CLIB_CUCKOO_KVP_PER_BUCKET];
+
+  /** auxiliary data - version, writer flag and used count */
+  volatile clib_cuckoo_bucket_aux_t aux;
+
+  /** cuckoo elements in this bucket */
+    CVT (clib_cuckoo_kv) elts[CLIB_CUCKOO_KVP_PER_BUCKET];
+} CVT (clib_cuckoo_bucket);
+
+#define clib_cuckoo_bucket_foreach_idx(var) \
+  for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++)
+
+#if CLIB_CUCKOO_OPTIMIZE_UNROLL
+#if CLIB_CUCKOO_KVP_PER_BUCKET == 2
+#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
+  do                                                       \
+    {                                                      \
+      var = 0;                                             \
+      body;                                                \
+      var = 1;                                             \
+      body;                                                \
+    }                                                      \
+  while (0);
+#elif CLIB_CUCKOO_KVP_PER_BUCKET == 4
+#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
+  do                                                       \
+    {                                                      \
+      var = 0;                                             \
+      body;                                                \
+      var = 1;                                             \
+      body;                                                \
+      var = 2;                                             \
+      body;                                                \
+      var = 3;                                             \
+      body;                                                \
+    }                                                      \
+  while (0);
+#elif CLIB_CUCKOO_KVP_PER_BUCKET == 8
+#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
+  do                                                       \
+    {                                                      \
+      var = 0;                                             \
+      body;                                                \
+      var = 1;                                             \
+      body;                                                \
+      var = 2;                                             \
+      body;                                                \
+      var = 3;                                             \
+      body;                                                \
+      var = 4;                                             \
+      body;                                                \
+      var = 5;                                             \
+      body;                                                \
+      var = 6;                                             \
+      body;                                                \
+      var = 7;                                             \
+      body;                                                \
+    }                                                      \
+  while (0);
+#else
+#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
+  clib_cuckoo_bucket_foreach_idx (var)                     \
+  {                                                        \
+    body;                                                  \
+  }
+#endif
+#else /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
+#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
+  clib_cuckoo_bucket_foreach_idx (var)                     \
+  {                                                        \
+    body;                                                  \
+  }
+#endif /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
+
+#define clib_cuckoo_bucket_foreach_elt_index(var, bucket) \
+  for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
+
+#define clib_cuckoo_foreach_bucket(var, h, body)        \
+  do                                                    \
+    {                                                   \
+      CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \
+      vec_foreach (var, __buckets)                      \
+      {                                                 \
+        body;                                           \
+      }                                                 \
+    }                                                   \
+  while (0)
+
+typedef struct CV (clib_cuckoo)
+{
+  /** vector of elements containing key-value pairs and auxiliary data */
+  CVT (clib_cuckoo_bucket) * volatile buckets;
+
+  /** garbage to be freed once its safe to do so .. */
+  CVT (clib_cuckoo_bucket) * *to_be_freed;
+
+  /** hash table name */
+  const char *name;
+
+  /** pool of cuckoo paths (reused when doing bfd search) */
+  clib_cuckoo_path_t *paths;
+
+  /**
+   * vector used as queue when doing cuckoo path searches - holds offsets
+   * in paths pool
+   */
+  uword *bfs_search_queue;
+
+  /**
+   * writer lock - whether this lock is taken or not has zero effect on
+   * readers
+   */
+  clib_spinlock_t writer_lock;
+
+  /** caller context passed to callback with garbage notification */
+  void *garbage_ctx;
+
+  /**
+   * garbage notify function - called when some garbage needs to be collected
+   * in main thread while other threads are stopped
+   */
+  void (*garbage_callback) (struct CV (clib_cuckoo) * h, void *garbage_ctx);
+
+#if CLIB_CUCKOO_DEBUG_COUNTERS
+  u64 steps_exceeded;
+  u64 bfs_queue_emptied;
+  u64 fast_adds;
+  u64 slow_adds;
+  u64 rehashes;
+#endif
+
+} CVT (clib_cuckoo);
+
+void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
+			    u64 nbuckets,
+			    void (*garbage_callback) (CVT (clib_cuckoo) *,
+						      void *),
+			    void *garbage_ctx);
+
+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);
+int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
+			     CVT (clib_cuckoo_kv) * search_v,
+			     CVT (clib_cuckoo_kv) * return_v);
+
+void CV (clib_cuckoo_foreach_key_value_pair) (CVT (clib_cuckoo) * h,
+					      void *callback, void *arg);
+
+float CV (clib_cuckoo_calc_load) (CVT (clib_cuckoo) * h);
+
+format_function_t CV (format_cuckoo);
+format_function_t CV (format_cuckoo_kvp);
+
+always_inline u8
+clib_cuckoo_reduce_hash (u64 hash)
+{
+  u32 v32 = ((u32) hash) ^ ((u32) (hash >> 32));
+  u16 v16 = ((u16) v32) ^ ((u16) (v32 >> 16));
+  u8 v8 = ((u8) v16) ^ ((u8) (v16 >> 8));
+  return v8;
+}
+
+always_inline u64
+clib_cuckoo_get_other_bucket (u64 nbuckets, u64 bucket, u8 reduced_hash)
+{
+  u64 mask = (nbuckets - 1);
+  return (bucket ^ ((reduced_hash + 1) * 0xc6a4a7935bd1e995)) & mask;
+}
+
+always_inline clib_cuckoo_lookup_info_t
+CV (clib_cuckoo_calc_lookup) (CVT (clib_cuckoo_bucket) * buckets, u64 hash)
+{
+  clib_cuckoo_lookup_info_t lookup;
+  u64 nbuckets = vec_len (buckets);
+  u64 mask = (nbuckets - 1);
+  lookup.bucket1 = hash & mask;
+#if CLIB_CUCKOO_OPTIMIZE_PREFETCH
+  CLIB_PREFETCH (vec_elt_at_index (buckets, lookup.bucket1),
+		 sizeof (*buckets), LOAD);
+#endif
+  u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
+  lookup.bucket2 =
+    clib_cuckoo_get_other_bucket (nbuckets, lookup.bucket1, reduced_hash);
+#if CLIB_CUCKOO_OPTIMIZE_PREFETCH
+  CLIB_PREFETCH (vec_elt_at_index (buckets, lookup.bucket2),
+		 sizeof (*buckets), LOAD);
+#endif
+  lookup.reduced_hash = reduced_hash;
+  ASSERT (lookup.bucket1 < nbuckets);
+  ASSERT (lookup.bucket2 < nbuckets);
+  return lookup;
+}
+
+/**
+ * search for key within bucket
+ */
+always_inline int CV (clib_cuckoo_bucket_search) (CVT (clib_cuckoo_bucket) *
+						  b,
+						  CVT (clib_cuckoo_kv) * kvp,
+						  u8 reduced_hash)
+{
+  clib_cuckoo_bucket_aux_t bucket_aux;
+  u8 writer_flag;
+  do
+    {
+      bucket_aux = b->aux;
+      writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (bucket_aux);
+    }
+  while (PREDICT_FALSE (writer_flag));	/* loop while writer flag is set */
+
+  int i;
+#if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
+  const int use_count = clib_cuckoo_bucket_aux_get_use_count (bucket_aux);
+#endif
+  /* *INDENT-OFF* */
+  clib_cuckoo_bucket_foreach_idx_unrolled (i, {
+#if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
+    if (i > use_count)
+      {
+        break;
+      }
+#endif
+    if (
+#if CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH
+        reduced_hash == b->reduced_hashes[i] &&
+#endif
+        0 == memcmp (&kvp->key, &b->elts[i].key, sizeof (kvp->key)))
+      {
+        kvp->value = b->elts[i].value;
+        clib_cuckoo_bucket_aux_t bucket_aux2 = b->aux;
+        if (PREDICT_TRUE (clib_cuckoo_bucket_aux_get_version (bucket_aux) ==
+                          clib_cuckoo_bucket_aux_get_version (bucket_aux2)))
+          {
+            /* yay, fresh data */
+            return CLIB_CUCKOO_ERROR_SUCCESS;
+          }
+        else
+          {
+            /* oops, modification detected */
+            return CLIB_CUCKOO_ERROR_AGAIN;
+          }
+      }
+  });
+  /* *INDENT-ON* */
+  return CLIB_CUCKOO_ERROR_NOT_FOUND;
+}
+
+always_inline int CV (clib_cuckoo_search_inline) (CVT (clib_cuckoo) * h,
+						  CVT (clib_cuckoo_kv) * kvp)
+{
+  clib_cuckoo_lookup_info_t lookup;
+  int rv;
+
+  u64 hash = CV (clib_cuckoo_hash) (kvp);
+  CVT (clib_cuckoo_bucket) * buckets;
+again:
+  buckets = h->buckets;
+  lookup = CV (clib_cuckoo_calc_lookup) (buckets, hash);
+  do
+    {
+      rv =
+	CV (clib_cuckoo_bucket_search) (vec_elt_at_index
+					(buckets, lookup.bucket1), kvp,
+					lookup.reduced_hash);
+    }
+  while (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv));
+  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
+    {
+      return CLIB_CUCKOO_ERROR_SUCCESS;
+    }
+
+  rv =
+    CV (clib_cuckoo_bucket_search) (vec_elt_at_index
+				    (buckets, lookup.bucket2), kvp,
+				    lookup.reduced_hash);
+  if (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv))
+    {
+      /*
+       * change to 2nd bucket could bump the item to 1st bucket and the bucket
+       * indexes might not even be valid anymore - restart the search
+       */
+      goto again;
+    }
+  return rv;
+}
+
+#endif /* __included_cuckoo_template_h__ */
+
+/** @endcond */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/test_cuckoo_bihash.c b/src/vppinfra/test_cuckoo_bihash.c
new file mode 100644
index 00000000000..eb17eed2ba1
--- /dev/null
+++ b/src/vppinfra/test_cuckoo_bihash.c
@@ -0,0 +1,451 @@
+/*
+ * 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.
+ */
+
+__thread int thread_id = 0;
+
+#include <vppinfra/time.h>
+#include <vppinfra/cache.h>
+#include <vppinfra/error.h>
+#include <vppinfra/heap.h>
+#include <vppinfra/format.h>
+#include <vppinfra/pool.h>
+#include <vppinfra/error.h>
+#include <vppinfra/hash.h>
+#include <vppinfra/cache.h>
+
+#define os_get_cpu_number() (thread_id)
+
+#include <vppinfra/cuckoo_8_8.h>
+#include <vppinfra/cuckoo_template.h>
+#include <vppinfra/cuckoo_template.c>
+
+#include <vppinfra/bihash_8_8.h>
+#include <vppinfra/bihash_template.h>
+#include <vppinfra/bihash_template.c>
+
+#include <pthread.h>
+
+#define MAX_THREADS 255
+
+typedef struct
+{
+  void *tm;
+  int thread_idx;
+  u64 nlookups;
+} thread_data_t;
+
+typedef struct
+{
+  u64 deadline;
+  u64 seed;
+  u32 nbuckets;
+  u32 nitems;
+  u32 runtime;
+  int verbose;
+  int non_random_keys;
+  int nthreads;
+  int search_iter;
+  uword *key_hash;
+  u64 *keys;
+    CVT (clib_cuckoo) ch;
+    BVT (clib_bihash) bh;
+  clib_time_t clib_time;
+  u64 *key_add_del_sequence;
+  u8 *key_op_sequence;
+  u64 *key_search_sequence[MAX_THREADS];
+  unformat_input_t *input;
+  u64 nadds;
+  u64 ndels;
+  pthread_t bwriter_thread;
+  pthread_t breader_threads[MAX_THREADS];
+  pthread_t cwriter_thread;
+  pthread_t creader_threads[MAX_THREADS];
+  thread_data_t wthread_data;
+  thread_data_t rthread_data[MAX_THREADS];
+} test_main_t;
+
+test_main_t test_main;
+
+uword
+vl (void *v)
+{
+  return vec_len (v);
+}
+
+#define w_thread(x, guts)                                               \
+  void *x##writer_thread (void *v)                                      \
+  {                                                                     \
+    test_main_t *tm = v;                                                \
+    uword counter = 0;                                                  \
+    u64 nadds = 0;                                                      \
+    u64 ndels = 0;                                                      \
+    u64 deadline = tm->deadline;                                        \
+    do                                                                  \
+      {                                                                 \
+        for (counter = 0; counter < vec_len (tm->key_add_del_sequence); \
+             ++counter)                                                 \
+          {                                                             \
+            u64 idx = tm->key_add_del_sequence[counter];                \
+            u8 op = tm->key_op_sequence[counter];                       \
+            if (op)                                                     \
+              {                                                         \
+                ++nadds;                                                \
+              }                                                         \
+            else                                                        \
+              {                                                         \
+                ++ndels;                                                \
+              }                                                         \
+            guts;                                                       \
+            if (clib_cpu_time_now () > deadline)                        \
+              {                                                         \
+                break;                                                  \
+              }                                                         \
+          }                                                             \
+      }                                                                 \
+    while (clib_cpu_time_now () < deadline);                            \
+    tm->nadds = nadds;                                                  \
+    tm->ndels = ndels;                                                  \
+    return NULL;                                                        \
+  }
+
+/* *INDENT-OFF* */
+w_thread (b, {
+  BVT (clib_bihash_kv) kv;
+  kv.key = tm->keys[idx];
+  kv.value = *hash_get (tm->key_hash, kv.key);
+  BV (clib_bihash_add_del) (&tm->bh, &kv, op);
+});
+/* *INDENT-ON* */
+
+/* *INDENT-OFF* */
+w_thread (c, {
+  CVT (clib_cuckoo_kv) kv;
+  kv.key = tm->keys[idx];
+  kv.value = *hash_get (tm->key_hash, kv.key);
+  CV (clib_cuckoo_add_del) (&tm->ch, &kv, op);
+});
+/* *INDENT-ON* */
+
+#define r_thread(x, guts)                                      \
+  void *x##reader_thread (void *v)                             \
+  {                                                            \
+    thread_data_t *data = v;                                   \
+    thread_id = data->thread_idx;                              \
+    test_main_t *tm = data->tm;                                \
+    uword thread_idx = data->thread_idx;                       \
+    u64 *idx;                                                  \
+    uword nlookups = 0;                                        \
+    u64 deadline = tm->deadline;                               \
+    do                                                         \
+      {                                                        \
+        vec_foreach (idx, tm->key_search_sequence[thread_idx]) \
+        {                                                      \
+          guts;                                                \
+          ++nlookups;                                          \
+          if (clib_cpu_time_now () > deadline)                 \
+            {                                                  \
+              break;                                           \
+            }                                                  \
+        }                                                      \
+      }                                                        \
+    while (clib_cpu_time_now () < deadline);                   \
+    data->nlookups = nlookups;                                 \
+    return NULL;                                               \
+  }
+
+/* *INDENT-OFF* */
+r_thread (c, {
+  CVT (clib_cuckoo_kv) kv;
+  kv.key = tm->keys[*idx];
+  kv.value = *hash_get (tm->key_hash, kv.key);
+  CV (clib_cuckoo_search) (&tm->ch, &kv, &kv);
+});
+/* *INDENT-ON* */
+
+/* *INDENT-OFF* */
+r_thread (b, {
+  BVT (clib_bihash_kv) kv;
+  kv.key = tm->keys[*idx];
+  kv.value = *hash_get (tm->key_hash, kv.key);
+  BV (clib_bihash_search) (&tm->bh, &kv, &kv);
+});
+/* *INDENT-ON* */
+
+#define run_threads(x)                                                        \
+  do                                                                          \
+    {                                                                         \
+                                                                              \
+      before = clib_time_now (&tm->clib_time);                                \
+      tm->deadline = clib_cpu_time_now () +                                   \
+                     tm->runtime * tm->clib_time.clocks_per_second;           \
+      fformat (stdout, #x "-> Start threads..., runtime is %llu second(s)\n", \
+               (long long unsigned)tm->runtime);                              \
+                                                                              \
+      /*                                                                      \
+      fformat (stdout, #x "-> Writer thread only...\n");                      \
+      if (0 !=                                                                \
+          pthread_create (&tm->x##writer_thread, NULL, x##writer_thread, tm)) \
+        {                                                                     \
+          perror ("pthread_create()");                                        \
+          abort ();                                                           \
+        }                                                                     \
+                                                                              \
+      if (0 != pthread_join (tm->x##writer_thread, NULL))                     \
+        {                                                                     \
+          perror ("pthread_join()");                                          \
+          abort ();                                                           \
+        }                                                                     \
+                                                                              \
+      delta = clib_time_now (&tm->clib_time) - before;                        \
+      fformat (stdout, #x "-> %wu adds, %wu dels in %.6f seconds\n",          \
+               tm->nadds, tm->ndels, delta);                                  \
+      tm->nadds = 0;                                                          \
+      tm->ndels = 0;                                                          \
+      */                                                                      \
+                                                                              \
+      fformat (stdout, #x "-> Writer + %d readers\n", tm->nthreads);          \
+      before = clib_time_now (&tm->clib_time);                                \
+      tm->deadline = clib_cpu_time_now () +                                   \
+                     tm->runtime * tm->clib_time.clocks_per_second;           \
+      if (0 !=                                                                \
+          pthread_create (&tm->x##writer_thread, NULL, x##writer_thread, tm)) \
+        {                                                                     \
+          perror ("pthread_create()");                                        \
+          abort ();                                                           \
+        }                                                                     \
+                                                                              \
+      for (i = 0; i < tm->nthreads; i++)                                      \
+        {                                                                     \
+          tm->rthread_data[i].nlookups = 0;                                   \
+          if (0 != pthread_create (&tm->x##reader_threads[i], NULL,           \
+                                   x##reader_thread, &tm->rthread_data[i]))   \
+            {                                                                 \
+              perror ("pthread_create()");                                    \
+              abort ();                                                       \
+            }                                                                 \
+        }                                                                     \
+                                                                              \
+      if (0 != pthread_join (tm->x##writer_thread, NULL))                     \
+        {                                                                     \
+          perror ("pthread_join()");                                          \
+          abort ();                                                           \
+        }                                                                     \
+                                                                              \
+      for (i = 0; i < tm->nthreads; i++)                                      \
+        {                                                                     \
+          if (0 != pthread_join (tm->x##reader_threads[i], NULL))             \
+            {                                                                 \
+              perror ("pthread_join()");                                      \
+              abort ();                                                       \
+            }                                                                 \
+        }                                                                     \
+                                                                              \
+      delta = clib_time_now (&tm->clib_time) - before;                        \
+                                                                              \
+      total_searches = 0;                                                     \
+      for (i = 0; i < tm->nthreads; ++i)                                      \
+        {                                                                     \
+          u64 nlookups = tm->rthread_data[i].nlookups;                        \
+          fformat (stdout, #x "-> Thread #%d: %u searches\n", i, nlookups);   \
+          total_searches += nlookups;                                         \
+        }                                                                     \
+                                                                              \
+      if (delta > 0)                                                          \
+        {                                                                     \
+          ops = (tm->nadds + tm->ndels) / (f64)delta;                         \
+          fformat (stdout, #x "-> %.f add/dels per second\n", ops);           \
+          sps = ((f64)total_searches) / delta;                                \
+          fformat (stdout, #x "-> %.f searches per second\n", sps);           \
+        }                                                                     \
+                                                                              \
+      fformat (stdout,                                                        \
+               #x "-> %wu adds, %wu dels, %lld searches in %.6f seconds\n",   \
+               tm->nadds, tm->ndels, total_searches, delta);                  \
+    }                                                                         \
+  while (0);
+
+static void
+cb (CVT (clib_cuckoo) * h, void *ctx)
+{
+  fformat (stdout, "Garbage callback called...\n");
+}
+
+static clib_error_t *
+test_cuckoo_bihash (test_main_t * tm)
+{
+  int i;
+  uword *p;
+  uword total_searches;
+  f64 before, delta;
+  f64 ops = 0, sps = 0;
+  f64 bops = 0, bsps = 0;
+  f64 cops = 0, csps = 0;
+  CVT (clib_cuckoo) * ch;
+  BVT (clib_bihash) * bh;
+
+  ch = &tm->ch;
+  bh = &tm->bh;
+
+  CV (clib_cuckoo_init) (ch, "test", 1, cb, NULL);
+  BV (clib_bihash_init) (bh, (char *) "test", tm->nbuckets, 256 << 20);
+
+  fformat (stdout, "Pick %lld unique %s keys...\n", tm->nitems,
+	   tm->non_random_keys ? "non-random" : "random");
+
+  for (i = 0; i < tm->nitems; i++)
+    {
+      u64 rndkey;
+
+      if (tm->non_random_keys == 0)
+	{
+
+	again:
+	  rndkey = random_u64 (&tm->seed);
+
+	  p = hash_get (tm->key_hash, rndkey);
+	  if (p)
+	    goto again;
+	}
+      else
+	rndkey = (u64) (i + 1) << 16;
+
+      hash_set (tm->key_hash, rndkey, i + 1);
+      vec_add1 (tm->keys, rndkey);
+
+      int j;
+      for (j = 0; j < tm->nthreads; ++j)
+	{
+	  u64 *x = tm->key_search_sequence[j];
+	  vec_add1 (x, random_u64 (&tm->seed) % tm->nitems);
+	  tm->key_search_sequence[j] = x;
+	}
+      vec_add1 (tm->key_add_del_sequence,
+		random_u64 (&tm->seed) % tm->nitems);
+      vec_add1 (tm->key_op_sequence, (rndkey % 10 < 8) ? 1 : 0);
+    }
+
+  int thread_counter = 0;
+  tm->wthread_data.tm = tm;
+  tm->wthread_data.thread_idx = thread_counter;
+  for (i = 0; i < tm->nthreads; ++i)
+    {
+      tm->rthread_data[i].tm = tm;
+      tm->rthread_data[i].thread_idx = thread_counter;
+      tm->rthread_data[i].nlookups = 0;
+      ++thread_counter;
+    }
+
+  int iter;
+  for (iter = 0; iter < tm->search_iter; ++iter)
+    {
+      fformat (stdout, "Bihash test #%d\n", iter);
+      run_threads (b);
+      bops = ops;
+      bsps = sps;
+      fformat (stdout, "%U", BV (format_bihash), bh, 0);
+      fformat (stdout, "Cuckoo test #%d\n", iter);
+      run_threads (c);
+      cops = ops;
+      csps = sps;
+      fformat (stdout, "%U", CV (format_cuckoo), ch, 0);
+      fformat (stdout,
+	       "Bihash add/del speed is %.2f%% of cuckoo add/del speed\n",
+	       bops / cops * 100);
+      fformat (stdout,
+	       "Bihash search speed is %.2f%% of cuckoo search speed\n",
+	       bsps / csps * 100);
+    }
+  return 0;
+}
+
+clib_error_t *
+test_cuckoo_bihash_main (test_main_t * tm)
+{
+  unformat_input_t *i = tm->input;
+  clib_error_t *error;
+
+  while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
+    {
+      if (unformat (i, "seed %u", &tm->seed))
+	;
+      else if (unformat (i, "nbuckets %d", &tm->nbuckets))
+	;
+      else if (unformat (i, "non-random-keys"))
+	tm->non_random_keys = 1;
+      else if (unformat (i, "nitems %d", &tm->nitems))
+	;
+      else if (unformat (i, "search_iter %d", &tm->search_iter))
+	;
+      else if (unformat (i, "verbose %d", &tm->verbose))
+	;
+      else if (unformat (i, "runtime %d", &tm->runtime))
+	;
+      else if (unformat (i, "nthreads %d", &tm->nthreads))
+	;
+      else if (unformat (i, "verbose"))
+	tm->verbose = 1;
+      else
+	return clib_error_return (0, "unknown input '%U'",
+				  format_unformat_error, i);
+    }
+
+  error = test_cuckoo_bihash (tm);
+
+  return error;
+}
+
+#ifdef CLIB_UNIX
+int
+main (int argc, char *argv[])
+{
+  unformat_input_t i;
+  clib_error_t *error;
+  test_main_t *tm = &test_main;
+  memset (&test_main, 0, sizeof (test_main));
+
+  clib_mem_init (0, 3ULL << 30);
+
+  tm->input = &i;
+  tm->seed = 0xdeaddabe;
+
+  tm->nbuckets = 2;
+  tm->nitems = 5;
+  tm->verbose = 1;
+  tm->nthreads = 1;
+  clib_time_init (&tm->clib_time);
+  tm->runtime = 1;
+  tm->search_iter = 1;
+  tm->key_hash = hash_create (0, sizeof (uword));
+
+  unformat_init_command_line (&i, argv);
+  error = test_cuckoo_bihash_main (tm);
+  unformat_free (&i);
+
+  if (error)
+    {
+      clib_error_report (error);
+      return 1;
+    }
+  return 0;
+}
+#endif /* CLIB_UNIX */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/test_cuckoo_template.c b/src/vppinfra/test_cuckoo_template.c
new file mode 100644
index 00000000000..52af38589c8
--- /dev/null
+++ b/src/vppinfra/test_cuckoo_template.c
@@ -0,0 +1,316 @@
+/*
+ * 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.
+ */
+
+#include <vppinfra/time.h>
+#include <vppinfra/cache.h>
+#include <vppinfra/error.h>
+#include <vppinfra/heap.h>
+#include <vppinfra/format.h>
+#include <vppinfra/pool.h>
+#include <vppinfra/error.h>
+#include <vppinfra/hash.h>
+#include <vppinfra/cache.h>
+
+#include <vppinfra/time.h>
+#include <vppinfra/cache.h>
+#include <vppinfra/error.h>
+
+#include <vppinfra/cuckoo_8_8.h>
+#include <vppinfra/cuckoo_template.h>
+#include <vppinfra/cuckoo_template.c>
+
+typedef struct
+{
+  u64 seed;
+  u32 nbuckets;
+  u32 nitems;
+  u32 search_iter;
+  int careful_delete_tests;
+  int verbose;
+  int non_random_keys;
+  uword *key_hash;
+  u64 *keys;
+    CVT (clib_cuckoo) hash;
+  clib_time_t clib_time;
+
+  unformat_input_t *input;
+
+} test_main_t;
+
+test_main_t test_main;
+
+uword
+vl (void *v)
+{
+  return vec_len (v);
+}
+
+void
+do_search (test_main_t * tm, CVT (clib_cuckoo) * h)
+{
+  int i, j;
+  CVT (clib_cuckoo_kv) kv;
+  for (j = 0; j < tm->search_iter; j++)
+    {
+      for (i = 0; i < tm->nitems; i++)
+	{
+	  kv.key = tm->keys[i];
+	  if (CV (clib_cuckoo_search) (h, &kv, &kv) < 0)
+	    if (CV (clib_cuckoo_search) (h, &kv, &kv) < 0)
+	      clib_warning ("[%d] search for key %llu failed unexpectedly\n",
+			    i, tm->keys[i]);
+	  if (kv.value != (u64) (i + 1))
+	    clib_warning
+	      ("[%d] search for key %llu returned %llu, not %llu\n", i,
+	       tm->keys[i], kv.value, (u64) (i + 1));
+	}
+    }
+}
+
+static void
+cb (CVT (clib_cuckoo) * h, void *ctx)
+{
+  fformat (stdout, "Garbage callback called...");
+  if (clib_cpu_time_now () % 3)
+    {
+      fformat (stdout, "collecting garbage...\n");
+      CV (clib_cuckoo_garbage_collect) (h);
+    }
+  else
+    {
+      fformat (stdout, "ignoring for now...\n");
+    }
+}
+
+static clib_error_t *
+test_cuckoo (test_main_t * tm)
+{
+  int i;
+  uword *p;
+  uword total_searches;
+  f64 before, delta;
+  CVT (clib_cuckoo) * h;
+  CVT (clib_cuckoo_kv) kv;
+
+  h = &tm->hash;
+
+  CV (clib_cuckoo_init) (h, "test", tm->nbuckets, cb, NULL);
+
+  fformat (stdout, "Pick %lld unique %s keys...\n", tm->nitems,
+	   tm->non_random_keys ? "non-random" : "random");
+
+  for (i = 0; i < tm->nitems; i++)
+    {
+      u64 rndkey;
+
+      if (tm->non_random_keys == 0)
+	{
+
+	again:
+	  rndkey = random_u64 (&tm->seed);
+
+	  p = hash_get (tm->key_hash, rndkey);
+	  if (p)
+	    goto again;
+	}
+      else
+	rndkey = (u64) (i + 1) << 16;
+
+      hash_set (tm->key_hash, rndkey, i + 1);
+      vec_add1 (tm->keys, rndkey);
+    }
+
+  fformat (stdout, "Add items...\n");
+  for (i = 0; i < tm->nitems; i++)
+    {
+      kv.key = tm->keys[i];
+      kv.value = i + 1;
+
+      CV (clib_cuckoo_add_del) (h, &kv, 1 /* is_add */ );
+
+      if (tm->verbose > 1)
+	{
+	  fformat (stdout, "--------------------\n");
+	  fformat (stdout, "After adding key %llu value %lld...\n",
+		   tm->keys[i], (u64) (i + 1));
+	  fformat (stdout, "%U", CV (format_cuckoo), h,
+		   2 /* very verbose */ );
+	}
+
+      CVT (clib_cuckoo_kv) kv2;
+      int rv = CV (clib_cuckoo_search) (h, &kv, &kv2);
+      ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
+    }
+
+  fformat (stdout, "%U", CV (format_cuckoo), h, 0 /* very verbose */ );
+
+  fformat (stdout, "Search for items %d times...\n", tm->search_iter);
+
+  before = clib_time_now (&tm->clib_time);
+
+  do_search (tm, h);
+
+  delta = clib_time_now (&tm->clib_time) - before;
+  total_searches = (uword) tm->search_iter * (uword) tm->nitems;
+
+  if (delta > 0)
+    fformat (stdout, "%.f searches per second\n",
+	     ((f64) total_searches) / delta);
+
+  fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
+
+#if 0
+  int j;
+  fformat (stdout, "Standard E-hash search for items %d times...\n",
+	   tm->search_iter);
+
+  before = clib_time_now (&tm->clib_time);
+
+  for (j = 0; j < tm->search_iter; j++)
+    {
+      for (i = 0; i < tm->nitems; i++)
+	{
+	  p = hash_get (tm->key_hash, tm->keys[i]);
+	  if (p == 0 || p[0] != (uword) (i + 1))
+	    clib_warning ("ugh, couldn't find %lld\n", tm->keys[i]);
+	}
+    }
+
+  delta = clib_time_now (&tm->clib_time) - before;
+  total_searches = (uword) tm->search_iter * (uword) tm->nitems;
+
+  fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
+
+  if (delta > 0)
+    fformat (stdout, "%.f searches per second\n",
+	     ((f64) total_searches) / delta);
+
+#endif
+  fformat (stdout, "Delete items...\n");
+
+  for (i = 0; i < tm->nitems; i++)
+    {
+      int j;
+      int rv;
+
+      kv.key = tm->keys[i];
+      kv.value = (u64) (i + 1);
+      rv = CV (clib_cuckoo_add_del) (h, &kv, 0 /* is_add */ );
+
+      if (rv < 0)
+	clib_warning ("delete key %lld not ok but should be", tm->keys[i]);
+
+      if (tm->careful_delete_tests)
+	{
+	  for (j = 0; j < tm->nitems; j++)
+	    {
+	      kv.key = tm->keys[j];
+	      rv = CV (clib_cuckoo_search) (h, &kv, &kv);
+	      if (j <= i && rv >= 0)
+		{
+		  clib_warning
+		    ("i %d j %d search ok but should not be, value %lld", i,
+		     j, kv.value);
+		}
+	      if (j > i && rv < 0)
+		{
+		  clib_warning ("i %d j %d search not ok but should be", i,
+				j);
+		}
+	    }
+	}
+    }
+
+  fformat (stdout, "After deletions, should be empty...\n");
+
+  fformat (stdout, "%U", CV (format_cuckoo), h, 0 /* very verbose */ );
+  return 0;
+}
+
+clib_error_t *
+test_cuckoo_main (test_main_t * tm)
+{
+  unformat_input_t *i = tm->input;
+  clib_error_t *error;
+
+  while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
+    {
+      if (unformat (i, "seed %u", &tm->seed))
+	;
+      else if (unformat (i, "nbuckets %d", &tm->nbuckets))
+	;
+      else if (unformat (i, "non-random-keys"))
+	tm->non_random_keys = 1;
+      else if (unformat (i, "nitems %d", &tm->nitems))
+	;
+      else if (unformat (i, "careful %d", &tm->careful_delete_tests))
+	;
+      else if (unformat (i, "verbose %d", &tm->verbose))
+	;
+      else if (unformat (i, "search %d", &tm->search_iter))
+	;
+      else if (unformat (i, "verbose"))
+	tm->verbose = 1;
+      else
+	return clib_error_return (0, "unknown input '%U'",
+				  format_unformat_error, i);
+    }
+
+  error = test_cuckoo (tm);
+
+  return error;
+}
+
+#ifdef CLIB_UNIX
+int
+main (int argc, char *argv[])
+{
+  unformat_input_t i;
+  clib_error_t *error;
+  test_main_t *tm = &test_main;
+
+  clib_mem_init (0, 3ULL << 30);
+
+  tm->input = &i;
+  tm->seed = 0xdeaddabe;
+
+  tm->nbuckets = 2;
+  tm->nitems = 100000;
+  tm->verbose = 1;
+  tm->search_iter = 10000;
+  tm->careful_delete_tests = 0;
+  tm->key_hash = hash_create (0, sizeof (uword));
+  clib_time_init (&tm->clib_time);
+
+  unformat_init_command_line (&i, argv);
+  error = test_cuckoo_main (tm);
+  unformat_free (&i);
+
+  if (error)
+    {
+      clib_error_report (error);
+      return 1;
+    }
+  return 0;
+}
+#endif /* CLIB_UNIX */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */