[dpdk-dev] [PATCH] Add toeplitz hash algorithm

[Gleb Natapov]

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 at 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?

> + * @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.