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
  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 /** @internal Logarithm of minimum size of the RSS ReTa */
 223 #define RTE_THASH_RETA_SZ_MIN   2U
 224 /** @internal Logarithm of maximum size of the RSS ReTa */
 225 #define RTE_THASH_RETA_SZ_MAX   16U
 226
 227 /**
 228  * LFSR will ignore if generated m-sequence has more than 2^n -1 bits,
 229  * where n is the logarithm of the RSS ReTa size.
 230  */
 231 #define RTE_THASH_IGNORE_PERIOD_OVERFLOW        0x1
 232 /**
 233  * Generate minimal required bit (equal to ReTa LSB) sequence into
 234  * the hash_key
 235  */
 236 #define RTE_THASH_MINIMAL_SEQ                   0x2
 237
 238 /** @internal thash context structure. */
 239 struct rte_thash_ctx;
 240 /** @internal thash helper structure. */
 241 struct rte_thash_subtuple_helper;
 242
 243 /**
 244  * Create a new thash context.
 245  *
 246  * @warning
 247  * @b EXPERIMENTAL: this API may change without prior notice.
 248  *
 249  * @param name
 250  *  Context name
 251  * @param key_len
 252  *  Length of the toeplitz hash key
 253  * @param reta_sz
 254  *  Logarithm of the NIC's Redirection Table (ReTa) size,
 255  *  i.e. number of the LSBs if the hash used to determine
 256  *  the reta entry.
 257  * @param key
 258  *  Pointer to the key used to init an internal key state.
 259  *  Could be NULL, in this case internal key will be inited with random.
 260  * @param flags
 261  *  Supported flags are:
 262  *   RTE_THASH_IGNORE_PERIOD_OVERFLOW
 263  *   RTE_THASH_MINIMAL_SEQ
 264  * @return
 265  *  A pointer to the created context on success
 266  *  NULL otherwise
 267  */
 268 __rte_experimental
 269 struct rte_thash_ctx *
 270 rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz,
 271         uint8_t *key, uint32_t flags);
 272
 273 /**
 274  * Find an existing thash context and return a pointer to it.
 275  *
 276  * @warning
 277  * @b EXPERIMENTAL: this API may change without prior notice.
 278  *
 279  * @param name
 280  *  Name of the thash context
 281  * @return
 282  *  Pointer to the thash context or NULL if it was not found with rte_errno
 283  *  set appropriately. Possible rte_errno values include:
 284  *   - ENOENT - required entry not available to return.
 285  */
 286 __rte_experimental
 287 struct rte_thash_ctx *
 288 rte_thash_find_existing(const char *name);
 289
 290 /**
 291  * Free a thash context object
 292  *
 293  * @warning
 294  * @b EXPERIMENTAL: this API may change without prior notice.
 295  *
 296  * @param ctx
 297  *  Thash context
 298  * @return
 299  *  None
 300  */
 301 __rte_experimental
 302 void
 303 rte_thash_free_ctx(struct rte_thash_ctx *ctx);
 304
 305 /**
 306  * Add a special properties to the toeplitz hash key inside a thash context.
 307  * Creates an internal helper struct which has a complementary table
 308  * to calculate toeplitz hash collisions.
 309  * This function is not multi-thread safe.
 310  *
 311  * @warning
 312  * @b EXPERIMENTAL: this API may change without prior notice.
 313  *
 314  * @param ctx
 315  *  Thash context
 316  * @param name
 317  *  Name of the helper
 318  * @param len
 319  *  Length in bits of the target subtuple
 320  *  Must be no shorter than reta_sz passed on rte_thash_init_ctx().
 321  * @param offset
 322  *  Offset in bits of the subtuple
 323  * @return
 324  *  0 on success
 325  *  negative on error
 326  */
 327 __rte_experimental
 328 int
 329 rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len,
 330         uint32_t offset);
 331
 332 /**
 333  * Find a helper in the context by the given name
 334  *
 335  * @warning
 336  * @b EXPERIMENTAL: this API may change without prior notice.
 337  *
 338  * @param ctx
 339  *  Thash context
 340  * @param name
 341  *  Name of the helper
 342  * @return
 343  *  Pointer to the thash helper or NULL if it was not found.
 344  */
 345 __rte_experimental
 346 struct rte_thash_subtuple_helper *
 347 rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name);
 348
 349 /**
 350  * Get a complementary value for the subtuple to produce a
 351  * partial toeplitz hash collision. It must be XOR'ed with the
 352  * subtuple to produce the hash value with the desired hash LSB's
 353  * This function is multi-thread safe.
 354  *
 355  * @param h
 356  *  Pointer to the helper struct
 357  * @param hash
 358  *  Toeplitz hash value calculated for the given tuple
 359  * @param desired_hash
 360  *  Desired hash value to find a collision for
 361  * @return
 362  *  A complementary value which must be xored with the corresponding subtuple
 363  */
 364 __rte_experimental
 365 uint32_t
 366 rte_thash_get_complement(struct rte_thash_subtuple_helper *h,
 367         uint32_t hash, uint32_t desired_hash);
 368
 369 /**
 370  * Get a pointer to the toeplitz hash contained in the context.
 371  * It changes after each addition of a helper. It should be installed to
 372  * the NIC.
 373  *
 374  * @warning
 375  * @b EXPERIMENTAL: this API may change without prior notice.
 376  *
 377  * @param ctx
 378  *  Thash context
 379  * @return
 380  *  A pointer to the toeplitz hash key
 381  */
 382 __rte_experimental
 383 const uint8_t *
 384 rte_thash_get_key(struct rte_thash_ctx *ctx);
 385
 386 /**
 387  * Function prototype for the rte_thash_adjust_tuple
 388  * to check if adjusted tuple could be used.
 389  * Generally it is some kind of lookup function to check
 390  * if adjusted tuple is already in use.
 391  *
 392  * @warning
 393  * @b EXPERIMENTAL: this API may change without prior notice.
 394  *
 395  * @param userdata
 396  *  Pointer to the userdata. It could be a pointer to the
 397  *  table with used tuples to search.
 398  * @param tuple
 399  *  Pointer to the tuple to check
 400  *
 401  * @return
 402  *  1 on success
 403  *  0 otherwise
 404  */
 405 typedef int (*rte_thash_check_tuple_t)(void *userdata, uint8_t *tuple);
 406
 407 /**
 408  * Adjusts tuple in the way to make Toeplitz hash has
 409  * desired least significant bits.
 410  * This function is multi-thread safe.
 411  *
 412  * @warning
 413  * @b EXPERIMENTAL: this API may change without prior notice.
 414  *
 415  * @param ctx
 416  *  Thash context
 417  * @param h
 418  *  Pointer to the helper struct
 419  * @param tuple
 420  *  Pointer to the tuple to be adjusted
 421  * @param tuple_len
 422  *  Length of the tuple. Must be multiple of 4.
 423  * @param desired_value
 424  *  Desired value of least significant bits of the hash
 425  * @param attempts
 426  *  Number of attempts to adjust tuple with fn() calling
 427  * @param fn
 428  *  Callback function to check adjusted tuple. Could be NULL
 429  * @param userdata
 430  *  Pointer to the userdata to be passed to fn(). Could be NULL
 431  *
 432  * @return
 433  *  0 on success
 434  *  negative otherwise
 435  */
 436 __rte_experimental
 437 int
 438 rte_thash_adjust_tuple(struct rte_thash_ctx *ctx,
 439         struct rte_thash_subtuple_helper *h,
 440         uint8_t *tuple, unsigned int tuple_len,
 441         uint32_t desired_value, unsigned int attempts,
 442         rte_thash_check_tuple_t fn, void *userdata);
 443
 444 #ifdef __cplusplus
 445 }
 446 #endif
 447
 448 #endif /* _RTE_THASH_H */