netfilter: remove the duplicate tables
Subsystems (3)
RFC PATCH 1/1 netfilter: remove the duplicate tables
As only xt_counters are private to each CPU, we don't need to maintain a whole individual table for each CPU.
In the kernel space, we use the memory of ipt_entry.counters to save a pointer to a percpu xt_counters. When iptables runs, it only update the counters on its own CPU.
On non SMP platforms, no change is made.
Only the code of iptables is converted. Thanks for reviews.
--- include/linux/netfilter/x_tables.h | 47 ++++++++++++++++-- net/ipv4/netfilter/ip_tables.c | 94 ++++++++++++++----------------------- net/netfilter/x_tables.c | 33 ++++-------- 3 files changed, 90 insertions(+), 84 deletions(-)
include/linux/netfilter/x_tables.h +41 -6
@@ -103,7 +103,6 @@ struct _xt_align {/* Error verdict. */ #define XT_ERROR_TARGET "ERROR" -#define SET_COUNTER (c,b,p) do { (c).bcnt = (b); (c).pcnt = (p); } while(0)#define ADD_COUNTER (c,b,p) do { (c).bcnt += (b); (c).pcnt += (p); } while(0)struct xt_counters {
@@ -404,13 +403,9 @@ struct xt_table_info {unsigned int stacksize;unsigned int __percpu *stackptr;void ***jumpstack; -/* ipt_entry tables: one per CPU */ -/* Note : this field MUST be the last one, see XT_TABLE_INFO_SZ */ -void *entries[1 ]; +void *entries; }; -#define XT_TABLE_INFO_SZ (offsetof(struct xt_table_info, entries) \ - + nr_cpu_ids * sizeof(char *))extern int xt_register_target (struct xt_target *target);extern void xt_unregister_target (struct xt_target *target);extern int xt_register_targets (struct xt_target *target,unsigned int n);
@@ -550,6 +545,46 @@ static inline unsigned long ifname_compare_aligned(const char *_a,extern struct nf_hook_ops *xt_hook_link (const struct xt_table *,nf_hookfn *);extern void xt_hook_unlink (const struct xt_table *,struct nf_hook_ops *); +#ifdef CONFIG_SMP +#define xt_counters_kern (c) (*(struct xt_counters __percpu **)(c)) +#endif + +static inline int xt_counters_kern_init (struct xt_counters *c) +{ +#ifdef CONFIG_SMP + xt_counters_kern(c) = alloc_percpu(struct xt_counters); +if (xt_counters_kern (c) ==NULL ) +return -ENOMEM ; +#endif +return 0 ; +} + +static inline void xt_counters_kern_destroy (struct xt_counters *c) +{ +#ifdef CONFIG_SMP +free_percpu (xt_counters_kern (c)); +#endif +} + +static inline struct xt_counters *xt_counters_kern_cpu (struct xt_counters *c, +int cpu) +{ +#ifdef CONFIG_SMP +return per_cpu_ptr (xt_counters_kern (c), cpu); +#else +return c; +#endif +} + +static inline struct xt_counters *xt_counters_kern_this (struct xt_counters *c) +{ +#ifdef CONFIG_SMP +return this_cpu_ptr (xt_counters_kern (c)); +#else +return c; +#endif +} +#ifdef CONFIG_COMPAT #include <net/compat.h>
net/ipv4/netfilter/ip_tables.c +37 -57
241 lines not on this page · raw message
net/netfilter/x_tables.c +12 -21
@@ -639,31 +639,24 @@ EXPORT_SYMBOL_GPL(xt_compat_target_to_user);struct xt_table_info *xt_alloc_table_info (unsigned int size) {struct xt_table_info *newinfo; -int cpu;/* Pedantry: prevent them from hitting BUG() in vmalloc.c --RR */ if ((SMP_ALIGN (size) >>PAGE_SHIFT ) +2 > totalram_pages)return NULL ; - newinfo =kzalloc (XT_TABLE_INFO_SZ ,GFP_KERNEL ); + newinfo =kzalloc (sizeof (*newinfo),GFP_KERNEL );if (!newinfo)return NULL ; newinfo->size = size; -for_each_possible_cpu (cpu) { -if (size <=PAGE_SIZE ) - newinfo->entries[cpu] =kmalloc_node (size, -GFP_KERNEL , -cpu_to_node (cpu)); -else - newinfo->entries[cpu] =vmalloc_node (size, -cpu_to_node (cpu)); - -if (newinfo->entries[cpu] ==NULL ) { -xt_free_table_info (newinfo); -return NULL ; - } +if (size <=PAGE_SIZE ) + newinfo->entries =kmalloc (size,GFP_KERNEL ); +else + newinfo->entries =vmalloc (size); +if (newinfo->entries ==NULL ) { +xt_free_table_info (newinfo); +return NULL ; }return newinfo;
@@ -674,12 +667,10 @@ void xt_free_table_info(struct xt_table_info *info) {int cpu; -for_each_possible_cpu (cpu) { -if (info->size <=PAGE_SIZE ) -kfree (info->entries[cpu]); -else -vfree (info->entries[cpu]); - } +if (info->size <=PAGE_SIZE ) +kfree (info->entries); +else +vfree (info->entries);if (info->jumpstack !=NULL ) {if (sizeof (void *) * info->stacksize >PAGE_SIZE ) {
Quoted 11 lines · Changli Gao
As only
xt_countersare private to each CPU, we don't need to maintain a whole individual table for each CPU.In the kernel space, we use the memory of ipt_entry.counters to save a pointer to a percpu
xt_counters. When iptables runs, it only update the counters on its own CPU.On non SMP platforms, no change is made.
Only the code of iptables is converted. Thanks for reviews.
Changli
I answered you a (difficult) work was in progress, still you post a patch that needs our review and time ? This is crazy.
I am tempted to stop here. Oh well...
Your way of allocating a percpu counter for each counter is a pure TLB and cache line blower (up to two cache lines per counter), not counting the time needed to load a new table with 10.000 entries. Some people still use scripts with hundred of calls to iptables.
percpu_alloc() is not meant to be used thousand of times per second. It is not scalable.
You consume 16 bytes per counter in the main table, while 4 bytes index should be enough on SMP build. Most firewalls I know use two or four cpus at most.
They care about speed, not really because iptables duplicates table on each cpu. By the way, not using NUMA can definitly hurt firewalls with many rules, unless you make sure the main table is vmalloced() with node distribution, not a single node. Even with this, this can hurt latencies.
Allocating one contiguous percpu var for all counters is a must.
Problem is : percpu alloc doesnt allow big allocations.
#define PCPU_MIN_UNIT_SIZE PFN_ALIGN(32 << 10)
So max allocation is 32 Kbytes, thats 2048 'xt_counters' only. -> cannot really use pcpu-alloc, but a kmalloc_node() or vmalloc_node() per cpu
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 10 lines · Eric Dumazet
Quoted 9 lines · Changli Gao
As only
xt_countersare private to each CPU, we don't need to maintain a whole individual table for each CPU.In the kernel space, we use the memory of ipt_entry.counters to save a pointer to a percpu
xt_counters. When iptables runs, it only update the counters on its own CPU.On non SMP platforms, no change is made.
Quoted 7 lines
Quoted 2 lines
Only the code of iptables is converted. Thanks for reviews.
Changli
I answered you a (difficult) work was in progress, still you post a patch that needs our review and time ? This is crazy.
Sorry for interrupt, and thanks for review. I posted this patch to check if I was in the right direction.
Quoted 8 lines
I am tempted to stop here. Oh well...
Your way of allocating a percpu counter for each counter is a pure TLB and cache line blower (up to two cache lines per counter), not counting the time needed to load a new table with 10.000 entries. Some people still use scripts with hundred of calls to iptables.
Quoted 6 lines
percpu_alloc()is not meant to be used thousand of times per second. It is not scalable.You consume 16 bytes per counter in the main table, while 4 bytes index should be enough on SMP build. Most firewalls I know use two or four cpus at most.
I think we can't change the structure of ipt_entry, as it is exposed to userspace as an ABI. Though there is no need to keep the same structure in the kernel space, converting is a big work. :)
Quoted 6 lines
They care about speed, not really because iptables duplicates table on each cpu. By the way, not using NUMA can definitly hurt firewalls with many rules, unless you make sure the main table is
vmalloced()with node distribution, not a single node. Even with this, this can hurt latencies.
This is what I worry about. I think only test can verify it.
Quoted 11 lines
Allocating one contiguous percpu var for all counters is a must.
Problem is : percpu alloc doesnt allow big allocations.
#define
PCPU_MIN_UNIT_SIZEPFN_ALIGN(32 << 10)So max allocation is 32 Kbytes, thats 2048 '
xt_counters' only. -> cannot really use pcpu-alloc, but akmalloc_node()orvmalloc_node()per cpu
Thanks. I'll try.
Signature · 2 lines
Regards, Changli Gao([email protected])
Quoted 9 lines · Changli Gao
Quoted 3 lines · Eric Dumazet
You consume 16 bytes per counter in the main table, while 4 bytes index should be enough on SMP build. Most firewalls I know use two or four cpus at most.
I think we can't change the structure of
ipt_entry, as it is exposed to userspace as an ABI. Though there is no need to keep the same structure in the kernel space, converting is a big work. :)
We already do that for COMPAT. This is a not a big deal to always use a converter and make it dependent on userland being 32 or 64 bit.
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 8 lines · Eric Dumazet
Quoted 7 lines · Changli Gao
As only
xt_countersare private to each CPU, we don't need to maintain a whole individual table for each CPU.In the kernel space, we use the memory of ipt_entry.counters to save a pointer to a percpu
xt_counters. When iptables runs, it only update the counters on its own CPU.
Quoted 8 lines
Quoted 4 lines
On non SMP platforms, no change is made.
Only the code of iptables is converted. Thanks for reviews.
Changli
I answered you a (difficult) work was in progress
Was it? Quoting Patrick from 24h prior to this post:
|so patches to get rid of the table duplication are highly welcome.
Quoted 1 line
still you post a patch that needs our review and time ? This is crazy.
You do not need to do it, but I will happily look at this. Of course my observations are the same as yours:
Quoted 4 lines
Your way of allocating a percpu counter for each counter is a pure TLB and cache line blower (up to two cache lines per counter), not counting the time needed to load a new table with 10.000 entries. Some people still use scripts with hundred of calls to iptables.
The two are statistically independent though. Even for a loaded ruleset, the TLB/DC miss accumulation will be desastrous - as I've found with linked-list rules/small allocs.
Quoted 9 lines
Allocating one contiguous percpu var for all counters is a must.
Problem is : percpu alloc doesnt allow big allocations.
#define
PCPU_MIN_UNIT_SIZEPFN_ALIGN(32 << 10)So max allocation is 32 Kbytes, thats 2048 '
xt_counters' only. -> cannot really use pcpu-alloc, but akmalloc_node()orvmalloc_node()per cpu
.. as is already done for jumpstack ;-)
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 22 lines · Jan Engelhardt
Was it? Quoting Patrick from 24h prior to this post:
|so patches to get rid of the table duplication are highly welcome.
Quoted 1 line
still you post a patch that needs our review and time ? This is crazy.
You do not need to do it, but I will happily look at this. Of course my observations are the same as yours:
Quoted 4 lines
Your way of allocating a percpu counter for each counter is a pure TLB and cache line blower (up to two cache lines per counter), not counting the time needed to load a new table with 10.000 entries. Some people still use scripts with hundred of calls to iptables.
The two are statistically independent though. Even for a loaded ruleset, the TLB/DC miss accumulation will be desastrous - as I've found with linked-list rules/small allocs.
Quoted 4 lines
Allocating one contiguous percpu var for all counters is a must.
Problem is : percpu alloc doesnt allow big allocations.
Quoted 7 lines
Quoted 5 lines
#define
PCPU_MIN_UNIT_SIZEPFN_ALIGN(32 << 10)So max allocation is 32 Kbytes, thats 2048 '
xt_counters' only. -> cannot really use pcpu-alloc, but akmalloc_node()orvmalloc_node()per cpu.. as is already done for jumpstack ;-)
IMHO, the real problem is not the table duplication. We know that adding a level of indirection is going to hurt a lot because of cache misses.
Its the atomic op (spinlock) done for every packet, entering every filter, with the conditional branch we do because of possible recursion.
per cpu variable, and spinlock... its really expensive.
Stephen tried an RCU conversion some time ago, that aborted because of RCU drawbacks (too much memory was possibly waiting to be freed after a grace period). Maybe RCU infrastructure is now ready to try again.
We should do what we did for u64 stats counters in network stack, using the u64_stats_sync.h infrastructure. No more synchro between the threads running through rules, and one gathering counters. Better latencies in particular.
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 4 lines · Eric Dumazet
IMHO, the real problem is not the table duplication. We know that adding a level of indirection is going to hurt a lot because of cache misses.
Currently, multi-core CPU is common, the cores in a CPU share the lowest level cache. Duplicate tables use more RAM, and may cause more pressure of the lowest level cache.
Signature · 2 lines
Regards, Changli Gao([email protected])
Quoted 9 lines · Changli Gao
Quoted 4 lines · Eric Dumazet
IMHO, the real problem is not the table duplication. We know that adding a level of indirection is going to hurt a lot because of cache misses.
Currently, multi-core CPU is common, the cores in a CPU share the lowest level cache. Duplicate tables use more RAM, and may cause more pressure of the lowest level cache.
There probably should be at most one copy per NUMA node. Maybe less, depending on what the benchmarks will say.
I started on some patch to reduce the ruleset from #cpu to #numa_nodes, but then stopped when I ran into the obvious fact that it would require locking the counters because xtables can actually run on more than one core within a given numa node. When decoupling counters from the ruleset, reducing the ruleset copies would become easier.
Quoted 4 lines · Jan Engelhardt
There probably should be at most one copy per NUMA node. Maybe less, depending on what the benchmarks will say.
I started on some patch to reduce the ruleset from #cpu to #numa_nodes,
It is a great idea! :)
Signature · 2 lines
Regards, Changli Gao([email protected])
Quoted 7 lines · Changli Gao
Quoted 4 lines · Jan Engelhardt
There probably should be at most one copy per NUMA node. Maybe less, depending on what the benchmarks will say.
I started on some patch to reduce the ruleset from #cpu to #numa_nodes,
It is a great idea! :)
Feel free to do it. (I don't have the patch anymore. It was just a few lines anyway.)