summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/cuckoo_template.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/vppinfra/cuckoo_template.h')
-rw-r--r--src/vppinfra/cuckoo_template.h460
1 files changed, 0 insertions, 460 deletions
diff --git a/src/vppinfra/cuckoo_template.h b/src/vppinfra/cuckoo_template.h
deleted file mode 100644
index 364c2919d96..00000000000
--- a/src/vppinfra/cuckoo_template.h
+++ /dev/null
@@ -1,460 +0,0 @@
-/*
- 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>
-
-#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
-{
- CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
-
- /** 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,
- uword 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 dont_overwrite);
-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 (CV (clib_cuckoo_key_compare) (kvp->key, b->elts[i].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_with_hash) (CVT (clib_cuckoo) * h, u64 hash,
- CVT (clib_cuckoo_kv) * kvp)
-{
- CVT (clib_cuckoo_bucket) * buckets = h->buckets;
- uword bucket1, bucket2;
- u8 reduced_hash;
- u64 nbuckets = vec_len (buckets);
- u64 mask = nbuckets - 1;
- int rv;
-
- bucket1 = hash & mask;
- reduced_hash = clib_cuckoo_reduce_hash (hash);
-
-again:
- rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket1),
- kvp, reduced_hash);
-
- if (rv == CLIB_CUCKOO_ERROR_SUCCESS)
- return CLIB_CUCKOO_ERROR_SUCCESS;
-
- if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
- goto again;
-
- bucket2 = clib_cuckoo_get_other_bucket (nbuckets, bucket1, reduced_hash);
- rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket2),
- kvp, reduced_hash);
-
- /* change to 2nd bucket could bump the item to 1st bucket and the bucket
- * indexes might not even be valid anymore - restart the search */
- if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
- goto again;
-
- return rv;
-}
-
-always_inline int CV (clib_cuckoo_search_inline) (CVT (clib_cuckoo) * h,
- CVT (clib_cuckoo_kv) * kvp)
-{
- u64 hash = CV (clib_cuckoo_hash) (kvp);
- return CV (clib_cuckoo_search_inline_with_hash) (h, hash, kvp);
-}
-
-#endif /* __included_cuckoo_template_h__ */
-
-/** @endcond */
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */