4 * Copyright(c) 2016-2017 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 #include <sys/queue.h>
42 #include <rte_eal_memconfig.h>
43 #include <rte_errno.h>
44 #include <rte_malloc.h>
45 #include <rte_memzone.h>
46 #include <rte_prefetch.h>
47 #include <rte_branch_prediction.h>
48 #include <rte_memcpy.h>
50 #include <rte_jhash.h>
51 #include <rte_hash_crc.h>
54 #if defined(RTE_ARCH_X86)
55 #include "rte_efd_x86.h"
58 #define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len))
59 /** Hash function used to determine chunk_id and bin_id for a group */
60 #define EFD_HASH(key, table) \
61 (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34))
62 /** Hash function used as constant component of perfect hash search */
63 #define EFD_HASHFUNCA(key, table) \
64 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35))
65 /** Hash function used as multiplicative component of perfect hash search */
66 #define EFD_HASHFUNCB(key, table) \
67 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36))
69 /*************************************************************************
71 *************************************************************************/
73 /* These parameters are fixed by the efd_bin_to_group balancing table */
74 #define EFD_CHUNK_NUM_GROUPS (64)
75 #define EFD_CHUNK_NUM_BINS (256)
76 #define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \
77 (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS)
80 * Target number of rules that each chunk is created to handle.
81 * Used when initially allocating the table
83 #define EFD_TARGET_CHUNK_NUM_RULES \
84 (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)
86 * Max number of rules that each chunk is created to handle.
87 * Used when initially allocating the table
89 #define EFD_TARGET_CHUNK_MAX_NUM_RULES \
90 (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES)
92 /** This is fixed based on the bin_to_group permutation array */
93 #define EFD_MAX_GROUP_NUM_BINS (16)
96 * The end of the chunks array needs some extra padding to ensure
97 * that vectorization over-reads on the last online chunk stay within
100 #define EFD_NUM_CHUNK_PADDING_BYTES (256)
102 /* All different internal lookup functions */
103 enum efd_lookup_internal_function {
104 EFD_LOOKUP_SCALAR = 0,
109 TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
111 static struct rte_tailq_elem rte_efd_tailq = {
114 EAL_REGISTER_TAILQ(rte_efd_tailq);
116 /** Internal permutation array used to shuffle bins into pseudorandom groups */
117 const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
119 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
120 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
121 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
122 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
123 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
124 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
125 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
126 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
127 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
128 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
129 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
130 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
131 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
132 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
133 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
134 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
137 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
138 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
139 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
140 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
141 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
142 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
143 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
144 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
145 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
146 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
147 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
148 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
149 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
150 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
151 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
152 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
155 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
156 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
157 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
158 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
159 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
160 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
161 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
162 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
163 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
164 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
165 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
166 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
167 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
168 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
169 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
170 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
173 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
174 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
175 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
176 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
177 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
178 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
179 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
180 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
181 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
182 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
183 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
184 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
185 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
186 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
187 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
188 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
192 /*************************************************************************
193 * Offline region structures
194 *************************************************************************/
196 /** Online group containing number of rules, values, keys and their bins
197 * for EFD_MAX_GROUP_NUM_RULES rules.
199 struct efd_offline_group_rules {
201 /**< Sum of the number of rules in all bins assigned to this group. */
203 uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
204 /**< Array with all keys of the group. */
205 efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
206 /**< Array with all values of the keys of the group. */
208 uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
209 /**< Stores the bin for each correspending key to
210 * avoid having to recompute it
214 /** Offline 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_offline_chunk_rules {
219 /**< Number of rules in the entire chunk;
220 * used to detect unbalanced groups
223 struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
224 /**< Array of all groups in the chunk. */
227 /*************************************************************************
228 * Online region structures
229 *************************************************************************/
231 /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */
232 struct efd_online_group_entry {
233 efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
234 efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
235 } __attribute__((__packed__));
238 * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
239 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
241 struct efd_online_chunk {
242 uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
243 /**< This is a packed indirection index into the 'groups' array.
244 * Each byte contains four two-bit values which index into
245 * the efd_bin_to_group array.
246 * The efd_bin_to_group array returns the index into the groups array
249 struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
250 /**< Array of all the groups in the chunk. */
251 } __attribute__((__packed__));
254 * EFD table structure
256 struct rte_efd_table {
257 char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */
259 uint32_t key_len; /**< Length of the key stored offline */
261 uint32_t max_num_rules;
262 /**< Static maximum number of entries the table was constructed to hold. */
265 /**< Number of entries currently in the table . */
268 /**< Number of chunks in the table needed to support num_rules. */
270 uint32_t num_chunks_shift;
271 /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */
273 enum efd_lookup_internal_function lookup_fn;
274 /**< Indicates which lookup function to use. */
276 struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
277 /**< Dynamic array of size num_chunks of chunk records. */
279 struct efd_offline_chunk_rules *offline_chunks;
280 /**< Dynamic array of size num_chunks of key-value pairs. */
282 struct rte_ring *free_slots;
283 /**< Ring that stores all indexes of the free slots in the key table */
285 uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */
289 * Computes the chunk ID for a given key hash
292 * EFD table to reference
294 * 32-bit key hash returned by EFD_HASH
297 * chunk ID containing this key hash
299 static inline uint32_t
300 efd_get_chunk_id(const struct rte_efd_table * const table,
301 const uint32_t hashed_key)
303 return hashed_key & (table->num_chunks - 1);
307 * Computes the bin ID for a given key hash
310 * EFD table to reference
312 * 32-bit key hash returned by EFD_HASH
314 * @return bin ID containing this key hash
316 static inline uint32_t
317 efd_get_bin_id(const struct rte_efd_table * const table,
318 const uint32_t hashed_key)
320 return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
324 * Looks up the current permutation choice for a particular bin in the online table
327 * EFD table to reference
329 * Socket ID to use to look up existing values (ideally caller's socket id)
331 * Chunk ID of bin to look up
336 * Currently active permutation choice in the online table
338 static inline uint8_t
339 efd_get_choice(const struct rte_efd_table * const table,
340 const unsigned int socket_id, const uint32_t chunk_id,
341 const uint32_t bin_id)
343 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
346 * Grab the chunk (byte) that contains the choices
347 * for four neighboring bins.
349 uint8_t choice_chunk =
350 chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
353 * Compute the offset into the chunk that contains
354 * the group_id lookup position
356 int offset = (bin_id & 0x3) * 2;
358 /* Extract from the byte just the desired lookup position */
359 return (uint8_t) ((choice_chunk >> offset) & 0x3);
363 * Compute the chunk_id and bin_id for a given key
366 * EFD table to reference
368 * Key to hash and find location of
376 efd_compute_ids(const struct rte_efd_table * const table,
377 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
379 /* Compute the position of the entry in the hash table */
380 uint32_t h = EFD_HASH(key, table);
382 /* Compute the chunk_id where that entry can be found */
383 *chunk_id = efd_get_chunk_id(table, h);
386 * Compute the bin within that chunk where the entry
387 * can be found (0 - 255)
389 *bin_id = efd_get_bin_id(table, h);
393 * Search for a hash function for a group that satisfies all group results
396 efd_search_hash(struct rte_efd_table * const table,
397 const struct efd_offline_group_rules * const off_group,
398 struct efd_online_group_entry * const on_group)
400 efd_hashfunc_t hash_idx;
401 efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
402 efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
404 uint32_t i, j, rule_id;
405 uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
406 uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
407 uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
410 rte_prefetch0(off_group->value);
413 * Prepopulate the hash_val tables by running the two hash functions
414 * for each provided rule
416 for (i = 0; i < off_group->num_rules; i++) {
417 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
418 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
419 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
422 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
423 hash_idx = on_group->hash_idx[i];
424 start_hash_idx[i] = hash_idx;
425 start_lookup_table[i] = on_group->lookup_table[i];
428 efd_lookuptbl_t lookup_table = 0;
429 efd_lookuptbl_t lookup_table_complement = 0;
431 for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
432 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
433 hash_val_b[rule_id]);
436 * The goal here is to find a hash function for this
437 * particular bit entry that meets the following criteria:
438 * The most significant bits of the hash result define a
439 * shift into the lookup table where the bit will be stored
442 /* Iterate over each provided rule */
443 for (rule_id = 0; rule_id < off_group->num_rules;
446 * Use the few most significant bits (number based on
447 * EFD_LOOKUPTBL_SIZE) to see what position the
448 * expected bit should be set in the lookup_table
450 uint32_t bucket_idx = hash_val[rule_id] >>
454 * Get the current bit of interest.
455 * This only find an appropriate hash function
456 * for one bit at a time of the rule
458 efd_lookuptbl_t expected =
459 (off_group->value[rule_id] >> i) & 0x1;
462 * Add the expected bit (if set) to a map
463 * (lookup_table). Also set its complement
464 * in lookup_table_complement
466 lookup_table |= expected << bucket_idx;
467 lookup_table_complement |= (1 - expected)
471 * If ever the hash function of two different
472 * elements result in different values at the
473 * same location in the lookup_table,
474 * the current hash_idx is not valid.
476 if (lookup_table & lookup_table_complement)
481 * Check if the previous loop completed without
484 if (rule_id == off_group->num_rules) {
486 * Current hash function worked, store it
487 * for the current group
489 on_group->hash_idx[i] = hash_idx;
490 on_group->lookup_table[i] = lookup_table;
493 * Make sure that the hash function has changed
494 * from the starting value
496 hash_idx = start_hash_idx[i] + 1;
501 } while (hash_idx != start_hash_idx[i]);
503 /* Failed to find perfect hash for this group */
504 if (hash_idx == start_hash_idx[i]) {
506 * Restore previous hash_idx and lookup_table
509 for (j = 0; j < i; j++) {
510 on_group->hash_idx[j] = start_hash_idx[j];
511 on_group->lookup_table[j] = start_lookup_table[j];
520 struct rte_efd_table *
521 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
522 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
524 struct rte_efd_table *table = NULL;
525 uint8_t *key_array = NULL;
526 uint32_t num_chunks, num_chunks_shift;
528 struct rte_efd_list *efd_list = NULL;
529 struct rte_tailq_entry *te;
530 uint64_t offline_table_size;
531 char ring_name[RTE_RING_NAMESIZE];
532 struct rte_ring *r = NULL;
535 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
537 if (online_cpu_socket_bitmask == 0) {
538 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
543 if (max_num_rules == 0) {
544 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
549 * Compute the minimum number of chunks (smallest power of 2)
550 * that can hold all of the rules
552 if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
553 num_chunks = rte_align32pow2(max_num_rules /
554 EFD_TARGET_CHUNK_NUM_RULES);
556 num_chunks = rte_align32pow2((max_num_rules /
557 EFD_TARGET_CHUNK_NUM_RULES) + 1);
559 num_chunks_shift = rte_bsf32(num_chunks);
561 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
564 * Guarantee there's no existing: this is normally already checked
565 * by ring creation above
567 TAILQ_FOREACH(te, efd_list, next)
569 table = (struct rte_efd_table *) te->data;
570 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
578 goto error_unlock_exit;
581 te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
583 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
584 goto error_unlock_exit;
587 /* Create a new EFD table management structure */
588 table = (struct rte_efd_table *) rte_zmalloc_socket(NULL,
589 sizeof(struct rte_efd_table),
593 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
594 " on socket %u failed\n",
596 goto error_unlock_exit;
600 RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
601 "on socket %u\n", offline_cpu_socket);
603 table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
604 table->num_rules = 0;
605 table->num_chunks = num_chunks;
606 table->num_chunks_shift = num_chunks_shift;
607 table->key_len = key_len;
610 key_array = (uint8_t *) rte_zmalloc_socket(NULL,
611 table->max_num_rules * table->key_len,
614 if (key_array == NULL) {
615 RTE_LOG(ERR, EFD, "Allocating key array"
616 " on socket %u failed\n",
618 goto error_unlock_exit;
620 table->keys = key_array;
621 snprintf(table->name, sizeof(table->name), "%s", name);
623 RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
624 " which potentially supports %u entries\n",
625 num_chunks, table->max_num_rules);
627 /* Make sure all the allocatable table pointers are NULL initially */
628 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
629 table->chunks[socket_id] = NULL;
630 table->offline_chunks = NULL;
633 * Allocate one online table per socket specified
634 * in the user-supplied bitmask
636 uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
637 EFD_NUM_CHUNK_PADDING_BYTES;
639 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
640 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
642 * Allocate all of the EFD table chunks (the online portion)
643 * as a continuous block
645 table->chunks[socket_id] =
646 (struct efd_online_chunk *) rte_zmalloc_socket(
651 if (table->chunks[socket_id] == NULL) {
653 "Allocating EFD online table on "
654 "socket %u failed\n",
656 goto error_unlock_exit;
659 "Allocated EFD online table of size "
660 "%"PRIu64" bytes (%.2f MB) on socket %u\n",
662 (float) online_table_size /
668 #if defined(RTE_ARCH_X86)
670 * For less than 4 bits, scalar function performs better
671 * than vectorised version
673 if (RTE_EFD_VALUE_NUM_BITS > 3 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))
674 table->lookup_fn = EFD_LOOKUP_AVX2;
677 table->lookup_fn = EFD_LOOKUP_SCALAR;
680 * Allocate the EFD table offline portion (with the actual rules
681 * mapping keys to values) as a continuous block.
682 * This could be several gigabytes of memory.
684 offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
685 table->offline_chunks =
686 (struct efd_offline_chunk_rules *) rte_zmalloc_socket(NULL,
690 if (table->offline_chunks == NULL) {
691 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
692 "failed\n", offline_cpu_socket);
693 goto error_unlock_exit;
697 "Allocated EFD offline table of size %"PRIu64" bytes "
698 " (%.2f MB) on socket %u\n", offline_table_size,
699 (float) offline_table_size / (1024.0F * 1024.0F),
702 te->data = (void *) table;
703 TAILQ_INSERT_TAIL(efd_list, te, next);
704 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
706 snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
707 /* Create ring (Dummy slot index is not enqueued) */
708 r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
709 offline_cpu_socket, 0);
711 RTE_LOG(ERR, EFD, "memory allocation failed\n");
712 goto error_unlock_exit;
715 /* Populate free slots ring. Entry zero is reserved for key misses. */
716 for (i = 0; i < table->max_num_rules; i++)
717 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
719 table->free_slots = r;
723 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
729 struct rte_efd_table *
730 rte_efd_find_existing(const char *name)
732 struct rte_efd_table *table = NULL;
733 struct rte_tailq_entry *te;
734 struct rte_efd_list *efd_list;
736 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
738 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
740 TAILQ_FOREACH(te, efd_list, next)
742 table = (struct rte_efd_table *) te->data;
743 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
746 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
756 rte_efd_free(struct rte_efd_table *table)
763 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
764 rte_free(table->chunks[socket_id]);
766 rte_ring_free(table->free_slots);
767 rte_free(table->offline_chunks);
768 rte_free(table->keys);
773 * Applies a previously computed table entry to the specified table for all
774 * socket-local copies of the online table.
775 * Intended to apply an update for only a single change
776 * to a key/value pair at a time
779 * EFD table to reference
781 * Socket ID to use to lookup existing values (ideally caller's socket id)
783 * Chunk index to update
785 * Group index to update
787 * Bin within the group that this update affects
788 * @param new_bin_choice
789 * Newly chosen permutation which this bin should use - only lower 2 bits
790 * @param new_group_entry
791 * Previously computed updated chunk/group entry
794 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
795 const uint32_t chunk_id, const uint32_t group_id,
796 const uint32_t bin_id, const uint8_t new_bin_choice,
797 const struct efd_online_group_entry * const new_group_entry)
800 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
801 uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
804 * Grab the current byte that contains the choices
805 * for four neighboring bins
807 uint8_t choice_chunk =
808 chunk->bin_choice_list[bin_index];
811 /* Compute the offset into the chunk that needs to be updated */
812 int offset = (bin_id & 0x3) * 2;
814 /* Zero the two bits of interest and set them to new_bin_choice */
815 choice_chunk = (choice_chunk & (~(0x03 << offset)))
816 | ((new_bin_choice & 0x03) << offset);
818 /* Update the online table with the new data across all sockets */
819 for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
820 if (table->chunks[i] != NULL) {
821 memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
823 sizeof(struct efd_online_group_entry));
824 table->chunks[i][chunk_id].bin_choice_list[bin_index] =
831 * Move the bin from prev group to the new group
834 move_groups(uint32_t bin_id, uint8_t bin_size,
835 struct efd_offline_group_rules *new_group,
836 struct efd_offline_group_rules * const current_group)
839 uint8_t empty_idx = 0;
842 if (new_group == current_group)
845 for (i = 0; i < current_group->num_rules; i++) {
847 * Move keys that belong to the same bin
850 if (current_group->bin_id[i] == bin_id) {
851 new_group->key_idx[new_group->num_rules] =
852 current_group->key_idx[i];
853 new_group->value[new_group->num_rules] =
854 current_group->value[i];
855 new_group->bin_id[new_group->num_rules] =
856 current_group->bin_id[i];
857 new_group->num_rules++;
859 if (i != empty_idx) {
861 * Need to move this key towards
862 * the top of the array
864 current_group->key_idx[empty_idx] =
865 current_group->key_idx[i];
866 current_group->value[empty_idx] =
867 current_group->value[i];
868 current_group->bin_id[empty_idx] =
869 current_group->bin_id[i];
875 current_group->num_rules -= bin_size;
879 * Revert group/s to their previous state before
880 * trying to insert/add a new key
883 revert_groups(struct efd_offline_group_rules *previous_group,
884 struct efd_offline_group_rules *current_group, uint8_t bin_size)
888 if (current_group == previous_group)
891 /* Move keys back to previous group */
892 for (i = current_group->num_rules - bin_size;
893 i < current_group->num_rules; i++) {
894 previous_group->key_idx[previous_group->num_rules] =
895 current_group->key_idx[i];
896 previous_group->value[previous_group->num_rules] =
897 current_group->value[i];
898 previous_group->bin_id[previous_group->num_rules] =
899 current_group->bin_id[i];
900 previous_group->num_rules++;
904 * Decrease number of rules after the move
907 current_group->num_rules -= bin_size;
911 * Computes an updated table entry where the supplied key points to a new host.
912 * If no entry exists, one is inserted.
914 * This function does NOT modify the online table(s)
915 * This function DOES modify the offline table
918 * EFD table to reference
920 * Socket ID to use to lookup existing values (ideally caller's socket id)
924 * Value to associate with key
926 * Chunk ID of the chunk that was modified
928 * Group ID of the group that was modified
930 * Bin ID that was modified
931 * @param new_bin_choice
932 * Newly chosen permutation which this bin will use
934 * Newly computed online entry to apply later with efd_apply_update
937 * RTE_EFD_UPDATE_WARN_GROUP_FULL
938 * Operation is insert, and the last available space in the
939 * key's group was just used. Future inserts may fail as groups fill up.
940 * This operation was still successful, and entry contains a valid update
941 * RTE_EFD_UPDATE_FAILED
942 * Either the EFD failed to find a suitable perfect hash or the group was full
943 * This is a fatal error, and the table is now in an indeterminite state
944 * RTE_EFD_UPDATE_NO_CHANGE
945 * Operation resulted in no change to the table (same value already exists)
947 * Insert or update was successful, and the new efd_online_group_entry
948 * is stored in *entry
951 * Note that entry will be UNCHANGED if the update has no effect, and thus any
952 * subsequent use of the entry content will likely be invalid
955 efd_compute_update(struct rte_efd_table * const table,
956 const unsigned int socket_id, const void *key,
957 const efd_value_t value, uint32_t * const chunk_id,
958 uint32_t * const group_id, uint32_t * const bin_id,
959 uint8_t * const new_bin_choice,
960 struct efd_online_group_entry * const entry)
965 void *new_k, *slot_id = NULL;
966 int status = EXIT_SUCCESS;
967 unsigned int found = 0;
969 efd_compute_ids(table, key, chunk_id, bin_id);
971 struct efd_offline_chunk_rules * const chunk =
972 &table->offline_chunks[*chunk_id];
973 struct efd_offline_group_rules *new_group;
975 uint8_t current_choice = efd_get_choice(table, socket_id,
977 uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
978 struct efd_offline_group_rules * const current_group =
979 &chunk->group_rules[current_group_id];
980 uint8_t bin_size = 0;
981 uint8_t key_changed_index = 0;
982 efd_value_t key_changed_previous_value = 0;
983 uint32_t key_idx_previous = 0;
985 /* Scan the current group and see if the key is already present */
986 for (i = 0; i < current_group->num_rules; i++) {
987 if (current_group->bin_id[i] == *bin_id)
992 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
993 if (found == 0 && unlikely(memcmp(key_stored, key,
994 table->key_len) == 0)) {
995 /* Key is already present */
998 * If previous value is same as new value,
999 * no additional work is required
1001 if (current_group->value[i] == value)
1002 return RTE_EFD_UPDATE_NO_CHANGE;
1004 key_idx_previous = current_group->key_idx[i];
1005 key_changed_previous_value = current_group->value[i];
1006 key_changed_index = i;
1007 current_group->value[i] = value;
1013 /* Key does not exist. Insert the rule into the bin/group */
1014 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1016 "Fatal: No room remaining for insert into "
1017 "chunk %u group %u bin %u\n",
1019 current_group_id, *bin_id);
1020 return RTE_EFD_UPDATE_FAILED;
1023 if (unlikely(current_group->num_rules ==
1024 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1025 RTE_LOG(INFO, EFD, "Warn: Insert into last "
1026 "available slot in chunk %u "
1027 "group %u bin %u\n", *chunk_id,
1028 current_group_id, *bin_id);
1029 status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1032 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1033 return RTE_EFD_UPDATE_FAILED;
1035 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1037 rte_prefetch0(new_k);
1038 new_idx = (uint32_t) ((uintptr_t) slot_id);
1040 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1041 current_group->key_idx[current_group->num_rules] = new_idx;
1042 current_group->value[current_group->num_rules] = value;
1043 current_group->bin_id[current_group->num_rules] = *bin_id;
1044 current_group->num_rules++;
1048 uint32_t last = current_group->num_rules - 1;
1049 /* Swap the key with the last key inserted*/
1050 current_group->key_idx[key_changed_index] =
1051 current_group->key_idx[last];
1052 current_group->value[key_changed_index] =
1053 current_group->value[last];
1054 current_group->bin_id[key_changed_index] =
1055 current_group->bin_id[last];
1058 * Key to be updated will always be available
1059 * at the end of the group
1061 current_group->key_idx[last] = key_idx_previous;
1062 current_group->value[last] = value;
1063 current_group->bin_id[last] = *bin_id;
1066 *new_bin_choice = current_choice;
1067 *group_id = current_group_id;
1068 new_group = current_group;
1070 /* Group need to be rebalanced when it starts to get loaded */
1071 if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1074 * Subtract the number of entries in the bin from
1075 * the original group
1077 current_group->num_rules -= bin_size;
1080 * Figure out which of the available groups that this bin
1081 * can map to is the smallest (using the current group
1084 uint8_t smallest_choice = current_choice;
1085 uint8_t smallest_size = current_group->num_rules;
1086 uint32_t smallest_group_id = current_group_id;
1087 unsigned char choice;
1089 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1091 uint32_t test_group_id =
1092 efd_bin_to_group[choice][*bin_id];
1093 uint32_t num_rules =
1094 chunk->group_rules[test_group_id].num_rules;
1095 if (num_rules < smallest_size) {
1096 smallest_choice = choice;
1097 smallest_size = num_rules;
1098 smallest_group_id = test_group_id;
1102 *new_bin_choice = smallest_choice;
1103 *group_id = smallest_group_id;
1104 new_group = &chunk->group_rules[smallest_group_id];
1105 current_group->num_rules += bin_size;
1111 if (current_group != new_group &&
1112 new_group->num_rules + bin_size >
1113 EFD_MAX_GROUP_NUM_RULES) {
1115 "Unable to move_groups to dest group "
1116 "containing %u entries."
1117 "bin_size:%u choice:%02x\n",
1118 new_group->num_rules, bin_size,
1122 move_groups(*bin_id, bin_size, new_group, current_group);
1124 * Recompute the hash function for the modified group,
1125 * and return it to the caller
1127 ret = efd_search_hash(table, new_group, entry);
1133 "Failed to find perfect hash for group "
1134 "containing %u entries. bin_size:%u choice:%02x\n",
1135 new_group->num_rules, bin_size, choice - 1);
1136 /* Restore groups modified to their previous state */
1137 revert_groups(current_group, new_group, bin_size);
1140 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1142 *new_bin_choice = choice;
1143 *group_id = efd_bin_to_group[choice][*bin_id];
1144 new_group = &chunk->group_rules[*group_id];
1149 current_group->num_rules--;
1152 current_group->value[current_group->num_rules - 1] =
1153 key_changed_previous_value;
1154 return RTE_EFD_UPDATE_FAILED;
1158 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1159 const void *key, const efd_value_t value)
1161 uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1162 uint8_t new_bin_choice = 0;
1163 struct efd_online_group_entry entry;
1165 int status = efd_compute_update(table, socket_id, key, value,
1166 &chunk_id, &group_id, &bin_id,
1167 &new_bin_choice, &entry);
1169 if (status == RTE_EFD_UPDATE_NO_CHANGE)
1170 return EXIT_SUCCESS;
1172 if (status == RTE_EFD_UPDATE_FAILED)
1175 efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1176 new_bin_choice, &entry);
1181 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1182 const void *key, efd_value_t * const prev_value)
1185 uint32_t chunk_id, bin_id;
1186 uint8_t not_found = 1;
1188 efd_compute_ids(table, key, &chunk_id, &bin_id);
1190 struct efd_offline_chunk_rules * const chunk =
1191 &table->offline_chunks[chunk_id];
1193 uint8_t current_choice = efd_get_choice(table, socket_id,
1195 uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1196 struct efd_offline_group_rules * const current_group =
1197 &chunk->group_rules[current_group_id];
1200 * Search the current group for the specified key.
1201 * If it exists, remove it and re-pack the other values
1203 for (i = 0; i < current_group->num_rules; i++) {
1205 /* Found key that needs to be removed */
1206 if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1207 key, table->key_len) == 0) {
1208 /* Store previous value if requested by caller */
1209 if (prev_value != NULL)
1210 *prev_value = current_group->value[i];
1213 rte_ring_sp_enqueue(table->free_slots,
1214 (void *)((uintptr_t)current_group->key_idx[i]));
1218 * If the desired key has been found,
1219 * need to shift other values up one
1222 /* Need to shift this entry back up one index */
1223 current_group->key_idx[i - 1] = current_group->key_idx[i];
1224 current_group->value[i - 1] = current_group->value[i];
1225 current_group->bin_id[i - 1] = current_group->bin_id[i];
1229 if (not_found == 0) {
1231 current_group->num_rules--;
1237 static inline efd_value_t
1238 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1239 const efd_lookuptbl_t *group_lookup_table,
1240 const uint32_t hash_val_a, const uint32_t hash_val_b)
1242 efd_value_t value = 0;
1245 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1247 uint32_t h = hash_val_a + (hash_val_b *
1248 group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1249 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1250 value |= (group_lookup_table[
1251 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1259 static inline efd_value_t
1260 efd_lookup_internal(const struct efd_online_group_entry * const group,
1261 const uint32_t hash_val_a, const uint32_t hash_val_b,
1262 enum efd_lookup_internal_function lookup_fn)
1264 efd_value_t value = 0;
1266 switch (lookup_fn) {
1268 #if defined(RTE_ARCH_X86)
1269 case EFD_LOOKUP_AVX2:
1270 return efd_lookup_internal_avx2(group->hash_idx,
1271 group->lookup_table,
1275 case EFD_LOOKUP_SCALAR:
1278 return efd_lookup_internal_scalar(group->hash_idx,
1279 group->lookup_table,
1288 rte_efd_lookup(const struct rte_efd_table * const table,
1289 const unsigned int socket_id, const void *key)
1291 uint32_t chunk_id, group_id, bin_id;
1293 const struct efd_online_group_entry *group;
1294 const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1296 /* Determine the chunk and group location for the given key */
1297 efd_compute_ids(table, key, &chunk_id, &bin_id);
1298 bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1299 group_id = efd_bin_to_group[bin_choice][bin_id];
1300 group = &chunks[chunk_id].groups[group_id];
1302 return efd_lookup_internal(group,
1303 EFD_HASHFUNCA(key, table),
1304 EFD_HASHFUNCB(key, table),
1308 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1309 const unsigned int socket_id, const int num_keys,
1310 const void **key_list, efd_value_t * const value_list)
1313 uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1314 uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1315 uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1316 uint32_t group_id_list[RTE_EFD_BURST_MAX];
1317 struct efd_online_group_entry *group;
1319 struct efd_online_chunk *chunks = table->chunks[socket_id];
1321 for (i = 0; i < num_keys; i++) {
1322 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1324 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1327 for (i = 0; i < num_keys; i++) {
1328 bin_choice_list[i] = efd_get_choice(table, socket_id,
1329 chunk_id_list[i], bin_id_list[i]);
1331 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1332 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1333 rte_prefetch0(group);
1336 for (i = 0; i < num_keys; i++) {
1337 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1338 value_list[i] = efd_lookup_internal(group,
1339 EFD_HASHFUNCA(key_list[i], table),
1340 EFD_HASHFUNCB(key_list[i], table),