Skip to main content

Browse the archive

Staging
v0.5.1
https://github.com/torvalds/linux
02 December 2023, 22:23:51 UTC
Revision e1b4b9f3986b80d5785d91dbd8d72cfaf9fd1117 authored by Al Viro on 12 December 2006, 08:29:52 UTC, committed by David S. Miller on 14 December 2006, 00:48:23 UTC 
[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 parent a96be24
History
Tip revision: e1b4b9f3986b80d5785d91dbd8d72cfaf9fd1117 authored by Al Viro on 12 December 2006, 08:29:52 UTC
[NETFILTER]: {ip,ip6,arp}_tables: fix exponential worst-case search for loops
Tip revision: e1b4b9f
File Mode Size
Kconfig -rw-r--r-- 1.5 KB
Kconfig.iosched -rw-r--r-- 1.9 KB
Makefile -rw-r--r-- 347 bytes
as-iosched.c -rw-r--r-- 37.7 KB
blktrace.c -rw-r--r-- 12.4 KB
cfq-iosched.c -rw-r--r-- 51.4 KB
deadline-iosched.c -rw-r--r-- 11.6 KB
elevator.c -rw-r--r-- 24.4 KB
genhd.c -rw-r--r-- 17.4 KB
ioctl.c -rw-r--r-- 7.4 KB
ll_rw_blk.c -rw-r--r-- 102.6 KB
noop-iosched.c -rw-r--r-- 2.5 KB
scsi_ioctl.c -rw-r--r-- 16.3 KB
back to top