[PATCH v7 1/1] hash: add XOR32 hash function

[Medvedkin, Vladimir]

Hi Bili,

Please find just one nit below inlined

Apart from it LGTM

Acked-by: Vladimir Medvedkin <vladimir.medvedkin at intel.com>

On 20/06/2023 20:12, Bili Dong wrote:
> An XOR32 hash is needed in the Software Switch (SWX) Pipeline for its
> use case in P4. We implement it in this patch so it could be easily
> registered in the pipeline later.
>
> Signed-off-by: Bili Dong <qobilidop at gmail.com>
> ---
> v7:
> * Simplified byte ordering conversion logic. (re Vladimir Medvedkin <medvedkinv at gmail.com>)
> * Added test cases with hash key length = 3 (mod 4). (re Vladimir Medvedkin <medvedkinv at gmail.com>)
> * Adopted a better way to access bytes. (re Mattias Rönnblom <hofors at lysator.liu.se>)
> * Adopted RTE_PTR_ADD for pointer arithmetic. (re Mattias Rönnblom <hofors at lysator.liu.se>)
>
>   .mailmap                       |   1 +
>   app/test/test_hash_functions.c |  47 +++++++++++---
>   lib/hash/rte_hash_xor.h        | 109 +++++++++++++++++++++++++++++++++
>   3 files changed, 147 insertions(+), 10 deletions(-)
>   create mode 100644 lib/hash/rte_hash_xor.h
>
> diff --git a/.mailmap b/.mailmap
> index 8e3940a253..997d89388f 100644
> --- a/.mailmap
> +++ b/.mailmap
> @@ -164,6 +164,7 @@ Bernard Iremonger <bernard.iremonger at intel.com>
>   Bert van Leeuwen <bert.vanleeuwen at netronome.com>
>   Bhagyada Modali <bhagyada.modali at amd.com>
>   Bharat Mota <bmota at vmware.com>
> +Bili Dong <qobilidop at gmail.com>
>   Bill Hong <bhong at brocade.com>
>   Billy McFall <bmcfall at redhat.com>
>   Billy O'Mahony <billy.o.mahony at intel.com>
> diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
> index 76d51b6e71..61f1341cbc 100644
> --- a/app/test/test_hash_functions.c
> +++ b/app/test/test_hash_functions.c
> @@ -15,6 +15,7 @@
>   #include <rte_hash.h>
>   #include <rte_jhash.h>
>   #include <rte_hash_crc.h>
> +#include <rte_hash_xor.h>
>
>   #include "test.h"
>
> @@ -22,35 +23,48 @@
>    * Hash values calculated for key sizes from array "hashtest_key_lens"
>    * and for initial values from array "hashtest_initvals.
>    * Each key will be formed by increasing each byte by 1:
> - * e.g.: key size = 4, key = 0x03020100
> - *       key size = 8, key = 0x0706050403020100
> + * e.g.: key size = 4, key = 0x00010203
> + *       key size = 8, key = 0x0001020304050607
>    */
> -static uint32_t hash_values_jhash[2][12] = {{
> -	0x8ba9414b, 0xdf0d39c9,
> +static uint32_t hash_values_jhash[2][14] = {{
> +	0x8ba9414b, 0xdf0d39c9, 0x6b12f277, 0x589511d8,
>   	0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe,
>   	0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816,
>   	0x12926a31, 0x1c9fa888
>   },
>   {
> -	0x5c62c303, 0x1b8cf784,
> +	0x5c62c303, 0x1b8cf784, 0x455e19f7, 0x785de928,
>   	0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f,
>   	0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494,
>   	0x91d0e462, 0x768087fc
>   }
>   };
> -static uint32_t hash_values_crc[2][12] = {{
> -	0x00000000, 0xf26b8303,
> +static uint32_t hash_values_crc[2][14] = {{
> +	0x00000000, 0xf26b8303, 0xf299e880, 0x18678721,
>   	0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4,
>   	0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e,
>   	0x43f44466, 0x4a11475e
>   },
>   {
> -	0xbdfd3980, 0x70204542,
> +	0xbdfd3980, 0x70204542, 0x410b3df9, 0xe3f8b2f1,
>   	0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c,
>   	0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539,
>   	0x789c104f, 0x53028d3e
>   }
>   };
> +static uint32_t hash_values_xor32[2][14] = {{
> +	0x00000000, 0x00010000, 0x00010200, 0x4040403,
> +	0x00010203, 0x04040404, 0x00000000, 0x00000000,
> +	0x00000000, 0x00000000, 0x0c040404, 0x000d0e0f,
> +	0x04212223, 0x04040404
> +},
> +{
> +	0xdeadbeef, 0xdeacbeef, 0xdeacbcef, 0xdaa9baec,
> +	0xdeacbcec, 0xdaa9baeb, 0xdeadbeef, 0xdeadbeef,
> +	0xdeadbeef, 0xdeadbeef, 0xd2a9baeb, 0xdea0b0e0,
> +	0xda8c9ccc, 0xdaa9baeb
> +}
> +};
>
>   /*******************************************************************************
>    * Hash function performance test configuration section. Each performance test
> @@ -61,10 +75,10 @@ static uint32_t hash_values_crc[2][12] = {{
>    */
>   #define HASHTEST_ITERATIONS 1000000
>   #define MAX_KEYSIZE 64
> -static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
> +static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hash_xor32};
>   static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
>   static uint32_t hashtest_key_lens[] = {
> -	1, 2,                 /* Unusual key sizes */
> +	1, 2, 3, 7,           /* Unusual key sizes */
>   	4, 8, 16, 32, 48, 64, /* standard key sizes */
>   	9,                    /* IPv4 SRC + DST + protocol, unpadded */
>   	13,                   /* IPv4 5-tuple, unpadded */
> @@ -85,6 +99,9 @@ get_hash_name(rte_hash_function f)
>   	if (f == rte_hash_crc)
>   		return "rte_hash_crc";
>
> +	if (f == rte_hash_xor32)
> +		return "rte_hash_xor32";
> +
>   	return "UnknownHash";
>   }
>
> @@ -173,6 +190,16 @@ verify_precalculated_hash_func_tests(void)
>   				       hash_values_crc[j][i], hash);
>   				return -1;
>   			}
> +
> +			hash = rte_hash_xor32(key, hashtest_key_lens[i],
> +					hashtest_initvals[j]);
> +			if (hash != hash_values_xor32[j][i]) {
> +				printf("XOR32 for %u bytes with initial value 0x%x."
> +				       " Expected 0x%x, but got 0x%x\n",
> +				       hashtest_key_lens[i], hashtest_initvals[j],
> +				       hash_values_xor32[j][i], hash);
> +				return -1;
> +			}
>   		}
>   	}
>
> diff --git a/lib/hash/rte_hash_xor.h b/lib/hash/rte_hash_xor.h
> new file mode 100644
> index 0000000000..7bc0953716
> --- /dev/null
> +++ b/lib/hash/rte_hash_xor.h
> @@ -0,0 +1,109 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2023 Intel Corporation
> + */
> +
> +#ifndef _RTE_HASH_XOR_H_
> +#define _RTE_HASH_XOR_H_
> +
> +/**
> + * @file
> + *
> + * RTE XOR Hash
> + */
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include <stdint.h>
> +
> +#include <rte_byteorder.h>
> +#include <rte_common.h>
> +
> +/**
> + * The following bytes access helper functions are expected to work
> + * without any particular input buffer alignment requirements.
> + */
> +
> +static inline uint64_t
> +rte_hash_access64(const void *data)
> +{
> +	uint64_t v;
> +	memcpy(&v, data, sizeof(v));
> +	return v;
> +}
> +
> +static inline uint32_t
> +rte_hash_access32(const void *data)
> +{
> +	uint32_t v;
> +	memcpy(&v, data, sizeof(v));
> +	return v;
> +}
> +
> +static inline uint16_t
> +rte_hash_access16(const void *data)
> +{
> +	uint16_t v;
> +	memcpy(&v, data, sizeof(v));
> +	return v;
> +}
> +
> +static inline uint8_t
> +rte_hash_access8(const void *data)
> +{
> +	uint8_t v;
> +	memcpy(&v, data, sizeof(v));
> +	return v;
> +}

