Skip to contentSkip to conversation

hash: fix bugs in 'free key with position'

PATCH Superseded Dharmik Thakkar 3 participants 30 messages May 8, 2019 – May 9, 2019 1 message not in the archive

lore
Share & tools
lore
#0 lore raw

cover hash: fix bugs in 'free key with position'

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(-)
Signature · 1 line
2.17.1
#1 lore raw

PATCH 1/2 hash: fix bugs in 'free key with position'

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")
---
 lib/librte_hash/rte_cuckoo_hash.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)
lib/librte_hash/rte_cuckoo_hash.c +9 -5
index 261267b7fd3d..590895d72062 100644
@@ -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;
Signature · 1 line
2.17.1
#2 lore raw

PATCH 2/2 test/hash: add test for 'free key with position'

In reply to Dharmik Thakkar

This patch adds a unit test for rte_hash_free_key_with_position().

---
 app/test/test_hash.c | 83 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)
app/test/test_hash.c +83 -0
index 390fbef87f42..a6949f2579a2 100644
@@ -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)
Signature · 1 line
2.17.1
#3 lore raw

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

Hi, thanks for the patch!
Reply inlined:

Quoted 27 lines

-----Original Message-----
From: Dharmik Thakkar [mailto:[email protected]]
Sent: Wednesday, May 8, 2019 9:51 AM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>; Richardson, Bruce <[email protected]>; De Lara Guarch, Pablo <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Dharmik Thakkar <[email protected]>
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().

---
app/test/test_hash.c | 83 ++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 83 insertions(+)
app/test/test_hash.c +3 -0
index 390fbef87f42..a6949f2579a2 100644
@@ -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

app/test/test_hash.c static int test_add_update_delete_free(void) · line 496

Quoted 10 lines
app/test/test_hash.c +10 -0
+ *	- 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.

app/test/test_hash.c static int test_add_update_delete_free(void) · line 508

Quoted 12 lines
app/test/test_hash.c +12 -0
+	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.

app/test/test_hash.c static int test_add_update_delete_free(void) · line 513

Quoted 5 lines
app/test/test_hash.c +5 -0
+	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

#4 lore raw

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

Quoted 6 lines · On May 8, 2019, at 3:11 PM, Wang, Yipeng1 <[email protected]> wrote:

Hi, thanks for the patch!
Reply inlined:

Hi Yipeng,
Thank you for the review!

Quoted 25 lines
Quoted 25 lines

-----Original Message-----
From: Dharmik Thakkar [mailto:[email protected]]
Sent: Wednesday, May 8, 2019 9:51 AM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>; Richardson, Bruce <[email protected]>; De Lara Guarch, Pablo <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Dharmik Thakkar <[email protected]>
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().

---
app/test/test_hash.c | 83 ++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 83 insertions(+)
app/test/test_hash.c +0 -0
index 390fbef87f42..a6949f2579a2 100644
@@ -481,6 +481,87 @@ static int test_add_update_delete_free(void)
 	return 0;
 }
 
Quoted 14 lines

app/test/test_hash.c static int test_add_update_delete_free(void) · line 496

Quoted 13 lines
app/test/test_hash.c +13 -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.

Quoted 2 lines

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.

Quoted 16 lines

app/test/test_hash.c static int test_add_update_delete_free(void) · line 508

Quoted 13 lines
app/test/test_hash.c +12 -0
+	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.

Quoted 10 lines

app/test/test_hash.c static int test_add_update_delete_free(void) · line 513

Quoted 6 lines
app/test/test_hash.c +5 -0
+	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

#5 lore raw

v2 cover hash: fix bugs in 'free key with position'

In reply to 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(-)
Signature · 1 line
2.17.1
#6 lore raw

PATCH v2 1/2 hash: fix bugs in 'free key with position'

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")
---
 lib/librte_hash/rte_cuckoo_hash.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)
lib/librte_hash/rte_cuckoo_hash.c +10 -5
index 261267b7fd3d..ed2e96b6f178 100644
@@ -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;
Signature · 1 line
2.17.1
#7 lore raw

09/05/2019 00:59, Dharmik Thakkar:

Quoted 3 lines

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.

A message that is not in the archive (sent off-list or not yet received): [email protected]

#9 lore raw

09/05/2019 12:40, 胡林帆:

Quoted 6 lines

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

Quoted 7 lines

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

Quoted 10 lines
Quoted 9 lines · Thomas Monjalon

09/05/2019 00:59, Dharmik Thakkar:

Quoted 3 lines

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.

#10 lore raw
Quoted 13 lines · Thomas Monjalon

09/05/2019 12:40, 胡林帆:

Quoted 8 lines

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:

Quoted 8 lines
Quoted 5 lines

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!

Quoted 19 lines

