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

Wang, Yipeng1 yipeng1.wang at intel.com
Thu Jul 4 02:39:12 CEST 2019


>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli at arm.com]
>Sent: Monday, July 1, 2019 9:35 PM
>To: Wang, Yipeng1 <yipeng1.wang at intel.com>; Gobriel, Sameh <sameh.gobriel at intel.com>; Richardson, Bruce
><bruce.richardson at intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch at intel.com>
>Cc: Gavin Hu (Arm Technology China) <Gavin.Hu at arm.com>; Ruifeng Wang (Arm Technology China) <Ruifeng.Wang at arm.com>;
>dev at dpdk.org; Honnappa Nagarahalli <Honnappa.Nagarahalli at arm.com>; nd <nd at arm.com>; stable at dpdk.org; nd <nd at 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 at dpdk.org
>> >
>> >Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli at arm.com>
>> >Reviewed-by: Gavin Hu <gavin.hu at arm.com>
>> >Tested-by: Ruifeng Wang <ruifeng.wang at 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?
>
>> >+	/* 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.



More information about the dev mailing list