[dpdk-dev] [PATCH 0/2] hash: fix bugs in 'free key with position'

[dpdk-dev] [PATCH 0/2] hash: fix bugs in 'free key with position'

[Dharmik Thakkar]

This patch series solves 2 bugs reported on Bugzilla (bug-261) within
the function rte_hash_free_key_with_postion(). It also adds a test case
to catch similar bugs in the future.

https://bugs.dpdk.org/show_bug.cgi?id=261

Dharmik Thakkar (2):
  hash: fix bugs in 'free key with position'
  test/hash: add test for 'free key with position'

 app/test/test_hash.c              | 83 +++++++++++++++++++++++++++++++
 lib/librte_hash/rte_cuckoo_hash.c | 14 ++++--
 2 files changed, 92 insertions(+), 5 deletions(-)

-- 
2.17.1

[dpdk-dev] [PATCH 1/2] hash: fix bugs in 'free key with position'

[Dharmik Thakkar]

This patch fixes 2 bugs-
1] Incorrect position returned to the free slots.
2] Incorrect computation of total_entries

Bugzilla ID: 261
Fixes: 9d033dac7d7c ("hash: support no free on delete")
Cc: honnappa.nagarahalli@arm.com
Cc: stable@dpdk.org

Reported-by: Linfan <zhongdahulinfan@163.com>
Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 lib/librte_hash/rte_cuckoo_hash.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 261267b7fd3d..590895d72062 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1587,14 +1587,18 @@ int __rte_experimental
 rte_hash_free_key_with_position(const struct rte_hash *h,
 				const int32_t position)
 {
-	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
+	/*  Key index where key is stored, adding the first dummy index*/
+	uint32_t key_idx = position + 1;
+
+	RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL);
 
 	unsigned int lcore_id, n_slots;
 	struct lcore_cache *cached_free_slots;
-	const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
+	const uint32_t total_entries = h->use_local_cache ?
+		h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1 : h->entries + 1;
 
 	/* Out of bounds */
-	if (position >= total_entries)
+	if (key_idx >= total_entries)
 		return -EINVAL;
 	if (h->ext_table_support && h->readwrite_concur_lf_support) {
 		uint32_t index = h->ext_bkt_to_free[position];
@@ -1619,11 +1623,11 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
 		}
 		/* Put index of new free slot in cache. */
 		cached_free_slots->objs[cached_free_slots->len] =
-					(void *)((uintptr_t)position);
+					(void *)((uintptr_t)key_idx);
 		cached_free_slots->len++;
 	} else {
 		rte_ring_sp_enqueue(h->free_slots,
-				(void *)((uintptr_t)position));
+				(void *)((uintptr_t)key_idx));
 	}
 
 	return 0;
-- 
2.17.1

[dpdk-dev] [PATCH 2/2] test/hash: add test for 'free key with position'

[Dharmik Thakkar]

This patch adds a unit test for rte_hash_free_key_with_position().

Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 app/test/test_hash.c | 83 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)

diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 390fbef87f42..a6949f2579a2 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -481,6 +481,87 @@ static int test_add_update_delete_free(void)
 	return 0;
 }
 
