DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] [PATCH] lib/librte_hash: avoid iterate bugs with delete keys.
@ 2020-04-27  3:41 Lilijun (Jerry)
  2020-05-12 23:50 ` Wang, Yipeng1
  0 siblings, 1 reply; 2+ messages in thread
From: Lilijun (Jerry) @ 2020-04-27  3:41 UTC (permalink / raw)
  To: 'dev@dpdk.org'; +Cc: wangyunjian, xudingke, 'stable@dpdk.org'

From 0faea722b82ffe30adfa55d5ea4ad3a23ed30d4e Mon Sep 17 00:00:00 2001
From: Yunjian Wang <wangyunjian@huawei.com>
Date: Mon, 27 Apr 2020 11:12:25 +0800
Subject: [PATCH] lib/librte_hash: avoid iterate bugs with delete keys.

The keys idx are stored in rte_hash main and extend bucket key slots.
We iterate every no empty Keys in h->buckets and h->buckets_ext
from start to last. When deleting keys the function
__rte_hash_compact_ll() may move last_bkt's key to previous bucket
in order to compact extend bucket list.
If the previous bucket has been iterated, the moved key may be missed
for users. Then those missed keys are leaked and rte_hash table can't
be cleanup.
So we add a new API rte_hash_del_key_fixed() used in iterate loop
to avoid this bugs.

Signed-off-by: Lilijun <jerry.lilijun@huawei.com>
Signed-off-by: Yunjian Wang <wangyunjian@huawei.com>
---
 lib/librte_hash/rte_cuckoo_hash.c    | 19 +++++++++++++-----
 lib/librte_hash/rte_hash.h           | 30 ++++++++++++++++++++++++++++
 lib/librte_hash/rte_hash_version.map |  1 +
 3 files changed, 45 insertions(+), 5 deletions(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 38767a8a1..1b6f84759 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1491,7 +1491,7 @@ search_and_remove(const struct rte_hash *h, const void *key,
 
 static inline int32_t
 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
-						hash_sig_t sig)
+						hash_sig_t sig, uint8_t compact)
 {
 	uint32_t prim_bucket_idx, sec_bucket_idx;
 	struct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt;
@@ -1509,7 +1509,8 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 	/* look for key in primary bucket */
 	ret = search_and_remove(h, key, prim_bkt, short_sig, &pos);
 	if (ret != -1) {
-		__rte_hash_compact_ll(h, prim_bkt, pos);
+		if (compact)
+			__rte_hash_compact_ll(h, prim_bkt, pos);
 		last_bkt = prim_bkt->next;
 		prev_bkt = prim_bkt;
 		goto return_bkt;
@@ -1521,7 +1522,8 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 	FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
 		ret = search_and_remove(h, key, cur_bkt, short_sig, &pos);
 		if (ret != -1) {
-			__rte_hash_compact_ll(h, cur_bkt, pos);
+			if (compact)
+				__rte_hash_compact_ll(h, cur_bkt, pos);
 			last_bkt = sec_bkt->next;
 			prev_bkt = sec_bkt;
 			goto return_bkt;
@@ -1576,14 +1578,21 @@ rte_hash_del_key_with_hash(const struct rte_hash *h,
 			const void *key, hash_sig_t sig)
 {
 	RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
-	return __rte_hash_del_key_with_hash(h, key, sig);
+	return __rte_hash_del_key_with_hash(h, key, sig, 1);
 }
 
 int32_t
 rte_hash_del_key(const struct rte_hash *h, const void *key)
 {
 	RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
-	return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
+	return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key), 1);
+}
+
+int32_t
+rte_hash_del_key_fixed(const struct rte_hash *h, const void *key)
+{
+	RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+	return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key), 0);
 }
 
 int
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index bff40251b..1bea33809 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -309,6 +309,36 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t
 int32_t
 rte_hash_del_key(const struct rte_hash *h, const void *key);
 
+/**
+ * Remove a key without compact ext bucket list from an existing hash table.
+ * This operation is not multi-thread safe
+ * and should only be called from one thread by default.
+ * Thread safety can be enabled by setting flag during
+ * table creation.
+ * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or
+ * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled,
+ * the key index returned by rte_hash_add_key_xxx APIs will not be
+ * freed by this API. rte_hash_free_key_with_position API must be called
+ * additionally to free the index associated with the key.
+ * rte_hash_free_key_with_position API should be called after all
+ * the readers have stopped referencing the entry corresponding to
+ * this key. RCU mechanisms could be used to determine such a state.
+ *
+ * @param h
+ *   Hash table to remove the key from.
+ * @param key
+ *   Key to remove from the hash table.
+ * @return
+ *   - -EINVAL if the parameters are invalid.
+ *   - -ENOENT if the key is not found.
+ *   - A positive value that can be used by the caller as an offset into an
+ *     array of user data. This value is unique for this key, and is the same
+ *     value that was returned when the key was added.
+ */
+__rte_experimental
+int32_t
+rte_hash_del_key_fixed(const struct rte_hash *h, const void *key);
+
 /**
  * Remove a key from an existing hash table.
  * This operation is not multi-thread safe
diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map
index c2a909443..11a7f9b61 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -36,5 +36,6 @@ EXPERIMENTAL {
 	rte_hash_lookup_with_hash_bulk;
 	rte_hash_lookup_with_hash_bulk_data;
 	rte_hash_max_key_id;
+	rte_hash_del_key_fixed;
 
 };
-- 
2.19.1


^ permalink raw reply	[flat|nested] 2+ messages in thread

* Re: [dpdk-dev] [PATCH] lib/librte_hash: avoid iterate bugs with delete keys.
  2020-04-27  3:41 [dpdk-dev] [PATCH] lib/librte_hash: avoid iterate bugs with delete keys Lilijun (Jerry)
@ 2020-05-12 23:50 ` Wang, Yipeng1
  0 siblings, 0 replies; 2+ messages in thread
