From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <dev-bounces@dpdk.org>
Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124])
by inbox.dpdk.org (Postfix) with ESMTP id EDD5FA0547;
Sat, 10 Apr 2021 02:11:05 +0200 (CEST)
Received: from [217.70.189.124] (localhost [127.0.0.1])
by mails.dpdk.org (Postfix) with ESMTP id 76BFF1410A9;
Sat, 10 Apr 2021 02:11:05 +0200 (CEST)
Received: from mga03.intel.com (mga03.intel.com [134.134.136.65])
by mails.dpdk.org (Postfix) with ESMTP id 3ABF640688
for <dev@dpdk.org>; Sat, 10 Apr 2021 02:11:03 +0200 (CEST)
IronPort-SDR: esVACYogP4JOXyeg5EkxHWS3gHBS+z7Ka68FIjHCCFomnnrXo5C+V6DCsa59fm+JlGv3nhTl0n
mvdEL6ZGsPrA==
X-IronPort-AV: E=McAfee;i="6000,8403,9949"; a="193901650"
X-IronPort-AV: E=Sophos;i="5.82,210,1613462400"; d="scan'208";a="193901650"
Received: from fmsmga007.fm.intel.com ([10.253.24.52])
by orsmga103.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384;
09 Apr 2021 17:11:02 -0700
IronPort-SDR: JdDmDWuCmmv8jJxNsx2vKFk19AFTeMd1GxPYicHqTRfbrB4QjDi45vnT+w3TxmK83Br8PsC4Li
eWW4BUUyF2aQ==
X-ExtLoop1: 1
X-IronPort-AV: E=Sophos;i="5.82,210,1613462400"; d="scan'208";a="387947194"
Received: from orsmsx605.amr.corp.intel.com ([10.22.229.18])
by fmsmga007.fm.intel.com with ESMTP; 09 Apr 2021 17:11:02 -0700
Received: from orsmsx612.amr.corp.intel.com (10.22.229.25) by
ORSMSX605.amr.corp.intel.com (10.22.229.18) with Microsoft SMTP Server
(version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id
15.1.2106.2; Fri, 9 Apr 2021 17:11:01 -0700
Received: from orsmsx612.amr.corp.intel.com (10.22.229.25) by
ORSMSX612.amr.corp.intel.com (10.22.229.25) with Microsoft SMTP Server
(version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id
15.1.2106.2; Fri, 9 Apr 2021 17:11:01 -0700
Received: from ORSEDG602.ED.cps.intel.com (10.7.248.7) by
orsmsx612.amr.corp.intel.com (10.22.229.25) with Microsoft SMTP Server
(version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2106.2
via Frontend Transport; Fri, 9 Apr 2021 17:11:01 -0700
Received: from NAM02-BL2-obe.outbound.protection.outlook.com (104.47.38.51) by
edgegateway.intel.com (134.134.137.103) with Microsoft SMTP Server
(version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id
15.1.2106.2; Fri, 9 Apr 2021 17:11:01 -0700
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none;
b=b8NLrJWcfYTnO7seAPokOJqyxtxP8yJtvazEhPoKWlhcYFGYV8X+ufIQ7XtaUHTmzdcZQ28Y/26XmDEfUnYgNxo6fXopquQHtPJqhqgozX7tEDOCBBi+EcQdkkt9xwlhLVgefIi3bsAB1fXOxs5CeqcfP7hFpRkfdCxmB52Be/HRW6Mp5iA0grhpAjEmSdxR4ZJsZTn0AuBjpIwfv1SzSUuQLa061+hhVcrGXCkJnhtnE+bZy5R6ZXQa6nALjPfeX1gp+q5Rt1MSQx7vWC9KMjs8tZDNEpojO/8C+r1XjcBAWANmfOt9cGdYKFeXwC7eNYxXNvxVh+Y+2fbJZE3+Jw==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com;
s=arcselector9901;
h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck;
bh=UVFmirwS7QBfcX807Y8xbHZLTbTCo/9t5gnYUjwVLFk=;
b=Wmbu34xkq7q/FjGRwk6Juw1kJnjOiPBy7G8NB66EJAJUzHgOPRNboGceExZn4Nr+RqctqkfzNtJIOiy7O/PP8WJhQLoEv6SzZ4lZ9b1WwubWxNuwLNBoqBagH+FL+tpfe26dwyg3iwXEqo4eegdZsG7b7dTSWUsy1pT86nKtS5FtxW2Ts83pPQ8wqh7Ho46YkJuf0q9e5uheOvq5l7bPwyVJW5jAcOfMUF+5YSF6AcymLBF4wfrDqo6XLrxbDTlRmHzPQ+EC947wRqGcDiozCNaDugHEFheN7p0mq+YT+xHfqRCjLLl9NBstcp6qK6PUin1xYM9luL33y6GY2JSm1g==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass
smtp.mailfrom=intel.com; dmarc=pass action=none header.from=intel.com;
dkim=pass header.d=intel.com; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=intel.onmicrosoft.com;
s=selector2-intel-onmicrosoft-com;
h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck;
bh=UVFmirwS7QBfcX807Y8xbHZLTbTCo/9t5gnYUjwVLFk=;
b=rzGJEMxLyGWaxBHjqIIfsMmk4RF9kwHI+DChMxM81RKMAPibArxGJs/GkO3FU8my0hvPwJahV4Ej5S+FhfxgNCOB2n8UCB5wsl7TR+eWigRpC1HYIOxKcEARkJ7bKfcO1qP4ljUIkX/erwggR88Ls4BJHlsTaF/Gz59qKXF2yiI=
Received: from BYAPR11MB3494.namprd11.prod.outlook.com (2603:10b6:a03:86::15)
by BYAPR11MB3381.namprd11.prod.outlook.com (2603:10b6:a03:79::33)
with Microsoft SMTP Server (version=TLS1_2,
cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3999.28; Sat, 10 Apr
2021 00:10:49 +0000
Received: from BYAPR11MB3494.namprd11.prod.outlook.com
([fe80::8446:4da6:a155:5b3e]) by BYAPR11MB3494.namprd11.prod.outlook.com
([fe80::8446:4da6:a155:5b3e%7]) with mapi id 15.20.3999.032; Sat, 10 Apr 2021
00:10:49 +0000
From: "Wang, Yipeng1" <yipeng1.wang@intel.com>
To: "Medvedkin, Vladimir" <vladimir.medvedkin@intel.com>, "dev@dpdk.org"
<dev@dpdk.org>
CC: "Ananyev, Konstantin" <konstantin.ananyev@intel.com>, "Chilikin, Andrey"
<andrey.chilikin@intel.com>, "Kinsella, Ray" <ray.kinsella@intel.com>,
"Gobriel, Sameh" <sameh.gobriel@intel.com>, "Richardson, Bruce"
<bruce.richardson@intel.com>, Stephen Hemminger <stephen@networkplumber.org>
Thread-Topic: [PATCH v2 2/3] hash: add predictable RSS implementation
Thread-Index: AQHXKx4zqI6NHnrQDkmyvvFzO5OOa6qs5C6g
Date: Sat, 10 Apr 2021 00:10:49 +0000
Message-ID: <BYAPR11MB34941D81BA16F7EB7E3C3946C3729@BYAPR11MB3494.namprd11.prod.outlook.com>
References: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com>
<1617738643-258635-3-git-send-email-vladimir.medvedkin@intel.com>
In-Reply-To: <1617738643-258635-3-git-send-email-vladimir.medvedkin@intel.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
dlp-reaction: no-action
dlp-version: 11.5.1.3
dlp-product: dlpe-windows
authentication-results: intel.com; dkim=none (message not signed)
header.d=none;intel.com; dmarc=none action=none header.from=intel.com;
x-originating-ip: [108.161.24.24]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: a910f963-027b-4450-f8ee-08d8fbb5189d
x-ms-traffictypediagnostic: BYAPR11MB3381:
x-ld-processed: 46c98d88-e344-4ed4-8496-4ed7712e255d,ExtAddr
x-ms-exchange-transport-forked: True
x-microsoft-antispam-prvs: <BYAPR11MB33812771791E06F59EBD58DEC3729@BYAPR11MB3381.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:146;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: tTWvvCeoNS7xiMKgPJzHmwUMpY99ddO7pQO4W48HT8fs0CUWM1SQIrzFmn66gdpbaNg09DzXoefl4kBz4O8mdlrCHnhFjs32cqpYVXMaSN0L6nBnWqoI0q5h7LG0hM2PZgiK3VErtqUl+x23pqqF/NQeEryS8q+alh8D1aBTzbzBZcHavX3lV9HrznV3qlpLZFP3OIyzAfl/IjBj1PGk56vk0GltX56K7yITTWp8i+VUK8rKBsGjvbwZdViRDTGlrwZQROsdElktVS/Qv2tGzkQV/Tc51q3hl+xWrr8kKKtwICHadR/pvSA50Mrb0Q25dNmMzMNbdjnwHVPsZieHmj0rOiHrIowZTpIFvZpD0uMJWLwJOCT6FG/qKN93g8C3IqBrCD2ibUdkgpt847hl5h0vL8ODLXpdK/r/2Nkd8xRQQ8K+976Zct6N1/KH+Xll/rjJ5XafITK03x25+tyE3OiYuQMXUUiW+xapbsRpsR649bilN7nDnq5To8OJf2S+uw8Kn2VQH0u3EhB4RyJiMVvUXX32/sX7ahq7LYB9NSogRt1//JMdMv1cbNbefrh1jbF/x8LZWolXKttN3pikmACcb6xBrvxhHv1IVjMcyh8WSb4krsrjomfLSEZtYLzLL81rnz3Nq74WM8an3kpPSphWkocR0Fb0+JRrK0o/nA4=
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:;
IPV:NLI; SFV:NSPM; H:BYAPR11MB3494.namprd11.prod.outlook.com; PTR:; CAT:NONE;
SFS:(376002)(39860400002)(366004)(396003)(346002)(136003)(26005)(2906002)(8936002)(478600001)(66476007)(186003)(38100700001)(4326008)(5660300002)(71200400001)(83380400001)(33656002)(64756008)(66556008)(110136005)(54906003)(9686003)(8676002)(30864003)(66946007)(55016002)(66446008)(76116006)(7696005)(316002)(52536014)(86362001)(6506007)(53546011)(579004);
DIR:OUT; SFP:1102;
x-ms-exchange-antispam-messagedata: =?us-ascii?Q?ms9nEt4oUfC9eVbd2Gf+T8xguTh1ym8aEW/9I592j50O6JorK+WvpArW3hR0?=
=?us-ascii?Q?W3t6v0SqkT8j3Q0n/1OS8fLe4Fq2Rza1mtKbrNW39nQOWwJS2wlAypw5xKFG?=
=?us-ascii?Q?aufmGSusSq9CR2wKJevEU2QLLHToPKo2kiBULt6p+K1Hym4iclO5eK3iaASh?=
=?us-ascii?Q?EMya0kdEXXz9zO+CTw28Z1GlJHL6SO6kjZZ6+TY6n/9THulqbhMrc2aXF3c0?=
=?us-ascii?Q?X22YnR0a4s4bEoggZsvVrFgEo0VAEvI1ALl1yGt4EkUKNqJuzoXDAmJppMid?=
=?us-ascii?Q?h/HRhPagDqv5PBcpdTzgJRkpAxfsTmgWXgG32bLDzlZHT1J7ZRpQGfUI8V89?=
=?us-ascii?Q?mq+G35nnNktHF1O40G6K06scLRmlkLjP5Js4DwAqDZ0oxiA2qX88CjtAcSFQ?=
=?us-ascii?Q?JGNOAOP+V3/FRzyiWqwDd3XQpbNxcHqgaW6sOU6bxsz7dYt9cx1zq8NLjX3i?=
=?us-ascii?Q?sNeBvaLtIKJ4DRf6q+56ckC7emIasTTFyBLa/cLWMb977m/giZN49MyugTMd?=
=?us-ascii?Q?Q6qFxSdH1USrF8W036ugadhvQKL8HlJDzS/sW9w8JSj6oFJgkTDlcpCkeQS7?=
=?us-ascii?Q?bltL3tH4hrJ3P/iQ9Ll2ffq5pvbqUhrGLFwETc4KsR1rDL9GoJDnL4GpzB6Z?=
=?us-ascii?Q?xNWUPEZ9ITSD8qDf2vHi7ZWF9d6rz1TpOnqJITkJ/f8KsgQspzIT4HmCTV/g?=
=?us-ascii?Q?htwhkdnrTF6RTEB3p80BRSBt9QqRtIooCTgG/s53Ymc5FyNdMzUClmONwh5y?=
=?us-ascii?Q?I/rNUPQexau/GKg4W9xLjvK0Ml+uJQa8tFmPbZoXFEjHomR2Jk8YccfwY/6D?=
=?us-ascii?Q?EoaD0CCcwO/4CeaFDrlqUvY3so41g4PqcFT+i4m5M5NPstMnIzcb1zqN17FM?=
=?us-ascii?Q?fJY502/PKT/4zPr97LaZ3emBYVAVyUQK2oVPbLy4GYK6x5KxZ0xoQ/1+8x0V?=
=?us-ascii?Q?L7d2CzkP9CmAytRtE5otynjDF0CEzZI/jVWEE3tXAnr9M+E4hnVpzLHo4QTS?=
=?us-ascii?Q?+IoRrXFfqUyrAbOf3kH/YHFB/9gFgenhKtso7wyjWBl+UiRTpI27k4XpCtxY?=
=?us-ascii?Q?DTkqwA0D+kzk332c3OCezJ47AcdXnEkyA+TJkdhKBGtvx0/paYOTTW4padLB?=
=?us-ascii?Q?veJ4Mk66JAkdYk2wipirQ3eInDHWh6qrkMn3Hosm2VPtu5Eer8/f6EM978WM?=
=?us-ascii?Q?SVE9se2ca9zrrN6QUObzkNuY9WyxR0sP0lidPYKhlyGsf0JZLyq7EyUDDm12?=
=?us-ascii?Q?LbJtLRAEeU7ULdEZiabK5igorLt9W41rV4mlolES32eR441nMGIXV0M9TFOZ?=
=?us-ascii?Q?6LazOqvy9EhHaAByIs8Utx7r?=
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: BYAPR11MB3494.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: a910f963-027b-4450-f8ee-08d8fbb5189d
X-MS-Exchange-CrossTenant-originalarrivaltime: 10 Apr 2021 00:10:49.2264 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: qIL55neHisJbXdLsfkxp9v//5oDmHJ12fA64xpG119rgYnWcuJNDZKX1icfA8S0zz9007wloOVUij6AOjvACrg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BYAPR11MB3381
X-OriginatorOrg: intel.com
Subject: Re: [dpdk-dev] [PATCH v2 2/3] hash: add predictable RSS
implementation
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>
> -----Original Message-----
> From: Medvedkin, Vladimir <vladimir.medvedkin@intel.com>
> Sent: Tuesday, April 6, 2021 12:51 PM
> To: dev@dpdk.org
> Cc: Ananyev, Konstantin <konstantin.ananyev@intel.com>; Chilikin, Andrey
> <andrey.chilikin@intel.com>; Kinsella, Ray <ray.kinsella@intel.com>; Wang=
,
> Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh
> <sameh.gobriel@intel.com>; Richardson, Bruce
> <bruce.richardson@intel.com>
> Subject: [PATCH v2 2/3] hash: add predictable RSS implementation
>=20
> This patch implements predictable RSS functionality.
>=20
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
> ---
> lib/librte_hash/rte_thash.c | 577
> ++++++++++++++++++++++++++++++++++++++++++--
> lib/librte_hash/rte_thash.h | 42 ++++
> lib/librte_hash/version.map | 1 +
> 3 files changed, 602 insertions(+), 18 deletions(-)
>=20
> diff --git a/lib/librte_hash/rte_thash.c b/lib/librte_hash/rte_thash.c in=
dex
> 79e8724..cc60ada 100644
> --- a/lib/librte_hash/rte_thash.c
> +++ b/lib/librte_hash/rte_thash.c
> @@ -12,6 +12,45 @@
> #include <rte_malloc.h>
>=20
> #define THASH_NAME_LEN 64
> +#define TOEPLITZ_HASH_LEN 32
> +
> +#define RETA_SZ_MIN 2U
> +#define RETA_SZ_MAX 16U
> +#define RETA_SZ_IN_RANGE(reta_sz) ((reta_sz >=3D RETA_SZ_MIN)
> && \
> + (reta_sz <=3D RETA_SZ_MAX))
> +
> +TAILQ_HEAD(rte_thash_list, rte_tailq_entry); static struct
> +rte_tailq_elem rte_thash_tailq =3D {
> + .name =3D "RTE_THASH",
> +};
> +EAL_REGISTER_TAILQ(rte_thash_tailq)
> +
> +/**
> + * Table of some irreducible polinomials over GF(2).
> + * For lfsr they are reperesented in BE bit order, and
> + * x^0 is masked out.
> + * For example, poly x^5 + x^2 + 1 will be represented
> + * as (101001b & 11111b) =3D 01001b =3D 0x9 */ static const uint32_t
> +irreducible_poly_table[][4] =3D {
> + {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},
> +};
>=20
> struct thash_lfsr {
> uint32_t ref_cnt;
> @@ -31,8 +70,10 @@ struct rte_thash_subtuple_helper {
> char name[THASH_NAME_LEN]; /** < Name of subtuple
> configuration */
> LIST_ENTRY(rte_thash_subtuple_helper) next;
> struct thash_lfsr *lfsr;
> - uint32_t offset; /** < Offset in bits of the subtuple */
> - uint32_t len; /** < Length in bits of the subtuple
> */
> + uint32_t offset; /** < Offset of the m-sequence */
> + uint32_t len; /** < Length of the m-sequence */
> + uint32_t tuple_offset; /** < Offset in bits of the subtuple */
> + uint32_t tuple_len; /** < Length in bits of the subtuple
> */
> uint32_t lsb_msk; /** < (1 << reta_sz_log) - 1 */
> __extension__ uint32_t compl_table[0] __rte_cache_aligned;
> /** < Complimentary table */
> @@ -48,49 +89,549 @@ struct rte_thash_ctx {
> uint8_t hash_key[0];
> };
>=20
> +static inline uint32_t
> +get_bit_lfsr(struct thash_lfsr *lfsr)
> +{
> + uint32_t bit, ret;
> +
> + /*
> + * masking the TAP bits defined by the polynomial and
> + * calculating parity
> + */
> + bit =3D __builtin_popcount(lfsr->state & lfsr->poly) & 0x1;
> + ret =3D lfsr->state & 0x1;
> + lfsr->state =3D ((lfsr->state >> 1) | (bit << (lfsr->deg - 1))) &
> + ((1 << lfsr->deg) - 1);
> +
> + lfsr->bits_cnt++;
> + return ret;
> +}
> +
> +static inline uint32_t
> +get_rev_bit_lfsr(struct thash_lfsr *lfsr) {
> + uint32_t bit, ret;
> +
> + bit =3D __builtin_popcount(lfsr->rev_state & lfsr->rev_poly) & 0x1;
> + ret =3D lfsr->rev_state & (1 << (lfsr->deg - 1));
> + lfsr->rev_state =3D ((lfsr->rev_state << 1) | bit) &
> + ((1 << lfsr->deg) - 1);
> +
> + lfsr->bits_cnt++;
> + 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)
> +{
> + struct thash_lfsr *lfsr;
> + uint32_t i;
> +
> + if (ctx =3D=3D NULL)
> + return NULL;
> +
> + lfsr =3D rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
> + if (lfsr =3D=3D NULL)
> + return NULL;
> +
> + lfsr->deg =3D ctx->reta_sz_log;
> + lfsr->poly =3D thash_get_rand_poly(lfsr->deg);
> + do {
> + lfsr->state =3D rte_rand() & ((1 << lfsr->deg) - 1);
> + } while (lfsr->state =3D=3D 0);
> + /* init reverse order polynomial */
> + lfsr->rev_poly =3D (lfsr->poly >> 1) | (1 << (lfsr->deg - 1));
> + /* init proper rev_state*/
> + lfsr->rev_state =3D lfsr->state;
> + for (i =3D 0; i <=3D lfsr->deg; i++)
> + get_rev_bit_lfsr(lfsr);
> +
> + /* clear bits_cnt after rev_state was inited */
> + lfsr->bits_cnt =3D 0;
> + lfsr->ref_cnt =3D 1;
> +
> + return lfsr;
> +}
> +
> +static void
> +attach_lfsr(struct rte_thash_subtuple_helper *h, struct thash_lfsr
> +*lfsr) {
> + lfsr->ref_cnt++;
> + h->lfsr =3D lfsr;
> +}
> +
> +static void
> +free_lfsr(struct thash_lfsr *lfsr)
> +{
> + lfsr->ref_cnt--;
> + if (lfsr->ref_cnt =3D=3D 0)
> + rte_free(lfsr);
> +}
> +
> struct rte_thash_ctx *
> -rte_thash_init_ctx(const char *name __rte_unused,
> - uint32_t key_len __rte_unused, uint32_t reta_sz __rte_unused,
> - uint8_t *key __rte_unused, uint32_t flags __rte_unused)
> +rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz,
> + uint8_t *key, uint32_t flags)
> {
> + struct rte_thash_ctx *ctx;
> + struct rte_tailq_entry *te;
> + struct rte_thash_list *thash_list;
> + uint32_t i;
> + if ((name =3D=3D NULL) || (key_len =3D=3D 0)
> || !RETA_SZ_IN_RANGE(reta_sz)) {
> + rte_errno =3D EINVAL;
> + return NULL;
> + }
> +
> + thash_list =3D RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> +
> + rte_mcfg_tailq_write_lock();
> +
> + /* guarantee there's no existing */
> + TAILQ_FOREACH(te, thash_list, next) {
> + ctx =3D (struct rte_thash_ctx *)te->data;
> + if (strncmp(name, ctx->name, sizeof(ctx->name)) =3D=3D 0)
> + break;
> + }
> + ctx =3D NULL;
> + if (te !=3D NULL) {
> + rte_errno =3D EEXIST;
> + goto exit;
> + }
> +
> + /* allocate tailq entry */
> + te =3D rte_zmalloc("THASH_TAILQ_ENTRY", sizeof(*te), 0);
> + if (te =3D=3D NULL) {
> + RTE_LOG(ERR, HASH,
> + "Can not allocate tailq entry for thash context %s\n",
> + name);
> + rte_errno =3D ENOMEM;
> + goto exit;
> + }
> +
> + ctx =3D rte_zmalloc(NULL, sizeof(struct rte_thash_ctx) + key_len, 0);
> + if (ctx =3D=3D NULL) {
> + RTE_LOG(ERR, HASH, "thash ctx %s memory allocation
> failed\n",
> + name);
> + rte_errno =3D ENOMEM;
> + goto free_te;
> + }
> +
> + rte_strlcpy(ctx->name, name, sizeof(ctx->name));
> + ctx->key_len =3D key_len;
> + ctx->reta_sz_log =3D reta_sz;
> + LIST_INIT(&ctx->head);
> + ctx->flags =3D flags;
> +
> + if (key)
> + rte_memcpy(ctx->hash_key, key, key_len);
> + else {
> + for (i =3D 0; i < key_len; i++)
> + ctx->hash_key[i] =3D rte_rand();
> + }
> +
> + te->data =3D (void *)ctx;
> + TAILQ_INSERT_TAIL(thash_list, te, next);
> +
> + rte_mcfg_tailq_write_unlock();
> +
> + return ctx;
> +free_te:
> + rte_free(te);
> +exit:
> + rte_mcfg_tailq_write_unlock();
> return NULL;
> }
>=20
> struct rte_thash_ctx *
> -rte_thash_find_existing(const char *name __rte_unused)
> +rte_thash_find_existing(const char *name)
> {
> - return NULL;
> + struct rte_thash_ctx *ctx;
> + struct rte_tailq_entry *te;
> + struct rte_thash_list *thash_list;
> +
> + thash_list =3D RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> +
> + rte_mcfg_tailq_read_lock();
> + TAILQ_FOREACH(te, thash_list, next) {
> + ctx =3D (struct rte_thash_ctx *)te->data;
> + if (strncmp(name, ctx->name, sizeof(ctx->name)) =3D=3D 0)
> + break;
> + }
> +
> + rte_mcfg_tailq_read_unlock();
> +
> + if (te =3D=3D NULL) {
> + rte_errno =3D ENOENT;
> + return NULL;
> + }
> +
> + return ctx;
> }
>=20
> void
> -rte_thash_free_ctx(struct rte_thash_ctx *ctx __rte_unused)
> +rte_thash_free_ctx(struct rte_thash_ctx *ctx)
> {
> + struct rte_tailq_entry *te;
> + struct rte_thash_list *thash_list;
> + struct rte_thash_subtuple_helper *ent, *tmp;
> +
> + if (ctx =3D=3D NULL)
> + return;
> +
> + thash_list =3D RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
> + rte_mcfg_tailq_write_lock();
> + TAILQ_FOREACH(te, thash_list, next) {
> + if (te->data =3D=3D (void *)ctx)
> + break;
> + }
> +
> + if (te !=3D NULL)
> + TAILQ_REMOVE(thash_list, te, next);
> +
> + rte_mcfg_tailq_write_unlock();
> + ent =3D LIST_FIRST(&(ctx->head));
> + while (ent) {
> + free_lfsr(ent->lfsr);
> + tmp =3D ent;
> + ent =3D LIST_NEXT(ent, next);
> + LIST_REMOVE(tmp, next);
> + rte_free(tmp);
> + }
> +
> + rte_free(ctx);
> + rte_free(te);
> +}
> +
> +static inline void
> +set_bit(uint8_t *ptr, uint32_t bit, uint32_t pos) {
> + uint32_t byte_idx =3D pos >> 3;
> + uint32_t bit_idx =3D (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
> + uint8_t tmp;
> +
> + tmp =3D ptr[byte_idx];
> + tmp &=3D ~(1 << bit_idx);
> + tmp |=3D bit << bit_idx;
> + ptr[byte_idx] =3D tmp;
> +}
> +
> +/**
> + * writes m-sequence to the hash_key for range [start, end]
> + * (i.e. including start and end positions) */ static int
> +generate_subkey(struct rte_thash_ctx *ctx, struct thash_lfsr *lfsr,
> + uint32_t start, uint32_t end)
> +{
> + uint32_t i;
> + uint32_t req_bits =3D (start < end) ? (end - start) : (start - end);
> + req_bits++; /* due to incuding end */
> +
> + /* check if lfsr overflow period of the m-sequence */
> + if (((lfsr->bits_cnt + req_bits) > (1ULL << lfsr->deg) - 1) &&
> + ((ctx->flags &
> RTE_THASH_IGNORE_PERIOD_OVERFLOW) !=3D
> + RTE_THASH_IGNORE_PERIOD_OVERFLOW))
> + return -ENOSPC;
[Wang, Yipeng]=20
If nospace, should one increase lfsr->deg? Or if it is already the highest =
deg you predefined then what to do?
Maybe a log msg could help user with more information on the solutions.
> +
> + if (start < end) {
> + /* original direction (from left to right)*/
> + for (i =3D start; i <=3D end; i++)
> + set_bit(ctx->hash_key, get_bit_lfsr(lfsr), i);
> +
> + } else {
> + /* reverse direction (from right to left) */
> + for (i =3D end; i >=3D start; i--)
> + set_bit(ctx->hash_key, get_rev_bit_lfsr(lfsr), i);
> + }
> +
> + return 0;
> +}
> +
> +static inline uint32_t
> +get_subvalue(struct rte_thash_ctx *ctx, uint32_t offset) {
> + uint32_t *tmp, val;
> +
> + tmp =3D (uint32_t *)(&ctx->hash_key[offset >> 3]);
> + val =3D rte_be_to_cpu_32(*tmp);
> + val >>=3D (TOEPLITZ_HASH_LEN - ((offset & (CHAR_BIT - 1)) +
> + ctx->reta_sz_log));
> +
> + return val & ((1 << ctx->reta_sz_log) - 1); }
> +
> +static inline void
> +generate_compliment_table(struct rte_thash_ctx *ctx,
> + struct rte_thash_subtuple_helper *h)
> +{
> + int i, j, k;
> + uint32_t val;
> + uint32_t start;
> +
> + start =3D h->offset + h->len - (2 * ctx->reta_sz_log - 1);
> +
> + for (i =3D 1; i < (1 << ctx->reta_sz_log); i++) {
> + val =3D 0;
> + for (j =3D i; j; j &=3D (j - 1)) {
> + k =3D rte_bsf32(j);
> + val ^=3D get_subvalue(ctx, start - k +
> + ctx->reta_sz_log - 1);
> + }
> + h->compl_table[val] =3D i;
> + }
> +}
> +
> +static inline int
> +insert_before(struct rte_thash_ctx *ctx,
> + struct rte_thash_subtuple_helper *ent,
> + struct rte_thash_subtuple_helper *cur_ent,
> + struct rte_thash_subtuple_helper *next_ent,
> + uint32_t start, uint32_t end, uint32_t range_end) {
> + int ret;
> +
> + if (end < cur_ent->offset) {
> + ent->lfsr =3D alloc_lfsr(ctx);
> + if (ent->lfsr =3D=3D NULL) {
> + rte_free(ent);
> + return -ENOMEM;
> + }
> + /* generate nonoverlapping range [start, end) */
> + ret =3D generate_subkey(ctx, ent->lfsr, start, end - 1);
> + if (ret !=3D 0) {
> + free_lfsr(ent->lfsr);
> + rte_free(ent);
> + return ret;
> + }
> + } else if ((next_ent !=3D NULL) && (end > next_ent->offset)) {
> + rte_free(ent);
> + return -ENOSPC;
> + }
> + attach_lfsr(ent, cur_ent->lfsr);
> +
> + /**
> + * generate partially overlapping range
> + * [start, cur_ent->start) in reverse order
> + */
> + ret =3D generate_subkey(ctx, ent->lfsr, cur_ent->offset - 1, start);
> + if (ret !=3D 0) {
> + free_lfsr(ent->lfsr);
> + rte_free(ent);
> + return ret;
> + }
> +
> + if (end > range_end) {
> + /**
> + * generate partially overlapping range
> + * (range_end, end)
> + */
> + ret =3D generate_subkey(ctx, ent->lfsr, range_end, end - 1);
> + if (ret !=3D 0) {
> + free_lfsr(ent->lfsr);
> + rte_free(ent);
> + return ret;
> + }
> + }
> +
> + LIST_INSERT_BEFORE(cur_ent, ent, next);
> + generate_compliment_table(ctx, ent);
> + ctx->subtuples_nb++;
> + return 0;
> +}
> +
> +static inline int
> +insert_after(struct rte_thash_ctx *ctx,
> + struct rte_thash_subtuple_helper *ent,
> + struct rte_thash_subtuple_helper *cur_ent,
> + struct rte_thash_subtuple_helper *next_ent,
> + struct rte_thash_subtuple_helper *prev_ent,
> + uint32_t end, uint32_t range_end)
> +{
> + int ret;
> +
> + if ((next_ent !=3D NULL) && (end > next_ent->offset)) {
> + rte_free(ent);
> + return -EEXIST;
> + }
> +
> + attach_lfsr(ent, cur_ent->lfsr);
> + if (end > range_end) {
> + /**
> + * generate partially overlapping range
> + * (range_end, end)
> + */
> + ret =3D generate_subkey(ctx, ent->lfsr, range_end, end - 1);
> + if (ret !=3D 0) {
> + free_lfsr(ent->lfsr);
> + rte_free(ent);
> + return ret;
> + }
> + }
> +
> + LIST_INSERT_AFTER(prev_ent, ent, next);
> + generate_compliment_table(ctx, ent);
> + ctx->subtuples_nb++;
> +
> + return 0;
> }
>=20
> int
> -rte_thash_add_helper(struct rte_thash_ctx *ctx __rte_unused,
> - const char *name __rte_unused, uint32_t len __rte_unused,
> - uint32_t offset __rte_unused)
> +rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name,
> uint32_t len,
> + uint32_t offset)
> {
> + struct rte_thash_subtuple_helper *ent, *cur_ent, *prev_ent,
> *next_ent;
> + uint32_t start, end;
> + int ret;
> +
> + if ((ctx =3D=3D NULL) || (name =3D=3D NULL) || (len < ctx->reta_sz_log)=
||
> + ((offset + len + TOEPLITZ_HASH_LEN - 1) >
> + ctx->key_len * CHAR_BIT))
> + return -EINVAL;
> +
> + /* Check for existing name*/
> + LIST_FOREACH(cur_ent, &ctx->head, next) {
> + if (strncmp(name, cur_ent->name, sizeof(cur_ent->name))
> =3D=3D 0)
> + return -EEXIST;
> + }
> +
> + end =3D offset + len + TOEPLITZ_HASH_LEN - 1;
> + start =3D ((ctx->flags & RTE_THASH_MINIMAL_SEQ) =3D=3D
> + RTE_THASH_MINIMAL_SEQ) ? (end - (2 * ctx->reta_sz_log -
> 1)) :
> + offset;
> +
> + ent =3D rte_zmalloc(NULL, sizeof(struct rte_thash_subtuple_helper) +
> + sizeof(uint32_t) * (1 << ctx->reta_sz_log), 0);
> + if (ent =3D=3D NULL)
> + return -ENOMEM;
> +
> + rte_strlcpy(ent->name, name, sizeof(ent->name));
> + ent->offset =3D start;
> + ent->len =3D end - start;
> + ent->tuple_offset =3D offset;
> + ent->tuple_len =3D len;
> + ent->lsb_msk =3D (1 << ctx->reta_sz_log) - 1;
> +
> + cur_ent =3D LIST_FIRST(&ctx->head);
> + while (cur_ent) {
> + uint32_t range_end =3D cur_ent->offset + cur_ent->len;
> + next_ent =3D LIST_NEXT(cur_ent, next);
> + prev_ent =3D cur_ent;
> + /* Iterate through overlapping ranges */
> + while ((next_ent !=3D NULL) && (next_ent->offset <
> range_end)) {
> + range_end =3D RTE_MAX(next_ent->offset +
> next_ent->len,
> + range_end);
> + if (start > next_ent->offset)
> + prev_ent =3D next_ent;
> +
> + next_ent =3D LIST_NEXT(next_ent, next);
> + }
> +
> + if (start < cur_ent->offset)
> + return insert_before(ctx, ent, cur_ent, next_ent,
> + start, end, range_end);
> + else if (start < range_end)
> + return insert_after(ctx, ent, cur_ent, next_ent,
> + prev_ent, end, range_end);
> +
> + cur_ent =3D next_ent;
> + continue;
> + }
> +
> + ent->lfsr =3D alloc_lfsr(ctx);
> + if (ent->lfsr =3D=3D NULL) {
> + rte_free(ent);
> + return -ENOMEM;
> + }
> +
> + /* generate nonoverlapping range [start, end) */
> + ret =3D generate_subkey(ctx, ent->lfsr, start, end - 1);
> + if (ret !=3D 0) {
> + free_lfsr(ent->lfsr);
> + rte_free(ent);
> + return ret;
> + }
> + if (LIST_EMPTY(&ctx->head)) {
> + LIST_INSERT_HEAD(&ctx->head, ent, next);
> + } else {
> + LIST_FOREACH(next_ent, &ctx->head, next)
> + prev_ent =3D next_ent;
> +
> + LIST_INSERT_AFTER(prev_ent, ent, next);
> + }
> + generate_compliment_table(ctx, ent);
> + ctx->subtuples_nb++;
> +
> return 0;
> }
>=20
> struct rte_thash_subtuple_helper *
> -rte_thash_get_helper(struct rte_thash_ctx *ctx __rte_unused,
> - const char *name __rte_unused)
> +rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name)
> {
> + struct rte_thash_subtuple_helper *ent;
> +
> + if ((ctx =3D=3D NULL) || (name =3D=3D NULL))
> + return NULL;
> +
> + LIST_FOREACH(ent, &ctx->head, next) {
> + if (strncmp(name, ent->name, sizeof(ent->name)) =3D=3D 0)
> + return ent;
> + }
> +
> return NULL;
> }
>=20
> uint32_t
> -rte_thash_get_compliment(struct rte_thash_subtuple_helper *h
> __rte_unused,
> - uint32_t hash __rte_unused, uint32_t desired_hash __rte_unused)
> +rte_thash_get_compliment(struct rte_thash_subtuple_helper *h,
> + uint32_t hash, uint32_t desired_hash)
> {
> - return 0;
> + return h->compl_table[(hash ^ desired_hash) & h->lsb_msk];
> }
>=20
> const uint8_t *
> -rte_thash_get_key(struct rte_thash_ctx *ctx __rte_unused)
> +rte_thash_get_key(struct rte_thash_ctx *ctx)
> {
> - return NULL;
> + return ctx->hash_key;
> +}
> +
> +static inline void
> +xor_bit(uint8_t *ptr, uint32_t bit, uint32_t pos) {
> + uint32_t byte_idx =3D pos >> 3;
> + uint32_t bit_idx =3D (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
> + uint8_t tmp;
> +
> + tmp =3D ptr[byte_idx];
> + tmp ^=3D bit << bit_idx;
> + ptr[byte_idx] =3D tmp;
> +}
> +
> +int
> +rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h,
> + uint8_t *orig_tuple, uint32_t adj_bits,
> + rte_thash_check_tuple_t fn, void *userdata) {
> + unsigned i;
> +
> + if ((h =3D=3D NULL) || (orig_tuple =3D=3D NULL))
> + return -EINVAL;
> +
> + adj_bits &=3D h->lsb_msk;
> + /* Hint: LSB of adj_bits corresponds to offset + len bit of tuple */
> + for (i =3D 0; i < sizeof(uint32_t) * CHAR_BIT; i++) {
> + uint8_t bit =3D (adj_bits >> i) & 0x1;
> + if (bit)
> + xor_bit(orig_tuple, bit,
> + h->tuple_offset + h->tuple_len - 1 - i);
> + }
> +
> + if (fn !=3D NULL)
> + return (fn(userdata, orig_tuple)) ? 0 : -EEXIST;
> +
> + return 0;
> }
> diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h in=
dex
> 38a641b..fd67931 100644
> --- a/lib/librte_hash/rte_thash.h
> +++ b/lib/librte_hash/rte_thash.h
> @@ -360,6 +360,48 @@ __rte_experimental
> const uint8_t *
> rte_thash_get_key(struct rte_thash_ctx *ctx);
>=20
> +/**
> + * Function prototype for the rte_thash_adjust_tuple
> + * to check if adjusted tuple could be used.
> + * Generally it is some kind of lookup function to check
> + * if adjusted tuple is already in use.
> + *
> + * @param userdata
> + * Pointer to the userdata. It could be a pointer to the
> + * table with used tuples to search.
> + * @param tuple
> + * Pointer to the tuple to check
> + *
> + * @return
> + * 1 on success
> + * 0 otherwise
> + */
> +typedef int (*rte_thash_check_tuple_t)(void *userdata, uint8_t *tuple);
> +
> +/**
> + * Adjust tuple with complimentary bits.
> + *
[Wang, Yipeng]=20
More explanation for this API is needed.
My understanding is that user should call this function in a loop, until
the above callback function returns success thus this function succeeds.
BTW, why not put this API in the first API commit?
> + * @param h
> + * Pointer to the helper struct
> + * @param orig_tuple
> + * Pointer to the tuple to be adjusted
> + * @param adj_bits
> + * Valure returned by rte_thash_get_compliment
[Wang, Yipeng] typo. *value
> + * @param fn
> + * Callback function to check adjusted tuple. Could be NULL
> + * @param userdata
> + * Pointer to the userdata to be passed to fn(). Could be NULL
> + *
> + * @return
> + * 0 on success
> + * negative otherwise
> + */
> +__rte_experimental
> +int
> +rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h,
> + uint8_t *orig_tuple, uint32_t adj_bits,
> + rte_thash_check_tuple_t fn, void *userdata);
> +
> #ifdef __cplusplus
> }
> #endif
> diff --git a/lib/librte_hash/version.map b/lib/librte_hash/version.map in=
dex
> 93cb230..a992a1e 100644
> --- a/lib/librte_hash/version.map
> +++ b/lib/librte_hash/version.map
> @@ -32,6 +32,7 @@ DPDK_21 {
> EXPERIMENTAL {
> global:
>=20
> + rte_thash_adjust_tuple;
> rte_hash_free_key_with_position;
> rte_hash_lookup_with_hash_bulk;
> rte_hash_lookup_with_hash_bulk_data;
> --
> 2.7.4