[PATCH v2 0/2] nft hash resize fixes

[PATCH v2 0/2] nft hash resize fixes

[Josh Hunt]

This is the minimal set of changes to get rhashtable expansion working with nft
hash sets. I will provide a followup patchset allowing the user to tune the
max size of the set.


Josh Hunt (2):
  rhashtable: require max_shift if grow_decision defined
  nft_hash: define max_shift rhashtable parameter

 lib/rhashtable.c         |    3 ++-
 net/netfilter/nft_hash.c |    4 ++++
 2 files changed, 6 insertions(+), 1 deletion(-)

-- 
1.7.9.5

[PATCH v2 1/2] rhashtable: require max_shift if grow_decision defined

[Josh Hunt]

If an rhashtable user defines a grow_decision fn they must also define a
max_shift parameter.

Signed-off-by: Josh Hunt <johunt@akamai.com>
---
 lib/rhashtable.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 9cc4c4a..7d6f539 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -1077,7 +1077,8 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	size = HASH_DEFAULT_SIZE;
 
 	if ((params->key_len && !params->hashfn) ||
-	    (!params->key_len && !params->obj_hashfn))
+	    (!params->key_len && !params->obj_hashfn) ||
+	    (params->grow_decision && !params->max_shift))
 		return -EINVAL;
 
 	if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
-- 
1.7.9.5

[PATCH v2 2/2] nft_hash: define max_shift rhashtable parameter

[Josh Hunt]

You must define a max_shift parameter to rhashtable or else the table cannot
grow. This sets max_shift for nft_hash to 24, which will allow the table to
grow to 2^24 or 16 million buckets.

Signed-off-by: Josh Hunt <johunt@akamai.com>
---
 net/netfilter/nft_hash.c |    4 ++++
 1 file changed, 4 insertions(+)

diff --git a/net/netfilter/nft_hash.c b/net/netfilter/nft_hash.c
index 61e6c40..839ed30 100644
--- a/net/netfilter/nft_hash.c
+++ b/net/netfilter/nft_hash.c
@@ -23,6 +23,9 @@
 /* We target a hash table size of 4, element hint is 75% of final size */
 #define NFT_HASH_ELEMENT_HINT 3
 
