lib_LTLIBRARIES += libvppinfra.la
-TESTS =
+TESTS = test_cuckoo_template \
+ test_bihash_template \
+ test_cuckoo_bihash
if ENABLE_TESTS
TESTS += test_bihash_template \
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
# 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
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
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
--- /dev/null
+/*
+ * 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:
+ */
--- /dev/null
+/*
+ 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:
+ */
--- /dev/null
+/*
+ * 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:
+ */
--- /dev/null
+/*
+ * 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:
+ */
--- /dev/null
+/*
+ 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:
+ */
--- /dev/null
+/*
+ * 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:
+ */
--- /dev/null
+/*
+ * 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:
+ */
Code Review / vpp.git / commitdiff