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