+/* Set default of 2^24 buckets or 16 million entries */
+#define NFT_HASH_MAX_ELEMENTS 24
+
 struct nft_hash_elem {
 	struct rhash_head		node;
 	struct nft_data			key;
@@ -192,6 +195,7 @@ static int nft_hash_init(const struct nft_set *set,
 		.key_offset = offsetof(struct nft_hash_elem, key),
 		.key_len = set->klen,
 		.hashfn = jhash,
+		.max_shift = NFT_HASH_MAX_ELEMENTS,
 		.grow_decision = rht_grow_above_75,
 		.shrink_decision = rht_shrink_below_30,
 	};
-- 
1.7.9.5

Re: [PATCH v2 1/2] rhashtable: require max_shift if grow_decision defined

[Thomas Graf]

On 02/24/15 at 11:10am, Josh Hunt wrote:
> If an rhashtable user defines a grow_decision fn they must also define a
> max_shift parameter.
> 
> Signed-off-by: Josh Hunt <johunt@akamai.com>

Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [PATCH v2 2/2] nft_hash: define max_shift rhashtable parameter

[Thomas Graf]

On 02/24/15 at 11:10am, Josh Hunt wrote:
> You must define a max_shift parameter to rhashtable or else the table cannot
> grow. This sets max_shift for nft_hash to 24, which will allow the table to
> grow to 2^24 or 16 million buckets.
> 
> Signed-off-by: Josh Hunt <johunt@akamai.com>
> ---
>  net/netfilter/nft_hash.c |    4 ++++
>  1 file changed, 4 insertions(+)
> 
> diff --git a/net/netfilter/nft_hash.c b/net/netfilter/nft_hash.c
> index 61e6c40..839ed30 100644
> --- a/net/netfilter/nft_hash.c
> +++ b/net/netfilter/nft_hash.c
> @@ -23,6 +23,9 @@
>  /* We target a hash table size of 4, element hint is 75% of final size */
>  #define NFT_HASH_ELEMENT_HINT 3
>  
> +/* Set default of 2^24 buckets or 16 million entries */
> +#define NFT_HASH_MAX_ELEMENTS 24

Maybe this should be called .._MAX_BUCKETS instead, the table
itself does not have a upper nelements limit but will not grow
above 16M buckets as the comment states correctly already.

After this change:
Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [PATCH v2 2/2] nft_hash: define max_shift rhashtable parameter

[Josh Hunt]

On 02/24/2015 10:42 AM, Thomas Graf wrote:
> Maybe this should be called .._MAX_BUCKETS instead, the table
> itself does not have a upper nelements limit but will not grow
> above 16M buckets as the comment states correctly already.
>
> After this change:
> Acked-by: Thomas Graf <tgraf@suug.ch>
>

Sure I can change the name to NFT_HASH_MAX_BUCKETS.

Thanks
Josh

Re: [PATCH v2 1/2] rhashtable: require max_shift if grow_decision defined

[David Miller]

From: Josh Hunt <johunt@akamai.com>
Date: Tue, 24 Feb 2015 11:10:57 -0500

> If an rhashtable user defines a grow_decision fn they must also define a
> max_shift parameter.
> 
> Signed-off-by: Josh Hunt <johunt@akamai.com>

I've already said today that I think this whole indirection stuff
with grow and shrink decisions should simply go away.

Everyone defines it to the generic rhashtable routine, therefore
that should just be made private to lib/rhashtable.c, called
directly, and the methods completely removed.

Given that, this change makes no sense.

When a limit is not specified, we should unconditionally grow rather
than refuse to grow.  One should not be required to specify this at
all.  If you have no idea what limit might be reasonable, you specify
nothing at all and just let available memory be the limiting factor.

Re: [PATCH v2 1/2] rhashtable: require max_shift if grow_decision defined

[Daniel Borkmann]

On 02/24/2015 07:18 PM, David Miller wrote:
...
> I've already said today that I think this whole indirection stuff
> with grow and shrink decisions should simply go away.
>
> Everyone defines it to the generic rhashtable routine, therefore
> that should just be made private to lib/rhashtable.c, called
> directly, and the methods completely removed.
>
> Given that, this change makes no sense.
>
> When a limit is not specified, we should unconditionally grow rather
> than refuse to grow.  One should not be required to specify this at
> all.  If you have no idea what limit might be reasonable, you specify
> nothing at all and just let available memory be the limiting factor.

I agree.

Fwiw, I believe this behavior came in as a regression via commit
c0c09bfdc415 ("rhashtable: avoid unnecessary wakeup for worker queue").
Initially, if no max_shift was specified, we'd just expand further.

I can take care of these above two fixups tomorrow, if you want.
I presume you want to route both via -net, or just the growth limit
issue via -net?

I also have some optimizations I was working on last week for
net-next, but I would wait for a -net into -net-next merge after
that to avoid merge conflicts, if that's fine. ;)

Thanks,
Daniel

Re: [PATCH v2 1/2] rhashtable: require max_shift if grow_decision defined

[David Miller]

From: Daniel Borkmann <daniel@iogearbox.net>
Date: Tue, 24 Feb 2015 20:48:10 +0100

> On 02/24/2015 07:18 PM, David Miller wrote:
> ...
>> I've already said today that I think this whole indirection stuff
>> with grow and shrink decisions should simply go away.
>>
>> Everyone defines it to the generic rhashtable routine, therefore
>> that should just be made private to lib/rhashtable.c, called
>> directly, and the methods completely removed.
>>
>> Given that, this change makes no sense.
>>
>> When a limit is not specified, we should unconditionally grow rather
>> than refuse to grow.  One should not be required to specify this at
>> all.  If you have no idea what limit might be reasonable, you specify
>> nothing at all and just let available memory be the limiting factor.
> 
> I agree.
> 
> Fwiw, I believe this behavior came in as a regression via commit
> c0c09bfdc415 ("rhashtable: avoid unnecessary wakeup for worker
> queue").
> Initially, if no max_shift was specified, we'd just expand further.
> 
> I can take care of these above two fixups tomorrow, if you want.
> I presume you want to route both via -net, or just the growth limit
> issue via -net?

Let's fix as much crap as we can in -net.  I'm going to have to do
a huge backport of all the rhashtables to -stable at some point
too.

> I also have some optimizations I was working on last week for
> net-next, but I would wait for a -net into -net-next merge after
> that to avoid merge conflicts, if that's fine. ;)

Yes, good idea :)

Re: [PATCH v2 1/2] rhashtable: require max_shift if grow_decision defined

[Josh Hunt]

On 02/24/2015 12:18 PM, David Miller wrote:
> From: Josh Hunt <johunt@akamai.com>
> Date: Tue, 24 Feb 2015 11:10:57 -0500
>
>> If an rhashtable user defines a grow_decision fn they must also define a
>> max_shift parameter.
>>
>> Signed-off-by: Josh Hunt <johunt@akamai.com>
>
> I've already said today that I think this whole indirection stuff
> with grow and shrink decisions should simply go away.
>
> Everyone defines it to the generic rhashtable routine, therefore
> that should just be made private to lib/rhashtable.c, called
> directly, and the methods completely removed.
>
> Given that, this change makes no sense.
>
> When a limit is not specified, we should unconditionally grow rather
> than refuse to grow.  One should not be required to specify this at
> all.  If you have no idea what limit might be reasonable, you specify
> nothing at all and just let available memory be the limiting factor.
>

I don't particularly care how this gets fixed at this point, just that 
it gets fixed. Right now nft hash sets can't expand b/c of this 
limitation. If we fix it by removing the max_shift requirement that 
works for me :)

