[dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Lilijun (Jerry)]

The keys idx are stored in rte_hash main bucket key slots and extend bucket key stots. 
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.

---
 lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
 lib/librte_hash/rte_hash.h           |  5 +++++
 lib/librte_hash/rte_hash_version.map |  1 +
 3 files changed, 20 insertions(+), 5 deletions(-)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index b52630b..2da3c1d 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1523,7 +1523,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;
@@ -1541,7 +1541,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;
@@ -1553,7 +1554,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;
@@ -1607,14 +1609,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 eceb365..9b71d8a 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -297,6 +297,11 @@ 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);
 
+
+/* for without compact */
+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 30cc086..1941d17 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -11,6 +11,7 @@ DPDK_20.0 {
 	rte_hash_count;
 	rte_hash_create;
 	rte_hash_del_key;
+	rte_hash_del_key_fixed;
 	rte_hash_del_key_with_hash;
 	rte_hash_find_existing;
 	rte_hash_free;
-- 
2.19.1

-----邮件原件-----
发件人: Lilijun (Jerry) 
发送时间: 2020年4月18日 18:00
收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org' <stable@dpdk.org>
主题: rte_hash bug: can't iterate all entries when deleting keys in rte_hash iterate loop.

Hi all,

    In my test, entries can't be cleanup in rte_hash table when deleting keys in rte_hash iterate loop. The test steps:
    1.  create a hash table table1 with limit 30000, ext bucket enabled,  and insert 30000 entries into this hash table.
    2.  create a larger hash table table2 with limit 60000, , ext bucket enabled.
    3.  iterate all entries of table1 and insert them to the table2. Insert new 10000 entries to this table2.
    4.  Then flush all entries from table2 by deleting keys in rte_hash iterate loop. But there are still some keys leaked in table2.

    From my analysis, the keys idx are stored in rte_hash main bucket key slots and extend bucket key stots. 
    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.

    Now I retry the iterate and delete keys, that can avoid this bug. 

    Is there any ideas or solutions on this bug?   Thanks.

Jerry.

Re: [dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Honnappa Nagarahalli]

<snip>

Hi Jerry,
	Few questions inline.

> Subject: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> without compact
> 
> The keys idx are stored in rte_hash main bucket key slots and extend bucket
> key stots.
> 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.
> 
> ---
>  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
>  lib/librte_hash/rte_hash.h           |  5 +++++
>  lib/librte_hash/rte_hash_version.map |  1 +
>  3 files changed, 20 insertions(+), 5 deletions(-)
> 
> diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> b/lib/librte_hash/rte_cuckoo_hash.c
> index b52630b..2da3c1d 100644
> --- a/lib/librte_hash/rte_cuckoo_hash.c
> +++ b/lib/librte_hash/rte_cuckoo_hash.c
> @@ -1523,7 +1523,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;
> @@ -1541,7 +1541,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;
> @@ -1553,7 +1554,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;
> @@ -1607,14 +1609,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
> eceb365..9b71d8a 100644
> --- a/lib/librte_hash/rte_hash.h
> +++ b/lib/librte_hash/rte_hash.h
> @@ -297,6 +297,11 @@ 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);
> 
> +
> +/* for without compact */
> +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 30cc086..1941d17 100644
> --- a/lib/librte_hash/rte_hash_version.map
> +++ b/lib/librte_hash/rte_hash_version.map
> @@ -11,6 +11,7 @@ DPDK_20.0 {
>  	rte_hash_count;
>  	rte_hash_create;
>  	rte_hash_del_key;
> +	rte_hash_del_key_fixed;
>  	rte_hash_del_key_with_hash;
>  	rte_hash_find_existing;
>  	rte_hash_free;
> --
> 2.19.1
> 
> -----邮件原件-----
> 发件人: Lilijun (Jerry)
> 发送时间: 2020年4月18日 18:00
> 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> <stable@dpdk.org>
> 主题: rte_hash bug: can't iterate all entries when deleting keys in rte_hash
> iterate loop.
> 
> Hi all,
> 
>     In my test, entries can't be cleanup in rte_hash table when deleting keys in
> rte_hash iterate loop. The test steps:
>     1.  create a hash table table1 with limit 30000, ext bucket enabled,  and
> insert 30000 entries into this hash table.
>     2.  create a larger hash table table2 with limit 60000, , ext bucket enabled.
>     3.  iterate all entries of table1 and insert them to the table2. Insert new
> 10000 entries to this table2.
>     4.  Then flush all entries from table2 by deleting keys in rte_hash iterate
> loop. But there are still some keys leaked in table2.
Is there any reason for flushing table2 in this manner?
Is it possible to use 'rte_hash_reset' instead?

> 
>     From my analysis, the keys idx are stored in rte_hash main bucket key slots
> and extend bucket key stots.
>     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.
> 
>     Now I retry the iterate and delete keys, that can avoid this bug.
> 
>     Is there any ideas or solutions on this bug?   Thanks.
> 
> Jerry.

[dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Lilijun (Jerry)]

Thanks for your reply.

Using rte_hash iterate and delete keys is to free the related data's memory. 
There are two reasons why rte_hash_reset() is not properly:
1)  the reset function just clear all keys, the key's related data are leaked.
2)  In some cases, I don't need delete all keys. Just some selected keys and data are deleted and released.

Jerry.

-----邮件原件-----
发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] 
发送时间: 2020年4月29日 4:46
收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org' <dev@dpdk.org>
抄送: wangyunjian <wangyunjian@huawei.com>; xudingke <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd <nd@arm.com>; Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>; nd <nd@arm.com>
主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

<snip>

Hi Jerry,
	Few questions inline.

> Subject: [dpdk-dev] [PATCH] lib/librte_hash: add 
> rte_hash_del_key_fixed without compact
> 
> The keys idx are stored in rte_hash main bucket key slots and extend 
> bucket key stots.
> 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.
> 
> ---
>  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
>  lib/librte_hash/rte_hash.h           |  5 +++++
>  lib/librte_hash/rte_hash_version.map |  1 +
>  3 files changed, 20 insertions(+), 5 deletions(-)
> 
> diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> b/lib/librte_hash/rte_cuckoo_hash.c
> index b52630b..2da3c1d 100644
> --- a/lib/librte_hash/rte_cuckoo_hash.c
> +++ b/lib/librte_hash/rte_cuckoo_hash.c
> @@ -1523,7 +1523,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; @@ 
> -1541,7 +1541,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;
> @@ -1553,7 +1554,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;
> @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> --- a/lib/librte_hash/rte_hash.h
> +++ b/lib/librte_hash/rte_hash.h
> @@ -297,6 +297,11 @@ 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);
> 
> +
> +/* for without compact */
> +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 30cc086..1941d17 100644
> --- a/lib/librte_hash/rte_hash_version.map
> +++ b/lib/librte_hash/rte_hash_version.map
> @@ -11,6 +11,7 @@ DPDK_20.0 {
>  	rte_hash_count;
>  	rte_hash_create;
>  	rte_hash_del_key;
> +	rte_hash_del_key_fixed;
>  	rte_hash_del_key_with_hash;
>  	rte_hash_find_existing;
>  	rte_hash_free;
> --
> 2.19.1
> 
> -----邮件原件-----
> 发件人: Lilijun (Jerry)
> 发送时间: 2020年4月18日 18:00
> 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> <stable@dpdk.org>
> 主题: rte_hash bug: can't iterate all entries when deleting keys in 
> rte_hash iterate loop.
> 
> Hi all,
> 
>     In my test, entries can't be cleanup in rte_hash table when 
> deleting keys in rte_hash iterate loop. The test steps:
>     1.  create a hash table table1 with limit 30000, ext bucket 
> enabled,  and insert 30000 entries into this hash table.
>     2.  create a larger hash table table2 with limit 60000, , ext bucket enabled.
>     3.  iterate all entries of table1 and insert them to the table2. 
> Insert new
> 10000 entries to this table2.
>     4.  Then flush all entries from table2 by deleting keys in 
> rte_hash iterate loop. But there are still some keys leaked in table2.
Is there any reason for flushing table2 in this manner?
Is it possible to use 'rte_hash_reset' instead?

> 
>     From my analysis, the keys idx are stored in rte_hash main bucket 
> key slots and extend bucket key stots.
>     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.
> 
>     Now I retry the iterate and delete keys, that can avoid this bug.
> 
>     Is there any ideas or solutions on this bug?   Thanks.
> 
> Jerry.

Re: [dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Honnappa Nagarahalli]

<snip>

Adding Yipeng, maintainer for hash library

> 
> Thanks for your reply.
> 
> Using rte_hash iterate and delete keys is to free the related data's memory.
> There are two reasons why rte_hash_reset() is not properly:
> 1)  the reset function just clear all keys, the key's related data are leaked.
That is a good point. I think this should be documented in the API.

> 2)  In some cases, I don't need delete all keys. Just some selected keys and
> data are deleted and released.
I understand the problem you have pointed out and understand how to reproduce it. But, the use case is not clear to me. Can you please explain the use case?

