| Message ID | 1468341323-15047-1-git-send-email-fw@strlen.de |
|---|---|
| State | Changes Requested |
| Delegated to: | Pablo Neira |
| Headers | show |
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 On Tue, Jul 12, 2016 at 9:35 AM, Florian Westphal <fw@strlen.de> wrote: > 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). > > Fixes: 36472341017529e ("netfilter: x_tables: validate targets of jumps") > Reported-by: Jeff Wu <wujiafu@gmail.com> > Signed-off-by: Florian Westphal <fw@strlen.de> > --- > 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(-) > > diff --git a/include/linux/netfilter/x_tables.h b/include/linux/netfilter/x_tables.h > index dc4f58a..5f968a3 100644 > --- a/include/linux/netfilter/x_tables.h > +++ b/include/linux/netfilter/x_tables.h > @@ -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, > diff --git a/net/ipv4/netfilter/ip_tables.c b/net/ipv4/netfilter/ip_tables.c > index 54906e0..f243769 100644 > --- a/net/ipv4/netfilter/ip_tables.c > +++ b/net/ipv4/netfilter/ip_tables.c > @@ -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 void > diff --git a/net/ipv6/netfilter/ip6_tables.c b/net/ipv6/netfilter/ip6_tables.c > index 63e06c3..02cf11f 100644 > --- a/net/ipv6/netfilter/ip6_tables.c > +++ b/net/ipv6/netfilter/ip6_tables.c > @@ -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 void > diff --git a/net/netfilter/x_tables.c b/net/netfilter/x_tables.c > index 2675d58..95e044a 100644 > --- a/net/netfilter/x_tables.c > +++ b/net/netfilter/x_tables.c > @@ -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 > -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Applied this patch on Debian 3.16.7-ckt25-2+deb8u3 and it works great! Jeff On Tue, Jul 12, 2016 at 1:57 PM, Jeff Wu <wujiafu@gmail.com> wrote: > 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 > -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Florian Westphal <fw@strlen.de> wrote: > + 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; 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. -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/include/linux/netfilter/x_tables.h b/include/linux/netfilter/x_tables.h index dc4f58a..5f968a3 100644 --- a/include/linux/netfilter/x_tables.h +++ b/include/linux/netfilter/x_tables.h @@ -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, diff --git a/net/ipv4/netfilter/ip_tables.c b/net/ipv4/netfilter/ip_tables.c index 54906e0..f243769 100644 --- a/net/ipv4/netfilter/ip_tables.c +++ b/net/ipv4/netfilter/ip_tables.c @@ -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 void diff --git a/net/ipv6/netfilter/ip6_tables.c b/net/ipv6/netfilter/ip6_tables.c index 63e06c3..02cf11f 100644 --- a/net/ipv6/netfilter/ip6_tables.c +++ b/net/ipv6/netfilter/ip6_tables.c @@ -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 void diff --git a/net/netfilter/x_tables.c b/net/netfilter/x_tables.c index 2675d58..95e044a 100644 --- a/net/netfilter/x_tables.c +++ b/net/netfilter/x_tables.c @@ -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) {
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). Fixes: 36472341017529e ("netfilter: x_tables: validate targets of jumps") Reported-by: Jeff Wu <wujiafu@gmail.com> Signed-off-by: Florian Westphal <fw@strlen.de> --- 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(-)