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_free(te);
 715         rte_efd_free(table);
 716
 717         return NULL;
 718 }
 719
 720 struct rte_efd_table *
 721 rte_efd_find_existing(const char *name)
 722 {
 723         struct rte_efd_table *table = NULL;
 724         struct rte_tailq_entry *te;
 725         struct rte_efd_list *efd_list;
 726
 727         efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
 728
 729         rte_mcfg_tailq_read_lock();
 730
 731         TAILQ_FOREACH(te, efd_list, next)
 732         {
 733                 table = (struct rte_efd_table *) te->data;
 734                 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
 735                         break;
 736         }
 737         rte_mcfg_tailq_read_unlock();
 738
 739         if (te == NULL) {
 740                 rte_errno = ENOENT;
 741                 return NULL;
 742         }
 743         return table;
 744 }
 745
 746 void
 747 rte_efd_free(struct rte_efd_table *table)
 748 {
 749         uint8_t socket_id;
 750         struct rte_efd_list *efd_list;
 751         struct rte_tailq_entry *te, *temp;
 752
 753         if (table == NULL)
 754                 return;
 755
 756         for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
 757                 rte_free(table->chunks[socket_id]);
 758
 759         efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
 760         rte_mcfg_tailq_write_lock();
 761
 762         TAILQ_FOREACH_SAFE(te, efd_list, next, temp) {
 763                 if (te->data == (void *) table) {
 764                         TAILQ_REMOVE(efd_list, te, next);
 765                         rte_free(te);
 766                         break;
 767                 }
 768         }
 769
 770         rte_mcfg_tailq_write_unlock();
 771         rte_ring_free(table->free_slots);
 772         rte_free(table->offline_chunks);
 773         rte_free(table->keys);
 774         rte_free(table);
 775 }
 776
 777 /**
 778  * Applies a previously computed table entry to the specified table for all
 779  * socket-local copies of the online table.
 780  * Intended to apply an update for only a single change
 781  * to a key/value pair at a time
 782  *
 783  * @param table
 784  *   EFD table to reference
 785  * @param socket_id
 786  *   Socket ID to use to lookup existing values (ideally caller's socket id)
 787  * @param chunk_id
 788  *   Chunk index to update
 789  * @param group_id
 790  *   Group index to update
 791  * @param bin_id
 792  *   Bin within the group that this update affects
 793  * @param new_bin_choice
 794  *   Newly chosen permutation which this bin should use - only lower 2 bits
 795  * @param new_group_entry
 796  *   Previously computed updated chunk/group entry
 797  */
 798 static inline void
 799 efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
 800                 const uint32_t chunk_id, const uint32_t group_id,
 801                 const uint32_t bin_id, const uint8_t new_bin_choice,
 802                 const struct efd_online_group_entry * const new_group_entry)
 803 {
 804         int i;
 805         struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
 806         uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
 807
 808         /*
 809          * Grab the current byte that contains the choices
 810          * for four neighboring bins
 811          */
 812         uint8_t choice_chunk =
 813                         chunk->bin_choice_list[bin_index];
 814
 815
 816         /* Compute the offset into the chunk that needs to be updated */
 817         int offset = (bin_id & 0x3) * 2;
 818
 819         /* Zero the two bits of interest and set them to new_bin_choice */
 820         choice_chunk = (choice_chunk & (~(0x03 << offset)))
 821                         | ((new_bin_choice & 0x03) << offset);
 822
 823         /* Update the online table with the new data across all sockets */
 824         for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
 825                 if (table->chunks[i] != NULL) {
 826                         memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
 827                                         new_group_entry,
 828                                         sizeof(struct efd_online_group_entry));
 829                         table->chunks[i][chunk_id].bin_choice_list[bin_index] =
 830                                         choice_chunk;
 831                 }
 832         }
 833 }
 834
 835 /*
 836  * Move the bin from prev group to the new group
 837  */
 838 static inline void
 839 move_groups(uint32_t bin_id, uint8_t bin_size,
 840                 struct efd_offline_group_rules *new_group,
 841                 struct efd_offline_group_rules * const current_group)
 842 {
 843
 844         uint8_t empty_idx = 0;
 845         unsigned int i;
 846
 847         if (new_group == current_group)
 848                 return;
 849
 850         for (i = 0; i < current_group->num_rules; i++) {
 851                 /*
 852                  * Move keys that belong to the same bin
 853                  * to the new group
 854                  */
 855                 if (current_group->bin_id[i] == bin_id) {
 856                         new_group->key_idx[new_group->num_rules] =
 857                                         current_group->key_idx[i];
 858                         new_group->value[new_group->num_rules] =
 859                                         current_group->value[i];
 860                         new_group->bin_id[new_group->num_rules] =
 861                                         current_group->bin_id[i];
 862                         new_group->num_rules++;
 863                 } else {
 864                         if (i != empty_idx) {
 865                                 /*
 866                                  * Need to move this key towards
 867                                  * the top of the array
 868                                  */
 869                                 current_group->key_idx[empty_idx] =
 870                                                 current_group->key_idx[i];
 871                                 current_group->value[empty_idx] =
 872                                                 current_group->value[i];
 873                                 current_group->bin_id[empty_idx] =
 874                                                 current_group->bin_id[i];
 875                         }
 876                         empty_idx++;
 877                 }
 878
 879         }
 880         current_group->num_rules -= bin_size;
 881 }
 882
 883 /*
 884  * Revert group/s to their previous state before
 885  * trying to insert/add a new key
 886  */
 887 static inline void
 888 revert_groups(struct efd_offline_group_rules *previous_group,
 889                 struct efd_offline_group_rules *current_group, uint8_t bin_size)
 890 {
 891         unsigned int i;
 892
 893         if (current_group == previous_group)
 894                 return;
 895
 896         /* Move keys back to previous group */
 897         for (i = current_group->num_rules - bin_size;
 898                         i < current_group->num_rules; i++) {
 899                 previous_group->key_idx[previous_group->num_rules] =
 900                                 current_group->key_idx[i];
 901                 previous_group->value[previous_group->num_rules] =
 902                                 current_group->value[i];
 903                 previous_group->bin_id[previous_group->num_rules] =
 904                                 current_group->bin_id[i];
 905                 previous_group->num_rules++;
 906         }
 907
 908         /*
 909          * Decrease number of rules after the move
 910          * in the new group
 911          */
 912         current_group->num_rules -= bin_size;
 913 }
 914
 915 /**
 916  * Computes an updated table entry where the supplied key points to a new host.
 917  * If no entry exists, one is inserted.
 918  *
 919  * This function does NOT modify the online table(s)
 920  * This function DOES modify the offline table
 921  *
 922  * @param table
 923  *   EFD table to reference
 924  * @param socket_id
 925  *   Socket ID to use to lookup existing values (ideally caller's socket id)
 926  * @param key
 927  *   Key to insert
 928  * @param value
 929  *   Value to associate with key
 930  * @param chunk_id
 931  *   Chunk ID of the chunk that was modified
 932  * @param group_id
 933  *   Group ID of the group that was modified
 934  * @param bin_id
 935  *   Bin ID that was modified
 936  * @param new_bin_choice
 937  *   Newly chosen permutation which this bin will use
 938  * @param entry
 939  *   Newly computed online entry to apply later with efd_apply_update
 940  *
 941  * @return
 942  *   RTE_EFD_UPDATE_WARN_GROUP_FULL
 943  *     Operation is insert, and the last available space in the
 944  *     key's group was just used. Future inserts may fail as groups fill up.
 945  *     This operation was still successful, and entry contains a valid update
 946  *   RTE_EFD_UPDATE_FAILED
 947  *     Either the EFD failed to find a suitable perfect hash or the group was full
 948  *     This is a fatal error, and the table is now in an indeterminate state
 949  *   RTE_EFD_UPDATE_NO_CHANGE
 950  *     Operation resulted in no change to the table (same value already exists)
 951  *   0
 952  *     Insert or update was successful, and the new efd_online_group_entry
 953  *     is stored in *entry
 954  *
 955  * @warning
 956  *   Note that entry will be UNCHANGED if the update has no effect, and thus any
 957  *   subsequent use of the entry content will likely be invalid
 958  */
 959 static inline int
 960 efd_compute_update(struct rte_efd_table * const table,
 961                 const unsigned int socket_id, const void *key,
 962                 const efd_value_t value, uint32_t * const chunk_id,
 963                 uint32_t * const group_id, uint32_t * const bin_id,
 964                 uint8_t * const new_bin_choice,
 965                 struct efd_online_group_entry * const entry)
 966 {
 967         unsigned int i;
 968         int ret;
 969         uint32_t new_idx;
 970         void *new_k, *slot_id = NULL;
 971         int status = EXIT_SUCCESS;
 972         unsigned int found = 0;
 973
 974         efd_compute_ids(table, key, chunk_id, bin_id);
 975
 976         struct efd_offline_chunk_rules * const chunk =
 977                         &table->offline_chunks[*chunk_id];
 978         struct efd_offline_group_rules *new_group;
 979
 980         uint8_t current_choice = efd_get_choice(table, socket_id,
 981                         *chunk_id, *bin_id);
 982         uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
 983         struct efd_offline_group_rules * const current_group =
 984                         &chunk->group_rules[current_group_id];
 985         uint8_t bin_size = 0;
 986         uint8_t key_changed_index = 0;
 987         efd_value_t key_changed_previous_value = 0;
 988         uint32_t key_idx_previous = 0;
 989
 990         /* Scan the current group and see if the key is already present */
 991         for (i = 0; i < current_group->num_rules; i++) {
 992                 if (current_group->bin_id[i] == *bin_id)
 993                         bin_size++;
 994                 else
 995                         continue;
 996
 997                 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
 998                 if (found == 0 && unlikely(memcmp(key_stored, key,
 999                                 table->key_len) == 0)) {
1000                         /* Key is already present */
1001
1002                         /*
1003                          * If previous value is same as new value,
1004                          * no additional work is required
1005                          */
1006                         if (current_group->value[i] == value)
1007                                 return RTE_EFD_UPDATE_NO_CHANGE;
1008
1009                         key_idx_previous = current_group->key_idx[i];
1010                         key_changed_previous_value = current_group->value[i];
1011                         key_changed_index = i;
1012                         current_group->value[i] = value;
1013                         found = 1;
1014                 }
1015         }
1016
1017         if (found == 0) {
1018                 /* Key does not exist. Insert the rule into the bin/group */
1019                 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1020                         RTE_LOG(ERR, EFD,
1021                                         "Fatal: No room remaining for insert into "
1022                                         "chunk %u group %u bin %u\n",
1023                                         *chunk_id,
1024                                         current_group_id, *bin_id);
1025                         return RTE_EFD_UPDATE_FAILED;
1026                 }
1027
1028                 if (unlikely(current_group->num_rules ==
1029                                 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1030                         RTE_LOG(INFO, EFD, "Warn: Insert into last "
1031                                         "available slot in chunk %u "
1032                                         "group %u bin %u\n", *chunk_id,
1033                                         current_group_id, *bin_id);
1034                         status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1035                 }
1036
1037                 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1038                         return RTE_EFD_UPDATE_FAILED;
1039
1040                 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1041                                         table->key_len);
1042                 rte_prefetch0(new_k);
1043                 new_idx = (uint32_t) ((uintptr_t) slot_id);
1044
1045                 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1046                 current_group->key_idx[current_group->num_rules] = new_idx;
1047                 current_group->value[current_group->num_rules] = value;
1048                 current_group->bin_id[current_group->num_rules] = *bin_id;
1049                 current_group->num_rules++;
1050                 table->num_rules++;
1051                 bin_size++;
1052         } else {
1053                 uint32_t last = current_group->num_rules - 1;
1054                 /* Swap the key with the last key inserted*/
1055                 current_group->key_idx[key_changed_index] =
1056                                 current_group->key_idx[last];
1057                 current_group->value[key_changed_index] =
1058                                 current_group->value[last];
1059                 current_group->bin_id[key_changed_index] =
1060                                 current_group->bin_id[last];
1061
1062                 /*
1063                  * Key to be updated will always be available
1064                  * at the end of the group
1065                  */
1066                 current_group->key_idx[last] = key_idx_previous;
1067                 current_group->value[last] = value;
1068                 current_group->bin_id[last] = *bin_id;
1069         }
1070
1071         *new_bin_choice = current_choice;
1072         *group_id = current_group_id;
1073         new_group = current_group;
1074
1075         /* Group need to be rebalanced when it starts to get loaded */
1076         if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1077
1078                 /*
1079                  * Subtract the number of entries in the bin from
1080                  * the original group
1081                  */
1082                 current_group->num_rules -= bin_size;
1083
1084                 /*
1085                  * Figure out which of the available groups that this bin
1086                  * can map to is the smallest (using the current group
1087                  * as baseline)
1088                  */
1089                 uint8_t smallest_choice = current_choice;
1090                 uint8_t smallest_size = current_group->num_rules;
1091                 uint32_t smallest_group_id = current_group_id;
1092                 unsigned char choice;
1093
1094                 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1095                                 choice++) {
1096                         uint32_t test_group_id =
1097                                         efd_bin_to_group[choice][*bin_id];
1098                         uint32_t num_rules =
1099                                         chunk->group_rules[test_group_id].num_rules;
1100                         if (num_rules < smallest_size) {
1101                                 smallest_choice = choice;
1102                                 smallest_size = num_rules;
1103                                 smallest_group_id = test_group_id;
1104                         }
1105                 }
1106
1107                 *new_bin_choice = smallest_choice;
1108                 *group_id = smallest_group_id;
1109                 new_group = &chunk->group_rules[smallest_group_id];
1110                 current_group->num_rules += bin_size;
1111
1112         }
1113
1114         uint8_t choice = 0;
1115         for (;;) {
1116                 if (current_group != new_group &&
1117                                 new_group->num_rules + bin_size >
1118                                         EFD_MAX_GROUP_NUM_RULES) {
1119                         RTE_LOG(DEBUG, EFD,
1120                                         "Unable to move_groups to dest group "
1121                                         "containing %u entries."
1122                                         "bin_size:%u choice:%02x\n",
1123                                         new_group->num_rules, bin_size,
1124                                         choice - 1);
1125                         goto next_choice;
1126                 }
1127                 move_groups(*bin_id, bin_size, new_group, current_group);
1128                 /*
1129                  * Recompute the hash function for the modified group,
1130                  * and return it to the caller
1131                  */
1132                 ret = efd_search_hash(table, new_group, entry);
1133
1134                 if (!ret)
1135                         return status;
1136
1137                 RTE_LOG(DEBUG, EFD,
1138                                 "Failed to find perfect hash for group "
1139                                 "containing %u entries. bin_size:%u choice:%02x\n",
1140                                 new_group->num_rules, bin_size, choice - 1);
1141                 /* Restore groups modified to their previous state */
1142                 revert_groups(current_group, new_group, bin_size);
1143
1144 next_choice:
1145                 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1146                         break;
1147                 *new_bin_choice = choice;
1148                 *group_id = efd_bin_to_group[choice][*bin_id];
1149                 new_group = &chunk->group_rules[*group_id];
1150                 choice++;
1151         }
1152
1153         if (!found) {
1154                 current_group->num_rules--;
1155                 table->num_rules--;
1156         } else
1157                 current_group->value[current_group->num_rules - 1] =
1158                         key_changed_previous_value;
1159         return RTE_EFD_UPDATE_FAILED;
1160 }
1161
1162 int
1163 rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1164                 const void *key, const efd_value_t value)
1165 {
1166         uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1167         uint8_t new_bin_choice = 0;
1168         struct efd_online_group_entry entry;
1169
1170         int status = efd_compute_update(table, socket_id, key, value,
1171                         &chunk_id, &group_id, &bin_id,
1172                         &new_bin_choice, &entry);
1173
1174         if (status == RTE_EFD_UPDATE_NO_CHANGE)
1175                 return EXIT_SUCCESS;
1176
1177         if (status == RTE_EFD_UPDATE_FAILED)
1178                 return status;
1179
1180         efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1181                         new_bin_choice, &entry);
1182         return status;
1183 }
1184
1185 int
1186 rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1187                 const void *key, efd_value_t * const prev_value)
1188 {
1189         unsigned int i;
1190         uint32_t chunk_id, bin_id;
1191         uint8_t not_found = 1;
1192
1193         efd_compute_ids(table, key, &chunk_id, &bin_id);
1194
1195         struct efd_offline_chunk_rules * const chunk =
1196                         &table->offline_chunks[chunk_id];
1197
1198         uint8_t current_choice = efd_get_choice(table, socket_id,
1199                         chunk_id, bin_id);
1200         uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1201         struct efd_offline_group_rules * const current_group =
1202                         &chunk->group_rules[current_group_id];
1203
1204         /*
1205          * Search the current group for the specified key.
1206          * If it exists, remove it and re-pack the other values
1207          */
1208         for (i = 0; i < current_group->num_rules; i++) {
1209                 if (not_found) {
1210                         /* Found key that needs to be removed */
1211                         if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1212                                         key, table->key_len) == 0) {
1213                                 /* Store previous value if requested by caller */
1214                                 if (prev_value != NULL)
1215                                         *prev_value = current_group->value[i];
1216
1217                                 not_found = 0;
1218                                 rte_ring_sp_enqueue(table->free_slots,
1219                                         (void *)((uintptr_t)current_group->key_idx[i]));
1220                         }
1221                 } else {
1222                         /*
1223                          * If the desired key has been found,
1224                          * need to shift other values up one
1225                          */
1226
1227                         /* Need to shift this entry back up one index */
1228                         current_group->key_idx[i - 1] = current_group->key_idx[i];
1229                         current_group->value[i - 1] = current_group->value[i];
1230                         current_group->bin_id[i - 1] = current_group->bin_id[i];
1231                 }
1232         }
1233
1234         if (not_found == 0) {
1235                 table->num_rules--;
1236                 current_group->num_rules--;
1237         }
1238
1239         return not_found;
1240 }
1241
1242 static inline efd_value_t
1243 efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1244                 const efd_lookuptbl_t *group_lookup_table,
1245                 const uint32_t hash_val_a, const uint32_t hash_val_b)
1246 {
1247         efd_value_t value = 0;
1248         uint32_t i;
1249
1250         for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1251                 value <<= 1;
1252                 uint32_t h = hash_val_a + (hash_val_b *
1253                         group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1254                 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1255                 value |= (group_lookup_table[
1256                                 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1257                                 bucket_idx) & 0x1;
1258         }
1259
1260         return value;
1261 }
1262
1263
1264 static inline efd_value_t
1265 efd_lookup_internal(const struct efd_online_group_entry * const group,
1266                 const uint32_t hash_val_a, const uint32_t hash_val_b,
1267                 enum efd_lookup_internal_function lookup_fn)
1268 {
1269         efd_value_t value = 0;
1270
1271         switch (lookup_fn) {
1272
1273 #if defined(RTE_ARCH_X86) && defined(CC_SUPPORT_AVX2)
1274         case EFD_LOOKUP_AVX2:
1275                 return efd_lookup_internal_avx2(group->hash_idx,
1276                                         group->lookup_table,
1277                                         hash_val_a,
1278                                         hash_val_b);
1279                 break;
1280 #endif
1281 #if defined(RTE_ARCH_ARM64)
1282         case EFD_LOOKUP_NEON:
1283                 return efd_lookup_internal_neon(group->hash_idx,
1284                                         group->lookup_table,
1285                                         hash_val_a,
1286                                         hash_val_b);
1287                 break;
1288 #endif
1289         case EFD_LOOKUP_SCALAR:
1290         /* Fall-through */
1291         default:
1292                 return efd_lookup_internal_scalar(group->hash_idx,
1293                                         group->lookup_table,
1294                                         hash_val_a,
1295                                         hash_val_b);
1296         }
1297
1298         return value;
1299 }
1300
1301 efd_value_t
1302 rte_efd_lookup(const struct rte_efd_table * const table,
1303                 const unsigned int socket_id, const void *key)
1304 {
1305         uint32_t chunk_id, group_id, bin_id;
1306         uint8_t bin_choice;
1307         const struct efd_online_group_entry *group;
1308         const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1309
1310         /* Determine the chunk and group location for the given key */
1311         efd_compute_ids(table, key, &chunk_id, &bin_id);
1312         bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1313         group_id = efd_bin_to_group[bin_choice][bin_id];
1314         group = &chunks[chunk_id].groups[group_id];
1315
1316         return efd_lookup_internal(group,
1317                         EFD_HASHFUNCA(key, table),
1318                         EFD_HASHFUNCB(key, table),
1319                         table->lookup_fn);
1320 }
1321
1322 void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1323                 const unsigned int socket_id, const int num_keys,
1324                 const void **key_list, efd_value_t * const value_list)
1325 {
1326         int i;
1327         uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1328         uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1329         uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1330         uint32_t group_id_list[RTE_EFD_BURST_MAX];
1331         struct efd_online_group_entry *group;
1332
1333         struct efd_online_chunk *chunks = table->chunks[socket_id];
1334
1335         for (i = 0; i < num_keys; i++) {
1336                 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1337                                 &bin_id_list[i]);
1338                 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1339         }
1340
1341         for (i = 0; i < num_keys; i++) {
1342                 bin_choice_list[i] = efd_get_choice(table, socket_id,
1343                                 chunk_id_list[i], bin_id_list[i]);
1344                 group_id_list[i] =
1345                                 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1346                 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1347                 rte_prefetch0(group);
1348         }
1349
1350         for (i = 0; i < num_keys; i++) {
1351                 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1352                 value_list[i] = efd_lookup_internal(group,
1353                                 EFD_HASHFUNCA(key_list[i], table),
1354                                 EFD_HASHFUNCB(key_list[i], table),
1355                                 table->lookup_fn);
1356         }
1357 }