FD.io VPP  v21.10.1-2-g0a485f517
Vector Packet Processing
bihash_doc.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2014 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 #error do not #include this file!
17 
18 /** \file
19 
20  Bounded-index extensible hashing. The basic algorithm performs
21  thread-safe constant-time lookups in the face of a rational number
22  of hash collisions. The computed hash code h(k) must have
23  reasonable statistics with respect to the key space. It won't do
24  to have h(k) = 0 or 1, for all values of k.
25 
26  Each bucket in the power-of-two bucket array contains the index
27  (in a private vppinfra memory heap) of the "backing store" for the
28  bucket, as well as a size field. The size field (log2_pages)
29  corresponds to 1, 2, 4, ... contiguous "pages" containing the
30  (key,value) pairs in the bucket.
31 
32  When a single page fills, we allocate two contiguous pages. We
33  recompute h(k) for each (key,value) pair, using an additional bit
34  to deal the (key, value) pairs into the "top" and "bottom" pages.
35 
36  At lookup time, we compute h(k), using lg(bucket-array-size) to
37  pick the bucket. We read the bucket to find the base of the
38  backing pages. We use an additional log2_pages' worth of bits
39  from h(k) to compute the offset of the page which will contain the
40  (key,value) pair we're trying to find.
41 */
42 
43 /** template key/value backing page structure */
44 typedef struct clib_bihash_value
45 {
46  union
47  {
48 
49  clib_bihash_kv kvp[BIHASH_KVP_PER_PAGE]; /**< the actual key/value pairs */
50  clib_bihash_value *next_free; /**< used when a KVP page (or block thereof) is on a freelist */
51  };
52 } clib_bihash_value_t
53 /** bihash bucket structure */
54  typedef struct
55 {
56  union
57  {
58  struct
59  {
60  u32 offset; /**< backing page offset in the clib memory heap */
61  u8 pad[3]; /**< log2 (size of the packing page block) */
63  };
64  u64 as_u64;
65  };
67 
68 /** A bounded index extensible hash table */
69 typedef struct
70 {
71  clib_bihash_bucket_t *buckets; /**< Hash bucket vector, power-of-two in size */
72  volatile u32 *writer_lock; /**< Writer lock, in its own cache line */
73  BVT (clib_bihash_value) ** working_copies;
74  /**< Working copies (various sizes), to avoid locking against readers */
75  clib_bihash_bucket_t saved_bucket; /**< Saved bucket pointer */
76  u32 nbuckets; /**< Number of hash buckets */
77  u32 log2_nbuckets; /**< lg(nbuckets) */
78  u8 *name; /**< hash table name */
79  BVT (clib_bihash_value) ** freelists;
80  /**< power of two freelist vector */
81  uword alloc_arena; /**< memory allocation arena */
82  uword alloc_arena_next; /**< first available mem chunk */
83  uword alloc_arena_size; /**< size of the arena */
84  uword alloc_arena_mapped; /**< size of mapped memory in the arena */
86 
87 /** Get pointer to value page given its clib mheap offset */
88 static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
89 
90 /** Get clib mheap offset given a pointer */
91 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
92 
93 /** initialize a bounded index extensible hash table
94 
95  @param h - the bi-hash table to initialize
96  @param name - name of the hash table
97  @param nbuckets - the number of buckets, will be rounded up to
98 a power of two
99  @param memory_size - clib mheap size, in bytes
100 */
101 
102 void clib_bihash_init
103  (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
104 
105 /** Destroy a bounded index extensible hash table
106  @param h - the bi-hash table to free
107 */
108 
109 void clib_bihash_free (clib_bihash * h);
110 
111 /** Add or delete a (key,value) pair from a bi-hash table
112 
113  @param h - the bi-hash table to search
114  @param add_v - the (key,value) pair to add
115  @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
116  @returns 0 on success, < 0 on error
117  @note This function will replace an existing (key,value) pair if the
118  new key matches an existing key
119 */
120 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
121 
122 
123 /** Search a bi-hash table, use supplied hash code
124 
125  @param h - the bi-hash table to search
126  @param hash - the hash code
127  @param in_out_kv - (key,value) pair containing the search key
128  @returns 0 on success (with in_out_kv set), < 0 on error
129 */
131  (clib_bihash * h, u64 hash, clib_bihash_kv * in_out_kv);
132 
133 /** Search a bi-hash table
134 
135  @param h - the bi-hash table to search
136  @param in_out_kv - (key,value) pair containing the search key
137  @returns 0 on success (with in_out_kv set), < 0 on error
138 */
139 int clib_bihash_search_inline (clib_bihash * h, clib_bihash_kv * in_out_kv);
140 
141 /** Prefetch a bi-hash bucket given a hash code
142 
143  @param h - the bi-hash table to search
144  @param hash - the hash code
145  @note see also clib_bihash_hash to compute the code
146 */
147 void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash);
148 
149 /** Prefetch bi-hash (key,value) data given a hash code
150 
151  @param h - the bi-hash table to search
152  @param hash - the hash code
153  @note assumes that the bucket has been prefetched, see
154  clib_bihash_prefetch_bucket
155 */
156 void clib_bihash_prefetch_data (clib_bihash * h, u64 hash);
157 
158 /** Search a bi-hash table
159 
160  @param h - the bi-hash table to search
161  @param search_key - (key,value) pair containing the search key
162  @param valuep - (key,value) set to search result
163  @returns 0 on success (with valuep set), < 0 on error
164  @note used in situations where key modification is not desired
165 */
167  (clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep);
168 
169 /* Calback function for walking a bihash table
170  *
171  * @param kv - KV pair visited
172  * @param ctx - Context passed to the walk
173  * @return BIHASH_WALK_CONTINUE to continue BIHASH_WALK_STOP to stop
174  */
175 typedef int (*clib_bihash_foreach_key_value_pair_cb) (clib_bihash_kv * kv,
176  void *ctx);
177 
178 /** Visit active (key,value) pairs in a bi-hash table
179 
180  @param h - the bi-hash table to search
181  @param callback - function to call with each active (key,value) pair
182  @param arg - arbitrary second argument passed to the callback function
183  First argument is the (key,value) pair to visit
184 */
185 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
187  * callback, void *arg);
188 
189 /*
190  * fd.io coding-style-patch-verification: ON
191  *
192  * Local Variables:
193  * eval: (c-set-style "gnu")
194  * End:
195  */
clib_bihash_prefetch_data
void clib_bihash_prefetch_data(clib_bihash *h, u64 hash)
Prefetch bi-hash (key,value) data given a hash code.
BIHASH_KVP_PER_PAGE
#define BIHASH_KVP_PER_PAGE
Definition: bihash_16_8.h:25
clib_bihash_value::next_free
clib_bihash_value * next_free
used when a KVP page (or block thereof) is on a freelist
Definition: bihash_doc.h:50
name
string name[64]
Definition: fib.api:25
clib_bihash_get_value
static void * clib_bihash_get_value(clib_bihash *h, uword offset)
Get pointer to value page given its clib mheap offset.
memory_size
u64 memory_size
Definition: vhost_user.h:124
h
h
Definition: flowhash_template.h:372
clib_bihash_search_inline
int clib_bihash_search_inline(clib_bihash *h, clib_bihash_kv *in_out_kv)
Search a bi-hash table.
clib_bihash_search_inline_2
int clib_bihash_search_inline_2(clib_bihash *h, clib_bihash_kv *search_key, clib_bihash_kv *valuep)
Search a bi-hash table.
clib_bihash_get_offset
static uword clib_bihash_get_offset(clib_bihash *h, void *v)
Get clib mheap offset given a pointer.
clib_bihash_init
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
clib_bihash_t::saved_bucket
clib_bihash_bucket_t saved_bucket
Saved bucket pointer.
Definition: bihash_doc.h:75
offset
struct clib_bihash_value offset
template key/value backing page structure
uword
u64 uword
Definition: types.h:112
clib_bihash_prefetch_bucket
void clib_bihash_prefetch_bucket(clib_bihash *h, u64 hash)
Prefetch a bi-hash bucket given a hash code.
clib_bihash_free
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
clib_bihash_t::writer_lock
volatile u32 * writer_lock
Writer lock, in its own cache line.
Definition: bihash_doc.h:72
BVT
BVT(clib_bihash)
The table of adjacencies indexed by the rewrite string.
Definition: l2_fib.c:1065
clib_bihash_t::log2_nbuckets
u32 log2_nbuckets
lg(nbuckets)
Definition: bihash_doc.h:77
log2_pages
u8 log2_pages
Definition: bihash_doc.h:62
clib_bihash_t::alloc_arena_next
uword alloc_arena_next
first available mem chunk
Definition: bihash_doc.h:82
clib_bihash_value
template key/value backing page structure
Definition: bihash_doc.h:44
u64
unsigned long u64
Definition: types.h:89
u32
unsigned int u32
Definition: types.h:88
clib_bihash_t::alloc_arena_size
uword alloc_arena_size
size of the arena
Definition: bihash_doc.h:83
ctx
long ctx[MAX_CONNS]
Definition: main.c:144
as_u64
u64 as_u64
Definition: bihash_doc.h:63
clib_bihash_add_del
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.
clib_bihash_t
A bounded index extensible hash table.
Definition: bihash_doc.h:69
clib_bihash_value::kvp
clib_bihash_kv kvp[BIHASH_KVP_PER_PAGE]
the actual key/value pairs
Definition: bihash_doc.h:49
clib_bihash_t::alloc_arena
uword alloc_arena
memory allocation arena
Definition: bihash_doc.h:81
clib_bihash_foreach_key_value_pair
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.
u8
unsigned char u8
Definition: types.h:56
clib_bihash_t::nbuckets
u32 nbuckets
Number of hash buckets.
Definition: bihash_doc.h:76
clib_bihash_bucket_t
clib_bihash_bucket_t
Definition: bihash_doc.h:65
clib_bihash_foreach_key_value_pair_cb
int(* clib_bihash_foreach_key_value_pair_cb)(clib_bihash_kv *kv, void *ctx)
Definition: bihash_doc.h:175
pad
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
clib_bihash_t::alloc_arena_mapped
uword alloc_arena_mapped
size of mapped memory in the arena
Definition: bihash_doc.h:84
clib_bihash_t::name
u8 * name
hash table name
Definition: bihash_doc.h:78
clib_bihash_search_inline_with_hash
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.
clib_bihash_t::buckets
clib_bihash_bucket_t * buckets
Hash bucket vector, power-of-two in size.
Definition: bihash_doc.h:71