netfilter: Improve inverted IP prefix matches
Subsystems (2)
Phil Sutter
reviewercover netfilter: Improve inverted IP prefix matches
The following two patches improve packet throughput in a test setup sending UDP packets (using iperf3) between two netns. The ruleset used on receiver side is like this:
| *filter | :test - [0:0] | -A INPUT -j test | -A INPUT -j ACCEPT | -A test ! -s 10.0.0.0/10 -j DROP # this line repeats 10000 times | COMMIT
These are the generated VM instructions for each rule:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 & 0x0000c0ff ) ^ 0x00000000 ] | [ cmp eq reg 1 0x0000000a ] | [ counter pkts 0 bytes 0 ] | [ immediate reg 0 drop ]
Both sender and receiver reside within 10/10 network, iperf3 is just used to fill the (virtual) wire:
| iperf3 -c 10.0.0.2 -u -b 10G -t 1000
On receiver side, "packets received" counter of 'netstat -su' is monitored to calculate throughput. Averaging over about a minute, these are the figures:
legacy: ~10000pkt/s
nft (base): ~3000pkt/s
nft (patch1): ~4000pkt/s
nft (patch1+2): ~5200pkt/s
In summary, this increases nftables throughput for this specific test case from 1/3 of legacy iptables to 1/2.
Phil Sutter (2):
net: netfilter: Enable fast nft_cmp for inverted matches
net: netfilter: Implement fast bitwise expression
include/net/netfilter/nf_tables_core.h | 11 ++ net/netfilter/nf_tables_core.c | 15 ++- net/netfilter/nft_bitwise.c | 141 +++++++++++++++++++++++-- net/netfilter/nft_cmp.c | 10 +- 4 files changed, 164 insertions(+), 13 deletions(-)
Signature · 1 line
2.28.0
Phil Sutter
reviewerPATCH 1/2 net: netfilter: Enable fast nft_cmp for inverted matches
Add a boolean indicating NFT_CMP_NEQ. To include it into the match decision, it is sufficient to XOR it with the data comparison's result.
While being at it, store the mask that is calculated during expression init and free the eval routine from having to recalculate it each time.
--- include/net/netfilter/nf_tables_core.h | 2 ++ net/netfilter/nf_tables_core.c | 3 +-- net/netfilter/nft_cmp.c | 10 +++++----- 3 files changed, 8 insertions(+), 7 deletions(-)
include/net/netfilter/nf_tables_core.h +2 -0
@@ -25,8 +25,10 @@ void nf_tables_core_module_exit(void);struct nft_cmp_fast_expr {u32 data; +u32 mask;enum nft_registers sreg:8 ;u8 len; +bool inv; };struct nft_immediate_expr {
net/netfilter/nf_tables_core.c +1 -2
@@ -51,9 +51,8 @@ static void nft_cmp_fast_eval(const struct nft_expr *expr, struct nft_regs *regs) {const struct nft_cmp_fast_expr *priv =nft_expr_priv (expr); -u32 mask =nft_cmp_fast_mask (priv->len); -if ((regs->data[priv->sreg] & mask) == priv->data) +if (((regs->data[priv->sreg] & priv->mask) == priv->data) ^ priv->inv)return ; regs->verdict.code =NFT_BREAK ; }
net/netfilter/nft_cmp.c +5 -5
@@ -167,7 +167,6 @@ static int nft_cmp_fast_init(const struct nft_ctx *ctx,struct nft_cmp_fast_expr *priv =nft_expr_priv (expr);struct nft_data_desc desc;struct nft_data data; -u32 mask;int err; err = nft_data_init(NULL, &data, sizeof(data), &desc,
@@ -181,10 +180,11 @@ static int nft_cmp_fast_init(const struct nft_ctx *ctx,return err; desc.len *=BITS_PER_BYTE ; - mask =nft_cmp_fast_mask (desc.len); - priv->data = data.data[0 ] & mask; + priv->mask =nft_cmp_fast_mask (desc.len); + priv->data = data.data[0 ] & priv->mask; priv->len = desc.len; + priv->inv =ntohl (nla_get_be32 (tb[NFTA_CMP_OP ])) !=NFT_CMP_EQ ;return 0 ; }
@@ -201,7 +201,7 @@ static int nft_cmp_fast_offload(struct nft_offload_ctx *ctx, }, .sreg = priv->sreg, .len = priv->len / BITS_PER_BYTE, - .op = NFT_CMP_EQ, + .op = priv->inv ? NFT_CMP_NEQ : NFT_CMP_EQ, };return __nft_cmp_offload (ctx, flow, &cmp);
@@ -272,7 +272,7 @@ nft_cmp_select_ops(const struct nft_ctx *ctx, const struct nlattr * const tb[]) goto err1; } -if (desc.len <=sizeof (u32) && op ==NFT_CMP_EQ ) +if (desc.len <=sizeof (u32) && (op ==NFT_CMP_EQ || op ==NFT_CMP_NEQ ))return &nft_cmp_fast_ops;return &nft_cmp_ops;
Signature · 1 line
2.28.0
Phil Sutter
reviewerPATCH v2 1/2 net: netfilter: Enable fast nft_cmp for inverted matches
Add a boolean indicating NFT_CMP_NEQ. To include it into the match decision, it is sufficient to XOR it with the data comparison's result.
While being at it, store the mask that is calculated during expression init and free the eval routine from having to recalculate it each time.
---
Changes since v1:
- Forgot to update nft_cmp_fast_dump.
--- include/net/netfilter/nf_tables_core.h | 2 ++ net/netfilter/nf_tables_core.c | 3 +-- net/netfilter/nft_cmp.c | 13 +++++++------ 3 files changed, 10 insertions(+), 8 deletions(-)
include/net/netfilter/nf_tables_core.h +2 -0
@@ -25,8 +25,10 @@ void nf_tables_core_module_exit(void);struct nft_cmp_fast_expr {u32 data; +u32 mask;enum nft_registers sreg:8 ;u8 len; +bool inv; };struct nft_immediate_expr {
net/netfilter/nf_tables_core.c +1 -2
@@ -51,9 +51,8 @@ static void nft_cmp_fast_eval(const struct nft_expr *expr, struct nft_regs *regs) {const struct nft_cmp_fast_expr *priv =nft_expr_priv (expr); -u32 mask =nft_cmp_fast_mask (priv->len); -if ((regs->data[priv->sreg] & mask) == priv->data) +if (((regs->data[priv->sreg] & priv->mask) == priv->data) ^ priv->inv)return ; regs->verdict.code =NFT_BREAK ; }
net/netfilter/nft_cmp.c +7 -6
@@ -167,7 +167,6 @@ static int nft_cmp_fast_init(const struct nft_ctx *ctx,struct nft_cmp_fast_expr *priv =nft_expr_priv (expr);struct nft_data_desc desc;struct nft_data data; -u32 mask;int err; err = nft_data_init(NULL, &data, sizeof(data), &desc,
@@ -181,10 +180,11 @@ static int nft_cmp_fast_init(const struct nft_ctx *ctx,return err; desc.len *=BITS_PER_BYTE ; - mask =nft_cmp_fast_mask (desc.len); - priv->data = data.data[0 ] & mask; + priv->mask =nft_cmp_fast_mask (desc.len); + priv->data = data.data[0 ] & priv->mask; priv->len = desc.len; + priv->inv =ntohl (nla_get_be32 (tb[NFTA_CMP_OP ])) !=NFT_CMP_EQ ;return 0 ; }
@@ -201,7 +201,7 @@ static int nft_cmp_fast_offload(struct nft_offload_ctx *ctx, }, .sreg = priv->sreg, .len = priv->len / BITS_PER_BYTE, - .op = NFT_CMP_EQ, + .op = priv->inv ? NFT_CMP_NEQ : NFT_CMP_EQ, };return __nft_cmp_offload (ctx, flow, &cmp);
@@ -210,11 +210,12 @@ static int nft_cmp_fast_offload(struct nft_offload_ctx *ctx,static int nft_cmp_fast_dump (struct sk_buff *skb,const struct nft_expr *expr) {const struct nft_cmp_fast_expr *priv =nft_expr_priv (expr); +enum nft_cmp_ops op = priv->inv ?NFT_CMP_NEQ :NFT_CMP_EQ ;struct nft_data data;if (nft_dump_register (skb,NFTA_CMP_SREG , priv->sreg)) goto nla_put_failure; -if (nla_put_be32 (skb,NFTA_CMP_OP ,htonl (NFT_CMP_EQ ))) +if (nla_put_be32 (skb,NFTA_CMP_OP ,htonl (op))) goto nla_put_failure; data.data[0 ] = priv->data;
@@ -272,7 +273,7 @@ nft_cmp_select_ops(const struct nft_ctx *ctx, const struct nlattr * const tb[]) goto err1; } -if (desc.len <=sizeof (u32) && op ==NFT_CMP_EQ ) +if (desc.len <=sizeof (u32) && (op ==NFT_CMP_EQ || op ==NFT_CMP_NEQ ))return &nft_cmp_fast_ops;return &nft_cmp_ops;
Signature · 1 line
2.28.0
Re: [net-next PATCH 1/2 v2] net: netfilter: Enable fast nft_cmp for inverted matches
Quoted 5 lines · Phil Sutter
Add a boolean indicating
NFT_CMP_NEQ. To include it into the match decision, it is sufficient to XOR it with the data comparison's result.While being at it, store the mask that is calculated during expression init and free the eval routine from having to recalculate it each time.
Applied, thanks
Phil Sutter
reviewerPATCH 2/2 net: netfilter: Implement fast bitwise expression
In reply to Phil SutterA typical use of bitwise expression is to mask out parts of an IP address when matching on the network part only. Optimize for this common use with a fast variant for NFT_BITWISE_BOOL-type expressions operating on 32bit-sized values.
--- include/net/netfilter/nf_tables_core.h | 9 ++ net/netfilter/nf_tables_core.c | 12 +++ net/netfilter/nft_bitwise.c | 141 +++++++++++++++++++++++-- 3 files changed, 156 insertions(+), 6 deletions(-)
include/net/netfilter/nf_tables_core.h +9 -0
@@ -23,6 +23,13 @@ extern struct nft_object_type nft_secmark_obj_type;int nf_tables_core_module_init (void );void nf_tables_core_module_exit (void ); +struct nft_bitwise_fast_expr { +u32 mask; +u32 xor; +enum nft_registers sreg:8 ; +enum nft_registers dreg:8 ; +}; +struct nft_cmp_fast_expr {u32 data;u32 mask;
@@ -68,6 +75,8 @@ struct nft_payload_set {extern const struct nft_expr_ops nft_payload_fast_ops; +extern const struct nft_expr_ops nft_bitwise_fast_ops; +extern struct static_key_false nft_counters_enabled;extern struct static_key_false nft_trace_enabled;
net/netfilter/nf_tables_core.c +12 -0
@@ -47,6 +47,16 @@ static inline void nft_trace_packet(struct nft_traceinfo *info, } } +static void nft_bitwise_fast_eval (const struct nft_expr *expr, +struct nft_regs *regs) +{ +const struct nft_bitwise_fast_expr *priv =nft_expr_priv (expr); +u32 *src = ®s->data[priv->sreg]; +u32 *dst = ®s->data[priv->dreg]; + + *dst = (*src & priv->mask) ^ priv->xor; +} +static void nft_cmp_fast_eval (const struct nft_expr *expr,struct nft_regs *regs) {
@@ -175,6 +185,8 @@ nft_do_chain(struct nft_pktinfo *pkt, void *priv)nft_rule_for_each_expr (expr, last, rule) {if (expr->ops == &nft_cmp_fast_ops)nft_cmp_fast_eval (expr, ®s); +else if (expr->ops == &nft_bitwise_fast_ops) +nft_bitwise_fast_eval (expr, ®s);else if (expr->ops != &nft_payload_fast_ops || !nft_payload_fast_eval (expr, ®s, pkt))expr_call_ops_eval (expr, ®s, pkt);
net/netfilter/nft_bitwise.c +135 -6
155 lines not on this page · raw message
Signature · 1 line
2.28.0
Re: [net-next PATCH 2/2] net: netfilter: Implement fast bitwise expression
Quoted 4 lines · Phil Sutter
A typical use of bitwise expression is to mask out parts of an IP address when matching on the network part only. Optimize for this common use with a fast variant for NFT_BITWISE_BOOL-type expressions operating on 32bit-sized values.
Applied, thanks.
Florian Westphal
maintainerQuoted 11 lines · Phil Sutter
The following two patches improve packet throughput in a test setup sending UDP packets (using iperf3) between two netns. The ruleset used on receiver side is like this:
| *filter | :test - [0:0] | -A INPUT -j test | -A INPUT -j ACCEPT | -A test ! -s 10.0.0.0/10 -j DROP # this line repeats 10000 times | COMMIT
Quoted 4 lines
These are the generated VM instructions for each rule:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 &
0x0000c0ff) ^0x00000000]
Not related to this patch, but we should avoid the bitop if the netmask is divisble by 8 (can adjust the cmp -- adjusting the payload expr is probably not worth it).
Quoted 2 lines
| [ cmp eq reg 1
0x0000000a]
| [ counter pkts 0 bytes 0 ]
Out of curiosity, does omitting 'counter' help?
nft counter is rather expensive due to bh disable, iptables does it once at the evaluation loop only.
Phil Sutter
reviewerHi Florian,
Quoted 12 lines · Florian Westphal
Quoted 11 lines · Phil Sutter
The following two patches improve packet throughput in a test setup sending UDP packets (using iperf3) between two netns. The ruleset used on receiver side is like this:
| *filter | :test - [0:0] | -A INPUT -j test | -A INPUT -j ACCEPT | -A test ! -s 10.0.0.0/10 -j DROP # this line repeats 10000 times | COMMIT
Quoted 8 lines
Quoted 4 lines
These are the generated VM instructions for each rule:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 &
0x0000c0ff) ^0x00000000]Not related to this patch, but we should avoid the bitop if the netmask is divisble by 8 (can adjust the cmp -- adjusting the payload expr is probably not worth it).
See the patch I just sent to this list. I adjusted both - it simply didn't appear to me that I could get by with reducing the cmp expression size only. The upside though is that detecting the prefix match based on payload expression length is quick and easy.
Someone will have to adjust nft tool, though. ;)
Quoted 7 lines
Quoted 2 lines
| [ cmp eq reg 1
0x0000000a]
| [ counter pkts 0 bytes 0 ]Out of curiosity, does omitting 'counter' help?
nft counter is rather expensive due to bh disable, iptables does it once at the evaluation loop only.
I changed the test to create the base ruleset using iptables-nft-restore just as before, but create the rules in 'test' chain like so:
| nft add rule filter test ip saddr != 10.0.0.0/10 drop
The VM code is as expected:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 & 0x0000c0ff ) ^ 0x00000000 ] | [ cmp eq reg 1 0x0000000a ] | [ immediate reg 0 drop ]
Performance is ~7000pkt/s. So while it's faster than iptables-nft, it's still quite a bit slower than legacy iptables despite the skipped counters.
Cheers, Phil
Pablo Neira Ayuso
maintainerHi Phil,
Quoted 46 lines · Phil Sutter
Hi Florian,
Quoted 12 lines · Florian Westphal
Quoted 11 lines · Phil Sutter
The following two patches improve packet throughput in a test setup sending UDP packets (using iperf3) between two netns. The ruleset used on receiver side is like this:
| *filter | :test - [0:0] | -A INPUT -j test | -A INPUT -j ACCEPT | -A test ! -s 10.0.0.0/10 -j DROP # this line repeats 10000 times | COMMITQuoted 8 lines
Quoted 4 lines
These are the generated VM instructions for each rule:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 &
0x0000c0ff) ^0x00000000]Not related to this patch, but we should avoid the bitop if the netmask is divisble by 8 (can adjust the cmp -- adjusting the payload expr is probably not worth it).
See the patch I just sent to this list. I adjusted both - it simply didn't appear to me that I could get by with reducing the cmp expression size only. The upside though is that detecting the prefix match based on payload expression length is quick and easy.
Someone will have to adjust nft tool, though. ;)
Quoted 7 lines
Quoted 2 lines
| [ cmp eq reg 1
0x0000000a]
| [ counter pkts 0 bytes 0 ]Out of curiosity, does omitting 'counter' help?
nft counter is rather expensive due to bh disable, iptables does it once at the evaluation loop only.
I changed the test to create the base ruleset using iptables-nft-restore just as before, but create the rules in 'test' chain like so:
| nft add rule filter test ip saddr != 10.0.0.0/10 drop
The VM code is as expected:
Quoted 8 lines
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 & 0x0000c0ff ) ^ 0x00000000 ] | [ cmp eq reg 1 0x0000000a ] | [ immediate reg 0 drop ]Performance is ~7000pkt/s. So while it's faster than iptables-nft, it's still quite a bit slower than legacy iptables despite the skipped counters.
iptables is optimized for matching on input/output device name and IPv4 address + mask (see ip_packet_match()) for historical reasons, iptables does not use a match for this since the beginning.
One possibility (in the short-term) is to add an internal kernel expression to achieve the same behaviour. The kernel needs to detects for:
payload (nh, offset to ip saddr or ip daddr or ip protocol) + cmp payload (nh, offset to ip saddr or ip daddr) + bitwise + cmp meta (iifname or oifname) + bitwise + cmp
meta (iifname or oifname) + cmp
at the very beginning of the rule.
and squash these expressions into the "built-in" iptables match expression which emulates ip_packet_match().
Not nice, but if microbenchmarks using thousand of rules really matter (this is worst case O(n) linear list evaluation...) then it might make sense to explore this.
Pablo Neira Ayuso
maintainerQuoted 54 lines · Pablo Neira Ayuso
Hi Phil,
Quoted 51 lines · Phil Sutter
Hi Florian,
Quoted 12 lines · Florian Westphal
Quoted 11 lines · Phil Sutter
The following two patches improve packet throughput in a test setup sending UDP packets (using iperf3) between two netns. The ruleset used on receiver side is like this:
| *filter | :test - [0:0] | -A INPUT -j test | -A INPUT -j ACCEPT | -A test ! -s 10.0.0.0/10 -j DROP # this line repeats 10000 times | COMMITQuoted 8 lines
Quoted 4 lines
These are the generated VM instructions for each rule:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 &
0x0000c0ff) ^0x00000000]Not related to this patch, but we should avoid the bitop if the netmask is divisble by 8 (can adjust the cmp -- adjusting the payload expr is probably not worth it).
See the patch I just sent to this list. I adjusted both - it simply didn't appear to me that I could get by with reducing the cmp expression size only. The upside though is that detecting the prefix match based on payload expression length is quick and easy.
Someone will have to adjust nft tool, though. ;)
Quoted 7 lines
Quoted 2 lines
| [ cmp eq reg 1
0x0000000a]
| [ counter pkts 0 bytes 0 ]Out of curiosity, does omitting 'counter' help?
nft counter is rather expensive due to bh disable, iptables does it once at the evaluation loop only.
I changed the test to create the base ruleset using iptables-nft-restore just as before, but create the rules in 'test' chain like so:
| nft add rule filter test ip saddr != 10.0.0.0/10 drop
The VM code is as expected:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 & 0x0000c0ff ) ^ 0x00000000 ] | [ cmp eq reg 1 0x0000000a ] | [ immediate reg 0 drop ]
Quoted 7 lines
Quoted 3 lines
Performance is ~7000pkt/s. So while it's faster than iptables-nft, it's still quite a bit slower than legacy iptables despite the skipped counters.
iptables is optimized for matching on input/output device name and IPv4 address + mask (see
ip_packet_match()) for historical reasons, iptables does not use a match for this since the beginning.
For clarity here, I mean: iptables does not use the generic match infrastructure for matching on these fields, instead it is using ip_packet_match() which is called from ipt_do_table() which is the core function that evaluates the packet.
Quoted 17 lines
One possibility (in the short-term) is to add an internal kernel expression to achieve the same behaviour. The kernel needs to detects for:
payload (nh, offset to ip saddr or ip daddr or ip protocol) + cmp payload (nh, offset to ip saddr or ip daddr) + bitwise + cmp meta (iifname or oifname) + bitwise + cmp
meta (iifname or oifname) + cmpat the very beginning of the rule.
and squash these expressions into the "built-in" iptables match expression which emulates
ip_packet_match().Not nice, but if microbenchmarks using thousand of rules really matter (this is worst case O(n) linear list evaluation...) then it might make sense to explore this.
Phil Sutter
reviewerHi Pablo,
Quoted 55 lines · Pablo Neira Ayuso
Quoted 54 lines · Pablo Neira Ayuso
Hi Phil,
Quoted 51 lines · Phil Sutter
Hi Florian,
Quoted 12 lines · Florian Westphal
Quoted 11 lines · Phil Sutter
The following two patches improve packet throughput in a test setup sending UDP packets (using iperf3) between two netns. The ruleset used on receiver side is like this:
| *filter | :test - [0:0] | -A INPUT -j test | -A INPUT -j ACCEPT | -A test ! -s 10.0.0.0/10 -j DROP # this line repeats 10000 times | COMMITQuoted 8 lines
Quoted 4 lines
These are the generated VM instructions for each rule:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 &
0x0000c0ff) ^0x00000000]Not related to this patch, but we should avoid the bitop if the netmask is divisble by 8 (can adjust the cmp -- adjusting the payload expr is probably not worth it).
See the patch I just sent to this list. I adjusted both - it simply didn't appear to me that I could get by with reducing the cmp expression size only. The upside though is that detecting the prefix match based on payload expression length is quick and easy.
Someone will have to adjust nft tool, though. ;)
Quoted 7 lines
Quoted 2 lines
| [ cmp eq reg 1
0x0000000a]
| [ counter pkts 0 bytes 0 ]Out of curiosity, does omitting 'counter' help?
nft counter is rather expensive due to bh disable, iptables does it once at the evaluation loop only.
I changed the test to create the base ruleset using iptables-nft-restore just as before, but create the rules in 'test' chain like so:
| nft add rule filter test ip saddr != 10.0.0.0/10 drop
The VM code is as expected:
| [ payload load 4b @ network header + 12 => reg 1 ] | [ bitwise reg 1 = (reg=1 & 0x0000c0ff ) ^ 0x00000000 ] | [ cmp eq reg 1 0x0000000a ] | [ immediate reg 0 drop ]
Quoted 7 lines
Quoted 7 lines
Quoted 3 lines
Performance is ~7000pkt/s. So while it's faster than iptables-nft, it's still quite a bit slower than legacy iptables despite the skipped counters.
iptables is optimized for matching on input/output device name and IPv4 address + mask (see
ip_packet_match()) for historical reasons, iptables does not use a match for this since the beginning.
Ah, thanks for the pointer. That function (and the code therein) pretty clearly shows why rule-shredding is so much slower in iptables-nft than legacy despite the attempts at improving it.
Quoted 22 lines
For clarity here, I mean: iptables does not use the generic match infrastructure for matching on these fields, instead it is using
ip_packet_match()which is called fromipt_do_table()which is the core function that evaluates the packet.Quoted 17 lines
One possibility (in the short-term) is to add an internal kernel expression to achieve the same behaviour. The kernel needs to detects for:
payload (nh, offset to ip saddr or ip daddr or ip protocol) + cmp payload (nh, offset to ip saddr or ip daddr) + bitwise + cmp meta (iifname or oifname) + bitwise + cmp
meta (iifname or oifname) + cmpat the very beginning of the rule.
and squash these expressions into the "built-in" iptables match expression which emulates
ip_packet_match().Not nice, but if microbenchmarks using thousand of rules really matter (this is worst case O(n) linear list evaluation...) then it might make sense to explore this.
I appreciate the effort to identify a solution which "just works", though am not sure if we really should implement such hacks (yet). That said, the "fast" expressions strictly speaking are hacks as well ...
Cheers, Phil