Then we'll need approval from the maintainers.

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

Quoted 10 lines
Quoted 9 lines · Thomas Monjalon

09/05/2019 00:59, Dharmik Thakkar:

Quoted 3 lines

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.

#11 lore raw

PATCH v2 2/2 test/hash: add test for 'free key with position'

In reply to Dharmik Thakkar

This patch adds a unit test for rte_hash_free_key_with_position().

---
 app/test/test_hash.c | 94 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)
app/test/test_hash.c +94 -0
index 390fbef87f42..e162592965ce 100644
@@ -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)
Signature · 1 line
2.17.1
#12 lore raw

v3 cover hash: fix bugs in 'free key with position'

In reply to 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(-)
Signature · 1 line
2.17.1
#13 lore raw

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")
---
 lib/librte_hash/rte_cuckoo_hash.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)
lib/librte_hash/rte_cuckoo_hash.c +7 -4
index 261267b7fd3d..8646ca52e60b 100644
@@ -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;
Signature · 1 line
2.17.1
#14 lore raw

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

Quoted 41 lines

-----Original Message-----
From: Dharmik Thakkar [mailto:[email protected]]
Sent: Thursday, May 9, 2019 6:39 AM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>; Richardson, Bruce <[email protected]>; De Lara Guarch, Pablo <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Dharmik Thakkar <[email protected]>; [email protected]
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")
---
 lib/librte_hash/rte_cuckoo_hash.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)
lib/librte_hash/rte_cuckoo_hash.c +3 -1
index 261267b7fd3d..8646ca52e60b 100644
@@ -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;
+

lib/librte_hash/rte_cuckoo_hash.c int __rte_experimental · line 1601

Quoted 10 lines
lib/librte_hash/rte_cuckoo_hash.c +2 -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

#15 lore raw

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

Quoted 52 lines · On May 9, 2019, at 10:48 AM, Wang, Yipeng1 <[email protected]> wrote:
Quoted 49 lines

-----Original Message-----
From: Dharmik Thakkar [mailto:[email protected]]
Sent: Thursday, May 9, 2019 6:39 AM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>; Richardson, Bruce <[email protected]>; De Lara Guarch, Pablo <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Dharmik Thakkar <[email protected]>; [email protected]
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")

---
lib/librte_hash/rte_cuckoo_hash.c | 11 +++++++----

1 file changed, 7 insertions(+), 4 deletions(-)
lib/librte_hash/rte_cuckoo_hash.c +4 -1
index 261267b7fd3d..8646ca52e60b 100644
@@ -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;
 
Quoted 8 lines

lib/librte_hash/rte_cuckoo_hash.c int __rte_experimental · line 1600

