1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2017 Intel Corporation
8 #include <rte_malloc.h>
12 #include "rte_member.h"
13 #include "rte_member_vbf.h"
16 * vBF currently implemented as a big array.
17 * The BFs have a vertical layout. Bits in same location of all bfs will stay
18 * in the same cache line.
19 * For example, if we have 32 bloom filters, we use a uint32_t array to
20 * represent all of them. array[0] represent the first location of all the
21 * bloom filters, array[1] represents the second location of all the
22 * bloom filters, etc. The advantage of this layout is to minimize the average
23 * number of memory accesses to test all bloom filters.
25 * Currently the implementation supports vBF containing 1,2,4,8,16,32 BFs.
28 rte_member_create_vbf(struct rte_member_setsum *ss,
29 const struct rte_member_parameters *params)
32 if (params->num_set > RTE_MEMBER_MAX_BF ||
33 !rte_is_power_of_2(params->num_set) ||
34 params->num_keys == 0 ||
35 params->false_positive_rate == 0 ||
36 params->false_positive_rate > 1) {
38 RTE_MEMBER_LOG(ERR, "Membership vBF create with invalid parameters\n");
42 /* We assume expected keys evenly distribute to all BFs */
43 uint32_t num_keys_per_bf = 1 + (params->num_keys - 1) / ss->num_set;
46 * Note that the false positive rate is for all BFs in the vBF
47 * such that the single BF's false positive rate needs to be
49 * Assume each BF's False positive rate is fp_one_bf. The total false
50 * positive rate is fp = 1-(1-fp_one_bf)^n.
51 * => fp_one_bf = 1 - (1-fp)^(1/n)
54 float fp_one_bf = 1 - pow((1 - params->false_positive_rate),
59 RTE_MEMBER_LOG(ERR, "Membership BF false positive rate is too small\n");
63 uint32_t bits = ceil((num_keys_per_bf *
65 log(1.0 / (pow(2.0, log(2.0)))));
67 /* We round to power of 2 for performance during lookup */
68 ss->bits = rte_align32pow2(bits);
70 ss->num_hashes = (uint32_t)(log(2.0) * bits / num_keys_per_bf);
71 ss->bit_mask = ss->bits - 1;
74 * Since we round the bits to power of 2, the final false positive
75 * rate will probably not be same as the user specified. We log the
76 * new value as debug message.
78 float new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
79 ss->num_hashes)), ss->num_hashes);
80 new_fp = 1 - pow((1 - new_fp), ss->num_set);
83 * Reduce hash function count, until we approach the user specified
84 * false-positive rate. Otherwise it is too conservative
86 int tmp_num_hash = ss->num_hashes;
88 while (tmp_num_hash > 1) {
89 float tmp_fp = new_fp;
92 new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
93 tmp_num_hash)), tmp_num_hash);
94 new_fp = 1 - pow((1 - new_fp), ss->num_set);
96 if (new_fp > params->false_positive_rate) {
103 ss->num_hashes = tmp_num_hash;
106 * To avoid multiplication and division:
107 * mul_shift is used for multiplication shift during bit test
108 * div_shift is used for division shift, to be divided by number of bits
109 * represented by a uint32_t variable
111 ss->mul_shift = __builtin_ctzl(ss->num_set);
112 ss->div_shift = __builtin_ctzl(32 >> ss->mul_shift);
114 RTE_MEMBER_LOG(DEBUG, "vector bloom filter created, "
115 "each bloom filter expects %u keys, needs %u bits, %u hashes, "
116 "with false positive rate set as %.5f, "
117 "The new calculated vBF false positive rate is %.5f\n",
118 num_keys_per_bf, ss->bits, ss->num_hashes, fp_one_bf, new_fp);
120 ss->table = rte_zmalloc_socket(NULL, ss->num_set * (ss->bits >> 3),
121 RTE_CACHE_LINE_SIZE, ss->socket_id);
122 if (ss->table == NULL)
128 static inline uint32_t
129 test_bit(uint32_t bit_loc, const struct rte_member_setsum *ss)
131 uint32_t *vbf = ss->table;
132 uint32_t n = ss->num_set;
133 uint32_t div_shift = ss->div_shift;
134 uint32_t mul_shift = ss->mul_shift;
136 * a is how many bits in one BF are represented by one 32bit
139 uint32_t a = 32 >> mul_shift;
141 * x>>b is the divide, x & (a-1) is the mod, & (1<<n-1) to mask out bits
144 return (vbf[bit_loc >> div_shift] >>
145 ((bit_loc & (a - 1)) << mul_shift)) & ((1ULL << n) - 1);
149 set_bit(uint32_t bit_loc, const struct rte_member_setsum *ss, int32_t set)
151 uint32_t *vbf = ss->table;
152 uint32_t div_shift = ss->div_shift;
153 uint32_t mul_shift = ss->mul_shift;
154 uint32_t a = 32 >> mul_shift;
156 vbf[bit_loc >> div_shift] |=
157 1UL << (((bit_loc & (a - 1)) << mul_shift) + set - 1);
161 rte_member_lookup_vbf(const struct rte_member_setsum *ss, const void *key,
162 member_set_t *set_id)
165 uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
166 uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
171 for (j = 0; j < ss->num_hashes; j++) {
172 bit_loc = (h1 + j * h2) & ss->bit_mask;
173 mask &= test_bit(bit_loc, ss);
177 *set_id = __builtin_ctzl(mask) + 1;
181 *set_id = RTE_MEMBER_NO_MATCH;
186 rte_member_lookup_bulk_vbf(const struct rte_member_setsum *ss,
187 const void **keys, uint32_t num_keys, member_set_t *set_ids)
190 uint32_t num_matches = 0;
191 uint32_t mask[RTE_MEMBER_LOOKUP_BULK_MAX];
192 uint32_t h1[RTE_MEMBER_LOOKUP_BULK_MAX], h2[RTE_MEMBER_LOOKUP_BULK_MAX];
195 for (i = 0; i < num_keys; i++)
196 h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
198 for (i = 0; i < num_keys; i++)
199 h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
201 for (i = 0; i < num_keys; i++) {
203 for (k = 0; k < ss->num_hashes; k++) {
204 bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
205 mask[i] &= test_bit(bit_loc, ss);
208 for (i = 0; i < num_keys; i++) {
210 set_ids[i] = __builtin_ctzl(mask[i]) + 1;
213 set_ids[i] = RTE_MEMBER_NO_MATCH;
219 rte_member_lookup_multi_vbf(const struct rte_member_setsum *ss,
220 const void *key, uint32_t match_per_key,
221 member_set_t *set_id)
223 uint32_t num_matches = 0;
225 uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
226 uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
231 for (j = 0; j < ss->num_hashes; j++) {
232 bit_loc = (h1 + j * h2) & ss->bit_mask;
233 mask &= test_bit(bit_loc, ss);
236 uint32_t loc = __builtin_ctzl(mask);
237 set_id[num_matches] = loc + 1;
239 if (num_matches >= match_per_key)
241 mask &= ~(1UL << loc);
247 rte_member_lookup_multi_bulk_vbf(const struct rte_member_setsum *ss,
248 const void **keys, uint32_t num_keys, uint32_t match_per_key,
249 uint32_t *match_count,
250 member_set_t *set_ids)
253 uint32_t num_matches = 0;
254 uint32_t match_cnt_t;
255 uint32_t mask[RTE_MEMBER_LOOKUP_BULK_MAX];
256 uint32_t h1[RTE_MEMBER_LOOKUP_BULK_MAX], h2[RTE_MEMBER_LOOKUP_BULK_MAX];
259 for (i = 0; i < num_keys; i++)
260 h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
262 for (i = 0; i < num_keys; i++)
263 h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
265 for (i = 0; i < num_keys; i++) {
267 for (k = 0; k < ss->num_hashes; k++) {
268 bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
269 mask[i] &= test_bit(bit_loc, ss);
272 for (i = 0; i < num_keys; i++) {
275 uint32_t loc = __builtin_ctzl(mask[i]);
276 set_ids[i * match_per_key + match_cnt_t] = loc + 1;
278 if (match_cnt_t >= match_per_key)
280 mask[i] &= ~(1UL << loc);
282 match_count[i] = match_cnt_t;
283 if (match_cnt_t != 0)
290 rte_member_add_vbf(const struct rte_member_setsum *ss,
291 const void *key, member_set_t set_id)
296 if (set_id > ss->num_set || set_id == RTE_MEMBER_NO_MATCH)
299 h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
300 h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t), ss->sec_hash_seed);
302 for (i = 0; i < ss->num_hashes; i++) {
303 bit_loc = (h1 + i * h2) & ss->bit_mask;
304 set_bit(bit_loc, ss, set_id);
310 rte_member_free_vbf(struct rte_member_setsum *ss)
316 rte_member_reset_vbf(const struct rte_member_setsum *ss)
318 uint32_t *vbf = ss->table;
319 memset(vbf, 0, (ss->num_set * ss->bits) >> 3);