Josh

Re: [PATCH v2 1/2] rhashtable: require max_shift if grow_decision defined

[Thomas Graf]

On 02/24/15 at 04:31pm, David Miller wrote:
> From: Daniel Borkmann <daniel@iogearbox.net>
> > Fwiw, I believe this behavior came in as a regression via commit
> > c0c09bfdc415 ("rhashtable: avoid unnecessary wakeup for worker
> > queue").
> > Initially, if no max_shift was specified, we'd just expand further.
> >
> > I can take care of these above two fixups tomorrow, if you want.

Thanks!

> > I presume you want to route both via -net, or just the growth limit
> > issue via -net?
> 
> Let's fix as much crap as we can in -net.  I'm going to have to do
> a huge backport of all the rhashtables to -stable at some point
> too.

All fixes except 2-3 should only affect the post per bucket lock
era. The fixes tags should be correct but I'll double check. I can
take care of the backports if you like.

Re: [PATCH v2 1/2] rhashtable: require max_shift if grow_decision defined

[David Miller]

From: Thomas Graf <tgraf@suug.ch>
Date: Tue, 24 Feb 2015 22:49:15 +0000

> On 02/24/15 at 04:31pm, David Miller wrote:
>> From: Daniel Borkmann <daniel@iogearbox.net>
>> Let's fix as much crap as we can in -net.  I'm going to have to do
>> a huge backport of all the rhashtables to -stable at some point
>> too.
> 
> All fixes except 2-3 should only affect the post per bucket lock
> era. The fixes tags should be correct but I'll double check. I can
> take care of the backports if you like.

There were several bugs that are only cured by the "per bucket
lock era" version fo rhashtable.

I only applied all of that work to net-next at the time because
suspected we'd still have to hash all of that out.

Therefore, all of the rhashtable stuff that went into 4.0-rc1
is going to need to be backported.

I also really wish Herbert Xu didn't drop off the map on this work, we
could really use his expertiece and suggestions right now. :-/