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.
40 #include <sys/queue.h>
43 #include <rte_eal_memconfig.h>
44 #include <rte_errno.h>
45 #include <rte_malloc.h>
46 #include <rte_memzone.h>
47 #include <rte_prefetch.h>
48 #include <rte_branch_prediction.h>
49 #include <rte_memcpy.h>
51 #include <rte_jhash.h>
52 #include <rte_hash_crc.h>
55 #if defined(RTE_ARCH_X86)
56 #include "rte_efd_x86.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,
110 TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
112 static struct rte_tailq_elem rte_efd_tailq = {
115 EAL_REGISTER_TAILQ(rte_efd_tailq);
117 /** Internal permutation array used to shuffle bins into pseudorandom groups */
118 const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
120 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
121 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
122 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
123 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
124 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
125 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
126 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
127 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
128 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
129 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
130 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
131 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
132 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
133 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
134 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
135 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
138 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
139 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
140 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
141 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
142 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
143 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
144 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
145 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
146 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
147 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
148 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
149 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
150 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
151 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
152 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
153 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
156 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
157 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
158 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
159 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
160 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
161 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
162 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
163 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
164 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
165 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
166 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
167 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
168 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
169 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
170 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
171 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
174 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
175 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
176 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
177 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
178 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
179 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
180 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
181 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
182 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
183 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
184 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
185 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
186 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
187 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
188 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
189 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
193 /*************************************************************************
194 * Offline region structures
195 *************************************************************************/
197 /** Online group containing number of rules, values, keys and their bins
198 * for EFD_MAX_GROUP_NUM_RULES rules.
200 struct efd_offline_group_rules {
202 /**< Sum of the number of rules in all bins assigned to this group. */
204 uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
205 /**< Array with all keys of the group. */
206 efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
207 /**< Array with all values of the keys of the group. */
209 uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
210 /**< Stores the bin for each correspending key to
211 * avoid having to recompute it
215 /** Offline chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
216 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
218 struct efd_offline_chunk_rules {
220 /**< Number of rules in the entire chunk;
221 * used to detect unbalanced groups
224 struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
225 /**< Array of all groups in the chunk. */
228 /*************************************************************************
229 * Online region structures
230 *************************************************************************/
232 /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */
233 struct efd_online_group_entry {
234 efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
235 efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
236 } __attribute__((__packed__));
239 * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
240 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
242 struct efd_online_chunk {
243 uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
244 /**< This is a packed indirection index into the 'groups' array.
245 * Each byte contains four two-bit values which index into
246 * the efd_bin_to_group array.
247 * The efd_bin_to_group array returns the index into the groups array
250 struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
251 /**< Array of all the groups in the chunk. */
252 } __attribute__((__packed__));
255 * EFD table structure
257 struct rte_efd_table {
258 char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */
260 uint32_t key_len; /**< Length of the key stored offline */
262 uint32_t max_num_rules;
263 /**< Static maximum number of entries the table was constructed to hold. */
266 /**< Number of entries currently in the table . */
269 /**< Number of chunks in the table needed to support num_rules. */
271 uint32_t num_chunks_shift;
272 /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */
274 enum efd_lookup_internal_function lookup_fn;
275 /**< Indicates which lookup function to use. */
277 struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
278 /**< Dynamic array of size num_chunks of chunk records. */
280 struct efd_offline_chunk_rules *offline_chunks;
281 /**< Dynamic array of size num_chunks of key-value pairs. */
283 struct rte_ring *free_slots;
284 /**< Ring that stores all indexes of the free slots in the key table */
286 uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */
290 * Computes the chunk ID for a given key hash
293 * EFD table to reference
295 * 32-bit key hash returned by EFD_HASH
298 * chunk ID containing this key hash
300 static inline uint32_t
301 efd_get_chunk_id(const struct rte_efd_table * const table,
302 const uint32_t hashed_key)
304 return hashed_key & (table->num_chunks - 1);
308 * Computes the bin ID for a given key hash
311 * EFD table to reference
313 * 32-bit key hash returned by EFD_HASH
315 * @return bin ID containing this key hash
317 static inline uint32_t
318 efd_get_bin_id(const struct rte_efd_table * const table,
319 const uint32_t hashed_key)
321 return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
325 * Looks up the current permutation choice for a particular bin in the online table
328 * EFD table to reference
330 * Socket ID to use to look up existing values (ideally caller's socket id)
332 * Chunk ID of bin to look up
337 * Currently active permutation choice in the online table
339 static inline uint8_t
340 efd_get_choice(const struct rte_efd_table * const table,
341 const unsigned int socket_id, const uint32_t chunk_id,
342 const uint32_t bin_id)
344 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
347 * Grab the chunk (byte) that contains the choices
348 * for four neighboring bins.
350 uint8_t choice_chunk =
351 chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
354 * Compute the offset into the chunk that contains
355 * the group_id lookup position
357 int offset = (bin_id & 0x3) * 2;
359 /* Extract from the byte just the desired lookup position */
360 return (uint8_t) ((choice_chunk >> offset) & 0x3);
364 * Compute the chunk_id and bin_id for a given key
367 * EFD table to reference
369 * Key to hash and find location of
377 efd_compute_ids(const struct rte_efd_table * const table,
378 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
380 /* Compute the position of the entry in the hash table */
381 uint32_t h = EFD_HASH(key, table);
383 /* Compute the chunk_id where that entry can be found */
384 *chunk_id = efd_get_chunk_id(table, h);
387 * Compute the bin within that chunk where the entry
388 * can be found (0 - 255)
390 *bin_id = efd_get_bin_id(table, h);
394 * Search for a hash function for a group that satisfies all group results
397 efd_search_hash(struct rte_efd_table * const table,
398 const struct efd_offline_group_rules * const off_group,
399 struct efd_online_group_entry * const on_group)
401 efd_hashfunc_t hash_idx;
402 efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
403 efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
405 uint32_t i, j, rule_id;
406 uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
407 uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
408 uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
411 rte_prefetch0(off_group->value);
414 * Prepopulate the hash_val tables by running the two hash functions
415 * for each provided rule
417 for (i = 0; i < off_group->num_rules; i++) {
418 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
419 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
420 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
423 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
424 hash_idx = on_group->hash_idx[i];
425 start_hash_idx[i] = hash_idx;
426 start_lookup_table[i] = on_group->lookup_table[i];
429 efd_lookuptbl_t lookup_table = 0;
430 efd_lookuptbl_t lookup_table_complement = 0;
432 for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
433 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
434 hash_val_b[rule_id]);
437 * The goal here is to find a hash function for this
438 * particular bit entry that meets the following criteria:
439 * The most significant bits of the hash result define a
440 * shift into the lookup table where the bit will be stored
443 /* Iterate over each provided rule */
444 for (rule_id = 0; rule_id < off_group->num_rules;
447 * Use the few most significant bits (number based on
448 * EFD_LOOKUPTBL_SIZE) to see what position the
449 * expected bit should be set in the lookup_table
451 uint32_t bucket_idx = hash_val[rule_id] >>
455 * Get the current bit of interest.
456 * This only find an appropriate hash function
457 * for one bit at a time of the rule
459 efd_lookuptbl_t expected =
460 (off_group->value[rule_id] >> i) & 0x1;
463 * Add the expected bit (if set) to a map
464 * (lookup_table). Also set its complement
465 * in lookup_table_complement
467 lookup_table |= expected << bucket_idx;
468 lookup_table_complement |= (1 - expected)
472 * If ever the hash function of two different
473 * elements result in different values at the
474 * same location in the lookup_table,
475 * the current hash_idx is not valid.
477 if (lookup_table & lookup_table_complement)
482 * Check if the previous loop completed without
485 if (rule_id == off_group->num_rules) {
487 * Current hash function worked, store it
488 * for the current group
490 on_group->hash_idx[i] = hash_idx;
491 on_group->lookup_table[i] = lookup_table;
494 * Make sure that the hash function has changed
495 * from the starting value
497 hash_idx = start_hash_idx[i] + 1;
502 } while (hash_idx != start_hash_idx[i]);
504 /* Failed to find perfect hash for this group */
505 if (hash_idx == start_hash_idx[i]) {
507 * Restore previous hash_idx and lookup_table
510 for (j = 0; j < i; j++) {
511 on_group->hash_idx[j] = start_hash_idx[j];
512 on_group->lookup_table[j] = start_lookup_table[j];
521 struct rte_efd_table *
522 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
523 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
525 struct rte_efd_table *table = NULL;
526 uint8_t *key_array = NULL;
527 uint32_t num_chunks, num_chunks_shift;
529 struct rte_efd_list *efd_list = NULL;
530 struct rte_tailq_entry *te;
531 uint64_t offline_table_size;
532 char ring_name[RTE_RING_NAMESIZE];
533 struct rte_ring *r = NULL;
536 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
538 if (online_cpu_socket_bitmask == 0) {
539 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
544 if (max_num_rules == 0) {
545 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
550 * Compute the minimum number of chunks (smallest power of 2)
551 * that can hold all of the rules
553 if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
554 num_chunks = rte_align32pow2(max_num_rules /
555 EFD_TARGET_CHUNK_NUM_RULES);
557 num_chunks = rte_align32pow2((max_num_rules /
558 EFD_TARGET_CHUNK_NUM_RULES) + 1);
560 num_chunks_shift = log2(num_chunks);
562 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
565 * Guarantee there's no existing: this is normally already checked
566 * by ring creation above
568 TAILQ_FOREACH(te, efd_list, next)
570 table = (struct rte_efd_table *) te->data;
571 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
579 goto error_unlock_exit;
582 te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
584 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
585 goto error_unlock_exit;
588 /* Create a new EFD table management structure */
589 table = (struct rte_efd_table *) rte_zmalloc_socket(NULL,
590 sizeof(struct rte_efd_table),
594 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
595 " on socket %u failed\n",
597 goto error_unlock_exit;
601 RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
602 "on socket %u\n", offline_cpu_socket);
604 table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
605 table->num_rules = 0;
606 table->num_chunks = num_chunks;
607 table->num_chunks_shift = num_chunks_shift;
608 table->key_len = key_len;
611 key_array = (uint8_t *) rte_zmalloc_socket(NULL,
612 table->max_num_rules * table->key_len,
615 if (key_array == NULL) {
616 RTE_LOG(ERR, EFD, "Allocating key array"
617 " on socket %u failed\n",
619 goto error_unlock_exit;
621 table->keys = key_array;
622 snprintf(table->name, sizeof(table->name), "%s", name);
624 RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
625 " which potentially supports %u entries\n",
626 num_chunks, table->max_num_rules);
628 /* Make sure all the allocatable table pointers are NULL initially */
629 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
630 table->chunks[socket_id] = NULL;
631 table->offline_chunks = NULL;
634 * Allocate one online table per socket specified
635 * in the user-supplied bitmask
637 uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
638 EFD_NUM_CHUNK_PADDING_BYTES;
640 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
641 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
643 * Allocate all of the EFD table chunks (the online portion)
644 * as a continuous block
646 table->chunks[socket_id] =
647 (struct efd_online_chunk *) rte_zmalloc_socket(
652 if (table->chunks[socket_id] == NULL) {
654 "Allocating EFD online table on "
655 "socket %u failed\n",
657 goto error_unlock_exit;
660 "Allocated EFD online table of size "
661 "%"PRIu64" bytes (%.2f MB) on socket %u\n",
663 (float) online_table_size /
669 #if defined(RTE_ARCH_X86)
671 * For less than 4 bits, scalar function performs better
672 * than vectorised version
674 if (RTE_EFD_VALUE_NUM_BITS > 3 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))
675 table->lookup_fn = EFD_LOOKUP_AVX2;
678 table->lookup_fn = EFD_LOOKUP_SCALAR;
681 * Allocate the EFD table offline portion (with the actual rules
682 * mapping keys to values) as a continuous block.
683 * This could be several gigabytes of memory.
685 offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
686 table->offline_chunks =
687 (struct efd_offline_chunk_rules *) rte_zmalloc_socket(NULL,
691 if (table->offline_chunks == NULL) {
692 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
693 "failed\n", offline_cpu_socket);
694 goto error_unlock_exit;
698 "Allocated EFD offline table of size %"PRIu64" bytes "
699 " (%.2f MB) on socket %u\n", offline_table_size,
700 (float) offline_table_size / (1024.0F * 1024.0F),
703 te->data = (void *) table;
704 TAILQ_INSERT_TAIL(efd_list, te, next);
705 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
707 snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
708 /* Create ring (Dummy slot index is not enqueued) */
709 r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
710 offline_cpu_socket, 0);
712 RTE_LOG(ERR, EFD, "memory allocation failed\n");
713 goto error_unlock_exit;
716 /* Populate free slots ring. Entry zero is reserved for key misses. */
717 for (i = 0; i < table->max_num_rules; i++)
718 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
720 table->free_slots = r;
724 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
730 struct rte_efd_table *
731 rte_efd_find_existing(const char *name)
733 struct rte_efd_table *table = NULL;
734 struct rte_tailq_entry *te;
735 struct rte_efd_list *efd_list;
737 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
739 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
741 TAILQ_FOREACH(te, efd_list, next)
743 table = (struct rte_efd_table *) te->data;
744 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
747 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
757 rte_efd_free(struct rte_efd_table *table)
764 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
765 rte_free(table->chunks[socket_id]);
767 rte_ring_free(table->free_slots);
768 rte_free(table->offline_chunks);
769 rte_free(table->keys);
774 * Applies a previously computed table entry to the specified table for all
775 * socket-local copies of the online table.
776 * Intended to apply an update for only a single change
777 * to a key/value pair at a time
780 * EFD table to reference
782 * Socket ID to use to lookup existing values (ideally caller's socket id)
784 * Chunk index to update
786 * Group index to update
788 * Bin within the group that this update affects
789 * @param new_bin_choice
790 * Newly chosen permutation which this bin should use - only lower 2 bits
791 * @param new_group_entry
792 * Previously computed updated chunk/group entry
795 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
796 const uint32_t chunk_id, const uint32_t group_id,
797 const uint32_t bin_id, const uint8_t new_bin_choice,
798 const struct efd_online_group_entry * const new_group_entry)
801 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
802 uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
805 * Grab the current byte that contains the choices
806 * for four neighboring bins
808 uint8_t choice_chunk =
809 chunk->bin_choice_list[bin_index];
812 /* Compute the offset into the chunk that needs to be updated */
813 int offset = (bin_id & 0x3) * 2;
815 /* Zero the two bits of interest and set them to new_bin_choice */
816 choice_chunk = (choice_chunk & (~(0x03 << offset)))
817 | ((new_bin_choice & 0x03) << offset);
819 /* Update the online table with the new data across all sockets */
820 for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
821 if (table->chunks[i] != NULL) {
822 memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
824 sizeof(struct efd_online_group_entry));
825 table->chunks[i][chunk_id].bin_choice_list[bin_index] =
832 * Move the bin from prev group to the new group
835 move_groups(uint32_t bin_id, uint8_t bin_size,
836 struct efd_offline_group_rules *new_group,
837 struct efd_offline_group_rules * const current_group)
840 uint8_t empty_idx = 0;
843 if (new_group == current_group)
846 for (i = 0; i < current_group->num_rules; i++) {
848 * Move keys that belong to the same bin
851 if (current_group->bin_id[i] == bin_id) {
852 new_group->key_idx[new_group->num_rules] =
853 current_group->key_idx[i];
854 new_group->value[new_group->num_rules] =
855 current_group->value[i];
856 new_group->bin_id[new_group->num_rules] =
857 current_group->bin_id[i];
858 new_group->num_rules++;
860 if (i != empty_idx) {
862 * Need to move this key towards
863 * the top of the array
865 current_group->key_idx[empty_idx] =
866 current_group->key_idx[i];
867 current_group->value[empty_idx] =
868 current_group->value[i];
869 current_group->bin_id[empty_idx] =
870 current_group->bin_id[i];
876 current_group->num_rules -= bin_size;
880 * Revert group/s to their previous state before
881 * trying to insert/add a new key
884 revert_groups(struct efd_offline_group_rules *previous_group,
885 struct efd_offline_group_rules *current_group, uint8_t bin_size)
889 if (current_group == previous_group)
892 /* Move keys back to previous group */
893 for (i = current_group->num_rules - bin_size;
894 i < current_group->num_rules; i++) {
895 previous_group->key_idx[previous_group->num_rules] =
896 current_group->key_idx[i];
897 previous_group->value[previous_group->num_rules] =
898 current_group->value[i];
899 previous_group->bin_id[previous_group->num_rules] =
900 current_group->bin_id[i];
901 previous_group->num_rules++;
905 * Decrease number of rules after the move
908 current_group->num_rules -= bin_size;
912 * Computes an updated table entry where the supplied key points to a new host.
913 * If no entry exists, one is inserted.
915 * This function does NOT modify the online table(s)
916 * This function DOES modify the offline table
919 * EFD table to reference
921 * Socket ID to use to lookup existing values (ideally caller's socket id)
925 * Value to associate with key
927 * Chunk ID of the chunk that was modified
929 * Group ID of the group that was modified
931 * Bin ID that was modified
932 * @param new_bin_choice
933 * Newly chosen permutation which this bin will use
935 * Newly computed online entry to apply later with efd_apply_update
938 * RTE_EFD_UPDATE_WARN_GROUP_FULL
939 * Operation is insert, and the last available space in the
940 * key's group was just used. Future inserts may fail as groups fill up.
941 * This operation was still successful, and entry contains a valid update
942 * RTE_EFD_UPDATE_FAILED
943 * Either the EFD failed to find a suitable perfect hash or the group was full
944 * This is a fatal error, and the table is now in an indeterminite state
945 * RTE_EFD_UPDATE_NO_CHANGE
946 * Operation resulted in no change to the table (same value already exists)
948 * Insert or update was successful, and the new efd_online_group_entry
949 * is stored in *entry
952 * Note that entry will be UNCHANGED if the update has no effect, and thus any
953 * subsequent use of the entry content will likely be invalid
956 efd_compute_update(struct rte_efd_table * const table,
957 const unsigned int socket_id, const void *key,
958 const efd_value_t value, uint32_t * const chunk_id,
959 uint32_t * const group_id, uint32_t * const bin_id,
960 uint8_t * const new_bin_choice,
961 struct efd_online_group_entry * const entry)
966 void *new_k, *slot_id = NULL;
967 int status = EXIT_SUCCESS;
968 unsigned int found = 0;
970 efd_compute_ids(table, key, chunk_id, bin_id);
972 struct efd_offline_chunk_rules * const chunk =
973 &table->offline_chunks[*chunk_id];
974 struct efd_offline_group_rules *new_group;
976 uint8_t current_choice = efd_get_choice(table, socket_id,
978 uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
979 struct efd_offline_group_rules * const current_group =
980 &chunk->group_rules[current_group_id];
981 uint8_t bin_size = 0;
982 uint8_t key_changed_index = 0;
983 efd_value_t key_changed_previous_value = 0;
984 uint32_t key_idx_previous = 0;
986 /* Scan the current group and see if the key is already present */
987 for (i = 0; i < current_group->num_rules; i++) {
988 if (current_group->bin_id[i] == *bin_id)
993 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
994 if (found == 0 && unlikely(memcmp(key_stored, key,
995 table->key_len) == 0)) {
996 /* Key is already present */
999 * If previous value is same as new value,
1000 * no additional work is required
1002 if (current_group->value[i] == value)
1003 return RTE_EFD_UPDATE_NO_CHANGE;
1005 key_idx_previous = current_group->key_idx[i];
1006 key_changed_previous_value = current_group->value[i];
1007 key_changed_index = i;
1008 current_group->value[i] = value;
1014 /* Key does not exist. Insert the rule into the bin/group */
1015 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1017 "Fatal: No room remaining for insert into "
1018 "chunk %u group %u bin %u\n",
1020 current_group_id, *bin_id);
1021 return RTE_EFD_UPDATE_FAILED;
1024 if (unlikely(current_group->num_rules ==
1025 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1026 RTE_LOG(INFO, EFD, "Warn: Insert into last "
1027 "available slot in chunk %u "
1028 "group %u bin %u\n", *chunk_id,
1029 current_group_id, *bin_id);
1030 status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1033 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1034 return RTE_EFD_UPDATE_FAILED;
1036 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1038 rte_prefetch0(new_k);
1039 new_idx = (uint32_t) ((uintptr_t) slot_id);
1041 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1042 current_group->key_idx[current_group->num_rules] = new_idx;
1043 current_group->value[current_group->num_rules] = value;
1044 current_group->bin_id[current_group->num_rules] = *bin_id;
1045 current_group->num_rules++;
1049 uint32_t last = current_group->num_rules - 1;
1050 /* Swap the key with the last key inserted*/
1051 current_group->key_idx[key_changed_index] =
1052 current_group->key_idx[last];
1053 current_group->value[key_changed_index] =
1054 current_group->value[last];
1055 current_group->bin_id[key_changed_index] =
1056 current_group->bin_id[last];
1059 * Key to be updated will always be available
1060 * at the end of the group
1062 current_group->key_idx[last] = key_idx_previous;
1063 current_group->value[last] = value;
1064 current_group->bin_id[last] = *bin_id;
1067 *new_bin_choice = current_choice;
1068 *group_id = current_group_id;
1069 new_group = current_group;
1071 /* Group need to be rebalanced when it starts to get loaded */
1072 if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1075 * Subtract the number of entries in the bin from
1076 * the original group
1078 current_group->num_rules -= bin_size;
1081 * Figure out which of the available groups that this bin
1082 * can map to is the smallest (using the current group
1085 uint8_t smallest_choice = current_choice;
1086 uint8_t smallest_size = current_group->num_rules;
1087 uint32_t smallest_group_id = current_group_id;
1088 unsigned char choice;
1090 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1092 uint32_t test_group_id =
1093 efd_bin_to_group[choice][*bin_id];
1094 uint32_t num_rules =
1095 chunk->group_rules[test_group_id].num_rules;
1096 if (num_rules < smallest_size) {
1097 smallest_choice = choice;
1098 smallest_size = num_rules;
1099 smallest_group_id = test_group_id;
1103 *new_bin_choice = smallest_choice;
1104 *group_id = smallest_group_id;
1105 new_group = &chunk->group_rules[smallest_group_id];
1106 current_group->num_rules += bin_size;
1112 if (current_group != new_group &&
1113 new_group->num_rules + bin_size >
1114 EFD_MAX_GROUP_NUM_RULES) {
1116 "Unable to move_groups to dest group "
1117 "containing %u entries."
1118 "bin_size:%u choice:%02x\n",
1119 new_group->num_rules, bin_size,
1123 move_groups(*bin_id, bin_size, new_group, current_group);
1125 * Recompute the hash function for the modified group,
1126 * and return it to the caller
1128 ret = efd_search_hash(table, new_group, entry);
1134 "Failed to find perfect hash for group "
1135 "containing %u entries. bin_size:%u choice:%02x\n",
1136 new_group->num_rules, bin_size, choice - 1);
1137 /* Restore groups modified to their previous state */
1138 revert_groups(current_group, new_group, bin_size);
1141 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1143 *new_bin_choice = choice;
1144 *group_id = efd_bin_to_group[choice][*bin_id];
1145 new_group = &chunk->group_rules[*group_id];
1150 current_group->num_rules--;
1153 current_group->value[current_group->num_rules - 1] =
1154 key_changed_previous_value;
1155 return RTE_EFD_UPDATE_FAILED;
1159 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1160 const void *key, const efd_value_t value)
1162 uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1163 uint8_t new_bin_choice = 0;
1164 struct efd_online_group_entry entry;
1166 int status = efd_compute_update(table, socket_id, key, value,
1167 &chunk_id, &group_id, &bin_id,
1168 &new_bin_choice, &entry);
1170 if (status == RTE_EFD_UPDATE_NO_CHANGE)
1171 return EXIT_SUCCESS;
1173 if (status == RTE_EFD_UPDATE_FAILED)
1176 efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1177 new_bin_choice, &entry);
1182 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1183 const void *key, efd_value_t * const prev_value)
1186 uint32_t chunk_id, bin_id;
1187 uint8_t not_found = 1;
1189 efd_compute_ids(table, key, &chunk_id, &bin_id);
1191 struct efd_offline_chunk_rules * const chunk =
1192 &table->offline_chunks[chunk_id];
1194 uint8_t current_choice = efd_get_choice(table, socket_id,
1196 uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1197 struct efd_offline_group_rules * const current_group =
1198 &chunk->group_rules[current_group_id];
1201 * Search the current group for the specified key.
1202 * If it exists, remove it and re-pack the other values
1204 for (i = 0; i < current_group->num_rules; i++) {
1206 /* Found key that needs to be removed */
1207 if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1208 key, table->key_len) == 0) {
1209 /* Store previous value if requested by caller */
1210 if (prev_value != NULL)
1211 *prev_value = current_group->value[i];
1214 rte_ring_sp_enqueue(table->free_slots,
1215 (void *)((uintptr_t)current_group->key_idx[i]));
1219 * If the desired key has been found,
1220 * need to shift other values up one
1223 /* Need to shift this entry back up one index */
1224 current_group->key_idx[i - 1] = current_group->key_idx[i];
1225 current_group->value[i - 1] = current_group->value[i];
1226 current_group->bin_id[i - 1] = current_group->bin_id[i];
1230 if (not_found == 0) {
1232 current_group->num_rules--;
1238 static inline efd_value_t
1239 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1240 const efd_lookuptbl_t *group_lookup_table,
1241 const uint32_t hash_val_a, const uint32_t hash_val_b)
1243 efd_value_t value = 0;
1246 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1248 uint32_t h = hash_val_a + (hash_val_b *
1249 group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1250 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1251 value |= (group_lookup_table[
1252 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1260 static inline efd_value_t
1261 efd_lookup_internal(const struct efd_online_group_entry * const group,
1262 const uint32_t hash_val_a, const uint32_t hash_val_b,
1263 enum efd_lookup_internal_function lookup_fn)
1265 efd_value_t value = 0;
1267 switch (lookup_fn) {
1269 #if defined(RTE_ARCH_X86)
1270 case EFD_LOOKUP_AVX2:
1271 return efd_lookup_internal_avx2(group->hash_idx,
1272 group->lookup_table,
1276 case EFD_LOOKUP_SCALAR:
1279 return efd_lookup_internal_scalar(group->hash_idx,
1280 group->lookup_table,
1289 rte_efd_lookup(const struct rte_efd_table * const table,
1290 const unsigned int socket_id, const void *key)
1292 uint32_t chunk_id, group_id, bin_id;
1294 const struct efd_online_group_entry *group;
1295 const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1297 /* Determine the chunk and group location for the given key */
1298 efd_compute_ids(table, key, &chunk_id, &bin_id);
1299 bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1300 group_id = efd_bin_to_group[bin_choice][bin_id];
1301 group = &chunks[chunk_id].groups[group_id];
1303 return efd_lookup_internal(group,
1304 EFD_HASHFUNCA(key, table),
1305 EFD_HASHFUNCB(key, table),
1309 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1310 const unsigned int socket_id, const int num_keys,
1311 const void **key_list, efd_value_t * const value_list)
1314 uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1315 uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1316 uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1317 uint32_t group_id_list[RTE_EFD_BURST_MAX];
1318 struct efd_online_group_entry *group;
1320 struct efd_online_chunk *chunks = table->chunks[socket_id];
1322 for (i = 0; i < num_keys; i++) {
1323 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1325 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1328 for (i = 0; i < num_keys; i++) {
1329 bin_choice_list[i] = efd_get_choice(table, socket_id,
1330 chunk_id_list[i], bin_id_list[i]);
1332 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1333 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1334 rte_prefetch0(group);
1337 for (i = 0; i < num_keys; i++) {
1338 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1339 value_list[i] = efd_lookup_internal(group,
1340 EFD_HASHFUNCA(key_list[i], table),
1341 EFD_HASHFUNCB(key_list[i], table),