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