From patchwork Thu Oct 10 12:33:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 145598 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id C603B45B04; Thu, 10 Oct 2024 14:33:39 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 937B04065A; Thu, 10 Oct 2024 14:33:37 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.14]) by mails.dpdk.org (Postfix) with ESMTP id 4DCAB402D8 for ; Thu, 10 Oct 2024 14:33:34 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1728563615; x=1760099615; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=uPz1i+jNHZAbn6gZLwe6W6ihW/cGY78kU71Bv8u0q6s=; b=f6cWBLP71ft9jVFN8NeRF7kcOOtTtQ+jA0nd8a4mD/BRPw0gf0RxTq5i jWrThOu3i4nf6StoISdc+7sJ5ebIPEuDI/i03Sw8puOjbMtYdF1Q47EI1 LS6JoyR1MJXIXtb0fWL6+2BiycRPX2JYXHS3XXw9eeNuLwX3JRscFlyo+ 3MHnec+gygzlrT2gNR8DihrBupHhsri3Sq8FNZv4lBn33Sqd3+YYAUhA0 kbSREAcitOH8OPZLXpbG3QkLhp1KfHE+4wrNmsIgNEUL1kFC8FVvdXx1g BXwhE3vyO0CoIMso9CBbL5mAuMphi7EdWCTqYaS5ZTda9Q+lfyhKattgz g==; X-CSE-ConnectionGUID: A8WN06HYRFqPJm5K8hDPxQ== X-CSE-MsgGUID: o0YBa/bJSiiRG7mIdMarMA== X-IronPort-AV: E=McAfee;i="6700,10204,11220"; a="31712319" X-IronPort-AV: E=Sophos;i="6.11,193,1725346800"; d="scan'208";a="31712319" Received: from fmviesa005.fm.intel.com ([10.60.135.145]) by orvoesa106.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 10 Oct 2024 05:33:34 -0700 X-CSE-ConnectionGUID: Rs82HGokQg+k56THGtJ7cA== X-CSE-MsgGUID: ji9tXNN3RwmoWX92xVMt+g== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,193,1725346800"; d="scan'208";a="81101881" Received: from unknown (HELO silpixa00401176.ir.intel.com) ([10.243.22.170]) by fmviesa005.fm.intel.com with ESMTP; 10 Oct 2024 05:33:32 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: stephen@networkplumber.org, Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [PATCH v2 1/4] thash: add RSS hash key generation API Date: Thu, 10 Oct 2024 12:33:28 +0000 Message-Id: <20241010123331.749004-2-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241010123331.749004-1-vladimir.medvedkin@intel.com> References: <20241010123331.749004-1-vladimir.medvedkin@intel.com> MIME-Version: 1.0 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 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 --- 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 { From patchwork Thu Oct 10 12:33:29 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 145599 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id CBC2B45B04; Thu, 10 Oct 2024 14:33:47 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 4C7F84066C; Thu, 10 Oct 2024 14:33:39 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.14]) by mails.dpdk.org (Postfix) with ESMTP id DD0DB4065A for ; Thu, 10 Oct 2024 14:33:35 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1728563616; x=1760099616; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=uGctXpVvo3elJqYkPDVuDN6PAEHpgYqsz9hKc7eib4I=; b=kVdTM20gZGmQ6Yh2qcDC73dqiDaoPrfn1eD9plmZQuSiR0w7U4b6+Vmf qrS0Lrt+O/KGBJwP1zbaB8i4dp3oKtSs7Afj1eXe8CyZ5US43dvFOQZkI z2u6smkScfiEUJ0a9aUawc3bQp1/Okd2Vgy7uwASF3GtA8ghDX5MZlsVT UgjokqEwrqB7djU3UiFxY+nYTiSEl7GeZuueANCcFHGy9Kvmuv0bEIZE3 vEY6fUzMzkEPcnYJ8dlS2+G21BSKbhs4GNSPVJ1RrMZnB2g4vyHE0Jjkd Rq5cy6R7RPAaWFYiaQfXKVAyc/7Z3biqSznSQn3U/0OZmtkcrV6ZtN+bI Q==; X-CSE-ConnectionGUID: pWcpfChPQfOjSGO+0q/bFg== X-CSE-MsgGUID: 6IHB1c0oQJGA/DqQIa9yOw== X-IronPort-AV: E=McAfee;i="6700,10204,11220"; a="31712323" X-IronPort-AV: E=Sophos;i="6.11,193,1725346800"; d="scan'208";a="31712323" Received: from fmviesa005.fm.intel.com ([10.60.135.145]) by orvoesa106.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 10 Oct 2024 05:33:36 -0700 X-CSE-ConnectionGUID: jL+p1E5LS1K6rJ7wDdkTDA== X-CSE-MsgGUID: tv1NphWHRdiAT8EP+kEFNA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,193,1725346800"; d="scan'208";a="81101886" Received: from unknown (HELO silpixa00401176.ir.intel.com) ([10.243.22.170]) by fmviesa005.fm.intel.com with ESMTP; 10 Oct 2024 05:33:34 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: stephen@networkplumber.org, Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [PATCH v2 2/4] hash: add dynamic polynomial calculation Date: Thu, 10 Oct 2024 12:33:29 +0000 Message-Id: <20241010123331.749004-3-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241010123331.749004-1-vladimir.medvedkin@intel.com> References: <20241010123331.749004-1-vladimir.medvedkin@intel.com> MIME-Version: 1.0 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 | 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 +#include +#include +#include +#include + +#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; }; From patchwork Thu Oct 10 12:33:30 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 145600 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 8CB2645B04; Thu, 10 Oct 2024 14:33:53 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 7F69940663; Thu, 10 Oct 2024 14:33:40 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.14]) by mails.dpdk.org (Postfix) with ESMTP id 1F3EB402D8 for ; Thu, 10 Oct 2024 14:33:36 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1728563618; x=1760099618; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=QTgQh3FKL7PbQnY32ydUhbRCB/FP8eXTYKRuUucG/TI=; b=FyTmljST8J4wQgKrpED+Mt58837O8zg9s4dG2Awm8/uhXZzVR99ssr9b Z6Eztz7mv1X8C6pXww0ay8F53IEsVqF3LGnDEz1Jl0z9m7h2pgIBCi7ve 040f74nZR70fzDUBvl3+5uZEClvgbGZGWqafdEqcHMDZmS5lfajwZ3pzQ nuoD3E1zdpah7HriJ+TXI41Rgu7VgKmcXppP5AS6Jq0Ur1Xml+upmF2OV L3Ur5KmYMwV4cKN484xkil209ku5a2UEViltuilTlLlNLLJ7hnq9t9uPT Wzi3Bm6/77+wxQSxUqo+mdFqa3t4OzxrFIH+jiPUhYw36xPoU0mr1FMM8 A==; X-CSE-ConnectionGUID: d+WzlvxqSeyKVV/PnFIzVQ== X-CSE-MsgGUID: iZQ2kfv0QoeV29Y0794VJg== X-IronPort-AV: E=McAfee;i="6700,10204,11220"; a="31712327" X-IronPort-AV: E=Sophos;i="6.11,193,1725346800"; d="scan'208";a="31712327" Received: from fmviesa005.fm.intel.com ([10.60.135.145]) by orvoesa106.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 10 Oct 2024 05:33:37 -0700 X-CSE-ConnectionGUID: 2JPHn8U/TWS23aS0ZlpIhA== X-CSE-MsgGUID: 4ozPNjOdQtC2dR5C6FXCeg== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,193,1725346800"; d="scan'208";a="81101892" Received: from unknown (HELO silpixa00401176.ir.intel.com) ([10.243.22.170]) by fmviesa005.fm.intel.com with ESMTP; 10 Oct 2024 05:33:35 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: stephen@networkplumber.org, Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [PATCH v2 3/4] hash: implement RSS hash key generation API Date: Thu, 10 Oct 2024 12:33:30 +0000 Message-Id: <20241010123331.749004-4-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241010123331.749004-1-vladimir.medvedkin@intel.com> References: <20241010123331.749004-1-vladimir.medvedkin@intel.com> MIME-Version: 1.0 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 This patch implements Toeplitz hash key generation function using the new polynomial generation function. Signed-off-by: Vladimir Medvedkin --- 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; } From patchwork Thu Oct 10 12:33:31 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 145601 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id CAAC745B04; Thu, 10 Oct 2024 14:33:59 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id DC90940664; Thu, 10 Oct 2024 14:33:41 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.14]) by mails.dpdk.org (Postfix) with ESMTP id 8B4D34065D for ; Thu, 10 Oct 2024 14:33:38 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1728563619; x=1760099619; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=tZLW4V2a8+qVfnPLzyNzWojs5kqS0+U1BFz3oLDsfB8=; b=CtQXbjiZbrfHxFi9+5w+L1XFjQCnPGPzVSt0+lcejQp7r06/kSdGlbsI qGInKINqiJ5Ri4uAAoAq3mlsaOrnx8sEwwPBNOG890zgZUD7/Lzwv4V+a 5ro46sX7MZaInRxN2YGcjkg1rWB0a96GhUfSdrMfKxiyStA5F5oSaAFkx n9+N//xdAMV8vlpGTT2lPFrLpZrnpker+N0/kQM6d9KNZME5DYIbef0og EZdkjrLFhXznFTTrN96Us3NTgIoACW3cCstn4ukYyR1VCyCwBYR4r7L71 OzdOyiXSn4ykY3haV5YQfBKBMH5VpXPCEwJmrmrnZtPingZ7djo7VFXug Q==; X-CSE-ConnectionGUID: Y7eokhenQn6KttgGnLLJ3A== X-CSE-MsgGUID: fKOWqyevRTyO7VYyIn4XfA== X-IronPort-AV: E=McAfee;i="6700,10204,11220"; a="31712337" X-IronPort-AV: E=Sophos;i="6.11,193,1725346800"; d="scan'208";a="31712337" Received: from fmviesa005.fm.intel.com ([10.60.135.145]) by orvoesa106.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 10 Oct 2024 05:33:38 -0700 X-CSE-ConnectionGUID: 0EqjRZnbSiSMzn6ejZ2LKA== X-CSE-MsgGUID: cbHApQ0ERYKj/W/lXsoa7w== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,193,1725346800"; d="scan'208";a="81101898" Received: from unknown (HELO silpixa00401176.ir.intel.com) ([10.243.22.170]) by fmviesa005.fm.intel.com with ESMTP; 10 Oct 2024 05:33:37 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: stephen@networkplumber.org, Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [PATCH v2 4/4] test/thash: add tests for RSS key generation API Date: Thu, 10 Oct 2024 12:33:31 +0000 Message-Id: <20241010123331.749004-5-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241010123331.749004-1-vladimir.medvedkin@intel.com> References: <20241010123331.749004-1-vladimir.medvedkin@intel.com> MIME-Version: 1.0 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 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 --- 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 #include #include +#include #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() } };