FD.io VPP  v20.09-64-g4f7b92f0a
Vector Packet Processing
cuckoo_template.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2017 Cisco and/or its affiliates.
3 
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:
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15 */
16 
17 /*
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)
22  */
23 
24 /*
25  * Note: to instantiate the template multiple times in a single file,
26  * #undef __included_cuckoo_template_h__...
27  */
28 #ifndef __included_cuckoo_template_h__
29 #define __included_cuckoo_template_h__
30 
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 
39 #ifndef CLIB_CUCKOO_TYPE
40 #error CLIB_CUCKOO_TYPE not defined
41 #endif
42 
43 #ifndef CLIB_CUCKOO_BFS_MAX_STEPS
44 #error CLIB_CUCKOO_BFS_MAX_STEPS not defined
45 #endif
46 
47 #ifndef CLIB_CUCKOO_KVP_PER_BUCKET
48 #error CLIB_CUCKOO_KVP_PER_BUCKET not defined
49 #endif
50 
51 #ifndef CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
52 #error CLIB_CUCKOO_LOG2_KVP_PER_BUCKET not defined
53 #endif
54 
55 #ifndef CLIB_CUCKOO_BFS_MAX_PATH_LENGTH
56 #error CLIB_CUCKOO_BFS_MAX_PATH_LENGTH not defined
57 #endif
58 
61  "CLIB_CUCKOO_KVP_PER_BUCKET != (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET");
62 
63 #define _cv(a, b) a##b
64 #define __cv(a, b) _cv (a, b)
65 #define CV(a) __cv (a, CLIB_CUCKOO_TYPE)
66 
67 #define _cvt(a, b) a##b##_t
68 #define __cvt(a, b) _cvt (a, b)
69 #define CVT(a) __cvt (a, CLIB_CUCKOO_TYPE)
70 
72 
73 #define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
74 
76 clib_cuckoo_bucket_aux_get_version (clib_cuckoo_bucket_aux_t aux)
77 {
78  return aux >> (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH);
79 }
80 
81 always_inline int
82 clib_cuckoo_bucket_aux_get_use_count (clib_cuckoo_bucket_aux_t aux)
83 {
84  u64 use_count_mask = (1 << CLIB_CUCKOO_USE_COUNT_BIT_WIDTH) - 1;
85  return (aux >> 1) & use_count_mask;
86 }
87 
88 always_inline int
89 clib_cuckoo_bucket_aux_get_writer_flag (clib_cuckoo_bucket_aux_t aux)
90 {
91  return aux & 1;
92 }
93 
94 always_inline clib_cuckoo_bucket_aux_t
95 clib_cuckoo_bucket_aux_pack (u64 version, int use_count, int writer_flag)
96 {
97  return (version << (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH)) +
98  (use_count << 1) + writer_flag;
99 }
100 
101 always_inline clib_cuckoo_bucket_aux_t
102 clib_cuckoo_bucket_aux_set_version (clib_cuckoo_bucket_aux_t aux, u64 version)
103 {
104  int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
105  int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
106  return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
107 }
108 
109 always_inline clib_cuckoo_bucket_aux_t
110 clib_cuckoo_bucket_aux_set_use_count (clib_cuckoo_bucket_aux_t aux,
111  int use_count)
112 {
114  int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
115  return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
116 }
117 
118 always_inline clib_cuckoo_bucket_aux_t
119 clib_cuckoo_bucket_aux_set_writer_flag (clib_cuckoo_bucket_aux_t aux,
120  int writer_flag)
121 {
123  int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
124  return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
125 }
126 
127 #define PATH_BITS_REQ \
128  (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
129 
130 #if PATH_BITS_REQ <= 8
131 typedef u8 path_data_t;
132 #elif PATH_BITS_REQ <= 16
133 typedef u16 path_data_t;
134 #elif PATH_BITS_REQ <= 32
135 typedef u32 path_data_t;
136 #elif PATH_BITS_REQ <= 64
137 typedef u64 path_data_t;
138 #else
139 #error no suitable datatype for path storage...
140 #endif
141 
142 typedef struct
143 {
144  /** bucket where this path begins */
146  /** bucket at end of path */
148  /** length of the path */
150  /** holds compressed offsets in buckets along path */
151  path_data_t data;
153 
154 typedef struct
155 {
156  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
157 
158  /** reduced hashes corresponding to elements */
160 
161  /** auxiliary data - version, writer flag and used count */
162  volatile clib_cuckoo_bucket_aux_t aux;
163 
164  /** cuckoo elements in this bucket */
165  CVT (clib_cuckoo_kv) elts[CLIB_CUCKOO_KVP_PER_BUCKET];
166 } CVT (clib_cuckoo_bucket);
167 
168 #define clib_cuckoo_bucket_foreach_idx(var) \
169  for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++)
170 
171 #if CLIB_CUCKOO_OPTIMIZE_UNROLL
172 #if CLIB_CUCKOO_KVP_PER_BUCKET == 2
173 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
174  do \
175  { \
176  var = 0; \
177  body; \
178  var = 1; \
179  body; \
180  } \
181  while (0);
182 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 4
183 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
184  do \
185  { \
186  var = 0; \
187  body; \
188  var = 1; \
189  body; \
190  var = 2; \
191  body; \
192  var = 3; \
193  body; \
194  } \
195  while (0);
196 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 8
197 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
198  do \
199  { \
200  var = 0; \
201  body; \
202  var = 1; \
203  body; \
204  var = 2; \
205  body; \
206  var = 3; \
207  body; \
208  var = 4; \
209  body; \
210  var = 5; \
211  body; \
212  var = 6; \
213  body; \
214  var = 7; \
215  body; \
216  } \
217  while (0);
218 #else
219 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
220  clib_cuckoo_bucket_foreach_idx (var) \
221  { \
222  body; \
223  }
224 #endif
225 #else /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
226 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
227  clib_cuckoo_bucket_foreach_idx (var) \
228  { \
229  body; \
230  }
231 #endif /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
232 
233 #define clib_cuckoo_bucket_foreach_elt_index(var, bucket) \
234  for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
235 
236 #define clib_cuckoo_foreach_bucket(var, h, body) \
237  do \
238  { \
239  CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \
240  vec_foreach (var, __buckets) \
241  { \
242  body; \
243  } \
244  } \
245  while (0)
246 
247 typedef struct CV (clib_cuckoo)
248 {
249  /** vector of elements containing key-value pairs and auxiliary data */
250  CVT (clib_cuckoo_bucket) * volatile buckets;
251 
252  /** garbage to be freed once its safe to do so .. */
253  CVT (clib_cuckoo_bucket) * *to_be_freed;
254 
255  /** hash table name */
256  const char *name;
257 
258  /** pool of cuckoo paths (reused when doing bfd search) */
260 
261  /**
262  * vector used as queue when doing cuckoo path searches - holds offsets
263  * in paths pool
264  */
265  uword *bfs_search_queue;
266 
267  /**
268  * writer lock - whether this lock is taken or not has zero effect on
269  * readers
270  */
271  clib_spinlock_t writer_lock;
272 
273  /** caller context passed to callback with garbage notification */
274  void *garbage_ctx;
275 
276  /**
277  * garbage notify function - called when some garbage needs to be collected
278  * in main thread while other threads are stopped
279  */
280  void (*garbage_callback) (struct CV (clib_cuckoo) * h, void *garbage_ctx);
281 
282 #if CLIB_CUCKOO_DEBUG_COUNTERS
283  u64 steps_exceeded;
284  u64 bfs_queue_emptied;
285  u64 fast_adds;
286  u64 slow_adds;
287  u64 rehashes;
288 #endif
289 
290 } CVT (clib_cuckoo);
291 
292 void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
293  uword nbuckets,
294  void (*garbage_callback) (CVT (clib_cuckoo) *,
295  void *),
296  void *garbage_ctx);
297 
298 void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h);
299 
300 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h);
301 
302 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
303  CVT (clib_cuckoo_kv) * add_v, int is_add,
304  int dont_overwrite);
305 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
306  CVT (clib_cuckoo_kv) * search_v,
307  CVT (clib_cuckoo_kv) * return_v);
308 
309 void CV (clib_cuckoo_foreach_key_value_pair) (CVT (clib_cuckoo) * h,
310  void *callback, void *arg);
311 
312 float CV (clib_cuckoo_calc_load) (CVT (clib_cuckoo) * h);
313 
315 format_function_t CV (format_cuckoo_kvp);
316 
319 {
320  u32 v32 = ((u32) hash) ^ ((u32) (hash >> 32));
321  u16 v16 = ((u16) v32) ^ ((u16) (v32 >> 16));
322  u8 v8 = ((u8) v16) ^ ((u8) (v16 >> 8));
323  return v8;
324 }
325 
327 clib_cuckoo_get_other_bucket (u64 nbuckets, u64 bucket, u8 reduced_hash)
328 {
329  u64 mask = (nbuckets - 1);
330  return (bucket ^ ((reduced_hash + 1) * 0xc6a4a7935bd1e995)) & mask;
331 }
332 
334 CV (clib_cuckoo_calc_lookup) (CVT (clib_cuckoo_bucket) * buckets, u64 hash)
335 {
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);
343 #endif
344  u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
345  lookup.bucket2 =
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);
350 #endif
351  lookup.reduced_hash = reduced_hash;
352  ASSERT (lookup.bucket1 < nbuckets);
353  ASSERT (lookup.bucket2 < nbuckets);
354  return lookup;
355 }
356 
357 /**
358  * search for key within bucket
359  */
360 always_inline int CV (clib_cuckoo_bucket_search) (CVT (clib_cuckoo_bucket) *
361  b,
362  CVT (clib_cuckoo_kv) * kvp,
363  u8 reduced_hash)
364 {
365  clib_cuckoo_bucket_aux_t bucket_aux;
366  u8 writer_flag;
367  do
368  {
369  bucket_aux = b->aux;
370  writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (bucket_aux);
371  }
372  while (PREDICT_FALSE (writer_flag)); /* loop while writer flag is set */
373 
374  int i;
375 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
376  const int use_count = clib_cuckoo_bucket_aux_get_use_count (bucket_aux);
377 #endif
378  /* *INDENT-OFF* */
380 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
381  if (i > use_count)
382  {
383  break;
384  }
385 #endif
386  if (CV (clib_cuckoo_key_compare) (kvp->key, b->elts[i].key))
387  {
388  kvp->value = b->elts[i].value;
389  clib_cuckoo_bucket_aux_t bucket_aux2 = b->aux;
390  if (PREDICT_TRUE (clib_cuckoo_bucket_aux_get_version (bucket_aux) ==
391  clib_cuckoo_bucket_aux_get_version (bucket_aux2)))
392  {
393  /* yay, fresh data */
394  return CLIB_CUCKOO_ERROR_SUCCESS;
395  }
396  else
397  {
398  /* oops, modification detected */
399  return CLIB_CUCKOO_ERROR_AGAIN;
400  }
401  }
402  });
403  /* *INDENT-ON* */
404  return CLIB_CUCKOO_ERROR_NOT_FOUND;
405 }
406 
407 always_inline int
408 CV (clib_cuckoo_search_inline_with_hash) (CVT (clib_cuckoo) * h, u64 hash,
409  CVT (clib_cuckoo_kv) * kvp)
410 {
411  CVT (clib_cuckoo_bucket) * buckets = h->buckets;
412  uword bucket1, bucket2;
413  u8 reduced_hash;
414  u64 nbuckets = vec_len (buckets);
415  u64 mask = nbuckets - 1;
416  int rv;
417 
418  bucket1 = hash & mask;
419  reduced_hash = clib_cuckoo_reduce_hash (hash);
420 
421 again:
422  rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket1),
423  kvp, reduced_hash);
424 
425  if (rv == CLIB_CUCKOO_ERROR_SUCCESS)
426  return CLIB_CUCKOO_ERROR_SUCCESS;
427 
428  if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
429  goto again;
430 
431  bucket2 = clib_cuckoo_get_other_bucket (nbuckets, bucket1, reduced_hash);
432  rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket2),
433  kvp, reduced_hash);
434 
435  /* change to 2nd bucket could bump the item to 1st bucket and the bucket
436  * indexes might not even be valid anymore - restart the search */
437  if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
438  goto again;
439 
440  return rv;
441 }
442 
444  CVT (clib_cuckoo_kv) * kvp)
445 {
446  u64 hash = CV (clib_cuckoo_hash) (kvp);
447  return CV (clib_cuckoo_search_inline_with_hash) (h, hash, kvp);
448 }
449 
450 #endif /* __included_cuckoo_template_h__ */
451 
452 /** @endcond */
453 
454 /*
455  * fd.io coding-style-patch-verification: ON
456  *
457  * Local Variables:
458  * eval: (c-set-style "gnu")
459  * End:
460  */
#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body)
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
Definition: cache.h:60
int CV() clib_cuckoo_search(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *search_v, CVT(clib_cuckoo_kv) *return_v)
u64 start
bucket where this path begins
option version
Definition: sample.api:19
unsigned long u64
Definition: types.h:89
volatile clib_cuckoo_bucket_aux_t aux
auxiliary data - version, writer flag and used count
u8 length
length of the path
Fixed length block allocator.
u8 v8
Definition: ikev2.h:33
int CV() clib_cuckoo_add_del(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *add_v, int is_add, int dont_overwrite)
u64 clib_cuckoo_bucket_aux_t
#define CLIB_CUCKOO_KVP_PER_BUCKET
Definition: cuckoo_16_8.h:18
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")
static u64 clib_cuckoo_get_other_bucket(u64 nbuckets, u64 bucket, u8 reduced_hash)
#define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH
u16 mask
Definition: flow_types.api:52
unsigned char u8
Definition: types.h:56
static u8 clib_cuckoo_reduce_hash(u64 hash)
#define CVT(a)
u8 *() format_function_t(u8 *s, va_list *args)
Definition: format.h:48
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_version(clib_cuckoo_bucket_aux_t aux, u64 version)
float CV() clib_cuckoo_calc_load(CVT(clib_cuckoo) *h)
void CV() clib_cuckoo_init(CVT(clib_cuckoo) *h, const char *name, uword nbuckets, void(*garbage_callback)(CVT(clib_cuckoo) *, void *), void *garbage_ctx)
#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
Definition: cuckoo_16_8.h:19
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_use_count(clib_cuckoo_bucket_aux_t aux, int use_count)
unsigned int u32
Definition: types.h:88
static u64 clib_cuckoo_bucket_aux_get_version(clib_cuckoo_bucket_aux_t aux)
unsigned short u16
Definition: types.h:57
u64 bucket
bucket at end of path
vec_header_t h
Definition: buffer.c:322
#define PREDICT_FALSE(x)
Definition: clib.h:120
#define always_inline
Definition: ipsec.h:28
static int CV() clib_cuckoo_bucket_search(CVT(clib_cuckoo_bucket) *b, CVT(clib_cuckoo_kv) *kvp, u8 reduced_hash)
search for key within bucket
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
Definition: hash.c:545
#define CV(a)
static int CV() clib_cuckoo_search_inline_with_hash(CVT(clib_cuckoo) *h, u64 hash, CVT(clib_cuckoo_kv) *kvp)
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:80
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:317
static int clib_cuckoo_bucket_aux_get_use_count(clib_cuckoo_bucket_aux_t aux)
string name[64]
Definition: ip.api:44
void CV() clib_cuckoo_foreach_key_value_pair(CVT(clib_cuckoo) *h, void *callback, void *arg)
u8 *CV() format_cuckoo(u8 *s, va_list *args)
vl_api_fib_path_t paths[n_paths]
Definition: ip.api:146
#define ASSERT(truth)
void CV() clib_cuckoo_free(CVT(clib_cuckoo) *h)
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_writer_flag(clib_cuckoo_bucket_aux_t aux, int writer_flag)
static clib_cuckoo_lookup_info_t CV() clib_cuckoo_calc_lookup(CVT(clib_cuckoo_bucket) *buckets, u64 hash)
static int CV() clib_cuckoo_search_inline(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *kvp)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u64 uword
Definition: types.h:112
void CV() clib_cuckoo_garbage_collect(CVT(clib_cuckoo) *h)
perform garbage collection
path_data_t data
holds compressed offsets in buckets along path
u8 path_data_t
static int clib_cuckoo_bucket_aux_get_writer_flag(clib_cuckoo_bucket_aux_t aux)
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_pack(u64 version, int use_count, int writer_flag)