[PATCH v2 0/4] RSS hash key generation

[PATCH v2 0/4] RSS hash key generation

[Vladimir Medvedkin]

Currently there are 2 methods to get the RSS hash key. The first method is to
randomly generate it. The second one is to use well known RSS hash keys. Both
methods have drawbacks. The first method not always provides a good hash
distribution. The second one does, but not for all ReTa sizes and not for all
traffic types. Additionaly, since these RSS hash keys are well known, they could
potentially be vulnerable to hash-collision DoS attacks.

The proposed API could be used to address both of these issues - the key can be
randomy generated and tailored to specific traffic profile distribution. For
example, if we know that we are receiving flows where source/destination
addresses are fixed or limited to a small quantity, but source port has good
distribution, we could generate an RSS key that will give us good distribution
across our ReTa.

v2
 - fix some minor issues

Vladimir Medvedkin (4):
  thash: add RSS hash key generation API
  hash: add dynamic polynomial calculation
  hash: implement RSS hash key generation API
  test/thash: add tests for RSS key generation API

 app/test/test_thash.c              | 108 ++++++++++++
 lib/hash/meson.build               |   1 +
 lib/hash/rte_thash.c               |  72 ++++----
 lib/hash/rte_thash.h               |  37 +++++
 lib/hash/rte_thash_gf2_poly_math.c | 253 +++++++++++++++++++++++++++++
 lib/hash/version.map               |   3 +
 6 files changed, 434 insertions(+), 40 deletions(-)
 create mode 100644 lib/hash/rte_thash_gf2_poly_math.c

-- 
2.34.1

[PATCH v2 1/4] thash: add RSS hash key generation API

[Vladimir Medvedkin]

Currently the only way to have non static Toeplitz hash key is to
generate it randomly. Such a key may not guarantee good packets
distribution, especially if there are small number of flows.

This patch adds stub implementation of the Toeplitz hash key generation
function, which may improve Toeplitz hash key with respect to hash values
distribution.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/rte_thash.c | 13 +++++++++++++
 lib/hash/rte_thash.h | 24 ++++++++++++++++++++++++
 lib/hash/version.map |  2 ++
 3 files changed, 39 insertions(+)

diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index 10721effe6..df9b4960ce 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -832,3 +832,16 @@ rte_thash_adjust_tuple(struct rte_thash_ctx *ctx,
 
 	return ret;
 }
+
+int
+rte_thash_gen_key(uint8_t *key, int key_len, int reta_sz_log,
+	int entropy_start, int entropy_sz)
+{
+	RTE_SET_USED(key);
+	RTE_SET_USED(key_len);
+	RTE_SET_USED(reta_sz_log);
+	RTE_SET_USED(entropy_start);
+	RTE_SET_USED(entropy_sz);
+
+	return 0;
+}
diff --git a/lib/hash/rte_thash.h b/lib/hash/rte_thash.h
index 30b657e67a..560fc1de73 100644
--- a/lib/hash/rte_thash.h
+++ b/lib/hash/rte_thash.h
@@ -447,6 +447,30 @@ rte_thash_adjust_tuple(struct rte_thash_ctx *ctx,
 	uint32_t desired_value, unsigned int attempts,
 	rte_thash_check_tuple_t fn, void *userdata);
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Modify RSS hash key such that subtuple bits corresponding to `entropy_sz`
+ * bits starting from `entropy_start` will have the most even distribution with
+ * this key with a given ReTa size.
+ *
+ * @param key pointer to the RSS hash key
+ * @param key_len length of the key
+ * @param reta_sz_log log2 of the size of RSS redirection table. i.e. number of
+ *   bits of the rss hash value used to identify RSS ReTa entry
+ * @param entropy_start bit offset from the beginning of the tuple where user
+ *   expects best distribution of the subtuple values.
+ * @param entropy_sz size in bits of the part of subtuple
+ *
+ * @return
+ *  0 on success negative otherwise
+ */
+__rte_experimental
+int
+rte_thash_gen_key(uint8_t *key, int key_len, int reta_sz_log,
+	int entropy_start, int entropy_sz);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 11a5394a45..4f13f1d5aa 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -52,6 +52,8 @@ EXPERIMENTAL {
 
 	# added in 24.07
 	rte_hash_rcu_qsbr_dq_reclaim;
+	# added in 24.11
+	rte_thash_gen_key;
 };
 
 INTERNAL {
-- 
2.34.1

Re: [PATCH v2 1/4] thash: add RSS hash key generation API

[Stephen Hemminger]

On Thu, 10 Oct 2024 12:33:28 +0000
Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:

> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Modify RSS hash key such that subtuple bits corresponding to `entropy_sz`
> + * bits starting from `entropy_start` will have the most even distribution with
> + * this key with a given ReTa size.
> + *
> + * @param key pointer to the RSS hash key
> + * @param key_len length of the key
> + * @param reta_sz_log log2 of the size of RSS redirection table. i.e. number of
> + *   bits of the rss hash value used to identify RSS ReTa entry
> + * @param entropy_start bit offset from the beginning of the tuple where user
> + *   expects best distribution of the subtuple values.
> + * @param entropy_sz size in bits of the part of subtuple
> + *
> + * @return
> + *  0 on success negative otherwise
> + */
> +__rte_experimental
> +int
> +rte_thash_gen_key(uint8_t *key, int key_len, int reta_sz_log,
> +	int entropy_start, int entropy_sz);

Avoid use of int wherever possible.
Unless you want to allow negative offsets.
Maybe something like?

int
rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_bits,
		uint32_t entropy_start, size_t entropy_sz)

[PATCH v2 2/4] hash: add dynamic polynomial calculation

[Vladimir Medvedkin]

Current polynomial table has the following limitations:

1. It has polynomials up to degree 16
2. For each degree there are only 4 polynomials

The above results in less entropy when generating Toeplitz hash key
subsequences.

This patch replaces the current static table approach with dynamic
polynomial calculation for polynomials of degree 7 or higher, resulting
in better entropy of generated RSS hash key.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/meson.build               |   1 +
 lib/hash/rte_thash.c               |  46 +-----
 lib/hash/rte_thash.h               |  13 ++
 lib/hash/rte_thash_gf2_poly_math.c | 253 +++++++++++++++++++++++++++++
 lib/hash/version.map               |   1 +
 5 files changed, 274 insertions(+), 40 deletions(-)
 create mode 100644 lib/hash/rte_thash_gf2_poly_math.c

diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa93..7ce504ee8b 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -23,6 +23,7 @@ sources = files(
         'rte_fbk_hash.c',
         'rte_thash.c',
         'rte_thash_gfni.c',
+        'rte_thash_gf2_poly_math.c',
 )
 
 deps += ['net']
diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index df9b4960ce..f57b275a72 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -31,33 +31,6 @@ static struct rte_tailq_elem rte_thash_tailq = {
 };
 EAL_REGISTER_TAILQ(rte_thash_tailq)
 
-/**
- * Table of some irreducible polinomials over GF(2).
- * For lfsr they are represented in BE bit order, and
- * x^0 is masked out.
- * For example, poly x^5 + x^2 + 1 will be represented
- * as (101001b & 11111b) = 01001b = 0x9
- */
-static const uint32_t irreducible_poly_table[][4] = {
-	{0, 0, 0, 0},	/** < degree 0 */
-	{1, 1, 1, 1},	/** < degree 1 */
-	{0x3, 0x3, 0x3, 0x3},	/** < degree 2 and so on... */
-	{0x5, 0x3, 0x5, 0x3},
-	{0x9, 0x3, 0x9, 0x3},
-	{0x9, 0x1b, 0xf, 0x5},
-	{0x21, 0x33, 0x1b, 0x2d},
-	{0x41, 0x11, 0x71, 0x9},
-	{0x71, 0xa9, 0xf5, 0x8d},
-	{0x21, 0xd1, 0x69, 0x1d9},
-	{0x81, 0x2c1, 0x3b1, 0x185},
-	{0x201, 0x541, 0x341, 0x461},
-	{0x941, 0x609, 0xe19, 0x45d},
-	{0x1601, 0x1f51, 0x1171, 0x359},
-	{0x2141, 0x2111, 0x2db1, 0x2109},
-	{0x4001, 0x801, 0x101, 0x7301},
-	{0x7781, 0xa011, 0x4211, 0x86d9},
-};
-
 struct thash_lfsr {
 	uint32_t	ref_cnt;
 	uint32_t	poly;
@@ -159,28 +132,21 @@ get_rev_bit_lfsr(struct thash_lfsr *lfsr)
 	return ret;
 }
 
-static inline uint32_t
-thash_get_rand_poly(uint32_t poly_degree)
-{
-	return irreducible_poly_table[poly_degree][rte_rand() %
-		RTE_DIM(irreducible_poly_table[poly_degree])];
-}
-
 static struct thash_lfsr *
-alloc_lfsr(struct rte_thash_ctx *ctx)
+alloc_lfsr(uint32_t poly_degree)
 {
 	struct thash_lfsr *lfsr;
 	uint32_t i;
 
-	if (ctx == NULL)
+	if ((poly_degree > 32) || (poly_degree == 0))
 		return NULL;
 
 	lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
 	if (lfsr == NULL)
 		return NULL;
 
-	lfsr->deg = ctx->reta_sz_log;
-	lfsr->poly = thash_get_rand_poly(lfsr->deg);
+	lfsr->deg = poly_degree;
+	lfsr->poly = rte_thash_get_rand_poly(lfsr->deg);
 	do {
 		lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1);
 	} while (lfsr->state == 0);
