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