* [PATCH 0/2] [RFC] nf_tables: speed up rule addition and deletion @ 2012-11-01 16:02 pablo 2012-11-01 16:02 ` [PATCH 1/2] netfilter: nf_tables: use 64-bits rule handle instead of 16-bits pablo 2012-11-01 16:02 ` [PATCH 2/2] netfilter: nf_tables: improve deletion performance pablo 0 siblings, 2 replies; 6+ messages in thread From: pablo @ 2012-11-01 16:02 UTC (permalink / raw) To: netfilter-devel; +Cc: Tomasz Bursztyka From: Pablo Neira Ayuso <pablo@netfilter.org> Hi! The following two RFC patches aim to improve rule addition and deletion timing. The current major bottleneck in the rule addition is the handle allocation per chain which is O(n), a simple way to get it O(1) is to use a 64-bits handle instead of 16-bits to uniquely identify the rule. The main concern here is to avoid wrap around of the handle (so we have no two rules with the same handle). We could stick to 32-bits. Overrun would happen after 2^32 rule additions, that seems unlikely but still possible in scenario in which rules are dynamically added and deleted. Regarding deletion, as it was documented in the source code, synchronize_rcu() really make performance suck. The alternative is to use kfree_rcu() and add one struct rcu_head per rule. This increases the length of the rule structure. I didn't come with any better simple solution like these two. I think this is yet another space-time tradeoff thing. So I'd put pressure on the memory side at this moment. Comments welcome. -- 1.7.10.4 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 1/2] netfilter: nf_tables: use 64-bits rule handle instead of 16-bits 2012-11-01 16:02 [PATCH 0/2] [RFC] nf_tables: speed up rule addition and deletion pablo @ 2012-11-01 16:02 ` pablo 2012-11-01 16:02 ` [PATCH 2/2] netfilter: nf_tables: improve deletion performance pablo 1 sibling, 0 replies; 6+ messages in thread From: pablo @ 2012-11-01 16:02 UTC (permalink / raw) To: netfilter-devel; +Cc: Tomasz Bursztyka From: Pablo Neira Ayuso <pablo@netfilter.org> This allows fast handle allocation. This speeds up rule addition from O(n) to O(1). I assume 64-bits handle should be enough to avoid an overrun (such thing may lead to two rules having the same handle quite easily with 16-bits). Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org> --- include/net/netfilter/nf_tables.h | 4 ++-- net/netfilter/nf_tables_api.c | 23 ++++++++--------------- 2 files changed, 10 insertions(+), 17 deletions(-) diff --git a/include/net/netfilter/nf_tables.h b/include/net/netfilter/nf_tables.h index 74b8b770..3289e0d 100644 --- a/include/net/netfilter/nf_tables.h +++ b/include/net/netfilter/nf_tables.h @@ -302,7 +302,7 @@ static inline void *nft_expr_priv(const struct nft_expr *expr) */ struct nft_rule { struct list_head list; - u16 handle; + u64 handle; u16 dlen; unsigned char data[] __attribute__((aligned(__alignof__(struct nft_expr)))); @@ -356,7 +356,7 @@ struct nft_chain { u8 policy; u16 use; u16 level; - u16 hgenerator; + u64 hgenerator; char name[NFT_CHAIN_MAXNAMELEN]; }; diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c index e510f18..cfe6b85 100644 --- a/net/netfilter/nf_tables_api.c +++ b/net/netfilter/nf_tables_api.c @@ -1061,7 +1061,7 @@ static void nf_tables_expr_destroy(const struct nft_ctx *ctx, */ static struct nft_rule *__nf_tables_rule_lookup(const struct nft_chain *chain, - u16 handle) + u64 handle) { struct nft_rule *rule; @@ -1080,26 +1080,19 @@ static struct nft_rule *nf_tables_rule_lookup(const struct nft_chain *chain, if (nla == NULL) return ERR_PTR(-EINVAL); - return __nf_tables_rule_lookup(chain, ntohs(nla_get_be16(nla))); + return __nf_tables_rule_lookup(chain, be64_to_cpu(nla_get_be64(nla))); } -static u16 nf_tables_rule_alloc_handle(struct nft_chain *chain) +static inline u64 nf_tables_rule_alloc_handle(struct nft_chain *chain) { - int i = 0xFFFF; - u16 handle; - - do { - handle = ++chain->hgenerator; - } while (--i > 0 && !IS_ERR(__nf_tables_rule_lookup(chain, handle))); - - return i > 0 ? handle : 0; + return ++chain->hgenerator; } static const struct nla_policy nft_rule_policy[NFTA_RULE_MAX + 1] = { [NFTA_RULE_TABLE] = { .type = NLA_STRING }, [NFTA_RULE_CHAIN] = { .type = NLA_STRING, .len = NFT_CHAIN_MAXNAMELEN - 1 }, - [NFTA_RULE_HANDLE] = { .type = NLA_U16 }, + [NFTA_RULE_HANDLE] = { .type = NLA_U64 }, [NFTA_RULE_EXPRESSIONS] = { .type = NLA_NESTED }, }; @@ -1129,7 +1122,7 @@ static int nf_tables_fill_rule_info(struct sk_buff *skb, u32 pid, u32 seq, goto nla_put_failure; if (nla_put_string(skb, NFTA_RULE_CHAIN, chain->name)) goto nla_put_failure; - if (nla_put_be16(skb, NFTA_RULE_HANDLE, htons(rule->handle))) + if (nla_put_be64(skb, NFTA_RULE_HANDLE, cpu_to_be64(rule->handle))) goto nla_put_failure; list = nla_nest_start(skb, NFTA_RULE_EXPRESSIONS); @@ -1317,7 +1310,7 @@ static int nf_tables_newrule(struct sock *nlsk, struct sk_buff *skb, unsigned int size, i, n; int err, rem; bool create; - u16 handle; + u64 handle; create = nlh->nlmsg_flags & NLM_F_CREATE ? true : false; @@ -1334,7 +1327,7 @@ static int nf_tables_newrule(struct sock *nlsk, struct sk_buff *skb, return PTR_ERR(chain); if (nla[NFTA_RULE_HANDLE]) { - handle = ntohs(nla_get_be16(nla[NFTA_RULE_HANDLE])); + handle = be64_to_cpu(nla_get_be64(nla[NFTA_RULE_HANDLE])); rule = __nf_tables_rule_lookup(chain, handle); if (IS_ERR(rule)) { if (PTR_ERR(rule) != -ENOENT) -- 1.7.10.4 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH 2/2] netfilter: nf_tables: improve deletion performance 2012-11-01 16:02 [PATCH 0/2] [RFC] nf_tables: speed up rule addition and deletion pablo 2012-11-01 16:02 ` [PATCH 1/2] netfilter: nf_tables: use 64-bits rule handle instead of 16-bits pablo @ 2012-11-01 16:02 ` pablo 2012-11-02 9:05 ` Tomasz Bursztyka 1 sibling, 1 reply; 6+ messages in thread From: pablo @ 2012-11-01 16:02 UTC (permalink / raw) To: netfilter-devel; +Cc: Tomasz Bursztyka From: Pablo Neira Ayuso <pablo@netfilter.org> Simple solution: Use kfree_rcu instead of synchronize_rcu. This gets struct nft_rule fatter. Regarding caching issues, it would be good to place struct rcu_head at the end of struct nft_rule. However, the expression area of one rule has variable length. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org> --- include/net/netfilter/nf_tables.h | 2 ++ net/netfilter/nf_tables_api.c | 11 +---------- 2 files changed, 3 insertions(+), 10 deletions(-) diff --git a/include/net/netfilter/nf_tables.h b/include/net/netfilter/nf_tables.h index 3289e0d..a179a6b 100644 --- a/include/net/netfilter/nf_tables.h +++ b/include/net/netfilter/nf_tables.h @@ -296,12 +296,14 @@ static inline void *nft_expr_priv(const struct nft_expr *expr) * struct nft_rule - nf_tables rule * * @list: used internally + * @rcu_head: used internally for rcu * @handle: rule handle * @dlen: length of expression data * @data: expression data */ struct nft_rule { struct list_head list; + struct rcu_head rcu_head; u64 handle; u16 dlen; unsigned char data[] diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c index cfe6b85..5ed8b06 100644 --- a/net/netfilter/nf_tables_api.c +++ b/net/netfilter/nf_tables_api.c @@ -1289,7 +1289,7 @@ static void nf_tables_rule_destroy(const struct nft_ctx *ctx, nf_tables_expr_destroy(ctx, expr); expr = nft_expr_next(expr); } - kfree(rule); + kfree_rcu(rule, rcu_head); } #define NFT_RULE_MAXEXPRS 12 @@ -1391,9 +1391,6 @@ static int nf_tables_newrule(struct sock *nlsk, struct sk_buff *skb, list_replace_rcu(&old_rule->list, &rule->list); - // FIXME: this makes deletion performance *really* suck - synchronize_rcu(); - nf_tables_rule_notify(skb, nlh, table, chain, old_rule, NFT_MSG_DELRULE, nfmsg->nfgen_family); nf_tables_rule_destroy(&ctx, old_rule); @@ -1448,9 +1445,6 @@ static int nf_tables_delrule(struct sock *nlsk, struct sk_buff *skb, /* List removal must be visible before destroying expressions */ list_del_rcu(&rule->list); - // FIXME: this makes deletion performance *really* suck - synchronize_rcu(); - nf_tables_rule_notify(skb, nlh, table, chain, rule, NFT_MSG_DELRULE, family); nft_ctx_init(&ctx, skb, nlh, afi, table, chain); @@ -1460,9 +1454,6 @@ static int nf_tables_delrule(struct sock *nlsk, struct sk_buff *skb, list_for_each_entry_safe(rule, tmp, &chain->rules, list) { list_del_rcu(&rule->list); - // FIXME: this makes deletion performance *really* suck - synchronize_rcu(); - nf_tables_rule_notify(skb, nlh, table, chain, rule, NFT_MSG_DELRULE, family); -- 1.7.10.4 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] netfilter: nf_tables: improve deletion performance 2012-11-01 16:02 ` [PATCH 2/2] netfilter: nf_tables: improve deletion performance pablo @ 2012-11-02 9:05 ` Tomasz Bursztyka 2012-11-04 18:44 ` Pablo Neira Ayuso 0 siblings, 1 reply; 6+ messages in thread From: Tomasz Bursztyka @ 2012-11-02 9:05 UTC (permalink / raw) To: pablo; +Cc: netfilter-devel Hi Pablo, > --- a/net/netfilter/nf_tables_api.c > +++ b/net/netfilter/nf_tables_api.c > @@ -1289,7 +1289,7 @@ static void nf_tables_rule_destroy(const struct nft_ctx *ctx, > nf_tables_expr_destroy(ctx, expr); > expr = nft_expr_next(expr); > } > - kfree(rule); > + kfree_rcu(rule, rcu_head); > } Shouldn't it free the expression list at the same moment when the rule will actually be freed? So call_rcu() instead of kfree_rcu(). Tomasz ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] netfilter: nf_tables: improve deletion performance 2012-11-02 9:05 ` Tomasz Bursztyka @ 2012-11-04 18:44 ` Pablo Neira Ayuso 2012-11-05 10:16 ` Tomasz Bursztyka 0 siblings, 1 reply; 6+ messages in thread From: Pablo Neira Ayuso @ 2012-11-04 18:44 UTC (permalink / raw) To: Tomasz Bursztyka; +Cc: netfilter-devel [-- Attachment #1: Type: text/plain, Size: 605 bytes --] Hi Tomasz, On Fri, Nov 02, 2012 at 11:05:32AM +0200, Tomasz Bursztyka wrote: > Hi Pablo, > > >--- a/net/netfilter/nf_tables_api.c > >+++ b/net/netfilter/nf_tables_api.c > >@@ -1289,7 +1289,7 @@ static void nf_tables_rule_destroy(const struct nft_ctx *ctx, > > nf_tables_expr_destroy(ctx, expr); > > expr = nft_expr_next(expr); > > } > >- kfree(rule); > >+ kfree_rcu(rule, rcu_head); > > } > > Shouldn't it free the expression list at the same moment when the > rule will actually be freed? > So call_rcu() instead of kfree_rcu(). You're right. New patch attached using the call_rcu approach. [-- Attachment #2: 0001-netfilter-nf_tables-improve-deletion-performance.patch --] [-- Type: text/x-diff, Size: 8265 bytes --] >From 568faf7915bd2c24a0980ba04f5dec403eecdd38 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso <pablo@netfilter.org> Date: Sun, 28 Oct 2012 22:15:36 +0100 Subject: [PATCH] netfilter: nf_tables: improve deletion performance Simple solution: Use call_rcu to delay object release until we reach RCU quiescent state instead of synchronize_rcu which is synchronous and too expensive. On the contrary, this increases the size of the struct nft_rule. Regarding caching issues, I think it would be good to place struct rcu_head at the end of struct nft_rule. However, the expression area of one rule has variable length. After this patch, rule object release becomes an asynchronous due to the usage of call_rcu. Therefore, we cannot pass the context information to the destroy callback to every expression. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org> --- include/net/netfilter/nf_tables.h | 5 +++-- net/netfilter/nf_tables_api.c | 37 ++++++++++++++----------------------- net/netfilter/nft_compat.c | 4 ++-- net/netfilter/nft_ct.c | 9 ++++++--- net/netfilter/nft_immediate.c | 3 +-- net/netfilter/nft_log.c | 3 +-- 6 files changed, 27 insertions(+), 34 deletions(-) diff --git a/include/net/netfilter/nf_tables.h b/include/net/netfilter/nf_tables.h index b49243b..ea5df3f 100644 --- a/include/net/netfilter/nf_tables.h +++ b/include/net/netfilter/nf_tables.h @@ -140,8 +140,7 @@ struct nft_expr_ops { int (*init)(const struct nft_ctx *ctx, const struct nft_expr *expr, const struct nlattr * const tb[]); - void (*destroy)(const struct nft_ctx *ctx, - const struct nft_expr *expr); + void (*destroy)(const struct nft_expr *expr); int (*dump)(struct sk_buff *skb, const struct nft_expr *expr); const struct nft_expr_type *type; @@ -171,12 +170,14 @@ static inline void *nft_expr_priv(const struct nft_expr *expr) * struct nft_rule - nf_tables rule * * @list: used internally + * @rcu_head: used internally for rcu * @handle: rule handle * @dlen: length of expression data * @data: expression data */ struct nft_rule { struct list_head list; + struct rcu_head rcu_head; u64 handle; u16 dlen; unsigned char data[] diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c index 8bcd991..c818924 100644 --- a/net/netfilter/nf_tables_api.c +++ b/net/netfilter/nf_tables_api.c @@ -1046,11 +1046,10 @@ err1: return err; } -static void nf_tables_expr_destroy(const struct nft_ctx *ctx, - struct nft_expr *expr) +static void nf_tables_expr_destroy(struct nft_expr *expr) { if (expr->ops->destroy) - expr->ops->destroy(ctx, expr); + expr->ops->destroy(expr); module_put(expr->ops->type->owner); } @@ -1273,9 +1272,9 @@ err: return err; } -static void nf_tables_rule_destroy(const struct nft_ctx *ctx, - struct nft_rule *rule) +static void nf_tables_rcu_rule_destroy(struct rcu_head *head) { + struct nft_rule *rule = container_of(head, struct nft_rule, rcu_head); struct nft_expr *expr; /* @@ -1284,12 +1283,17 @@ static void nf_tables_rule_destroy(const struct nft_ctx *ctx, */ expr = nft_expr_first(rule); while (expr->ops && expr != nft_expr_last(rule)) { - nf_tables_expr_destroy(ctx, expr); + nf_tables_expr_destroy(expr); expr = nft_expr_next(expr); } kfree(rule); } +static void nf_tables_rule_destroy(struct nft_rule *rule) +{ + call_rcu(&rule->rcu_head, nf_tables_rcu_rule_destroy); +} + #define NFT_RULE_MAXEXPRS 12 static int nf_tables_newrule(struct sock *nlsk, struct sk_buff *skb, @@ -1389,12 +1393,9 @@ static int nf_tables_newrule(struct sock *nlsk, struct sk_buff *skb, list_replace_rcu(&old_rule->list, &rule->list); - // FIXME: this makes deletion performance *really* suck - synchronize_rcu(); - nf_tables_rule_notify(skb, nlh, table, chain, old_rule, NFT_MSG_DELRULE, nfmsg->nfgen_family); - nf_tables_rule_destroy(&ctx, old_rule); + nf_tables_rule_destroy(old_rule); } else if (nlh->nlmsg_flags & NLM_F_APPEND) list_add_tail_rcu(&rule->list, &chain->rules); else @@ -1405,7 +1406,7 @@ static int nf_tables_newrule(struct sock *nlsk, struct sk_buff *skb, return 0; err2: - nf_tables_rule_destroy(&ctx, rule); + nf_tables_rule_destroy(rule); err1: for (i = 0; i < n; i++) { if (info[i].ops != NULL) @@ -1423,7 +1424,6 @@ static int nf_tables_delrule(struct sock *nlsk, struct sk_buff *skb, const struct nft_table *table; struct nft_chain *chain; struct nft_rule *rule, *tmp; - struct nft_ctx ctx; int family = nfmsg->nfgen_family; afi = nf_tables_afinfo_lookup(family, false); @@ -1446,26 +1446,17 @@ static int nf_tables_delrule(struct sock *nlsk, struct sk_buff *skb, /* List removal must be visible before destroying expressions */ list_del_rcu(&rule->list); - // FIXME: this makes deletion performance *really* suck - synchronize_rcu(); - nf_tables_rule_notify(skb, nlh, table, chain, rule, NFT_MSG_DELRULE, family); - nft_ctx_init(&ctx, skb, nlh, afi, table, chain); - nf_tables_rule_destroy(&ctx, rule); + nf_tables_rule_destroy(rule); } else { /* Remove all rules in this chain */ list_for_each_entry_safe(rule, tmp, &chain->rules, list) { list_del_rcu(&rule->list); - // FIXME: this makes deletion performance *really* suck - synchronize_rcu(); - nf_tables_rule_notify(skb, nlh, table, chain, rule, NFT_MSG_DELRULE, family); - - nft_ctx_init(&ctx, skb, nlh, afi, table, chain); - nf_tables_rule_destroy(&ctx, rule); + nf_tables_rule_destroy(rule); } } diff --git a/net/netfilter/nft_compat.c b/net/netfilter/nft_compat.c index aa2e3be..b4a3ad3 100644 --- a/net/netfilter/nft_compat.c +++ b/net/netfilter/nft_compat.c @@ -182,7 +182,7 @@ err: } static void -nft_target_destroy(const struct nft_ctx *ctx, const struct nft_expr *expr) +nft_target_destroy(const struct nft_expr *expr) { struct nft_target *priv = nft_expr_priv(expr); @@ -317,7 +317,7 @@ err: } static void -nft_match_destroy(const struct nft_ctx *ctx, const struct nft_expr *expr) +nft_match_destroy(const struct nft_expr *expr) { struct nft_match *priv = nft_expr_priv(expr); diff --git a/net/netfilter/nft_ct.c b/net/netfilter/nft_ct.c index 1fffe27..5df7c76 100644 --- a/net/netfilter/nft_ct.c +++ b/net/netfilter/nft_ct.c @@ -23,6 +23,7 @@ struct nft_ct { enum nft_ct_keys key:8; enum ip_conntrack_dir dir:8; enum nft_registers dreg:8; + uint8_t family; }; static void nft_ct_eval(const struct nft_expr *expr, @@ -178,6 +179,7 @@ static int nft_ct_init(const struct nft_ctx *ctx, err = nf_ct_l3proto_try_module_get(ctx->afi->family); if (err < 0) return err; + priv->family = ctx->afi->family; priv->dreg = ntohl(nla_get_be32(tb[NFTA_CT_DREG])); err = nft_validate_output_register(priv->dreg); @@ -194,10 +196,11 @@ err1: return err; } -static void nft_ct_destroy(const struct nft_ctx *ctx, - const struct nft_expr *expr) +static void nft_ct_destroy(const struct nft_expr *expr) { - nf_ct_l3proto_module_put(ctx->afi->family); + struct nft_ct *priv = nft_expr_priv(expr); + + nf_ct_l3proto_module_put(priv->family); } static int nft_ct_dump(struct sk_buff *skb, const struct nft_expr *expr) diff --git a/net/netfilter/nft_immediate.c b/net/netfilter/nft_immediate.c index 4b61563..d1e901e 100644 --- a/net/netfilter/nft_immediate.c +++ b/net/netfilter/nft_immediate.c @@ -70,8 +70,7 @@ err1: return err; } -static void nft_immediate_destroy(const struct nft_ctx *ctx, - const struct nft_expr *expr) +static void nft_immediate_destroy(const struct nft_expr *expr) { const struct nft_immediate_expr *priv = nft_expr_priv(expr); return nft_data_uninit(&priv->data, nft_dreg_to_type(priv->dreg)); diff --git a/net/netfilter/nft_log.c b/net/netfilter/nft_log.c index 9fe2be2..bbec4062 100644 --- a/net/netfilter/nft_log.c +++ b/net/netfilter/nft_log.c @@ -72,8 +72,7 @@ static int nft_log_init(const struct nft_ctx *ctx, return 0; } -static void nft_log_destroy(const struct nft_ctx *ctx, - const struct nft_expr *expr) +static void nft_log_destroy(const struct nft_expr *expr) { struct nft_log *priv = nft_expr_priv(expr); -- 1.7.10.4 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] netfilter: nf_tables: improve deletion performance 2012-11-04 18:44 ` Pablo Neira Ayuso @ 2012-11-05 10:16 ` Tomasz Bursztyka 0 siblings, 0 replies; 6+ messages in thread From: Tomasz Bursztyka @ 2012-11-05 10:16 UTC (permalink / raw) To: Pablo Neira Ayuso; +Cc: netfilter-devel Hi Pablo, >> Shouldn't it free the expression list at the same moment when the >> rule will actually be freed? >> So call_rcu() instead of kfree_rcu(). > You're right. New patch attached using the call_rcu approach. The patch looks fine now. Removing the nft_ctx does not harm actually, it was providing superfluous flexibility in this destroying case. Tomasz ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2012-11-05 10:16 UTC | newest] Thread overview: 6+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2012-11-01 16:02 [PATCH 0/2] [RFC] nf_tables: speed up rule addition and deletion pablo 2012-11-01 16:02 ` [PATCH 1/2] netfilter: nf_tables: use 64-bits rule handle instead of 16-bits pablo 2012-11-01 16:02 ` [PATCH 2/2] netfilter: nf_tables: improve deletion performance pablo 2012-11-02 9:05 ` Tomasz Bursztyka 2012-11-04 18:44 ` Pablo Neira Ayuso 2012-11-05 10:16 ` Tomasz Bursztyka
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).