netfilter: x_tables: speed up jump target validation
Subsystems (2)
Florian Westphal
maintainerPATCH v3 1/1 netfilter: x_tables: speed up jump target validation
The dummy ruleset I used to test the original validation change was broken, most rules were unreachable and were not tested by mark_source_chains().
In some cases rulesets that used to load in a few seconds now require several minutes.
sample ruleset that shows the behaviour:
echo "*filter"
for i in $(seq 0 100000);do
printf ":chain_%06x - [0:0]\n" $i
done
for i in $(seq 0 100000);do
printf -- "-A INPUT -j chain_%06x\n" $i
printf -- "-A INPUT -j chain_%06x\n" $i
printf -- "-A INPUT -j chain_%06x\n" $i
done
echo COMMIT
[ pipe result into iptables-restore ]
This ruleset will be about 74mbyte in size, with ~500k searches though all 500k[1] rule entries. iptables-restore will take forever (gave up after 10 minutes)
Instead of always searching the entire blob for a match, fill an array with the start offsets of every single ipt_entry struct, then do a binary search to check if the jump target is present or not.
After this change ruleset restore times get again close to what one gets when reverting 36472341017529e (~3 seconds on my workstation).
[1] every user-defined rule gets an implicit RETURN, so we get 300k jumps + 100k userchains + 100k returns -> 500k rule entries
---
v3:
- also use bsearch in arptables
v2:
- get rid of unneeded 'offsets &&' clause in if-test
- add Tested-by Tag from Jeff Wu
- fixup some parts of commit message wrt. size of example ruleset
include/linux/netfilter/x_tables.h | 4 +++ net/ipv4/netfilter/arp_tables.c | 47 ++++++++++++++++++----------------- net/ipv4/netfilter/ip_tables.c | 45 ++++++++++++++++++---------------- net/ipv6/netfilter/ip6_tables.c | 45 ++++++++++++++++++---------------- net/netfilter/x_tables.c | 50 ++++++++++++++++++++++++++++++++++++++ 5 files changed, 127 insertions(+), 64 deletions(-)
include/linux/netfilter/x_tables.h +4 -0
@@ -246,6 +246,10 @@ int xt_check_entry_offsets(const void *base, const char *elems,unsigned int target_offset, unsigned int next_offset); +unsigned int *xt_alloc_entry_offsets (unsigned int size); +bool xt_find_jump_offset (const unsigned int *offsets, +unsigned int target,unsigned int size); +int xt_check_match (struct xt_mtchk_param *,unsigned int size,u_int8_t proto,bool inv_proto); int xt_check_target(struct xt_tgchk_param *, unsigned int size, u_int8_t proto,
net/ipv4/netfilter/arp_tables.c +25 -22
106 lines not on this page · raw message
net/ipv4/netfilter/ip_tables.c +24 -21
103 lines not on this page · raw message
net/ipv6/netfilter/ip6_tables.c +24 -21
103 lines not on this page · raw message
net/netfilter/x_tables.c +50 -0
56 lines not on this page · raw message
Signature · 1 line
2.7.3
Pablo Neira Ayuso
maintainerQuoted 5 lines · Florian Westphal
The dummy ruleset I used to test the original validation change was broken, most rules were unreachable and were not tested by
mark_source_chains().In some cases rulesets that used to load in a few seconds now require several minutes.
Thanks for fixing this so fast. I was a bit surprised this O(n!) validation was only taking 11% more time when you first posted this patchset.
Quoted 4 lines
sample ruleset that shows the behaviour:
echo "*filter"
for i in $(seq 0 100000);do
Quoted 8 lines
printf ":chain_%06x - [0:0]\n" $idone
for i in $(seq 0 100000);do
printf -- "-A INPUT -j chain_%06x\n" $i
printf -- "-A INPUT -j chain_%06x\n" $i
printf -- "-A INPUT -j chain_%06x\n" $i
done
echo COMMIT
Not exactly related to this patch.
As I said in the workshop, I would really to love to see more tests in our trees.
Is there any chance you can get reuse that tests/shell/ directory that Arturo made for nftables and place this in one of those scripts? You can inagurate it with this scripts, and others that you used to fix the lack of sanity checks (those actually would require some little C code though).
With something like this in place, we can all validate better that tests are not broken and catch regressions.
Thanks!
Florian Westphal
maintainerQuoted 10 lines · Pablo Neira Ayuso
Quoted 5 lines · Florian Westphal
The dummy ruleset I used to test the original validation change was broken, most rules were unreachable and were not tested by
mark_source_chains().In some cases rulesets that used to load in a few seconds now require several minutes.
Thanks for fixing this so fast. I was a bit surprised this O(n!) validation was only taking 11% more time when you first posted this patchset.
Indeed ...
Quoted 15 lines
Quoted 4 lines
sample ruleset that shows the behaviour:
echo "*filter"
for i in $(seq 0 100000);doQuoted 8 lines
printf ":chain_%06x - [0:0]\n" $idone
for i in $(seq 0 100000);do
printf -- "-A INPUT -j chain_%06x\n" $i
printf -- "-A INPUT -j chain_%06x\n" $i
printf -- "-A INPUT -j chain_%06x\n" $i
done
echo COMMITNot exactly related to this patch.
Quoted 8 lines
As I said in the workshop, I would really to love to see more tests in our trees.
Is there any chance you can get reuse that tests/shell/ directory that Arturo made for nftables and place this in one of those scripts? You can inagurate it with this scripts, and others that you used to fix the lack of sanity checks (those actually would require some little C code though).
Yes, I will see if I can do this.
Quoted 2 lines · Florian Westphal
After this change ruleset restore times get again close to what one gets when reverting
36472341017529e(~3 seconds on my workstation).
Applied, thanks.