FD.io VPP  v19.04.2-12-g66b1689
Vector Packet Processing
bihash_template.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 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 /** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */
17 
18 static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes)
19 {
20  uword rv;
21 
22  /* Round to an even number of cache lines */
23  nbytes += CLIB_CACHE_LINE_BYTES - 1;
24  nbytes &= ~(CLIB_CACHE_LINE_BYTES - 1);
25 
26  rv = alloc_arena_next (h);
27  alloc_arena_next (h) += nbytes;
28 
29  if (rv >= alloc_arena_size (h))
31 
32  return (void *) (uword) (rv + alloc_arena (h));
33 }
34 
35 
36 void BV (clib_bihash_init)
37  (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
38 {
39  uword bucket_size;
40 
41  nbuckets = 1 << (max_log2 (nbuckets));
42 
43  h->name = (u8 *) name;
44  h->nbuckets = nbuckets;
45  h->log2_nbuckets = max_log2 (nbuckets);
46 
47  /*
48  * Make sure the requested size is rational. The max table
49  * size without playing the alignment card is 64 Gbytes.
50  * If someone starts complaining that's not enough, we can shift
51  * the offset by CLIB_LOG2_CACHE_LINE_BYTES...
52  */
53  ASSERT (memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
54 
55  alloc_arena (h) = (uword) clib_mem_vm_alloc (memory_size);
56  alloc_arena_next (h) = 0;
57  alloc_arena_size (h) = memory_size;
58 
59  bucket_size = nbuckets * sizeof (h->buckets[0]);
60  h->buckets = BV (alloc_aligned) (h, bucket_size);
61 
62  h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES);
63  h->alloc_lock[0] = 0;
64 
65  h->fmt_fn = NULL;
66 }
67 
68 #if BIHASH_32_64_SVM
69 #if !defined (MFD_ALLOW_SEALING)
70 #define MFD_ALLOW_SEALING 0x0002U
71 #endif
72 
73 void BV (clib_bihash_master_init_svm)
74  (BVT (clib_bihash) * h, char *name, u32 nbuckets, u64 memory_size)
75 {
76  uword bucket_size;
77  u8 *mmap_addr;
78  vec_header_t *freelist_vh;
79  int fd;
80 
81  ASSERT (memory_size < (1ULL << 32));
82  /* Set up for memfd sharing */
83  if ((fd = memfd_create (name, MFD_ALLOW_SEALING)) == -1)
84  {
85  clib_unix_warning ("memfd_create");
86  return;
87  }
88 
89  if (ftruncate (fd, memory_size) < 0)
90  {
91  clib_unix_warning ("ftruncate");
92  return;
93  }
94 
95  /* Not mission-critical, complain and continue */
96  if ((fcntl (fd, F_ADD_SEALS, F_SEAL_SHRINK)) == -1)
97  clib_unix_warning ("fcntl (F_ADD_SEALS)");
98 
99  mmap_addr = mmap (0, memory_size,
100  PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ );
101 
102  if (mmap_addr == MAP_FAILED)
103  {
104  clib_unix_warning ("mmap failed");
105  ASSERT (0);
106  }
107 
108  h->sh = (void *) mmap_addr;
109  h->memfd = fd;
110  nbuckets = 1 << (max_log2 (nbuckets));
111 
112  h->name = (u8 *) name;
113  h->sh->nbuckets = h->nbuckets = nbuckets;
114  h->log2_nbuckets = max_log2 (nbuckets);
115 
116  alloc_arena (h) = (u64) (uword) mmap_addr;
117  alloc_arena_next (h) = CLIB_CACHE_LINE_BYTES;
118  alloc_arena_size (h) = memory_size;
119 
120  bucket_size = nbuckets * sizeof (h->buckets[0]);
121  h->buckets = BV (alloc_aligned) (h, bucket_size);
122  h->sh->buckets_as_u64 = (u64) BV (clib_bihash_get_offset) (h, h->buckets);
123 
124  h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES);
125  h->alloc_lock[0] = 0;
126 
127  h->sh->alloc_lock_as_u64 =
128  (u64) BV (clib_bihash_get_offset) (h, (void *) h->alloc_lock);
129  freelist_vh =
130  BV (alloc_aligned) (h,
131  sizeof (vec_header_t) +
132  BIHASH_FREELIST_LENGTH * sizeof (u64));
133  freelist_vh->len = BIHASH_FREELIST_LENGTH;
134  freelist_vh->dlmalloc_header_offset = 0xDEADBEEF;
135  h->sh->freelists_as_u64 =
136  (u64) BV (clib_bihash_get_offset) (h, freelist_vh->vector_data);
137  h->freelists = (void *) (freelist_vh->vector_data);
138 
139  h->fmt_fn = NULL;
140 }
141 
142 void BV (clib_bihash_slave_init_svm)
143  (BVT (clib_bihash) * h, char *name, int fd)
144 {
145  u8 *mmap_addr;
147  BVT (clib_bihash_shared_header) * sh;
148 
149  /* Trial mapping, to learn the segment size */
150  mmap_addr = mmap (0, 4096, PROT_READ, MAP_SHARED, fd, 0 /* offset */ );
151  if (mmap_addr == MAP_FAILED)
152  {
153  clib_unix_warning ("trial mmap failed");
154  ASSERT (0);
155  }
156 
157  sh = (BVT (clib_bihash_shared_header) *) mmap_addr;
158 
159  memory_size = sh->alloc_arena_size;
160 
161  munmap (mmap_addr, 4096);
162 
163  /* Actual mapping, at the required size */
164  mmap_addr = mmap (0, memory_size,
165  PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ );
166 
167  if (mmap_addr == MAP_FAILED)
168  {
169  clib_unix_warning ("mmap failed");
170  ASSERT (0);
171  }
172 
173  (void) close (fd);
174 
175  h->sh = (void *) mmap_addr;
176  alloc_arena (h) = (u64) (uword) mmap_addr;
177  h->memfd = -1;
178 
179  h->name = (u8 *) name;
180  h->buckets = BV (clib_bihash_get_value) (h, h->sh->buckets_as_u64);
181  h->nbuckets = h->sh->nbuckets;
182  h->log2_nbuckets = max_log2 (h->nbuckets);
183 
184  h->alloc_lock = BV (clib_bihash_get_value) (h, h->sh->alloc_lock_as_u64);
185  h->freelists = BV (clib_bihash_get_value) (h, h->sh->freelists_as_u64);
186  h->fmt_fn = NULL;
187 }
188 #endif /* BIHASH_32_64_SVM */
189 
190 void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
191  format_function_t * fmt_fn)
192 {
193  h->fmt_fn = fmt_fn;
194 }
195 
196 void BV (clib_bihash_free) (BVT (clib_bihash) * h)
197 {
198  vec_free (h->working_copies);
199 #if BIHASH_32_64_SVM == 0
200  vec_free (h->freelists);
201 #else
202  if (h->memfd > 0)
203  (void) close (h->memfd);
204 #endif
205  clib_mem_vm_free ((void *) (uword) (alloc_arena (h)), alloc_arena_size (h));
206  clib_memset (h, 0, sizeof (*h));
207 }
208 
209 static
211 BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
212 {
213  BVT (clib_bihash_value) * rv = 0;
214 
215  ASSERT (h->alloc_lock[0]);
216 
217 #if BIHASH_32_64_SVM
218  ASSERT (log2_pages < vec_len (h->freelists));
219 #endif
220 
221  if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
222  {
223  vec_validate_init_empty (h->freelists, log2_pages, 0);
224  rv = BV (alloc_aligned) (h, (sizeof (*rv) * (1 << log2_pages)));
225  goto initialize;
226  }
227  rv = BV (clib_bihash_get_value) (h, (uword) h->freelists[log2_pages]);
228  h->freelists[log2_pages] = rv->next_free_as_u64;
229 
230 initialize:
231  ASSERT (rv);
232  /*
233  * Latest gcc complains that the length arg is zero
234  * if we replace (1<<log2_pages) with vec_len(rv).
235  * No clue.
236  */
237  clib_memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
238  return rv;
239 }
240 
241 static void
242 BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
243  u32 log2_pages)
244 {
245  ASSERT (h->alloc_lock[0]);
246 
247  ASSERT (vec_len (h->freelists) > log2_pages);
248 
249  if (CLIB_DEBUG > 0)
250  clib_memset (v, 0xFE, sizeof (*v) * (1 << log2_pages));
251 
252  v->next_free_as_u64 = (u64) h->freelists[log2_pages];
253  h->freelists[log2_pages] = (u64) BV (clib_bihash_get_offset) (h, v);
254 }
255 
256 static inline void
257 BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
258 {
259  BVT (clib_bihash_value) * v;
260  BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8)));
261  BVT (clib_bihash_value) * working_copy;
262  u32 thread_index = os_get_thread_index ();
263  int log2_working_copy_length;
264 
265  ASSERT (h->alloc_lock[0]);
266 
267  if (thread_index >= vec_len (h->working_copies))
268  {
269  vec_validate (h->working_copies, thread_index);
270  vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0);
271  }
272 
273  /*
274  * working_copies are per-cpu so that near-simultaneous
275  * updates from multiple threads will not result in sporadic, spurious
276  * lookup failures.
277  */
278  working_copy = h->working_copies[thread_index];
279  log2_working_copy_length = h->working_copy_lengths[thread_index];
280 
281  h->saved_bucket.as_u64 = b->as_u64;
282 
283  if (b->log2_pages > log2_working_copy_length)
284  {
285  /*
286  * It's not worth the bookkeeping to free working copies
287  * if (working_copy)
288  * clib_mem_free (working_copy);
289  */
290  working_copy = BV (alloc_aligned)
291  (h, sizeof (working_copy[0]) * (1 << b->log2_pages));
292  h->working_copy_lengths[thread_index] = b->log2_pages;
293  h->working_copies[thread_index] = working_copy;
294  }
295 
296  v = BV (clib_bihash_get_value) (h, b->offset);
297 
298  clib_memcpy_fast (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
299  working_bucket.as_u64 = b->as_u64;
300  working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
302  b->as_u64 = working_bucket.as_u64;
303  h->working_copies[thread_index] = working_copy;
304 }
305 
306 static
308 BV (split_and_rehash)
309  (BVT (clib_bihash) * h,
310  BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
311  u32 new_log2_pages)
312 {
313  BVT (clib_bihash_value) * new_values, *new_v;
314  int i, j, length_in_kvs;
315 
316  ASSERT (h->alloc_lock[0]);
317 
318  new_values = BV (value_alloc) (h, new_log2_pages);
319  length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
320 
321  for (i = 0; i < length_in_kvs; i++)
322  {
323  u64 new_hash;
324 
325  /* Entry not in use? Forget it */
326  if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
327  continue;
328 
329  /* rehash the item onto its new home-page */
330  new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
331  new_hash >>= h->log2_nbuckets;
332  new_hash &= (1 << new_log2_pages) - 1;
333  new_v = &new_values[new_hash];
334 
335  /* Across the new home-page */
336  for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
337  {
338  /* Empty slot */
339  if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
340  {
341  clib_memcpy_fast (&(new_v->kvp[j]), &(old_values->kvp[i]),
342  sizeof (new_v->kvp[j]));
343  goto doublebreak;
344  }
345  }
346  /* Crap. Tell caller to try again */
347  BV (value_free) (h, new_values, new_log2_pages);
348  return 0;
349  doublebreak:;
350  }
351 
352  return new_values;
353 }
354 
355 static
358  (BVT (clib_bihash) * h,
359  BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
360  u32 new_log2_pages)
361 {
362  BVT (clib_bihash_value) * new_values;
363  int i, j, new_length, old_length;
364 
365  ASSERT (h->alloc_lock[0]);
366 
367  new_values = BV (value_alloc) (h, new_log2_pages);
368  new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
369  old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
370 
371  j = 0;
372  /* Across the old value array */
373  for (i = 0; i < old_length; i++)
374  {
375  /* Find a free slot in the new linear scan bucket */
376  for (; j < new_length; j++)
377  {
378  /* Old value not in use? Forget it. */
379  if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
380  goto doublebreak;
381 
382  /* New value should never be in use */
383  if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
384  {
385  /* Copy the old value and move along */
386  clib_memcpy_fast (&(new_values->kvp[j]), &(old_values->kvp[i]),
387  sizeof (new_values->kvp[j]));
388  j++;
389  goto doublebreak;
390  }
391  }
392  /* This should never happen... */
393  clib_warning ("BUG: linear rehash failed!");
394  BV (value_free) (h, new_values, new_log2_pages);
395  return 0;
396 
397  doublebreak:;
398  }
399  return new_values;
400 }
401 
402 static inline int BV (clib_bihash_add_del_inline)
403  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add,
404  int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
405 {
406  u32 bucket_index;
407  BVT (clib_bihash_bucket) * b, tmp_b;
408  BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
409  int i, limit;
410  u64 hash, new_hash;
411  u32 new_log2_pages, old_log2_pages;
412  u32 thread_index = os_get_thread_index ();
413  int mark_bucket_linear;
414  int resplit_once;
415 
416  hash = BV (clib_bihash_hash) (add_v);
417 
418  bucket_index = hash & (h->nbuckets - 1);
419  b = &h->buckets[bucket_index];
420 
421  hash >>= h->log2_nbuckets;
422 
423  BV (clib_bihash_lock_bucket) (b);
424 
425  /* First elt in the bucket? */
426  if (BV (clib_bihash_bucket_is_empty) (b))
427  {
428  if (is_add == 0)
429  {
430  BV (clib_bihash_unlock_bucket) (b);
431  return (-1);
432  }
433 
434  BV (clib_bihash_alloc_lock) (h);
435  v = BV (value_alloc) (h, 0);
436  BV (clib_bihash_alloc_unlock) (h);
437 
438  *v->kvp = *add_v;
439  tmp_b.as_u64 = 0; /* clears bucket lock */
440  tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
441  tmp_b.refcnt = 1;
443 
444  b->as_u64 = tmp_b.as_u64; /* unlocks the bucket */
445  return (0);
446  }
447 
448  /* WARNING: we're still looking at the live copy... */
449  limit = BIHASH_KVP_PER_PAGE;
450  v = BV (clib_bihash_get_value) (h, b->offset);
451 
452  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
453  if (b->linear_search)
454  limit <<= b->log2_pages;
455 
456  if (is_add)
457  {
458  /*
459  * Because reader threads are looking at live data,
460  * we have to be extra careful. Readers do NOT hold the
461  * bucket lock. We need to be SLOWER than a search, past the
462  * point where readers CHECK the bucket lock.
463  */
464 
465  /*
466  * For obvious (in hindsight) reasons, see if we're supposed to
467  * replace an existing key, then look for an empty slot.
468  */
469  for (i = 0; i < limit; i++)
470  {
471  if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
472  {
473  CLIB_MEMORY_BARRIER (); /* Add a delay */
474  clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
475  BV (clib_bihash_unlock_bucket) (b);
476  return (0);
477  }
478  }
479  /*
480  * Look for an empty slot. If found, use it
481  */
482  for (i = 0; i < limit; i++)
483  {
484  if (BV (clib_bihash_is_free) (&(v->kvp[i])))
485  {
486  /*
487  * Copy the value first, so that if a reader manages
488  * to match the new key, the value will be right...
489  */
490  clib_memcpy_fast (&(v->kvp[i].value),
491  &add_v->value, sizeof (add_v->value));
492  CLIB_MEMORY_BARRIER (); /* Make sure the value has settled */
493  clib_memcpy_fast (&(v->kvp[i]), &add_v->key,
494  sizeof (add_v->key));
495  b->refcnt++;
496  ASSERT (b->refcnt > 0);
497  BV (clib_bihash_unlock_bucket) (b);
498  return (0);
499  }
500  }
501  /* look for stale data to overwrite */
502  if (is_stale_cb)
503  {
504  for (i = 0; i < limit; i++)
505  {
506  if (is_stale_cb (&(v->kvp[i]), arg))
507  {
509  clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
510  BV (clib_bihash_unlock_bucket) (b);
511  return (0);
512  }
513  }
514  }
515  /* Out of space in this bucket, split the bucket... */
516  }
517  else /* delete case */
518  {
519  for (i = 0; i < limit; i++)
520  {
521  /* Found the key? Kill it... */
522  if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
523  {
524  clib_memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
525  /* Is the bucket empty? */
526  if (PREDICT_TRUE (b->refcnt > 1))
527  {
528  b->refcnt--;
529  BV (clib_bihash_unlock_bucket) (b);
530  return (0);
531  }
532  else /* yes, free it */
533  {
534  /* Save old bucket value, need log2_pages to free it */
535  tmp_b.as_u64 = b->as_u64;
537 
538  /* Kill and unlock the bucket */
539  b->as_u64 = 0;
540 
541  /* And free the backing storage */
542  BV (clib_bihash_alloc_lock) (h);
543  /* Note: v currently points into the middle of the bucket */
544  v = BV (clib_bihash_get_value) (h, tmp_b.offset);
545  BV (value_free) (h, v, tmp_b.log2_pages);
546  BV (clib_bihash_alloc_unlock) (h);
547  return (0);
548  }
549  }
550  }
551  /* Not found... */
552  BV (clib_bihash_unlock_bucket) (b);
553  return (-3);
554  }
555 
556  /* Move readers to a (locked) temp copy of the bucket */
557  BV (clib_bihash_alloc_lock) (h);
558  BV (make_working_copy) (h, b);
559 
560  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
561 
562  old_log2_pages = h->saved_bucket.log2_pages;
563  new_log2_pages = old_log2_pages + 1;
564  mark_bucket_linear = 0;
565 
566  working_copy = h->working_copies[thread_index];
567  resplit_once = 0;
568 
569  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
570  new_log2_pages);
571  if (new_v == 0)
572  {
573  try_resplit:
574  resplit_once = 1;
575  new_log2_pages++;
576  /* Try re-splitting. If that fails, fall back to linear search */
577  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
578  new_log2_pages);
579  if (new_v == 0)
580  {
581  mark_linear:
582  new_log2_pages--;
583  /* pinned collisions, use linear search */
584  new_v =
585  BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
586  new_log2_pages);
587  mark_bucket_linear = 1;
588  }
589  }
590 
591  /* Try to add the new entry */
592  save_new_v = new_v;
593  new_hash = BV (clib_bihash_hash) (add_v);
594  limit = BIHASH_KVP_PER_PAGE;
595  if (mark_bucket_linear)
596  limit <<= new_log2_pages;
597  new_hash >>= h->log2_nbuckets;
598  new_hash &= (1 << new_log2_pages) - 1;
599  new_v += mark_bucket_linear ? 0 : new_hash;
600 
601  for (i = 0; i < limit; i++)
602  {
603  if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
604  {
605  clib_memcpy_fast (&(new_v->kvp[i]), add_v, sizeof (*add_v));
606  goto expand_ok;
607  }
608  }
609 
610  /* Crap. Try again */
611  BV (value_free) (h, save_new_v, new_log2_pages);
612  /*
613  * If we've already doubled the size of the bucket once,
614  * fall back to linear search now.
615  */
616  if (resplit_once)
617  goto mark_linear;
618  else
619  goto try_resplit;
620 
621 expand_ok:
622  tmp_b.log2_pages = new_log2_pages;
623  tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
624  tmp_b.linear_search = mark_bucket_linear;
625  tmp_b.refcnt = h->saved_bucket.refcnt + 1;
626  ASSERT (tmp_b.refcnt > 0);
627  tmp_b.lock = 0;
629  b->as_u64 = tmp_b.as_u64;
630  /* free the old bucket */
631  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
632  BV (value_free) (h, v, h->saved_bucket.log2_pages);
633  BV (clib_bihash_alloc_unlock) (h);
634  return (0);
635 }
636 
637 int BV (clib_bihash_add_del)
638  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
639 {
640  return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
641 }
642 
643 int BV (clib_bihash_add_or_overwrite_stale)
644  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
645  int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
646 {
647  return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
648 }
649 
650 int BV (clib_bihash_search)
651  (BVT (clib_bihash) * h,
652  BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
653 {
654  u64 hash;
655  u32 bucket_index;
656  BVT (clib_bihash_value) * v;
657  BVT (clib_bihash_bucket) * b;
658  int i, limit;
659 
660  ASSERT (valuep);
661 
662  hash = BV (clib_bihash_hash) (search_key);
663 
664  bucket_index = hash & (h->nbuckets - 1);
665  b = &h->buckets[bucket_index];
666 
667  if (BV (clib_bihash_bucket_is_empty) (b))
668  return -1;
669 
670  if (PREDICT_FALSE (b->lock))
671  {
672  volatile BVT (clib_bihash_bucket) * bv = b;
673  while (bv->lock)
674  CLIB_PAUSE ();
675  }
676 
677  hash >>= h->log2_nbuckets;
678 
679  v = BV (clib_bihash_get_value) (h, b->offset);
680  limit = BIHASH_KVP_PER_PAGE;
681  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
682  if (PREDICT_FALSE (b->linear_search))
683  limit <<= b->log2_pages;
684 
685  for (i = 0; i < limit; i++)
686  {
687  if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
688  {
689  *valuep = v->kvp[i];
690  return 0;
691  }
692  }
693  return -1;
694 }
695 
696 u8 *BV (format_bihash) (u8 * s, va_list * args)
697 {
698  BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
699  int verbose = va_arg (*args, int);
700  BVT (clib_bihash_bucket) * b;
701  BVT (clib_bihash_value) * v;
702  int i, j, k;
703  u64 active_elements = 0;
704  u64 active_buckets = 0;
705  u64 linear_buckets = 0;
706  u64 used_bytes;
707 
708  s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
709 
710  for (i = 0; i < h->nbuckets; i++)
711  {
712  b = &h->buckets[i];
713  if (BV (clib_bihash_bucket_is_empty) (b))
714  {
715  if (verbose > 1)
716  s = format (s, "[%d]: empty\n", i);
717  continue;
718  }
719 
720  active_buckets++;
721 
722  if (b->linear_search)
723  linear_buckets++;
724 
725  if (verbose)
726  {
727  s = format (s, "[%d]: heap offset %lld, len %d, linear %d\n", i,
728  b->offset, (1 << b->log2_pages), b->linear_search);
729  }
730 
731  v = BV (clib_bihash_get_value) (h, b->offset);
732  for (j = 0; j < (1 << b->log2_pages); j++)
733  {
734  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
735  {
736  if (BV (clib_bihash_is_free) (&v->kvp[k]))
737  {
738  if (verbose > 1)
739  s = format (s, " %d: empty\n",
740  j * BIHASH_KVP_PER_PAGE + k);
741  continue;
742  }
743  if (verbose)
744  {
745  if (h->fmt_fn)
746  {
747  s = format (s, " %d: %U\n",
748  j * BIHASH_KVP_PER_PAGE + k,
749  h->fmt_fn, &(v->kvp[k]));
750  }
751  else
752  {
753  s = format (s, " %d: %U\n",
754  j * BIHASH_KVP_PER_PAGE + k,
755  BV (format_bihash_kvp), &(v->kvp[k]));
756  }
757  }
758  active_elements++;
759  }
760  v++;
761  }
762  }
763 
764  s = format (s, " %lld active elements %lld active buckets\n",
765  active_elements, active_buckets);
766  s = format (s, " %d free lists\n", vec_len (h->freelists));
767 
768  for (i = 0; i < vec_len (h->freelists); i++)
769  {
770  u32 nfree = 0;
771  BVT (clib_bihash_value) * free_elt;
772  u64 free_elt_as_u64 = h->freelists[i];
773 
774  while (free_elt_as_u64)
775  {
776  free_elt = BV (clib_bihash_get_value) (h, free_elt_as_u64);
777  nfree++;
778  free_elt_as_u64 = free_elt->next_free_as_u64;
779  }
780 
781  if (nfree || verbose)
782  s = format (s, " [len %d] %u free elts\n", 1 << i, nfree);
783  }
784 
785  s = format (s, " %lld linear search buckets\n", linear_buckets);
786  used_bytes = alloc_arena_next (h);
787  s = format (s,
788  " arena: base %llx, next %llx\n"
789  " used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
790  alloc_arena (h), alloc_arena_next (h),
791  used_bytes, used_bytes >> 20,
792  alloc_arena_size (h), alloc_arena_size (h) >> 20);
793  return s;
794 }
795 
797  (BVT (clib_bihash) * h, void *callback, void *arg)
798 {
799  int i, j, k;
800  BVT (clib_bihash_bucket) * b;
801  BVT (clib_bihash_value) * v;
802  void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
803 
804  for (i = 0; i < h->nbuckets; i++)
805  {
806  b = &h->buckets[i];
807  if (BV (clib_bihash_bucket_is_empty) (b))
808  continue;
809 
810  v = BV (clib_bihash_get_value) (h, b->offset);
811  for (j = 0; j < (1 << b->log2_pages); j++)
812  {
813  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
814  {
815  if (BV (clib_bihash_is_free) (&v->kvp[k]))
816  continue;
817 
818  (*fp) (&v->kvp[k], arg);
819  /*
820  * In case the callback deletes the last entry in the bucket...
821  */
822  if (BV (clib_bihash_bucket_is_empty) (b))
823  goto doublebreak;
824  }
825  v++;
826  }
827  doublebreak:
828  ;
829  }
830 }
831 
832 /** @endcond */
833 
834 /*
835  * fd.io coding-style-patch-verification: ON
836  *
837  * Local Variables:
838  * eval: (c-set-style "gnu")
839  * End:
840  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:439
#define CLIB_PAUSE()
Definition: lock.h:22
#define BIHASH_KVP_PER_PAGE
Definition: bihash_16_8.h:19
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
#define PREDICT_TRUE(x)
Definition: clib.h:112
unsigned long u64
Definition: types.h:89
#define clib_memcpy_fast(a, b, c)
Definition: string.h:81
#define F_ADD_SEALS
Definition: mem.c:40
#define NULL
Definition: clib.h:58
static int memfd_create(const char *name, unsigned int flags)
Definition: syscall.h:52
void os_out_of_memory(void)
Definition: unix-misc.c:219
for(i=1;i<=collision_buckets;i++)
int i
clib_memset(h->entries, 0, sizeof(h->entries[0])*entries)
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
unsigned char u8
Definition: types.h:56
#define MFD_ALLOW_SEALING
Definition: main.c:104
int clib_bihash_add_del(clib_bihash *h, clib_bihash_kv *add_v, int is_add)
Add or delete a (key,value) pair from a bi-hash table.
u32 dlmalloc_header_offset
offset to memory allocator offset
Definition: vec_bootstrap.h:61
static BVT(clib_bihash)
Definition: adj_nbr.c:28
unsigned int u32
Definition: types.h:88
#define F_SEAL_SHRINK
Definition: mem.c:44
static uword clib_bihash_get_offset(clib_bihash *h, void *v)
Get clib mheap offset given a pointer.
u64 memory_size
Definition: vhost_user.h:115
static vnet_classify_entry_t * split_and_rehash_linear(vnet_classify_table_t *t, vnet_classify_entry_t *old_values, u32 old_log2_pages, u32 new_log2_pages)
#define PREDICT_FALSE(x)
Definition: clib.h:111
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
u8 name[64]
Definition: memclnt.api:152
void clib_bihash_foreach_key_value_pair(clib_bihash *h, void *callback, void *arg)
Visit active (key,value) pairs in a bi-hash table.
static vnet_classify_entry_t * split_and_rehash(vnet_classify_table_t *t, vnet_classify_entry_t *old_values, u32 old_log2_pages, u32 new_log2_pages)
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:341
#define clib_warning(format, args...)
Definition: error.h:59
u32 len
Number of elements in vector (NOT its allocated length).
Definition: vec_bootstrap.h:60
static void make_working_copy(vnet_classify_table_t *t, vnet_classify_bucket_t *b)
#define ASSERT(truth)
u8 is_add
Definition: ipsec_gre.api:36
u8 log2_pages
Definition: bihash_doc.h:62
vector header structure
Definition: vec_bootstrap.h:55
template key/value backing page structure
Definition: bihash_doc.h:44
static void clib_mem_vm_free(void *addr, uword size)
Definition: mem.h:327
u8 vector_data[0]
Vector data .
Definition: vec_bootstrap.h:63
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static uword max_log2(uword x)
Definition: clib.h:191
u64 uword
Definition: types.h:112
#define clib_unix_warning(format, args...)
Definition: error.h:68
static_always_inline uword os_get_thread_index(void)
Definition: os.h:62
#define CLIB_MEMORY_BARRIER()
Definition: clib.h:115
static void * clib_bihash_get_value(clib_bihash *h, uword offset)
Get pointer to value page given its clib mheap offset.
#define vec_validate_init_empty(V, I, INIT)
Make sure vector is long enough for given index and initialize empty space (no header, unspecified alignment)
Definition: vec.h:486
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:59
static void * clib_mem_vm_alloc(uword size)
Definition: mem.h:310
static void * alloc_aligned(uword size, uword log2_align, void **ptr_to_free)
Definition: test_vec.h:191