[dpdk-stable] [dpdk-dev] [PATCH] lib/librte_hash: add rte_hash_del_key_fixed without compact
Honnappa Nagarahalli
Honnappa.Nagarahalli at arm.com
Wed May 6 01:17:45 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?
>
> 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 stable
mailing list