1/* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2016-2017 Intel Corporation 3 */ 4 5#ifndef _RTE_EFD_H_ 6#define _RTE_EFD_H_ 7 8/** 9 * @file 10 * 11 * RTE EFD Table 12 */ 13 14#include <stdint.h> 15 16#ifdef __cplusplus 17extern "C" { 18#endif 19 20/************************************************************************* 21 * User selectable constants 22 *************************************************************************/ 23 24/* 25 * If possible, best lookup performance will be achieved by ensuring that 26 * the entire table fits in the L3 cache. 27 * 28 * Some formulas for calculating various sizes are listed below: 29 * 30 * # of chunks = 31 * 2 ^ (ceiling(log2((requested # of rules) / 32 * (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)))) 33 * 34 * Target # of rules = (# of chunks) * EFD_CHUNK_NUM_GROUPS * 35 * EFD_TARGET_GROUP_NUM_RULES 36 * 37 * Group Size (in bytes) = 4 (per value bit) 38 * 39 * Table size (in bytes) = RTE_EFD_VALUE_NUM_BITS * (# of chunks) * 40 * EFD_CHUNK_NUM_GROUPS * (group size) 41 */ 42 43/** 44 * !!! This parameter should be adjusted for your application !!! 45 * 46 * This parameter adjusts the number of bits of value that can be 47 * stored in the table. 48 * For example, setting the number of bits to 3 will allow storing 8 values 49 * in the table (between 0 and 7). 50 * 51 * This number directly affects the performance of both lookups and insertion. 52 * In general, performance decreases as more bits are stored in the table. 53 * 54 * This number is directly proportional to the size of the online region 55 * used for lookups. 56 * 57 * Note that due to the way the CPU operates on memory, best lookup performance 58 * will be achieved when RTE_EFD_VALUE_NUM_BITS is a multiple of 8. 59 * These values align the hash indexes on 16-byte boundaries. 60 * The greatest performance drop is moving from 8->9 bits, 16->17 bits, etc. 61 * 62 * This value must be between 1 and 32 63 */ 64#ifndef RTE_EFD_VALUE_NUM_BITS 65#define RTE_EFD_VALUE_NUM_BITS (8) 66#endif 67 68/* 69 * EFD_TARGET_GROUP_NUM_RULES: 70 * Adjusts how many groups/chunks are allocated at table creation time 71 * to support the requested number of rules. Higher values pack entries 72 * more tightly in memory, resulting in a smaller memory footprint 73 * for the online table. 74 * This comes at the cost of lower insert/update performance. 75 * 76 * EFD_MAX_GROUP_NUM_RULES: 77 * This adjusts the amount of offline memory allocated to store key/value 78 * pairs for the table. The recommended numbers are upper-bounds for 79 * this parameter 80 * - any higher and it becomes very unlikely that a perfect hash function 81 * can be found for that group size. This value should be at 82 * least 40% larger than EFD_TARGET_GROUP_NUM_RULES 83 * 84 * Recommended values for various lookuptable and hashfunc sizes are: 85 * 86 * HASH_FUNC_SIZE = 16, LOOKUPTBL_SIZE = 16: 87 * EFD_TARGET_GROUP_NUM_RULES = 22 88 * EFD_MAX_GROUP_NUM_RULES = 28 89 */ 90#define EFD_TARGET_GROUP_NUM_RULES (22) 91#define EFD_MAX_GROUP_NUM_RULES (28LU) 92 93#define EFD_MIN_BALANCED_NUM_RULES 5 94 95/** 96 * Maximum number of keys that can be looked up in one call to efd_lookup_bulk 97 */ 98#ifndef RTE_EFD_BURST_MAX 99#define RTE_EFD_BURST_MAX (32) 100#endif 101 102/** Maximum number of characters in efd name.*/ 103#define RTE_EFD_NAMESIZE 32 104 105#if (RTE_EFD_VALUE_NUM_BITS > 0 && RTE_EFD_VALUE_NUM_BITS <= 8) 106typedef uint8_t efd_value_t; 107#elif (RTE_EFD_VALUE_NUM_BITS > 8 && RTE_EFD_VALUE_NUM_BITS <= 16) 108typedef uint16_t efd_value_t; 109#elif (RTE_EFD_VALUE_NUM_BITS > 16 && RTE_EFD_VALUE_NUM_BITS <= 32) 110typedef uint32_t efd_value_t; 111#else 112#error("RTE_EFD_VALUE_NUM_BITS must be in the range [1:32]") 113#endif 114 115#define EFD_LOOKUPTBL_SHIFT (32 - 4) 116typedef uint16_t efd_lookuptbl_t; 117typedef uint16_t efd_hashfunc_t; 118 119/** 120 * Creates an EFD table with a single offline region and multiple per-socket 121 * internally-managed copies of the online table used for lookups 122 * 123 * @param name 124 * EFD table name 125 * @param max_num_rules 126 * Minimum number of rules the table should be sized to hold. 127 * Will be rounded up to the next smallest valid table size 128 * @param key_len 129 * Length of the key 130 * @param online_cpu_socket_bitmask 131 * Bitmask specifying which sockets should get a copy of the online table. 132 * LSB = socket 0, etc. 133 * @param offline_cpu_socket 134 * Identifies the socket where the offline table will be allocated 135 * (and most efficiently accessed in the case of updates/insertions) 136 * 137 * @return 138 * EFD table, or NULL if table allocation failed or the bitmask is invalid 139 */ 140struct rte_efd_table * 141rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len, 142 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket); 143 144/** 145 * Releases the resources from an EFD table 146 * 147 * @param table 148 * Table to free 149 */ 150void 151rte_efd_free(struct rte_efd_table *table); 152 153/** 154 * Find an existing EFD table object and return a pointer to it. 155 * 156 * @param name 157 * Name of the EFD table as passed to rte_efd_create() 158 * @return 159 * Pointer to EFD table or NULL if object not found 160 * with rte_errno set appropriately. Possible rte_errno values include: 161 * - ENOENT - value not available for return 162 */ 163struct rte_efd_table* 164rte_efd_find_existing(const char *name); 165 166#define RTE_EFD_UPDATE_WARN_GROUP_FULL (1) 167#define RTE_EFD_UPDATE_NO_CHANGE (2) 168#define RTE_EFD_UPDATE_FAILED (3) 169 170/** 171 * Computes an updated table entry for the supplied key/value pair. 172 * The update is then immediately applied to the provided table and 173 * all socket-local copies of the chunks are updated. 174 * This operation is not multi-thread safe 175 * and should only be called one from thread. 176 * 177 * @param table 178 * EFD table to reference 179 * @param socket_id 180 * Socket ID to use to lookup existing value (ideally caller's socket id) 181 * @param key 182 * EFD table key to modify 183 * @param value 184 * Value to associate with the key 185 * 186 * @return 187 * RTE_EFD_UPDATE_WARN_GROUP_FULL 188 * Operation is insert, and the last available space in the 189 * key's group was just used 190 * Future inserts may fail as groups fill up 191 * This operation was still successful, and entry contains a valid update 192 * RTE_EFD_UPDATE_FAILED 193 * Either the EFD failed to find a suitable perfect hash or the group was full 194 * This is a fatal error, and the table is now in an indeterminate state 195 * RTE_EFD_UPDATE_NO_CHANGE 196 * Operation resulted in no change to the table (same value already exists) 197 * 0 - success 198 */ 199int 200rte_efd_update(struct rte_efd_table *table, unsigned int socket_id, 201 const void *key, efd_value_t value); 202 203/** 204 * Removes any value currently associated with the specified key from the table 205 * This operation is not multi-thread safe 206 * and should only be called from one thread. 207 * 208 * @param table 209 * EFD table to reference 210 * @param socket_id 211 * Socket ID to use to lookup existing value (ideally caller's socket id) 212 * @param key 213 * EFD table key to delete 214 * @param prev_value 215 * If not NULL, will store the previous value here before deleting it 216 * 217 * @return 218 * 0 - successfully found and deleted the key 219 * nonzero otherwise 220 */ 221int 222rte_efd_delete(struct rte_efd_table *table, unsigned int socket_id, 223 const void *key, efd_value_t *prev_value); 224 225/** 226 * Looks up the value associated with a key 227 * This operation is multi-thread safe. 228 * 229 * NOTE: Lookups will *always* succeed - this is a property of 230 * using a perfect hash table. 231 * If the specified key was never inserted, a pseudorandom answer will be returned. 232 * There is no way to know based on the lookup if the key was ever inserted 233 * originally, so this must be tracked elsewhere. 234 * 235 * @param table 236 * EFD table to reference 237 * @param socket_id 238 * Socket ID to use to lookup existing value (ideally caller's socket id) 239 * @param key 240 * EFD table key to look up 241 * 242 * @return 243 * Value associated with the key, or random junk if they key was never inserted 244 */ 245efd_value_t 246rte_efd_lookup(const struct rte_efd_table *table, unsigned int socket_id, 247 const void *key); 248 249/** 250 * Looks up the value associated with several keys. 251 * This operation is multi-thread safe. 252 * 253 * NOTE: Lookups will *always* succeed - this is a property of 254 * using a perfect hash table. 255 * If the specified key was never inserted, a pseudorandom answer will be returned. 256 * There is no way to know based on the lookup if the key was ever inserted 257 * originally, so this must be tracked elsewhere. 258 * 259 * @param table 260 * EFD table to reference 261 * @param socket_id 262 * Socket ID to use to lookup existing value (ideally caller's socket id) 263 * @param num_keys 264 * Number of keys in the key_list array, must be less than RTE_EFD_BURST_MAX 265 * @param key_list 266 * Array of num_keys pointers which point to keys to look up 267 * @param value_list 268 * Array of size num_keys where lookup values will be stored 269 */ 270void 271rte_efd_lookup_bulk(const struct rte_efd_table *table, unsigned int socket_id, 272 int num_keys, const void **key_list, 273 efd_value_t *value_list); 274 275#ifdef __cplusplus 276} 277#endif 278 279#endif /* _RTE_EFD_H_ */ 280