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