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

[Bruce Richardson]

On Fri, Sep 28, 2018 at 02:00:00AM +0100, Wang, Yipeng1 wrote:
> Reply inlined:
> 
> >-----Original Message-----
> >From: dev [mailto:dev-bounces at dpdk.org] On Behalf Of Honnappa Nagarahalli
> >Sent: Thursday, September 6, 2018 10:12 AM
> >To: Richardson, Bruce <bruce.richardson at intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch at intel.com>
> >Cc: dev at dpdk.org; honnappa.nagarahalli at dpdk.org; gavin.hu at arm.com; steve.capper at arm.com; ola.liljedahl at arm.com;
> >nd at arm.com; Honnappa Nagarahalli <honnappa.nagarahalli at arm.com>
> >Subject: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys
> >
> >Reader-writer concurrency issue, caused by moving the keys
> >to their alternative locations during key insert, is solved
> >by introducing a global counter(tbl_chng_cnt) indicating a
> >change in table.
> >
> >@@ -662,6 +679,20 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,
> > 		curr_bkt = curr_node->bkt;
> > 	}
> >
> >+	/* Inform the previous move. The current move need
> >+	 * not be informed now as the current bucket entry
> >+	 * is present in both primary and secondary.
> >+	 * Since there is one writer, load acquires on
> >+	 * tbl_chng_cnt are not required.
> >+	 */
> >+	__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.
> 
> >@@ -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?
> 
> >--- a/lib/librte_hash/rte_hash.h
> >+++ b/lib/librte_hash/rte_hash.h
> >@@ -156,7 +156,7 @@ rte_hash_count(const struct rte_hash *h);
> >  *   - -ENOSPC if there is no space in the hash for this key.
> >  */
> > int
> >-rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data);
> >+rte_hash_add_key_data(struct rte_hash *h, const void *key, void *data);
> >
> > /**
> >  * Add a key-value pair with a pre-computed hash value
> >@@ -180,7 +180,7 @@ rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data);
> >  *   - -ENOSPC if there is no space in the hash for this key.
> >  */
> > int32_t
> >-rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key,
> >+rte_hash_add_key_with_hash_data(struct rte_hash *h, const void *key,
> > 						hash_sig_t sig, void *data);
> >
> > /**
> >@@ -200,7 +200,7 @@ rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key,
> >  *     array of user data. This value is unique for this key.
> >  */
> > int32_t
> >-rte_hash_add_key(const struct rte_hash *h, const void *key);
> >+rte_hash_add_key(struct rte_hash *h, const void *key);
> >
> > /**
> >  * Add a key to an existing hash table.
> >@@ -222,7 +222,7 @@ rte_hash_add_key(const struct rte_hash *h, const void *key);
> >  *     array of user data. This value is unique for this key.
> >  */
> > int32_t
> >-rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
> >+rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig);
> >
> > /
> 
> I think the above changes will break ABI by changing the parameter type? Other people may know better on this.

Just removing a const should not change the ABI, I believe, since the const
is just advisory hint to the compiler. Actual parameter size and count
remains unchanged so I don't believe there is an issue. 
[ABI experts, please correct me if I'm wrong on this]

/Bruce