[PATCH 0/3] nft hash set expansion fixes

[PATCH 0/3] nft hash set expansion fixes

[Josh Hunt]

This patchset resolves some issues I've come across while investigating nft hash
sets.

The first patch requires users of rhashtable to define a max_shift as suggested
by Daniel Borkmann and Thomas Graf. One side-effect of not setting max_shift is
that tables are not allowed to expand. I was observing this behavior with nft
hash sets prior to these changes.

The next patch implements this requirement for nft hash sets using desc->size as
the max_shift if it's provided by the user. If not, it falls back to a newly
defined default of 1024 elements. This value is somewhat arbitrary, but seems
like a reasonable default to me.

I used 'size' above for max_shift because it appears to be used as a ceiling for
the number of elements in a set in nft_add_set_elem(). It's also used in the
estimate fn. Prior to the next patch 'size' was also being used as the nelem_hint
to pass to rhashtable_init(). This seems incorrect since nelem_hint is meant to
provide a hint for how many hash buckets to initially allocate.

Instead of using 'size' for nelem_hint, the final patch introduces a new set
parameter named 'init_size'. If this approach is acceptable I can provide the
userspace patches to fully implement the new parameter.

The patchset is against net-next.

Josh Hunt (3):
  rhashtable: require max_shift definition
  nft_hash: define max_shift rhashtable param
  nft_hash: introduce init_size set parameter

 include/net/netfilter/nf_tables.h        |    4 +++-
 include/uapi/linux/netfilter/nf_tables.h |    2 ++
 lib/rhashtable.c                         |    3 ++-
 net/netfilter/nf_tables_api.c            |    4 ++++
 net/netfilter/nft_hash.c                 |    7 ++++++-
 5 files changed, 17 insertions(+), 3 deletions(-)

-- 
1.7.9.5

[PATCH 1/3] rhashtable: require max_shift definition

[Josh Hunt]

Force rhashtable users to define a max_shift value. This places a ceiling
on how large the table can grow.

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..f1bdfb0 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->max_shift))
 		return -EINVAL;
 
 	if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
-- 
1.7.9.5

Re: [PATCH 1/3] rhashtable: require max_shift definition

[Thomas Graf]

On 02/09/15 at 07:48pm, Josh Hunt wrote:
>  	if ((params->key_len && !params->hashfn) ||
> -	    (!params->key_len && !params->obj_hashfn))
> +	    (!params->key_len && !params->obj_hashfn) ||
> +	    (!params->max_shift))
>  		return -EINVAL;

You can drop the parenthesis around the new max_shift check.

Other than that:

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

Re: [PATCH 1/3] rhashtable: require max_shift definition

[Daniel Borkmann]

On 02/10/2015 01:58 AM, Thomas Graf wrote:
> On 02/09/15 at 07:48pm, Josh Hunt wrote:
>>   	if ((params->key_len && !params->hashfn) ||
>> -	    (!params->key_len && !params->obj_hashfn))
>> +	    (!params->key_len && !params->obj_hashfn) ||
>> +	    (!params->max_shift))
>>   		return -EINVAL;
>
> You can drop the parenthesis around the new max_shift check.

Also, I think the test should be expanded to check if there's
a grow_decision given and only in that case require max_shift
to be non-zero, otherwise we would require users who don't
want to expand their table to give a upper expansion limit.

Thanks,
Daniel

Re: [PATCH 1/3] rhashtable: require max_shift definition

[Josh Hunt]

On 02/10/2015 02:30 AM, Daniel Borkmann wrote:
> On 02/10/2015 01:58 AM, Thomas Graf wrote:
>> On 02/09/15 at 07:48pm, Josh Hunt wrote:
>>>       if ((params->key_len && !params->hashfn) ||
>>> -        (!params->key_len && !params->obj_hashfn))
>>> +        (!params->key_len && !params->obj_hashfn) ||
>>> +        (!params->max_shift))
>>>           return -EINVAL;
>>
>> You can drop the parenthesis around the new max_shift check.
>
> Also, I think the test should be expanded to check if there's
> a grow_decision given and only in that case require max_shift
> to be non-zero, otherwise we would require users who don't
> want to expand their table to give a upper expansion limit.

This is a good point. I'll make this change.

max_shift restricts the # of buckets, but should there be an optional 
parameter, maxelems, to set a ceiling on the # of elements in a table 
also? If not, I believe users will be able to add an "unlimited" # of 
entries to the existing buckets, whether or not a grow_decision fn is 
defined.

Josh

Re: [PATCH 1/3] rhashtable: require max_shift definition

[Daniel Borkmann]