> 
> Jerry.
> 
> -----邮件原件-----
> 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> 发送时间: 2020年4月29日 4:46
> 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> <dev@dpdk.org>
> 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> <nd@arm.com>; Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> nd <nd@arm.com>
> 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> without compact
> 
> <snip>
> 
> Hi Jerry,
> 	Few questions inline.
> 
> > Subject: [dpdk-dev] [PATCH] lib/librte_hash: add
> > rte_hash_del_key_fixed without compact
> >
> > The keys idx are stored in rte_hash main bucket key slots and extend
> > bucket key stots.
> > 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.
> >
> > ---
> >  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
> >  lib/librte_hash/rte_hash.h           |  5 +++++
> >  lib/librte_hash/rte_hash_version.map |  1 +
> >  3 files changed, 20 insertions(+), 5 deletions(-)
> >
> > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > b/lib/librte_hash/rte_cuckoo_hash.c
> > index b52630b..2da3c1d 100644
> > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > @@ -1523,7 +1523,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;
> @@
> > -1541,7 +1541,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;
> > @@ -1553,7 +1554,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;
> > @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> > --- a/lib/librte_hash/rte_hash.h
> > +++ b/lib/librte_hash/rte_hash.h
> > @@ -297,6 +297,11 @@ 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);
> >
> > +
> > +/* for without compact */
> > +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 30cc086..1941d17 100644
> > --- a/lib/librte_hash/rte_hash_version.map
> > +++ b/lib/librte_hash/rte_hash_version.map
> > @@ -11,6 +11,7 @@ DPDK_20.0 {
> >  	rte_hash_count;
> >  	rte_hash_create;
> >  	rte_hash_del_key;
> > +	rte_hash_del_key_fixed;
> >  	rte_hash_del_key_with_hash;
> >  	rte_hash_find_existing;
> >  	rte_hash_free;
> > --
> > 2.19.1
> >
> > -----邮件原件-----
> > 发件人: Lilijun (Jerry)
> > 发送时间: 2020年4月18日 18:00
> > 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> > <stable@dpdk.org>
> > 主题: rte_hash bug: can't iterate all entries when deleting keys in
> > rte_hash iterate loop.
> >
> > Hi all,
> >
> >     In my test, entries can't be cleanup in rte_hash table when
> > deleting keys in rte_hash iterate loop. The test steps:
> >     1.  create a hash table table1 with limit 30000, ext bucket
> > enabled,  and insert 30000 entries into this hash table.
> >     2.  create a larger hash table table2 with limit 60000, , ext bucket
> enabled.
> >     3.  iterate all entries of table1 and insert them to the table2.
> > Insert new
> > 10000 entries to this table2.
> >     4.  Then flush all entries from table2 by deleting keys in
> > rte_hash iterate loop. But there are still some keys leaked in table2.
> Is there any reason for flushing table2 in this manner?
> Is it possible to use 'rte_hash_reset' instead?
> 
> >
> >     From my analysis, the keys idx are stored in rte_hash main bucket
> > key slots and extend bucket key stots.
> >     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.
> >
> >     Now I retry the iterate and delete keys, that can avoid this bug.
> >
> >     Is there any ideas or solutions on this bug?   Thanks.
> >
> > Jerry.

[dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Lilijun (Jerry)]

> -----邮件原件-----
> 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> 发送时间: 2020年5月6日 7:18
> 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> <dev@dpdk.org>
> 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> <nd@arm.com>; Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> yipeng1.wang@intel.com; nd <nd@arm.com>
> 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> without compact
> 
> <snip>
> 
> Adding Yipeng, maintainer for hash library
> 
> >
> > Thanks for your reply.
> >
> > Using rte_hash iterate and delete keys is to free the related data's memory.
> > There are two reasons why rte_hash_reset() is not properly:
> > 1)  the reset function just clear all keys, the key's related data are leaked.
> That is a good point. I think this should be documented in the API.
> 
> > 2)  In some cases, I don't need delete all keys. Just some selected
> > keys and data are deleted and released.
> I understand the problem you have pointed out and understand how to
> reproduce it. But, the use case is not clear to me. Can you please explain the
> use case?
[Lilijun (Jerry)] 

As you know, the dpdk rte_hash use a fixed size table to store all keys/datas. The memory used by hash table is related with this fixed size.
In my case, normally the count of keys is about 100,000 but sometimes the count may burst up to 30,000,000.
In order to save memory usage, I create a small hash table with 100,000 size and replace to a bigger one with 30,000,000 size when
there are more keys to be stored. Also when the key's count reduced to less than 100,000, I replace the hash table with a small one to
save the memory.

> 
> >
> > Jerry.
> >
> > -----邮件原件-----
> > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > 发送时间: 2020年4月29日 4:46
> > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > <dev@dpdk.org>
> > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > <nd@arm.com>; Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> nd
> > <nd@arm.com>
> > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> > without compact
> >
> > <snip>
> >
> > Hi Jerry,
> > 	Few questions inline.
> >
> > > Subject: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > rte_hash_del_key_fixed without compact
> > >
> > > The keys idx are stored in rte_hash main bucket key slots and extend
> > > bucket key stots.
> > > 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.
> > >
> > > ---
> > >  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
> > >  lib/librte_hash/rte_hash.h           |  5 +++++
> > >  lib/librte_hash/rte_hash_version.map |  1 +
> > >  3 files changed, 20 insertions(+), 5 deletions(-)
> > >
> > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > > b/lib/librte_hash/rte_cuckoo_hash.c
> > > index b52630b..2da3c1d 100644
> > > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > > @@ -1523,7 +1523,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;
> > @@
> > > -1541,7 +1541,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;
> > > @@ -1553,7 +1554,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;
> > > @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> > > --- a/lib/librte_hash/rte_hash.h
> > > +++ b/lib/librte_hash/rte_hash.h
> > > @@ -297,6 +297,11 @@ 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);
> > >
> > > +
> > > +/* for without compact */
> > > +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 30cc086..1941d17 100644
> > > --- a/lib/librte_hash/rte_hash_version.map
> > > +++ b/lib/librte_hash/rte_hash_version.map
> > > @@ -11,6 +11,7 @@ DPDK_20.0 {
> > >  	rte_hash_count;
> > >  	rte_hash_create;
> > >  	rte_hash_del_key;
> > > +	rte_hash_del_key_fixed;
> > >  	rte_hash_del_key_with_hash;
> > >  	rte_hash_find_existing;
> > >  	rte_hash_free;
> > > --
> > > 2.19.1
> > >
> > > -----邮件原件-----
> > > 发件人: Lilijun (Jerry)
> > > 发送时间: 2020年4月18日 18:00
> > > 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> > > <stable@dpdk.org>
> > > 主题: rte_hash bug: can't iterate all entries when deleting keys in
> > > rte_hash iterate loop.
> > >
> > > Hi all,
> > >
> > >     In my test, entries can't be cleanup in rte_hash table when
> > > deleting keys in rte_hash iterate loop. The test steps:
> > >     1.  create a hash table table1 with limit 30000, ext bucket
> > > enabled,  and insert 30000 entries into this hash table.
> > >     2.  create a larger hash table table2 with limit 60000, , ext
> > > bucket
> > enabled.
> > >     3.  iterate all entries of table1 and insert them to the table2.
> > > Insert new
> > > 10000 entries to this table2.
> > >     4.  Then flush all entries from table2 by deleting keys in
> > > rte_hash iterate loop. But there are still some keys leaked in table2.
> > Is there any reason for flushing table2 in this manner?
> > Is it possible to use 'rte_hash_reset' instead?
> >
> > >
> > >     From my analysis, the keys idx are stored in rte_hash main
> > > bucket key slots and extend bucket key stots.
> > >     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.
> > >
> > >     Now I retry the iterate and delete keys, that can avoid this bug.
> > >
> > >     Is there any ideas or solutions on this bug?   Thanks.
> > >
> > > Jerry.

Re: [dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Wang, Yipeng1]

> -----Original Message-----
> From: Lilijun (Jerry) <jerry.lilijun@huawei.com>
> Sent: Tuesday, May 5, 2020 6:10 PM
> To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> 'dev@dpdk.org' <dev@dpdk.org>
> Cc: wangyunjian <wangyunjian@huawei.com>; xudingke
> <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> <nd@arm.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>; nd
> <nd@arm.com>
> Subject: 答复: [dpdk-dev] [PATCH] lib/librte_hash: add
> rte_hash_del_key_fixed without compact
> 
> > -----邮件原件-----
> > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > 发送时间: 2020年5月6日 7:18
> > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > <dev@dpdk.org>
> > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > <nd@arm.com>; Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> > yipeng1.wang@intel.com; nd <nd@arm.com>
> > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> > without compact
> >
> > <snip>
> >
> > Adding Yipeng, maintainer for hash library
> >
> > >
> > > Thanks for your reply.
> > >
> > > Using rte_hash iterate and delete keys is to free the related data's
> memory.
> > > There are two reasons why rte_hash_reset() is not properly:
> > > 1)  the reset function just clear all keys, the key's related data are leaked.
> > That is a good point. I think this should be documented in the API.

[Yipeng]
By leaking, do you mean that you keep data in separate places and the pointers
to them are missed from table after reset? Can you keep data in an array and iterate that array instead? 
> >
> > > 2)  In some cases, I don't need delete all keys. Just some selected
> > > keys and data are deleted and released.
[Yipeng]
Could you keep a candidate list of keys you want to delete in another data structure
so you don’t need to iterate the whole hash table?

