1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2017 Intel Corporation
8 #include <rte_malloc.h>
9 #include <rte_memory.h>
10 #include <rte_errno.h>
13 #include "rte_member.h"
14 #include "rte_member_vbf.h"
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.
26 * Currently the implementation supports vBF containing 1,2,4,8,16,32 BFs.
29 rte_member_create_vbf(struct rte_member_setsum
*ss
,
30 const struct rte_member_parameters
*params
)
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) {
39 RTE_MEMBER_LOG(ERR
, "Membership vBF create with invalid parameters\n");
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
;
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
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)
55 float fp_one_bf
= 1 - pow((1 - params
->false_positive_rate
),
60 RTE_MEMBER_LOG(ERR
, "Membership BF false positive rate is too small\n");
64 uint32_t bits
= ceil((num_keys_per_bf
*
66 log(1.0 / (pow(2.0, log(2.0)))));
68 /* We round to power of 2 for performance during lookup */
69 ss
->bits
= rte_align32pow2(bits
);
71 ss
->num_hashes
= (uint32_t)(log(2.0) * bits
/ num_keys_per_bf
);
72 ss
->bit_mask
= ss
->bits
- 1;
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.
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
);
84 * Reduce hash function count, until we approach the user specified
85 * false-positive rate. Otherwise it is too conservative
87 int tmp_num_hash
= ss
->num_hashes
;
89 while (tmp_num_hash
> 1) {
90 float tmp_fp
= new_fp
;
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
);
97 if (new_fp
> params
->false_positive_rate
) {
104 ss
->num_hashes
= tmp_num_hash
;
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
112 ss
->mul_shift
= __builtin_ctzl(ss
->num_set
);
113 ss
->div_shift
= __builtin_ctzl(32 >> ss
->mul_shift
);
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
);
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
)
129 static inline uint32_t
130 test_bit(uint32_t bit_loc
, const struct rte_member_setsum
*ss
)
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
;
137 * a is how many bits in one BF are represented by one 32bit
140 uint32_t a
= 32 >> mul_shift
;
142 * x>>b is the divide, x & (a-1) is the mod, & (1<<n-1) to mask out bits
145 return (vbf
[bit_loc
>> div_shift
] >>
146 ((bit_loc
& (a
- 1)) << mul_shift
)) & ((1ULL << n
) - 1);
150 set_bit(uint32_t bit_loc
, const struct rte_member_setsum
*ss
, int32_t set
)
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
;
157 vbf
[bit_loc
>> div_shift
] |=
158 1UL << (((bit_loc
& (a
- 1)) << mul_shift
) + set
- 1);
162 rte_member_lookup_vbf(const struct rte_member_setsum
*ss
, const void *key
,
163 member_set_t
*set_id
)
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),
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
);
178 *set_id
= __builtin_ctzl(mask
) + 1;
182 *set_id
= RTE_MEMBER_NO_MATCH
;
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
)
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
];
196 for (i
= 0; i
< num_keys
; i
++)
197 h1
[i
] = MEMBER_HASH_FUNC(keys
[i
], ss
->key_len
,
199 for (i
= 0; i
< num_keys
; i
++)
200 h2
[i
] = MEMBER_HASH_FUNC(&h1
[i
], sizeof(uint32_t),
202 for (i
= 0; i
< num_keys
; i
++) {
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
);
209 for (i
= 0; i
< num_keys
; i
++) {
211 set_ids
[i
] = __builtin_ctzl(mask
[i
]) + 1;
214 set_ids
[i
] = RTE_MEMBER_NO_MATCH
;
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
)
224 uint32_t num_matches
= 0;
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),
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
);
237 uint32_t loc
= __builtin_ctzl(mask
);
238 set_id
[num_matches
] = loc
+ 1;
240 if (num_matches
>= match_per_key
)
242 mask
&= ~(1UL << loc
);
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
)
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
];
260 for (i
= 0; i
< num_keys
; i
++)
261 h1
[i
] = MEMBER_HASH_FUNC(keys
[i
], ss
->key_len
,
263 for (i
= 0; i
< num_keys
; i
++)
264 h2
[i
] = MEMBER_HASH_FUNC(&h1
[i
], sizeof(uint32_t),
266 for (i
= 0; i
< num_keys
; i
++) {
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
);
273 for (i
= 0; i
< num_keys
; i
++) {
276 uint32_t loc
= __builtin_ctzl(mask
[i
]);
277 set_ids
[i
* match_per_key
+ match_cnt_t
] = loc
+ 1;
279 if (match_cnt_t
>= match_per_key
)
281 mask
[i
] &= ~(1UL << loc
);
283 match_count
[i
] = match_cnt_t
;
284 if (match_cnt_t
!= 0)
291 rte_member_add_vbf(const struct rte_member_setsum
*ss
,
292 const void *key
, member_set_t set_id
)
297 if (set_id
> ss
->num_set
|| set_id
== RTE_MEMBER_NO_MATCH
)
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
);
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
);
311 rte_member_free_vbf(struct rte_member_setsum
*ss
)
317 rte_member_reset_vbf(const struct rte_member_setsum
*ss
)
319 uint32_t *vbf
= ss
->table
;
320 memset(vbf
, 0, (ss
->num_set
* ss
->bits
) >> 3);