FD.io VPP  v17.01.1-3-gc6833f8
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  vec_validate_aligned (rv, (1 << log2_pages) - 1, CLIB_CACHE_LINE_BYTES);
59  clib_mem_set_heap (oldheap);
60  goto initialize;
61  }
62  rv = h->freelists[log2_pages];
63  h->freelists[log2_pages] = rv->next_free;
64 
65 initialize:
66  ASSERT (rv);
67  ASSERT (vec_len (rv) == (1 << log2_pages));
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)
79 {
81 
82  ASSERT (h->writer_lock[0]);
83 
84  log2_pages = min_log2 (vec_len (v));
85 
86  ASSERT (vec_len (h->freelists) > log2_pages);
87 
88  v->next_free = h->freelists[log2_pages];
89  h->freelists[log2_pages] = v;
90 }
91 
92 static inline void
93 BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
94 {
96  clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8)));
97  void *oldheap;
98  BVT (clib_bihash_value) * working_copy;
99  u32 cpu_number = os_get_cpu_number ();
100 
101  if (cpu_number >= vec_len (h->working_copies))
102  {
103  oldheap = clib_mem_set_heap (h->mheap);
104  vec_validate (h->working_copies, cpu_number);
105  clib_mem_set_heap (oldheap);
106  }
107 
108  /*
109  * working_copies are per-cpu so that near-simultaneous
110  * updates from multiple threads will not result in sporadic, spurious
111  * lookup failures.
112  */
113  working_copy = h->working_copies[cpu_number];
114 
115  h->saved_bucket.as_u64 = b->as_u64;
116  oldheap = clib_mem_set_heap (h->mheap);
117 
118  if ((1 << b->log2_pages) > vec_len (working_copy))
119  {
120  vec_validate_aligned (working_copy, (1 << b->log2_pages) - 1,
121  sizeof (u64));
122  h->working_copies[cpu_number] = working_copy;
123  }
124 
125  _vec_len (working_copy) = 1 << b->log2_pages;
126  clib_mem_set_heap (oldheap);
127 
128  v = BV (clib_bihash_get_value) (h, b->offset);
129 
130  clib_memcpy (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
131  working_bucket.as_u64 = b->as_u64;
132  working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
134  b->as_u64 = working_bucket.as_u64;
135  h->working_copies[cpu_number] = working_copy;
136 }
137 
138 static
140 BV (split_and_rehash)
141  (BVT (clib_bihash) * h,
142  BVT (clib_bihash_value) * old_values, u32 new_log2_pages)
143 {
144  BVT (clib_bihash_value) * new_values, *v, *new_v;
145  int i, j, k;
146 
147  new_values = BV (value_alloc) (h, new_log2_pages);
148 
149  v = old_values;
150  for (i = 0; i < vec_len (old_values); i++)
151  {
152  u64 new_hash;
153 
154  for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
155  {
156  if (BV (clib_bihash_is_free) (&(v->kvp[j])) == 0)
157  {
158  new_hash = BV (clib_bihash_hash) (&(v->kvp[j]));
159  new_hash >>= h->log2_nbuckets;
160  new_hash &= (1 << new_log2_pages) - 1;
161 
162  new_v = &new_values[new_hash];
163 
164  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
165  {
166  if (BV (clib_bihash_is_free) (&(new_v->kvp[k])))
167  {
168  clib_memcpy (&(new_v->kvp[k]), &(v->kvp[j]),
169  sizeof (new_v->kvp[k]));
170  goto doublebreak;
171  }
172  }
173  /* Crap. Tell caller to try again */
174  BV (value_free) (h, new_values);
175  return 0;
176  }
177  doublebreak:
178  ;
179  }
180  v++;
181  }
182  return new_values;
183 }
184 
185 int BV (clib_bihash_add_del)
186  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
187 {
188  u32 bucket_index;
189  clib_bihash_bucket_t *b, tmp_b;
190  BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
191  u32 value_index;
192  int rv = 0;
193  int i;
194  u64 hash, new_hash;
195  u32 new_log2_pages;
196  u32 cpu_number = os_get_cpu_number ();
197 
198  hash = BV (clib_bihash_hash) (add_v);
199 
200  bucket_index = hash & (h->nbuckets - 1);
201  b = &h->buckets[bucket_index];
202 
203  hash >>= h->log2_nbuckets;
204 
205  while (__sync_lock_test_and_set (h->writer_lock, 1))
206  ;
207 
208  /* First elt in the bucket? */
209  if (b->offset == 0)
210  {
211  if (is_add == 0)
212  {
213  rv = -1;
214  goto unlock;
215  }
216 
217  v = BV (value_alloc) (h, 0);
218  *v->kvp = *add_v;
219  tmp_b.as_u64 = 0;
220  tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
221 
222  b->as_u64 = tmp_b.as_u64;
223  goto unlock;
224  }
225 
226  BV (make_working_copy) (h, b);
227 
228  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
229  value_index = hash & ((1 << h->saved_bucket.log2_pages) - 1);
230  v += value_index;
231 
232  if (is_add)
233  {
234  /*
235  * For obvious (in hindsight) reasons, see if we're supposed to
236  * replace an existing key, then look for an empty slot.
237  */
238  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
239  {
240  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
241  {
242  clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
244  /* Restore the previous (k,v) pairs */
245  b->as_u64 = h->saved_bucket.as_u64;
246  goto unlock;
247  }
248  }
249  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
250  {
251  if (BV (clib_bihash_is_free) (&(v->kvp[i])))
252  {
253  clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
255  b->as_u64 = h->saved_bucket.as_u64;
256  goto unlock;
257  }
258  }
259  /* no room at the inn... split case... */
260  }
261  else
262  {
263  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
264  {
265  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
266  {
267  memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
269  b->as_u64 = h->saved_bucket.as_u64;
270  goto unlock;
271  }
272  }
273  rv = -3;
274  b->as_u64 = h->saved_bucket.as_u64;
275  goto unlock;
276  }
277 
278  new_log2_pages = h->saved_bucket.log2_pages + 1;
279 
280 expand_again:
281  working_copy = h->working_copies[cpu_number];
282  new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
283  if (new_v == 0)
284  {
285  new_log2_pages++;
286  goto expand_again;
287  }
288 
289  /* Try to add the new entry */
290  save_new_v = new_v;
291  new_hash = BV (clib_bihash_hash) (add_v);
292  new_hash >>= h->log2_nbuckets;
293  new_hash &= (1 << min_log2 (vec_len (new_v))) - 1;
294  new_v += new_hash;
295 
296  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
297  {
298  if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
299  {
300  clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
301  goto expand_ok;
302  }
303  }
304  /* Crap. Try again */
305  new_log2_pages++;
306  BV (value_free) (h, save_new_v);
307  goto expand_again;
308 
309 expand_ok:
310  tmp_b.log2_pages = min_log2 (vec_len (save_new_v));
311  tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
313  b->as_u64 = tmp_b.as_u64;
314  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
315  BV (value_free) (h, v);
316 
317 unlock:
319  h->writer_lock[0] = 0;
320  return rv;
321 }
322 
323 int BV (clib_bihash_search)
324  (const BVT (clib_bihash) * h,
325  BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
326 {
327  u64 hash;
328  u32 bucket_index;
329  uword value_index;
330  BVT (clib_bihash_value) * v;
332  int i;
333 
334  ASSERT (valuep);
335 
336  hash = BV (clib_bihash_hash) (search_key);
337 
338  bucket_index = hash & (h->nbuckets - 1);
339  b = &h->buckets[bucket_index];
340 
341  if (b->offset == 0)
342  return -1;
343 
344  hash >>= h->log2_nbuckets;
345 
346  v = BV (clib_bihash_get_value) (h, b->offset);
347  value_index = hash & ((1 << b->log2_pages) - 1);
348  v += value_index;
349 
350  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
351  {
352  if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
353  {
354  *valuep = v->kvp[i];
355  return 0;
356  }
357  }
358  return -1;
359 }
360 
361 u8 *BV (format_bihash) (u8 * s, va_list * args)
362 {
363  BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
364  int verbose = va_arg (*args, int);
366  BVT (clib_bihash_value) * v;
367  int i, j, k;
368  u64 active_elements = 0;
369 
370  s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
371 
372  for (i = 0; i < h->nbuckets; i++)
373  {
374  b = &h->buckets[i];
375  if (b->offset == 0)
376  {
377  if (verbose > 1)
378  s = format (s, "[%d]: empty\n", i);
379  continue;
380  }
381 
382  if (verbose)
383  {
384  s = format (s, "[%d]: heap offset %d, len %d\n", i,
385  b->offset, (1 << b->log2_pages));
386  }
387 
388  v = BV (clib_bihash_get_value) (h, b->offset);
389  for (j = 0; j < (1 << b->log2_pages); j++)
390  {
391  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
392  {
393  if (BV (clib_bihash_is_free) (&v->kvp[k]))
394  {
395  if (verbose > 1)
396  s = format (s, " %d: empty\n",
397  j * BIHASH_KVP_PER_PAGE + k);
398  continue;
399  }
400  if (verbose)
401  {
402  s = format (s, " %d: %U\n",
403  j * BIHASH_KVP_PER_PAGE + k,
404  BV (format_bihash_kvp), &(v->kvp[k]));
405  }
406  active_elements++;
407  }
408  v++;
409  }
410  }
411 
412  s = format (s, " %lld active elements\n", active_elements);
413  s = format (s, " %d free lists\n", vec_len (h->freelists));
414 
415  return s;
416 }
417 
419  (BVT (clib_bihash) * h, void *callback, void *arg)
420 {
421  int i, j, k;
423  BVT (clib_bihash_value) * v;
424  void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
425 
426  for (i = 0; i < h->nbuckets; i++)
427  {
428  b = &h->buckets[i];
429  if (b->offset == 0)
430  continue;
431 
432  v = BV (clib_bihash_get_value) (h, b->offset);
433  for (j = 0; j < (1 << b->log2_pages); j++)
434  {
435  for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
436  {
437  if (BV (clib_bihash_is_free) (&v->kvp[k]))
438  continue;
439 
440  (*fp) (&v->kvp[k], arg);
441  }
442  v++;
443  }
444  }
445 }
446 
447 /** @endcond */
448 
449 /*
450  * fd.io coding-style-patch-verification: ON
451  *
452  * Local Variables:
453  * eval: (c-set-style "gnu")
454  * End:
455  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:396
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
clib_bihash_bucket_t
Definition: bihash_doc.h:65
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
void * mheap_alloc(void *memory, uword size)
Definition: mheap.c:953
#define vec_validate_aligned(V, I, A)
Make sure vector is long enough for given index (no header, specified alignment)
Definition: vec.h:407
static uword min_log2(uword x)
Definition: clib.h:183
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:314
#define BIHASH_KVP_PER_PAGE
Definition: bihash_24_8.h:18
uword os_get_cpu_number(void)
Definition: unix-misc.c:224
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 void * clib_mem_set_heap(void *heap)
Definition: mem.h:223
u64 memory_size
Definition: vhost-user.h:75
#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.
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:222
static void * clib_mem_alloc_aligned(uword size, uword align)
Definition: mem.h:117
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:418
#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 CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
static vnet_classify_entry_t * split_and_rehash(vnet_classify_table_t *t, vnet_classify_entry_t *old_values, u32 new_log2_pages)