+/*
+ * Sequence of operations for a single key with 'rw concurrency lock free' set:
+ *	- add
+ *	- delete: hit
+ *	- free: hit
+ * Repeat the test case when 'multi writer add' is enabled.
+ *	- add
+ *	- delete: hit
+ *	- free: hit
+ */
+static int test_add_delete_free_lf(void)
+{
+#define LCORE_CACHE_SIZE	64
+	struct rte_hash *handle;
+	hash_sig_t hash_value;
+	int pos, expectedPos, delPos;
+	uint8_t extra_flag;
+	uint32_t i, ip_src;
+
+	extra_flag = ut_params.extra_flag;
+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+	ut_params.extra_flag = extra_flag;
+
+	for (i = 0; i < ut_params.entries + 1; i++) {
+		hash_value = rte_hash_hash(handle, &keys[0]);
+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Add", &keys[0], pos);
+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
+		expectedPos = pos;
+
+		pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Del", &keys[0], pos);
+		RETURN_IF_ERROR(pos != expectedPos,
+				"failed to delete key (pos=%d)", pos);
+		delPos = pos;
+
+		pos = rte_hash_free_key_with_position(handle, delPos);
+		print_key_info("Free", &keys[0], delPos);
+		RETURN_IF_ERROR(pos != 0,
+				"failed to free key (pos=%d)", delPos);
+	}
+
+	rte_hash_free(handle);
+
+	extra_flag = ut_params.extra_flag;
+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF |
+				RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD;
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+	ut_params.extra_flag = extra_flag;
+
+	ip_src = keys[0].ip_src;
+	for (i = 0; i < ut_params.entries + (RTE_MAX_LCORE - 1) *
+					(LCORE_CACHE_SIZE - 1) + 1; i++) {
+		keys[0].ip_src++;
+		hash_value = rte_hash_hash(handle, &keys[0]);
+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Add", &keys[0], pos);
+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
+		expectedPos = pos;
+
+		pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Del", &keys[0], pos);
+		RETURN_IF_ERROR(pos != expectedPos,
+			"failed to delete key (pos=%d)", pos);
+		delPos = pos;
+
+		pos = rte_hash_free_key_with_position(handle, delPos);
+		print_key_info("Free", &keys[0], delPos);
+		RETURN_IF_ERROR(pos != 0,
+			"failed to free key (pos=%d)", delPos);
+	}
+	keys[0].ip_src = ip_src;
+
+	rte_hash_free(handle);
+
+	return 0;
+}
+
 /*
  * Sequence of operations for retrieving a key with its position
  *
@@ -1743,6 +1824,8 @@ test_hash(void)
 		return -1;
 	if (test_add_update_delete_free() < 0)
 		return -1;
+	if (test_add_delete_free_lf() < 0)
+		return -1;
 	if (test_five_keys() < 0)
 		return -1;
 	if (test_full_bucket() < 0)
-- 
2.17.1

Re: [dpdk-dev] [PATCH 2/2] test/hash: add test for 'free key with position'

[Wang, Yipeng1]

Hi, thanks for the patch!
Reply inlined:

>-----Original Message-----
>From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
>Sent: Wednesday, May 8, 2019 9:51 AM
>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>
>Cc: dev@dpdk.org; honnappa.nagarahalli@arm.com; zhongdahulinfan@163.com; Dharmik Thakkar <dharmik.thakkar@arm.com>
>Subject: [PATCH 2/2] test/hash: add test for 'free key with position'
>
>This patch adds a unit test for rte_hash_free_key_with_position().
>
>Suggested-by: Linfan <zhongdahulinfan@163.com>
>Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
>---
> app/test/test_hash.c | 83 ++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 83 insertions(+)
>
>diff --git a/app/test/test_hash.c b/app/test/test_hash.c
>index 390fbef87f42..a6949f2579a2 100644
>--- a/app/test/test_hash.c
>+++ b/app/test/test_hash.c
>@@ -481,6 +481,87 @@ static int test_add_update_delete_free(void)
> 	return 0;
> }
>
>+/*
>+ * Sequence of operations for a single key with 'rw concurrency lock free' set:
>+ *	- add
>+ *	- delete: hit
>+ *	- free: hit
>+ * Repeat the test case when 'multi writer add' is enabled.
>+ *	- add
>+ *	- delete: hit
>+ *	- free: hit
>+ */
>+static int test_add_delete_free_lf(void)
>+{
>+#define LCORE_CACHE_SIZE	64
[Wang, Yipeng]  We could say this should match the #define LCORE_CACHE_SIZE value in rte_cuckoo_hash.h
I also found the #define BUCKET_ENTRIES 4 in this file without comment. I think it should match #define RTE_HASH_BUCKET_ENTRIES
Which is supposed to be 8? If so please add a commit for bug fix.

>+	struct rte_hash *handle;
>+	hash_sig_t hash_value;
>+	int pos, expectedPos, delPos;
>+	uint8_t extra_flag;
>+	uint32_t i, ip_src;
>+
>+	extra_flag = ut_params.extra_flag;
>+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
>+	handle = rte_hash_create(&ut_params);
>+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
>+	ut_params.extra_flag = extra_flag;
>+
 [Wang, Yipeng]  Here we could say:" The number of iterations is at least the same as the number of slots rte_hash allocates internally. This is to
Reveal potential issues of not freeing keys successfully."
Same for the other loop.

>+	for (i = 0; i < ut_params.entries + 1; i++) {
>+		hash_value = rte_hash_hash(handle, &keys[0]);
>+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
>+		print_key_info("Add", &keys[0], pos);
>+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
..

Thanks
Yipeng

Re: [dpdk-dev] [PATCH 2/2] test/hash: add test for 'free key with position'

[Dharmik Thakkar]

> On May 8, 2019, at 3:11 PM, Wang, Yipeng1 <yipeng1.wang@intel.com> wrote:
> 
> Hi, thanks for the patch!
> Reply inlined:
Hi Yipeng,
Thank you for the review!
> 
>> -----Original Message-----
>> From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
>> Sent: Wednesday, May 8, 2019 9:51 AM
>> 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>
>> Cc: dev@dpdk.org; honnappa.nagarahalli@arm.com; zhongdahulinfan@163.com; Dharmik Thakkar <dharmik.thakkar@arm.com>
>> Subject: [PATCH 2/2] test/hash: add test for 'free key with position'
>> 
>> This patch adds a unit test for rte_hash_free_key_with_position().
>> 
>> Suggested-by: Linfan <zhongdahulinfan@163.com>
>> Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
>> ---
>> app/test/test_hash.c | 83 ++++++++++++++++++++++++++++++++++++++++++++
>> 1 file changed, 83 insertions(+)
>> 
>> diff --git a/app/test/test_hash.c b/app/test/test_hash.c
>> index 390fbef87f42..a6949f2579a2 100644
>> --- a/app/test/test_hash.c
>> +++ b/app/test/test_hash.c
>> @@ -481,6 +481,87 @@ static int test_add_update_delete_free(void)
>> 	return 0;
>> }
>> 
>> +/*
>> + * Sequence of operations for a single key with 'rw concurrency lock free' set:
>> + *	- add
>> + *	- delete: hit
>> + *	- free: hit
>> + * Repeat the test case when 'multi writer add' is enabled.
>> + *	- add
>> + *	- delete: hit
>> + *	- free: hit
>> + */
>> +static int test_add_delete_free_lf(void)
>> +{
>> +#define LCORE_CACHE_SIZE	64
> [Wang, Yipeng]  We could say this should match the #define LCORE_CACHE_SIZE value in rte_cuckoo_hash.h
Sure, will add in the next version.
> I also found the #define BUCKET_ENTRIES 4 in this file without comment. I think it should match #define RTE_HASH_BUCKET_ENTRIES
> Which is supposed to be 8? If so please add a commit for bug fix.
I think this is done to test with bad parameters.
> 
>> +	struct rte_hash *handle;
>> +	hash_sig_t hash_value;
>> +	int pos, expectedPos, delPos;
>> +	uint8_t extra_flag;
>> +	uint32_t i, ip_src;
>> +
>> +	extra_flag = ut_params.extra_flag;
>> +	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
>> +	handle = rte_hash_create(&ut_params);
>> +	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
>> +	ut_params.extra_flag = extra_flag;
>> +
> [Wang, Yipeng]  Here we could say:" The number of iterations is at least the same as the number of slots rte_hash allocates internally. This is to
> Reveal potential issues of not freeing keys successfully."
> Same for the other loop.
Will add in the next version.
> 
>> +	for (i = 0; i < ut_params.entries + 1; i++) {
>> +		hash_value = rte_hash_hash(handle, &keys[0]);
>> +		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
>> +		print_key_info("Add", &keys[0], pos);
>> +		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
> ..
> 
> Thanks
> Yipeng

[dpdk-dev] [PATCH v2 0/2] hash: fix bugs in 'free key with position'

[Dharmik Thakkar]

This patch series solves 2 bugs reported on Bugzilla (bug-261) within
the function rte_hash_free_key_with_postion(). It also adds a test case
 to catch similar bugs in the future.

https://bugs.dpdk.org/show_bug.cgi?id=261
---
v2:
 * Add comments in test_hash.c (Yipeng)
 * Resolve checkpatch warning

Dharmik Thakkar (2):
  hash: fix bugs in 'free key with position'
  test/hash: add test for 'free key with position'

 app/test/test_hash.c              | 94 +++++++++++++++++++++++++++++++
 lib/librte_hash/rte_cuckoo_hash.c | 15 +++--
 2 files changed, 104 insertions(+), 5 deletions(-)

-- 
2.17.1

[dpdk-dev] [PATCH v2 1/2] hash: fix bugs in 'free key with position'

[Dharmik Thakkar]

This patch fixes 2 bugs-
1] Incorrect position returned to the free slots.
2] Incorrect computation of total_entries

Bugzilla ID: 261
Fixes: 9d033dac7d7c ("hash: support no free on delete")
Cc: honnappa.nagarahalli@arm.com
Cc: stable@dpdk.org

Reported-by: Linfan <zhongdahulinfan@163.com>
Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 lib/librte_hash/rte_cuckoo_hash.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 261267b7fd3d..ed2e96b6f178 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1587,14 +1587,19 @@ int __rte_experimental
 rte_hash_free_key_with_position(const struct rte_hash *h,
 				const int32_t position)
 {
-	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
+	/*  Key index where key is stored, adding the first dummy index*/
+	uint32_t key_idx = position + 1;
+
+	RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL);
 
 	unsigned int lcore_id, n_slots;
 	struct lcore_cache *cached_free_slots;
-	const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
+	const uint32_t total_entries = h->use_local_cache ?
+		h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1
+							: h->entries + 1;
 
 	/* Out of bounds */
-	if (position >= total_entries)
+	if (key_idx >= total_entries)
 		return -EINVAL;
 	if (h->ext_table_support && h->readwrite_concur_lf_support) {
 		uint32_t index = h->ext_bkt_to_free[position];
@@ -1619,11 +1624,11 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
 		}
 		/* Put index of new free slot in cache. */
 		cached_free_slots->objs[cached_free_slots->len] =
-					(void *)((uintptr_t)position);
+					(void *)((uintptr_t)key_idx);
 		cached_free_slots->len++;
 	} else {
 		rte_ring_sp_enqueue(h->free_slots,
-				(void *)((uintptr_t)position));
+				(void *)((uintptr_t)key_idx));
 	}
 
 	return 0;
