FD.io VPP  v17.07.01-10-g3be13f0
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 void BV (clib_bihash_init)
19  (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
20 {
21  void *oldheap;
22 
23  nbuckets = 1 << (max_log2 (nbuckets));
24 
25  h->name = (u8 *) name;
26  h->nbuckets = nbuckets;
27  h->log2_nbuckets = max_log2 (nbuckets);
28 
29  h->mheap = mheap_alloc (0 /* use VM */ , memory_size);
30 
31  oldheap = clib_mem_set_heap (h->mheap);
32  vec_validate_aligned (h->buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
35 
36  clib_mem_set_heap (oldheap);
37 }
38 
39 void BV (clib_bihash_free) (BVT (clib_bihash) * h)
40 {
41  mheap_free (h->mheap);
42  memset (h, 0, sizeof (*h));
43 }
44 
45 static
47 BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
48 {
49  BVT (clib_bihash_value) * rv = 0;
50  void *oldheap;
51 
52  ASSERT (h->writer_lock[0]);
53  if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
54  {
55  oldheap = clib_mem_set_heap (h->mheap);
56 
57  vec_validate (h->freelists, log2_pages);
58  rv = clib_mem_alloc_aligned ((sizeof (*rv) * (1 << log2_pages)),
60  clib_mem_set_heap (oldheap);
61  goto initialize;
62  }
63  rv = h->freelists[log2_pages];
64  h->freelists[log2_pages] = rv->next_free;
65 
66 initialize:
67  ASSERT (rv);
68  /*
69  * Latest gcc complains that the length arg is zero
70  * if we replace (1<<log2_pages) with vec_len(rv).
71  * No clue.
72  */
73  memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
74  return rv;
75 }
76 
77 static void
78 BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
80 {
81  ASSERT (h->writer_lock[0]);
82 
83  ASSERT (vec_len (h->freelists) > log2_pages);
84 
85  v->next_free = h->freelists[log2_pages];
86  h->freelists[log2_pages] = v;
87 }
88 
89 static inline void
90 BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
91 {
93  clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8)));
94  void *oldheap;
95  BVT (clib_bihash_value) * working_copy;
96  u32 thread_index = os_get_thread_index ();
97  int log2_working_copy_length;
98 
99  if (thread_index >= vec_len (h->working_copies))
100  {
101  oldheap = clib_mem_set_heap (h->mheap);
102  vec_validate (h->working_copies, thread_index);
103  vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0);
104  clib_mem_set_heap (oldheap);
105  }
106 
107  /*
108  * working_copies are per-cpu so that near-simultaneous
109  * updates from multiple threads will not result in sporadic, spurious
110  * lookup failures.
111  */
112  working_copy = h->working_copies[thread_index];
113  log2_working_copy_length = h->working_copy_lengths[thread_index];
114 
115  h->saved_bucket.as_u64 = b->as_u64;
116  oldheap = clib_mem_set_heap (h->mheap);
117 
118  if (b->log2_pages > log2_working_copy_length)
119  {
120  if (working_copy)
121  clib_mem_free (working_copy);
122 
123  working_copy = clib_mem_alloc_aligned
124  (sizeof (working_copy[0]) * (1 << b->log2_pages),
126  h->working_copy_lengths[thread_index] = b->log2_pages;
127  h->working_copies[thread_index] = working_copy;
128  }
129 
130  clib_mem_set_heap (oldheap);
131 
132  v = BV (clib_bihash_get_value) (h, b->offset);
133 
134  clib_memcpy (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
135  working_bucket.as_u64 = b->as_u64;
136  working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
138  b->as_u64 = working_bucket.as_u64;
139  h->working_copies[thread_index] = working_copy;
140 }
141 
142 static
144 BV (split_and_rehash)
145  (BVT (clib_bihash) * h,
146  BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
147  u32 new_log2_pages)
148 {
149  BVT (clib_bihash_value) * new_values, *new_v;
150  int i, j, length_in_kvs;
151 
152  new_values = BV (value_alloc) (h, new_log2_pages);
153  length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
154 
155  for (i = 0; i < length_in_kvs; i++)
156  {
157  u64 new_hash;
158 
159  /* Entry not in use? Forget it */
160  if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
161  continue;
162 
163  /* rehash the item onto its new home-page */
164  new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
165  new_hash >>= h->log2_nbuckets;
166  new_hash &= (1 << new_log2_pages) - 1;
167  new_v = &new_values[new_hash];
168 
169  /* Across the new home-page */
170  for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
171  {
172  /* Empty slot */
173  if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
174  {
175  clib_memcpy (&(new_v->kvp[j]), &(old_values->kvp[i]),
176  sizeof (new_v->kvp[j]));
177  goto doublebreak;
178  }
179  }
180  /* Crap. Tell caller to try again */
181  BV (value_free) (h, new_values, new_log2_pages);
182  return 0;
183  doublebreak:;
184  }
185 
186  return new_values;
187 }
188 
189 static
192  (BVT (clib_bihash) * h,
193  BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
194  u32 new_log2_pages)
195 {
196  BVT (clib_bihash_value) * new_values;
197  int i, j, new_length, old_length;
198 
199  new_values = BV (value_alloc) (h, new_log2_pages);
200  new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
201  old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
202 
203  j = 0;
204  /* Across the old value array */
205  for (i = 0; i < old_length; i++)
206  {
207  /* Find a free slot in the new linear scan bucket */
208  for (; j < new_length; j++)
209  {
210  /* Old value not in use? Forget it. */
211  if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
212  goto doublebreak;
213 
214  /* New value should never be in use */
215  if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
216  {
217  /* Copy the old value and move along */
218  clib_memcpy (&(new_values->kvp[j]), &(old_values->kvp[i]),
219  sizeof (new_values->kvp[j]));
220  j++;
221  goto doublebreak;
222  }
223  }
224  /* This should never happen... */
225  clib_warning ("BUG: linear rehash failed!");
226  BV (value_free) (h, new_values, new_log2_pages);
227  return 0;
228 
229  doublebreak:;
230  }
231  return new_values;
232 }
233 
234 int BV (clib_bihash_add_del)
235  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
236 {
237  u32 bucket_index;
238  clib_bihash_bucket_t *b, tmp_b;
239  BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
240  int rv = 0;
241  int i, limit;
242  u64 hash, new_hash;
243  u32 new_log2_pages, old_log2_pages;
244  u32 thread_index = os_get_thread_index ();
245  int mark_bucket_linear;
246  int resplit_once;
247 
248  hash = BV (clib_bihash_hash) (add_v);
249 
250  bucket_index = hash & (h->nbuckets - 1);
251  b = &h->buckets[bucket_index];
252 
253  hash >>= h->log2_nbuckets;
254 
255  tmp_b.linear_search = 0;
256 
257  while (__sync_lock_test_and_set (h->writer_lock, 1))
258  ;
259 
260  /* First elt in the bucket? */
261  if (b->offset == 0)
262  {
263  if (is_add == 0)
264  {
265  rv = -1;
266  goto unlock;
267  }
268 
269  v = BV (value_alloc) (h, 0);
270 
271  *v->kvp = *add_v;
272  tmp_b.as_u64 = 0;
273  tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
274 
275  b->as_u64 = tmp_b.as_u64;
276  goto unlock;
277  }
278 
279  BV (make_working_copy) (h, b);
280 
281  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
282 
283  limit = BIHASH_KVP_PER_PAGE;
284  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
285  if (b->linear_search)
286  limit <<= b->log2_pages;
287 
288  if (is_add)
289  {
290  /*
291  * For obvious (in hindsight) reasons, see if we're supposed to
292  * replace an existing key, then look for an empty slot.
293  */
294  for (i = 0; i < limit; i++)
295  {
296  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
297  {
298  clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
300  /* Restore the previous (k,v) pairs */
301  b->as_u64 = h->saved_bucket.as_u64;
302  goto unlock;
303  }
304  }
305  for (i = 0; i < limit; i++)
306  {
307  if (BV (clib_bihash_is_free) (&(v->kvp[i])))
308  {
309  clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
311  b->as_u64 = h->saved_bucket.as_u64;
312  goto unlock;
313  }
314  }
315  /* no room at the inn... split case... */
316  }
317  else
318  {
319  for (i = 0; i < limit; i++)
320  {
321  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
322  {
323  memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
325  b->as_u64 = h->saved_bucket.as_u64;
326  goto unlock;
327  }
328  }
329  rv = -3;
330  b->as_u64 = h->saved_bucket.as_u64;
331  goto unlock;
332  }
333 
334  old_log2_pages = h->saved_bucket.log2_pages;
335  new_log2_pages = old_log2_pages + 1;
336  mark_bucket_linear = 0;
337 
338  working_copy = h->working_copies[thread_index];
339  resplit_once = 0;
340 
341  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
342  new_log2_pages);
343  if (new_v == 0)
344  {
345  try_resplit:
346  resplit_once = 1;
347  new_log2_pages++;
348  /* Try re-splitting. If that fails, fall back to linear search */
349  new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
350  new_log2_pages);
351  if (new_v == 0)
352  {
353  mark_linear:
354  new_log2_pages--;
355  /* pinned collisions, use linear search */
356  new_v =
357  BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
358  new_log2_pages);
359  mark_bucket_linear = 1;
360  }
361  }
362 
363  /* Try to add the new entry */
364  save_new_v = new_v;
365  new_hash = BV (clib_bihash_hash) (add_v);
366  limit = BIHASH_KVP_PER_PAGE;
367  if (mark_bucket_linear)
368  limit <<= new_log2_pages;
369  new_hash >>= h->log2_nbuckets;
370  new_hash &= (1 << new_log2_pages) - 1;
371  new_v += mark_bucket_linear ? 0 : new_hash;
372 
373  for (i = 0; i < limit; i++)
374  {
375  if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
376  {
377  clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
378  goto expand_ok;
379  }
380  }
381 
382  /* Crap. Try again */
383  BV (value_free) (h, save_new_v, new_log2_pages);
384  /*
385  * If we've already doubled the size of the bucket once,
386  * fall back to linear search now.
387  */
388  if (resplit_once)
389  goto mark_linear;
390  else
391  goto try_resplit;
392 
393 expand_ok:
394  /* Keep track of the number of linear-scan buckets */
395  if (tmp_b.linear_search ^ mark_bucket_linear)
396  h->linear_buckets += (mark_bucket_linear == 1) ? 1 : -1;
397 
398  tmp_b.log2_pages = new_log2_pages;
399  tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
400  tmp_b.linear_search = mark_bucket_linear;
401 
403  b->as_u64 = tmp_b.as_u64;
404  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
405  BV (value_free) (h, v, old_log2_pages);
406 
407 unlock:
409  h->writer_lock[0] = 0;
410  return rv;
411 }
412 
413 int BV (clib_bihash_search)
414  (const BVT (clib_bihash) * h,
415  BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
416 {
417  u64 hash;
418  u32 bucket_index;
419  BVT (clib_bihash_value) * v;
421  int i, limit;
422 
423  ASSERT (valuep);
424 
425  hash = BV (clib_bihash_hash) (search_key);
426 
427  bucket_index = hash & (h->nbuckets - 1);
428  b = &h->buckets[bucket_index];
429 
430  if (b->offset == 0)
431  return -1;
432 
433  hash >>= h->log2_nbuckets;
434 
435  v = BV (clib_bihash_get_value) (h, b->offset);
436  limit = BIHASH_KVP_PER_PAGE;
437  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
438  if (PREDICT_FALSE (b->linear_search))
439  limit <<= b->log2_pages;
440 
441  for (i = 0; i < limit; i++)
442  {
443  if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
444  {
445  *valuep = v->kvp[i];
446  return 0;
447  }
448  }
449  return -1;
450 }
451 
452 u8 *BV (format_bihash) (u8 * s, va_list * args)
453 {
454  BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
455  int verbose = va_arg (*args, int);
457  BVT (clib_bihash_value) * v;
458  int i, j, k;
459  u64 active_elements = 0;
460 
461  s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
462 
463  for (i = 0; i < h->nbuckets; i++)
464  {
465  b = &h->buckets[i];
466  if (b->offset == 0)
467  {
468  if (verbose > 1)
469  s = format (s, "[%d]: empty\n", i);
470  continue;
471  }
472 
473  if (verbose)
474  {
475  s = format (s, "[%d]: heap offset %d, len %d, linear %d\n", i,
476  b->offset, (1 << b->log2_pages), b->linear_search);
477  }
478 
479  v = BV (clib_bihash_get_value) (h, b->offset);
480  for (j = 0; j < (1 << b->log2_pages); j++)
481  {
482  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
483  {
484  if (BV (clib_bihash_is_free) (&v->kvp[k]))
485  {
486  if (verbose > 1)
487  s = format (s, " %d: empty\n",
488  j * BIHASH_KVP_PER_PAGE + k);
489  continue;
490  }
491  if (verbose)
492  {
493  s = format (s, " %d: %U\n",
494  j * BIHASH_KVP_PER_PAGE + k,
495  BV (format_bihash_kvp), &(v->kvp[k]));
496  }
497  active_elements++;
498  }
499  v++;
500  }
501  }
502 
503  s = format (s, " %lld active elements\n", active_elements);
504  s = format (s, " %d free lists\n", vec_len (h->freelists));
505  s = format (s, " %d linear search buckets\n", h->linear_buckets);
506 
507  return s;
508 }
509 
511  (BVT (clib_bihash) * h, void *callback, void *arg)
512 {
513  int i, j, k;
515  BVT (clib_bihash_value) * v;
516  void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
517 
518  for (i = 0; i < h->nbuckets; i++)
519  {
520  b = &h->buckets[i];
521  if (b->offset == 0)
522  continue;
523 
524  v = BV (clib_bihash_get_value) (h, b->offset);
525  for (j = 0; j < (1 << b->log2_pages); j++)
526  {
527  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
528  {
529  if (BV (clib_bihash_is_free) (&v->kvp[k]))
530  continue;
531 
532  (*fp) (&v->kvp[k], arg);
533  }
534  v++;
535  }
536  }
537 }
538 
539 /** @endcond */
540 
541 /*
542  * fd.io coding-style-patch-verification: ON
543  *
544  * Local Variables:
545  * eval: (c-set-style "gnu")
546  * End:
547  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:436
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
clib_bihash_bucket_t
Definition: bihash_doc.h:65
#define BIHASH_KVP_PER_PAGE
Definition: bihash_16_8.h:18
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
void * mheap_alloc(void *memory, uword size)
Definition: mheap.c:947
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
#define vec_validate_aligned(V, I, A)
Make sure vector is long enough for given index (no header, specified alignment)
Definition: vec.h:447
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.
static BVT(clib_bihash)
Definition: adj_nbr.c:26
unsigned long u64
Definition: types.h:89
#define mheap_free(v)
Definition: mheap.h:62
static uword clib_bihash_get_offset(clib_bihash *h, void *v)
Get clib mheap offset given a pointer.
#define v
Definition: acl.c:320
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:97
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
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)
static void * clib_mem_set_heap(void *heap)
Definition: mem.h:223
#define clib_warning(format, args...)
Definition: error.h:59
u64 memory_size
Definition: vhost-user.h:76
#define clib_memcpy(a, b, c)
Definition: string.h:69
static void make_working_copy(vnet_classify_table_t *t, vnet_classify_bucket_t *b)
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
int clib_bihash_search(clib_bihash *h, clib_bihash_kv *search_v, clib_bihash_kv *return_v)
Search a bi-hash table.
static void clib_mem_free(void *p)
Definition: mem.h:176
u8 log2_pages
Definition: bihash_doc.h:62
u64 uword
Definition: types.h:112
template key/value backing page structure
Definition: bihash_doc.h:44
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
static uword max_log2(uword x)
Definition: clib.h:228
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:117
#define CLIB_MEMORY_BARRIER()
Definition: clib.h:101
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:485
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67