4 * Copyright(c) 2016-2017 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
47 /*************************************************************************
48 * User selectable constants
49 *************************************************************************/
52 * If possible, best lookup performance will be achieved by ensuring that
53 * the entire table fits in the L3 cache.
55 * Some formulas for calculating various sizes are listed below:
58 * 2 ^ (ceiling(log2((requested # of rules) /
59 * (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES))))
61 * Target # of rules = (# of chunks) * EFD_CHUNK_NUM_GROUPS *
62 * EFD_TARGET_GROUP_NUM_RULES
64 * Group Size (in bytes) = 4 (per value bit)
66 * Table size (in bytes) = RTE_EFD_VALUE_NUM_BITS * (# of chunks) *
67 * EFD_CHUNK_NUM_GROUPS * (group size)
71 * !!! This parameter should be adjusted for your application !!!
73 * This parameter adjusts the number of bits of value that can be
74 * stored in the table.
75 * For example, setting the number of bits to 3 will allow storing 8 values
76 * in the table (between 0 and 7).
78 * This number directly affects the performance of both lookups and insertion.
79 * In general, performance decreases as more bits are stored in the table.
81 * This number is directly proportional to the size of the online region
84 * Note that due to the way the CPU operates on memory, best lookup performance
85 * will be achieved when RTE_EFD_VALUE_NUM_BITS is a multiple of 8.
86 * These values align the hash indexes on 16-byte boundaries.
87 * The greatest performance drop is moving from 8->9 bits, 16->17 bits, etc.
89 * This value must be between 1 and 32
91 #ifndef RTE_EFD_VALUE_NUM_BITS
92 #define RTE_EFD_VALUE_NUM_BITS (8)
96 * EFD_TARGET_GROUP_NUM_RULES:
97 * Adjusts how many groups/chunks are allocated at table creation time
98 * to support the requested number of rules. Higher values pack entries
99 * more tightly in memory, resulting in a smaller memory footprint
100 * for the online table.
101 * This comes at the cost of lower insert/update performance.
103 * EFD_MAX_GROUP_NUM_RULES:
104 * This adjusts the amount of offline memory allocated to store key/value
105 * pairs for the table. The recommended numbers are upper-bounds for
107 * - any higher and it becomes very unlikely that a perfect hash function
108 * can be found for that group size. This value should be at
109 * least 40% larger than EFD_TARGET_GROUP_NUM_RULES
111 * Recommended values for various lookuptable and hashfunc sizes are:
113 * HASH_FUNC_SIZE = 16, LOOKUPTBL_SIZE = 16:
114 * EFD_TARGET_GROUP_NUM_RULES = 22
115 * EFD_MAX_GROUP_NUM_RULES = 28
117 #define EFD_TARGET_GROUP_NUM_RULES (22)
118 #define EFD_MAX_GROUP_NUM_RULES (28LU)
120 #define EFD_MIN_BALANCED_NUM_RULES 5
123 * Maximum number of keys that can be looked up in one call to efd_lookup_bulk
125 #ifndef RTE_EFD_BURST_MAX
126 #define RTE_EFD_BURST_MAX (32)
129 /** Maximum number of characters in efd name.*/
130 #define RTE_EFD_NAMESIZE 32
132 #if (RTE_EFD_VALUE_NUM_BITS > 0 && RTE_EFD_VALUE_NUM_BITS <= 8)
133 typedef uint8_t efd_value_t;
134 #elif (RTE_EFD_VALUE_NUM_BITS > 8 && RTE_EFD_VALUE_NUM_BITS <= 16)
135 typedef uint16_t efd_value_t;
136 #elif (RTE_EFD_VALUE_NUM_BITS > 16 && RTE_EFD_VALUE_NUM_BITS <= 32)
137 typedef uint32_t efd_value_t;
139 #error("RTE_EFD_VALUE_NUM_BITS must be in the range [1:32]")
142 #define EFD_LOOKUPTBL_SHIFT (32 - 4)
143 typedef uint16_t efd_lookuptbl_t;
144 typedef uint16_t efd_hashfunc_t;
147 * Creates an EFD table with a single offline region and multiple per-socket
148 * internally-managed copies of the online table used for lookups
152 * @param max_num_rules
153 * Minimum number of rules the table should be sized to hold.
154 * Will be rounded up to the next smallest valid table size
157 * @param online_cpu_socket_bitmask
158 * Bitmask specifying which sockets should get a copy of the online table.
159 * LSB = socket 0, etc.
160 * @param offline_cpu_socket
161 * Identifies the socket where the offline table will be allocated
162 * (and most efficiently accessed in the case of updates/insertions)
165 * EFD table, or NULL if table allocation failed or the bitmask is invalid
167 struct rte_efd_table *
168 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
169 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket);
172 * Releases the resources from an EFD table
178 rte_efd_free(struct rte_efd_table *table);
181 * Find an existing EFD table object and return a pointer to it.
184 * Name of the EFD table as passed to rte_efd_create()
186 * Pointer to EFD table or NULL if object not found
187 * with rte_errno set appropriately. Possible rte_errno values include:
188 * - ENOENT - value not available for return
190 struct rte_efd_table*
191 rte_efd_find_existing(const char *name);
193 #define RTE_EFD_UPDATE_WARN_GROUP_FULL (1)
194 #define RTE_EFD_UPDATE_NO_CHANGE (2)
195 #define RTE_EFD_UPDATE_FAILED (3)
198 * Computes an updated table entry for the supplied key/value pair.
199 * The update is then immediately applied to the provided table and
200 * all socket-local copies of the chunks are updated.
201 * This operation is not multi-thread safe
202 * and should only be called one from thread.
205 * EFD table to reference
207 * Socket ID to use to lookup existing value (ideally caller's socket id)
209 * EFD table key to modify
211 * Value to associate with the key
214 * RTE_EFD_UPDATE_WARN_GROUP_FULL
215 * Operation is insert, and the last available space in the
216 * key's group was just used
217 * Future inserts may fail as groups fill up
218 * This operation was still successful, and entry contains a valid update
219 * RTE_EFD_UPDATE_FAILED
220 * Either the EFD failed to find a suitable perfect hash or the group was full
221 * This is a fatal error, and the table is now in an indeterminite state
222 * RTE_EFD_UPDATE_NO_CHANGE
223 * Operation resulted in no change to the table (same value already exists)
227 rte_efd_update(struct rte_efd_table *table, unsigned int socket_id,
228 const void *key, efd_value_t value);
231 * Removes any value currently associated with the specified key from the table
232 * This operation is not multi-thread safe
233 * and should only be called from one thread.
236 * EFD table to reference
238 * Socket ID to use to lookup existing value (ideally caller's socket id)
240 * EFD table key to delete
242 * If not NULL, will store the previous value here before deleting it
245 * 0 - successfully found and deleted the key
249 rte_efd_delete(struct rte_efd_table *table, unsigned int socket_id,
250 const void *key, efd_value_t *prev_value);
253 * Looks up the value associated with a key
254 * This operation is multi-thread safe.
256 * NOTE: Lookups will *always* succeed - this is a property of
257 * using a perfect hash table.
258 * If the specified key was never inserted, a pseudorandom answer will be returned.
259 * There is no way to know based on the lookup if the key was ever inserted
260 * originally, so this must be tracked elsewhere.
263 * EFD table to reference
265 * Socket ID to use to lookup existing value (ideally caller's socket id)
267 * EFD table key to look up
270 * Value associated with the key, or random junk if they key was never inserted
273 rte_efd_lookup(const struct rte_efd_table *table, unsigned int socket_id,
277 * Looks up the value associated with several keys.
278 * This operation is multi-thread safe.
280 * NOTE: Lookups will *always* succeed - this is a property of
281 * using a perfect hash table.
282 * If the specified key was never inserted, a pseudorandom answer will be returned.
283 * There is no way to know based on the lookup if the key was ever inserted
284 * originally, so this must be tracked elsewhere.
287 * EFD table to reference
289 * Socket ID to use to lookup existing value (ideally caller's socket id)
291 * Number of keys in the key_list array, must be less than RTE_EFD_BURST_MAX
293 * Array of num_keys pointers which point to keys to look up
295 * Array of size num_keys where lookup values will be stored
298 rte_efd_lookup_bulk(const struct rte_efd_table *table, unsigned int socket_id,
299 int num_keys, const void **key_list,
300 efd_value_t *value_list);
306 #endif /* _RTE_EFD_H_ */