-- 
2.17.1

Re: [dpdk-dev] [dpdk-stable] [PATCH v2 1/2] hash: fix bugs in 'free key with position'

[Thomas Monjalon]

09/05/2019 00:59, Dharmik Thakkar:
> This patch fixes 2 bugs-
> 1] Incorrect position returned to the free slots.
> 2] Incorrect computation of total_entries

Is it possible to split in 2 patches?

How critical is this bug? It looks old.
I'm afraid it will miss 19.05.

Re: [dpdk-dev] [dpdk-stable] [PATCH v2 1/2] hash: fix bugs in 'free key with position'

[Thomas Monjalon]

09/05/2019 12:40, 胡林帆:
> This bug makes 'lock free reader/writer concurrency hash' unusable.
> There are two reasons:
> 1] memory leak because we cannot free keys which indexes greater than the number of total entries
> 
> 2] the ring of free_slots may have unexpected key conflict with in use one
> 
> The patch fixes these 2 issues, both of which are in the same API:
> 
> int __rte_experimental
> rte_hash_free_key_with_position(const struct rte_hash *h,
>     const int32_t position)
> 
> I don't think it is necessarily to split in 2 patches.

Sorry for insisting, I think it is necessary to split in 2 patches
with better explanations in the commit logs.
Then we'll need approval from the maintainers.

PS1: Please provide your full name in english alphabet
PS2: Please do not top-post


> At 2019-05-09 16:29:56, "Thomas Monjalon" <thomas@monjalon.net> wrote:
> >09/05/2019 00:59, Dharmik Thakkar:
> >> This patch fixes 2 bugs-
> >> 1] Incorrect position returned to the free slots.
> >> 2] Incorrect computation of total_entries
> >
> >Is it possible to split in 2 patches?
> >
> >How critical is this bug? It looks old.
> >I'm afraid it will miss 19.05.

Re: [dpdk-dev] [dpdk-stable] [PATCH v2 1/2] hash: fix bugs in 'free key with position'

[Dharmik Thakkar]

> On May 9, 2019, at 6:25 AM, Thomas Monjalon <thomas@monjalon.net> wrote:
>
> 09/05/2019 12:40, 胡林帆:
>> This bug makes 'lock free reader/writer concurrency hash' unusable.
>> There are two reasons:
>> 1] memory leak because we cannot free keys which indexes greater than the number of total entries
>>
>> 2] the ring of free_slots may have unexpected key conflict with in use one
>>
>> The patch fixes these 2 issues, both of which are in the same API:
>>
>> int __rte_experimental
>> rte_hash_free_key_with_position(const struct rte_hash *h,
>>    const int32_t position)
>>
>> I don't think it is necessarily to split in 2 patches.
>
> Sorry for insisting, I think it is necessary to split in 2 patches
> with better explanations in the commit logs.
I will update the patch. Thanks!
> Then we'll need approval from the maintainers.
>
> PS1: Please provide your full name in english alphabet
> PS2: Please do not top-post
>
>
>> At 2019-05-09 16:29:56, "Thomas Monjalon" <thomas@monjalon.net> wrote:
>>> 09/05/2019 00:59, Dharmik Thakkar:
>>>> This patch fixes 2 bugs-
>>>> 1] Incorrect position returned to the free slots.
>>>> 2] Incorrect computation of total_entries
>>>
>>> Is it possible to split in 2 patches?
>>>
>>> How critical is this bug? It looks old.
>>> I'm afraid it will miss 19.05.
>
>
>

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

[dpdk-dev] [PATCH v2 2/2] test/hash: add test for 'free key with position'

[Dharmik Thakkar]

This patch adds a unit test for rte_hash_free_key_with_position().

Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 app/test/test_hash.c | 94 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)

diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 390fbef87f42..e162592965ce 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -481,6 +481,98 @@ static int test_add_update_delete_free(void)
 	return 0;
 }
 
