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