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