Quoted 3 lines
lib/librte_hash/rte_cuckoo_hash.c +1 -1
 	/* 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.

Quoted 3 lines

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!

Quoted 5 lines

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

Thanks
Yipeng

#16 lore raw

PATCH v3 2/3 hash: fix total entries in free key with position

In reply to 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")
---
 lib/librte_hash/rte_cuckoo_hash.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
lib/librte_hash/rte_cuckoo_hash.c +3 -1
index 8646ca52e60b..ed2e96b6f178 100644
@@ -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)
Signature · 1 line
2.17.1
#17 lore raw

PATCH v3 3/3 test/hash: add test for 'free key with position'

In reply to Dharmik Thakkar

This patch adds a unit test for rte_hash_free_key_with_position().

---
 app/test/test_hash.c | 94 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)
app/test/test_hash.c +94 -0
index 390fbef87f42..e162592965ce 100644
@@ -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)
Signature · 1 line
2.17.1
#18 lore raw

v4 cover hash: fix bugs in 'free key with position'

In reply to 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(-)
Signature · 1 line
2.17.1
#19 lore raw

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")
---
 lib/librte_hash/rte_cuckoo_hash.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)
lib/librte_hash/rte_cuckoo_hash.c +8 -5
index 261267b7fd3d..5029f9f61fae 100644
@@ -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;
Signature · 1 line
2.17.1
Acked-by on v4 1/3
#20 lore raw

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

Quoted 34 lines

-----Original Message-----
From: Dharmik Thakkar [mailto:[email protected]]
Sent: Thursday, May 9, 2019 10:19 AM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>; Richardson, Bruce <[email protected]>; De Lara Guarch, Pablo <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Dharmik Thakkar <[email protected]>; [email protected]
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")

---
lib/librte_hash/rte_cuckoo_hash.c | 13 ++++++++-----

1 file changed, 8 insertions(+), 5 deletions(-)
lib/librte_hash/rte_cuckoo_hash.c +0 -0
index 261267b7fd3d..5029f9f61fae 100644

lib/librte_hash/rte_cuckoo_hash.c int __rte_experimental · line 1590

Quoted 5 lines
lib/librte_hash/rte_cuckoo_hash.c +1 -1
@@ -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.

#21 lore raw

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

Quoted 33 lines · On May 9, 2019, at 2:27 PM, Wang, Yipeng1 <[email protected]> wrote:
Quoted 30 lines

-----Original Message-----
From: Dharmik Thakkar [mailto:[email protected]]
Sent: Thursday, May 9, 2019 10:19 AM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>; Richardson, Bruce <[email protected]>; De Lara Guarch, Pablo <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Dharmik Thakkar <[email protected]>; [email protected]
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")

---
lib/librte_hash/rte_cuckoo_hash.c | 13 ++++++++-----

1 file changed, 8 insertions(+), 5 deletions(-)
Quoted 11 lines

lib/librte_hash/rte_cuckoo_hash.c int __rte_experimental · line 1590

Quoted 10 lines
lib/librte_hash/rte_cuckoo_hash.c +1 -1
index 261267b7fd3d..5029f9f61fae 100644
@@ -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?

Quoted 2 lines

Thank you!

#22 lore raw

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

09/05/2019 22:14, Dharmik Thakkar:

Quoted 5 lines
Quoted 4 lines · On May 9, 2019, at 2:27 PM, Wang, Yipeng1 <[email protected]> wrote:

lib/librte_hash/rte_cuckoo_hash.c int __rte_experimental · line 1590

Quoted 2 lines
lib/librte_hash/rte_cuckoo_hash.c +1 -1
-	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.

#23 lore raw

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

Quoted 12 lines · Thomas Monjalon

09/05/2019 22:14, Dharmik Thakkar:

Quoted 5 lines
Quoted 4 lines · On May 9, 2019, at 2:27 PM, Wang, Yipeng1 <[email protected]> wrote:

lib/librte_hash/rte_cuckoo_hash.c int __rte_experimental · line 1590

Quoted 2 lines
lib/librte_hash/rte_cuckoo_hash.c +1 -1
-	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!

Quoted 3 lines
#24 lore raw

PATCH v4 2/3 hash: fix total entries in free key with position

In reply to 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")
---
 lib/librte_hash/rte_cuckoo_hash.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
lib/librte_hash/rte_cuckoo_hash.c +3 -1
index 5029f9f61fae..ed2e96b6f178 100644
@@ -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)
Signature · 1 line
2.17.1
Acked-by on v4 2/3
#25 lore raw

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

Quoted 18 lines

-----Original Message-----
From: Dharmik Thakkar [mailto:[email protected]]
Sent: Thursday, May 9, 2019 10:19 AM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>; Richardson, Bruce <[email protected]>; De Lara Guarch, Pablo <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Dharmik Thakkar <[email protected]>; [email protected]
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.

Quoted 8 lines

Bugzilla ID: 261

Fixes 9d033dac7d7c ("hash: support no free on delete")
#26 lore raw

PATCH v4 3/3 test/hash: add test for 'free key with position'

In reply to Dharmik Thakkar

This patch adds a unit test for rte_hash_free_key_with_position().

---
 app/test/test_hash.c | 94 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)
app/test/test_hash.c +94 -0
index 390fbef87f42..e162592965ce 100644
@@ -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)
Signature · 1 line
2.17.1
Acked-by on v4 3/3
#27 lore raw

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

Quoted 8 lines

-----Original Message-----
From: Dharmik Thakkar [mailto:[email protected]]
Sent: Thursday, May 9, 2019 10:19 AM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>; Richardson, Bruce <[email protected]>; De Lara Guarch, Pablo <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Dharmik Thakkar <[email protected]>
Subject: [PATCH v4 3/3] test/hash: add test for 'free key with position'

Quoted 4 lines

This patch adds a unit test for rte_hash_free_key_with_position().

#29 lore raw
Quoted 12 lines

-----Original Message-----
From: Thomas Monjalon [mailto:[email protected]]
Sent: Thursday, May 9, 2019 12:24 PM
To: Wang, Yipeng1 <[email protected]>; Gobriel, Sameh <[email protected]>
Cc: [email protected]; Dharmik Thakkar <[email protected]>; [email protected]; [email protected]
Subject: Re: [dpdk-dev] [PATCH v4 0/3] hash: fix bugs in 'free key with position'

09/05/2019 19:19, Dharmik Thakkar:

Quoted 4 lines

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.

Quoted 5 lines
Quoted 1 line

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.

#30 lore raw

09/05/2019 21:36, Wang, Yipeng1:

Quoted 8 lines

From: Thomas Monjalon [mailto:[email protected]]

Quoted 7 lines

09/05/2019 19:19, Dharmik Thakkar:

Quoted 5 lines

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

Quoted 8 lines
Quoted 3 lines

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