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