FD.io VPP  v16.09
Vector Packet Processing
bihash_template.h
Go to the documentation of this file.
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 
30 #ifndef BIHASH_TYPE
31 #error BIHASH_TYPE not defined
32 #endif
33 
34 #define _bv(a,b) a##b
35 #define __bv(a,b) _bv(a,b)
36 #define BV(a) __bv(a,BIHASH_TYPE)
37 
38 #define _bvt(a,b) a##b##_t
39 #define __bvt(a,b) _bvt(a,b)
40 #define BVT(a) __bvt(a,BIHASH_TYPE)
41 
42 typedef struct BV (clib_bihash_value)
43 {
44  union
45  {
46  BVT (clib_bihash_kv) kvp[BIHASH_KVP_PER_PAGE];
47  struct BV (clib_bihash_value) * next_free;
48  };
49 } BVT (clib_bihash_value);
50 
51 /*
52  * This is shared across all uses of the template, so it needs
53  * a "personal" #include recursion block
54  */
55 #ifndef __defined_clib_bihash_bucket_t__
56 #define __defined_clib_bihash_bucket_t__
57 typedef struct
58 {
59  union
60  {
61  struct
62  {
63  u32 offset;
64  u8 pad[3];
65  u8 log2_pages;
66  };
67  u64 as_u64;
68  };
70 #endif /* __defined_clib_bihash_bucket_t__ */
71 
72 typedef struct
73 {
74  BVT (clib_bihash_value) * values;
75  clib_bihash_bucket_t *buckets;
76  volatile u32 *writer_lock;
77 
78  BVT (clib_bihash_value) ** working_copies;
79  clib_bihash_bucket_t saved_bucket;
80 
81  u32 nbuckets;
82  u32 log2_nbuckets;
83  u8 *name;
84 
85  BVT (clib_bihash_value) ** freelists;
86  void *mheap;
87 
88 } BVT (clib_bihash);
89 
90 
91 static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h,
92  uword offset)
93 {
94  u8 *hp = h->mheap;
95  u8 *vp = hp + offset;
96 
97  return (void *) vp;
98 }
99 
100 static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h,
101  void *v)
102 {
103  u8 *hp, *vp;
104 
105  hp = (u8 *) h->mheap;
106  vp = (u8 *) v;
107 
108  ASSERT ((vp - hp) < 0x100000000ULL);
109  return vp - hp;
110 }
111 
112 void BV (clib_bihash_init)
113  (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size);
114 
115 void BV (clib_bihash_free) (BVT (clib_bihash) * h);
116 
117 int BV (clib_bihash_add_del) (BVT (clib_bihash) * h,
118  BVT (clib_bihash_kv) * add_v, int is_add);
119 int BV (clib_bihash_search) (BVT (clib_bihash) * h,
120  BVT (clib_bihash_kv) * search_v,
121  BVT (clib_bihash_kv) * return_v);
122 
123 void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h,
124  void *callback, void *arg);
125 
126 format_function_t BV (format_bihash);
127 format_function_t BV (format_bihash_kvp);
128 
129 
130 static inline int BV (clib_bihash_search_inline)
131  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * kvp)
132 {
133  u64 hash;
134  u32 bucket_index;
135  uword value_index;
136  BVT (clib_bihash_value) * v;
138  int i;
139 
140  hash = BV (clib_bihash_hash) (kvp);
141 
142  bucket_index = hash & (h->nbuckets - 1);
143  b = &h->buckets[bucket_index];
144 
145  if (b->offset == 0)
146  return -1;
147 
148  hash >>= h->log2_nbuckets;
149 
150  v = BV (clib_bihash_get_value) (h, b->offset);
151  value_index = hash & ((1 << b->log2_pages) - 1);
152  v += value_index;
153 
154  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
155  {
156  if (BV (clib_bihash_key_compare) (v->kvp[i].key, kvp->key))
157  {
158  *kvp = v->kvp[i];
159  return 0;
160  }
161  }
162  return -1;
163 }
164 
165 static inline int BV (clib_bihash_search_inline_2)
166  (BVT (clib_bihash) * h,
167  BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
168 {
169  u64 hash;
170  u32 bucket_index;
171  uword value_index;
172  BVT (clib_bihash_value) * v;
174  int i;
175 
176  ASSERT (valuep);
177 
178  hash = BV (clib_bihash_hash) (search_key);
179 
180  bucket_index = hash & (h->nbuckets - 1);
181  b = &h->buckets[bucket_index];
182 
183  if (b->offset == 0)
184  return -1;
185 
186  hash >>= h->log2_nbuckets;
187 
188  v = BV (clib_bihash_get_value) (h, b->offset);
189  value_index = hash & ((1 << b->log2_pages) - 1);
190  v += value_index;
191 
192  for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
193  {
194  if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
195  {
196  *valuep = v->kvp[i];
197  return 0;
198  }
199  }
200  return -1;
201 }
202 
203 
204 #endif /* __included_bihash_template_h__ */
205 
206 /** @endcond */
207 
208 /*
209  * fd.io coding-style-patch-verification: ON
210  *
211  * Local Variables:
212  * eval: (c-set-style "gnu")
213  * End:
214  */
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
clib_bihash_bucket_t
Definition: bihash_doc.h:65
u64 as_u64
Definition: bihash_doc.h:63
void clib_bihash_free(clib_bihash *h)
Destroy a bounded index extensible hash table.
Fixed length block allocator.
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.
unsigned long u64
Definition: types.h:89
static uword clib_bihash_get_offset(clib_bihash *h, void *v)
Get clib mheap offset given a pointer.
#define BIHASH_KVP_PER_PAGE
Definition: bihash_24_8.h:18
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
BVT(clib_bihash)
Definition: l2_fib.c:577
void clib_bihash_foreach_key_value_pair(clib_bihash *h, void *callback, void *arg)
Visit active (key,value) pairs in a bi-hash table.
#define ASSERT(truth)
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
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
u64 uword
Definition: types.h:112
unsigned char u8
Definition: types.h:56
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.