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