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