+/*
+ * Sequence of operations for a single key with 'rw concurrency lock free' set:
+ *	- add
+ *	- delete: hit
+ *	- free: hit
+ * Repeat the test case when 'multi writer add' is enabled.
+ *	- add
+ *	- delete: hit
+ *	- free: hit
+ */
+static int test_add_delete_free_lf(void)
+{
+/* Should match the #define LCORE_CACHE_SIZE value in rte_cuckoo_hash.h */
+#define LCORE_CACHE_SIZE	64
+	struct rte_hash *handle;
+	hash_sig_t hash_value;
+	int pos, expectedPos, delPos;
+	uint8_t extra_flag;
+	uint32_t i, ip_src;
+
+	extra_flag = ut_params.extra_flag;
+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+	ut_params.extra_flag = extra_flag;
+
+	/*
+	 * The number of iterations is at least the same as the number of slots
+	 * rte_hash allocates internally. This is to reveal potential issues of
+	 * not freeing keys successfully.
+	 */
+	for (i = 0; i < ut_params.entries + 1; i++) {
+		hash_value = rte_hash_hash(handle, &keys[0]);
+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Add", &keys[0], pos);
+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
+		expectedPos = pos;
+
+		pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Del", &keys[0], pos);
+		RETURN_IF_ERROR(pos != expectedPos,
+				"failed to delete key (pos=%d)", pos);
+		delPos = pos;
+
+		pos = rte_hash_free_key_with_position(handle, delPos);
+		print_key_info("Free", &keys[0], delPos);
+		RETURN_IF_ERROR(pos != 0,
+				"failed to free key (pos=%d)", delPos);
+	}
+
+	rte_hash_free(handle);
+
+	extra_flag = ut_params.extra_flag;
+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF |
+				RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD;
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+	ut_params.extra_flag = extra_flag;
+
+	ip_src = keys[0].ip_src;
+	/*
+	 * The number of iterations is at least the same as the number of slots
+	 * rte_hash allocates internally. This is to reveal potential issues of
+	 * not freeing keys successfully.
+	 */
+	for (i = 0; i < ut_params.entries + (RTE_MAX_LCORE - 1) *
+					(LCORE_CACHE_SIZE - 1) + 1; i++) {
+		keys[0].ip_src++;
+		hash_value = rte_hash_hash(handle, &keys[0]);
+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Add", &keys[0], pos);
+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
+		expectedPos = pos;
+
+		pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Del", &keys[0], pos);
+		RETURN_IF_ERROR(pos != expectedPos,
+			"failed to delete key (pos=%d)", pos);
+		delPos = pos;
+
+		pos = rte_hash_free_key_with_position(handle, delPos);
+		print_key_info("Free", &keys[0], delPos);
+		RETURN_IF_ERROR(pos != 0,
+			"failed to free key (pos=%d)", delPos);
+	}
+	keys[0].ip_src = ip_src;
+
+	rte_hash_free(handle);
+
+	return 0;
+}
+
 /*
  * Sequence of operations for retrieving a key with its position
  *
@@ -1743,6 +1835,8 @@ test_hash(void)
 		return -1;
 	if (test_add_update_delete_free() < 0)
 		return -1;
+	if (test_add_delete_free_lf() < 0)
+		return -1;
 	if (test_five_keys() < 0)
 		return -1;
 	if (test_full_bucket() < 0)
-- 
2.17.1

[dpdk-dev] [PATCH v3 0/3] hash: fix bugs in 'free key with position'

[Dharmik Thakkar]

This patch series solves 2 bugs reported on Bugzilla (bug-261) within
the function rte_hash_free_key_with_postion(). It also adds a test case
 to catch similar bugs in the future.

https://bugs.dpdk.org/show_bug.cgi?id=261
---
v3:
 * Split the patch and update commit logs (Thomas)
v2:
 * Add comments in test_hash.c (Yipeng)
 * Resolve checkpatch warning

Dharmik Thakkar (3):
  hash: fix position bug in 'free key with position'
  hash: fix total entries in free key with position
  test/hash: add test for 'free key with position'

 app/test/test_hash.c              | 94 +++++++++++++++++++++++++++++++
 lib/librte_hash/rte_cuckoo_hash.c | 15 +++--
 2 files changed, 104 insertions(+), 5 deletions(-)

-- 
2.17.1

[dpdk-dev] [PATCH v3 1/3] hash: fix position bug in 'free key with position'

[Dharmik Thakkar]

Currently, in rte_hash_free_key_with_position(), the position returned
to the ring of free_slots leads to an unexpected conflict with a key
already in use.

This patch fixes incorrect position returned to the ring of free_slots.

Bugzilla ID: 261
Fixes: 9d033dac7d7c ("hash: support no free on delete")
Cc: honnappa.nagarahalli@arm.com
Cc: stable@dpdk.org

Reported-by: Linfan <zhongdahulinfan@163.com>
Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 lib/librte_hash/rte_cuckoo_hash.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 261267b7fd3d..8646ca52e60b 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1587,14 +1587,17 @@ int __rte_experimental
 rte_hash_free_key_with_position(const struct rte_hash *h,
 				const int32_t position)
 {
-	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
+	/*  Key index where key is stored, adding the first dummy index*/
+	uint32_t key_idx = position + 1;
+
+	RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL);
 
 	unsigned int lcore_id, n_slots;
 	struct lcore_cache *cached_free_slots;
 	const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
 
 	/* Out of bounds */
-	if (position >= total_entries)
+	if (key_idx >= total_entries)
 		return -EINVAL;
 	if (h->ext_table_support && h->readwrite_concur_lf_support) {
 		uint32_t index = h->ext_bkt_to_free[position];
@@ -1619,11 +1622,11 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
 		}
 		/* Put index of new free slot in cache. */
 		cached_free_slots->objs[cached_free_slots->len] =
-					(void *)((uintptr_t)position);
+					(void *)((uintptr_t)key_idx);
 		cached_free_slots->len++;
 	} else {
 		rte_ring_sp_enqueue(h->free_slots,
-				(void *)((uintptr_t)position));
+				(void *)((uintptr_t)key_idx));
 	}
 
 	return 0;
-- 
2.17.1

Re: [dpdk-dev] [PATCH v3 1/3] hash: fix position bug in 'free key with position'

[Wang, Yipeng1]

> -----Original Message-----
> From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
> Sent: Thursday, May 9, 2019 6:39 AM
> 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>
> Cc: dev@dpdk.org; honnappa.nagarahalli@arm.com;
> zhongdahulinfan@163.com; Dharmik Thakkar <dharmik.thakkar@arm.com>;
> stable@dpdk.org
> Subject: [PATCH v3 1/3] hash: fix position bug in 'free key with position'
> 
> Currently, in rte_hash_free_key_with_position(), the position returned to the
> ring of free_slots leads to an unexpected conflict with a key already in use.
> 
> This patch fixes incorrect position returned to the ring of free_slots.
> 
> Bugzilla ID: 261
> Fixes: 9d033dac7d7c ("hash: support no free on delete")
> Cc: honnappa.nagarahalli@arm.com
> Cc: stable@dpdk.org
> 
> Reported-by: Linfan <zhongdahulinfan@163.com>
> Suggested-by: Linfan <zhongdahulinfan@163.com>
> Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
> ---
>  lib/librte_hash/rte_cuckoo_hash.c | 11 +++++++----
>  1 file changed, 7 insertions(+), 4 deletions(-)
> 
> diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> b/lib/librte_hash/rte_cuckoo_hash.c
> index 261267b7fd3d..8646ca52e60b 100644
> --- a/lib/librte_hash/rte_cuckoo_hash.c
> +++ b/lib/librte_hash/rte_cuckoo_hash.c
> @@ -1587,14 +1587,17 @@ int __rte_experimental
> rte_hash_free_key_with_position(const struct rte_hash *h,
>  				const int32_t position)
>  {
> -	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
> +	/*  Key index where key is stored, adding the first dummy index*/
> +	uint32_t key_idx = position + 1;
> +
> +	RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL);
> 
>  	unsigned int lcore_id, n_slots;
>  	struct lcore_cache *cached_free_slots;
>  	const int32_t total_entries = h->num_buckets *
> RTE_HASH_BUCKET_ENTRIES;
> 
>  	/* Out of bounds */
> -	if (position >= total_entries)
> +	if (key_idx >= total_entries)
[Wang, Yipeng] 
Compiling fail after this commit.
/rte_cuckoo_hash.c:1600:14: error: comparison between signed and unsigned integer expressions [-Werror=sign-compare]
  if (key_idx >= total_entries)
