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