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