exponential worst-case search for loops (ip_tables.c)
Subsystems (2)
PATCH 1/1 exponential worst-case search for loops (ip_tables.c)
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]>
--- net/ipv4/netfilter/ip_tables.c | 5 +++-- 1 files changed, 3 insertions(+), 2 deletions(-)
net/ipv4/netfilter/ip_tables.c +3 -2
@@ -384,6 +384,7 @@ mark_source_chains(struct xt_table_infofor (;;) {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 |= ((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;/* Return: backtrack through the last
Signature · 1 line
1.4.2.GIT