please fix.

Please run the test-build and test-meson-build scripts. I currently have some issue with my meson setup on my new system so I will
rely on other reviewers or you guys to pass the meson test.

Logically these two bug fixes are valid and should be upstreamed otherwise this API breaks. But this is the experimental tag for :)

Thanks
Yipeng

Re: [dpdk-dev] [PATCH v3 1/3] hash: fix position bug in 'free key with position'

[Dharmik Thakkar]

> On May 9, 2019, at 10:48 AM, Wang, Yipeng1 <yipeng1.wang@intel.com> wrote:
> 
>> -----Original Message-----
>> From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
>> Sent: Thursday, May 9, 2019 6:39 AM
>> 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>
>> Cc: dev@dpdk.org; honnappa.nagarahalli@arm.com;
>> zhongdahulinfan@163.com; Dharmik Thakkar <dharmik.thakkar@arm.com>;
>> stable@dpdk.org
>> Subject: [PATCH v3 1/3] hash: fix position bug in 'free key with position'
>> 
>> Currently, in rte_hash_free_key_with_position(), the position returned to the
>> ring of free_slots leads to an unexpected conflict with a key already in use.
>> 
>> This patch fixes incorrect position returned to the ring of free_slots.
>> 
>> Bugzilla ID: 261
>> Fixes: 9d033dac7d7c ("hash: support no free on delete")
>> Cc: honnappa.nagarahalli@arm.com
>> Cc: stable@dpdk.org
>> 
>> Reported-by: Linfan <zhongdahulinfan@163.com>
>> Suggested-by: Linfan <zhongdahulinfan@163.com>
>> Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
>> ---
>> lib/librte_hash/rte_cuckoo_hash.c | 11 +++++++----
>> 1 file changed, 7 insertions(+), 4 deletions(-)
>> 
>> diff --git a/lib/librte_hash/rte_cuckoo_hash.c
>> b/lib/librte_hash/rte_cuckoo_hash.c
>> index 261267b7fd3d..8646ca52e60b 100644
>> --- a/lib/librte_hash/rte_cuckoo_hash.c
>> +++ b/lib/librte_hash/rte_cuckoo_hash.c
>> @@ -1587,14 +1587,17 @@ int __rte_experimental
>> rte_hash_free_key_with_position(const struct rte_hash *h,
>> 				const int32_t position)
>> {
>> -	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
>> +	/*  Key index where key is stored, adding the first dummy index*/
>> +	uint32_t key_idx = position + 1;
>> +
>> +	RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL);
>> 
>> 	unsigned int lcore_id, n_slots;
>> 	struct lcore_cache *cached_free_slots;
>> 	const int32_t total_entries = h->num_buckets *
>> RTE_HASH_BUCKET_ENTRIES;
>> 
>> 	/* Out of bounds */
>> -	if (position >= total_entries)
>> +	if (key_idx >= total_entries)
> [Wang, Yipeng] 
> Compiling fail after this commit.
> /rte_cuckoo_hash.c:1600:14: error: comparison between signed and unsigned integer expressions [-Werror=sign-compare]
>  if (key_idx >= total_entries)
> please fix.
Thank you for reporting! I have fixed the issue and updated the patch.
> 
> Please run the test-build and test-meson-build scripts. I currently have some issue with my meson setup on my new system so I will
> rely on other reviewers or you guys to pass the meson test.
I ran the scripts on my setup. Thanks!
> 
> Logically these two bug fixes are valid and should be upstreamed otherwise this API breaks. But this is the experimental tag for :)
> 
> Thanks
> Yipeng

[dpdk-dev] [PATCH v3 2/3] hash: fix total entries in free key with position

[Dharmik Thakkar]

In rte_hash, with current implementation, it is possible that keys
are stored at indexes greater than the number of total entries.

Currently, in rte_hash_free_key_with_position(), due to incorrect
computation of total_entries, application cannot free keys with
indexes greater than the number of total entries.

This patch fixes this incorrect computation of total_entries.

Bugzilla ID: 261
Fixes: 9d033dac7d7c ("hash: support no free on delete")
Cc: honnappa.nagarahalli@arm.com
Cc: stable@dpdk.org

Reported-by: Linfan <zhongdahulinfan@163.com>
Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 lib/librte_hash/rte_cuckoo_hash.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 8646ca52e60b..ed2e96b6f178 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1594,7 +1594,9 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
 
 	unsigned int lcore_id, n_slots;
 	struct lcore_cache *cached_free_slots;
-	const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
+	const uint32_t total_entries = h->use_local_cache ?
+		h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1
+							: h->entries + 1;
 
 	/* Out of bounds */
 	if (key_idx >= total_entries)
-- 
2.17.1

[dpdk-dev] [PATCH v3 3/3] test/hash: add test for 'free key with position'

[Dharmik Thakkar]

This patch adds a unit test for rte_hash_free_key_with_position().

Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 app/test/test_hash.c | 94 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)

diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 390fbef87f42..e162592965ce 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -481,6 +481,98 @@ static int test_add_update_delete_free(void)
 	return 0;
 }
 
