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 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 MEMBER_LOG(ERR, "Membership vBF create with invalid parameters"); 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 MEMBER_LOG(ERR, "Membership BF false positive rate is too small"); 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 = rte_ctz32(ss->num_set); 113 ss->div_shift = rte_ctz32(32 >> ss->mul_shift); 114 115 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 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 = rte_ctz32(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] = rte_ctz32(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 = rte_ctz32(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 = rte_ctz32(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 } 322