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