+/*
+ * Sequence of operations for a single key with 'rw concurrency lock free' set:
+ *	- add
+ *	- delete: hit
+ *	- free: hit
+ * Repeat the test case when 'multi writer add' is enabled.
+ *	- add
+ *	- delete: hit
+ *	- free: hit
+ */
+static int test_add_delete_free_lf(void)
+{
+/* Should match the #define LCORE_CACHE_SIZE value in rte_cuckoo_hash.h */
+#define LCORE_CACHE_SIZE	64
+	struct rte_hash *handle;
+	hash_sig_t hash_value;
+	int pos, expectedPos, delPos;
+	uint8_t extra_flag;
+	uint32_t i, ip_src;
+
+	extra_flag = ut_params.extra_flag;
+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+	ut_params.extra_flag = extra_flag;
+
+	/*
+	 * The number of iterations is at least the same as the number of slots
+	 * rte_hash allocates internally. This is to reveal potential issues of
+	 * not freeing keys successfully.
+	 */
+	for (i = 0; i < ut_params.entries + 1; i++) {
+		hash_value = rte_hash_hash(handle, &keys[0]);
+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Add", &keys[0], pos);
+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
+		expectedPos = pos;
+
+		pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Del", &keys[0], pos);
+		RETURN_IF_ERROR(pos != expectedPos,
+				"failed to delete key (pos=%d)", pos);
+		delPos = pos;
+
+		pos = rte_hash_free_key_with_position(handle, delPos);
+		print_key_info("Free", &keys[0], delPos);
+		RETURN_IF_ERROR(pos != 0,
+				"failed to free key (pos=%d)", delPos);
+	}
+
+	rte_hash_free(handle);
+
+	extra_flag = ut_params.extra_flag;
+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF |
+				RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD;
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+	ut_params.extra_flag = extra_flag;
+
+	ip_src = keys[0].ip_src;
+	/*
+	 * The number of iterations is at least the same as the number of slots
+	 * rte_hash allocates internally. This is to reveal potential issues of
+	 * not freeing keys successfully.
+	 */
+	for (i = 0; i < ut_params.entries + (RTE_MAX_LCORE - 1) *
+					(LCORE_CACHE_SIZE - 1) + 1; i++) {
+		keys[0].ip_src++;
+		hash_value = rte_hash_hash(handle, &keys[0]);
+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Add", &keys[0], pos);
+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
+		expectedPos = pos;
+
+		pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Del", &keys[0], pos);
+		RETURN_IF_ERROR(pos != expectedPos,
+			"failed to delete key (pos=%d)", pos);
+		delPos = pos;
+
+		pos = rte_hash_free_key_with_position(handle, delPos);
+		print_key_info("Free", &keys[0], delPos);
+		RETURN_IF_ERROR(pos != 0,
+			"failed to free key (pos=%d)", delPos);
+	}
+	keys[0].ip_src = ip_src;
+
+	rte_hash_free(handle);
+
+	return 0;
+}
+
 /*
  * Sequence of operations for retrieving a key with its position
  *
@@ -1743,6 +1835,8 @@ test_hash(void)
 		return -1;
 	if (test_add_update_delete_free() < 0)
 		return -1;
+	if (test_add_delete_free_lf() < 0)
+		return -1;
 	if (test_five_keys() < 0)
 		return -1;
 	if (test_full_bucket() < 0)
-- 
2.17.1

[dpdk-dev] [PATCH v4 0/3] hash: fix bugs in 'free key with position'

[Dharmik Thakkar]

This patch series solves 2 bugs reported on Bugzilla (bug-261) within
the function rte_hash_free_key_with_postion(). It also adds a test case
 to catch similar bugs in the future.

https://bugs.dpdk.org/show_bug.cgi?id=261
---
v4:
 * Fix compilation failure (Yipeng)
v3:
 * Split the patch and update commit logs (Thomas)
v2:
 * Add comments in test_hash.c (Yipeng)
 * Resolve checkpatch warning

Dharmik Thakkar (3):
  hash: fix position bug in 'free key with position'
  hash: fix total entries in free key with position
  test/hash: add test for 'free key with position'

 app/test/test_hash.c              | 94 +++++++++++++++++++++++++++++++
 lib/librte_hash/rte_cuckoo_hash.c | 15 +++--
 2 files changed, 104 insertions(+), 5 deletions(-)

-- 
2.17.1

[dpdk-dev] [PATCH v4 1/3] hash: fix position bug in 'free key with position'

[Dharmik Thakkar]

Currently, in rte_hash_free_key_with_position(), the position returned
to the ring of free_slots leads to an unexpected conflict with a key
already in use.

This patch fixes incorrect position returned to the ring of free_slots.

Bugzilla ID: 261
Fixes: 9d033dac7d7c ("hash: support no free on delete")
Cc: honnappa.nagarahalli@arm.com
Cc: stable@dpdk.org

Reported-by: Linfan <zhongdahulinfan@163.com>
Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 lib/librte_hash/rte_cuckoo_hash.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 261267b7fd3d..5029f9f61fae 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1587,14 +1587,17 @@ int __rte_experimental
 rte_hash_free_key_with_position(const struct rte_hash *h,
 				const int32_t position)
 {
-	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
+	/*  Key index where key is stored, adding the first dummy index*/
+	uint32_t key_idx = position + 1;
+
+	RETURN_IF_TRUE(((h == NULL) || (key_idx == EMPTY_SLOT)), -EINVAL);
 
 	unsigned int lcore_id, n_slots;
 	struct lcore_cache *cached_free_slots;
-	const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
+	const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
 
 	/* Out of bounds */
-	if (position >= total_entries)
+	if (key_idx >= total_entries)
 		return -EINVAL;
 	if (h->ext_table_support && h->readwrite_concur_lf_support) {
 		uint32_t index = h->ext_bkt_to_free[position];
@@ -1619,11 +1622,11 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
 		}
 		/* Put index of new free slot in cache. */
 		cached_free_slots->objs[cached_free_slots->len] =
-					(void *)((uintptr_t)position);
+					(void *)((uintptr_t)key_idx);
 		cached_free_slots->len++;
 	} else {
 		rte_ring_sp_enqueue(h->free_slots,
-				(void *)((uintptr_t)position));
+				(void *)((uintptr_t)key_idx));
 	}
 
 	return 0;
-- 
2.17.1

Re: [dpdk-dev] [PATCH v4 1/3] hash: fix position bug in 'free key with position'

[Wang, Yipeng1]

