2 Copyright (c) 2017 Cisco and/or its affiliates.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 * cuckoo hash implementation based on paper
19 * 'Algorithmic Improvements for Fast Concurrent Cuckoo Hashing'
20 * by Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman
21 * and their libcuckoo implementation (https://github.com/efficient/libcuckoo)
25 * Note: to instantiate the template multiple times in a single file,
26 * #undef __included_cuckoo_template_h__...
28 #ifndef __included_cuckoo_template_h__
29 #define __included_cuckoo_template_h__
31 #include <vppinfra/heap.h>
32 #include <vppinfra/format.h>
33 #include <vppinfra/pool.h>
34 #include <vppinfra/lock.h>
35 #include <vppinfra/error.h>
36 #include <vppinfra/hash.h>
37 #include <vppinfra/cache.h>
38 #include <vppinfra/cuckoo_8_8.h>
40 #ifndef CLIB_CUCKOO_TYPE
41 #error CLIB_CUCKOO_TYPE not defined
44 #ifndef CLIB_CUCKOO_BFS_MAX_STEPS
45 #error CLIB_CUCKOO_BFS_MAX_STEPS not defined
48 #ifndef CLIB_CUCKOO_KVP_PER_BUCKET
49 #error CLIB_CUCKOO_KVP_PER_BUCKET not defined
52 #ifndef CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
53 #error CLIB_CUCKOO_LOG2_KVP_PER_BUCKET not defined
56 #ifndef CLIB_CUCKOO_BFS_MAX_PATH_LENGTH
57 #error CLIB_CUCKOO_BFS_MAX_PATH_LENGTH not defined
60 STATIC_ASSERT (CLIB_CUCKOO_KVP_PER_BUCKET ==
61 (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET),
62 "CLIB_CUCKOO_KVP_PER_BUCKET != (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET");
64 #define _cv(a, b) a##b
65 #define __cv(a, b) _cv (a, b)
66 #define CV(a) __cv (a, CLIB_CUCKOO_TYPE)
68 #define _cvt(a, b) a##b##_t
69 #define __cvt(a, b) _cvt (a, b)
70 #define CVT(a) __cvt (a, CLIB_CUCKOO_TYPE)
72 typedef u64 clib_cuckoo_bucket_aux_t;
74 #define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
77 clib_cuckoo_bucket_aux_get_version (clib_cuckoo_bucket_aux_t aux)
79 return aux >> (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH);
83 clib_cuckoo_bucket_aux_get_use_count (clib_cuckoo_bucket_aux_t aux)
85 u64 use_count_mask = (1 << CLIB_CUCKOO_USE_COUNT_BIT_WIDTH) - 1;
86 return (aux >> 1) & use_count_mask;
90 clib_cuckoo_bucket_aux_get_writer_flag (clib_cuckoo_bucket_aux_t aux)
95 always_inline clib_cuckoo_bucket_aux_t
96 clib_cuckoo_bucket_aux_pack (u64 version, int use_count, int writer_flag)
98 return (version << (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH)) +
99 (use_count << 1) + writer_flag;
102 always_inline clib_cuckoo_bucket_aux_t
103 clib_cuckoo_bucket_aux_set_version (clib_cuckoo_bucket_aux_t aux, u64 version)
105 int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
106 int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
107 return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
110 always_inline clib_cuckoo_bucket_aux_t
111 clib_cuckoo_bucket_aux_set_use_count (clib_cuckoo_bucket_aux_t aux,
114 u64 version = clib_cuckoo_bucket_aux_get_version (aux);
115 int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
116 return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
119 always_inline clib_cuckoo_bucket_aux_t
120 clib_cuckoo_bucket_aux_set_writer_flag (clib_cuckoo_bucket_aux_t aux,
123 u64 version = clib_cuckoo_bucket_aux_get_version (aux);
124 int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
125 return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
128 #define PATH_BITS_REQ \
129 (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
131 #if PATH_BITS_REQ <= 8
132 typedef u8 path_data_t;
133 #elif PATH_BITS_REQ <= 16
134 typedef u16 path_data_t;
135 #elif PATH_BITS_REQ <= 32
136 typedef u32 path_data_t;
137 #elif PATH_BITS_REQ <= 64
138 typedef u64 path_data_t;
140 #error no suitable datatype for path storage...
145 /** bucket where this path begins */
147 /** bucket at end of path */
149 /** length of the path */
151 /** holds compressed offsets in buckets along path */
153 } clib_cuckoo_path_t;
157 CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
159 /** reduced hashes corresponding to elements */
160 u8 reduced_hashes[CLIB_CUCKOO_KVP_PER_BUCKET];
162 /** auxiliary data - version, writer flag and used count */
163 volatile clib_cuckoo_bucket_aux_t aux;
165 /** cuckoo elements in this bucket */
166 CVT (clib_cuckoo_kv) elts[CLIB_CUCKOO_KVP_PER_BUCKET];
167 } CVT (clib_cuckoo_bucket);
169 #define clib_cuckoo_bucket_foreach_idx(var) \
170 for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++)
172 #if CLIB_CUCKOO_OPTIMIZE_UNROLL
173 #if CLIB_CUCKOO_KVP_PER_BUCKET == 2
174 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
183 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 4
184 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
197 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 8
198 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
220 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
221 clib_cuckoo_bucket_foreach_idx (var) \
226 #else /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
227 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
228 clib_cuckoo_bucket_foreach_idx (var) \
232 #endif /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
234 #define clib_cuckoo_bucket_foreach_elt_index(var, bucket) \
235 for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
237 #define clib_cuckoo_foreach_bucket(var, h, body) \
240 CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \
241 vec_foreach (var, __buckets) \
248 typedef struct CV (clib_cuckoo)
250 /** vector of elements containing key-value pairs and auxiliary data */
251 CVT (clib_cuckoo_bucket) * volatile buckets;
253 /** garbage to be freed once its safe to do so .. */
254 CVT (clib_cuckoo_bucket) * *to_be_freed;
256 /** hash table name */
259 /** pool of cuckoo paths (reused when doing bfd search) */
260 clib_cuckoo_path_t *paths;
263 * vector used as queue when doing cuckoo path searches - holds offsets
266 uword *bfs_search_queue;
269 * writer lock - whether this lock is taken or not has zero effect on
272 clib_spinlock_t writer_lock;
274 /** caller context passed to callback with garbage notification */
278 * garbage notify function - called when some garbage needs to be collected
279 * in main thread while other threads are stopped
281 void (*garbage_callback) (struct CV (clib_cuckoo) * h, void *garbage_ctx);
283 #if CLIB_CUCKOO_DEBUG_COUNTERS
285 u64 bfs_queue_emptied;
293 void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
295 void (*garbage_callback) (CVT (clib_cuckoo) *,
299 void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h);
301 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h);
303 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
304 CVT (clib_cuckoo_kv) * add_v, int is_add);
305 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
306 CVT (clib_cuckoo_kv) * search_v,
307 CVT (clib_cuckoo_kv) * return_v);
309 void CV (clib_cuckoo_foreach_key_value_pair) (CVT (clib_cuckoo) * h,
310 void *callback, void *arg);
312 float CV (clib_cuckoo_calc_load) (CVT (clib_cuckoo) * h);
314 format_function_t CV (format_cuckoo);
315 format_function_t CV (format_cuckoo_kvp);
318 clib_cuckoo_reduce_hash (u64 hash)
320 u32 v32 = ((u32) hash) ^ ((u32) (hash >> 32));
321 u16 v16 = ((u16) v32) ^ ((u16) (v32 >> 16));
322 u8 v8 = ((u8) v16) ^ ((u8) (v16 >> 8));
327 clib_cuckoo_get_other_bucket (u64 nbuckets, u64 bucket, u8 reduced_hash)
329 u64 mask = (nbuckets - 1);
330 return (bucket ^ ((reduced_hash + 1) * 0xc6a4a7935bd1e995)) & mask;
333 always_inline clib_cuckoo_lookup_info_t
334 CV (clib_cuckoo_calc_lookup) (CVT (clib_cuckoo_bucket) * buckets, u64 hash)
336 clib_cuckoo_lookup_info_t lookup;
337 u64 nbuckets = vec_len (buckets);
338 u64 mask = (nbuckets - 1);
339 lookup.bucket1 = hash & mask;
340 #if CLIB_CUCKOO_OPTIMIZE_PREFETCH
341 CLIB_PREFETCH (vec_elt_at_index (buckets, lookup.bucket1),
342 sizeof (*buckets), LOAD);
344 u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
346 clib_cuckoo_get_other_bucket (nbuckets, lookup.bucket1, reduced_hash);
347 #if CLIB_CUCKOO_OPTIMIZE_PREFETCH
348 CLIB_PREFETCH (vec_elt_at_index (buckets, lookup.bucket2),
349 sizeof (*buckets), LOAD);
351 lookup.reduced_hash = reduced_hash;
352 ASSERT (lookup.bucket1 < nbuckets);
353 ASSERT (lookup.bucket2 < nbuckets);
358 * search for key within bucket
360 always_inline int CV (clib_cuckoo_bucket_search) (CVT (clib_cuckoo_bucket) *
362 CVT (clib_cuckoo_kv) * kvp,
365 clib_cuckoo_bucket_aux_t bucket_aux;
370 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (bucket_aux);
372 while (PREDICT_FALSE (writer_flag)); /* loop while writer flag is set */
375 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
376 const int use_count = clib_cuckoo_bucket_aux_get_use_count (bucket_aux);
379 clib_cuckoo_bucket_foreach_idx_unrolled (i, {
380 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
387 #if CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH
388 reduced_hash == b->reduced_hashes[i] &&
390 0 == memcmp (&kvp->key, &b->elts[i].key, sizeof (kvp->key)))
392 kvp->value = b->elts[i].value;
393 clib_cuckoo_bucket_aux_t bucket_aux2 = b->aux;
394 if (PREDICT_TRUE (clib_cuckoo_bucket_aux_get_version (bucket_aux) ==
395 clib_cuckoo_bucket_aux_get_version (bucket_aux2)))
397 /* yay, fresh data */
398 return CLIB_CUCKOO_ERROR_SUCCESS;
402 /* oops, modification detected */
403 return CLIB_CUCKOO_ERROR_AGAIN;
408 return CLIB_CUCKOO_ERROR_NOT_FOUND;
411 always_inline int CV (clib_cuckoo_search_inline) (CVT (clib_cuckoo) * h,
412 CVT (clib_cuckoo_kv) * kvp)
414 clib_cuckoo_lookup_info_t lookup;
417 u64 hash = CV (clib_cuckoo_hash) (kvp);
418 CVT (clib_cuckoo_bucket) * buckets;
420 buckets = h->buckets;
421 lookup = CV (clib_cuckoo_calc_lookup) (buckets, hash);
425 CV (clib_cuckoo_bucket_search) (vec_elt_at_index
426 (buckets, lookup.bucket1), kvp,
427 lookup.reduced_hash);
429 while (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv));
430 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
432 return CLIB_CUCKOO_ERROR_SUCCESS;
436 CV (clib_cuckoo_bucket_search) (vec_elt_at_index
437 (buckets, lookup.bucket2), kvp,
438 lookup.reduced_hash);
439 if (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv))
442 * change to 2nd bucket could bump the item to 1st bucket and the bucket
443 * indexes might not even be valid anymore - restart the search
450 #endif /* __included_cuckoo_template_h__ */
455 * fd.io coding-style-patch-verification: ON
458 * eval: (c-set-style "gnu")