From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id E5C58A0A0E; Wed, 7 Apr 2021 14:53:42 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 7683E406A3; Wed, 7 Apr 2021 14:53:42 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by mails.dpdk.org (Postfix) with ESMTP id 81DBE4013F for ; Wed, 7 Apr 2021 14:53:40 +0200 (CEST) IronPort-SDR: uyUWCsv0MGcFWMMD4Yddlb/VIkAfPbTf7hrZbU0vNdTxQ4qByn4r2uz7egUlm4AXwwE8lA8k3i LRtEVzBV0t3g== X-IronPort-AV: E=McAfee;i="6000,8403,9947"; a="193412665" X-IronPort-AV: E=Sophos;i="5.82,203,1613462400"; d="scan'208";a="193412665" Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by orsmga102.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 07 Apr 2021 05:53:39 -0700 IronPort-SDR: 9cEQxo7Kp6xDsEC2I9AaqQ6pQAE7T12ecRyeTZqh0MykBQOtYwqFFE84ONBmZxqDagpWBO1F6Z IEhPlOTYCj2Q== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.82,203,1613462400"; d="scan'208";a="449111626" Received: from orsmsx603.amr.corp.intel.com ([10.22.229.16]) by fmsmga002.fm.intel.com with ESMTP; 07 Apr 2021 05:53:38 -0700 Received: from orsmsx602.amr.corp.intel.com (10.22.229.15) by ORSMSX603.amr.corp.intel.com (10.22.229.16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2106.2; Wed, 7 Apr 2021 05:53:37 -0700 Received: from ORSEDG601.ED.cps.intel.com (10.7.248.6) by orsmsx602.amr.corp.intel.com (10.22.229.15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2106.2 via Frontend Transport; Wed, 7 Apr 2021 05:53:37 -0700 Received: from NAM04-DM6-obe.outbound.protection.outlook.com (104.47.73.41) by edgegateway.intel.com (134.134.137.102) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.2106.2; Wed, 7 Apr 2021 05:53:33 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=AuLl771d3xmJLWqWWWlvhCserBe9kOTZCgTyy2yD9OK4et6HiMIA5dQm0Dp8HYeFsDKS6g2QW/MrkeyqtSf7hEvxA/NL9IL9qak3oDZUMjuO3Hlbuec55cUpK+2i6FtFKMi1i0Zi8B/DdtuODCcCAJDzlwU1/o7redEaTWnZgk1VCI0t4pYs5HX0Kju2ew+WsA6XVO8blb2OUWpQ3Pw6XTB9BkqK90pbMfrIcVweAkftswRbsoS0siwGOiv0QUL5kDoJoeb2DxAbsampR2mgp9vock7Z7n3oZjZUvT4843msG4k0yyol6Rhe7Q99PnYt71mnnx2/8AW8MMA/3zOfdQ== 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=dDo6yLrK1fguSJkweAZJPDHwNzktkQuoiTJn26HZ7Zs=; b=FcquqFsOpbRhtjT2ySmZ66S8WOHxr4Df7B8l+PQxUssdH1OKKseujR6pLR5RWZegsnLAhCdgM0/1axTHG9MNi8fBjxI8b5nWAVDic/wBs1c//tBiSMf72R6M9x5kT3fg6kbBhuVHDxPlIeYCtntdLj1PGovtoyXP7X+MNRXlNCWvM14s8C6TjkxDClaZ7Xi4ddnVK7pHEuKEvJ+gVsLSOF+hQ4Dpz3U6XcG8FjrGNcZZ7havhNJlVX7ZUHqLS4pCz49eaTQfphCZQIZvHaxp4lYSThxCU2cImmf5cYBMlIExCX41Ki+NrAv/x7x5xpv4mzGfMOc34T3Wooi4oViXcg== 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=dDo6yLrK1fguSJkweAZJPDHwNzktkQuoiTJn26HZ7Zs=; b=d6mZUa7FGg2FIrI3Wjx+jyIsv/gewdP0RQRq/MF6p+z48xWdIV1WUdkC1rEzP97pTigNjheNM6sPySZMEyv65/V7+fghX2E7nNI/is6ItBrACXcL+rxYlWU/NnpyaMjNYDy+qpUkEbIN6Ad0LkMDSBrTR5o9tgCUMSOLAHIeYdw= Received: from DM6PR11MB4491.namprd11.prod.outlook.com (2603:10b6:5:204::19) by DM4PR11MB5438.namprd11.prod.outlook.com (2603:10b6:5:399::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3999.28; Wed, 7 Apr 2021 12:53:30 +0000 Received: from DM6PR11MB4491.namprd11.prod.outlook.com ([fe80::3182:6da2:8c64:f07a]) by DM6PR11MB4491.namprd11.prod.outlook.com ([fe80::3182:6da2:8c64:f07a%3]) with mapi id 15.20.3999.032; Wed, 7 Apr 2021 12:53:30 +0000 From: "Ananyev, Konstantin" To: "Medvedkin, Vladimir" , "dev@dpdk.org" CC: "Chilikin, Andrey" , "Kinsella, Ray" , "Wang, Yipeng1" , "Gobriel, Sameh" , "Richardson, Bruce" Thread-Topic: [PATCH v2 2/3] hash: add predictable RSS implementation Thread-Index: AQHXKx4z4KHwRyQf/km0I9UBUFkDHqqo978g Date: Wed, 7 Apr 2021 12:53:30 +0000 Message-ID: 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-GB, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-product: dlpe-windows dlp-reaction: no-action dlp-version: 11.5.1.3 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: [109.255.184.192] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 9e5e7c2e-55f3-4acf-e462-08d8f9c42556 x-ms-traffictypediagnostic: DM4PR11MB5438: x-ld-processed: 46c98d88-e344-4ed4-8496-4ed7712e255d,ExtAddr x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:3631; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: TISTg1nhjU1xaw2HBZMeok3wIv11lrOBi6NWjsIpdfZv5i998BA634ECmwB6TqQkgUmqGLb3lwTIVdAOxb259CBqvPgTrSGj7Y4aU0ecsWhLE0k11YOOyazI9emz2YdLOklZLsaWSwFacb3qg8jLDGEZzVj3MicTgwkrPva552Y5bEOs4sSmE4SIeYN8bkE8bg5Xsnx47ZQ48S8gaqcs3q97K6sOg4F/wRBrqYjJ+FQxjrdArXJIETStEt3Ad1dp0melfimX57xdbvpNPTXxz63HFKiaP7LoFlu2b8GqcEIUscj5/9/gcZYz4mUdSzAhWayyjtEdtUOGyL5r2DOODbu7+8NvEw57uXa0pFotTCZksotN7W6LuPxeWcubDrF+Y5kA1R1Kfp4iaC8igUlHUndSoUH43oNWjqhxlppMtgUxhAgkVnBnYlmWhlgWcpzsugpPMjKayWf19hiwF1nlgNCtC3kHqqOHtrOV645n3YFChsc9NvB9Hg1+LC9YfU2TcyVGjuw0WAh59dRSBxUyG649XN+iALI2+3grc0IShIBfQPApPNALR33GyszYn1fqyyUewyEAR+286BFt7PqOkkJLsVlF0j2KfYt+NHZh3BwmDDvizCiTCuBzrTNqWUy5A/UqJrMGnFGWCSZ2F05J6i5hXaVhz/d2zFmi8sxU4M4= x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:DM6PR11MB4491.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFS:(39860400002)(376002)(346002)(136003)(396003)(366004)(66556008)(66476007)(66446008)(66946007)(64756008)(5660300002)(30864003)(52536014)(38100700001)(55016002)(76116006)(9686003)(186003)(33656002)(26005)(2906002)(316002)(4326008)(8936002)(8676002)(83380400001)(54906003)(110136005)(71200400001)(478600001)(7696005)(107886003)(86362001)(6506007)(55236004)(579004); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata: =?us-ascii?Q?lq3tkrenSqZj/ZlaoQWy1poQ6A7lOmU0BGs9ryyVBdqbj41HSB9i4wLDufuH?= =?us-ascii?Q?0zwMNmiQ0ETEL0y7XN2TtpbU55x1//TbjgO8PLJRgQup8R7UZjZ2+MZ1v1ZM?= =?us-ascii?Q?JpjYfiT7yvZklP++KZjylSeGnJcw5YbrizyELqLRQjO661SQ9LpWdhpFear9?= =?us-ascii?Q?wHe3fM3bsATScNdBAY5/nOGcon4Blbzcz9xOCEYqE0tl9TgUMfnk24Ou+ZfR?= =?us-ascii?Q?U1bwsD47kbiLyJ0c2W8SUQiPOcp/uQUtx71KXDh1El5C9JmTCeI5OErQCsd/?= =?us-ascii?Q?+ju4AXzJgW+xQ7p4TsZbkT6CjemEzNO0LJNcDK6HPgORYyR5SZbFTzBFPSGq?= =?us-ascii?Q?yTk9lW8pcSK4+uyBSguPG154o48zilGUfhsFcIIDLOYz1cPmg7Nzpd5lVDFu?= =?us-ascii?Q?E9G4TiDf99KJwofAUuC+4VT17+8KJPmPMbZRq3gSBRi1aW+2XN0XkaNF0Njl?= =?us-ascii?Q?9cFbabit+Q/4yLiHWkVpIVO/hEa6bI+f+h4qMAhyQuxT1w6ATpxQDKaS4uSJ?= =?us-ascii?Q?ChDi4yTO9i/VPOBXqGw58qsDJJzFWUQ96Nno536Yfg81kYqugJrbeBsqtdHz?= =?us-ascii?Q?lDcWK78Mn/Kzfo1nib9c3YLXZavkZCtJFSklocDUQxDzWcM3Jry71zwHobeB?= =?us-ascii?Q?GdZvpqtDLk6ZZ11LvrS8MRizwT2rurf+V+Vnyre5u6JCyxXKoC88jzFf2t4s?= =?us-ascii?Q?aMzEKDFAp9gIZyxCPzSB6y62+4FJuEJH1Z8BoI7/YcRmOfYt8UzSEJjZ7uEV?= =?us-ascii?Q?GVkrZFtZeiuJP78YszoLEvm2qrY2Cz6k0Bf1iJEGYkTtOtudJUDG1IZqAN+2?= =?us-ascii?Q?p5hZOhetYDcxGLU4tJwg8ZeRTO50iSvlzZN2A3HlJmXqf3H+uZSnPcX4kyLP?= =?us-ascii?Q?cNput6pApbI0fnsuTfHoZXAiS9zvKm8bpaZd+6MKPVmUUbbvPnAW7xR1w/ne?= =?us-ascii?Q?KYwsCmW0bFHKiLQtlM9CZpWp0YArO/3Xz/w2o+ASaj08UfVYgIAR1BvOYW8T?= =?us-ascii?Q?SNqn/6oWGxw3rZwj8OWDVPnBNQ9ss2V0TEakybwJLBUsKrnW0qoUanf3sD4B?= =?us-ascii?Q?2Bs9PMbmYZ/HKALEwNfjQZZwXyY7pM//ytDBXlvi8bRlVLfWjDIzgPHHmcC5?= =?us-ascii?Q?PGLPuD49/drJxw90TAG/FQULLC8YuYvrLFaciqzjGcYKxxRUaioEyK7BXSlw?= =?us-ascii?Q?92WkFwkek58/j7k2TCPhqVJskeOrjWLF0MNmoIDjcfxXA54MtEFGXyNW6uuF?= =?us-ascii?Q?Dl/UvXsKNKZqtBA0XLLcBWki6So9P+kAF0zpIjgeK0P7BbMD+Kl4rk4HXVMy?= =?us-ascii?Q?qeu8CP5HLXpVtYz9MeDiM4sB?= 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: DM6PR11MB4491.namprd11.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 9e5e7c2e-55f3-4acf-e462-08d8f9c42556 X-MS-Exchange-CrossTenant-originalarrivaltime: 07 Apr 2021 12:53:30.6024 (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: ckHNOR+AlvNustZSrBO3t7nlkaUf/tX0LQo4Ax18AQ8VoKQTLkwz7/vR1uxcKf3I1JWm1AZ3hV/37E41LrpPOjSCgBeddztOKRHf+WZoEtc= X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM4PR11MB5438 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Hi Vladimir, Few comments below, mostly minor. One generic one - doc seems missing. With that in place: Acked-by: Konstantin Ananyev >=20 > This patch implements predictable RSS functionality. >=20 > Signed-off-by: Vladimir Medvedkin > --- > 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 > index 79e8724..cc60ada 100644 > --- a/lib/librte_hash/rte_thash.c > +++ b/lib/librte_hash/rte_thash.c > @@ -12,6 +12,45 @@ > #include >=20 > #define THASH_NAME_LEN 64 > +#define TOEPLITZ_HASH_LEN 32 > + > +#define RETA_SZ_MIN 2U > +#define RETA_SZ_MAX 16U Should these RETA_SZ defines be in public header? So user can know what are allowed values? > +#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; Empty line is missing. > + 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; Just as a nit to be consistent with the line below: pos / CHAR_BIT;=20 > + 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; > + > + 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); Helper can be used by data-path code (via rte_thash_get_compliment()) right= ? Then might be better to align it at cache-line.=20 > + 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_unuse= d, > - 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]; > } Would it make sense to add another-one for multi values: rte_thash_get_compliment(uint32_t hash, const uint32_t desired_hashes[], ui= nt32_t adj_hash[], uint32_t num); So user can get adjustment values for multiple queues at once?=20 >=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; > } Not sure is there much point to have a callback that is called only once. Might be better to rework the function in a way that user to provide 2 call= backs - one to generate new value, second to check. Something like that: int rte_thash_gen_tuple(struct rte_thash_subtuple_helper *h, uint8_t *tuple, uint32_t desired_hash, int (*cb_gen_tuple)(uint8_t *, void *), int (*cb_check_tuple)(const uint8_t *, void *), void *userdata)=20 { do { rc =3D cb_gen_tuple(tuple, userdata); if (rc !=3D 0) return rc; hash =3D rte_softrss(tuple, ...); adj =3D rte_thash_get_compliment(h, hash, desired_hash); update_tuple(tuple, adj, ...); rc =3D cb_check_tuple(tuple, userdata);=20 } while(rc !=3D 0); return rc; } > diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h > index 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. > + * > + * @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 > + * @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 > index 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