[v9] hash: add XOR32 hash function

Message ID 20230710220003.1176400-1-qobilidop@gmail.com (mailing list archive)
State New
Delegated to: David Marchand
Headers
Series [v9] hash: add XOR32 hash function |

Checks

Context Check Description
ci/checkpatch success coding style OK
ci/loongarch-compilation success Compilation OK
ci/loongarch-unit-testing success Unit Testing PASS
ci/Intel-compilation success Compilation OK
ci/intel-Testing success Testing PASS
ci/github-robot: build success github build: passed
ci/iol-mellanox-Performance success Performance Testing PASS
ci/intel-Functional success Functional PASS
ci/iol-abi-testing success Testing PASS
ci/iol-aarch-unit-testing success Testing PASS
ci/iol-unit-testing success Testing PASS
ci/iol-broadcom-Performance success Performance Testing PASS
ci/iol-intel-Performance success Performance Testing PASS
ci/iol-aarch64-compile-testing success Testing PASS
ci/iol-x86_64-compile-testing success Testing PASS
ci/iol-testing success Testing PASS
ci/iol-x86_64-unit-testing success Testing PASS
ci/iol-broadcom-Functional success Functional Testing PASS
ci/iol-intel-Functional success Functional Testing PASS

Commit Message

Bili Dong July 10, 2023, 9:59 p.m. UTC
  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@gmail.com>
---
v9:
* Marked internl helper functions as @internal. (re Stephen Hemminger <stephen@networkplumber.org>)

v8:
* Removed unnecessary helper function. (re Vladimir Medvedkin <vladimir.medvedkin@intel.com>)

v7:
* Simplified byte ordering conversion logic. (re Vladimir Medvedkin <medvedkinv@gmail.com>)
* Added test cases with hash key length = 3 (mod 4). (re Vladimir Medvedkin <medvedkinv@gmail.com>)
* Adopted a better way to access bytes. (re Mattias Rönnblom <hofors@lysator.liu.se>)
* Adopted RTE_PTR_ADD for pointer arithmetic. (re Mattias Rönnblom <hofors@lysator.liu.se>)

 .mailmap                       |   1 +
 app/test/test_hash_functions.c |  47 +++++++++++---
 lib/hash/rte_hash_xor.h        | 113 +++++++++++++++++++++++++++++++++
 3 files changed, 151 insertions(+), 10 deletions(-)
 create mode 100644 lib/hash/rte_hash_xor.h

--
2.41.0.390.g38632f3daf-goog
  

Comments

David Marchand Sept. 29, 2023, 3:38 p.m. UTC | #1
On Tue, Jul 11, 2023 at 12:00 AM Bili Dong <qobilidop@gmail.com> 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@gmail.com>

Review, please.
  
Medvedkin, Vladimir Oct. 3, 2023, 4:51 p.m. UTC | #2
Acked-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>

On 10/07/2023 22:59, 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@gmail.com>
>
>
>
  
David Marchand Oct. 6, 2023, 8:06 a.m. UTC | #3
Hello,

On Tue, Jul 11, 2023 at 12:00 AM Bili Dong <qobilidop@gmail.com> 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@gmail.com>
>  .mailmap                       |   1 +
>  app/test/test_hash_functions.c |  47 +++++++++++---
>  lib/hash/rte_hash_xor.h        | 113 +++++++++++++++++++++++++++++++++
>  3 files changed, 151 insertions(+), 10 deletions(-)
>  create mode 100644 lib/hash/rte_hash_xor.h
>

I was about to merge this patch but there are some issues that should
have been caught by the library maintainer...

It seems the intention is to have a public API (meaning external DPDK
apps) consumption.
Then the header must be exported via 'headers' in lib/hash/meson.build.
Besides, such API addition must be announced in the release notes.
And this API should be documented either in some doc/guides/ or at
least with doxygen (meaning that rte_hash_xor.h must be referenced in
doc/api/doxy-api-index.md).


Thanks.
  

Patch

diff --git a/.mailmap b/.mailmap
index 8e3940a253..997d89388f 100644
--- a/.mailmap
+++ b/.mailmap
@@ -164,6 +164,7 @@  Bernard Iremonger <bernard.iremonger@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@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..7175841507
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,113 @@ 
+/* 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.
+ */
+
+/**
+ * @internal
+ * Access the next 8 bytes.
+ */
+static inline uint64_t
+rte_hash_access64(const void *data)
+{
+	uint64_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+/**
+ * @internal
+ * Access the next 4 bytes.
+ */
+static inline uint32_t
+rte_hash_access32(const void *data)
+{
+	uint32_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+/**
+ * @internal
+ * Access the next 2 bytes.
+ */
+static inline uint16_t
+rte_hash_access16(const void *data)
+{
+	uint16_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+/**
+ * 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 ^= (*(const uint8_t *)data) << bit_offset;
+
+	hash32 ^= rte_be_to_cpu_32((uint32_t)hash64 ^ (hash64 >> 32));
+	return hash32;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */