[dpdk-dev] [RFC 1/2] hash: add lock free support for extendable bucket

[Dharmik Thakkar]

+ Honnappa

Hi Yipeng,

Thank you for the review comments!


> On Mar 7, 2019, at 11:49 AM, Wang, Yipeng1 <yipeng1.wang at intel.com> wrote:
> 
> Thanks for this patch! Some initial comments inlined:
> 
>> -----Original Message-----
>> From: Dharmik Thakkar [mailto:dharmik.thakkar at arm.com]
>> Sent: Friday, March 1, 2019 4:24 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>; Mcnamara, John
>> <john.mcnamara at intel.com>; Kovacevic, Marko <marko.kovacevic at intel.com>
>> Cc: dev at dpdk.org; Dharmik Thakkar <dharmik.thakkar at arm.com>
>> Subject: [RFC 1/2] hash: add lock free support for extendable bucket
>> 
>> This patch enables lock-free read-write concurrency support for
>> extendable bucket feature.
>> 
>> Suggested-by: Honnappa Nagarahalli <honnappa.nagarahalli at arm.com>
>> Signed-off-by: Dharmik Thakkar <dharmik.thakkar at arm.com>
>> ---
>> doc/guides/prog_guide/hash_lib.rst |   3 +-
>> lib/librte_hash/rte_cuckoo_hash.c  | 150 +++++++++++++++++++----------
>> lib/librte_hash/rte_cuckoo_hash.h  |   8 ++
>> 3 files changed, 110 insertions(+), 51 deletions(-)
>> 
>> diff --git a/doc/guides/prog_guide/hash_lib.rst b/doc/guides/prog_guide/hash_lib.rst
>> index 85a6edfa8b16..b00446e949ba 100644
>> --- a/doc/guides/prog_guide/hash_lib.rst
>> +++ b/doc/guides/prog_guide/hash_lib.rst
>> @@ -108,8 +108,7 @@ Extendable Bucket Functionality support
>> An extra flag is used to enable this functionality (flag is not set by default). When the (RTE_HASH_EXTRA_FLAGS_EXT_TABLE) is set
>> and
>> in the very unlikely case due to excessive hash collisions that a key has failed to be inserted, the hash table bucket is extended with a
>> linked
>> list to insert these failed keys. This feature is important for the workloads (e.g. telco workloads) that need to insert up to 100% of the
>> -hash table size and can't tolerate any key insertion failure (even if very few). Currently the extendable bucket is not supported
>> -with the lock-free concurrency implementation (RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF).
>> +hash table size and can't tolerate any key insertion failure (even if very few).
>> 
>> 
>> Implementation Details (non Extendable Bucket Case)
>> diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
>> index c01489ba5193..54762533ce36 100644
>> --- a/lib/librte_hash/rte_cuckoo_hash.c
>> +++ b/lib/librte_hash/rte_cuckoo_hash.c
>> @@ -170,15 +170,6 @@ rte_hash_create(const struct rte_hash_parameters *params)
>> 		return NULL;
>> 	}
>> 
>> -	if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) &&
>> -	    (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)) {
>> -		rte_errno = EINVAL;
>> -		RTE_LOG(ERR, HASH, "rte_hash_create: extendable bucket "
>> -			"feature not supported with rw concurrency "
>> -			"lock free\n");
>> -		return NULL;
>> -	}
>> -
>> 	/* Check extra flags field to check extra options. */
>> 	if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT)
>> 		hw_trans_mem_support = 1;
>> @@ -1054,7 +1045,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
>> 			/* Check if slot is available */
>> 			if (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)) {
>> 				cur_bkt->sig_current[i] = short_sig;
>> -				cur_bkt->key_idx[i] = new_idx;
>> +				/* 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.
>> +				 */
>> +				__atomic_store_n(&cur_bkt->key_idx[i],
>> +						 new_idx,
>> +						 __ATOMIC_RELEASE);
>> 				__hash_rw_writer_unlock(h);
>> 				return new_idx - 1;
>> 			}
>> @@ -1072,10 +1071,23 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
>> 	bkt_id = (uint32_t)((uintptr_t)ext_bkt_id) - 1;
>> 	/* Use the first location of the new bucket */
>> 	(h->buckets_ext[bkt_id]).sig_current[0] = short_sig;
>> -	(h->buckets_ext[bkt_id]).key_idx[0] = new_idx;
>> +	/* 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.
>> +	 */
>> +	__atomic_store_n(&(h->buckets_ext[bkt_id]).key_idx[0],
>> +			 new_idx,
>> +			 __ATOMIC_RELEASE);
> [Wang, Yipeng] Since it has not been linked and later on the linking is protected by
> release, do we really need atomic store here?
Atomic store is used here to maintain the code consistency.
> 
>> 	/* Link the new bucket to sec bucket linked list */
>> 	last = rte_hash_get_last_bkt(sec_bkt);
>> -	last->next = &h->buckets_ext[bkt_id];
>> +	/* New bucket's memory stores (key as well as data)
>> +	 * should be complete before it is referenced
>> +	 */
>> +	__atomic_store_n(&last->next,
>> +			 &h->buckets_ext[bkt_id],
>> +			 __ATOMIC_RELEASE);
>> 	__hash_rw_writer_unlock(h);
>> 	return new_idx - 1;
>> 
>> @@ -1366,7 +1378,8 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
>> * empty slot.
>> */
>> static inline void
>> -__rte_hash_compact_ll(struct rte_hash_bucket *cur_bkt, int pos) {
>> +__rte_hash_compact_ll(const struct rte_hash *h,
>> +			struct rte_hash_bucket *cur_bkt, int pos) {
>> 	int i;
>> 	struct rte_hash_bucket *last_bkt;
>> 
>> @@ -1377,10 +1390,27 @@ __rte_hash_compact_ll(struct rte_hash_bucket *cur_bkt, int pos) {
>> 
>> 	for (i = RTE_HASH_BUCKET_ENTRIES - 1; i >= 0; i--) {
>> 		if (last_bkt->key_idx[i] != EMPTY_SLOT) {
>> -			cur_bkt->key_idx[pos] = last_bkt->key_idx[i];
>> 			cur_bkt->sig_current[pos] = last_bkt->sig_current[i];
>> +			__atomic_store_n(&cur_bkt->key_idx[pos],
>> +					 last_bkt->key_idx[i],
>> +					 __ATOMIC_RELEASE);
>> +			if (h->readwrite_concur_lf_support) {
>> +				/* Inform the readers that the table has changed
>> +				 * 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);
>> +			}
>> 			last_bkt->sig_current[i] = NULL_SIGNATURE;
>> -			last_bkt->key_idx[i] = EMPTY_SLOT;
>> +			__atomic_store_n(&last_bkt->key_idx[i],
>> +					 EMPTY_SLOT,
>> +					 __ATOMIC_RELEASE);
>> 			return;
>> 		}
>> 	}
>> @@ -1449,7 +1479,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
>> 	/* look for key in primary bucket */
>> 	ret = search_and_remove(h, key, prim_bkt, short_sig, &pos);
>> 	if (ret != -1) {
>> -		__rte_hash_compact_ll(prim_bkt, pos);
>> +		__rte_hash_compact_ll(h, prim_bkt, pos);
>> 		last_bkt = prim_bkt->next;
>> 		prev_bkt = prim_bkt;
>> 		goto return_bkt;
>> @@ -1461,7 +1491,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
>> 	FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
>> 		ret = search_and_remove(h, key, cur_bkt, short_sig, &pos);
>> 		if (ret != -1) {
>> -			__rte_hash_compact_ll(cur_bkt, pos);
>> +			__rte_hash_compact_ll(h, cur_bkt, pos);
>> 			last_bkt = sec_bkt->next;
>> 			prev_bkt = sec_bkt;
>> 			goto return_bkt;
>> @@ -1488,11 +1518,21 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
>> 	}
>> 	/* found empty bucket and recycle */
>> 	if (i == RTE_HASH_BUCKET_ENTRIES) {
>> -		prev_bkt->next = last_bkt->next = NULL;
>> +		__atomic_store_n(&prev_bkt->next,
>> +				 NULL,
>> +				 __ATOMIC_RELEASE);
>> 		uint32_t index = last_bkt - h->buckets_ext + 1;
>> -		rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index);
>> -	}
>> +		if (!h->no_free_on_del)
>> +			rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index);
>> +		else {
>> +			struct rte_hash_key *key_slot =
>> +				(struct rte_hash_key *)(
>> +				(char *)h->key_store +
>> +				ret * h->key_entry_size);
>> +			key_slot->ext_bkt_to_free = index;
> [Wang, Yipeng] Is there chance that a key_slot may already have one previous ext_bkt
> and now got overwritten, so that the previous one gone forever?
No, it is not possible. Since, the index is being stored in a key_slot which is associated with a deleted key.
>> 
>> +		}
>> +	}
>> 	__hash_rw_writer_unlock(h);
>> 	return ret;
>> }
>> @@ -1567,6 +1607,14 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
>> 				(void *)((uintptr_t)position));
>> 	}
>> 
>> +	const struct rte_hash_key *key_slot = (const struct rte_hash_key *)(
>> +						(const char *)h->key_store +
>> +						position * h->key_entry_size);
>> +	uint32_t index = key_slot->ext_bkt_to_free;
>> +	if (!index)
>> +		/* Recycle empty ext bkt to free list. */
>> +		rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index);
>> +
>> 	return 0;
>> }
>> 
>> @@ -1855,6 +1903,9 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
>> 		rte_prefetch0(secondary_bkt[i]);
>> 	}
>> 
>> +	for (i = 0; i < num_keys; i++)
>> +		positions[i] = -ENOENT;
> [Wang, Yipeng] So is this for performance reason?
Resetting positions[] on each iteration of do…while() require ‘hits’ to be reset as well, which causes performance hit.
>> +
>> 	do {
>> 		/* Load the table change counter before the lookup
>> 		 * starts. Acquire semantics will make sure that
>> @@ -1899,7 +1950,6 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
>> 
>> 		/* Compare keys, first hits in primary first */
>> 		for (i = 0; i < num_keys; i++) {
>> -			positions[i] = -ENOENT;
>> 			while (prim_hitmask[i]) {
>> 				uint32_t hit_index =
>> 						__builtin_ctzl(prim_hitmask[i])
>> @@ -1972,6 +2022,36 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
>> 			continue;
>> 		}
>> 
>> +
>> +		/* all found, do not need to go through ext bkt */
>> +		if (hits == ((1ULL << num_keys) - 1)) {
>> +			if (hit_mask != NULL)
>> +				*hit_mask = hits;
> 
> [Wang, Yipeng] I think you need to check the version counter before return,
> and how about the fence?
If all the keys are found, there is no need to check the counter.
>> +			return;
>> +		}
>> +		/* need to check ext buckets for match */
>> +		if (h->ext_table_support) {
>> +			for (i = 0; i < num_keys; i++) {
>> +				if ((hits & (1ULL << i)) != 0)
>> +					continue;
>> +				next_bkt = secondary_bkt[i]->next;
>> +				FOR_EACH_BUCKET(cur_bkt, next_bkt) {
>> +					if (data != NULL)
>> +						ret = search_one_bucket_lf(h,
>> +							keys[i], sig[i],
>> +							&data[i], cur_bkt);
>> +					else
>> +						ret = search_one_bucket_lf(h,
>> +								keys[i], sig[i],
>> +								NULL, cur_bkt);
>> +					if (ret != -1) {
>> +						positions[i] = ret;
>> +						hits |= 1ULL << i;
>> +						break;
>> +					}
>> +				}
>> +			}
>> +		}
>> 		/* The loads of sig_current in compare_signatures
>> 		 * should not move below the load from tbl_chng_cnt.
>> 		 */
>> @@ -1988,34 +2068,6 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
>> 					__ATOMIC_ACQUIRE);
>> 	} while (cnt_b != cnt_a);
>> 
>> -	/* all found, do not need to go through ext bkt */
>> -	if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) {
>> -		if (hit_mask != NULL)
>> -			*hit_mask = hits;
>> -		__hash_rw_reader_unlock(h);
>> -		return;
>> -	}
>> -
>> -	/* need to check ext buckets for match */
>> -	for (i = 0; i < num_keys; i++) {
>> -		if ((hits & (1ULL << i)) != 0)
>> -			continue;
>> -		next_bkt = secondary_bkt[i]->next;
>> -		FOR_EACH_BUCKET(cur_bkt, next_bkt) {
>> -			if (data != NULL)
>> -				ret = search_one_bucket_lf(h, keys[i],
>> -						sig[i], &data[i], cur_bkt);
>> -			else
>> -				ret = search_one_bucket_lf(h, keys[i],
>> -						sig[i], NULL, cur_bkt);
>> -			if (ret != -1) {
>> -				positions[i] = ret;
>> -				hits |= 1ULL << i;
>> -				break;
>> -			}
>> -		}
>> -	}
>> -
>> 	if (hit_mask != NULL)
>> 		*hit_mask = hits;
>> }
>> diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h
>> index eacdaa8d4684..062cc2dd0296 100644
>> --- a/lib/librte_hash/rte_cuckoo_hash.h
>> +++ b/lib/librte_hash/rte_cuckoo_hash.h
>> @@ -129,6 +129,14 @@ struct lcore_cache {
>> 
>> /* Structure that stores key-value pair */
>> struct rte_hash_key {
>> +	/* Stores index of an empty ext bkt to be recycled on calling
>> +	 * rte_hash_del_xxx APIs. When lock free read-wrie concurrency is
> [Wang, Yipeng] typo
Will update it in the next version.
>> +	 * enabled, an empty ext bkt cannot be put into free list immediately
>> +	 * (as readers might be using it still). Hence freeing of the ext bkt
>> +	 * is piggy-backed to freeing of the key index.
>> +	 */
> [Wang, Yipeng] I am thinking if this breaks the "guarantee" provided by ext table, Since
> a whole bucket could not be reused if one key not freed. Is there any fundamental issue with
> a new API to recycle ext bucket or you just do not want to add a new API?
With lock-free feature, ‘delete’ becomes a two step process of ‘delete’ and ‘free’. In other words,
it can be viewed by the applications as a 'prolonged delete’. I’m not sure how adding a new API
to recycle ext bucket will help solving the issue.
>> +	uint32_t ext_bkt_to_free;
>> +
>> 	union {
>> 		uintptr_t idata;
>> 		void *pdata;
>> --
>> 2.17.1