[RFC 0/4] RSS hash key generation

[RFC 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.

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               |   5 +-
 6 files changed, 435 insertions(+), 41 deletions(-)
 create mode 100644 lib/hash/rte_thash_gf2_poly_math.c

-- 
2.34.1

[RFC 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 |  4 +++-
 3 files changed, 40 insertions(+), 1 deletion(-)

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..7d31fc1ba5 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 {
@@ -59,4 +61,4 @@ INTERNAL {
 
 	rte_thash_gfni_stub;
 	rte_thash_gfni_bulk_stub;
-};
+};
\ No newline at end of file
-- 
2.34.1

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

[Stephen Hemminger]

On Fri,  6 Sep 2024 16:53:15 +0000
Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:

> diff --git a/lib/hash/version.map b/lib/hash/version.map
> index 11a5394a45..7d31fc1ba5 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 {
> @@ -59,4 +61,4 @@ INTERNAL {
>  
>  	rte_thash_gfni_stub;
>  	rte_thash_gfni_bulk_stub;
> -};
> +};
> \ No newline at end of file

Fix your editor settings to always end file with newline

[RFC 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..87d213e741
--- /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 {
+	int n; /* number of divisors */
+	int 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)
+{
+	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 7d31fc1ba5..059d0ff16e 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;
 };
\ No newline at end of file
-- 
2.34.1

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

[Stephen Hemminger]

On Fri,  6 Sep 2024 16:53:16 +0000
Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:

> +struct divisors {
> +	int n; /* number of divisors */
> +	int div_arr[MAX_DIVISORS];
> +};

Why int instead of a fixed size unsigned, like uint32_t?

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

[Medvedkin, Vladimir]

Hi Stephen,

Thanks for the review.

No particular reason, will change it to uint32_t in v2.

On 09/09/2024 01:11, Stephen Hemminger wrote:
> On Fri,  6 Sep 2024 16:53:16 +0000
> Vladimir Medvedkin <vladimir.medvedkin@intel.com> wrote:
>
>> +struct divisors {
>> +	int n; /* number of divisors */
>> +	int div_arr[MAX_DIVISORS];
>> +};
> Why int instead of a fixed size unsigned, like uint32_t?

-- 
Regards,
Vladimir

[RFC 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

[RFC 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