Skip to contentSkip to conversation

Patch "netfilter: x_tables: speed up jump target validation" has been added to the 4.4-stable tree

PATCH [email protected] 1 participant 1 message Jan 24, 2018

Subsystems (3)
lore
Share & tools
lore

[email protected]

author maintainer Applied
#0 lore raw

This is a note to let you know that I've just added the patch titled

netfilter: x_tables: speed up jump target validation

to the 4.4-stable tree which can be found at:
http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
netfilter-x_tables-speed-up-jump-target-validation.patch
and it can be found in the queue-4.4 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree, please let <[email protected]> know about it.

Quoted 1 line

From f4dc77713f8016d2e8a3295e1c9c53a21f296def Mon Sep 17 00:00:00 2001

From: Florian Westphal <[email protected]>
Date: Thu, 14 Jul 2016 17:51:26 +0200
Subject: netfilter: x_tables: speed up jump target validation

From: Florian Westphal <[email protected]>

commit f4dc77713f8016d2e8a3295e1c9c53a21f296def upstream.

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")
---
 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
@@ -243,6 +243,10 @@ int xt_check_entry_offsets(const void *b
 			   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

112 lines not on this page · raw message

net/ipv4/netfilter/ip_tables.c +24 -21

109 lines not on this page · raw message

net/ipv6/netfilter/ip6_tables.c +24 -21

109 lines not on this page · raw message

net/netfilter/x_tables.c +50 -0

56 lines not on this page · raw message

Patches currently in stable-queue which might be from [email protected] are

queue-4.4/netfilter-x_tables-speed-up-jump-target-validation.patch queue-4.4/netfilter-arp_tables-fix-invoking-32bit-iptable-p-input-accept-failed-in-64bit-kernel.patch queue-4.4/netfilter-restart-search-if-moved-to-other-chain.patch queue-4.4/netfilter-nfnetlink_queue-reject-verdict-request-from-different-portid.patch