netfilter: x_table: speedup compat operations
authorEric Dumazet <eric.dumazet@gmail.com>
Sat, 18 Dec 2010 17:35:15 +0000 (18:35 +0100)
committerPablo Neira Ayuso <pablo@netfilter.org>
Thu, 13 Jan 2011 11:05:12 +0000 (12:05 +0100)
commit255d0dc34068a976550ce555e153c0bfcfec7cc6
treee936c3d55eaf144cbc4edf8f9332d8089719d0d4
parentb017900aac4a158b9bf7ffdcb8a369a91115b3e4
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>
include/linux/netfilter/x_tables.h
net/bridge/netfilter/ebtables.c
net/ipv4/netfilter/arp_tables.c
net/ipv4/netfilter/ip_tables.c
net/ipv6/netfilter/ip6_tables.c
net/netfilter/x_tables.c