common/octeontx2: upgrade mbox definition to version 7
[dpdk.git] / lib / librte_hash / rte_hash.h
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2010-2015 Intel Corporation
3  */
4
5 #ifndef _RTE_HASH_H_
6 #define _RTE_HASH_H_
7
8 /**
9  * @file
10  *
11  * RTE Hash Table
12  */
13
14 #include <stdint.h>
15 #include <stddef.h>
16
17 #include <rte_compat.h>
18
19 #ifdef __cplusplus
20 extern "C" {
21 #endif
22
23 /** Maximum size of hash table that can be created. */
24 #define RTE_HASH_ENTRIES_MAX                    (1 << 30)
25
26 /** Maximum number of characters in hash name.*/
27 #define RTE_HASH_NAMESIZE                       32
28
29 /** Maximum number of keys that can be searched for using rte_hash_lookup_bulk. */
30 #define RTE_HASH_LOOKUP_BULK_MAX                64
31 #define RTE_HASH_LOOKUP_MULTI_MAX               RTE_HASH_LOOKUP_BULK_MAX
32
33 /** Enable Hardware transactional memory support. */
34 #define RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT  0x01
35
36 /** Default behavior of insertion, single writer/multi writer */
37 #define RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD 0x02
38
39 /** Flag to support reader writer concurrency */
40 #define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY 0x04
41
42 /** Flag to indicate the extendable bucket table feature should be used */
43 #define RTE_HASH_EXTRA_FLAGS_EXT_TABLE 0x08
44
45 /** Flag to disable freeing of key index on hash delete.
46  * Refer to rte_hash_del_xxx APIs for more details.
47  * This is enabled by default when RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF
48  * is enabled.
49  */
50 #define RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL 0x10
51
52 /** Flag to support lock free reader writer concurrency. Both single writer
53  * and multi writer use cases are supported.
54  */
55 #define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x20
56
57 /**
58  * The type of hash value of a key.
59  * It should be a value of at least 32bit with fully random pattern.
60  */
61 typedef uint32_t hash_sig_t;
62
63 /** Type of function that can be used for calculating the hash value. */
64 typedef uint32_t (*rte_hash_function)(const void *key, uint32_t key_len,
65                                       uint32_t init_val);
66
67 /** Type of function used to compare the hash key. */
68 typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len);
69
70 /**
71  * Parameters used when creating the hash table.
72  */
73 struct rte_hash_parameters {
74         const char *name;               /**< Name of the hash. */
75         uint32_t entries;               /**< Total hash table entries. */
76         uint32_t reserved;              /**< Unused field. Should be set to 0 */
77         uint32_t key_len;               /**< Length of hash key. */
78         rte_hash_function hash_func;    /**< Primary Hash function used to calculate hash. */
79         uint32_t hash_func_init_val;    /**< Init value used by hash_func. */
80         int socket_id;                  /**< NUMA Socket ID for memory. */
81         uint8_t extra_flag;             /**< Indicate if additional parameters are present. */
82 };
83
84 /** @internal A hash table structure. */
85 struct rte_hash;
86
87 /**
88  * Create a new hash table.
89  *
90  * @param params
91  *   Parameters used to create and initialise the hash table.
92  * @return
93  *   Pointer to hash table structure that is used in future hash table
94  *   operations, or NULL on error, with error code set in rte_errno.
95  *   Possible rte_errno errors include:
96  *    - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure
97  *    - E_RTE_SECONDARY - function was called from a secondary process instance
98  *    - ENOENT - missing entry
99  *    - EINVAL - invalid parameter passed to function
100  *    - ENOSPC - the maximum number of memzones has already been allocated
101  *    - EEXIST - a memzone with the same name already exists
102  *    - ENOMEM - no appropriate memory area found in which to create memzone
103  */
104 struct rte_hash *
105 rte_hash_create(const struct rte_hash_parameters *params);
106
107 /**
108  * Set a new hash compare function other than the default one.
109  *
110  * @note Function pointer does not work with multi-process, so do not use it
111  * in multi-process mode.
112  *
113  * @param h
114  *   Hash table for which the function is to be changed
115  * @param func
116  *   New compare function
117  */
118 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func);
119
120 /**
121  * Find an existing hash table object and return a pointer to it.
122  *
123  * @param name
124  *   Name of the hash table as passed to rte_hash_create()
125  * @return
126  *   Pointer to hash table or NULL if object not found
127  *   with rte_errno set appropriately. Possible rte_errno values include:
128  *    - ENOENT - value not available for return
129  */
130 struct rte_hash *
131 rte_hash_find_existing(const char *name);
132
133 /**
134  * De-allocate all memory used by hash table.
135  * @param h
136  *   Hash table to free
137  */
138 void
139 rte_hash_free(struct rte_hash *h);
140
141 /**
142  * Reset all hash structure, by zeroing all entries.
143  * When RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled,
144  * it is application's responsibility to make sure that
145  * none of the readers are referencing the hash table
146  * while calling this API.
147  *
148  * @param h
149  *   Hash table to reset
150  */
151 void
152 rte_hash_reset(struct rte_hash *h);
153
154 /**
155  * Return the number of keys in the hash table
156  * @param h
157  *  Hash table to query from
158  * @return
159  *   - -EINVAL if parameters are invalid
160  *   - A value indicating how many keys were inserted in the table.
161  */
162 int32_t
163 rte_hash_count(const struct rte_hash *h);
164
165 /**
166  * @warning
167  * @b EXPERIMENTAL: this API may change without prior notice
168  *
169  * Return the maximum key value ID that could possibly be returned by
170  * rte_hash_add_key function.
171  *
172  * @param h
173  *  Hash table to query from
174  * @return
175  *   - -EINVAL if parameters are invalid
176  *   - A value indicating the max key ID of key slots present in the table.
177  */
178 __rte_experimental
179 int32_t
180 rte_hash_max_key_id(const struct rte_hash *h);
181
182 /**
183  * Add a key-value pair to an existing hash table.
184  * This operation is not multi-thread safe
185  * and should only be called from one thread by default.
186  * Thread safety can be enabled by setting flag during
187  * table creation.
188  * If the key exists already in the table, this API updates its value
189  * with 'data' passed in this API. It is the responsibility of
190  * the application to manage any memory associated with the old value.
191  * The readers might still be using the old value even after this API
192  * has returned.
193  *
194  * @param h
195  *   Hash table to add the key to.
196  * @param key
197  *   Key to add to the hash table.
198  * @param data
199  *   Data to add to the hash table.
200  * @return
201  *   - 0 if added successfully
202  *   - -EINVAL if the parameters are invalid.
203  *   - -ENOSPC if there is no space in the hash for this key.
204  */
205 int
206 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data);
207
208 /**
209  * Add a key-value pair with a pre-computed hash value
210  * to an existing hash table.
211  * This operation is not multi-thread safe
212  * and should only be called from one thread by default.
213  * Thread safety can be enabled by setting flag during
214  * table creation.
215  * If the key exists already in the table, this API updates its value
216  * with 'data' passed in this API. It is the responsibility of
217  * the application to manage any memory associated with the old value.
218  * The readers might still be using the old value even after this API
219  * has returned.
220  *
221  * @param h
222  *   Hash table to add the key to.
223  * @param key
224  *   Key to add to the hash table.
225  * @param sig
226  *   Precomputed hash value for 'key'
227  * @param data
228  *   Data to add to the hash table.
229  * @return
230  *   - 0 if added successfully
231  *   - -EINVAL if the parameters are invalid.
232  *   - -ENOSPC if there is no space in the hash for this key.
233  */
234 int32_t
235 rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key,
236                                                 hash_sig_t sig, void *data);
237
238 /**
239  * Add a key to an existing hash table. This operation is not multi-thread safe
240  * and should only be called from one thread by default.
241  * Thread safety can be enabled by setting flag during
242  * table creation.
243  *
244  * @param h
245  *   Hash table to add the key to.
246  * @param key
247  *   Key to add to the hash table.
248  * @return
249  *   - -EINVAL if the parameters are invalid.
250  *   - -ENOSPC if there is no space in the hash for this key.
251  *   - A positive value that can be used by the caller as an offset into an
252  *     array of user data. This value is unique for this key. This
253  *     unique key id may be larger than the user specified entry count
254  *     when RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD flag is set.
255  */
256 int32_t
257 rte_hash_add_key(const struct rte_hash *h, const void *key);
258
259 /**
260  * Add a key to an existing hash table.
261  * This operation is not multi-thread safe
262  * and should only be called from one thread by default.
263  * Thread safety can be enabled by setting flag during
264  * table creation.
265  *
266  * @param h
267  *   Hash table to add the key to.
268  * @param key
269  *   Key to add to the hash table.
270  * @param sig
271  *   Precomputed hash value for 'key'.
272  * @return
273  *   - -EINVAL if the parameters are invalid.
274  *   - -ENOSPC if there is no space in the hash for this key.
275  *   - A positive value that can be used by the caller as an offset into an
276  *     array of user data. This value is unique for this key. This
277  *     unique key ID may be larger than the user specified entry count
278  *     when RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD flag is set.
279  */
280 int32_t
281 rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
282
283 /**
284  * Remove a key from an existing hash table.
285  * This operation is not multi-thread safe
286  * and should only be called from one thread by default.
287  * Thread safety can be enabled by setting flag during
288  * table creation.
289  * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or
290  * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled,
291  * the key index returned by rte_hash_add_key_xxx APIs will not be
292  * freed by this API. rte_hash_free_key_with_position API must be called
293  * additionally to free the index associated with the key.
294  * rte_hash_free_key_with_position API should be called after all
295  * the readers have stopped referencing the entry corresponding to
296  * this key. RCU mechanisms could be used to determine such a state.
297  *
298  * @param h
299  *   Hash table to remove the key from.
300  * @param key
301  *   Key to remove from the hash table.
302  * @return
303  *   - -EINVAL if the parameters are invalid.
304  *   - -ENOENT if the key is not found.
305  *   - A positive value that can be used by the caller as an offset into an
306  *     array of user data. This value is unique for this key, and is the same
307  *     value that was returned when the key was added.
308  */
309 int32_t
310 rte_hash_del_key(const struct rte_hash *h, const void *key);
311
312 /**
313  * Remove a key from an existing hash table.
314  * This operation is not multi-thread safe
315  * and should only be called from one thread by default.
316  * Thread safety can be enabled by setting flag during
317  * table creation.
318  * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or
319  * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled,
320  * the key index returned by rte_hash_add_key_xxx APIs will not be
321  * freed by this API. rte_hash_free_key_with_position API must be called
322  * additionally to free the index associated with the key.
323  * rte_hash_free_key_with_position API should be called after all
324  * the readers have stopped referencing the entry corresponding to
325  * this key. RCU mechanisms could be used to determine such a state.
326  *
327  * @param h
328  *   Hash table to remove the key from.
329  * @param key
330  *   Key to remove from the hash table.
331  * @param sig
332  *   Precomputed hash value for 'key'.
333  * @return
334  *   - -EINVAL if the parameters are invalid.
335  *   - -ENOENT if the key is not found.
336  *   - A positive value that can be used by the caller as an offset into an
337  *     array of user data. This value is unique for this key, and is the same
338  *     value that was returned when the key was added.
339  */
340 int32_t
341 rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
342
343 /**
344  * Find a key in the hash table given the position.
345  * This operation is multi-thread safe with regarding to other lookup threads.
346  * Read-write concurrency can be enabled by setting flag during
347  * table creation.
348  *
349  * @param h
350  *   Hash table to get the key from.
351  * @param position
352  *   Position returned when the key was inserted.
353  * @param key
354  *   Output containing a pointer to the key
355  * @return
356  *   - 0 if retrieved successfully
357  *   - -EINVAL if the parameters are invalid.
358  *   - -ENOENT if no valid key is found in the given position.
359  */
360 int
361 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
362                                void **key);
363
364 /**
365  * @warning
366  * @b EXPERIMENTAL: this API may change without prior notice
367  *
368  * Free a hash key in the hash table given the position
369  * of the key. This operation is not multi-thread safe and should
370  * only be called from one thread by default. Thread safety
371  * can be enabled by setting flag during table creation.
372  * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or
373  * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled,
374  * the key index returned by rte_hash_del_key_xxx APIs must be freed
375  * using this API. This API should be called after all the readers
376  * have stopped referencing the entry corresponding to this key.
377  * RCU mechanisms could be used to determine such a state.
378  * This API does not validate if the key is already freed.
379  *
380  * @param h
381  *   Hash table to free the key from.
382  * @param position
383  *   Position returned when the key was deleted.
384  * @return
385  *   - 0 if freed successfully
386  *   - -EINVAL if the parameters are invalid.
387  */
388 __rte_experimental
389 int
390 rte_hash_free_key_with_position(const struct rte_hash *h,
391                                 const int32_t position);
392
393 /**
394  * Find a key-value pair in the hash table.
395  * This operation is multi-thread safe with regarding to other lookup threads.
396  * Read-write concurrency can be enabled by setting flag during
397  * table creation.
398  *
399  * @param h
400  *   Hash table to look in.
401  * @param key
402  *   Key to find.
403  * @param data
404  *   Output with pointer to data returned from the hash table.
405  * @return
406  *   - A positive value that can be used by the caller as an offset into an
407  *     array of user data. This value is unique for this key, and is the same
408  *     value that was returned when the key was added.
409  *   - -EINVAL if the parameters are invalid.
410  *   - -ENOENT if the key is not found.
411  */
412 int
413 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data);
414
415 /**
416  * Find a key-value pair with a pre-computed hash value
417  * to an existing hash table.
418  * This operation is multi-thread safe with regarding to other lookup threads.
419  * Read-write concurrency can be enabled by setting flag during
420  * table creation.
421  *
422  * @param h
423  *   Hash table to look in.
424  * @param key
425  *   Key to find.
426  * @param sig
427  *   Precomputed hash value for 'key'
428  * @param data
429  *   Output with pointer to data returned from the hash table.
430  * @return
431  *   - A positive value that can be used by the caller as an offset into an
432  *     array of user data. This value is unique for this key, and is the same
433  *     value that was returned when the key was added.
434  *   - -EINVAL if the parameters are invalid.
435  *   - -ENOENT if the key is not found.
436  */
437 int
438 rte_hash_lookup_with_hash_data(const struct rte_hash *h, const void *key,
439                                         hash_sig_t sig, void **data);
440
441 /**
442  * Find a key in the hash table.
443  * This operation is multi-thread safe with regarding to other lookup threads.
444  * Read-write concurrency can be enabled by setting flag during
445  * table creation.
446  *
447  * @param h
448  *   Hash table to look in.
449  * @param key
450  *   Key to find.
451  * @return
452  *   - -EINVAL if the parameters are invalid.
453  *   - -ENOENT if the key is not found.
454  *   - A positive value that can be used by the caller as an offset into an
455  *     array of user data. This value is unique for this key, and is the same
456  *     value that was returned when the key was added.
457  */
458 int32_t
459 rte_hash_lookup(const struct rte_hash *h, const void *key);
460
461 /**
462  * Find a key in the hash table.
463  * This operation is multi-thread safe with regarding to other lookup threads.
464  * Read-write concurrency can be enabled by setting flag during
465  * table creation.
466  *
467  * @param h
468  *   Hash table to look in.
469  * @param key
470  *   Key to find.
471  * @param sig
472  *   Precomputed hash value for 'key'.
473  * @return
474  *   - -EINVAL if the parameters are invalid.
475  *   - -ENOENT if the key is not found.
476  *   - A positive value that can be used by the caller as an offset into an
477  *     array of user data. This value is unique for this key, and is the same
478  *     value that was returned when the key was added.
479  */
480 int32_t
481 rte_hash_lookup_with_hash(const struct rte_hash *h,
482                                 const void *key, hash_sig_t sig);
483
484 /**
485  * Calc a hash value by key.
486  * This operation is not multi-process safe.
487  *
488  * @param h
489  *   Hash table to look in.
490  * @param key
491  *   Key to find.
492  * @return
493  *   - hash value
494  */
495 hash_sig_t
496 rte_hash_hash(const struct rte_hash *h, const void *key);
497
498 /**
499  * Find multiple keys in the hash table.
500  * This operation is multi-thread safe with regarding to other lookup threads.
501  * Read-write concurrency can be enabled by setting flag during
502  * table creation.
503  *
504  * @param h
505  *   Hash table to look in.
506  * @param keys
507  *   A pointer to a list of keys to look for.
508  * @param num_keys
509  *   How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
510  * @param hit_mask
511  *   Output containing a bitmask with all successful lookups.
512  * @param data
513  *   Output containing array of data returned from all the successful lookups.
514  * @return
515  *   -EINVAL if there's an error, otherwise number of successful lookups.
516  */
517 int
518 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
519                       uint32_t num_keys, uint64_t *hit_mask, void *data[]);
520
521 /**
522  * @warning
523  * @b EXPERIMENTAL: this API may change without prior notice
524  *
525  * Find multiple keys in the hash table with precomputed hash value array.
526  * This operation is multi-thread safe with regarding to other lookup threads.
527  * Read-write concurrency can be enabled by setting flag during
528  * table creation.
529  *
530  * @param h
531  *   Hash table to look in.
532  * @param keys
533  *   A pointer to a list of keys to look for.
534  * @param sig
535  *   A pointer to a list of precomputed hash values for keys.
536  * @param num_keys
537  *   How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
538  * @param positions
539  *   Output containing a list of values, corresponding to the list of keys that
540  *   can be used by the caller as an offset into an array of user data. These
541  *   values are unique for each key, and are the same values that were returned
542  *   when each key was added. If a key in the list was not found, then -ENOENT
543  *   will be the value.
544  * @return
545  *   -EINVAL if there's an error, otherwise 0.
546  */
547 __rte_experimental
548 int
549 rte_hash_lookup_with_hash_bulk(const struct rte_hash *h, const void **keys,
550                 hash_sig_t *sig, uint32_t num_keys, int32_t *positions);
551
552 /**
553  * @warning
554  * @b EXPERIMENTAL: this API may change without prior notice
555  *
556  * Find multiple keys in the hash table with precomputed hash value array.
557  * This operation is multi-thread safe with regarding to other lookup threads.
558  * Read-write concurrency can be enabled by setting flag during
559  * table creation.
560  *
561  * @param h
562  *   Hash table to look in.
563  * @param keys
564  *   A pointer to a list of keys to look for.
565  * @param sig
566  *   A pointer to a list of precomputed hash values for keys.
567  * @param num_keys
568  *   How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
569  * @param hit_mask
570  *   Output containing a bitmask with all successful lookups.
571  * @param data
572  *   Output containing array of data returned from all the successful lookups.
573  * @return
574  *   -EINVAL if there's an error, otherwise number of successful lookups.
575  */
576 __rte_experimental
577 int
578 rte_hash_lookup_with_hash_bulk_data(const struct rte_hash *h,
579                 const void **keys, hash_sig_t *sig,
580                 uint32_t num_keys, uint64_t *hit_mask, void *data[]);
581
582 /**
583  * Find multiple keys in the hash table.
584  * This operation is multi-thread safe with regarding to other lookup threads.
585  * Read-write concurrency can be enabled by setting flag during
586  * table creation.
587  *
588  * @param h
589  *   Hash table to look in.
590  * @param keys
591  *   A pointer to a list of keys to look for.
592  * @param num_keys
593  *   How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
594  * @param positions
595  *   Output containing a list of values, corresponding to the list of keys that
596  *   can be used by the caller as an offset into an array of user data. These
597  *   values are unique for each key, and are the same values that were returned
598  *   when each key was added. If a key in the list was not found, then -ENOENT
599  *   will be the value.
600  * @return
601  *   -EINVAL if there's an error, otherwise 0.
602  */
603 int
604 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
605                       uint32_t num_keys, int32_t *positions);
606
607 /**
608  * Iterate through the hash table, returning key-value pairs.
609  *
610  * @param h
611  *   Hash table to iterate
612  * @param key
613  *   Output containing the key where current iterator
614  *   was pointing at
615  * @param data
616  *   Output containing the data associated with key.
617  *   Returns NULL if data was not stored.
618  * @param next
619  *   Pointer to iterator. Should be 0 to start iterating the hash table.
620  *   Iterator is incremented after each call of this function.
621  * @return
622  *   Position where key was stored, if successful.
623  *   - -EINVAL if the parameters are invalid.
624  *   - -ENOENT if end of the hash table.
625  */
626 int32_t
627 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next);
628 #ifdef __cplusplus
629 }
630 #endif
631
632 #endif /* _RTE_HASH_H_ */