>-----Original Message-----
>From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
>Sent: Thursday, May 9, 2019 10:19 AM
>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>
>Cc: dev@dpdk.org; honnappa.nagarahalli@arm.com; zhongdahulinfan@163.com; Dharmik Thakkar <dharmik.thakkar@arm.com>;
>stable@dpdk.org
>Subject: [PATCH v4 1/3] hash: fix position bug in 'free key with position'
>
>Currently, in rte_hash_free_key_with_position(), the position returned
>to the ring of free_slots leads to an unexpected conflict with a key
>already in use.
>
>This patch fixes incorrect position returned to the ring of free_slots.
>
>Bugzilla ID: 261
>Fixes: 9d033dac7d7c ("hash: support no free on delete")
>Cc: honnappa.nagarahalli@arm.com
>Cc: stable@dpdk.org
>
>Reported-by: Linfan <zhongdahulinfan@163.com>
>Suggested-by: Linfan <zhongdahulinfan@163.com>
>Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
>---
> lib/librte_hash/rte_cuckoo_hash.c | 13 ++++++++-----
> 1 file changed, 8 insertions(+), 5 deletions(-)
>
>diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
>index 261267b7fd3d..5029f9f61fae 100644
>--- a/lib/librte_hash/rte_cuckoo_hash.c
>+++ b/lib/librte_hash/rte_cuckoo_hash.c
>@@ -1587,14 +1587,17 @@ int __rte_experimental
> rte_hash_free_key_with_position(const struct rte_hash *h,
> 				const int32_t position)
> {
>-	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
>+	/*  Key index where key is stored, adding the first dummy index*/
[Wang, Yipeng] Minor issue, missing a space at the end.

Acked-by: Yipeng Wang <yipeng1.wang@intel.com>

Re: [dpdk-dev] [PATCH v4 1/3] hash: fix position bug in 'free key with position'

[Dharmik Thakkar]

> On May 9, 2019, at 2:27 PM, Wang, Yipeng1 <yipeng1.wang@intel.com> wrote:
> 
> 
> 
>> -----Original Message-----
>> From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
>> Sent: Thursday, May 9, 2019 10:19 AM
>> 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>
>> Cc: dev@dpdk.org; honnappa.nagarahalli@arm.com; zhongdahulinfan@163.com; Dharmik Thakkar <dharmik.thakkar@arm.com>;
>> stable@dpdk.org
>> Subject: [PATCH v4 1/3] hash: fix position bug in 'free key with position'
>> 
>> Currently, in rte_hash_free_key_with_position(), the position returned
>> to the ring of free_slots leads to an unexpected conflict with a key
>> already in use.
>> 
>> This patch fixes incorrect position returned to the ring of free_slots.
>> 
>> Bugzilla ID: 261
>> Fixes: 9d033dac7d7c ("hash: support no free on delete")
>> Cc: honnappa.nagarahalli@arm.com
>> Cc: stable@dpdk.org
>> 
>> Reported-by: Linfan <zhongdahulinfan@163.com>
>> Suggested-by: Linfan <zhongdahulinfan@163.com>
>> Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
>> ---
>> lib/librte_hash/rte_cuckoo_hash.c | 13 ++++++++-----
>> 1 file changed, 8 insertions(+), 5 deletions(-)
>> 
>> diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
>> index 261267b7fd3d..5029f9f61fae 100644
>> --- a/lib/librte_hash/rte_cuckoo_hash.c
>> +++ b/lib/librte_hash/rte_cuckoo_hash.c
>> @@ -1587,14 +1587,17 @@ int __rte_experimental
>> rte_hash_free_key_with_position(const struct rte_hash *h,
>> 				const int32_t position)
>> {
>> -	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
>> +	/*  Key index where key is stored, adding the first dummy index*/
> [Wang, Yipeng] Minor issue, missing a space at the end.
Is there a need to update the version?
> 
> Acked-by: Yipeng Wang <yipeng1.wang@intel.com>
Thank you!

Re: [dpdk-dev] [dpdk-stable] [PATCH v4 1/3] hash: fix position bug in 'free key with position'

[Thomas Monjalon]

09/05/2019 22:14, Dharmik Thakkar:
> > On May 9, 2019, at 2:27 PM, Wang, Yipeng1 <yipeng1.wang@intel.com> wrote:
> >> -	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
> >> +	/*  Key index where key is stored, adding the first dummy index*/
> > [Wang, Yipeng] Minor issue, missing a space at the end.
> Is there a need to update the version?

No, I am applying.

Re: [dpdk-dev] [dpdk-stable] [PATCH v4 1/3] hash: fix position bug in 'free key with position'

[Dharmik Thakkar]

> On May 9, 2019, at 3:23 PM, Thomas Monjalon <thomas@monjalon.net> wrote:
> 
> 09/05/2019 22:14, Dharmik Thakkar:
>>> On May 9, 2019, at 2:27 PM, Wang, Yipeng1 <yipeng1.wang@intel.com> wrote:
>>>> -	RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
>>>> +	/*  Key index where key is stored, adding the first dummy index*/
>>> [Wang, Yipeng] Minor issue, missing a space at the end.
>> Is there a need to update the version?
> 
> No, I am applying.
Sounds good. Thank you, Thomas!
> 
> 
> 

[dpdk-dev] [PATCH v4 2/3] hash: fix total entries in free key with position

[Dharmik Thakkar]

In rte_hash, with current implementation, it is possible that keys
are stored at indexes greater than the number of total entries.

Currently, in rte_hash_free_key_with_position(), due to incorrect
computation of total_entries, application cannot free keys with
indexes greater than the number of total entries.

This patch fixes this incorrect computation of total_entries.

Bugzilla ID: 261
Fixes: 9d033dac7d7c ("hash: support no free on delete")
Cc: honnappa.nagarahalli@arm.com
Cc: stable@dpdk.org

Reported-by: Linfan <zhongdahulinfan@163.com>
Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 lib/librte_hash/rte_cuckoo_hash.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 5029f9f61fae..ed2e96b6f178 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1594,7 +1594,9 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
 
 	unsigned int lcore_id, n_slots;
 	struct lcore_cache *cached_free_slots;
-	const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
+	const uint32_t total_entries = h->use_local_cache ?
+		h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1) + 1
+							: h->entries + 1;
 
 	/* Out of bounds */
 	if (key_idx >= total_entries)
-- 
2.17.1

Re: [dpdk-dev] [PATCH v4 2/3] hash: fix total entries in free key with position

[Wang, Yipeng1]

>-----Original Message-----
>From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
>Sent: Thursday, May 9, 2019 10:19 AM
>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>
>Cc: dev@dpdk.org; honnappa.nagarahalli@arm.com; zhongdahulinfan@163.com; Dharmik Thakkar <dharmik.thakkar@arm.com>;
>stable@dpdk.org
>Subject: [PATCH v4 2/3] hash: fix total entries in free key with position
>
>In rte_hash, with current implementation, it is possible that keys
>are stored at indexes greater than the number of total entries.
>
>Currently, in rte_hash_free_key_with_position(), due to incorrect
>computation of total_entries, application cannot free keys with
>indexes greater than the number of total entries.
>
>This patch fixes this incorrect computation of total_entries.
>
>Bugzilla ID: 261
>Fixes: 9d033dac7d7c ("hash: support no free on delete")
>Cc: honnappa.nagarahalli@arm.com
>Cc: stable@dpdk.org
>
>Reported-by: Linfan <zhongdahulinfan@163.com>
>Suggested-by: Linfan <zhongdahulinfan@163.com>
>Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
Acked-by: Yipeng Wang <yipeng1.wang@intel.com>

[dpdk-dev] [PATCH v4 3/3] test/hash: add test for 'free key with position'

[Dharmik Thakkar]

This patch adds a unit test for rte_hash_free_key_with_position().

Suggested-by: Linfan <zhongdahulinfan@163.com>
Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
---
 app/test/test_hash.c | 94 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)

diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 390fbef87f42..e162592965ce 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -481,6 +481,98 @@ static int test_add_update_delete_free(void)
 	return 0;
 }
 
