lib/hash/rte_thash.h

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