From: Wang, Yipeng1 @ 2020-05-12 23:50 UTC (permalink / raw)
  To: Lilijun (Jerry), 'dev@dpdk.org'
  Cc: wangyunjian, xudingke, 'stable@dpdk.org'

> -----Original Message-----
> From: dev <dev-bounces@dpdk.org> On Behalf Of Lilijun (Jerry)
> Sent: Sunday, April 26, 2020 8:41 PM
> To: 'dev@dpdk.org' <dev@dpdk.org>
> Cc: wangyunjian <wangyunjian@huawei.com>; xudingke
> <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>
> Subject: [dpdk-dev] [PATCH] lib/librte_hash: avoid iterate bugs with delete
> keys.
> 
> From 0faea722b82ffe30adfa55d5ea4ad3a23ed30d4e Mon Sep 17 00:00:00
> 2001
> From: Yunjian Wang <wangyunjian@huawei.com>
> Date: Mon, 27 Apr 2020 11:12:25 +0800
> Subject: [PATCH] lib/librte_hash: avoid iterate bugs with delete keys.
> 
> The keys idx are stored in rte_hash main and extend bucket key slots.
> We iterate every no empty Keys in h->buckets and h->buckets_ext from
> start to last. When deleting keys the function
> __rte_hash_compact_ll() may move last_bkt's key to previous bucket in
> order to compact extend bucket list.
> If the previous bucket has been iterated, the moved key may be missed for
> users. Then those missed keys are leaked and rte_hash table can't be
> cleanup.
> So we add a new API rte_hash_del_key_fixed() used in iterate loop to avoid
> this bugs.
> 
> Signed-off-by: Lilijun <jerry.lilijun@huawei.com>
> Signed-off-by: Yunjian Wang <wangyunjian@huawei.com>
> ---
> --
> 2.19.1
[Wang, Yipeng] 
Is this the same patch to the previous one? Please see my reply on the previous thread.
You could add " --in-reply-to" to supersede the previous version, which will make the maintaining work easier.

^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2020-05-12 23:50 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-04-27  3:41 [dpdk-dev] [PATCH] lib/librte_hash: avoid iterate bugs with delete keys Lilijun (Jerry)
2020-05-12 23:50 ` Wang, Yipeng1

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).