Line data Source code
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 : #include <vppinfra/lock.h>
31 :
32 : #ifndef BIHASH_TYPE
33 : #error BIHASH_TYPE not defined
34 : #endif
35 :
36 : #ifdef BIHASH_32_64_SVM
37 : #include <vppinfra/linux/syscall.h>
38 : #include <fcntl.h>
39 : #define F_LINUX_SPECIFIC_BASE 1024
40 : #define F_ADD_SEALS (F_LINUX_SPECIFIC_BASE + 9)
41 : #define F_SEAL_SHRINK (2)
42 : /* Max page size 2**16 due to refcount width */
43 : #define BIHASH_FREELIST_LENGTH 17
44 : #endif
45 :
46 : /* default is 2MB, use 30 for 1GB */
47 : #ifndef BIHASH_LOG2_HUGEPAGE_SIZE
48 : #define BIHASH_LOG2_HUGEPAGE_SIZE 21
49 : #endif
50 :
51 : #define _bv(a,b) a##b
52 : #define __bv(a,b) _bv(a,b)
53 : #define BV(a) __bv(a,BIHASH_TYPE)
54 :
55 : #define _bvt(a,b) a##b##_t
56 : #define __bvt(a,b) _bvt(a,b)
57 : #define BVT(a) __bvt(a,BIHASH_TYPE)
58 :
59 : #define _bvs(a,b) struct a##b
60 : #define __bvs(a,b) _bvs(a,b)
61 : #define BVS(a) __bvs(a,BIHASH_TYPE)
62 :
63 : #if _LP64 == 0
64 : #define OVERFLOW_ASSERT(x) ASSERT(((x) & 0xFFFFFFFF00000000ULL) == 0)
65 : #define u64_to_pointer(x) (void *)(u32)((x))
66 : #define pointer_to_u64(x) (u64)(u32)((x))
67 : #else
68 : #define OVERFLOW_ASSERT(x)
69 : #define u64_to_pointer(x) (void *)((x))
70 : #define pointer_to_u64(x) (u64)((x))
71 : #endif
72 :
73 : typedef struct BV (clib_bihash_value)
74 : {
75 : union
76 : {
77 : BVT (clib_bihash_kv) kvp[BIHASH_KVP_PER_PAGE];
78 : u64 next_free_as_u64;
79 : };
80 : } BVT (clib_bihash_value);
81 :
82 : #define BIHASH_BUCKET_OFFSET_BITS 36
83 :
84 : typedef struct
85 : {
86 : union
87 : {
88 : struct
89 : {
90 : u64 offset:BIHASH_BUCKET_OFFSET_BITS;
91 : u64 lock:1;
92 : u64 linear_search:1;
93 : u64 log2_pages:8;
94 : u64 refcnt:16;
95 : };
96 : u64 as_u64;
97 : };
98 : } BVT (clib_bihash_bucket);
99 :
100 : STATIC_ASSERT_SIZEOF (BVT (clib_bihash_bucket), sizeof (u64));
101 :
102 : /* *INDENT-OFF* */
103 : typedef CLIB_PACKED (struct {
104 : /*
105 : * Backing store allocation. Since bihash manages its own
106 : * freelists, we simple dole out memory starting from alloc_arena[alloc_arena_next].
107 : */
108 : u64 alloc_arena_next; /* Next offset from alloc_arena to allocate, definitely NOT a constant */
109 : u64 alloc_arena_size; /* Size of the arena */
110 : u64 alloc_arena_mapped; /* Size of the mapped memory in the arena */
111 : /* Two SVM pointers stored as 8-byte integers */
112 : u64 alloc_lock_as_u64;
113 : u64 buckets_as_u64;
114 : /* freelist list-head arrays/vectors */
115 : u64 freelists_as_u64;
116 : u32 nbuckets; /* Number of buckets */
117 : /* Set when header valid */
118 : volatile u32 ready;
119 : u64 pad[1];
120 : }) BVT (clib_bihash_shared_header);
121 : /* *INDENT-ON* */
122 :
123 : STATIC_ASSERT_SIZEOF (BVT (clib_bihash_shared_header), 8 * sizeof (u64));
124 :
125 : typedef
126 : BVS (clib_bihash_alloc_chunk)
127 : {
128 : CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
129 :
130 : /* chunk size */
131 : uword size;
132 :
133 : /* pointer to the next allocation */
134 : u8 *next_alloc;
135 :
136 : /* number of bytes left in this chunk */
137 : uword bytes_left;
138 :
139 : /* doubly linked list of heap allocated chunks */
140 : BVS (clib_bihash_alloc_chunk) * prev, *next;
141 :
142 : } BVT (clib_bihash_alloc_chunk);
143 :
144 : typedef
145 : BVS (clib_bihash)
146 : {
147 : BVT (clib_bihash_bucket) * buckets;
148 : volatile u32 *alloc_lock;
149 :
150 : BVT (clib_bihash_value) ** working_copies;
151 : int *working_copy_lengths;
152 : BVT (clib_bihash_bucket) saved_bucket;
153 :
154 : u32 nbuckets;
155 : u32 log2_nbuckets;
156 : u64 memory_size;
157 : u8 *name;
158 : format_function_t *fmt_fn;
159 : void *heap;
160 : BVT (clib_bihash_alloc_chunk) * chunks;
161 :
162 : u64 *freelists;
163 :
164 : #if BIHASH_32_64_SVM
165 : BVT (clib_bihash_shared_header) * sh;
166 : int memfd;
167 : #else
168 : BVT (clib_bihash_shared_header) sh;
169 : #endif
170 :
171 : u64 alloc_arena; /* Base of the allocation arena */
172 : volatile u8 instantiated;
173 : u8 dont_add_to_all_bihash_list;
174 :
175 : /**
176 : * A custom format function to print the Key and Value of bihash_key instead of default hexdump
177 : */
178 : format_function_t *kvp_fmt_fn;
179 :
180 : /** Optional statistics-gathering callback */
181 : #if BIHASH_ENABLE_STATS
182 : void (*inc_stats_callback) (BVS (clib_bihash) *, int stat_id, u64 count);
183 :
184 : /** Statistics callback context (e.g. address of stats data structure) */
185 : void *inc_stats_context;
186 : #endif
187 :
188 : } BVT (clib_bihash);
189 :
190 : typedef struct
191 : {
192 : BVT (clib_bihash) * h;
193 : char *name;
194 : u32 nbuckets;
195 : uword memory_size;
196 : format_function_t *kvp_fmt_fn;
197 : u8 instantiate_immediately;
198 : u8 dont_add_to_all_bihash_list;
199 : } BVT (clib_bihash_init2_args);
200 :
201 : extern void **clib_all_bihashes;
202 :
203 : #if BIHASH_32_64_SVM
204 : #undef alloc_arena_next
205 : #undef alloc_arena_size
206 : #undef alloc_arena_mapped
207 : #undef alloc_arena
208 : #undef CLIB_BIHASH_READY_MAGIC
209 : #define alloc_arena_next(h) (((h)->sh)->alloc_arena_next)
210 : #define alloc_arena_size(h) (((h)->sh)->alloc_arena_size)
211 : #define alloc_arena_mapped(h) (((h)->sh)->alloc_arena_mapped)
212 : #define alloc_arena(h) ((h)->alloc_arena)
213 : #define CLIB_BIHASH_READY_MAGIC 0xFEEDFACE
214 : #else
215 : #undef alloc_arena_next
216 : #undef alloc_arena_size
217 : #undef alloc_arena_mapped
218 : #undef alloc_arena
219 : #undef CLIB_BIHASH_READY_MAGIC
220 : #define alloc_arena_next(h) ((h)->sh.alloc_arena_next)
221 : #define alloc_arena_size(h) ((h)->sh.alloc_arena_size)
222 : #define alloc_arena_mapped(h) ((h)->sh.alloc_arena_mapped)
223 : #define alloc_arena(h) ((h)->alloc_arena)
224 : #define CLIB_BIHASH_READY_MAGIC 0
225 : #endif
226 :
227 : #ifndef BIHASH_STAT_IDS
228 : #define BIHASH_STAT_IDS 1
229 :
230 : #define foreach_bihash_stat \
231 : _(alloc_add) \
232 : _(add) \
233 : _(split_add) \
234 : _(replace) \
235 : _(update) \
236 : _(del) \
237 : _(del_free) \
238 : _(linear) \
239 : _(resplit) \
240 : _(working_copy_lost) \
241 : _(splits) /* must be last */
242 :
243 : typedef enum
244 : {
245 : #define _(a) BIHASH_STAT_##a,
246 : foreach_bihash_stat
247 : #undef _
248 : BIHASH_STAT_N_STATS,
249 : } BVT (clib_bihash_stat_id);
250 : #endif /* BIHASH_STAT_IDS */
251 :
252 6554177 : static inline void BV (clib_bihash_increment_stat) (BVT (clib_bihash) * h,
253 : int stat_id, u64 count)
254 : {
255 : #if BIHASH_ENABLE_STATS
256 6201220 : if (PREDICT_FALSE (h->inc_stats_callback != 0))
257 6201220 : h->inc_stats_callback (h, stat_id, count);
258 : #endif
259 6554177 : }
260 :
261 : #if BIHASH_ENABLE_STATS
262 3 : static inline void BV (clib_bihash_set_stats_callback)
263 : (BVT (clib_bihash) * h, void (*cb) (BVT (clib_bihash) *, int, u64),
264 : void *ctx)
265 : {
266 3 : h->inc_stats_callback = cb;
267 3 : h->inc_stats_context = ctx;
268 3 : }
269 : #endif
270 :
271 :
272 2092442 : static inline void BV (clib_bihash_alloc_lock) (BVT (clib_bihash) * h)
273 : {
274 5277752 : while (__atomic_test_and_set (h->alloc_lock, __ATOMIC_ACQUIRE))
275 3185307 : CLIB_PAUSE ();
276 2092445 : }
277 :
278 2092445 : static inline void BV (clib_bihash_alloc_unlock) (BVT (clib_bihash) * h)
279 : {
280 2092445 : __atomic_clear (h->alloc_lock, __ATOMIC_RELEASE);
281 2092445 : }
282 :
283 6473729 : static inline void BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b)
284 : {
285 : /* *INDENT-OFF* */
286 6473729 : BVT (clib_bihash_bucket) mask = { .lock = 1 };
287 : /* *INDENT-ON* */
288 : u64 old;
289 :
290 8408769 : try_again:
291 8408769 : old = clib_atomic_fetch_or (&b->as_u64, mask.as_u64);
292 :
293 8408769 : if (PREDICT_FALSE (old & mask.as_u64))
294 : {
295 : /* somebody else flipped the bit, try again */
296 1935020 : CLIB_PAUSE ();
297 1935040 : goto try_again;
298 : }
299 6473749 : }
300 :
301 4383161 : static inline void BV (clib_bihash_unlock_bucket)
302 : (BVT (clib_bihash_bucket) * b)
303 : {
304 4383161 : b->lock = 0;
305 4383161 : }
306 :
307 27541554 : static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h,
308 : uword offset)
309 : {
310 27541554 : u8 *hp = (u8 *) (uword) alloc_arena (h);
311 27541554 : u8 *vp = hp + offset;
312 :
313 27541554 : return (void *) vp;
314 : }
315 :
316 1353318282 : static inline int BV (clib_bihash_bucket_is_empty)
317 : (BVT (clib_bihash_bucket) * b)
318 : {
319 : /* Note: applied to locked buckets, test offset */
320 : if (BIHASH_KVP_AT_BUCKET_LEVEL == 0)
321 478195890 : return b->offset == 0;
322 : else
323 875122392 : return (b->log2_pages == 0 && b->refcnt == 1);
324 : }
325 :
326 153371958 : static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h,
327 : void *v)
328 : {
329 : u8 *hp, *vp;
330 :
331 153371958 : hp = (u8 *) (uword) alloc_arena (h);
332 153371958 : vp = (u8 *) v;
333 :
334 153371958 : return vp - hp;
335 : }
336 :
337 : #define BIHASH_ADD 1
338 : #define BIHASH_DEL 0
339 :
340 : void BV (clib_bihash_init)
341 : (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size);
342 :
343 : void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a);
344 :
345 : #if BIHASH_32_64_SVM
346 : void BV (clib_bihash_initiator_init_svm)
347 : (BVT (clib_bihash) * h, char *name, u32 nbuckets, u64 memory_size);
348 : void BV (clib_bihash_responder_init_svm)
349 : (BVT (clib_bihash) * h, char *name, int fd);
350 : #endif
351 :
352 : void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
353 : format_function_t * kvp_fmt_fn);
354 :
355 : void BV (clib_bihash_free) (BVT (clib_bihash) * h);
356 :
357 : int BV (clib_bihash_add_del) (BVT (clib_bihash) * h,
358 : BVT (clib_bihash_kv) * add_v, int is_add);
359 :
360 : int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h,
361 : BVT (clib_bihash_kv) * add_v, u64 hash,
362 : int is_add);
363 : int BV (clib_bihash_add_or_overwrite_stale) (BVT (clib_bihash) * h,
364 : BVT (clib_bihash_kv) * add_v,
365 : int (*is_stale_cb) (BVT
366 : (clib_bihash_kv)
367 : *, void *),
368 : void *arg);
369 : int BV (clib_bihash_add_with_overwrite_cb) (
370 : BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
371 : void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *arg);
372 : int BV (clib_bihash_search) (BVT (clib_bihash) * h,
373 : BVT (clib_bihash_kv) * search_v,
374 : BVT (clib_bihash_kv) * return_v);
375 :
376 : int BV (clib_bihash_is_initialised) (const BVT (clib_bihash) * h);
377 :
378 : #define BIHASH_WALK_STOP 0
379 : #define BIHASH_WALK_CONTINUE 1
380 :
381 : typedef
382 : int (*BV (clib_bihash_foreach_key_value_pair_cb)) (BVT (clib_bihash_kv) *,
383 : void *);
384 : void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h,
385 : BV
386 : (clib_bihash_foreach_key_value_pair_cb)
387 : cb, void *arg);
388 : void *clib_all_bihash_set_heap (void);
389 : void clib_bihash_copied (void *dst, void *src);
390 :
391 : format_function_t BV (format_bihash);
392 : format_function_t BV (format_bihash_kvp);
393 : format_function_t BV (format_bihash_lru);
394 :
395 : static inline
396 : BVT (clib_bihash_bucket) *
397 1537283025 : BV (clib_bihash_get_bucket) (BVT (clib_bihash) * h, u64 hash)
398 : {
399 : #if BIHASH_KVP_AT_BUCKET_LEVEL
400 : uword offset;
401 1059146280 : offset = (hash & (h->nbuckets - 1));
402 1059146280 : offset = offset * (sizeof (BVT (clib_bihash_bucket))
403 : + (BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv))));
404 1059146280 : return ((BVT (clib_bihash_bucket) *) (((u8 *) h->buckets) + offset));
405 : #else
406 478136745 : return h->buckets + (hash & (h->nbuckets - 1));
407 : #endif
408 : }
409 :
410 11415580 : static inline int BV (clib_bihash_search_inline_with_hash)
411 : (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * key_result)
412 : {
413 : BVT (clib_bihash_kv) rv;
414 : BVT (clib_bihash_value) * v;
415 : BVT (clib_bihash_bucket) * b;
416 : int i, limit;
417 :
418 : /* *INDENT-OFF* */
419 : static const BVT (clib_bihash_bucket) mask = {
420 : .linear_search = 1,
421 : .log2_pages = -1
422 : };
423 : /* *INDENT-ON* */
424 :
425 : #if BIHASH_LAZY_INSTANTIATE
426 7444 : if (PREDICT_FALSE (h->instantiated == 0))
427 33 : return -1;
428 : #endif
429 :
430 11415547 : b = BV (clib_bihash_get_bucket) (h, hash);
431 :
432 11415547 : if (PREDICT_FALSE (BV (clib_bihash_bucket_is_empty) (b)))
433 8455 : return -1;
434 :
435 11407094 : if (PREDICT_FALSE (b->lock))
436 : {
437 0 : volatile BVT (clib_bihash_bucket) * bv = b;
438 0 : while (bv->lock)
439 0 : CLIB_PAUSE ();
440 : }
441 :
442 11407094 : v = BV (clib_bihash_get_value) (h, b->offset);
443 :
444 : /* If the bucket has unresolvable collisions, use linear search */
445 11407094 : limit = BIHASH_KVP_PER_PAGE;
446 :
447 11407094 : if (PREDICT_FALSE (b->as_u64 & mask.as_u64))
448 : {
449 0 : if (PREDICT_FALSE (b->linear_search))
450 0 : limit <<= b->log2_pages;
451 : else
452 0 : v += extract_bits (hash, h->log2_nbuckets, b->log2_pages);
453 : }
454 :
455 11407126 : for (i = 0; i < limit; i++)
456 : {
457 11407123 : if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key))
458 : {
459 11407091 : rv = v->kvp[i];
460 11407091 : if (BV (clib_bihash_is_free) (&rv))
461 9 : return -1;
462 11407082 : *key_result = rv;
463 11407082 : return 0;
464 : }
465 : }
466 3 : return -1;
467 : }
468 :
469 11415580 : static inline int BV (clib_bihash_search_inline)
470 : (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result)
471 : {
472 : u64 hash;
473 :
474 11415580 : hash = BV (clib_bihash_hash) (key_result);
475 :
476 11415580 : return BV (clib_bihash_search_inline_with_hash) (h, hash, key_result);
477 : }
478 :
479 11096 : static inline void BV (clib_bihash_prefetch_bucket)
480 : (BVT (clib_bihash) * h, u64 hash)
481 : {
482 11096 : CLIB_PREFETCH (BV (clib_bihash_get_bucket) (h, hash),
483 : BIHASH_BUCKET_PREFETCH_CACHE_LINES * CLIB_CACHE_LINE_BYTES,
484 : LOAD);
485 11096 : }
486 :
487 11609 : static inline void BV (clib_bihash_prefetch_data)
488 : (BVT (clib_bihash) * h, u64 hash)
489 : {
490 : BVT (clib_bihash_value) * v;
491 : BVT (clib_bihash_bucket) * b;
492 :
493 : #if BIHASH_LAZY_INSTANTIATE
494 3968 : if (PREDICT_FALSE (h->instantiated == 0))
495 838 : return;
496 : #endif
497 :
498 10771 : b = BV (clib_bihash_get_bucket) (h, hash);
499 :
500 10771 : if (PREDICT_FALSE (BV (clib_bihash_bucket_is_empty) (b)))
501 8354 : return;
502 :
503 2417 : v = BV (clib_bihash_get_value) (h, b->offset);
504 :
505 2417 : if (PREDICT_FALSE (b->log2_pages && b->linear_search == 0))
506 88 : v += extract_bits (hash, h->log2_nbuckets, b->log2_pages);
507 :
508 2417 : CLIB_PREFETCH (v, BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv)),
509 : LOAD);
510 : }
511 :
512 11334724 : static inline int BV (clib_bihash_search_inline_2_with_hash)
513 : (BVT (clib_bihash) * h,
514 : u64 hash, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
515 : {
516 : BVT (clib_bihash_kv) rv;
517 : BVT (clib_bihash_value) * v;
518 : BVT (clib_bihash_bucket) * b;
519 : int i, limit;
520 :
521 : /* *INDENT-OFF* */
522 : static const BVT (clib_bihash_bucket) mask = {
523 : .linear_search = 1,
524 : .log2_pages = -1
525 : };
526 : /* *INDENT-ON* */
527 :
528 11334724 : ASSERT (valuep);
529 :
530 : #if BIHASH_LAZY_INSTANTIATE
531 10801728 : if (PREDICT_FALSE (h->instantiated == 0))
532 2138 : return -1;
533 : #endif
534 :
535 11332586 : b = BV (clib_bihash_get_bucket) (h, hash);
536 :
537 11332387 : if (PREDICT_FALSE (BV (clib_bihash_bucket_is_empty) (b)))
538 3209754 : return -1;
539 :
540 8123940 : if (PREDICT_FALSE (b->lock))
541 : {
542 0 : volatile BVT (clib_bihash_bucket) * bv = b;
543 0 : while (bv->lock)
544 0 : CLIB_PAUSE ();
545 : }
546 :
547 8123940 : v = BV (clib_bihash_get_value) (h, b->offset);
548 :
549 : /* If the bucket has unresolvable collisions, use linear search */
550 8123922 : limit = BIHASH_KVP_PER_PAGE;
551 :
552 8123922 : if (PREDICT_FALSE (b->as_u64 & mask.as_u64))
553 : {
554 364229 : if (PREDICT_FALSE (b->linear_search))
555 1771 : limit <<= b->log2_pages;
556 : else
557 362458 : v += extract_bits (hash, h->log2_nbuckets, b->log2_pages);
558 : }
559 :
560 9498836 : for (i = 0; i < limit; i++)
561 : {
562 9425434 : if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
563 : {
564 8050297 : rv = v->kvp[i];
565 8050297 : if (BV (clib_bihash_is_free) (&rv))
566 60 : return -1;
567 8050258 : *valuep = rv;
568 8050258 : return 0;
569 : }
570 : }
571 73402 : return -1;
572 : }
573 :
574 11322869 : static inline int BV (clib_bihash_search_inline_2)
575 : (BVT (clib_bihash) * h,
576 : BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
577 : {
578 : u64 hash;
579 :
580 11322869 : hash = BV (clib_bihash_hash) (search_key);
581 :
582 11322250 : return BV (clib_bihash_search_inline_2_with_hash) (h, hash, search_key,
583 : valuep);
584 : }
585 :
586 :
587 : #endif /* __included_bihash_template_h__ */
588 :
589 : /** @endcond */
590 :
591 : /*
592 : * fd.io coding-style-patch-verification: ON
593 : *
594 : * Local Variables:
595 : * eval: (c-set-style "gnu")
596 : * End:
597 : */
|
