Skip to contentSkip to conversation

netfilter: remove the duplicate tables

RFC PATCH In review Changli Gao 3 participants 10 messages Nov 18, 2010 – Nov 19, 2010

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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
index 742bec0..593fe04 100644
@@ -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
index 8046350..8053cbe 100644
@@ -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) {
#1 lore raw
Quoted 11 lines · Changli Gao

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.

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

#2 lore raw
Quoted 10 lines · Eric Dumazet
Quoted 9 lines · Changli Gao

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.

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_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

Thanks. I'll try.

Signature · 2 lines
Regards,
Changli Gao([email protected])
#3 lore raw
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

#4 lore raw
In reply to Eric Dumazet
Quoted 8 lines · Eric Dumazet
Quoted 7 lines · Changli Gao

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.

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_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

.. 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

#5 lore raw
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_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

.. 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

#6 lore raw
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])
#7 lore raw
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.

#8 lore raw
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])
#9 lore raw
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.)