Re: [dpdk-dev] [PATCH 2/3] lib/hash: load pData after full key compare

["Wang, Yipeng1" <yipeng1.wang@intel.com>]

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>Sent: Thursday, July 4, 2019 10:33 PM
>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; Richardson, Bruce
><bruce.richardson@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
>Cc: Gavin Hu (Arm Technology China) <Gavin.Hu@arm.com>; Ruifeng Wang (Arm Technology China) <Ruifeng.Wang@arm.com>;
>dev@dpdk.org; nd <nd@arm.com>; stable@dpdk.org; nd <nd@arm.com>; nd <nd@arm.com>
>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 <honnappa.nagarahalli@arm.com>
>> >> >Reviewed-by: Gavin Hu <gavin.hu@arm.com>
>> >> >Tested-by: Ruifeng Wang <ruifeng.wang@arm.com>
>> >> >---
>> >> > 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 = (struct rte_hash_key *) ((char *)keys +
>> >> > 					bkt->key_idx[i] * h->key_entry_size);
>> >> > 			if (rte_hash_cmp_eq(key, k->key, h) == 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] == EMPTY_SLOT)) {
>> >> > 			prim_bkt->sig_current[i] = 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 = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
>> >> > 	new_idx = (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 referenced.
>> >> >-	 * 'pdata' acts as the synchronization point when an existing hash
>> >> >-	 * entry is updated.
>> >> >+	/* The store to application data (by the application) at *data should
>> >> >+	 * 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 pData
>> in hash_add when the lock-free algorithm was introduced.
>>
>> [Wang, Yipeng] Sorry that I am still a bit confused, we already have store
>> 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 about 2 paths in the code:
>1) When a new key is getting inserted, store-release of key_idx acts as the 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 this 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-release 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 both 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 would
>> 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 easier to understand.
[Wang, Yipeng]

Acked-by: Yipeng Wang <yipeng1.wang@intel.com>