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