+/*
+ * Sequence of operations for a single key with 'rw concurrency lock free' set:
+ *	- add
+ *	- delete: hit
+ *	- free: hit
+ * Repeat the test case when 'multi writer add' is enabled.
+ *	- add
+ *	- delete: hit
+ *	- free: hit
+ */
+static int test_add_delete_free_lf(void)
+{
+/* Should match the #define LCORE_CACHE_SIZE value in rte_cuckoo_hash.h */
+#define LCORE_CACHE_SIZE	64
+	struct rte_hash *handle;
+	hash_sig_t hash_value;
+	int pos, expectedPos, delPos;
+	uint8_t extra_flag;
+	uint32_t i, ip_src;
+
+	extra_flag = ut_params.extra_flag;
+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+	ut_params.extra_flag = extra_flag;
+
+	/*
+	 * The number of iterations is at least the same as the number of slots
+	 * rte_hash allocates internally. This is to reveal potential issues of
+	 * not freeing keys successfully.
+	 */
+	for (i = 0; i < ut_params.entries + 1; i++) {
+		hash_value = rte_hash_hash(handle, &keys[0]);
+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Add", &keys[0], pos);
+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
+		expectedPos = pos;
+
+		pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Del", &keys[0], pos);
+		RETURN_IF_ERROR(pos != expectedPos,
+				"failed to delete key (pos=%d)", pos);
+		delPos = pos;
+
+		pos = rte_hash_free_key_with_position(handle, delPos);
+		print_key_info("Free", &keys[0], delPos);
+		RETURN_IF_ERROR(pos != 0,
+				"failed to free key (pos=%d)", delPos);
+	}
+
+	rte_hash_free(handle);
+
+	extra_flag = ut_params.extra_flag;
+	ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF |
+				RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD;
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+	ut_params.extra_flag = extra_flag;
+
+	ip_src = keys[0].ip_src;
+	/*
+	 * The number of iterations is at least the same as the number of slots
+	 * rte_hash allocates internally. This is to reveal potential issues of
+	 * not freeing keys successfully.
+	 */
+	for (i = 0; i < ut_params.entries + (RTE_MAX_LCORE - 1) *
+					(LCORE_CACHE_SIZE - 1) + 1; i++) {
+		keys[0].ip_src++;
+		hash_value = rte_hash_hash(handle, &keys[0]);
+		pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Add", &keys[0], pos);
+		RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
+		expectedPos = pos;
+
+		pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
+		print_key_info("Del", &keys[0], pos);
+		RETURN_IF_ERROR(pos != expectedPos,
+			"failed to delete key (pos=%d)", pos);
+		delPos = pos;
+
+		pos = rte_hash_free_key_with_position(handle, delPos);
+		print_key_info("Free", &keys[0], delPos);
+		RETURN_IF_ERROR(pos != 0,
+			"failed to free key (pos=%d)", delPos);
+	}
+	keys[0].ip_src = ip_src;
+
+	rte_hash_free(handle);
+
+	return 0;
+}
+
 /*
  * Sequence of operations for retrieving a key with its position
  *
@@ -1743,6 +1835,8 @@ test_hash(void)
 		return -1;
 	if (test_add_update_delete_free() < 0)
 		return -1;
+	if (test_add_delete_free_lf() < 0)
+		return -1;
 	if (test_five_keys() < 0)
 		return -1;
 	if (test_full_bucket() < 0)
-- 
2.17.1

Re: [dpdk-dev] [PATCH v4 3/3] test/hash: add test for 'free key with position'

[Wang, Yipeng1]

>-----Original Message-----
>From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com]
>Sent: Thursday, May 9, 2019 10:19 AM
>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>
>Cc: dev@dpdk.org; honnappa.nagarahalli@arm.com; zhongdahulinfan@163.com; Dharmik Thakkar <dharmik.thakkar@arm.com>
>Subject: [PATCH v4 3/3] test/hash: add test for 'free key with position'
>
>This patch adds a unit test for rte_hash_free_key_with_position().
>
>Suggested-by: Linfan <zhongdahulinfan@163.com>
>Signed-off-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
Acked-by: Yipeng Wang <yipeng1.wang@intel.com>

Re: [dpdk-dev] [PATCH v4 0/3] hash: fix bugs in 'free key with position'

[Thomas Monjalon]

09/05/2019 19:19, Dharmik Thakkar:
> This patch series solves 2 bugs reported on Bugzilla (bug-261) within
> the function rte_hash_free_key_with_postion(). It also adds a test case
>  to catch similar bugs in the future.
> 
> https://bugs.dpdk.org/show_bug.cgi?id=261

Yipeng, Sameh, should it enter in 19.05-rc4?
Are you sure it does not break things more?
If yes, please give your ack.

Re: [dpdk-dev] [PATCH v4 0/3] hash: fix bugs in 'free key with position'

[Wang, Yipeng1]

>-----Original Message-----
>From: Thomas Monjalon [mailto:thomas@monjalon.net]
>Sent: Thursday, May 9, 2019 12:24 PM
>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>
>Cc: dev@dpdk.org; Dharmik Thakkar <dharmik.thakkar@arm.com>; honnappa.nagarahalli@arm.com; zhongdahulinfan@163.com
>Subject: Re: [dpdk-dev] [PATCH v4 0/3] hash: fix bugs in 'free key with position'
>
>09/05/2019 19:19, Dharmik Thakkar:
>> This patch series solves 2 bugs reported on Bugzilla (bug-261) within
>> the function rte_hash_free_key_with_postion(). It also adds a test case
>>  to catch similar bugs in the future.
>>
>> https://bugs.dpdk.org/show_bug.cgi?id=261
>
>Yipeng, Sameh, should it enter in 19.05-rc4?
>Are you sure it does not break things more?
>If yes, please give your ack.
[Wang, Yipeng] 
Please go ahead Thomas, I reviewed the code and it will not break other things. The
changes are refrained inside an experimental API function.

I haven't done the meson build test though.

Re: [dpdk-dev] [PATCH v4 0/3] hash: fix bugs in 'free key with position'

[Thomas Monjalon]

09/05/2019 21:36, Wang, Yipeng1:
> From: Thomas Monjalon [mailto:thomas@monjalon.net]
> >09/05/2019 19:19, Dharmik Thakkar:
> >> This patch series solves 2 bugs reported on Bugzilla (bug-261) within
> >> the function rte_hash_free_key_with_postion(). It also adds a test case
> >>  to catch similar bugs in the future.
> >>
> >> https://bugs.dpdk.org/show_bug.cgi?id=261
> >
> >Yipeng, Sameh, should it enter in 19.05-rc4?
> >Are you sure it does not break things more?
> >If yes, please give your ack.
> [Wang, Yipeng] 
> Please go ahead Thomas, I reviewed the code and it will not break other things. The
> changes are refrained inside an experimental API function.
> 
> I haven't done the meson build test though.

Applied, thanks