diff mbox series

[v5,1/5] hash: add new toeplitz hash implementation

Message ID 1634842469-27119-2-git-send-email-vladimir.medvedkin@intel.com (mailing list archive)
State Superseded, archived
Delegated to: Thomas Monjalon
Headers show
Series optimized Toeplitz hash implementation | expand

Checks

Context Check Description
ci/iol-testing warning apply patch failure
ci/checkpatch success coding style OK

Commit Message

Vladimir Medvedkin Oct. 21, 2021, 6:54 p.m. UTC
This patch add a new Toeplitz hash implementation using
Galios Fields New Instructions (GFNI).

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
Acked-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
---
 doc/api/doxy-api-index.md     |   1 +
 lib/hash/meson.build          |   1 +
 lib/hash/rte_thash.c          |  29 ++++++
 lib/hash/rte_thash.h          |  35 +++++++
 lib/hash/rte_thash_gfni.h     |  87 +++++++++++++++++
 lib/hash/rte_thash_x86_gfni.h | 221 ++++++++++++++++++++++++++++++++++++++++++
 lib/hash/version.map          |   2 +
 7 files changed, 376 insertions(+)
 create mode 100644 lib/hash/rte_thash_gfni.h
 create mode 100644 lib/hash/rte_thash_x86_gfni.h

Comments

Thomas Monjalon Oct. 25, 2021, 5:05 p.m. UTC | #1
21/10/2021 20:54, Vladimir Medvedkin:
> This patch add a new Toeplitz hash implementation using
> Galios Fields New Instructions (GFNI).
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
> Acked-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
> ---
> --- a/lib/hash/version.map
> +++ b/lib/hash/version.map
> @@ -39,10 +39,12 @@ EXPERIMENTAL {
>  
>  	rte_thash_add_helper;
>  	rte_thash_adjust_tuple;
> +	rte_thash_complete_matrix;
>  	rte_thash_find_existing;
>  	rte_thash_free_ctx;
>  	rte_thash_get_complement;
>  	rte_thash_get_helper;
>  	rte_thash_get_key;
> +	rte_thash_gfni_supported;
>  	rte_thash_init_ctx;
>  };
> 

It should be like this:

--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -37,6 +37,7 @@ DPDK_22 {
 EXPERIMENTAL {
        global:
 
+       # added in 21.05
        rte_thash_add_helper;
        rte_thash_adjust_tuple;
        rte_thash_find_existing;
@@ -45,4 +46,8 @@ EXPERIMENTAL {
        rte_thash_get_helper;
        rte_thash_get_key;
        rte_thash_init_ctx;
+
+       # added in 21.11
+       rte_thash_complete_matrix;
+       rte_thash_gfni_supported;
 };
diff mbox series

Patch

diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md
index 2939050..d9cecf3 100644
--- a/doc/api/doxy-api-index.md
+++ b/doc/api/doxy-api-index.md
@@ -140,6 +140,7 @@  The public API headers are grouped by topics:
   [hash]               (@ref rte_hash.h),
   [jhash]              (@ref rte_jhash.h),
   [thash]              (@ref rte_thash.h),
+  [thash_gfni]         (@ref rte_thash_gfni.h),
   [FBK hash]           (@ref rte_fbk_hash.h),
   [CRC hash]           (@ref rte_hash_crc.h)
 
diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 9bc5ef9..40444ac 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -7,6 +7,7 @@  headers = files(
         'rte_hash.h',
         'rte_jhash.h',
         'rte_thash.h',
+        'rte_thash_gfni.h',
 )
 indirect_headers += files('rte_crc_arm64.h')
 
diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index 696a112..e605a6f 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -90,6 +90,35 @@  struct rte_thash_ctx {
 	uint8_t		hash_key[0];
 };
 
+int
+rte_thash_gfni_supported(void)
+{
+#ifdef RTE_THASH_GFNI_DEFINED
+	if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_GFNI) &&
+			(rte_vect_get_max_simd_bitwidth() >=
+			RTE_VECT_SIMD_512))
+		return 1;
+#endif
+
+	return 0;
+};
+
+void
+rte_thash_complete_matrix(uint64_t *matrixes, const uint8_t *rss_key, int size)
+{
+	int i, j;
+	uint8_t *m = (uint8_t *)matrixes;
+	uint8_t left_part, right_part;
+
+	for (i = 0; i < size; i++) {
+		for (j = 0; j < 8; j++) {
+			left_part = rss_key[i] << j;
+			right_part = (uint16_t)(rss_key[i + 1]) >> (8 - j);
+			m[i * 8 + j] = left_part|right_part;
+		}
+	}
+}
+
 static inline uint32_t
 get_bit_lfsr(struct thash_lfsr *lfsr)
 {
diff --git a/lib/hash/rte_thash.h b/lib/hash/rte_thash.h
index 76109fc..a406be0 100644
--- a/lib/hash/rte_thash.h
+++ b/lib/hash/rte_thash.h
@@ -28,6 +28,7 @@  extern "C" {
 #include <rte_config.h>
 #include <rte_ip.h>
 #include <rte_common.h>
+#include <rte_thash_gfni.h>
 
 #if defined(RTE_ARCH_X86) || defined(__ARM_NEON)
 #include <rte_vect.h>
@@ -223,6 +224,40 @@  rte_softrss_be(uint32_t *input_tuple, uint32_t input_len,
 	return ret;
 }
 
+/**
+ * Indicates if GFNI implementations of the Toeplitz hash are supported.
+ *
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * @return
+ *  1 if GFNI is supported
+ *  0 otherwise
+ */
+__rte_experimental
+int
+rte_thash_gfni_supported(void);
+
+/**
+ * Converts Toeplitz hash key (RSS key) into matrixes required
+ * for GFNI implementation
+ *
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * @param matrixes
+ *  pointer to the memory where matrices will be written.
+ *  Note: the size of this memory must be equal to size * 8
+ * @param rss_key
+ *  pointer to the Toeplitz hash key
+ * @param size
+ *  Size of the rss_key in bytes.
+ */
+__rte_experimental
+void
+rte_thash_complete_matrix(uint64_t *matrixes, const uint8_t *rss_key,
+	int size);
+
 /** @internal Logarithm of minimum size of the RSS ReTa */
 #define	RTE_THASH_RETA_SZ_MIN	2U
 /** @internal Logarithm of maximum size of the RSS ReTa */
diff --git a/lib/hash/rte_thash_gfni.h b/lib/hash/rte_thash_gfni.h
new file mode 100644
index 0000000..95718d1
--- /dev/null
+++ b/lib/hash/rte_thash_gfni.h
@@ -0,0 +1,87 @@ 
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2021 Intel Corporation
+ */
+
+#ifndef _RTE_THASH_GFNI_H_
+#define _RTE_THASH_GFNI_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <rte_log.h>
+
+#ifdef RTE_ARCH_X86
+
+#include <rte_thash_x86_gfni.h>
+
+#endif
+
+#ifndef RTE_THASH_GFNI_DEFINED
+
+/**
+ * Calculate Toeplitz hash.
+ * Dummy implementation.
+ *
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * @param m
+ *  Pointer to the matrices generated from the corresponding
+ *  RSS hash key using rte_thash_complete_matrix().
+ * @param tuple
+ *  Pointer to the data to be hashed. Data must be in network byte order.
+ * @param len
+ *  Length of the data to be hashed.
+ * @return
+ *  Calculated Toeplitz hash value.
+ */
+__rte_experimental
+static inline uint32_t
+rte_thash_gfni(const uint64_t *mtrx __rte_unused,
+	const uint8_t *key __rte_unused, int len __rte_unused)
+{
+	RTE_LOG(ERR, HASH, "%s is undefined under given arch\n", __func__);
+	return 0;
+}
+
+/**
+ * Bulk implementation for Toeplitz hash.
+ * Dummy implementation.
+ *
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * @param m
+ *  Pointer to the matrices generated from the corresponding
+ *  RSS hash key using rte_thash_complete_matrix().
+ * @param tuple
+ *  Array of the pointers on data to be hashed.
+ *  Data must be in network byte order.
+ * @param len
+ *  Length of the largest data buffer to be hashed.
+ * @param val
+ *  Array of uint32_t where to put calculated Toeplitz hash values
+ * @param num
+ *  Number of tuples to hash.
+ */
+__rte_experimental
+static inline void
+rte_thash_gfni_bulk(const uint64_t *mtrx __rte_unused,
+	int len __rte_unused, uint8_t *tuple[] __rte_unused,
+	uint32_t val[], uint32_t num)
+{
+	unsigned int i;
+
+	RTE_LOG(ERR, HASH, "%s is undefined under given arch\n", __func__);
+	for (i = 0; i < num; i++)
+		val[i] = 0;
+}
+
+#endif /* RTE_THASH_GFNI_DEFINED */
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_THASH_GFNI_H_ */
diff --git a/lib/hash/rte_thash_x86_gfni.h b/lib/hash/rte_thash_x86_gfni.h
new file mode 100644
index 0000000..faa340a
--- /dev/null
+++ b/lib/hash/rte_thash_x86_gfni.h
@@ -0,0 +1,221 @@ 
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2021 Intel Corporation
+ */
+
+#ifndef _RTE_THASH_X86_GFNI_H_
+#define _RTE_THASH_X86_GFNI_H_
+
+/**
+ * @file
+ *
+ * Optimized Toeplitz hash functions implementation
+ * using Galois Fields New Instructions.
+ */
+
+#include <rte_vect.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifdef __GFNI__
+#define RTE_THASH_GFNI_DEFINED
+
+#define RTE_THASH_FIRST_ITER_MSK	0x0f0f0f0f0f0e0c08
+#define RTE_THASH_PERM_MSK		0x0f0f0f0f0f0f0f0f
+#define RTE_THASH_FIRST_ITER_MSK_2	0xf0f0f0f0f0e0c080
+#define RTE_THASH_PERM_MSK_2		0xf0f0f0f0f0f0f0f0
+#define RTE_THASH_REWIND_MSK		0x0000000000113377
+
+__rte_internal
+static inline void
+__rte_thash_xor_reduce(__m512i xor_acc, uint32_t *val_1, uint32_t *val_2)
+{
+	__m256i tmp_256_1, tmp_256_2;
+	__m128i tmp128_1, tmp128_2;
+	uint64_t tmp_1, tmp_2;
+
+	tmp_256_1 = _mm512_castsi512_si256(xor_acc);
+	tmp_256_2 = _mm512_extracti32x8_epi32(xor_acc, 1);
+	tmp_256_1 = _mm256_xor_si256(tmp_256_1, tmp_256_2);
+
+	tmp128_1 = _mm256_castsi256_si128(tmp_256_1);
+	tmp128_2 = _mm256_extracti32x4_epi32(tmp_256_1, 1);
+	tmp128_1 = _mm_xor_si128(tmp128_1, tmp128_2);
+
+	tmp_1 = _mm_extract_epi64(tmp128_1, 0);
+	tmp_2 = _mm_extract_epi64(tmp128_1, 1);
+	tmp_1 ^= tmp_2;
+
+	*val_1 = (uint32_t)tmp_1;
+	*val_2 = (uint32_t)(tmp_1 >> 32);
+}
+
+__rte_internal
+static inline __m512i
+__rte_thash_gfni(const uint64_t *mtrx, const uint8_t *tuple,
+	const uint8_t *secondary_tuple, int len)
+{
+	__m512i permute_idx = _mm512_set_epi8(7, 6, 5, 4, 7, 6, 5, 4,
+						6, 5, 4, 3, 6, 5, 4, 3,
+						5, 4, 3, 2, 5, 4, 3, 2,
+						4, 3, 2, 1, 4, 3, 2, 1,
+						3, 2, 1, 0, 3, 2, 1, 0,
+						2, 1, 0, -1, 2, 1, 0, -1,
+						1, 0, -1, -2, 1, 0, -1, -2,
+						0, -1, -2, -3, 0, -1, -2, -3);
+
+	const __m512i rewind_idx = _mm512_set_epi8(0, 0, 0, 0, 0, 0, 0, 0,
+						0, 0, 0, 0, 0, 0, 0, 0,
+						0, 0, 0, 0, 0, 0, 0, 0,
+						0, 0, 0, 0, 0, 0, 0, 0,
+						0, 0, 0, 0, 0, 0, 0, 0,
+						0, 0, 0, 59, 0, 0, 0, 59,
+						0, 0, 59, 58, 0, 0, 59, 58,
+						0, 59, 58, 57, 0, 59, 58, 57);
+	const __mmask64 rewind_mask = RTE_THASH_REWIND_MSK;
+	const __m512i shift_8 = _mm512_set1_epi8(8);
+	__m512i xor_acc = _mm512_setzero_si512();
+	__m512i perm_bytes = _mm512_setzero_si512();
+	__m512i vals, matrixes, tuple_bytes, tuple_bytes_2;
+	__mmask64 load_mask, permute_mask, permute_mask_2;
+	int chunk_len = 0, i = 0;
+	uint8_t mtrx_msk;
+	const int prepend = 3;
+
+	for (; len > 0; len -= 64, tuple += 64) {
+		if (i == 8)
+			perm_bytes = _mm512_maskz_permutexvar_epi8(rewind_mask,
+				rewind_idx, perm_bytes);
+
+		permute_mask = RTE_THASH_FIRST_ITER_MSK;
+		load_mask = (len >= 64) ? UINT64_MAX : ((1ULL << len) - 1);
+		tuple_bytes = _mm512_maskz_loadu_epi8(load_mask, tuple);
+		if (secondary_tuple) {
+			permute_mask_2 = RTE_THASH_FIRST_ITER_MSK_2;
+			tuple_bytes_2 = _mm512_maskz_loadu_epi8(load_mask,
+				secondary_tuple);
+		}
+
+		chunk_len = __builtin_popcountll(load_mask);
+		for (i = 0; i < ((chunk_len + prepend) / 8); i++, mtrx += 8) {
+			perm_bytes = _mm512_mask_permutexvar_epi8(perm_bytes,
+				permute_mask, permute_idx, tuple_bytes);
+
+			if (secondary_tuple)
+				perm_bytes =
+					_mm512_mask_permutexvar_epi8(perm_bytes,
+					permute_mask_2, permute_idx,
+					tuple_bytes_2);
+
+			matrixes = _mm512_maskz_loadu_epi64(UINT8_MAX, mtrx);
+			vals = _mm512_gf2p8affine_epi64_epi8(perm_bytes,
+				matrixes, 0);
+
+			xor_acc = _mm512_xor_si512(xor_acc, vals);
+			permute_idx = _mm512_add_epi8(permute_idx, shift_8);
+			permute_mask = RTE_THASH_PERM_MSK;
+			if (secondary_tuple)
+				permute_mask_2 = RTE_THASH_PERM_MSK_2;
+		}
+	}
+
+	int rest_len = (chunk_len + prepend) % 8;
+	if (rest_len != 0) {
+		mtrx_msk = (1 << (rest_len % 8)) - 1;
+		matrixes = _mm512_maskz_loadu_epi64(mtrx_msk, mtrx);
+		if (i == 8) {
+			perm_bytes = _mm512_maskz_permutexvar_epi8(rewind_mask,
+				rewind_idx, perm_bytes);
+		} else {
+			perm_bytes = _mm512_mask_permutexvar_epi8(perm_bytes,
+				permute_mask, permute_idx, tuple_bytes);
+
+			if (secondary_tuple)
+				perm_bytes =
+					_mm512_mask_permutexvar_epi8(
+					perm_bytes, permute_mask_2,
+					permute_idx, tuple_bytes_2);
+		}
+
+		vals = _mm512_gf2p8affine_epi64_epi8(perm_bytes, matrixes, 0);
+		xor_acc = _mm512_xor_si512(xor_acc, vals);
+	}
+
+	return xor_acc;
+}
+
+/**
+ * Calculate Toeplitz hash.
+ *
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * @param m
+ *  Pointer to the matrices generated from the corresponding
+ *  RSS hash key using rte_thash_complete_matrix().
+ * @param tuple
+ *  Pointer to the data to be hashed. Data must be in network byte order.
+ * @param len
+ *  Length of the data to be hashed.
+ * @return
+ *  Calculated Toeplitz hash value.
+ */
+__rte_experimental
+static inline uint32_t
+rte_thash_gfni(const uint64_t *m, const uint8_t *tuple, int len)
+{
+	uint32_t val, val_zero;
+
+	__m512i xor_acc = __rte_thash_gfni(m, tuple, NULL, len);
+	__rte_thash_xor_reduce(xor_acc, &val, &val_zero);
+
+	return val;
+}
+
+/**
+ * Bulk implementation for Toeplitz hash.
+ *
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * @param m
+ *  Pointer to the matrices generated from the corresponding
+ *  RSS hash key using rte_thash_complete_matrix().
+ * @param tuple
+ *  Array of the pointers on data to be hashed.
+ *  Data must be in network byte order.
+ * @param len
+ *  Length of the largest data buffer to be hashed.
+ * @param val
+ *  Array of uint32_t where to put calculated Toeplitz hash values
+ * @param num
+ *  Number of tuples to hash.
+ */
+__rte_experimental
+static inline void
+rte_thash_gfni_bulk(const uint64_t *mtrx, int len, uint8_t *tuple[],
+	uint32_t val[], uint32_t num)
+{
+	uint32_t i;
+	uint32_t val_zero;
+	__m512i xor_acc;
+
+	for (i = 0; i != (num & ~1); i += 2) {
+		xor_acc = __rte_thash_gfni(mtrx, tuple[i], tuple[i + 1], len);
+		__rte_thash_xor_reduce(xor_acc, val + i, val + i + 1);
+	}
+
+	if (num & 1) {
+		xor_acc = __rte_thash_gfni(mtrx, tuple[i], NULL, len);
+		__rte_thash_xor_reduce(xor_acc, val + i, &val_zero);
+	}
+}
+
+#endif /* _GFNI_ */
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_THASH_X86_GFNI_H_ */
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 8185470..64bed86 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -39,10 +39,12 @@  EXPERIMENTAL {
 
 	rte_thash_add_helper;
 	rte_thash_adjust_tuple;
+	rte_thash_complete_matrix;
 	rte_thash_find_existing;
 	rte_thash_free_ctx;
 	rte_thash_get_complement;
 	rte_thash_get_helper;
 	rte_thash_get_key;
+	rte_thash_gfni_supported;
 	rte_thash_init_ctx;
 };