FD.io VPP  v21.06
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  */
u8 * name
hash table name
Definition: bihash_doc.h:78
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.
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
clib_bihash_bucket_t
Definition: bihash_doc.h:65
#define BIHASH_KVP_PER_PAGE
Definition: bihash_16_8.h:25
u64 as_u64
Definition: bihash_doc.h:63
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
unsigned long u64
Definition: types.h:89
clib_bihash_bucket_t saved_bucket
Saved bucket pointer.
Definition: bihash_doc.h:75
clib_bihash_bucket_t * buckets
Hash bucket vector, power-of-two in size.
Definition: bihash_doc.h:71
string name[64]
Definition: fib.api:25
unsigned char u8
Definition: types.h:56
unsigned int u32
Definition: types.h:88
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_kv kvp[BIHASH_KVP_PER_PAGE]
the actual key/value pairs
Definition: bihash_doc.h:49
static uword clib_bihash_get_offset(clib_bihash *h, void *v)
Get clib mheap offset given a pointer.
int(* clib_bihash_foreach_key_value_pair_cb)(clib_bihash_kv *kv, void *ctx)
Definition: bihash_doc.h:175
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.
u32 log2_nbuckets
lg(nbuckets)
Definition: bihash_doc.h:77
uword alloc_arena_mapped
size of mapped memory in the arena
Definition: bihash_doc.h:84
long ctx[MAX_CONNS]
Definition: main.c:144
u64 memory_size
Definition: vhost_user.h:124
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.
BVT(clib_bihash)
The table of adjacencies indexed by the rewrite string.
Definition: l2_fib.c:1069
void clib_bihash_prefetch_data(clib_bihash *h, u64 hash)
Prefetch bi-hash (key,value) data given a hash code.
A bounded index extensible hash table.
Definition: bihash_doc.h:69
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
clib_bihash_value * next_free
used when a KVP page (or block thereof) is on a freelist
Definition: bihash_doc.h:50
template key/value backing page structure
Definition: bihash_doc.h:44
u32 nbuckets
Number of hash buckets.
Definition: bihash_doc.h:76
u64 uword
Definition: types.h:112
uword alloc_arena_size
size of the arena
Definition: bihash_doc.h:83
volatile u32 * writer_lock
Writer lock, in its own cache line.
Definition: bihash_doc.h:72
uword alloc_arena_next
first available mem chunk
Definition: bihash_doc.h:82
struct clib_bihash_value offset
template key/value backing page structure
uword alloc_arena
memory allocation arena
Definition: bihash_doc.h:81
static void * clib_bihash_get_value(clib_bihash *h, uword offset)
Get pointer to value page given its clib mheap offset.