]> git.baikalelectronics.ru Git - kernel.git/commit
[NETFILTER]: {ip,ip6,arp}_tables: fix exponential worst-case search for loops
authorAl Viro <viro@zeniv.linux.org.uk>
Tue, 12 Dec 2006 08:29:52 +0000 (00:29 -0800)
committerDavid S. Miller <davem@sunset.davemloft.net>
Thu, 14 Dec 2006 00:48:23 +0000 (16:48 -0800)
commit3c614201c16c446eb24b7f4db1776f7ed7bb8357
tree96732395f387104b7af0641a5127352dc0d6124d
parent6ca59efe5c4e25a26df2f650a8e133bb16cc1602
[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>
net/ipv4/netfilter/arp_tables.c
net/ipv4/netfilter/ip_tables.c
net/ipv6/netfilter/ip6_tables.c