* [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
* 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
* [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
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).