lib/librte_member/rte_member.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2017 Intel Corporation
   3  */
   4
   5 /**
   6  * @file
   7  *
   8  * RTE Membership Library
   9  *
  10  * The Membership Library is an extension and generalization of a traditional
  11  * filter (for example Bloom Filter and cuckoo filter) structure that has
  12  * multiple usages in a variety of workloads and applications. The library is
  13  * used to test if a key belongs to certain sets. Two types of such
  14  * "set-summary" structures are implemented: hash-table based (HT) and vector
  15  * bloom filter (vBF). For HT setsummary, two subtypes or modes are available,
  16  * cache and non-cache modes. The table below summarize some properties of
  17  * the different implementations.
  18  *
  19  * @warning
  20  * @b EXPERIMENTAL: this API may change without prior notice
  21  */
  22
  23 /**
  24  * <!--
  25  * +==========+=====================+================+=========================+
  26  * |   type   |      vbf            |     HT-cache   |     HT-non-cache        |
  27  * +==========+=====================+==========================================+
  28  * |structure |  bloom-filter array |  hash-table like without storing key     |
  29  * +----------+---------------------+------------------------------------------+
  30  * |set id    | limited by bf count |           [1, 0x7fff]                    |
  31  * |          | up to 32.           |                                          |
  32  * +----------+---------------------+------------------------------------------+
  33  * |usages &  | small set range,    | can delete,    | cache most recent keys, |
  34  * |properties| user-specified      | big set range, | have both false-positive|
  35  * |          | false-positive rate,| small false    | and false-negative      |
  36  * |          | no deletion support.| positive depend| depend on table size,   |
  37  * |          |                     | on table size, | automatic overwritten.  |
  38  * |          |                     | new key does   |                         |
  39  * |          |                     | not overwrite  |                         |
  40  * |          |                     | existing key.  |                         |
  41  * +----------+---------------------+----------------+-------------------------+
  42  * -->
  43  */
  44
  45 #ifndef _RTE_MEMBER_H_
  46 #define _RTE_MEMBER_H_
  47
  48 #ifdef __cplusplus
  49 extern "C" {
  50 #endif
  51
  52 #include <stdint.h>
  53
  54 /** The set ID type that stored internally in hash table based set summary. */
  55 typedef uint16_t member_set_t;
  56 /** Invalid set ID used to mean no match found. */
  57 #define RTE_MEMBER_NO_MATCH 0
  58 /** Maximum size of hash table that can be created. */
  59 #define RTE_MEMBER_ENTRIES_MAX (1 << 30)
  60 /** Maximum number of keys that can be searched as a bulk */
  61 #define RTE_MEMBER_LOOKUP_BULK_MAX 64
  62 /** Entry count per bucket in hash table based mode. */
  63 #define RTE_MEMBER_BUCKET_ENTRIES 16
  64 /** Maximum number of characters in setsum name. */
  65 #define RTE_MEMBER_NAMESIZE 32
  66
  67 /** @internal Hash function used by membership library. */
  68 #if defined(RTE_ARCH_X86) || defined(RTE_MACHINE_CPUFLAG_CRC32)
  69 #include <rte_hash_crc.h>
  70 #define MEMBER_HASH_FUNC       rte_hash_crc
  71 #else
  72 #include <rte_jhash.h>
  73 #define MEMBER_HASH_FUNC       rte_jhash
  74 #endif
  75
  76 extern int librte_member_logtype;
  77
  78 #define RTE_MEMBER_LOG(level, fmt, args...) \
  79 rte_log(RTE_LOG_ ## level, librte_member_logtype, "%s(): " fmt, \
  80         __func__, ## args)
  81
  82 /** @internal setsummary structure. */
  83 struct rte_member_setsum;
  84
  85 /**
  86  * @warning
  87  * @b EXPERIMENTAL: this API may change without prior notice
  88  *
  89  * Parameter struct used to create set summary
  90  */
  91 struct rte_member_parameters;
  92
  93 /**
  94  * @warning
  95  * @b EXPERIMENTAL: this API may change without prior notice
  96  *
  97  * Define different set summary types
  98  */
  99 enum rte_member_setsum_type {
 100         RTE_MEMBER_TYPE_HT = 0,  /**< Hash table based set summary. */
 101         RTE_MEMBER_TYPE_VBF,     /**< Vector of bloom filters. */
 102         RTE_MEMBER_NUM_TYPE
 103 };
 104
 105 /** @internal compare function for different arch. */
 106 enum rte_member_sig_compare_function {
 107         RTE_MEMBER_COMPARE_SCALAR = 0,
 108         RTE_MEMBER_COMPARE_AVX2,
 109         RTE_MEMBER_COMPARE_NUM
 110 };
 111
 112 /** @internal setsummary structure. */
 113 struct rte_member_setsum {
 114         enum rte_member_setsum_type type; /* Type of the set summary. */
 115         uint32_t key_len;               /* Length of key. */
 116         uint32_t prim_hash_seed;        /* Primary hash function seed. */
 117         uint32_t sec_hash_seed;         /* Secondary hash function seed. */
 118
 119         /* Hash table based. */
 120         uint32_t bucket_cnt;            /* Number of buckets. */
 121         uint32_t bucket_mask;           /* Bit mask to get bucket index. */
 122         /* For runtime selecting AVX, scalar, etc for signature comparison. */
 123         enum rte_member_sig_compare_function sig_cmp_fn;
 124         uint8_t cache;                  /* If it is cache mode for ht based. */
 125
 126         /* Vector bloom filter. */
 127         uint32_t num_set;               /* Number of set (bf) in vbf. */
 128         uint32_t bits;                  /* Number of bits in each bf. */
 129         uint32_t bit_mask;      /* Bit mask to get bit location in bf. */
 130         uint32_t num_hashes;    /* Number of hash values to index bf. */
 131
 132         uint32_t mul_shift;  /* vbf internal variable used during bit test. */
 133         uint32_t div_shift;  /* vbf internal variable used during bit test. */
 134
 135         void *table;    /* This is the handler of hash table or vBF array. */
 136
 137
 138         /* Second cache line should start here. */
 139         uint32_t socket_id;          /* NUMA Socket ID for memory. */
 140         char name[RTE_MEMBER_NAMESIZE]; /* Name of this set summary. */
 141 } __rte_cache_aligned;
 142
 143 /**
 144  * @warning
 145  * @b EXPERIMENTAL: this API may change without prior notice
 146  *
 147  * Parameters used when create the set summary table. Currently user can
 148  * specify two types of setsummary: HT based and vBF. For HT based, user can
 149  * specify cache or non-cache mode. Here is a table to describe some differences
 150  *
 151  */
 152 struct rte_member_parameters {
 153         const char *name;                       /**< Name of the hash. */
 154
 155         /**
 156          * User to specify the type of the setsummary from one of
 157          * rte_member_setsum_type.
 158          *
 159          * HT based setsummary is implemented like a hash table. User should use
 160          * this type when there are many sets.
 161          *
 162          * vBF setsummary is a vector of bloom filters. It is used when number
 163          * of sets is not big (less than 32 for current implementation).
 164          */
 165         enum rte_member_setsum_type type;
 166
 167         /**
 168          * is_cache is only used for HT based setsummary.
 169          *
 170          * If it is HT based setsummary, user to specify the subtype or mode
 171          * of the setsummary. It could be cache, or non-cache mode.
 172          * Set is_cache to be 1 if to use as cache mode.
 173          *
 174          * For cache mode, keys can be evicted out of the HT setsummary. Keys
 175          * with the same signature and map to the same bucket
 176          * will overwrite each other in the setsummary table.
 177          * This mode is useful for the case that the set-summary only
 178          * needs to keep record of the recently inserted keys. Both
 179          * false-negative and false-positive could happen.
 180          *
 181          * For non-cache mode, keys cannot be evicted out of the cache. So for
 182          * this mode the setsummary will become full eventually. Keys with the
 183          * same signature but map to the same bucket will still occupy multiple
 184          * entries. This mode does not give false-negative result.
 185          */
 186         uint8_t is_cache;
 187
 188         /**
 189          * For HT setsummary, num_keys equals to the number of entries of the
 190          * table. When the number of keys inserted in the HT setsummary
 191          * approaches this number, eviction could happen. For cache mode,
 192          * keys could be evicted out of the table. For non-cache mode, keys will
 193          * be evicted to other buckets like cuckoo hash. The table will also
 194          * likely to become full before the number of inserted keys equal to the
 195          * total number of entries.
 196          *
 197          * For vBF, num_keys equal to the expected number of keys that will
 198          * be inserted into the vBF. The implementation assumes the keys are
 199          * evenly distributed to each BF in vBF. This is used to calculate the
 200          * number of bits we need for each BF. User does not specify the size of
 201          * each BF directly because the optimal size depends on the num_keys
 202          * and false positive rate.
 203          */
 204         uint32_t num_keys;
 205
 206         /**
 207          * The length of key is used for hash calculation. Since key is not
 208          * stored in set-summary, large key does not require more memory space.
 209          */
 210         uint32_t key_len;
 211
 212         /**
 213          * num_set is only used for vBF, but not used for HT setsummary.
 214          *
 215          * num_set is equal to the number of BFs in vBF. For current
 216          * implementation, it only supports 1,2,4,8,16,32 BFs in one vBF set
 217          * summary. If other number of sets are needed, for example 5, the user
 218          * should allocate the minimum available value that larger than 5,
 219          * which is 8.
 220          */
 221         uint32_t num_set;
 222
 223         /**
 224          * false_positive_rate is only used for vBF, but not used for HT
 225          * setsummary.
 226          *
 227          * For vBF, false_positive_rate is the user-defined false positive rate
 228          * given expected number of inserted keys (num_keys). It is used to
 229          * calculate the total number of bits for each BF, and the number of
 230          * hash values used during lookup and insertion. For details please
 231          * refer to vBF implementation and membership library documentation.
 232          *
 233          * For HT, This parameter is not directly set by users.
 234          * HT setsummary's false positive rate is in the order of:
 235          * false_pos = (1/bucket_count)*(1/2^16), since we use 16-bit signature.
 236          * This is because two keys needs to map to same bucket and same
 237          * signature to have a collision (false positive). bucket_count is equal
 238          * to number of entries (num_keys) divided by entry count per bucket
 239          * (RTE_MEMBER_BUCKET_ENTRIES). Thus, the false_positive_rate is not
 240          * directly set by users for HT mode.
 241          */
 242         float false_positive_rate;
 243
 244         /**
 245          * We use two seeds to calculate two independent hashes for each key.
 246          *
 247          * For HT type, one hash is used as signature, and the other is used
 248          * for bucket location.
 249          * For vBF type, these two hashes and their combinations are used as
 250          * hash locations to index the bit array.
 251          */
 252         uint32_t prim_hash_seed;
 253
 254         /**
 255          * The secondary seed should be a different value from the primary seed.
 256          */
 257         uint32_t sec_hash_seed;
 258
 259         int socket_id;                  /**< NUMA Socket ID for memory. */
 260 };
 261
 262 /**
 263  * @warning
 264  * @b EXPERIMENTAL: this API may change without prior notice
 265  *
 266  * Find an existing set-summary and return a pointer to it.
 267  *
 268  * @param name
 269  *   Name of the set-summary.
 270  * @return
 271  *   Pointer to the set-summary or NULL if object not found
 272  *   with rte_errno set appropriately. Possible rte_errno values include:
 273  *    - ENOENT - value not available for return
 274  */
 275 struct rte_member_setsum *
 276 rte_member_find_existing(const char *name);
 277
 278 /**
 279  * @warning
 280  * @b EXPERIMENTAL: this API may change without prior notice
 281  *
 282  * Create set-summary (SS).
 283  *
 284  * @param params
 285  *   Parameters to initialize the setsummary.
 286  * @return
 287  *   Return the pointer to the setsummary.
 288  *   Return value is NULL if the creation failed.
 289  */
 290 struct rte_member_setsum *
 291 rte_member_create(const struct rte_member_parameters *params);
 292
 293 /**
 294  * @warning
 295  * @b EXPERIMENTAL: this API may change without prior notice
 296  *
 297  * Lookup key in set-summary (SS).
 298  * Single key lookup and return as soon as the first match found
 299  *
 300  * @param setsum
 301  *   Pointer of a setsummary.
 302  * @param key
 303  *   Pointer of the key to be looked up.
 304  * @param set_id
 305  *   Output the set id matches the key.
 306  * @return
 307  *   Return 1 for found a match and 0 for not found a match.
 308  */
 309 int
 310 rte_member_lookup(const struct rte_member_setsum *setsum, const void *key,
 311                         member_set_t *set_id);
 312
 313 /**
 314  * @warning
 315  * @b EXPERIMENTAL: this API may change without prior notice
 316  *
 317  * Lookup bulk of keys in set-summary (SS).
 318  * Each key lookup returns as soon as the first match found
 319  *
 320  * @param setsum
 321  *   Pointer of a setsummary.
 322  * @param keys
 323  *   Pointer of the bulk of keys to be looked up.
 324  * @param num_keys
 325  *   Number of keys that will be lookup.
 326  * @param set_ids
 327  *   Output set ids for all the keys to this array.
 328  *   User should preallocate array that can contain all results, which size is
 329  *   the num_keys.
 330  * @return
 331  *   The number of keys that found a match.
 332  */
 333 int
 334 rte_member_lookup_bulk(const struct rte_member_setsum *setsum,
 335                         const void **keys, uint32_t num_keys,
 336                         member_set_t *set_ids);
 337
 338 /**
 339  * @warning
 340  * @b EXPERIMENTAL: this API may change without prior notice
 341  *
 342  * Lookup a key in set-summary (SS) for multiple matches.
 343  * The key lookup will find all matched entries (multiple match).
 344  * Note that for cache mode of HT, each key can have at most one match. This is
 345  * because keys with same signature that maps to same bucket will overwrite
 346  * each other. So multi-match lookup should be used for vBF and non-cache HT.
 347  *
 348  * @param setsum
 349  *   Pointer of a set-summary.
 350  * @param key
 351  *   Pointer of the key that to be looked up.
 352  * @param max_match_per_key
 353  *   User specified maximum number of matches for each key. The function returns
 354  *   as soon as this number of matches found for the key.
 355  * @param set_id
 356  *   Output set ids for all the matches of the key. User needs to preallocate
 357  *   the array that can contain max_match_per_key number of results.
 358  * @return
 359  *   The number of matches that found for the key.
 360  *   For cache mode HT set-summary, the number should be at most 1.
 361  */
 362 int
 363 rte_member_lookup_multi(const struct rte_member_setsum *setsum,
 364                 const void *key, uint32_t max_match_per_key,
 365                 member_set_t *set_id);
 366
 367 /**
 368  * @warning
 369  * @b EXPERIMENTAL: this API may change without prior notice
 370  *
 371  * Lookup a bulk of keys in set-summary (SS) for multiple matches each key.
 372  * Each key lookup will find all matched entries (multiple match).
 373  * Note that for cache mode HT, each key can have at most one match. So
 374  * multi-match function is mainly used for vBF and non-cache mode HT.
 375  *
 376  * @param setsum
 377  *   Pointer of a setsummary.
 378  * @param keys
 379  *   Pointer of the keys to be looked up.
 380  * @param num_keys
 381  *   The number of keys that will be lookup.
 382  * @param max_match_per_key
 383  *   The possible maximum number of matches for each key.
 384  * @param match_count
 385  *   Output the number of matches for each key in an array.
 386  * @param set_ids
 387  *   Return set ids for all the matches of all keys. Users pass in a
 388  *   preallocated 2D array with first dimension as key index and second
 389  *   dimension as match index. For example set_ids[bulk_size][max_match_per_key]
 390  * @return
 391  *   The number of keys that found one or more matches in the set-summary.
 392  */
 393 int
 394 rte_member_lookup_multi_bulk(const struct rte_member_setsum *setsum,
 395                 const void **keys, uint32_t num_keys,
 396                 uint32_t max_match_per_key,
 397                 uint32_t *match_count,
 398                 member_set_t *set_ids);
 399
 400 /**
 401  * @warning
 402  * @b EXPERIMENTAL: this API may change without prior notice
 403  *
 404  * Insert key into set-summary (SS).
 405  *
 406  * @param setsum
 407  *   Pointer of a set-summary.
 408  * @param key
 409  *   Pointer of the key to be added.
 410  * @param set_id
 411  *   The set id associated with the key that needs to be added. Different mode
 412  *   supports different set_id ranges. 0 cannot be used as set_id since
 413  *   RTE_MEMBER_NO_MATCH by default is set as 0.
 414  *   For HT mode, the set_id has range as [1, 0x7FFF], MSB is reserved.
 415  *   For vBF mode the set id is limited by the num_set parameter when create
 416  *   the set-summary.
 417  * @return
 418  *   HT (cache mode) and vBF should never fail unless the set_id is not in the
 419  *   valid range. In such case -EINVAL is returned.
 420  *   For HT (non-cache mode) it could fail with -ENOSPC error code when table is
 421  *   full.
 422  *   For success it returns different values for different modes to provide
 423  *   extra information for users.
 424  *   Return 0 for HT (cache mode) if the add does not cause
 425  *   eviction, return 1 otherwise. Return 0 for non-cache mode if success,
 426  *   -ENOSPC for full, and 1 if cuckoo eviction happens.
 427  *   Always returns 0 for vBF mode.
 428  */
 429 int
 430 rte_member_add(const struct rte_member_setsum *setsum, const void *key,
 431                         member_set_t set_id);
 432
 433 /**
 434  * @warning
 435  * @b EXPERIMENTAL: this API may change without prior notice
 436  *
 437  * De-allocate memory used by set-summary.
 438  *
 439  * @param setsum
 440  *   Pointer to the set summary.
 441  */
 442 void
 443 rte_member_free(struct rte_member_setsum *setsum);
 444
 445 /**
 446  * @warning
 447  * @b EXPERIMENTAL: this API may change without prior notice
 448  *
 449  * Reset the set-summary tables. E.g. reset bits to be 0 in BF,
 450  * reset set_id in each entry to be RTE_MEMBER_NO_MATCH in HT based SS.
 451  *
 452  * @param setsum
 453  *   Pointer to the set-summary.
 454  */
 455 void
 456 rte_member_reset(const struct rte_member_setsum *setsum);
 457
 458 /**
 459  * @warning
 460  * @b EXPERIMENTAL: this API may change without prior notice
 461  *
 462  * Delete items from the set-summary. Note that vBF does not support deletion
 463  * in current implementation. For vBF, error code of -EINVAL will be returned.
 464  *
 465  * @param setsum
 466  *   Pointer to the set-summary.
 467  * @param key
 468  *   Pointer of the key to be deleted.
 469  * @param set_id
 470  *   For HT mode, we need both key and its corresponding set_id to
 471  *   properly delete the key. Without set_id, we may delete other keys with the
 472  *   same signature.
 473  * @return
 474  *   If no entry found to delete, an error code of -ENOENT could be returned.
 475  */
 476 int
 477 rte_member_delete(const struct rte_member_setsum *setsum, const void *key,
 478                         member_set_t set_id);
 479
 480 #ifdef __cplusplus
 481 }
 482 #endif
 483
 484 #endif /* _RTE_MEMBER_H_ */