Re: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys

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

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>Sent: Sunday, September 30, 2018 4:06 PM
>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Richardson, Bruce <bruce.richardson@intel.com>; De Lara Guarch, Pablo
><pablo.de.lara.guarch@intel.com>
>Cc: dev@dpdk.org; Gavin Hu (Arm Technology China) <Gavin.Hu@arm.com>; Steve Capper <Steve.Capper@arm.com>; Ola Liljedahl
><Ola.Liljedahl@arm.com>; nd <nd@arm.com>
>Subject: RE: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys
>
>> >+	__atomic_store_n(&h->tbl_chng_cnt,
>> >+			 h->tbl_chng_cnt + 1,
>> >+			 __ATOMIC_RELEASE);
>> >+	/* The stores to sig_alt and sig_current should not
>> >+	 * move above the store to tbl_chng_cnt.
>> >+	 */
>> >+	__atomic_thread_fence(__ATOMIC_RELEASE);
>> >+
>> [Wang, Yipeng] I believe for X86 this fence should not be compiled to any
>> code, otherwise we need macros for the compile time check.
>'__atomic_thread_fence(__ATOMIC_RELEASE)' provides load-load and load-store fence [1]. Hence, it should not add any barriers for
>x86.
>
>[1] https://preshing.com/20130922/acquire-and-release-fences/
>
[Wang, Yipeng] Thanks for the link, it is very informative!
>>
>> >@@ -926,30 +957,56 @@ __rte_hash_lookup_with_hash(const struct
>> rte_hash *h, const void *key,
>> > 	uint32_t bucket_idx;
>> > 	hash_sig_t alt_hash;
>> > 	struct rte_hash_bucket *bkt;
>> >+	uint32_t cnt_b, cnt_a;
>> > 	int ret;
>> >
>> >-	bucket_idx = sig & h->bucket_bitmask;
>> >-	bkt = &h->buckets[bucket_idx];
>> >-
>> > 	__hash_rw_reader_lock(h);
>> >
>> >-	/* Check if key is in primary location */
>> >-	ret = search_one_bucket(h, key, sig, data, bkt);
>> >-	if (ret != -1) {
>> >-		__hash_rw_reader_unlock(h);
>> >-		return ret;
>> >-	}
>> >-	/* Calculate secondary hash */
>> >-	alt_hash = rte_hash_secondary_hash(sig);
>> >-	bucket_idx = alt_hash & h->bucket_bitmask;
>> >-	bkt = &h->buckets[bucket_idx];
>> >+	do {
>> [Wang, Yipeng] As far as I know, the MemC3 paper "MemC3: Compact and
>> Concurrent MemCache with Dumber Caching and Smarter Hashing"
>> as well as OvS cmap uses similar version counter to implement read-write
>> concurrency for hash table, but one difference is reader checks even/odd of
>> the version counter to make sure there is no concurrent writer. Could you just
>> double check and confirm that this is not needed for your implementation?
>>
>I relooked at this paper. My patch makes use of the fact that during the process of shifting the key will be present in both primary and
>secondary buckets. The check for odd version counter is not required as the full key comparison would have identified any false
>signature matches.
[Wang, Yipeng] I was thinking about another corner case and wondering if the version counter needs to be done on key deletion as well.
For example, a reader reads out the index and falsely matches a signature, before it reads out the data and the key, the key-data pair got
deleted, removed, and recycled by another writer thread.  This writer partially overwrote the key (because key store is too large to be atomic).
Now, the reader begins to compare the key, and accidentally matches the key (because the key is partially written and accidentally matches), will
The reader read the wrong data out (which should have been a lookup miss)?