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