FD.io VPP  v18.11-rc0-18-g2a3fb1a
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 */
85 
86 /** Get pointer to value page given its clib mheap offset */
87 static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
88 
89 /** Get clib mheap offset given a pointer */
90 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
91 
92 /** initialize a bounded index extensible hash table
93 
94  @param h - the bi-hash table to initialize
95  @param name - name of the hash table
96  @param nbuckets - the number of buckets, will be rounded up to
97 a power of two
98  @param memory_size - clib mheap size, in bytes
99 */
100 
101 void clib_bihash_init
102  (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
103 
104 /** Destroy a bounded index extensible hash table
105  @param h - the bi-hash table to free
106 */
107 
108 void clib_bihash_free (clib_bihash * h);
109 
110 /** Add or delete a (key,value) pair from a bi-hash table
111 
112  @param h - the bi-hash table to search
113  @param add_v - the (key,value) pair to add
114  @param is_add - add=1, delete=0
115  @returns 0 on success, < 0 on error
116  @note This function will replace an existing (key,value) pair if the
117  new key matches an existing key
118 */
119 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
120 
121 
122 /** Search a bi-hash table, use supplied hash code
123 
124  @param h - the bi-hash table to search
125  @param hash - the hash code
126  @param in_out_kv - (key,value) pair containing the search key
127  @returns 0 on success (with in_out_kv set), < 0 on error
128 */
130  (clib_bihash * h, u64 hash, clib_bihash_kv * in_out_kv);
131 
132 /** Search a bi-hash table
133 
134  @param h - the bi-hash table to search
135  @param in_out_kv - (key,value) pair containing the search key
136  @returns 0 on success (with in_out_kv set), < 0 on error
137 */
138 int clib_bihash_search_inline (clib_bihash * h, clib_bihash_kv * in_out_kv);
139 
140 /** Prefetch a bi-hash bucket given a hash code
141 
142  @param h - the bi-hash table to search
143  @param hash - the hash code
144  @note see also clib_bihash_hash to compute the code
145 */
146 void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash);
147 
148 /** Prefetch bi-hash (key,value) data given a hash code
149 
150  @param h - the bi-hash table to search
151  @param hash - the hash code
152  @note assumes that the bucket has been prefetched, see
153  clib_bihash_prefetch_bucket
154 */
155 void clib_bihash_prefetch_data (clib_bihash * h, u64 hash);
156 
157 /** Search a bi-hash table
158 
159  @param h - the bi-hash table to search
160  @param search_key - (key,value) pair containing the search key
161  @param valuep - (key,value) set to search result
162  @returns 0 on success (with valuep set), < 0 on error
163  @note used in situations where key modification is not desired
164 */
166  (clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep);
167 
168 /** Visit active (key,value) pairs in a bi-hash table
169 
170  @param h - the bi-hash table to search
171  @param callback - function to call with each active (key,value) pair
172  @param arg - arbitrary second argument passed to the callback function
173  First argument is the (key,value) pair to visit
174  @note Trying to supply a proper function prototype for the
175  callback function appears to be a fool's errand.
176 */
177 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
178  void *callback, void *arg);
179 
180 /*
181  * fd.io coding-style-patch-verification: ON
182  *
183  * Local Variables:
184  * eval: (c-set-style "gnu")
185  * End:
186  */
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:20
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
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
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.
u32 log2_nbuckets
lg(nbuckets)
Definition: bihash_doc.h:77
#define v
Definition: acl.c:491
u64 memory_size
Definition: vhost_user.h:110
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.
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.