On 02/10/2015 04:56 PM, Josh Hunt wrote:
> On 02/10/2015 02:30 AM, Daniel Borkmann wrote:
>> On 02/10/2015 01:58 AM, Thomas Graf wrote:
>>> On 02/09/15 at 07:48pm, Josh Hunt wrote:
>>>>       if ((params->key_len && !params->hashfn) ||
>>>> -        (!params->key_len && !params->obj_hashfn))
>>>> +        (!params->key_len && !params->obj_hashfn) ||
>>>> +        (!params->max_shift))
>>>>           return -EINVAL;
>>>
>>> You can drop the parenthesis around the new max_shift check.
>>
>> Also, I think the test should be expanded to check if there's
>> a grow_decision given and only in that case require max_shift
>> to be non-zero, otherwise we would require users who don't
>> want to expand their table to give a upper expansion limit.
>
> This is a good point. I'll make this change.
>
> max_shift restricts the # of buckets, but should there be an optional parameter, maxelems, to set a ceiling on the # of elements in a table also? If not, I believe users will be able to add an "unlimited" # of entries to the existing buckets, whether or not a grow_decision fn is defined.

Hm, given that min_shift/max_shift are parameters that directly
concern internals of rhashtable i.e. are tightly coupled to expand
and shrink functionality, I'd say that depending on the use case,
a maxelem limit should rather be handled outside of it, if it's
truly an issue/concern.

Re: [PATCH 1/3] rhashtable: require max_shift definition

[Thomas Graf]

On 02/10/15 at 06:06pm, Daniel Borkmann wrote:
> Hm, given that min_shift/max_shift are parameters that directly
> concern internals of rhashtable i.e. are tightly coupled to expand
> and shrink functionality, I'd say that depending on the use case,
> a maxelem limit should rather be handled outside of it, if it's
> truly an issue/concern.

Agreed, Netlink already uses the atomic counter of rhashtable to
enforce  upper limit of table entries:

        err = -ENOMEM;
        if (BITS_PER_LONG > 32 &&
            unlikely(atomic_read(&table->hash.nelems) >= UINT_MAX))
                goto err;

Re: [PATCH 1/3] rhashtable: require max_shift definition

[Patrick McHardy]

Am 10. Februar 2015 18:22:41 MEZ, schrieb Thomas Graf <tgraf@suug.ch>:
>On 02/10/15 at 06:06pm, Daniel Borkmann wrote:
>> Hm, given that min_shift/max_shift are parameters that directly
>> concern internals of rhashtable i.e. are tightly coupled to expand
>> and shrink functionality, I'd say that depending on the use case,
>> a maxelem limit should rather be handled outside of it, if it's
>> truly an issue/concern.
>
>Agreed, Netlink already uses the atomic counter of rhashtable to
>enforce  upper limit of table entries:
>
>        err = -ENOMEM;
>        if (BITS_PER_LONG > 32 &&
>            unlikely(atomic_read(&table->hash.nelems) >= UINT_MAX))
>                goto err;

I would tend to agree with Pablo, now we're handling half (shift) internally and half (max) externally, using internal values.

Re: [PATCH 1/3] rhashtable: require max_shift definition

[Josh Hunt]

On 02/10/2015 11:44 AM, Patrick McHardy wrote:
> Am 10. Februar 2015 18:22:41 MEZ, schrieb Thomas Graf <tgraf@suug.ch>:
>> On 02/10/15 at 06:06pm, Daniel Borkmann wrote:
>>> Hm, given that min_shift/max_shift are parameters that directly
>>> concern internals of rhashtable i.e. are tightly coupled to expand
>>> and shrink functionality, I'd say that depending on the use case,
>>> a maxelem limit should rather be handled outside of it, if it's
>>> truly an issue/concern.
>>
>> Agreed, Netlink already uses the atomic counter of rhashtable to
>> enforce  upper limit of table entries:
>>
>>         err = -ENOMEM;
>>         if (BITS_PER_LONG > 32 &&
>>             unlikely(atomic_read(&table->hash.nelems) >= UINT_MAX))
>>                 goto err;
>
> I would tend to agree with Pablo, now we're handling half (shift) internally and half (max) externally, using internal values.

OK. Thanks for all the feedback. I will send a v2 once the other 2 
patches get reviewed.

Thanks
Josh

[PATCH 2/3] nft_hash: define max_shift rhashtable param

[Josh Hunt]

Starting with commit "rhashtable: require max_shift definition" all users of
rhashtable must define a max_shift value to set an upper bound the table can
grow to. nft sets presently use nft_set_desc.size to enforce a limit on the size
a set can grow. Use this value to also set the ceiling for rhashtables.

If a user doesn't define a size it will fall back to a newly defined default of
10 (1024 elements.)

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

diff --git a/net/netfilter/nft_hash.c b/net/netfilter/nft_hash.c
index 61e6c40..08ec179 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
 
