netfilter: x_tables: speed up jump target validation
Subsystems (2)
Florian Westphal
maintainerPATCH 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 exhibits 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 128mbyte in size, with ~100k searches though the 100k 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 (~6 seconds on my workstation).
---
Jeff, it would be nice if you can check if this works for you.
The same patch (but with a few changes so it applies to 4.6-stable
where we still have a bunch of debug printks which makes cherry-pick fail...) is here:
http://www.strlen.de/fw/0001-netfilter-x_tables-speed-up-jump-target-validation.patch
Pablo, I know its later for -nf -- please put it in -next if needed, it applies cleanly there as well.
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
@@ -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
Cool! I applied your previous ipv4 only patch(bsearch_offsets.patch) on Debian 3.16.36-1 kernel and it works great!
Now, I'm trying this full patch.
Thanks!
Jeff
Quoted 359 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.
sample ruleset that exhibits the behaviour:
echo "*filter"
for i in $(seq 0 100000);doprintf ":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[ pipe result into iptables-restore ]
This ruleset will be about 128mbyte in size, with ~100k searches though the 100k 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_entrystruct, 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(~6 seconds on my workstation).Fixes 36472341017529e ("netfilter: x_tables: validate targets of jumps")Reported-by Jeff Wu <[email protected]>Signed-off-by Florian Westphal <[email protected]>---
Jeff, it would be nice if you can check if this works for you.The same patch (but with a few changes so it applies to 4.6-stable
where we still have a bunch of debug printks which makes cherry-pick fail...) is here:http://www.strlen.de/fw/0001-netfilter-x_tables-speed-up-jump-target-validation.patch
Pablo, I know its later for -nf -- please put it in -next if needed, it applies cleanly there as well.
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@@ -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@@ -375,23 +375,12 @@ ipt_do_table(struct sk_buff *skb,else return verdict; } -static bool find_jump_target (const struct xt_table_info *t, -const struct ipt_entry *target) -{ -struct ipt_entry *iter; - - xt_entry_foreach(iter, t->entries, t->size) { -if (iter == target) -return true; - } -return false; -} -/* Figures out from what hook each rule can be called: returns 0 if there are loops. Puts hook bitmask in comefrom. */ static int mark_source_chains (const struct xt_table_info *newinfo, -unsigned int valid_hooks,void *entry0) +unsigned int valid_hooks,void *entry0, +unsigned int *offsets) {unsigned int hook;@@ -460,10 +449,11 @@ mark_source_chains(const struct xt_table_info *newinfo, XT_STANDARD_TARGET) == 0 && newpos >= 0) {/* This a jump; chase it. */ +if (!xt_find_jump_offset (offsets, newpos, + newinfo->number)) +return 0 ; e = (struct ipt_entry *) (entry0 + newpos); -if (!find_jump_target (newinfo, e)) -return 0 ; } else {/* ... this is a fallthru */ newpos = pos + e->next_offset;@@ -696,6 +686,7 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, const struct ipt_replace *repl) {struct ipt_entry *iter; +unsigned int *offsets;unsigned int i;int ret =0 ;@@ -708,6 +699,9 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, newinfo->underflow[i] =0xFFFFFFFF ; } + offsets =xt_alloc_entry_offsets (newinfo->number); +if (!offsets) +return -ENOMEM ; i =0 ;/* Walk through entries, checking offsets. */ xt_entry_foreach(iter, entry0, newinfo->size) {@@ -717,15 +711,18 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, repl->underflow, repl->valid_hooks);if (ret !=0 ) -return ret; + goto out_free; +if (offsets && i < repl->num_entries) + offsets[i] = (void *)iter - entry0; ++i;if (strcmp (ipt_get_target (iter)->u.user.name,XT_ERROR_TARGET ) ==0 ) ++newinfo->stacksize; } + ret = -EINVAL ;if (i != repl->num_entries) -return -EINVAL ; + goto out_free;/* Check hooks all assigned */ for (i =0 ; i <NF_INET_NUMHOOKS ; i++) {@@ -733,13 +730,16 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0,if (!(repl->valid_hooks & (1 << i)))continue ;if (newinfo->hook_entry[i] ==0xFFFFFFFF ) -return -EINVAL ; + goto out_free;if (newinfo->underflow[i] ==0xFFFFFFFF ) -return -EINVAL ; + goto out_free; } -if (!mark_source_chains (newinfo, repl->valid_hooks, entry0)) -return -ELOOP ; +if (!mark_source_chains (newinfo, repl->valid_hooks, entry0, offsets)) { + ret = -ELOOP ; + goto out_free; + } +kvfree (offsets);/* Finally, each sanity check must pass */ i =0 ;@@ -760,6 +760,9 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, }return ret; + out_free: +kvfree (offsets); +return ret; } static voidnet/ipv6/netfilter/ip6_tables.c +24
-21@@ -402,23 +402,12 @@ ip6t_do_table(struct sk_buff *skb,else return verdict; } -static bool find_jump_target (const struct xt_table_info *t, -const struct ip6t_entry *target) -{ -struct ip6t_entry *iter; - - xt_entry_foreach(iter, t->entries, t->size) { -if (iter == target) -return true; - } -return false; -} -/* Figures out from what hook each rule can be called: returns 0 if there are loops. Puts hook bitmask in comefrom. */ static int mark_source_chains (const struct xt_table_info *newinfo, -unsigned int valid_hooks,void *entry0) +unsigned int valid_hooks,void *entry0, +unsigned int *offsets) {unsigned int hook;@@ -487,10 +476,11 @@ mark_source_chains(const struct xt_table_info *newinfo, XT_STANDARD_TARGET) == 0 && newpos >= 0) {/* This a jump; chase it. */ +if (!xt_find_jump_offset (offsets, newpos, + newinfo->number)) +return 0 ; e = (struct ip6t_entry *) (entry0 + newpos); -if (!find_jump_target (newinfo, e)) -return 0 ; } else {/* ... this is a fallthru */ newpos = pos + e->next_offset;@@ -724,6 +714,7 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, const struct ip6t_replace *repl) {struct ip6t_entry *iter; +unsigned int *offsets;unsigned int i;int ret =0 ;@@ -736,6 +727,9 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, newinfo->underflow[i] =0xFFFFFFFF ; } + offsets =xt_alloc_entry_offsets (newinfo->number); +if (!offsets) +return -ENOMEM ; i =0 ;/* Walk through entries, checking offsets. */ xt_entry_foreach(iter, entry0, newinfo->size) {@@ -745,15 +739,18 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, repl->underflow, repl->valid_hooks);if (ret !=0 ) -return ret; + goto out_free; +if (offsets && i < repl->num_entries) + offsets[i] = (void *)iter - entry0; ++i;if (strcmp (ip6t_get_target (iter)->u.user.name,XT_ERROR_TARGET ) ==0 ) ++newinfo->stacksize; } + ret = -EINVAL ;if (i != repl->num_entries) -return -EINVAL ; + goto out_free;/* Check hooks all assigned */ for (i =0 ; i <NF_INET_NUMHOOKS ; i++) {@@ -761,13 +758,16 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0,if (!(repl->valid_hooks & (1 << i)))continue ;if (newinfo->hook_entry[i] ==0xFFFFFFFF ) -return -EINVAL ; + goto out_free;if (newinfo->underflow[i] ==0xFFFFFFFF ) -return -EINVAL ; + goto out_free; } -if (!mark_source_chains (newinfo, repl->valid_hooks, entry0)) -return -ELOOP ; +if (!mark_source_chains (newinfo, repl->valid_hooks, entry0, offsets)) { + ret = -ELOOP ; + goto out_free; + } +kvfree (offsets);/* Finally, each sanity check must pass */ i =0 ;@@ -788,6 +788,9 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, }return ret; + out_free: +kvfree (offsets); +return ret; } static voidnet/netfilter/x_tables.c +50
-1@@ -702,6 +702,56 @@ int xt_check_entry_offsets(const void *base, }EXPORT_SYMBOL (xt_check_entry_offsets); +/** +* xt_alloc_entry_offsets - allocate array to store rule head offsets +* +* @size: number of entries +* +* Return: NULL or kmalloc'd or vmalloc'd array +*/ +unsigned int *xt_alloc_entry_offsets (unsigned int size) +{ +unsigned int *off; + + off =kcalloc (size,sizeof (unsigned int ),GFP_KERNEL | __GFP_NOWARN); + +if (off) +return off; + +if (size < (SIZE_MAX /sizeof (unsigned int ))) + off =vmalloc (size *sizeof (unsigned int )); + +return off; +} +EXPORT_SYMBOL (xt_alloc_entry_offsets); + +/** +* xt_find_jump_offset - check if target is a valid jump offset +* +* @offsets: array containing all valid rule start offsets of a rule blob +* @target: the jump target to search for +* @size: entries in @offset +*/ +bool xt_find_jump_offset (const unsigned int *offsets, +unsigned int target,unsigned int size) +{ +int m, low =0 , hi = size; + +while (hi > low) { + m = (low + hi) /2u ; + +if (offsets[m] > target) + hi = m; +else if (offsets[m] < target) + low = m +1 ; +else +return true; + } + +return false; +} +EXPORT_SYMBOL (xt_find_jump_offset); +int xt_check_target (struct xt_tgchk_param *par,unsigned int size,u_int8_t proto,bool inv_proto) { --2.7.3
Applied this patch on Debian 3.16.7-ckt25-2+deb8u3 and it works great!
Jeff
Quoted 9 lines · Jeff Wu
Cool! I applied your previous ipv4 only
patch(bsearch_offsets.patch)on Debian 3.16.36-1 kernel and it works great!Now, I'm trying this full patch.
Thanks!
Jeff
Florian Westphal
maintainerQuoted 7 lines · Florian Westphal
net/ipv4/netfilter/ip_tables.c +3
-0+ offsets =xt_alloc_entry_offsets (newinfo->number); +if (!offsets) +return -ENOMEM ; i =0 ;/* Walk through entries, checking offsets. */ xt_entry_foreach(iter, entry0, newinfo->size) {
net/ipv4/netfilter/ip_tables.c translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, · line 717
Quoted 8 lines
net/ipv4/netfilter/ip_tables.c +3
-1@@ -717,15 +711,18 @@ translate_table(struct net *net, struct xt_table_info *newinfo, void *entry0, repl->underflow, repl->valid_hooks);if (ret !=0 ) -return ret; + goto out_free; +if (offsets && i < repl->num_entries) + offsets[i] = (void *)iter - entry0; ++i;
Ahem. This superflous "offsets &&" hunk is a left-over of the old version that did not -ENOMEM on xt_alloc_entry_offsets error.
I will submit a v2 tomorrow that removes this part.