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