1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2015-2019 Vladimir Medvedkin <medvedkinv@gmail.com> 3 * Copyright(c) 2021 Intel Corporation 4 */ 5 6 #ifndef _RTE_THASH_H 7 #define _RTE_THASH_H 8 9 /** 10 * @file 11 * 12 * Software implementation of the Toeplitz hash function used by RSS. 13 * Can be used either for packet distribution on single queue NIC 14 * or for simulating of RSS computation on specific NIC (for example 15 * after GRE header decapsulating) 16 */ 17 18 #include <stdint.h> 19 20 #include <rte_byteorder.h> 21 #include <rte_ip.h> 22 #include <rte_common.h> 23 #include <rte_thash_gfni.h> 24 25 #if defined(RTE_ARCH_X86) || defined(__ARM_NEON) 26 #include <rte_vect.h> 27 #endif 28 29 #ifdef __cplusplus 30 extern "C" { 31 #endif 32 33 #ifdef RTE_ARCH_X86 34 /* Byte swap mask used for converting IPv6 address 35 * 4-byte chunks to CPU byte order 36 */ 37 static const __m128i rte_thash_ipv6_bswap_mask = { 38 0x0405060700010203ULL, 0x0C0D0E0F08090A0BULL}; 39 #endif 40 41 /** 42 * length in dwords of input tuple to 43 * calculate hash of ipv4 header only 44 */ 45 #define RTE_THASH_V4_L3_LEN ((sizeof(struct rte_ipv4_tuple) - \ 46 sizeof(((struct rte_ipv4_tuple *)0)->sctp_tag)) / 4) 47 48 /** 49 * length in dwords of input tuple to 50 * calculate hash of ipv4 header + 51 * transport header 52 */ 53 #define RTE_THASH_V4_L4_LEN ((sizeof(struct rte_ipv4_tuple)) / 4) 54 55 /** 56 * length in dwords of input tuple to 57 * calculate hash of ipv6 header only 58 */ 59 #define RTE_THASH_V6_L3_LEN ((sizeof(struct rte_ipv6_tuple) - \ 60 sizeof(((struct rte_ipv6_tuple *)0)->sctp_tag)) / 4) 61 62 /** 63 * length in dwords of input tuple to 64 * calculate hash of ipv6 header + 65 * transport header 66 */ 67 #define RTE_THASH_V6_L4_LEN ((sizeof(struct rte_ipv6_tuple)) / 4) 68 69 /** 70 * IPv4 tuple 71 * addresses and ports/sctp_tag have to be CPU byte order 72 */ 73 struct rte_ipv4_tuple { 74 uint32_t src_addr; 75 uint32_t dst_addr; 76 union { 77 struct { 78 uint16_t dport; 79 uint16_t sport; 80 }; 81 uint32_t sctp_tag; 82 }; 83 }; 84 85 /** 86 * IPv6 tuple 87 * Addresses have to be filled by rte_thash_load_v6_addr() 88 * ports/sctp_tag have to be CPU byte order 89 */ 90 struct rte_ipv6_tuple { 91 struct rte_ipv6_addr src_addr; 92 struct rte_ipv6_addr dst_addr; 93 union { 94 struct { 95 uint16_t dport; 96 uint16_t sport; 97 }; 98 uint32_t sctp_tag; 99 }; 100 }; 101 102 #ifdef RTE_ARCH_X86 103 union __rte_aligned(XMM_SIZE) rte_thash_tuple { 104 #else 105 union rte_thash_tuple { 106 #endif 107 struct rte_ipv4_tuple v4; 108 struct rte_ipv6_tuple v6; 109 }; 110 111 /** @internal 112 * @brief Generates a random polynomial 113 * 114 * @param poly_degree 115 * degree of the polynomial 116 * 117 * @return 118 * random polynomial 119 */ 120 __rte_internal 121 uint32_t 122 thash_get_rand_poly(uint32_t poly_degree); 123 124 /** 125 * Prepare special converted key to use with rte_softrss_be() 126 * @param orig 127 * pointer to original RSS key 128 * @param targ 129 * pointer to target RSS key 130 * @param len 131 * RSS key length 132 */ 133 static inline void 134 rte_convert_rss_key(const uint32_t *orig, uint32_t *targ, int len) 135 { 136 int i; 137 138 for (i = 0; i < (len >> 2); i++) 139 targ[i] = rte_be_to_cpu_32(orig[i]); 140 } 141 142 /** 143 * Prepare and load IPv6 addresses (src and dst) 144 * into target tuple 145 * @param orig 146 * Pointer to ipv6 header of the original packet 147 * @param targ 148 * Pointer to rte_ipv6_tuple structure 149 */ 150 static inline void 151 rte_thash_load_v6_addrs(const struct rte_ipv6_hdr *orig, 152 union rte_thash_tuple *targ) 153 { 154 #ifdef RTE_ARCH_X86 155 __m128i ipv6 = _mm_loadu_si128((const __m128i *)&orig->src_addr); 156 *(__m128i *)&targ->v6.src_addr = 157 _mm_shuffle_epi8(ipv6, rte_thash_ipv6_bswap_mask); 158 ipv6 = _mm_loadu_si128((const __m128i *)&orig->dst_addr); 159 *(__m128i *)&targ->v6.dst_addr = 160 _mm_shuffle_epi8(ipv6, rte_thash_ipv6_bswap_mask); 161 #elif defined(__ARM_NEON) 162 uint8x16_t ipv6 = vld1q_u8(orig->src_addr.a); 163 vst1q_u8(targ->v6.src_addr.a, vrev32q_u8(ipv6)); 164 ipv6 = vld1q_u8(orig->dst_addr.a); 165 vst1q_u8(targ->v6.dst_addr.a, vrev32q_u8(ipv6)); 166 #else 167 int i; 168 for (i = 0; i < 4; i++) { 169 *((uint32_t *)&targ->v6.src_addr + i) = 170 rte_be_to_cpu_32(*((const uint32_t *)&orig->src_addr + i)); 171 *((uint32_t *)&targ->v6.dst_addr + i) = 172 rte_be_to_cpu_32(*((const uint32_t *)&orig->dst_addr + i)); 173 } 174 #endif 175 } 176 177 /** 178 * Generic implementation. Can be used with original rss_key 179 * @param input_tuple 180 * Pointer to input tuple 181 * @param input_len 182 * Length of input_tuple in 4-bytes chunks 183 * @param rss_key 184 * Pointer to RSS hash key. 185 * @return 186 * Calculated hash value. 187 */ 188 static inline uint32_t 189 rte_softrss(uint32_t *input_tuple, uint32_t input_len, 190 const uint8_t *rss_key) 191 { 192 uint32_t i, j, map, ret = 0; 193 194 for (j = 0; j < input_len; j++) { 195 for (map = input_tuple[j]; map; map &= (map - 1)) { 196 i = rte_bsf32(map); 197 ret ^= rte_cpu_to_be_32(((const uint32_t *)rss_key)[j]) << (31 - i) | 198 (uint32_t)((uint64_t)(rte_cpu_to_be_32(((const uint32_t *)rss_key)[j + 1])) >> 199 (i + 1)); 200 } 201 } 202 return ret; 203 } 204 205 /** 206 * Optimized implementation. 207 * If you want the calculated hash value matches NIC RSS value 208 * you have to use special converted key with rte_convert_rss_key() fn. 209 * @param input_tuple 210 * Pointer to input tuple 211 * @param input_len 212 * Length of input_tuple in 4-bytes chunks 213 * @param *rss_key 214 * Pointer to RSS hash key. 215 * @return 216 * Calculated hash value. 217 */ 218 static inline uint32_t 219 rte_softrss_be(uint32_t *input_tuple, uint32_t input_len, 220 const uint8_t *rss_key) 221 { 222 uint32_t i, j, map, ret = 0; 223 224 for (j = 0; j < input_len; j++) { 225 for (map = input_tuple[j]; map; map &= (map - 1)) { 226 i = rte_bsf32(map); 227 ret ^= ((const uint32_t *)rss_key)[j] << (31 - i) | 228 (uint32_t)((uint64_t)(((const uint32_t *)rss_key)[j + 1]) >> (i + 1)); 229 } 230 } 231 return ret; 232 } 233 234 /** 235 * Indicates if GFNI implementations of the Toeplitz hash are supported. 236 * 237 * @return 238 * 1 if GFNI is supported 239 * 0 otherwise 240 */ 241 int 242 rte_thash_gfni_supported(void); 243 244 /** 245 * Converts Toeplitz hash key (RSS key) into matrixes required 246 * for GFNI implementation 247 * 248 * @param matrixes 249 * pointer to the memory where matrices will be written. 250 * Note: the size of this memory must be equal to size * 8 251 * @param rss_key 252 * pointer to the Toeplitz hash key 253 * @param size 254 * Size of the rss_key in bytes. 255 */ 256 void 257 rte_thash_complete_matrix(uint64_t *matrixes, const uint8_t *rss_key, 258 int size); 259 260 /** @internal Logarithm of minimum size of the RSS ReTa */ 261 #define RTE_THASH_RETA_SZ_MIN 2U 262 /** @internal Logarithm of maximum size of the RSS ReTa */ 263 #define RTE_THASH_RETA_SZ_MAX 16U 264 265 /** 266 * LFSR will ignore if generated m-sequence has more than 2^n -1 bits, 267 * where n is the logarithm of the RSS ReTa size. 268 */ 269 #define RTE_THASH_IGNORE_PERIOD_OVERFLOW 0x1 270 /** 271 * Generate minimal required bit (equal to ReTa LSB) sequence into 272 * the hash_key 273 */ 274 #define RTE_THASH_MINIMAL_SEQ 0x2 275 276 /** @internal thash context structure. */ 277 struct rte_thash_ctx; 278 /** @internal thash helper structure. */ 279 struct rte_thash_subtuple_helper; 280 281 /** 282 * Create a new thash context. 283 * 284 * @param name 285 * Context name 286 * @param key_len 287 * Length of the toeplitz hash key 288 * @param reta_sz 289 * Logarithm of the NIC's Redirection Table (ReTa) size, 290 * i.e. number of the LSBs if the hash used to determine 291 * the reta entry. 292 * @param key 293 * Pointer to the key used to init an internal key state. 294 * Could be NULL, in this case internal key will be inited with random. 295 * @param flags 296 * Supported flags are: 297 * RTE_THASH_IGNORE_PERIOD_OVERFLOW 298 * RTE_THASH_MINIMAL_SEQ 299 * @return 300 * A pointer to the created context on success 301 * NULL otherwise 302 */ 303 struct rte_thash_ctx * 304 rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz, 305 uint8_t *key, uint32_t flags); 306 307 /** 308 * Find an existing thash context and return a pointer to it. 309 * 310 * @param name 311 * Name of the thash context 312 * @return 313 * Pointer to the thash context or NULL if it was not found with rte_errno 314 * set appropriately. Possible rte_errno values include: 315 * - ENOENT - required entry not available to return. 316 */ 317 struct rte_thash_ctx * 318 rte_thash_find_existing(const char *name); 319 320 /** 321 * Free a thash context object 322 * 323 * @param ctx 324 * Thash context 325 */ 326 void 327 rte_thash_free_ctx(struct rte_thash_ctx *ctx); 328 329 /** 330 * Add a special properties to the toeplitz hash key inside a thash context. 331 * Creates an internal helper struct which has a complementary table 332 * to calculate toeplitz hash collisions. 333 * This function is not multi-thread safe. 334 * 335 * @param ctx 336 * Thash context 337 * @param name 338 * Name of the helper 339 * @param len 340 * Length in bits of the target subtuple 341 * Must be no shorter than reta_sz passed on rte_thash_init_ctx(). 342 * @param offset 343 * Offset in bits of the subtuple 344 * @return 345 * 0 on success 346 * negative on error 347 */ 348 int 349 rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len, 350 uint32_t offset); 351 352 /** 353 * Find a helper in the context by the given name 354 * 355 * @param ctx 356 * Thash context 357 * @param name 358 * Name of the helper 359 * @return 360 * Pointer to the thash helper or NULL if it was not found. 361 */ 362 struct rte_thash_subtuple_helper * 363 rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name); 364 365 /** 366 * Get a complementary value for the subtuple to produce a 367 * partial toeplitz hash collision. It must be XOR'ed with the 368 * subtuple to produce the hash value with the desired hash LSB's 369 * This function is multi-thread safe. 370 * 371 * @param h 372 * Pointer to the helper struct 373 * @param hash 374 * Toeplitz hash value calculated for the given tuple 375 * @param desired_hash 376 * Desired hash value to find a collision for 377 * @return 378 * A complementary value which must be xored with the corresponding subtuple 379 */ 380 uint32_t 381 rte_thash_get_complement(struct rte_thash_subtuple_helper *h, 382 uint32_t hash, uint32_t desired_hash); 383 384 /** 385 * Get a pointer to the toeplitz hash contained in the context. 386 * It changes after each addition of a helper. It should be installed to 387 * the NIC. 388 * 389 * @param ctx 390 * Thash context 391 * @return 392 * A pointer to the toeplitz hash key 393 */ 394 const uint8_t * 395 rte_thash_get_key(struct rte_thash_ctx *ctx); 396 397 /** 398 * Get a pointer to the toeplitz hash matrices contained in the context. 399 * These matrices could be used with fast toeplitz hash implementation if 400 * CPU supports GFNI. 401 * Matrices changes after each addition of a helper. 402 * 403 * @param ctx 404 * Thash context 405 * @return 406 * A pointer to the toeplitz hash key matrices on success 407 * NULL if GFNI is not supported. 408 */ 409 const uint64_t * 410 rte_thash_get_gfni_matrices(struct rte_thash_ctx *ctx); 411 412 /** 413 * Function prototype for the rte_thash_adjust_tuple 414 * to check if adjusted tuple could be used. 415 * Generally it is some kind of lookup function to check 416 * if adjusted tuple is already in use. 417 * 418 * @param userdata 419 * Pointer to the userdata. It could be a pointer to the 420 * table with used tuples to search. 421 * @param tuple 422 * Pointer to the tuple to check 423 * 424 * @return 425 * 1 on success 426 * 0 otherwise 427 */ 428 typedef int (*rte_thash_check_tuple_t)(void *userdata, uint8_t *tuple); 429 430 /** 431 * Adjusts tuple in the way to make Toeplitz hash has 432 * desired least significant bits. 433 * This function is multi-thread safe. 434 * 435 * @param ctx 436 * Thash context 437 * @param h 438 * Pointer to the helper struct 439 * @param tuple 440 * Pointer to the tuple to be adjusted 441 * @param tuple_len 442 * Length of the tuple. Must be multiple of 4. 443 * @param desired_value 444 * Desired value of least significant bits of the hash 445 * @param attempts 446 * Number of attempts to adjust tuple with fn() calling 447 * @param fn 448 * Callback function to check adjusted tuple. Could be NULL 449 * @param userdata 450 * Pointer to the userdata to be passed to fn(). Could be NULL 451 * 452 * @return 453 * 0 on success 454 * negative otherwise 455 */ 456 int 457 rte_thash_adjust_tuple(struct rte_thash_ctx *ctx, 458 struct rte_thash_subtuple_helper *h, 459 uint8_t *tuple, unsigned int tuple_len, 460 uint32_t desired_value, unsigned int attempts, 461 rte_thash_check_tuple_t fn, void *userdata); 462 463 /** 464 * @warning 465 * @b EXPERIMENTAL: this API may change without prior notice. 466 * 467 * Modify RSS hash key such that subtuple bits corresponding to `entropy_sz` 468 * bits starting from `entropy_start` will have the most even distribution with 469 * this key with a given ReTa size. 470 * 471 * @param key 472 * Pointer to the RSS hash key. 473 * @param key_len 474 * Length of the key. 475 * @param reta_sz_log 476 * Log2 of the size of RSS redirection table, 477 * i.e. number of bits of the RSS hash value used to identify RSS ReTa entry. 478 * @param entropy_start 479 * Bit offset from the beginning of the tuple 480 * where user expects best distribution of the subtuple values. 481 * @param entropy_sz 482 * Size in bits of the part of subtuple. 483 * 484 * @return 485 * 0 on success negative otherwise 486 */ 487 __rte_experimental 488 int 489 rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_log, 490 uint32_t entropy_start, size_t entropy_sz); 491 492 #ifdef __cplusplus 493 } 494 #endif 495 496 #endif /* _RTE_THASH_H */ 497