Skip to contentSkip to conversation

netfilter: x_tables: speed up jump target validation

PATCH Applied Florian Westphal 2 participants 4 messages Jul 14, 2016 – Jul 19, 2016

Subsystems (2)
lore
Share & tools
lore

Florian Westphal

author maintainer
#0 lore raw

PATCH 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

Fixes 36472341017529e ("netfilter: x_tables: validate targets of jumps")

---
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
index dc4f58a..5f968a3 100644
@@ -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
#1 lore raw
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.

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" $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

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!

author maintainer
#2 lore raw
Quoted 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);do

Quoted 8 lines
        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

Not 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.

maintainer Applied
#3 lore raw
In reply to Florian Westphal
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.