lib/librte_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_memory.h>
  10 #include <rte_errno.h>
  11 #include <rte_log.h>
  12
  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                 RTE_MEMBER_LOG(ERR, "Membership vBF create with invalid parameters\n");
  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                 RTE_MEMBER_LOG(ERR, "Membership BF false positive rate is too small\n");
  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 = __builtin_ctzl(ss->num_set);
 113         ss->div_shift = __builtin_ctzl(32 >> ss->mul_shift);
 114
 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);
 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 = __builtin_ctzl(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] = __builtin_ctzl(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 = __builtin_ctzl(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 = __builtin_ctzl(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 }