FD.io VPP  v17.07-30-g839fa73
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  void *mheap; /**< clib memory heap */
83 
84 /** Get pointer to value page given its clib mheap offset */
85 static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
86 
87 /** Get clib mheap offset given a pointer */
88 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
89 
90 /** initialize a bounded index extensible hash table
91 
92  @param h - the bi-hash table to initialize
93  @param name - name of the hash table
94  @param nbuckets - the number of buckets, will be rounded up to
95 a power of two
96  @param memory_size - clib mheap size, in bytes
97 */
98 
100  (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
101 
102 /** Destroy a bounded index extensible hash table
103  @param h - the bi-hash table to free
104 */
105 
106 void clib_bihash_free (clib_bihash * h);
107 
108 /** Add or delete a (key,value) pair from a bi-hash table
109 
110  @param h - the bi-hash table to search
111  @param add_v - the (key,value) pair to add
112  @param is_add - add=1, delete=0
113  @returns 0 on success, < 0 on error
114  @note This function will replace an existing (key,value) pair if the
115  new key matches an existing key
116 */
117 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
118 
119 
120 /** Search a bi-hash table
121 
122  @param h - the bi-hash table to search
123  @param search_v - (key,value) pair containing the search key
124  @param return_v - (key,value) pair which matches search_v.key
125  @returns 0 on success (with return_v set), < 0 on error
126 */
127 int clib_bihash_search (clib_bihash * h,
128  clib_bihash_kv * search_v, clib_bihash_kv * return_v);
129 
130 
131 /** Visit active (key,value) pairs in a bi-hash table
132 
133  @param h - the bi-hash table to search
134  @param callback - function to call with each active (key,value) pair
135  @param arg - arbitrary second argument passed to the callback function
136  First argument is the (key,value) pair to visit
137  @note Trying to supply a proper function prototype for the
138  callback function appears to be a fool's errand.
139 */
140 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
141  void *callback, void *arg);
142 
143 /*
144  * fd.io coding-style-patch-verification: ON
145  *
146  * Local Variables:
147  * eval: (c-set-style "gnu")
148  * End:
149  */
u8 * name
hash table name
Definition: bihash_doc.h:78
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:18
u64 as_u64
Definition: bihash_doc.h:63
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
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
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 long u64
Definition: types.h:89
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:320
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
void clib_bihash_foreach_key_value_pair(clib_bihash *h, void *callback, void *arg)
Visit active (key,value) pairs in a bi-hash table.
A bounded index extensible hash table.
Definition: bihash_doc.h:69
u64 memory_size
Definition: vhost-user.h:76
void * mheap
clib memory heap
Definition: bihash_doc.h:81
unsigned int u32
Definition: types.h:88
int clib_bihash_search(clib_bihash *h, clib_bihash_kv *search_v, clib_bihash_kv *return_v)
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
u64 uword
Definition: types.h:112
template key/value backing page structure
Definition: bihash_doc.h:44
unsigned char u8
Definition: types.h:56
u32 nbuckets
Number of hash buckets.
Definition: bihash_doc.h:76
volatile u32 * writer_lock
Writer lock, in its own cache line.
Definition: bihash_doc.h:72
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.