FD.io VPP  v20.09-64-g4f7b92f0a
Vector Packet Processing
cuckoo_template.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2017 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 /*
17  * cuckoo hash implementation based on paper
18  * 'Algorithmic Improvements for Fast Concurrent Cuckoo Hashing'
19  * by Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman
20  * and their libcuckoo implementation (https://github.com/efficient/libcuckoo)
21  */
22 
23 #include <vppinfra/vec.h>
24 
25 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
26  CVT (clib_cuckoo_kv) * search_v,
27  CVT (clib_cuckoo_kv) * return_v)
28 {
29  CVT (clib_cuckoo_kv) tmp = *search_v;
30  int rv = CV (clib_cuckoo_search_inline) (h, &tmp);
31  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
32  {
33  *return_v = tmp;
34  }
35  return rv;
36 }
37 
38 static
39 CVT (clib_cuckoo_bucket) *
40 CV (clib_cuckoo_bucket_at_index) (CVT (clib_cuckoo) * h, uword bucket)
41 {
42  return vec_elt_at_index (h->buckets, bucket);
43 }
44 
45 static uword CV (clib_cuckoo_get_nbuckets) (CVT (clib_cuckoo) * h)
46 {
47  return vec_len (h->buckets);
48 }
49 
50 static inline uword
51 CV (clib_cuckoo_elt_in_bucket_to_offset) (CVT (clib_cuckoo_bucket) * b,
52  CVT (clib_cuckoo_kv) * e)
53 {
54  ASSERT (e >= b->elts);
55  ASSERT (e <= &b->elts[sizeof (b->elts) / sizeof (b->elts[0]) - 1]);
56  return e - b->elts;
57 }
58 
59 u8 *CV (format_cuckoo_elt) (u8 * s, va_list * args)
60 {
61  CVT (clib_cuckoo_kv) * elt = va_arg (*args, CVT (clib_cuckoo_kv) *);
62  unsigned reduced_hash = va_arg (*args, unsigned);
63  if (CV (clib_cuckoo_kv_is_free) (elt))
64  {
65  s = format (s, "[ -- empty -- ]");
66  }
67  else
68  {
69  s = format (s, "[%U, reduced hash: %u]", CV (format_cuckoo_kvp), elt,
70  reduced_hash);
71  }
72  return s;
73 }
74 
75 u8 *CV (format_cuckoo_bucket) (u8 * s, va_list * args)
76 {
77  CVT (clib_cuckoo_bucket) * bucket =
78  va_arg (*args, CVT (clib_cuckoo_bucket) *);
79  int i = 0;
80 
81  /* *INDENT-OFF* */
83  {
84  CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
85  s = format (s, "bucket %p, offset %d: %U\n", bucket, i,
86  CV (format_cuckoo_elt), elt, bucket->reduced_hashes[i]);
87  }
88  /* *INDENT-ON* */
89  clib_cuckoo_bucket_aux_t aux = bucket->aux;
90  s = format (s, "version: %lld, use count: %d\n",
93  return s;
94 }
95 
96 #if CLIB_CUCKOO_DEBUG
97 static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
98 {
99  CVT (clib_cuckoo_bucket) * bucket;
100  uword bucket_idx = 0;
101  /* *INDENT-OFF* */
102  clib_cuckoo_foreach_bucket (bucket, h, {
103  int i = 0;
104  int used = 0;
106  {
107  CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
108  if (!CV (clib_cuckoo_kv_is_free) (elt))
109  {
110  u64 hash = CV (clib_cuckoo_hash) (elt);
112  CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
113  CVT (clib_cuckoo_kv) kv = *elt;
114  int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
115  if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
116  {
117  CLIB_CUCKOO_DBG ("Search for elt `%U' failed!",
118  CV (format_cuckoo_elt), elt,
119  bucket->reduced_hashes[i]);
120  CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
121  }
122  ASSERT (lookup.bucket1 == bucket_idx || lookup.bucket2 == bucket_idx);
123  ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
124  ++used;
125  }
126  }
127  clib_cuckoo_bucket_aux_t aux = bucket->aux;
129  ++bucket_idx;
130  });
131  /* *INDENT-ON* */
132  // CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h);
133 }
134 
135 #define CLIB_CUCKOO_DEEP_SELF_CHECK(h) CV (clib_cuckoo_deep_self_check) (h)
136 #define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b) \
137  do \
138  { \
139  int i; \
140  int min_free = CLIB_CUCKOO_KVP_PER_BUCKET; \
141  int max_used = 0; \
142  clib_cuckoo_bucket_foreach_idx (i) \
143  { \
144  if (!CV (clib_cuckoo_kv_is_free) (b->elts + i)) \
145  { \
146  max_used = i; \
147  } \
148  if (CV (clib_cuckoo_kv_is_free) (b->elts + \
149  (CLIB_CUCKOO_KVP_PER_BUCKET - i))) \
150  { \
151  min_free = i; \
152  } \
153  } \
154  ASSERT (min_free > max_used); \
155  } \
156  while (0)
157 
158 #else
159 #define CLIB_CUCKOO_DEEP_SELF_CHECK(h)
160 #define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b)
161 #endif
162 
163 void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
164  uword nbuckets,
165  void (*garbage_callback) (CVT (clib_cuckoo) *,
166  void *),
167  void *garbage_ctx)
168 {
169  uword log2_nbuckets = max_log2 (nbuckets);
170  nbuckets = 1ULL << (log2_nbuckets);
171  CLIB_CUCKOO_DBG ("New cuckoo, adjusted nbuckets %wu", nbuckets);
172  CVT (clib_cuckoo_bucket) * buckets = NULL;
173  vec_validate_aligned (buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
174  ASSERT (nbuckets == vec_len (buckets));
175  h->buckets = buckets;
176  clib_spinlock_init (&h->writer_lock);
177  /* mark all elements free ... */
178  CVT (clib_cuckoo_bucket) * bucket;
179  /* *INDENT-OFF* */
181  bucket, h, { clib_memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
182  /* *INDENT-ON* */
183  h->name = name;
184  h->garbage_callback = garbage_callback;
185  h->garbage_ctx = garbage_ctx;
186 }
187 
188 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h)
189 {
190  clib_memset (h, 0, sizeof (*h));
191 }
192 
194 CV (clib_cuckoo_bucket_version_bump_and_lock) (CVT (clib_cuckoo_bucket) * b)
195 {
196  clib_cuckoo_bucket_aux_t aux = b->aux;
198  u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
199  u8 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
200  ASSERT (0 == writer_flag);
201  aux = clib_cuckoo_bucket_aux_pack (version + 1, use_count, 1);
202  b->aux = aux;
203  return aux;
204 }
205 
206 static void CV (clib_cuckoo_bucket_unlock) (CVT (clib_cuckoo_bucket) * b,
208 {
210  u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
211  u8 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
212  ASSERT (1 == writer_flag);
213  aux = clib_cuckoo_bucket_aux_pack (version, use_count, 0);
214  b->aux = aux;
215 }
216 
217 #define CLIB_CUCKOO_DEBUG_PATH (1)
218 #define CLIB_CUCKOO_DEBUG_PATH_DETAIL (0)
219 
220 #if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH
221 static u8 *CV (format_cuckoo_path) (u8 * s, va_list * args);
222 #endif
223 
224 static clib_cuckoo_path_t *CV (clib_cuckoo_path_get) (CVT (clib_cuckoo) * h)
225 {
227  pool_get (h->paths, path);
228  clib_memset (path, 0, sizeof (*path));
229 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL
230  CLIB_CUCKOO_DBG ("Get path @%lu", (long unsigned) (path - h->paths));
231 #endif
232  return path;
233 }
234 
235 static void CV (clib_cuckoo_path_put) (CVT (clib_cuckoo) * h, uword path_idx)
236 {
237  clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
238 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL
239  CLIB_CUCKOO_DBG ("Put path @%lu", (long unsigned) (path - h->paths));
240 #endif
241  pool_put (h->paths, path);
242 }
243 
244 static clib_cuckoo_path_t *CV (clib_cuckoo_path_begin) (CVT (clib_cuckoo) * h,
245  uword bucket,
246  uword next_offset)
247 {
248  ASSERT (next_offset < CLIB_CUCKOO_KVP_PER_BUCKET);
250  new_path->length = 1;
251  new_path->data = next_offset;
252  new_path->start = bucket;
253  new_path->bucket = bucket;
254 #if CLIB_CUCKOO_DEBUG_PATH
255  CLIB_CUCKOO_DBG ("Create new path @%wu, length: %u data: %llu bucket: %wu "
256  "next-offset: %wu",
257  new_path - h->paths, new_path->length,
258  (long long unsigned) new_path->data, new_path->bucket,
259  next_offset);
260 #endif
261  return new_path;
262 }
263 
264 /**
265  * create a new path based on existing path extended by adding a bucket
266  * and offset
267  */
268 static uword CV (clib_cuckoo_path_extend) (CVT (clib_cuckoo) * h,
269  uword path_idx, uword bucket,
270  unsigned offset)
271 {
274  uword new_path_idx = new_path - h->paths;
275  clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
276  new_path->start = path->start;
277  new_path->length = path->length + 1;
278  new_path->data = (path->data << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) + offset;
279  new_path->bucket = bucket;
280 #if CLIB_CUCKOO_DEBUG_PATH
281  CLIB_CUCKOO_DBG ("Extend path @%wu, new path @%wu, %U", path_idx,
282  new_path_idx, CV (format_cuckoo_path), h, new_path_idx);
283 #endif
284  return new_path_idx;
285 }
286 
287 /** return the offset of the last element in the path */
289  path)
290 {
291  ASSERT (path->length > 0);
293  uword offset = path->data & mask;
294  return offset;
295 }
296 
297 static
298 CVT (clib_cuckoo_kv) *
299 CV (clib_cuckoo_bucket_find_empty) (CVT (clib_cuckoo_bucket) * bucket)
300 {
301  clib_cuckoo_bucket_aux_t aux = bucket->aux;
302  u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
303  if (use_count < CLIB_CUCKOO_KVP_PER_BUCKET)
304  {
305  return bucket->elts + use_count;
306  }
307  return NULL;
308 }
309 
310 /**
311  * walk the cuckoo path two ways,
312  * first backwards, extracting offsets,
313  * then forward, extracting buckets
314  *
315  * buckets and offsets are arrays filled with elements extracted from path
316  * the arrays must be able to contain CLIB_CUCKOO_BFS_MAX_PATH_LENGTH elements
317  */
318 static void
319 clib_cuckoo_path_walk (CVT (clib_cuckoo) * h, uword path_idx,
320  uword * buckets, uword * offsets)
321 {
322  clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
323  ASSERT (path->length > 0);
324  u64 data = path->data;
326  uword i;
327  for (i = path->length; i > 0; --i)
328  {
329  uword offset = data & mask;
330  offsets[i - 1] = offset;
332  }
333  buckets[0] = path->start;
334  for (i = 1; i < path->length; ++i)
335  {
336  CVT (clib_cuckoo_bucket) * b =
337  CV (clib_cuckoo_bucket_at_index) (h, buckets[i - 1]);
338  buckets[i] =
340  buckets[i - 1],
341  b->reduced_hashes[offsets[i - 1]]);
342  }
343 }
344 
345 #if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH
346 static u8 *CV (format_cuckoo_path) (u8 * s, va_list * args)
347 {
348  CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
349  uword path_idx = va_arg (*args, uword);
350  clib_cuckoo_path_t *p = pool_elt_at_index (h->paths, path_idx);
353  clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
354  s = format (s, "length %u: ", p->length);
355  for (uword i = p->length - 1; i > 0; --i)
356  {
357  s = format (s, "%wu[%wu]->", buckets[i], offsets[i]);
358  }
359  if (p->length)
360  {
361  s = format (s, "%wu[%wu]", buckets[0], offsets[0]);
362  }
363  return s;
364 }
365 #endif
366 
367 /*
368  * perform breadth-first search in the cuckoo hash, finding the closest
369  * empty slot, i.e. one which requires minimum swaps to move it
370  * to one of the buckets provided
371  */
372 static int CV (clib_cuckoo_find_empty_slot_bfs) (CVT (clib_cuckoo) * h,
374  lookup, uword * path_idx_out,
375  uword * found_bucket,
376  CVT (clib_cuckoo_kv) *
377  *found_elt)
378 {
379  uword *tail;
380  ASSERT (!vec_len (h->bfs_search_queue));
381  clib_cuckoo_path_t *tmp;
382  pool_flush (tmp, h->paths,);
383  int rv = CLIB_CUCKOO_ERROR_AGAIN;
384  int counter = 0;
385  /* start by creating paths starting in each of the buckets ... */
386  vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
387  int i;
388  for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
389  {
391  CV (clib_cuckoo_path_begin) (h, lookup->bucket1, i);
392  tail[i] = path - h->paths;
393  }
394  if (lookup->bucket1 != lookup->bucket2)
395  {
396  vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
397  for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
398  {
400  CV (clib_cuckoo_path_begin) (h, lookup->bucket2, i);
401  tail[i] = path - h->paths;
402  }
403  }
404  while (1)
405  {
406  if (counter >= CLIB_CUCKOO_BFS_MAX_STEPS)
407  {
408 #if CLIB_CUCKOO_DEBUG_COUNTERS
409  ++h->steps_exceeded;
410 #endif
411  break;
412  }
413  if (counter >= vec_len (h->bfs_search_queue))
414  {
415 #if CLIB_CUCKOO_DEBUG_COUNTERS
416  ++h->bfs_queue_emptied;
417 #endif
418  break;
419  }
420  const uword path_idx = vec_elt (h->bfs_search_queue, counter);
421  const clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
422 #if CLIB_CUCKOO_DEBUG_PATH
423  CLIB_CUCKOO_DBG ("Examine path @%wu: %U", path_idx,
424  CV (format_cuckoo_path), h, path_idx);
425 #endif
426  /* TODO prefetch ? */
427  /* search the alternative bucket for free space */
429  CVT (clib_cuckoo_bucket) * bucket =
430  CV (clib_cuckoo_bucket_at_index) (h, path->bucket);
431  uword other_bucket =
433  path->bucket,
434  bucket->reduced_hashes[offset]);
436  ("Path ends in bucket %wu, offset #%wu, other bucket is %wu",
437  path->bucket, CV (clib_cuckoo_path_peek_offset) (path),
438  other_bucket);
439  if (path->bucket != other_bucket)
440  {
441  if ((*found_elt =
442  CV (clib_cuckoo_bucket_find_empty) (CV
443  (clib_cuckoo_bucket_at_index)
444  (h, other_bucket))))
445  {
446  /* found empty element */
447  *found_bucket = other_bucket;
448  *path_idx_out = path_idx;
449  rv = CLIB_CUCKOO_ERROR_SUCCESS;
450 #if CLIB_CUCKOO_DEBUG_PATH
451  CLIB_CUCKOO_DBG ("Bucket with empty slot:\n%U",
453  CV (clib_cuckoo_bucket_at_index) (h,
454  other_bucket));
455 #endif
456  goto out;
457  }
458  /* extend the current path with possible next buckets and add to
459  * queue */
461  vec_len (h->bfs_search_queue) < CLIB_CUCKOO_BFS_MAX_STEPS)
462  {
463  uword *tail;
464  vec_add2 (h->bfs_search_queue, tail,
465  CLIB_CUCKOO_KVP_PER_BUCKET);
466  for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
467  {
468  uword new_path_idx =
469  CV (clib_cuckoo_path_extend) (h, path_idx, other_bucket,
470  i);
471  tail[i] = new_path_idx;
472  }
473  }
474  }
475  else
476  {
477  CLIB_CUCKOO_DBG ("Discard path @%wu, loop detected", path_idx);
478  }
479  /* done with this path - put back to pool for later reuse */
480  CV (clib_cuckoo_path_put) (h, path_idx);
481  ++counter;
482  }
483 out:
484  vec_reset_length (h->bfs_search_queue);
485  return rv;
486 }
487 
488 static void CV (clib_cuckoo_swap_elts_in_bucket) (CVT (clib_cuckoo_bucket) *
489  b, uword e1, uword e2)
490 {
491  CVT (clib_cuckoo_kv) kv;
492  clib_memcpy (&kv, b->elts + e1, sizeof (kv));
493  clib_memcpy (b->elts + e1, b->elts + e2, sizeof (kv));
494  clib_memcpy (b->elts + e2, &kv, sizeof (kv));
495  u8 reduced_hash = b->reduced_hashes[e1];
496  b->reduced_hashes[e1] = b->reduced_hashes[e2];
497  b->reduced_hashes[e2] = reduced_hash;
498 }
499 
500 static void CV (clib_cuckoo_bucket_tidy) (CVT (clib_cuckoo_bucket) * b)
501 {
502  int i = 0;
503  int j = CLIB_CUCKOO_KVP_PER_BUCKET - 1;
504  while (i != j)
505  {
506  int min_free = i;
507  int max_used = j;
508  while (!CV (clib_cuckoo_kv_is_free) (&b->elts[min_free]))
509  {
510  ++min_free;
511  }
512  while (CV (clib_cuckoo_kv_is_free) (&b->elts[max_used]))
513  {
514  --max_used;
515  }
516  if (min_free < max_used)
517  {
518  CV (clib_cuckoo_swap_elts_in_bucket) (b, min_free, max_used);
519  i = min_free + 1;
520  j = max_used - 1;
521  }
522  else
523  {
524  break;
525  }
526  }
527 }
528 
529 static void CV (clib_cuckoo_free_locked_elt) (CVT (clib_cuckoo_kv) * elt)
530 {
531  /*
532  * FIXME - improve performance by getting rid of this clib_memset - make all
533  * functions in this file not rely on clib_cuckoo_kv_is_free but instead
534  * take use_count into account */
535  clib_memset (elt, 0xff, sizeof (*elt));
536 }
537 
538 static void CV (clib_cuckoo_free_elt_in_bucket) (CVT (clib_cuckoo_bucket) * b,
539  CVT (clib_cuckoo_kv) * elt)
540 {
543  int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
544  int offset = elt - b->elts;
545  ASSERT (offset < use_count);
547  if (offset != use_count - 1)
548  {
550  }
551  aux = clib_cuckoo_bucket_aux_set_use_count (aux, use_count - 1);
552  CV (clib_cuckoo_bucket_unlock) (b, aux);
553 }
554 
555 static void CV (clib_cuckoo_set_locked_elt) (CVT (clib_cuckoo_bucket) * b,
556  CVT (clib_cuckoo_kv) * elt,
557  CVT (clib_cuckoo_kv) * kvp,
558  u8 reduced_hash)
559 {
561  clib_memcpy (elt, kvp, sizeof (*elt));
562  b->reduced_hashes[offset] = reduced_hash;
563  CLIB_CUCKOO_DBG ("Set bucket %p, offset %d, %U", b, offset,
564  CV (format_cuckoo_elt), elt, b->reduced_hashes[offset]);
565 }
566 
567 static void CV (clib_cuckoo_set_elt) (CVT (clib_cuckoo_bucket) * b,
568  CVT (clib_cuckoo_kv) * elt,
569  CVT (clib_cuckoo_kv) * kvp,
570  u8 reduced_hash)
571 {
574  CV (clib_cuckoo_set_locked_elt) (b, elt, kvp, reduced_hash);
575  CV (clib_cuckoo_bucket_unlock) (b, aux);
576 }
577 
578 static int CV (clib_cuckoo_add_slow) (CVT (clib_cuckoo) * h,
579  CVT (clib_cuckoo_kv) * kvp,
581  u8 reduced_hash)
582 {
583  uword path_idx;
584  uword empty_bucket_idx;
585  CVT (clib_cuckoo_kv) * empty_elt;
586  int rv = CV (clib_cuckoo_find_empty_slot_bfs) (h, lookup, &path_idx,
587  &empty_bucket_idx,
588  &empty_elt);
589  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
590  {
593  clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
594  /*
595  * walk back the path, moving the free element forward to one of our
596  * buckets ...
597  */
598  clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
599  CVT (clib_cuckoo_bucket) * empty_bucket =
600  CV (clib_cuckoo_bucket_at_index) (h, empty_bucket_idx);
601  int i;
602  for (i = path->length - 1; i >= 0; --i)
603  {
604  /* copy the key-value in path to the bucket with empty element */
605  CVT (clib_cuckoo_bucket) * b =
606  CV (clib_cuckoo_bucket_at_index) (h, buckets[i]);
607  CVT (clib_cuckoo_kv) * elt = b->elts + offsets[i];
608  clib_cuckoo_bucket_aux_t empty_aux =
611  (empty_bucket, empty_elt, elt, b->reduced_hashes[elt - b->elts]);
612  if (i == path->length - 1)
613  {
614  /* we only need to increase the use count for the bucket with
615  * free element - all other buckets' use counts won't change */
616  empty_aux = clib_cuckoo_bucket_aux_set_use_count (empty_aux,
618  (empty_aux) +
619  1);
620  }
621  CV (clib_cuckoo_bucket_unlock) (empty_bucket, empty_aux);
622  /*
623  * the element now exists in both places - in the previously empty
624  * element and in its original bucket - we can now safely overwrite
625  * the element in the original bucket with previous element in path
626  * without loosing data (and we don't need to modify the use count)
627  */
628  empty_bucket = b;
629  empty_elt = elt;
630  }
631  /* now we have a place to put the kvp in ... */
632  CV (clib_cuckoo_set_elt) (empty_bucket, empty_elt, kvp, reduced_hash);
633  CLIB_CUCKOO_DBG ("Slow insert success, bucket: %p\n%U", empty_bucket,
634  CV (format_cuckoo_bucket), empty_bucket);
635 #if CLIB_CUCKOO_DEBUG_COUNTERS
636  ++h->slow_adds;
637 #endif
638  }
639  return rv;
640 }
641 
642 static int CV (clib_cuckoo_add_fast) (CVT (clib_cuckoo) * h,
644  CVT (clib_cuckoo_kv) * kvp,
645  u8 reduced_hash)
646 {
647  CVT (clib_cuckoo_kv) * elt;
648  CVT (clib_cuckoo_bucket) * bucket1 =
649  CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket1);
650  if ((elt = CV (clib_cuckoo_bucket_find_empty) (bucket1)))
651  {
654  CV (clib_cuckoo_set_locked_elt) (bucket1, elt, kvp, reduced_hash);
655  aux =
658  (aux) + 1);
659  CV (clib_cuckoo_bucket_unlock) (bucket1, aux);
660 #if CLIB_CUCKOO_DEBUG_COUNTERS
661  ++h->fast_adds;
662 #endif
663  return CLIB_CUCKOO_ERROR_SUCCESS;
664  }
665  CVT (clib_cuckoo_bucket) * bucket2 =
666  CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket2);
667  if ((elt =
668  CV (clib_cuckoo_bucket_find_empty) (CV (clib_cuckoo_bucket_at_index)
669  (h, lookup->bucket2))))
670  {
673  CV (clib_cuckoo_set_locked_elt) (bucket2, elt, kvp, reduced_hash);
674  aux =
677  (aux) + 1);
678  CV (clib_cuckoo_bucket_unlock) (bucket2, aux);
679 #if CLIB_CUCKOO_DEBUG_COUNTERS
680  ++h->fast_adds;
681 #endif
682  return CLIB_CUCKOO_ERROR_SUCCESS;
683  }
684  return CLIB_CUCKOO_ERROR_AGAIN;
685 }
686 
687 /**
688  * perform garbage collection
689  *
690  * this function assumes there is no other thread touching the cuckoo hash,
691  * not even a reader, it's meant to be called from main thread
692  * in a stop-the-world situation
693  */
694 void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h)
695 {
697  CVT (clib_cuckoo_bucket) * *b;
698  /* *INDENT-OFF* */
699  vec_foreach (b, h->to_be_freed)
700  {
701  if (*b == h->buckets)
702  {
703  continue;
704  }
705 #if CLIB_CUCKOO_DEBUG_GC
706  fformat (stdout, "gc: free %p\n", *b);
707 #endif
708  vec_free (*b);
709  }
710  /* *INDENT-ON* */
711  vec_free (h->to_be_freed);
713 }
714 
715 /**
716  * expand and rehash a cuckoo hash
717  *
718  * 1. double the size of the hash table
719  * 2. move items to new locations derived from the new size
720  */
721 static void CV (clib_cuckoo_rehash) (CVT (clib_cuckoo) * h)
722 {
723  CVT (clib_cuckoo_bucket) * old = h->buckets;
724  uword old_nbuckets = vec_len (old);
725  uword new_nbuckets = 2 * old_nbuckets;
726  CVT (clib_cuckoo_bucket) * new =
728  /* allocate space */
729  vec_validate_aligned (new, new_nbuckets - 1, CLIB_CACHE_LINE_BYTES);
730  ASSERT (new_nbuckets == vec_len (new));
731  /* store old pointer in to-be-freed list */
732  vec_add1 (h->to_be_freed, old);
733  /* mark new elements as free */
734  CVT (clib_cuckoo_bucket) * bucket;
735  for (bucket = new + old_nbuckets; bucket < vec_end (new); ++bucket)
736  {
737  clib_memset (bucket->elts, 0xff, sizeof (bucket->elts));
738  }
739  /*
740  * this for loop manipulates the new (unseen) memory, so no locks
741  * are required here
742  */
743  uword old_bucket_idx;
744  for (old_bucket_idx = 0; old_bucket_idx < old_nbuckets; ++old_bucket_idx)
745  {
746  /* items in old bucket might be moved to new bucket */
747  uword new_bucket_idx = old_bucket_idx + old_nbuckets;
748  CVT (clib_cuckoo_bucket) * old_bucket = new + old_bucket_idx;
749  CVT (clib_cuckoo_bucket) * new_bucket = new + new_bucket_idx;
750  int i = 0;
751  int moved = 0;
752  clib_cuckoo_bucket_aux_t aux = old_bucket->aux;
753  for (i = 0; i < clib_cuckoo_bucket_aux_get_use_count (aux); ++i)
754  {
755  CVT (clib_cuckoo_kv) * elt = old_bucket->elts + i;
756  u64 hash = CV (clib_cuckoo_hash) (elt);
757  clib_cuckoo_lookup_info_t old_lookup =
758  CV (clib_cuckoo_calc_lookup) (old, hash);
759  clib_cuckoo_lookup_info_t new_lookup =
760  CV (clib_cuckoo_calc_lookup) (new, hash);
761  if ((old_bucket_idx == old_lookup.bucket1 &&
762  new_bucket_idx == new_lookup.bucket1) ||
763  (old_bucket_idx == old_lookup.bucket2 &&
764  new_bucket_idx == new_lookup.bucket2))
765  {
766  /* move the item to new bucket */
767  CVT (clib_cuckoo_kv) * empty_elt = new_bucket->elts + moved;
768  ASSERT (empty_elt);
770  (new_bucket, empty_elt, elt, old_bucket->reduced_hashes[i]);
772  ++moved;
773  }
774  }
775  if (moved)
776  {
777  CV (clib_cuckoo_bucket_tidy) (old_bucket);
778  aux =
780  clib_cuckoo_bucket_aux_get_use_count
781  (aux) - moved);
782  old_bucket->aux = aux;
783  aux = new_bucket->aux;
784  aux =
786  clib_cuckoo_bucket_aux_get_use_count
787  (aux) + moved);
788  new_bucket->aux = aux;
789  }
790  }
791  h->buckets = new;
792 #if CLIB_CUCKOO_DEBUG_COUNTERS
793  ++h->rehashes;
794 #endif
795  h->garbage_callback (h, h->garbage_ctx);
796 }
797 
798 static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h,
799  uword bucket,
800  CVT (clib_cuckoo_kv) *
801  kvp,
802  CVT (clib_cuckoo_kv) *
803  *found)
804 {
805  CVT (clib_cuckoo_bucket) * b = CV (clib_cuckoo_bucket_at_index) (h, bucket);
806  int i;
807  /* *INDENT-OFF* */
809  CVT (clib_cuckoo_kv) *elt = &b->elts[i];
810  if (CV (clib_cuckoo_key_compare) (elt->key, kvp->key))
811  {
812  *found = elt;
813  return CLIB_CUCKOO_ERROR_SUCCESS;
814  }
815  });
816  /* *INDENT-ON* */
817  return CLIB_CUCKOO_ERROR_NOT_FOUND;
818 }
819 
820 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
821  CVT (clib_cuckoo_kv) * kvp, int is_add,
822  int dont_overwrite)
823 {
824  CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp),
825  kvp);
827  u64 hash = CV (clib_cuckoo_hash) (kvp);
828  u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
829  clib_spinlock_lock (&h->writer_lock);
830 restart:
831  lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
832  CVT (clib_cuckoo_bucket) * b =
833  CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1);
834  CVT (clib_cuckoo_kv) * found;
835  int rv =
836  CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket1, kvp, &found);
837  if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
838  {
839  ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
840  b = CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2);
841  rv = CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket2, kvp,
842  &found);
843  }
844  if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
845  {
846  if (is_add)
847  {
848  if (dont_overwrite)
849  {
850  CLIB_CUCKOO_DBG ("Refused replacing existing %U",
851  CV (format_cuckoo_elt), found,
852  b->reduced_hashes[found - b->elts]);
853  rv = CLIB_CUCKOO_ERROR_AGAIN;
854  }
855  else
856  {
857  /* prevent readers reading this bucket while we switch the values */
860  clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
861  CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
862  found, b->reduced_hashes[found - b->elts]);
863  CV (clib_cuckoo_bucket_unlock) (b, aux);
864  rv = CLIB_CUCKOO_ERROR_SUCCESS;
865  }
866  }
867  else
868  {
869  CV (clib_cuckoo_free_elt_in_bucket) (b, found);
870  rv = CLIB_CUCKOO_ERROR_SUCCESS;
871  }
873  goto unlock;
874  }
875  if (!is_add)
876  {
877  CLIB_CUCKOO_DBG ("%U not present in table", CV (format_cuckoo_kvp),
878  kvp);
879  rv = CLIB_CUCKOO_ERROR_NOT_FOUND;
880  goto unlock;
881  }
882  /* from this point on, it's add code only */
883  ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
884  /* fast path: try to search for unoccupied slot in one of the buckets */
885  rv = CV (clib_cuckoo_add_fast) (h, &lookup, kvp, reduced_hash);
887  if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
888  {
890  ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U",
891  lookup.bucket1, lookup.bucket2, CV (format_cuckoo_bucket),
892  CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1),
894  CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2));
895  /* slow path */
896  rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
898  if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
899  {
900  CLIB_CUCKOO_DBG ("Slow insert failed, rehash required:\n%U",
901  CV (format_cuckoo), h, 1);
902  /* ultra slow path */
903  CV (clib_cuckoo_rehash) (h);
905  CLIB_CUCKOO_DBG ("Restarting add after rehash...");
906  goto restart;
907  }
908  }
909 unlock:
910  clib_spinlock_unlock (&h->writer_lock);
911  return rv;
912 }
913 
914 u8 *CV (format_cuckoo) (u8 * s, va_list * args)
915 {
916  CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
917  int verbose = va_arg (*args, int);
918 
919  s = format (s, "Hash table %s\n", h->name ? h->name : "(unnamed)");
920 
921  uword free = 0;
922  uword used = 0;
923  uword use_count_total = 0;
924  float load_factor;
925  CVT (clib_cuckoo_bucket) * b;
926  /* *INDENT-OFF* */
928  if (verbose)
929  {
930  s = format (s, "%U", CV (format_cuckoo_bucket), b);
931  }
932  int i;
934  {
935  CVT (clib_cuckoo_kv) *elt = &b->elts[i];
936  if (CV (clib_cuckoo_kv_is_free) (elt))
937  {
938  ++free;
939  }
940  else
941  {
942  ++used;
943  }
944  }
945  clib_cuckoo_bucket_aux_t aux = b->aux;
946  use_count_total += clib_cuckoo_bucket_aux_get_use_count (aux);
947  });
948  /* *INDENT-ON* */
949  s = format (s, "Used slots: %wu\n", used);
950  s = format (s, "Use count total: %wu\n", use_count_total);
951  s = format (s, "Free slots: %wu\n", free);
952  if (free + used != 0)
953  load_factor = ((float) used) / ((float) (free + used));
954  else
955  load_factor = 0.0;
956  s = format (s, "Load factor: %.2f\n", load_factor);
957 #if CLIB_CUCKOO_DEBUG_COUNTERS
958  s = format (s, "BFS attempts limited by max steps: %lld\n",
959  h->steps_exceeded);
960  s = format (s, "BFS cutoffs due to empty queue: %lld\n",
961  h->bfs_queue_emptied);
962  s = format (s, "Fast adds: %lld\n", h->fast_adds);
963  s = format (s, "Slow adds: %lld\n", h->slow_adds);
964  s = format (s, "Rehashes: %lld\n", h->rehashes);
965 #endif
966  return s;
967 }
968 
969 float CV (clib_cuckoo_calculate_load_factor) (CVT (clib_cuckoo) * h)
970 {
971  uword nonfree = 0;
972  uword all = 0;
973  CVT (clib_cuckoo_bucket) * bucket;
974  /* *INDENT-OFF* */
975  clib_cuckoo_foreach_bucket (bucket, h, {
976  int i;
978  {
979  CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
980  ++all;
981  if (!CV (clib_cuckoo_kv_is_free) (elt))
982  {
983  ++nonfree;
984  }
985  }
986  });
987  /* *INDENT-ON* */
988  if (all)
989  return (float) nonfree / (float) all;
990  else
991  return 0.0;
992 }
993 
994 /** @endcond */
995 
996 /*
997  * fd.io coding-style-patch-verification: ON
998  *
999  * Local Variables:
1000  * eval: (c-set-style "gnu")
1001  * End:
1002  */
void CV() clib_cuckoo_garbage_collect(CVT(clib_cuckoo) *h)
perform garbage collection
#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body)
static_always_inline void clib_spinlock_unlock(clib_spinlock_t *p)
Definition: lock.h:119
static_always_inline void clib_spinlock_lock(clib_spinlock_t *p)
Definition: lock.h:80
u8 *CV() format_cuckoo_bucket(u8 *s, va_list *args)
static CVT(clib_cuckoo_bucket)
u64 start
bucket where this path begins
option version
Definition: sample.api:19
unsigned long u64
Definition: types.h:89
u8 length
length of the path
u64 clib_cuckoo_bucket_aux_t
#define clib_cuckoo_foreach_bucket(var, h, body)
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
static clib_cuckoo_path_t *CV() clib_cuckoo_path_get(CVT(clib_cuckoo) *h)
u8 *CV() format_cuckoo_elt(u8 *s, va_list *args)
#define CLIB_CUCKOO_KVP_PER_BUCKET
Definition: cuckoo_16_8.h:18
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 vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:592
static u64 clib_cuckoo_get_other_bucket(u64 nbuckets, u64 bucket, u8 reduced_hash)
static void clib_cuckoo_path_walk(CVT(clib_cuckoo) *h, uword path_idx, uword *buckets, uword *offsets)
walk the cuckoo path two ways, first backwards, extracting offsets, then forward, extracting buckets ...
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:630
static void CV() clib_cuckoo_free_locked_elt(CVT(clib_cuckoo_kv) *elt)
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
vl_api_fib_path_t path
Definition: mfib_types.api:34
#define vec_validate_aligned(V, I, A)
Make sure vector is long enough for given index (no header, specified alignment)
Definition: vec.h:520
u16 mask
Definition: flow_types.api:52
static void CV() clib_cuckoo_swap_elts_in_bucket(CVT(clib_cuckoo_bucket) *b, uword e1, uword e2)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:252
#define CLIB_CUCKOO_DEEP_SELF_CHECK(h)
unsigned char u8
Definition: types.h:56
static u8 clib_cuckoo_reduce_hash(u64 hash)
u8 data[128]
Definition: ipsec_types.api:89
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
#define clib_memcpy(d, s, n)
Definition: string.h:180
static void CV() clib_cuckoo_rehash(CVT(clib_cuckoo) *h)
expand and rehash a cuckoo hash
#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
Definition: cuckoo_16_8.h:19
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)
static clib_cuckoo_path_t *CV() clib_cuckoo_path_begin(CVT(clib_cuckoo) *h, uword bucket, uword next_offset)
#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)
static void CV() clib_cuckoo_bucket_tidy(CVT(clib_cuckoo_bucket) *b)
#define vec_end(v)
End (last data address) of vector.
static void CV() clib_cuckoo_path_put(CVT(clib_cuckoo) *h, uword path_idx)
#define CLIB_CUCKOO_BFS_MAX_PATH_LENGTH
Definition: cuckoo_16_8.h:21
static int CV() clib_cuckoo_bucket_search_internal(CVT(clib_cuckoo) *h, uword bucket, CVT(clib_cuckoo_kv) *kvp, CVT(clib_cuckoo_kv) **found)
static uword CV() clib_cuckoo_get_nbuckets(CVT(clib_cuckoo) *h)
static void clib_spinlock_init(clib_spinlock_t *p)
Definition: lock.h:63
#define pool_flush(VAR, POOL, BODY)
Remove all elements from a pool in a safe way.
Definition: pool.h:573
static u64 clib_cuckoo_bucket_aux_get_version(clib_cuckoo_bucket_aux_t aux)
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:534
static void CV() clib_cuckoo_bucket_unlock(CVT(clib_cuckoo_bucket) *b, clib_cuckoo_bucket_aux_t aux)
u64 bucket
bucket at end of path
vec_header_t h
Definition: buffer.c:322
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)
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:302
static clib_cuckoo_bucket_aux_t CV() clib_cuckoo_bucket_version_bump_and_lock(CVT(clib_cuckoo_bucket) *b)
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)
#define CLIB_CUCKOO_DBG(...)
Definition: cuckoo_debug.h:71
word fformat(FILE *f, char *fmt,...)
Definition: format.c:462
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
Definition: hash.c:545
int CV() clib_cuckoo_add_del(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *kvp, int is_add, int dont_overwrite)
#define clib_cuckoo_bucket_foreach_idx(var)
#define CV(a)
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:317
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:380
static int clib_cuckoo_bucket_aux_get_use_count(clib_cuckoo_bucket_aux_t aux)
string name[64]
Definition: ip.api:44
u8 *CV() format_cuckoo(u8 *s, va_list *args)
#define ASSERT(truth)
int CV() clib_cuckoo_search(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *search_v, CVT(clib_cuckoo_kv) *return_v)
static void CV() clib_cuckoo_free_elt_in_bucket(CVT(clib_cuckoo_bucket) *b, CVT(clib_cuckoo_kv) *elt)
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)
static clib_cuckoo_lookup_info_t CV() clib_cuckoo_calc_lookup(CVT(clib_cuckoo_bucket) *buckets, u64 hash)
#define vec_elt(v, i)
Get vector value at index i.
static int CV() clib_cuckoo_search_inline(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *kvp)
template key/value backing page structure
Definition: bihash_doc.h:44
#define vec_dup_aligned(V, A)
Return copy of vector (no header, alignment specified).
Definition: vec.h:438
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static uword max_log2(uword x)
Definition: clib.h:208
u64 uword
Definition: types.h:112
void CV() clib_cuckoo_free(CVT(clib_cuckoo) *h)
struct clib_bihash_value offset
template key/value backing page structure
static uword CV() clib_cuckoo_elt_in_bucket_to_offset(CVT(clib_cuckoo_bucket) *b, CVT(clib_cuckoo_kv) *e)
path_data_t data
holds compressed offsets in buckets along path
#define vec_foreach(var, vec)
Vector iterator.
#define CLIB_MEMORY_BARRIER()
Definition: clib.h:132
#define CLIB_CUCKOO_BFS_MAX_STEPS
Definition: cuckoo_16_8.h:20
static uword CV() clib_cuckoo_path_peek_offset(const clib_cuckoo_path_t *path)
return the offset of the last element in the path
static uword CV() clib_cuckoo_path_extend(CVT(clib_cuckoo) *h, uword path_idx, uword bucket, unsigned offset)
create a new path based on existing path extended by adding a bucket and offset
float CV() clib_cuckoo_calculate_load_factor(CVT(clib_cuckoo) *h)
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:59
static int clib_cuckoo_bucket_aux_get_writer_flag(clib_cuckoo_bucket_aux_t 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)
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_pack(u64 version, int use_count, int writer_flag)
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".