1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2016-2017 Intel Corporation
10 #include <sys/queue.h>
12 #include <rte_string_fns.h>
14 #include <rte_eal_memconfig.h>
15 #include <rte_errno.h>
16 #include <rte_malloc.h>
17 #include <rte_prefetch.h>
18 #include <rte_branch_prediction.h>
19 #include <rte_memcpy.h>
21 #include <rte_jhash.h>
22 #include <rte_hash_crc.h>
25 #if defined(RTE_ARCH_X86)
26 #include "rte_efd_x86.h"
27 #elif defined(RTE_ARCH_ARM64)
28 #include "rte_efd_arm64.h"
31 #define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len))
32 /** Hash function used to determine chunk_id and bin_id for a group */
33 #define EFD_HASH(key, table) \
34 (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34))
35 /** Hash function used as constant component of perfect hash search */
36 #define EFD_HASHFUNCA(key, table) \
37 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35))
38 /** Hash function used as multiplicative component of perfect hash search */
39 #define EFD_HASHFUNCB(key, table) \
40 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36))
42 /*************************************************************************
44 *************************************************************************/
46 /* These parameters are fixed by the efd_bin_to_group balancing table */
47 #define EFD_CHUNK_NUM_GROUPS (64)
48 #define EFD_CHUNK_NUM_BINS (256)
49 #define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \
50 (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS)
53 * Target number of rules that each chunk is created to handle.
54 * Used when initially allocating the table
56 #define EFD_TARGET_CHUNK_NUM_RULES \
57 (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)
59 * Max number of rules that each chunk is created to handle.
60 * Used when initially allocating the table
62 #define EFD_TARGET_CHUNK_MAX_NUM_RULES \
63 (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES)
65 /** This is fixed based on the bin_to_group permutation array */
66 #define EFD_MAX_GROUP_NUM_BINS (16)
69 * The end of the chunks array needs some extra padding to ensure
70 * that vectorization over-reads on the last online chunk stay within
73 #define EFD_NUM_CHUNK_PADDING_BYTES (256)
75 /* All different internal lookup functions */
76 enum efd_lookup_internal_function {
77 EFD_LOOKUP_SCALAR = 0,
83 TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
85 static struct rte_tailq_elem rte_efd_tailq = {
88 EAL_REGISTER_TAILQ(rte_efd_tailq);
90 /** Internal permutation array used to shuffle bins into pseudorandom groups */
91 const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
93 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
94 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
95 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
96 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
97 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
98 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
99 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
100 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
101 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
102 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
103 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
104 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
105 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
106 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
107 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
108 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
111 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
112 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
113 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
114 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
115 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
116 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
117 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
118 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
119 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
120 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
121 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
122 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
123 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
124 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
125 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
126 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
129 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
130 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
131 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
132 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
133 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
134 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
135 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
136 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
137 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
138 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
139 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
140 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
141 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
142 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
143 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
144 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
147 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
148 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
149 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
150 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
151 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
152 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
153 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
154 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
155 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
156 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
157 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
158 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
159 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
160 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
161 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
162 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
166 /*************************************************************************
167 * Offline region structures
168 *************************************************************************/
170 /** Online group containing number of rules, values, keys and their bins
171 * for EFD_MAX_GROUP_NUM_RULES rules.
173 struct efd_offline_group_rules {
175 /**< Sum of the number of rules in all bins assigned to this group. */
177 uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
178 /**< Array with all keys of the group. */
179 efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
180 /**< Array with all values of the keys of the group. */
182 uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
183 /**< Stores the bin for each correspending key to
184 * avoid having to recompute it
188 /** Offline chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
189 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
191 struct efd_offline_chunk_rules {
193 /**< Number of rules in the entire chunk;
194 * used to detect unbalanced groups
197 struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
198 /**< Array of all groups in the chunk. */
201 /*************************************************************************
202 * Online region structures
203 *************************************************************************/
205 /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */
206 struct efd_online_group_entry {
207 efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
208 efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
209 } __attribute__((__packed__));
212 * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
213 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
215 struct efd_online_chunk {
216 uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
217 /**< This is a packed indirection index into the 'groups' array.
218 * Each byte contains four two-bit values which index into
219 * the efd_bin_to_group array.
220 * The efd_bin_to_group array returns the index into the groups array
223 struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
224 /**< Array of all the groups in the chunk. */
225 } __attribute__((__packed__));
228 * EFD table structure
230 struct rte_efd_table {
231 char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */
233 uint32_t key_len; /**< Length of the key stored offline */
235 uint32_t max_num_rules;
236 /**< Static maximum number of entries the table was constructed to hold. */
239 /**< Number of entries currently in the table . */
242 /**< Number of chunks in the table needed to support num_rules. */
244 uint32_t num_chunks_shift;
245 /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */
247 enum efd_lookup_internal_function lookup_fn;
248 /**< Indicates which lookup function to use. */
250 struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
251 /**< Dynamic array of size num_chunks of chunk records. */
253 struct efd_offline_chunk_rules *offline_chunks;
254 /**< Dynamic array of size num_chunks of key-value pairs. */
256 struct rte_ring *free_slots;
257 /**< Ring that stores all indexes of the free slots in the key table */
259 uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */
263 * Computes the chunk ID for a given key hash
266 * EFD table to reference
268 * 32-bit key hash returned by EFD_HASH
271 * chunk ID containing this key hash
273 static inline uint32_t
274 efd_get_chunk_id(const struct rte_efd_table * const table,
275 const uint32_t hashed_key)
277 return hashed_key & (table->num_chunks - 1);
281 * Computes the bin ID for a given key hash
284 * EFD table to reference
286 * 32-bit key hash returned by EFD_HASH
288 * @return bin ID containing this key hash
290 static inline uint32_t
291 efd_get_bin_id(const struct rte_efd_table * const table,
292 const uint32_t hashed_key)
294 return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
298 * Looks up the current permutation choice for a particular bin in the online table
301 * EFD table to reference
303 * Socket ID to use to look up existing values (ideally caller's socket id)
305 * Chunk ID of bin to look up
310 * Currently active permutation choice in the online table
312 static inline uint8_t
313 efd_get_choice(const struct rte_efd_table * const table,
314 const unsigned int socket_id, const uint32_t chunk_id,
315 const uint32_t bin_id)
317 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
320 * Grab the chunk (byte) that contains the choices
321 * for four neighboring bins.
323 uint8_t choice_chunk =
324 chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
327 * Compute the offset into the chunk that contains
328 * the group_id lookup position
330 int offset = (bin_id & 0x3) * 2;
332 /* Extract from the byte just the desired lookup position */
333 return (uint8_t) ((choice_chunk >> offset) & 0x3);
337 * Compute the chunk_id and bin_id for a given key
340 * EFD table to reference
342 * Key to hash and find location of
350 efd_compute_ids(const struct rte_efd_table * const table,
351 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
353 /* Compute the position of the entry in the hash table */
354 uint32_t h = EFD_HASH(key, table);
356 /* Compute the chunk_id where that entry can be found */
357 *chunk_id = efd_get_chunk_id(table, h);
360 * Compute the bin within that chunk where the entry
361 * can be found (0 - 255)
363 *bin_id = efd_get_bin_id(table, h);
367 * Search for a hash function for a group that satisfies all group results
370 efd_search_hash(struct rte_efd_table * const table,
371 const struct efd_offline_group_rules * const off_group,
372 struct efd_online_group_entry * const on_group)
374 efd_hashfunc_t hash_idx;
375 efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
376 efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
378 uint32_t i, j, rule_id;
379 uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
380 uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
381 uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
384 rte_prefetch0(off_group->value);
387 * Prepopulate the hash_val tables by running the two hash functions
388 * for each provided rule
390 for (i = 0; i < off_group->num_rules; i++) {
391 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
392 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
393 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
396 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
397 hash_idx = on_group->hash_idx[i];
398 start_hash_idx[i] = hash_idx;
399 start_lookup_table[i] = on_group->lookup_table[i];
402 efd_lookuptbl_t lookup_table = 0;
403 efd_lookuptbl_t lookup_table_complement = 0;
405 for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
406 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
407 hash_val_b[rule_id]);
410 * The goal here is to find a hash function for this
411 * particular bit entry that meets the following criteria:
412 * The most significant bits of the hash result define a
413 * shift into the lookup table where the bit will be stored
416 /* Iterate over each provided rule */
417 for (rule_id = 0; rule_id < off_group->num_rules;
420 * Use the few most significant bits (number based on
421 * EFD_LOOKUPTBL_SIZE) to see what position the
422 * expected bit should be set in the lookup_table
424 uint32_t bucket_idx = hash_val[rule_id] >>
428 * Get the current bit of interest.
429 * This only find an appropriate hash function
430 * for one bit at a time of the rule
432 efd_lookuptbl_t expected =
433 (off_group->value[rule_id] >> i) & 0x1;
436 * Add the expected bit (if set) to a map
437 * (lookup_table). Also set its complement
438 * in lookup_table_complement
440 lookup_table |= expected << bucket_idx;
441 lookup_table_complement |= (1 - expected)
445 * If ever the hash function of two different
446 * elements result in different values at the
447 * same location in the lookup_table,
448 * the current hash_idx is not valid.
450 if (lookup_table & lookup_table_complement)
455 * Check if the previous loop completed without
458 if (rule_id == off_group->num_rules) {
460 * Current hash function worked, store it
461 * for the current group
463 on_group->hash_idx[i] = hash_idx;
464 on_group->lookup_table[i] = lookup_table;
467 * Make sure that the hash function has changed
468 * from the starting value
470 hash_idx = start_hash_idx[i] + 1;
475 } while (hash_idx != start_hash_idx[i]);
477 /* Failed to find perfect hash for this group */
478 if (hash_idx == start_hash_idx[i]) {
480 * Restore previous hash_idx and lookup_table
483 for (j = 0; j < i; j++) {
484 on_group->hash_idx[j] = start_hash_idx[j];
485 on_group->lookup_table[j] = start_lookup_table[j];
494 struct rte_efd_table *
495 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
496 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
498 struct rte_efd_table *table = NULL;
499 uint8_t *key_array = NULL;
500 uint32_t num_chunks, num_chunks_shift;
502 struct rte_efd_list *efd_list = NULL;
503 struct rte_tailq_entry *te;
504 uint64_t offline_table_size;
505 char ring_name[RTE_RING_NAMESIZE];
506 struct rte_ring *r = NULL;
509 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
511 if (online_cpu_socket_bitmask == 0) {
512 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
517 if (max_num_rules == 0) {
518 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
523 * Compute the minimum number of chunks (smallest power of 2)
524 * that can hold all of the rules
526 if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
527 num_chunks = rte_align32pow2(max_num_rules /
528 EFD_TARGET_CHUNK_NUM_RULES);
530 num_chunks = rte_align32pow2((max_num_rules /
531 EFD_TARGET_CHUNK_NUM_RULES) + 1);
533 num_chunks_shift = rte_bsf32(num_chunks);
535 rte_mcfg_tailq_write_lock();
538 * Guarantee there's no existing: this is normally already checked
539 * by ring creation above
541 TAILQ_FOREACH(te, efd_list, next)
543 table = (struct rte_efd_table *) te->data;
544 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
552 goto error_unlock_exit;
555 te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
557 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
558 goto error_unlock_exit;
561 /* Create a new EFD table management structure */
562 table = rte_zmalloc_socket(NULL,
563 sizeof(struct rte_efd_table),
567 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
568 " on socket %u failed\n",
570 goto error_unlock_exit;
574 RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
575 "on socket %u\n", offline_cpu_socket);
577 table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
578 table->num_rules = 0;
579 table->num_chunks = num_chunks;
580 table->num_chunks_shift = num_chunks_shift;
581 table->key_len = key_len;
584 key_array = rte_zmalloc_socket(NULL,
585 table->max_num_rules * table->key_len,
588 if (key_array == NULL) {
589 RTE_LOG(ERR, EFD, "Allocating key array"
590 " on socket %u failed\n",
592 goto error_unlock_exit;
594 table->keys = key_array;
595 strlcpy(table->name, name, sizeof(table->name));
597 RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
598 " which potentially supports %u entries\n",
599 num_chunks, table->max_num_rules);
601 /* Make sure all the allocatable table pointers are NULL initially */
602 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
603 table->chunks[socket_id] = NULL;
604 table->offline_chunks = NULL;
607 * Allocate one online table per socket specified
608 * in the user-supplied bitmask
610 uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
611 EFD_NUM_CHUNK_PADDING_BYTES;
613 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
614 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
616 * Allocate all of the EFD table chunks (the online portion)
617 * as a continuous block
619 table->chunks[socket_id] =
625 if (table->chunks[socket_id] == NULL) {
627 "Allocating EFD online table on "
628 "socket %u failed\n",
630 goto error_unlock_exit;
633 "Allocated EFD online table of size "
634 "%"PRIu64" bytes (%.2f MB) on socket %u\n",
636 (float) online_table_size /
642 #if defined(RTE_ARCH_X86)
644 * For less than 4 bits, scalar function performs better
645 * than vectorised version
647 if (RTE_EFD_VALUE_NUM_BITS > 3 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))
648 table->lookup_fn = EFD_LOOKUP_AVX2;
651 #if defined(RTE_ARCH_ARM64)
653 * For less than or equal to 16 bits, scalar function performs better
654 * than vectorised version
656 if (RTE_EFD_VALUE_NUM_BITS > 16 &&
657 rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON))
658 table->lookup_fn = EFD_LOOKUP_NEON;
661 table->lookup_fn = EFD_LOOKUP_SCALAR;
664 * Allocate the EFD table offline portion (with the actual rules
665 * mapping keys to values) as a continuous block.
666 * This could be several gigabytes of memory.
668 offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
669 table->offline_chunks =
670 rte_zmalloc_socket(NULL,
674 if (table->offline_chunks == NULL) {
675 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
676 "failed\n", offline_cpu_socket);
677 goto error_unlock_exit;
681 "Allocated EFD offline table of size %"PRIu64" bytes "
682 " (%.2f MB) on socket %u\n", offline_table_size,
683 (float) offline_table_size / (1024.0F * 1024.0F),
686 te->data = (void *) table;
687 TAILQ_INSERT_TAIL(efd_list, te, next);
688 rte_mcfg_tailq_write_unlock();
690 snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
691 /* Create ring (Dummy slot index is not enqueued) */
692 r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
693 offline_cpu_socket, 0);
695 RTE_LOG(ERR, EFD, "memory allocation failed\n");
700 /* Populate free slots ring. Entry zero is reserved for key misses. */
701 for (i = 0; i < table->max_num_rules; i++)
702 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
704 table->free_slots = r;
708 rte_mcfg_tailq_write_unlock();
714 struct rte_efd_table *
715 rte_efd_find_existing(const char *name)
717 struct rte_efd_table *table = NULL;
718 struct rte_tailq_entry *te;
719 struct rte_efd_list *efd_list;
721 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
723 rte_mcfg_tailq_read_lock();
725 TAILQ_FOREACH(te, efd_list, next)
727 table = (struct rte_efd_table *) te->data;
728 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
731 rte_mcfg_tailq_read_unlock();
741 rte_efd_free(struct rte_efd_table *table)
744 struct rte_efd_list *efd_list;
745 struct rte_tailq_entry *te, *temp;
750 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
751 rte_free(table->chunks[socket_id]);
753 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
754 rte_mcfg_tailq_write_lock();
756 TAILQ_FOREACH_SAFE(te, efd_list, next, temp) {
757 if (te->data == (void *) table) {
758 TAILQ_REMOVE(efd_list, te, next);
764 rte_mcfg_tailq_write_unlock();
765 rte_ring_free(table->free_slots);
766 rte_free(table->offline_chunks);
767 rte_free(table->keys);
772 * Applies a previously computed table entry to the specified table for all
773 * socket-local copies of the online table.
774 * Intended to apply an update for only a single change
775 * to a key/value pair at a time
778 * EFD table to reference
780 * Socket ID to use to lookup existing values (ideally caller's socket id)
782 * Chunk index to update
784 * Group index to update
786 * Bin within the group that this update affects
787 * @param new_bin_choice
788 * Newly chosen permutation which this bin should use - only lower 2 bits
789 * @param new_group_entry
790 * Previously computed updated chunk/group entry
793 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
794 const uint32_t chunk_id, const uint32_t group_id,
795 const uint32_t bin_id, const uint8_t new_bin_choice,
796 const struct efd_online_group_entry * const new_group_entry)
799 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
800 uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
803 * Grab the current byte that contains the choices
804 * for four neighboring bins
806 uint8_t choice_chunk =
807 chunk->bin_choice_list[bin_index];
810 /* Compute the offset into the chunk that needs to be updated */
811 int offset = (bin_id & 0x3) * 2;
813 /* Zero the two bits of interest and set them to new_bin_choice */
814 choice_chunk = (choice_chunk & (~(0x03 << offset)))
815 | ((new_bin_choice & 0x03) << offset);
817 /* Update the online table with the new data across all sockets */
818 for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
819 if (table->chunks[i] != NULL) {
820 memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
822 sizeof(struct efd_online_group_entry));
823 table->chunks[i][chunk_id].bin_choice_list[bin_index] =
830 * Move the bin from prev group to the new group
833 move_groups(uint32_t bin_id, uint8_t bin_size,
834 struct efd_offline_group_rules *new_group,
835 struct efd_offline_group_rules * const current_group)
838 uint8_t empty_idx = 0;
841 if (new_group == current_group)
844 for (i = 0; i < current_group->num_rules; i++) {
846 * Move keys that belong to the same bin
849 if (current_group->bin_id[i] == bin_id) {
850 new_group->key_idx[new_group->num_rules] =
851 current_group->key_idx[i];
852 new_group->value[new_group->num_rules] =
853 current_group->value[i];
854 new_group->bin_id[new_group->num_rules] =
855 current_group->bin_id[i];
856 new_group->num_rules++;
858 if (i != empty_idx) {
860 * Need to move this key towards
861 * the top of the array
863 current_group->key_idx[empty_idx] =
864 current_group->key_idx[i];
865 current_group->value[empty_idx] =
866 current_group->value[i];
867 current_group->bin_id[empty_idx] =
868 current_group->bin_id[i];
874 current_group->num_rules -= bin_size;
878 * Revert group/s to their previous state before
879 * trying to insert/add a new key
882 revert_groups(struct efd_offline_group_rules *previous_group,
883 struct efd_offline_group_rules *current_group, uint8_t bin_size)
887 if (current_group == previous_group)
890 /* Move keys back to previous group */
891 for (i = current_group->num_rules - bin_size;
892 i < current_group->num_rules; i++) {
893 previous_group->key_idx[previous_group->num_rules] =
894 current_group->key_idx[i];
895 previous_group->value[previous_group->num_rules] =
896 current_group->value[i];
897 previous_group->bin_id[previous_group->num_rules] =
898 current_group->bin_id[i];
899 previous_group->num_rules++;
903 * Decrease number of rules after the move
906 current_group->num_rules -= bin_size;
910 * Computes an updated table entry where the supplied key points to a new host.
911 * If no entry exists, one is inserted.
913 * This function does NOT modify the online table(s)
914 * This function DOES modify the offline table
917 * EFD table to reference
919 * Socket ID to use to lookup existing values (ideally caller's socket id)
923 * Value to associate with key
925 * Chunk ID of the chunk that was modified
927 * Group ID of the group that was modified
929 * Bin ID that was modified
930 * @param new_bin_choice
931 * Newly chosen permutation which this bin will use
933 * Newly computed online entry to apply later with efd_apply_update
936 * RTE_EFD_UPDATE_WARN_GROUP_FULL
937 * Operation is insert, and the last available space in the
938 * key's group was just used. Future inserts may fail as groups fill up.
939 * This operation was still successful, and entry contains a valid update
940 * RTE_EFD_UPDATE_FAILED
941 * Either the EFD failed to find a suitable perfect hash or the group was full
942 * This is a fatal error, and the table is now in an indeterminate state
943 * RTE_EFD_UPDATE_NO_CHANGE
944 * Operation resulted in no change to the table (same value already exists)
946 * Insert or update was successful, and the new efd_online_group_entry
947 * is stored in *entry
950 * Note that entry will be UNCHANGED if the update has no effect, and thus any
951 * subsequent use of the entry content will likely be invalid
954 efd_compute_update(struct rte_efd_table * const table,
955 const unsigned int socket_id, const void *key,
956 const efd_value_t value, uint32_t * const chunk_id,
957 uint32_t * const group_id, uint32_t * const bin_id,
958 uint8_t * const new_bin_choice,
959 struct efd_online_group_entry * const entry)
964 void *new_k, *slot_id = NULL;
965 int status = EXIT_SUCCESS;
966 unsigned int found = 0;
968 efd_compute_ids(table, key, chunk_id, bin_id);
970 struct efd_offline_chunk_rules * const chunk =
971 &table->offline_chunks[*chunk_id];
972 struct efd_offline_group_rules *new_group;
974 uint8_t current_choice = efd_get_choice(table, socket_id,
976 uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
977 struct efd_offline_group_rules * const current_group =
978 &chunk->group_rules[current_group_id];
979 uint8_t bin_size = 0;
980 uint8_t key_changed_index = 0;
981 efd_value_t key_changed_previous_value = 0;
982 uint32_t key_idx_previous = 0;
984 /* Scan the current group and see if the key is already present */
985 for (i = 0; i < current_group->num_rules; i++) {
986 if (current_group->bin_id[i] == *bin_id)
991 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
992 if (found == 0 && unlikely(memcmp(key_stored, key,
993 table->key_len) == 0)) {
994 /* Key is already present */
997 * If previous value is same as new value,
998 * no additional work is required
1000 if (current_group->value[i] == value)
1001 return RTE_EFD_UPDATE_NO_CHANGE;
1003 key_idx_previous = current_group->key_idx[i];
1004 key_changed_previous_value = current_group->value[i];
1005 key_changed_index = i;
1006 current_group->value[i] = value;
1012 /* Key does not exist. Insert the rule into the bin/group */
1013 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1015 "Fatal: No room remaining for insert into "
1016 "chunk %u group %u bin %u\n",
1018 current_group_id, *bin_id);
1019 return RTE_EFD_UPDATE_FAILED;
1022 if (unlikely(current_group->num_rules ==
1023 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1024 RTE_LOG(INFO, EFD, "Warn: Insert into last "
1025 "available slot in chunk %u "
1026 "group %u bin %u\n", *chunk_id,
1027 current_group_id, *bin_id);
1028 status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1031 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1032 return RTE_EFD_UPDATE_FAILED;
1034 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1036 rte_prefetch0(new_k);
1037 new_idx = (uint32_t) ((uintptr_t) slot_id);
1039 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1040 current_group->key_idx[current_group->num_rules] = new_idx;
1041 current_group->value[current_group->num_rules] = value;
1042 current_group->bin_id[current_group->num_rules] = *bin_id;
1043 current_group->num_rules++;
1047 uint32_t last = current_group->num_rules - 1;
1048 /* Swap the key with the last key inserted*/
1049 current_group->key_idx[key_changed_index] =
1050 current_group->key_idx[last];
1051 current_group->value[key_changed_index] =
1052 current_group->value[last];
1053 current_group->bin_id[key_changed_index] =
1054 current_group->bin_id[last];
1057 * Key to be updated will always be available
1058 * at the end of the group
1060 current_group->key_idx[last] = key_idx_previous;
1061 current_group->value[last] = value;
1062 current_group->bin_id[last] = *bin_id;
1065 *new_bin_choice = current_choice;
1066 *group_id = current_group_id;
1067 new_group = current_group;
1069 /* Group need to be rebalanced when it starts to get loaded */
1070 if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1073 * Subtract the number of entries in the bin from
1074 * the original group
1076 current_group->num_rules -= bin_size;
1079 * Figure out which of the available groups that this bin
1080 * can map to is the smallest (using the current group
1083 uint8_t smallest_choice = current_choice;
1084 uint8_t smallest_size = current_group->num_rules;
1085 uint32_t smallest_group_id = current_group_id;
1086 unsigned char choice;
1088 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1090 uint32_t test_group_id =
1091 efd_bin_to_group[choice][*bin_id];
1092 uint32_t num_rules =
1093 chunk->group_rules[test_group_id].num_rules;
1094 if (num_rules < smallest_size) {
1095 smallest_choice = choice;
1096 smallest_size = num_rules;
1097 smallest_group_id = test_group_id;
1101 *new_bin_choice = smallest_choice;
1102 *group_id = smallest_group_id;
1103 new_group = &chunk->group_rules[smallest_group_id];
1104 current_group->num_rules += bin_size;
1110 if (current_group != new_group &&
1111 new_group->num_rules + bin_size >
1112 EFD_MAX_GROUP_NUM_RULES) {
1114 "Unable to move_groups to dest group "
1115 "containing %u entries."
1116 "bin_size:%u choice:%02x\n",
1117 new_group->num_rules, bin_size,
1121 move_groups(*bin_id, bin_size, new_group, current_group);
1123 * Recompute the hash function for the modified group,
1124 * and return it to the caller
1126 ret = efd_search_hash(table, new_group, entry);
1132 "Failed to find perfect hash for group "
1133 "containing %u entries. bin_size:%u choice:%02x\n",
1134 new_group->num_rules, bin_size, choice - 1);
1135 /* Restore groups modified to their previous state */
1136 revert_groups(current_group, new_group, bin_size);
1139 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1141 *new_bin_choice = choice;
1142 *group_id = efd_bin_to_group[choice][*bin_id];
1143 new_group = &chunk->group_rules[*group_id];
1148 current_group->num_rules--;
1151 current_group->value[current_group->num_rules - 1] =
1152 key_changed_previous_value;
1153 return RTE_EFD_UPDATE_FAILED;
1157 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1158 const void *key, const efd_value_t value)
1160 uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1161 uint8_t new_bin_choice = 0;
1162 struct efd_online_group_entry entry;
1164 int status = efd_compute_update(table, socket_id, key, value,
1165 &chunk_id, &group_id, &bin_id,
1166 &new_bin_choice, &entry);
1168 if (status == RTE_EFD_UPDATE_NO_CHANGE)
1169 return EXIT_SUCCESS;
1171 if (status == RTE_EFD_UPDATE_FAILED)
1174 efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1175 new_bin_choice, &entry);
1180 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1181 const void *key, efd_value_t * const prev_value)
1184 uint32_t chunk_id, bin_id;
1185 uint8_t not_found = 1;
1187 efd_compute_ids(table, key, &chunk_id, &bin_id);
1189 struct efd_offline_chunk_rules * const chunk =
1190 &table->offline_chunks[chunk_id];
1192 uint8_t current_choice = efd_get_choice(table, socket_id,
1194 uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1195 struct efd_offline_group_rules * const current_group =
1196 &chunk->group_rules[current_group_id];
1199 * Search the current group for the specified key.
1200 * If it exists, remove it and re-pack the other values
1202 for (i = 0; i < current_group->num_rules; i++) {
1204 /* Found key that needs to be removed */
1205 if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1206 key, table->key_len) == 0) {
1207 /* Store previous value if requested by caller */
1208 if (prev_value != NULL)
1209 *prev_value = current_group->value[i];
1212 rte_ring_sp_enqueue(table->free_slots,
1213 (void *)((uintptr_t)current_group->key_idx[i]));
1217 * If the desired key has been found,
1218 * need to shift other values up one
1221 /* Need to shift this entry back up one index */
1222 current_group->key_idx[i - 1] = current_group->key_idx[i];
1223 current_group->value[i - 1] = current_group->value[i];
1224 current_group->bin_id[i - 1] = current_group->bin_id[i];
1228 if (not_found == 0) {
1230 current_group->num_rules--;
1236 static inline efd_value_t
1237 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1238 const efd_lookuptbl_t *group_lookup_table,
1239 const uint32_t hash_val_a, const uint32_t hash_val_b)
1241 efd_value_t value = 0;
1244 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1246 uint32_t h = hash_val_a + (hash_val_b *
1247 group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1248 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1249 value |= (group_lookup_table[
1250 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1258 static inline efd_value_t
1259 efd_lookup_internal(const struct efd_online_group_entry * const group,
1260 const uint32_t hash_val_a, const uint32_t hash_val_b,
1261 enum efd_lookup_internal_function lookup_fn)
1263 efd_value_t value = 0;
1265 switch (lookup_fn) {
1267 #if defined(RTE_ARCH_X86) && defined(CC_SUPPORT_AVX2)
1268 case EFD_LOOKUP_AVX2:
1269 return efd_lookup_internal_avx2(group->hash_idx,
1270 group->lookup_table,
1275 #if defined(RTE_ARCH_ARM64)
1276 case EFD_LOOKUP_NEON:
1277 return efd_lookup_internal_neon(group->hash_idx,
1278 group->lookup_table,
1283 case EFD_LOOKUP_SCALAR:
1286 return efd_lookup_internal_scalar(group->hash_idx,
1287 group->lookup_table,
1296 rte_efd_lookup(const struct rte_efd_table * const table,
1297 const unsigned int socket_id, const void *key)
1299 uint32_t chunk_id, group_id, bin_id;
1301 const struct efd_online_group_entry *group;
1302 const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1304 /* Determine the chunk and group location for the given key */
1305 efd_compute_ids(table, key, &chunk_id, &bin_id);
1306 bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1307 group_id = efd_bin_to_group[bin_choice][bin_id];
1308 group = &chunks[chunk_id].groups[group_id];
1310 return efd_lookup_internal(group,
1311 EFD_HASHFUNCA(key, table),
1312 EFD_HASHFUNCB(key, table),
1316 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1317 const unsigned int socket_id, const int num_keys,
1318 const void **key_list, efd_value_t * const value_list)
1321 uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1322 uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1323 uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1324 uint32_t group_id_list[RTE_EFD_BURST_MAX];
1325 struct efd_online_group_entry *group;
1327 struct efd_online_chunk *chunks = table->chunks[socket_id];
1329 for (i = 0; i < num_keys; i++) {
1330 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1332 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1335 for (i = 0; i < num_keys; i++) {
1336 bin_choice_list[i] = efd_get_choice(table, socket_id,
1337 chunk_id_list[i], bin_id_list[i]);
1339 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1340 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1341 rte_prefetch0(group);
1344 for (i = 0; i < num_keys; i++) {
1345 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1346 value_list[i] = efd_lookup_internal(group,
1347 EFD_HASHFUNCA(key_list[i], table),
1348 EFD_HASHFUNCB(key_list[i], table),