Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2017 Intel Corporation
3 : : */
4 : :
5 : : #include <math.h>
6 : : #include <string.h>
7 : :
8 : : #include <rte_malloc.h>
9 : : #include <rte_errno.h>
10 : : #include <rte_log.h>
11 : :
12 : : #include "member.h"
13 : : #include "rte_member.h"
14 : : #include "rte_member_vbf.h"
15 : :
16 : : /*
17 : : * vBF currently implemented as a big array.
18 : : * The BFs have a vertical layout. Bits in same location of all bfs will stay
19 : : * in the same cache line.
20 : : * For example, if we have 32 bloom filters, we use a uint32_t array to
21 : : * represent all of them. array[0] represent the first location of all the
22 : : * bloom filters, array[1] represents the second location of all the
23 : : * bloom filters, etc. The advantage of this layout is to minimize the average
24 : : * number of memory accesses to test all bloom filters.
25 : : *
26 : : * Currently the implementation supports vBF containing 1,2,4,8,16,32 BFs.
27 : : */
28 : : int
29 : 4 : rte_member_create_vbf(struct rte_member_setsum *ss,
30 : : const struct rte_member_parameters *params)
31 : : {
32 : :
33 [ + - ]: 4 : if (params->num_set > RTE_MEMBER_MAX_BF ||
34 : 3 : !rte_is_power_of_2(params->num_set) ||
35 [ + + ]: 3 : params->num_keys == 0 ||
36 [ + + - + ]: 2 : params->false_positive_rate == 0 ||
37 : : params->false_positive_rate > 1) {
38 : 3 : rte_errno = EINVAL;
39 : 3 : MEMBER_LOG(ERR, "Membership vBF create with invalid parameters");
40 : 3 : return -EINVAL;
41 : : }
42 : :
43 : : /* We assume expected keys evenly distribute to all BFs */
44 : 1 : uint32_t num_keys_per_bf = 1 + (params->num_keys - 1) / ss->num_set;
45 : :
46 : : /*
47 : : * Note that the false positive rate is for all BFs in the vBF
48 : : * such that the single BF's false positive rate needs to be
49 : : * calculated.
50 : : * Assume each BF's False positive rate is fp_one_bf. The total false
51 : : * positive rate is fp = 1-(1-fp_one_bf)^n.
52 : : * => fp_one_bf = 1 - (1-fp)^(1/n)
53 : : */
54 : :
55 : 1 : float fp_one_bf = 1 - pow((1 - params->false_positive_rate),
56 : : 1.0 / ss->num_set);
57 : :
58 [ - + ]: 1 : if (fp_one_bf == 0) {
59 : 0 : rte_errno = EINVAL;
60 : 0 : MEMBER_LOG(ERR, "Membership BF false positive rate is too small");
61 : 0 : return -EINVAL;
62 : : }
63 : :
64 : 1 : uint32_t bits = ceil((num_keys_per_bf *
65 : 1 : log(fp_one_bf)) /
66 : : log(1.0 / (pow(2.0, log(2.0)))));
67 : :
68 : : /* We round to power of 2 for performance during lookup */
69 : 1 : ss->bits = rte_align32pow2(bits);
70 : :
71 : 1 : ss->num_hashes = (uint32_t)(log(2.0) * bits / num_keys_per_bf);
72 : 1 : ss->bit_mask = ss->bits - 1;
73 : :
74 : : /*
75 : : * Since we round the bits to power of 2, the final false positive
76 : : * rate will probably not be same as the user specified. We log the
77 : : * new value as debug message.
78 : : */
79 : 1 : float new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
80 : : ss->num_hashes)), ss->num_hashes);
81 : 1 : new_fp = 1 - pow((1 - new_fp), ss->num_set);
82 : :
83 : : /*
84 : : * Reduce hash function count, until we approach the user specified
85 : : * false-positive rate. Otherwise it is too conservative
86 : : */
87 : 1 : int tmp_num_hash = ss->num_hashes;
88 : :
89 [ + - ]: 5 : while (tmp_num_hash > 1) {
90 : : float tmp_fp = new_fp;
91 : :
92 : 5 : tmp_num_hash--;
93 : 5 : new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
94 : : tmp_num_hash)), tmp_num_hash);
95 : 5 : new_fp = 1 - pow((1 - new_fp), ss->num_set);
96 : :
97 [ + + ]: 5 : if (new_fp > params->false_positive_rate) {
98 : : new_fp = tmp_fp;
99 : : tmp_num_hash++;
100 : : break;
101 : : }
102 : : }
103 : :
104 : 1 : ss->num_hashes = tmp_num_hash;
105 : :
106 : : /*
107 : : * To avoid multiplication and division:
108 : : * mul_shift is used for multiplication shift during bit test
109 : : * div_shift is used for division shift, to be divided by number of bits
110 : : * represented by a uint32_t variable
111 : : */
112 : 1 : ss->mul_shift = rte_ctz32(ss->num_set);
113 : 1 : ss->div_shift = rte_ctz32(32 >> ss->mul_shift);
114 : :
115 : 1 : MEMBER_LOG(DEBUG, "vector bloom filter created, "
116 : : "each bloom filter expects %u keys, needs %u bits, %u hashes, "
117 : : "with false positive rate set as %.5f, "
118 : : "The new calculated vBF false positive rate is %.5f",
119 : : num_keys_per_bf, ss->bits, ss->num_hashes, fp_one_bf, new_fp);
120 : :
121 : 2 : ss->table = rte_zmalloc_socket(NULL, ss->num_set * (ss->bits >> 3),
122 : 1 : RTE_CACHE_LINE_SIZE, ss->socket_id);
123 [ - + ]: 1 : if (ss->table == NULL)
124 : 0 : return -ENOMEM;
125 : :
126 : : return 0;
127 : : }
128 : :
129 : : static inline uint32_t
130 : : test_bit(uint32_t bit_loc, const struct rte_member_setsum *ss)
131 : : {
132 : 150 : uint32_t *vbf = ss->table;
133 : 150 : uint32_t n = ss->num_set;
134 : 150 : uint32_t div_shift = ss->div_shift;
135 : 150 : uint32_t mul_shift = ss->mul_shift;
136 : : /*
137 : : * a is how many bits in one BF are represented by one 32bit
138 : : * variable.
139 : : */
140 : 150 : uint32_t a = 32 >> mul_shift;
141 : : /*
142 : : * x>>b is the divide, x & (a-1) is the mod, & (1<<n-1) to mask out bits
143 : : * we do not need
144 : : */
145 : 150 : return (vbf[bit_loc >> div_shift] >>
146 : 150 : ((bit_loc & (a - 1)) << mul_shift)) & ((1ULL << n) - 1);
147 : : }
148 : :
149 : : static inline void
150 : : set_bit(uint32_t bit_loc, const struct rte_member_setsum *ss, int32_t set)
151 : : {
152 : 225 : uint32_t *vbf = ss->table;
153 : 225 : uint32_t div_shift = ss->div_shift;
154 : 225 : uint32_t mul_shift = ss->mul_shift;
155 : 225 : uint32_t a = 32 >> mul_shift;
156 : :
157 : 225 : vbf[bit_loc >> div_shift] |=
158 : 225 : 1UL << (((bit_loc & (a - 1)) << mul_shift) + set - 1);
159 : : }
160 : :
161 : : int
162 : 10 : rte_member_lookup_vbf(const struct rte_member_setsum *ss, const void *key,
163 : : member_set_t *set_id)
164 : : {
165 : : uint32_t j;
166 : 10 : uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
167 : 10 : uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
168 : 10 : ss->sec_hash_seed);
169 : : uint32_t mask = ~0;
170 : : uint32_t bit_loc;
171 : :
172 [ + + ]: 60 : for (j = 0; j < ss->num_hashes; j++) {
173 : 50 : bit_loc = (h1 + j * h2) & ss->bit_mask;
174 : 50 : mask &= test_bit(bit_loc, ss);
175 : : }
176 : :
177 [ + - ]: 10 : if (mask) {
178 : 10 : *set_id = rte_ctz32(mask) + 1;
179 : 10 : return 1;
180 : : }
181 : :
182 : 0 : *set_id = RTE_MEMBER_NO_MATCH;
183 : 0 : return 0;
184 : : }
185 : :
186 : : uint32_t
187 : 2 : rte_member_lookup_bulk_vbf(const struct rte_member_setsum *ss,
188 : : const void **keys, uint32_t num_keys, member_set_t *set_ids)
189 : : {
190 : : uint32_t i, k;
191 : : uint32_t num_matches = 0;
192 : : uint32_t mask[RTE_MEMBER_LOOKUP_BULK_MAX];
193 : : uint32_t h1[RTE_MEMBER_LOOKUP_BULK_MAX], h2[RTE_MEMBER_LOOKUP_BULK_MAX];
194 : : uint32_t bit_loc;
195 : :
196 [ + + ]: 12 : for (i = 0; i < num_keys; i++)
197 : 10 : h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
198 : 10 : ss->prim_hash_seed);
199 [ + + ]: 12 : for (i = 0; i < num_keys; i++)
200 : 10 : h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
201 : 10 : ss->sec_hash_seed);
202 [ + + ]: 12 : for (i = 0; i < num_keys; i++) {
203 : 10 : mask[i] = ~0;
204 [ + + ]: 60 : for (k = 0; k < ss->num_hashes; k++) {
205 : 50 : bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
206 : 50 : mask[i] &= test_bit(bit_loc, ss);
207 : : }
208 : : }
209 [ + + ]: 12 : for (i = 0; i < num_keys; i++) {
210 [ + - ]: 10 : if (mask[i]) {
211 : 10 : set_ids[i] = rte_ctz32(mask[i]) + 1;
212 : 10 : num_matches++;
213 : : } else
214 : 0 : set_ids[i] = RTE_MEMBER_NO_MATCH;
215 : : }
216 : 2 : return num_matches;
217 : : }
218 : :
219 : : uint32_t
220 : 5 : rte_member_lookup_multi_vbf(const struct rte_member_setsum *ss,
221 : : const void *key, uint32_t match_per_key,
222 : : member_set_t *set_id)
223 : : {
224 : : uint32_t num_matches = 0;
225 : : uint32_t j;
226 : 5 : uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
227 : 5 : uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
228 : 5 : ss->sec_hash_seed);
229 : : uint32_t mask = ~0;
230 : : uint32_t bit_loc;
231 : :
232 [ + + ]: 30 : for (j = 0; j < ss->num_hashes; j++) {
233 : 25 : bit_loc = (h1 + j * h2) & ss->bit_mask;
234 : 25 : mask &= test_bit(bit_loc, ss);
235 : : }
236 [ + + ]: 45 : while (mask) {
237 : : uint32_t loc = rte_ctz32(mask);
238 : 40 : set_id[num_matches] = loc + 1;
239 : 40 : num_matches++;
240 [ - + ]: 40 : if (num_matches >= match_per_key)
241 : 0 : return num_matches;
242 : 40 : mask &= ~(1UL << loc);
243 : : }
244 : : return num_matches;
245 : : }
246 : :
247 : : uint32_t
248 : 1 : rte_member_lookup_multi_bulk_vbf(const struct rte_member_setsum *ss,
249 : : const void **keys, uint32_t num_keys, uint32_t match_per_key,
250 : : uint32_t *match_count,
251 : : member_set_t *set_ids)
252 : : {
253 : : uint32_t i, k;
254 : : uint32_t num_matches = 0;
255 : : uint32_t match_cnt_t;
256 : : uint32_t mask[RTE_MEMBER_LOOKUP_BULK_MAX];
257 : : uint32_t h1[RTE_MEMBER_LOOKUP_BULK_MAX], h2[RTE_MEMBER_LOOKUP_BULK_MAX];
258 : : uint32_t bit_loc;
259 : :
260 [ + + ]: 6 : for (i = 0; i < num_keys; i++)
261 : 5 : h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
262 : 5 : ss->prim_hash_seed);
263 [ + + ]: 6 : for (i = 0; i < num_keys; i++)
264 : 5 : h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
265 : 5 : ss->sec_hash_seed);
266 [ + + ]: 6 : for (i = 0; i < num_keys; i++) {
267 : 5 : mask[i] = ~0;
268 [ + + ]: 30 : for (k = 0; k < ss->num_hashes; k++) {
269 : 25 : bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
270 : 25 : mask[i] &= test_bit(bit_loc, ss);
271 : : }
272 : : }
273 [ + + ]: 6 : for (i = 0; i < num_keys; i++) {
274 : : match_cnt_t = 0;
275 [ + + ]: 45 : while (mask[i]) {
276 : : uint32_t loc = rte_ctz32(mask[i]);
277 : 40 : set_ids[i * match_per_key + match_cnt_t] = loc + 1;
278 : 40 : match_cnt_t++;
279 [ + - ]: 40 : if (match_cnt_t >= match_per_key)
280 : : break;
281 : 40 : mask[i] &= ~(1UL << loc);
282 : : }
283 : 5 : match_count[i] = match_cnt_t;
284 [ + - ]: 5 : if (match_cnt_t != 0)
285 : 5 : num_matches++;
286 : : }
287 : 1 : return num_matches;
288 : : }
289 : :
290 : : int
291 : 45 : rte_member_add_vbf(const struct rte_member_setsum *ss,
292 : : const void *key, member_set_t set_id)
293 : : {
294 : : uint32_t i, h1, h2;
295 : : uint32_t bit_loc;
296 : :
297 [ + - + - ]: 45 : if (set_id > ss->num_set || set_id == RTE_MEMBER_NO_MATCH)
298 : : return -EINVAL;
299 : :
300 : 45 : h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
301 : 45 : h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t), ss->sec_hash_seed);
302 : :
303 [ + + ]: 270 : for (i = 0; i < ss->num_hashes; i++) {
304 : 225 : bit_loc = (h1 + i * h2) & ss->bit_mask;
305 : : set_bit(bit_loc, ss, set_id);
306 : : }
307 : : return 0;
308 : : }
309 : :
310 : : void
311 : 1 : rte_member_free_vbf(struct rte_member_setsum *ss)
312 : : {
313 : 1 : rte_free(ss->table);
314 : 1 : }
315 : :
316 : : void
317 : 1 : rte_member_reset_vbf(const struct rte_member_setsum *ss)
318 : : {
319 : 1 : uint32_t *vbf = ss->table;
320 : 1 : memset(vbf, 0, (ss->num_set * ss->bits) >> 3);
321 : 1 : }
|
