lib/librte_member/rte_member_vbf.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2017 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #include <math.h>
  35 #include <string.h>
  36
  37 #include <rte_malloc.h>
  38 #include <rte_memory.h>
  39 #include <rte_errno.h>
  40 #include <rte_log.h>
  41
  42 #include "rte_member.h"
  43 #include "rte_member_vbf.h"
  44
  45 /*
  46  * vBF currently implemented as a big array.
  47  * The BFs have a vertical layout. Bits in same location of all bfs will stay
  48  * in the same cache line.
  49  * For example, if we have 32 bloom filters, we use a uint32_t array to
  50  * represent all of them. array[0] represent the first location of all the
  51  * bloom filters, array[1] represents the second location of all the
  52  * bloom filters, etc. The advantage of this layout is to minimize the average
  53  * number of memory accesses to test all bloom filters.
  54  *
  55  * Currently the implementation supports vBF containing 1,2,4,8,16,32 BFs.
  56  */
  57 int
  58 rte_member_create_vbf(struct rte_member_setsum *ss,
  59                 const struct rte_member_parameters *params)
  60 {
  61
  62         if (params->num_set > RTE_MEMBER_MAX_BF ||
  63                         !rte_is_power_of_2(params->num_set) ||
  64                         params->num_keys == 0 ||
  65                         params->false_positive_rate == 0 ||
  66                         params->false_positive_rate > 1) {
  67                 rte_errno = EINVAL;
  68                 RTE_MEMBER_LOG(ERR, "Membership vBF create with invalid parameters\n");
  69                 return -EINVAL;
  70         }
  71
  72         /* We assume expected keys evenly distribute to all BFs */
  73         uint32_t num_keys_per_bf = 1 + (params->num_keys - 1) / ss->num_set;
  74
  75         /*
  76          * Note that the false positive rate is for all BFs in the vBF
  77          * such that the single BF's false positive rate needs to be
  78          * calculated.
  79          * Assume each BF's False positive rate is fp_one_bf. The total false
  80          * positive rate is fp = 1-(1-fp_one_bf)^n.
  81          * => fp_one_bf = 1 - (1-fp)^(1/n)
  82          */
  83
  84         float fp_one_bf = 1 - pow((1 - params->false_positive_rate),
  85                                         1.0 / ss->num_set);
  86
  87         if (fp_one_bf == 0) {
  88                 rte_errno = EINVAL;
  89                 RTE_MEMBER_LOG(ERR, "Membership BF false positive rate is too small\n");
  90                 return -EINVAL;
  91         }
  92
  93         uint32_t bits = ceil((num_keys_per_bf *
  94                                 log(fp_one_bf)) /
  95                                 log(1.0 / (pow(2.0, log(2.0)))));
  96
  97         /* We round to power of 2 for performance during lookup */
  98         ss->bits = rte_align32pow2(bits);
  99
 100         ss->num_hashes = (uint32_t)(log(2.0) * bits / num_keys_per_bf);
 101         ss->bit_mask = ss->bits - 1;
 102
 103         /*
 104          * Since we round the bits to power of 2, the final false positive
 105          * rate will probably not be same as the user specified. We log the
 106          * new value as debug message.
 107          */
 108         float new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
 109                                         ss->num_hashes)), ss->num_hashes);
 110         new_fp = 1 - pow((1 - new_fp), ss->num_set);
 111
 112         /*
 113          * Reduce hash function count, until we approach the user specified
 114          * false-positive rate. Otherwise it is too conservative
 115          */
 116         int tmp_num_hash = ss->num_hashes;
 117
 118         while (tmp_num_hash > 1) {
 119                 float tmp_fp = new_fp;
 120
 121                 tmp_num_hash--;
 122                 new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
 123                                         tmp_num_hash)), tmp_num_hash);
 124                 new_fp = 1 - pow((1 - new_fp), ss->num_set);
 125
 126                 if (new_fp > params->false_positive_rate) {
 127                         new_fp = tmp_fp;
 128                         tmp_num_hash++;
 129                         break;
 130                 }
 131         }
 132
 133         ss->num_hashes = tmp_num_hash;
 134
 135         /*
 136          * To avoid multiplication and division:
 137          * mul_shift is used for multiplication shift during bit test
 138          * div_shift is used for division shift, to be divided by number of bits
 139          * represented by a uint32_t variable
 140          */
 141         ss->mul_shift = __builtin_ctzl(ss->num_set);
 142         ss->div_shift = __builtin_ctzl(32 >> ss->mul_shift);
 143
 144         RTE_MEMBER_LOG(DEBUG, "vector bloom filter created, "
 145                 "each bloom filter expects %u keys, needs %u bits, %u hashes, "
 146                 "with false positive rate set as %.5f, "
 147                 "The new calculated vBF false positive rate is %.5f\n",
 148                 num_keys_per_bf, ss->bits, ss->num_hashes, fp_one_bf, new_fp);
 149
 150         ss->table = rte_zmalloc_socket(NULL, ss->num_set * (ss->bits >> 3),
 151                                         RTE_CACHE_LINE_SIZE, ss->socket_id);
 152         if (ss->table == NULL)
 153                 return -ENOMEM;
 154
 155         return 0;
 156 }
 157
 158 static inline uint32_t
 159 test_bit(uint32_t bit_loc, const struct rte_member_setsum *ss)
 160 {
 161         uint32_t *vbf = ss->table;
 162         uint32_t n = ss->num_set;
 163         uint32_t div_shift = ss->div_shift;
 164         uint32_t mul_shift = ss->mul_shift;
 165         /*
 166          * a is how many bits in one BF are represented by one 32bit
 167          * variable.
 168          */
 169         uint32_t a = 32 >> mul_shift;
 170         /*
 171          * x>>b is the divide, x & (a-1) is the mod, & (1<<n-1) to mask out bits
 172          * we do not need
 173          */
 174         return (vbf[bit_loc >> div_shift] >>
 175                         ((bit_loc & (a - 1)) << mul_shift)) & ((1ULL << n) - 1);
 176 }
 177
 178 static inline void
 179 set_bit(uint32_t bit_loc, const struct rte_member_setsum *ss, int32_t set)
 180 {
 181         uint32_t *vbf = ss->table;
 182         uint32_t div_shift = ss->div_shift;
 183         uint32_t mul_shift = ss->mul_shift;
 184         uint32_t a = 32 >> mul_shift;
 185
 186         vbf[bit_loc >> div_shift] |=
 187                         1UL << (((bit_loc & (a - 1)) << mul_shift) + set - 1);
 188 }
 189
 190 int
 191 rte_member_lookup_vbf(const struct rte_member_setsum *ss, const void *key,
 192                 member_set_t *set_id)
 193 {
 194         uint32_t j;
 195         uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
 196         uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
 197                                                 ss->sec_hash_seed);
 198         uint32_t mask = ~0;
 199         uint32_t bit_loc;
 200
 201         for (j = 0; j < ss->num_hashes; j++) {
 202                 bit_loc = (h1 + j * h2) & ss->bit_mask;
 203                 mask &= test_bit(bit_loc, ss);
 204         }
 205
 206         if (mask) {
 207                 *set_id = __builtin_ctzl(mask) + 1;
 208                 return 1;
 209         }
 210
 211         *set_id = RTE_MEMBER_NO_MATCH;
 212         return 0;
 213 }
 214
 215 uint32_t
 216 rte_member_lookup_bulk_vbf(const struct rte_member_setsum *ss,
 217                 const void **keys, uint32_t num_keys, member_set_t *set_ids)
 218 {
 219         uint32_t i, k;
 220         uint32_t num_matches = 0;
 221         uint32_t mask[RTE_MEMBER_LOOKUP_BULK_MAX];
 222         uint32_t h1[RTE_MEMBER_LOOKUP_BULK_MAX], h2[RTE_MEMBER_LOOKUP_BULK_MAX];
 223         uint32_t bit_loc;
 224
 225         for (i = 0; i < num_keys; i++)
 226                 h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
 227                                                 ss->prim_hash_seed);
 228         for (i = 0; i < num_keys; i++)
 229                 h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
 230                                                 ss->sec_hash_seed);
 231         for (i = 0; i < num_keys; i++) {
 232                 mask[i] = ~0;
 233                 for (k = 0; k < ss->num_hashes; k++) {
 234                         bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
 235                         mask[i] &= test_bit(bit_loc, ss);
 236                 }
 237         }
 238         for (i = 0; i < num_keys; i++) {
 239                 if (mask[i]) {
 240                         set_ids[i] = __builtin_ctzl(mask[i]) + 1;
 241                         num_matches++;
 242                 } else
 243                         set_ids[i] = RTE_MEMBER_NO_MATCH;
 244         }
 245         return num_matches;
 246 }
 247
 248 uint32_t
 249 rte_member_lookup_multi_vbf(const struct rte_member_setsum *ss,
 250                 const void *key, uint32_t match_per_key,
 251                 member_set_t *set_id)
 252 {
 253         uint32_t num_matches = 0;
 254         uint32_t j;
 255         uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
 256         uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
 257                                                 ss->sec_hash_seed);
 258         uint32_t mask = ~0;
 259         uint32_t bit_loc;
 260
 261         for (j = 0; j < ss->num_hashes; j++) {
 262                 bit_loc = (h1 + j * h2) & ss->bit_mask;
 263                 mask &= test_bit(bit_loc, ss);
 264         }
 265         while (mask) {
 266                 uint32_t loc = __builtin_ctzl(mask);
 267                 set_id[num_matches] = loc + 1;
 268                 num_matches++;
 269                 if (num_matches >= match_per_key)
 270                         return num_matches;
 271                 mask &= ~(1UL << loc);
 272         }
 273         return num_matches;
 274 }
 275
 276 uint32_t
 277 rte_member_lookup_multi_bulk_vbf(const struct rte_member_setsum *ss,
 278                 const void **keys, uint32_t num_keys, uint32_t match_per_key,
 279                 uint32_t *match_count,
 280                 member_set_t *set_ids)
 281 {
 282         uint32_t i, k;
 283         uint32_t num_matches = 0;
 284         uint32_t match_cnt_t;
 285         uint32_t mask[RTE_MEMBER_LOOKUP_BULK_MAX];
 286         uint32_t h1[RTE_MEMBER_LOOKUP_BULK_MAX], h2[RTE_MEMBER_LOOKUP_BULK_MAX];
 287         uint32_t bit_loc;
 288
 289         for (i = 0; i < num_keys; i++)
 290                 h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
 291                                                 ss->prim_hash_seed);
 292         for (i = 0; i < num_keys; i++)
 293                 h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
 294                                                 ss->sec_hash_seed);
 295         for (i = 0; i < num_keys; i++) {
 296                 mask[i] = ~0;
 297                 for (k = 0; k < ss->num_hashes; k++) {
 298                         bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
 299                         mask[i] &= test_bit(bit_loc, ss);
 300                 }
 301         }
 302         for (i = 0; i < num_keys; i++) {
 303                 match_cnt_t = 0;
 304                 while (mask[i]) {
 305                         uint32_t loc = __builtin_ctzl(mask[i]);
 306                         set_ids[i * match_per_key + match_cnt_t] = loc + 1;
 307                         match_cnt_t++;
 308                         if (match_cnt_t >= match_per_key)
 309                                 break;
 310                         mask[i] &= ~(1UL << loc);
 311                 }
 312                 match_count[i] = match_cnt_t;
 313                 if (match_cnt_t != 0)
 314                         num_matches++;
 315         }
 316         return num_matches;
 317 }
 318
 319 int
 320 rte_member_add_vbf(const struct rte_member_setsum *ss,
 321                 const void *key, member_set_t set_id)
 322 {
 323         uint32_t i, h1, h2;
 324         uint32_t bit_loc;
 325
 326         if (set_id > ss->num_set || set_id == RTE_MEMBER_NO_MATCH)
 327                 return -EINVAL;
 328
 329         h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
 330         h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t), ss->sec_hash_seed);
 331
 332         for (i = 0; i < ss->num_hashes; i++) {
 333                 bit_loc = (h1 + i * h2) & ss->bit_mask;
 334                 set_bit(bit_loc, ss, set_id);
 335         }
 336         return 0;
 337 }
 338
 339 void
 340 rte_member_free_vbf(struct rte_member_setsum *ss)
 341 {
 342         rte_free(ss->table);
 343 }
 344
 345 void
 346 rte_member_reset_vbf(const struct rte_member_setsum *ss)
 347 {
 348         uint32_t *vbf = ss->table;
 349         memset(vbf, 0, (ss->num_set * ss->bits) >> 3);
 350 }