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 "rte_member.h" 13 #include "rte_member_vbf.h" 14 15 /* 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. 24 * 25 * Currently the implementation supports vBF containing 1,2,4,8,16,32 BFs. 26 */ 27 int 28 rte_member_create_vbf(struct rte_member_setsum *ss, 29 const struct rte_member_parameters *params) 30 { 31 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) { 37 rte_errno = EINVAL; 38 RTE_MEMBER_LOG(ERR, "Membership vBF create with invalid parameters\n"); 39 return -EINVAL; 40 } 41 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; 44 45 /* 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 48 * calculated. 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) 52 */ 53 54 float fp_one_bf = 1 - pow((1 - params->false_positive_rate), 55 1.0 / ss->num_set); 56 57 if (fp_one_bf == 0) { 58 rte_errno = EINVAL; 59 RTE_MEMBER_LOG(ERR, "Membership BF false positive rate is too small\n"); 60 return -EINVAL; 61 } 62 63 uint32_t bits = ceil((num_keys_per_bf * 64 log(fp_one_bf)) / 65 log(1.0 / (pow(2.0, log(2.0))))); 66 67 /* We round to power of 2 for performance during lookup */ 68 ss->bits = rte_align32pow2(bits); 69 70 ss->num_hashes = (uint32_t)(log(2.0) * bits / num_keys_per_bf); 71 ss->bit_mask = ss->bits - 1; 72 73 /* 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. 77 */ 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); 81 82 /* 83 * Reduce hash function count, until we approach the user specified 84 * false-positive rate. Otherwise it is too conservative 85 */ 86 int tmp_num_hash = ss->num_hashes; 87 88 while (tmp_num_hash > 1) { 89 float tmp_fp = new_fp; 90 91 tmp_num_hash--; 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); 95 96 if (new_fp > params->false_positive_rate) { 97 new_fp = tmp_fp; 98 tmp_num_hash++; 99 break; 100 } 101 } 102 103 ss->num_hashes = tmp_num_hash; 104 105 /* 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 110 */ 111 ss->mul_shift = __builtin_ctzl(ss->num_set); 112 ss->div_shift = __builtin_ctzl(32 >> ss->mul_shift); 113 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); 119 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) 123 return -ENOMEM; 124 125 return 0; 126 } 127 128 static inline uint32_t 129 test_bit(uint32_t bit_loc, const struct rte_member_setsum *ss) 130 { 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; 135 /* 136 * a is how many bits in one BF are represented by one 32bit 137 * variable. 138 */ 139 uint32_t a = 32 >> mul_shift; 140 /* 141 * x>>b is the divide, x & (a-1) is the mod, & (1<<n-1) to mask out bits 142 * we do not need 143 */ 144 return (vbf[bit_loc >> div_shift] >> 145 ((bit_loc & (a - 1)) << mul_shift)) & ((1ULL << n) - 1); 146 } 147 148 static inline void 149 set_bit(uint32_t bit_loc, const struct rte_member_setsum *ss, int32_t set) 150 { 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; 155 156 vbf[bit_loc >> div_shift] |= 157 1UL << (((bit_loc & (a - 1)) << mul_shift) + set - 1); 158 } 159 160 int 161 rte_member_lookup_vbf(const struct rte_member_setsum *ss, const void *key, 162 member_set_t *set_id) 163 { 164 uint32_t j; 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), 167 ss->sec_hash_seed); 168 uint32_t mask = ~0; 169 uint32_t bit_loc; 170 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); 174 } 175 176 if (mask) { 177 *set_id = __builtin_ctzl(mask) + 1; 178 return 1; 179 } 180 181 *set_id = RTE_MEMBER_NO_MATCH; 182 return 0; 183 } 184 185 uint32_t 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) 188 { 189 uint32_t i, k; 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]; 193 uint32_t bit_loc; 194 195 for (i = 0; i < num_keys; i++) 196 h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len, 197 ss->prim_hash_seed); 198 for (i = 0; i < num_keys; i++) 199 h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t), 200 ss->sec_hash_seed); 201 for (i = 0; i < num_keys; i++) { 202 mask[i] = ~0; 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); 206 } 207 } 208 for (i = 0; i < num_keys; i++) { 209 if (mask[i]) { 210 set_ids[i] = __builtin_ctzl(mask[i]) + 1; 211 num_matches++; 212 } else 213 set_ids[i] = RTE_MEMBER_NO_MATCH; 214 } 215 return num_matches; 216 } 217 218 uint32_t 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) 222 { 223 uint32_t num_matches = 0; 224 uint32_t j; 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), 227 ss->sec_hash_seed); 228 uint32_t mask = ~0; 229 uint32_t bit_loc; 230 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); 234 } 235 while (mask) { 236 uint32_t loc = __builtin_ctzl(mask); 237 set_id[num_matches] = loc + 1; 238 num_matches++; 239 if (num_matches >= match_per_key) 240 return num_matches; 241 mask &= ~(1UL << loc); 242 } 243 return num_matches; 244 } 245 246 uint32_t 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) 251 { 252 uint32_t i, k; 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]; 257 uint32_t bit_loc; 258 259 for (i = 0; i < num_keys; i++) 260 h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len, 261 ss->prim_hash_seed); 262 for (i = 0; i < num_keys; i++) 263 h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t), 264 ss->sec_hash_seed); 265 for (i = 0; i < num_keys; i++) { 266 mask[i] = ~0; 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); 270 } 271 } 272 for (i = 0; i < num_keys; i++) { 273 match_cnt_t = 0; 274 while (mask[i]) { 275 uint32_t loc = __builtin_ctzl(mask[i]); 276 set_ids[i * match_per_key + match_cnt_t] = loc + 1; 277 match_cnt_t++; 278 if (match_cnt_t >= match_per_key) 279 break; 280 mask[i] &= ~(1UL << loc); 281 } 282 match_count[i] = match_cnt_t; 283 if (match_cnt_t != 0) 284 num_matches++; 285 } 286 return num_matches; 287 } 288 289 int 290 rte_member_add_vbf(const struct rte_member_setsum *ss, 291 const void *key, member_set_t set_id) 292 { 293 uint32_t i, h1, h2; 294 uint32_t bit_loc; 295 296 if (set_id > ss->num_set || set_id == RTE_MEMBER_NO_MATCH) 297 return -EINVAL; 298 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); 301 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); 305 } 306 return 0; 307 } 308 309 void 310 rte_member_free_vbf(struct rte_member_setsum *ss) 311 { 312 rte_free(ss->table); 313 } 314 315 void 316 rte_member_reset_vbf(const struct rte_member_setsum *ss) 317 { 318 uint32_t *vbf = ss->table; 319 memset(vbf, 0, (ss->num_set * ss->bits) >> 3); 320 } 321