> > I understand the problem you have pointed out and understand how to
> > reproduce it. But, the use case is not clear to me. Can you please
> > explain the use case?
> [Lilijun (Jerry)]
> 
> As you know, the dpdk rte_hash use a fixed size table to store all keys/datas.
> The memory used by hash table is related with this fixed size.
> In my case, normally the count of keys is about 100,000 but sometimes the
> count may burst up to 30,000,000.
> In order to save memory usage, I create a small hash table with 100,000 size
> and replace to a bigger one with 30,000,000 size when there are more keys to
> be stored. Also when the key's count reduced to less than 100,000, I replace
> the hash table with a small one to save the memory.
[Yipeng]
Could you tell me more on the use case? Since insertion would also invalidate the
Iterator, do you insert keys only to new table during resizing?
 
> 
> >
> > >
> > > Jerry.
> > >
> > > -----邮件原件-----
> > > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > > 发送时间: 2020年4月29日 4:46
> > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > <dev@dpdk.org>
> > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > <nd@arm.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>;
> > nd
> > > <nd@arm.com>
> > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > rte_hash_del_key_fixed without compact
> > >
> > > <snip>
> > >
> > > Hi Jerry,
> > > 	Few questions inline.
> > >
> > > > Subject: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > rte_hash_del_key_fixed without compact
> > > >
> > > > The keys idx are stored in rte_hash main bucket key slots and
> > > > extend bucket key stots.
> > > > 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.
> > > >
> > > > ---
> > > >  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
> > > >  lib/librte_hash/rte_hash.h           |  5 +++++
> > > >  lib/librte_hash/rte_hash_version.map |  1 +
> > > >  3 files changed, 20 insertions(+), 5 deletions(-)
> > > >
> > > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > > > b/lib/librte_hash/rte_cuckoo_hash.c
> > > > index b52630b..2da3c1d 100644
> > > > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > > > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > > > @@ -1523,7 +1523,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;
> > > @@
> > > > -1541,7 +1541,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;
> > > > @@ -1553,7 +1554,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;
> > > > @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> > > > --- a/lib/librte_hash/rte_hash.h
> > > > +++ b/lib/librte_hash/rte_hash.h
> > > > @@ -297,6 +297,11 @@ 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);
> > > >
> > > > +
> > > > +/* for without compact */
> > > > +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 30cc086..1941d17 100644
> > > > --- a/lib/librte_hash/rte_hash_version.map
> > > > +++ b/lib/librte_hash/rte_hash_version.map
> > > > @@ -11,6 +11,7 @@ DPDK_20.0 {
> > > >  	rte_hash_count;
> > > >  	rte_hash_create;
> > > >  	rte_hash_del_key;
> > > > +	rte_hash_del_key_fixed;
> > > >  	rte_hash_del_key_with_hash;
> > > >  	rte_hash_find_existing;
> > > >  	rte_hash_free;
> > > > --
> > > > 2.19.1
> > > >
> > > > -----邮件原件-----
> > > > 发件人: Lilijun (Jerry)
> > > > 发送时间: 2020年4月18日 18:00
> > > > 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> > > > <stable@dpdk.org>
> > > > 主题: rte_hash bug: can't iterate all entries when deleting keys in
> > > > rte_hash iterate loop.
> > > >
> > > > Hi all,
> > > >
> > > >     In my test, entries can't be cleanup in rte_hash table when
> > > > deleting keys in rte_hash iterate loop. The test steps:
> > > >     1.  create a hash table table1 with limit 30000, ext bucket
> > > > enabled,  and insert 30000 entries into this hash table.
> > > >     2.  create a larger hash table table2 with limit 60000, , ext
> > > > bucket
> > > enabled.
> > > >     3.  iterate all entries of table1 and insert them to the table2.
> > > > Insert new
> > > > 10000 entries to this table2.
> > > >     4.  Then flush all entries from table2 by deleting keys in
> > > > rte_hash iterate loop. But there are still some keys leaked in table2.
> > > Is there any reason for flushing table2 in this manner?
> > > Is it possible to use 'rte_hash_reset' instead?
> > >
> > > >
> > > >     From my analysis, the keys idx are stored in rte_hash main
> > > > bucket key slots and extend bucket key stots.
> > > >     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.
> > > >
> > > >     Now I retry the iterate and delete keys, that can avoid this bug.
> > > >
> > > >     Is there any ideas or solutions on this bug?   Thanks.
> > > >
> > > > Jerry.
[Wang, Yipeng] 
Thanks Honnappa for adding me to the recipient list, I am sorry that I missed this patch previously.
In future you could add me to the recipient list for hash related patches/questions! Thanks!

Although it is not a bug to me, I think this is a valid issue and thanks for bringing it up.
I see the iterate function as like the iterator from C++ stl. Any insertion/delete should invalidate
the current iterator (insertion too, since insertion could move things around in cuckoo path).
From this point of view, by design there is no guarantee that the "next" pointer is still valid
after any insertion/deletion during the iteration. We at least should clarify this in the documentation.

That said, in c++ stl there is indeed a way to iterate and delete since it provides an erase function returning the next valid iterator.
I think we don’t have such capability in rte_hash now as you pointed out, and this is a gap you want to fill.

However, the proposed API " rte_hash_del_key_fixed" exposes the internals of the implementation.
The internal of hash lib is supposed to be a black box to the user. Although the issue is caused by "compaction",
the API should not expose that. I am thinking a function like the "erase" from stl which returns the next valid
iterator should be a better way. What do you think?

Resizing is an important feature that we always think to add into rte_hash. Feel free to propose resizing
Features too into rte_hash as you are already doing similar thing right now. 

BTW, you can add a [RFC] prefix to the subject line for future RFC patches.

Other questions/comments are inlined.
 

[dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Lilijun (Jerry)]

> -----邮件原件-----
> 发件人: Wang, Yipeng1 [mailto:yipeng1.wang@intel.com]
> 发送时间: 2020年5月13日 7:41
> 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; 'dev@dpdk.org' <dev@dpdk.org>
> 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> <nd@arm.com>; nd <nd@arm.com>
> 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> without compact
> 
> > -----Original Message-----
> > From: Lilijun (Jerry) <jerry.lilijun@huawei.com>
> > Sent: Tuesday, May 5, 2020 6:10 PM
> > To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> > 'dev@dpdk.org' <dev@dpdk.org>
> > Cc: wangyunjian <wangyunjian@huawei.com>; xudingke
> > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > <nd@arm.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>; nd
> <nd@arm.com>
> > Subject: 答复: [dpdk-dev] [PATCH] lib/librte_hash: add
> > rte_hash_del_key_fixed without compact
> >
> > > -----邮件原件-----
> > > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > > 发送时间: 2020年5月6日 7:18
> > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > <dev@dpdk.org>
> > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > <nd@arm.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>;
> > > yipeng1.wang@intel.com; nd <nd@arm.com>
> > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > rte_hash_del_key_fixed without compact
> > >
> > > <snip>
> > >
> > > Adding Yipeng, maintainer for hash library
> > >
> > > >
> > > > Thanks for your reply.
> > > >
> > > > Using rte_hash iterate and delete keys is to free the related
> > > > data's
> > memory.
> > > > There are two reasons why rte_hash_reset() is not properly:
> > > > 1)  the reset function just clear all keys, the key's related data are
> leaked.
> > > That is a good point. I think this should be documented in the API.
> 
> [Yipeng]
> By leaking, do you mean that you keep data in separate places and the
> pointers to them are missed from table after reset? Can you keep data in an
> array and iterate that array instead?
[Lilijun (Jerry)] 
Yes, the data pointers in rte hash table are missed after reset.
The solution using an external array to keep all data can avoid this problem, but it may introduce some extra memories cost.
It's better rte_hash can support iterate when inserting or deleting.
> > >
> > > > 2)  In some cases, I don't need delete all keys. Just some
> > > > selected keys and data are deleted and released.
> [Yipeng]
> Could you keep a candidate list of keys you want to delete in another data
> structure so you don’t need to iterate the whole hash table?
> 
[Lilijun (Jerry)] 
I need iterate the hash table at first and decide which key are candidate,  then delete the key/data instantly.
Of course, here I can keep those candidate keys and datas in a temporary list and delete them after the iterate is finished.
This may be a second choice for me although it became more complicated.
> > > I understand the problem you have pointed out and understand how to
> > > reproduce it. But, the use case is not clear to me. Can you please
> > > explain the use case?
> > [Lilijun (Jerry)]
> >
> > As you know, the dpdk rte_hash use a fixed size table to store all
> keys/datas.
> > The memory used by hash table is related with this fixed size.
> > In my case, normally the count of keys is about 100,000 but sometimes
> > the count may burst up to 30,000,000.
> > In order to save memory usage, I create a small hash table with
> > 100,000 size and replace to a bigger one with 30,000,000 size when
> > there are more keys to be stored. Also when the key's count reduced to
> > less than 100,000, I replace the hash table with a small one to save the
> memory.
> [Yipeng]
> Could you tell me more on the use case? Since insertion would also invalidate
> the Iterator, do you insert keys only to new table during resizing?
> 
[Lilijun (Jerry)] 
Yes, Insert only to new table. Because the resize process need take a write lock and the old table's key insertion are prevented by the lock now. 
Do you mean the key insertion may change other key's position by cuckoo hash algorithm and invalidate the iterator?
That maybe a new question I haven't met yet.
> >
> > >
> > > >
> > > > Jerry.
> > > >
> > > > -----邮件原件-----
> > > > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > > > 发送时间: 2020年4月29日 4:46
> > > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > > <dev@dpdk.org>
> > > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > > <nd@arm.com>; Honnappa Nagarahalli
> > <Honnappa.Nagarahalli@arm.com>;
> > > nd
> > > > <nd@arm.com>
> > > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > rte_hash_del_key_fixed without compact
> > > >
> > > > <snip>
> > > >
> > > > Hi Jerry,
> > > > 	Few questions inline.
> > > >
> > > > > Subject: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > > rte_hash_del_key_fixed without compact
> > > > >
> > > > > The keys idx are stored in rte_hash main bucket key slots and
> > > > > extend bucket key stots.
> > > > > 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.
> > > > >
> > > > > ---
> > > > >  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
> > > > >  lib/librte_hash/rte_hash.h           |  5 +++++
> > > > >  lib/librte_hash/rte_hash_version.map |  1 +
> > > > >  3 files changed, 20 insertions(+), 5 deletions(-)
> > > > >
> > > > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > > > > b/lib/librte_hash/rte_cuckoo_hash.c
> > > > > index b52630b..2da3c1d 100644
> > > > > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > > > > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > > > > @@ -1523,7 +1523,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;
> > > > @@
> > > > > -1541,7 +1541,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;
> > > > > @@ -1553,7 +1554,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;
> > > > > @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> > > > > --- a/lib/librte_hash/rte_hash.h
> > > > > +++ b/lib/librte_hash/rte_hash.h
> > > > > @@ -297,6 +297,11 @@ 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);
> > > > >
> > > > > +
> > > > > +/* for without compact */
> > > > > +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 30cc086..1941d17 100644
> > > > > --- a/lib/librte_hash/rte_hash_version.map
> > > > > +++ b/lib/librte_hash/rte_hash_version.map
> > > > > @@ -11,6 +11,7 @@ DPDK_20.0 {
> > > > >  	rte_hash_count;
> > > > >  	rte_hash_create;
> > > > >  	rte_hash_del_key;
> > > > > +	rte_hash_del_key_fixed;
> > > > >  	rte_hash_del_key_with_hash;
> > > > >  	rte_hash_find_existing;
> > > > >  	rte_hash_free;
> > > > > --
> > > > > 2.19.1
> > > > >
> > > > > -----邮件原件-----
> > > > > 发件人: Lilijun (Jerry)
> > > > > 发送时间: 2020年4月18日 18:00
> > > > > 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> > > > > <stable@dpdk.org>
> > > > > 主题: rte_hash bug: can't iterate all entries when deleting keys
> > > > > in rte_hash iterate loop.
> > > > >
> > > > > Hi all,
> > > > >
> > > > >     In my test, entries can't be cleanup in rte_hash table when
> > > > > deleting keys in rte_hash iterate loop. The test steps:
> > > > >     1.  create a hash table table1 with limit 30000, ext bucket
> > > > > enabled,  and insert 30000 entries into this hash table.
> > > > >     2.  create a larger hash table table2 with limit 60000, ,
> > > > > ext bucket
> > > > enabled.
> > > > >     3.  iterate all entries of table1 and insert them to the table2.
> > > > > Insert new
> > > > > 10000 entries to this table2.
> > > > >     4.  Then flush all entries from table2 by deleting keys in
> > > > > rte_hash iterate loop. But there are still some keys leaked in table2.
> > > > Is there any reason for flushing table2 in this manner?
> > > > Is it possible to use 'rte_hash_reset' instead?
> > > >
> > > > >
> > > > >     From my analysis, the keys idx are stored in rte_hash main
> > > > > bucket key slots and extend bucket key stots.
> > > > >     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.
> > > > >
> > > > >     Now I retry the iterate and delete keys, that can avoid this bug.
> > > > >
> > > > >     Is there any ideas or solutions on this bug?   Thanks.
> > > > >
> > > > > Jerry.
> [Wang, Yipeng]
> Thanks Honnappa for adding me to the recipient list, I am sorry that I missed
> this patch previously.
> In future you could add me to the recipient list for hash related
> patches/questions! Thanks!
> 
> Although it is not a bug to me, I think this is a valid issue and thanks for
> bringing it up.
> I see the iterate function as like the iterator from C++ stl. Any
> insertion/delete should invalidate the current iterator (insertion too, since
> insertion could move things around in cuckoo path).
> From this point of view, by design there is no guarantee that the "next"
> pointer is still valid after any insertion/deletion during the iteration. We at
> least should clarify this in the documentation.
> 
> That said, in c++ stl there is indeed a way to iterate and delete since it
> provides an erase function returning the next valid iterator.
> I think we don’t have such capability in rte_hash now as you pointed out, and
> this is a gap you want to fill.
> 
> However, the proposed API " rte_hash_del_key_fixed" exposes the
> internals of the implementation.
> The internal of hash lib is supposed to be a black box to the user. Although
> the issue is caused by "compaction", the API should not expose that. I am
> thinking a function like the "erase" from stl which returns the next valid
> iterator should be a better way. What do you think?
> 
[Lilijun (Jerry)] 
Yes, I am agree with your views. Some "erase" function may be better for this cases.

> Resizing is an important feature that we always think to add into rte_hash.
> Feel free to propose resizing Features too into rte_hash as you are already
> doing similar thing right now.
> 
[Lilijun (Jerry)] 
Yes, the memory cost by rte hash may be waste when the keys usage is not high in common.
Resize features can figure out that problem in rte_hash. Thanks for your advice.

> BTW, you can add a [RFC] prefix to the subject line for future RFC patches.
> 
> Other questions/comments are inlined.
> 

Re: [dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Wang, Yipeng1]

> -----Original Message-----
> From: Lilijun (Jerry) <jerry.lilijun@huawei.com>
> Sent: Tuesday, May 12, 2020 6:28 PM
> To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; 'dev@dpdk.org' <dev@dpdk.org>
> Cc: wangyunjian <wangyunjian@huawei.com>; xudingke
> <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> <nd@arm.com>; nd <nd@arm.com>
> Subject: 答复: [dpdk-dev] [PATCH] lib/librte_hash: add
> rte_hash_del_key_fixed without compact

<...>

> > [Yipeng]
> > Could you tell me more on the use case? Since insertion would also
> > invalidate the Iterator, do you insert keys only to new table during resizing?
> >
> [Lilijun (Jerry)]
> Yes, Insert only to new table. Because the resize process need take a write
> lock and the old table's key insertion are prevented by the lock now.
> Do you mean the key insertion may change other key's position by cuckoo
> hash algorithm and invalidate the iterator?
> That maybe a new question I haven't met yet.

[Wang, Yipeng] 
For cuckoo algorithm, if the table is relatively full, new inserted key could move other keys around in the table.
For example, when I insert A, A could move B to B's alternative bucket to make
space for A, that’s where the name "cuckoo" comes from. 😊
So if you insert keys into table, the iterators should be invalidated too. But as you said you only insert keys
to new table while you iterate only the old table right?

Re: [dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Thomas Monjalon]

Sorry for not following the full thread.
What is the conclusion please?

13/05/2020 03:28, Lilijun (Jerry):
> 
> > -----邮件原件-----
> > 发件人: Wang, Yipeng1 [mailto:yipeng1.wang@intel.com]
> > 发送时间: 2020年5月13日 7:41
> > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; Honnappa Nagarahalli
> > <Honnappa.Nagarahalli@arm.com>; 'dev@dpdk.org' <dev@dpdk.org>
> > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > <nd@arm.com>; nd <nd@arm.com>
> > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> > without compact
> > 
> > > -----Original Message-----
> > > From: Lilijun (Jerry) <jerry.lilijun@huawei.com>
> > > Sent: Tuesday, May 5, 2020 6:10 PM
> > > To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> > > 'dev@dpdk.org' <dev@dpdk.org>
> > > Cc: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > <nd@arm.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>; nd
> > <nd@arm.com>
> > > Subject: 答复: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > rte_hash_del_key_fixed without compact
> > >
> > > > -----邮件原件-----
> > > > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > > > 发送时间: 2020年5月6日 7:18
> > > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > > <dev@dpdk.org>
> > > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > > <nd@arm.com>; Honnappa Nagarahalli
> > <Honnappa.Nagarahalli@arm.com>;
> > > > yipeng1.wang@intel.com; nd <nd@arm.com>
> > > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > rte_hash_del_key_fixed without compact
> > > >
> > > > <snip>
> > > >
> > > > Adding Yipeng, maintainer for hash library
> > > >
> > > > >
> > > > > Thanks for your reply.
> > > > >
> > > > > Using rte_hash iterate and delete keys is to free the related
> > > > > data's
> > > memory.
> > > > > There are two reasons why rte_hash_reset() is not properly:
> > > > > 1)  the reset function just clear all keys, the key's related data are
> > leaked.
> > > > That is a good point. I think this should be documented in the API.
> > 
> > [Yipeng]
> > By leaking, do you mean that you keep data in separate places and the
> > pointers to them are missed from table after reset? Can you keep data in an
> > array and iterate that array instead?
> [Lilijun (Jerry)] 
> Yes, the data pointers in rte hash table are missed after reset.
> The solution using an external array to keep all data can avoid this problem, but it may introduce some extra memories cost.
> It's better rte_hash can support iterate when inserting or deleting.
> > > >
> > > > > 2)  In some cases, I don't need delete all keys. Just some
> > > > > selected keys and data are deleted and released.
> > [Yipeng]
> > Could you keep a candidate list of keys you want to delete in another data
> > structure so you don’t need to iterate the whole hash table?
> > 
> [Lilijun (Jerry)] 
> I need iterate the hash table at first and decide which key are candidate,  then delete the key/data instantly.
> Of course, here I can keep those candidate keys and datas in a temporary list and delete them after the iterate is finished.
> This may be a second choice for me although it became more complicated.
> > > > I understand the problem you have pointed out and understand how to
> > > > reproduce it. But, the use case is not clear to me. Can you please
> > > > explain the use case?
> > > [Lilijun (Jerry)]
> > >
> > > As you know, the dpdk rte_hash use a fixed size table to store all
> > keys/datas.
> > > The memory used by hash table is related with this fixed size.
> > > In my case, normally the count of keys is about 100,000 but sometimes
> > > the count may burst up to 30,000,000.
> > > In order to save memory usage, I create a small hash table with
> > > 100,000 size and replace to a bigger one with 30,000,000 size when
> > > there are more keys to be stored. Also when the key's count reduced to
> > > less than 100,000, I replace the hash table with a small one to save the
> > memory.
> > [Yipeng]
> > Could you tell me more on the use case? Since insertion would also invalidate
> > the Iterator, do you insert keys only to new table during resizing?
> > 
> [Lilijun (Jerry)] 
> Yes, Insert only to new table. Because the resize process need take a write lock and the old table's key insertion are prevented by the lock now. 
> Do you mean the key insertion may change other key's position by cuckoo hash algorithm and invalidate the iterator?
> That maybe a new question I haven't met yet.
> > >
> > > >
> > > > >
> > > > > Jerry.
> > > > >
> > > > > -----邮件原件-----
> > > > > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > > > > 发送时间: 2020年4月29日 4:46
> > > > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > > > <dev@dpdk.org>
> > > > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > > > <nd@arm.com>; Honnappa Nagarahalli
> > > <Honnappa.Nagarahalli@arm.com>;
> > > > nd
> > > > > <nd@arm.com>
> > > > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > > rte_hash_del_key_fixed without compact
> > > > >
> > > > > <snip>
> > > > >
> > > > > Hi Jerry,
> > > > > 	Few questions inline.
> > > > >
> > > > > > Subject: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > > > rte_hash_del_key_fixed without compact
> > > > > >
> > > > > > The keys idx are stored in rte_hash main bucket key slots and
> > > > > > extend bucket key stots.
> > > > > > 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.
> > > > > >
> > > > > > ---
> > > > > >  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
> > > > > >  lib/librte_hash/rte_hash.h           |  5 +++++
> > > > > >  lib/librte_hash/rte_hash_version.map |  1 +
> > > > > >  3 files changed, 20 insertions(+), 5 deletions(-)
> > > > > >
> > > > > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > > > > > b/lib/librte_hash/rte_cuckoo_hash.c
> > > > > > index b52630b..2da3c1d 100644
> > > > > > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > > > > > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > > > > > @@ -1523,7 +1523,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;
> > > > > @@
> > > > > > -1541,7 +1541,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;
> > > > > > @@ -1553,7 +1554,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;
> > > > > > @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> > > > > > --- a/lib/librte_hash/rte_hash.h
> > > > > > +++ b/lib/librte_hash/rte_hash.h
> > > > > > @@ -297,6 +297,11 @@ 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);
> > > > > >
> > > > > > +
> > > > > > +/* for without compact */
> > > > > > +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 30cc086..1941d17 100644
> > > > > > --- a/lib/librte_hash/rte_hash_version.map
> > > > > > +++ b/lib/librte_hash/rte_hash_version.map
> > > > > > @@ -11,6 +11,7 @@ DPDK_20.0 {
> > > > > >  	rte_hash_count;
> > > > > >  	rte_hash_create;
> > > > > >  	rte_hash_del_key;
> > > > > > +	rte_hash_del_key_fixed;
> > > > > >  	rte_hash_del_key_with_hash;
> > > > > >  	rte_hash_find_existing;
> > > > > >  	rte_hash_free;
> > > > > > --
> > > > > > 2.19.1
> > > > > >
> > > > > > -----邮件原件-----
> > > > > > 发件人: Lilijun (Jerry)
> > > > > > 发送时间: 2020年4月18日 18:00
> > > > > > 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> > > > > > <stable@dpdk.org>
> > > > > > 主题: rte_hash bug: can't iterate all entries when deleting keys
> > > > > > in rte_hash iterate loop.
> > > > > >
> > > > > > Hi all,
> > > > > >
> > > > > >     In my test, entries can't be cleanup in rte_hash table when
> > > > > > deleting keys in rte_hash iterate loop. The test steps:
> > > > > >     1.  create a hash table table1 with limit 30000, ext bucket
> > > > > > enabled,  and insert 30000 entries into this hash table.
> > > > > >     2.  create a larger hash table table2 with limit 60000, ,
> > > > > > ext bucket
> > > > > enabled.
> > > > > >     3.  iterate all entries of table1 and insert them to the table2.
> > > > > > Insert new
> > > > > > 10000 entries to this table2.
> > > > > >     4.  Then flush all entries from table2 by deleting keys in
> > > > > > rte_hash iterate loop. But there are still some keys leaked in table2.
> > > > > Is there any reason for flushing table2 in this manner?
> > > > > Is it possible to use 'rte_hash_reset' instead?
> > > > >
> > > > > >
> > > > > >     From my analysis, the keys idx are stored in rte_hash main
> > > > > > bucket key slots and extend bucket key stots.
> > > > > >     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.
> > > > > >
> > > > > >     Now I retry the iterate and delete keys, that can avoid this bug.
> > > > > >
> > > > > >     Is there any ideas or solutions on this bug?   Thanks.
> > > > > >
> > > > > > Jerry.
> > [Wang, Yipeng]
> > Thanks Honnappa for adding me to the recipient list, I am sorry that I missed
> > this patch previously.
> > In future you could add me to the recipient list for hash related
> > patches/questions! Thanks!
> > 
> > Although it is not a bug to me, I think this is a valid issue and thanks for
> > bringing it up.
> > I see the iterate function as like the iterator from C++ stl. Any
> > insertion/delete should invalidate the current iterator (insertion too, since
> > insertion could move things around in cuckoo path).
> > From this point of view, by design there is no guarantee that the "next"
> > pointer is still valid after any insertion/deletion during the iteration. We at
> > least should clarify this in the documentation.
> > 
> > That said, in c++ stl there is indeed a way to iterate and delete since it
> > provides an erase function returning the next valid iterator.
> > I think we don’t have such capability in rte_hash now as you pointed out, and
> > this is a gap you want to fill.
> > 
> > However, the proposed API " rte_hash_del_key_fixed" exposes the
> > internals of the implementation.
> > The internal of hash lib is supposed to be a black box to the user. Although
> > the issue is caused by "compaction", the API should not expose that. I am
> > thinking a function like the "erase" from stl which returns the next valid
> > iterator should be a better way. What do you think?
> > 
> [Lilijun (Jerry)] 
> Yes, I am agree with your views. Some "erase" function may be better for this cases.
> 
> > Resizing is an important feature that we always think to add into rte_hash.
> > Feel free to propose resizing Features too into rte_hash as you are already
> > doing similar thing right now.
> > 
> [Lilijun (Jerry)] 
> Yes, the memory cost by rte hash may be waste when the keys usage is not high in common.
> Resize features can figure out that problem in rte_hash. Thanks for your advice.
> 
> > BTW, you can add a [RFC] prefix to the subject line for future RFC patches.
> > 
> > Other questions/comments are inlined.

Re: [dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Wang, Yipeng1]

> -----Original Message-----
> From: Thomas Monjalon <thomas@monjalon.net>
> Sent: Wednesday, March 24, 2021 2:33 PM
> To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; Lilijun (Jerry) <jerry.lilijun@huawei.com>
> Cc: 'dev@dpdk.org' <dev@dpdk.org>; stable@dpdk.org; wangyunjian
> <wangyunjian@huawei.com>; xudingke <xudingke@huawei.com>
> Subject: Re: [dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add
> rte_hash_del_key_fixed without compact
> 
> Sorry for not following the full thread.
> What is the conclusion please?
> 
[Wang, Yipeng] 
Hi, I reviewed my previous comment, I recall that this patch is an RFC for a new API.

The proposed API is not directly appliable for now since it discloses the internals of the implementation to user.

I am waiting for Jerry to post a new RFC, and more details of the use case to motivate the change.
Thomas, you could change the status accordingly.


> 13/05/2020 03:28, Lilijun (Jerry):
> >
> > > -----邮件原件-----
> > > 发件人: Wang, Yipeng1 [mailto:yipeng1.wang@intel.com]
> > > 发送时间: 2020年5月13日 7:41
> > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; Honnappa
> > > Nagarahalli <Honnappa.Nagarahalli@arm.com>; 'dev@dpdk.org'
> > > <dev@dpdk.org>
> > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > <nd@arm.com>; nd <nd@arm.com>
> > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > rte_hash_del_key_fixed without compact
> > >
> > > > -----Original Message-----
> > > > From: Lilijun (Jerry) <jerry.lilijun@huawei.com>
> > > > Sent: Tuesday, May 5, 2020 6:10 PM
> > > > To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> > > > 'dev@dpdk.org' <dev@dpdk.org>
> > > > Cc: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > > <nd@arm.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>; nd
> > > <nd@arm.com>
> > > > Subject: 答复: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > rte_hash_del_key_fixed without compact
> > > >
> > > > > -----邮件原件-----
> > > > > 发件人: Honnappa Nagarahalli
> [mailto:Honnappa.Nagarahalli@arm.com]
> > > > > 发送时间: 2020年5月6日 7:18
> > > > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > > > <dev@dpdk.org>
> > > > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > > > <nd@arm.com>; Honnappa Nagarahalli
> > > <Honnappa.Nagarahalli@arm.com>;
> > > > > yipeng1.wang@intel.com; nd <nd@arm.com>
> > > > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > > rte_hash_del_key_fixed without compact
> > > > >
> > > > > <snip>
> > > > >
> > > > > Adding Yipeng, maintainer for hash library
> > > > >
> > > > > >
> > > > > > Thanks for your reply.
> > > > > >
> > > > > > Using rte_hash iterate and delete keys is to free the related
> > > > > > data's
> > > > memory.
> > > > > > There are two reasons why rte_hash_reset() is not properly:
> > > > > > 1)  the reset function just clear all keys, the key's related
> > > > > > data are
> > > leaked.
> > > > > That is a good point. I think this should be documented in the API.
> > >
> > > [Yipeng]
> > > By leaking, do you mean that you keep data in separate places and
> > > the pointers to them are missed from table after reset? Can you keep
> > > data in an array and iterate that array instead?
> > [Lilijun (Jerry)]
> > Yes, the data pointers in rte hash table are missed after reset.
> > The solution using an external array to keep all data can avoid this problem,
> but it may introduce some extra memories cost.
> > It's better rte_hash can support iterate when inserting or deleting.
> > > > >
> > > > > > 2)  In some cases, I don't need delete all keys. Just some
> > > > > > selected keys and data are deleted and released.
> > > [Yipeng]
> > > Could you keep a candidate list of keys you want to delete in
> > > another data structure so you don’t need to iterate the whole hash table?
> > >
> > [Lilijun (Jerry)]
> > I need iterate the hash table at first and decide which key are candidate,
> then delete the key/data instantly.
> > Of course, here I can keep those candidate keys and datas in a temporary
> list and delete them after the iterate is finished.
> > This may be a second choice for me although it became more complicated.
> > > > > I understand the problem you have pointed out and understand how
> > > > > to reproduce it. But, the use case is not clear to me. Can you
> > > > > please explain the use case?
> > > > [Lilijun (Jerry)]
> > > >
> > > > As you know, the dpdk rte_hash use a fixed size table to store all
> > > keys/datas.
> > > > The memory used by hash table is related with this fixed size.
> > > > In my case, normally the count of keys is about 100,000 but
> > > > sometimes the count may burst up to 30,000,000.
> > > > In order to save memory usage, I create a small hash table with
> > > > 100,000 size and replace to a bigger one with 30,000,000 size when
> > > > there are more keys to be stored. Also when the key's count
> > > > reduced to less than 100,000, I replace the hash table with a
> > > > small one to save the
> > > memory.
> > > [Yipeng]
> > > Could you tell me more on the use case? Since insertion would also
> > > invalidate the Iterator, do you insert keys only to new table during
> resizing?
> > >
> > [Lilijun (Jerry)]
> > Yes, Insert only to new table. Because the resize process need take a write
> lock and the old table's key insertion are prevented by the lock now.
> > Do you mean the key insertion may change other key's position by cuckoo
> hash algorithm and invalidate the iterator?
> > That maybe a new question I haven't met yet.
> > > >
> > > > >
> > > > > >
> > > > > > Jerry.
> > > > > >
> > > > > > -----邮件原件-----
> > > > > > 发件人: Honnappa Nagarahalli
> > > > > > [mailto:Honnappa.Nagarahalli@arm.com]
> > > > > > 发送时间: 2020年4月29日 4:46
> > > > > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > > > > <dev@dpdk.org>
> > > > > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > > > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>;
> nd
> > > > > > <nd@arm.com>; Honnappa Nagarahalli
> > > > <Honnappa.Nagarahalli@arm.com>;
> > > > > nd
> > > > > > <nd@arm.com>
> > > > > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > > > rte_hash_del_key_fixed without compact
> > > > > >
> > > > > > <snip>
> > > > > >
> > > > > > Hi Jerry,
> > > > > > 	Few questions inline.
> > > > > >
> > > > > > > Subject: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > > > > rte_hash_del_key_fixed without compact
> > > > > > >
> > > > > > > The keys idx are stored in rte_hash main bucket key slots
> > > > > > > and extend bucket key stots.
> > > > > > > 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.
> > > > > > >
> > > > > > > ---
> > > > > > >  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
> > > > > > >  lib/librte_hash/rte_hash.h           |  5 +++++
> > > > > > >  lib/librte_hash/rte_hash_version.map |  1 +
> > > > > > >  3 files changed, 20 insertions(+), 5 deletions(-)
> > > > > > >
> > > > > > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > > > > > > b/lib/librte_hash/rte_cuckoo_hash.c
> > > > > > > index b52630b..2da3c1d 100644
> > > > > > > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > > > > > > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > > > > > > @@ -1523,7 +1523,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;
> > > > > > @@
> > > > > > > -1541,7 +1541,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;
> > > > > > > @@ -1553,7 +1554,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;
> > > > > > > @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> > > > > > > --- a/lib/librte_hash/rte_hash.h
> > > > > > > +++ b/lib/librte_hash/rte_hash.h
> > > > > > > @@ -297,6 +297,11 @@ 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);
> > > > > > >
> > > > > > > +
> > > > > > > +/* for without compact */
> > > > > > > +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 30cc086..1941d17 100644
> > > > > > > --- a/lib/librte_hash/rte_hash_version.map
> > > > > > > +++ b/lib/librte_hash/rte_hash_version.map
> > > > > > > @@ -11,6 +11,7 @@ DPDK_20.0 {
> > > > > > >  	rte_hash_count;
> > > > > > >  	rte_hash_create;
> > > > > > >  	rte_hash_del_key;
> > > > > > > +	rte_hash_del_key_fixed;
> > > > > > >  	rte_hash_del_key_with_hash;
> > > > > > >  	rte_hash_find_existing;
> > > > > > >  	rte_hash_free;
> > > > > > > --
> > > > > > > 2.19.1
> > > > > > >
> > > > > > > -----邮件原件-----
> > > > > > > 发件人: Lilijun (Jerry)
> > > > > > > 发送时间: 2020年4月18日 18:00
> > > > > > > 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> > > > > > > <stable@dpdk.org>
> > > > > > > 主题: rte_hash bug: can't iterate all entries when deleting
> > > > > > > keys in rte_hash iterate loop.
> > > > > > >
> > > > > > > Hi all,
> > > > > > >
> > > > > > >     In my test, entries can't be cleanup in rte_hash table
> > > > > > > when deleting keys in rte_hash iterate loop. The test steps:
> > > > > > >     1.  create a hash table table1 with limit 30000, ext
> > > > > > > bucket enabled,  and insert 30000 entries into this hash table.
> > > > > > >     2.  create a larger hash table table2 with limit 60000,
> > > > > > > , ext bucket
> > > > > > enabled.
> > > > > > >     3.  iterate all entries of table1 and insert them to the table2.
> > > > > > > Insert new
> > > > > > > 10000 entries to this table2.
> > > > > > >     4.  Then flush all entries from table2 by deleting keys
> > > > > > > in rte_hash iterate loop. But there are still some keys leaked in
> table2.
> > > > > > Is there any reason for flushing table2 in this manner?
> > > > > > Is it possible to use 'rte_hash_reset' instead?
> > > > > >
> > > > > > >
> > > > > > >     From my analysis, the keys idx are stored in rte_hash
> > > > > > > main bucket key slots and extend bucket key stots.
> > > > > > >     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.
> > > > > > >
> > > > > > >     Now I retry the iterate and delete keys, that can avoid this bug.
> > > > > > >
> > > > > > >     Is there any ideas or solutions on this bug?   Thanks.
> > > > > > >
> > > > > > > Jerry.
> > > [Wang, Yipeng]
> > > Thanks Honnappa for adding me to the recipient list, I am sorry that
> > > I missed this patch previously.
> > > In future you could add me to the recipient list for hash related
> > > patches/questions! Thanks!
> > >
> > > Although it is not a bug to me, I think this is a valid issue and
> > > thanks for bringing it up.
> > > I see the iterate function as like the iterator from C++ stl. Any
> > > insertion/delete should invalidate the current iterator (insertion
> > > too, since insertion could move things around in cuckoo path).
> > > From this point of view, by design there is no guarantee that the "next"
> > > pointer is still valid after any insertion/deletion during the
> > > iteration. We at least should clarify this in the documentation.
> > >
> > > That said, in c++ stl there is indeed a way to iterate and delete
> > > since it provides an erase function returning the next valid iterator.
> > > I think we don’t have such capability in rte_hash now as you pointed
> > > out, and this is a gap you want to fill.
> > >
> > > However, the proposed API " rte_hash_del_key_fixed" exposes the
> > > internals of the implementation.
> > > The internal of hash lib is supposed to be a black box to the user.
> > > Although the issue is caused by "compaction", the API should not
> > > expose that. I am thinking a function like the "erase" from stl
> > > which returns the next valid iterator should be a better way. What do you
> think?
> > >
> > [Lilijun (Jerry)]
> > Yes, I am agree with your views. Some "erase" function may be better for
> this cases.
> >
> > > Resizing is an important feature that we always think to add into rte_hash.
> > > Feel free to propose resizing Features too into rte_hash as you are
> > > already doing similar thing right now.
> > >
> > [Lilijun (Jerry)]
> > Yes, the memory cost by rte hash may be waste when the keys usage is not
> high in common.
> > Resize features can figure out that problem in rte_hash. Thanks for your
> advice.
> >
> > > BTW, you can add a [RFC] prefix to the subject line for future RFC patches.
> > >
> > > Other questions/comments are inlined.
> 
> 

Re: [dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Thomas Monjalon]

25/03/2021 00:25, Wang, Yipeng1:
> Hi, I reviewed my previous comment, I recall that this patch is an RFC for a new API.
> 
> The proposed API is not directly appliable for now since it discloses the internals of the implementation to user.
> 
> I am waiting for Jerry to post a new RFC, and more details of the use case to motivate the change.
> Thomas, you could change the status accordingly.

Thanks, status updated:
https://patches.dpdk.org/project/dpdk/patch/40280F65B1B0B44E8089ED31C01616EBA49921F2@dggeml529-mbx.china.huawei.com/
https://patches.dpdk.org/project/dpdk/patch/40280F65B1B0B44E8089ED31C01616EBA49922F6@dggeml529-mbx.china.huawei.com/

Re: [dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Honnappa Nagarahalli]

> > <snip>
> >
> > Adding Yipeng, maintainer for hash library
> >
> > >
> > > Thanks for your reply.
> > >
> > > Using rte_hash iterate and delete keys is to free the related data's
> memory.
> > > There are two reasons why rte_hash_reset() is not properly:
> > > 1)  the reset function just clear all keys, the key's related data are leaked.
> > That is a good point. I think this should be documented in the API.
> >
> > > 2)  In some cases, I don't need delete all keys. Just some selected
> > > keys and data are deleted and released.
> > I understand the problem you have pointed out and understand how to
> > reproduce it. But, the use case is not clear to me. Can you please
> > explain the use case?
> [Lilijun (Jerry)]
> 
> As you know, the dpdk rte_hash use a fixed size table to store all keys/datas.
> The memory used by hash table is related with this fixed size.
> In my case, normally the count of keys is about 100,000 but sometimes the
> count may burst up to 30,000,000.
> In order to save memory usage, I create a small hash table with 100,000 size
> and replace to a bigger one with 30,000,000 size when there are more keys to
> be stored. Also when the key's count reduced to less than 100,000, I replace
> the hash table with a small one to save the memory.
Thank you for explaining this. What happens to the reader when you are deleting from old table and inserting in the new one? Which table does the reader lookup from?

