From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id EE8CD1B75D for ; Sat, 23 Mar 2019 00:48:31 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga001.jf.intel.com ([10.7.209.18]) by fmsmga103.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 22 Mar 2019 16:48:31 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,256,1549958400"; d="scan'208";a="216734237" Received: from orsmsx110.amr.corp.intel.com ([10.22.240.8]) by orsmga001.jf.intel.com with ESMTP; 22 Mar 2019 16:48:30 -0700 Received: from orsmsx156.amr.corp.intel.com (10.22.240.22) by ORSMSX110.amr.corp.intel.com (10.22.240.8) with Microsoft SMTP Server (TLS) id 14.3.408.0; Fri, 22 Mar 2019 16:48:30 -0700 Received: from orsmsx104.amr.corp.intel.com ([169.254.4.204]) by ORSMSX156.amr.corp.intel.com ([169.254.8.82]) with mapi id 14.03.0415.000; Fri, 22 Mar 2019 16:48:30 -0700 From: "Wang, Yipeng1" To: Dharmik Thakkar , "Gobriel, Sameh" , "Richardson, Bruce" , "De Lara Guarch, Pablo" , "Mcnamara, John" , "Kovacevic, Marko" CC: "dev@dpdk.org" , "Gobriel, Sameh" , "Tai, Charlie" Thread-Topic: [PATCH 1/2] hash: add lock free support for extendable bucket Thread-Index: AQHU320+gi3xAp/4cECANhIJFC/CHqYYTY0g Date: Fri, 22 Mar 2019 23:48:29 +0000 Message-ID: References: <20190320223513.31249-1-dharmik.thakkar@arm.com> <20190320223513.31249-2-dharmik.thakkar@arm.com> In-Reply-To: <20190320223513.31249-2-dharmik.thakkar@arm.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-ctpclassification: CTP_NT x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiNGZhZTk1MzEtZGQ2ZC00NjkxLWFhZmYtNTI2NmFmNWIzZjhjIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoibUttRVQ1bmxoaWZsSlFnTG5cL3gwK1Fab0tRMjI3ZFlyd293ZVdKd2tVWXJWSmd1ZDI3TjE1XC9mZ2FTcjZsdXFOIn0= x-originating-ip: [10.22.254.140] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 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: , X-List-Received-Date: Fri, 22 Mar 2019 23:48:32 -0000 Thanks for the patch!=20 Comments inlined: >-----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 > >This patch enables lock-free read-write concurrency support for >extendable bucket feature. > >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(-) > >diff --git a/doc/guides/prog_guide/hash_lib.rst b/doc/guides/prog_guide/ha= sh_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 de= fault). When the (RTE_HASH_EXTRA_FLAGS_EXT_TABLE) is set >and > in the very unlikely case due to excessive hash collisions that a key has= 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 workl= oads (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 ver= y few). Currently the extendable bucket is not supported >-with the lock-free concurrency implementation (RTE_HASH_EXTRA_FLAGS_RW_CO= NCURRENCY_LF). >+hash table size and can't tolerate any key insertion failure (even if ver= y few). [Wang, Yipeng] I am thinking maybe make it a bit more clear here by adding = something like: Please note that with the lock-free flag enabled, users need to promptly fr= ee the deleted keys, to maintain the 100% capacity guarantee. I want to add this because of the piggy-back mechanism, one un-recycled key= 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 usef= ul to remind the user here. > > >@@ -1054,7 +1059,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash = *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 sig= nature store leaking after the key_idx store. But the comment does not exactly describe this reason. >+ __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_ha= sh *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_NO_= FREE_ON_DEL to be 1 But LF flag to be 0. I think here you assume this function only called when= LF flag is 1. You may need to Add another condition e.g. if(h->ext_table_support && h->readwrite_concur_l= f_support) >+ 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; >+ } >+ } > > if (h->use_local_cache) { > lcore_id =3D rte_lcore_id(); 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 7B3A5A00E6 for ; Sat, 23 Mar 2019 00:48:33 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 1287A1B75E; Sat, 23 Mar 2019 00:48:33 +0100 (CET) Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id EE8CD1B75D for ; Sat, 23 Mar 2019 00:48:31 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga001.jf.intel.com ([10.7.209.18]) by fmsmga103.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 22 Mar 2019 16:48:31 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.60,256,1549958400"; d="scan'208";a="216734237" Received: from orsmsx110.amr.corp.intel.com ([10.22.240.8]) by orsmga001.jf.intel.com with ESMTP; 22 Mar 2019 16:48:30 -0700 Received: from orsmsx156.amr.corp.intel.com (10.22.240.22) by ORSMSX110.amr.corp.intel.com (10.22.240.8) with Microsoft SMTP Server (TLS) id 14.3.408.0; Fri, 22 Mar 2019 16:48:30 -0700 Received: from orsmsx104.amr.corp.intel.com ([169.254.4.204]) by ORSMSX156.amr.corp.intel.com ([169.254.8.82]) with mapi id 14.03.0415.000; Fri, 22 Mar 2019 16:48:30 -0700 From: "Wang, Yipeng1" To: Dharmik Thakkar , "Gobriel, Sameh" , "Richardson, Bruce" , "De Lara Guarch, Pablo" , "Mcnamara, John" , "Kovacevic, Marko" CC: "dev@dpdk.org" , "Gobriel, Sameh" , "Tai, Charlie" Thread-Topic: [PATCH 1/2] hash: add lock free support for extendable bucket Thread-Index: AQHU320+gi3xAp/4cECANhIJFC/CHqYYTY0g Date: Fri, 22 Mar 2019 23:48:29 +0000 Message-ID: References: <20190320223513.31249-1-dharmik.thakkar@arm.com> <20190320223513.31249-2-dharmik.thakkar@arm.com> In-Reply-To: <20190320223513.31249-2-dharmik.thakkar@arm.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-ctpclassification: CTP_NT x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiNGZhZTk1MzEtZGQ2ZC00NjkxLWFhZmYtNTI2NmFmNWIzZjhjIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoibUttRVQ1bmxoaWZsSlFnTG5cL3gwK1Fab0tRMjI3ZFlyd293ZVdKd2tVWXJWSmd1ZDI3TjE1XC9mZ2FTcjZsdXFOIn0= x-originating-ip: [10.22.254.140] Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 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: <20190322234829.KR-9U5ggA2yyv7k7Fa2JFUqgNv1kTXqBR3uiXVUXNW8@z> Thanks for the patch!=20 Comments inlined: >-----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 > >This patch enables lock-free read-write concurrency support for >extendable bucket feature. > >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(-) > >diff --git a/doc/guides/prog_guide/hash_lib.rst b/doc/guides/prog_guide/ha= sh_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 de= fault). When the (RTE_HASH_EXTRA_FLAGS_EXT_TABLE) is set >and > in the very unlikely case due to excessive hash collisions that a key has= 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 workl= oads (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 ver= y few). Currently the extendable bucket is not supported >-with the lock-free concurrency implementation (RTE_HASH_EXTRA_FLAGS_RW_CO= NCURRENCY_LF). >+hash table size and can't tolerate any key insertion failure (even if ver= y few). [Wang, Yipeng] I am thinking maybe make it a bit more clear here by adding = something like: Please note that with the lock-free flag enabled, users need to promptly fr= ee the deleted keys, to maintain the 100% capacity guarantee. I want to add this because of the piggy-back mechanism, one un-recycled key= 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 usef= ul to remind the user here. > > >@@ -1054,7 +1059,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash = *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 sig= nature store leaking after the key_idx store. But the comment does not exactly describe this reason. >+ __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_ha= sh *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_NO_= FREE_ON_DEL to be 1 But LF flag to be 0. I think here you assume this function only called when= LF flag is 1. You may need to Add another condition e.g. if(h->ext_table_support && h->readwrite_concur_l= f_support) >+ 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; >+ } >+ } > > if (h->use_local_cache) { > lcore_id =3D rte_lcore_id();