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