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