From mboxrd@z Thu Jan 1 00:00:00 1970 From: Dharmik Thakkar Subject: Re: [PATCH 1/2] hash: add lock free support for extendable bucket 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> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Cc: "Gobriel, Sameh" , "Richardson, Bruce" , "De Lara Guarch, Pablo" , "Mcnamara, John" , "Kovacevic, Marko" , "dev@dpdk.org" , "Tai, Charlie" , nd , Honnappa Nagarahalli To: "Wang, Yipeng1" Return-path: 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) In-Reply-To: Content-Language: en-US Content-ID: List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" +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();