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>
23 #include <rte_tailq.h>
27 #if defined(RTE_ARCH_X86)
28 #include "rte_efd_x86.h"
29 #elif defined(RTE_ARCH_ARM64)
30 #include "rte_efd_arm64.h"
33 #define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len))
34 /** Hash function used to determine chunk_id and bin_id for a group */
35 #define EFD_HASH(key, table) \
36 (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34))
37 /** Hash function used as constant component of perfect hash search */
38 #define EFD_HASHFUNCA(key, table) \
39 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35))
40 /** Hash function used as multiplicative component of perfect hash search */
41 #define EFD_HASHFUNCB(key, table) \
42 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36))
44 /*************************************************************************
46 *************************************************************************/
48 /* These parameters are fixed by the efd_bin_to_group balancing table */
49 #define EFD_CHUNK_NUM_GROUPS (64)
50 #define EFD_CHUNK_NUM_BINS (256)
51 #define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \
52 (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS)
55 * Target number of rules that each chunk is created to handle.
56 * Used when initially allocating the table
58 #define EFD_TARGET_CHUNK_NUM_RULES \
59 (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)
61 * Max number of rules that each chunk is created to handle.
62 * Used when initially allocating the table
64 #define EFD_TARGET_CHUNK_MAX_NUM_RULES \
65 (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES)
67 /** This is fixed based on the bin_to_group permutation array */
68 #define EFD_MAX_GROUP_NUM_BINS (16)
71 * The end of the chunks array needs some extra padding to ensure
72 * that vectorization over-reads on the last online chunk stay within
75 #define EFD_NUM_CHUNK_PADDING_BYTES (256)
77 /* All different internal lookup functions */
78 enum efd_lookup_internal_function {
79 EFD_LOOKUP_SCALAR = 0,
85 TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
87 static struct rte_tailq_elem rte_efd_tailq = {
90 EAL_REGISTER_TAILQ(rte_efd_tailq);
92 /** Internal permutation array used to shuffle bins into pseudorandom groups */
93 const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
95 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
96 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
97 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
98 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
99 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
100 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
101 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
102 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
103 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
104 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
105 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
106 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
107 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
108 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
109 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
110 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
113 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
114 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
115 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
116 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
117 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
118 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
119 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
120 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
121 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
122 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
123 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
124 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
125 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
126 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
127 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
128 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
131 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
132 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
133 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
134 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
135 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
136 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
137 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
138 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
139 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
140 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
141 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
142 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
143 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
144 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
145 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
146 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
149 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
150 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
151 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
152 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
153 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
154 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
155 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
156 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
157 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
158 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
159 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
160 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
161 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
162 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
163 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
164 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
168 /*************************************************************************
169 * Offline region structures
170 *************************************************************************/
172 /** Online group containing number of rules, values, keys and their bins
173 * for EFD_MAX_GROUP_NUM_RULES rules.
175 struct efd_offline_group_rules {
177 /**< Sum of the number of rules in all bins assigned to this group. */
179 uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
180 /**< Array with all keys of the group. */
181 efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
182 /**< Array with all values of the keys of the group. */
184 uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
185 /**< Stores the bin for each corresponding key to
186 * avoid having to recompute it
190 /** Offline chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
191 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
193 struct efd_offline_chunk_rules {
195 /**< Number of rules in the entire chunk;
196 * used to detect unbalanced groups
199 struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
200 /**< Array of all groups in the chunk. */
203 /*************************************************************************
204 * Online region structures
205 *************************************************************************/
207 /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */
208 struct efd_online_group_entry {
209 efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
210 efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
214 * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
215 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
217 struct efd_online_chunk {
218 uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
219 /**< This is a packed indirection index into the 'groups' array.
220 * Each byte contains four two-bit values which index into
221 * the efd_bin_to_group array.
222 * The efd_bin_to_group array returns the index into the groups array
225 struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
226 /**< Array of all the groups in the chunk. */
230 * EFD table structure
232 struct rte_efd_table {
233 char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */
235 uint32_t key_len; /**< Length of the key stored offline */
237 uint32_t max_num_rules;
238 /**< Static maximum number of entries the table was constructed to hold. */
241 /**< Number of entries currently in the table . */
244 /**< Number of chunks in the table needed to support num_rules. */
246 uint32_t num_chunks_shift;
247 /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */
249 enum efd_lookup_internal_function lookup_fn;
250 /**< Indicates which lookup function to use. */
252 struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
253 /**< Dynamic array of size num_chunks of chunk records. */
255 struct efd_offline_chunk_rules *offline_chunks;
256 /**< Dynamic array of size num_chunks of key-value pairs. */
258 struct rte_ring *free_slots;
259 /**< Ring that stores all indexes of the free slots in the key table */
261 uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */
265 * Computes the chunk ID for a given key hash
268 * EFD table to reference
270 * 32-bit key hash returned by EFD_HASH
273 * chunk ID containing this key hash
275 static inline uint32_t
276 efd_get_chunk_id(const struct rte_efd_table * const table,
277 const uint32_t hashed_key)
279 return hashed_key & (table->num_chunks - 1);
283 * Computes the bin ID for a given key hash
286 * EFD table to reference
288 * 32-bit key hash returned by EFD_HASH
290 * @return bin ID containing this key hash
292 static inline uint32_t
293 efd_get_bin_id(const struct rte_efd_table * const table,
294 const uint32_t hashed_key)
296 return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
300 * Looks up the current permutation choice for a particular bin in the online table
303 * EFD table to reference
305 * Socket ID to use to look up existing values (ideally caller's socket id)
307 * Chunk ID of bin to look up
312 * Currently active permutation choice in the online table
314 static inline uint8_t
315 efd_get_choice(const struct rte_efd_table * const table,
316 const unsigned int socket_id, const uint32_t chunk_id,
317 const uint32_t bin_id)
319 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
322 * Grab the chunk (byte) that contains the choices
323 * for four neighboring bins.
325 uint8_t choice_chunk =
326 chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
329 * Compute the offset into the chunk that contains
330 * the group_id lookup position
332 int offset = (bin_id & 0x3) * 2;
334 /* Extract from the byte just the desired lookup position */
335 return (uint8_t) ((choice_chunk >> offset) & 0x3);
339 * Compute the chunk_id and bin_id for a given key
342 * EFD table to reference
344 * Key to hash and find location of
352 efd_compute_ids(const struct rte_efd_table * const table,
353 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
355 /* Compute the position of the entry in the hash table */
356 uint32_t h = EFD_HASH(key, table);
358 /* Compute the chunk_id where that entry can be found */
359 *chunk_id = efd_get_chunk_id(table, h);
362 * Compute the bin within that chunk where the entry
363 * can be found (0 - 255)
365 *bin_id = efd_get_bin_id(table, h);
369 * Search for a hash function for a group that satisfies all group results
372 efd_search_hash(struct rte_efd_table * const table,
373 const struct efd_offline_group_rules * const off_group,
374 struct efd_online_group_entry * const on_group)
376 efd_hashfunc_t hash_idx;
377 efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
378 efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
380 uint32_t i, j, rule_id;
381 uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
382 uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
383 uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
386 rte_prefetch0(off_group->value);
389 * Prepopulate the hash_val tables by running the two hash functions
390 * for each provided rule
392 for (i = 0; i < off_group->num_rules; i++) {
393 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
394 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
395 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
398 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
399 hash_idx = on_group->hash_idx[i];
400 start_hash_idx[i] = hash_idx;
401 start_lookup_table[i] = on_group->lookup_table[i];
404 efd_lookuptbl_t lookup_table = 0;
405 efd_lookuptbl_t lookup_table_complement = 0;
407 for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
408 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
409 hash_val_b[rule_id]);
412 * The goal here is to find a hash function for this
413 * particular bit entry that meets the following criteria:
414 * The most significant bits of the hash result define a
415 * shift into the lookup table where the bit will be stored
418 /* Iterate over each provided rule */
419 for (rule_id = 0; rule_id < off_group->num_rules;
422 * Use the few most significant bits (number based on
423 * EFD_LOOKUPTBL_SIZE) to see what position the
424 * expected bit should be set in the lookup_table
426 uint32_t bucket_idx = hash_val[rule_id] >>
430 * Get the current bit of interest.
431 * This only find an appropriate hash function
432 * for one bit at a time of the rule
434 efd_lookuptbl_t expected =
435 (off_group->value[rule_id] >> i) & 0x1;
438 * Add the expected bit (if set) to a map
439 * (lookup_table). Also set its complement
440 * in lookup_table_complement
442 lookup_table |= expected << bucket_idx;
443 lookup_table_complement |= (1 - expected)
447 * If ever the hash function of two different
448 * elements result in different values at the
449 * same location in the lookup_table,
450 * the current hash_idx is not valid.
452 if (lookup_table & lookup_table_complement)
457 * Check if the previous loop completed without
460 if (rule_id == off_group->num_rules) {
462 * Current hash function worked, store it
463 * for the current group
465 on_group->hash_idx[i] = hash_idx;
466 on_group->lookup_table[i] = lookup_table;
469 * Make sure that the hash function has changed
470 * from the starting value
472 hash_idx = start_hash_idx[i] + 1;
477 } while (hash_idx != start_hash_idx[i]);
479 /* Failed to find perfect hash for this group */
480 if (hash_idx == start_hash_idx[i]) {
482 * Restore previous hash_idx and lookup_table
485 for (j = 0; j < i; j++) {
486 on_group->hash_idx[j] = start_hash_idx[j];
487 on_group->lookup_table[j] = start_lookup_table[j];
496 struct rte_efd_table *
497 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
498 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
500 struct rte_efd_table *table = NULL;
501 uint8_t *key_array = NULL;
502 uint32_t num_chunks, num_chunks_shift;
504 struct rte_efd_list *efd_list = NULL;
505 struct rte_tailq_entry *te;
506 uint64_t offline_table_size;
507 char ring_name[RTE_RING_NAMESIZE];
508 struct rte_ring *r = NULL;
511 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
513 if (online_cpu_socket_bitmask == 0) {
514 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
519 if (max_num_rules == 0) {
520 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
525 * Compute the minimum number of chunks (smallest power of 2)
526 * that can hold all of the rules
528 if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
529 num_chunks = rte_align32pow2(max_num_rules /
530 EFD_TARGET_CHUNK_NUM_RULES);
532 num_chunks = rte_align32pow2((max_num_rules /
533 EFD_TARGET_CHUNK_NUM_RULES) + 1);
535 num_chunks_shift = rte_bsf32(num_chunks);
537 rte_mcfg_tailq_write_lock();
540 * Guarantee there's no existing: this is normally already checked
541 * by ring creation above
543 TAILQ_FOREACH(te, efd_list, next)
545 table = (struct rte_efd_table *) te->data;
546 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
554 goto error_unlock_exit;
557 te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
559 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
560 goto error_unlock_exit;
563 /* Create a new EFD table management structure */
564 table = rte_zmalloc_socket(NULL,
565 sizeof(struct rte_efd_table),
569 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
570 " on socket %u failed\n",
572 goto error_unlock_exit;
576 RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
577 "on socket %u\n", offline_cpu_socket);
579 table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
580 table->num_rules = 0;
581 table->num_chunks = num_chunks;
582 table->num_chunks_shift = num_chunks_shift;
583 table->key_len = key_len;
586 key_array = rte_zmalloc_socket(NULL,
587 table->max_num_rules * table->key_len,
590 if (key_array == NULL) {
591 RTE_LOG(ERR, EFD, "Allocating key array"
592 " on socket %u failed\n",
594 goto error_unlock_exit;
596 table->keys = key_array;
597 strlcpy(table->name, name, sizeof(table->name));
599 RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
600 " which potentially supports %u entries\n",
601 num_chunks, table->max_num_rules);
603 /* Make sure all the allocatable table pointers are NULL initially */
604 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
605 table->chunks[socket_id] = NULL;
606 table->offline_chunks = NULL;
609 * Allocate one online table per socket specified
610 * in the user-supplied bitmask
612 uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
613 EFD_NUM_CHUNK_PADDING_BYTES;
615 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
616 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
618 * Allocate all of the EFD table chunks (the online portion)
619 * as a continuous block
621 table->chunks[socket_id] =
627 if (table->chunks[socket_id] == NULL) {
629 "Allocating EFD online table on "
630 "socket %u failed\n",
632 goto error_unlock_exit;
635 "Allocated EFD online table of size "
636 "%"PRIu64" bytes (%.2f MB) on socket %u\n",
638 (float) online_table_size /
644 #if defined(RTE_ARCH_X86)
646 * For less than 4 bits, scalar function performs better
647 * than vectorised version
649 if (RTE_EFD_VALUE_NUM_BITS > 3
650 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2)
651 && rte_vect_get_max_simd_bitwidth() >= RTE_VECT_SIMD_256)
652 table->lookup_fn = EFD_LOOKUP_AVX2;
655 #if defined(RTE_ARCH_ARM64)
657 * For less than or equal to 16 bits, scalar function performs better
658 * than vectorised version
660 if (RTE_EFD_VALUE_NUM_BITS > 16 &&
661 rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON) &&
662 rte_vect_get_max_simd_bitwidth() >= RTE_VECT_SIMD_128)
663 table->lookup_fn = EFD_LOOKUP_NEON;
666 table->lookup_fn = EFD_LOOKUP_SCALAR;
669 * Allocate the EFD table offline portion (with the actual rules
670 * mapping keys to values) as a continuous block.
671 * This could be several gigabytes of memory.
673 offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
674 table->offline_chunks =
675 rte_zmalloc_socket(NULL,
679 if (table->offline_chunks == NULL) {
680 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
681 "failed\n", offline_cpu_socket);
682 goto error_unlock_exit;
686 "Allocated EFD offline table of size %"PRIu64" bytes "
687 " (%.2f MB) on socket %u\n", offline_table_size,
688 (float) offline_table_size / (1024.0F * 1024.0F),
691 te->data = (void *) table;
692 TAILQ_INSERT_TAIL(efd_list, te, next);
693 rte_mcfg_tailq_write_unlock();
695 snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
696 /* Create ring (Dummy slot index is not enqueued) */
697 r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
698 offline_cpu_socket, 0);
700 RTE_LOG(ERR, EFD, "memory allocation failed\n");
705 /* Populate free slots ring. Entry zero is reserved for key misses. */
706 for (i = 0; i < table->max_num_rules; i++)
707 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
709 table->free_slots = r;
713 rte_mcfg_tailq_write_unlock();
719 struct rte_efd_table *
720 rte_efd_find_existing(const char *name)
722 struct rte_efd_table *table = NULL;
723 struct rte_tailq_entry *te;
724 struct rte_efd_list *efd_list;
726 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
728 rte_mcfg_tailq_read_lock();
730 TAILQ_FOREACH(te, efd_list, next)
732 table = (struct rte_efd_table *) te->data;
733 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
736 rte_mcfg_tailq_read_unlock();
746 rte_efd_free(struct rte_efd_table *table)
749 struct rte_efd_list *efd_list;
750 struct rte_tailq_entry *te, *temp;
755 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
756 rte_free(table->chunks[socket_id]);
758 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
759 rte_mcfg_tailq_write_lock();
761 TAILQ_FOREACH_SAFE(te, efd_list, next, temp) {
762 if (te->data == (void *) table) {
763 TAILQ_REMOVE(efd_list, te, next);
769 rte_mcfg_tailq_write_unlock();
770 rte_ring_free(table->free_slots);
771 rte_free(table->offline_chunks);
772 rte_free(table->keys);
777 * Applies a previously computed table entry to the specified table for all
778 * socket-local copies of the online table.
779 * Intended to apply an update for only a single change
780 * to a key/value pair at a time
783 * EFD table to reference
785 * Socket ID to use to lookup existing values (ideally caller's socket id)
787 * Chunk index to update
789 * Group index to update
791 * Bin within the group that this update affects
792 * @param new_bin_choice
793 * Newly chosen permutation which this bin should use - only lower 2 bits
794 * @param new_group_entry
795 * Previously computed updated chunk/group entry
798 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
799 const uint32_t chunk_id, const uint32_t group_id,
800 const uint32_t bin_id, const uint8_t new_bin_choice,
801 const struct efd_online_group_entry * const new_group_entry)
804 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
805 uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
808 * Grab the current byte that contains the choices
809 * for four neighboring bins
811 uint8_t choice_chunk =
812 chunk->bin_choice_list[bin_index];
815 /* Compute the offset into the chunk that needs to be updated */
816 int offset = (bin_id & 0x3) * 2;
818 /* Zero the two bits of interest and set them to new_bin_choice */
819 choice_chunk = (choice_chunk & (~(0x03 << offset)))
820 | ((new_bin_choice & 0x03) << offset);
822 /* Update the online table with the new data across all sockets */
823 for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
824 if (table->chunks[i] != NULL) {
825 memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
827 sizeof(struct efd_online_group_entry));
828 table->chunks[i][chunk_id].bin_choice_list[bin_index] =
835 * Move the bin from prev group to the new group
838 move_groups(uint32_t bin_id, uint8_t bin_size,
839 struct efd_offline_group_rules *new_group,
840 struct efd_offline_group_rules * const current_group)
843 uint8_t empty_idx = 0;
846 if (new_group == current_group)
849 for (i = 0; i < current_group->num_rules; i++) {
851 * Move keys that belong to the same bin
854 if (current_group->bin_id[i] == bin_id) {
855 new_group->key_idx[new_group->num_rules] =
856 current_group->key_idx[i];
857 new_group->value[new_group->num_rules] =
858 current_group->value[i];
859 new_group->bin_id[new_group->num_rules] =
860 current_group->bin_id[i];
861 new_group->num_rules++;
863 if (i != empty_idx) {
865 * Need to move this key towards
866 * the top of the array
868 current_group->key_idx[empty_idx] =
869 current_group->key_idx[i];
870 current_group->value[empty_idx] =
871 current_group->value[i];
872 current_group->bin_id[empty_idx] =
873 current_group->bin_id[i];
879 current_group->num_rules -= bin_size;
883 * Revert group/s to their previous state before
884 * trying to insert/add a new key
887 revert_groups(struct efd_offline_group_rules *previous_group,
888 struct efd_offline_group_rules *current_group, uint8_t bin_size)
892 if (current_group == previous_group)
895 /* Move keys back to previous group */
896 for (i = current_group->num_rules - bin_size;
897 i < current_group->num_rules; i++) {
898 previous_group->key_idx[previous_group->num_rules] =
899 current_group->key_idx[i];
900 previous_group->value[previous_group->num_rules] =
901 current_group->value[i];
902 previous_group->bin_id[previous_group->num_rules] =
903 current_group->bin_id[i];
904 previous_group->num_rules++;
908 * Decrease number of rules after the move
911 current_group->num_rules -= bin_size;
915 * Computes an updated table entry where the supplied key points to a new host.
916 * If no entry exists, one is inserted.
918 * This function does NOT modify the online table(s)
919 * This function DOES modify the offline table
922 * EFD table to reference
924 * Socket ID to use to lookup existing values (ideally caller's socket id)
928 * Value to associate with key
930 * Chunk ID of the chunk that was modified
932 * Group ID of the group that was modified
934 * Bin ID that was modified
935 * @param new_bin_choice
936 * Newly chosen permutation which this bin will use
938 * Newly computed online entry to apply later with efd_apply_update
941 * RTE_EFD_UPDATE_WARN_GROUP_FULL
942 * Operation is insert, and the last available space in the
943 * key's group was just used. Future inserts may fail as groups fill up.
944 * This operation was still successful, and entry contains a valid update
945 * RTE_EFD_UPDATE_FAILED
946 * Either the EFD failed to find a suitable perfect hash or the group was full
947 * This is a fatal error, and the table is now in an indeterminate state
948 * RTE_EFD_UPDATE_NO_CHANGE
949 * Operation resulted in no change to the table (same value already exists)
951 * Insert or update was successful, and the new efd_online_group_entry
952 * is stored in *entry
955 * Note that entry will be UNCHANGED if the update has no effect, and thus any
956 * subsequent use of the entry content will likely be invalid
959 efd_compute_update(struct rte_efd_table * const table,
960 const unsigned int socket_id, const void *key,
961 const efd_value_t value, uint32_t * const chunk_id,
962 uint32_t * const group_id, uint32_t * const bin_id,
963 uint8_t * const new_bin_choice,
964 struct efd_online_group_entry * const entry)
969 void *new_k, *slot_id = NULL;
970 int status = EXIT_SUCCESS;
971 unsigned int found = 0;
973 efd_compute_ids(table, key, chunk_id, bin_id);
975 struct efd_offline_chunk_rules * const chunk =
976 &table->offline_chunks[*chunk_id];
977 struct efd_offline_group_rules *new_group;
979 uint8_t current_choice = efd_get_choice(table, socket_id,
981 uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
982 struct efd_offline_group_rules * const current_group =
983 &chunk->group_rules[current_group_id];
984 uint8_t bin_size = 0;
985 uint8_t key_changed_index = 0;
986 efd_value_t key_changed_previous_value = 0;
987 uint32_t key_idx_previous = 0;
989 /* Scan the current group and see if the key is already present */
990 for (i = 0; i < current_group->num_rules; i++) {
991 if (current_group->bin_id[i] == *bin_id)
996 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
997 if (found == 0 && unlikely(memcmp(key_stored, key,
998 table->key_len) == 0)) {
999 /* Key is already present */
1002 * If previous value is same as new value,
1003 * no additional work is required
1005 if (current_group->value[i] == value)
1006 return RTE_EFD_UPDATE_NO_CHANGE;
1008 key_idx_previous = current_group->key_idx[i];
1009 key_changed_previous_value = current_group->value[i];
1010 key_changed_index = i;
1011 current_group->value[i] = value;
1017 /* Key does not exist. Insert the rule into the bin/group */
1018 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1020 "Fatal: No room remaining for insert into "
1021 "chunk %u group %u bin %u\n",
1023 current_group_id, *bin_id);
1024 return RTE_EFD_UPDATE_FAILED;
1027 if (unlikely(current_group->num_rules ==
1028 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1029 RTE_LOG(INFO, EFD, "Warn: Insert into last "
1030 "available slot in chunk %u "
1031 "group %u bin %u\n", *chunk_id,
1032 current_group_id, *bin_id);
1033 status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1036 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1037 return RTE_EFD_UPDATE_FAILED;
1039 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1041 rte_prefetch0(new_k);
1042 new_idx = (uint32_t) ((uintptr_t) slot_id);
1044 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1045 current_group->key_idx[current_group->num_rules] = new_idx;
1046 current_group->value[current_group->num_rules] = value;
1047 current_group->bin_id[current_group->num_rules] = *bin_id;
1048 current_group->num_rules++;
1052 uint32_t last = current_group->num_rules - 1;
1053 /* Swap the key with the last key inserted*/
1054 current_group->key_idx[key_changed_index] =
1055 current_group->key_idx[last];
1056 current_group->value[key_changed_index] =
1057 current_group->value[last];
1058 current_group->bin_id[key_changed_index] =
1059 current_group->bin_id[last];
1062 * Key to be updated will always be available
1063 * at the end of the group
1065 current_group->key_idx[last] = key_idx_previous;
1066 current_group->value[last] = value;
1067 current_group->bin_id[last] = *bin_id;
1070 *new_bin_choice = current_choice;
1071 *group_id = current_group_id;
1072 new_group = current_group;
1074 /* Group need to be rebalanced when it starts to get loaded */
1075 if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1078 * Subtract the number of entries in the bin from
1079 * the original group
1081 current_group->num_rules -= bin_size;
1084 * Figure out which of the available groups that this bin
1085 * can map to is the smallest (using the current group
1088 uint8_t smallest_choice = current_choice;
1089 uint8_t smallest_size = current_group->num_rules;
1090 uint32_t smallest_group_id = current_group_id;
1091 unsigned char choice;
1093 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1095 uint32_t test_group_id =
1096 efd_bin_to_group[choice][*bin_id];
1097 uint32_t num_rules =
1098 chunk->group_rules[test_group_id].num_rules;
1099 if (num_rules < smallest_size) {
1100 smallest_choice = choice;
1101 smallest_size = num_rules;
1102 smallest_group_id = test_group_id;
1106 *new_bin_choice = smallest_choice;
1107 *group_id = smallest_group_id;
1108 new_group = &chunk->group_rules[smallest_group_id];
1109 current_group->num_rules += bin_size;
1115 if (current_group != new_group &&
1116 new_group->num_rules + bin_size >
1117 EFD_MAX_GROUP_NUM_RULES) {
1119 "Unable to move_groups to dest group "
1120 "containing %u entries."
1121 "bin_size:%u choice:%02x\n",
1122 new_group->num_rules, bin_size,
1126 move_groups(*bin_id, bin_size, new_group, current_group);
1128 * Recompute the hash function for the modified group,
1129 * and return it to the caller
1131 ret = efd_search_hash(table, new_group, entry);
1137 "Failed to find perfect hash for group "
1138 "containing %u entries. bin_size:%u choice:%02x\n",
1139 new_group->num_rules, bin_size, choice - 1);
1140 /* Restore groups modified to their previous state */
1141 revert_groups(current_group, new_group, bin_size);
1144 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1146 *new_bin_choice = choice;
1147 *group_id = efd_bin_to_group[choice][*bin_id];
1148 new_group = &chunk->group_rules[*group_id];
1153 current_group->num_rules--;
1156 current_group->value[current_group->num_rules - 1] =
1157 key_changed_previous_value;
1158 return RTE_EFD_UPDATE_FAILED;
1162 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1163 const void *key, const efd_value_t value)
1165 uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1166 uint8_t new_bin_choice = 0;
1167 struct efd_online_group_entry entry;
1169 int status = efd_compute_update(table, socket_id, key, value,
1170 &chunk_id, &group_id, &bin_id,
1171 &new_bin_choice, &entry);
1173 if (status == RTE_EFD_UPDATE_NO_CHANGE)
1174 return EXIT_SUCCESS;
1176 if (status == RTE_EFD_UPDATE_FAILED)
1179 efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1180 new_bin_choice, &entry);
1185 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1186 const void *key, efd_value_t * const prev_value)
1189 uint32_t chunk_id, bin_id;
1190 uint8_t not_found = 1;
1192 efd_compute_ids(table, key, &chunk_id, &bin_id);
1194 struct efd_offline_chunk_rules * const chunk =
1195 &table->offline_chunks[chunk_id];
1197 uint8_t current_choice = efd_get_choice(table, socket_id,
1199 uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1200 struct efd_offline_group_rules * const current_group =
1201 &chunk->group_rules[current_group_id];
1204 * Search the current group for the specified key.
1205 * If it exists, remove it and re-pack the other values
1207 for (i = 0; i < current_group->num_rules; i++) {
1209 /* Found key that needs to be removed */
1210 if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1211 key, table->key_len) == 0) {
1212 /* Store previous value if requested by caller */
1213 if (prev_value != NULL)
1214 *prev_value = current_group->value[i];
1217 rte_ring_sp_enqueue(table->free_slots,
1218 (void *)((uintptr_t)current_group->key_idx[i]));
1222 * If the desired key has been found,
1223 * need to shift other values up one
1226 /* Need to shift this entry back up one index */
1227 current_group->key_idx[i - 1] = current_group->key_idx[i];
1228 current_group->value[i - 1] = current_group->value[i];
1229 current_group->bin_id[i - 1] = current_group->bin_id[i];
1233 if (not_found == 0) {
1235 current_group->num_rules--;
1241 static inline efd_value_t
1242 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1243 const efd_lookuptbl_t *group_lookup_table,
1244 const uint32_t hash_val_a, const uint32_t hash_val_b)
1246 efd_value_t value = 0;
1249 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1251 uint32_t h = hash_val_a + (hash_val_b *
1252 group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1253 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1254 value |= (group_lookup_table[
1255 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1263 static inline efd_value_t
1264 efd_lookup_internal(const struct efd_online_group_entry * const group,
1265 const uint32_t hash_val_a, const uint32_t hash_val_b,
1266 enum efd_lookup_internal_function lookup_fn)
1268 efd_value_t value = 0;
1270 switch (lookup_fn) {
1272 #if defined(RTE_ARCH_X86) && defined(CC_SUPPORT_AVX2)
1273 case EFD_LOOKUP_AVX2:
1274 return efd_lookup_internal_avx2(group->hash_idx,
1275 group->lookup_table,
1280 #if defined(RTE_ARCH_ARM64)
1281 case EFD_LOOKUP_NEON:
1282 return efd_lookup_internal_neon(group->hash_idx,
1283 group->lookup_table,
1288 case EFD_LOOKUP_SCALAR:
1291 return efd_lookup_internal_scalar(group->hash_idx,
1292 group->lookup_table,
1301 rte_efd_lookup(const struct rte_efd_table * const table,
1302 const unsigned int socket_id, const void *key)
1304 uint32_t chunk_id, group_id, bin_id;
1306 const struct efd_online_group_entry *group;
1307 const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1309 /* Determine the chunk and group location for the given key */
1310 efd_compute_ids(table, key, &chunk_id, &bin_id);
1311 bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1312 group_id = efd_bin_to_group[bin_choice][bin_id];
1313 group = &chunks[chunk_id].groups[group_id];
1315 return efd_lookup_internal(group,
1316 EFD_HASHFUNCA(key, table),
1317 EFD_HASHFUNCB(key, table),
1321 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1322 const unsigned int socket_id, const int num_keys,
1323 const void **key_list, efd_value_t * const value_list)
1326 uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1327 uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1328 uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1329 uint32_t group_id_list[RTE_EFD_BURST_MAX];
1330 struct efd_online_group_entry *group;
1332 struct efd_online_chunk *chunks = table->chunks[socket_id];
1334 for (i = 0; i < num_keys; i++) {
1335 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1337 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1340 for (i = 0; i < num_keys; i++) {
1341 bin_choice_list[i] = efd_get_choice(table, socket_id,
1342 chunk_id_list[i], bin_id_list[i]);
1344 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1345 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1346 rte_prefetch0(group);
1349 for (i = 0; i < num_keys; i++) {
1350 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1351 value_list[i] = efd_lookup_internal(group,
1352 EFD_HASHFUNCA(key_list[i], table),
1353 EFD_HASHFUNCB(key_list[i], table),