+/* Default max number of elements if user doesn't specify a size */
+#define NFT_HASH_MAX_ELEMENTS 10
+
 struct nft_hash_elem {
 	struct rhash_head		node;
 	struct nft_data			key;
@@ -194,6 +197,8 @@ static int nft_hash_init(const struct nft_set *set,
 		.hashfn = jhash,
 		.grow_decision = rht_grow_above_75,
 		.shrink_decision = rht_shrink_below_30,
+		.max_shift = desc->size ?
+			roundup_pow_of_two(desc->size) : NFT_HASH_MAX_ELEMENTS,
 	};
 
 	return rhashtable_init(priv, &params);
-- 
1.7.9.5

[PATCH 3/3] nft_hash: introduce init_size set parameter

[Josh Hunt]

Currently nft_hash is using desc->size to both set a ceiling on the number of
entries a set can have, and as the nelem_hint for rhashtable. This not correct
since nelem_hint defines the # of initial buckets for the set to use. It is not
used to enforce a maximum size on the table. That's done through max_shift.

This creates a new parameter 'init_size' to pass as the nelem_hint to rhashtable
as the # of buckets you would like to initialize the table with.

Signed-off-by: Josh Hunt <johunt@akamai.com>
---
 include/net/netfilter/nf_tables.h        |    4 +++-
 include/uapi/linux/netfilter/nf_tables.h |    2 ++
 net/netfilter/nf_tables_api.c            |    4 ++++
 net/netfilter/nft_hash.c                 |    2 +-
 4 files changed, 10 insertions(+), 2 deletions(-)

diff --git a/include/net/netfilter/nf_tables.h b/include/net/netfilter/nf_tables.h
index 9eaaa78..2c9130d 100644
--- a/include/net/netfilter/nf_tables.h
+++ b/include/net/netfilter/nf_tables.h
@@ -153,12 +153,14 @@ struct nft_set_iter {
  *
  *	@klen: key length
  *	@dlen: data length
- *	@size: number of set elements
+ *	@size: max number of set elements
+ *	@init_size: initial set size
  */
 struct nft_set_desc {
 	unsigned int		klen;
 	unsigned int		dlen;
 	unsigned int		size;
+	unsigned int		init_size;
 };
 
 /**
diff --git a/include/uapi/linux/netfilter/nf_tables.h b/include/uapi/linux/netfilter/nf_tables.h
index 832bc46..63e53eb 100644
--- a/include/uapi/linux/netfilter/nf_tables.h
+++ b/include/uapi/linux/netfilter/nf_tables.h
@@ -230,10 +230,12 @@ enum nft_set_policies {
  * enum nft_set_desc_attributes - set element description
  *
  * @NFTA_SET_DESC_SIZE: number of elements in set (NLA_U32)
+ * @NFTA_SET_DESC_INIT_SIZE: initial set size (NLA_U32)
  */
 enum nft_set_desc_attributes {
 	NFTA_SET_DESC_UNSPEC,
 	NFTA_SET_DESC_SIZE,
+	NFTA_SET_DESC_INIT_SIZE,
 	__NFTA_SET_DESC_MAX
 };
 #define NFTA_SET_DESC_MAX	(__NFTA_SET_DESC_MAX - 1)
diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c
index 199fd0f..275f41b 100644
--- a/net/netfilter/nf_tables_api.c
+++ b/net/netfilter/nf_tables_api.c
@@ -2211,6 +2211,7 @@ static const struct nla_policy nft_set_policy[NFTA_SET_MAX + 1] = {
 
 static const struct nla_policy nft_set_desc_policy[NFTA_SET_DESC_MAX + 1] = {
 	[NFTA_SET_DESC_SIZE]		= { .type = NLA_U32 },
+	[NFTA_SET_DESC_INIT_SIZE]	= { .type = NLA_U32 },
 };
 
 static int nft_ctx_init_from_setattr(struct nft_ctx *ctx,
@@ -2552,6 +2553,9 @@ static int nf_tables_set_desc_parse(const struct nft_ctx *ctx,
 	if (da[NFTA_SET_DESC_SIZE] != NULL)
 		desc->size = ntohl(nla_get_be32(da[NFTA_SET_DESC_SIZE]));
 
+	if (da[NFTA_SET_DESC_INIT_SIZE] != NULL)
+		desc->init_size = ntohl(nla_get_be32(da[NFTA_SET_DESC_INIT_SIZE]));
+
 	return 0;
 }
 
diff --git a/net/netfilter/nft_hash.c b/net/netfilter/nft_hash.c
index 08ec179..e03d1c6 100644
--- a/net/netfilter/nft_hash.c
+++ b/net/netfilter/nft_hash.c
@@ -190,7 +190,7 @@ static int nft_hash_init(const struct nft_set *set,
 {
 	struct rhashtable *priv = nft_set_priv(set);
 	struct rhashtable_params params = {
-		.nelem_hint = desc->size ? : NFT_HASH_ELEMENT_HINT,
+		.nelem_hint = desc->init_size ? : NFT_HASH_ELEMENT_HINT,
 		.head_offset = offsetof(struct nft_hash_elem, node),
 		.key_offset = offsetof(struct nft_hash_elem, key),
 		.key_len = set->klen,
-- 
1.7.9.5