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