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  * 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  */
  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 /**
 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  *
 150  * @param h
 151  *   Hash table to reset
 152  */
 153 void
 154 rte_hash_reset(struct rte_hash *h);
 155
 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
 167 /**
 168  * @warning
 169  * @b EXPERIMENTAL: this API may change without prior notice
 170  *
 171  * Return the maximum key value ID that could possibly be returned by
 172  * rte_hash_add_key function.
 173  *
 174  * @param h
 175  *  Hash table to query from
 176  * @return
 177  *   - -EINVAL if parameters are invalid
 178  *   - A value indicating the max key ID of key slots present in the table.
 179  */
 180 __rte_experimental
 181 int32_t
 182 rte_hash_max_key_id(const struct rte_hash *h);
 183
 184 /**
 185  * Add a key-value pair to an existing hash table.
 186  * This operation is not multi-thread safe
 187  * and should only be called from one thread by default.
 188  * Thread safety can be enabled by setting flag during
 189  * table creation.
 190  * If the key exists already in the table, this API updates its value
 191  * with 'data' passed in this API. It is the responsibility of
 192  * the application to manage any memory associated with the old value.
 193  * The readers might still be using the old value even after this API
 194  * has returned.
 195  *
 196  * @param h
 197  *   Hash table to add the key to.
 198  * @param key
 199  *   Key to add to the hash table.
 200  * @param data
 201  *   Data to add to the hash table.
 202  * @return
 203  *   - 0 if added successfully
 204  *   - -EINVAL if the parameters are invalid.
 205  *   - -ENOSPC if there is no space in the hash for this key.
 206  */
 207 int
 208 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data);
 209
 210 /**
 211  * Add a key-value pair with a pre-computed hash value
 212  * to an existing hash table.
 213  * This operation is not multi-thread safe
 214  * and should only be called from one thread by default.
 215  * Thread safety can be enabled by setting flag during
 216  * table creation.
 217  * If the key exists already in the table, this API updates its value
 218  * with 'data' passed in this API. It is the responsibility of
 219  * the application to manage any memory associated with the old value.
 220  * The readers might still be using the old value even after this API
 221  * has returned.
 222  *
 223  * @param h
 224  *   Hash table to add the key to.
 225  * @param key
 226  *   Key to add to the hash table.
 227  * @param sig
 228  *   Precomputed hash value for 'key'
 229  * @param data
 230  *   Data to add to the hash table.
 231  * @return
 232  *   - 0 if added successfully
 233  *   - -EINVAL if the parameters are invalid.
 234  *   - -ENOSPC if there is no space in the hash for this key.
 235  */
 236 int32_t
 237 rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key,
 238                                                 hash_sig_t sig, void *data);
 239
 240 /**
 241  * Add a key to an existing hash table. This operation is not multi-thread safe
 242  * and should only be called from one thread by default.
 243  * Thread safety can be enabled by setting flag during
 244  * table creation.
 245  *
 246  * @param h
 247  *   Hash table to add the key to.
 248  * @param key
 249  *   Key to add to the hash table.
 250  * @return
 251  *   - -EINVAL if the parameters are invalid.
 252  *   - -ENOSPC if there is no space in the hash for this key.
 253  *   - A positive value that can be used by the caller as an offset into an
 254  *     array of user data. This value is unique for this key. This
 255  *     unique key id may be larger than the user specified entry count
 256  *     when RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD flag is set.
 257  */
 258 int32_t
 259 rte_hash_add_key(const struct rte_hash *h, const void *key);
 260
 261 /**
 262  * Add a key to an existing hash table.
 263  * This operation is not multi-thread safe
 264  * and should only be called from one thread by default.
 265  * Thread safety can be enabled by setting flag during
 266  * table creation.
 267  *
 268  * @param h
 269  *   Hash table to add the key to.
 270  * @param key
 271  *   Key to add to the hash table.
 272  * @param sig
 273  *   Precomputed hash value for 'key'.
 274  * @return
 275  *   - -EINVAL if the parameters are invalid.
 276  *   - -ENOSPC if there is no space in the hash for this key.
 277  *   - A positive value that can be used by the caller as an offset into an
 278  *     array of user data. This value is unique for this key. This
 279  *     unique key ID may be larger than the user specified entry count
 280  *     when RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD flag is set.
 281  */
 282 int32_t
 283 rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
 284
 285 /**
 286  * Remove a key from an existing hash table.
 287  * This operation is not multi-thread safe
 288  * and should only be called from one thread by default.
 289  * Thread safety can be enabled by setting flag during
 290  * table creation.
 291  * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or
 292  * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled,
 293  * the key index returned by rte_hash_add_key_xxx APIs will not be
 294  * freed by this API. rte_hash_free_key_with_position API must be called
 295  * additionally to free the index associated with the key.
 296  * rte_hash_free_key_with_position API should be called after all
 297  * the readers have stopped referencing the entry corresponding to
 298  * this key. RCU mechanisms could be used to determine such a state.
 299  *
 300  * @param h
 301  *   Hash table to remove the key from.
 302  * @param key
 303  *   Key to remove from the hash table.
 304  * @return
 305  *   - -EINVAL if the parameters are invalid.
 306  *   - -ENOENT if the key is not found.
 307  *   - A positive value that can be used by the caller as an offset into an
 308  *     array of user data. This value is unique for this key, and is the same
 309  *     value that was returned when the key was added.
 310  */
 311 int32_t
 312 rte_hash_del_key(const struct rte_hash *h, const void *key);
 313
 314 /**
 315  * Remove a key from an existing hash table.
 316  * This operation is not multi-thread safe
 317  * and should only be called from one thread by default.
 318  * Thread safety can be enabled by setting flag during
 319  * table creation.
 320  * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or
 321  * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled,
 322  * the key index returned by rte_hash_add_key_xxx APIs will not be
 323  * freed by this API. rte_hash_free_key_with_position API must be called
 324  * additionally to free the index associated with the key.
 325  * rte_hash_free_key_with_position API should be called after all
 326  * the readers have stopped referencing the entry corresponding to
 327  * this key. RCU mechanisms could be used to determine such a state.
 328  *
 329  * @param h
 330  *   Hash table to remove the key from.
 331  * @param key
 332  *   Key to remove from the hash table.
 333  * @param sig
 334  *   Precomputed hash value for 'key'.
 335  * @return
 336  *   - -EINVAL if the parameters are invalid.
 337  *   - -ENOENT if the key is not found.
 338  *   - A positive value that can be used by the caller as an offset into an
 339  *     array of user data. This value is unique for this key, and is the same
 340  *     value that was returned when the key was added.
 341  */
 342 int32_t
 343 rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
 344
 345 /**
 346  * Find a key in the hash table given the position.
 347  * This operation is multi-thread safe with regarding to other lookup threads.
 348  * Read-write concurrency can be enabled by setting flag during
 349  * table creation.
 350  *
 351  * @param h
 352  *   Hash table to get the key from.
 353  * @param position
 354  *   Position returned when the key was inserted.
 355  * @param key
 356  *   Output containing a pointer to the key
 357  * @return
 358  *   - 0 if retrieved successfully
 359  *   - -EINVAL if the parameters are invalid.
 360  *   - -ENOENT if no valid key is found in the given position.
 361  */
 362 int
 363 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
 364                                void **key);
 365
 366 /**
 367  * @warning
 368  * @b EXPERIMENTAL: this API may change without prior notice
 369  *
 370  * Free a hash key in the hash table given the position
 371  * of the key. This operation is not multi-thread safe and should
 372  * only be called from one thread by default. Thread safety
 373  * can be enabled by setting flag during table creation.
 374  * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or
 375  * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled,
 376  * the key index returned by rte_hash_del_key_xxx APIs must be freed
 377  * using this API. This API should be called after all the readers
 378  * have stopped referencing the entry corresponding to this key.
 379  * RCU mechanisms could be used to determine such a state.
 380  * This API does not validate if the key is already freed.
 381  *
 382  * @param h
 383  *   Hash table to free the key from.
 384  * @param position
 385  *   Position returned when the key was deleted.
 386  * @return
 387  *   - 0 if freed successfully
 388  *   - -EINVAL if the parameters are invalid.
 389  */
 390 __rte_experimental
 391 int
 392 rte_hash_free_key_with_position(const struct rte_hash *h,
 393                                 const int32_t position);
 394
 395 /**
 396  * Find a key-value pair in the hash table.
 397  * This operation is multi-thread safe with regarding to other lookup threads.
 398  * Read-write concurrency can be enabled by setting flag during
 399  * table creation.
 400  *
 401  * @param h
 402  *   Hash table to look in.
 403  * @param key
 404  *   Key to find.
 405  * @param data
 406  *   Output with pointer to data returned from the hash table.
 407  * @return
 408  *   - A positive value that can be used by the caller as an offset into an
 409  *     array of user data. This value is unique for this key, and is the same
 410  *     value that was returned when the key was added.
 411  *   - -EINVAL if the parameters are invalid.
 412  *   - -ENOENT if the key is not found.
 413  */
 414 int
 415 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data);
 416
 417 /**
 418  * Find a key-value pair with a pre-computed hash value
 419  * to an existing hash table.
 420  * This operation is multi-thread safe with regarding to other lookup threads.
 421  * Read-write concurrency can be enabled by setting flag during
 422  * table creation.
 423  *
 424  * @param h
 425  *   Hash table to look in.
 426  * @param key
 427  *   Key to find.
 428  * @param sig
 429  *   Precomputed hash value for 'key'
 430  * @param data
 431  *   Output with pointer to data returned from the hash table.
 432  * @return
 433  *   - A positive value that can be used by the caller as an offset into an
 434  *     array of user data. This value is unique for this key, and is the same
 435  *     value that was returned when the key was added.
 436  *   - -EINVAL if the parameters are invalid.
 437  *   - -ENOENT if the key is not found.
 438  */
 439 int
 440 rte_hash_lookup_with_hash_data(const struct rte_hash *h, const void *key,
 441                                         hash_sig_t sig, void **data);
 442
 443 /**
 444  * Find a key in the hash table.
 445  * This operation is multi-thread safe with regarding to other lookup threads.
 446  * Read-write concurrency can be enabled by setting flag during
 447  * table creation.
 448  *
 449  * @param h
 450  *   Hash table to look in.
 451  * @param key
 452  *   Key to find.
 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(const struct rte_hash *h, const void *key);
 462
 463 /**
 464  * Find a key in the hash table.
 465  * This operation is multi-thread safe with regarding to other lookup threads.
 466  * Read-write concurrency can be enabled by setting flag during
 467  * table creation.
 468  *
 469  * @param h
 470  *   Hash table to look in.
 471  * @param key
 472  *   Key to find.
 473  * @param sig
 474  *   Precomputed hash value for 'key'.
 475  * @return
 476  *   - -EINVAL if the parameters are invalid.
 477  *   - -ENOENT if the key is not found.
 478  *   - A positive value that can be used by the caller as an offset into an
 479  *     array of user data. This value is unique for this key, and is the same
 480  *     value that was returned when the key was added.
 481  */
 482 int32_t
 483 rte_hash_lookup_with_hash(const struct rte_hash *h,
 484                                 const void *key, hash_sig_t sig);
 485
 486 /**
 487  * Calc a hash value by key.
 488  * This operation is not multi-process safe.
 489  *
 490  * @param h
 491  *   Hash table to look in.
 492  * @param key
 493  *   Key to find.
 494  * @return
 495  *   - hash value
 496  */
 497 hash_sig_t
 498 rte_hash_hash(const struct rte_hash *h, const void *key);
 499
 500 /**
 501  * Find multiple keys 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 keys
 509  *   A pointer to a list of keys to look for.
 510  * @param num_keys
 511  *   How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
 512  * @param hit_mask
 513  *   Output containing a bitmask with all successful lookups.
 514  * @param data
 515  *   Output containing array of data returned from all the successful lookups.
 516  * @return
 517  *   -EINVAL if there's an error, otherwise number of successful lookups.
 518  */
 519 int
 520 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
 521                       uint32_t num_keys, uint64_t *hit_mask, void *data[]);
 522
 523 /**
 524  * Find multiple keys in the hash table.
 525  * This operation is multi-thread safe with regarding to other lookup threads.
 526  * Read-write concurrency can be enabled by setting flag during
 527  * table creation.
 528  *
 529  * @param h
 530  *   Hash table to look in.
 531  * @param keys
 532  *   A pointer to a list of keys to look for.
 533  * @param num_keys
 534  *   How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
 535  * @param positions
 536  *   Output containing a list of values, corresponding to the list of keys that
 537  *   can be used by the caller as an offset into an array of user data. These
 538  *   values are unique for each key, and are the same values that were returned
 539  *   when each key was added. If a key in the list was not found, then -ENOENT
 540  *   will be the value.
 541  * @return
 542  *   -EINVAL if there's an error, otherwise 0.
 543  */
 544 int
 545 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
 546                       uint32_t num_keys, int32_t *positions);
 547
 548 /**
 549  * Iterate through the hash table, returning key-value pairs.
 550  *
 551  * @param h
 552  *   Hash table to iterate
 553  * @param key
 554  *   Output containing the key where current iterator
 555  *   was pointing at
 556  * @param data
 557  *   Output containing the data associated with key.
 558  *   Returns NULL if data was not stored.
 559  * @param next
 560  *   Pointer to iterator. Should be 0 to start iterating the hash table.
 561  *   Iterator is incremented after each call of this function.
 562  * @return
 563  *   Position where key was stored, if successful.
 564  *   - -EINVAL if the parameters are invalid.
 565  *   - -ENOENT if end of the hash table.
 566  */
 567 int32_t
 568 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next);
 569 #ifdef __cplusplus
 570 }
 571 #endif
 572
 573 #endif /* _RTE_HASH_H_ */