From: Vladimir Medvedkin <medvedkinv@gmail.com>
To: Gleb Natapov <gleb@cloudius-systems.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>
Subject: Re: [dpdk-dev] [PATCH] Add toeplitz hash algorithm
Date: Thu, 9 Apr 2015 15:57:14 +0300 [thread overview]
Message-ID: <CANDrEHnrtjAnyX=jnCU+x4DE7D1iAxM2NyNQjwFFF-x9VqdriQ@mail.gmail.com> (raw)
In-Reply-To: <20150409063742.GA16818@cloudius-systems.com>
Hi Gleb,
2015-04-09 9:37 GMT+03:00 Gleb Natapov <gleb@cloudius-systems.com>:
> On Wed, Apr 08, 2015 at 03:06:13PM -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).
> >
> > Signed-off-by: Vladimir Medvedkin <medvedkinv@gmail.com>
> > ---
> > lib/librte_hash/Makefile | 1 +
> > lib/librte_hash/rte_thash.h | 179
> ++++++++++++++++++++++++++++++++++++++++++++
> > 2 files changed, 180 insertions(+)
> > create mode 100644 lib/librte_hash/rte_thash.h
> >
> > diff --git a/lib/librte_hash/Makefile b/lib/librte_hash/Makefile
> > index 3696cb1..083a9e5 100644
> > --- a/lib/librte_hash/Makefile
> > +++ b/lib/librte_hash/Makefile
> > @@ -50,6 +50,7 @@ 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_fbk_hash.h
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_thash.h
> >
> > # this lib needs eal
> > DEPDIRS-$(CONFIG_RTE_LIBRTE_HASH) += lib/librte_eal lib/librte_malloc
> > diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h
> > new file mode 100644
> > index 0000000..1acfa3a
> > --- /dev/null
> > +++ b/lib/librte_hash/rte_thash.h
> > @@ -0,0 +1,179 @@
> > +/*-
> > + * BSD LICENSE
> > + *
> > + * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
> > + * 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>
> > +
> > +enum rte_thash_flag {
> > + RTE_THASH_L3 = 0, //calculate hash tacking into account only
> l3 header
> > + RTE_THASH_L4 //calculate hash tacking into account l4 +
> l4 headers
> > +};
> > +
> > +/**
> > + * Prepare special converted key to use with rte_softrss_be()
> > + * @param orig
> > + * pointer to original RSS key
> > + * @param targ
> > + * pointer to target RSS key
> > + */
> > +
> > +static inline void
> > +rte_convert_rss_key(uint32_t *orig, uint32_t *targ)
> > +{
> > + int i;
> > + for (i = 0; i < 10; i++) {
> > + targ[i] = rte_be_to_cpu_32(orig[i]);
> > + }
> > +}
> > +
> > +/**
> > + * Generic implementation. Can be used with original rss_key
> > + * All ip's and ports have to be CPU byte order.
> > + * @param sip
> > + * Source ip address.
> > + * @param dip
> > + * Destination ip address.
> ipv4, what about ipv6? Why not define rss function that works on byte
> buffer and let caller build it according to whatever fields it want to
> hash?
>
Good idea, I will think about it.
>
> > + * @param sp
> > + * Source TCP|UDP port.
> > + * @param dp
> > + * Destination TCP|UDP port.
> > + * @param flag
> > + * RTE_THASH_L3: calculate hash tacking into account only sip and
> dip
> > + * RTE_THASH_L4: calculate hash tacking into account sip, dip, sp
> and dp
> > + * @param *rss_key
> > + * Pointer to 40-byte RSS hash key.
> i40e has 52 byte RSS hash key.
>
> > + * @return
> > + * Calculated hash value.
> > + */
> > +
> > +static inline uint32_t
> > +rte_softrss(uint32_t sip, uint32_t dip, uint16_t sp, uint16_t dp, enum
> rte_thash_flag flag, uint32_t *rss_key)
> > +{
> > + uint32_t ret = 0;
> > + int i;
> > + for (i = 0; i < 32; i++) {
> > + if (sip & (1 << (31 - i))) {
> > + ret ^= (rte_cpu_to_be_32(*rss_key) <<
> i)|(uint32_t)((uint64_t)(rte_cpu_to_be_32(*(rss_key + 1))) >> (32 - i));
> > + }
> > + }
> > + rss_key++;
> > + for (i = 0; i < 32; i++) {
> > + if (dip & (1 << (31 - i))) {
> > + ret ^= (rte_cpu_to_be_32(*rss_key) <<
> i)|(uint32_t)((uint64_t)(rte_cpu_to_be_32(*(rss_key + 1))) >> (32 - i));
> > + }
> > + }
> > + if (flag == RTE_THASH_L4) {
> > + rss_key++;
> > + for (i = 0; i < 32; i++) {
> > + if (((sp<<16)|dp) & (1 << (31 - i))) {
> > + ret ^= (rte_cpu_to_be_32(*rss_key) <<
> i)|(uint32_t)((uint64_t)(rte_cpu_to_be_32(*(rss_key + 1))) >> (32 - i));
> > + }
> > + }
> > + }
> > + return ret;
> > +}
> > +
> > +/**
> > + * Optimized implementation.
> > + * If you want the calculated hash value matches NIC RSS value
> > + * you have to use special converted key.
> > + * All ip's and ports have to be CPU byte order.
> > + * @param sip
> > + * Source ip address.
> > + * @param dip
> > + * Destination ip address.
> > + * @param sp
> > + * Source TCP|UDP port.
> > + * @param dp
> > + * Destination TCP|UDP port.
> > + * @param flag
> > + * RTE_THASH_L3: calculate hash tacking into account only sip and
> dip
> > + * RTE_THASH_L4: calculate hash tacking into account sip, dip, sp
> and dp
> > + * @param *rss_key
> > + * Pointer to 40-byte RSS hash key.
> > + * @return
> > + * Calculated hash value.
> > + */
> > +
> > +static inline uint32_t
> > +rte_softrss_be(uint32_t sip, uint32_t dip, uint16_t sp, uint16_t dp,
> enum rte_thash_flag flag, uint32_t *rss_key)
> > +{
> > + uint32_t ret = 0;
> > + int i;
> > + for (i = 0; i < 32; i++) {
> > + if (sip & (1 << (31 - i))) {
> > + ret ^= (*rss_key <<
> i)|(uint32_t)((uint64_t)*(rss_key + 1) >> (32 - i));
> > + }
> > + }
> > + rss_key++;
> > + for (i = 0; i < 32; i++) {
> > + if (dip & (1 << (31 - i))) {
> > + ret ^= (*rss_key <<
> i)|(uint32_t)((uint64_t)*(rss_key + 1) >> (32 - i));
> > + }
> > + }
> > + if (flag == RTE_THASH_L4) {
> > + rss_key++;
> > + for (i = 0; i < 32; i++) {
> > + if (((sp<<16)|dp) & (1 << (31 - i))) {
> > + ret ^= (*rss_key <<
> i)|(uint32_t)((uint64_t)*(rss_key + 1) >> (32 - i));
> > + }
> > + }
> > + }
> > + return ret;
> > +}
> > +
> > +#ifdef __cplusplus
> > +}
> > +#endif
> > +
> > +#endif /* _RTE_THASH_H */
> > --
> > 1.8.3.2
> >
>
> --
> Gleb.
>
next prev parent reply other threads:[~2015-04-09 12:57 UTC|newest]
Thread overview: 37+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-04-08 19:06 Vladimir Medvedkin
2015-04-08 22:24 ` Stephen Hemminger
2015-04-09 12:50 ` Vladimir Medvedkin
2015-04-09 6:37 ` Gleb Natapov
2015-04-09 12:57 ` Vladimir Medvedkin [this message]
2015-05-05 13:20 ` [dpdk-dev] [PATCH v2] Add toeplitz hash algorithm used by RSS Vladimir Medvedkin
2015-05-05 16:03 ` Chilikin, Andrey
2015-05-07 10:28 ` Vladimir Medvedkin
2015-05-07 11:38 ` Chilikin, Andrey
2015-05-08 14:58 ` Vladimir Medvedkin
2015-05-08 14:58 ` Vladimir Medvedkin
2015-06-03 14:07 ` Thomas Monjalon
2015-06-16 9:07 ` Thomas Monjalon
2015-06-16 10:36 ` Bruce Richardson
2015-06-16 12:29 ` Bruce Richardson
2015-06-16 19:26 ` Vladimir Medvedkin
2015-06-19 14:55 ` [dpdk-dev] [PATCH v4] " Vladimir Medvedkin
2015-06-19 15:59 ` Richardson, Bruce
2015-06-19 16:14 ` Vladimir Medvedkin
2015-06-29 12:18 ` Bruce Richardson
2015-06-19 16:33 ` Mcnamara, John
2015-06-19 17:31 ` [dpdk-dev] [PATCH v5] " Vladimir Medvedkin
2015-06-29 12:40 ` Bruce Richardson
2015-06-30 12:14 ` Vladimir Medvedkin
2015-06-30 12:48 ` Bruce Richardson
2015-06-30 23:40 ` [dpdk-dev] [PATCH v6] " Vladimir Medvedkin
2015-07-01 15:29 ` Bruce Richardson
2015-07-01 21:23 ` Thomas Monjalon
2015-07-22 7:55 ` Tony Lu
2015-07-27 11:57 ` Vladimir Medvedkin
2015-07-29 5:01 ` Qiu, Michael
2015-07-29 14:00 ` Vladimir Medvedkin
2015-06-19 17:32 ` [dpdk-dev] [PATCH v3] Add unit test for thash library Vladimir Medvedkin
2015-06-29 12:42 ` Bruce Richardson
2015-06-30 23:41 ` [dpdk-dev] [PATCH v4] " Vladimir Medvedkin
2015-07-01 15:30 ` Bruce Richardson
2015-07-01 21:28 ` Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CANDrEHnrtjAnyX=jnCU+x4DE7D1iAxM2NyNQjwFFF-x9VqdriQ@mail.gmail.com' \
--to=medvedkinv@gmail.com \
--cc=dev@dpdk.org \
--cc=gleb@cloudius-systems.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).