[NETFILTER]: {ip,ip6,arp}_tables: fix exponential worst-case search for loops

If we come to node we'd already marked as seen and it's not a part of path
(i.e. we don't have a loop right there), we already know that it isn't a
part of any loop, so we don't need to revisit it.

That speeds the things up if some chain is refered to from several places
and kills O(exp(table size)) worst-case behaviour (without sleeping,
at that, so if you manage to self-LART that way, you are SOL for a long
time)...

Signed-off-by: Al Viro <viro@zeniv.linux.org.uk>
Signed-off-by: Patrick McHardy <kaber@trash.net>
Signed-off-by: David S. Miller <davem@davemloft.net>

1 files changed, 3 insertions, 2 deletions

diff --git a/net/ipv6/netfilter/ip6_tables.c b/net/ipv6/netfilter/ip6_tables.c
index 4eec4b3988b8..99502c5da4c4 100644
--- a/net/ipv6/netfilter/ip6_tables.c
+++ b/net/ipv6/netfilter/ip6_tables.c
@@ -413,6 +413,7 @@ mark_source_chains(struct xt_table_info *newinfo,
                 unsigned int pos = newinfo->hook_entry[hook];
                 struct ip6t_entry *e
                         = (struct ip6t_entry *)(entry0 + pos);
+                int visited = e->comefrom & (1 << hook);
 
                 if (!(valid_hooks & (1 << hook)))
                         continue;
@@ -433,11 +434,11 @@ mark_source_chains(struct xt_table_info *newinfo,
                                 |= ((1 << hook) | (1 << NF_IP6_NUMHOOKS));
 
                         /* Unconditional return/END. */
-                        if (e->target_offset == sizeof(struct ip6t_entry)
+                        if ((e->target_offset == sizeof(struct ip6t_entry)
                             && (strcmp(t->target.u.user.name,
                                        IP6T_STANDARD_TARGET) == 0)
                             && t->verdict < 0
-                            && unconditional(&e->ipv6)) {
+                            && unconditional(&e->ipv6)) || visited) {
                                 unsigned int oldpos, size;
 
                                 if (t->verdict < -NF_MAX_VERDICT - 1) {