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_ */