* [PATCH 0/3] nft hash set expansion fixes
@ 2015-02-10 0:48 Josh Hunt
2015-02-10 0:48 ` [PATCH 1/3] rhashtable: require max_shift definition Josh Hunt
` (2 more replies)
0 siblings, 3 replies; 11+ messages in thread
From: Josh Hunt @ 2015-02-10 0:48 UTC (permalink / raw)
To: Pablo Neira Ayuso, Patrick McHardy, Thomas Graf
Cc: netfilter-devel, netdev, Daniel Borkmann, 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
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 1/3] rhashtable: require max_shift definition
2015-02-10 0:48 [PATCH 0/3] nft hash set expansion fixes Josh Hunt
@ 2015-02-10 0:48 ` Josh Hunt
2015-02-10 0:58 ` Thomas Graf
2015-02-10 0:48 ` [PATCH 2/3] nft_hash: define max_shift rhashtable param Josh Hunt
2015-02-10 0:48 ` [PATCH 3/3] nft_hash: introduce init_size set parameter Josh Hunt
2 siblings, 1 reply; 11+ messages in thread
From: Josh Hunt @ 2015-02-10 0:48 UTC (permalink / raw)
To: Pablo Neira Ayuso, Patrick McHardy, Thomas Graf
Cc: netfilter-devel, netdev, Daniel Borkmann, 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH 2/3] nft_hash: define max_shift rhashtable param
2015-02-10 0:48 [PATCH 0/3] nft hash set expansion fixes Josh Hunt
2015-02-10 0:48 ` [PATCH 1/3] rhashtable: require max_shift definition Josh Hunt
@ 2015-02-10 0:48 ` Josh Hunt
2015-02-10 0:48 ` [PATCH 3/3] nft_hash: introduce init_size set parameter Josh Hunt
2 siblings, 0 replies; 11+ messages in thread
From: Josh Hunt @ 2015-02-10 0:48 UTC (permalink / raw)
To: Pablo Neira Ayuso, Patrick McHardy, Thomas Graf
Cc: netfilter-devel, netdev, Daniel Borkmann, 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, ¶ms);
--
1.7.9.5
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH 3/3] nft_hash: introduce init_size set parameter
2015-02-10 0:48 [PATCH 0/3] nft hash set expansion fixes Josh Hunt
2015-02-10 0:48 ` [PATCH 1/3] rhashtable: require max_shift definition Josh Hunt
2015-02-10 0:48 ` [PATCH 2/3] nft_hash: define max_shift rhashtable param Josh Hunt
@ 2015-02-10 0:48 ` Josh Hunt
2 siblings, 0 replies; 11+ messages in thread
From: Josh Hunt @ 2015-02-10 0:48 UTC (permalink / raw)
To: Pablo Neira Ayuso, Patrick McHardy, Thomas Graf
Cc: netfilter-devel, netdev, Daniel Borkmann, 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] rhashtable: require max_shift definition
2015-02-10 0:48 ` [PATCH 1/3] rhashtable: require max_shift definition Josh Hunt
@ 2015-02-10 0:58 ` Thomas Graf
2015-02-10 8:30 ` Daniel Borkmann
0 siblings, 1 reply; 11+ messages in thread
From: Thomas Graf @ 2015-02-10 0:58 UTC (permalink / raw)
To: Josh Hunt
Cc: Pablo Neira Ayuso, Patrick McHardy, netfilter-devel, netdev,
Daniel Borkmann
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>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] rhashtable: require max_shift definition
2015-02-10 0:58 ` Thomas Graf
@ 2015-02-10 8:30 ` Daniel Borkmann
2015-02-10 15:56 ` Josh Hunt
0 siblings, 1 reply; 11+ messages in thread
From: Daniel Borkmann @ 2015-02-10 8:30 UTC (permalink / raw)
To: Thomas Graf
Cc: Josh Hunt, Pablo Neira Ayuso, Patrick McHardy, netfilter-devel, netdev
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] rhashtable: require max_shift definition
2015-02-10 8:30 ` Daniel Borkmann
@ 2015-02-10 15:56 ` Josh Hunt
2015-02-10 17:06 ` Daniel Borkmann
0 siblings, 1 reply; 11+ messages in thread
From: Josh Hunt @ 2015-02-10 15:56 UTC (permalink / raw)
To: Daniel Borkmann, Thomas Graf
Cc: Pablo Neira Ayuso, Patrick McHardy, netfilter-devel, netdev
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] rhashtable: require max_shift definition
2015-02-10 15:56 ` Josh Hunt
@ 2015-02-10 17:06 ` Daniel Borkmann
2015-02-10 17:22 ` Thomas Graf
0 siblings, 1 reply; 11+ messages in thread
From: Daniel Borkmann @ 2015-02-10 17:06 UTC (permalink / raw)
To: Josh Hunt
Cc: Thomas Graf, Pablo Neira Ayuso, Patrick McHardy, netfilter-devel, netdev
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] rhashtable: require max_shift definition
2015-02-10 17:06 ` Daniel Borkmann
@ 2015-02-10 17:22 ` Thomas Graf
2015-02-10 17:44 ` Patrick McHardy
0 siblings, 1 reply; 11+ messages in thread
From: Thomas Graf @ 2015-02-10 17:22 UTC (permalink / raw)
To: Daniel Borkmann
Cc: Josh Hunt, Pablo Neira Ayuso, Patrick McHardy, netfilter-devel, netdev
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;
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] rhashtable: require max_shift definition
2015-02-10 17:22 ` Thomas Graf
@ 2015-02-10 17:44 ` Patrick McHardy
2015-02-10 21:18 ` Josh Hunt
0 siblings, 1 reply; 11+ messages in thread
From: Patrick McHardy @ 2015-02-10 17:44 UTC (permalink / raw)
To: Thomas Graf, Daniel Borkmann
Cc: Josh Hunt, Pablo Neira Ayuso, netfilter-devel, netdev
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] rhashtable: require max_shift definition
2015-02-10 17:44 ` Patrick McHardy
@ 2015-02-10 21:18 ` Josh Hunt
0 siblings, 0 replies; 11+ messages in thread
From: Josh Hunt @ 2015-02-10 21:18 UTC (permalink / raw)
To: Patrick McHardy, Thomas Graf, Daniel Borkmann
Cc: Pablo Neira Ayuso, netfilter-devel, netdev
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
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2015-02-10 21:18 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-02-10 0:48 [PATCH 0/3] nft hash set expansion fixes Josh Hunt
2015-02-10 0:48 ` [PATCH 1/3] rhashtable: require max_shift definition Josh Hunt
2015-02-10 0:58 ` Thomas Graf
2015-02-10 8:30 ` Daniel Borkmann
2015-02-10 15:56 ` Josh Hunt
2015-02-10 17:06 ` Daniel Borkmann
2015-02-10 17:22 ` Thomas Graf
2015-02-10 17:44 ` Patrick McHardy
2015-02-10 21:18 ` Josh Hunt
2015-02-10 0:48 ` [PATCH 2/3] nft_hash: define max_shift rhashtable param Josh Hunt
2015-02-10 0:48 ` [PATCH 3/3] nft_hash: introduce init_size set parameter Josh Hunt
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).