I don't think this function is necessary.


> +
> +/**
> + * Calculate XOR32 hash on user-supplied byte array.
> + *
> + * @param data
> + *   Data to perform hash on.
> + * @param data_len
> + *   How many bytes to use to calculate hash value.
> + * @param init_val
> + *   Value to initialise hash generator.
> + * @return
> + *   32bit calculated hash value.
> + */
> +static inline uint32_t
> +rte_hash_xor32(const void *data, uint32_t data_len, uint32_t init_val)
> +{
> +	uint32_t hash32 = init_val;
> +	uint64_t hash64 = 0;
> +
> +	/* Batch process in 8 bytes for better performance. */
> +	uint32_t i;
> +	for (i = 0; i < data_len / 8; i++) {
> +		hash64 ^= rte_hash_access64(data);
> +		data = RTE_PTR_ADD(data, 8);
> +	}
> +
> +	if (data_len & 0x4) {
> +		hash64 ^= rte_hash_access32(data);
> +		data = RTE_PTR_ADD(data, 4);
> +	}
> +
> +	/* Deal with remaining (< 4) bytes. */
> +	uint8_t bit_offset = 0;
> +	if (data_len & 0x2) {
> +		hash64 ^= rte_hash_access16(data);
> +		data = RTE_PTR_ADD(data, 2);
> +		bit_offset += 16;
> +
> +	}
> +	if (data_len & 0x1)
> +		hash64 ^= rte_hash_access8(data) << bit_offset;
> +
> +	hash32 ^= rte_be_to_cpu_32((uint32_t)hash64 ^ (hash64 >> 32));
> +	return hash32;
> +}
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_HASH_XOR_H_ */
> --
> 2.41.0.162.gfafddb0af9-goog
>
-- 
Regards,
Vladimir