diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/vppinfra.am | 12 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_8_8.h | 122 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_common.h | 60 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_debug.h | 83 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_template.c | 982 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_template.h | 458 | ||||
| -rw-r--r-- | src/vppinfra/test_cuckoo_bihash.c | 451 | ||||
| -rw-r--r-- | src/vppinfra/test_cuckoo_template.c | 316 |
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: + */ |