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

[Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>]

<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.