aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorAl Viro <viro@zeniv.linux.org.uk>2006-12-12 03:29:52 -0500
committerDavid S. Miller <davem@sunset.davemloft.net>2006-12-13 19:48:23 -0500
commite1b4b9f3986b80d5785d91dbd8d72cfaf9fd1117 (patch)
tree96732395f387104b7af0641a5127352dc0d6124d /net
parenta96be24679198469df28976c809575423e70d843 (diff)
[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>
Diffstat (limited to 'net')
-rw-r--r--net/ipv4/netfilter/arp_tables.c5
-rw-r--r--net/ipv4/netfilter/ip_tables.c5
-rw-r--r--net/ipv6/netfilter/ip6_tables.c5
3 files changed, 9 insertions, 6 deletions
diff --git a/net/ipv4/netfilter/arp_tables.c b/net/ipv4/netfilter/arp_tables.c
index 71b76ade00e1..9aa22398b3dc 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,
358 for (;;) { 358 for (;;) {
359 struct arpt_standard_target *t 359 struct arpt_standard_target *t
360 = (void *)arpt_get_target(e); 360 = (void *)arpt_get_target(e);
361 int visited = e->comefrom & (1 << hook);
361 362
362 if (e->comefrom & (1 << NF_ARP_NUMHOOKS)) { 363 if (e->comefrom & (1 << NF_ARP_NUMHOOKS)) {
363 printk("arptables: loop hook %u pos %u %08X.\n", 364 printk("arptables: loop hook %u pos %u %08X.\n",
@@ -368,11 +369,11 @@ static int mark_source_chains(struct xt_table_info *newinfo,
368 |= ((1 << hook) | (1 << NF_ARP_NUMHOOKS)); 369 |= ((1 << hook) | (1 << NF_ARP_NUMHOOKS));
369 370
370 /* Unconditional return/END. */ 371 /* Unconditional return/END. */
371 if (e->target_offset == sizeof(struct arpt_entry) 372 if ((e->target_offset == sizeof(struct arpt_entry)
372 && (strcmp(t->target.u.user.name, 373 && (strcmp(t->target.u.user.name,
373 ARPT_STANDARD_TARGET) == 0) 374 ARPT_STANDARD_TARGET) == 0)
374 && t->verdict < 0 375 && t->verdict < 0
375 && unconditional(&e->arp)) { 376 && unconditional(&e->arp)) || visited) {
376 unsigned int oldpos, size; 377 unsigned int oldpos, size;
377 378
378 if (t->verdict < -NF_MAX_VERDICT - 1) { 379 if (t->verdict < -NF_MAX_VERDICT - 1) {
diff --git a/net/ipv4/netfilter/ip_tables.c b/net/ipv4/netfilter/ip_tables.c
index 83ebbeb80b6e..09696f16aa95 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,
384 for (;;) { 384 for (;;) {
385 struct ipt_standard_target *t 385 struct ipt_standard_target *t
386 = (void *)ipt_get_target(e); 386 = (void *)ipt_get_target(e);
387 int visited = e->comefrom & (1 << hook);
387 388
388 if (e->comefrom & (1 << NF_IP_NUMHOOKS)) { 389 if (e->comefrom & (1 << NF_IP_NUMHOOKS)) {
389 printk("iptables: loop hook %u pos %u %08X.\n", 390 printk("iptables: loop hook %u pos %u %08X.\n",
@@ -394,11 +395,11 @@ mark_source_chains(struct xt_table_info *newinfo,
394 |= ((1 << hook) | (1 << NF_IP_NUMHOOKS)); 395 |= ((1 << hook) | (1 << NF_IP_NUMHOOKS));
395 396
396 /* Unconditional return/END. */ 397 /* Unconditional return/END. */
397 if (e->target_offset == sizeof(struct ipt_entry) 398 if ((e->target_offset == sizeof(struct ipt_entry)
398 && (strcmp(t->target.u.user.name, 399 && (strcmp(t->target.u.user.name,
399 IPT_STANDARD_TARGET) == 0) 400 IPT_STANDARD_TARGET) == 0)
400 && t->verdict < 0 401 && t->verdict < 0
401 && unconditional(&e->ip)) { 402 && unconditional(&e->ip)) || visited) {
402 unsigned int oldpos, size; 403 unsigned int oldpos, size;
403 404
404 if (t->verdict < -NF_MAX_VERDICT - 1) { 405 if (t->verdict < -NF_MAX_VERDICT - 1) {
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,
413 unsigned int pos = newinfo->hook_entry[hook]; 413 unsigned int pos = newinfo->hook_entry[hook];
414 struct ip6t_entry *e 414 struct ip6t_entry *e
415 = (struct ip6t_entry *)(entry0 + pos); 415 = (struct ip6t_entry *)(entry0 + pos);
416 int visited = e->comefrom & (1 << hook);
416 417
417 if (!(valid_hooks & (1 << hook))) 418 if (!(valid_hooks & (1 << hook)))
418 continue; 419 continue;
@@ -433,11 +434,11 @@ mark_source_chains(struct xt_table_info *newinfo,
433 |= ((1 << hook) | (1 << NF_IP6_NUMHOOKS)); 434 |= ((1 << hook) | (1 << NF_IP6_NUMHOOKS));
434 435
435 /* Unconditional return/END. */ 436 /* Unconditional return/END. */
436 if (e->target_offset == sizeof(struct ip6t_entry) 437 if ((e->target_offset == sizeof(struct ip6t_entry)
437 && (strcmp(t->target.u.user.name, 438 && (strcmp(t->target.u.user.name,
438 IP6T_STANDARD_TARGET) == 0) 439 IP6T_STANDARD_TARGET) == 0)
439 && t->verdict < 0 440 && t->verdict < 0
440 && unconditional(&e->ipv6)) { 441 && unconditional(&e->ipv6)) || visited) {
441 unsigned int oldpos, size; 442 unsigned int oldpos, size;
442 443
443 if (t->verdict < -NF_MAX_VERDICT - 1) { 444 if (t->verdict < -NF_MAX_VERDICT - 1) {