FD.io VPP  v18.07.1-19-g511ce25
Vector Packet Processing
bihash_template.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2014 Cisco and/or its affiliates.
3 
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15 */
16 
17 /** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */
18 
19 /*
20  * Note: to instantiate the template multiple times in a single file,
21  * #undef __included_bihash_template_h__...
22  */
23 #ifndef __included_bihash_template_h__
24 #define __included_bihash_template_h__
25 
26 #include <vppinfra/heap.h>
27 #include <vppinfra/format.h>
28 #include <vppinfra/pool.h>
29 #include <vppinfra/cache.h>
30 
31 #ifndef BIHASH_TYPE
32 #error BIHASH_TYPE not defined
33 #endif
34 
35 #define _bv(a,b) a##b
36 #define __bv(a,b) _bv(a,b)
37 #define BV(a) __bv(a,BIHASH_TYPE)
38 
39 #define _bvt(a,b) a##b##_t
40 #define __bvt(a,b) _bvt(a,b)
41 #define BVT(a) __bvt(a,BIHASH_TYPE)
42 
43 typedef struct BV (clib_bihash_value)
44 {
45  union
46  {
47  BVT (clib_bihash_kv) kvp[BIHASH_KVP_PER_PAGE];
48  struct BV (clib_bihash_value) * next_free;
49  };
50 } BVT (clib_bihash_value);
51 
52 #if BIHASH_KVP_CACHE_SIZE > 5
53 #error Requested KVP cache LRU data exceeds 16 bits
54 #endif
55 
56 typedef struct
57 {
58  union
59  {
60  struct
61  {
62  u32 offset;
63  u8 linear_search;
64  u8 log2_pages;
65  i16 refcnt;
66  };
67  u64 as_u64;
68  };
69 #if BIHASH_KVP_CACHE_SIZE > 0
70  u16 cache_lru;
71  BVT (clib_bihash_kv) cache[BIHASH_KVP_CACHE_SIZE];
72 #endif
73 } BVT (clib_bihash_bucket);
74 
75 typedef struct
76 {
77  BVT (clib_bihash_value) * values;
78  BVT (clib_bihash_bucket) * buckets;
79  volatile u32 *writer_lock;
80 
81  BVT (clib_bihash_value) ** working_copies;
82  int *working_copy_lengths;
83  BVT (clib_bihash_bucket) saved_bucket;
84 
85  u32 nbuckets;
86  u32 log2_nbuckets;
87  u8 *name;
88 
89  u64 cache_hits;
90  u64 cache_misses;
91 
92  BVT (clib_bihash_value) ** freelists;
93 
94  /*
95  * Backing store allocation. Since bihash manages its own
96  * freelists, we simple dole out memory at alloc_arena_next.
97  */
98  uword alloc_arena;
99  uword alloc_arena_next;
100  uword alloc_arena_size;
101 
102  /**
103  * A custom format function to print the Key and Value of bihash_key instead of default hexdump
104  */
105  format_function_t *fmt_fn;
106 
107 } BVT (clib_bihash);
108 
109 
110 static inline void
111 BV (clib_bihash_update_lru) (BVT (clib_bihash_bucket) * b, u8 slot)
112 {
113 #if BIHASH_KVP_CACHE_SIZE > 1
114  u16 value, tmp, mask;
115  u8 found_lru_pos;
116  u16 save_hi;
117 
118  ASSERT (slot < BIHASH_KVP_CACHE_SIZE);
119 
120  /* First, find the slot in cache_lru */
121  mask = slot;
122  if (BIHASH_KVP_CACHE_SIZE > 1)
123  mask |= slot << 3;
124  if (BIHASH_KVP_CACHE_SIZE > 2)
125  mask |= slot << 6;
126  if (BIHASH_KVP_CACHE_SIZE > 3)
127  mask |= slot << 9;
128  if (BIHASH_KVP_CACHE_SIZE > 4)
129  mask |= slot << 12;
130 
131  value = b->cache_lru;
132  tmp = value ^ mask;
133 
134  /* Already the most-recently used? */
135  if ((tmp & 7) == 0)
136  return;
137 
138  found_lru_pos = ((tmp & (7 << 3)) == 0) ? 1 : 0;
139  if (BIHASH_KVP_CACHE_SIZE > 2)
140  found_lru_pos = ((tmp & (7 << 6)) == 0) ? 2 : found_lru_pos;
141  if (BIHASH_KVP_CACHE_SIZE > 3)
142  found_lru_pos = ((tmp & (7 << 9)) == 0) ? 3 : found_lru_pos;
143  if (BIHASH_KVP_CACHE_SIZE > 4)
144  found_lru_pos = ((tmp & (7 << 12)) == 0) ? 4 : found_lru_pos;
145 
146  ASSERT (found_lru_pos);
147 
148  /* create a mask to kill bits in or above slot */
149  mask = 0xFFFF << found_lru_pos;
150  mask <<= found_lru_pos;
151  mask <<= found_lru_pos;
152  mask ^= 0xFFFF;
153  tmp = value & mask;
154 
155  /* Save bits above slot */
156  mask ^= 0xFFFF;
157  mask <<= 3;
158  save_hi = value & mask;
159 
160  value = save_hi | (tmp << 3) | slot;
161 
162  b->cache_lru = value;
163 #endif
164 }
165 
166 void
167 BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b,
168  u8 slot);
169 
170 static inline u8 BV (clib_bihash_get_lru) (BVT (clib_bihash_bucket) * b)
171 {
172 #if BIHASH_KVP_CACHE_SIZE > 0
173  return (b->cache_lru >> (3 * (BIHASH_KVP_CACHE_SIZE - 1))) & 7;
174 #else
175  return 0;
176 #endif
177 }
178 
179 static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b)
180 {
181 #if BIHASH_KVP_CACHE_SIZE > 0
182  u16 initial_lru_value;
183 
184  memset (b->cache, 0xff, sizeof (b->cache));
185 
186  /*
187  * We'll want the cache to be loaded from slot 0 -> slot N, so
188  * the initial LRU order is reverse index order.
189  */
190  if (BIHASH_KVP_CACHE_SIZE == 1)
191  initial_lru_value = 0;
192  else if (BIHASH_KVP_CACHE_SIZE == 2)
193  initial_lru_value = (0 << 3) | (1 << 0);
194  else if (BIHASH_KVP_CACHE_SIZE == 3)
195  initial_lru_value = (0 << 6) | (1 << 3) | (2 << 0);
196  else if (BIHASH_KVP_CACHE_SIZE == 4)
197  initial_lru_value = (0 << 9) | (1 << 6) | (2 << 3) | (3 << 0);
198  else if (BIHASH_KVP_CACHE_SIZE == 5)
199  initial_lru_value = (0 << 12) | (1 << 9) | (2 << 6) | (3 << 3) | (4 << 0);
200 
201  b->cache_lru = initial_lru_value;
202 #endif
203 }
204 
205 static inline int BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b)
206 {
207 #if BIHASH_KVP_CACHE_SIZE > 0
208  u16 cache_lru_bit;
209  u16 rv;
210 
211  cache_lru_bit = 1 << 15;
212 
213  rv = __sync_fetch_and_or (&b->cache_lru, cache_lru_bit);
214  /* Was already locked? */
215  if (rv & (1 << 15))
216  return 0;
217 #endif
218  return 1;
219 }
220 
221 static inline void BV (clib_bihash_unlock_bucket)
222  (BVT (clib_bihash_bucket) * b)
223 {
224 #if BIHASH_KVP_CACHE_SIZE > 0
225  u16 cache_lru;
226 
227  cache_lru = b->cache_lru & ~(1 << 15);
228  b->cache_lru = cache_lru;
229 #endif
230 }
231 
232 static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h,
233  uword offset)
234 {
235  u8 *hp = (u8 *) h->alloc_arena;
236  u8 *vp = hp + offset;
237 
238  return (void *) vp;
239 }
240 
241 static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h,
242  void *v)
243 {
244  u8 *hp, *vp;
245 
246  hp = (u8 *) h->alloc_arena;
247  vp = (u8 *) v;
248 
249  return vp - hp;
250 }
251 
252 void BV (clib_bihash_init)
253  (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size);
254 
255 void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
256  format_function_t * fmt_fn);
257 
258 void BV (clib_bihash_free) (BVT (clib_bihash) * h);
259 
260 int BV (clib_bihash_add_del) (BVT (clib_bihash) * h,
261  BVT (clib_bihash_kv) * add_v, int is_add);
262 int BV (clib_bihash_search) (BVT (clib_bihash) * h,
263  BVT (clib_bihash_kv) * search_v,
264  BVT (clib_bihash_kv) * return_v);
265 
266 void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h,
267  void *callback, void *arg);
268 
269 format_function_t BV (format_bihash);
270 format_function_t BV (format_bihash_kvp);
271 format_function_t BV (format_bihash_lru);
272 
273 static inline int BV (clib_bihash_search_inline_with_hash)
274  (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * key_result)
275 {
276  u32 bucket_index;
277  BVT (clib_bihash_value) * v;
278  BVT (clib_bihash_bucket) * b;
279 #if BIHASH_KVP_CACHE_SIZE > 0
280  BVT (clib_bihash_kv) * kvp;
281 #endif
282  int i, limit;
283 
284  bucket_index = hash & (h->nbuckets - 1);
285  b = &h->buckets[bucket_index];
286 
287  if (b->offset == 0)
288  return -1;
289 
290 #if BIHASH_KVP_CACHE_SIZE > 0
291  /* Check the cache, if not currently locked */
292  if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0))
293  {
294  limit = BIHASH_KVP_CACHE_SIZE;
295  kvp = b->cache;
296  for (i = 0; i < limit; i++)
297  {
298  if (BV (clib_bihash_key_compare) (kvp[i].key, key_result->key))
299  {
300  *key_result = kvp[i];
301  h->cache_hits++;
302  return 0;
303  }
304  }
305  }
306 #endif
307 
308  hash >>= h->log2_nbuckets;
309 
310  v = BV (clib_bihash_get_value) (h, b->offset);
311 
312  /* If the bucket has unresolvable collisions, use linear search */
313  limit = BIHASH_KVP_PER_PAGE;
314  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
315  if (PREDICT_FALSE (b->linear_search))
316  limit <<= b->log2_pages;
317 
318  for (i = 0; i < limit; i++)
319  {
320  if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key))
321  {
322  *key_result = v->kvp[i];
323 
324 #if BIHASH_KVP_CACHE_SIZE > 0
325  u8 cache_slot;
326  /* Try to lock the bucket */
327  if (BV (clib_bihash_lock_bucket) (b))
328  {
329  cache_slot = BV (clib_bihash_get_lru) (b);
330  b->cache[cache_slot] = v->kvp[i];
331  BV (clib_bihash_update_lru) (b, cache_slot);
332 
333  /* Unlock the bucket */
334  BV (clib_bihash_unlock_bucket) (b);
335  h->cache_misses++;
336  }
337 #endif
338  return 0;
339  }
340  }
341  return -1;
342 }
343 
344 static inline int BV (clib_bihash_search_inline)
345  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result)
346 {
347  u64 hash;
348 
349  hash = BV (clib_bihash_hash) (key_result);
350 
351  return BV (clib_bihash_search_inline_with_hash) (h, hash, key_result);
352 }
353 
354 static inline void BV (clib_bihash_prefetch_bucket)
355  (BVT (clib_bihash) * h, u64 hash)
356 {
357  u32 bucket_index;
358  BVT (clib_bihash_bucket) * b;
359 
360  bucket_index = hash & (h->nbuckets - 1);
361  b = &h->buckets[bucket_index];
362 
364 }
365 
366 static inline void BV (clib_bihash_prefetch_data)
367  (BVT (clib_bihash) * h, u64 hash)
368 {
369  u32 bucket_index;
370  BVT (clib_bihash_value) * v;
371  BVT (clib_bihash_bucket) * b;
372 
373  bucket_index = hash & (h->nbuckets - 1);
374  b = &h->buckets[bucket_index];
375 
376  if (PREDICT_FALSE (b->offset == 0))
377  return;
378 
379  hash >>= h->log2_nbuckets;
380  v = BV (clib_bihash_get_value) (h, b->offset);
381 
382  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
383 
385 }
386 
387 static inline int BV (clib_bihash_search_inline_2_with_hash)
388  (BVT (clib_bihash) * h,
389  u64 hash, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
390 {
391  u32 bucket_index;
392  BVT (clib_bihash_value) * v;
393  BVT (clib_bihash_bucket) * b;
394 #if BIHASH_KVP_CACHE_SIZE > 0
395  BVT (clib_bihash_kv) * kvp;
396 #endif
397  int i, limit;
398 
399  ASSERT (valuep);
400 
401  bucket_index = hash & (h->nbuckets - 1);
402  b = &h->buckets[bucket_index];
403 
404  if (b->offset == 0)
405  return -1;
406 
407  /* Check the cache, if currently unlocked */
408 #if BIHASH_KVP_CACHE_SIZE > 0
409  if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0))
410  {
411  limit = BIHASH_KVP_CACHE_SIZE;
412  kvp = b->cache;
413  for (i = 0; i < limit; i++)
414  {
415  if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key))
416  {
417  *valuep = kvp[i];
418  h->cache_hits++;
419  return 0;
420  }
421  }
422  }
423 #endif
424 
425  hash >>= h->log2_nbuckets;
426  v = BV (clib_bihash_get_value) (h, b->offset);
427 
428  /* If the bucket has unresolvable collisions, use linear search */
429  limit = BIHASH_KVP_PER_PAGE;
430  v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
431  if (PREDICT_FALSE (b->linear_search))
432  limit <<= b->log2_pages;
433 
434  for (i = 0; i < limit; i++)
435  {
436  if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
437  {
438  *valuep = v->kvp[i];
439 
440 #if BIHASH_KVP_CACHE_SIZE > 0
441  u8 cache_slot;
442 
443  /* Try to lock the bucket */
444  if (BV (clib_bihash_lock_bucket) (b))
445  {
446  cache_slot = BV (clib_bihash_get_lru) (b);
447  b->cache[cache_slot] = v->kvp[i];
448  BV (clib_bihash_update_lru) (b, cache_slot);
449 
450  /* Reenable the cache */
451  BV (clib_bihash_unlock_bucket) (b);
452  h->cache_misses++;
453  }
454 #endif
455  return 0;
456  }
457  }
458  return -1;
459 }
460 
461 static inline int BV (clib_bihash_search_inline_2)
462  (BVT (clib_bihash) * h,
463  BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
464 {
465  u64 hash;
466 
467  hash = BV (clib_bihash_hash) (search_key);
468 
469  return BV (clib_bihash_search_inline_2_with_hash) (h, hash, search_key,
470  valuep);
471 }
472 
473 
474 #endif /* __included_bihash_template_h__ */
475 
476 /** @endcond */
477 
478 /*
479  * fd.io coding-style-patch-verification: ON
480  *
481  * Local Variables:
482  * eval: (c-set-style "gnu")
483  * End:
484  */
int clib_bihash_search_inline_with_hash(clib_bihash *h, u64 hash, clib_bihash_kv *in_out_kv)
Search a bi-hash table, use supplied hash code.
#define BIHASH_KVP_PER_PAGE
Definition: bihash_16_8.h:20
u64 as_u64
Definition: bihash_doc.h:63
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
#define PREDICT_TRUE(x)
Definition: clib.h:106
unsigned long u64
Definition: types.h:89
Fixed length block allocator.
for(i=1;i<=collision_buckets;i++)
int i
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
unsigned char u8
Definition: types.h:56
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 int u32
Definition: types.h:88
static uword clib_bihash_get_offset(clib_bihash *h, void *v)
Get clib mheap offset given a pointer.
#define v
Definition: acl.c:491
unsigned short u16
Definition: types.h:57
u64 memory_size
Definition: vhost_user.h:110
#define PREDICT_FALSE(x)
Definition: clib.h:105
int clib_bihash_search_inline(clib_bihash *h, clib_bihash_kv *in_out_kv)
Search a bi-hash table.
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
void clib_bihash_prefetch_bucket(clib_bihash *h, u64 hash)
Prefetch a bi-hash bucket given a hash code.
void clib_bihash_foreach_key_value_pair(clib_bihash *h, void *callback, void *arg)
Visit active (key,value) pairs in a bi-hash table.
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:77
void clib_bihash_prefetch_data(clib_bihash *h, u64 hash)
Prefetch bi-hash (key,value) data given a hash code.
#define ASSERT(truth)
int clib_bihash_search_inline_2(clib_bihash *h, clib_bihash_kv *search_key, clib_bihash_kv *valuep)
Search a bi-hash table.
u8 log2_pages
Definition: bihash_doc.h:62
template key/value backing page structure
Definition: bihash_doc.h:44
u64 uword
Definition: types.h:112
struct clib_bihash_value offset
template key/value backing page structure
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:62
#define BIHASH_KVP_CACHE_SIZE
Definition: bihash_16_8.h:21
signed short i16
Definition: types.h:46