Re: [PATCH 1/2] hash: add lock free support for extendable bucket

[Dharmik Thakkar <Dharmik.Thakkar@arm.com>]

+Honnappa

Hi Yipeng,

Thank you for reviewing!

> On Mar 22, 2019, at 6:48 PM, Wang, Yipeng1 <yipeng1.wang@intel.com> wrote:
> 
> Thanks for the patch! 
> 
> Comments inlined:
> 
>> -----Original Message-----
>> From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
>> Sent: Wednesday, March 20, 2019 3:35 PM
>> To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; Richardson, Bruce
>> <bruce.richardson@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>; Mcnamara, John
>> <john.mcnamara@intel.com>; Kovacevic, Marko <marko.kovacevic@intel.com>
>> Cc: dev@dpdk.org; Dharmik Thakkar <dharmik.thakkar@arm.com>
>> Subject: [PATCH 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@arm.com>
>> Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
>> Reviewed-by: Ruifeng Wang <ruifeng.wang@arm.com>
>> Reviewed-by: Gavin Hu <gavin.hu@arm.com>
>> Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
>> ---
>> doc/guides/prog_guide/hash_lib.rst |   3 +-
>> lib/librte_hash/rte_cuckoo_hash.c  | 163 ++++++++++++++++++++---------
>> lib/librte_hash/rte_cuckoo_hash.h  |   7 ++
>> 3 files changed, 121 insertions(+), 52 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).
> [Wang, Yipeng] I am thinking maybe make it a bit more clear here by adding something like:
> Please note that with the lock-free flag enabled, users need to promptly free the deleted keys, to maintain the 100% capacity guarantee.
> 
> I want to add this because of the piggy-back mechanism, one un-recycled key with an un-recycled ext bucket may actually makes in total
> of 9 entries unavailable (8 entries in the ext bucket). So it would be useful to remind the user here.
All right. I will add it.
>> 
>> 
>> @@ -1054,7 +1059,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.
>> +				 */
> [Wang, Yipeng]  My understanding is this atomic store is to prevent the signature store leaking after the key_idx store.
> But the comment does not exactly describe this reason.
I will update the comment.
>> +				__atomic_store_n(&cur_bkt->key_idx[i],
>> +						 new_idx,
>> +						 __ATOMIC_RELEASE);
>> 				__hash_rw_writer_unlock(h);
>> 				return new_idx - 1;
>> 			}
>> @@ -1545,6 +1597,14 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
>> 	/* Out of bounds */
>> 	if (position >= total_entries)
>> 		return -EINVAL;
>> +	if (h->ext_table_support) {
>> +		uint32_t index = h->ext_bkt_to_free[position];
> [Wang, Yipeng] I think user can theoretically set  RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL to be 1
> But LF flag to be 0. I think here you assume this function only called when LF flag is 1. You may need to
> Add another condition e.g. if(h->ext_table_support && h->readwrite_concur_lf_support)
Correct. I will update it.
>> +		if (index) {
>> +			/* Recycle empty ext bkt to free list. */
>> +			rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index);
>> +			h->ext_bkt_to_free[position] = 0;
>> +		}
>> +	}
>> 
>> 	if (h->use_local_cache) {
>> 		lcore_id = rte_lcore_id();