From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 377EAA0A0E for ; Wed, 24 Mar 2021 22:33:21 +0100 (CET) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 26CF0140D57; Wed, 24 Mar 2021 22:33:21 +0100 (CET) Received: from out3-smtp.messagingengine.com (out3-smtp.messagingengine.com [66.111.4.27]) by mails.dpdk.org (Postfix) with ESMTP id D13434014F; Wed, 24 Mar 2021 22:33:18 +0100 (CET) Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.nyi.internal (Postfix) with ESMTP id 7417B5C006E; Wed, 24 Mar 2021 17:33:18 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute2.internal (MEProxy); Wed, 24 Mar 2021 17:33:18 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=monjalon.net; h= from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding:content-type; s=fm3; bh= Sc567GfK0X/YETRc3y95qkh3k3XWKk5pIMSWf/xelgM=; b=b8QHYR/rOjkUFP3B ZJWMHpHqiH287OZW4cx8rZ3CJ8T+A0dE1V0ynOJqVxnHeUJ2t686oB2um+C5vzoO EgFTgoDXmJuTPmw8nX2DEhuRc5jHkVVNev0Wwq1z+nRWCeZBPLEq/JD/IBfIWXWv yec2Ho/9UXIIP5H3QYSYonTBjlILMli/r2WMn+I+G2bCitGVaJue/GwZtQtZUQcu nxn3smwnJHh3PGJqcLZ/QTh+9FCkeZHKyXEP1rZPWYr5D5EjXBOQpxlTiu+emGyu N5dsOixu/pUDQK2Oe0oePholp8pdM57vQevfRgmt9GyQ10hJIpOr4GzK0D21gWs2 612z5A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm2; bh=Sc567GfK0X/YETRc3y95qkh3k3XWKk5pIMSWf/xel gM=; b=q9r37Y+nvKvgi5UkII4Q9henJmdlIMV610S97v1kKwilFna64g6+YfOIq UAXRuFjQl2yAITs4PlbUHEi0/T4Nvj2vTrcahI5ATlGeaZHSQS2XRxKBwBrGs3oT OG/pvhG8XX+hziabFI4KbrJ9zsvVuWJoGxebVXJgsch0x0ouu7cmyRI3xAMRrSa/ Y9RL25rDXwPXPREDf7rvDDTizI+tDXqECj5Zl8k3xysZW4z62DEPLJ/4ZpSsw+Ws nhnfNZe9OL+rm4JmeN2KiCmU7taMOB5BpRadyKUy1OQsIphOepqdZ0Ww3K1d8L1I cY575EsjKYdUDltfL2XAffV4qeflQ== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrudegkedgudehudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpefhvffufffkjghfggfgtgesthhqredttddtjeenucfhrhhomhepvfhhohhm rghsucfoohhnjhgrlhhonhcuoehthhhomhgrshesmhhonhhjrghlohhnrdhnvghtqeenuc ggtffrrghtthgvrhhnpeekteehtdeivefhieegjeelgedufeejheekkeetueevieeuvdev uedtjeevheevteenucfkphepjeejrddufeegrddvtdefrddukeegnecuvehluhhsthgvrh fuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepthhhohhmrghssehmohhnjhgr lhhonhdrnhgvth X-ME-Proxy: Received: from xps.localnet (184.203.134.77.rev.sfr.net [77.134.203.184]) by mail.messagingengine.com (Postfix) with ESMTPA id D8ACE1080054; Wed, 24 Mar 2021 17:33:16 -0400 (EDT) From: Thomas Monjalon To: "Wang, Yipeng1" , Honnappa Nagarahalli , "Lilijun (Jerry)" Cc: "'dev@dpdk.org'" , stable@dpdk.org, wangyunjian , xudingke Date: Wed, 24 Mar 2021 22:33:15 +0100 Message-ID: <5797361.OYrOJzcSuM@thomas> In-Reply-To: <40280F65B1B0B44E8089ED31C01616EBA49C65F4@dggeml529-mbx.china.huawei.com> References: <40280F65B1B0B44E8089ED31C01616EBA49921F2@dggeml529-mbx.china.huawei.com> <40280F65B1B0B44E8089ED31C01616EBA49C65F4@dggeml529-mbx.china.huawei.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="UTF-8" Subject: Re: [dpdk-stable] =?utf-8?b?562U5aSNOiBbZHBkay1kZXZdIFtQQVRDSF0gbGli?= =?utf-8?q?/librte=5Fhash=3A_add_rte=5Fhash=5Fdel=5Fkey=5Ffixed_without_co?= =?utf-8?q?mpact?= X-BeenThere: stable@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: patches for DPDK stable branches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: stable-bounces@dpdk.org Sender: "stable" Sorry for not following the full thread. What is the conclusion please? 13/05/2020 03:28, Lilijun (Jerry): >=20 > > -----=E9=82=AE=E4=BB=B6=E5=8E=9F=E4=BB=B6----- > > =E5=8F=91=E4=BB=B6=E4=BA=BA: Wang, Yipeng1 [mailto:yipeng1.wang@intel.c= om] > > =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2020=E5=B9=B45=E6=9C=8813=E6=97= =A5 7:41 > > =E6=94=B6=E4=BB=B6=E4=BA=BA: Lilijun (Jerry) = ; Honnappa Nagarahalli > > ; 'dev@dpdk.org' > > =E6=8A=84=E9=80=81: wangyunjian ; xudingke > > ; 'stable@dpdk.org' ; nd > > ; nd > > =E4=B8=BB=E9=A2=98: RE: [dpdk-dev] [PATCH] lib/librte_hash: add rte_has= h_del_key_fixed > > without compact > >=20 > > > -----Original Message----- > > > From: Lilijun (Jerry) > > > Sent: Tuesday, May 5, 2020 6:10 PM > > > To: Honnappa Nagarahalli ; > > > 'dev@dpdk.org' > > > Cc: wangyunjian ; xudingke > > > ; 'stable@dpdk.org' ; nd > > > ; Wang, Yipeng1 ; nd > > > > > Subject: =E7=AD=94=E5=A4=8D: [dpdk-dev] [PATCH] lib/librte_hash: add > > > rte_hash_del_key_fixed without compact > > > > > > > -----=E9=82=AE=E4=BB=B6=E5=8E=9F=E4=BB=B6----- > > > > =E5=8F=91=E4=BB=B6=E4=BA=BA: Honnappa Nagarahalli [mailto:Honnappa.= Nagarahalli@arm.com] > > > > =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2020=E5=B9=B45=E6=9C=886=E6= =97=A5 7:18 > > > > =E6=94=B6=E4=BB=B6=E4=BA=BA: Lilijun (Jerry) ; 'dev@dpdk.org' > > > > > > > > =E6=8A=84=E9=80=81: wangyunjian ; xudingke > > > > ; 'stable@dpdk.org' ; nd > > > > ; Honnappa Nagarahalli > > ; > > > > yipeng1.wang@intel.com; nd > > > > =E4=B8=BB=E9=A2=98: RE: [dpdk-dev] [PATCH] lib/librte_hash: add > > > > rte_hash_del_key_fixed without compact > > > > > > > > > > > > > > > > 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 dat= a are > > leaked. > > > > That is a good point. I think this should be documented in the API. > >=20 > > [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 i= n an > > array and iterate that array instead? > [Lilijun (Jerry)]=20 > 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 prob= lem, 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 d= ata > > structure so you don=E2=80=99t need to iterate the whole hash table? > >=20 > [Lilijun (Jerry)]=20 > 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 inva= lidate > > the Iterator, do you insert keys only to new table during resizing? > >=20 > [Lilijun (Jerry)]=20 > Yes, Insert only to new table. Because the resize process need take a wri= te lock and the old table's key insertion are prevented by the lock now.=20 > Do you mean the key insertion may change other key's position by cuckoo h= ash algorithm and invalidate the iterator? > That maybe a new question I haven't met yet. > > > > > > > > > > > > > > > > > Jerry. > > > > > > > > > > -----=E9=82=AE=E4=BB=B6=E5=8E=9F=E4=BB=B6----- > > > > > =E5=8F=91=E4=BB=B6=E4=BA=BA: Honnappa Nagarahalli [mailto:Honnapp= a.Nagarahalli@arm.com] > > > > > =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2020=E5=B9=B44=E6=9C=8829= =E6=97=A5 4:46 > > > > > =E6=94=B6=E4=BB=B6=E4=BA=BA: Lilijun (Jerry) ; 'dev@dpdk.org' > > > > > > > > > > =E6=8A=84=E9=80=81: wangyunjian ; xudingke > > > > > ; 'stable@dpdk.org' ; nd > > > > > ; Honnappa Nagarahalli > > > ; > > > > nd > > > > > > > > > > =E4=B8=BB=E9=A2=98: RE: [dpdk-dev] [PATCH] lib/librte_hash: add > > > > > rte_hash_del_key_fixed without compact > > > > > > > > > > > > > > > > > > > > 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 bu= cket > > 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 =3D search_and_remove(h, key, prim_bkt, short_sig, &pos); > > > > > > if (ret !=3D -1) { > > > > > > - __rte_hash_compact_ll(h, prim_bkt, pos); > > > > > > + if (compact) > > > > > > + __rte_hash_compact_ll(h, prim_bkt, pos); > > > > > > last_bkt =3D prim_bkt->next; > > > > > > prev_bkt =3D 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 =3D search_and_remove(h, key, cur_bkt, short_sig, > > &pos); > > > > > > if (ret !=3D -1) { > > > > > > - __rte_hash_compact_ll(h, cur_bkt, pos); > > > > > > + if (compact) > > > > > > + __rte_hash_compact_ll(h, cur_bkt, > > pos); > > > > > > last_bkt =3D sec_bkt->next; > > > > > > prev_bkt =3D 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 =3D=3D NULL) || (key =3D=3D NULL)), -EINVA= L); > > > > > > - 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 =3D=3D NULL) || (key =3D=3D NULL)), -EINVA= L); > > > > > > - 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 *k= ey) > > { > > > > > > + RETURN_IF_TRUE(((h =3D=3D NULL) || (key =3D=3D NULL)), -EINVA= L); > > > > > > + 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 > > > > > > > > > > > > -----=E9=82=AE=E4=BB=B6=E5=8E=9F=E4=BB=B6----- > > > > > > =E5=8F=91=E4=BB=B6=E4=BA=BA: Lilijun (Jerry) > > > > > > =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2020=E5=B9=B44=E6=9C=8818= =E6=97=A5 18:00 > > > > > > =E6=94=B6=E4=BB=B6=E4=BA=BA: 'dev@dpdk.org' ; 'st= able@dpdk.org' > > > > > > > > > > > > =E4=B8=BB=E9=A2=98: rte_hash bug: can't iterate all entries whe= n 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 ta= ble2. > > > > > > 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 thi= s 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! > >=20 > > Although it is not a bug to me, I think this is a valid issue and thank= s 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 iteratio= n. We at > > least should clarify this in the documentation. > >=20 > > 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=E2=80=99t have such capability in rte_hash now as you po= inted out, and > > this is a gap you want to fill. > >=20 > > 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. Alt= hough > > 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 va= lid > > iterator should be a better way. What do you think? > >=20 > [Lilijun (Jerry)]=20 > Yes, I am agree with your views. Some "erase" function may be better for = this cases. >=20 > > Resizing is an important feature that we always think to add into rte_h= ash. > > Feel free to propose resizing Features too into rte_hash as you are alr= eady > > doing similar thing right now. > >=20 > [Lilijun (Jerry)]=20 > 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. >=20 > > BTW, you can add a [RFC] prefix to the subject line for future RFC patc= hes. > >=20 > > Other questions/comments are inlined.