1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2010-2017 Intel Corporation 3 */ 4 5 #ifndef __INCLUDE_RTE_TABLE_HASH_H__ 6 #define __INCLUDE_RTE_TABLE_HASH_H__ 7 8 #ifdef __cplusplus 9 extern "C" { 10 #endif 11 12 /** 13 * @file 14 * RTE Table Hash 15 * 16 * These tables use the exact match criterion to uniquely associate data to 17 * lookup keys. 18 * 19 * Hash table types: 20 * 1. Entry add strategy on bucket full: 21 * a. Least Recently Used (LRU): One of the existing keys in the bucket is 22 * deleted and the new key is added in its place. The number of keys in 23 * each bucket never grows bigger than 4. The logic to pick the key to 24 * be dropped from the bucket is LRU. The hash table lookup operation 25 * maintains the order in which the keys in the same bucket are hit, so 26 * every time a key is hit, it becomes the new Most Recently Used (MRU) 27 * key, i.e. the most unlikely candidate for drop. When a key is added 28 * to the bucket, it also becomes the new MRU key. When a key needs to 29 * be picked and dropped, the most likely candidate for drop, i.e. the 30 * current LRU key, is always picked. The LRU logic requires maintaining 31 * specific data structures per each bucket. Use-cases: flow cache, etc. 32 * b. Extendable bucket (ext): The bucket is extended with space for 4 more 33 * keys. This is done by allocating additional memory at table init time, 34 * which is used to create a pool of free keys (the size of this pool is 35 * configurable and always a multiple of 4). On key add operation, the 36 * allocation of a group of 4 keys only happens successfully within the 37 * limit of free keys, otherwise the key add operation fails. On key 38 * delete operation, a group of 4 keys is freed back to the pool of free 39 * keys when the key to be deleted is the only key that was used within 40 * its group of 4 keys at that time. On key lookup operation, if the 41 * current bucket is in extended state and a match is not found in the 42 * first group of 4 keys, the search continues beyond the first group of 43 * 4 keys, potentially until all keys in this bucket are examined. The 44 * extendable bucket logic requires maintaining specific data structures 45 * per table and per each bucket. Use-cases: flow table, etc. 46 * 2. Key size: 47 * a. Configurable key size 48 * b. Single key size (8-byte, 16-byte or 32-byte key size) 49 * 50 ***/ 51 #include <stdint.h> 52 53 #include "rte_table.h" 54 55 /** Hash function */ 56 typedef uint64_t (*rte_table_hash_op_hash)( 57 void *key, 58 void *key_mask, 59 uint32_t key_size, 60 uint64_t seed); 61 62 /** Hash table parameters */ 63 struct rte_table_hash_params { 64 /** Name */ 65 const char *name; 66 67 /** Key size (number of bytes) */ 68 uint32_t key_size; 69 70 /** Byte offset within packet meta-data where the key is located */ 71 uint32_t key_offset; 72 73 /** Key mask */ 74 uint8_t *key_mask; 75 76 /** Number of keys */ 77 uint32_t n_keys; 78 79 /** Number of buckets */ 80 uint32_t n_buckets; 81 82 /** Hash function */ 83 rte_table_hash_op_hash f_hash; 84 85 /** Seed value for the hash function */ 86 uint64_t seed; 87 }; 88 89 /** Extendable bucket hash table operations */ 90 extern struct rte_table_ops rte_table_hash_ext_ops; 91 extern struct rte_table_ops rte_table_hash_key8_ext_ops; 92 extern struct rte_table_ops rte_table_hash_key16_ext_ops; 93 extern struct rte_table_ops rte_table_hash_key32_ext_ops; 94 95 /** LRU hash table operations */ 96 extern struct rte_table_ops rte_table_hash_lru_ops; 97 98 extern struct rte_table_ops rte_table_hash_key8_lru_ops; 99 extern struct rte_table_ops rte_table_hash_key16_lru_ops; 100 extern struct rte_table_ops rte_table_hash_key32_lru_ops; 101 102 #ifdef __cplusplus 103 } 104 #endif 105 106 #endif 107