From patchwork Fri Sep 6 16:53:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 143753 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 9F7E145920; Fri, 6 Sep 2024 18:53:27 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id B099542FD3; Fri, 6 Sep 2024 18:53:23 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.13]) by mails.dpdk.org (Postfix) with ESMTP id 7290142E82 for ; Fri, 6 Sep 2024 18:53:21 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1725641602; x=1757177602; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=shgQm+QcPCbC2pORmOXWwSqel1NKaK7Uf0+78G7aFTs=; b=ZAGW/u0CF0Y835kYUB8m6pxbnlEGcTN5yy5ogInYT+iyhphjNnJ4Tn8z hQQJa00Vxk52IU1FIa1FBV+QaAsGxFwzzV+WkLHB6Jj97wIJ0sy70qagJ g2bANh2ik3wB3Flo87mUnW7s2KK1KkBBFd0oeg6RiBgWPQoEgK2M/EXIy BxWqMSPyqishL/6qIBaKSyTWj4wzboa6mNtw2LC21JtAWt/8+wFHKdjGn 5iziV2ThJkV7tg7axD+uBBo9fD9zwqUC1Vc6bWkiW/pBZATazLk3g3tIC fZWQHAvknjKasWGb1utRqyNRdVjxfbJ/MiBN4yQtfWUWUTzMUBp+uJ/Zf Q==; X-CSE-ConnectionGUID: ydXU9eaKRZyTz3wwNEIxNQ== X-CSE-MsgGUID: Q5uIRET6TE6OvEPRkRM26g== X-IronPort-AV: E=McAfee;i="6700,10204,11187"; a="27334100" X-IronPort-AV: E=Sophos;i="6.10,208,1719903600"; d="scan'208";a="27334100" Received: from fmviesa009.fm.intel.com ([10.60.135.149]) by fmvoesa107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Sep 2024 09:53:21 -0700 X-CSE-ConnectionGUID: GxR+NXjtSsOMvBRQxtYbTg== X-CSE-MsgGUID: 9A5TVWOnTuOL/RYsjR/D1w== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.10,208,1719903600"; d="scan'208";a="65996772" Received: from silpixa00401176.ir.intel.com ([10.243.22.170]) by fmviesa009.fm.intel.com with ESMTP; 06 Sep 2024 09:53:20 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [RFC 1/4] thash: add RSS hash key generation API Date: Fri, 6 Sep 2024 16:53:15 +0000 Message-Id: <20240906165318.1322550-2-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240906165318.1322550-1-vladimir.medvedkin@intel.com> References: <20240906165318.1322550-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 | 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 From patchwork Fri Sep 6 16:53:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 143754 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 C85B645920; Fri, 6 Sep 2024 18:53:35 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 710F442FED; Fri, 6 Sep 2024 18:53:25 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.13]) by mails.dpdk.org (Postfix) with ESMTP id DEF4742FB1 for ; Fri, 6 Sep 2024 18:53:22 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1725641603; x=1757177603; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=tqhB56/gaAl/LXhVhR4Y5X4YCHl5YGkl7v4wKXeqz78=; b=VPmJMNb0NOwyXNljumYyPF7wOxYish9YWNeiYixUDZXfaYcMGD87yaJ3 v5kfeVnt3XJRshUlemGuoW+KJwPEDSNmIehiEs5aHdyur+C/eUrKeMMxu DaRO11JLUJLQCrR5uvm+/U4yNwJWj1W35vRbttuax4XklqfMrYgf7QkXP 7nN6XTEQ9b4c57te01k9HccDMaY2LrR/uJL3ktnOcOgO60tyR3kiiP6Q3 BplJc2O/VeR7yt7uPkN7xOuWeM7bvd45cbnl7VSni85WoaIIQ5hs6nk4H uY3D7HypDzpxaAgP1lNrGoXJnp2n1FRDb4QCSjLG5FK/qRfKhmywbCrac Q==; X-CSE-ConnectionGUID: tf4c1G3tR2OLVxCwFenGyQ== X-CSE-MsgGUID: dQV06XtgQcCo9MYWrZjwrA== X-IronPort-AV: E=McAfee;i="6700,10204,11187"; a="27334103" X-IronPort-AV: E=Sophos;i="6.10,208,1719903600"; d="scan'208";a="27334103" Received: from fmviesa009.fm.intel.com ([10.60.135.149]) by fmvoesa107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Sep 2024 09:53:23 -0700 X-CSE-ConnectionGUID: dcLuI3t1So6lzL8YZkxIXw== X-CSE-MsgGUID: MML+4ClfQk+U180OwpsRew== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.10,208,1719903600"; d="scan'208";a="65996780" Received: from silpixa00401176.ir.intel.com ([10.243.22.170]) by fmviesa009.fm.intel.com with ESMTP; 06 Sep 2024 09:53:22 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [RFC 2/4] hash: add dynamic polynomial calculation Date: Fri, 6 Sep 2024 16:53:16 +0000 Message-Id: <20240906165318.1322550-3-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240906165318.1322550-1-vladimir.medvedkin@intel.com> References: <20240906165318.1322550-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..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 +#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 { + 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 From patchwork Fri Sep 6 16:53:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 143755 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 0559F45920; Fri, 6 Sep 2024 18:53:49 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 0CC2842FF7; Fri, 6 Sep 2024 18:53:28 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.13]) by mails.dpdk.org (Postfix) with ESMTP id 3005842FCB for ; Fri, 6 Sep 2024 18:53:24 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1725641605; x=1757177605; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=QTgQh3FKL7PbQnY32ydUhbRCB/FP8eXTYKRuUucG/TI=; b=f4qTICG2XzBHpypoqKBith5rCb9RBh27hBXgF+w8JDWagpS/3hML42EB +uefb8+TqWo+xXHEcGTPmRXceUsCuu3nqiujJtycjzOpfYDl5RSlXyfFg MCi7/Poq9ezLPxx4HIi8VS0dhIW8kzDtK1JwOQrzmKIL789lhubrzKtmK XYAq2UL7GHW7zG11rlG7H2ikcrw+qReW2eqlJej1Z7rizt+PWpH4oOxLf bmxFIctzrhXgeCtwM8UHuOXqZngxKIC6q4EnDPYGtadXMX1+If3UGTV99 rnjM7FxFqOJdulLdyfekfdDuLgg/qXMs60382VySWwttej2j7i2FCJAbf Q==; X-CSE-ConnectionGUID: 6ARL7ezzQM2/2tyFAneRjA== X-CSE-MsgGUID: NTuLQgW0QamWA1+xnh0a7Q== X-IronPort-AV: E=McAfee;i="6700,10204,11187"; a="27334107" X-IronPort-AV: E=Sophos;i="6.10,208,1719903600"; d="scan'208";a="27334107" Received: from fmviesa009.fm.intel.com ([10.60.135.149]) by fmvoesa107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Sep 2024 09:53:24 -0700 X-CSE-ConnectionGUID: hKwKsSDuTS+3nBU8JTgKEA== X-CSE-MsgGUID: PuqO5K9RQm6LU/8qM2sZSQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.10,208,1719903600"; d="scan'208";a="65996786" Received: from silpixa00401176.ir.intel.com ([10.243.22.170]) by fmviesa009.fm.intel.com with ESMTP; 06 Sep 2024 09:53:23 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [RFC 3/4] hash: implement RSS hash key generation API Date: Fri, 6 Sep 2024 16:53:17 +0000 Message-Id: <20240906165318.1322550-4-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240906165318.1322550-1-vladimir.medvedkin@intel.com> References: <20240906165318.1322550-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 Fri Sep 6 16:53:18 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 143756 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 06DAF45920; Fri, 6 Sep 2024 18:53:56 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 4C2D643001; Fri, 6 Sep 2024 18:53:29 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.13]) by mails.dpdk.org (Postfix) with ESMTP id 69F8942FEB for ; Fri, 6 Sep 2024 18:53:25 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1725641606; x=1757177606; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=tZLW4V2a8+qVfnPLzyNzWojs5kqS0+U1BFz3oLDsfB8=; b=BHDXEzQX8pXsjDh70htvjhTQft0w+wvqnCtSqxqJnvXOSgY41lztx1/e b9UzucesycZL2LPFSljp/VZpkFTXIuwvdwVO7cAP5Sr1XxYc1ly4L7EDE 4gYMtXl22AmNVC6TuOE4xyudkBujf6QCyltmrw90wztaTvzXUt9n//J/8 hNJqt4F3x+GCt1+64kjrhyFbUywFSnEegPCiTUjN31sgqQs4tKCTVvJLK H5mw5CWwngU7JjgJu8NG46fjXy9Usyv8slo18WZ+I2zIagRN6w20d4d94 cdRZGQKn5Zu22LarJOHM/ZWJsZbFzsdYCWUK+jYXSgDvYz1K30cLG7/RD A==; X-CSE-ConnectionGUID: 4Pz2cMb+TA6C1RsisIjMWA== X-CSE-MsgGUID: PtpPWB7eTAOhgp6sNas+UQ== X-IronPort-AV: E=McAfee;i="6700,10204,11187"; a="27334110" X-IronPort-AV: E=Sophos;i="6.10,208,1719903600"; d="scan'208";a="27334110" Received: from fmviesa009.fm.intel.com ([10.60.135.149]) by fmvoesa107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Sep 2024 09:53:25 -0700 X-CSE-ConnectionGUID: 7nEb3wLeRoC2zqRyO/Lymw== X-CSE-MsgGUID: nvO3XIhHTqSnySX2vv3z6g== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.10,208,1719903600"; d="scan'208";a="65996790" Received: from silpixa00401176.ir.intel.com ([10.243.22.170]) by fmviesa009.fm.intel.com with ESMTP; 06 Sep 2024 09:53:24 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: Yipeng Wang , Sameh Gobriel , Bruce Richardson Subject: [RFC 4/4] test/thash: add tests for RSS key generation API Date: Fri, 6 Sep 2024 16:53:18 +0000 Message-Id: <20240906165318.1322550-5-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240906165318.1322550-1-vladimir.medvedkin@intel.com> References: <20240906165318.1322550-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() } };