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_prefetch.h>
46 #include <rte_branch_prediction.h>
47 #include <rte_memcpy.h>
49 #include <rte_jhash.h>
50 #include <rte_hash_crc.h>
53 #if defined(RTE_ARCH_X86)
54 #include "rte_efd_x86.h"
55 #elif defined(RTE_ARCH_ARM64)
56 #include "rte_efd_arm64.h"
59 #define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len))
60 /** Hash function used to determine chunk_id and bin_id for a group */
61 #define EFD_HASH(key, table) \
62 (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34))
63 /** Hash function used as constant component of perfect hash search */
64 #define EFD_HASHFUNCA(key, table) \
65 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35))
66 /** Hash function used as multiplicative component of perfect hash search */
67 #define EFD_HASHFUNCB(key, table) \
68 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36))
70 /*************************************************************************
72 *************************************************************************/
74 /* These parameters are fixed by the efd_bin_to_group balancing table */
75 #define EFD_CHUNK_NUM_GROUPS (64)
76 #define EFD_CHUNK_NUM_BINS (256)
77 #define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \
78 (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS)
81 * Target number of rules that each chunk is created to handle.
82 * Used when initially allocating the table
84 #define EFD_TARGET_CHUNK_NUM_RULES \
85 (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)
87 * Max number of rules that each chunk is created to handle.
88 * Used when initially allocating the table
90 #define EFD_TARGET_CHUNK_MAX_NUM_RULES \
91 (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES)
93 /** This is fixed based on the bin_to_group permutation array */
94 #define EFD_MAX_GROUP_NUM_BINS (16)
97 * The end of the chunks array needs some extra padding to ensure
98 * that vectorization over-reads on the last online chunk stay within
101 #define EFD_NUM_CHUNK_PADDING_BYTES (256)
103 /* All different internal lookup functions */
104 enum efd_lookup_internal_function {
105 EFD_LOOKUP_SCALAR = 0,
111 TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
113 static struct rte_tailq_elem rte_efd_tailq = {
116 EAL_REGISTER_TAILQ(rte_efd_tailq);
118 /** Internal permutation array used to shuffle bins into pseudorandom groups */
119 const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
121 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
122 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
123 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
124 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
125 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
126 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
127 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
128 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
129 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
130 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
131 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
132 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
133 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
134 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
135 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
136 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
139 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
140 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
141 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
142 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
143 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
144 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
145 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
146 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
147 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
148 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
149 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
150 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
151 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
152 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
153 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
154 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
157 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
158 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
159 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
160 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
161 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
162 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
163 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
164 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
165 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
166 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
167 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
168 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
169 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
170 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
171 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
172 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
175 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
176 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
177 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
178 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
179 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
180 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
181 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
182 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
183 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
184 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
185 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
186 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
187 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
188 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
189 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
190 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
194 /*************************************************************************
195 * Offline region structures
196 *************************************************************************/
198 /** Online group containing number of rules, values, keys and their bins
199 * for EFD_MAX_GROUP_NUM_RULES rules.
201 struct efd_offline_group_rules {
203 /**< Sum of the number of rules in all bins assigned to this group. */
205 uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
206 /**< Array with all keys of the group. */
207 efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
208 /**< Array with all values of the keys of the group. */
210 uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
211 /**< Stores the bin for each correspending key to
212 * avoid having to recompute it
216 /** Offline chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
217 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
219 struct efd_offline_chunk_rules {
221 /**< Number of rules in the entire chunk;
222 * used to detect unbalanced groups
225 struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
226 /**< Array of all groups in the chunk. */
229 /*************************************************************************
230 * Online region structures
231 *************************************************************************/
233 /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */
234 struct efd_online_group_entry {
235 efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
236 efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
237 } __attribute__((__packed__));
240 * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
241 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
243 struct efd_online_chunk {
244 uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
245 /**< This is a packed indirection index into the 'groups' array.
246 * Each byte contains four two-bit values which index into
247 * the efd_bin_to_group array.
248 * The efd_bin_to_group array returns the index into the groups array
251 struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
252 /**< Array of all the groups in the chunk. */
253 } __attribute__((__packed__));
256 * EFD table structure
258 struct rte_efd_table {
259 char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */
261 uint32_t key_len; /**< Length of the key stored offline */
263 uint32_t max_num_rules;
264 /**< Static maximum number of entries the table was constructed to hold. */
267 /**< Number of entries currently in the table . */
270 /**< Number of chunks in the table needed to support num_rules. */
272 uint32_t num_chunks_shift;
273 /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */
275 enum efd_lookup_internal_function lookup_fn;
276 /**< Indicates which lookup function to use. */
278 struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
279 /**< Dynamic array of size num_chunks of chunk records. */
281 struct efd_offline_chunk_rules *offline_chunks;
282 /**< Dynamic array of size num_chunks of key-value pairs. */
284 struct rte_ring *free_slots;
285 /**< Ring that stores all indexes of the free slots in the key table */
287 uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */
291 * Computes the chunk ID for a given key hash
294 * EFD table to reference
296 * 32-bit key hash returned by EFD_HASH
299 * chunk ID containing this key hash
301 static inline uint32_t
302 efd_get_chunk_id(const struct rte_efd_table * const table,
303 const uint32_t hashed_key)
305 return hashed_key & (table->num_chunks - 1);
309 * Computes the bin ID for a given key hash
312 * EFD table to reference
314 * 32-bit key hash returned by EFD_HASH
316 * @return bin ID containing this key hash
318 static inline uint32_t
319 efd_get_bin_id(const struct rte_efd_table * const table,
320 const uint32_t hashed_key)
322 return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
326 * Looks up the current permutation choice for a particular bin in the online table
329 * EFD table to reference
331 * Socket ID to use to look up existing values (ideally caller's socket id)
333 * Chunk ID of bin to look up
338 * Currently active permutation choice in the online table
340 static inline uint8_t
341 efd_get_choice(const struct rte_efd_table * const table,
342 const unsigned int socket_id, const uint32_t chunk_id,
343 const uint32_t bin_id)
345 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
348 * Grab the chunk (byte) that contains the choices
349 * for four neighboring bins.
351 uint8_t choice_chunk =
352 chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
355 * Compute the offset into the chunk that contains
356 * the group_id lookup position
358 int offset = (bin_id & 0x3) * 2;
360 /* Extract from the byte just the desired lookup position */
361 return (uint8_t) ((choice_chunk >> offset) & 0x3);
365 * Compute the chunk_id and bin_id for a given key
368 * EFD table to reference
370 * Key to hash and find location of
378 efd_compute_ids(const struct rte_efd_table * const table,
379 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
381 /* Compute the position of the entry in the hash table */
382 uint32_t h = EFD_HASH(key, table);
384 /* Compute the chunk_id where that entry can be found */
385 *chunk_id = efd_get_chunk_id(table, h);
388 * Compute the bin within that chunk where the entry
389 * can be found (0 - 255)
391 *bin_id = efd_get_bin_id(table, h);
395 * Search for a hash function for a group that satisfies all group results
398 efd_search_hash(struct rte_efd_table * const table,
399 const struct efd_offline_group_rules * const off_group,
400 struct efd_online_group_entry * const on_group)
402 efd_hashfunc_t hash_idx;
403 efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
404 efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
406 uint32_t i, j, rule_id;
407 uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
408 uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
409 uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
412 rte_prefetch0(off_group->value);
415 * Prepopulate the hash_val tables by running the two hash functions
416 * for each provided rule
418 for (i = 0; i < off_group->num_rules; i++) {
419 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
420 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
421 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
424 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
425 hash_idx = on_group->hash_idx[i];
426 start_hash_idx[i] = hash_idx;
427 start_lookup_table[i] = on_group->lookup_table[i];
430 efd_lookuptbl_t lookup_table = 0;
431 efd_lookuptbl_t lookup_table_complement = 0;
433 for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
434 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
435 hash_val_b[rule_id]);
438 * The goal here is to find a hash function for this
439 * particular bit entry that meets the following criteria:
440 * The most significant bits of the hash result define a
441 * shift into the lookup table where the bit will be stored
444 /* Iterate over each provided rule */
445 for (rule_id = 0; rule_id < off_group->num_rules;
448 * Use the few most significant bits (number based on
449 * EFD_LOOKUPTBL_SIZE) to see what position the
450 * expected bit should be set in the lookup_table
452 uint32_t bucket_idx = hash_val[rule_id] >>
456 * Get the current bit of interest.
457 * This only find an appropriate hash function
458 * for one bit at a time of the rule
460 efd_lookuptbl_t expected =
461 (off_group->value[rule_id] >> i) & 0x1;
464 * Add the expected bit (if set) to a map
465 * (lookup_table). Also set its complement
466 * in lookup_table_complement
468 lookup_table |= expected << bucket_idx;
469 lookup_table_complement |= (1 - expected)
473 * If ever the hash function of two different
474 * elements result in different values at the
475 * same location in the lookup_table,
476 * the current hash_idx is not valid.
478 if (lookup_table & lookup_table_complement)
483 * Check if the previous loop completed without
486 if (rule_id == off_group->num_rules) {
488 * Current hash function worked, store it
489 * for the current group
491 on_group->hash_idx[i] = hash_idx;
492 on_group->lookup_table[i] = lookup_table;
495 * Make sure that the hash function has changed
496 * from the starting value
498 hash_idx = start_hash_idx[i] + 1;
503 } while (hash_idx != start_hash_idx[i]);
505 /* Failed to find perfect hash for this group */
506 if (hash_idx == start_hash_idx[i]) {
508 * Restore previous hash_idx and lookup_table
511 for (j = 0; j < i; j++) {
512 on_group->hash_idx[j] = start_hash_idx[j];
513 on_group->lookup_table[j] = start_lookup_table[j];
522 struct rte_efd_table *
523 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
524 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
526 struct rte_efd_table *table = NULL;
527 uint8_t *key_array = NULL;
528 uint32_t num_chunks, num_chunks_shift;
530 struct rte_efd_list *efd_list = NULL;
531 struct rte_tailq_entry *te;
532 uint64_t offline_table_size;
533 char ring_name[RTE_RING_NAMESIZE];
534 struct rte_ring *r = NULL;
537 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
539 if (online_cpu_socket_bitmask == 0) {
540 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
545 if (max_num_rules == 0) {
546 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
551 * Compute the minimum number of chunks (smallest power of 2)
552 * that can hold all of the rules
554 if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
555 num_chunks = rte_align32pow2(max_num_rules /
556 EFD_TARGET_CHUNK_NUM_RULES);
558 num_chunks = rte_align32pow2((max_num_rules /
559 EFD_TARGET_CHUNK_NUM_RULES) + 1);
561 num_chunks_shift = rte_bsf32(num_chunks);
563 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
566 * Guarantee there's no existing: this is normally already checked
567 * by ring creation above
569 TAILQ_FOREACH(te, efd_list, next)
571 table = (struct rte_efd_table *) te->data;
572 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
580 goto error_unlock_exit;
583 te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
585 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
586 goto error_unlock_exit;
589 /* Create a new EFD table management structure */
590 table = (struct rte_efd_table *) rte_zmalloc_socket(NULL,
591 sizeof(struct rte_efd_table),
595 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
596 " on socket %u failed\n",
598 goto error_unlock_exit;
602 RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
603 "on socket %u\n", offline_cpu_socket);
605 table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
606 table->num_rules = 0;
607 table->num_chunks = num_chunks;
608 table->num_chunks_shift = num_chunks_shift;
609 table->key_len = key_len;
612 key_array = (uint8_t *) rte_zmalloc_socket(NULL,
613 table->max_num_rules * table->key_len,
616 if (key_array == NULL) {
617 RTE_LOG(ERR, EFD, "Allocating key array"
618 " on socket %u failed\n",
620 goto error_unlock_exit;
622 table->keys = key_array;
623 snprintf(table->name, sizeof(table->name), "%s", name);
625 RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
626 " which potentially supports %u entries\n",
627 num_chunks, table->max_num_rules);
629 /* Make sure all the allocatable table pointers are NULL initially */
630 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
631 table->chunks[socket_id] = NULL;
632 table->offline_chunks = NULL;
635 * Allocate one online table per socket specified
636 * in the user-supplied bitmask
638 uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
639 EFD_NUM_CHUNK_PADDING_BYTES;
641 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
642 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
644 * Allocate all of the EFD table chunks (the online portion)
645 * as a continuous block
647 table->chunks[socket_id] =
648 (struct efd_online_chunk *) rte_zmalloc_socket(
653 if (table->chunks[socket_id] == NULL) {
655 "Allocating EFD online table on "
656 "socket %u failed\n",
658 goto error_unlock_exit;
661 "Allocated EFD online table of size "
662 "%"PRIu64" bytes (%.2f MB) on socket %u\n",
664 (float) online_table_size /
670 #if defined(RTE_ARCH_X86)
672 * For less than 4 bits, scalar function performs better
673 * than vectorised version
675 if (RTE_EFD_VALUE_NUM_BITS > 3 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))
676 table->lookup_fn = EFD_LOOKUP_AVX2;
679 #if defined(RTE_ARCH_ARM64)
681 * For less than or equal to 16 bits, scalar function performs better
682 * than vectorised version
684 if (RTE_EFD_VALUE_NUM_BITS > 16 &&
685 rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON))
686 table->lookup_fn = EFD_LOOKUP_NEON;
689 table->lookup_fn = EFD_LOOKUP_SCALAR;
692 * Allocate the EFD table offline portion (with the actual rules
693 * mapping keys to values) as a continuous block.
694 * This could be several gigabytes of memory.
696 offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
697 table->offline_chunks =
698 (struct efd_offline_chunk_rules *) rte_zmalloc_socket(NULL,
702 if (table->offline_chunks == NULL) {
703 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
704 "failed\n", offline_cpu_socket);
705 goto error_unlock_exit;
709 "Allocated EFD offline table of size %"PRIu64" bytes "
710 " (%.2f MB) on socket %u\n", offline_table_size,
711 (float) offline_table_size / (1024.0F * 1024.0F),
714 te->data = (void *) table;
715 TAILQ_INSERT_TAIL(efd_list, te, next);
716 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
718 snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
719 /* Create ring (Dummy slot index is not enqueued) */
720 r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
721 offline_cpu_socket, 0);
723 RTE_LOG(ERR, EFD, "memory allocation failed\n");
724 goto error_unlock_exit;
727 /* Populate free slots ring. Entry zero is reserved for key misses. */
728 for (i = 0; i < table->max_num_rules; i++)
729 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
731 table->free_slots = r;
735 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
741 struct rte_efd_table *
742 rte_efd_find_existing(const char *name)
744 struct rte_efd_table *table = NULL;
745 struct rte_tailq_entry *te;
746 struct rte_efd_list *efd_list;
748 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
750 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
752 TAILQ_FOREACH(te, efd_list, next)
754 table = (struct rte_efd_table *) te->data;
755 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
758 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
768 rte_efd_free(struct rte_efd_table *table)
775 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
776 rte_free(table->chunks[socket_id]);
778 rte_ring_free(table->free_slots);
779 rte_free(table->offline_chunks);
780 rte_free(table->keys);
785 * Applies a previously computed table entry to the specified table for all
786 * socket-local copies of the online table.
787 * Intended to apply an update for only a single change
788 * to a key/value pair at a time
791 * EFD table to reference
793 * Socket ID to use to lookup existing values (ideally caller's socket id)
795 * Chunk index to update
797 * Group index to update
799 * Bin within the group that this update affects
800 * @param new_bin_choice
801 * Newly chosen permutation which this bin should use - only lower 2 bits
802 * @param new_group_entry
803 * Previously computed updated chunk/group entry
806 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
807 const uint32_t chunk_id, const uint32_t group_id,
808 const uint32_t bin_id, const uint8_t new_bin_choice,
809 const struct efd_online_group_entry * const new_group_entry)
812 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
813 uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
816 * Grab the current byte that contains the choices
817 * for four neighboring bins
819 uint8_t choice_chunk =
820 chunk->bin_choice_list[bin_index];
823 /* Compute the offset into the chunk that needs to be updated */
824 int offset = (bin_id & 0x3) * 2;
826 /* Zero the two bits of interest and set them to new_bin_choice */
827 choice_chunk = (choice_chunk & (~(0x03 << offset)))
828 | ((new_bin_choice & 0x03) << offset);
830 /* Update the online table with the new data across all sockets */
831 for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
832 if (table->chunks[i] != NULL) {
833 memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
835 sizeof(struct efd_online_group_entry));
836 table->chunks[i][chunk_id].bin_choice_list[bin_index] =
843 * Move the bin from prev group to the new group
846 move_groups(uint32_t bin_id, uint8_t bin_size,
847 struct efd_offline_group_rules *new_group,
848 struct efd_offline_group_rules * const current_group)
851 uint8_t empty_idx = 0;
854 if (new_group == current_group)
857 for (i = 0; i < current_group->num_rules; i++) {
859 * Move keys that belong to the same bin
862 if (current_group->bin_id[i] == bin_id) {
863 new_group->key_idx[new_group->num_rules] =
864 current_group->key_idx[i];
865 new_group->value[new_group->num_rules] =
866 current_group->value[i];
867 new_group->bin_id[new_group->num_rules] =
868 current_group->bin_id[i];
869 new_group->num_rules++;
871 if (i != empty_idx) {
873 * Need to move this key towards
874 * the top of the array
876 current_group->key_idx[empty_idx] =
877 current_group->key_idx[i];
878 current_group->value[empty_idx] =
879 current_group->value[i];
880 current_group->bin_id[empty_idx] =
881 current_group->bin_id[i];
887 current_group->num_rules -= bin_size;
891 * Revert group/s to their previous state before
892 * trying to insert/add a new key
895 revert_groups(struct efd_offline_group_rules *previous_group,
896 struct efd_offline_group_rules *current_group, uint8_t bin_size)
900 if (current_group == previous_group)
903 /* Move keys back to previous group */
904 for (i = current_group->num_rules - bin_size;
905 i < current_group->num_rules; i++) {
906 previous_group->key_idx[previous_group->num_rules] =
907 current_group->key_idx[i];
908 previous_group->value[previous_group->num_rules] =
909 current_group->value[i];
910 previous_group->bin_id[previous_group->num_rules] =
911 current_group->bin_id[i];
912 previous_group->num_rules++;
916 * Decrease number of rules after the move
919 current_group->num_rules -= bin_size;
923 * Computes an updated table entry where the supplied key points to a new host.
924 * If no entry exists, one is inserted.
926 * This function does NOT modify the online table(s)
927 * This function DOES modify the offline table
930 * EFD table to reference
932 * Socket ID to use to lookup existing values (ideally caller's socket id)
936 * Value to associate with key
938 * Chunk ID of the chunk that was modified
940 * Group ID of the group that was modified
942 * Bin ID that was modified
943 * @param new_bin_choice
944 * Newly chosen permutation which this bin will use
946 * Newly computed online entry to apply later with efd_apply_update
949 * RTE_EFD_UPDATE_WARN_GROUP_FULL
950 * Operation is insert, and the last available space in the
951 * key's group was just used. Future inserts may fail as groups fill up.
952 * This operation was still successful, and entry contains a valid update
953 * RTE_EFD_UPDATE_FAILED
954 * Either the EFD failed to find a suitable perfect hash or the group was full
955 * This is a fatal error, and the table is now in an indeterminate state
956 * RTE_EFD_UPDATE_NO_CHANGE
957 * Operation resulted in no change to the table (same value already exists)
959 * Insert or update was successful, and the new efd_online_group_entry
960 * is stored in *entry
963 * Note that entry will be UNCHANGED if the update has no effect, and thus any
964 * subsequent use of the entry content will likely be invalid
967 efd_compute_update(struct rte_efd_table * const table,
968 const unsigned int socket_id, const void *key,
969 const efd_value_t value, uint32_t * const chunk_id,
970 uint32_t * const group_id, uint32_t * const bin_id,
971 uint8_t * const new_bin_choice,
972 struct efd_online_group_entry * const entry)
977 void *new_k, *slot_id = NULL;
978 int status = EXIT_SUCCESS;
979 unsigned int found = 0;
981 efd_compute_ids(table, key, chunk_id, bin_id);
983 struct efd_offline_chunk_rules * const chunk =
984 &table->offline_chunks[*chunk_id];
985 struct efd_offline_group_rules *new_group;
987 uint8_t current_choice = efd_get_choice(table, socket_id,
989 uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
990 struct efd_offline_group_rules * const current_group =
991 &chunk->group_rules[current_group_id];
992 uint8_t bin_size = 0;
993 uint8_t key_changed_index = 0;
994 efd_value_t key_changed_previous_value = 0;
995 uint32_t key_idx_previous = 0;
997 /* Scan the current group and see if the key is already present */
998 for (i = 0; i < current_group->num_rules; i++) {
999 if (current_group->bin_id[i] == *bin_id)
1004 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
1005 if (found == 0 && unlikely(memcmp(key_stored, key,
1006 table->key_len) == 0)) {
1007 /* Key is already present */
1010 * If previous value is same as new value,
1011 * no additional work is required
1013 if (current_group->value[i] == value)
1014 return RTE_EFD_UPDATE_NO_CHANGE;
1016 key_idx_previous = current_group->key_idx[i];
1017 key_changed_previous_value = current_group->value[i];
1018 key_changed_index = i;
1019 current_group->value[i] = value;
1025 /* Key does not exist. Insert the rule into the bin/group */
1026 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1028 "Fatal: No room remaining for insert into "
1029 "chunk %u group %u bin %u\n",
1031 current_group_id, *bin_id);
1032 return RTE_EFD_UPDATE_FAILED;
1035 if (unlikely(current_group->num_rules ==
1036 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1037 RTE_LOG(INFO, EFD, "Warn: Insert into last "
1038 "available slot in chunk %u "
1039 "group %u bin %u\n", *chunk_id,
1040 current_group_id, *bin_id);
1041 status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1044 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1045 return RTE_EFD_UPDATE_FAILED;
1047 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1049 rte_prefetch0(new_k);
1050 new_idx = (uint32_t) ((uintptr_t) slot_id);
1052 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1053 current_group->key_idx[current_group->num_rules] = new_idx;
1054 current_group->value[current_group->num_rules] = value;
1055 current_group->bin_id[current_group->num_rules] = *bin_id;
1056 current_group->num_rules++;
1060 uint32_t last = current_group->num_rules - 1;
1061 /* Swap the key with the last key inserted*/
1062 current_group->key_idx[key_changed_index] =
1063 current_group->key_idx[last];
1064 current_group->value[key_changed_index] =
1065 current_group->value[last];
1066 current_group->bin_id[key_changed_index] =
1067 current_group->bin_id[last];
1070 * Key to be updated will always be available
1071 * at the end of the group
1073 current_group->key_idx[last] = key_idx_previous;
1074 current_group->value[last] = value;
1075 current_group->bin_id[last] = *bin_id;
1078 *new_bin_choice = current_choice;
1079 *group_id = current_group_id;
1080 new_group = current_group;
1082 /* Group need to be rebalanced when it starts to get loaded */
1083 if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1086 * Subtract the number of entries in the bin from
1087 * the original group
1089 current_group->num_rules -= bin_size;
1092 * Figure out which of the available groups that this bin
1093 * can map to is the smallest (using the current group
1096 uint8_t smallest_choice = current_choice;
1097 uint8_t smallest_size = current_group->num_rules;
1098 uint32_t smallest_group_id = current_group_id;
1099 unsigned char choice;
1101 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1103 uint32_t test_group_id =
1104 efd_bin_to_group[choice][*bin_id];
1105 uint32_t num_rules =
1106 chunk->group_rules[test_group_id].num_rules;
1107 if (num_rules < smallest_size) {
1108 smallest_choice = choice;
1109 smallest_size = num_rules;
1110 smallest_group_id = test_group_id;
1114 *new_bin_choice = smallest_choice;
1115 *group_id = smallest_group_id;
1116 new_group = &chunk->group_rules[smallest_group_id];
1117 current_group->num_rules += bin_size;
1123 if (current_group != new_group &&
1124 new_group->num_rules + bin_size >
1125 EFD_MAX_GROUP_NUM_RULES) {
1127 "Unable to move_groups to dest group "
1128 "containing %u entries."
1129 "bin_size:%u choice:%02x\n",
1130 new_group->num_rules, bin_size,
1134 move_groups(*bin_id, bin_size, new_group, current_group);
1136 * Recompute the hash function for the modified group,
1137 * and return it to the caller
1139 ret = efd_search_hash(table, new_group, entry);
1145 "Failed to find perfect hash for group "
1146 "containing %u entries. bin_size:%u choice:%02x\n",
1147 new_group->num_rules, bin_size, choice - 1);
1148 /* Restore groups modified to their previous state */
1149 revert_groups(current_group, new_group, bin_size);
1152 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1154 *new_bin_choice = choice;
1155 *group_id = efd_bin_to_group[choice][*bin_id];
1156 new_group = &chunk->group_rules[*group_id];
1161 current_group->num_rules--;
1164 current_group->value[current_group->num_rules - 1] =
1165 key_changed_previous_value;
1166 return RTE_EFD_UPDATE_FAILED;
1170 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1171 const void *key, const efd_value_t value)
1173 uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1174 uint8_t new_bin_choice = 0;
1175 struct efd_online_group_entry entry;
1177 int status = efd_compute_update(table, socket_id, key, value,
1178 &chunk_id, &group_id, &bin_id,
1179 &new_bin_choice, &entry);
1181 if (status == RTE_EFD_UPDATE_NO_CHANGE)
1182 return EXIT_SUCCESS;
1184 if (status == RTE_EFD_UPDATE_FAILED)
1187 efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1188 new_bin_choice, &entry);
1193 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1194 const void *key, efd_value_t * const prev_value)
1197 uint32_t chunk_id, bin_id;
1198 uint8_t not_found = 1;
1200 efd_compute_ids(table, key, &chunk_id, &bin_id);
1202 struct efd_offline_chunk_rules * const chunk =
1203 &table->offline_chunks[chunk_id];
1205 uint8_t current_choice = efd_get_choice(table, socket_id,
1207 uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1208 struct efd_offline_group_rules * const current_group =
1209 &chunk->group_rules[current_group_id];
1212 * Search the current group for the specified key.
1213 * If it exists, remove it and re-pack the other values
1215 for (i = 0; i < current_group->num_rules; i++) {
1217 /* Found key that needs to be removed */
1218 if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1219 key, table->key_len) == 0) {
1220 /* Store previous value if requested by caller */
1221 if (prev_value != NULL)
1222 *prev_value = current_group->value[i];
1225 rte_ring_sp_enqueue(table->free_slots,
1226 (void *)((uintptr_t)current_group->key_idx[i]));
1230 * If the desired key has been found,
1231 * need to shift other values up one
1234 /* Need to shift this entry back up one index */
1235 current_group->key_idx[i - 1] = current_group->key_idx[i];
1236 current_group->value[i - 1] = current_group->value[i];
1237 current_group->bin_id[i - 1] = current_group->bin_id[i];
1241 if (not_found == 0) {
1243 current_group->num_rules--;
1249 static inline efd_value_t
1250 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1251 const efd_lookuptbl_t *group_lookup_table,
1252 const uint32_t hash_val_a, const uint32_t hash_val_b)
1254 efd_value_t value = 0;
1257 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1259 uint32_t h = hash_val_a + (hash_val_b *
1260 group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1261 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1262 value |= (group_lookup_table[
1263 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1271 static inline efd_value_t
1272 efd_lookup_internal(const struct efd_online_group_entry * const group,
1273 const uint32_t hash_val_a, const uint32_t hash_val_b,
1274 enum efd_lookup_internal_function lookup_fn)
1276 efd_value_t value = 0;
1278 switch (lookup_fn) {
1280 #if defined(RTE_ARCH_X86) && defined(CC_SUPPORT_AVX2)
1281 case EFD_LOOKUP_AVX2:
1282 return efd_lookup_internal_avx2(group->hash_idx,
1283 group->lookup_table,
1288 #if defined(RTE_ARCH_ARM64)
1289 case EFD_LOOKUP_NEON:
1290 return efd_lookup_internal_neon(group->hash_idx,
1291 group->lookup_table,
1296 case EFD_LOOKUP_SCALAR:
1299 return efd_lookup_internal_scalar(group->hash_idx,
1300 group->lookup_table,
1309 rte_efd_lookup(const struct rte_efd_table * const table,
1310 const unsigned int socket_id, const void *key)
1312 uint32_t chunk_id, group_id, bin_id;
1314 const struct efd_online_group_entry *group;
1315 const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1317 /* Determine the chunk and group location for the given key */
1318 efd_compute_ids(table, key, &chunk_id, &bin_id);
1319 bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1320 group_id = efd_bin_to_group[bin_choice][bin_id];
1321 group = &chunks[chunk_id].groups[group_id];
1323 return efd_lookup_internal(group,
1324 EFD_HASHFUNCA(key, table),
1325 EFD_HASHFUNCB(key, table),
1329 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1330 const unsigned int socket_id, const int num_keys,
1331 const void **key_list, efd_value_t * const value_list)
1334 uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1335 uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1336 uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1337 uint32_t group_id_list[RTE_EFD_BURST_MAX];
1338 struct efd_online_group_entry *group;
1340 struct efd_online_chunk *chunks = table->chunks[socket_id];
1342 for (i = 0; i < num_keys; i++) {
1343 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1345 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1348 for (i = 0; i < num_keys; i++) {
1349 bin_choice_list[i] = efd_get_choice(table, socket_id,
1350 chunk_id_list[i], bin_id_list[i]);
1352 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1353 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1354 rte_prefetch0(group);
1357 for (i = 0; i < num_keys; i++) {
1358 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1359 value_list[i] = efd_lookup_internal(group,
1360 EFD_HASHFUNCA(key_list[i], table),
1361 EFD_HASHFUNCB(key_list[i], table),