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

Honnappa Nagarahalli Honnappa.Nagarahalli at arm.com
Wed May 13 21:27:04 CEST 2020


> > <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 at arm.com]
> > > 发送时间: 2020年4月29日 4:46
> > > 收件人: Lilijun (Jerry) <jerry.lilijun at huawei.com>; 'dev at dpdk.org'
> > > <dev at dpdk.org>
> > > 抄送: wangyunjian <wangyunjian at huawei.com>; xudingke
> > > <xudingke at huawei.com>; 'stable at dpdk.org' <stable at dpdk.org>; nd
> > > <nd at arm.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli at arm.com>;
> > nd
> > > <nd at 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 at dpdk.org' <dev at dpdk.org>; 'stable at dpdk.org'
> > > > <stable at 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.


More information about the dev mailing list