Skip to contentSkip to conversation

netfilter: x_tables: speed up jump target validation

PATCH Superseded Florian Westphal 1 participant 2 messages Jul 13, 2016 – Jul 14, 2016

Subsystems (2)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Florian Westphal

author maintainer
#0 lore raw

PATCH v2 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 ]

78401416, count 500009
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")

---
Changes since 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/ip_tables.c     | 45 ++++++++++++++++++----------------
 net/ipv6/netfilter/ip6_tables.c    | 45 ++++++++++++++++++----------------
 net/netfilter/x_tables.c           | 50 ++++++++++++++++++++++++++++++++++++++
 4 files changed, 102 insertions(+), 42 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/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
author maintainer
#1 lore raw
Quoted 2 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().

...

I will send a v3 to also include arptables.
I thought arptables was irrelevant since arptable rulesets are usually very small but I forgot about DoS angle (we use single mutext for all net nsamespaces).