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