@@ -460,7 +426,7 @@ insert_before(struct rte_thash_ctx *ctx,
 	int ret;
 
 	if (end < cur_ent->offset) {
-		ent->lfsr = alloc_lfsr(ctx);
+		ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
 		if (ent->lfsr == NULL) {
 			rte_free(ent);
 			return -ENOMEM;
@@ -613,7 +579,7 @@ rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len,
 		continue;
 	}
 
-	ent->lfsr = alloc_lfsr(ctx);
+	ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
 	if (ent->lfsr == NULL) {
 		rte_free(ent);
 		return -ENOMEM;
diff --git a/lib/hash/rte_thash.h b/lib/hash/rte_thash.h
index 560fc1de73..fca2924d93 100644
--- a/lib/hash/rte_thash.h
+++ b/lib/hash/rte_thash.h
@@ -108,6 +108,19 @@ union rte_thash_tuple {
 	struct rte_ipv6_tuple	v6;
 };
 
+/** @internal
+ *  @brief Generates a random polynomial
+ *
+ * @param poly_degree
+ *   degree of the polynomial
+ *
+ * @return
+ *   random polynomial
+ */
+__rte_internal
+uint32_t
+rte_thash_get_rand_poly(uint32_t poly_degree);
+
 /**
  * Prepare special converted key to use with rte_softrss_be()
  * @param orig
diff --git a/lib/hash/rte_thash_gf2_poly_math.c b/lib/hash/rte_thash_gf2_poly_math.c
new file mode 100644
index 0000000000..e6eb1ef3c5
--- /dev/null
+++ b/lib/hash/rte_thash_gf2_poly_math.c
@@ -0,0 +1,253 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2024 Intel Corporation
+ */
+#include <rte_random.h>
+#include <rte_common.h>
+#include <rte_bitops.h>
+#include <rte_debug.h>
+#include <rte_thash.h>
+
+#define MAX_TOEPLITZ_KEY_LENGTH 64
+
+/*
+ * Finite field math for field extensions with irreducing polynomial
+ * of degree <= 32.
+ * Polynomials are represented with 2 arguments - uint32_t poly and int degree.
+ * poly argument does not hold the highest degree coefficient,
+ * so full polynomial can be expressed as poly|(1ULL << degree).
+ * The algorithm to produce random irreducible polynomial was inspired by:
+ * "Computation in finite fields" by John Kerl, Chapter 10.4.
+ */
+
+static const uint32_t irreducible_poly_table[][3] = {
+	{0, 0, 0},		/* degree 0 */
+	{0x1, 0x1, 0x1},	/* degree 1 */
+	{0x3, 0x3, 0x3},	/* degree 2 and so on.. */
+	{0x3, 0x5, 0x3},	/* x^3+x^2+1(0x5) is reverted x^3+x+1(0x3) */
+	{0x3, 0x9, 0x3},	/* x^4+x^3+1(0x9) is reverted x^4+x+1(0x3) */
+	{0x5, 0xf, 0x17},	/* 0x5 <-> 0x9; 0xf <-> 0x1d; 0x17 <-> 0x1b */
+	{0x3, 0x27, 0x1b},	/* 0x3 <-> 0x21; 0x27 <-> 0x33; 0x1b <-> 0x2d*/
+};
+
+/*
+ * Table of the monic lowest weight irreducible polynomials over GF(2)
+ * starting from degree 7 up to degree 32.
+ * Taken from Handbook of Finite Fields by Gary L. Mullen and
+ * Daniel Penario p.33 Table 2.2.1.
+ * https://people.math.carleton.ca/~daniel/hff/irred/F2-2to10000.txt
+ */
+static const uint32_t default_irreducible_poly[] = {
+	0x3,    /* x^7 + x + 1*/
+	0x1b,   /* x^8 + x^4 + x^3 + x + 1 */
+	0x3,    /* x^9 + x + 1*/
+	0x9,    /* x^10 + x^3 + 1 */
+	0x5,    /* x^11 + x^2 + 1 */
+	0x9,    /* x^12 + x^3 + 1 */
+	0x1b,   /* x^13 + x^4 + x^3 + x + 1 */
+	0x33,   /* x^14 + x^5 + 1 */
+	0x3,    /* x^15 + x + 1 */
+	0x2b,   /* x^16 + x^5 + x^3 + x + 1 */
+	0x9,    /* x^17 + x^3 + 1 */
+	0x9,    /* x^18 + x^3 + 1 */
+	0x27,   /* x^19 + x^5 + x^2 + x + 1 */
+	0x9,    /* x^20 + x^3 + 1 */
+	0x5,    /* x^21 + x^2 + 1 */
+	0x3,    /* x^22 + x + 1 */
+	0x21,   /* x^23 + x^5 + 1 */
+	0x1b,   /* x^24 + x^4 + x^3 + x + 1 */
+	0x9,    /* x^25 + x^3 + 1 */
+	0x1b,   /* x^26 + x^4 + x^3 + x + 1 */
+	0x27,   /* x^27 + x^5 + x^2 + x + 1 */
+	0x3,    /* x^28 + x + 1 */
+	0x5,    /* x^29 + x^2 + 1 */
+	0x3,    /* x^30 + x + 1 */
+	0x9,    /* x^31 + x^3 + 1 */
+	0x8d,   /* x^32 + x^7 + x^3 + x^2 + 1 */
+};
+
+#define MAX_DIVISORS 28 /* 2^24 - 1 */
+
+struct divisors {
+	uint32_t n; /* number of divisors */
+	uint32_t div_arr[MAX_DIVISORS];
+};
+
+/* divisors of (2^n - 1) less than MIN(512, 2^n - 1) for all n in [7, 32] */
+static const struct divisors divisors[] = {
+	{ .n = 0, .div_arr = {} }, /* 2^7-1 is Mersenne prime */
+	{ .n = 6, .div_arr = {3, 5, 15, 17, 51, 85} },
+	{ .n = 2, .div_arr = {7, 73} },
+	{ .n = 6, .div_arr = {3, 11, 31, 33, 93, 341} },
+	{ .n = 2, .div_arr = {23, 89} },
+	{ .n = 19, .div_arr = {3, 5, 7, 9, 13, 15, 21, 35, 39, 45, 63, 65, 91,
+		105, 117, 195, 273, 315, 455} },
+	{ .n = 0, .div_arr = {} }, /* 2^13-1 is Mersenne prime */
+	{ .n = 5, .div_arr = {3, 43, 127, 129, 381} },
+	{ .n = 4, .div_arr = {7, 31, 151, 217} },
+	{ .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} },
+	{ .n = 0, .div_arr = {} }, /* 2^17-1 is Mersenne prime */
+	{ .n = 14, .div_arr = {3, 7, 9, 19, 21, 27, 57, 63, 73, 133, 171, 189,
+		219, 399} },
+	{ .n = 0, .div_arr = {0} }, /* 2^19-1 is Mersenne prime */
+	{ .n = 19, .div_arr = {3, 5, 11, 15, 25, 31, 33, 41, 55, 75, 93, 123,
+		155, 165, 205, 275, 341, 451, 465} },
+	{ .n = 4, .div_arr = {7, 49, 127, 337} },
+	{ .n = 5, .div_arr = {3, 23, 69, 89, 267} },
+	{ .n = 1, .div_arr = {47} },
+	{ .n = 28, .div_arr = {3, 5, 7, 9, 13, 15, 17, 21, 35, 39, 45, 51, 63,
+		65, 85, 91, 105, 117, 119, 153, 195, 221, 241, 255, 273, 315,
+		357, 455} },
+	{ .n = 1, .div_arr = {31} },
+	{ .n = 1, .div_arr = {3} },
+	{ .n = 2, .div_arr = {7, 73} },
+	{ .n = 14, .div_arr = {3, 5, 15, 29, 43, 87, 113, 127, 129, 145, 215,
+		339, 381, 435} },
+	{ .n = 1, .div_arr = {233} },
+	{ .n = 18, .div_arr = {3, 7, 9, 11, 21, 31, 33, 63, 77, 93, 99, 151,
+		217, 231, 279, 331, 341, 453} },
+	{ .n = 0, .div_arr = {} },/* 2^31-1 is Mersenne prime */
+	{ .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} },
+};
+
+static uint32_t
+gf2_mul(uint32_t a, uint32_t b, uint32_t r, int degree)
+{
+	uint64_t product = 0;
+	uint64_t r_poly = r|(1ULL << degree);
+
+	for (; b; b &= (b - 1))
+		product ^= (uint64_t)a << (rte_bsf32(b));
+
+	for (int i = degree * 2 - 1; i >= degree; i--)
+		if (product & (1 << i))
+			product ^= r_poly << (i - degree);
+
+	return product;
+}
+
+static uint32_t
+gf2_pow(uint32_t a, uint32_t pow, uint32_t r, int degree)
+{
+	uint32_t result = 1;
+	unsigned int i;
+
+	for (i = 0; i < (sizeof(pow)*CHAR_BIT - rte_clz32(pow)); i++) {
+		if (pow & (1 << i))
+			result = gf2_mul(result, a, r, degree);
+
+		a = gf2_mul(a, a, r, degree);
+	}
+
+	return result;
+}
+
+static uint32_t
+__thash_get_rand_poly(int poly_degree)
+{
+	uint32_t roots[poly_degree];
+	uint32_t rnd;
+	uint32_t ret_poly = 0;
+	int i, j;
+	bool short_orbit = false;
+
+	/* special case for low degree */
+	if (poly_degree < 7)
+		return irreducible_poly_table[poly_degree][rte_rand() %
+			RTE_DIM(irreducible_poly_table[poly_degree])];
+
+	uint32_t r = default_irreducible_poly[poly_degree - 7];
+
+	do {
+		short_orbit = false;
+		do {
+			rnd = rte_rand() & ((1 << poly_degree) - 1);
+		} while ((rnd == 0) || (rnd == 1));
+
+		/*
+		 * Quick check if random returned one of the roots of
+		 * the initial polynomial.
+		 * In other words if we randomy got x, x^2, x^4, x^8 or x^16
+		 */
+#define ROOT_POLY_MSK ((1 << 1)|(1 << 2)|(1 << 4)|(1 << 8)|(1 << 16))
+		if ((rte_popcount32(rnd) == 1) && (rnd & ROOT_POLY_MSK))
+			return default_irreducible_poly[poly_degree - 7];
+
+		/*
+		 * init array with some random polynomial roots
+		 * applying Frobenius automorphism (i.e. squaring them)
+		 * also checking for short orbits (i.e. if there are repeated roots)
+		 */
+		roots[0] = rnd;
+		for (i = 1; i < poly_degree; i++) {
+			roots[i] = gf2_pow(roots[i - 1], 2, r, poly_degree);
+			if (roots[i] == roots[0])
+				short_orbit = true;
+		}
+	} while (short_orbit);
+
+	/*
+	 * Get coefficients of the polynomial for
+	 * (x - roots[0])(x - roots[1])...(x - roots[n])
+	 */
+	uint32_t poly_coefficients[poly_degree + 1];
+	for (i = 0; i <= poly_degree; i++)
+		poly_coefficients[i] = 0;
+
+	poly_coefficients[0] = 1; /* highest degree term coefficient in the end */
+	for (i = 0; i < (int)poly_degree; i++) {
+		/* multiply by x */
+		for (j = i; j >= 0; j--)
+			poly_coefficients[j + 1] = poly_coefficients[j];
+
+		poly_coefficients[0] = 0;
+
+		/* multiply by root */
+		for (j = 0; j <= i; j++)
+			poly_coefficients[j] ^=
+				gf2_mul(poly_coefficients[j + 1],
+				roots[i], r, poly_degree);
+	}
+
+	for (i = 0; i < poly_degree; i++) {
+		if (poly_coefficients[i]) {
+			RTE_ASSERT(poly_coefficients[i] == 1);
+			ret_poly |= 1 << i;
+		}
+	}
+
+	return ret_poly;
+}
+
+/* test an order of the multiplicative subgroup generated by x */
+static int
+thash_test_poly_order(uint32_t poly, int degree)
+{
+	unsigned int i;
+	int div_idx = degree - 7;
+
+	if (degree < 7)
+		return 0;
+
+	for (i = 0; i < divisors[div_idx].n; i++) {
+		if (gf2_pow(0x2, divisors[div_idx].div_arr[i],
+				poly, degree) == 1)
+			return 1;
+	}
+
+	return 0;
+}
+
+uint32_t
+rte_thash_get_rand_poly(uint32_t poly_degree)
+{
+	uint32_t ret_poly;
+
+	if (poly_degree > 32)
+		return 0;
+
+	do
+		ret_poly = __thash_get_rand_poly(poly_degree);
+	while (thash_test_poly_order(ret_poly, poly_degree));
+
+	return ret_poly;
+}
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 4f13f1d5aa..7ce6ab1121 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -61,4 +61,5 @@ INTERNAL {
 
 	rte_thash_gfni_stub;
 	rte_thash_gfni_bulk_stub;
+	rte_thash_get_rand_poly;
 };
-- 
2.34.1

[PATCH v2 3/4] hash: implement RSS hash key generation API

[Vladimir Medvedkin]

This patch implements Toeplitz hash key generation function using the new
polynomial generation function.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/rte_thash.c | 23 ++++++++++++++++++-----
 1 file changed, 18 insertions(+), 5 deletions(-)

diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index f57b275a72..a452567228 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -803,11 +803,24 @@ int
 rte_thash_gen_key(uint8_t *key, int key_len, int reta_sz_log,
 	int entropy_start, int entropy_sz)
 {
-	RTE_SET_USED(key);
-	RTE_SET_USED(key_len);
-	RTE_SET_USED(reta_sz_log);
-	RTE_SET_USED(entropy_start);
-	RTE_SET_USED(entropy_sz);
+	int i, end, start;
+
+	/* define lfsr sequence range*/
+	end = entropy_start + entropy_sz + TOEPLITZ_HASH_LEN - 1;
+	start = end - (entropy_sz + reta_sz_log - 1);
+
+	if ((key == NULL) || (key_len * CHAR_BIT < entropy_start + entropy_sz) ||
+			(entropy_sz < reta_sz_log) || (reta_sz_log > TOEPLITZ_HASH_LEN))
+		return -EINVAL;
+
+	struct thash_lfsr *lfsr = alloc_lfsr(reta_sz_log);
+	if (lfsr == NULL)
+		return -ENOMEM;
+
+	for (i = start; i < end; i++)
+		set_bit(key, get_bit_lfsr(lfsr), i);
+
+	free_lfsr(lfsr);
 
 	return 0;
 }
-- 
2.34.1

[PATCH v2 4/4] test/thash: add tests for RSS key generation API

[Vladimir Medvedkin]

This patch adds tests for RSS key generation. In this test we measure
distribution of hash LSBs for a given random tuple where only some part
of bits is variable.

At first we generate random hash key and measure the worst distribution
for a given ReTa size value (RETA_SZ_LOG). Then we adjust the key with
the new API and run the test again, noting the new distribution. Finally,
we also measure said distribution for some well known RSS hash key which
is used in some PMDs.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 app/test/test_thash.c | 108 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 108 insertions(+)

diff --git a/app/test/test_thash.c b/app/test/test_thash.c
index 65d42fd900..fca2ba03dd 100644
--- a/app/test/test_thash.c
+++ b/app/test/test_thash.c
@@ -7,6 +7,7 @@
 #include <rte_ip.h>
 #include <rte_random.h>
 #include <rte_malloc.h>
+#include <rte_byteorder.h>
 
 #include "test.h"
 
@@ -935,6 +936,112 @@ test_adjust_tuple_mult_reta(void)
 	return TEST_SUCCESS;
 }
 
