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>
56 #define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len))
57 /** Hash function used to determine chunk_id and bin_id for a group */
58 #define EFD_HASH(key, table) \
59 (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34))
60 /** Hash function used as constant component of perfect hash search */
61 #define EFD_HASHFUNCA(key, table) \
62 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35))
63 /** Hash function used as multiplicative component of perfect hash search */
64 #define EFD_HASHFUNCB(key, table) \
65 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36))
67 /*************************************************************************
69 *************************************************************************/
71 /* These parameters are fixed by the efd_bin_to_group balancing table */
72 #define EFD_CHUNK_NUM_GROUPS (64)
73 #define EFD_CHUNK_NUM_BINS (256)
74 #define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \
75 (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS)
78 * Target number of rules that each chunk is created to handle.
79 * Used when initially allocating the table
81 #define EFD_TARGET_CHUNK_NUM_RULES \
82 (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)
84 * Max number of rules that each chunk is created to handle.
85 * Used when initially allocating the table
87 #define EFD_TARGET_CHUNK_MAX_NUM_RULES \
88 (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES)
90 /** This is fixed based on the bin_to_group permutation array */
91 #define EFD_MAX_GROUP_NUM_BINS (16)
94 * The end of the chunks array needs some extra padding to ensure
95 * that vectorization over-reads on the last online chunk stay within
98 #define EFD_NUM_CHUNK_PADDING_BYTES (256)
100 /* All different internal lookup functions */
101 enum efd_lookup_internal_function {
102 EFD_LOOKUP_SCALAR = 0,
106 TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
108 static struct rte_tailq_elem rte_efd_tailq = {
111 EAL_REGISTER_TAILQ(rte_efd_tailq);
113 /** Internal permutation array used to shuffle bins into pseudorandom groups */
114 const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
116 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
117 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
118 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
119 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
120 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
121 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
122 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
123 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
124 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
125 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
126 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
127 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
128 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
129 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
130 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
131 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
134 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
135 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
136 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
137 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
138 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
139 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
140 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
141 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
142 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
143 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
144 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
145 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
146 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
147 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
148 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
149 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
152 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
153 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
154 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
155 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
156 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
157 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
158 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
159 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
160 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
161 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
162 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
163 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
164 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
165 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
166 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
167 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
170 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
171 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
172 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
173 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
174 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
175 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
176 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
177 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
178 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
179 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
180 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
181 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
182 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
183 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
184 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
185 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
189 /*************************************************************************
190 * Offline region structures
191 *************************************************************************/
193 /** Online group containing number of rules, values, keys and their bins
194 * for EFD_MAX_GROUP_NUM_RULES rules.
196 struct efd_offline_group_rules {
198 /**< Sum of the number of rules in all bins assigned to this group. */
200 uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
201 /**< Array with all keys of the group. */
202 efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
203 /**< Array with all values of the keys of the group. */
205 uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
206 /**< Stores the bin for each correspending key to
207 * avoid having to recompute it
211 /** Offline chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
212 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
214 struct efd_offline_chunk_rules {
216 /**< Number of rules in the entire chunk;
217 * used to detect unbalanced groups
220 struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
221 /**< Array of all groups in the chunk. */
224 /*************************************************************************
225 * Online region structures
226 *************************************************************************/
228 /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */
229 struct efd_online_group_entry {
230 efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
231 efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
232 } __attribute__((__packed__));
235 * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
236 * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
238 struct efd_online_chunk {
239 uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
240 /**< This is a packed indirection index into the 'groups' array.
241 * Each byte contains four two-bit values which index into
242 * the efd_bin_to_group array.
243 * The efd_bin_to_group array returns the index into the groups array
246 struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
247 /**< Array of all the groups in the chunk. */
248 } __attribute__((__packed__));
251 * EFD table structure
253 struct rte_efd_table {
254 char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */
256 uint32_t key_len; /**< Length of the key stored offline */
258 uint32_t max_num_rules;
259 /**< Static maximum number of entries the table was constructed to hold. */
262 /**< Number of entries currently in the table . */
265 /**< Number of chunks in the table needed to support num_rules. */
267 uint32_t num_chunks_shift;
268 /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */
270 enum efd_lookup_internal_function lookup_fn;
271 /**< Indicates which lookup function to use. */
273 struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
274 /**< Dynamic array of size num_chunks of chunk records. */
276 struct efd_offline_chunk_rules *offline_chunks;
277 /**< Dynamic array of size num_chunks of key-value pairs. */
279 struct rte_ring *free_slots;
280 /**< Ring that stores all indexes of the free slots in the key table */
282 uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */
286 * Computes the chunk ID for a given key hash
289 * EFD table to reference
291 * 32-bit key hash returned by EFD_HASH
294 * chunk ID containing this key hash
296 static inline uint32_t
297 efd_get_chunk_id(const struct rte_efd_table * const table,
298 const uint32_t hashed_key)
300 return hashed_key & (table->num_chunks - 1);
304 * Computes the bin ID for a given key hash
307 * EFD table to reference
309 * 32-bit key hash returned by EFD_HASH
311 * @return bin ID containing this key hash
313 static inline uint32_t
314 efd_get_bin_id(const struct rte_efd_table * const table,
315 const uint32_t hashed_key)
317 return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
321 * Looks up the current permutation choice for a particular bin in the online table
324 * EFD table to reference
326 * Socket ID to use to look up existing values (ideally caller's socket id)
328 * Chunk ID of bin to look up
333 * Currently active permutation choice in the online table
335 static inline uint8_t
336 efd_get_choice(const struct rte_efd_table * const table,
337 const unsigned int socket_id, const uint32_t chunk_id,
338 const uint32_t bin_id)
340 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
343 * Grab the chunk (byte) that contains the choices
344 * for four neighboring bins.
346 uint8_t choice_chunk =
347 chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
350 * Compute the offset into the chunk that contains
351 * the group_id lookup position
353 int offset = (bin_id & 0x3) * 2;
355 /* Extract from the byte just the desired lookup position */
356 return (uint8_t) ((choice_chunk >> offset) & 0x3);
360 * Compute the chunk_id and bin_id for a given key
363 * EFD table to reference
365 * Key to hash and find location of
373 efd_compute_ids(const struct rte_efd_table * const table,
374 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
376 /* Compute the position of the entry in the hash table */
377 uint32_t h = EFD_HASH(key, table);
379 /* Compute the chunk_id where that entry can be found */
380 *chunk_id = efd_get_chunk_id(table, h);
383 * Compute the bin within that chunk where the entry
384 * can be found (0 - 255)
386 *bin_id = efd_get_bin_id(table, h);
390 * Search for a hash function for a group that satisfies all group results
393 efd_search_hash(struct rte_efd_table * const table,
394 const struct efd_offline_group_rules * const off_group,
395 struct efd_online_group_entry * const on_group)
397 efd_hashfunc_t hash_idx;
398 efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
399 efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
401 uint32_t i, j, rule_id;
402 uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
403 uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
404 uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
407 rte_prefetch0(off_group->value);
410 * Prepopulate the hash_val tables by running the two hash functions
411 * for each provided rule
413 for (i = 0; i < off_group->num_rules; i++) {
414 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
415 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
416 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
419 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
420 hash_idx = on_group->hash_idx[i];
421 start_hash_idx[i] = hash_idx;
422 start_lookup_table[i] = on_group->lookup_table[i];
425 efd_lookuptbl_t lookup_table = 0;
426 efd_lookuptbl_t lookup_table_complement = 0;
428 for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
429 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
430 hash_val_b[rule_id]);
433 * The goal here is to find a hash function for this
434 * particular bit entry that meets the following criteria:
435 * The most significant bits of the hash result define a
436 * shift into the lookup table where the bit will be stored
439 /* Iterate over each provided rule */
440 for (rule_id = 0; rule_id < off_group->num_rules;
443 * Use the few most significant bits (number based on
444 * EFD_LOOKUPTBL_SIZE) to see what position the
445 * expected bit should be set in the lookup_table
447 uint32_t bucket_idx = hash_val[rule_id] >>
451 * Get the current bit of interest.
452 * This only find an appropriate hash function
453 * for one bit at a time of the rule
455 efd_lookuptbl_t expected =
456 (off_group->value[rule_id] >> i) & 0x1;
459 * Add the expected bit (if set) to a map
460 * (lookup_table). Also set its complement
461 * in lookup_table_complement
463 lookup_table |= expected << bucket_idx;
464 lookup_table_complement |= (1 - expected)
468 * If ever the hash function of two different
469 * elements result in different values at the
470 * same location in the lookup_table,
471 * the current hash_idx is not valid.
473 if (lookup_table & lookup_table_complement)
478 * Check if the previous loop completed without
481 if (rule_id == off_group->num_rules) {
483 * Current hash function worked, store it
484 * for the current group
486 on_group->hash_idx[i] = hash_idx;
487 on_group->lookup_table[i] = lookup_table;
490 * Make sure that the hash function has changed
491 * from the starting value
493 hash_idx = start_hash_idx[i] + 1;
498 } while (hash_idx != start_hash_idx[i]);
500 /* Failed to find perfect hash for this group */
501 if (hash_idx == start_hash_idx[i]) {
503 * Restore previous hash_idx and lookup_table
506 for (j = 0; j < i; j++) {
507 on_group->hash_idx[j] = start_hash_idx[j];
508 on_group->lookup_table[j] = start_lookup_table[j];
517 struct rte_efd_table *
518 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
519 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
521 struct rte_efd_table *table = NULL;
522 uint8_t *key_array = NULL;
523 uint32_t num_chunks, num_chunks_shift;
525 struct rte_efd_list *efd_list = NULL;
526 struct rte_tailq_entry *te;
527 uint64_t offline_table_size;
528 char ring_name[RTE_RING_NAMESIZE];
529 struct rte_ring *r = NULL;
532 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
534 if (online_cpu_socket_bitmask == 0) {
535 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
540 if (max_num_rules == 0) {
541 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
546 * Compute the minimum number of chunks (smallest power of 2)
547 * that can hold all of the rules
549 if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
550 num_chunks = rte_align32pow2(max_num_rules /
551 EFD_TARGET_CHUNK_NUM_RULES);
553 num_chunks = rte_align32pow2((max_num_rules /
554 EFD_TARGET_CHUNK_NUM_RULES) + 1);
556 num_chunks_shift = log2(num_chunks);
558 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
561 * Guarantee there's no existing: this is normally already checked
562 * by ring creation above
564 TAILQ_FOREACH(te, efd_list, next)
566 table = (struct rte_efd_table *) te->data;
567 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
575 goto error_unlock_exit;
578 te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
580 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
581 goto error_unlock_exit;
584 /* Create a new EFD table management structure */
585 table = (struct rte_efd_table *) rte_zmalloc_socket(NULL,
586 sizeof(struct rte_efd_table),
590 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
591 " on socket %u failed\n",
593 goto error_unlock_exit;
597 RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
598 "on socket %u\n", offline_cpu_socket);
600 table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
601 table->num_rules = 0;
602 table->num_chunks = num_chunks;
603 table->num_chunks_shift = num_chunks_shift;
604 table->key_len = key_len;
607 key_array = (uint8_t *) rte_zmalloc_socket(NULL,
608 table->max_num_rules * table->key_len,
611 if (key_array == NULL) {
612 RTE_LOG(ERR, EFD, "Allocating key array"
613 " on socket %u failed\n",
615 goto error_unlock_exit;
617 table->keys = key_array;
618 snprintf(table->name, sizeof(table->name), "%s", name);
620 RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
621 " which potentially supports %u entries\n",
622 num_chunks, table->max_num_rules);
624 /* Make sure all the allocatable table pointers are NULL initially */
625 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
626 table->chunks[socket_id] = NULL;
627 table->offline_chunks = NULL;
630 * Allocate one online table per socket specified
631 * in the user-supplied bitmask
633 uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
634 EFD_NUM_CHUNK_PADDING_BYTES;
636 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
637 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
639 * Allocate all of the EFD table chunks (the online portion)
640 * as a continuous block
642 table->chunks[socket_id] =
643 (struct efd_online_chunk *) rte_zmalloc_socket(
648 if (table->chunks[socket_id] == NULL) {
650 "Allocating EFD online table on "
651 "socket %u failed\n",
653 goto error_unlock_exit;
656 "Allocated EFD online table of size "
657 "%"PRIu64" bytes (%.2f MB) on socket %u\n",
659 (float) online_table_size /
665 table->lookup_fn = EFD_LOOKUP_SCALAR;
668 * Allocate the EFD table offline portion (with the actual rules
669 * mapping keys to values) as a continuous block.
670 * This could be several gigabytes of memory.
672 offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
673 table->offline_chunks =
674 (struct efd_offline_chunk_rules *) rte_zmalloc_socket(NULL,
678 if (table->offline_chunks == NULL) {
679 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
680 "failed\n", offline_cpu_socket);
681 goto error_unlock_exit;
685 "Allocated EFD offline table of size %"PRIu64" bytes "
686 " (%.2f MB) on socket %u\n", offline_table_size,
687 (float) offline_table_size / (1024.0F * 1024.0F),
690 te->data = (void *) table;
691 TAILQ_INSERT_TAIL(efd_list, te, next);
692 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
694 snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
695 /* Create ring (Dummy slot index is not enqueued) */
696 r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
697 offline_cpu_socket, 0);
699 RTE_LOG(ERR, EFD, "memory allocation failed\n");
700 goto error_unlock_exit;
703 /* Populate free slots ring. Entry zero is reserved for key misses. */
704 for (i = 0; i < table->max_num_rules; i++)
705 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
707 table->free_slots = r;
711 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
717 struct rte_efd_table *
718 rte_efd_find_existing(const char *name)
720 struct rte_efd_table *table = NULL;
721 struct rte_tailq_entry *te;
722 struct rte_efd_list *efd_list;
724 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
726 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
728 TAILQ_FOREACH(te, efd_list, next)
730 table = (struct rte_efd_table *) te->data;
731 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
734 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
744 rte_efd_free(struct rte_efd_table *table)
751 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
752 rte_free(table->chunks[socket_id]);
754 rte_ring_free(table->free_slots);
755 rte_free(table->offline_chunks);
756 rte_free(table->keys);
761 * Applies a previously computed table entry to the specified table for all
762 * socket-local copies of the online table.
763 * Intended to apply an update for only a single change
764 * to a key/value pair at a time
767 * EFD table to reference
769 * Socket ID to use to lookup existing values (ideally caller's socket id)
771 * Chunk index to update
773 * Group index to update
775 * Bin within the group that this update affects
776 * @param new_bin_choice
777 * Newly chosen permutation which this bin should use - only lower 2 bits
778 * @param new_group_entry
779 * Previously computed updated chunk/group entry
782 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
783 const uint32_t chunk_id, const uint32_t group_id,
784 const uint32_t bin_id, const uint8_t new_bin_choice,
785 const struct efd_online_group_entry * const new_group_entry)
788 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
789 uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
792 * Grab the current byte that contains the choices
793 * for four neighboring bins
795 uint8_t choice_chunk =
796 chunk->bin_choice_list[bin_index];
799 /* Compute the offset into the chunk that needs to be updated */
800 int offset = (bin_id & 0x3) * 2;
802 /* Zero the two bits of interest and set them to new_bin_choice */
803 choice_chunk = (choice_chunk & (~(0x03 << offset)))
804 | ((new_bin_choice & 0x03) << offset);
806 /* Update the online table with the new data across all sockets */
807 for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
808 if (table->chunks[i] != NULL) {
809 memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
811 sizeof(struct efd_online_group_entry));
812 table->chunks[i][chunk_id].bin_choice_list[bin_index] =
819 * Move the bin from prev group to the new group
822 move_groups(uint32_t bin_id, uint8_t bin_size,
823 struct efd_offline_group_rules *new_group,
824 struct efd_offline_group_rules * const current_group)
827 uint8_t empty_idx = 0;
830 if (new_group == current_group)
833 for (i = 0; i < current_group->num_rules; i++) {
835 * Move keys that belong to the same bin
838 if (current_group->bin_id[i] == bin_id) {
839 new_group->key_idx[new_group->num_rules] =
840 current_group->key_idx[i];
841 new_group->value[new_group->num_rules] =
842 current_group->value[i];
843 new_group->bin_id[new_group->num_rules] =
844 current_group->bin_id[i];
845 new_group->num_rules++;
847 if (i != empty_idx) {
849 * Need to move this key towards
850 * the top of the array
852 current_group->key_idx[empty_idx] =
853 current_group->key_idx[i];
854 current_group->value[empty_idx] =
855 current_group->value[i];
856 current_group->bin_id[empty_idx] =
857 current_group->bin_id[i];
863 current_group->num_rules -= bin_size;
867 * Revert group/s to their previous state before
868 * trying to insert/add a new key
871 revert_groups(struct efd_offline_group_rules *previous_group,
872 struct efd_offline_group_rules *current_group, uint8_t bin_size)
876 if (current_group == previous_group)
879 /* Move keys back to previous group */
880 for (i = current_group->num_rules - bin_size;
881 i < current_group->num_rules; i++) {
882 previous_group->key_idx[previous_group->num_rules] =
883 current_group->key_idx[i];
884 previous_group->value[previous_group->num_rules] =
885 current_group->value[i];
886 previous_group->bin_id[previous_group->num_rules] =
887 current_group->bin_id[i];
888 previous_group->num_rules++;
892 * Decrease number of rules after the move
895 current_group->num_rules -= bin_size;
899 * Computes an updated table entry where the supplied key points to a new host.
900 * If no entry exists, one is inserted.
902 * This function does NOT modify the online table(s)
903 * This function DOES modify the offline table
906 * EFD table to reference
908 * Socket ID to use to lookup existing values (ideally caller's socket id)
912 * Value to associate with key
914 * Chunk ID of the chunk that was modified
916 * Group ID of the group that was modified
918 * Bin ID that was modified
919 * @param new_bin_choice
920 * Newly chosen permutation which this bin will use
922 * Newly computed online entry to apply later with efd_apply_update
925 * RTE_EFD_UPDATE_WARN_GROUP_FULL
926 * Operation is insert, and the last available space in the
927 * key's group was just used. Future inserts may fail as groups fill up.
928 * This operation was still successful, and entry contains a valid update
929 * RTE_EFD_UPDATE_FAILED
930 * Either the EFD failed to find a suitable perfect hash or the group was full
931 * This is a fatal error, and the table is now in an indeterminite state
932 * RTE_EFD_UPDATE_NO_CHANGE
933 * Operation resulted in no change to the table (same value already exists)
935 * Insert or update was successful, and the new efd_online_group_entry
936 * is stored in *entry
939 * Note that entry will be UNCHANGED if the update has no effect, and thus any
940 * subsequent use of the entry content will likely be invalid
943 efd_compute_update(struct rte_efd_table * const table,
944 const unsigned int socket_id, const void *key,
945 const efd_value_t value, uint32_t * const chunk_id,
946 uint32_t * const group_id, uint32_t * const bin_id,
947 uint8_t * const new_bin_choice,
948 struct efd_online_group_entry * const entry)
953 void *new_k, *slot_id = NULL;
954 int status = EXIT_SUCCESS;
955 unsigned int found = 0;
957 efd_compute_ids(table, key, chunk_id, bin_id);
959 struct efd_offline_chunk_rules * const chunk =
960 &table->offline_chunks[*chunk_id];
961 struct efd_offline_group_rules *new_group;
963 uint8_t current_choice = efd_get_choice(table, socket_id,
965 uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
966 struct efd_offline_group_rules * const current_group =
967 &chunk->group_rules[current_group_id];
968 uint8_t bin_size = 0;
969 uint8_t key_changed_index = 0;
970 efd_value_t key_changed_previous_value = 0;
971 uint32_t key_idx_previous = 0;
973 /* Scan the current group and see if the key is already present */
974 for (i = 0; i < current_group->num_rules; i++) {
975 if (current_group->bin_id[i] == *bin_id)
980 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
981 if (found == 0 && unlikely(memcmp(key_stored, key,
982 table->key_len) == 0)) {
983 /* Key is already present */
986 * If previous value is same as new value,
987 * no additional work is required
989 if (current_group->value[i] == value)
990 return RTE_EFD_UPDATE_NO_CHANGE;
992 key_idx_previous = current_group->key_idx[i];
993 key_changed_previous_value = current_group->value[i];
994 key_changed_index = i;
995 current_group->value[i] = value;
1001 /* Key does not exist. Insert the rule into the bin/group */
1002 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1004 "Fatal: No room remaining for insert into "
1005 "chunk %u group %u bin %u\n",
1007 current_group_id, *bin_id);
1008 return RTE_EFD_UPDATE_FAILED;
1011 if (unlikely(current_group->num_rules ==
1012 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1013 RTE_LOG(INFO, EFD, "Warn: Insert into last "
1014 "available slot in chunk %u "
1015 "group %u bin %u\n", *chunk_id,
1016 current_group_id, *bin_id);
1017 status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1020 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1021 return RTE_EFD_UPDATE_FAILED;
1023 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1025 rte_prefetch0(new_k);
1026 new_idx = (uint32_t) ((uintptr_t) slot_id);
1028 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1029 current_group->key_idx[current_group->num_rules] = new_idx;
1030 current_group->value[current_group->num_rules] = value;
1031 current_group->bin_id[current_group->num_rules] = *bin_id;
1032 current_group->num_rules++;
1036 uint32_t last = current_group->num_rules - 1;
1037 /* Swap the key with the last key inserted*/
1038 current_group->key_idx[key_changed_index] =
1039 current_group->key_idx[last];
1040 current_group->value[key_changed_index] =
1041 current_group->value[last];
1042 current_group->bin_id[key_changed_index] =
1043 current_group->bin_id[last];
1046 * Key to be updated will always be available
1047 * at the end of the group
1049 current_group->key_idx[last] = key_idx_previous;
1050 current_group->value[last] = value;
1051 current_group->bin_id[last] = *bin_id;
1054 *new_bin_choice = current_choice;
1055 *group_id = current_group_id;
1056 new_group = current_group;
1058 /* Group need to be rebalanced when it starts to get loaded */
1059 if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1062 * Subtract the number of entries in the bin from
1063 * the original group
1065 current_group->num_rules -= bin_size;
1068 * Figure out which of the available groups that this bin
1069 * can map to is the smallest (using the current group
1072 uint8_t smallest_choice = current_choice;
1073 uint8_t smallest_size = current_group->num_rules;
1074 uint32_t smallest_group_id = current_group_id;
1075 unsigned char choice;
1077 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1079 uint32_t test_group_id =
1080 efd_bin_to_group[choice][*bin_id];
1081 uint32_t num_rules =
1082 chunk->group_rules[test_group_id].num_rules;
1083 if (num_rules < smallest_size) {
1084 smallest_choice = choice;
1085 smallest_size = num_rules;
1086 smallest_group_id = test_group_id;
1090 *new_bin_choice = smallest_choice;
1091 *group_id = smallest_group_id;
1092 new_group = &chunk->group_rules[smallest_group_id];
1093 current_group->num_rules += bin_size;
1099 if (current_group != new_group &&
1100 new_group->num_rules + bin_size >
1101 EFD_MAX_GROUP_NUM_RULES) {
1103 "Unable to move_groups to dest group "
1104 "containing %u entries."
1105 "bin_size:%u choice:%02x\n",
1106 new_group->num_rules, bin_size,
1110 move_groups(*bin_id, bin_size, new_group, current_group);
1112 * Recompute the hash function for the modified group,
1113 * and return it to the caller
1115 ret = efd_search_hash(table, new_group, entry);
1121 "Failed to find perfect hash for group "
1122 "containing %u entries. bin_size:%u choice:%02x\n",
1123 new_group->num_rules, bin_size, choice - 1);
1124 /* Restore groups modified to their previous state */
1125 revert_groups(current_group, new_group, bin_size);
1128 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1130 *new_bin_choice = choice;
1131 *group_id = efd_bin_to_group[choice][*bin_id];
1132 new_group = &chunk->group_rules[*group_id];
1137 current_group->num_rules--;
1140 current_group->value[current_group->num_rules - 1] =
1141 key_changed_previous_value;
1142 return RTE_EFD_UPDATE_FAILED;
1146 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1147 const void *key, const efd_value_t value)
1149 uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1150 uint8_t new_bin_choice = 0;
1151 struct efd_online_group_entry entry;
1153 int status = efd_compute_update(table, socket_id, key, value,
1154 &chunk_id, &group_id, &bin_id,
1155 &new_bin_choice, &entry);
1157 if (status == RTE_EFD_UPDATE_NO_CHANGE)
1158 return EXIT_SUCCESS;
1160 if (status == RTE_EFD_UPDATE_FAILED)
1163 efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1164 new_bin_choice, &entry);
1169 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1170 const void *key, efd_value_t * const prev_value)
1173 uint32_t chunk_id, bin_id;
1174 uint8_t not_found = 1;
1176 efd_compute_ids(table, key, &chunk_id, &bin_id);
1178 struct efd_offline_chunk_rules * const chunk =
1179 &table->offline_chunks[chunk_id];
1181 uint8_t current_choice = efd_get_choice(table, socket_id,
1183 uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1184 struct efd_offline_group_rules * const current_group =
1185 &chunk->group_rules[current_group_id];
1188 * Search the current group for the specified key.
1189 * If it exists, remove it and re-pack the other values
1191 for (i = 0; i < current_group->num_rules; i++) {
1193 /* Found key that needs to be removed */
1194 if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1195 key, table->key_len) == 0) {
1196 /* Store previous value if requested by caller */
1197 if (prev_value != NULL)
1198 *prev_value = current_group->value[i];
1201 rte_ring_sp_enqueue(table->free_slots,
1202 (void *)((uintptr_t)current_group->key_idx[i]));
1206 * If the desired key has been found,
1207 * need to shift other values up one
1210 /* Need to shift this entry back up one index */
1211 current_group->key_idx[i - 1] = current_group->key_idx[i];
1212 current_group->value[i - 1] = current_group->value[i];
1213 current_group->bin_id[i - 1] = current_group->bin_id[i];
1217 if (not_found == 0) {
1219 current_group->num_rules--;
1225 static inline efd_value_t
1226 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1227 const efd_lookuptbl_t *group_lookup_table,
1228 const uint32_t hash_val_a, const uint32_t hash_val_b)
1230 efd_value_t value = 0;
1233 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1235 uint32_t h = hash_val_a + (hash_val_b *
1236 group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1237 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1238 value |= (group_lookup_table[
1239 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1247 static inline efd_value_t
1248 efd_lookup_internal(const struct efd_online_group_entry * const group,
1249 const uint32_t hash_val_a, const uint32_t hash_val_b,
1250 enum efd_lookup_internal_function lookup_fn)
1252 efd_value_t value = 0;
1254 switch (lookup_fn) {
1256 case EFD_LOOKUP_SCALAR:
1259 return efd_lookup_internal_scalar(group->hash_idx,
1260 group->lookup_table,
1269 rte_efd_lookup(const struct rte_efd_table * const table,
1270 const unsigned int socket_id, const void *key)
1272 uint32_t chunk_id, group_id, bin_id;
1274 const struct efd_online_group_entry *group;
1275 const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1277 /* Determine the chunk and group location for the given key */
1278 efd_compute_ids(table, key, &chunk_id, &bin_id);
1279 bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1280 group_id = efd_bin_to_group[bin_choice][bin_id];
1281 group = &chunks[chunk_id].groups[group_id];
1283 return efd_lookup_internal(group,
1284 EFD_HASHFUNCA(key, table),
1285 EFD_HASHFUNCB(key, table),
1289 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1290 const unsigned int socket_id, const int num_keys,
1291 const void **key_list, efd_value_t * const value_list)
1294 uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1295 uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1296 uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1297 uint32_t group_id_list[RTE_EFD_BURST_MAX];
1298 struct efd_online_group_entry *group;
1300 struct efd_online_chunk *chunks = table->chunks[socket_id];
1302 for (i = 0; i < num_keys; i++) {
1303 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1305 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1308 for (i = 0; i < num_keys; i++) {
1309 bin_choice_list[i] = efd_get_choice(table, socket_id,
1310 chunk_id_list[i], bin_id_list[i]);
1312 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1313 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1314 rte_prefetch0(group);
1317 for (i = 0; i < num_keys; i++) {
1318 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1319 value_list[i] = efd_lookup_internal(group,
1320 EFD_HASHFUNCA(key_list[i], table),
1321 EFD_HASHFUNCB(key_list[i], table),