]>
Commit | Line | Data |
---|---|---|
9f95a23c TL |
1 | /* SPDX-License-Identifier: BSD-3-Clause |
2 | * Copyright(c) 2016-2017 Intel Corporation | |
11fdf7f2 TL |
3 | */ |
4 | #include <stdio.h> | |
5 | #include <string.h> | |
6 | #include <stdint.h> | |
7 | #include <inttypes.h> | |
8 | #include <errno.h> | |
9 | #include <stdarg.h> | |
10 | #include <sys/queue.h> | |
11 | ||
9f95a23c | 12 | #include <rte_string_fns.h> |
11fdf7f2 TL |
13 | #include <rte_log.h> |
14 | #include <rte_eal_memconfig.h> | |
15 | #include <rte_errno.h> | |
16 | #include <rte_malloc.h> | |
11fdf7f2 TL |
17 | #include <rte_prefetch.h> |
18 | #include <rte_branch_prediction.h> | |
19 | #include <rte_memcpy.h> | |
20 | #include <rte_ring.h> | |
21 | #include <rte_jhash.h> | |
22 | #include <rte_hash_crc.h> | |
23 | ||
24 | #include "rte_efd.h" | |
25 | #if defined(RTE_ARCH_X86) | |
26 | #include "rte_efd_x86.h" | |
9f95a23c TL |
27 | #elif defined(RTE_ARCH_ARM64) |
28 | #include "rte_efd_arm64.h" | |
11fdf7f2 TL |
29 | #endif |
30 | ||
31 | #define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len)) | |
32 | /** Hash function used to determine chunk_id and bin_id for a group */ | |
33 | #define EFD_HASH(key, table) \ | |
34 | (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34)) | |
35 | /** Hash function used as constant component of perfect hash search */ | |
36 | #define EFD_HASHFUNCA(key, table) \ | |
37 | (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35)) | |
38 | /** Hash function used as multiplicative component of perfect hash search */ | |
39 | #define EFD_HASHFUNCB(key, table) \ | |
40 | (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36)) | |
41 | ||
42 | /************************************************************************* | |
43 | * Fixed constants | |
44 | *************************************************************************/ | |
45 | ||
46 | /* These parameters are fixed by the efd_bin_to_group balancing table */ | |
47 | #define EFD_CHUNK_NUM_GROUPS (64) | |
48 | #define EFD_CHUNK_NUM_BINS (256) | |
49 | #define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \ | |
50 | (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS) | |
51 | ||
52 | /* | |
53 | * Target number of rules that each chunk is created to handle. | |
54 | * Used when initially allocating the table | |
55 | */ | |
56 | #define EFD_TARGET_CHUNK_NUM_RULES \ | |
57 | (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES) | |
58 | /* | |
59 | * Max number of rules that each chunk is created to handle. | |
60 | * Used when initially allocating the table | |
61 | */ | |
62 | #define EFD_TARGET_CHUNK_MAX_NUM_RULES \ | |
63 | (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES) | |
64 | ||
65 | /** This is fixed based on the bin_to_group permutation array */ | |
66 | #define EFD_MAX_GROUP_NUM_BINS (16) | |
67 | ||
68 | /** | |
69 | * The end of the chunks array needs some extra padding to ensure | |
70 | * that vectorization over-reads on the last online chunk stay within | |
71 | allocated memory | |
72 | */ | |
73 | #define EFD_NUM_CHUNK_PADDING_BYTES (256) | |
74 | ||
75 | /* All different internal lookup functions */ | |
76 | enum efd_lookup_internal_function { | |
77 | EFD_LOOKUP_SCALAR = 0, | |
78 | EFD_LOOKUP_AVX2, | |
9f95a23c | 79 | EFD_LOOKUP_NEON, |
11fdf7f2 TL |
80 | EFD_LOOKUP_NUM |
81 | }; | |
82 | ||
83 | TAILQ_HEAD(rte_efd_list, rte_tailq_entry); | |
84 | ||
85 | static struct rte_tailq_elem rte_efd_tailq = { | |
86 | .name = "RTE_EFD", | |
87 | }; | |
88 | EAL_REGISTER_TAILQ(rte_efd_tailq); | |
89 | ||
90 | /** Internal permutation array used to shuffle bins into pseudorandom groups */ | |
91 | const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = { | |
92 | { | |
93 | 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, | |
94 | 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, | |
95 | 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, | |
96 | 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, | |
97 | 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, | |
98 | 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, | |
99 | 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, | |
100 | 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, | |
101 | 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35, | |
102 | 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39, | |
103 | 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43, | |
104 | 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, | |
105 | 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51, | |
106 | 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, | |
107 | 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59, | |
108 | 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63 | |
109 | }, | |
110 | { | |
111 | 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5, | |
112 | 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6, | |
113 | 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7, | |
114 | 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34, | |
115 | 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18, | |
116 | 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27, | |
117 | 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55, | |
118 | 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41, | |
119 | 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43, | |
120 | 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13, | |
121 | 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27, | |
122 | 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39, | |
123 | 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42, | |
124 | 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10, | |
125 | 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30, | |
126 | 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50 | |
127 | }, | |
128 | { | |
129 | 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54, | |
130 | 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1, | |
131 | 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22, | |
132 | 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38, | |
133 | 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51, | |
134 | 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30, | |
135 | 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9, | |
136 | 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28, | |
137 | 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21, | |
138 | 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8, | |
139 | 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57, | |
140 | 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23, | |
141 | 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60, | |
142 | 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4, | |
143 | 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23, | |
144 | 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0 | |
145 | }, | |
146 | { | |
147 | 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0, | |
148 | 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26, | |
149 | 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54, | |
150 | 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18, | |
151 | 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50, | |
152 | 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4, | |
153 | 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41, | |
154 | 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47, | |
155 | 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51, | |
156 | 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11, | |
157 | 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2, | |
158 | 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50, | |
159 | 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52, | |
160 | 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42, | |
161 | 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20, | |
162 | 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52 | |
163 | }, | |
164 | }; | |
165 | ||
166 | /************************************************************************* | |
167 | * Offline region structures | |
168 | *************************************************************************/ | |
169 | ||
170 | /** Online group containing number of rules, values, keys and their bins | |
171 | * for EFD_MAX_GROUP_NUM_RULES rules. | |
172 | */ | |
173 | struct efd_offline_group_rules { | |
174 | uint32_t num_rules; | |
175 | /**< Sum of the number of rules in all bins assigned to this group. */ | |
176 | ||
177 | uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES]; | |
178 | /**< Array with all keys of the group. */ | |
179 | efd_value_t value[EFD_MAX_GROUP_NUM_RULES]; | |
180 | /**< Array with all values of the keys of the group. */ | |
181 | ||
182 | uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES]; | |
183 | /**< Stores the bin for each correspending key to | |
184 | * avoid having to recompute it | |
185 | */ | |
186 | }; | |
187 | ||
188 | /** Offline chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules. | |
189 | * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk. | |
190 | */ | |
191 | struct efd_offline_chunk_rules { | |
192 | uint16_t num_rules; | |
193 | /**< Number of rules in the entire chunk; | |
194 | * used to detect unbalanced groups | |
195 | */ | |
196 | ||
197 | struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS]; | |
198 | /**< Array of all groups in the chunk. */ | |
199 | }; | |
200 | ||
201 | /************************************************************************* | |
202 | * Online region structures | |
203 | *************************************************************************/ | |
204 | ||
205 | /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */ | |
206 | struct efd_online_group_entry { | |
207 | efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS]; | |
208 | efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS]; | |
209 | } __attribute__((__packed__)); | |
210 | ||
211 | /** | |
212 | * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules. | |
213 | * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk. | |
214 | */ | |
215 | struct efd_online_chunk { | |
216 | uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8]; | |
217 | /**< This is a packed indirection index into the 'groups' array. | |
218 | * Each byte contains four two-bit values which index into | |
219 | * the efd_bin_to_group array. | |
220 | * The efd_bin_to_group array returns the index into the groups array | |
221 | */ | |
222 | ||
223 | struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS]; | |
224 | /**< Array of all the groups in the chunk. */ | |
225 | } __attribute__((__packed__)); | |
226 | ||
227 | /** | |
228 | * EFD table structure | |
229 | */ | |
230 | struct rte_efd_table { | |
231 | char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */ | |
232 | ||
233 | uint32_t key_len; /**< Length of the key stored offline */ | |
234 | ||
235 | uint32_t max_num_rules; | |
236 | /**< Static maximum number of entries the table was constructed to hold. */ | |
237 | ||
238 | uint32_t num_rules; | |
239 | /**< Number of entries currently in the table . */ | |
240 | ||
241 | uint32_t num_chunks; | |
242 | /**< Number of chunks in the table needed to support num_rules. */ | |
243 | ||
244 | uint32_t num_chunks_shift; | |
245 | /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */ | |
246 | ||
247 | enum efd_lookup_internal_function lookup_fn; | |
248 | /**< Indicates which lookup function to use. */ | |
249 | ||
250 | struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES]; | |
251 | /**< Dynamic array of size num_chunks of chunk records. */ | |
252 | ||
253 | struct efd_offline_chunk_rules *offline_chunks; | |
254 | /**< Dynamic array of size num_chunks of key-value pairs. */ | |
255 | ||
256 | struct rte_ring *free_slots; | |
257 | /**< Ring that stores all indexes of the free slots in the key table */ | |
258 | ||
259 | uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */ | |
260 | }; | |
261 | ||
262 | /** | |
263 | * Computes the chunk ID for a given key hash | |
264 | * | |
265 | * @param table | |
266 | * EFD table to reference | |
267 | * @param hashed_key | |
268 | * 32-bit key hash returned by EFD_HASH | |
269 | * | |
270 | * @return | |
271 | * chunk ID containing this key hash | |
272 | */ | |
273 | static inline uint32_t | |
274 | efd_get_chunk_id(const struct rte_efd_table * const table, | |
275 | const uint32_t hashed_key) | |
276 | { | |
277 | return hashed_key & (table->num_chunks - 1); | |
278 | } | |
279 | ||
280 | /** | |
281 | * Computes the bin ID for a given key hash | |
282 | * | |
283 | * @param table | |
284 | * EFD table to reference | |
285 | * @param hashed_key | |
286 | * 32-bit key hash returned by EFD_HASH | |
287 | * | |
288 | * @return bin ID containing this key hash | |
289 | */ | |
290 | static inline uint32_t | |
291 | efd_get_bin_id(const struct rte_efd_table * const table, | |
292 | const uint32_t hashed_key) | |
293 | { | |
294 | return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1); | |
295 | } | |
296 | ||
297 | /** | |
298 | * Looks up the current permutation choice for a particular bin in the online table | |
299 | * | |
300 | * @param table | |
301 | * EFD table to reference | |
302 | * @param socket_id | |
303 | * Socket ID to use to look up existing values (ideally caller's socket id) | |
304 | * @param chunk_id | |
305 | * Chunk ID of bin to look up | |
306 | * @param bin_id | |
307 | * Bin ID to look up | |
308 | * | |
309 | * @return | |
310 | * Currently active permutation choice in the online table | |
311 | */ | |
312 | static inline uint8_t | |
313 | efd_get_choice(const struct rte_efd_table * const table, | |
314 | const unsigned int socket_id, const uint32_t chunk_id, | |
315 | const uint32_t bin_id) | |
316 | { | |
317 | struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id]; | |
318 | ||
319 | /* | |
320 | * Grab the chunk (byte) that contains the choices | |
321 | * for four neighboring bins. | |
322 | */ | |
323 | uint8_t choice_chunk = | |
324 | chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS]; | |
325 | ||
326 | /* | |
327 | * Compute the offset into the chunk that contains | |
328 | * the group_id lookup position | |
329 | */ | |
330 | int offset = (bin_id & 0x3) * 2; | |
331 | ||
332 | /* Extract from the byte just the desired lookup position */ | |
333 | return (uint8_t) ((choice_chunk >> offset) & 0x3); | |
334 | } | |
335 | ||
336 | /** | |
337 | * Compute the chunk_id and bin_id for a given key | |
338 | * | |
339 | * @param table | |
340 | * EFD table to reference | |
341 | * @param key | |
342 | * Key to hash and find location of | |
343 | * @param chunk_id | |
344 | * Computed chunk ID | |
345 | * @param bin_id | |
346 | * Computed bin ID | |
347 | * | |
348 | */ | |
349 | static inline void | |
350 | efd_compute_ids(const struct rte_efd_table * const table, | |
351 | const void *key, uint32_t * const chunk_id, uint32_t * const bin_id) | |
352 | { | |
353 | /* Compute the position of the entry in the hash table */ | |
354 | uint32_t h = EFD_HASH(key, table); | |
355 | ||
356 | /* Compute the chunk_id where that entry can be found */ | |
357 | *chunk_id = efd_get_chunk_id(table, h); | |
358 | ||
359 | /* | |
360 | * Compute the bin within that chunk where the entry | |
361 | * can be found (0 - 255) | |
362 | */ | |
363 | *bin_id = efd_get_bin_id(table, h); | |
364 | } | |
365 | ||
366 | /** | |
367 | * Search for a hash function for a group that satisfies all group results | |
368 | */ | |
369 | static inline int | |
370 | efd_search_hash(struct rte_efd_table * const table, | |
371 | const struct efd_offline_group_rules * const off_group, | |
372 | struct efd_online_group_entry * const on_group) | |
373 | { | |
374 | efd_hashfunc_t hash_idx; | |
375 | efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS]; | |
376 | efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS]; | |
377 | ||
378 | uint32_t i, j, rule_id; | |
379 | uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES]; | |
380 | uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES]; | |
381 | uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES]; | |
382 | ||
383 | ||
384 | rte_prefetch0(off_group->value); | |
385 | ||
386 | /* | |
387 | * Prepopulate the hash_val tables by running the two hash functions | |
388 | * for each provided rule | |
389 | */ | |
390 | for (i = 0; i < off_group->num_rules; i++) { | |
391 | void *key_stored = EFD_KEY(off_group->key_idx[i], table); | |
392 | hash_val_b[i] = EFD_HASHFUNCB(key_stored, table); | |
393 | hash_val_a[i] = EFD_HASHFUNCA(key_stored, table); | |
394 | } | |
395 | ||
396 | for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) { | |
397 | hash_idx = on_group->hash_idx[i]; | |
398 | start_hash_idx[i] = hash_idx; | |
399 | start_lookup_table[i] = on_group->lookup_table[i]; | |
400 | ||
401 | do { | |
402 | efd_lookuptbl_t lookup_table = 0; | |
403 | efd_lookuptbl_t lookup_table_complement = 0; | |
404 | ||
405 | for (rule_id = 0; rule_id < off_group->num_rules; rule_id++) | |
406 | hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx * | |
407 | hash_val_b[rule_id]); | |
408 | ||
409 | /* | |
410 | * The goal here is to find a hash function for this | |
411 | * particular bit entry that meets the following criteria: | |
412 | * The most significant bits of the hash result define a | |
413 | * shift into the lookup table where the bit will be stored | |
414 | */ | |
415 | ||
416 | /* Iterate over each provided rule */ | |
417 | for (rule_id = 0; rule_id < off_group->num_rules; | |
418 | rule_id++) { | |
419 | /* | |
420 | * Use the few most significant bits (number based on | |
421 | * EFD_LOOKUPTBL_SIZE) to see what position the | |
422 | * expected bit should be set in the lookup_table | |
423 | */ | |
424 | uint32_t bucket_idx = hash_val[rule_id] >> | |
425 | EFD_LOOKUPTBL_SHIFT; | |
426 | ||
427 | /* | |
428 | * Get the current bit of interest. | |
429 | * This only find an appropriate hash function | |
430 | * for one bit at a time of the rule | |
431 | */ | |
432 | efd_lookuptbl_t expected = | |
433 | (off_group->value[rule_id] >> i) & 0x1; | |
434 | ||
435 | /* | |
436 | * Add the expected bit (if set) to a map | |
437 | * (lookup_table). Also set its complement | |
438 | * in lookup_table_complement | |
439 | */ | |
440 | lookup_table |= expected << bucket_idx; | |
441 | lookup_table_complement |= (1 - expected) | |
442 | << bucket_idx; | |
443 | ||
444 | /* | |
445 | * If ever the hash function of two different | |
446 | * elements result in different values at the | |
447 | * same location in the lookup_table, | |
448 | * the current hash_idx is not valid. | |
449 | */ | |
450 | if (lookup_table & lookup_table_complement) | |
451 | break; | |
452 | } | |
453 | ||
454 | /* | |
455 | * Check if the previous loop completed without | |
456 | * breaking early | |
457 | */ | |
458 | if (rule_id == off_group->num_rules) { | |
459 | /* | |
460 | * Current hash function worked, store it | |
461 | * for the current group | |
462 | */ | |
463 | on_group->hash_idx[i] = hash_idx; | |
464 | on_group->lookup_table[i] = lookup_table; | |
465 | ||
466 | /* | |
467 | * Make sure that the hash function has changed | |
468 | * from the starting value | |
469 | */ | |
470 | hash_idx = start_hash_idx[i] + 1; | |
471 | break; | |
472 | } | |
473 | hash_idx++; | |
474 | ||
475 | } while (hash_idx != start_hash_idx[i]); | |
476 | ||
477 | /* Failed to find perfect hash for this group */ | |
478 | if (hash_idx == start_hash_idx[i]) { | |
479 | /* | |
480 | * Restore previous hash_idx and lookup_table | |
481 | * for all value bits | |
482 | */ | |
483 | for (j = 0; j < i; j++) { | |
484 | on_group->hash_idx[j] = start_hash_idx[j]; | |
485 | on_group->lookup_table[j] = start_lookup_table[j]; | |
486 | } | |
487 | return 1; | |
488 | } | |
489 | } | |
490 | ||
491 | return 0; | |
492 | } | |
493 | ||
494 | struct rte_efd_table * | |
495 | rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len, | |
496 | uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket) | |
497 | { | |
498 | struct rte_efd_table *table = NULL; | |
499 | uint8_t *key_array = NULL; | |
500 | uint32_t num_chunks, num_chunks_shift; | |
501 | uint8_t socket_id; | |
502 | struct rte_efd_list *efd_list = NULL; | |
503 | struct rte_tailq_entry *te; | |
504 | uint64_t offline_table_size; | |
505 | char ring_name[RTE_RING_NAMESIZE]; | |
506 | struct rte_ring *r = NULL; | |
507 | unsigned int i; | |
508 | ||
509 | efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list); | |
510 | ||
511 | if (online_cpu_socket_bitmask == 0) { | |
512 | RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled " | |
513 | "in the bitmask\n"); | |
514 | return NULL; | |
515 | } | |
516 | ||
517 | if (max_num_rules == 0) { | |
518 | RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n"); | |
519 | return NULL; | |
520 | } | |
521 | ||
522 | /* | |
523 | * Compute the minimum number of chunks (smallest power of 2) | |
524 | * that can hold all of the rules | |
525 | */ | |
526 | if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0) | |
527 | num_chunks = rte_align32pow2(max_num_rules / | |
528 | EFD_TARGET_CHUNK_NUM_RULES); | |
529 | else | |
530 | num_chunks = rte_align32pow2((max_num_rules / | |
531 | EFD_TARGET_CHUNK_NUM_RULES) + 1); | |
532 | ||
533 | num_chunks_shift = rte_bsf32(num_chunks); | |
534 | ||
535 | rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); | |
536 | ||
537 | /* | |
538 | * Guarantee there's no existing: this is normally already checked | |
539 | * by ring creation above | |
540 | */ | |
541 | TAILQ_FOREACH(te, efd_list, next) | |
542 | { | |
543 | table = (struct rte_efd_table *) te->data; | |
544 | if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0) | |
545 | break; | |
546 | } | |
547 | ||
548 | table = NULL; | |
549 | if (te != NULL) { | |
550 | rte_errno = EEXIST; | |
551 | te = NULL; | |
552 | goto error_unlock_exit; | |
553 | } | |
554 | ||
555 | te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0); | |
556 | if (te == NULL) { | |
557 | RTE_LOG(ERR, EFD, "tailq entry allocation failed\n"); | |
558 | goto error_unlock_exit; | |
559 | } | |
560 | ||
561 | /* Create a new EFD table management structure */ | |
9f95a23c | 562 | table = rte_zmalloc_socket(NULL, |
11fdf7f2 TL |
563 | sizeof(struct rte_efd_table), |
564 | RTE_CACHE_LINE_SIZE, | |
565 | offline_cpu_socket); | |
566 | if (table == NULL) { | |
567 | RTE_LOG(ERR, EFD, "Allocating EFD table management structure" | |
568 | " on socket %u failed\n", | |
569 | offline_cpu_socket); | |
570 | goto error_unlock_exit; | |
571 | } | |
572 | ||
573 | ||
574 | RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure " | |
575 | "on socket %u\n", offline_cpu_socket); | |
576 | ||
577 | table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES; | |
578 | table->num_rules = 0; | |
579 | table->num_chunks = num_chunks; | |
580 | table->num_chunks_shift = num_chunks_shift; | |
581 | table->key_len = key_len; | |
582 | ||
583 | /* key_array */ | |
9f95a23c | 584 | key_array = rte_zmalloc_socket(NULL, |
11fdf7f2 TL |
585 | table->max_num_rules * table->key_len, |
586 | RTE_CACHE_LINE_SIZE, | |
587 | offline_cpu_socket); | |
588 | if (key_array == NULL) { | |
589 | RTE_LOG(ERR, EFD, "Allocating key array" | |
590 | " on socket %u failed\n", | |
591 | offline_cpu_socket); | |
592 | goto error_unlock_exit; | |
593 | } | |
594 | table->keys = key_array; | |
9f95a23c | 595 | strlcpy(table->name, name, sizeof(table->name)); |
11fdf7f2 TL |
596 | |
597 | RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks," | |
598 | " which potentially supports %u entries\n", | |
599 | num_chunks, table->max_num_rules); | |
600 | ||
601 | /* Make sure all the allocatable table pointers are NULL initially */ | |
602 | for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) | |
603 | table->chunks[socket_id] = NULL; | |
604 | table->offline_chunks = NULL; | |
605 | ||
606 | /* | |
607 | * Allocate one online table per socket specified | |
608 | * in the user-supplied bitmask | |
609 | */ | |
610 | uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) + | |
611 | EFD_NUM_CHUNK_PADDING_BYTES; | |
612 | ||
613 | for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) { | |
614 | if ((online_cpu_socket_bitmask >> socket_id) & 0x01) { | |
615 | /* | |
616 | * Allocate all of the EFD table chunks (the online portion) | |
617 | * as a continuous block | |
618 | */ | |
619 | table->chunks[socket_id] = | |
9f95a23c | 620 | rte_zmalloc_socket( |
11fdf7f2 TL |
621 | NULL, |
622 | online_table_size, | |
623 | RTE_CACHE_LINE_SIZE, | |
624 | socket_id); | |
625 | if (table->chunks[socket_id] == NULL) { | |
626 | RTE_LOG(ERR, EFD, | |
627 | "Allocating EFD online table on " | |
628 | "socket %u failed\n", | |
629 | socket_id); | |
630 | goto error_unlock_exit; | |
631 | } | |
632 | RTE_LOG(DEBUG, EFD, | |
633 | "Allocated EFD online table of size " | |
634 | "%"PRIu64" bytes (%.2f MB) on socket %u\n", | |
635 | online_table_size, | |
636 | (float) online_table_size / | |
637 | (1024.0F * 1024.0F), | |
638 | socket_id); | |
639 | } | |
640 | } | |
641 | ||
642 | #if defined(RTE_ARCH_X86) | |
643 | /* | |
644 | * For less than 4 bits, scalar function performs better | |
645 | * than vectorised version | |
646 | */ | |
647 | if (RTE_EFD_VALUE_NUM_BITS > 3 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2)) | |
648 | table->lookup_fn = EFD_LOOKUP_AVX2; | |
649 | else | |
9f95a23c TL |
650 | #endif |
651 | #if defined(RTE_ARCH_ARM64) | |
652 | /* | |
653 | * For less than or equal to 16 bits, scalar function performs better | |
654 | * than vectorised version | |
655 | */ | |
656 | if (RTE_EFD_VALUE_NUM_BITS > 16 && | |
657 | rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON)) | |
658 | table->lookup_fn = EFD_LOOKUP_NEON; | |
659 | else | |
11fdf7f2 TL |
660 | #endif |
661 | table->lookup_fn = EFD_LOOKUP_SCALAR; | |
662 | ||
663 | /* | |
664 | * Allocate the EFD table offline portion (with the actual rules | |
665 | * mapping keys to values) as a continuous block. | |
666 | * This could be several gigabytes of memory. | |
667 | */ | |
668 | offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules); | |
669 | table->offline_chunks = | |
9f95a23c | 670 | rte_zmalloc_socket(NULL, |
11fdf7f2 TL |
671 | offline_table_size, |
672 | RTE_CACHE_LINE_SIZE, | |
673 | offline_cpu_socket); | |
674 | if (table->offline_chunks == NULL) { | |
675 | RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u " | |
676 | "failed\n", offline_cpu_socket); | |
677 | goto error_unlock_exit; | |
678 | } | |
679 | ||
680 | RTE_LOG(DEBUG, EFD, | |
681 | "Allocated EFD offline table of size %"PRIu64" bytes " | |
682 | " (%.2f MB) on socket %u\n", offline_table_size, | |
683 | (float) offline_table_size / (1024.0F * 1024.0F), | |
684 | offline_cpu_socket); | |
685 | ||
686 | te->data = (void *) table; | |
687 | TAILQ_INSERT_TAIL(efd_list, te, next); | |
688 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); | |
689 | ||
690 | snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name); | |
691 | /* Create ring (Dummy slot index is not enqueued) */ | |
692 | r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules), | |
693 | offline_cpu_socket, 0); | |
694 | if (r == NULL) { | |
695 | RTE_LOG(ERR, EFD, "memory allocation failed\n"); | |
9f95a23c TL |
696 | rte_efd_free(table); |
697 | return NULL; | |
11fdf7f2 TL |
698 | } |
699 | ||
700 | /* Populate free slots ring. Entry zero is reserved for key misses. */ | |
701 | for (i = 0; i < table->max_num_rules; i++) | |
702 | rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i)); | |
703 | ||
704 | table->free_slots = r; | |
705 | return table; | |
706 | ||
707 | error_unlock_exit: | |
708 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); | |
709 | rte_efd_free(table); | |
710 | ||
711 | return NULL; | |
712 | } | |
713 | ||
714 | struct rte_efd_table * | |
715 | rte_efd_find_existing(const char *name) | |
716 | { | |
717 | struct rte_efd_table *table = NULL; | |
718 | struct rte_tailq_entry *te; | |
719 | struct rte_efd_list *efd_list; | |
720 | ||
721 | efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list); | |
722 | ||
723 | rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); | |
724 | ||
725 | TAILQ_FOREACH(te, efd_list, next) | |
726 | { | |
727 | table = (struct rte_efd_table *) te->data; | |
728 | if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0) | |
729 | break; | |
730 | } | |
731 | rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); | |
732 | ||
733 | if (te == NULL) { | |
734 | rte_errno = ENOENT; | |
735 | return NULL; | |
736 | } | |
737 | return table; | |
738 | } | |
739 | ||
740 | void | |
741 | rte_efd_free(struct rte_efd_table *table) | |
742 | { | |
743 | uint8_t socket_id; | |
9f95a23c TL |
744 | struct rte_efd_list *efd_list; |
745 | struct rte_tailq_entry *te, *temp; | |
11fdf7f2 TL |
746 | |
747 | if (table == NULL) | |
748 | return; | |
749 | ||
750 | for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) | |
751 | rte_free(table->chunks[socket_id]); | |
752 | ||
9f95a23c TL |
753 | efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list); |
754 | rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); | |
755 | ||
756 | TAILQ_FOREACH_SAFE(te, efd_list, next, temp) { | |
757 | if (te->data == (void *) table) { | |
758 | TAILQ_REMOVE(efd_list, te, next); | |
759 | rte_free(te); | |
760 | break; | |
761 | } | |
762 | } | |
763 | ||
764 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); | |
11fdf7f2 TL |
765 | rte_ring_free(table->free_slots); |
766 | rte_free(table->offline_chunks); | |
767 | rte_free(table->keys); | |
768 | rte_free(table); | |
769 | } | |
770 | ||
771 | /** | |
772 | * Applies a previously computed table entry to the specified table for all | |
773 | * socket-local copies of the online table. | |
774 | * Intended to apply an update for only a single change | |
775 | * to a key/value pair at a time | |
776 | * | |
777 | * @param table | |
778 | * EFD table to reference | |
779 | * @param socket_id | |
780 | * Socket ID to use to lookup existing values (ideally caller's socket id) | |
781 | * @param chunk_id | |
782 | * Chunk index to update | |
783 | * @param group_id | |
784 | * Group index to update | |
785 | * @param bin_id | |
786 | * Bin within the group that this update affects | |
787 | * @param new_bin_choice | |
788 | * Newly chosen permutation which this bin should use - only lower 2 bits | |
789 | * @param new_group_entry | |
790 | * Previously computed updated chunk/group entry | |
791 | */ | |
792 | static inline void | |
793 | efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id, | |
794 | const uint32_t chunk_id, const uint32_t group_id, | |
795 | const uint32_t bin_id, const uint8_t new_bin_choice, | |
796 | const struct efd_online_group_entry * const new_group_entry) | |
797 | { | |
798 | int i; | |
799 | struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id]; | |
800 | uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS; | |
801 | ||
802 | /* | |
803 | * Grab the current byte that contains the choices | |
804 | * for four neighboring bins | |
805 | */ | |
806 | uint8_t choice_chunk = | |
807 | chunk->bin_choice_list[bin_index]; | |
808 | ||
809 | ||
810 | /* Compute the offset into the chunk that needs to be updated */ | |
811 | int offset = (bin_id & 0x3) * 2; | |
812 | ||
813 | /* Zero the two bits of interest and set them to new_bin_choice */ | |
814 | choice_chunk = (choice_chunk & (~(0x03 << offset))) | |
815 | | ((new_bin_choice & 0x03) << offset); | |
816 | ||
817 | /* Update the online table with the new data across all sockets */ | |
818 | for (i = 0; i < RTE_MAX_NUMA_NODES; i++) { | |
819 | if (table->chunks[i] != NULL) { | |
820 | memcpy(&(table->chunks[i][chunk_id].groups[group_id]), | |
821 | new_group_entry, | |
822 | sizeof(struct efd_online_group_entry)); | |
823 | table->chunks[i][chunk_id].bin_choice_list[bin_index] = | |
824 | choice_chunk; | |
825 | } | |
826 | } | |
827 | } | |
828 | ||
829 | /* | |
830 | * Move the bin from prev group to the new group | |
831 | */ | |
832 | static inline void | |
833 | move_groups(uint32_t bin_id, uint8_t bin_size, | |
834 | struct efd_offline_group_rules *new_group, | |
835 | struct efd_offline_group_rules * const current_group) | |
836 | { | |
837 | ||
838 | uint8_t empty_idx = 0; | |
839 | unsigned int i; | |
840 | ||
841 | if (new_group == current_group) | |
842 | return; | |
843 | ||
844 | for (i = 0; i < current_group->num_rules; i++) { | |
845 | /* | |
846 | * Move keys that belong to the same bin | |
847 | * to the new group | |
848 | */ | |
849 | if (current_group->bin_id[i] == bin_id) { | |
850 | new_group->key_idx[new_group->num_rules] = | |
851 | current_group->key_idx[i]; | |
852 | new_group->value[new_group->num_rules] = | |
853 | current_group->value[i]; | |
854 | new_group->bin_id[new_group->num_rules] = | |
855 | current_group->bin_id[i]; | |
856 | new_group->num_rules++; | |
857 | } else { | |
858 | if (i != empty_idx) { | |
859 | /* | |
860 | * Need to move this key towards | |
861 | * the top of the array | |
862 | */ | |
863 | current_group->key_idx[empty_idx] = | |
864 | current_group->key_idx[i]; | |
865 | current_group->value[empty_idx] = | |
866 | current_group->value[i]; | |
867 | current_group->bin_id[empty_idx] = | |
868 | current_group->bin_id[i]; | |
869 | } | |
870 | empty_idx++; | |
871 | } | |
872 | ||
873 | } | |
874 | current_group->num_rules -= bin_size; | |
875 | } | |
876 | ||
877 | /* | |
878 | * Revert group/s to their previous state before | |
879 | * trying to insert/add a new key | |
880 | */ | |
881 | static inline void | |
882 | revert_groups(struct efd_offline_group_rules *previous_group, | |
883 | struct efd_offline_group_rules *current_group, uint8_t bin_size) | |
884 | { | |
885 | unsigned int i; | |
886 | ||
887 | if (current_group == previous_group) | |
888 | return; | |
889 | ||
890 | /* Move keys back to previous group */ | |
891 | for (i = current_group->num_rules - bin_size; | |
892 | i < current_group->num_rules; i++) { | |
893 | previous_group->key_idx[previous_group->num_rules] = | |
894 | current_group->key_idx[i]; | |
895 | previous_group->value[previous_group->num_rules] = | |
896 | current_group->value[i]; | |
897 | previous_group->bin_id[previous_group->num_rules] = | |
898 | current_group->bin_id[i]; | |
899 | previous_group->num_rules++; | |
900 | } | |
901 | ||
902 | /* | |
903 | * Decrease number of rules after the move | |
904 | * in the new group | |
905 | */ | |
906 | current_group->num_rules -= bin_size; | |
907 | } | |
908 | ||
909 | /** | |
910 | * Computes an updated table entry where the supplied key points to a new host. | |
911 | * If no entry exists, one is inserted. | |
912 | * | |
913 | * This function does NOT modify the online table(s) | |
914 | * This function DOES modify the offline table | |
915 | * | |
916 | * @param table | |
917 | * EFD table to reference | |
918 | * @param socket_id | |
919 | * Socket ID to use to lookup existing values (ideally caller's socket id) | |
920 | * @param key | |
921 | * Key to insert | |
922 | * @param value | |
923 | * Value to associate with key | |
924 | * @param chunk_id | |
925 | * Chunk ID of the chunk that was modified | |
926 | * @param group_id | |
927 | * Group ID of the group that was modified | |
928 | * @param bin_id | |
929 | * Bin ID that was modified | |
930 | * @param new_bin_choice | |
931 | * Newly chosen permutation which this bin will use | |
932 | * @param entry | |
933 | * Newly computed online entry to apply later with efd_apply_update | |
934 | * | |
935 | * @return | |
936 | * RTE_EFD_UPDATE_WARN_GROUP_FULL | |
937 | * Operation is insert, and the last available space in the | |
938 | * key's group was just used. Future inserts may fail as groups fill up. | |
939 | * This operation was still successful, and entry contains a valid update | |
940 | * RTE_EFD_UPDATE_FAILED | |
941 | * Either the EFD failed to find a suitable perfect hash or the group was full | |
9f95a23c | 942 | * This is a fatal error, and the table is now in an indeterminate state |
11fdf7f2 TL |
943 | * RTE_EFD_UPDATE_NO_CHANGE |
944 | * Operation resulted in no change to the table (same value already exists) | |
945 | * 0 | |
946 | * Insert or update was successful, and the new efd_online_group_entry | |
947 | * is stored in *entry | |
948 | * | |
949 | * @warning | |
950 | * Note that entry will be UNCHANGED if the update has no effect, and thus any | |
951 | * subsequent use of the entry content will likely be invalid | |
952 | */ | |
953 | static inline int | |
954 | efd_compute_update(struct rte_efd_table * const table, | |
955 | const unsigned int socket_id, const void *key, | |
956 | const efd_value_t value, uint32_t * const chunk_id, | |
957 | uint32_t * const group_id, uint32_t * const bin_id, | |
958 | uint8_t * const new_bin_choice, | |
959 | struct efd_online_group_entry * const entry) | |
960 | { | |
961 | unsigned int i; | |
962 | int ret; | |
963 | uint32_t new_idx; | |
964 | void *new_k, *slot_id = NULL; | |
965 | int status = EXIT_SUCCESS; | |
966 | unsigned int found = 0; | |
967 | ||
968 | efd_compute_ids(table, key, chunk_id, bin_id); | |
969 | ||
970 | struct efd_offline_chunk_rules * const chunk = | |
971 | &table->offline_chunks[*chunk_id]; | |
972 | struct efd_offline_group_rules *new_group; | |
973 | ||
974 | uint8_t current_choice = efd_get_choice(table, socket_id, | |
975 | *chunk_id, *bin_id); | |
976 | uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id]; | |
977 | struct efd_offline_group_rules * const current_group = | |
978 | &chunk->group_rules[current_group_id]; | |
979 | uint8_t bin_size = 0; | |
980 | uint8_t key_changed_index = 0; | |
981 | efd_value_t key_changed_previous_value = 0; | |
982 | uint32_t key_idx_previous = 0; | |
983 | ||
984 | /* Scan the current group and see if the key is already present */ | |
985 | for (i = 0; i < current_group->num_rules; i++) { | |
986 | if (current_group->bin_id[i] == *bin_id) | |
987 | bin_size++; | |
988 | else | |
989 | continue; | |
990 | ||
991 | void *key_stored = EFD_KEY(current_group->key_idx[i], table); | |
992 | if (found == 0 && unlikely(memcmp(key_stored, key, | |
993 | table->key_len) == 0)) { | |
994 | /* Key is already present */ | |
995 | ||
996 | /* | |
997 | * If previous value is same as new value, | |
998 | * no additional work is required | |
999 | */ | |
1000 | if (current_group->value[i] == value) | |
1001 | return RTE_EFD_UPDATE_NO_CHANGE; | |
1002 | ||
1003 | key_idx_previous = current_group->key_idx[i]; | |
1004 | key_changed_previous_value = current_group->value[i]; | |
1005 | key_changed_index = i; | |
1006 | current_group->value[i] = value; | |
1007 | found = 1; | |
1008 | } | |
1009 | } | |
1010 | ||
1011 | if (found == 0) { | |
1012 | /* Key does not exist. Insert the rule into the bin/group */ | |
1013 | if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) { | |
1014 | RTE_LOG(ERR, EFD, | |
1015 | "Fatal: No room remaining for insert into " | |
1016 | "chunk %u group %u bin %u\n", | |
1017 | *chunk_id, | |
1018 | current_group_id, *bin_id); | |
1019 | return RTE_EFD_UPDATE_FAILED; | |
1020 | } | |
1021 | ||
1022 | if (unlikely(current_group->num_rules == | |
1023 | (EFD_MAX_GROUP_NUM_RULES - 1))) { | |
1024 | RTE_LOG(INFO, EFD, "Warn: Insert into last " | |
1025 | "available slot in chunk %u " | |
1026 | "group %u bin %u\n", *chunk_id, | |
1027 | current_group_id, *bin_id); | |
1028 | status = RTE_EFD_UPDATE_WARN_GROUP_FULL; | |
1029 | } | |
1030 | ||
1031 | if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0) | |
1032 | return RTE_EFD_UPDATE_FAILED; | |
1033 | ||
1034 | new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id * | |
1035 | table->key_len); | |
1036 | rte_prefetch0(new_k); | |
1037 | new_idx = (uint32_t) ((uintptr_t) slot_id); | |
1038 | ||
1039 | rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len); | |
1040 | current_group->key_idx[current_group->num_rules] = new_idx; | |
1041 | current_group->value[current_group->num_rules] = value; | |
1042 | current_group->bin_id[current_group->num_rules] = *bin_id; | |
1043 | current_group->num_rules++; | |
1044 | table->num_rules++; | |
1045 | bin_size++; | |
1046 | } else { | |
1047 | uint32_t last = current_group->num_rules - 1; | |
1048 | /* Swap the key with the last key inserted*/ | |
1049 | current_group->key_idx[key_changed_index] = | |
1050 | current_group->key_idx[last]; | |
1051 | current_group->value[key_changed_index] = | |
1052 | current_group->value[last]; | |
1053 | current_group->bin_id[key_changed_index] = | |
1054 | current_group->bin_id[last]; | |
1055 | ||
1056 | /* | |
1057 | * Key to be updated will always be available | |
1058 | * at the end of the group | |
1059 | */ | |
1060 | current_group->key_idx[last] = key_idx_previous; | |
1061 | current_group->value[last] = value; | |
1062 | current_group->bin_id[last] = *bin_id; | |
1063 | } | |
1064 | ||
1065 | *new_bin_choice = current_choice; | |
1066 | *group_id = current_group_id; | |
1067 | new_group = current_group; | |
1068 | ||
1069 | /* Group need to be rebalanced when it starts to get loaded */ | |
1070 | if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) { | |
1071 | ||
1072 | /* | |
1073 | * Subtract the number of entries in the bin from | |
1074 | * the original group | |
1075 | */ | |
1076 | current_group->num_rules -= bin_size; | |
1077 | ||
1078 | /* | |
1079 | * Figure out which of the available groups that this bin | |
1080 | * can map to is the smallest (using the current group | |
1081 | * as baseline) | |
1082 | */ | |
1083 | uint8_t smallest_choice = current_choice; | |
1084 | uint8_t smallest_size = current_group->num_rules; | |
1085 | uint32_t smallest_group_id = current_group_id; | |
1086 | unsigned char choice; | |
1087 | ||
1088 | for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS; | |
1089 | choice++) { | |
1090 | uint32_t test_group_id = | |
1091 | efd_bin_to_group[choice][*bin_id]; | |
1092 | uint32_t num_rules = | |
1093 | chunk->group_rules[test_group_id].num_rules; | |
1094 | if (num_rules < smallest_size) { | |
1095 | smallest_choice = choice; | |
1096 | smallest_size = num_rules; | |
1097 | smallest_group_id = test_group_id; | |
1098 | } | |
1099 | } | |
1100 | ||
1101 | *new_bin_choice = smallest_choice; | |
1102 | *group_id = smallest_group_id; | |
1103 | new_group = &chunk->group_rules[smallest_group_id]; | |
1104 | current_group->num_rules += bin_size; | |
1105 | ||
1106 | } | |
1107 | ||
1108 | uint8_t choice = 0; | |
1109 | for (;;) { | |
1110 | if (current_group != new_group && | |
1111 | new_group->num_rules + bin_size > | |
1112 | EFD_MAX_GROUP_NUM_RULES) { | |
1113 | RTE_LOG(DEBUG, EFD, | |
1114 | "Unable to move_groups to dest group " | |
1115 | "containing %u entries." | |
1116 | "bin_size:%u choice:%02x\n", | |
1117 | new_group->num_rules, bin_size, | |
1118 | choice - 1); | |
1119 | goto next_choice; | |
1120 | } | |
1121 | move_groups(*bin_id, bin_size, new_group, current_group); | |
1122 | /* | |
1123 | * Recompute the hash function for the modified group, | |
1124 | * and return it to the caller | |
1125 | */ | |
1126 | ret = efd_search_hash(table, new_group, entry); | |
1127 | ||
1128 | if (!ret) | |
1129 | return status; | |
1130 | ||
1131 | RTE_LOG(DEBUG, EFD, | |
1132 | "Failed to find perfect hash for group " | |
1133 | "containing %u entries. bin_size:%u choice:%02x\n", | |
1134 | new_group->num_rules, bin_size, choice - 1); | |
1135 | /* Restore groups modified to their previous state */ | |
1136 | revert_groups(current_group, new_group, bin_size); | |
1137 | ||
1138 | next_choice: | |
1139 | if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS) | |
1140 | break; | |
1141 | *new_bin_choice = choice; | |
1142 | *group_id = efd_bin_to_group[choice][*bin_id]; | |
1143 | new_group = &chunk->group_rules[*group_id]; | |
1144 | choice++; | |
1145 | } | |
1146 | ||
1147 | if (!found) { | |
1148 | current_group->num_rules--; | |
1149 | table->num_rules--; | |
1150 | } else | |
1151 | current_group->value[current_group->num_rules - 1] = | |
1152 | key_changed_previous_value; | |
1153 | return RTE_EFD_UPDATE_FAILED; | |
1154 | } | |
1155 | ||
1156 | int | |
1157 | rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id, | |
1158 | const void *key, const efd_value_t value) | |
1159 | { | |
1160 | uint32_t chunk_id = 0, group_id = 0, bin_id = 0; | |
1161 | uint8_t new_bin_choice = 0; | |
1162 | struct efd_online_group_entry entry; | |
1163 | ||
1164 | int status = efd_compute_update(table, socket_id, key, value, | |
1165 | &chunk_id, &group_id, &bin_id, | |
1166 | &new_bin_choice, &entry); | |
1167 | ||
1168 | if (status == RTE_EFD_UPDATE_NO_CHANGE) | |
1169 | return EXIT_SUCCESS; | |
1170 | ||
1171 | if (status == RTE_EFD_UPDATE_FAILED) | |
1172 | return status; | |
1173 | ||
1174 | efd_apply_update(table, socket_id, chunk_id, group_id, bin_id, | |
1175 | new_bin_choice, &entry); | |
1176 | return status; | |
1177 | } | |
1178 | ||
1179 | int | |
1180 | rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id, | |
1181 | const void *key, efd_value_t * const prev_value) | |
1182 | { | |
1183 | unsigned int i; | |
1184 | uint32_t chunk_id, bin_id; | |
1185 | uint8_t not_found = 1; | |
1186 | ||
1187 | efd_compute_ids(table, key, &chunk_id, &bin_id); | |
1188 | ||
1189 | struct efd_offline_chunk_rules * const chunk = | |
1190 | &table->offline_chunks[chunk_id]; | |
1191 | ||
1192 | uint8_t current_choice = efd_get_choice(table, socket_id, | |
1193 | chunk_id, bin_id); | |
1194 | uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id]; | |
1195 | struct efd_offline_group_rules * const current_group = | |
1196 | &chunk->group_rules[current_group_id]; | |
1197 | ||
1198 | /* | |
1199 | * Search the current group for the specified key. | |
1200 | * If it exists, remove it and re-pack the other values | |
1201 | */ | |
1202 | for (i = 0; i < current_group->num_rules; i++) { | |
1203 | if (not_found) { | |
1204 | /* Found key that needs to be removed */ | |
1205 | if (memcmp(EFD_KEY(current_group->key_idx[i], table), | |
1206 | key, table->key_len) == 0) { | |
1207 | /* Store previous value if requested by caller */ | |
1208 | if (prev_value != NULL) | |
1209 | *prev_value = current_group->value[i]; | |
1210 | ||
1211 | not_found = 0; | |
1212 | rte_ring_sp_enqueue(table->free_slots, | |
1213 | (void *)((uintptr_t)current_group->key_idx[i])); | |
1214 | } | |
1215 | } else { | |
1216 | /* | |
1217 | * If the desired key has been found, | |
1218 | * need to shift other values up one | |
1219 | */ | |
1220 | ||
1221 | /* Need to shift this entry back up one index */ | |
1222 | current_group->key_idx[i - 1] = current_group->key_idx[i]; | |
1223 | current_group->value[i - 1] = current_group->value[i]; | |
1224 | current_group->bin_id[i - 1] = current_group->bin_id[i]; | |
1225 | } | |
1226 | } | |
1227 | ||
1228 | if (not_found == 0) { | |
1229 | table->num_rules--; | |
1230 | current_group->num_rules--; | |
1231 | } | |
1232 | ||
1233 | return not_found; | |
1234 | } | |
1235 | ||
1236 | static inline efd_value_t | |
1237 | efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx, | |
1238 | const efd_lookuptbl_t *group_lookup_table, | |
1239 | const uint32_t hash_val_a, const uint32_t hash_val_b) | |
1240 | { | |
1241 | efd_value_t value = 0; | |
1242 | uint32_t i; | |
1243 | ||
1244 | for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) { | |
1245 | value <<= 1; | |
1246 | uint32_t h = hash_val_a + (hash_val_b * | |
1247 | group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]); | |
1248 | uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT; | |
1249 | value |= (group_lookup_table[ | |
1250 | RTE_EFD_VALUE_NUM_BITS - i - 1] >> | |
1251 | bucket_idx) & 0x1; | |
1252 | } | |
1253 | ||
1254 | return value; | |
1255 | } | |
1256 | ||
1257 | ||
1258 | static inline efd_value_t | |
1259 | efd_lookup_internal(const struct efd_online_group_entry * const group, | |
1260 | const uint32_t hash_val_a, const uint32_t hash_val_b, | |
1261 | enum efd_lookup_internal_function lookup_fn) | |
1262 | { | |
1263 | efd_value_t value = 0; | |
1264 | ||
1265 | switch (lookup_fn) { | |
1266 | ||
9f95a23c | 1267 | #if defined(RTE_ARCH_X86) && defined(CC_SUPPORT_AVX2) |
11fdf7f2 TL |
1268 | case EFD_LOOKUP_AVX2: |
1269 | return efd_lookup_internal_avx2(group->hash_idx, | |
1270 | group->lookup_table, | |
1271 | hash_val_a, | |
1272 | hash_val_b); | |
9f95a23c TL |
1273 | break; |
1274 | #endif | |
1275 | #if defined(RTE_ARCH_ARM64) | |
1276 | case EFD_LOOKUP_NEON: | |
1277 | return efd_lookup_internal_neon(group->hash_idx, | |
1278 | group->lookup_table, | |
1279 | hash_val_a, | |
1280 | hash_val_b); | |
1281 | break; | |
11fdf7f2 TL |
1282 | #endif |
1283 | case EFD_LOOKUP_SCALAR: | |
1284 | /* Fall-through */ | |
1285 | default: | |
1286 | return efd_lookup_internal_scalar(group->hash_idx, | |
1287 | group->lookup_table, | |
1288 | hash_val_a, | |
1289 | hash_val_b); | |
1290 | } | |
1291 | ||
1292 | return value; | |
1293 | } | |
1294 | ||
1295 | efd_value_t | |
1296 | rte_efd_lookup(const struct rte_efd_table * const table, | |
1297 | const unsigned int socket_id, const void *key) | |
1298 | { | |
1299 | uint32_t chunk_id, group_id, bin_id; | |
1300 | uint8_t bin_choice; | |
1301 | const struct efd_online_group_entry *group; | |
1302 | const struct efd_online_chunk * const chunks = table->chunks[socket_id]; | |
1303 | ||
1304 | /* Determine the chunk and group location for the given key */ | |
1305 | efd_compute_ids(table, key, &chunk_id, &bin_id); | |
1306 | bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id); | |
1307 | group_id = efd_bin_to_group[bin_choice][bin_id]; | |
1308 | group = &chunks[chunk_id].groups[group_id]; | |
1309 | ||
1310 | return efd_lookup_internal(group, | |
1311 | EFD_HASHFUNCA(key, table), | |
1312 | EFD_HASHFUNCB(key, table), | |
1313 | table->lookup_fn); | |
1314 | } | |
1315 | ||
1316 | void rte_efd_lookup_bulk(const struct rte_efd_table * const table, | |
1317 | const unsigned int socket_id, const int num_keys, | |
1318 | const void **key_list, efd_value_t * const value_list) | |
1319 | { | |
1320 | int i; | |
1321 | uint32_t chunk_id_list[RTE_EFD_BURST_MAX]; | |
1322 | uint32_t bin_id_list[RTE_EFD_BURST_MAX]; | |
1323 | uint8_t bin_choice_list[RTE_EFD_BURST_MAX]; | |
1324 | uint32_t group_id_list[RTE_EFD_BURST_MAX]; | |
1325 | struct efd_online_group_entry *group; | |
1326 | ||
1327 | struct efd_online_chunk *chunks = table->chunks[socket_id]; | |
1328 | ||
1329 | for (i = 0; i < num_keys; i++) { | |
1330 | efd_compute_ids(table, key_list[i], &chunk_id_list[i], | |
1331 | &bin_id_list[i]); | |
1332 | rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list); | |
1333 | } | |
1334 | ||
1335 | for (i = 0; i < num_keys; i++) { | |
1336 | bin_choice_list[i] = efd_get_choice(table, socket_id, | |
1337 | chunk_id_list[i], bin_id_list[i]); | |
1338 | group_id_list[i] = | |
1339 | efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]]; | |
1340 | group = &chunks[chunk_id_list[i]].groups[group_id_list[i]]; | |
1341 | rte_prefetch0(group); | |
1342 | } | |
1343 | ||
1344 | for (i = 0; i < num_keys; i++) { | |
1345 | group = &chunks[chunk_id_list[i]].groups[group_id_list[i]]; | |
1346 | value_list[i] = efd_lookup_internal(group, | |
1347 | EFD_HASHFUNCA(key_list[i], table), | |
1348 | EFD_HASHFUNCB(key_list[i], table), | |
1349 | table->lookup_fn); | |
1350 | } | |
1351 | } |