4 * Copyright(c) 2016-2017 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 #include <sys/queue.h>
42 #include <rte_eal_memconfig.h>
43 #include <rte_errno.h>
44 #include <rte_malloc.h>
45 #include <rte_memzone.h>
46 #include <rte_prefetch.h>
47 #include <rte_branch_prediction.h>
48 #include <rte_memcpy.h>
50 #include <rte_jhash.h>
51 #include <rte_hash_crc.h>
54 #if defined(RTE_ARCH_X86)
55 #include "rte_efd_x86.h"
56 #elif defined(RTE_ARCH_ARM64)
57 #include "rte_efd_arm64.h"
60 #define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len))
61 /** Hash function used to determine chunk_id and bin_id for a group */
62 #define EFD_HASH(key, table) \
63 (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34))
64 /** Hash function used as constant component of perfect hash search */
65 #define EFD_HASHFUNCA(key, table) \
66 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35))
67 /** Hash function used as multiplicative component of perfect hash search */
68 #define EFD_HASHFUNCB(key, table) \
69 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36))
71 /*************************************************************************
73 *************************************************************************/
75 /* These parameters are fixed by the efd_bin_to_group balancing table */
76 #define EFD_CHUNK_NUM_GROUPS (64)
77 #define EFD_CHUNK_NUM_BINS (256)
78 #define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \
79 (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS)
82 * Target number of rules that each chunk is created to handle.
83 * Used when initially allocating the table
85 #define EFD_TARGET_CHUNK_NUM_RULES \
86 (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)
88 * Max number of rules that each chunk is created to handle.
89 * Used when initially allocating the table
91 #define EFD_TARGET_CHUNK_MAX_NUM_RULES \
92 (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES)
94 /** This is fixed based on the bin_to_group permutation array */
95 #define EFD_MAX_GROUP_NUM_BINS (16)
98 * The end of the chunks array needs some extra padding to ensure
99 * that vectorization over-reads on the last online chunk stay within
102 #define EFD_NUM_CHUNK_PADDING_BYTES (256)
104 /* All different internal lookup functions */
105 enum efd_lookup_internal_function {
106 EFD_LOOKUP_SCALAR = 0,
112 TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
114 static struct rte_tailq_elem rte_efd_tailq = {
117 EAL_REGISTER_TAILQ(rte_efd_tailq);
119 /** Internal permutation array used to shuffle bins into pseudorandom groups */
120 const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
122 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
123 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
124 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
125 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
126 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
127 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
128 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
129 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
130 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
131 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
132 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
133 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
134 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
135 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
136 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
137 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
140 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
141 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
142 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
143 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
144 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
145 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
146 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
147 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
148 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
149 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
150 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
151 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
152 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
153 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
154 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
155 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
158 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
159 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
160 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
161 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
162 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
163 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
164 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
165 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
166 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
167 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
168 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
169 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
170 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
171 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
172 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
173 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
176 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
177 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
178 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
179 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
180 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
181 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
182 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
183 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
184 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
185 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
186 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
187 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
188 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
189 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
190 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
191 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
195 /*************************************************************************
196 * Offline region structures
197 *************************************************************************/
199 /** Online group containing number of rules, values, keys and their bins
200 * for EFD_MAX_GROUP_NUM_RULES rules.
202 struct efd_offline_group_rules {
204 /**< Sum of the number of rules in all bins assigned to this group. */
206 uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
207 /**< Array with all keys of the group. */
208 efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
209 /**< Array with all values of the keys of the group. */
211 uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
212 /**< Stores the bin for each correspending key to
213 * avoid having to recompute it
217 /** Offline chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
218 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
220 struct efd_offline_chunk_rules {
222 /**< Number of rules in the entire chunk;
223 * used to detect unbalanced groups
226 struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
227 /**< Array of all groups in the chunk. */
230 /*************************************************************************
231 * Online region structures
232 *************************************************************************/
234 /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */
235 struct efd_online_group_entry {
236 efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
237 efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
238 } __attribute__((__packed__));
241 * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
242 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
244 struct efd_online_chunk {
245 uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
246 /**< This is a packed indirection index into the 'groups' array.
247 * Each byte contains four two-bit values which index into
248 * the efd_bin_to_group array.
249 * The efd_bin_to_group array returns the index into the groups array
252 struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
253 /**< Array of all the groups in the chunk. */
254 } __attribute__((__packed__));
257 * EFD table structure
259 struct rte_efd_table {
260 char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */
262 uint32_t key_len; /**< Length of the key stored offline */
264 uint32_t max_num_rules;
265 /**< Static maximum number of entries the table was constructed to hold. */
268 /**< Number of entries currently in the table . */
271 /**< Number of chunks in the table needed to support num_rules. */
273 uint32_t num_chunks_shift;
274 /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */
276 enum efd_lookup_internal_function lookup_fn;
277 /**< Indicates which lookup function to use. */
279 struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
280 /**< Dynamic array of size num_chunks of chunk records. */
282 struct efd_offline_chunk_rules *offline_chunks;
283 /**< Dynamic array of size num_chunks of key-value pairs. */
285 struct rte_ring *free_slots;
286 /**< Ring that stores all indexes of the free slots in the key table */
288 uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */
292 * Computes the chunk ID for a given key hash
295 * EFD table to reference
297 * 32-bit key hash returned by EFD_HASH
300 * chunk ID containing this key hash
302 static inline uint32_t
303 efd_get_chunk_id(const struct rte_efd_table * const table,
304 const uint32_t hashed_key)
306 return hashed_key & (table->num_chunks - 1);
310 * Computes the bin ID for a given key hash
313 * EFD table to reference
315 * 32-bit key hash returned by EFD_HASH
317 * @return bin ID containing this key hash
319 static inline uint32_t
320 efd_get_bin_id(const struct rte_efd_table * const table,
321 const uint32_t hashed_key)
323 return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
327 * Looks up the current permutation choice for a particular bin in the online table
330 * EFD table to reference
332 * Socket ID to use to look up existing values (ideally caller's socket id)
334 * Chunk ID of bin to look up
339 * Currently active permutation choice in the online table
341 static inline uint8_t
342 efd_get_choice(const struct rte_efd_table * const table,
343 const unsigned int socket_id, const uint32_t chunk_id,
344 const uint32_t bin_id)
346 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
349 * Grab the chunk (byte) that contains the choices
350 * for four neighboring bins.
352 uint8_t choice_chunk =
353 chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
356 * Compute the offset into the chunk that contains
357 * the group_id lookup position
359 int offset = (bin_id & 0x3) * 2;
361 /* Extract from the byte just the desired lookup position */
362 return (uint8_t) ((choice_chunk >> offset) & 0x3);
366 * Compute the chunk_id and bin_id for a given key
369 * EFD table to reference
371 * Key to hash and find location of
379 efd_compute_ids(const struct rte_efd_table * const table,
380 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
382 /* Compute the position of the entry in the hash table */
383 uint32_t h = EFD_HASH(key, table);
385 /* Compute the chunk_id where that entry can be found */
386 *chunk_id = efd_get_chunk_id(table, h);
389 * Compute the bin within that chunk where the entry
390 * can be found (0 - 255)
392 *bin_id = efd_get_bin_id(table, h);
396 * Search for a hash function for a group that satisfies all group results
399 efd_search_hash(struct rte_efd_table * const table,
400 const struct efd_offline_group_rules * const off_group,
401 struct efd_online_group_entry * const on_group)
403 efd_hashfunc_t hash_idx;
404 efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
405 efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
407 uint32_t i, j, rule_id;
408 uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
409 uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
410 uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
413 rte_prefetch0(off_group->value);
416 * Prepopulate the hash_val tables by running the two hash functions
417 * for each provided rule
419 for (i = 0; i < off_group->num_rules; i++) {
420 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
421 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
422 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
425 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
426 hash_idx = on_group->hash_idx[i];
427 start_hash_idx[i] = hash_idx;
428 start_lookup_table[i] = on_group->lookup_table[i];
431 efd_lookuptbl_t lookup_table = 0;
432 efd_lookuptbl_t lookup_table_complement = 0;
434 for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
435 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
436 hash_val_b[rule_id]);
439 * The goal here is to find a hash function for this
440 * particular bit entry that meets the following criteria:
441 * The most significant bits of the hash result define a
442 * shift into the lookup table where the bit will be stored
445 /* Iterate over each provided rule */
446 for (rule_id = 0; rule_id < off_group->num_rules;
449 * Use the few most significant bits (number based on
450 * EFD_LOOKUPTBL_SIZE) to see what position the
451 * expected bit should be set in the lookup_table
453 uint32_t bucket_idx = hash_val[rule_id] >>
457 * Get the current bit of interest.
458 * This only find an appropriate hash function
459 * for one bit at a time of the rule
461 efd_lookuptbl_t expected =
462 (off_group->value[rule_id] >> i) & 0x1;
465 * Add the expected bit (if set) to a map
466 * (lookup_table). Also set its complement
467 * in lookup_table_complement
469 lookup_table |= expected << bucket_idx;
470 lookup_table_complement |= (1 - expected)
474 * If ever the hash function of two different
475 * elements result in different values at the
476 * same location in the lookup_table,
477 * the current hash_idx is not valid.
479 if (lookup_table & lookup_table_complement)
484 * Check if the previous loop completed without
487 if (rule_id == off_group->num_rules) {
489 * Current hash function worked, store it
490 * for the current group
492 on_group->hash_idx[i] = hash_idx;
493 on_group->lookup_table[i] = lookup_table;
496 * Make sure that the hash function has changed
497 * from the starting value
499 hash_idx = start_hash_idx[i] + 1;
504 } while (hash_idx != start_hash_idx[i]);
506 /* Failed to find perfect hash for this group */
507 if (hash_idx == start_hash_idx[i]) {
509 * Restore previous hash_idx and lookup_table
512 for (j = 0; j < i; j++) {
513 on_group->hash_idx[j] = start_hash_idx[j];
514 on_group->lookup_table[j] = start_lookup_table[j];
523 struct rte_efd_table *
524 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
525 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
527 struct rte_efd_table *table = NULL;
528 uint8_t *key_array = NULL;
529 uint32_t num_chunks, num_chunks_shift;
531 struct rte_efd_list *efd_list = NULL;
532 struct rte_tailq_entry *te;
533 uint64_t offline_table_size;
534 char ring_name[RTE_RING_NAMESIZE];
535 struct rte_ring *r = NULL;
538 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
540 if (online_cpu_socket_bitmask == 0) {
541 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
546 if (max_num_rules == 0) {
547 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
552 * Compute the minimum number of chunks (smallest power of 2)
553 * that can hold all of the rules
555 if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
556 num_chunks = rte_align32pow2(max_num_rules /
557 EFD_TARGET_CHUNK_NUM_RULES);
559 num_chunks = rte_align32pow2((max_num_rules /
560 EFD_TARGET_CHUNK_NUM_RULES) + 1);
562 num_chunks_shift = rte_bsf32(num_chunks);
564 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
567 * Guarantee there's no existing: this is normally already checked
568 * by ring creation above
570 TAILQ_FOREACH(te, efd_list, next)
572 table = (struct rte_efd_table *) te->data;
573 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
581 goto error_unlock_exit;
584 te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
586 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
587 goto error_unlock_exit;
590 /* Create a new EFD table management structure */
591 table = (struct rte_efd_table *) rte_zmalloc_socket(NULL,
592 sizeof(struct rte_efd_table),
596 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
597 " on socket %u failed\n",
599 goto error_unlock_exit;
603 RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
604 "on socket %u\n", offline_cpu_socket);
606 table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
607 table->num_rules = 0;
608 table->num_chunks = num_chunks;
609 table->num_chunks_shift = num_chunks_shift;
610 table->key_len = key_len;
613 key_array = (uint8_t *) rte_zmalloc_socket(NULL,
614 table->max_num_rules * table->key_len,
617 if (key_array == NULL) {
618 RTE_LOG(ERR, EFD, "Allocating key array"
619 " on socket %u failed\n",
621 goto error_unlock_exit;
623 table->keys = key_array;
624 snprintf(table->name, sizeof(table->name), "%s", name);
626 RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
627 " which potentially supports %u entries\n",
628 num_chunks, table->max_num_rules);
630 /* Make sure all the allocatable table pointers are NULL initially */
631 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
632 table->chunks[socket_id] = NULL;
633 table->offline_chunks = NULL;
636 * Allocate one online table per socket specified
637 * in the user-supplied bitmask
639 uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
640 EFD_NUM_CHUNK_PADDING_BYTES;
642 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
643 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
645 * Allocate all of the EFD table chunks (the online portion)
646 * as a continuous block
648 table->chunks[socket_id] =
649 (struct efd_online_chunk *) rte_zmalloc_socket(
654 if (table->chunks[socket_id] == NULL) {
656 "Allocating EFD online table on "
657 "socket %u failed\n",
659 goto error_unlock_exit;
662 "Allocated EFD online table of size "
663 "%"PRIu64" bytes (%.2f MB) on socket %u\n",
665 (float) online_table_size /
671 #if defined(RTE_ARCH_X86)
673 * For less than 4 bits, scalar function performs better
674 * than vectorised version
676 if (RTE_EFD_VALUE_NUM_BITS > 3 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))
677 table->lookup_fn = EFD_LOOKUP_AVX2;
680 #if defined(RTE_ARCH_ARM64)
682 * For less than or equal to 16 bits, scalar function performs better
683 * than vectorised version
685 if (RTE_EFD_VALUE_NUM_BITS > 16 &&
686 rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON))
687 table->lookup_fn = EFD_LOOKUP_NEON;
690 table->lookup_fn = EFD_LOOKUP_SCALAR;
693 * Allocate the EFD table offline portion (with the actual rules
694 * mapping keys to values) as a continuous block.
695 * This could be several gigabytes of memory.
697 offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
698 table->offline_chunks =
699 (struct efd_offline_chunk_rules *) rte_zmalloc_socket(NULL,
703 if (table->offline_chunks == NULL) {
704 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
705 "failed\n", offline_cpu_socket);
706 goto error_unlock_exit;
710 "Allocated EFD offline table of size %"PRIu64" bytes "
711 " (%.2f MB) on socket %u\n", offline_table_size,
712 (float) offline_table_size / (1024.0F * 1024.0F),
715 te->data = (void *) table;
716 TAILQ_INSERT_TAIL(efd_list, te, next);
717 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
719 snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
720 /* Create ring (Dummy slot index is not enqueued) */
721 r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
722 offline_cpu_socket, 0);
724 RTE_LOG(ERR, EFD, "memory allocation failed\n");
725 goto error_unlock_exit;
728 /* Populate free slots ring. Entry zero is reserved for key misses. */
729 for (i = 0; i < table->max_num_rules; i++)
730 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
732 table->free_slots = r;
736 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
742 struct rte_efd_table *
743 rte_efd_find_existing(const char *name)
745 struct rte_efd_table *table = NULL;
746 struct rte_tailq_entry *te;
747 struct rte_efd_list *efd_list;
749 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
751 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
753 TAILQ_FOREACH(te, efd_list, next)
755 table = (struct rte_efd_table *) te->data;
756 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
759 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
769 rte_efd_free(struct rte_efd_table *table)
776 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
777 rte_free(table->chunks[socket_id]);
779 rte_ring_free(table->free_slots);
780 rte_free(table->offline_chunks);
781 rte_free(table->keys);
786 * Applies a previously computed table entry to the specified table for all
787 * socket-local copies of the online table.
788 * Intended to apply an update for only a single change
789 * to a key/value pair at a time
792 * EFD table to reference
794 * Socket ID to use to lookup existing values (ideally caller's socket id)
796 * Chunk index to update
798 * Group index to update
800 * Bin within the group that this update affects
801 * @param new_bin_choice
802 * Newly chosen permutation which this bin should use - only lower 2 bits
803 * @param new_group_entry
804 * Previously computed updated chunk/group entry
807 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
808 const uint32_t chunk_id, const uint32_t group_id,
809 const uint32_t bin_id, const uint8_t new_bin_choice,
810 const struct efd_online_group_entry * const new_group_entry)
813 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
814 uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
817 * Grab the current byte that contains the choices
818 * for four neighboring bins
820 uint8_t choice_chunk =
821 chunk->bin_choice_list[bin_index];
824 /* Compute the offset into the chunk that needs to be updated */
825 int offset = (bin_id & 0x3) * 2;
827 /* Zero the two bits of interest and set them to new_bin_choice */
828 choice_chunk = (choice_chunk & (~(0x03 << offset)))
829 | ((new_bin_choice & 0x03) << offset);
831 /* Update the online table with the new data across all sockets */
832 for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
833 if (table->chunks[i] != NULL) {
834 memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
836 sizeof(struct efd_online_group_entry));
837 table->chunks[i][chunk_id].bin_choice_list[bin_index] =
844 * Move the bin from prev group to the new group
847 move_groups(uint32_t bin_id, uint8_t bin_size,
848 struct efd_offline_group_rules *new_group,
849 struct efd_offline_group_rules * const current_group)
852 uint8_t empty_idx = 0;
855 if (new_group == current_group)
858 for (i = 0; i < current_group->num_rules; i++) {
860 * Move keys that belong to the same bin
863 if (current_group->bin_id[i] == bin_id) {
864 new_group->key_idx[new_group->num_rules] =
865 current_group->key_idx[i];
866 new_group->value[new_group->num_rules] =
867 current_group->value[i];
868 new_group->bin_id[new_group->num_rules] =
869 current_group->bin_id[i];
870 new_group->num_rules++;
872 if (i != empty_idx) {
874 * Need to move this key towards
875 * the top of the array
877 current_group->key_idx[empty_idx] =
878 current_group->key_idx[i];
879 current_group->value[empty_idx] =
880 current_group->value[i];
881 current_group->bin_id[empty_idx] =
882 current_group->bin_id[i];
888 current_group->num_rules -= bin_size;
892 * Revert group/s to their previous state before
893 * trying to insert/add a new key
896 revert_groups(struct efd_offline_group_rules *previous_group,
897 struct efd_offline_group_rules *current_group, uint8_t bin_size)
901 if (current_group == previous_group)
904 /* Move keys back to previous group */
905 for (i = current_group->num_rules - bin_size;
906 i < current_group->num_rules; i++) {
907 previous_group->key_idx[previous_group->num_rules] =
908 current_group->key_idx[i];
909 previous_group->value[previous_group->num_rules] =
910 current_group->value[i];
911 previous_group->bin_id[previous_group->num_rules] =
912 current_group->bin_id[i];
913 previous_group->num_rules++;
917 * Decrease number of rules after the move
920 current_group->num_rules -= bin_size;
924 * Computes an updated table entry where the supplied key points to a new host.
925 * If no entry exists, one is inserted.
927 * This function does NOT modify the online table(s)
928 * This function DOES modify the offline table
931 * EFD table to reference
933 * Socket ID to use to lookup existing values (ideally caller's socket id)
937 * Value to associate with key
939 * Chunk ID of the chunk that was modified
941 * Group ID of the group that was modified
943 * Bin ID that was modified
944 * @param new_bin_choice
945 * Newly chosen permutation which this bin will use
947 * Newly computed online entry to apply later with efd_apply_update
950 * RTE_EFD_UPDATE_WARN_GROUP_FULL
951 * Operation is insert, and the last available space in the
952 * key's group was just used. Future inserts may fail as groups fill up.
953 * This operation was still successful, and entry contains a valid update
954 * RTE_EFD_UPDATE_FAILED
955 * Either the EFD failed to find a suitable perfect hash or the group was full
956 * This is a fatal error, and the table is now in an indeterminite state
957 * RTE_EFD_UPDATE_NO_CHANGE
958 * Operation resulted in no change to the table (same value already exists)
960 * Insert or update was successful, and the new efd_online_group_entry
961 * is stored in *entry
964 * Note that entry will be UNCHANGED if the update has no effect, and thus any
965 * subsequent use of the entry content will likely be invalid
968 efd_compute_update(struct rte_efd_table * const table,
969 const unsigned int socket_id, const void *key,
970 const efd_value_t value, uint32_t * const chunk_id,
971 uint32_t * const group_id, uint32_t * const bin_id,
972 uint8_t * const new_bin_choice,
973 struct efd_online_group_entry * const entry)
978 void *new_k, *slot_id = NULL;
979 int status = EXIT_SUCCESS;
980 unsigned int found = 0;
982 efd_compute_ids(table, key, chunk_id, bin_id);
984 struct efd_offline_chunk_rules * const chunk =
985 &table->offline_chunks[*chunk_id];
986 struct efd_offline_group_rules *new_group;
988 uint8_t current_choice = efd_get_choice(table, socket_id,
990 uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
991 struct efd_offline_group_rules * const current_group =
992 &chunk->group_rules[current_group_id];
993 uint8_t bin_size = 0;
994 uint8_t key_changed_index = 0;
995 efd_value_t key_changed_previous_value = 0;
996 uint32_t key_idx_previous = 0;
998 /* Scan the current group and see if the key is already present */
999 for (i = 0; i < current_group->num_rules; i++) {
1000 if (current_group->bin_id[i] == *bin_id)
1005 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
1006 if (found == 0 && unlikely(memcmp(key_stored, key,
1007 table->key_len) == 0)) {
1008 /* Key is already present */
1011 * If previous value is same as new value,
1012 * no additional work is required
1014 if (current_group->value[i] == value)
1015 return RTE_EFD_UPDATE_NO_CHANGE;
1017 key_idx_previous = current_group->key_idx[i];
1018 key_changed_previous_value = current_group->value[i];
1019 key_changed_index = i;
1020 current_group->value[i] = value;
1026 /* Key does not exist. Insert the rule into the bin/group */
1027 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1029 "Fatal: No room remaining for insert into "
1030 "chunk %u group %u bin %u\n",
1032 current_group_id, *bin_id);
1033 return RTE_EFD_UPDATE_FAILED;
1036 if (unlikely(current_group->num_rules ==
1037 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1038 RTE_LOG(INFO, EFD, "Warn: Insert into last "
1039 "available slot in chunk %u "
1040 "group %u bin %u\n", *chunk_id,
1041 current_group_id, *bin_id);
1042 status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1045 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1046 return RTE_EFD_UPDATE_FAILED;
1048 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1050 rte_prefetch0(new_k);
1051 new_idx = (uint32_t) ((uintptr_t) slot_id);
1053 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1054 current_group->key_idx[current_group->num_rules] = new_idx;
1055 current_group->value[current_group->num_rules] = value;
1056 current_group->bin_id[current_group->num_rules] = *bin_id;
1057 current_group->num_rules++;
1061 uint32_t last = current_group->num_rules - 1;
1062 /* Swap the key with the last key inserted*/
1063 current_group->key_idx[key_changed_index] =
1064 current_group->key_idx[last];
1065 current_group->value[key_changed_index] =
1066 current_group->value[last];
1067 current_group->bin_id[key_changed_index] =
1068 current_group->bin_id[last];
1071 * Key to be updated will always be available
1072 * at the end of the group
1074 current_group->key_idx[last] = key_idx_previous;
1075 current_group->value[last] = value;
1076 current_group->bin_id[last] = *bin_id;
1079 *new_bin_choice = current_choice;
1080 *group_id = current_group_id;
1081 new_group = current_group;
1083 /* Group need to be rebalanced when it starts to get loaded */
1084 if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1087 * Subtract the number of entries in the bin from
1088 * the original group
1090 current_group->num_rules -= bin_size;
1093 * Figure out which of the available groups that this bin
1094 * can map to is the smallest (using the current group
1097 uint8_t smallest_choice = current_choice;
1098 uint8_t smallest_size = current_group->num_rules;
1099 uint32_t smallest_group_id = current_group_id;
1100 unsigned char choice;
1102 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1104 uint32_t test_group_id =
1105 efd_bin_to_group[choice][*bin_id];
1106 uint32_t num_rules =
1107 chunk->group_rules[test_group_id].num_rules;
1108 if (num_rules < smallest_size) {
1109 smallest_choice = choice;
1110 smallest_size = num_rules;
1111 smallest_group_id = test_group_id;
1115 *new_bin_choice = smallest_choice;
1116 *group_id = smallest_group_id;
1117 new_group = &chunk->group_rules[smallest_group_id];
1118 current_group->num_rules += bin_size;
1124 if (current_group != new_group &&
1125 new_group->num_rules + bin_size >
1126 EFD_MAX_GROUP_NUM_RULES) {
1128 "Unable to move_groups to dest group "
1129 "containing %u entries."
1130 "bin_size:%u choice:%02x\n",
1131 new_group->num_rules, bin_size,
1135 move_groups(*bin_id, bin_size, new_group, current_group);
1137 * Recompute the hash function for the modified group,
1138 * and return it to the caller
1140 ret = efd_search_hash(table, new_group, entry);
1146 "Failed to find perfect hash for group "
1147 "containing %u entries. bin_size:%u choice:%02x\n",
1148 new_group->num_rules, bin_size, choice - 1);
1149 /* Restore groups modified to their previous state */
1150 revert_groups(current_group, new_group, bin_size);
1153 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1155 *new_bin_choice = choice;
1156 *group_id = efd_bin_to_group[choice][*bin_id];
1157 new_group = &chunk->group_rules[*group_id];
1162 current_group->num_rules--;
1165 current_group->value[current_group->num_rules - 1] =
1166 key_changed_previous_value;
1167 return RTE_EFD_UPDATE_FAILED;
1171 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1172 const void *key, const efd_value_t value)
1174 uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1175 uint8_t new_bin_choice = 0;
1176 struct efd_online_group_entry entry;
1178 int status = efd_compute_update(table, socket_id, key, value,
1179 &chunk_id, &group_id, &bin_id,
1180 &new_bin_choice, &entry);
1182 if (status == RTE_EFD_UPDATE_NO_CHANGE)
1183 return EXIT_SUCCESS;
1185 if (status == RTE_EFD_UPDATE_FAILED)
1188 efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1189 new_bin_choice, &entry);
1194 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1195 const void *key, efd_value_t * const prev_value)
1198 uint32_t chunk_id, bin_id;
1199 uint8_t not_found = 1;
1201 efd_compute_ids(table, key, &chunk_id, &bin_id);
1203 struct efd_offline_chunk_rules * const chunk =
1204 &table->offline_chunks[chunk_id];
1206 uint8_t current_choice = efd_get_choice(table, socket_id,
1208 uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1209 struct efd_offline_group_rules * const current_group =
1210 &chunk->group_rules[current_group_id];
1213 * Search the current group for the specified key.
1214 * If it exists, remove it and re-pack the other values
1216 for (i = 0; i < current_group->num_rules; i++) {
1218 /* Found key that needs to be removed */
1219 if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1220 key, table->key_len) == 0) {
1221 /* Store previous value if requested by caller */
1222 if (prev_value != NULL)
1223 *prev_value = current_group->value[i];
1226 rte_ring_sp_enqueue(table->free_slots,
1227 (void *)((uintptr_t)current_group->key_idx[i]));
1231 * If the desired key has been found,
1232 * need to shift other values up one
1235 /* Need to shift this entry back up one index */
1236 current_group->key_idx[i - 1] = current_group->key_idx[i];
1237 current_group->value[i - 1] = current_group->value[i];
1238 current_group->bin_id[i - 1] = current_group->bin_id[i];
1242 if (not_found == 0) {
1244 current_group->num_rules--;
1250 static inline efd_value_t
1251 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1252 const efd_lookuptbl_t *group_lookup_table,
1253 const uint32_t hash_val_a, const uint32_t hash_val_b)
1255 efd_value_t value = 0;
1258 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1260 uint32_t h = hash_val_a + (hash_val_b *
1261 group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1262 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1263 value |= (group_lookup_table[
1264 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1272 static inline efd_value_t
1273 efd_lookup_internal(const struct efd_online_group_entry * const group,
1274 const uint32_t hash_val_a, const uint32_t hash_val_b,
1275 enum efd_lookup_internal_function lookup_fn)
1277 efd_value_t value = 0;
1279 switch (lookup_fn) {
1281 #if defined(RTE_ARCH_X86)
1282 case EFD_LOOKUP_AVX2:
1283 return efd_lookup_internal_avx2(group->hash_idx,
1284 group->lookup_table,
1289 #if defined(RTE_ARCH_ARM64)
1290 case EFD_LOOKUP_NEON:
1291 return efd_lookup_internal_neon(group->hash_idx,
1292 group->lookup_table,
1297 case EFD_LOOKUP_SCALAR:
1300 return efd_lookup_internal_scalar(group->hash_idx,
1301 group->lookup_table,
1310 rte_efd_lookup(const struct rte_efd_table * const table,
1311 const unsigned int socket_id, const void *key)
1313 uint32_t chunk_id, group_id, bin_id;
1315 const struct efd_online_group_entry *group;
1316 const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1318 /* Determine the chunk and group location for the given key */
1319 efd_compute_ids(table, key, &chunk_id, &bin_id);
1320 bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1321 group_id = efd_bin_to_group[bin_choice][bin_id];
1322 group = &chunks[chunk_id].groups[group_id];
1324 return efd_lookup_internal(group,
1325 EFD_HASHFUNCA(key, table),
1326 EFD_HASHFUNCB(key, table),
1330 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1331 const unsigned int socket_id, const int num_keys,
1332 const void **key_list, efd_value_t * const value_list)
1335 uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1336 uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1337 uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1338 uint32_t group_id_list[RTE_EFD_BURST_MAX];
1339 struct efd_online_group_entry *group;
1341 struct efd_online_chunk *chunks = table->chunks[socket_id];
1343 for (i = 0; i < num_keys; i++) {
1344 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1346 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1349 for (i = 0; i < num_keys; i++) {
1350 bin_choice_list[i] = efd_get_choice(table, socket_id,
1351 chunk_id_list[i], bin_id_list[i]);
1353 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1354 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1355 rte_prefetch0(group);
1358 for (i = 0; i < num_keys; i++) {
1359 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1360 value_list[i] = efd_lookup_internal(group,
1361 EFD_HASHFUNCA(key_list[i], table),
1362 EFD_HASHFUNCB(key_list[i], table),