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>

1 files changed, 2 insertions, 0 deletions

diff --git a/net/ipv6/netfilter/ip6_tables.c b/net/ipv6/netfilter/ip6_tables.c
index 455582384ece..0c9973a657fb 100644
--- a/net/ipv6/netfilter/ip6_tables.c
+++ b/net/ipv6/netfilter/ip6_tables.c
@@ -1093,6 +1093,7 @@ static int compat_table_info(const struct xt_table_info *info,
         memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
         newinfo->initial_entries = 0;
         loc_cpu_entry = info->entries[raw_smp_processor_id()];
+        xt_compat_init_offsets(AF_INET6, info->number);
         xt_entry_foreach(iter, loc_cpu_entry, info->size) {
                 ret = compat_calc_entry(iter, info, loc_cpu_entry, newinfo);
                 if (ret != 0)
@@ -1696,6 +1697,7 @@ translate_compat_table(struct net *net,
         duprintf("translate_compat_table: size %u\n", info->size);
         j = 0;
         xt_compat_lock(AF_INET6);
+        xt_compat_init_offsets(AF_INET6, number);
         /* Walk through entries, checking offsets. */
         xt_entry_foreach(iter0, entry0, total_size) {
                 ret = check_compat_entry_size_and_hooks(iter0, info, &size,