> 
> >
> > >
> > > Jerry.
> > >
> > > -----邮件原件-----
> > > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > > 发送时间: 2020年4月29日 4:46
> > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > <dev@dpdk.org>
> > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > <nd@arm.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>;
> > nd
> > > <nd@arm.com>
> > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > rte_hash_del_key_fixed without compact
> > >
> > > <snip>
> > >
> > > Hi Jerry,
> > > 	Few questions inline.
> > >
> > > > Subject: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > rte_hash_del_key_fixed without compact
> > > >
> > > > The keys idx are stored in rte_hash main bucket key slots and
> > > > extend bucket key stots.
> > > > 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.
> > > >
> > > > ---
> > > >  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
> > > >  lib/librte_hash/rte_hash.h           |  5 +++++
> > > >  lib/librte_hash/rte_hash_version.map |  1 +
> > > >  3 files changed, 20 insertions(+), 5 deletions(-)
> > > >
> > > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > > > b/lib/librte_hash/rte_cuckoo_hash.c
> > > > index b52630b..2da3c1d 100644
> > > > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > > > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > > > @@ -1523,7 +1523,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;
> > > @@
> > > > -1541,7 +1541,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;
> > > > @@ -1553,7 +1554,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;
> > > > @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> > > > --- a/lib/librte_hash/rte_hash.h
> > > > +++ b/lib/librte_hash/rte_hash.h
> > > > @@ -297,6 +297,11 @@ 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);
> > > >
> > > > +
> > > > +/* for without compact */
> > > > +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 30cc086..1941d17 100644
> > > > --- a/lib/librte_hash/rte_hash_version.map
> > > > +++ b/lib/librte_hash/rte_hash_version.map
> > > > @@ -11,6 +11,7 @@ DPDK_20.0 {
> > > >  	rte_hash_count;
> > > >  	rte_hash_create;
> > > >  	rte_hash_del_key;
> > > > +	rte_hash_del_key_fixed;
> > > >  	rte_hash_del_key_with_hash;
> > > >  	rte_hash_find_existing;
> > > >  	rte_hash_free;
> > > > --
> > > > 2.19.1
> > > >
> > > > -----邮件原件-----
> > > > 发件人: Lilijun (Jerry)
> > > > 发送时间: 2020年4月18日 18:00
> > > > 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> > > > <stable@dpdk.org>
> > > > 主题: rte_hash bug: can't iterate all entries when deleting keys in
> > > > rte_hash iterate loop.
> > > >
> > > > Hi all,
> > > >
> > > >     In my test, entries can't be cleanup in rte_hash table when
> > > > deleting keys in rte_hash iterate loop. The test steps:
> > > >     1.  create a hash table table1 with limit 30000, ext bucket
> > > > enabled,  and insert 30000 entries into this hash table.
> > > >     2.  create a larger hash table table2 with limit 60000, , ext
> > > > bucket
> > > enabled.
> > > >     3.  iterate all entries of table1 and insert them to the table2.
> > > > Insert new
> > > > 10000 entries to this table2.
> > > >     4.  Then flush all entries from table2 by deleting keys in
> > > > rte_hash iterate loop. But there are still some keys leaked in table2.
> > > Is there any reason for flushing table2 in this manner?
> > > Is it possible to use 'rte_hash_reset' instead?
> > >
> > > >
> > > >     From my analysis, the keys idx are stored in rte_hash main
> > > > bucket key slots and extend bucket key stots.
> > > >     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.
> > > >
> > > >     Now I retry the iterate and delete keys, that can avoid this bug.
> > > >
> > > >     Is there any ideas or solutions on this bug?   Thanks.
> > > >
> > > > Jerry.

[dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Lilijun (Jerry)]

> -----邮件原件-----
> 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> 发送时间: 2020年5月14日 3:27
> 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> <dev@dpdk.org>
> 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> <nd@arm.com>; yipeng1.wang@intel.com; nd <nd@arm.com>; Honnappa
> Nagarahalli <Honnappa.Nagarahalli@arm.com>; nd <nd@arm.com>
> 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> without compact
> 
> > > <snip>
> > >
> > > Adding Yipeng, maintainer for hash library
> > >
> > > >
> > > > Thanks for your reply.
> > > >
> > > > Using rte_hash iterate and delete keys is to free the related
> > > > data's
> > memory.
> > > > There are two reasons why rte_hash_reset() is not properly:
> > > > 1)  the reset function just clear all keys, the key's related data are
> leaked.
> > > That is a good point. I think this should be documented in the API.
> > >
> > > > 2)  In some cases, I don't need delete all keys. Just some
> > > > selected keys and data are deleted and released.
> > > I understand the problem you have pointed out and understand how to
> > > reproduce it. But, the use case is not clear to me. Can you please
> > > explain the use case?
> > [Lilijun (Jerry)]
> >
> > As you know, the dpdk rte_hash use a fixed size table to store all
> keys/datas.
> > The memory used by hash table is related with this fixed size.
> > In my case, normally the count of keys is about 100,000 but sometimes
> > the count may burst up to 30,000,000.
> > In order to save memory usage, I create a small hash table with
> > 100,000 size and replace to a bigger one with 30,000,000 size when
> > there are more keys to be stored. Also when the key's count reduced to
> > less than 100,000, I replace the hash table with a small one to save the
> memory.
> Thank you for explaining this. What happens to the reader when you are
> deleting from old table and inserting in the new one? Which table does the
> reader lookup from?
[Lilijun (Jerry)] 
Lookup functions works well at any time. The problem is in rte_hash_iterate() functions. Some example codes like this:
*next = 0;
//If rh has 10000 entries at first.
while ((idx = rte_hash_iterate(rh, key, data, next)) >= 0) {
              rte_hash_del_key(rh, key);  //BUT HERE maybe only delete 9990 keys !!!
              free(*data);
}
//There are still 10 key/datas not freed and will be leaked.
rte_hash_free(rh);
> 
> >
> > >
> > > >
> > > > Jerry.
> > > >
> > > > -----邮件原件-----
> > > > 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > > > 发送时间: 2020年4月29日 4:46
> > > > 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> > > > <dev@dpdk.org>
> > > > 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> > > > <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> > > > <nd@arm.com>; Honnappa Nagarahalli
> > <Honnappa.Nagarahalli@arm.com>;
> > > nd
> > > > <nd@arm.com>
> > > > 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > rte_hash_del_key_fixed without compact
> > > >
> > > > <snip>
> > > >
> > > > Hi Jerry,
> > > > 	Few questions inline.
> > > >
> > > > > Subject: [dpdk-dev] [PATCH] lib/librte_hash: add
> > > > > rte_hash_del_key_fixed without compact
> > > > >
> > > > > The keys idx are stored in rte_hash main bucket key slots and
> > > > > extend bucket key stots.
> > > > > 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.
> > > > >
> > > > > ---
> > > > >  lib/librte_hash/rte_cuckoo_hash.c    | 19 ++++++++++++++-----
> > > > >  lib/librte_hash/rte_hash.h           |  5 +++++
> > > > >  lib/librte_hash/rte_hash_version.map |  1 +
> > > > >  3 files changed, 20 insertions(+), 5 deletions(-)
> > > > >
> > > > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > > > > b/lib/librte_hash/rte_cuckoo_hash.c
> > > > > index b52630b..2da3c1d 100644
> > > > > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > > > > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > > > > @@ -1523,7 +1523,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;
> > > > @@
> > > > > -1541,7 +1541,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;
> > > > > @@ -1553,7 +1554,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;
> > > > > @@ -1607,14 +1609,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 eceb365..9b71d8a 100644
> > > > > --- a/lib/librte_hash/rte_hash.h
> > > > > +++ b/lib/librte_hash/rte_hash.h
> > > > > @@ -297,6 +297,11 @@ 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);
> > > > >
> > > > > +
> > > > > +/* for without compact */
> > > > > +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 30cc086..1941d17 100644
> > > > > --- a/lib/librte_hash/rte_hash_version.map
> > > > > +++ b/lib/librte_hash/rte_hash_version.map
> > > > > @@ -11,6 +11,7 @@ DPDK_20.0 {
> > > > >  	rte_hash_count;
> > > > >  	rte_hash_create;
> > > > >  	rte_hash_del_key;
> > > > > +	rte_hash_del_key_fixed;
> > > > >  	rte_hash_del_key_with_hash;
> > > > >  	rte_hash_find_existing;
> > > > >  	rte_hash_free;
> > > > > --
> > > > > 2.19.1
> > > > >
> > > > > -----邮件原件-----
> > > > > 发件人: Lilijun (Jerry)
> > > > > 发送时间: 2020年4月18日 18:00
> > > > > 收件人: 'dev@dpdk.org' <dev@dpdk.org>; 'stable@dpdk.org'
> > > > > <stable@dpdk.org>
> > > > > 主题: rte_hash bug: can't iterate all entries when deleting keys
> > > > > in rte_hash iterate loop.
> > > > >
> > > > > Hi all,
> > > > >
> > > > >     In my test, entries can't be cleanup in rte_hash table when
> > > > > deleting keys in rte_hash iterate loop. The test steps:
> > > > >     1.  create a hash table table1 with limit 30000, ext bucket
> > > > > enabled,  and insert 30000 entries into this hash table.
> > > > >     2.  create a larger hash table table2 with limit 60000, ,
> > > > > ext bucket
> > > > enabled.
> > > > >     3.  iterate all entries of table1 and insert them to the table2.
> > > > > Insert new
> > > > > 10000 entries to this table2.
> > > > >     4.  Then flush all entries from table2 by deleting keys in
> > > > > rte_hash iterate loop. But there are still some keys leaked in table2.
> > > > Is there any reason for flushing table2 in this manner?
> > > > Is it possible to use 'rte_hash_reset' instead?
> > > >
> > > > >
> > > > >     From my analysis, the keys idx are stored in rte_hash main
> > > > > bucket key slots and extend bucket key stots.
> > > > >     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.
> > > > >
> > > > >     Now I retry the iterate and delete keys, that can avoid this bug.
> > > > >
> > > > >     Is there any ideas or solutions on this bug?   Thanks.
> > > > >
> > > > > Jerry.

Re: [dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Honnappa Nagarahalli]

<snip>

> > > >
> > > > Adding Yipeng, maintainer for hash library
> > > >
> > > > >
> > > > > Thanks for your reply.
> > > > >
> > > > > Using rte_hash iterate and delete keys is to free the related
> > > > > data's
> > > memory.
> > > > > There are two reasons why rte_hash_reset() is not properly:
> > > > > 1)  the reset function just clear all keys, the key's related
> > > > > data are
> > leaked.
> > > > That is a good point. I think this should be documented in the API.
> > > >
> > > > > 2)  In some cases, I don't need delete all keys. Just some
> > > > > selected keys and data are deleted and released.
> > > > I understand the problem you have pointed out and understand how
> > > > to reproduce it. But, the use case is not clear to me. Can you
> > > > please explain the use case?
> > > [Lilijun (Jerry)]
> > >
> > > As you know, the dpdk rte_hash use a fixed size table to store all
> > keys/datas.
> > > The memory used by hash table is related with this fixed size.
> > > In my case, normally the count of keys is about 100,000 but
> > > sometimes the count may burst up to 30,000,000.
> > > In order to save memory usage, I create a small hash table with
> > > 100,000 size and replace to a bigger one with 30,000,000 size when
> > > there are more keys to be stored. Also when the key's count reduced
> > > to less than 100,000, I replace the hash table with a small one to
> > > save the
> > memory.
> > Thank you for explaining this. What happens to the reader when you are
> > deleting from old table and inserting in the new one? Which table does
> > the reader lookup from?
> [Lilijun (Jerry)]
> Lookup functions works well at any time. The problem is in rte_hash_iterate()
> functions. Some example codes like this:
> *next = 0;
> //If rh has 10000 entries at first.
> while ((idx = rte_hash_iterate(rh, key, data, next)) >= 0) {
>               rte_hash_del_key(rh, key);  //BUT HERE maybe only delete 9990
> keys !!!
>               free(*data);
> }
> //There are still 10 key/datas not freed and will be leaked.
> rte_hash_free(rh);
I understand this problem.
I am trying to understand if there are other problems in the process you are following.
For ex: when you are transferring an entry from the old table, if the reader is looking up from the old table, the entry will not be found, even though the entry is available in the new table. Can this happen?

