nft_rhash_walk, rhashtable and resize event

nft_rhash_walk, rhashtable and resize event

[Alexander Aring]

Hi,

I try to find some ways that fits my use case of iterating a
rhashtable. I found [0] but it somehow tries to skip objects again if
a rhashtable resize event occurs during a hash walk. It does that by
skipping the already iterated objects according to a counter that is
tracked, see [0]:

if (iter->count < iter->skip)

from my understanding.

My question is here? Is that allowed to do because a resize event may
change the order how to iterate over a rhashtable.

Thanks.

- Alex

[0] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/net/netfilter/nft_set_hash.c?h=v6.6-rc1#n257

Re: nft_rhash_walk, rhashtable and resize event

[Herbert Xu]

On Fri, Sep 15, 2023 at 10:05:06AM -0400, Alexander Aring wrote:
>
> My question is here? Is that allowed to do because a resize event may
> change the order how to iterate over a rhashtable.

Walking over an rhashtable should be a last resort.  There is
no guarantee of stability.

If you skip entries after a resize then you may miss entries.

If you want a stable walk, allocate an extra 8 bytes and use
a linked list.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: nft_rhash_walk, rhashtable and resize event

[Pablo Neira Ayuso]

Hi Herbert,

On Sat, Sep 16, 2023 at 11:37:51AM +0800, Herbert Xu wrote:
> On Fri, Sep 15, 2023 at 10:05:06AM -0400, Alexander Aring wrote:
> >
> > My question is here? Is that allowed to do because a resize event may
> > change the order how to iterate over a rhashtable.
> 
> Walking over an rhashtable should be a last resort.  There is
> no guarantee of stability.
> 
> If you skip entries after a resize then you may miss entries.

One more question: this walk might miss entries but may it also
duplicate the same entries?

> If you want a stable walk, allocate an extra 8 bytes and use
> a linked list.

I will work on a patch to update netfilter clients for this code to
use a rcu linked list.

Thanks.

Re: nft_rhash_walk, rhashtable and resize event

[Herbert Xu]

On Mon, Sep 18, 2023 at 01:59:47PM +0200, Pablo Neira Ayuso wrote:
>
> One more question: this walk might miss entries but may it also
> duplicate the same entries?

It depends on what happens during the walk.  If you're lucky
and no resize event occurs during the walk, then you won't miss
any entries or see duplicates.

When a resize event does occur, then we will tell you that it
happened by returning EAGAIN.  It means that you should start
from the beginning and redo the whole walk.  If you do that
then you won't miss anything (although, you may never finish
if the table keeps getting resized).

But obviously duplicates will occur if you take this approach.

> I will work on a patch to update netfilter clients for this code to
> use a rcu linked list.

Sounds good!

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: nft_rhash_walk, rhashtable and resize event

[Alexander Aring]

Hi,

On Mon, Sep 18, 2023 at 8:26 AM Herbert Xu <herbert@gondor.apana.org.au> wrote:
>
> On Mon, Sep 18, 2023 at 01:59:47PM +0200, Pablo Neira Ayuso wrote:
> >
> > One more question: this walk might miss entries but may it also
> > duplicate the same entries?
>
> It depends on what happens during the walk.  If you're lucky
> and no resize event occurs during the walk, then you won't miss
> any entries or see duplicates.
>
> When a resize event does occur, then we will tell you that it
> happened by returning EAGAIN.  It means that you should start
> from the beginning and redo the whole walk.  If you do that

To confirm this, redo the whole walk means starting at
rhashtable_walk_start() again?

Thanks.

- Alex

Re: nft_rhash_walk, rhashtable and resize event

[Herbert Xu]

On Mon, Sep 18, 2023 at 08:38:09AM -0400, Alexander Aring wrote:
>
> To confirm this, redo the whole walk means starting at
> rhashtable_walk_start() again?

According to the documentation:

 * Returns -EAGAIN if resize event occurred.  Note that the iterator
 * will rewind back to the beginning and you may use it immediately
 * by calling rhashtable_walk_next.

So you shouldn't have to do anything other than keep on
iterating (if you wish to).

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt