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 extendabe 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  * Add a key-value pair to an existing hash table.
 169  * This operation is not multi-thread safe
 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.
 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
 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.
 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
 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  *
 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
 245  * and should only be called from one thread by default.
 246  * Thread safety can be enabled by setting flag during
 247  * table creation.
 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
 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.
 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
 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.
 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.
 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.
 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
 338  *   - -EINVAL if the parameters are invalid.
 339  *   - -ENOENT if no valid key is found in the given position.
 340  */
 341 int
 342 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
 343                                void **key);
 344
 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
 373 /**
 374  * Find a key-value pair in the hash table.
 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.
 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
 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.
 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.
 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.
 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
 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.
 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.
 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.
 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.
 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  * @param sig
 452  *   Precomputed hash value for 'key'.
 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.
 466  * This operation is not multi-thread safe.
 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.
 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.
 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.
 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.
 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_ */