diff options
author | Eric Dumazet <eric.dumazet@gmail.com> | 2010-12-18 12:35:15 -0500 |
---|---|---|
committer | Pablo Neira Ayuso <pablo@netfilter.org> | 2011-01-13 06:05:12 -0500 |
commit | 255d0dc34068a976550ce555e153c0bfcfec7cc6 (patch) | |
tree | e936c3d55eaf144cbc4edf8f9332d8089719d0d4 /include/linux/netfilter | |
parent | b017900aac4a158b9bf7ffdcb8a369a91115b3e4 (diff) |
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')
-rw-r--r-- | include/linux/netfilter/x_tables.h | 3 |
1 files changed, 2 insertions, 1 deletions
diff --git a/include/linux/netfilter/x_tables.h b/include/linux/netfilter/x_tables.h index 742bec05144..0f04d985b41 100644 --- a/include/linux/netfilter/x_tables.h +++ b/include/linux/netfilter/x_tables.h | |||
@@ -611,8 +611,9 @@ struct _compat_xt_align { | |||
611 | extern void xt_compat_lock(u_int8_t af); | 611 | extern void xt_compat_lock(u_int8_t af); |
612 | extern void xt_compat_unlock(u_int8_t af); | 612 | extern void xt_compat_unlock(u_int8_t af); |
613 | 613 | ||
614 | extern int xt_compat_add_offset(u_int8_t af, unsigned int offset, short delta); | 614 | extern int xt_compat_add_offset(u_int8_t af, unsigned int offset, int delta); |
615 | extern void xt_compat_flush_offsets(u_int8_t af); | 615 | extern void xt_compat_flush_offsets(u_int8_t af); |
616 | extern void xt_compat_init_offsets(u_int8_t af, unsigned int number); | ||
616 | extern int xt_compat_calc_jump(u_int8_t af, unsigned int offset); | 617 | extern int xt_compat_calc_jump(u_int8_t af, unsigned int offset); |
617 | 618 | ||
618 | extern int xt_compat_match_offset(const struct xt_match *match); | 619 | extern int xt_compat_match_offset(const struct xt_match *match); |