FD.io VPP  v21.06-3-gbb25fbf28
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 #ifndef MAP_HUGE_SHIFT
19 #define MAP_HUGE_SHIFT 26
20 #endif
21 
22 #ifndef BIIHASH_MIN_ALLOC_LOG2_PAGES
23 #define BIIHASH_MIN_ALLOC_LOG2_PAGES 10
24 #endif
25 
26 #ifndef BIHASH_USE_HEAP
27 #define BIHASH_USE_HEAP 1
28 #endif
29 
30 static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes)
31 {
32  uword rv;
33 
34  /* Round to an even number of cache lines */
35  nbytes = round_pow2 (nbytes, CLIB_CACHE_LINE_BYTES);
36 
37  if (BIHASH_USE_HEAP)
38  {
39  void *rv, *oldheap;
40  uword page_sz = sizeof (BVT (clib_bihash_value));
41  uword chunk_sz = round_pow2 (page_sz << BIIHASH_MIN_ALLOC_LOG2_PAGES,
43 
44  BVT (clib_bihash_alloc_chunk) * chunk = h->chunks;
45 
46  /* if there is enough space in the currenrt chunk */
47  if (chunk && chunk->bytes_left >= nbytes)
48  {
49  rv = chunk->next_alloc;
50  chunk->bytes_left -= nbytes;
51  chunk->next_alloc += nbytes;
52  return rv;
53  }
54 
55  /* requested allocation is bigger than chunk size */
56  if (nbytes >= chunk_sz)
57  {
58  oldheap = clib_mem_set_heap (h->heap);
59  chunk = clib_mem_alloc_aligned (nbytes + sizeof (*chunk),
61  clib_mem_set_heap (oldheap);
62  clib_memset_u8 (chunk, 0, sizeof (*chunk));
63  chunk->size = nbytes;
64  rv = (u8 *) (chunk + 1);
65  if (h->chunks)
66  {
67  /* take 2nd place in the list */
68  chunk->next = h->chunks->next;
69  chunk->prev = h->chunks;
70  h->chunks->next = chunk;
71  if (chunk->next)
72  chunk->next->prev = chunk;
73  }
74  else
75  h->chunks = chunk;
76 
77  return rv;
78  }
79 
80  oldheap = clib_mem_set_heap (h->heap);
81  chunk = clib_mem_alloc_aligned (chunk_sz + sizeof (*chunk),
83  clib_mem_set_heap (oldheap);
84  chunk->size = chunk_sz;
85  chunk->bytes_left = chunk_sz;
86  chunk->next_alloc = (u8 *) (chunk + 1);
87  chunk->next = h->chunks;
88  chunk->prev = 0;
89  if (chunk->next)
90  chunk->next->prev = chunk;
91  h->chunks = chunk;
92  rv = chunk->next_alloc;
93  chunk->bytes_left -= nbytes;
94  chunk->next_alloc += nbytes;
95  return rv;
96  }
97 
98  rv = alloc_arena_next (h);
99  alloc_arena_next (h) += nbytes;
100 
101  if (alloc_arena_next (h) > alloc_arena_size (h))
102  os_out_of_memory ();
103 
104  if (alloc_arena_next (h) > alloc_arena_mapped (h))
105  {
106  void *base, *rv;
107  uword alloc = alloc_arena_next (h) - alloc_arena_mapped (h);
108  int mmap_flags = MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS;
109  int mmap_flags_huge = (mmap_flags | MAP_HUGETLB | MAP_LOCKED |
110  BIHASH_LOG2_HUGEPAGE_SIZE << MAP_HUGE_SHIFT);
111 
112  /* new allocation is 25% of existing one */
113  if (alloc_arena_mapped (h) >> 2 > alloc)
114  alloc = alloc_arena_mapped (h) >> 2;
115 
116  /* round allocation to page size */
117  alloc = round_pow2 (alloc, 1 << BIHASH_LOG2_HUGEPAGE_SIZE);
118 
119  base = (void *) (uword) (alloc_arena (h) + alloc_arena_mapped (h));
120 
121  rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags_huge, -1, 0);
122 
123  /* fallback - maybe we are still able to allocate normal pages */
124  if (rv == MAP_FAILED || mlock (base, alloc) != 0)
125  rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags, -1, 0);
126 
127  if (rv == MAP_FAILED)
128  os_out_of_memory ();
129 
130  alloc_arena_mapped (h) += alloc;
131  }
132 
133  return (void *) (uword) (rv + alloc_arena (h));
134 }
135 
136 static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h)
137 {
138  uword bucket_size;
139 
140  if (BIHASH_USE_HEAP)
141  {
142  h->heap = clib_mem_get_heap ();
143  h->chunks = 0;
144  alloc_arena (h) = (uword) clib_mem_get_heap_base (h->heap);
145  }
146  else
147  {
148  alloc_arena (h) = clib_mem_vm_reserve (0, h->memory_size,
149  BIHASH_LOG2_HUGEPAGE_SIZE);
150  if (alloc_arena (h) == ~0)
151  os_out_of_memory ();
152  alloc_arena_next (h) = 0;
153  alloc_arena_size (h) = h->memory_size;
154  alloc_arena_mapped (h) = 0;
155  }
156 
157  bucket_size = h->nbuckets * sizeof (h->buckets[0]);
158 
160  bucket_size +=
161  h->nbuckets * BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv));
162 
163  h->buckets = BV (alloc_aligned) (h, bucket_size);
164  clib_memset_u8 (h->buckets, 0, bucket_size);
165 
167  {
168  int i;
169  BVT (clib_bihash_bucket) * b;
170 
171  b = h->buckets;
172 
173  for (i = 0; i < h->nbuckets; i++)
174  {
175  b->offset = BV (clib_bihash_get_offset) (h, (void *) (b + 1));
176  b->refcnt = 1;
177  /* Mark all elements free */
178  clib_memset_u8 ((b + 1), 0xff, BIHASH_KVP_PER_PAGE *
179  sizeof (BVT (clib_bihash_kv)));
180 
181  /* Compute next bucket start address */
182  b = (void *) (((uword) b) + sizeof (*b) +
184  sizeof (BVT (clib_bihash_kv))));
185  }
186  }
188  h->instantiated = 1;
189 }
190 
191 void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a)
192 {
193  int i;
194  void *oldheap;
195  BVT (clib_bihash) * h = a->h;
196 
197  a->nbuckets = 1 << (max_log2 (a->nbuckets));
198 
199  h->name = (u8 *) a->name;
200  h->nbuckets = a->nbuckets;
201  h->log2_nbuckets = max_log2 (a->nbuckets);
202  h->memory_size = BIHASH_USE_HEAP ? 0 : a->memory_size;
203  h->instantiated = 0;
204  h->fmt_fn = BV (format_bihash);
205  h->kvp_fmt_fn = a->kvp_fmt_fn;
206 
207  alloc_arena (h) = 0;
208 
209  /*
210  * Make sure the requested size is rational. The max table
211  * size without playing the alignment card is 64 Gbytes.
212  * If someone starts complaining that's not enough, we can shift
213  * the offset by CLIB_LOG2_CACHE_LINE_BYTES...
214  */
215  if (BIHASH_USE_HEAP)
216  ASSERT (h->memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
217 
218  /* Add this hash table to the list */
219  if (a->dont_add_to_all_bihash_list == 0)
220  {
221  for (i = 0; i < vec_len (clib_all_bihashes); i++)
222  if (clib_all_bihashes[i] == h)
223  goto do_lock;
224  oldheap = clib_all_bihash_set_heap ();
225  vec_add1 (clib_all_bihashes, (void *) h);
226  clib_mem_set_heap (oldheap);
227  }
228 
229 do_lock:
230  if (h->alloc_lock)
231  clib_mem_free ((void *) h->alloc_lock);
232 
233  /*
234  * Set up the lock now, so we can use it to make the first add
235  * thread-safe
236  */
239  h->alloc_lock[0] = 0;
240 
241 #if BIHASH_LAZY_INSTANTIATE
242  if (a->instantiate_immediately)
243 #endif
244  BV (clib_bihash_instantiate) (h);
245 }
246 
247 void BV (clib_bihash_init)
248  (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
249 {
250  BVT (clib_bihash_init2_args) _a, *a = &_a;
251 
252  memset (a, 0, sizeof (*a));
253 
254  a->h = h;
255  a->name = name;
256  a->nbuckets = nbuckets;
257  a->memory_size = memory_size;
258 
259  BV (clib_bihash_init2) (a);
260 }
261 
262 #if BIHASH_32_64_SVM
263 #if !defined (MFD_ALLOW_SEALING)
264 #define MFD_ALLOW_SEALING 0x0002U
265 #endif
266 
267 void BV (clib_bihash_initiator_init_svm)
268  (BVT (clib_bihash) * h, char *name, u32 nbuckets, u64 memory_size)
269 {
270  uword bucket_size;
271  u8 *mmap_addr;
272  vec_header_t *freelist_vh;
273  int fd;
274 
275  ASSERT (BIHASH_USE_HEAP == 0);
276 
277  ASSERT (memory_size < (1ULL << 32));
278  /* Set up for memfd sharing */
280  {
281  clib_unix_warning ("memfd_create");
282  return;
283  }
284 
285  if (ftruncate (fd, memory_size) < 0)
286  {
287  clib_unix_warning ("ftruncate");
288  return;
289  }
290 
291  /* Not mission-critical, complain and continue */
292  if ((fcntl (fd, F_ADD_SEALS, F_SEAL_SHRINK)) == -1)
293  clib_unix_warning ("fcntl (F_ADD_SEALS)");
294 
295  mmap_addr = mmap (0, memory_size,
296  PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ );
297 
298  if (mmap_addr == MAP_FAILED)
299  {
300  clib_unix_warning ("mmap failed");
301  ASSERT (0);
302  }
303 
304  h->sh = (void *) mmap_addr;
305  h->memfd = fd;
306  nbuckets = 1 << (max_log2 (nbuckets));
307 
308  h->name = (u8 *) name;
309  h->sh->nbuckets = h->nbuckets = nbuckets;
310  h->log2_nbuckets = max_log2 (nbuckets);
311 
312  alloc_arena (h) = (u64) (uword) mmap_addr;
313  alloc_arena_next (h) = CLIB_CACHE_LINE_BYTES;
314  alloc_arena_size (h) = memory_size;
315 
316  bucket_size = nbuckets * sizeof (h->buckets[0]);
317  h->buckets = BV (alloc_aligned) (h, bucket_size);
318  clib_memset_u8 (h->buckets, 0, bucket_size);
319  h->sh->buckets_as_u64 = (u64) BV (clib_bihash_get_offset) (h, h->buckets);
320 
321  h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES);
322  h->alloc_lock[0] = 0;
323 
324  h->sh->alloc_lock_as_u64 =
325  (u64) BV (clib_bihash_get_offset) (h, (void *) h->alloc_lock);
326  freelist_vh =
327  BV (alloc_aligned) (h,
328  sizeof (vec_header_t) +
329  BIHASH_FREELIST_LENGTH * sizeof (u64));
330  freelist_vh->len = BIHASH_FREELIST_LENGTH;
331  h->sh->freelists_as_u64 =
332  (u64) BV (clib_bihash_get_offset) (h, freelist_vh->vector_data);
333  h->freelists = (void *) (freelist_vh->vector_data);
334 
335  h->fmt_fn = BV (format_bihash);
336  h->kvp_fmt_fn = NULL;
337  h->instantiated = 1;
338 }
339 
340 void BV (clib_bihash_responder_init_svm)
341  (BVT (clib_bihash) * h, char *name, int fd)
342 {
343  u8 *mmap_addr;
345  BVT (clib_bihash_shared_header) * sh;
346 
347  ASSERT (BIHASH_USE_HEAP == 0);
348 
349  /* Trial mapping, to learn the segment size */
350  mmap_addr = mmap (0, 4096, PROT_READ, MAP_SHARED, fd, 0 /* offset */ );
351  if (mmap_addr == MAP_FAILED)
352  {
353  clib_unix_warning ("trial mmap failed");
354  ASSERT (0);
355  }
356 
357  sh = (BVT (clib_bihash_shared_header) *) mmap_addr;
358 
359  memory_size = sh->alloc_arena_size;
360 
361  munmap (mmap_addr, 4096);
362 
363  /* Actual mapping, at the required size */
364  mmap_addr = mmap (0, memory_size,
365  PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ );
366 
367  if (mmap_addr == MAP_FAILED)
368  {
369  clib_unix_warning ("mmap failed");
370  ASSERT (0);
371  }
372 
373  (void) close (fd);
374 
375  h->sh = (void *) mmap_addr;
376  alloc_arena (h) = (u64) (uword) mmap_addr;
377  h->memfd = -1;
378 
379  h->name = (u8 *) name;
380  h->buckets = BV (clib_bihash_get_value) (h, h->sh->buckets_as_u64);
381  h->nbuckets = h->sh->nbuckets;
382  h->log2_nbuckets = max_log2 (h->nbuckets);
383 
384  h->alloc_lock = BV (clib_bihash_get_value) (h, h->sh->alloc_lock_as_u64);
385  h->freelists = BV (clib_bihash_get_value) (h, h->sh->freelists_as_u64);
386  h->fmt_fn = BV (format_bihash);
387  h->kvp_fmt_fn = NULL;
388 }
389 #endif /* BIHASH_32_64_SVM */
390 
391 void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
392  format_function_t * kvp_fmt_fn)
393 {
394  h->kvp_fmt_fn = kvp_fmt_fn;
395 }
396 
397 int BV (clib_bihash_is_initialised) (const BVT (clib_bihash) * h)
398 {
399  return (h->instantiated != 0);
400 }
401 
402 void BV (clib_bihash_free) (BVT (clib_bihash) * h)
403 {
404  int i;
405 
406  if (PREDICT_FALSE (h->instantiated == 0))
407  goto never_initialized;
408 
409  h->instantiated = 0;
410 
411  if (BIHASH_USE_HEAP)
412  {
413  BVT (clib_bihash_alloc_chunk) * next, *chunk;
414  void *oldheap = clib_mem_set_heap (h->heap);
415 
416  chunk = h->chunks;
417  while (chunk)
418  {
419  next = chunk->next;
420  clib_mem_free (chunk);
421  chunk = next;
422  }
423  clib_mem_set_heap (oldheap);
424  }
425 
426  vec_free (h->working_copies);
427  vec_free (h->working_copy_lengths);
428 #if BIHASH_32_64_SVM == 0
429  vec_free (h->freelists);
430 #else
431  if (h->memfd > 0)
432  (void) close (h->memfd);
433 #endif
434  if (BIHASH_USE_HEAP == 0)
435  clib_mem_vm_free ((void *) (uword) (alloc_arena (h)),
436  alloc_arena_size (h));
437 never_initialized:
438  clib_memset_u8 (h, 0, sizeof (*h));
439  for (i = 0; i < vec_len (clib_all_bihashes); i++)
440  {
441  if ((void *) h == clib_all_bihashes[i])
442  {
444  return;
445  }
446  }
447  clib_warning ("Couldn't find hash table %llx on clib_all_bihashes...",
448  (u64) (uword) h);
449 }
450 
451 static
453 BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
454 {
455  BVT (clib_bihash_value) * rv = 0;
456 
457  ASSERT (h->alloc_lock[0]);
458 
459 #if BIHASH_32_64_SVM
460  ASSERT (log2_pages < vec_len (h->freelists));
461 #endif
462 
463  if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
464  {
465  vec_validate_init_empty (h->freelists, log2_pages, 0);
466  rv = BV (alloc_aligned) (h, (sizeof (*rv) * (1 << log2_pages)));
467  goto initialize;
468  }
469  rv = BV (clib_bihash_get_value) (h, (uword) h->freelists[log2_pages]);
470  h->freelists[log2_pages] = rv->next_free_as_u64;
471 
472 initialize:
473  ASSERT (rv);
474  /*
475  * Latest gcc complains that the length arg is zero
476  * if we replace (1<<log2_pages) with vec_len(rv).
477  * No clue.
478  */
479  clib_memset_u8 (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
480  return rv;
481 }
482 
483 static void
484 BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
485  u32 log2_pages)
486 {
487  ASSERT (h->alloc_lock[0]);
488 
489  ASSERT (vec_len (h->freelists) > log2_pages);
490 
491  if (BIHASH_USE_HEAP && log2_pages >= BIIHASH_MIN_ALLOC_LOG2_PAGES)
492  {
493  /* allocations bigger or equal to chunk size always contain single
494  * alloc and they can be given back to heap */
495  void *oldheap;
496  BVT (clib_bihash_alloc_chunk) * c;
497  c = (BVT (clib_bihash_alloc_chunk) *) v - 1;
498 
499  if (c->prev)
500  c->prev->next = c->next;
501  else
502  h->chunks = c->next;
503 
504  if (c->next)
505  c->next->prev = c->prev;
506 
507  oldheap = clib_mem_set_heap (h->heap);
508  clib_mem_free (c);
509  clib_mem_set_heap (oldheap);
510  return;
511  }
512 
513  if (CLIB_DEBUG > 0)
514  clib_memset_u8 (v, 0xFE, sizeof (*v) * (1 << log2_pages));
515 
516  v->next_free_as_u64 = (u64) h->freelists[log2_pages];
517  h->freelists[log2_pages] = (u64) BV (clib_bihash_get_offset) (h, v);
518 }
519 
520 static inline void
521 BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
522 {
523  BVT (clib_bihash_value) * v;
524  BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8)));
525  BVT (clib_bihash_value) * working_copy;
527  int log2_working_copy_length;
528 
529  ASSERT (h->alloc_lock[0]);
530 
531  if (thread_index >= vec_len (h->working_copies))
532  {
533  vec_validate (h->working_copies, thread_index);
534  vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0);
535  }
536 
537  /*
538  * working_copies are per-cpu so that near-simultaneous
539  * updates from multiple threads will not result in sporadic, spurious
540  * lookup failures.
541  */
542  working_copy = h->working_copies[thread_index];
543  log2_working_copy_length = h->working_copy_lengths[thread_index];
544 
545  h->saved_bucket.as_u64 = b->as_u64;
546 
547  if (b->log2_pages > log2_working_copy_length)
548  {
549  /*
550  * It's not worth the bookkeeping to free working copies
551  * if (working_copy)
552  * clib_mem_free (working_copy);
553  */
554  working_copy = BV (alloc_aligned)
555  (h, sizeof (working_copy[0]) * (1 << b->log2_pages));
556  h->working_copy_lengths[thread_index] = b->log2_pages;
557  h->working_copies[thread_index] = working_copy;
558 
559  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_working_copy_lost,
560  1ULL << b->log2_pages);
561  }
562 
563  v = BV (clib_bihash_get_value) (h, b->offset);
564 
565  clib_memcpy_fast (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
566  working_bucket.as_u64 = b->as_u64;
567  working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
569  b->as_u64 = working_bucket.as_u64;
570  h->working_copies[thread_index] = working_copy;
571 }
572 
573 static
575 BV (split_and_rehash)
576  (BVT (clib_bihash) * h,
577  BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
578  u32 new_log2_pages)
579 {
580  BVT (clib_bihash_value) * new_values, *new_v;
581  int i, j, length_in_kvs;
582 
583  ASSERT (h->alloc_lock[0]);
584 
585  new_values = BV (value_alloc) (h, new_log2_pages);
586  length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
587 
588  for (i = 0; i < length_in_kvs; i++)
589  {
590  u64 new_hash;
591 
592  /* Entry not in use? Forget it */
593  if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
594  continue;
595 
596  /* rehash the item onto its new home-page */
597  new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
598  new_hash = extract_bits (new_hash, h->log2_nbuckets, new_log2_pages);
599  new_v = &new_values[new_hash];
600 
601  /* Across the new home-page */
602  for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
603  {
604  /* Empty slot */
605  if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
606  {
607  clib_memcpy_fast (&(new_v->kvp[j]), &(old_values->kvp[i]),
608  sizeof (new_v->kvp[j]));
609  goto doublebreak;
610  }
611  }
612  /* Crap. Tell caller to try again */
613  BV (value_free) (h, new_values, new_log2_pages);
614  return 0;
615  doublebreak:;
616  }
617 
618  return new_values;
619 }
620 
621 static
624  (BVT (clib_bihash) * h,
625  BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
626  u32 new_log2_pages)
627 {
628  BVT (clib_bihash_value) * new_values;
629  int i, j, new_length, old_length;
630 
631  ASSERT (h->alloc_lock[0]);
632 
633  new_values = BV (value_alloc) (h, new_log2_pages);
634  new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
635  old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
636 
637  j = 0;
638  /* Across the old value array */
639  for (i = 0; i < old_length; i++)
640  {
641  /* Find a free slot in the new linear scan bucket */
642  for (; j < new_length; j++)
643  {
644  /* Old value not in use? Forget it. */
645  if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
646  goto doublebreak;
647 
648  /* New value should never be in use */
649  if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
650  {
651  /* Copy the old value and move along */
652  clib_memcpy_fast (&(new_values->kvp[j]), &(old_values->kvp[i]),
653  sizeof (new_values->kvp[j]));
654  j++;
655  goto doublebreak;
656  }
657  }
658  /* This should never happen... */
659  clib_warning ("BUG: linear rehash failed!");
660  BV (value_free) (h, new_values, new_log2_pages);
661  return 0;
662 
663  doublebreak:;
664  }
665  return new_values;
666 }
667 
668 static_always_inline int BV (clib_bihash_add_del_inline_with_hash)
669  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, u64 hash, int is_add,
670  int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
671 {
672  BVT (clib_bihash_bucket) * b, tmp_b;
673  BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
674  int i, limit;
675  u64 new_hash;
676  u32 new_log2_pages, old_log2_pages;
678  int mark_bucket_linear;
679  int resplit_once;
680 
681  /* *INDENT-OFF* */
682  static const BVT (clib_bihash_bucket) mask = {
683  .linear_search = 1,
684  .log2_pages = -1
685  };
686  /* *INDENT-ON* */
687 
688 #if BIHASH_LAZY_INSTANTIATE
689  /*
690  * Create the table (is_add=1,2), or flunk the request now (is_add=0)
691  * Use the alloc_lock to protect the instantiate operation.
692  */
693  if (PREDICT_FALSE (h->instantiated == 0))
694  {
695  if (is_add == 0)
696  return (-1);
697 
698  BV (clib_bihash_alloc_lock) (h);
699  if (h->instantiated == 0)
700  BV (clib_bihash_instantiate) (h);
701  BV (clib_bihash_alloc_unlock) (h);
702  }
703 #else
704  /* Debug image: make sure the table has been instantiated */
705  ASSERT (h->instantiated != 0);
706 #endif
707 
708  b = BV (clib_bihash_get_bucket) (h, hash);
709 
710  BV (clib_bihash_lock_bucket) (b);
711 
712  /* First elt in the bucket? */
713  if (BIHASH_KVP_AT_BUCKET_LEVEL == 0 && BV (clib_bihash_bucket_is_empty) (b))
714  {
715  if (is_add == 0)
716  {
717  BV (clib_bihash_unlock_bucket) (b);
718  return (-1);
719  }
720 
721  BV (clib_bihash_alloc_lock) (h);
722  v = BV (value_alloc) (h, 0);
723  BV (clib_bihash_alloc_unlock) (h);
724 
725  *v->kvp = *add_v;
726  tmp_b.as_u64 = 0; /* clears bucket lock */
727  tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
728  tmp_b.refcnt = 1;
730 
731  b->as_u64 = tmp_b.as_u64; /* unlocks the bucket */
732  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_alloc_add, 1);
733 
734  return (0);
735  }
736 
737  /* WARNING: we're still looking at the live copy... */
738  limit = BIHASH_KVP_PER_PAGE;
739  v = BV (clib_bihash_get_value) (h, b->offset);
740 
741  if (PREDICT_FALSE (b->as_u64 & mask.as_u64))
742  {
743  if (PREDICT_FALSE (b->linear_search))
744  limit <<= b->log2_pages;
745  else
746  v += extract_bits (hash, h->log2_nbuckets, b->log2_pages);
747  }
748 
749  if (is_add)
750  {
751  /*
752  * Because reader threads are looking at live data,
753  * we have to be extra careful. Readers do NOT hold the
754  * bucket lock. We need to be SLOWER than a search, past the
755  * point where readers CHECK the bucket lock.
756  */
757 
758  /*
759  * For obvious (in hindsight) reasons, see if we're supposed to
760  * replace an existing key, then look for an empty slot.
761  */
762  for (i = 0; i < limit; i++)
763  {
764  if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
765  {
766  /* Add but do not overwrite? */
767  if (is_add == 2)
768  {
769  BV (clib_bihash_unlock_bucket) (b);
770  return (-2);
771  }
772 
773  clib_memcpy_fast (&(v->kvp[i].value),
774  &add_v->value, sizeof (add_v->value));
775  BV (clib_bihash_unlock_bucket) (b);
776  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
777  return (0);
778  }
779  }
780  /*
781  * Look for an empty slot. If found, use it
782  */
783  for (i = 0; i < limit; i++)
784  {
785  if (BV (clib_bihash_is_free) (&(v->kvp[i])))
786  {
787  /*
788  * Copy the value first, so that if a reader manages
789  * to match the new key, the value will be right...
790  */
791  clib_memcpy_fast (&(v->kvp[i].value),
792  &add_v->value, sizeof (add_v->value));
793  CLIB_MEMORY_STORE_BARRIER (); /* Make sure the value has settled */
794  clib_memcpy_fast (&(v->kvp[i]), &add_v->key,
795  sizeof (add_v->key));
796  b->refcnt++;
797  ASSERT (b->refcnt > 0);
798  BV (clib_bihash_unlock_bucket) (b);
799  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_add, 1);
800  return (0);
801  }
802  }
803  /* look for stale data to overwrite */
804  if (is_stale_cb)
805  {
806  for (i = 0; i < limit; i++)
807  {
808  if (is_stale_cb (&(v->kvp[i]), arg))
809  {
810  clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
812  BV (clib_bihash_unlock_bucket) (b);
813  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
814  return (0);
815  }
816  }
817  }
818  /* Out of space in this bucket, split the bucket... */
819  }
820  else /* delete case */
821  {
822  for (i = 0; i < limit; i++)
823  {
824  /* Found the key? Kill it... */
825  if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
826  {
827  clib_memset_u8 (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
828  /* Is the bucket empty? */
829  if (PREDICT_TRUE (b->refcnt > 1))
830  {
831  b->refcnt--;
832  /* Switch back to the bucket-level kvp array? */
833  if (BIHASH_KVP_AT_BUCKET_LEVEL && b->refcnt == 1
834  && b->log2_pages > 0)
835  {
836  tmp_b.as_u64 = b->as_u64;
837  b->offset = BV (clib_bihash_get_offset)
838  (h, (void *) (b + 1));
839  b->linear_search = 0;
840  b->log2_pages = 0;
841  /* Clean up the bucket-level kvp array */
842  clib_memset_u8 ((b + 1), 0xff, BIHASH_KVP_PER_PAGE *
843  sizeof (BVT (clib_bihash_kv)));
845  BV (clib_bihash_unlock_bucket) (b);
846  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
847  goto free_backing_store;
848  }
849 
851  BV (clib_bihash_unlock_bucket) (b);
852  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
853  return (0);
854  }
855  else /* yes, free it */
856  {
857  /* Save old bucket value, need log2_pages to free it */
858  tmp_b.as_u64 = b->as_u64;
859 
860  /* Kill and unlock the bucket */
861  b->as_u64 = 0;
862 
863  free_backing_store:
864  /* And free the backing storage */
865  BV (clib_bihash_alloc_lock) (h);
866  /* Note: v currently points into the middle of the bucket */
867  v = BV (clib_bihash_get_value) (h, tmp_b.offset);
868  BV (value_free) (h, v, tmp_b.log2_pages);
869  BV (clib_bihash_alloc_unlock) (h);
870  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del_free,
871  1);
872  return (0);
873  }
874  }
875  }
876  /* Not found... */
877  BV (clib_bihash_unlock_bucket) (b);
878  return (-3);
879  }
880 
881  /* Move readers to a (locked) temp copy of the bucket */
882  BV (clib_bihash_alloc_lock) (h);
883  BV (make_working_copy) (h, b);
884 
885  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
886 
887  old_log2_pages = h->saved_bucket.log2_pages;
888  new_log2_pages = old_log2_pages + 1;
889  mark_bucket_linear = 0;
890  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_split_add, 1);
891  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, old_log2_pages);
892 
893  working_copy = h->working_copies[thread_index];
894  resplit_once = 0;
895  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, 1);
896 
897  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
898  new_log2_pages);
899  if (new_v == 0)
900  {
901  try_resplit:
902  resplit_once = 1;
903  new_log2_pages++;
904  /* Try re-splitting. If that fails, fall back to linear search */
905  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
906  new_log2_pages);
907  if (new_v == 0)
908  {
909  mark_linear:
910  new_log2_pages--;
911  /* pinned collisions, use linear search */
912  new_v =
913  BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
914  new_log2_pages);
915  mark_bucket_linear = 1;
916  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_linear, 1);
917  }
918  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_resplit, 1);
919  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits,
920  old_log2_pages + 1);
921  }
922 
923  /* Try to add the new entry */
924  save_new_v = new_v;
925  new_hash = BV (clib_bihash_hash) (add_v);
926  limit = BIHASH_KVP_PER_PAGE;
927  if (mark_bucket_linear)
928  limit <<= new_log2_pages;
929  else
930  new_v += extract_bits (new_hash, h->log2_nbuckets, new_log2_pages);
931 
932  for (i = 0; i < limit; i++)
933  {
934  if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
935  {
936  clib_memcpy_fast (&(new_v->kvp[i]), add_v, sizeof (*add_v));
937  goto expand_ok;
938  }
939  }
940 
941  /* Crap. Try again */
942  BV (value_free) (h, save_new_v, new_log2_pages);
943  /*
944  * If we've already doubled the size of the bucket once,
945  * fall back to linear search now.
946  */
947  if (resplit_once)
948  goto mark_linear;
949  else
950  goto try_resplit;
951 
952 expand_ok:
953  tmp_b.log2_pages = new_log2_pages;
954  tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
955  tmp_b.linear_search = mark_bucket_linear;
956 #if BIHASH_KVP_AT_BUCKET_LEVEL
957  /* Compensate for permanent refcount bump at the bucket level */
958  if (new_log2_pages > 0)
959 #endif
960  tmp_b.refcnt = h->saved_bucket.refcnt + 1;
961  ASSERT (tmp_b.refcnt > 0);
962  tmp_b.lock = 0;
964  b->as_u64 = tmp_b.as_u64;
965 
966 #if BIHASH_KVP_AT_BUCKET_LEVEL
967  if (h->saved_bucket.log2_pages > 0)
968  {
969 #endif
970 
971  /* free the old bucket, except at the bucket level if so configured */
972  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
973  BV (value_free) (h, v, h->saved_bucket.log2_pages);
974 
975 #if BIHASH_KVP_AT_BUCKET_LEVEL
976  }
977 #endif
978 
979 
980  BV (clib_bihash_alloc_unlock) (h);
981  return (0);
982 }
983 
984 static_always_inline int BV (clib_bihash_add_del_inline)
985  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add,
986  int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
987 {
988  u64 hash = BV (clib_bihash_hash) (add_v);
989  return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add,
990  is_stale_cb, arg);
991 }
992 
993 int BV (clib_bihash_add_del)
994  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
995 {
996  return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
997 }
998 
999 int BV (clib_bihash_add_or_overwrite_stale)
1000  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
1001  int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
1002 {
1003  return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
1004 }
1005 
1006 int BV (clib_bihash_search)
1007  (BVT (clib_bihash) * h,
1008  BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
1009 {
1010  return BV (clib_bihash_search_inline_2) (h, search_key, valuep);
1011 }
1012 
1013 u8 *BV (format_bihash) (u8 * s, va_list * args)
1014 {
1015  BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
1016  int verbose = va_arg (*args, int);
1017  BVT (clib_bihash_bucket) * b;
1018  BVT (clib_bihash_value) * v;
1019  int i, j, k;
1020  u64 active_elements = 0;
1021  u64 active_buckets = 0;
1022  u64 linear_buckets = 0;
1023 
1024  s = format (s, "Hash table '%s'\n", h->name ? h->name : (u8 *) "(unnamed)");
1025 
1026 #if BIHASH_LAZY_INSTANTIATE
1027  if (PREDICT_FALSE (h->instantiated == 0))
1028  return format (s, " empty, uninitialized");
1029 #endif
1030 
1031  for (i = 0; i < h->nbuckets; i++)
1032  {
1033  b = BV (clib_bihash_get_bucket) (h, i);
1034  if (BV (clib_bihash_bucket_is_empty) (b))
1035  {
1036  if (verbose > 1)
1037  s = format (s, "[%d]: empty\n", i);
1038  continue;
1039  }
1040 
1041  active_buckets++;
1042 
1043  if (b->linear_search)
1044  linear_buckets++;
1045 
1046  if (verbose)
1047  {
1048  s = format
1049  (s, "[%d]: heap offset %lld, len %d, refcnt %d, linear %d\n", i,
1050  b->offset, (1 << b->log2_pages), b->refcnt, b->linear_search);
1051  }
1052 
1053  v = BV (clib_bihash_get_value) (h, b->offset);
1054  for (j = 0; j < (1 << b->log2_pages); j++)
1055  {
1056  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
1057  {
1058  if (BV (clib_bihash_is_free) (&v->kvp[k]))
1059  {
1060  if (verbose > 1)
1061  s = format (s, " %d: empty\n",
1062  j * BIHASH_KVP_PER_PAGE + k);
1063  continue;
1064  }
1065  if (verbose)
1066  {
1067  if (h->kvp_fmt_fn)
1068  {
1069  s = format (s, " %d: %U\n",
1070  j * BIHASH_KVP_PER_PAGE + k,
1071  h->kvp_fmt_fn, &(v->kvp[k]), verbose);
1072  }
1073  else
1074  {
1075  s = format (s, " %d: %U\n",
1076  j * BIHASH_KVP_PER_PAGE + k,
1077  BV (format_bihash_kvp), &(v->kvp[k]));
1078  }
1079  }
1080  active_elements++;
1081  }
1082  v++;
1083  }
1084  }
1085 
1086  s = format (s, " %lld active elements %lld active buckets\n",
1087  active_elements, active_buckets);
1088  s = format (s, " %d free lists\n", vec_len (h->freelists));
1089 
1090  for (i = 0; i < vec_len (h->freelists); i++)
1091  {
1092  u32 nfree = 0;
1093  BVT (clib_bihash_value) * free_elt;
1094  u64 free_elt_as_u64 = h->freelists[i];
1095 
1096  while (free_elt_as_u64)
1097  {
1098  free_elt = BV (clib_bihash_get_value) (h, free_elt_as_u64);
1099  nfree++;
1100  free_elt_as_u64 = free_elt->next_free_as_u64;
1101  }
1102 
1103  if (nfree || verbose)
1104  s = format (s, " [len %d] %u free elts\n", 1 << i, nfree);
1105  }
1106 
1107  s = format (s, " %lld linear search buckets\n", linear_buckets);
1108  if (BIHASH_USE_HEAP)
1109  {
1110  BVT (clib_bihash_alloc_chunk) * c = h->chunks;
1111  uword bytes_left = 0, total_size = 0, n_chunks = 0;
1112 
1113  while (c)
1114  {
1115  bytes_left += c->bytes_left;
1116  total_size += c->size;
1117  n_chunks += 1;
1118  c = c->next;
1119  }
1120  s = format (s,
1121  " heap: %u chunk(s) allocated\n"
1122  " bytes: used %U, scrap %U\n", n_chunks,
1123  format_memory_size, total_size,
1124  format_memory_size, bytes_left);
1125  }
1126  else
1127  {
1128  u64 used_bytes = alloc_arena_next (h);
1129  s = format (s,
1130  " arena: base %llx, next %llx\n"
1131  " used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
1132  alloc_arena (h), alloc_arena_next (h),
1133  used_bytes, used_bytes >> 20,
1134  alloc_arena_size (h), alloc_arena_size (h) >> 20);
1135  }
1136  return s;
1137 }
1138 
1140  (BVT (clib_bihash) * h,
1141  BV (clib_bihash_foreach_key_value_pair_cb) cb, void *arg)
1142 {
1143  int i, j, k;
1144  BVT (clib_bihash_bucket) * b;
1145  BVT (clib_bihash_value) * v;
1146 
1147 
1148 #if BIHASH_LAZY_INSTANTIATE
1149  if (PREDICT_FALSE (h->instantiated == 0))
1150  return;
1151 #endif
1152 
1153  for (i = 0; i < h->nbuckets; i++)
1154  {
1155  b = BV (clib_bihash_get_bucket) (h, i);
1156  if (BV (clib_bihash_bucket_is_empty) (b))
1157  continue;
1158 
1159  v = BV (clib_bihash_get_value) (h, b->offset);
1160  for (j = 0; j < (1 << b->log2_pages); j++)
1161  {
1162  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
1163  {
1164  if (BV (clib_bihash_is_free) (&v->kvp[k]))
1165  continue;
1166 
1167  if (BIHASH_WALK_STOP == cb (&v->kvp[k], arg))
1168  return;
1169  /*
1170  * In case the callback deletes the last entry in the bucket...
1171  */
1172  if (BV (clib_bihash_bucket_is_empty) (b))
1173  goto doublebreak;
1174  }
1175  v++;
1176  }
1177  doublebreak:
1178  ;
1179  }
1180 }
1181 
1182 /** @endcond */
1183 
1184 /*
1185  * fd.io coding-style-patch-verification: ON
1186  *
1187  * Local Variables:
1188  * eval: (c-set-style "gnu")
1189  * End:
1190  */
thread_index
u32 thread_index
Definition: nat44_ei_hairpinning.c:492
clib_mem_get_heap
static clib_mem_heap_t * clib_mem_get_heap(void)
Definition: mem.h:359
clib_mem_get_heap_base
void * clib_mem_get_heap_base(clib_mem_heap_t *heap)
Definition: mem_dlmalloc.c:586
F_SEAL_SHRINK
#define F_SEAL_SHRINK
Definition: mem.c:44
BIHASH_KVP_PER_PAGE
#define BIHASH_KVP_PER_PAGE
Definition: bihash_16_8.h:25
name
string name[64]
Definition: fib.api:25
next
u16 * next
Definition: nat44_ei_out2in.c:718
clib_mem_free
static void clib_mem_free(void *p)
Definition: mem.h:311
os_out_of_memory
void os_out_of_memory(void)
Definition: unix-misc.c:219
vec_delete
#define vec_delete(V, N, M)
Delete N elements starting at element M.
Definition: vec.h:875
clib_bihash_get_value
static void * clib_bihash_get_value(clib_bihash *h, uword offset)
Get pointer to value page given its clib mheap offset.
clib_memcpy_fast
static_always_inline void * clib_memcpy_fast(void *restrict dst, const void *restrict src, size_t n)
Definition: string.h:92
memory_size
u64 memory_size
Definition: vhost_user.h:124
h
h
Definition: flowhash_template.h:372
clib_unix_warning
#define clib_unix_warning(format, args...)
Definition: error.h:68
clib_all_bihash_set_heap
__clib_export clib_mem_heap_t * clib_all_bihash_set_heap(void)
Definition: bihash_all_vector.c:23
clib_bihash_search_inline_2
int clib_bihash_search_inline_2(clib_bihash *h, clib_bihash_kv *search_key, clib_bihash_kv *valuep)
Search a bi-hash table.
clib_mem_vm_create_fd
__clib_export int clib_mem_vm_create_fd(clib_mem_page_sz_t log2_page_size, char *fmt,...)
Definition: mem.c:263
clib_bihash_get_offset
static uword clib_bihash_get_offset(clib_bihash *h, void *v)
Get clib mheap offset given a pointer.
max_log2
static uword max_log2(uword x)
Definition: clib.h:223
split_and_rehash_linear
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)
Definition: vnet_classify.c:335
round_pow2
static uword round_pow2(uword x, uword pow2)
Definition: clib.h:279
alloc_aligned
static void * alloc_aligned(uword size, uword log2_align, void **ptr_to_free)
Definition: test_vec.h:191
vec_len
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: vec_bootstrap.h:142
CLIB_MEMORY_STORE_BARRIER
#define CLIB_MEMORY_STORE_BARRIER()
Definition: clib.h:140
clib_bihash_init
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
vec_add1
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:606
clib_all_bihashes
__clib_export void ** clib_all_bihashes
Definition: bihash_all_vector.c:19
PREDICT_FALSE
#define PREDICT_FALSE(x)
Definition: clib.h:124
c
svmdb_client_t * c
Definition: vpp_get_metrics.c:48
static_always_inline
#define static_always_inline
Definition: clib.h:112
uword
u64 uword
Definition: types.h:112
clib_bihash_free
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
F_ADD_SEALS
#define F_ADD_SEALS
Definition: mem.c:40
vec_header_t::vector_data
u8 vector_data[0]
Vector data .
Definition: vec_bootstrap.h:60
BVT
BVT(clib_bihash)
The table of adjacencies indexed by the rewrite string.
Definition: l2_fib.c:1069
i
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:261
mask
vl_api_pnat_mask_t mask
Definition: pnat.api:45
vec_validate
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment)
Definition: vec.h:523
clib_mem_vm_free
static void clib_mem_vm_free(void *addr, uword size)
Definition: mem.h:443
log2_pages
u8 log2_pages
Definition: bihash_doc.h:62
clib_mem_vm_reserve
uword clib_mem_vm_reserve(uword start, uword size, clib_mem_page_sz_t log2_page_sz)
Definition: mem.c:331
CLIB_CACHE_LINE_BYTES
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:59
format_memory_size
u8 * format_memory_size(u8 *s, va_list *va)
Definition: std-formats.c:209
clib_memset_u8
static_always_inline void clib_memset_u8(void *p, u8 val, uword count)
Definition: string.h:441
os_get_thread_index
static_always_inline uword os_get_thread_index(void)
Definition: os.h:63
BIHASH_KVP_AT_BUCKET_LEVEL
#define BIHASH_KVP_AT_BUCKET_LEVEL
Definition: bihash_16_8.h:26
format_function_t
u8 *() format_function_t(u8 *s, va_list *args)
Definition: format.h:48
vec_free
#define vec_free(V)
Free vector's memory (no header).
Definition: vec.h:395
clib_bihash_value
template key/value backing page structure
Definition: bihash_doc.h:44
u64
unsigned long u64
Definition: types.h:89
split_and_rehash
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)
Definition: vnet_classify.c:284
format
description fragment has unexpected format
Definition: map.api:433
ASSERT
#define ASSERT(truth)
Definition: error_bootstrap.h:69
vec_validate_init_empty
#define vec_validate_init_empty(V, I, INIT)
Make sure vector is long enough for given index and initialize empty space (no header,...
Definition: vec.h:570
u32
unsigned int u32
Definition: types.h:88
extract_bits
static uword extract_bits(uword x, int start, int count)
Definition: clib.h:327
CLIB_MEM_PAGE_SZ_DEFAULT
@ CLIB_MEM_PAGE_SZ_DEFAULT
Definition: mem.h:60
make_working_copy
static void make_working_copy(vnet_classify_table_t *t, vnet_classify_bucket_t *b)
Definition: vnet_classify.c:229
BIHASH_USE_HEAP
#define BIHASH_USE_HEAP
Definition: bihash_16_8.h:29
clib_bihash_add_del
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.
vec_header_t
vector header structure
Definition: vec_bootstrap.h:55
clib_bihash_foreach_key_value_pair
void clib_bihash_foreach_key_value_pair(clib_bihash *h, clib_bihash_foreach_key_value_pair_cb *callback, void *arg)
Visit active (key,value) pairs in a bi-hash table.
b
vlib_buffer_t ** b
Definition: nat44_ei_out2in.c:717
u8
unsigned char u8
Definition: types.h:56
a
a
Definition: bitmap.h:544
clib_warning
#define clib_warning(format, args...)
Definition: error.h:59
clib_mem_alloc_aligned
static void * clib_mem_alloc_aligned(uword size, uword align)
Definition: mem.h:261
clib_bihash_foreach_key_value_pair_cb
int(* clib_bihash_foreach_key_value_pair_cb)(clib_bihash_kv *kv, void *ctx)
Definition: bihash_doc.h:175
rv
int __clib_unused rv
Definition: application.c:491
MAP_HUGE_SHIFT
#define MAP_HUGE_SHIFT
Definition: ip4_mtrie.c:787
PREDICT_TRUE
#define PREDICT_TRUE(x)
Definition: clib.h:125
vec_header_t::len
u32 len
Number of elements in vector (NOT its allocated length).
Definition: vec_bootstrap.h:57
clib_mem_set_heap
static clib_mem_heap_t * clib_mem_set_heap(clib_mem_heap_t *heap)
Definition: mem.h:365