[PATCH v2 0/2] nft hash resize fixes

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

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 <redacted>
---
 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

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

Signed-off-by: Josh Hunt <redacted>
---
 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

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 <redacted>

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

On 02/24/15 at 11:10am, Josh Hunt 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>

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

From: Josh Hunt <redacted>
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 <redacted>

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.

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

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:
...

quoted

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 :)

On 02/24/2015 12:18 PM, David Miller wrote:

From: Josh Hunt <redacted>
Date: Tue, 24 Feb 2015 11:10:57 -0500

quoted

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

Signed-off-by: Josh Hunt <redacted>

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

On 02/24/15 at 04:31pm, David Miller wrote:

From: Daniel Borkmann <daniel@iogearbox.net>

quoted

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!

quoted

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.

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:

quoted

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. :-/