<snip the diff>

[dpdk-stable] 答复: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact

[Lilijun (Jerry)]

> -----邮件原件-----
> 发件人: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> 发送时间: 2020年5月14日 9:22
> 收件人: Lilijun (Jerry) <jerry.lilijun@huawei.com>; 'dev@dpdk.org'
> <dev@dpdk.org>
> 抄送: wangyunjian <wangyunjian@huawei.com>; xudingke
> <xudingke@huawei.com>; 'stable@dpdk.org' <stable@dpdk.org>; nd
> <nd@arm.com>; yipeng1.wang@intel.com; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; nd <nd@arm.com>
> 主题: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed
> without compact
> 
> <snip>
> 
> > > > >
> > > > > Adding Yipeng, maintainer for hash library
> > > > >
> > > > > >
> > > > > > Thanks for your reply.
> > > > > >
> > > > > > Using rte_hash iterate and delete keys is to free the related
> > > > > > data's
> > > > memory.
> > > > > > There are two reasons why rte_hash_reset() is not properly:
> > > > > > 1)  the reset function just clear all keys, the key's related
> > > > > > data are
> > > leaked.
> > > > > That is a good point. I think this should be documented in the API.
> > > > >
> > > > > > 2)  In some cases, I don't need delete all keys. Just some
> > > > > > selected keys and data are deleted and released.
> > > > > I understand the problem you have pointed out and understand how
> > > > > to reproduce it. But, the use case is not clear to me. Can you
> > > > > please explain the use case?
> > > > [Lilijun (Jerry)]
> > > >
> > > > As you know, the dpdk rte_hash use a fixed size table to store all
> > > keys/datas.
> > > > The memory used by hash table is related with this fixed size.
> > > > In my case, normally the count of keys is about 100,000 but
> > > > sometimes the count may burst up to 30,000,000.
> > > > In order to save memory usage, I create a small hash table with
> > > > 100,000 size and replace to a bigger one with 30,000,000 size when
> > > > there are more keys to be stored. Also when the key's count
> > > > reduced to less than 100,000, I replace the hash table with a
> > > > small one to save the
> > > memory.
> > > Thank you for explaining this. What happens to the reader when you
> > > are deleting from old table and inserting in the new one? Which
> > > table does the reader lookup from?
> > [Lilijun (Jerry)]
> > Lookup functions works well at any time. The problem is in
> > rte_hash_iterate() functions. Some example codes like this:
> > *next = 0;
> > //If rh has 10000 entries at first.
> > while ((idx = rte_hash_iterate(rh, key, data, next)) >= 0) {
> >               rte_hash_del_key(rh, key);  //BUT HERE maybe only delete
> > 9990 keys !!!
> >               free(*data);
> > }
> > //There are still 10 key/datas not freed and will be leaked.
> > rte_hash_free(rh);
> I understand this problem.
> I am trying to understand if there are other problems in the process you are
> following.
> For ex: when you are transferring an entry from the old table, if the reader is
> looking up from the old table, the entry will not be found, even though the
> entry is available in the new table. Can this happen?
> 
[Lilijun (Jerry)] 
Your example may be happen if read and resize are in two thread context and it's like a RCU cases. 
But I think it can be fixed for reader can retry the lookup or use a read-lock while resize using a write-lock.

> <snip the diff>