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