FD.io VPP  v19.01.3-6-g70449b9b9
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;
445  BV (clib_bihash_unlock_bucket) (b);
446  return (0);
447  }
448 
449  /* WARNING: we're still looking at the live copy... */
450  limit = BIHASH_KVP_PER_PAGE;
451  v = BV (clib_bihash_get_value) (h, b->offset);
452 
453  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
454  if (b->linear_search)
455  limit <<= b->log2_pages;
456 
457  if (is_add)
458  {
459  /*
460  * Because reader threads are looking at live data,
461  * we have to be extra careful. Readers do NOT hold the
462  * bucket lock. We need to be SLOWER than a search, past the
463  * point where readers CHECK the bucket lock.
464  */
465 
466  /*
467  * For obvious (in hindsight) reasons, see if we're supposed to
468  * replace an existing key, then look for an empty slot.
469  */
470  for (i = 0; i < limit; i++)
471  {
472  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
473  {
474  CLIB_MEMORY_BARRIER (); /* Add a delay */
475  clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
476  BV (clib_bihash_unlock_bucket) (b);
477  return (0);
478  }
479  }
480  /*
481  * Look for an empty slot. If found, use it
482  */
483  for (i = 0; i < limit; i++)
484  {
485  if (BV (clib_bihash_is_free) (&(v->kvp[i])))
486  {
487  /*
488  * Copy the value first, so that if a reader manages
489  * to match the new key, the value will be right...
490  */
491  clib_memcpy_fast (&(v->kvp[i].value),
492  &add_v->value, sizeof (add_v->value));
493  CLIB_MEMORY_BARRIER (); /* Make sure the value has settled */
494  clib_memcpy_fast (&(v->kvp[i]), &add_v->key,
495  sizeof (add_v->key));
496  b->refcnt++;
497  ASSERT (b->refcnt > 0);
498  BV (clib_bihash_unlock_bucket) (b);
499  return (0);
500  }
501  }
502  /* look for stale data to overwrite */
503  if (is_stale_cb)
504  {
505  for (i = 0; i < limit; i++)
506  {
507  if (is_stale_cb (&(v->kvp[i]), arg))
508  {
510  clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
511  BV (clib_bihash_unlock_bucket) (b);
512  return (0);
513  }
514  }
515  }
516  /* Out of space in this bucket, split the bucket... */
517  }
518  else /* delete case */
519  {
520  for (i = 0; i < limit; i++)
521  {
522  /* Found the key? Kill it... */
523  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
524  {
525  clib_memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
526  /* Is the bucket empty? */
527  if (PREDICT_TRUE (b->refcnt > 1))
528  {
529  b->refcnt--;
530  BV (clib_bihash_unlock_bucket) (b);
531  return (0);
532  }
533  else /* yes, free it */
534  {
535  /* Save old bucket value, need log2_pages to free it */
536  tmp_b.as_u64 = b->as_u64;
538 
539  /* Kill and unlock the bucket */
540  b->as_u64 = 0;
541 
542  /* And free the backing storage */
543  BV (clib_bihash_alloc_lock) (h);
544  /* Note: v currently points into the middle of the bucket */
545  v = BV (clib_bihash_get_value) (h, tmp_b.offset);
546  BV (value_free) (h, v, tmp_b.log2_pages);
547  BV (clib_bihash_alloc_unlock) (h);
548  return (0);
549  }
550  }
551  }
552  /* Not found... */
553  BV (clib_bihash_unlock_bucket) (b);
554  return (-3);
555  }
556 
557  /* Move readers to a (locked) temp copy of the bucket */
558  BV (clib_bihash_alloc_lock) (h);
559  BV (make_working_copy) (h, b);
560 
561  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
562 
563  old_log2_pages = h->saved_bucket.log2_pages;
564  new_log2_pages = old_log2_pages + 1;
565  mark_bucket_linear = 0;
566 
567  working_copy = h->working_copies[thread_index];
568  resplit_once = 0;
569 
570  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
571  new_log2_pages);
572  if (new_v == 0)
573  {
574  try_resplit:
575  resplit_once = 1;
576  new_log2_pages++;
577  /* Try re-splitting. If that fails, fall back to linear search */
578  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
579  new_log2_pages);
580  if (new_v == 0)
581  {
582  mark_linear:
583  new_log2_pages--;
584  /* pinned collisions, use linear search */
585  new_v =
586  BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
587  new_log2_pages);
588  mark_bucket_linear = 1;
589  }
590  }
591 
592  /* Try to add the new entry */
593  save_new_v = new_v;
594  new_hash = BV (clib_bihash_hash) (add_v);
595  limit = BIHASH_KVP_PER_PAGE;
596  if (mark_bucket_linear)
597  limit <<= new_log2_pages;
598  new_hash >>= h->log2_nbuckets;
599  new_hash &= (1 << new_log2_pages) - 1;
600  new_v += mark_bucket_linear ? 0 : new_hash;
601 
602  for (i = 0; i < limit; i++)
603  {
604  if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
605  {
606  clib_memcpy_fast (&(new_v->kvp[i]), add_v, sizeof (*add_v));
607  goto expand_ok;
608  }
609  }
610 
611  /* Crap. Try again */
612  BV (value_free) (h, save_new_v, new_log2_pages);
613  /*
614  * If we've already doubled the size of the bucket once,
615  * fall back to linear search now.
616  */
617  if (resplit_once)
618  goto mark_linear;
619  else
620  goto try_resplit;
621 
622 expand_ok:
623  tmp_b.log2_pages = new_log2_pages;
624  tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
625  tmp_b.linear_search = mark_bucket_linear;
626  tmp_b.refcnt = h->saved_bucket.refcnt + 1;
627  ASSERT (tmp_b.refcnt > 0);
628  tmp_b.lock = 0;
630  b->as_u64 = tmp_b.as_u64;
631  /* free the old bucket */
632  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
633  BV (value_free) (h, v, h->saved_bucket.log2_pages);
634  BV (clib_bihash_alloc_unlock) (h);
635  return (0);
636 }
637 
638 int BV (clib_bihash_add_del)
639  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
640 {
641  return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
642 }
643 
644 int BV (clib_bihash_add_or_overwrite_stale)
645  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
646  int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
647 {
648  return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
649 }
650 
651 int BV (clib_bihash_search)
652  (BVT (clib_bihash) * h,
653  BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
654 {
655  u64 hash;
656  u32 bucket_index;
657  BVT (clib_bihash_value) * v;
658  BVT (clib_bihash_bucket) * b;
659  int i, limit;
660 
661  ASSERT (valuep);
662 
663  hash = BV (clib_bihash_hash) (search_key);
664 
665  bucket_index = hash & (h->nbuckets - 1);
666  b = &h->buckets[bucket_index];
667 
668  if (BV (clib_bihash_bucket_is_empty) (b))
669  return -1;
670 
671  if (PREDICT_FALSE (b->lock))
672  {
673  volatile BVT (clib_bihash_bucket) * bv = b;
674  while (bv->lock)
675  CLIB_PAUSE ();
676  }
677 
678  hash >>= h->log2_nbuckets;
679 
680  v = BV (clib_bihash_get_value) (h, b->offset);
681  limit = BIHASH_KVP_PER_PAGE;
682  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
683  if (PREDICT_FALSE (b->linear_search))
684  limit <<= b->log2_pages;
685 
686  for (i = 0; i < limit; i++)
687  {
688  if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
689  {
690  *valuep = v->kvp[i];
691  return 0;
692  }
693  }
694  return -1;
695 }
696 
697 u8 *BV (format_bihash) (u8 * s, va_list * args)
698 {
699  BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
700  int verbose = va_arg (*args, int);
701  BVT (clib_bihash_bucket) * b;
702  BVT (clib_bihash_value) * v;
703  int i, j, k;
704  u64 active_elements = 0;
705  u64 active_buckets = 0;
706  u64 linear_buckets = 0;
707  u64 used_bytes;
708 
709  s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
710 
711  for (i = 0; i < h->nbuckets; i++)
712  {
713  b = &h->buckets[i];
714  if (BV (clib_bihash_bucket_is_empty) (b))
715  {
716  if (verbose > 1)
717  s = format (s, "[%d]: empty\n", i);
718  continue;
719  }
720 
721  active_buckets++;
722 
723  if (b->linear_search)
724  linear_buckets++;
725 
726  if (verbose)
727  {
728  s = format (s, "[%d]: heap offset %lld, len %d, linear %d\n", i,
729  b->offset, (1 << b->log2_pages), b->linear_search);
730  }
731 
732  v = BV (clib_bihash_get_value) (h, b->offset);
733  for (j = 0; j < (1 << b->log2_pages); j++)
734  {
735  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
736  {
737  if (BV (clib_bihash_is_free) (&v->kvp[k]))
738  {
739  if (verbose > 1)
740  s = format (s, " %d: empty\n",
741  j * BIHASH_KVP_PER_PAGE + k);
742  continue;
743  }
744  if (verbose)
745  {
746  if (h->fmt_fn)
747  {
748  s = format (s, " %d: %U\n",
749  j * BIHASH_KVP_PER_PAGE + k,
750  h->fmt_fn, &(v->kvp[k]));
751  }
752  else
753  {
754  s = format (s, " %d: %U\n",
755  j * BIHASH_KVP_PER_PAGE + k,
756  BV (format_bihash_kvp), &(v->kvp[k]));
757  }
758  }
759  active_elements++;
760  }
761  v++;
762  }
763  }
764 
765  s = format (s, " %lld active elements %lld active buckets\n",
766  active_elements, active_buckets);
767  s = format (s, " %d free lists\n", vec_len (h->freelists));
768 
769  for (i = 0; i < vec_len (h->freelists); i++)
770  {
771  u32 nfree = 0;
772  BVT (clib_bihash_value) * free_elt;
773  u64 free_elt_as_u64 = h->freelists[i];
774 
775  while (free_elt_as_u64)
776  {
777  free_elt = BV (clib_bihash_get_value) (h, free_elt_as_u64);
778  nfree++;
779  free_elt_as_u64 = free_elt->next_free_as_u64;
780  }
781 
782  if (nfree || verbose)
783  s = format (s, " [len %d] %u free elts\n", 1 << i, nfree);
784  }
785 
786  s = format (s, " %lld linear search buckets\n", linear_buckets);
787  used_bytes = alloc_arena_next (h);
788  s = format (s,
789  " arena: base %llx, next %llx\n"
790  " used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
791  alloc_arena (h), alloc_arena_next (h),
792  used_bytes, used_bytes >> 20,
793  alloc_arena_size (h), alloc_arena_size (h) >> 20);
794  return s;
795 }
796 
798  (BVT (clib_bihash) * h, void *callback, void *arg)
799 {
800  int i, j, k;
801  BVT (clib_bihash_bucket) * b;
802  BVT (clib_bihash_value) * v;
803  void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
804 
805  for (i = 0; i < h->nbuckets; i++)
806  {
807  b = &h->buckets[i];
808  if (BV (clib_bihash_bucket_is_empty) (b))
809  continue;
810 
811  v = BV (clib_bihash_get_value) (h, b->offset);
812  for (j = 0; j < (1 << b->log2_pages); j++)
813  {
814  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
815  {
816  if (BV (clib_bihash_is_free) (&v->kvp[k]))
817  continue;
818 
819  (*fp) (&v->kvp[k], arg);
820  /*
821  * In case the callback deletes the last entry in the bucket...
822  */
823  if (BV (clib_bihash_bucket_is_empty) (b))
824  goto doublebreak;
825  }
826  v++;
827  }
828  doublebreak:
829  ;
830  }
831 }
832 
833 /** @endcond */
834 
835 /*
836  * fd.io coding-style-patch-verification: ON
837  *
838  * Local Variables:
839  * eval: (c-set-style "gnu")
840  * End:
841  */
#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
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
static int memfd_create(const char *name, unsigned int flags)
Definition: syscall.h:50
void os_out_of_memory(void)
Definition: unix-misc.c:219
for(i=1;i<=collision_buckets;i++)
int i
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
unsigned char u8
Definition: types.h:56
u8 *() format_function_t(u8 *s, va_list *args)
Definition: format.h:48
#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 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:488
#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