1 .. SPDX-License-Identifier: BSD-3-Clause
2 Copyright(c) 2021 Intel Corporation.
7 DPDK provides a Toeplitz Hash Library
8 to calculate the Toeplitz hash function and to use its properties.
9 The Toeplitz hash function is commonly used in a wide range of NICs
10 to calculate the RSS hash sum to spread the traffic among the queues.
12 .. _figure_rss_queue_assign:
14 .. figure:: img/rss_queue_assign.*
16 RSS queue assignment example
19 Toeplitz hash function API
20 --------------------------
22 There are three functions that provide calculation of the Toeplitz hash sum:
25 * ``rte_softrss_be()``
26 * ``rte_thash_gfni()``
28 First two functions are scalar implementation and take the parameters:
30 * A pointer to the tuple, containing fields extracted from the packet.
31 * A length of this tuple counted in double words.
32 * A pointer to the RSS hash key corresponding to the one installed on the NIC.
34 Both of above mentioned _softrss_ functions expect the tuple to be in
35 "host" byte order and a multiple of 4 bytes in length.
36 The ``rte_softrss()`` function expects the ``rss_key``
37 to be exactly the same as the one installed on the NIC.
38 The ``rte_softrss_be`` function is a faster implementation,
39 but it expects ``rss_key`` to be converted to the host byte order.
41 The last function is vectorized implementation using
42 Galois Fields New Instructions. Could be used if ``rte_thash_gfni_supported`` returns true.
43 It expects the tuple to be in network byte order.
45 ``rte_thash_gfni()`` calculates the hash value for a single tuple
47 ``rte_thash_gfni()`` takes the parameters:
49 * A pointer to the matrices derived from the RSS hash key using ``rte_thash_complete_matrix()``.
50 * A pointer to the tuple.
51 * A length of the tuple in bytes.
53 ``rte_thash_complete_matrix()`` is a function that calculates matrices required by
54 GFNI implementations from the RSS hash key. It takes the parameters:
56 * A pointer to the memory where the matrices will be written.
57 * A pointer to the RSS hash key.
58 * Length of the RSS hash key in bytes.
64 In some use cases it is useful to have a way to find partial collisions of the
65 Toeplitz hash function. In figure :numref:`figure_rss_queue_assign` only a few
66 of the least significant bits (LSB) of the hash value are used to indicate an
67 entry in the RSS Redirection Table (ReTa) and thus the index of the queue. So,
68 in this case it would be useful to find another tuple whose hash has the same
69 LSB's as the hash from the original tuple.
73 - In the case of SNAT (Source Network Address Translation) it is possible to
74 find a special source port number on translation so that the hash of
75 returning packets, of the given connection, will have desired LSB's.
76 - In the case of MPLS (Multiprotocol Label Switching), if the MPLS tag is used
77 in the hash calculation, the Label Switching router can allocate a special
78 MPLS tag to bind an LSP (Label Switching Path) to a given queue. This method
79 can be used with the allocation of IPSec SPI, VXLan VNI, etc., to bind the
80 tunnel to the desired queue.
81 - In the case of a TCP stack, a special source port could be chosen for
82 outgoing connections, such that the response packets will be assigned to the
85 This functionality is provided by the API shown below.
86 The API consists of 3 parts:
88 * Create the thash context.
90 * Create the thash helper, associated with a context.
92 * Use the helper run time to calculate the adjustable bits of the tuple to
99 The function ``rte_thash_init_ctx()`` initializes the context struct
100 associated with a particular NIC or a set of NICs. It expects:
102 * The log2 value of the size of the RSS redirection table for the
103 corresponding NIC. It reflects the number of least significant bits of the
104 hash value to produce a collision for.
106 * A predefined RSS hash key. This is optional, if ``NULL`` then a random key
109 * The length of the RSS hash key. This value is usually hardware/driver
110 specific and can be found in the NIC datasheet.
112 * Optional flags, as shown below.
116 * ``RTE_THASH_IGNORE_PERIOD_OVERFLOW`` - By default, and for security reasons,
117 the library prohibits generating a repeatable sequence in the hash key. This
118 flag disables such checking. The flag is mainly used for testing in the lab
119 to generate an RSS hash key with a uniform hash distribution, if the input
120 traffic also has a uniform distribution.
122 * ``RTE_THASH_MINIMAL_SEQ`` - By default, the library generates a special bit
123 sequence in the hash key for all the bits of the subtuple. However, the
124 collision generation task requires only the ``log2(RETA_SZ)`` bits in the
125 subtuple. This flag forces the minimum bit sequence in the hash key to be
126 generated for the required ``log2(RETA_SZ)`` least significant bits of the
127 subtuple. The flag can be used in the case of a relatively large number of
128 helpers that may overlap with their corresponding bit sequences of RSS hash
135 The function ``rte_thash_add_helper()`` initializes the helper struct
136 associated with a given context and a part of a target tuple of interest which
137 could be altered to produce a hash collision. On success it writes a specially
138 calculated bit sequence into the RSS hash key which is stored in the context
139 and calculates a table with values to be XORed with a subtuple.
143 * A pointer to the Thash context to be associated with.
145 * A length of the subtuple to be modified. The length is counted in bits.
147 * An offset of the subtuple to be modified from the beginning of the tuple. It
148 is also counted in bits.
152 Adding a helper changes the key stored in the corresponding context. So the
153 updated RSS hash key must be uploaded into the NIC after creating all the
157 Calculation of the complementary bits to adjust the subtuple
158 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
160 The ``rte_thash_get_complement()`` function returns a special bit sequence
161 with length ``N = log2(rss_reta_sz)`` (for the ``rss_reta_sz`` provided at
162 context initialization) to be xored with N least significant bits of the
167 * A corresponding helper created for a given subtuple of the tuple.
169 * A hash value of the tuple we want to alter.
171 * The desired LSB's of the hash value the user expects to have.
173 After the returned bit sequence has been XORed with the subtuple, the resulted
174 LSB's of the new hash value, calculated from the altered tuple, will be the
175 same as in ``desired_hash``.
181 The ``rte_thash_get_complement()`` function is a user-friendly wrapper around
182 a number of other functions. It alters a passed tuple to meet the above
183 mentioned requirements around the desired hash LSB's.
187 * A Thash context and helper.
189 * A pointer to the tuple to be changed.
191 * The length of the tuple.
193 * A callback function and its userdata to check the tuple after it has been
196 * The number of attempts to change the tuple. Basically, it makes sense if
197 there is a callback and a limit on the number of attempts to change the
198 tuple, if the callback function returns an error.
204 There could be a number of different use cases, such as NAT, TCP stack, MPLS
205 tag allocation, etc. In the following we will consider a SNAT application.
207 Packets of a single bidirectional flow belonging to different directions can
208 end up being assigned to different queues and thus processed by different
209 lcores, as shown in :numref:`figure_predictable_snat_1`:
211 .. _figure_predictable_snat_1:
213 .. figure:: img/predictable_snat_1.*
215 Bidirectional flow packets distribution in general
217 That leads to a situation where the same packet flow can be shared between two
218 cores. Such a situation is not ideal from a performance perspective and
219 requires extra synchronization efforts that might lead to various performance
220 penalties, for example:
222 * The connections table is global so locking/RCU on the flow insertion/removal
225 * Connection metadata must be protected to avoid race conditions.
227 * More cache pressure if a single connection metadata is kept in different
228 L1/L2 caches of a different CPU core.
230 * Cache pressure/less cache locality on packet handover to the different cores.
232 We can avoid all these penalties if it can be guaranteed that packets
233 belonging to one bidirectional flow will be assigned to the same queue, as
234 shown in :numref:`figure_predictable_snat_2`:
236 .. _figure_predictable_snat_2:
238 .. figure:: img/predictable_snat_2.*
240 Bidirectional flow packets distribution with predictable RSS
243 To achieve this in a SNAT scenario it is possible to choose a source port not
244 randomly, but using the predictable RSS library to produce a partial hash
245 collision. This is shown in the code below.
249 int key_len = 40; /* The default Niantic RSS key length. */
251 /** The default Niantic RSS reta size = 2^7 entries, LSBs of hash value are
252 * used as an indexes in RSS ReTa. */
255 struct rte_thash_ctx *ctx;
257 uint8_t initial_key[key_len] = {0}; /* Default empty key. */
259 /* Create and initialize a new thash context. */
260 ctx = rte_thash_init_ctx("SNAT", key_len, reta_sz, initial_key, 0);
262 /** Add a helper and specify the variable tuple part and its length. In the
263 * SNAT case we want to choose a new source port on SNAT translation in a
264 * way that the reverse tuple will have the same LSBs as the original
265 * direction tuple so that the selected source port will be the
266 * destination port on reply.
268 ret = rte_thash_add_helper(ctx, "snat", sizeof(uint16_t) * 8,
269 offsetof(union rte_thash_tuple, v4.dport) * 8);
274 /* Get handler of the required helper. */
275 struct rte_thash_subtuple_helper *h = rte_thash_get_helper(ctx, "snat");
277 /** After calling rte_thash_add_helper() the initial_key passed on ctx
278 * creation has been changed so we get the new one.
280 uint8_t *new_key = rte_thash_get_key(ctx);
282 union rte_thash_tuple tuple, rev_tuple;
284 /* A complete tuple from the packet. */
285 complete_tuple(mbuf, &tuple);
287 /* Calculate the RSS hash or get it from mbuf->hash.rss. */
288 uint32_t orig_hash = rte_softrss((uint32_t *)&tuple, RTE_THASH_V4_L4_LEN, new_key);
290 /** Complete the reverse tuple by translating the SRC address and swapping
291 * src and dst addresses and ports.
293 get_rev_tuple(&rev_tuple, &tuple, new_ip);
295 /* Calculate the expected rss hash for the reverse tuple. */
296 uint32_t rev_hash = rte_softrss((uint32_t *)&rev_tuple, RTE_THASH_V4_L4_LEN, new_key);
298 /* Get the adjustment bits for the src port to get a new port. */
299 uint32_t adj = rte_thash_get_compliment(h, rev_hash, orig_hash);
301 /* Adjust the source port bits. */
302 uint16_t new_sport = tuple.v4.sport ^ adj;
304 /* Make an actual packet translation. */
305 do_snat(mbuf, new_ip, new_sport);