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