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 three functions that provide calculation of the Toeplitz hash sum:
  23
  24 * ``rte_softrss()``
  25 * ``rte_softrss_be()``
  26 * ``rte_thash_gfni()``
  27
  28 First two functions are scalar implementation and take the parameters:
  29
  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.
  33
  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.
  40
  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.
  44
  45 ``rte_thash_gfni()`` calculates the hash value for a single tuple
  46
  47 ``rte_thash_gfni()`` takes the parameters:
  48
  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.
  52
  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:
  55
  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.
  59
  60
  61 Predictable RSS
  62 ---------------
  63
  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.
  70
  71 For example:
  72
  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
  83   desired queue.
  84
  85 This functionality is provided by the API shown below.
  86 The API consists of 3 parts:
  87
  88 * Create the thash context.
  89
  90 * Create the thash helper, associated with a context.
  91
  92 * Use the helper run time to calculate the adjustable bits of the tuple to
  93   ensure a collision.
  94
  95
  96 Thash context
  97 ~~~~~~~~~~~~~
  98
  99 The function ``rte_thash_init_ctx()`` initializes the context struct
 100 associated with a particular NIC or a set of NICs. It expects:
 101
 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.
 105
 106 * A predefined RSS hash key. This is optional, if ``NULL`` then a random key
 107   will be initialized.
 108
 109 * The length of the RSS hash key. This value is usually hardware/driver
 110   specific and can be found in the NIC datasheet.
 111
 112 * Optional flags, as shown below.
 113
 114 Supported flags:
 115
 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.
 121
 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
 129   keys.
 130
 131
 132 Thash helper
 133 ~~~~~~~~~~~~
 134
 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.
 140
 141 It expects:
 142
 143 * A pointer to the Thash context to be associated with.
 144
 145 * A length of the subtuple to be modified. The length is counted in bits.
 146
 147 * An offset of the subtuple to be modified from the beginning of the tuple. It
 148   is also counted in bits.
 149
 150 .. note::
 151
 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
 154    required helpers.
 155
 156
 157 Calculation of the complementary bits to adjust the subtuple
 158 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 159
 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
 163 subtuple.
 164
 165 It expects:
 166
 167 * A corresponding helper created for a given subtuple of the tuple.
 168
 169 * A hash value of the tuple we want to alter.
 170
 171 * The desired LSB's of the hash value the user expects to have.
 172
 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``.
 176
 177
 178 Adjust tuple API
 179 ~~~~~~~~~~~~~~~~~
 180
 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.
 184
 185 It expects:
 186
 187 * A Thash context and helper.
 188
 189 * A pointer to the tuple to be changed.
 190
 191 * The length of the tuple.
 192
 193 * A callback function and its userdata to check the tuple after it has been
 194   changed.
 195
 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.
 199
 200
 201 Use case example
 202 ----------------
 203
 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.
 206
 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`:
 210
 211 .. _figure_predictable_snat_1:
 212
 213 .. figure:: img/predictable_snat_1.*
 214
 215    Bidirectional flow packets distribution in general
 216
 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:
 221
 222 * The connections table is global so locking/RCU on the flow insertion/removal
 223   is required.
 224
 225 * Connection metadata must be protected to avoid race conditions.
 226
 227 * More cache pressure if a single connection metadata is kept in different
 228   L1/L2 caches of a different CPU core.
 229
 230 * Cache pressure/less cache locality on packet handover to the different cores.
 231
 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`:
 235
 236 .. _figure_predictable_snat_2:
 237
 238 .. figure:: img/predictable_snat_2.*
 239
 240    Bidirectional flow packets distribution with predictable RSS
 241
 242
 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.
 246
 247 .. code-block:: c
 248
 249    int key_len = 40; /* The default Niantic RSS key length. */
 250
 251    /** The default Niantic RSS reta size = 2^7 entries, LSBs of hash value are
 252     *  used as an indexes in RSS ReTa. */
 253    int reta_sz = 7;
 254    int ret;
 255    struct rte_thash_ctx *ctx;
 256
 257    uint8_t initial_key[key_len] = {0}; /* Default empty key. */
 258
 259    /* Create and initialize a new thash context. */
 260    ctx = rte_thash_init_ctx("SNAT", key_len, reta_sz, initial_key, 0);
 261
 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.
 267     */
 268    ret = rte_thash_add_helper(ctx, "snat", sizeof(uint16_t) * 8,
 269                               offsetof(union rte_thash_tuple, v4.dport) * 8);
 270
 271    if (ret != 0)
 272        return ret;
 273
 274    /* Get handler of the required helper. */
 275    struct rte_thash_subtuple_helper *h = rte_thash_get_helper(ctx, "snat");
 276
 277    /** After calling rte_thash_add_helper() the initial_key passed on ctx
 278     *  creation has been changed so we get the new one.
 279     */
 280    uint8_t *new_key = rte_thash_get_key(ctx);
 281
 282    union rte_thash_tuple tuple, rev_tuple;
 283
 284    /* A complete tuple from the packet. */
 285    complete_tuple(mbuf, &tuple);
 286
 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);
 289
 290    /** Complete the reverse tuple by translating the SRC address and swapping
 291     *  src and dst addresses and ports.
 292     */
 293    get_rev_tuple(&rev_tuple, &tuple, new_ip);
 294
 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);
 297
 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);
 300
 301    /* Adjust the source port bits. */
 302    uint16_t new_sport = tuple.v4.sport ^ adj;
 303
 304    /* Make an actual packet translation. */
 305    do_snat(mbuf, new_ip, new_sport);