From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 1B8C045BC3; Thu, 24 Oct 2024 20:47:19 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 0EF0543534; Thu, 24 Oct 2024 20:47:19 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.18]) by mails.dpdk.org (Postfix) with ESMTP id C622143527 for ; Thu, 24 Oct 2024 20:47:04 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1729795626; x=1761331626; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=cQYON0P7fIpc0ZZ3mCQSOeY8iODzjAK+qjS5sMhJJjo=; b=X7U0sD9gy20nYr/X3UoMIs1RxI1aITJKDcv4u0X29mAU0gq5Y9YAhSX5 k4VdAtIt4eXyaJ/UXRywxKN/gwM0DEG72P2dJ6VIHyGR1AztYDiEOAjpd iCnR7ioQydlCuZet5J+4hcDal4Xx5NA/Qiu/u3w/JdyC1hC3olHj1SOzi A9X0xep3uwtn+iRJz8VI73tOaVSg4zSHJkLYkT7G5W6+JeVPTYziO/lP0 GXgG9YxwnJZRRwqoHCLEb9hfgtEmilg8U7juJZsqxNMC8MR/cE+YByZ5j CUve6fCwy6JtMhQ/eSEMFrpJbNWk+xBpcDQzThI1UDwUoQ3xpGtDioIG5 Q==; X-CSE-ConnectionGUID: r8TD/zpwSni+FbCcd4nMkQ== X-CSE-MsgGUID: RQuHtlk2STKlY/6IkFER2Q== X-IronPort-AV: E=McAfee;i="6700,10204,11222"; a="29607977" X-IronPort-AV: E=Sophos;i="6.11,199,1725346800"; d="scan'208";a="29607977" Received: from fmviesa004.fm.intel.com ([10.60.135.144]) by orvoesa110.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 24 Oct 2024 11:47:04 -0700 X-CSE-ConnectionGUID: Jv7yW23JSWW0koZuxxrSRg== X-CSE-MsgGUID: O8RPU5kVQC2mGt95fPLhaw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,230,1725346800"; d="scan'208";a="85280464" Received: from silpixa00401176.ir.intel.com ([10.243.23.21]) by fmviesa004.fm.intel.com with ESMTP; 24 Oct 2024 11:47:02 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: stephen@networkplumber.org, Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [PATCH v4 2/4] hash: add dynamic polynomial calculation Date: Thu, 24 Oct 2024 18:46:54 +0000 Message-ID: <20241024184657.901099-3-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20241024184657.901099-1-vladimir.medvedkin@intel.com> References: <20241011181703.236985-1-vladimir.medvedkin@intel.com> <20241024184657.901099-1-vladimir.medvedkin@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org 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 --- 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 +#include +#include +#include +#include +#include + +#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