lib/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_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 }