Re: [dpdk-dev] [PATCH v2] Add toeplitz hash algorithm used by RSS

[Vladimir Medvedkin <medvedkinv@gmail.com>]

Hi Bruce,

2015-06-16 15:29 GMT+03:00 Bruce Richardson <bruce.richardson@intel.com>:

> On Fri, May 08, 2015 at 10:58:12AM -0400, Vladimir Medvedkin wrote:
> > Software implementation of the Toeplitz hash function used by RSS.
> > Can be used either for packet distribution on single queue NIC
> > or for simulating of RSS computation on specific NIC (for example
> > after GRE header decapsulating).
> >
> > v3 changes
> > - Rework API to be more generic
> > - Add sctp_tag into tuple
> >
> > v2 changes
> > - Add ipv6 support
> > - Various style fixes
> >
> > Signed-off-by: Vladimir Medvedkin <medvedkinv@gmail.com>
>
> Hi Vladimir,
>
> first off, thanks for this patch, it looks like something we want into
> DPDK.
> However, as Thomas has already pointed out, I think we could really do with
> some unit tests for this code. As it stands right now, we don't even know
> if this
> header compiles, as the header file is not used by any C file in DPDK.
>
I'll try to make a unit test this week

>
> Some other comments are inline below.
>
> Regards,
> /Bruce
> > ---
> >  lib/librte_hash/Makefile    |   1 +
> >  lib/librte_hash/rte_thash.h | 207
> ++++++++++++++++++++++++++++++++++++++++++++
> >  2 files changed, 208 insertions(+)
> >  create mode 100644 lib/librte_hash/rte_thash.h
> >
> > diff --git a/lib/librte_hash/Makefile b/lib/librte_hash/Makefile
> > index 3696cb1..981230b 100644
> > --- a/lib/librte_hash/Makefile
> > +++ b/lib/librte_hash/Makefile
> > @@ -49,6 +49,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += rte_fbk_hash.c
> >  SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include := rte_hash.h
> >  SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_hash_crc.h
> >  SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_jhash.h
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_thash.h
> >  SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_fbk_hash.h
> >
> >  # this lib needs eal
> > diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h
> > new file mode 100644
> > index 0000000..5d5111b
> > --- /dev/null
> > +++ b/lib/librte_hash/rte_thash.h
> > @@ -0,0 +1,207 @@
> > +/*-
> > + *   BSD LICENSE
> > + *
> > + *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
>
> Date and copyright owner look to need update here.
>
> > + *   All rights reserved.
> > + *
> > + *   Redistribution and use in source and binary forms, with or without
> > + *   modification, are permitted provided that the following conditions
> > + *   are met:
> > + *
> > + *     * Redistributions of source code must retain the above copyright
> > + *       notice, this list of conditions and the following disclaimer.
> > + *     * Redistributions in binary form must reproduce the above
> copyright
> > + *       notice, this list of conditions and the following disclaimer in
> > + *       the documentation and/or other materials provided with the
> > + *       distribution.
> > + *     * Neither the name of Intel Corporation nor the names of its
> > + *       contributors may be used to endorse or promote products derived
> > + *       from this software without specific prior written permission.
> > + *
> > + *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
> > + *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
> > + *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
> FOR
> > + *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
> COPYRIGHT
> > + *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
> INCIDENTAL,
> > + *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
> > + *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
> USE,
> > + *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
> ANY
> > + *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> > + *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
> USE
> > + *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> DAMAGE.
> > + */
> > +
> > +#ifndef _RTE_THASH_H
> > +#define _RTE_THASH_H
> > +
> > +/**
> > + * @file
> > + *
> > + * toeplitz hash functions.
> > + */
> > +
> > +#ifdef __cplusplus
> > +extern "C" {
> > +#endif
> > +
> > +/**
> > + * Software implementation of the Toeplitz hash function used by RSS.
> > + * Can be used either for packet distribution on single queue NIC
> > + * or for simulating of RSS computation on specific NIC (for example
> > + * after GRE header decapsulating)
> > + */
> > +
> > +#include <stdint.h>
> > +#include <rte_byteorder.h>
> > +#include <rte_vect.h>
> > +
> > +#ifdef __SSE3__
> > +static const __m128i bswap_mask = {0x0405060700010203,
> 0x0C0D0E0F08090A0B};
> > +#endif
>
> I think a more descriptive name for this might help. Yes, it's a mask for
> byteswapping, but I think the name could do with being more descriptive. I
> see
> below it's used for IPv6 IP extraction, so maybe that could be put in the
> name
> somehow. A comment should also be added on what it is used for.
> Finally, since this is a public symbol in the including C file, it should
> have
> an rte_ prefix - or perhaps just an underscore prefix "_".
>
> I think rte_thash_ipv6_bswap_maskwill be more appropriate

> > +
> > +#define RTE_THASH_V4_L3       2      /*calculate hash of ipv4 header
> only*/
> > +#define RTE_THASH_V4_L4       3      /*calculate hash of ipv4 +
> transport headers*/
> > +#define RTE_THASH_V6_L3       8      /*calculate hash of ipv6 header
> only */
> > +#define RTE_THASH_V6_L4       9      /*calculate hash of ipv6 +
> transport headers */
> > +
>
> Are these #defines used anywhere? If not, they should be removed.
>
It can be used in code that uses this library.

>
> > +struct rte_ports {
> > +        uint16_t dport;
> > +        uint16_t sport;
> > +};
> > +
> > +union rte_thash_l4 {
> > +        struct          rte_ports ports;
> > +        uint32_t        sctp_tag;
> > +};
> > +
>
> Any reason for the rte_ports struct being separated out from the
> rte_thash_l4
> structure?
>
You're right, no reason, I'll make unnamed struct field.

>
> > +/**
> > + * IPv4 tuple
> > + * addreses and ports/sctp_tag have to be CPU byte order
> > + */
> > +struct rte_ipv4_tuple {
> > +     uint32_t        src_addr;
> > +     uint32_t        dst_addr;
> > +     union rte_thash_l4 l4;
> > +};
> > +
> > +/**
> > + * IPv6 tuple
> > + * Addresses have to be filled by rte_thash_load_v6_addr()
> > + * ports/sctp_tag have to be CPU byte order
> > + */
> > +struct rte_ipv6_tuple {
> > +     uint8_t         src_addr[16];
> > +     uint8_t         dst_addr[16];
> > +     union rte_thash_l4 l4;
> > +};
> > +
> > +union rte_thash_tuple {
> > +     struct rte_ipv4_tuple   v4;
> > +     struct rte_ipv6_tuple   v6;
> > +} __attribute__((aligned(16)));
> > +
>
> I can see the reason for these structure, but they are not actually used
> anywhere in the code below. Should some of the functions, e.g.
> load_v6_addr fn
> not use these as type parameters?
>
Agree

>
> > +/**
> > + * Prepare special converted key to use with rte_softrss_be()
> > + * @param orig
> > + *   pointer to original RSS key
> > + * @param targ
> > + *   pointer to target RSS key
> > + * @param len
> > + *   RSS key length
> > + */
> > +static inline void
> > +rte_convert_rss_key(const uint32_t *orig, uint32_t *targ, int len)
> > +{
> > +     int i;
> > +
> > +     for (i = 0; i < (len >> 2); i++) {
> > +             targ[i] = rte_be_to_cpu_32(orig[i]);
> > +     }
> > +}
> > +
> > +/**
> > + * Prepare and load IPv6 address
> > + * @param orig
> > + *   Pointer to ipv6 address inside ipv6_hdr
> > + * @param targ
> > + *   Pointer to ipv6 address inside rte_ipv6_tuple
> > + */
> > +static inline void
> > +rte_thash_load_v6_addr(const uint8_t *orig, uint8_t *targ)
>
> Why not take a struct ipv6_hdr (from ip.h) and struct rte_ipv6_tuple
> parameters
> directly, rather than uint8_t parameters to somewhere in the middle of the
> structures? Specifying that way allows the compile to check the user is
> doing
> things correctly.
>
Agree too. I think it shoul be like rte_thash_load_v6_addr(const struct
ipv6_hdr *orig, union rte_thash_tuple *targ)

>
> > +{
> > +#ifdef __SSE3__
>
> I actually think the minimum supported SSE instruction set level for DPDK
> is
> SSE3, so perhaps these #idefs could be removed.
>
> > +     __m128i ipv6 = _mm_loadu_si128((const __m128i *)orig);
> > +     *(__m128i *)targ = _mm_shuffle_epi8(ipv6, bswap_mask);
> > +#else
> > +     int i;
> > +
> > +     for (i = 0; i < 4; i++) {
> > +             *((uint32_t *)targ + i) =
> > +                     rte_be_to_cpu_32(*((const uint32_t *)orig + i));
> > +     }
> > +#endif
> > +}
> > +
> > +/**
> > + * Generic implementation. Can be used with original rss_key
> > + * @param input_tuple
> > + *   Pointer to input tuple
> > + * @param input_len
> > + *   Length of input_tuple in 4-bytes chunks
> > + * @param rss_key
> > + *   Pointer to RSS hash key.
> > + * @return
> > + *   Calculated hash value.
> > + */
> > +static inline uint32_t
> > +rte_softrss(uint32_t *input_tuple, uint32_t input_len,
> > +             const uint8_t *rss_key)
> > +{
> > +     uint32_t i, j, ret = 0;
> > +
> > +     for (j = 0; j < input_len; j++) {
> > +             for (i = 0; i < 32; i++) {
> > +                     if (input_tuple[j] & (1 << (31 - i))) {
> > +                             ret ^= rte_cpu_to_be_32(((const uint32_t
> *)rss_key)[j]) << i |
> > +
>  (uint32_t)((uint64_t)(rte_cpu_to_be_32(((const uint32_t *)rss_key)[j +
> 1])) >> (32 - i));
>
> Line is rather long and not terribly readable. Can it be split up into a
> number
> of easier to read statements (without affecting performance)?
>
I don't see how it can be done

>
> > +                     }
> > +             }
> > +     }
> > +     return ret;
> > +}
> > +
> > +/**
> > + * Optimized implementation.
> > + * If you want the calculated hash value matches NIC RSS value
> > + * you have to use special converted key.
>
> Put in reference to function used for the conversion.
> Can you also document when you might want to use this version over the
> previous one?
>
> > + * @param input_tuple
> > + *   Pointer to input tuple
> > + * @param input_len
> > + *   Length of input_tuple in 4-bytes chunks
> > + * @param *rss_key
> > + *   Pointer to RSS hash key.
> > + * @return
> > + *   Calculated hash value.
> > + */
> > +static inline uint32_t
> > +rte_softrss_be(uint32_t *input_tuple, uint32_t input_len,
> > +             const uint8_t *rss_key)
> > +{
> > +     uint32_t i, j, ret = 0;
> > +
> > +     for (j = 0; j < input_len; j++) {
> > +             for (i = 0; i < 32; i++) {
> > +                     if (input_tuple[j] & (1 << (31 - i))) {
> > +                             ret ^= ((const uint32_t *)rss_key)[j] << i
> |
> > +                                     (uint32_t)((uint64_t)(((const
> uint32_t *)rss_key)[j + 1]) >> (32 - i));
> > +                     }
> > +             }
> > +     }
> > +     return ret;
> > +}
> > +
> > +#ifdef __cplusplus
> > +}
> > +#endif
> > +
> > +#endif /* _RTE_THASH_H */
> > --
> > 1.8.3.2
> >
>