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