diff options
| author |   Eric Dumazet <eric.dumazet@gmail.com> | 2010-12-18 18:35:15 +0100 |
|---|---|---|
| committer |   Pablo Neira Ayuso <pablo@netfilter.org> | 2011-01-13 12:05:12 +0100 |
| commit | 255d0dc34068a976550ce555e153c0bfcfec7cc6 (patch) | |
| tree | e936c3d55eaf144cbc4edf8f9332d8089719d0d4 /include/linux/netfilter_bridge | |
| parent | netfilter: xt_conntrack: support matching on port ranges (diff) | |
| download | linux-dev-255d0dc34068a976550ce555e153c0bfcfec7cc6.tar.xz linux-dev-255d0dc34068a976550ce555e153c0bfcfec7cc6.zip | |
netfilter: x_table: speedup compat operations
One iptables invocation with 135000 rules takes 35 seconds of cpu time
on a recent server, using a 32bit distro and a 64bit kernel.
We eventually trigger NMI/RCU watchdog.
INFO: rcu_sched_state detected stall on CPU 3 (t=6000 jiffies)
COMPAT mode has quadratic behavior and consume 16 bytes of memory per
rule.
Switch the xt_compat algos to use an array instead of list, and use a
binary search to locate an offset in the sorted array.
This halves memory need (8 bytes per rule), and removes quadratic
behavior [ O(N*N) -> O(N*log2(N)) ]
Time of iptables goes from 35 s to 150 ms.
Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Diffstat (limited to 'include/linux/netfilter_bridge')
0 files changed, 0 insertions, 0 deletions