lib/librte_efd/rte_efd.c

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