Gitweb:     
http://git.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=e1b4b9f3986b80d5785d91dbd8d72cfaf9fd1117
Commit:     e1b4b9f3986b80d5785d91dbd8d72cfaf9fd1117
Parent:     a96be24679198469df28976c809575423e70d843
Author:     Al Viro <[EMAIL PROTECTED]>
AuthorDate: Tue Dec 12 00:29:52 2006 -0800
Committer:  David S. Miller <[EMAIL PROTECTED]>
CommitDate: Wed Dec 13 16:48:23 2006 -0800

    [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 <[EMAIL PROTECTED]>
    Signed-off-by: Patrick McHardy <[EMAIL PROTECTED]>
    Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
---
 net/ipv4/netfilter/arp_tables.c |    5 +++--
 net/ipv4/netfilter/ip_tables.c  |    5 +++--
 net/ipv6/netfilter/ip6_tables.c |    5 +++--
 3 files changed, 9 insertions(+), 6 deletions(-)

diff --git a/net/ipv4/netfilter/arp_tables.c b/net/ipv4/netfilter/arp_tables.c
index 71b76ad..9aa2239 100644
--- a/net/ipv4/netfilter/arp_tables.c
+++ b/net/ipv4/netfilter/arp_tables.c
@@ -358,6 +358,7 @@ static int mark_source_chains(struct xt_table_info *newinfo,
                for (;;) {
                        struct arpt_standard_target *t
                                = (void *)arpt_get_target(e);
+                       int visited = e->comefrom & (1 << hook);
 
                        if (e->comefrom & (1 << NF_ARP_NUMHOOKS)) {
                                printk("arptables: loop hook %u pos %u %08X.\n",
@@ -368,11 +369,11 @@ static int mark_source_chains(struct xt_table_info 
*newinfo,
                                |= ((1 << hook) | (1 << NF_ARP_NUMHOOKS));
 
                        /* Unconditional return/END. */
-                       if (e->target_offset == sizeof(struct arpt_entry)
+                       if ((e->target_offset == sizeof(struct arpt_entry)
                            && (strcmp(t->target.u.user.name,
                                       ARPT_STANDARD_TARGET) == 0)
                            && t->verdict < 0
-                           && unconditional(&e->arp)) {
+                           && unconditional(&e->arp)) || visited) {
                                unsigned int oldpos, size;
 
                                if (t->verdict < -NF_MAX_VERDICT - 1) {
diff --git a/net/ipv4/netfilter/ip_tables.c b/net/ipv4/netfilter/ip_tables.c
index 83ebbeb..09696f1 100644
--- a/net/ipv4/netfilter/ip_tables.c
+++ b/net/ipv4/netfilter/ip_tables.c
@@ -384,6 +384,7 @@ mark_source_chains(struct xt_table_info *newinfo,
                for (;;) {
                        struct ipt_standard_target *t
                                = (void *)ipt_get_target(e);
+                       int visited = e->comefrom & (1 << hook);
 
                        if (e->comefrom & (1 << NF_IP_NUMHOOKS)) {
                                printk("iptables: loop hook %u pos %u %08X.\n",
@@ -394,11 +395,11 @@ mark_source_chains(struct xt_table_info *newinfo,
                                |= ((1 << hook) | (1 << NF_IP_NUMHOOKS));
 
                        /* Unconditional return/END. */
-                       if (e->target_offset == sizeof(struct ipt_entry)
+                       if ((e->target_offset == sizeof(struct ipt_entry)
                            && (strcmp(t->target.u.user.name,
                                       IPT_STANDARD_TARGET) == 0)
                            && t->verdict < 0
-                           && unconditional(&e->ip)) {
+                           && unconditional(&e->ip)) || visited) {
                                unsigned int oldpos, size;
 
                                if (t->verdict < -NF_MAX_VERDICT - 1) {
diff --git a/net/ipv6/netfilter/ip6_tables.c b/net/ipv6/netfilter/ip6_tables.c
index 4eec4b3..99502c5 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) {
-
To unsubscribe from this list: send the line "unsubscribe git-commits-head" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to