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