crypto/bcmfs: add queue pair management
[dpdk.git] / lib / librte_member / rte_member_vbf.c
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_memory.h>
10 #include <rte_errno.h>
11 #include <rte_log.h>
12
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 rte_member_create_vbf(struct rte_member_setsum *ss,
30                 const struct rte_member_parameters *params)
31 {
32
33         if (params->num_set > RTE_MEMBER_MAX_BF ||
34                         !rte_is_power_of_2(params->num_set) ||
35                         params->num_keys == 0 ||
36                         params->false_positive_rate == 0 ||
37                         params->false_positive_rate > 1) {
38                 rte_errno = EINVAL;
39                 RTE_MEMBER_LOG(ERR, "Membership vBF create with invalid parameters\n");
40                 return -EINVAL;
41         }
42
43         /* We assume expected keys evenly distribute to all BFs */
44         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         float fp_one_bf = 1 - pow((1 - params->false_positive_rate),
56                                         1.0 / ss->num_set);
57
58         if (fp_one_bf == 0) {
59                 rte_errno = EINVAL;
60                 RTE_MEMBER_LOG(ERR, "Membership BF false positive rate is too small\n");
61                 return -EINVAL;
62         }
63
64         uint32_t bits = ceil((num_keys_per_bf *
65                                 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         ss->bits = rte_align32pow2(bits);
70
71         ss->num_hashes = (uint32_t)(log(2.0) * bits / num_keys_per_bf);
72         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         float new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
80                                         ss->num_hashes)), ss->num_hashes);
81         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         int tmp_num_hash = ss->num_hashes;
88
89         while (tmp_num_hash > 1) {
90                 float tmp_fp = new_fp;
91
92                 tmp_num_hash--;
93                 new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
94                                         tmp_num_hash)), tmp_num_hash);
95                 new_fp = 1 - pow((1 - new_fp), ss->num_set);
96
97                 if (new_fp > params->false_positive_rate) {
98                         new_fp = tmp_fp;
99                         tmp_num_hash++;
100                         break;
101                 }
102         }
103
104         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         ss->mul_shift = __builtin_ctzl(ss->num_set);
113         ss->div_shift = __builtin_ctzl(32 >> ss->mul_shift);
114
115         RTE_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\n",
119                 num_keys_per_bf, ss->bits, ss->num_hashes, fp_one_bf, new_fp);
120
121         ss->table = rte_zmalloc_socket(NULL, ss->num_set * (ss->bits >> 3),
122                                         RTE_CACHE_LINE_SIZE, ss->socket_id);
123         if (ss->table == NULL)
124                 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         uint32_t *vbf = ss->table;
133         uint32_t n = ss->num_set;
134         uint32_t div_shift = ss->div_shift;
135         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         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         return (vbf[bit_loc >> div_shift] >>
146                         ((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         uint32_t *vbf = ss->table;
153         uint32_t div_shift = ss->div_shift;
154         uint32_t mul_shift = ss->mul_shift;
155         uint32_t a = 32 >> mul_shift;
156
157         vbf[bit_loc >> div_shift] |=
158                         1UL << (((bit_loc & (a - 1)) << mul_shift) + set - 1);
159 }
160
161 int
162 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         uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
167         uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
168                                                 ss->sec_hash_seed);
169         uint32_t mask = ~0;
170         uint32_t bit_loc;
171
172         for (j = 0; j < ss->num_hashes; j++) {
173                 bit_loc = (h1 + j * h2) & ss->bit_mask;
174                 mask &= test_bit(bit_loc, ss);
175         }
176
177         if (mask) {
178                 *set_id = __builtin_ctzl(mask) + 1;
179                 return 1;
180         }
181
182         *set_id = RTE_MEMBER_NO_MATCH;
183         return 0;
184 }
185
186 uint32_t
187 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         for (i = 0; i < num_keys; i++)
197                 h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
198                                                 ss->prim_hash_seed);
199         for (i = 0; i < num_keys; i++)
200                 h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
201                                                 ss->sec_hash_seed);
202         for (i = 0; i < num_keys; i++) {
203                 mask[i] = ~0;
204                 for (k = 0; k < ss->num_hashes; k++) {
205                         bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
206                         mask[i] &= test_bit(bit_loc, ss);
207                 }
208         }
209         for (i = 0; i < num_keys; i++) {
210                 if (mask[i]) {
211                         set_ids[i] = __builtin_ctzl(mask[i]) + 1;
212                         num_matches++;
213                 } else
214                         set_ids[i] = RTE_MEMBER_NO_MATCH;
215         }
216         return num_matches;
217 }
218
219 uint32_t
220 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         uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
227         uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
228                                                 ss->sec_hash_seed);
229         uint32_t mask = ~0;
230         uint32_t bit_loc;
231
232         for (j = 0; j < ss->num_hashes; j++) {
233                 bit_loc = (h1 + j * h2) & ss->bit_mask;
234                 mask &= test_bit(bit_loc, ss);
235         }
236         while (mask) {
237                 uint32_t loc = __builtin_ctzl(mask);
238                 set_id[num_matches] = loc + 1;
239                 num_matches++;
240                 if (num_matches >= match_per_key)
241                         return num_matches;
242                 mask &= ~(1UL << loc);
243         }
244         return num_matches;
245 }
246
247 uint32_t
248 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         for (i = 0; i < num_keys; i++)
261                 h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
262                                                 ss->prim_hash_seed);
263         for (i = 0; i < num_keys; i++)
264                 h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
265                                                 ss->sec_hash_seed);
266         for (i = 0; i < num_keys; i++) {
267                 mask[i] = ~0;
268                 for (k = 0; k < ss->num_hashes; k++) {
269                         bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
270                         mask[i] &= test_bit(bit_loc, ss);
271                 }
272         }
273         for (i = 0; i < num_keys; i++) {
274                 match_cnt_t = 0;
275                 while (mask[i]) {
276                         uint32_t loc = __builtin_ctzl(mask[i]);
277                         set_ids[i * match_per_key + match_cnt_t] = loc + 1;
278                         match_cnt_t++;
279                         if (match_cnt_t >= match_per_key)
280                                 break;
281                         mask[i] &= ~(1UL << loc);
282                 }
283                 match_count[i] = match_cnt_t;
284                 if (match_cnt_t != 0)
285                         num_matches++;
286         }
287         return num_matches;
288 }
289
290 int
291 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         if (set_id > ss->num_set || set_id == RTE_MEMBER_NO_MATCH)
298                 return -EINVAL;
299
300         h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
301         h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t), ss->sec_hash_seed);
302
303         for (i = 0; i < ss->num_hashes; i++) {
304                 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 rte_member_free_vbf(struct rte_member_setsum *ss)
312 {
313         rte_free(ss->table);
314 }
315
316 void
317 rte_member_reset_vbf(const struct rte_member_setsum *ss)
318 {
319         uint32_t *vbf = ss->table;
320         memset(vbf, 0, (ss->num_set * ss->bits) >> 3);
321 }