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