app/testpmd: add flow table management
[dpdk.git] / doc / guides / prog_guide / toeplitz_hash_lib.rst
1 ..  SPDX-License-Identifier: BSD-3-Clause
2     Copyright(c) 2021 Intel Corporation.
3
4 Toeplitz Hash Library
5 =====================
6
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.
11
12 .. _figure_rss_queue_assign:
13
14 .. figure:: img/rss_queue_assign.*
15
16    RSS queue assignment example
17
18
19 Toeplitz hash function API
20 --------------------------
21
22 There are four functions that provide calculation of the Toeplitz hash sum:
23
24 * ``rte_softrss()``
25 * ``rte_softrss_be()``
26 * ``rte_thash_gfni()``
27 * ``rte_thash_gfni_bulk()``
28
29 First two functions are scalar implementation and take the parameters:
30
31 * A pointer to the tuple, containing fields extracted from the packet.
32 * A length of this tuple counted in double words.
33 * A pointer to the RSS hash key corresponding to the one installed on the NIC.
34
35 Both of above mentioned _softrss_ functions expect the tuple to be in
36 "host" byte order and a multiple of 4 bytes in length.
37 The ``rte_softrss()`` function expects the ``rss_key``
38 to be exactly the same as the one installed on the NIC.
39 The ``rte_softrss_be`` function is a faster implementation,
40 but it expects ``rss_key`` to be converted to the host byte order.
41
42 The last two functions are vectorized implementations using
43 Galois Fields New Instructions. Could be used if ``rte_thash_gfni_supported`` is true.
44 They expect the tuple to be in network byte order.
45
46 ``rte_thash_gfni()`` calculates the hash value for a single tuple, and
47 ``rte_thash_gfni_bulk()`` bulk implementation of the rte_thash_gfni().
48
49 ``rte_thash_gfni()`` takes the parameters:
50
51 * A pointer to the matrices derived from the RSS hash key using ``rte_thash_complete_matrix()``.
52 * A pointer to the tuple.
53 * A length of the tuple in bytes.
54
55 ``rte_thash_gfni_bulk()`` takes the parameters:
56
57 * A pointer to the matrices derived from the RSS hash key using ``rte_thash_complete_matrix()``.
58 * A length of the longest tuple in bytes.
59 * Array of the pointers on data to be hashed.
60 * Array of ``uint32_t`` where to put calculated Toeplitz hash values
61 * Number of tuples in a bulk.
62
63 ``rte_thash_complete_matrix()`` is a function that calculates matrices required by
64 GFNI implementations from the RSS hash key. It takes the parameters:
65
66 * A pointer to the memory where the matrices will be written.
67 * A pointer to the RSS hash key.
68 * Length of the RSS hash key in bytes.
69
70
71 Predictable RSS
72 ---------------
73
74 In some use cases it is useful to have a way to find partial collisions of the
75 Toeplitz hash function. In figure :numref:`figure_rss_queue_assign` only a few
76 of the least significant bits (LSB) of the hash value are used to indicate an
77 entry in the RSS Redirection Table (ReTa) and thus the index of the queue. So,
78 in this case it would be useful to find another tuple whose hash has the same
79 LSB's as the hash from the original tuple.
80
81 For example:
82
83 - In the case of SNAT (Source Network Address Translation) it is possible to
84   find a special source port number on translation so that the hash of
85   returning packets, of the given connection, will have desired LSB's.
86 - In the case of MPLS (Multiprotocol Label Switching), if the MPLS tag is used
87   in the hash calculation, the Label Switching router can allocate a special
88   MPLS tag to bind an LSP (Label Switching Path) to a given queue. This method
89   can be used with the allocation of IPSec SPI, VXLan VNI, etc., to bind the
90   tunnel to the desired queue.
91 - In the case of a TCP stack, a special source port could be chosen for
92   outgoing connections, such that the response packets will be assigned to the
93   desired queue.
94
95 This functionality is provided by the API shown below.
96 The API consists of 3 parts:
97
98 * Create the thash context.
99
100 * Create the thash helper, associated with a context.
101
102 * Use the helper run time to calculate the adjustable bits of the tuple to
103   ensure a collision.
104
105
106 Thash context
107 ~~~~~~~~~~~~~
108
109 The function ``rte_thash_init_ctx()`` initializes the context struct
110 associated with a particular NIC or a set of NICs. It expects:
111
112 * The log2 value of the size of the RSS redirection table for the
113   corresponding NIC. It reflects the number of least significant bits of the
114   hash value to produce a collision for.
115
116 * A predefined RSS hash key. This is optional, if ``NULL`` then a random key
117   will be initialized.
118
119 * The length of the RSS hash key. This value is usually hardware/driver
120   specific and can be found in the NIC datasheet.
121
122 * Optional flags, as shown below.
123
124 Supported flags:
125
126 * ``RTE_THASH_IGNORE_PERIOD_OVERFLOW`` - By default, and for security reasons,
127   the library prohibits generating a repeatable sequence in the hash key. This
128   flag disables such checking. The flag is mainly used for testing in the lab
129   to generate an RSS hash key with a uniform hash distribution, if the input
130   traffic also has a uniform distribution.
131
132 * ``RTE_THASH_MINIMAL_SEQ`` - By default, the library generates a special bit
133   sequence in the hash key for all the bits of the subtuple. However, the
134   collision generation task requires only the ``log2(RETA_SZ)`` bits in the
135   subtuple. This flag forces the minimum bit sequence in the hash key to be
136   generated for the required ``log2(RETA_SZ)`` least significant bits of the
137   subtuple. The flag can be used in the case of a relatively large number of
138   helpers that may overlap with their corresponding bit sequences of RSS hash
139   keys.
140
141
142 Thash helper
143 ~~~~~~~~~~~~
144
145 The function ``rte_thash_add_helper()`` initializes the helper struct
146 associated with a given context and a part of a target tuple of interest which
147 could be altered to produce a hash collision. On success it writes a specially
148 calculated bit sequence into the RSS hash key which is stored in the context
149 and calculates a table with values to be XORed with a subtuple.
150
151 It expects:
152
153 * A pointer to the Thash context to be associated with.
154
155 * A length of the subtuple to be modified. The length is counted in bits.
156
157 * An offset of the subtuple to be modified from the beginning of the tuple. It
158   is also counted in bits.
159
160 .. note::
161
162    Adding a helper changes the key stored in the corresponding context. So the
163    updated RSS hash key must be uploaded into the NIC after creating all the
164    required helpers.
165
166
167 Calculation of the complementary bits to adjust the subtuple
168 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
169
170 The ``rte_thash_get_complement()`` function returns a special bit sequence
171 with length ``N = log2(rss_reta_sz)`` (for the ``rss_reta_sz`` provided at
172 context initialization) to be xored with N least significant bits of the
173 subtuple.
174
175 It expects:
176
177 * A corresponding helper created for a given subtuple of the tuple.
178
179 * A hash value of the tuple we want to alter.
180
181 * The desired LSB's of the hash value the user expects to have.
182
183 After the returned bit sequence has been XORed with the subtuple, the resulted
184 LSB's of the new hash value, calculated from the altered tuple, will be the
185 same as in ``desired_hash``.
186
187
188 Adjust tuple API
189 ~~~~~~~~~~~~~~~~~
190
191 The ``rte_thash_get_complement()`` function is a user-friendly wrapper around
192 a number of other functions. It alters a passed tuple to meet the above
193 mentioned requirements around the desired hash LSB's.
194
195 It expects:
196
197 * A Thash context and helper.
198
199 * A pointer to the tuple to be changed.
200
201 * The length of the tuple.
202
203 * A callback function and its userdata to check the tuple after it has been
204   changed.
205
206 * The number of attempts to change the tuple. Basically, it makes sense if
207   there is a callback and a limit on the number of attempts to change the
208   tuple, if the callback function returns an error.
209
210
211 Use case example
212 ----------------
213
214 There could be a number of different use cases, such as NAT, TCP stack, MPLS
215 tag allocation, etc. In the following we will consider a SNAT application.
216
217 Packets of a single bidirectional flow belonging to different directions can
218 end up being assigned to different queues and thus processed by different
219 lcores, as shown in :numref:`figure_predictable_snat_1`:
220
221 .. _figure_predictable_snat_1:
222
223 .. figure:: img/predictable_snat_1.*
224
225    Bidirectional flow packets distribution in general
226
227 That leads to a situation where the same packet flow can be shared between two
228 cores. Such a situation is not ideal from a performance perspective and
229 requires extra synchronization efforts that might lead to various performance
230 penalties, for example:
231
232 * The connections table is global so locking/RCU on the flow insertion/removal
233   is required.
234
235 * Connection metadata must be protected to avoid race conditions.
236
237 * More cache pressure if a single connection metadata is kept in different
238   L1/L2 caches of a different CPU core.
239
240 * Cache pressure/less cache locality on packet handover to the different cores.
241
242 We can avoid all these penalties if it can be guaranteed that packets
243 belonging to one bidirectional flow will be assigned to the same queue, as
244 shown in :numref:`figure_predictable_snat_2`:
245
246 .. _figure_predictable_snat_2:
247
248 .. figure:: img/predictable_snat_2.*
249
250    Bidirectional flow packets distribution with predictable RSS
251
252
253 To achieve this in a SNAT scenario it is possible to choose a source port not
254 randomly, but using the predictable RSS library to produce a partial hash
255 collision. This is shown in the code below.
256
257 .. code-block:: c
258
259    int key_len = 40; /* The default Niantic RSS key length. */
260
261    /** The default Niantic RSS reta size = 2^7 entries, LSBs of hash value are
262     *  used as an indexes in RSS ReTa. */
263    int reta_sz = 7;
264    int ret;
265    struct rte_thash_ctx *ctx;
266
267    uint8_t initial_key[key_len] = {0}; /* Default empty key. */
268
269    /* Create and initialize a new thash context. */
270    ctx = rte_thash_init_ctx("SNAT", key_len, reta_sz, initial_key, 0);
271
272    /** Add a helper and specify the variable tuple part and its length. In the
273     *  SNAT case we want to choose a new source port on SNAT translation in a
274     *  way that the reverse tuple will have the same LSBs as the original
275     *  direction tuple so that the selected source port will be the
276     *  destination port on reply.
277     */
278    ret = rte_thash_add_helper(ctx, "snat", sizeof(uint16_t) * 8,
279                               offsetof(union rte_thash_tuple, v4.dport) * 8);
280
281    if (ret != 0)
282        return ret;
283
284    /* Get handler of the required helper. */
285    struct rte_thash_subtuple_helper *h = rte_thash_get_helper(ctx, "snat");
286
287    /** After calling rte_thash_add_helper() the initial_key passed on ctx
288     *  creation has been changed so we get the new one.
289     */
290    uint8_t *new_key = rte_thash_get_key(ctx);
291
292    union rte_thash_tuple tuple, rev_tuple;
293
294    /* A complete tuple from the packet. */
295    complete_tuple(mbuf, &tuple);
296
297    /* Calculate the RSS hash or get it from mbuf->hash.rss. */
298    uint32_t orig_hash = rte_softrss((uint32_t *)&tuple, RTE_THASH_V4_L4_LEN, new_key);
299
300    /** Complete the reverse tuple by translating the SRC address and swapping
301     *  src and dst addresses and ports.
302     */
303    get_rev_tuple(&rev_tuple, &tuple, new_ip);
304
305    /* Calculate the expected rss hash for the reverse tuple. */
306    uint32_t rev_hash = rte_softrss((uint32_t *)&rev_tuple, RTE_THASH_V4_L4_LEN, new_key);
307
308    /* Get the adjustment bits for the src port to get a new port. */
309    uint32_t adj = rte_thash_get_compliment(h, rev_hash, orig_hash);
310
311    /* Adjust the source port bits. */
312    uint16_t new_sport = tuple.v4.sport ^ adj;
313
314    /* Make an actual packet translation. */
315    do_snat(mbuf, new_ip, new_sport);