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

[Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>]

> >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.