+#define RETA_SZ_LOG		11
+#define RSS_KEY_SZ		40
+#define RETA_SZ			(1 << RETA_SZ_LOG)
+#define NB_HASH_ITER	RETA_SZ
+#define NB_TEST_ITER	10
+
+static inline void
+run_hash_calc_loop(uint8_t *key, union rte_thash_tuple *tuple,
+					unsigned int *rss_reta_hits)
+{
+	uint32_t rss_hash;
+	int i;
+
+	for (i = 0; i < NB_HASH_ITER; i++) {
+		/* variable part starts from the most significant bit */
+		tuple->v4.dport = (i << (sizeof(tuple->v4.dport) * CHAR_BIT -
+			RETA_SZ_LOG));
+		/*
+		 * swap sport and dport on LE arch since rte_softrss()
+		 * works with host byte order uint32_t values
+		 */
+		tuple->v4.dport = rte_cpu_to_be_16(tuple->v4.dport);
+		tuple->v4.sctp_tag = rte_be_to_cpu_32(tuple->v4.sctp_tag);
+		rss_hash = rte_softrss((uint32_t *)tuple,
+				RTE_THASH_V4_L4_LEN, key);
+		/* unroll swap, required only for sport */
+		tuple->v4.sctp_tag = rte_cpu_to_be_32(tuple->v4.sctp_tag);
+		rss_reta_hits[rss_hash & (RETA_SZ - 1)]++;
+	}
+}
+
+static int
+hash_calc_iteration(unsigned int *min_before, unsigned int *max_before,
+		unsigned int *min_after, unsigned int *max_after,
+		unsigned int *min_default, unsigned int *max_default)
+{
+	uint8_t key[RSS_KEY_SZ] = {0};
+	union rte_thash_tuple tuple;
+	unsigned int rss_reta_hits_before_adjust[RETA_SZ] = {0};
+	unsigned int rss_reta_hits_after_adjust[RETA_SZ] = {0};
+	unsigned int rss_reta_hits_default_key[RETA_SZ] = {0};
+	int i;
+
+	for (i = 0; i < RSS_KEY_SZ; i++)
+		key[i] = rte_rand();
+
+	tuple.v4.src_addr = rte_rand();
+	tuple.v4.dst_addr = rte_rand();
+	tuple.v4.sport = rte_rand();
+
+	run_hash_calc_loop(key, &tuple, rss_reta_hits_before_adjust);
+
+	int ret = rte_thash_gen_key(key, RSS_KEY_SZ, RETA_SZ_LOG,
+		offsetof(union rte_thash_tuple, v4.dport)*CHAR_BIT,
+		RETA_SZ_LOG);
+
+	if (ret) {
+		printf("Can't generate key\n");
+		return -1;
+	}
+
+	run_hash_calc_loop(key, &tuple, rss_reta_hits_after_adjust);
+
+	run_hash_calc_loop(default_rss_key, &tuple, rss_reta_hits_default_key);
+
+	for (i = 0; i < RETA_SZ; i++) {
+		*min_before = RTE_MIN(*min_before, rss_reta_hits_before_adjust[i]);
+		*max_before = RTE_MAX(*max_before, rss_reta_hits_before_adjust[i]);
+		*min_after = RTE_MIN(*min_after, rss_reta_hits_after_adjust[i]);
+		*max_after = RTE_MAX(*max_after, rss_reta_hits_after_adjust[i]);
+		*min_default = RTE_MIN(*min_default, rss_reta_hits_default_key[i]);
+		*max_default = RTE_MAX(*max_default, rss_reta_hits_default_key[i]);
+	}
+
+	return 0;
+}
+
+static int
+test_keygen(void)
+{
+	int i, ret;
+	unsigned int min_before = UINT32_MAX;
+	unsigned int min_after = UINT32_MAX;
+	unsigned int min_default = UINT32_MAX;
+	unsigned int max_before = 0;
+	unsigned int max_after = 0;
+	unsigned int max_default = 0;
+
+	for (i = 0; i < NB_TEST_ITER; i++) {
+		/* calculates the worst distribution for each key */
+		ret = hash_calc_iteration(&min_before, &max_before, &min_after,
+			&max_after, &min_default, &max_default);
+		if (ret)
+			return ret;
+	}
+
+	printf("RSS before key adjustment: min=%d, max=%d\n",
+		min_before, max_before);
+	printf("RSS after key adjustment: min=%d, max=%d\n",
+		min_after, max_after);
+	printf("RSS default key: min=%d, max=%d\n",
+		min_default, max_default);
+
+	return TEST_SUCCESS;
+}
+
 static struct unit_test_suite thash_tests = {
 	.suite_name = "thash autotest",
 	.setup = NULL,
@@ -956,6 +1063,7 @@ static struct unit_test_suite thash_tests = {
 	TEST_CASE(test_predictable_rss_multirange),
 	TEST_CASE(test_adjust_tuple),
 	TEST_CASE(test_adjust_tuple_mult_reta),
+	TEST_CASE(test_keygen),
 	TEST_CASES_END()
 	}
 };
-- 
2.34.1

[PATCH v3 0/4] RSS hash key generation

[Vladimir Medvedkin]

Currently there are 2 methods to get the RSS hash key. The first method is to
randomly generate it. The second one is to use well known RSS hash keys. Both
methods have drawbacks. The first method not always provides a good hash
distribution. The second one does, but not for all ReTa sizes and not for all
traffic types. Additionaly, since these RSS hash keys are well known, they could
potentially be vulnerable to hash-collision DoS attacks.

The proposed API could be used to address both of these issues - the key can be
randomy generated and tailored to specific traffic profile distribution. For
example, if we know that we are receiving flows where source/destination
addresses are fixed or limited to a small quantity, but source port has good
distribution, we could generate an RSS key that will give us good distribution
across our ReTa.

v3
 - change rte_thash_gen_key() arguments types
v2
 - fix some minor issues

Vladimir Medvedkin (4):
  thash: add RSS hash key generation API
  hash: add dynamic polynomial calculation
  hash: implement RSS hash key generation API
  test/thash: add tests for RSS key generation API

 app/test/test_thash.c              | 108 ++++++++++++
 lib/hash/meson.build               |   1 +
 lib/hash/rte_thash.c               |  72 ++++----
 lib/hash/rte_thash.h               |  37 +++++
 lib/hash/rte_thash_gf2_poly_math.c | 253 +++++++++++++++++++++++++++++
 lib/hash/version.map               |   3 +
 6 files changed, 434 insertions(+), 40 deletions(-)
 create mode 100644 lib/hash/rte_thash_gf2_poly_math.c

-- 
2.43.0

[PATCH v3 1/4] thash: add RSS hash key generation API

[Vladimir Medvedkin]

Currently the only way to have non static Toeplitz hash key is to
generate it randomly. Such a key may not guarantee good packets
distribution, especially if there are small number of flows.

This patch adds stub implementation of the Toeplitz hash key generation
function, which may improve Toeplitz hash key with respect to hash values
distribution.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/rte_thash.c | 13 +++++++++++++
 lib/hash/rte_thash.h | 24 ++++++++++++++++++++++++
 lib/hash/version.map |  2 ++
 3 files changed, 39 insertions(+)

diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index 10721effe6..894b4d9197 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -832,3 +832,16 @@ rte_thash_adjust_tuple(struct rte_thash_ctx *ctx,
 
 	return ret;
 }
