eal: export function to get runtime directory
[dpdk.git] / lib / librte_efd / rte_efd.c
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2016-2017 Intel Corporation
3  */
4 #include <stdio.h>
5 #include <string.h>
6 #include <stdint.h>
7 #include <inttypes.h>
8 #include <errno.h>
9 #include <stdarg.h>
10 #include <sys/queue.h>
11
12 #include <rte_log.h>
13 #include <rte_eal_memconfig.h>
14 #include <rte_errno.h>
15 #include <rte_malloc.h>
16 #include <rte_prefetch.h>
17 #include <rte_branch_prediction.h>
18 #include <rte_memcpy.h>
19 #include <rte_ring.h>
20 #include <rte_jhash.h>
21 #include <rte_hash_crc.h>
22
23 #include "rte_efd.h"
24 #if defined(RTE_ARCH_X86)
25 #include "rte_efd_x86.h"
26 #elif defined(RTE_ARCH_ARM64)
27 #include "rte_efd_arm64.h"
28 #endif
29
30 #define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len))
31 /** Hash function used to determine chunk_id and bin_id for a group */
32 #define EFD_HASH(key, table) \
33         (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34))
34 /** Hash function used as constant component of perfect hash search */
35 #define EFD_HASHFUNCA(key, table) \
36         (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35))
37 /** Hash function used as multiplicative component of perfect hash search */
38 #define EFD_HASHFUNCB(key, table) \
39         (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36))
40
41 /*************************************************************************
42  * Fixed constants
43  *************************************************************************/
44
45 /* These parameters are fixed by the efd_bin_to_group balancing table */
46 #define EFD_CHUNK_NUM_GROUPS (64)
47 #define EFD_CHUNK_NUM_BINS   (256)
48 #define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \
49         (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS)
50
51 /*
52  * Target number of rules that each chunk is created to handle.
53  * Used when initially allocating the table
54  */
55 #define EFD_TARGET_CHUNK_NUM_RULES  \
56         (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)
57 /*
58  * Max number of rules that each chunk is created to handle.
59  * Used when initially allocating the table
60  */
61 #define EFD_TARGET_CHUNK_MAX_NUM_RULES  \
62         (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES)
63
64 /** This is fixed based on the bin_to_group permutation array */
65 #define EFD_MAX_GROUP_NUM_BINS (16)
66
67 /**
68  * The end of the chunks array needs some extra padding to ensure
69  * that vectorization over-reads on the last online chunk stay within
70 allocated memory
71  */
72 #define EFD_NUM_CHUNK_PADDING_BYTES (256)
73
74 /* All different internal lookup functions */
75 enum efd_lookup_internal_function {
76         EFD_LOOKUP_SCALAR = 0,
77         EFD_LOOKUP_AVX2,
78         EFD_LOOKUP_NEON,
79         EFD_LOOKUP_NUM
80 };
81
82 TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
83
84 static struct rte_tailq_elem rte_efd_tailq = {
85         .name = "RTE_EFD",
86 };
87 EAL_REGISTER_TAILQ(rte_efd_tailq);
88
89 /** Internal permutation array used to shuffle bins into pseudorandom groups */
90 const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
91         {
92                 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
93                 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
94                 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
95                 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
96                 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
97                 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
98                 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
99                 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
100                 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
101                 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
102                 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
103                 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
104                 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
105                 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
106                 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
107                 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
108         },
109         {
110                 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
111                 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
112                 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
113                 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
114                 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
115                 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
116                 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
117                 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
118                 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
119                 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
120                 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
121                 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
122                 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
123                 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
124                 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
125                 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
126         },
127         {
128                 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
129                 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
130                 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
131                 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
132                 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
133                 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
134                 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
135                 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
136                 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
137                 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
138                 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
139                 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
140                 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
141                 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
142                 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
143                 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
144         },
145         {
146                 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
147                 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
148                 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
149                 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
150                 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
151                 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
152                 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
153                 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
154                 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
155                 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
156                 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
157                 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
158                 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
159                 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
160                 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
161                 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
162         },
163 };
164
165 /*************************************************************************
166  * Offline region structures
167  *************************************************************************/
168
169 /** Online group containing number of rules, values, keys and their bins
170  * for EFD_MAX_GROUP_NUM_RULES rules.
171  */
172 struct efd_offline_group_rules {
173         uint32_t num_rules;
174         /**< Sum of the number of rules in all bins assigned to this group. */
175
176         uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
177         /**< Array with all keys of the group. */
178         efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
179         /**< Array with all values of the keys of the group. */
180
181         uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
182         /**< Stores the bin for each correspending key to
183          * avoid having to recompute it
184          */
185 };
186
187 /** Offline chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
188  * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
189  */
190 struct efd_offline_chunk_rules {
191         uint16_t num_rules;
192         /**< Number of rules in the entire chunk;
193          * used to detect unbalanced groups
194          */
195
196         struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
197         /**< Array of all groups in the chunk. */
198 };
199
200 /*************************************************************************
201  * Online region structures
202  *************************************************************************/
203
204 /** Online group containing values for EFD_MAX_GROUP_NUM_RULES rules. */
205 struct efd_online_group_entry {
206         efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
207         efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
208 } __attribute__((__packed__));
209
210 /**
211  * A single chunk record, containing EFD_TARGET_CHUNK_NUM_RULES rules.
212  * Those rules are split into EFD_CHUNK_NUM_GROUPS groups per chunk.
213  */
214 struct efd_online_chunk {
215         uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
216         /**< This is a packed indirection index into the 'groups' array.
217          * Each byte contains four two-bit values which index into
218          * the efd_bin_to_group array.
219          * The efd_bin_to_group array returns the index into the groups array
220          */
221
222         struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
223         /**< Array of all the groups in the chunk. */
224 } __attribute__((__packed__));
225
226 /**
227  * EFD table structure
228  */
229 struct rte_efd_table {
230         char name[RTE_EFD_NAMESIZE]; /**< Name of the efd table. */
231
232         uint32_t key_len; /**< Length of the key stored offline */
233
234         uint32_t max_num_rules;
235         /**< Static maximum number of entries the table was constructed to hold. */
236
237         uint32_t num_rules;
238         /**< Number of entries currently in the table . */
239
240         uint32_t num_chunks;
241         /**< Number of chunks in the table needed to support num_rules. */
242
243         uint32_t num_chunks_shift;
244         /**< Bits to shift to get chunk id, instead of dividing by num_chunk. */
245
246         enum efd_lookup_internal_function lookup_fn;
247         /**< Indicates which lookup function to use. */
248
249         struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
250         /**< Dynamic array of size num_chunks of chunk records. */
251
252         struct efd_offline_chunk_rules *offline_chunks;
253         /**< Dynamic array of size num_chunks of key-value pairs. */
254
255         struct rte_ring *free_slots;
256         /**< Ring that stores all indexes of the free slots in the key table */
257
258         uint8_t *keys; /**< Dynamic array of size max_num_rules of keys */
259 };
260
261 /**
262  * Computes the chunk ID for a given key hash
263  *
264  * @param table
265  *   EFD table to reference
266  * @param hashed_key
267  *   32-bit key hash returned by EFD_HASH
268  *
269  * @return
270  *   chunk ID containing this key hash
271  */
272 static inline uint32_t
273 efd_get_chunk_id(const struct rte_efd_table * const table,
274                 const uint32_t hashed_key)
275 {
276         return hashed_key & (table->num_chunks - 1);
277 }
278
279 /**
280  * Computes the bin ID for a given key hash
281  *
282  * @param table
283  *   EFD table to reference
284  * @param hashed_key
285  *   32-bit key hash returned by EFD_HASH
286  *
287  * @return bin ID containing this key hash
288  */
289 static inline uint32_t
290 efd_get_bin_id(const struct rte_efd_table * const table,
291                 const uint32_t hashed_key)
292 {
293         return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
294 }
295
296 /**
297  * Looks up the current permutation choice for a particular bin in the online table
298  *
299  * @param table
300  *  EFD table to reference
301  * @param socket_id
302  *   Socket ID to use to look up existing values (ideally caller's socket id)
303  * @param chunk_id
304  *   Chunk ID of bin to look up
305  * @param bin_id
306  *   Bin ID to look up
307  *
308  * @return
309  *   Currently active permutation choice in the online table
310  */
311 static inline uint8_t
312 efd_get_choice(const struct rte_efd_table * const table,
313                 const unsigned int socket_id, const uint32_t chunk_id,
314                 const uint32_t bin_id)
315 {
316         struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
317
318         /*
319          * Grab the chunk (byte) that contains the choices
320          * for four neighboring bins.
321          */
322         uint8_t choice_chunk =
323                         chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
324
325         /*
326          * Compute the offset into the chunk that contains
327          * the group_id lookup position
328          */
329         int offset = (bin_id & 0x3) * 2;
330
331         /* Extract from the byte just the desired lookup position */
332         return (uint8_t) ((choice_chunk >> offset) & 0x3);
333 }
334
335 /**
336  * Compute the chunk_id and bin_id for a given key
337  *
338  * @param table
339  *   EFD table to reference
340  * @param key
341  *   Key to hash and find location of
342  * @param chunk_id
343  *   Computed chunk ID
344  * @param bin_id
345  *   Computed bin ID
346  *
347  */
348 static inline void
349 efd_compute_ids(const struct rte_efd_table * const table,
350                 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
351 {
352         /* Compute the position of the entry in the hash table */
353         uint32_t h = EFD_HASH(key, table);
354
355         /* Compute the chunk_id where that entry can be found */
356         *chunk_id = efd_get_chunk_id(table, h);
357
358         /*
359          * Compute the bin within that chunk where the entry
360          * can be found (0 - 255)
361          */
362         *bin_id = efd_get_bin_id(table, h);
363 }
364
365 /**
366  * Search for a hash function for a group that satisfies all group results
367  */
368 static inline int
369 efd_search_hash(struct rte_efd_table * const table,
370                 const struct efd_offline_group_rules * const off_group,
371                 struct efd_online_group_entry * const on_group)
372 {
373         efd_hashfunc_t hash_idx;
374         efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
375         efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
376
377         uint32_t i, j, rule_id;
378         uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
379         uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
380         uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
381
382
383         rte_prefetch0(off_group->value);
384
385         /*
386          * Prepopulate the hash_val tables by running the two hash functions
387          * for each provided rule
388          */
389         for (i = 0; i < off_group->num_rules; i++) {
390                 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
391                 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
392                 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
393         }
394
395         for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
396                 hash_idx = on_group->hash_idx[i];
397                 start_hash_idx[i] = hash_idx;
398                 start_lookup_table[i] = on_group->lookup_table[i];
399
400                 do {
401                         efd_lookuptbl_t lookup_table = 0;
402                         efd_lookuptbl_t lookup_table_complement = 0;
403
404                         for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
405                                 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
406                                         hash_val_b[rule_id]);
407
408                         /*
409                          * The goal here is to find a hash function for this
410                          * particular bit entry that meets the following criteria:
411                          * The most significant bits of the hash result define a
412                          * shift into the lookup table where the bit will be stored
413                          */
414
415                         /* Iterate over each provided rule */
416                         for (rule_id = 0; rule_id < off_group->num_rules;
417                                         rule_id++) {
418                                 /*
419                                  * Use the few most significant bits (number based on
420                                  * EFD_LOOKUPTBL_SIZE) to see what position the
421                                  * expected bit should be set in the lookup_table
422                                  */
423                                 uint32_t bucket_idx = hash_val[rule_id] >>
424                                                 EFD_LOOKUPTBL_SHIFT;
425
426                                 /*
427                                  * Get the current bit of interest.
428                                  * This only find an appropriate hash function
429                                  * for one bit at a time of the rule
430                                  */
431                                 efd_lookuptbl_t expected =
432                                                 (off_group->value[rule_id] >> i) & 0x1;
433
434                                 /*
435                                  * Add the expected bit (if set) to a map
436                                  * (lookup_table). Also set its complement
437                                  * in lookup_table_complement
438                                  */
439                                 lookup_table |= expected << bucket_idx;
440                                 lookup_table_complement |= (1 - expected)
441                                                 << bucket_idx;
442
443                                 /*
444                                  * If ever the hash function of two different
445                                  * elements result in different values at the
446                                  * same location in the lookup_table,
447                                  * the current hash_idx is not valid.
448                                  */
449                                 if (lookup_table & lookup_table_complement)
450                                         break;
451                         }
452
453                         /*
454                          * Check if the previous loop completed without
455                          * breaking early
456                          */
457                         if (rule_id == off_group->num_rules) {
458                                 /*
459                                  * Current hash function worked, store it
460                                  * for the current group
461                                  */
462                                 on_group->hash_idx[i] = hash_idx;
463                                 on_group->lookup_table[i] = lookup_table;
464
465                                 /*
466                                  * Make sure that the hash function has changed
467                                  * from the starting value
468                                  */
469                                 hash_idx = start_hash_idx[i] + 1;
470                                 break;
471                         }
472                         hash_idx++;
473
474                 } while (hash_idx != start_hash_idx[i]);
475
476                 /* Failed to find perfect hash for this group */
477                 if (hash_idx == start_hash_idx[i]) {
478                         /*
479                          * Restore previous hash_idx and lookup_table
480                          * for all value bits
481                          */
482                         for (j = 0; j < i; j++) {
483                                 on_group->hash_idx[j] = start_hash_idx[j];
484                                 on_group->lookup_table[j] = start_lookup_table[j];
485                         }
486                         return 1;
487                 }
488         }
489
490         return 0;
491 }
492
493 struct rte_efd_table *
494 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
495                 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
496 {
497         struct rte_efd_table *table = NULL;
498         uint8_t *key_array = NULL;
499         uint32_t num_chunks, num_chunks_shift;
500         uint8_t socket_id;
501         struct rte_efd_list *efd_list = NULL;
502         struct rte_tailq_entry *te;
503         uint64_t offline_table_size;
504         char ring_name[RTE_RING_NAMESIZE];
505         struct rte_ring *r = NULL;
506         unsigned int i;
507
508         efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
509
510         if (online_cpu_socket_bitmask == 0) {
511                 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
512                                 "in the bitmask\n");
513                 return NULL;
514         }
515
516         if (max_num_rules == 0) {
517                 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
518                 return NULL;
519         }
520
521         /*
522          * Compute the minimum number of chunks (smallest power of 2)
523          * that can hold all of the rules
524          */
525         if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
526                 num_chunks = rte_align32pow2(max_num_rules /
527                         EFD_TARGET_CHUNK_NUM_RULES);
528         else
529                 num_chunks = rte_align32pow2((max_num_rules /
530                         EFD_TARGET_CHUNK_NUM_RULES) + 1);
531
532         num_chunks_shift = rte_bsf32(num_chunks);
533
534         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
535
536         /*
537          * Guarantee there's no existing: this is normally already checked
538          * by ring creation above
539          */
540         TAILQ_FOREACH(te, efd_list, next)
541         {
542                 table = (struct rte_efd_table *) te->data;
543                 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
544                         break;
545         }
546
547         table = NULL;
548         if (te != NULL) {
549                 rte_errno = EEXIST;
550                 te = NULL;
551                 goto error_unlock_exit;
552         }
553
554         te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
555         if (te == NULL) {
556                 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
557                 goto error_unlock_exit;
558         }
559
560         /* Create a new EFD table management structure */
561         table = rte_zmalloc_socket(NULL,
562                         sizeof(struct rte_efd_table),
563                         RTE_CACHE_LINE_SIZE,
564                         offline_cpu_socket);
565         if (table == NULL) {
566                 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
567                                 " on socket %u failed\n",
568                                 offline_cpu_socket);
569                 goto error_unlock_exit;
570         }
571
572
573         RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
574                         "on socket %u\n", offline_cpu_socket);
575
576         table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
577         table->num_rules = 0;
578         table->num_chunks = num_chunks;
579         table->num_chunks_shift = num_chunks_shift;
580         table->key_len = key_len;
581
582         /* key_array */
583         key_array = rte_zmalloc_socket(NULL,
584                         table->max_num_rules * table->key_len,
585                         RTE_CACHE_LINE_SIZE,
586                         offline_cpu_socket);
587         if (key_array == NULL) {
588                 RTE_LOG(ERR, EFD, "Allocating key array"
589                                 " on socket %u failed\n",
590                                 offline_cpu_socket);
591                 goto error_unlock_exit;
592         }
593         table->keys = key_array;
594         snprintf(table->name, sizeof(table->name), "%s", name);
595
596         RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
597                         " which potentially supports %u entries\n",
598                         num_chunks, table->max_num_rules);
599
600         /* Make sure all the allocatable table pointers are NULL initially */
601         for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
602                 table->chunks[socket_id] = NULL;
603         table->offline_chunks = NULL;
604
605         /*
606          * Allocate one online table per socket specified
607          * in the user-supplied bitmask
608          */
609         uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
610                         EFD_NUM_CHUNK_PADDING_BYTES;
611
612         for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
613                 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
614                         /*
615                          * Allocate all of the EFD table chunks (the online portion)
616                          * as a continuous block
617                          */
618                         table->chunks[socket_id] =
619                                 rte_zmalloc_socket(
620                                 NULL,
621                                 online_table_size,
622                                 RTE_CACHE_LINE_SIZE,
623                                 socket_id);
624                         if (table->chunks[socket_id] == NULL) {
625                                 RTE_LOG(ERR, EFD,
626                                                 "Allocating EFD online table on "
627                                                 "socket %u failed\n",
628                                                 socket_id);
629                                 goto error_unlock_exit;
630                         }
631                         RTE_LOG(DEBUG, EFD,
632                                         "Allocated EFD online table of size "
633                                         "%"PRIu64" bytes (%.2f MB) on socket %u\n",
634                                         online_table_size,
635                                         (float) online_table_size /
636                                                 (1024.0F * 1024.0F),
637                                         socket_id);
638                 }
639         }
640
641 #if defined(RTE_ARCH_X86)
642         /*
643          * For less than 4 bits, scalar function performs better
644          * than vectorised version
645          */
646         if (RTE_EFD_VALUE_NUM_BITS > 3 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))
647                 table->lookup_fn = EFD_LOOKUP_AVX2;
648         else
649 #endif
650 #if defined(RTE_ARCH_ARM64)
651         /*
652          * For less than or equal to 16 bits, scalar function performs better
653          * than vectorised version
654          */
655         if (RTE_EFD_VALUE_NUM_BITS > 16 &&
656             rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON))
657                 table->lookup_fn = EFD_LOOKUP_NEON;
658         else
659 #endif
660                 table->lookup_fn = EFD_LOOKUP_SCALAR;
661
662         /*
663          * Allocate the EFD table offline portion (with the actual rules
664          * mapping keys to values) as a continuous block.
665          * This could be several gigabytes of memory.
666          */
667         offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
668         table->offline_chunks =
669                         rte_zmalloc_socket(NULL,
670                         offline_table_size,
671                         RTE_CACHE_LINE_SIZE,
672                         offline_cpu_socket);
673         if (table->offline_chunks == NULL) {
674                 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
675                                 "failed\n", offline_cpu_socket);
676                 goto error_unlock_exit;
677         }
678
679         RTE_LOG(DEBUG, EFD,
680                         "Allocated EFD offline table of size %"PRIu64" bytes "
681                         " (%.2f MB) on socket %u\n", offline_table_size,
682                         (float) offline_table_size / (1024.0F * 1024.0F),
683                         offline_cpu_socket);
684
685         te->data = (void *) table;
686         TAILQ_INSERT_TAIL(efd_list, te, next);
687         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
688
689         snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
690         /* Create ring (Dummy slot index is not enqueued) */
691         r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
692                         offline_cpu_socket, 0);
693         if (r == NULL) {
694                 RTE_LOG(ERR, EFD, "memory allocation failed\n");
695                 goto error_unlock_exit;
696         }
697
698         /* Populate free slots ring. Entry zero is reserved for key misses. */
699         for (i = 0; i < table->max_num_rules; i++)
700                 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
701
702         table->free_slots = r;
703         return table;
704
705 error_unlock_exit:
706         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
707         rte_efd_free(table);
708
709         return NULL;
710 }
711
712 struct rte_efd_table *
713 rte_efd_find_existing(const char *name)
714 {
715         struct rte_efd_table *table = NULL;
716         struct rte_tailq_entry *te;
717         struct rte_efd_list *efd_list;
718
719         efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
720
721         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
722
723         TAILQ_FOREACH(te, efd_list, next)
724         {
725                 table = (struct rte_efd_table *) te->data;
726                 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
727                         break;
728         }
729         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
730
731         if (te == NULL) {
732                 rte_errno = ENOENT;
733                 return NULL;
734         }
735         return table;
736 }
737
738 void
739 rte_efd_free(struct rte_efd_table *table)
740 {
741         uint8_t socket_id;
742
743         if (table == NULL)
744                 return;
745
746         for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
747                 rte_free(table->chunks[socket_id]);
748
749         rte_ring_free(table->free_slots);
750         rte_free(table->offline_chunks);
751         rte_free(table->keys);
752         rte_free(table);
753 }
754
755 /**
756  * Applies a previously computed table entry to the specified table for all
757  * socket-local copies of the online table.
758  * Intended to apply an update for only a single change
759  * to a key/value pair at a time
760  *
761  * @param table
762  *   EFD table to reference
763  * @param socket_id
764  *   Socket ID to use to lookup existing values (ideally caller's socket id)
765  * @param chunk_id
766  *   Chunk index to update
767  * @param group_id
768  *   Group index to update
769  * @param bin_id
770  *   Bin within the group that this update affects
771  * @param new_bin_choice
772  *   Newly chosen permutation which this bin should use - only lower 2 bits
773  * @param new_group_entry
774  *   Previously computed updated chunk/group entry
775  */
776 static inline void
777 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
778                 const uint32_t chunk_id, const uint32_t group_id,
779                 const uint32_t bin_id, const uint8_t new_bin_choice,
780                 const struct efd_online_group_entry * const new_group_entry)
781 {
782         int i;
783         struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
784         uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
785
786         /*
787          * Grab the current byte that contains the choices
788          * for four neighboring bins
789          */
790         uint8_t choice_chunk =
791                         chunk->bin_choice_list[bin_index];
792
793
794         /* Compute the offset into the chunk that needs to be updated */
795         int offset = (bin_id & 0x3) * 2;
796
797         /* Zero the two bits of interest and set them to new_bin_choice */
798         choice_chunk = (choice_chunk & (~(0x03 << offset)))
799                         | ((new_bin_choice & 0x03) << offset);
800
801         /* Update the online table with the new data across all sockets */
802         for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
803                 if (table->chunks[i] != NULL) {
804                         memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
805                                         new_group_entry,
806                                         sizeof(struct efd_online_group_entry));
807                         table->chunks[i][chunk_id].bin_choice_list[bin_index] =
808                                         choice_chunk;
809                 }
810         }
811 }
812
813 /*
814  * Move the bin from prev group to the new group
815  */
816 static inline void
817 move_groups(uint32_t bin_id, uint8_t bin_size,
818                 struct efd_offline_group_rules *new_group,
819                 struct efd_offline_group_rules * const current_group)
820 {
821
822         uint8_t empty_idx = 0;
823         unsigned int i;
824
825         if (new_group == current_group)
826                 return;
827
828         for (i = 0; i < current_group->num_rules; i++) {
829                 /*
830                  * Move keys that belong to the same bin
831                  * to the new group
832                  */
833                 if (current_group->bin_id[i] == bin_id) {
834                         new_group->key_idx[new_group->num_rules] =
835                                         current_group->key_idx[i];
836                         new_group->value[new_group->num_rules] =
837                                         current_group->value[i];
838                         new_group->bin_id[new_group->num_rules] =
839                                         current_group->bin_id[i];
840                         new_group->num_rules++;
841                 } else {
842                         if (i != empty_idx) {
843                                 /*
844                                  * Need to move this key towards
845                                  * the top of the array
846                                  */
847                                 current_group->key_idx[empty_idx] =
848                                                 current_group->key_idx[i];
849                                 current_group->value[empty_idx] =
850                                                 current_group->value[i];
851                                 current_group->bin_id[empty_idx] =
852                                                 current_group->bin_id[i];
853                         }
854                         empty_idx++;
855                 }
856
857         }
858         current_group->num_rules -= bin_size;
859 }
860
861 /*
862  * Revert group/s to their previous state before
863  * trying to insert/add a new key
864  */
865 static inline void
866 revert_groups(struct efd_offline_group_rules *previous_group,
867                 struct efd_offline_group_rules *current_group, uint8_t bin_size)
868 {
869         unsigned int i;
870
871         if (current_group == previous_group)
872                 return;
873
874         /* Move keys back to previous group */
875         for (i = current_group->num_rules - bin_size;
876                         i < current_group->num_rules; i++) {
877                 previous_group->key_idx[previous_group->num_rules] =
878                                 current_group->key_idx[i];
879                 previous_group->value[previous_group->num_rules] =
880                                 current_group->value[i];
881                 previous_group->bin_id[previous_group->num_rules] =
882                                 current_group->bin_id[i];
883                 previous_group->num_rules++;
884         }
885
886         /*
887          * Decrease number of rules after the move
888          * in the new group
889          */
890         current_group->num_rules -= bin_size;
891 }
892
893 /**
894  * Computes an updated table entry where the supplied key points to a new host.
895  * If no entry exists, one is inserted.
896  *
897  * This function does NOT modify the online table(s)
898  * This function DOES modify the offline table
899  *
900  * @param table
901  *   EFD table to reference
902  * @param socket_id
903  *   Socket ID to use to lookup existing values (ideally caller's socket id)
904  * @param key
905  *   Key to insert
906  * @param value
907  *   Value to associate with key
908  * @param chunk_id
909  *   Chunk ID of the chunk that was modified
910  * @param group_id
911  *   Group ID of the group that was modified
912  * @param bin_id
913  *   Bin ID that was modified
914  * @param new_bin_choice
915  *   Newly chosen permutation which this bin will use
916  * @param entry
917  *   Newly computed online entry to apply later with efd_apply_update
918  *
919  * @return
920  *   RTE_EFD_UPDATE_WARN_GROUP_FULL
921  *     Operation is insert, and the last available space in the
922  *     key's group was just used. Future inserts may fail as groups fill up.
923  *     This operation was still successful, and entry contains a valid update
924  *   RTE_EFD_UPDATE_FAILED
925  *     Either the EFD failed to find a suitable perfect hash or the group was full
926  *     This is a fatal error, and the table is now in an indeterminate state
927  *   RTE_EFD_UPDATE_NO_CHANGE
928  *     Operation resulted in no change to the table (same value already exists)
929  *   0
930  *     Insert or update was successful, and the new efd_online_group_entry
931  *     is stored in *entry
932  *
933  * @warning
934  *   Note that entry will be UNCHANGED if the update has no effect, and thus any
935  *   subsequent use of the entry content will likely be invalid
936  */
937 static inline int
938 efd_compute_update(struct rte_efd_table * const table,
939                 const unsigned int socket_id, const void *key,
940                 const efd_value_t value, uint32_t * const chunk_id,
941                 uint32_t * const group_id, uint32_t * const bin_id,
942                 uint8_t * const new_bin_choice,
943                 struct efd_online_group_entry * const entry)
944 {
945         unsigned int i;
946         int ret;
947         uint32_t new_idx;
948         void *new_k, *slot_id = NULL;
949         int status = EXIT_SUCCESS;
950         unsigned int found = 0;
951
952         efd_compute_ids(table, key, chunk_id, bin_id);
953
954         struct efd_offline_chunk_rules * const chunk =
955                         &table->offline_chunks[*chunk_id];
956         struct efd_offline_group_rules *new_group;
957
958         uint8_t current_choice = efd_get_choice(table, socket_id,
959                         *chunk_id, *bin_id);
960         uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
961         struct efd_offline_group_rules * const current_group =
962                         &chunk->group_rules[current_group_id];
963         uint8_t bin_size = 0;
964         uint8_t key_changed_index = 0;
965         efd_value_t key_changed_previous_value = 0;
966         uint32_t key_idx_previous = 0;
967
968         /* Scan the current group and see if the key is already present */
969         for (i = 0; i < current_group->num_rules; i++) {
970                 if (current_group->bin_id[i] == *bin_id)
971                         bin_size++;
972                 else
973                         continue;
974
975                 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
976                 if (found == 0 && unlikely(memcmp(key_stored, key,
977                                 table->key_len) == 0)) {
978                         /* Key is already present */
979
980                         /*
981                          * If previous value is same as new value,
982                          * no additional work is required
983                          */
984                         if (current_group->value[i] == value)
985                                 return RTE_EFD_UPDATE_NO_CHANGE;
986
987                         key_idx_previous = current_group->key_idx[i];
988                         key_changed_previous_value = current_group->value[i];
989                         key_changed_index = i;
990                         current_group->value[i] = value;
991                         found = 1;
992                 }
993         }
994
995         if (found == 0) {
996                 /* Key does not exist. Insert the rule into the bin/group */
997                 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
998                         RTE_LOG(ERR, EFD,
999                                         "Fatal: No room remaining for insert into "
1000                                         "chunk %u group %u bin %u\n",
1001                                         *chunk_id,
1002                                         current_group_id, *bin_id);
1003                         return RTE_EFD_UPDATE_FAILED;
1004                 }
1005
1006                 if (unlikely(current_group->num_rules ==
1007                                 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1008                         RTE_LOG(INFO, EFD, "Warn: Insert into last "
1009                                         "available slot in chunk %u "
1010                                         "group %u bin %u\n", *chunk_id,
1011                                         current_group_id, *bin_id);
1012                         status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1013                 }
1014
1015                 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1016                         return RTE_EFD_UPDATE_FAILED;
1017
1018                 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1019                                         table->key_len);
1020                 rte_prefetch0(new_k);
1021                 new_idx = (uint32_t) ((uintptr_t) slot_id);
1022
1023                 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1024                 current_group->key_idx[current_group->num_rules] = new_idx;
1025                 current_group->value[current_group->num_rules] = value;
1026                 current_group->bin_id[current_group->num_rules] = *bin_id;
1027                 current_group->num_rules++;
1028                 table->num_rules++;
1029                 bin_size++;
1030         } else {
1031                 uint32_t last = current_group->num_rules - 1;
1032                 /* Swap the key with the last key inserted*/
1033                 current_group->key_idx[key_changed_index] =
1034                                 current_group->key_idx[last];
1035                 current_group->value[key_changed_index] =
1036                                 current_group->value[last];
1037                 current_group->bin_id[key_changed_index] =
1038                                 current_group->bin_id[last];
1039
1040                 /*
1041                  * Key to be updated will always be available
1042                  * at the end of the group
1043                  */
1044                 current_group->key_idx[last] = key_idx_previous;
1045                 current_group->value[last] = value;
1046                 current_group->bin_id[last] = *bin_id;
1047         }
1048
1049         *new_bin_choice = current_choice;
1050         *group_id = current_group_id;
1051         new_group = current_group;
1052
1053         /* Group need to be rebalanced when it starts to get loaded */
1054         if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1055
1056                 /*
1057                  * Subtract the number of entries in the bin from
1058                  * the original group
1059                  */
1060                 current_group->num_rules -= bin_size;
1061
1062                 /*
1063                  * Figure out which of the available groups that this bin
1064                  * can map to is the smallest (using the current group
1065                  * as baseline)
1066                  */
1067                 uint8_t smallest_choice = current_choice;
1068                 uint8_t smallest_size = current_group->num_rules;
1069                 uint32_t smallest_group_id = current_group_id;
1070                 unsigned char choice;
1071
1072                 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1073                                 choice++) {
1074                         uint32_t test_group_id =
1075                                         efd_bin_to_group[choice][*bin_id];
1076                         uint32_t num_rules =
1077                                         chunk->group_rules[test_group_id].num_rules;
1078                         if (num_rules < smallest_size) {
1079                                 smallest_choice = choice;
1080                                 smallest_size = num_rules;
1081                                 smallest_group_id = test_group_id;
1082                         }
1083                 }
1084
1085                 *new_bin_choice = smallest_choice;
1086                 *group_id = smallest_group_id;
1087                 new_group = &chunk->group_rules[smallest_group_id];
1088                 current_group->num_rules += bin_size;
1089
1090         }
1091
1092         uint8_t choice = 0;
1093         for (;;) {
1094                 if (current_group != new_group &&
1095                                 new_group->num_rules + bin_size >
1096                                         EFD_MAX_GROUP_NUM_RULES) {
1097                         RTE_LOG(DEBUG, EFD,
1098                                         "Unable to move_groups to dest group "
1099                                         "containing %u entries."
1100                                         "bin_size:%u choice:%02x\n",
1101                                         new_group->num_rules, bin_size,
1102                                         choice - 1);
1103                         goto next_choice;
1104                 }
1105                 move_groups(*bin_id, bin_size, new_group, current_group);
1106                 /*
1107                  * Recompute the hash function for the modified group,
1108                  * and return it to the caller
1109                  */
1110                 ret = efd_search_hash(table, new_group, entry);
1111
1112                 if (!ret)
1113                         return status;
1114
1115                 RTE_LOG(DEBUG, EFD,
1116                                 "Failed to find perfect hash for group "
1117                                 "containing %u entries. bin_size:%u choice:%02x\n",
1118                                 new_group->num_rules, bin_size, choice - 1);
1119                 /* Restore groups modified to their previous state */
1120                 revert_groups(current_group, new_group, bin_size);
1121
1122 next_choice:
1123                 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1124                         break;
1125                 *new_bin_choice = choice;
1126                 *group_id = efd_bin_to_group[choice][*bin_id];
1127                 new_group = &chunk->group_rules[*group_id];
1128                 choice++;
1129         }
1130
1131         if (!found) {
1132                 current_group->num_rules--;
1133                 table->num_rules--;
1134         } else
1135                 current_group->value[current_group->num_rules - 1] =
1136                         key_changed_previous_value;
1137         return RTE_EFD_UPDATE_FAILED;
1138 }
1139
1140 int
1141 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1142                 const void *key, const efd_value_t value)
1143 {
1144         uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1145         uint8_t new_bin_choice = 0;
1146         struct efd_online_group_entry entry;
1147
1148         int status = efd_compute_update(table, socket_id, key, value,
1149                         &chunk_id, &group_id, &bin_id,
1150                         &new_bin_choice, &entry);
1151
1152         if (status == RTE_EFD_UPDATE_NO_CHANGE)
1153                 return EXIT_SUCCESS;
1154
1155         if (status == RTE_EFD_UPDATE_FAILED)
1156                 return status;
1157
1158         efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1159                         new_bin_choice, &entry);
1160         return status;
1161 }
1162
1163 int
1164 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1165                 const void *key, efd_value_t * const prev_value)
1166 {
1167         unsigned int i;
1168         uint32_t chunk_id, bin_id;
1169         uint8_t not_found = 1;
1170
1171         efd_compute_ids(table, key, &chunk_id, &bin_id);
1172
1173         struct efd_offline_chunk_rules * const chunk =
1174                         &table->offline_chunks[chunk_id];
1175
1176         uint8_t current_choice = efd_get_choice(table, socket_id,
1177                         chunk_id, bin_id);
1178         uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1179         struct efd_offline_group_rules * const current_group =
1180                         &chunk->group_rules[current_group_id];
1181
1182         /*
1183          * Search the current group for the specified key.
1184          * If it exists, remove it and re-pack the other values
1185          */
1186         for (i = 0; i < current_group->num_rules; i++) {
1187                 if (not_found) {
1188                         /* Found key that needs to be removed */
1189                         if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1190                                         key, table->key_len) == 0) {
1191                                 /* Store previous value if requested by caller */
1192                                 if (prev_value != NULL)
1193                                         *prev_value = current_group->value[i];
1194
1195                                 not_found = 0;
1196                                 rte_ring_sp_enqueue(table->free_slots,
1197                                         (void *)((uintptr_t)current_group->key_idx[i]));
1198                         }
1199                 } else {
1200                         /*
1201                          * If the desired key has been found,
1202                          * need to shift other values up one
1203                          */
1204
1205                         /* Need to shift this entry back up one index */
1206                         current_group->key_idx[i - 1] = current_group->key_idx[i];
1207                         current_group->value[i - 1] = current_group->value[i];
1208                         current_group->bin_id[i - 1] = current_group->bin_id[i];
1209                 }
1210         }
1211
1212         if (not_found == 0) {
1213                 table->num_rules--;
1214                 current_group->num_rules--;
1215         }
1216
1217         return not_found;
1218 }
1219
1220 static inline efd_value_t
1221 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1222                 const efd_lookuptbl_t *group_lookup_table,
1223                 const uint32_t hash_val_a, const uint32_t hash_val_b)
1224 {
1225         efd_value_t value = 0;
1226         uint32_t i;
1227
1228         for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1229                 value <<= 1;
1230                 uint32_t h = hash_val_a + (hash_val_b *
1231                         group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1232                 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1233                 value |= (group_lookup_table[
1234                                 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1235                                 bucket_idx) & 0x1;
1236         }
1237
1238         return value;
1239 }
1240
1241
1242 static inline efd_value_t
1243 efd_lookup_internal(const struct efd_online_group_entry * const group,
1244                 const uint32_t hash_val_a, const uint32_t hash_val_b,
1245                 enum efd_lookup_internal_function lookup_fn)
1246 {
1247         efd_value_t value = 0;
1248
1249         switch (lookup_fn) {
1250
1251 #if defined(RTE_ARCH_X86) && defined(CC_SUPPORT_AVX2)
1252         case EFD_LOOKUP_AVX2:
1253                 return efd_lookup_internal_avx2(group->hash_idx,
1254                                         group->lookup_table,
1255                                         hash_val_a,
1256                                         hash_val_b);
1257                 break;
1258 #endif
1259 #if defined(RTE_ARCH_ARM64)
1260         case EFD_LOOKUP_NEON:
1261                 return efd_lookup_internal_neon(group->hash_idx,
1262                                         group->lookup_table,
1263                                         hash_val_a,
1264                                         hash_val_b);
1265                 break;
1266 #endif
1267         case EFD_LOOKUP_SCALAR:
1268         /* Fall-through */
1269         default:
1270                 return efd_lookup_internal_scalar(group->hash_idx,
1271                                         group->lookup_table,
1272                                         hash_val_a,
1273                                         hash_val_b);
1274         }
1275
1276         return value;
1277 }
1278
1279 efd_value_t
1280 rte_efd_lookup(const struct rte_efd_table * const table,
1281                 const unsigned int socket_id, const void *key)
1282 {
1283         uint32_t chunk_id, group_id, bin_id;
1284         uint8_t bin_choice;
1285         const struct efd_online_group_entry *group;
1286         const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1287
1288         /* Determine the chunk and group location for the given key */
1289         efd_compute_ids(table, key, &chunk_id, &bin_id);
1290         bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1291         group_id = efd_bin_to_group[bin_choice][bin_id];
1292         group = &chunks[chunk_id].groups[group_id];
1293
1294         return efd_lookup_internal(group,
1295                         EFD_HASHFUNCA(key, table),
1296                         EFD_HASHFUNCB(key, table),
1297                         table->lookup_fn);
1298 }
1299
1300 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1301                 const unsigned int socket_id, const int num_keys,
1302                 const void **key_list, efd_value_t * const value_list)
1303 {
1304         int i;
1305         uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1306         uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1307         uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1308         uint32_t group_id_list[RTE_EFD_BURST_MAX];
1309         struct efd_online_group_entry *group;
1310
1311         struct efd_online_chunk *chunks = table->chunks[socket_id];
1312
1313         for (i = 0; i < num_keys; i++) {
1314                 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1315                                 &bin_id_list[i]);
1316                 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1317         }
1318
1319         for (i = 0; i < num_keys; i++) {
1320                 bin_choice_list[i] = efd_get_choice(table, socket_id,
1321                                 chunk_id_list[i], bin_id_list[i]);
1322                 group_id_list[i] =
1323                                 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1324                 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1325                 rte_prefetch0(group);
1326         }
1327
1328         for (i = 0; i < num_keys; i++) {
1329                 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1330                 value_list[i] = efd_lookup_internal(group,
1331                                 EFD_HASHFUNCA(key_list[i], table),
1332                                 EFD_HASHFUNCB(key_list[i], table),
1333                                 table->lookup_fn);
1334         }
1335 }