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