+
+int
+rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_log,
+	uint32_t entropy_start, size_t entropy_sz)
+{
+	RTE_SET_USED(key);
+	RTE_SET_USED(key_len);
+	RTE_SET_USED(reta_sz_log);
+	RTE_SET_USED(entropy_start);
+	RTE_SET_USED(entropy_sz);
+
+	return 0;
+}
diff --git a/lib/hash/rte_thash.h b/lib/hash/rte_thash.h
index 30b657e67a..ab534aea2f 100644
--- a/lib/hash/rte_thash.h
+++ b/lib/hash/rte_thash.h
@@ -447,6 +447,30 @@ rte_thash_adjust_tuple(struct rte_thash_ctx *ctx,
 	uint32_t desired_value, unsigned int attempts,
 	rte_thash_check_tuple_t fn, void *userdata);
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Modify RSS hash key such that subtuple bits corresponding to `entropy_sz`
+ * bits starting from `entropy_start` will have the most even distribution with
+ * this key with a given ReTa size.
+ *
+ * @param key pointer to the RSS hash key
+ * @param key_len length of the key
+ * @param reta_sz_log log2 of the size of RSS redirection table. i.e. number of
+ *   bits of the rss hash value used to identify RSS ReTa entry
+ * @param entropy_start bit offset from the beginning of the tuple where user
+ *   expects best distribution of the subtuple values.
+ * @param entropy_sz size in bits of the part of subtuple
+ *
+ * @return
+ *  0 on success negative otherwise
+ */
+__rte_experimental
+int
+rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_log,
+	uint32_t entropy_start, size_t entropy_sz);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 11a5394a45..4f13f1d5aa 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -52,6 +52,8 @@ EXPERIMENTAL {
 
 	# added in 24.07
 	rte_hash_rcu_qsbr_dq_reclaim;
+	# added in 24.11
+	rte_thash_gen_key;
 };
 
 INTERNAL {
-- 
2.43.0

[PATCH v3 2/4] hash: add dynamic polynomial calculation

[Vladimir Medvedkin]

Current polynomial table has the following limitations:

1. It has polynomials up to degree 16
2. For each degree there are only 4 polynomials

The above results in less entropy when generating Toeplitz hash key
subsequences.

This patch replaces the current static table approach with dynamic
polynomial calculation for polynomials of degree 7 or higher, resulting
in better entropy of generated RSS hash key.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/meson.build               |   1 +
 lib/hash/rte_thash.c               |  46 +-----
 lib/hash/rte_thash.h               |  13 ++
 lib/hash/rte_thash_gf2_poly_math.c | 253 +++++++++++++++++++++++++++++
 lib/hash/version.map               |   1 +
 5 files changed, 274 insertions(+), 40 deletions(-)
 create mode 100644 lib/hash/rte_thash_gf2_poly_math.c

diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa93..7ce504ee8b 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -23,6 +23,7 @@ sources = files(
         'rte_fbk_hash.c',
         'rte_thash.c',
         'rte_thash_gfni.c',
+        'rte_thash_gf2_poly_math.c',
 )
 
 deps += ['net']
diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index 894b4d9197..5c3d246657 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -31,33 +31,6 @@ static struct rte_tailq_elem rte_thash_tailq = {
 };
 EAL_REGISTER_TAILQ(rte_thash_tailq)
 
-/**
- * Table of some irreducible polinomials over GF(2).
- * For lfsr they are represented in BE bit order, and
- * x^0 is masked out.
- * For example, poly x^5 + x^2 + 1 will be represented
- * as (101001b & 11111b) = 01001b = 0x9
- */
-static const uint32_t irreducible_poly_table[][4] = {
-	{0, 0, 0, 0},	/** < degree 0 */
-	{1, 1, 1, 1},	/** < degree 1 */
-	{0x3, 0x3, 0x3, 0x3},	/** < degree 2 and so on... */
-	{0x5, 0x3, 0x5, 0x3},
-	{0x9, 0x3, 0x9, 0x3},
-	{0x9, 0x1b, 0xf, 0x5},
-	{0x21, 0x33, 0x1b, 0x2d},
-	{0x41, 0x11, 0x71, 0x9},
-	{0x71, 0xa9, 0xf5, 0x8d},
-	{0x21, 0xd1, 0x69, 0x1d9},
-	{0x81, 0x2c1, 0x3b1, 0x185},
-	{0x201, 0x541, 0x341, 0x461},
-	{0x941, 0x609, 0xe19, 0x45d},
-	{0x1601, 0x1f51, 0x1171, 0x359},
-	{0x2141, 0x2111, 0x2db1, 0x2109},
-	{0x4001, 0x801, 0x101, 0x7301},
-	{0x7781, 0xa011, 0x4211, 0x86d9},
-};
-
 struct thash_lfsr {
 	uint32_t	ref_cnt;
 	uint32_t	poly;
@@ -159,28 +132,21 @@ get_rev_bit_lfsr(struct thash_lfsr *lfsr)
 	return ret;
 }
 
-static inline uint32_t
-thash_get_rand_poly(uint32_t poly_degree)
-{
-	return irreducible_poly_table[poly_degree][rte_rand() %
-		RTE_DIM(irreducible_poly_table[poly_degree])];
-}
-
 static struct thash_lfsr *
-alloc_lfsr(struct rte_thash_ctx *ctx)
+alloc_lfsr(uint32_t poly_degree)
 {
 	struct thash_lfsr *lfsr;
 	uint32_t i;
 
-	if (ctx == NULL)
+	if ((poly_degree > 32) || (poly_degree == 0))
 		return NULL;
 
 	lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
 	if (lfsr == NULL)
 		return NULL;
 
-	lfsr->deg = ctx->reta_sz_log;
-	lfsr->poly = thash_get_rand_poly(lfsr->deg);
+	lfsr->deg = poly_degree;
+	lfsr->poly = rte_thash_get_rand_poly(lfsr->deg);
 	do {
 		lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1);
 	} while (lfsr->state == 0);
@@ -460,7 +426,7 @@ insert_before(struct rte_thash_ctx *ctx,
 	int ret;
 
 	if (end < cur_ent->offset) {
-		ent->lfsr = alloc_lfsr(ctx);
+		ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
 		if (ent->lfsr == NULL) {
 			rte_free(ent);
 			return -ENOMEM;
@@ -613,7 +579,7 @@ rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len,
 		continue;
 	}
 
-	ent->lfsr = alloc_lfsr(ctx);
+	ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
 	if (ent->lfsr == NULL) {
 		rte_free(ent);
 		return -ENOMEM;
diff --git a/lib/hash/rte_thash.h b/lib/hash/rte_thash.h
index ab534aea2f..943cdff390 100644
--- a/lib/hash/rte_thash.h
+++ b/lib/hash/rte_thash.h
@@ -108,6 +108,19 @@ union rte_thash_tuple {
 	struct rte_ipv6_tuple	v6;
 };
 
+/** @internal
+ *  @brief Generates a random polynomial
+ *
+ * @param poly_degree
+ *   degree of the polynomial
+ *
+ * @return
+ *   random polynomial
+ */
+__rte_internal
+uint32_t
+rte_thash_get_rand_poly(uint32_t poly_degree);
+
 /**
  * Prepare special converted key to use with rte_softrss_be()
  * @param orig
diff --git a/lib/hash/rte_thash_gf2_poly_math.c b/lib/hash/rte_thash_gf2_poly_math.c
new file mode 100644
index 0000000000..e6eb1ef3c5
--- /dev/null
+++ b/lib/hash/rte_thash_gf2_poly_math.c
@@ -0,0 +1,253 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2024 Intel Corporation
+ */
+#include <rte_random.h>
+#include <rte_common.h>
+#include <rte_bitops.h>
+#include <rte_debug.h>
+#include <rte_thash.h>
+
+#define MAX_TOEPLITZ_KEY_LENGTH 64
+
+/*
+ * Finite field math for field extensions with irreducing polynomial
+ * of degree <= 32.
+ * Polynomials are represented with 2 arguments - uint32_t poly and int degree.
+ * poly argument does not hold the highest degree coefficient,
+ * so full polynomial can be expressed as poly|(1ULL << degree).
+ * The algorithm to produce random irreducible polynomial was inspired by:
+ * "Computation in finite fields" by John Kerl, Chapter 10.4.
+ */
+
+static const uint32_t irreducible_poly_table[][3] = {
+	{0, 0, 0},		/* degree 0 */
+	{0x1, 0x1, 0x1},	/* degree 1 */
+	{0x3, 0x3, 0x3},	/* degree 2 and so on.. */
+	{0x3, 0x5, 0x3},	/* x^3+x^2+1(0x5) is reverted x^3+x+1(0x3) */
+	{0x3, 0x9, 0x3},	/* x^4+x^3+1(0x9) is reverted x^4+x+1(0x3) */
+	{0x5, 0xf, 0x17},	/* 0x5 <-> 0x9; 0xf <-> 0x1d; 0x17 <-> 0x1b */
+	{0x3, 0x27, 0x1b},	/* 0x3 <-> 0x21; 0x27 <-> 0x33; 0x1b <-> 0x2d*/
+};
+
+/*
+ * Table of the monic lowest weight irreducible polynomials over GF(2)
+ * starting from degree 7 up to degree 32.
+ * Taken from Handbook of Finite Fields by Gary L. Mullen and
+ * Daniel Penario p.33 Table 2.2.1.
+ * https://people.math.carleton.ca/~daniel/hff/irred/F2-2to10000.txt
+ */
+static const uint32_t default_irreducible_poly[] = {
+	0x3,    /* x^7 + x + 1*/
+	0x1b,   /* x^8 + x^4 + x^3 + x + 1 */
+	0x3,    /* x^9 + x + 1*/
+	0x9,    /* x^10 + x^3 + 1 */
+	0x5,    /* x^11 + x^2 + 1 */
+	0x9,    /* x^12 + x^3 + 1 */
+	0x1b,   /* x^13 + x^4 + x^3 + x + 1 */
+	0x33,   /* x^14 + x^5 + 1 */
+	0x3,    /* x^15 + x + 1 */
+	0x2b,   /* x^16 + x^5 + x^3 + x + 1 */
+	0x9,    /* x^17 + x^3 + 1 */
+	0x9,    /* x^18 + x^3 + 1 */
+	0x27,   /* x^19 + x^5 + x^2 + x + 1 */
+	0x9,    /* x^20 + x^3 + 1 */
+	0x5,    /* x^21 + x^2 + 1 */
+	0x3,    /* x^22 + x + 1 */
+	0x21,   /* x^23 + x^5 + 1 */
+	0x1b,   /* x^24 + x^4 + x^3 + x + 1 */
+	0x9,    /* x^25 + x^3 + 1 */
+	0x1b,   /* x^26 + x^4 + x^3 + x + 1 */
+	0x27,   /* x^27 + x^5 + x^2 + x + 1 */
+	0x3,    /* x^28 + x + 1 */
+	0x5,    /* x^29 + x^2 + 1 */
+	0x3,    /* x^30 + x + 1 */
+	0x9,    /* x^31 + x^3 + 1 */
+	0x8d,   /* x^32 + x^7 + x^3 + x^2 + 1 */
+};
+
+#define MAX_DIVISORS 28 /* 2^24 - 1 */
+
+struct divisors {
+	uint32_t n; /* number of divisors */
+	uint32_t div_arr[MAX_DIVISORS];
+};
+
+/* divisors of (2^n - 1) less than MIN(512, 2^n - 1) for all n in [7, 32] */
+static const struct divisors divisors[] = {
+	{ .n = 0, .div_arr = {} }, /* 2^7-1 is Mersenne prime */
+	{ .n = 6, .div_arr = {3, 5, 15, 17, 51, 85} },
+	{ .n = 2, .div_arr = {7, 73} },
+	{ .n = 6, .div_arr = {3, 11, 31, 33, 93, 341} },
+	{ .n = 2, .div_arr = {23, 89} },
+	{ .n = 19, .div_arr = {3, 5, 7, 9, 13, 15, 21, 35, 39, 45, 63, 65, 91,
+		105, 117, 195, 273, 315, 455} },
+	{ .n = 0, .div_arr = {} }, /* 2^13-1 is Mersenne prime */
+	{ .n = 5, .div_arr = {3, 43, 127, 129, 381} },
+	{ .n = 4, .div_arr = {7, 31, 151, 217} },
+	{ .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} },
+	{ .n = 0, .div_arr = {} }, /* 2^17-1 is Mersenne prime */
+	{ .n = 14, .div_arr = {3, 7, 9, 19, 21, 27, 57, 63, 73, 133, 171, 189,
+		219, 399} },
+	{ .n = 0, .div_arr = {0} }, /* 2^19-1 is Mersenne prime */
+	{ .n = 19, .div_arr = {3, 5, 11, 15, 25, 31, 33, 41, 55, 75, 93, 123,
+		155, 165, 205, 275, 341, 451, 465} },
+	{ .n = 4, .div_arr = {7, 49, 127, 337} },
+	{ .n = 5, .div_arr = {3, 23, 69, 89, 267} },
+	{ .n = 1, .div_arr = {47} },
+	{ .n = 28, .div_arr = {3, 5, 7, 9, 13, 15, 17, 21, 35, 39, 45, 51, 63,
+		65, 85, 91, 105, 117, 119, 153, 195, 221, 241, 255, 273, 315,
+		357, 455} },
+	{ .n = 1, .div_arr = {31} },
+	{ .n = 1, .div_arr = {3} },
+	{ .n = 2, .div_arr = {7, 73} },
+	{ .n = 14, .div_arr = {3, 5, 15, 29, 43, 87, 113, 127, 129, 145, 215,
+		339, 381, 435} },
+	{ .n = 1, .div_arr = {233} },
+	{ .n = 18, .div_arr = {3, 7, 9, 11, 21, 31, 33, 63, 77, 93, 99, 151,
+		217, 231, 279, 331, 341, 453} },
+	{ .n = 0, .div_arr = {} },/* 2^31-1 is Mersenne prime */
+	{ .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} },
+};
+
+static uint32_t
+gf2_mul(uint32_t a, uint32_t b, uint32_t r, int degree)
+{
+	uint64_t product = 0;
+	uint64_t r_poly = r|(1ULL << degree);
+
+	for (; b; b &= (b - 1))
+		product ^= (uint64_t)a << (rte_bsf32(b));
+
+	for (int i = degree * 2 - 1; i >= degree; i--)
+		if (product & (1 << i))
+			product ^= r_poly << (i - degree);
+
+	return product;
+}
+
+static uint32_t
+gf2_pow(uint32_t a, uint32_t pow, uint32_t r, int degree)
+{
+	uint32_t result = 1;
+	unsigned int i;
+
+	for (i = 0; i < (sizeof(pow)*CHAR_BIT - rte_clz32(pow)); i++) {
+		if (pow & (1 << i))
+			result = gf2_mul(result, a, r, degree);
+
+		a = gf2_mul(a, a, r, degree);
+	}
+
+	return result;
+}
+
+static uint32_t
+__thash_get_rand_poly(int poly_degree)
+{
+	uint32_t roots[poly_degree];
+	uint32_t rnd;
+	uint32_t ret_poly = 0;
+	int i, j;
+	bool short_orbit = false;
+
+	/* special case for low degree */
+	if (poly_degree < 7)
+		return irreducible_poly_table[poly_degree][rte_rand() %
+			RTE_DIM(irreducible_poly_table[poly_degree])];
+
+	uint32_t r = default_irreducible_poly[poly_degree - 7];
+
+	do {
+		short_orbit = false;
+		do {
+			rnd = rte_rand() & ((1 << poly_degree) - 1);
+		} while ((rnd == 0) || (rnd == 1));
+
+		/*
+		 * Quick check if random returned one of the roots of
+		 * the initial polynomial.
+		 * In other words if we randomy got x, x^2, x^4, x^8 or x^16
+		 */
+#define ROOT_POLY_MSK ((1 << 1)|(1 << 2)|(1 << 4)|(1 << 8)|(1 << 16))
+		if ((rte_popcount32(rnd) == 1) && (rnd & ROOT_POLY_MSK))
+			return default_irreducible_poly[poly_degree - 7];
+
+		/*
+		 * init array with some random polynomial roots
+		 * applying Frobenius automorphism (i.e. squaring them)
+		 * also checking for short orbits (i.e. if there are repeated roots)
+		 */
+		roots[0] = rnd;
+		for (i = 1; i < poly_degree; i++) {
+			roots[i] = gf2_pow(roots[i - 1], 2, r, poly_degree);
+			if (roots[i] == roots[0])
+				short_orbit = true;
+		}
+	} while (short_orbit);
+
+	/*
+	 * Get coefficients of the polynomial for
+	 * (x - roots[0])(x - roots[1])...(x - roots[n])
+	 */
+	uint32_t poly_coefficients[poly_degree + 1];
+	for (i = 0; i <= poly_degree; i++)
+		poly_coefficients[i] = 0;
+
+	poly_coefficients[0] = 1; /* highest degree term coefficient in the end */
+	for (i = 0; i < (int)poly_degree; i++) {
+		/* multiply by x */
+		for (j = i; j >= 0; j--)
+			poly_coefficients[j + 1] = poly_coefficients[j];
+
+		poly_coefficients[0] = 0;
+
+		/* multiply by root */
+		for (j = 0; j <= i; j++)
+			poly_coefficients[j] ^=
+				gf2_mul(poly_coefficients[j + 1],
+				roots[i], r, poly_degree);
+	}
+
+	for (i = 0; i < poly_degree; i++) {
+		if (poly_coefficients[i]) {
+			RTE_ASSERT(poly_coefficients[i] == 1);
+			ret_poly |= 1 << i;
+		}
+	}
+
+	return ret_poly;
+}
+
+/* test an order of the multiplicative subgroup generated by x */
+static int
+thash_test_poly_order(uint32_t poly, int degree)
+{
+	unsigned int i;
+	int div_idx = degree - 7;
+
+	if (degree < 7)
+		return 0;
+
+	for (i = 0; i < divisors[div_idx].n; i++) {
+		if (gf2_pow(0x2, divisors[div_idx].div_arr[i],
+				poly, degree) == 1)
+			return 1;
+	}
+
+	return 0;
+}
+
+uint32_t
+rte_thash_get_rand_poly(uint32_t poly_degree)
+{
+	uint32_t ret_poly;
+
+	if (poly_degree > 32)
+		return 0;
+
+	do
+		ret_poly = __thash_get_rand_poly(poly_degree);
+	while (thash_test_poly_order(ret_poly, poly_degree));
+
+	return ret_poly;
+}
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 4f13f1d5aa..7ce6ab1121 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -61,4 +61,5 @@ INTERNAL {
 
 	rte_thash_gfni_stub;
 	rte_thash_gfni_bulk_stub;
+	rte_thash_get_rand_poly;
 };
-- 
2.43.0

Re: [PATCH v3 2/4] hash: add dynamic polynomial calculation

[Stephen Hemminger]

On Fri, 11 Oct 2024 18:17:00 +0000
Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:

> +
> +uint32_t
> +rte_thash_get_rand_poly(uint32_t poly_degree)
> +{
> +	uint32_t ret_poly;
> +
> +	if (poly_degree > 32)
> +		return 0;
> +
> +	do
> +		ret_poly = __thash_get_rand_poly(poly_degree);
> +	while (thash_test_poly_order(ret_poly, poly_degree));

Unbounded loop adds some risk, should there be an upper limit on retries.

> +
> +	return ret_poly;
> +}
> diff --git a/lib/hash/version.map b/lib/hash/version.map
> index 4f13f1d5aa..7ce6ab1121 100644
> --- a/lib/hash/version.map
> +++ b/lib/hash/version.map
> @@ -61,4 +61,5 @@ INTERNAL {
>  
>  	rte_thash_gfni_stub;
>  	rte_thash_gfni_bulk_stub;
> +	rte_thash_get_rand_poly;

Why does this function need to be moved to its own file?
Only used in one place in rte_thash.c.

Re: [PATCH v3 2/4] hash: add dynamic polynomial calculation

[Medvedkin, Vladimir]

[-- Attachment #1: Type: text/plain, Size: 1463 bytes --]

Hi Stephen,

On 15/10/2024 23:29, Stephen Hemminger wrote:
> On Fri, 11 Oct 2024 18:17:00 +0000
> Vladimir Medvedkin<vladimir.medvedkin@intel.com>  wrote:
>
>> +
>> +uint32_t
>> +rte_thash_get_rand_poly(uint32_t poly_degree)
>> +{
>> +	uint32_t ret_poly;
>> +
>> +	if (poly_degree > 32)
>> +		return 0;
>> +
>> +	do
>> +		ret_poly = __thash_get_rand_poly(poly_degree);
>> +	while (thash_test_poly_order(ret_poly, poly_degree));
> Unbounded loop adds some risk, should there be an upper limit on retries.

Thisis the probabilisticpartof the algorithm.

__thash_get_rand_poly() returns a random polynomial that either 
satisfies the order criteria (element <x> of the field must generate 
multiplicative subgroup of order not less than some number), or not. The 
probability that it does not meet this criteria is strictly less than 1. 
Thus, with each attempt, the probability of not finding suitable 
polynomial exponentially tends to zero.

>
>> +
>> +	return ret_poly;
>> +}
>> diff --git a/lib/hash/version.map b/lib/hash/version.map
>> index 4f13f1d5aa..7ce6ab1121 100644
>> --- a/lib/hash/version.map
>> +++ b/lib/hash/version.map
>> @@ -61,4 +61,5 @@ INTERNAL {
>>   
>>   	rte_thash_gfni_stub;
>>   	rte_thash_gfni_bulk_stub;
>> +	rte_thash_get_rand_poly;
> Why does this function need to be moved to its own file?
> Only used in one place in rte_thash.c.
It was done just for convenience. If you insist, I'll move it to rte_thash.c

-- 
Regards,
Vladimir

[-- Attachment #2: Type: text/html, Size: 3178 bytes --]

Re: [PATCH v3 2/4] hash: add dynamic polynomial calculation

[Stephen Hemminger]

On Wed, 16 Oct 2024 17:28:17 +0100
"Medvedkin, Vladimir" <vladimir.medvedkin@intel.com> wrote:

> Hi Stephen,
> 
> On 15/10/2024 23:29, Stephen Hemminger wrote:
> > On Fri, 11 Oct 2024 18:17:00 +0000
> > Vladimir Medvedkin<vladimir.medvedkin@intel.com>  wrote:
> >  
> >> +
> >> +uint32_t
> >> +rte_thash_get_rand_poly(uint32_t poly_degree)
> >> +{
> >> +	uint32_t ret_poly;
> >> +
> >> +	if (poly_degree > 32)

Error log here?

> >> +		return 0;
> >> +
> >> +	do
> >> +		ret_poly = __thash_get_rand_poly(poly_degree);
> >> +	while (thash_test_poly_order(ret_poly, poly_degree));  
> > Unbounded loop adds some risk, should there be an upper limit on retries.  
> 
> Thisis the probabilisticpartof the algorithm.
> 
> __thash_get_rand_poly() returns a random polynomial that either 
> satisfies the order criteria (element <x> of the field must generate 
> multiplicative subgroup of order not less than some number), or not. The 
> probability that it does not meet this criteria is strictly less than 1. 
> Thus, with each attempt, the probability of not finding suitable 
> polynomial exponentially tends to zero.

Never trust probabilities to converge. Just add an upper bound of something big
like 32 tries and log error and give up.

> 
> >  
> >> +
> >> +	return ret_poly;
> >> +}
> >> diff --git a/lib/hash/version.map b/lib/hash/version.map
> >> index 4f13f1d5aa..7ce6ab1121 100644
> >> --- a/lib/hash/version.map
> >> +++ b/lib/hash/version.map
> >> @@ -61,4 +61,5 @@ INTERNAL {
> >>   
> >>   	rte_thash_gfni_stub;
> >>   	rte_thash_gfni_bulk_stub;
> >> +	rte_thash_get_rand_poly;  
> > Why does this function need to be moved to its own file?
> > Only used in one place in rte_thash.c.  
> It was done just for convenience. If you insist, I'll move it to rte_thash.c


It is actually good to put in seperate file, but you can keep the old name.
Best to reserve names with rte_ prefix for user visible prefixes.

Re: [PATCH v3 2/4] hash: add dynamic polynomial calculation

[Medvedkin, Vladimir]

[-- Attachment #1: Type: text/plain, Size: 3349 bytes --]

Hi Stephen,

On 17/10/2024 04:23, Stephen Hemminger wrote:
> On Wed, 16 Oct 2024 17:28:17 +0100
> "Medvedkin, Vladimir"<vladimir.medvedkin@intel.com>  wrote:
>
>> Hi Stephen,
>>
>> On 15/10/2024 23:29, Stephen Hemminger wrote:
>>> On Fri, 11 Oct 2024 18:17:00 +0000
>>> Vladimir Medvedkin<vladimir.medvedkin@intel.com>   wrote:
>>>   
>>>> +
>>>> +uint32_t
>>>> +rte_thash_get_rand_poly(uint32_t poly_degree)
>>>> +{
>>>> +	uint32_t ret_poly;
>>>> +
>>>> +	if (poly_degree > 32)
> Error log here?
>
>>>> +		return 0;
>>>> +
>>>> +	do
>>>> +		ret_poly = __thash_get_rand_poly(poly_degree);
>>>> +	while (thash_test_poly_order(ret_poly, poly_degree));
>>> Unbounded loop adds some risk, should there be an upper limit on retries.
>> Thisis the probabilisticpartof the algorithm.
>>
>> __thash_get_rand_poly() returns a random polynomial that either
>> satisfies the order criteria (element <x> of the field must generate
>> multiplicative subgroup of order not less than some number), or not. The
>> probability that it does not meet this criteria is strictly less than 1.
>> Thus, with each attempt, the probability of not finding suitable
>> polynomial exponentially tends to zero.
> Never trust probabilities to converge. Just add an upper bound of something big
> like 32 tries and log error and give up.

I disagree. I don't want this to give up. Take a look at this algorithm 
from the perspective of an equivalent bounded random function:

https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171 
<https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171>

or

https://elixir.bootlin.com/linux/v6.11.3/source/include/linux/random.h#L60

The job must be done. Imagine if these random functions may return 
something like "EAGAIN". The caller needs random value at this pointto 
continue, so there are only 2 options left - either panic or call the 
function again.

We definitely don't want to panic here. But calling this algorithm again 
will have the same effect as not having runtime bound inside the 
algorithm at all. In other words, here I prefer to have "Las Vegas" 
rather than "Monte Carlo" algorithm. And it make sense since in these 
particular cases (i.e. my algorithm and bounded random implementations) 
we have:

1. A simple deterministic algorithm for checking the complianceof 
somerandomvariablewith a condition

2. Every random variable is independent from each other. So probability 
of getting unsatisfying random variable after n steps drops 
exponentially (negative outcome probabilities multiplies). That's why 
those algorithms runtime expected value is bounded.


>
>>>   
>>>> +
>>>> +	return ret_poly;
>>>> +}
>>>> diff --git a/lib/hash/version.map b/lib/hash/version.map
>>>> index 4f13f1d5aa..7ce6ab1121 100644
>>>> --- a/lib/hash/version.map
>>>> +++ b/lib/hash/version.map
>>>> @@ -61,4 +61,5 @@ INTERNAL {
>>>>    
>>>>    	rte_thash_gfni_stub;
>>>>    	rte_thash_gfni_bulk_stub;
>>>> +	rte_thash_get_rand_poly;
>>> Why does this function need to be moved to its own file?
>>> Only used in one place in rte_thash.c.
>> It was done just for convenience. If you insist, I'll move it to rte_thash.c
>
> It is actually good to put in seperate file, but you can keep the old name.
> Best to reserve names with rte_ prefix for user visible prefixes.
>
>
-- 
Regards,
Vladimir

[-- Attachment #2: Type: text/html, Size: 8261 bytes --]

[PATCH v3 3/4] hash: implement RSS hash key generation API

[Vladimir Medvedkin]

This patch implements Toeplitz hash key generation function using the new
polynomial generation function.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/rte_thash.c | 23 ++++++++++++++++++-----
 1 file changed, 18 insertions(+), 5 deletions(-)

diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index 5c3d246657..80fcfe866f 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -803,11 +803,24 @@ int
 rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_log,
 	uint32_t entropy_start, size_t entropy_sz)
 {
-	RTE_SET_USED(key);
-	RTE_SET_USED(key_len);
-	RTE_SET_USED(reta_sz_log);
-	RTE_SET_USED(entropy_start);
-	RTE_SET_USED(entropy_sz);
+	size_t i, end, start;
+
+	/* define lfsr sequence range*/
+	end = entropy_start + entropy_sz + TOEPLITZ_HASH_LEN - 1;
+	start = end - (entropy_sz + reta_sz_log - 1);
+
+	if ((key == NULL) || (key_len * CHAR_BIT < entropy_start + entropy_sz) ||
+			(entropy_sz < reta_sz_log) || (reta_sz_log > TOEPLITZ_HASH_LEN))
+		return -EINVAL;
+
+	struct thash_lfsr *lfsr = alloc_lfsr(reta_sz_log);
+	if (lfsr == NULL)
+		return -ENOMEM;
+
+	for (i = start; i < end; i++)
+		set_bit(key, get_bit_lfsr(lfsr), i);
+
+	free_lfsr(lfsr);
 
 	return 0;
 }
-- 
2.43.0

[PATCH v3 4/4] test/thash: add tests for RSS key generation API

[Vladimir Medvedkin]

This patch adds tests for RSS key generation. In this test we measure
distribution of hash LSBs for a given random tuple where only some part
of bits is variable.

At first we generate random hash key and measure the worst distribution
for a given ReTa size value (RETA_SZ_LOG). Then we adjust the key with
the new API and run the test again, noting the new distribution. Finally,
we also measure said distribution for some well known RSS hash key which
is used in some PMDs.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 app/test/test_thash.c | 108 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 108 insertions(+)

diff --git a/app/test/test_thash.c b/app/test/test_thash.c
index 65d42fd900..fca2ba03dd 100644
--- a/app/test/test_thash.c
+++ b/app/test/test_thash.c
@@ -7,6 +7,7 @@
 #include <rte_ip.h>
 #include <rte_random.h>
 #include <rte_malloc.h>
+#include <rte_byteorder.h>
 
 #include "test.h"
 
@@ -935,6 +936,112 @@ test_adjust_tuple_mult_reta(void)
 	return TEST_SUCCESS;
 }
 
+#define RETA_SZ_LOG		11
+#define RSS_KEY_SZ		40
+#define RETA_SZ			(1 << RETA_SZ_LOG)
+#define NB_HASH_ITER	RETA_SZ
+#define NB_TEST_ITER	10
+
+static inline void
+run_hash_calc_loop(uint8_t *key, union rte_thash_tuple *tuple,
+					unsigned int *rss_reta_hits)
+{
+	uint32_t rss_hash;
+	int i;
+
+	for (i = 0; i < NB_HASH_ITER; i++) {
+		/* variable part starts from the most significant bit */
+		tuple->v4.dport = (i << (sizeof(tuple->v4.dport) * CHAR_BIT -
+			RETA_SZ_LOG));
+		/*
+		 * swap sport and dport on LE arch since rte_softrss()
+		 * works with host byte order uint32_t values
+		 */
+		tuple->v4.dport = rte_cpu_to_be_16(tuple->v4.dport);
+		tuple->v4.sctp_tag = rte_be_to_cpu_32(tuple->v4.sctp_tag);
+		rss_hash = rte_softrss((uint32_t *)tuple,
+				RTE_THASH_V4_L4_LEN, key);
+		/* unroll swap, required only for sport */
+		tuple->v4.sctp_tag = rte_cpu_to_be_32(tuple->v4.sctp_tag);
+		rss_reta_hits[rss_hash & (RETA_SZ - 1)]++;
+	}
+}
+
+static int
+hash_calc_iteration(unsigned int *min_before, unsigned int *max_before,
+		unsigned int *min_after, unsigned int *max_after,
+		unsigned int *min_default, unsigned int *max_default)
+{
+	uint8_t key[RSS_KEY_SZ] = {0};
+	union rte_thash_tuple tuple;
+	unsigned int rss_reta_hits_before_adjust[RETA_SZ] = {0};
+	unsigned int rss_reta_hits_after_adjust[RETA_SZ] = {0};
+	unsigned int rss_reta_hits_default_key[RETA_SZ] = {0};
+	int i;
+
+	for (i = 0; i < RSS_KEY_SZ; i++)
+		key[i] = rte_rand();
+
+	tuple.v4.src_addr = rte_rand();
+	tuple.v4.dst_addr = rte_rand();
+	tuple.v4.sport = rte_rand();
+
+	run_hash_calc_loop(key, &tuple, rss_reta_hits_before_adjust);
+
+	int ret = rte_thash_gen_key(key, RSS_KEY_SZ, RETA_SZ_LOG,
+		offsetof(union rte_thash_tuple, v4.dport)*CHAR_BIT,
+		RETA_SZ_LOG);
+
+	if (ret) {
+		printf("Can't generate key\n");
+		return -1;
+	}
+
+	run_hash_calc_loop(key, &tuple, rss_reta_hits_after_adjust);
+
+	run_hash_calc_loop(default_rss_key, &tuple, rss_reta_hits_default_key);
+
+	for (i = 0; i < RETA_SZ; i++) {
+		*min_before = RTE_MIN(*min_before, rss_reta_hits_before_adjust[i]);
+		*max_before = RTE_MAX(*max_before, rss_reta_hits_before_adjust[i]);
+		*min_after = RTE_MIN(*min_after, rss_reta_hits_after_adjust[i]);
+		*max_after = RTE_MAX(*max_after, rss_reta_hits_after_adjust[i]);
+		*min_default = RTE_MIN(*min_default, rss_reta_hits_default_key[i]);
+		*max_default = RTE_MAX(*max_default, rss_reta_hits_default_key[i]);
+	}
+
+	return 0;
+}
+
+static int
+test_keygen(void)
+{
+	int i, ret;
+	unsigned int min_before = UINT32_MAX;
+	unsigned int min_after = UINT32_MAX;
+	unsigned int min_default = UINT32_MAX;
+	unsigned int max_before = 0;
+	unsigned int max_after = 0;
+	unsigned int max_default = 0;
+
+	for (i = 0; i < NB_TEST_ITER; i++) {
+		/* calculates the worst distribution for each key */
+		ret = hash_calc_iteration(&min_before, &max_before, &min_after,
+			&max_after, &min_default, &max_default);
+		if (ret)
+			return ret;
+	}
+
+	printf("RSS before key adjustment: min=%d, max=%d\n",
+		min_before, max_before);
+	printf("RSS after key adjustment: min=%d, max=%d\n",
+		min_after, max_after);
+	printf("RSS default key: min=%d, max=%d\n",
+		min_default, max_default);
+
+	return TEST_SUCCESS;
+}
+
 static struct unit_test_suite thash_tests = {
 	.suite_name = "thash autotest",
 	.setup = NULL,
@@ -956,6 +1063,7 @@ static struct unit_test_suite thash_tests = {
 	TEST_CASE(test_predictable_rss_multirange),
 	TEST_CASE(test_adjust_tuple),
 	TEST_CASE(test_adjust_tuple_mult_reta),
+	TEST_CASE(test_keygen),
 	TEST_CASES_END()
 	}
 };
-- 
2.43.0

[PATCH v4 0/4] RSS hash key generation

[Vladimir Medvedkin]

Currently there are 2 methods to get the RSS hash key. The first method is to
randomly generate it. The second one is to use well known RSS hash keys. Both
methods have drawbacks. The first method not always provides a good hash
distribution. The second one does, but not for all ReTa sizes and not for all
traffic types. Additionaly, since these RSS hash keys are well known, they could
potentially be vulnerable to hash-collision DoS attacks.

The proposed API could be used to address both of these issues - the key can be
randomy generated and tailored to specific traffic profile distribution. For
example, if we know that we are receiving flows where source/destination
addresses are fixed or limited to a small quantity, but source port has good
distribution, we could generate an RSS key that will give us good distribution
across our ReTa.

v4
 - address some comments
 - update release notes
 - rebase to current version

v3
 - change rte_thash_gen_key() arguments types
v2
 - fix some minor issues

Vladimir Medvedkin (4):
  thash: add RSS hash key generation API
  hash: add dynamic polynomial calculation
  hash: implement RSS hash key generation API
  test/thash: add tests for RSS key generation API

 app/test/test_thash.c                  | 108 ++++++++++
 doc/guides/rel_notes/release_24_11.rst |   3 +
 lib/hash/meson.build                   |   1 +
 lib/hash/rte_thash.c                   |  70 +++----
 lib/hash/rte_thash.h                   |  37 ++++
 lib/hash/rte_thash_gf2_poly_math.c     | 260 +++++++++++++++++++++++++
 lib/hash/version.map                   |   3 +
 7 files changed, 443 insertions(+), 39 deletions(-)
 create mode 100644 lib/hash/rte_thash_gf2_poly_math.c

-- 
2.43.0

[PATCH v4 1/4] thash: add RSS hash key generation API

[Vladimir Medvedkin]

Currently the only way to have non static Toeplitz hash key is to
generate it randomly. Such a key may not guarantee good packets
distribution, especially if there are small number of flows.

This patch adds stub implementation of the Toeplitz hash key generation
function, which may improve Toeplitz hash key with respect to hash values
distribution.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/rte_thash.c | 13 +++++++++++++
 lib/hash/rte_thash.h | 24 ++++++++++++++++++++++++
 lib/hash/version.map |  2 ++
 3 files changed, 39 insertions(+)

diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index 99a685f0c8..463992368a 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -856,3 +856,16 @@ rte_thash_adjust_tuple(struct rte_thash_ctx *ctx,
 
 	return ret;
 }
+
+int
+rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_log,
+	uint32_t entropy_start, size_t entropy_sz)
+{
+	RTE_SET_USED(key);
+	RTE_SET_USED(key_len);
+	RTE_SET_USED(reta_sz_log);
+	RTE_SET_USED(entropy_start);
+	RTE_SET_USED(entropy_sz);
+
+	return 0;
+}
diff --git a/lib/hash/rte_thash.h b/lib/hash/rte_thash.h
index e8fdb89530..80313705a1 100644
--- a/lib/hash/rte_thash.h
+++ b/lib/hash/rte_thash.h
@@ -447,6 +447,30 @@ rte_thash_adjust_tuple(struct rte_thash_ctx *ctx,
 	uint32_t desired_value, unsigned int attempts,
 	rte_thash_check_tuple_t fn, void *userdata);
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Modify RSS hash key such that subtuple bits corresponding to `entropy_sz`
+ * bits starting from `entropy_start` will have the most even distribution with
+ * this key with a given ReTa size.
+ *
+ * @param key pointer to the RSS hash key
+ * @param key_len length of the key
+ * @param reta_sz_log log2 of the size of RSS redirection table. i.e. number of
+ *   bits of the rss hash value used to identify RSS ReTa entry
+ * @param entropy_start bit offset from the beginning of the tuple where user
+ *   expects best distribution of the subtuple values.
+ * @param entropy_sz size in bits of the part of subtuple
+ *
+ * @return
+ *  0 on success negative otherwise
+ */
+__rte_experimental
+int
+rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_log,
+	uint32_t entropy_start, size_t entropy_sz);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 11a5394a45..4f13f1d5aa 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -52,6 +52,8 @@ EXPERIMENTAL {
 
 	# added in 24.07
 	rte_hash_rcu_qsbr_dq_reclaim;
+	# added in 24.11
+	rte_thash_gen_key;
 };
 
 INTERNAL {
-- 
2.43.0

Re: [PATCH v4 1/4] thash: add RSS hash key generation API

[Stephen Hemminger]

On Thu, 24 Oct 2024 18:46:53 +0000
Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:

> Currently the only way to have non static Toeplitz hash key is to
> generate it randomly. Such a key may not guarantee good packets
> distribution, especially if there are small number of flows.
> 
> This patch adds stub implementation of the Toeplitz hash key generation
> function, which may improve Toeplitz hash key with respect to hash values
> distribution.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>

Acked-by: Stephen Hemminger <stephen@networkplumber.org>

[PATCH v4 2/4] hash: add dynamic polynomial calculation

[Vladimir Medvedkin]

Current polynomial table has the following limitations:

1. It has polynomials up to degree 16
2. For each degree there are only 4 polynomials

The above results in less entropy when generating Toeplitz hash key
subsequences.

This patch replaces the current static table approach with dynamic
polynomial calculation for polynomials of degree 7 or higher, resulting
in better entropy of generated RSS hash key.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/meson.build               |   1 +
 lib/hash/rte_thash.c               |  44 +----
 lib/hash/rte_thash.h               |  13 ++
 lib/hash/rte_thash_gf2_poly_math.c | 260 +++++++++++++++++++++++++++++
 lib/hash/version.map               |   1 +
 5 files changed, 280 insertions(+), 39 deletions(-)
 create mode 100644 lib/hash/rte_thash_gf2_poly_math.c

diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa93..7ce504ee8b 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -23,6 +23,7 @@ sources = files(
         'rte_fbk_hash.c',
         'rte_thash.c',
         'rte_thash_gfni.c',
+        'rte_thash_gf2_poly_math.c',
 )
 
 deps += ['net']
diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index 463992368a..da35aec860 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -31,33 +31,6 @@ static struct rte_tailq_elem rte_thash_tailq = {
 };
 EAL_REGISTER_TAILQ(rte_thash_tailq)
 
-/**
- * Table of some irreducible polinomials over GF(2).
- * For lfsr they are represented in BE bit order, and
- * x^0 is masked out.
- * For example, poly x^5 + x^2 + 1 will be represented
- * as (101001b & 11111b) = 01001b = 0x9
- */
-static const uint32_t irreducible_poly_table[][4] = {
-	{0, 0, 0, 0},	/** < degree 0 */
-	{1, 1, 1, 1},	/** < degree 1 */
-	{0x3, 0x3, 0x3, 0x3},	/** < degree 2 and so on... */
-	{0x5, 0x3, 0x5, 0x3},
-	{0x9, 0x3, 0x9, 0x3},
-	{0x9, 0x1b, 0xf, 0x5},
-	{0x21, 0x33, 0x1b, 0x2d},
-	{0x41, 0x11, 0x71, 0x9},
-	{0x71, 0xa9, 0xf5, 0x8d},
-	{0x21, 0xd1, 0x69, 0x1d9},
-	{0x81, 0x2c1, 0x3b1, 0x185},
-	{0x201, 0x541, 0x341, 0x461},
-	{0x941, 0x609, 0xe19, 0x45d},
-	{0x1601, 0x1f51, 0x1171, 0x359},
-	{0x2141, 0x2111, 0x2db1, 0x2109},
-	{0x4001, 0x801, 0x101, 0x7301},
-	{0x7781, 0xa011, 0x4211, 0x86d9},
-};
-
 struct thash_lfsr {
 	uint32_t	ref_cnt;
 	uint32_t	poly;
@@ -159,13 +132,6 @@ get_rev_bit_lfsr(struct thash_lfsr *lfsr)
 	return ret;
 }
 
-static inline uint32_t
-thash_get_rand_poly(uint32_t poly_degree)
-{
-	return irreducible_poly_table[poly_degree][rte_rand() %
-		RTE_DIM(irreducible_poly_table[poly_degree])];
-}
-
 static inline uint32_t
 get_rev_poly(uint32_t poly, int degree)
 {
@@ -191,19 +157,19 @@ get_rev_poly(uint32_t poly, int degree)
 }
 
 static struct thash_lfsr *
-alloc_lfsr(struct rte_thash_ctx *ctx)
+alloc_lfsr(uint32_t poly_degree)
 {
 	struct thash_lfsr *lfsr;
 	uint32_t i;
 
-	if (ctx == NULL)
+	if ((poly_degree > 32) || (poly_degree == 0))
 		return NULL;
 
 	lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
 	if (lfsr == NULL)
 		return NULL;
 
-	lfsr->deg = ctx->reta_sz_log;
+	lfsr->deg = poly_degree;
 	lfsr->poly = thash_get_rand_poly(lfsr->deg);
 	do {
 		lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1);
@@ -484,7 +450,7 @@ insert_before(struct rte_thash_ctx *ctx,
 	int ret;
 
 	if (end < cur_ent->offset) {
-		ent->lfsr = alloc_lfsr(ctx);
+		ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
 		if (ent->lfsr == NULL) {
 			rte_free(ent);
 			return -ENOMEM;
@@ -637,7 +603,7 @@ rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len,
 		continue;
 	}
 
-	ent->lfsr = alloc_lfsr(ctx);
+	ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
 	if (ent->lfsr == NULL) {
 		rte_free(ent);
 		return -ENOMEM;
diff --git a/lib/hash/rte_thash.h b/lib/hash/rte_thash.h
index 80313705a1..a8fda72896 100644
--- a/lib/hash/rte_thash.h
+++ b/lib/hash/rte_thash.h
@@ -108,6 +108,19 @@ union rte_thash_tuple {
 	struct rte_ipv6_tuple	v6;
 };
 
+/** @internal
+ *  @brief Generates a random polynomial
+ *
+ * @param poly_degree
+ *   degree of the polynomial
+ *
+ * @return
+ *   random polynomial
+ */
+__rte_internal
+uint32_t
+thash_get_rand_poly(uint32_t poly_degree);
+
 /**
  * Prepare special converted key to use with rte_softrss_be()
  * @param orig
diff --git a/lib/hash/rte_thash_gf2_poly_math.c b/lib/hash/rte_thash_gf2_poly_math.c
new file mode 100644
index 0000000000..1c62974e71
--- /dev/null
+++ b/lib/hash/rte_thash_gf2_poly_math.c
@@ -0,0 +1,260 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2024 Intel Corporation
+ */
+#include <rte_random.h>
+#include <rte_common.h>
+#include <rte_bitops.h>
+#include <rte_debug.h>
+#include <rte_thash.h>
+#include <rte_log.h>
+
+#define MAX_TOEPLITZ_KEY_LENGTH 64
+RTE_LOG_REGISTER_SUFFIX(thash_poly_logtype, thash_poly, INFO);
+#define RTE_LOGTYPE_HASH thash_poly_logtype
+#define HASH_LOG(level, ...) \
+	RTE_LOG_LINE(level, HASH, "" __VA_ARGS__)
+
+/*
+ * Finite field math for field extensions with irreducing polynomial
+ * of degree <= 32.
+ * Polynomials are represented with 2 arguments - uint32_t poly and int degree.
+ * poly argument does not hold the highest degree coefficient,
+ * so full polynomial can be expressed as poly|(1ULL << degree).
+ * The algorithm to produce random irreducible polynomial was inspired by:
+ * "Computation in finite fields" by John Kerl, Chapter 10.4.
+ */
+
+static const uint32_t irreducible_poly_table[][3] = {
+	{0, 0, 0},		/* degree 0 */
+	{0x1, 0x1, 0x1},	/* degree 1 */
+	{0x3, 0x3, 0x3},	/* degree 2 and so on.. */
+	{0x3, 0x5, 0x3},	/* x^3+x^2+1(0x5) is reverted x^3+x+1(0x3) */
+	{0x3, 0x9, 0x3},	/* x^4+x^3+1(0x9) is reverted x^4+x+1(0x3) */
+	{0x5, 0xf, 0x17},	/* 0x5 <-> 0x9; 0xf <-> 0x1d; 0x17 <-> 0x1b */
+	{0x3, 0x27, 0x1b},	/* 0x3 <-> 0x21; 0x27 <-> 0x33; 0x1b <-> 0x2d*/
+};
+
+/*
+ * Table of the monic lowest weight irreducible polynomials over GF(2)
+ * starting from degree 7 up to degree 32.
+ * Taken from Handbook of Finite Fields by Gary L. Mullen and
+ * Daniel Penario p.33 Table 2.2.1.
+ * https://people.math.carleton.ca/~daniel/hff/irred/F2-2to10000.txt
+ */
+static const uint32_t default_irreducible_poly[] = {
+	0x3,    /* x^7 + x + 1*/
+	0x1b,   /* x^8 + x^4 + x^3 + x + 1 */
+	0x3,    /* x^9 + x + 1*/
+	0x9,    /* x^10 + x^3 + 1 */
+	0x5,    /* x^11 + x^2 + 1 */
+	0x9,    /* x^12 + x^3 + 1 */
+	0x1b,   /* x^13 + x^4 + x^3 + x + 1 */
+	0x33,   /* x^14 + x^5 + 1 */
+	0x3,    /* x^15 + x + 1 */
+	0x2b,   /* x^16 + x^5 + x^3 + x + 1 */
+	0x9,    /* x^17 + x^3 + 1 */
+	0x9,    /* x^18 + x^3 + 1 */
+	0x27,   /* x^19 + x^5 + x^2 + x + 1 */
+	0x9,    /* x^20 + x^3 + 1 */
+	0x5,    /* x^21 + x^2 + 1 */
+	0x3,    /* x^22 + x + 1 */
+	0x21,   /* x^23 + x^5 + 1 */
+	0x1b,   /* x^24 + x^4 + x^3 + x + 1 */
+	0x9,    /* x^25 + x^3 + 1 */
+	0x1b,   /* x^26 + x^4 + x^3 + x + 1 */
+	0x27,   /* x^27 + x^5 + x^2 + x + 1 */
+	0x3,    /* x^28 + x + 1 */
+	0x5,    /* x^29 + x^2 + 1 */
+	0x3,    /* x^30 + x + 1 */
+	0x9,    /* x^31 + x^3 + 1 */
+	0x8d,   /* x^32 + x^7 + x^3 + x^2 + 1 */
+};
+
+#define MAX_DIVISORS 28 /* 2^24 - 1 */
+
+struct divisors {
+	uint32_t n; /* number of divisors */
+	uint32_t div_arr[MAX_DIVISORS];
+};
+
+/* divisors of (2^n - 1) less than MIN(512, 2^n - 1) for all n in [7, 32] */
+static const struct divisors divisors[] = {
+	{ .n = 0, .div_arr = {} }, /* 2^7-1 is Mersenne prime */
+	{ .n = 6, .div_arr = {3, 5, 15, 17, 51, 85} },
+	{ .n = 2, .div_arr = {7, 73} },
+	{ .n = 6, .div_arr = {3, 11, 31, 33, 93, 341} },
+	{ .n = 2, .div_arr = {23, 89} },
+	{ .n = 19, .div_arr = {3, 5, 7, 9, 13, 15, 21, 35, 39, 45, 63, 65, 91,
+		105, 117, 195, 273, 315, 455} },
+	{ .n = 0, .div_arr = {} }, /* 2^13-1 is Mersenne prime */
+	{ .n = 5, .div_arr = {3, 43, 127, 129, 381} },
+	{ .n = 4, .div_arr = {7, 31, 151, 217} },
+	{ .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} },
+	{ .n = 0, .div_arr = {} }, /* 2^17-1 is Mersenne prime */
+	{ .n = 14, .div_arr = {3, 7, 9, 19, 21, 27, 57, 63, 73, 133, 171, 189,
+		219, 399} },
+	{ .n = 0, .div_arr = {0} }, /* 2^19-1 is Mersenne prime */
+	{ .n = 19, .div_arr = {3, 5, 11, 15, 25, 31, 33, 41, 55, 75, 93, 123,
+		155, 165, 205, 275, 341, 451, 465} },
+	{ .n = 4, .div_arr = {7, 49, 127, 337} },
+	{ .n = 5, .div_arr = {3, 23, 69, 89, 267} },
+	{ .n = 1, .div_arr = {47} },
+	{ .n = 28, .div_arr = {3, 5, 7, 9, 13, 15, 17, 21, 35, 39, 45, 51, 63,
+		65, 85, 91, 105, 117, 119, 153, 195, 221, 241, 255, 273, 315,
+		357, 455} },
+	{ .n = 1, .div_arr = {31} },
+	{ .n = 1, .div_arr = {3} },
+	{ .n = 2, .div_arr = {7, 73} },
+	{ .n = 14, .div_arr = {3, 5, 15, 29, 43, 87, 113, 127, 129, 145, 215,
+		339, 381, 435} },
+	{ .n = 1, .div_arr = {233} },
+	{ .n = 18, .div_arr = {3, 7, 9, 11, 21, 31, 33, 63, 77, 93, 99, 151,
+		217, 231, 279, 331, 341, 453} },
+	{ .n = 0, .div_arr = {} },/* 2^31-1 is Mersenne prime */
+	{ .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} },
+};
+
+static uint32_t
+gf2_mul(uint32_t a, uint32_t b, uint32_t r, int degree)
+{
+	uint64_t product = 0;
+	uint64_t r_poly = r|(1ULL << degree);
+
+	for (; b; b &= (b - 1))
+		product ^= (uint64_t)a << (rte_bsf32(b));
+
+	for (int i = degree * 2 - 1; i >= degree; i--)
+		if (product & (1 << i))
+			product ^= r_poly << (i - degree);
+
+	return product;
+}
+
+static uint32_t
+gf2_pow(uint32_t a, uint32_t pow, uint32_t r, int degree)
+{
+	uint32_t result = 1;
+	unsigned int i;
+
+	for (i = 0; i < (sizeof(pow)*CHAR_BIT - rte_clz32(pow)); i++) {
+		if (pow & (1 << i))
+			result = gf2_mul(result, a, r, degree);
+
+		a = gf2_mul(a, a, r, degree);
+	}
+
+	return result;
+}
+
+static uint32_t
+__thash_get_rand_poly(int poly_degree)
+{
+	uint32_t roots[poly_degree];
+	uint32_t rnd;
+	uint32_t ret_poly = 0;
+	int i, j;
+	bool short_orbit = false;
+
+	/* special case for low degree */
+	if (poly_degree < 7)
+		return irreducible_poly_table[poly_degree][rte_rand() %
+			RTE_DIM(irreducible_poly_table[poly_degree])];
+
+	uint32_t r = default_irreducible_poly[poly_degree - 7];
+
+	do {
+		short_orbit = false;
+		do {
+			rnd = rte_rand() & ((1 << poly_degree) - 1);
+		} while ((rnd == 0) || (rnd == 1));
+
+		/*
+		 * Quick check if random returned one of the roots of
+		 * the initial polynomial.
+		 * In other words if we randomy got x, x^2, x^4, x^8 or x^16
+		 */
+#define ROOT_POLY_MSK ((1 << 1)|(1 << 2)|(1 << 4)|(1 << 8)|(1 << 16))
+		if ((rte_popcount32(rnd) == 1) && (rnd & ROOT_POLY_MSK))
+			return default_irreducible_poly[poly_degree - 7];
+
+		/*
+		 * init array with some random polynomial roots
+		 * applying Frobenius automorphism (i.e. squaring them)
+		 * also checking for short orbits (i.e. if there are repeated roots)
+		 */
+		roots[0] = rnd;
+		for (i = 1; i < poly_degree; i++) {
+			roots[i] = gf2_pow(roots[i - 1], 2, r, poly_degree);
+			if (roots[i] == roots[0])
+				short_orbit = true;
+		}
+	} while (short_orbit);
+
+	/*
+	 * Get coefficients of the polynomial for
+	 * (x - roots[0])(x - roots[1])...(x - roots[n])
+	 */
+	uint32_t poly_coefficients[poly_degree + 1];
+	for (i = 0; i <= poly_degree; i++)
+		poly_coefficients[i] = 0;
+
+	poly_coefficients[0] = 1; /* highest degree term coefficient in the end */
+	for (i = 0; i < (int)poly_degree; i++) {
+		/* multiply by x */
+		for (j = i; j >= 0; j--)
+			poly_coefficients[j + 1] = poly_coefficients[j];
+
+		poly_coefficients[0] = 0;
+
+		/* multiply by root */
+		for (j = 0; j <= i; j++)
+			poly_coefficients[j] ^=
+				gf2_mul(poly_coefficients[j + 1],
+				roots[i], r, poly_degree);
+	}
+
+	for (i = 0; i < poly_degree; i++) {
+		if (poly_coefficients[i]) {
+			RTE_ASSERT(poly_coefficients[i] == 1);
+			ret_poly |= 1 << i;
+		}
+	}
+
+	return ret_poly;
+}
+
+/* test an order of the multiplicative subgroup generated by x */
+static int
+thash_test_poly_order(uint32_t poly, int degree)
+{
+	unsigned int i;
+	int div_idx = degree - 7;
+
+	if (degree < 7)
+		return 0;
+
+	for (i = 0; i < divisors[div_idx].n; i++) {
+		if (gf2_pow(0x2, divisors[div_idx].div_arr[i],
+				poly, degree) == 1)
+			return 1;
+	}
+
+	return 0;
+}
+
+uint32_t
+thash_get_rand_poly(uint32_t poly_degree)
+{
+	uint32_t ret_poly;
+
+	if (poly_degree > 32) {
+		HASH_LOG(ERR, "Wrong polynomial degree %d, must be in range [1, 32]", poly_degree);
+		return 0;
+	}
+
+	do
+		ret_poly = __thash_get_rand_poly(poly_degree);
+	while (thash_test_poly_order(ret_poly, poly_degree));
+
+	return ret_poly;
+}
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 4f13f1d5aa..a0dd86807f 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -61,4 +61,5 @@ INTERNAL {
 
 	rte_thash_gfni_stub;
 	rte_thash_gfni_bulk_stub;
+	thash_get_rand_poly;
 };
-- 
2.43.0

Re: [PATCH v4 2/4] hash: add dynamic polynomial calculation

[Stephen Hemminger]

On Thu, 24 Oct 2024 18:46:54 +0000
Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:

> Current polynomial table has the following limitations:
> 
> 1. It has polynomials up to degree 16
> 2. For each degree there are only 4 polynomials
> 
> The above results in less entropy when generating Toeplitz hash key
> subsequences.
> 
> This patch replaces the current static table approach with dynamic
> polynomial calculation for polynomials of degree 7 or higher, resulting
> in better entropy of generated RSS hash key.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
Acked-by: Stephen Hemminger <stephen@networkplumber.org>

[PATCH v4 3/4] hash: implement RSS hash key generation API

[Vladimir Medvedkin]

This patch implements Toeplitz hash key generation function using the new
polynomial generation function.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 doc/guides/rel_notes/release_24_11.rst |  3 +++
 lib/hash/rte_thash.c                   | 23 ++++++++++++++++++-----
 2 files changed, 21 insertions(+), 5 deletions(-)

diff --git a/doc/guides/rel_notes/release_24_11.rst b/doc/guides/rel_notes/release_24_11.rst
index fa4822d928..9d00a2e1c2 100644
--- a/doc/guides/rel_notes/release_24_11.rst
+++ b/doc/guides/rel_notes/release_24_11.rst
@@ -247,6 +247,9 @@ New Features
   Added ability for node to advertise and update multiple xstat counters,
   that can be retrieved using ``rte_graph_cluster_stats_get``.
 
+* **Added RSS hash key generating API.**
+  A new function ``rte_thash_gen_key`` is provided to modify the RSS hash key
+  to achieve better traffic distribution with RSS.
 
 Removed Items
 -------------
diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index da35aec860..336c228e64 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -827,11 +827,24 @@ int
 rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_log,
 	uint32_t entropy_start, size_t entropy_sz)
 {
-	RTE_SET_USED(key);
-	RTE_SET_USED(key_len);
-	RTE_SET_USED(reta_sz_log);
-	RTE_SET_USED(entropy_start);
-	RTE_SET_USED(entropy_sz);
+	size_t i, end, start;
+
+	/* define lfsr sequence range*/
+	end = entropy_start + entropy_sz + TOEPLITZ_HASH_LEN - 1;
+	start = end - (entropy_sz + reta_sz_log - 1);
+
+	if ((key == NULL) || (key_len * CHAR_BIT < entropy_start + entropy_sz) ||
+			(entropy_sz < reta_sz_log) || (reta_sz_log > TOEPLITZ_HASH_LEN))
+		return -EINVAL;
+
+	struct thash_lfsr *lfsr = alloc_lfsr(reta_sz_log);
+	if (lfsr == NULL)
+		return -ENOMEM;
+
+	for (i = start; i < end; i++)
+		set_bit(key, get_bit_lfsr(lfsr), i);
+
+	free_lfsr(lfsr);
 
 	return 0;
 }
-- 
2.43.0

Re: [PATCH v4 3/4] hash: implement RSS hash key generation API

[Stephen Hemminger]

On Thu, 24 Oct 2024 18:46:55 +0000
Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:

> This patch implements Toeplitz hash key generation function using the new
> polynomial generation function.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
Acked-by: Stephen Hemminger <stephen@networkplumber.org>

[PATCH v4 4/4] test/thash: add tests for RSS key generation API

[Vladimir Medvedkin]

This patch adds tests for RSS key generation. In this test we measure
distribution of hash LSBs for a given random tuple where only some part
of bits is variable.

At first we generate random hash key and measure the worst distribution
for a given ReTa size value (RETA_SZ_LOG). Then we adjust the key with
the new API and run the test again, noting the new distribution. Finally,
we also measure said distribution for some well known RSS hash key which
is used in some PMDs.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 app/test/test_thash.c | 108 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 108 insertions(+)

diff --git a/app/test/test_thash.c b/app/test/test_thash.c
index 0ad6943cf8..b9c6e9118e 100644
--- a/app/test/test_thash.c
+++ b/app/test/test_thash.c
@@ -7,6 +7,7 @@
 #include <rte_ip.h>
 #include <rte_random.h>
 #include <rte_malloc.h>
+#include <rte_byteorder.h>
 
 #include "test.h"
 
@@ -923,6 +924,112 @@ test_adjust_tuple_mult_reta(void)
 	return TEST_SUCCESS;
 }
 
+#define RETA_SZ_LOG		11
+#define RSS_KEY_SZ		40
+#define RETA_SZ			(1 << RETA_SZ_LOG)
+#define NB_HASH_ITER	RETA_SZ
+#define NB_TEST_ITER	10
+
+static inline void
+run_hash_calc_loop(uint8_t *key, union rte_thash_tuple *tuple,
+					unsigned int *rss_reta_hits)
+{
+	uint32_t rss_hash;
+	int i;
+
+	for (i = 0; i < NB_HASH_ITER; i++) {
+		/* variable part starts from the most significant bit */
+		tuple->v4.dport = (i << (sizeof(tuple->v4.dport) * CHAR_BIT -
+			RETA_SZ_LOG));
+		/*
+		 * swap sport and dport on LE arch since rte_softrss()
+		 * works with host byte order uint32_t values
+		 */
+		tuple->v4.dport = rte_cpu_to_be_16(tuple->v4.dport);
+		tuple->v4.sctp_tag = rte_be_to_cpu_32(tuple->v4.sctp_tag);
+		rss_hash = rte_softrss((uint32_t *)tuple,
+				RTE_THASH_V4_L4_LEN, key);
+		/* unroll swap, required only for sport */
+		tuple->v4.sctp_tag = rte_cpu_to_be_32(tuple->v4.sctp_tag);
+		rss_reta_hits[rss_hash & (RETA_SZ - 1)]++;
+	}
+}
+
+static int
+hash_calc_iteration(unsigned int *min_before, unsigned int *max_before,
+		unsigned int *min_after, unsigned int *max_after,
+		unsigned int *min_default, unsigned int *max_default)
+{
+	uint8_t key[RSS_KEY_SZ] = {0};
+	union rte_thash_tuple tuple;
+	unsigned int rss_reta_hits_before_adjust[RETA_SZ] = {0};
+	unsigned int rss_reta_hits_after_adjust[RETA_SZ] = {0};
+	unsigned int rss_reta_hits_default_key[RETA_SZ] = {0};
+	int i;
+
+	for (i = 0; i < RSS_KEY_SZ; i++)
+		key[i] = rte_rand();
+
+	tuple.v4.src_addr = rte_rand();
+	tuple.v4.dst_addr = rte_rand();
+	tuple.v4.sport = rte_rand();
+
+	run_hash_calc_loop(key, &tuple, rss_reta_hits_before_adjust);
+
+	int ret = rte_thash_gen_key(key, RSS_KEY_SZ, RETA_SZ_LOG,
+		offsetof(union rte_thash_tuple, v4.dport)*CHAR_BIT,
+		RETA_SZ_LOG);
+
+	if (ret) {
+		printf("Can't generate key\n");
+		return -1;
+	}
+
+	run_hash_calc_loop(key, &tuple, rss_reta_hits_after_adjust);
+
+	run_hash_calc_loop(default_rss_key, &tuple, rss_reta_hits_default_key);
+
+	for (i = 0; i < RETA_SZ; i++) {
+		*min_before = RTE_MIN(*min_before, rss_reta_hits_before_adjust[i]);
+		*max_before = RTE_MAX(*max_before, rss_reta_hits_before_adjust[i]);
+		*min_after = RTE_MIN(*min_after, rss_reta_hits_after_adjust[i]);
+		*max_after = RTE_MAX(*max_after, rss_reta_hits_after_adjust[i]);
+		*min_default = RTE_MIN(*min_default, rss_reta_hits_default_key[i]);
+		*max_default = RTE_MAX(*max_default, rss_reta_hits_default_key[i]);
+	}
+
+	return 0;
+}
+
+static int
+test_keygen(void)
+{
+	int i, ret;
+	unsigned int min_before = UINT32_MAX;
+	unsigned int min_after = UINT32_MAX;
+	unsigned int min_default = UINT32_MAX;
+	unsigned int max_before = 0;
+	unsigned int max_after = 0;
+	unsigned int max_default = 0;
+
+	for (i = 0; i < NB_TEST_ITER; i++) {
+		/* calculates the worst distribution for each key */
+		ret = hash_calc_iteration(&min_before, &max_before, &min_after,
+			&max_after, &min_default, &max_default);
+		if (ret)
+			return ret;
+	}
+
+	printf("RSS before key adjustment: min=%d, max=%d\n",
+		min_before, max_before);
+	printf("RSS after key adjustment: min=%d, max=%d\n",
+		min_after, max_after);
+	printf("RSS default key: min=%d, max=%d\n",
+		min_default, max_default);
+
+	return TEST_SUCCESS;
+}
+
 static struct unit_test_suite thash_tests = {
 	.suite_name = "thash autotest",
 	.setup = NULL,
@@ -944,6 +1051,7 @@ static struct unit_test_suite thash_tests = {
 	TEST_CASE(test_predictable_rss_multirange),
 	TEST_CASE(test_adjust_tuple),
 	TEST_CASE(test_adjust_tuple_mult_reta),
+	TEST_CASE(test_keygen),
 	TEST_CASES_END()
 	}
 };
-- 
2.43.0

Re: [PATCH v4 4/4] test/thash: add tests for RSS key generation API

[Stephen Hemminger]

On Thu, 24 Oct 2024 18:46:56 +0000
Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:

> This patch adds tests for RSS key generation. In this test we measure
> distribution of hash LSBs for a given random tuple where only some part
> of bits is variable.
> 
> At first we generate random hash key and measure the worst distribution
> for a given ReTa size value (RETA_SZ_LOG). Then we adjust the key with
> the new API and run the test again, noting the new distribution. Finally,
> we also measure said distribution for some well known RSS hash key which
> is used in some PMDs.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
Acked-by: Stephen Hemminger <stephen@networkplumber.org>

Re: [PATCH v4 0/4] RSS hash key generation

[Thomas Monjalon]

24/10/2024 20:46, Vladimir Medvedkin:
> Vladimir Medvedkin (4):
>   thash: add RSS hash key generation API
>   hash: add dynamic polynomial calculation
>   hash: implement RSS hash key generation API
>   test/thash: add tests for RSS key generation API

Squash stub patch and applied with minor improvements for spacing and punctuation.