From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id ED6AFA05D3 for ; Mon, 25 Mar 2019 21:10:53 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 6B4D437B0; Mon, 25 Mar 2019 21:10:53 +0100 (CET) Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-eopbgr140043.outbound.protection.outlook.com [40.107.14.43]) by dpdk.org (Postfix) with ESMTP id AA95D10A3 for ; Mon, 25 Mar 2019 21:10:52 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=xS3QhNtUZBaqsuq0+4MA6v2QM97rmNHospvY4cZeTOk=; b=bQ7Lbv4bZypOVJIzLhmfIxbBJ6Ktwls2FgHrrQ+OD5x8g/lO0bipiQ1JoInX0EGu36xajVgL6VpfI5VSzaWAouOs/7ml/C0Iisv4knkdG7srIh6iFVXvmM6AfIyap9AeG9uIGAFwe9hK3Jp7uRptSUTRt20yOxH7voQvzgcssug= Received: from AM0PR08MB3379.eurprd08.prod.outlook.com (20.177.109.142) by AM0PR08MB3283.eurprd08.prod.outlook.com (52.134.94.28) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1730.16; Mon, 25 Mar 2019 20:10:50 +0000 Received: from AM0PR08MB3379.eurprd08.prod.outlook.com ([fe80::5406:d342:c4b0:c23a]) by AM0PR08MB3379.eurprd08.prod.outlook.com ([fe80::5406:d342:c4b0:c23a%2]) with mapi id 15.20.1730.019; Mon, 25 Mar 2019 20:10:50 +0000 From: Dharmik Thakkar To: "Wang, Yipeng1" CC: "Gobriel, Sameh" , "Richardson, Bruce" , "De Lara Guarch, Pablo" , "Mcnamara, John" , "Kovacevic, Marko" , "dev@dpdk.org" , "Tai, Charlie" , nd , Honnappa Nagarahalli Thread-Topic: [PATCH 1/2] hash: add lock free support for extendable bucket Thread-Index: AQHU32081C8WzzafJ0u4aa+c0p9GZ6YYVKWAgAR6LYA= Date: Mon, 25 Mar 2019 20:10:50 +0000 Message-ID: References: <20190320223513.31249-1-dharmik.thakkar@arm.com> <20190320223513.31249-2-dharmik.thakkar@arm.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Dharmik.Thakkar@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: f93c7311-3fa0-41c8-c431-08d6b15dfa07 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600127)(711020)(4605104)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM0PR08MB3283; x-ms-traffictypediagnostic: AM0PR08MB3283: nodisclaimer: True x-microsoft-antispam-prvs: x-forefront-prvs: 0987ACA2E2 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(346002)(366004)(396003)(136003)(376002)(39860400002)(199004)(51914003)(189003)(13464003)(2616005)(11346002)(486006)(6486002)(25786009)(229853002)(82746002)(86362001)(68736007)(83716004)(71190400001)(71200400001)(6436002)(3846002)(6116002)(66066001)(316002)(36756003)(476003)(99286004)(97736004)(446003)(54906003)(33656002)(102836004)(6506007)(53546011)(81156014)(81166006)(8676002)(8936002)(14454004)(7736002)(76176011)(305945005)(6246003)(2906002)(106356001)(186003)(26005)(105586002)(256004)(14444005)(6916009)(5660300002)(4326008)(72206003)(478600001)(53936002)(6512007); DIR:OUT; SFP:1101; SCL:1; SRVR:AM0PR08MB3283; H:AM0PR08MB3379.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-microsoft-antispam-message-info: KcSCsjZvP8HNcIQXxh3vuANBctwoIXtAK4VqKt6EGzReF7AkNGTthFuytXP2BLsMcjvbNQLOsldyk2jhezm898qU3Vi1rN0IbtvdxliGkmUPMWF9niyQ2xT+wrEUQFWIxirAqqdRsB8vpdFA2LBZo3S8LuFZ/LgDd7J7FnaOuKEmemSdz0TsL/vUiXNsix/0DVcuQT9Q4eGG0j/ZugyP4AmvcV5AgFdhlTI4LXGa3LKYPEV2eL09Mrhm2Y2BB6zceuAGtkiN9oQz6+XDjw2NLwSVPjwE6lea0Ng/JLUpCHuYymaXl5tR7KnLNazGWM2UyEkYqXNitMdm0e+pm9LoTrjkVmMimP1q7jRR22SQfWDEfjHZpRH7OP7VXKp5x0z3evLuZMJxGBo/0pHnUV12KzcIQs5jmgvLo42xOhNE37k= Content-Type: text/plain; charset="UTF-8" Content-ID: Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: f93c7311-3fa0-41c8-c431-08d6b15dfa07 X-MS-Exchange-CrossTenant-originalarrivaltime: 25 Mar 2019 20:10:50.3931 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM0PR08MB3283 Subject: Re: [dpdk-dev] [PATCH 1/2] hash: add lock free support for extendable bucket X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 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" Message-ID: <20190325201050.OMiS6ZRwZM4uqe6_oarjnouYCfhpsP-LOTqNYGHZ3nM@z> +Honnappa Hi Yipeng, Thank you for reviewing! > On Mar 22, 2019, at 6:48 PM, Wang, Yipeng1 wrote= : >=20 > Thanks for the patch!=20 >=20 > Comments inlined: >=20 >> -----Original Message----- >> From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com] >> Sent: Wednesday, March 20, 2019 3:35 PM >> To: Wang, Yipeng1 ; Gobriel, Sameh ; Richardson, Bruce >> ; De Lara Guarch, Pablo ; Mcnamara, John >> ; Kovacevic, Marko >> Cc: dev@dpdk.org; Dharmik Thakkar >> Subject: [PATCH 1/2] hash: add lock free support for extendable bucket >>=20 >> This patch enables lock-free read-write concurrency support for >> extendable bucket feature. >>=20 >> Suggested-by: Honnappa Nagarahalli >> Signed-off-by: Dharmik Thakkar >> Reviewed-by: Ruifeng Wang >> Reviewed-by: Gavin Hu >> Reviewed-by: Honnappa Nagarahalli >> --- >> doc/guides/prog_guide/hash_lib.rst | 3 +- >> lib/librte_hash/rte_cuckoo_hash.c | 163 ++++++++++++++++++++--------- >> lib/librte_hash/rte_cuckoo_hash.h | 7 ++ >> 3 files changed, 121 insertions(+), 52 deletions(-) >>=20 >> diff --git a/doc/guides/prog_guide/hash_lib.rst b/doc/guides/prog_guide/= hash_lib.rst >> index 85a6edfa8b16..b00446e949ba 100644 >> --- a/doc/guides/prog_guide/hash_lib.rst >> +++ b/doc/guides/prog_guide/hash_lib.rst >> @@ -108,8 +108,7 @@ Extendable Bucket Functionality support >> An extra flag is used to enable this functionality (flag is not set by d= efault). When the (RTE_HASH_EXTRA_FLAGS_EXT_TABLE) is set >> and >> in the very unlikely case due to excessive hash collisions that a key ha= s failed to be inserted, the hash table bucket is extended with a >> linked >> list to insert these failed keys. This feature is important for the work= loads (e.g. telco workloads) that need to insert up to 100% of the >> -hash table size and can't tolerate any key insertion failure (even if v= ery few). Currently the extendable bucket is not supported >> -with the lock-free concurrency implementation (RTE_HASH_EXTRA_FLAGS_RW_= CONCURRENCY_LF). >> +hash table size and can't tolerate any key insertion failure (even if v= ery few). > [Wang, Yipeng] I am thinking maybe make it a bit more clear here by addin= g something like: > Please note that with the lock-free flag enabled, users need to promptly = free the deleted keys, to maintain the 100% capacity guarantee. >=20 > I want to add this because of the piggy-back mechanism, one un-recycled k= ey with an un-recycled ext bucket may actually makes in total > of 9 entries unavailable (8 entries in the ext bucket). So it would be us= eful to remind the user here. All right. I will add it. >>=20 >>=20 >> @@ -1054,7 +1059,15 @@ __rte_hash_add_key_with_hash(const struct rte_has= h *h, const void *key, >> /* Check if slot is available */ >> if (likely(cur_bkt->key_idx[i] =3D=3D EMPTY_SLOT)) { >> cur_bkt->sig_current[i] =3D short_sig; >> - cur_bkt->key_idx[i] =3D new_idx; >> + /* Key can be of arbitrary length, so it is >> + * not possible to store it atomically. >> + * Hence the new key element's memory stores >> + * (key as well as data) should be complete >> + * before it is referenced. >> + */ > [Wang, Yipeng] My understanding is this atomic store is to prevent the s= ignature store leaking after the key_idx store. > But the comment does not exactly describe this reason. I will update the comment. >> + __atomic_store_n(&cur_bkt->key_idx[i], >> + new_idx, >> + __ATOMIC_RELEASE); >> __hash_rw_writer_unlock(h); >> return new_idx - 1; >> } >> @@ -1545,6 +1597,14 @@ rte_hash_free_key_with_position(const struct rte_= hash *h, >> /* Out of bounds */ >> if (position >=3D total_entries) >> return -EINVAL; >> + if (h->ext_table_support) { >> + uint32_t index =3D h->ext_bkt_to_free[position]; > [Wang, Yipeng] I think user can theoretically set RTE_HASH_EXTRA_FLAGS_N= O_FREE_ON_DEL to be 1 > But LF flag to be 0. I think here you assume this function only called wh= en LF flag is 1. You may need to > Add another condition e.g. if(h->ext_table_support && h->readwrite_concur= _lf_support) Correct. I will update it. >> + if (index) { >> + /* Recycle empty ext bkt to free list. */ >> + rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index); >> + h->ext_bkt_to_free[position] =3D 0; >> + } >> + } >>=20 >> if (h->use_local_cache) { >> lcore_id =3D rte_lcore_id();