From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 167E6A00E6 for ; Mon, 8 Jul 2019 18:44:22 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 8580F4C8D; Mon, 8 Jul 2019 18:44:20 +0200 (CEST) Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id 79AC32C23; Mon, 8 Jul 2019 18:44:17 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga005.jf.intel.com ([10.7.209.41]) by fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 08 Jul 2019 09:44:16 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.63,466,1557212400"; d="scan'208";a="340495545" Received: from orsmsx101.amr.corp.intel.com ([10.22.225.128]) by orsmga005.jf.intel.com with ESMTP; 08 Jul 2019 09:44:15 -0700 Received: from orsmsx104.amr.corp.intel.com ([169.254.4.232]) by ORSMSX101.amr.corp.intel.com ([169.254.8.157]) with mapi id 14.03.0439.000; Mon, 8 Jul 2019 09:44:14 -0700 From: "Wang, Yipeng1" To: Honnappa Nagarahalli , "Gobriel, Sameh" , "Richardson, Bruce" , "De Lara Guarch, Pablo" CC: "Gavin Hu (Arm Technology China)" , "Ruifeng Wang (Arm Technology China)" , "dev@dpdk.org" , nd , "stable@dpdk.org" , nd , nd Thread-Topic: [PATCH 2/3] lib/hash: load pData after full key compare Thread-Index: AQHVK5syNdL2m0zXvEuHE2Sc2GqGyKaxYNTwgAXcXYCAAmsW8IACXC8AgAT82qA= Date: Mon, 8 Jul 2019 16:44:14 +0000 Message-ID: References: <20190625211520.43181-1-honnappa.nagarahalli@arm.com> <20190625211520.43181-3-honnappa.nagarahalli@arm.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-product: dlpe-windows dlp-version: 11.0.600.7 dlp-reaction: no-action x-ctpclassification: CTP_NT x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiYjhjYmFhMjItNTlmOC00OGRlLTk0ZGQtYTMwYTY5ZGQwMTZmIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiemtwWjdDWXV3Y3JyM2R1aFNNYzlGUDJqNGdcL3FOVkd6RkZXMFwvYWpaT01NZFRaVTQ5dENpdEVEYTNldXRuU3ZyIn0= x-originating-ip: [10.22.254.138] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH 2/3] lib/hash: load pData after full key compare 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" >-----Original Message----- >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] >Sent: Thursday, July 4, 2019 10:33 PM >To: Wang, Yipeng1 ; Gobriel, Sameh ; Richardson, Bruce >; De Lara Guarch, Pablo >Cc: Gavin Hu (Arm Technology China) ; Ruifeng Wang (Arm = Technology China) ; >dev@dpdk.org; nd ; stable@dpdk.org; nd ; nd >Subject: RE: [PATCH 2/3] lib/hash: load pData after full key compare > >> >Subject: RE: [PATCH 2/3] lib/hash: load pData after full key compare >> > >> >Thank you Yipeng for your comments. >> > >> >> > >> >> >When a hash entry is added, there are 2 sets of stores. >> >> > >> >> >1) The application writes its data to memory (whose address is >> >> >provided in rte_hash_add_key_with_hash_data API (or NULL)) >> >> >2) The rte_hash library writes to its own internal data structures; >> >> >key store entry and the hash table. >> >> > >> >> >The only ordering requirement between these 2 is that - the store to >> >> >the application data must complete before the store to key_index. >> >> >There are no ordering requirements between the stores to the >> >> >key/signature and store to application data. The synchronization >> >> >point for application data can be any point between the 'store to >> >> >application data' and 'store to the key_index'. So, pData should not >> >> >be a guard variable for the data in hash table. It should be a guard >> >> >variable only for the application data written to the memory >> >> >location pointed by pData. Hence, pData can be loaded after full key >> comparison. >> >> > >> >> >Fixes: e605a1d36 ("hash: add lock-free r/w concurrency") >> >> >Cc: stable@dpdk.org >> >> > >> >> >Signed-off-by: Honnappa Nagarahalli >> >> >Reviewed-by: Gavin Hu >> >> >Tested-by: Ruifeng Wang >> >> >--- >> >> > lib/librte_hash/rte_cuckoo_hash.c | 67 >> >> >+++++++++++++++---------------- >> >> > 1 file changed, 32 insertions(+), 35 deletions(-) >> >> > >> >> >diff --git a/lib/librte_hash/rte_cuckoo_hash.c >> >> >b/lib/librte_hash/rte_cuckoo_hash.c >> >> >index f37f6957d..077328fed 100644 >> >> >--- a/lib/librte_hash/rte_cuckoo_hash.c >> >> >+++ b/lib/librte_hash/rte_cuckoo_hash.c >> >> >@@ -649,9 +649,11 @@ search_and_update(const struct rte_hash *h, >> >> >void >> >> *data, const void *key, >> >> > k =3D (struct rte_hash_key *) ((char *)keys + >> >> > bkt->key_idx[i] * h->key_entry_size); >> >> > if (rte_hash_cmp_eq(key, k->key, h) =3D=3D 0) { >> >> >- /* 'pdata' acts as the synchronization point >> >> >- * when an existing hash entry is updated. >> >> >- * Key is not updated in this case. >> >> >+ /* The store to application data at *data >> >> >+ * should not leak after the store to pdata >> >> >+ * in the key store. i.e. pdata is the guard >> >> >+ * variable. Release the application data >> >> >+ * to the readers. >> >> > */ >> >> > __atomic_store_n(&k->pdata, >> >> > data, >> >> >@@ -711,11 +713,10 @@ rte_hash_cuckoo_insert_mw(const struct >> >> rte_hash *h, >> >> > /* Check if slot is available */ >> >> > if (likely(prim_bkt->key_idx[i] =3D=3D EMPTY_SLOT)) { >> >> > prim_bkt->sig_current[i] =3D sig; >> >> >- /* 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. >> >> >+ /* Store to signature and key should not >> >> >+ * leak after the store to key_idx. i.e. >> >> >+ * key_idx is the guard variable for signature >> >> >+ * and key. >> >> > */ >> >> > __atomic_store_n(&prim_bkt->key_idx[i], >> >> > new_idx, >> >> >@@ -990,17 +991,15 @@ __rte_hash_add_key_with_hash(const struct >> >> >rte_hash *h, const void *key, >> >> > >> >> > new_k =3D RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size= ); >> >> > new_idx =3D (uint32_t)((uintptr_t) slot_id); >> >> >- /* Copy key */ >> >> >- memcpy(new_k->key, key, h->key_len); >> >> >- /* 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 reference= d. >> >> >- * 'pdata' acts as the synchronization point when an existing hash >> >> >- * entry is updated. >> >> >+ /* The store to application data (by the application) at *data sho= uld >> >> >+ * not leak after the store of pdata in the key store. i.e. pdata = is >> >> >+ * the guard variable. Release the application data to the readers= . >> >> > */ >> >> > __atomic_store_n(&new_k->pdata, >> >> > data, >> >> > __ATOMIC_RELEASE); >> >> [Wang, Yipeng] Actually do we need to guard pdata for the newly >> >> inserted key? I thought the guard of key_idx already can make sure >> >> The order for the application to read data. >> >Yes, you are correct. In the hash_add case, the store-release on >> >key_idx would be sufficient. However, hash_update case requires >> >store-release on pData. This was the reason to keep store-release for p= Data >> in hash_add when the lock-free algorithm was introduced. >> >> [Wang, Yipeng] Sorry that I am still a bit confused, we already have sto= re >> release in search_and_update function right? Isn't that enough for the >> hash_update case? >No problem, looks like I did not use the correct terms. We are talking abo= ut 2 paths in the code: >1) When a new key is getting inserted, store-release of key_idx acts as th= e guard variable for the store to application data as well as >the stores to internal hash table structures (signature, key, pdata). >2) But when an existing key is updated, there is no store to key_idx. In t= his case 'pdata' acts as the guard variable for the store to >application data. Hence we need a store-release on 'pdata'. Due to this we= need a load-acquire on 'pdata' in the lookup function. > >Then, why do we need store-release on 'pdata' in code path 1? - store-rele= ase on 'pdata' in code path 1 is done for consistency with >code path 2 i.e. we want to use store-release on 'pdata' consistently in b= oth the code paths (unless we see performance degradation >in path 1). IMO, it is much easier to understand the code this way. > >> > >> >> >+ /* Copy key */ >> >> >+ memcpy(new_k->key, key, h->key_len); >> >> [Wang, Yipeng] You don't need to do the order change just to show the >> >> point of unnecessary ordering I think. >> >> I am afraid it may cause further confusion for future people who read >> >> this change, especially it is not in the commit Message (and it is a = bug fix). >> >I made this change to keep it inline with the corresponding change in >> >the lookup function. I can add this explanation to the commit message. >> Please let me know if this is ok for you. >> >> [Wang, Yipeng] Thanks for the change. >> To me it still looks unnecessary but If you think this cosmetic change w= ould >> help others to understand the code better, I am OK with it. >I agree this is unnecessary. When the change was being reviewed internally= at Arm, I had not made this change initially. It resulted in >questions as the new key insert's memory ordering steps did not match that= of the lookup function. IMO, if we look at the algorithm >as a whole (instead of looking at this commit alone), this code will be ea= sier to understand. [Wang, Yipeng] Acked-by: Yipeng Wang