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

[Wang, Yipeng1]

Thanks for the patch! 

Comments inlined:

>-----Original Message-----
>From: Dharmik Thakkar [mailto:dharmik.thakkar at arm.com]
>Sent: Wednesday, March 20, 2019 3: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>; 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: [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 at arm.com>
>Signed-off-by: Dharmik Thakkar <dharmik.thakkar at arm.com>
>Reviewed-by: Ruifeng Wang <ruifeng.wang at arm.com>
>Reviewed-by: Gavin Hu <gavin.hu at arm.com>
>Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli at 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.
>
>
>@@ -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.
>+				__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)
>+		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();