Re: [RFT 0/3] netfilter: lock free tables

Re: [RFT 0/3] netfilter: lock free tables

[Rick Jones]

Stephen Hemminger wrote:
> This is the "swap" version of lock less iptables counter update.
> It gets rid of the expensive reader/writer lock and uses RCU
> and swapping to accomplish the same thing.
> 
> Patches are against current net-next tree.
> It is not ready for inclusion until it is tested by others who
> actually use iptables heavily.

Patches applied with minimal fuzz on a net-next I snapped this afternoon. 
Resulting kernel booted on my 32-core IA64 system.  I was able to run the "none" 
case - no iptables --list command.

When I executed an iptables --list command to setup the "empty" test case, the 
following appeared on the console:

sut42:~# [ 1670.161689] ip_tables: (C) 2000-2006 Netfilter Core Team
[ 1670.235690] Unable to handle kernel paging request at virtual address 
a00000021e468000
[ 1670.235917] iptables[5723]: Oops 8813272891392 [1]
[ 1670.236060] Modules linked in: iptable_filter ip_tables x_tables s2io ipv6 
loop evdev ext3 jbd mbcache sg st sr_mod osst cdrom sd_mod mptspi mptscsih 
mptbase scsi_transport_spi scsi_mod tg3 libphy [last unloaded: s2io]
[ 1670.236716]
[ 1670.236717] Pid: 5723, CPU 7, comm:             iptables
[ 1670.236922] psr : 00001010085a6010 ifs : 8000000000000389 ip  : 
[<a00000021e421cb0>]    Not tainted (2.6.29-rc3-nexthemminger3)
[ 1670.237263] ip is at alloc_counters+0x170/0x280 [ip_tables]
[ 1670.237425] unat: 0000000000000000 pfs : 0000000000000389 rsc : 0000000000000003
[ 1670.237635] rnat: 0000000000000000 bsps: 0000000000000000 pr  : 00000000a695a599
[ 1670.237846] ldrs: 0000000000000000 ccv : 0000000000000000 fpsr: 0009804c0270033f
[ 1670.238057] csd : 0000000000000000 ssd : 0000000000000000
[ 1670.238213] b0  : a00000021e421c60 b6  : a000000100074800 b7  : a00000010000b700
[ 1670.238628] f6  : 0fffbfffffffff0000000 f7  : 0ffebfc62000000000000
[ 1670.238807] f8  : 1003e00000000a0000000 f9  : 1003e0000009bf42aa33e
[ 1670.238987] f10 : 1003e789aa606c0000000 f11 : 1003e0000000000000061
[ 1670.239166] r1  : a00000021e424cd0 r2  : 0000000000000000 r3  : 0000000000000000
[ 1670.239378] r8  : 0000000000000040 r9  : 0000000000000278 r10 : 0000000000000011
[ 1670.239589] r11 : e000070f85837308 r12 : e000070f8dc47de0 r13 : e000070f8dc40000
[ 1670.239628] r14 : 0000000000000278 r15 : 0000000000000400 r16 : 0000000000000000
[ 1670.239628] r17 : e000070f8dc40cc4 r18 : a00000021e468000 r19 : e000070f87e119e8
[ 1670.239628] r20 : e000070f87e119e0 r21 : 0000000000000000 r22 : 0000000000000401
[ 1670.239628] r23 : e000070f85837390 r24 : 0000000000000000 r25 : bea7a9a2c2b9b978
[ 1670.239628] r26 : e000070f87e119da r27 : 6e6e6e6e6e6e6e6e r28 : c1d5909426a6ead0
[ 1670.239628] r29 : 6e6e6e6e6e6e6e6e r30 : 50393b34544b4b0a r31 : e000070f87e11980
[ 1670.239628]
[ 1670.239628] Call Trace:
[ 1670.239628]  [<a000000100014cb0>] show_stack+0x50/0xa0
[ 1670.239628]                                 sp=e000070f8dc479b0 
bsp=e000070f8dc411e0
[ 1670.239628]  [<a000000100015520>] show_regs+0x820/0x860
[ 1670.239628]                                 sp=e000070f8dc47b80 
bsp=e000070f8dc41188
[ 1670.239628]  [<a000000100039f60>] die+0x1a0/0x2c0
[ 1670.239628]                                 sp=e000070f8dc47b80 
bsp=e000070f8dc41148
[ 1670.239628]  [<a000000100059370>] ia64_do_page_fault+0x8b0/0x9e0
[ 1670.239628]                                 sp=e000070f8dc47b80 
bsp=e000070f8dc410f8
[ 1670.239628]  [<a00000010000bf20>] ia64_native_leave_kernel+0x0/0x270
[ 1670.239628]                                 sp=e000070f8dc47c10 
bsp=e000070f8dc410f8
[ 1670.239628]  [<a00000021e421cb0>] alloc_counters+0x170/0x280 [ip_tables]
[ 1670.239628]                                 sp=e000070f8dc47de0 
bsp=e000070f8dc410b0
[ 1670.239628]  [<a00000021e422040>] do_ipt_get_ctl+0x280/0x8e0 [ip_tables]
[ 1670.239628]                                 sp=e000070f8dc47de0 
bsp=e000070f8dc41018
[ 1670.239628]  [<a00000010055c080>] nf_sockopt+0xc0/0x160
[ 1670.239628]                                 sp=e000070f8dc47e10 
bsp=e000070f8dc40fc0
[ 1670.239628]  [<a00000010055c160>] nf_getsockopt+0x40/0x60
[ 1670.239628]                                 sp=e000070f8dc47e10 
bsp=e000070f8dc40f80
[ 1670.239628]  [<a000000100578fd0>] ip_getsockopt+0x170/0x280
[ 1670.239628]                                 sp=e000070f8dc47e10 
bsp=e000070f8dc40f40
[ 1670.239628]  [<a0000001005c1700>] raw_getsockopt+0x40/0xa0
[ 1670.239628]                                 sp=e000070f8dc47e20 
bsp=e000070f8dc40f00
[ 1670.239628]  [<a0000001004ebeb0>] sock_common_getsockopt+0x70/0xa0
[ 1670.239628]                                 sp=e000070f8dc47e20 
bsp=e000070f8dc40ec0
[ 1670.239628]  [<a0000001004e77f0>] sys_getsockopt+0x110/0x1c0
[ 1670.239628]                                 sp=e000070f8dc47e20 
bsp=e000070f8dc40e40
[ 1670.239628]  [<a00000010000bd80>] ia64_ret_from_syscall+0x0/0x20
[ 1670.239628]                                 sp=e000070f8dc47e30 
bsp=e000070f8dc40e40
[ 1670.239628]  [<a000000000010720>] __start_ivt_text+0xffffffff00010720/0x400
[ 1670.239628]                                 sp=e000070f8dc48000 
bsp=e000070f8dc40e40
[ 1670.367369] Kernel panic - not syncing: Aiee, killing interrupt handler!


I'm in the midst of rebooting the system to try to pull the typescript from the 
compilation.

rick jones

Re: [RFT 3/3] iptables: lock free counters

[Eric Dumazet]

Stephen Hemminger a écrit :
> Make netfilter tables that use x_tables (iptables, ip6tables, arptables)
> operatate without locking on the receive path.
> Replace existing reader/writer lock with Read-Copy-Update to
> elminate the overhead of a read lock on each incoming packet.
> This should reduce the overhead of iptables especially on SMP
> systems.
> 
> The previous code used a reader-writer lock for two purposes.
> The first was to ensure that the xt_table_info reference was not in
> process of being changed. Since xt_table_info is only freed via one
> routine, it was a direct conversion to RCU.
> 
> The other use of the reader-writer lock was to to block changes
> to counters while they were being read. This is handled by swapping in
> a new set of counter values and then summing the old ones. The sum
> is then restored back on a single cpu.
> 
> Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
> 
> ---
>  include/linux/netfilter/x_tables.h |   13 ++++
>  net/ipv4/netfilter/arp_tables.c    |   92 ++++++++++++++++++++++++-----------
>  net/ipv4/netfilter/ip_tables.c     |   97 ++++++++++++++++++++++++-------------
>  net/ipv6/netfilter/ip6_tables.c    |   97 +++++++++++++++++++++++--------------
>  net/netfilter/x_tables.c           |   67 +++++++++++++++++++++----
>  5 files changed, 258 insertions(+), 108 deletions(-)
> 
> --- a/include/linux/netfilter/x_tables.h	2009-02-02 15:06:39.893751845 -0800
> +++ b/include/linux/netfilter/x_tables.h	2009-02-03 15:44:21.743663216 -0800
> @@ -353,7 +353,7 @@ struct xt_table
>  	unsigned int valid_hooks;
>  
>  	/* Lock for the curtain */
> -	rwlock_t lock;
> +	struct mutex lock;
>  
>  	/* Man behind the curtain... */
>  	struct xt_table_info *private;
> @@ -383,9 +383,15 @@ struct xt_table_info
>  	unsigned int hook_entry[NF_INET_NUMHOOKS];
>  	unsigned int underflow[NF_INET_NUMHOOKS];
>  
> +	/* For the dustman... */
> +	union {
> +		struct rcu_head rcu;
> +		struct work_struct work;
> +	};
> +
>  	/* ipt_entry tables: one per CPU */
>  	/* Note : this field MUST be the last one, see XT_TABLE_INFO_SZ */
> -	char *entries[1];
> +	void *entries[1];
>  };
>  
>  #define XT_TABLE_INFO_SZ (offsetof(struct xt_table_info, entries) \
> @@ -432,6 +438,9 @@ extern void xt_proto_fini(struct net *ne
>  
>  extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
>  extern void xt_free_table_info(struct xt_table_info *info);
> +extern void xt_zero_table_entries(struct xt_table_info *info);
> +extern void xt_swap_table_entries(struct xt_table_info *old,
> +				  struct xt_table_info *new);
>  
>  #ifdef CONFIG_COMPAT
>  #include <net/compat.h>
> --- a/net/ipv4/netfilter/ip_tables.c	2009-02-02 15:06:29.684249364 -0800
> +++ b/net/ipv4/netfilter/ip_tables.c	2009-02-03 15:52:32.047583686 -0800
> @@ -347,10 +347,12 @@ ipt_do_table(struct sk_buff *skb,
>  	mtpar.family  = tgpar.family = NFPROTO_IPV4;
>  	tgpar.hooknum = hook;
>  
> -	read_lock_bh(&table->lock);
>  	IP_NF_ASSERT(table->valid_hooks & (1 << hook));
> -	private = table->private;
> -	table_base = (void *)private->entries[smp_processor_id()];
> +
> +	rcu_read_lock_bh();
> +	private = rcu_dereference(table->private);
> +	table_base = rcu_dereference(private->entries[smp_processor_id()]);
> +
>  	e = get_entry(table_base, private->hook_entry[hook]);
>  
>  	/* For return from builtin chain */
> @@ -445,7 +447,7 @@ ipt_do_table(struct sk_buff *skb,
>  		}
>  	} while (!hotdrop);
>  
> -	read_unlock_bh(&table->lock);
> +	rcu_read_unlock_bh();
>  
>  #ifdef DEBUG_ALLOW_ALL
>  	return NF_ACCEPT;
> @@ -924,13 +926,45 @@ get_counters(const struct xt_table_info 
>  				  counters,
>  				  &i);
>  	}
> +
> +}
> +
> +/* We're lazy, and add to the first CPU; overflow works its fey magic
> + * and everything is OK. */
> +static int
> +add_counter_to_entry(struct ipt_entry *e,
> +		     const struct xt_counters addme[],
> +		     unsigned int *i)
> +{
> +	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
> +
> +	(*i)++;
> +	return 0;
> +}
> +
> +/* Take values from counters and add them back onto the current cpu */
> +static void put_counters(struct xt_table_info *t,
> +			 const struct xt_counters counters[])
> +{
> +	unsigned int i, cpu;
> +
> +	local_bh_disable();
> +	cpu = smp_processor_id();
> +	i = 0;
> +	IPT_ENTRY_ITERATE(t->entries[cpu],
> +			  t->size,
> +			  add_counter_to_entry,
> +			  counters,
> +			  &i);
> +	local_bh_enable();
>  }
>  
>  static struct xt_counters * alloc_counters(struct xt_table *table)
>  {
>  	unsigned int countersize;
>  	struct xt_counters *counters;
> -	const struct xt_table_info *private = table->private;
> +	struct xt_table_info *private = table->private;
> +	struct xt_table_info *tmp;
>  
>  	/* We need atomic snapshot of counters: rest doesn't change
>  	   (other than comefrom, which userspace doesn't care
> @@ -939,14 +973,30 @@ static struct xt_counters * alloc_counte
>  	counters = vmalloc_node(countersize, numa_node_id());
>  
>  	if (counters == NULL)
> -		return ERR_PTR(-ENOMEM);
> +		goto nomem;
> +
> +	tmp = xt_alloc_table_info(private->size);
> +	if (!tmp)
> +		goto free_counters;
> +

> +	xt_zero_table_entries(tmp);
This is not correct. We must copy rules and zero counters on the copied stuff.

> +
> +	mutex_lock(&table->lock);
> +	xt_swap_table_entries(private, tmp);
> +	synchronize_net();	/* Wait until smoke has cleared */
>  
> -	/* First, sum counters... */
> -	write_lock_bh(&table->lock);
> -	get_counters(private, counters);
> -	write_unlock_bh(&table->lock);
> +	get_counters(tmp, counters);

Yes, tmp now hold previous pointers

> +	put_counters(private, counters);
> +	mutex_unlock(&table->lock);
> +
> +	xt_free_table_info(tmp);
>  
>  	return counters;
> +
> + free_counters:
> +	vfree(counters);
> + nomem:
> +	return ERR_PTR(-ENOMEM);
>  }
>  
>  static int
> @@ -1312,27 +1362,6 @@ do_replace(struct net *net, void __user 
>  	return ret;
>  }
>  
> -/* We're lazy, and add to the first CPU; overflow works its fey magic
> - * and everything is OK. */
> -static int
> -add_counter_to_entry(struct ipt_entry *e,
> -		     const struct xt_counters addme[],
> -		     unsigned int *i)
> -{
> -#if 0
> -	duprintf("add_counter: Entry %u %lu/%lu + %lu/%lu\n",
> -		 *i,
> -		 (long unsigned int)e->counters.pcnt,
> -		 (long unsigned int)e->counters.bcnt,
> -		 (long unsigned int)addme[*i].pcnt,
> -		 (long unsigned int)addme[*i].bcnt);
> -#endif
> -
> -	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
> -
> -	(*i)++;
> -	return 0;
> -}
>  
>  static int
>  do_add_counters(struct net *net, void __user *user, unsigned int len, int compat)
> @@ -1393,13 +1422,14 @@ do_add_counters(struct net *net, void __
>  		goto free;
>  	}
>  
> -	write_lock_bh(&t->lock);
> +	mutex_lock(&t->lock);
>  	private = t->private;
>  	if (private->number != num_counters) {
>  		ret = -EINVAL;
>  		goto unlock_up_free;
>  	}
>  
> +	preempt_disable();
>  	i = 0;
>  	/* Choose the copy that is on our node */
>  	loc_cpu_entry = private->entries[raw_smp_processor_id()];
> @@ -1408,8 +1438,9 @@ do_add_counters(struct net *net, void __
>  			  add_counter_to_entry,
>  			  paddc,
>  			  &i);
> +	preempt_enable();
>   unlock_up_free:
> -	write_unlock_bh(&t->lock);
> +	mutex_unlock(&t->lock);
>  	xt_table_unlock(t);
>  	module_put(t->me);
>   free:
> --- a/net/netfilter/x_tables.c	2009-02-02 15:06:29.708249745 -0800
> +++ b/net/netfilter/x_tables.c	2009-02-03 15:44:21.743663216 -0800
> @@ -611,18 +611,61 @@ struct xt_table_info *xt_alloc_table_inf
>  }
>  EXPORT_SYMBOL(xt_alloc_table_info);
>  
> -void xt_free_table_info(struct xt_table_info *info)
> +/* Zero out entries */
> +void xt_zero_table_entries(struct xt_table_info *info)
>  {
> -	int cpu;
> +	unsigned int cpu;
> +
> +	for_each_possible_cpu(cpu)
> +		memset(info->entries[cpu], 0, info->size);
> +}
> +EXPORT_SYMBOL_GPL(xt_zero_table_entries);

Hum, you forgot entries[cpu] points to quite complex data set,
with iptables rules, countaining counters...

Only counters must be zeroed, one by one.

You thus need an ITERATE invocation...

I wont be able to make the incremental patch (too busy @work at this moment),
I am sorry :(

--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFT 3/3] iptables: lock free counters

[Patrick McHardy]

Eric Dumazet wrote:
> Stephen Hemminger a écrit :
>> @@ -939,14 +973,30 @@ static struct xt_counters * alloc_counte
>>  	counters = vmalloc_node(countersize, numa_node_id());
>>  
>>  	if (counters == NULL)
>> -		return ERR_PTR(-ENOMEM);
>> +		goto nomem;
>> +
>> +	tmp = xt_alloc_table_info(private->size);
>> +	if (!tmp)
>> +		goto free_counters;
>> +
> 
>> +	xt_zero_table_entries(tmp);
> This is not correct. We must copy rules and zero counters on the copied stuff.

Indeed.

>>  static int
>>  do_add_counters(struct net *net, void __user *user, unsigned int len, int compat)
>> @@ -1393,13 +1422,14 @@ do_add_counters(struct net *net, void __
>>  		goto free;
>>  	}
>>  
>> -	write_lock_bh(&t->lock);
>> +	mutex_lock(&t->lock);
>>  	private = t->private;
>>  	if (private->number != num_counters) {
>>  		ret = -EINVAL;
>>  		goto unlock_up_free;
>>  	}
>>  
>> +	preempt_disable();
>>  	i = 0;
>>  	/* Choose the copy that is on our node */

This isn't actually necessary, its merely an optimization. Since this
can take quite a while, it might be nicer not to disable preempt.

Re: [RFT 3/3] iptables: lock free counters

[Stephen Hemminger]

On Mon, 09 Feb 2009 16:52:59 +0100
Patrick McHardy <kaber@trash.net> wrote:

> Eric Dumazet wrote:
> > Stephen Hemminger a écrit :
> >> @@ -939,14 +973,30 @@ static struct xt_counters * alloc_counte
> >>  	counters = vmalloc_node(countersize, numa_node_id());
> >>  
> >>  	if (counters == NULL)
> >> -		return ERR_PTR(-ENOMEM);
> >> +		goto nomem;
> >> +
> >> +	tmp = xt_alloc_table_info(private->size);
> >> +	if (!tmp)
> >> +		goto free_counters;
> >> +
> > 
> >> +	xt_zero_table_entries(tmp);
> > This is not correct. We must copy rules and zero counters on the copied stuff.
> 
> Indeed.
It is in next version.

> >>  static int
> >>  do_add_counters(struct net *net, void __user *user, unsigned int len, int compat)
> >> @@ -1393,13 +1422,14 @@ do_add_counters(struct net *net, void __
> >>  		goto free;
> >>  	}
> >>  
> >> -	write_lock_bh(&t->lock);
> >> +	mutex_lock(&t->lock);
> >>  	private = t->private;
> >>  	if (private->number != num_counters) {
> >>  		ret = -EINVAL;
> >>  		goto unlock_up_free;
> >>  	}
> >>  
> >> +	preempt_disable();
> >>  	i = 0;
> >>  	/* Choose the copy that is on our node */
> 
> This isn't actually necessary, its merely an optimization. Since this
> can take quite a while, it might be nicer not to disable preempt.

Need to stay on same cpu, to avoid race of preempt and two cpu's updating
same counter entry (and 64 bit counter update is not atomic)

[RFC] iptables: lock free counters (v0.6)

[Stephen Hemminger]

The reader/writer lock in ip_tables is acquired in the critical path of
processing packets and is one of the reasons just loading iptables can cause
a 20% performance loss. The rwlock serves two functions:

1) it prevents changes to table state (xt_replace) while table is in use.
   This is now handled by doing rcu on the xt_table. When table is
   replaced, the new table(s) are put in and the old one table(s) are freed
   after RCU period.

2) it provides synchronization when accesing the counter values.
   This is now handled by swapping in new table_info entries for each cpu
   then summing the old values, and putting the result back onto one
   cpu.  On a busy system it may cause sampling to occur at different
   times on each cpu, but no packet/byte counts are lost in the process.

Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>

---
 include/linux/netfilter/x_tables.h |    6 +
 net/ipv4/netfilter/arp_tables.c    |  114 ++++++++++++++++++++++++++---------
 net/ipv4/netfilter/ip_tables.c     |  120 ++++++++++++++++++++++++++-----------
 net/ipv6/netfilter/ip6_tables.c    |  119 +++++++++++++++++++++++++-----------
 net/netfilter/x_tables.c           |   26 ++++++--
 5 files changed, 283 insertions(+), 102 deletions(-)

--- a/include/linux/netfilter/x_tables.h	2009-02-09 08:31:47.955781543 -0800
+++ b/include/linux/netfilter/x_tables.h	2009-02-09 08:32:41.202805664 -0800
@@ -353,7 +353,7 @@ struct xt_table
 	unsigned int valid_hooks;
 
 	/* Lock for the curtain */
-	rwlock_t lock;
+	struct mutex lock;
 
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
@@ -385,7 +385,7 @@ struct xt_table_info
 
 	/* ipt_entry tables: one per CPU */
 	/* Note : this field MUST be the last one, see XT_TABLE_INFO_SZ */
-	char *entries[1];
+	void *entries[1];
 };
 
 #define XT_TABLE_INFO_SZ (offsetof(struct xt_table_info, entries) \
@@ -432,6 +432,8 @@ extern void xt_proto_fini(struct net *ne
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
+extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
+				    struct xt_table_info *new);
 
 #ifdef CONFIG_COMPAT
 #include <net/compat.h>
--- a/net/ipv4/netfilter/ip_tables.c	2009-02-09 08:30:58.606781650 -0800
+++ b/net/ipv4/netfilter/ip_tables.c	2009-02-09 09:00:59.651532539 -0800
@@ -347,10 +347,12 @@ ipt_do_table(struct sk_buff *skb,
 	mtpar.family  = tgpar.family = NFPROTO_IPV4;
 	tgpar.hooknum = hook;
 
-	read_lock_bh(&table->lock);
 	IP_NF_ASSERT(table->valid_hooks & (1 << hook));
-	private = table->private;
-	table_base = (void *)private->entries[smp_processor_id()];
+
+	rcu_read_lock();
+	private = rcu_dereference(table->private);
+	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+
 	e = get_entry(table_base, private->hook_entry[hook]);
 
 	/* For return from builtin chain */
@@ -445,7 +447,7 @@ ipt_do_table(struct sk_buff *skb,
 		}
 	} while (!hotdrop);
 
-	read_unlock_bh(&table->lock);
+	rcu_read_unlock();
 
 #ifdef DEBUG_ALLOW_ALL
 	return NF_ACCEPT;
@@ -924,13 +926,68 @@ get_counters(const struct xt_table_info 
 				  counters,
 				  &i);
 	}
+
+}
+
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct ipt_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
+
+/* Take values from counters and add them back onto the current cpu */
+static void put_counters(struct xt_table_info *t,
+			 const struct xt_counters counters[])
+{
+	unsigned int i, cpu;
+
+	local_bh_disable();
+	cpu = smp_processor_id();
+	i = 0;
+	IPT_ENTRY_ITERATE(t->entries[cpu],
+			  t->size,
+			  add_counter_to_entry,
+			  counters,
+			  &i);
+	local_bh_enable();
+}
+
+
+static inline int
+zero_entry_counter(struct ipt_entry *e, void *arg)
+{
+	e->counters.bcnt = 0;
+	e->counters.pcnt = 0;
+	return 0;
+}
+
+static void
+clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
+{
+	unsigned int cpu;
+	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
+
+	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
+	for_each_possible_cpu(cpu) {
+		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
+		IPT_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
+				  zero_entry_counter, NULL);
+	}
 }
 
 static struct xt_counters * alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
-	const struct xt_table_info *private = table->private;
+	struct xt_table_info *private = table->private;
+	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	   (other than comefrom, which userspace doesn't care
@@ -939,14 +996,30 @@ static struct xt_counters * alloc_counte
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		return ERR_PTR(-ENOMEM);
+		goto nomem;
+
+	info = xt_alloc_table_info(private->size);
+	if (!info)
+		goto free_counters;
+
+	clone_counters(info, private);
 
-	/* First, sum counters... */
-	write_lock_bh(&table->lock);
-	get_counters(private, counters);
-	write_unlock_bh(&table->lock);
+	mutex_lock(&table->lock);
+	xt_table_entry_swap_rcu(private, info);
+	synchronize_net();	/* Wait until smoke has cleared */
+
+	get_counters(info, counters);
+	put_counters(private, counters);
+	mutex_unlock(&table->lock);
+
+	xt_free_table_info(info);
 
 	return counters;
+
+ free_counters:
+	vfree(counters);
+ nomem:
+	return ERR_PTR(-ENOMEM);
 }
 
 static int
@@ -1312,27 +1385,6 @@ do_replace(struct net *net, void __user 
 	return ret;
 }
 
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK. */
-static int
-add_counter_to_entry(struct ipt_entry *e,
-		     const struct xt_counters addme[],
-		     unsigned int *i)
-{
-#if 0
-	duprintf("add_counter: Entry %u %lu/%lu + %lu/%lu\n",
-		 *i,
-		 (long unsigned int)e->counters.pcnt,
-		 (long unsigned int)e->counters.bcnt,
-		 (long unsigned int)addme[*i].pcnt,
-		 (long unsigned int)addme[*i].bcnt);
-#endif
-
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
 
 static int
 do_add_counters(struct net *net, void __user *user, unsigned int len, int compat)
@@ -1393,13 +1445,14 @@ do_add_counters(struct net *net, void __
 		goto free;
 	}
 
-	write_lock_bh(&t->lock);
+	mutex_lock(&t->lock);
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
+	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
 	loc_cpu_entry = private->entries[raw_smp_processor_id()];
@@ -1408,8 +1461,9 @@ do_add_counters(struct net *net, void __
 			  add_counter_to_entry,
 			  paddc,
 			  &i);
+	preempt_enable();
  unlock_up_free:
-	write_unlock_bh(&t->lock);
+	mutex_unlock(&t->lock);
 	xt_table_unlock(t);
 	module_put(t->me);
  free:
--- a/net/netfilter/x_tables.c	2009-02-09 08:30:58.642782131 -0800
+++ b/net/netfilter/x_tables.c	2009-02-09 08:32:24.018308401 -0800
@@ -625,6 +625,20 @@ void xt_free_table_info(struct xt_table_
 }
 EXPORT_SYMBOL(xt_free_table_info);
 
+void xt_table_entry_swap_rcu(struct xt_table_info *oldinfo,
+			     struct xt_table_info *newinfo)
+{
+	unsigned int cpu;
+
+	for_each_possible_cpu(cpu) {
+		void *p = oldinfo->entries[cpu];
+		rcu_assign_pointer(oldinfo->entries[cpu], newinfo->entries[cpu]);
+		newinfo->entries[cpu] = p;
+	}
+
+}
+EXPORT_SYMBOL_GPL(xt_table_entry_swap_rcu);
+
 /* Find table by name, grabs mutex & ref.  Returns ERR_PTR() on error. */
 struct xt_table *xt_find_table_lock(struct net *net, u_int8_t af,
 				    const char *name)
@@ -671,21 +685,22 @@ xt_replace_table(struct xt_table *table,
 	struct xt_table_info *oldinfo, *private;
 
 	/* Do the substitution. */
-	write_lock_bh(&table->lock);
+	mutex_lock(&table->lock);
 	private = table->private;
 	/* Check inside lock: is the old number correct? */
 	if (num_counters != private->number) {
 		duprintf("num_counters != table->private->number (%u/%u)\n",
 			 num_counters, private->number);
-		write_unlock_bh(&table->lock);
+		mutex_unlock(&table->lock);
 		*error = -EAGAIN;
 		return NULL;
 	}
 	oldinfo = private;
-	table->private = newinfo;
+	rcu_assign_pointer(table->private, newinfo);
 	newinfo->initial_entries = oldinfo->initial_entries;
-	write_unlock_bh(&table->lock);
+	mutex_unlock(&table->lock);
 
+	synchronize_net();
 	return oldinfo;
 }
 EXPORT_SYMBOL_GPL(xt_replace_table);
@@ -719,7 +734,8 @@ struct xt_table *xt_register_table(struc
 
 	/* Simplifies replace_table code. */
 	table->private = bootstrap;
-	rwlock_init(&table->lock);
+	mutex_init(&table->lock);
+
 	if (!xt_replace_table(table, 0, newinfo, &ret))
 		goto unlock;
 
--- a/net/ipv4/netfilter/arp_tables.c	2009-02-09 08:30:58.630817607 -0800
+++ b/net/ipv4/netfilter/arp_tables.c	2009-02-09 09:07:18.120931959 -0800
@@ -237,9 +237,10 @@ unsigned int arpt_do_table(struct sk_buf
 	indev = in ? in->name : nulldevname;
 	outdev = out ? out->name : nulldevname;
 
-	read_lock_bh(&table->lock);
-	private = table->private;
-	table_base = (void *)private->entries[smp_processor_id()];
+	rcu_read_lock_bh();
+	private = rcu_dereference(table->private);
+	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+
 	e = get_entry(table_base, private->hook_entry[hook]);
 	back = get_entry(table_base, private->underflow[hook]);
 
@@ -311,7 +312,8 @@ unsigned int arpt_do_table(struct sk_buf
 			e = (void *)e + e->next_offset;
 		}
 	} while (!hotdrop);
-	read_unlock_bh(&table->lock);
+
+	rcu_read_unlock_bh();
 
 	if (hotdrop)
 		return NF_DROP;
@@ -714,11 +716,65 @@ static void get_counters(const struct xt
 	}
 }
 
-static inline struct xt_counters *alloc_counters(struct xt_table *table)
+
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct arpt_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
+
+/* Take values from counters and add them back onto the current cpu */
+static void put_counters(struct xt_table_info *t,
+			 const struct xt_counters counters[])
+{
+	unsigned int i, cpu;
+
+	local_bh_disable();
+	cpu = smp_processor_id();
+	i = 0;
+	ARPT_ENTRY_ITERATE(t->entries[cpu],
+			  t->size,
+			  add_counter_to_entry,
+			  counters,
+			  &i);
+	local_bh_enable();
+}
+
+static inline int
+zero_entry_counter(struct arpt_entry *e, void *arg)
+{
+	e->counters.bcnt = 0;
+	e->counters.pcnt = 0;
+	return 0;
+}
+
+static void
+clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
+{
+	unsigned int cpu;
+	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
+
+	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
+	for_each_possible_cpu(cpu) {
+		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
+		ARPT_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
+				  zero_entry_counter, NULL);
+	}
+}
+
+static struct xt_counters *alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
-	const struct xt_table_info *private = table->private;
+	struct xt_table_info *private = table->private;
+	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	 * (other than comefrom, which userspace doesn't care
@@ -728,14 +784,30 @@ static inline struct xt_counters *alloc_
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		return ERR_PTR(-ENOMEM);
+		goto nomem;
 
-	/* First, sum counters... */
-	write_lock_bh(&table->lock);
-	get_counters(private, counters);
-	write_unlock_bh(&table->lock);
+	info = xt_alloc_table_info(private->size);
+	if (!info)
+		goto free_counters;
+
+	clone_counters(info, private);
+
+	mutex_lock(&table->lock);
+	xt_table_entry_swap_rcu(private, info);
+	synchronize_net();	/* Wait until smoke has cleared */
+
+	get_counters(info, counters);
+	put_counters(private, counters);
+	mutex_unlock(&table->lock);
+
+	xt_free_table_info(info);
 
 	return counters;
+
+ free_counters:
+	vfree(counters);
+ nomem:
+	return ERR_PTR(-ENOMEM);
 }
 
 static int copy_entries_to_user(unsigned int total_size,
@@ -1075,20 +1147,6 @@ static int do_replace(struct net *net, v
 	return ret;
 }
 
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK.
- */
-static inline int add_counter_to_entry(struct arpt_entry *e,
-				       const struct xt_counters addme[],
-				       unsigned int *i)
-{
-
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
-
 static int do_add_counters(struct net *net, void __user *user, unsigned int len,
 			   int compat)
 {
@@ -1148,13 +1206,14 @@ static int do_add_counters(struct net *n
 		goto free;
 	}
 
-	write_lock_bh(&t->lock);
+	mutex_lock(&t->lock);
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
+	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
 	loc_cpu_entry = private->entries[smp_processor_id()];
@@ -1164,7 +1223,8 @@ static int do_add_counters(struct net *n
 			   paddc,
 			   &i);
  unlock_up_free:
-	write_unlock_bh(&t->lock);
+	mutex_unlock(&t->lock);
+
 	xt_table_unlock(t);
 	module_put(t->me);
  free:
--- a/net/ipv6/netfilter/ip6_tables.c	2009-02-09 08:30:58.662807566 -0800
+++ b/net/ipv6/netfilter/ip6_tables.c	2009-02-09 09:00:50.195531719 -0800
@@ -373,10 +373,12 @@ ip6t_do_table(struct sk_buff *skb,
 	mtpar.family  = tgpar.family = NFPROTO_IPV6;
 	tgpar.hooknum = hook;
 
-	read_lock_bh(&table->lock);
 	IP_NF_ASSERT(table->valid_hooks & (1 << hook));
-	private = table->private;
-	table_base = (void *)private->entries[smp_processor_id()];
+
+	rcu_read_lock_bh();
+	private = rcu_dereference(table->private);
+	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+
 	e = get_entry(table_base, private->hook_entry[hook]);
 
 	/* For return from builtin chain */
@@ -474,7 +476,7 @@ ip6t_do_table(struct sk_buff *skb,
 #ifdef CONFIG_NETFILTER_DEBUG
 	((struct ip6t_entry *)table_base)->comefrom = NETFILTER_LINK_POISON;
 #endif
-	read_unlock_bh(&table->lock);
+	rcu_read_unlock_bh();
 
 #ifdef DEBUG_ALLOW_ALL
 	return NF_ACCEPT;
@@ -955,11 +957,64 @@ get_counters(const struct xt_table_info 
 	}
 }
 
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct ip6t_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
+
+/* Take values from counters and add them back onto the current cpu */
+static void put_counters(struct xt_table_info *t,
+			 const struct xt_counters counters[])
+{
+	unsigned int i, cpu;
+
+	local_bh_disable();
+	cpu = smp_processor_id();
+	i = 0;
+	IP6T_ENTRY_ITERATE(t->entries[cpu],
+			   t->size,
+			   add_counter_to_entry,
+			   counters,
+			   &i);
+	local_bh_enable();
+}
+
+static inline int
+zero_entry_counter(struct ip6t_entry *e, void *arg)
+{
+	e->counters.bcnt = 0;
+	e->counters.pcnt = 0;
+	return 0;
+}
+
+static void
+clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
+{
+	unsigned int cpu;
+	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
+
+	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
+	for_each_possible_cpu(cpu) {
+		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
+		IP6T_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
+				   zero_entry_counter, NULL);
+	}
+}
+
 static struct xt_counters *alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
-	const struct xt_table_info *private = table->private;
+	struct xt_table_info *private = table->private;
+	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	   (other than comefrom, which userspace doesn't care
@@ -968,14 +1023,28 @@ static struct xt_counters *alloc_counter
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		return ERR_PTR(-ENOMEM);
+		goto nomem;
 
-	/* First, sum counters... */
-	write_lock_bh(&table->lock);
-	get_counters(private, counters);
-	write_unlock_bh(&table->lock);
+	info = xt_alloc_table_info(private->size);
+	if (!info)
+		goto free_counters;
+
+	clone_counters(info, private);
 
-	return counters;
+	mutex_lock(&table->lock);
+	xt_table_entry_swap_rcu(private, info);
+	synchronize_net();	/* Wait until smoke has cleared */
+
+	get_counters(info, counters);
+	put_counters(private, counters);
+	mutex_unlock(&table->lock);
+
+	xt_free_table_info(info);
+
+ free_counters:
+	vfree(counters);
+ nomem:
+	return ERR_PTR(-ENOMEM);
 }
 
 static int
@@ -1342,28 +1411,6 @@ do_replace(struct net *net, void __user 
 	return ret;
 }
 
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK. */
-static inline int
-add_counter_to_entry(struct ip6t_entry *e,
-		     const struct xt_counters addme[],
-		     unsigned int *i)
-{
-#if 0
-	duprintf("add_counter: Entry %u %lu/%lu + %lu/%lu\n",
-		 *i,
-		 (long unsigned int)e->counters.pcnt,
-		 (long unsigned int)e->counters.bcnt,
-		 (long unsigned int)addme[*i].pcnt,
-		 (long unsigned int)addme[*i].bcnt);
-#endif
-
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
-
 static int
 do_add_counters(struct net *net, void __user *user, unsigned int len,
 		int compat)
@@ -1424,13 +1471,14 @@ do_add_counters(struct net *net, void __
 		goto free;
 	}
 
-	write_lock_bh(&t->lock);
+	mutex_lock(&t->lock);
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
+	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
 	loc_cpu_entry = private->entries[raw_smp_processor_id()];
@@ -1439,8 +1487,9 @@ do_add_counters(struct net *net, void __
 			  add_counter_to_entry,
 			  paddc,
 			  &i);
+	preempt_enable();
  unlock_up_free:
-	write_unlock_bh(&t->lock);
+	mutex_unlock(&t->lock);
 	xt_table_unlock(t);
 	module_put(t->me);
  free:

Re: [RFC] iptables: lock free counters (v0.6)

[Ranjit Manomohan]

On Tue, Feb 10, 2009 at 9:52 AM, Stephen Hemminger
<shemminger@vyatta.com> wrote:
> The reader/writer lock in ip_tables is acquired in the critical path of
> processing packets and is one of the reasons just loading iptables can cause
> a 20% performance loss. The rwlock serves two functions:
>
> 1) it prevents changes to table state (xt_replace) while table is in use.
>   This is now handled by doing rcu on the xt_table. When table is
>   replaced, the new table(s) are put in and the old one table(s) are freed
>   after RCU period.
>
> 2) it provides synchronization when accesing the counter values.
>   This is now handled by swapping in new table_info entries for each cpu
>   then summing the old values, and putting the result back onto one
>   cpu.  On a busy system it may cause sampling to occur at different
>   times on each cpu, but no packet/byte counts are lost in the process.
>
> Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
>
> ---
>  include/linux/netfilter/x_tables.h |    6 +
>  net/ipv4/netfilter/arp_tables.c    |  114 ++++++++++++++++++++++++++---------
>  net/ipv4/netfilter/ip_tables.c     |  120 ++++++++++++++++++++++++++-----------
>  net/ipv6/netfilter/ip6_tables.c    |  119 +++++++++++++++++++++++++-----------
>  net/netfilter/x_tables.c           |   26 ++++++--
>  5 files changed, 283 insertions(+), 102 deletions(-)
>
> --- a/include/linux/netfilter/x_tables.h        2009-02-09 08:31:47.955781543 -0800
> +++ b/include/linux/netfilter/x_tables.h        2009-02-09 08:32:41.202805664 -0800
> @@ -353,7 +353,7 @@ struct xt_table
>        unsigned int valid_hooks;
>
>        /* Lock for the curtain */
> -       rwlock_t lock;
> +       struct mutex lock;
>
>        /* Man behind the curtain... */
>        struct xt_table_info *private;
> @@ -385,7 +385,7 @@ struct xt_table_info
>
>        /* ipt_entry tables: one per CPU */
>        /* Note : this field MUST be the last one, see XT_TABLE_INFO_SZ */
> -       char *entries[1];
> +       void *entries[1];
>  };
>
>  #define XT_TABLE_INFO_SZ (offsetof(struct xt_table_info, entries) \
> @@ -432,6 +432,8 @@ extern void xt_proto_fini(struct net *ne
>
>  extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
>  extern void xt_free_table_info(struct xt_table_info *info);
> +extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
> +                                   struct xt_table_info *new);
>
>  #ifdef CONFIG_COMPAT
>  #include <net/compat.h>
> --- a/net/ipv4/netfilter/ip_tables.c    2009-02-09 08:30:58.606781650 -0800
> +++ b/net/ipv4/netfilter/ip_tables.c    2009-02-09 09:00:59.651532539 -0800
> @@ -347,10 +347,12 @@ ipt_do_table(struct sk_buff *skb,
>        mtpar.family  = tgpar.family = NFPROTO_IPV4;
>        tgpar.hooknum = hook;
>
> -       read_lock_bh(&table->lock);
>        IP_NF_ASSERT(table->valid_hooks & (1 << hook));
> -       private = table->private;
> -       table_base = (void *)private->entries[smp_processor_id()];
> +
> +       rcu_read_lock();

Any reason why we don't disable bh here? Is it because the different
counter entries are not touched by the receive path?

seems inconsistent with the other arp/ip6_do_table routines which do a
bh disable version.

> +       private = rcu_dereference(table->private);
> +       table_base = rcu_dereference(private->entries[smp_processor_id()]);
> +
>        e = get_entry(table_base, private->hook_entry[hook]);
>
>        /* For return from builtin chain */
> @@ -445,7 +447,7 @@ ipt_do_table(struct sk_buff *skb,
>                }
>        } while (!hotdrop);
>
> -       read_unlock_bh(&table->lock);
> +       rcu_read_unlock();
>
>  #ifdef DEBUG_ALLOW_ALL
>        return NF_ACCEPT;
> @@ -924,13 +926,68 @@ get_counters(const struct xt_table_info
>                                  counters,
>                                  &i);
>        }
> +
> +}
> +
> +/* We're lazy, and add to the first CPU; overflow works its fey magic
> + * and everything is OK. */
> +static int
> +add_counter_to_entry(struct ipt_entry *e,
> +                    const struct xt_counters addme[],
> +                    unsigned int *i)
> +{
> +       ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
> +
> +       (*i)++;
> +       return 0;
> +}
> +
> +/* Take values from counters and add them back onto the current cpu */
> +static void put_counters(struct xt_table_info *t,
> +                        const struct xt_counters counters[])
> +{
> +       unsigned int i, cpu;
> +
> +       local_bh_disable();
> +       cpu = smp_processor_id();
> +       i = 0;
> +       IPT_ENTRY_ITERATE(t->entries[cpu],
> +                         t->size,
> +                         add_counter_to_entry,
> +                         counters,
> +                         &i);
> +       local_bh_enable();
> +}
> +
> +
> +static inline int
> +zero_entry_counter(struct ipt_entry *e, void *arg)
> +{
> +       e->counters.bcnt = 0;
> +       e->counters.pcnt = 0;
> +       return 0;
> +}
> +
> +static void
> +clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
> +{

probably should be named clone_entries?

> +       unsigned int cpu;
> +       const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
> +
> +       memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
> +       for_each_possible_cpu(cpu) {
> +               memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
> +               IPT_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
> +                                 zero_entry_counter, NULL);
> +       }
>  }
>
>  static struct xt_counters * alloc_counters(struct xt_table *table)
>  {
>        unsigned int countersize;
>        struct xt_counters *counters;
> -       const struct xt_table_info *private = table->private;
> +       struct xt_table_info *private = table->private;
> +       struct xt_table_info *info;
>
>        /* We need atomic snapshot of counters: rest doesn't change
>           (other than comefrom, which userspace doesn't care
> @@ -939,14 +996,30 @@ static struct xt_counters * alloc_counte
>        counters = vmalloc_node(countersize, numa_node_id());
>
>        if (counters == NULL)
> -               return ERR_PTR(-ENOMEM);
> +               goto nomem;
> +
> +       info = xt_alloc_table_info(private->size);
> +       if (!info)
> +               goto free_counters;
> +
> +       clone_counters(info, private);
>
> -       /* First, sum counters... */
> -       write_lock_bh(&table->lock);
> -       get_counters(private, counters);
> -       write_unlock_bh(&table->lock);
> +       mutex_lock(&table->lock);
> +       xt_table_entry_swap_rcu(private, info);
> +       synchronize_net();      /* Wait until smoke has cleared */
> +
> +       get_counters(info, counters);
> +       put_counters(private, counters);
> +       mutex_unlock(&table->lock);
> +
> +       xt_free_table_info(info);
>
>        return counters;
> +
> + free_counters:
> +       vfree(counters);
> + nomem:
> +       return ERR_PTR(-ENOMEM);
>  }
>
>  static int
> @@ -1312,27 +1385,6 @@ do_replace(struct net *net, void __user
>        return ret;
>  }
>
> -/* We're lazy, and add to the first CPU; overflow works its fey magic
> - * and everything is OK. */
> -static int
> -add_counter_to_entry(struct ipt_entry *e,
> -                    const struct xt_counters addme[],
> -                    unsigned int *i)
> -{
> -#if 0
> -       duprintf("add_counter: Entry %u %lu/%lu + %lu/%lu\n",
> -                *i,
> -                (long unsigned int)e->counters.pcnt,
> -                (long unsigned int)e->counters.bcnt,
> -                (long unsigned int)addme[*i].pcnt,
> -                (long unsigned int)addme[*i].bcnt);
> -#endif
> -
> -       ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
> -
> -       (*i)++;
> -       return 0;
> -}
>
>  static int
>  do_add_counters(struct net *net, void __user *user, unsigned int len, int compat)
> @@ -1393,13 +1445,14 @@ do_add_counters(struct net *net, void __
>                goto free;
>        }
>
> -       write_lock_bh(&t->lock);
> +       mutex_lock(&t->lock);
>        private = t->private;
>        if (private->number != num_counters) {
>                ret = -EINVAL;
>                goto unlock_up_free;
>        }
>
> +       preempt_disable();

Should be local_bh_disable since the counters could be touched in that path?

>        i = 0;
>        /* Choose the copy that is on our node */
>        loc_cpu_entry = private->entries[raw_smp_processor_id()];
> @@ -1408,8 +1461,9 @@ do_add_counters(struct net *net, void __
>                          add_counter_to_entry,
>                          paddc,
>                          &i);
> +       preempt_enable();
>  unlock_up_free:
> -       write_unlock_bh(&t->lock);
> +       mutex_unlock(&t->lock);
>        xt_table_unlock(t);
>        module_put(t->me);
>  free:
> --- a/net/netfilter/x_tables.c  2009-02-09 08:30:58.642782131 -0800
> +++ b/net/netfilter/x_tables.c  2009-02-09 08:32:24.018308401 -0800
> @@ -625,6 +625,20 @@ void xt_free_table_info(struct xt_table_
>  }
>  EXPORT_SYMBOL(xt_free_table_info);
>
> +void xt_table_entry_swap_rcu(struct xt_table_info *oldinfo,
> +                            struct xt_table_info *newinfo)
> +{
> +       unsigned int cpu;
> +
> +       for_each_possible_cpu(cpu) {
> +               void *p = oldinfo->entries[cpu];
> +               rcu_assign_pointer(oldinfo->entries[cpu], newinfo->entries[cpu]);
> +               newinfo->entries[cpu] = p;
> +       }
> +
> +}
> +EXPORT_SYMBOL_GPL(xt_table_entry_swap_rcu);
> +
>  /* Find table by name, grabs mutex & ref.  Returns ERR_PTR() on error. */
>  struct xt_table *xt_find_table_lock(struct net *net, u_int8_t af,
>                                    const char *name)
> @@ -671,21 +685,22 @@ xt_replace_table(struct xt_table *table,
>        struct xt_table_info *oldinfo, *private;
>
>        /* Do the substitution. */
> -       write_lock_bh(&table->lock);
> +       mutex_lock(&table->lock);
>        private = table->private;
>        /* Check inside lock: is the old number correct? */
>        if (num_counters != private->number) {
>                duprintf("num_counters != table->private->number (%u/%u)\n",
>                         num_counters, private->number);
> -               write_unlock_bh(&table->lock);
> +               mutex_unlock(&table->lock);
>                *error = -EAGAIN;
>                return NULL;
>        }
>        oldinfo = private;
> -       table->private = newinfo;
> +       rcu_assign_pointer(table->private, newinfo);
>        newinfo->initial_entries = oldinfo->initial_entries;
> -       write_unlock_bh(&table->lock);
> +       mutex_unlock(&table->lock);
>
> +       synchronize_net();
>        return oldinfo;
>  }
>  EXPORT_SYMBOL_GPL(xt_replace_table);
> @@ -719,7 +734,8 @@ struct xt_table *xt_register_table(struc
>
>        /* Simplifies replace_table code. */
>        table->private = bootstrap;
> -       rwlock_init(&table->lock);
> +       mutex_init(&table->lock);
> +
>        if (!xt_replace_table(table, 0, newinfo, &ret))
>                goto unlock;
>
> --- a/net/ipv4/netfilter/arp_tables.c   2009-02-09 08:30:58.630817607 -0800
> +++ b/net/ipv4/netfilter/arp_tables.c   2009-02-09 09:07:18.120931959 -0800
> @@ -237,9 +237,10 @@ unsigned int arpt_do_table(struct sk_buf
>        indev = in ? in->name : nulldevname;
>        outdev = out ? out->name : nulldevname;
>
> -       read_lock_bh(&table->lock);
> -       private = table->private;
> -       table_base = (void *)private->entries[smp_processor_id()];
> +       rcu_read_lock_bh();
> +       private = rcu_dereference(table->private);
> +       table_base = rcu_dereference(private->entries[smp_processor_id()]);
> +
>        e = get_entry(table_base, private->hook_entry[hook]);
>        back = get_entry(table_base, private->underflow[hook]);
>
> @@ -311,7 +312,8 @@ unsigned int arpt_do_table(struct sk_buf
>                        e = (void *)e + e->next_offset;
>                }
>        } while (!hotdrop);
> -       read_unlock_bh(&table->lock);
> +
> +       rcu_read_unlock_bh();
>
>        if (hotdrop)
>                return NF_DROP;
> @@ -714,11 +716,65 @@ static void get_counters(const struct xt
>        }
>  }
>
> -static inline struct xt_counters *alloc_counters(struct xt_table *table)
> +
> +/* We're lazy, and add to the first CPU; overflow works its fey magic
> + * and everything is OK. */
> +static int
> +add_counter_to_entry(struct arpt_entry *e,
> +                    const struct xt_counters addme[],
> +                    unsigned int *i)
> +{
> +       ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
> +
> +       (*i)++;
> +       return 0;
> +}
> +
> +/* Take values from counters and add them back onto the current cpu */
> +static void put_counters(struct xt_table_info *t,
> +                        const struct xt_counters counters[])
> +{
> +       unsigned int i, cpu;
> +
> +       local_bh_disable();
> +       cpu = smp_processor_id();
> +       i = 0;
> +       ARPT_ENTRY_ITERATE(t->entries[cpu],
> +                         t->size,
> +                         add_counter_to_entry,
> +                         counters,
> +                         &i);
> +       local_bh_enable();
> +}
> +
> +static inline int
> +zero_entry_counter(struct arpt_entry *e, void *arg)
> +{
> +       e->counters.bcnt = 0;
> +       e->counters.pcnt = 0;
> +       return 0;
> +}
> +
> +static void
> +clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
> +{
> +       unsigned int cpu;
> +       const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
> +
> +       memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
> +       for_each_possible_cpu(cpu) {
> +               memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
> +               ARPT_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
> +                                 zero_entry_counter, NULL);
> +       }
> +}
> +
> +static struct xt_counters *alloc_counters(struct xt_table *table)
>  {
>        unsigned int countersize;
>        struct xt_counters *counters;
> -       const struct xt_table_info *private = table->private;
> +       struct xt_table_info *private = table->private;
> +       struct xt_table_info *info;
>
>        /* We need atomic snapshot of counters: rest doesn't change
>         * (other than comefrom, which userspace doesn't care
> @@ -728,14 +784,30 @@ static inline struct xt_counters *alloc_
>        counters = vmalloc_node(countersize, numa_node_id());
>
>        if (counters == NULL)
> -               return ERR_PTR(-ENOMEM);
> +               goto nomem;
>
> -       /* First, sum counters... */
> -       write_lock_bh(&table->lock);
> -       get_counters(private, counters);
> -       write_unlock_bh(&table->lock);
> +       info = xt_alloc_table_info(private->size);
> +       if (!info)
> +               goto free_counters;
> +
> +       clone_counters(info, private);
> +
> +       mutex_lock(&table->lock);
> +       xt_table_entry_swap_rcu(private, info);
> +       synchronize_net();      /* Wait until smoke has cleared */
> +
> +       get_counters(info, counters);
> +       put_counters(private, counters);
> +       mutex_unlock(&table->lock);
> +
> +       xt_free_table_info(info);
>
>        return counters;
> +
> + free_counters:
> +       vfree(counters);
> + nomem:
> +       return ERR_PTR(-ENOMEM);
>  }
>
>  static int copy_entries_to_user(unsigned int total_size,
> @@ -1075,20 +1147,6 @@ static int do_replace(struct net *net, v
>        return ret;
>  }
>
> -/* We're lazy, and add to the first CPU; overflow works its fey magic
> - * and everything is OK.
> - */
> -static inline int add_counter_to_entry(struct arpt_entry *e,
> -                                      const struct xt_counters addme[],
> -                                      unsigned int *i)
> -{
> -
> -       ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
> -
> -       (*i)++;
> -       return 0;
> -}
> -
>  static int do_add_counters(struct net *net, void __user *user, unsigned int len,
>                           int compat)
>  {
> @@ -1148,13 +1206,14 @@ static int do_add_counters(struct net *n
>                goto free;
>        }
>
> -       write_lock_bh(&t->lock);
> +       mutex_lock(&t->lock);
>        private = t->private;
>        if (private->number != num_counters) {
>                ret = -EINVAL;
>                goto unlock_up_free;
>        }
>
> +       preempt_disable();
>        i = 0;
>        /* Choose the copy that is on our node */
>        loc_cpu_entry = private->entries[smp_processor_id()];
> @@ -1164,7 +1223,8 @@ static int do_add_counters(struct net *n
>                           paddc,
>                           &i);
>  unlock_up_free:
> -       write_unlock_bh(&t->lock);
> +       mutex_unlock(&t->lock);
> +
>        xt_table_unlock(t);
>        module_put(t->me);
>  free:
> --- a/net/ipv6/netfilter/ip6_tables.c   2009-02-09 08:30:58.662807566 -0800
> +++ b/net/ipv6/netfilter/ip6_tables.c   2009-02-09 09:00:50.195531719 -0800
> @@ -373,10 +373,12 @@ ip6t_do_table(struct sk_buff *skb,
>        mtpar.family  = tgpar.family = NFPROTO_IPV6;
>        tgpar.hooknum = hook;
>
> -       read_lock_bh(&table->lock);
>        IP_NF_ASSERT(table->valid_hooks & (1 << hook));
> -       private = table->private;
> -       table_base = (void *)private->entries[smp_processor_id()];
> +
> +       rcu_read_lock_bh();
> +       private = rcu_dereference(table->private);
> +       table_base = rcu_dereference(private->entries[smp_processor_id()]);
> +
>        e = get_entry(table_base, private->hook_entry[hook]);
>
>        /* For return from builtin chain */
> @@ -474,7 +476,7 @@ ip6t_do_table(struct sk_buff *skb,
>  #ifdef CONFIG_NETFILTER_DEBUG
>        ((struct ip6t_entry *)table_base)->comefrom = NETFILTER_LINK_POISON;
>  #endif
> -       read_unlock_bh(&table->lock);
> +       rcu_read_unlock_bh();
>
>  #ifdef DEBUG_ALLOW_ALL
>        return NF_ACCEPT;
> @@ -955,11 +957,64 @@ get_counters(const struct xt_table_info
>        }
>  }
>
> +/* We're lazy, and add to the first CPU; overflow works its fey magic
> + * and everything is OK. */
> +static int
> +add_counter_to_entry(struct ip6t_entry *e,
> +                    const struct xt_counters addme[],
> +                    unsigned int *i)
> +{
> +       ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
> +
> +       (*i)++;
> +       return 0;
> +}
> +
> +/* Take values from counters and add them back onto the current cpu */
> +static void put_counters(struct xt_table_info *t,
> +                        const struct xt_counters counters[])
> +{
> +       unsigned int i, cpu;
> +
> +       local_bh_disable();
> +       cpu = smp_processor_id();
> +       i = 0;
> +       IP6T_ENTRY_ITERATE(t->entries[cpu],
> +                          t->size,
> +                          add_counter_to_entry,
> +                          counters,
> +                          &i);
> +       local_bh_enable();
> +}
> +
> +static inline int
> +zero_entry_counter(struct ip6t_entry *e, void *arg)
> +{
> +       e->counters.bcnt = 0;
> +       e->counters.pcnt = 0;
> +       return 0;
> +}
> +
> +static void
> +clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
> +{
> +       unsigned int cpu;
> +       const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
> +
> +       memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
> +       for_each_possible_cpu(cpu) {
> +               memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
> +               IP6T_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
> +                                  zero_entry_counter, NULL);
> +       }
> +}
> +
>  static struct xt_counters *alloc_counters(struct xt_table *table)
>  {
>        unsigned int countersize;
>        struct xt_counters *counters;
> -       const struct xt_table_info *private = table->private;
> +       struct xt_table_info *private = table->private;
> +       struct xt_table_info *info;
>
>        /* We need atomic snapshot of counters: rest doesn't change
>           (other than comefrom, which userspace doesn't care
> @@ -968,14 +1023,28 @@ static struct xt_counters *alloc_counter
>        counters = vmalloc_node(countersize, numa_node_id());
>
>        if (counters == NULL)
> -               return ERR_PTR(-ENOMEM);
> +               goto nomem;
>
> -       /* First, sum counters... */
> -       write_lock_bh(&table->lock);
> -       get_counters(private, counters);
> -       write_unlock_bh(&table->lock);
> +       info = xt_alloc_table_info(private->size);
> +       if (!info)
> +               goto free_counters;
> +
> +       clone_counters(info, private);
>
> -       return counters;
> +       mutex_lock(&table->lock);
> +       xt_table_entry_swap_rcu(private, info);
> +       synchronize_net();      /* Wait until smoke has cleared */
> +
> +       get_counters(info, counters);
> +       put_counters(private, counters);
> +       mutex_unlock(&table->lock);
> +
> +       xt_free_table_info(info);
> +
> + free_counters:
> +       vfree(counters);
> + nomem:
> +       return ERR_PTR(-ENOMEM);
>  }
>
>  static int
> @@ -1342,28 +1411,6 @@ do_replace(struct net *net, void __user
>        return ret;
>  }
>
> -/* We're lazy, and add to the first CPU; overflow works its fey magic
> - * and everything is OK. */
> -static inline int
> -add_counter_to_entry(struct ip6t_entry *e,
> -                    const struct xt_counters addme[],
> -                    unsigned int *i)
> -{
> -#if 0
> -       duprintf("add_counter: Entry %u %lu/%lu + %lu/%lu\n",
> -                *i,
> -                (long unsigned int)e->counters.pcnt,
> -                (long unsigned int)e->counters.bcnt,
> -                (long unsigned int)addme[*i].pcnt,
> -                (long unsigned int)addme[*i].bcnt);
> -#endif
> -
> -       ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
> -
> -       (*i)++;
> -       return 0;
> -}
> -
>  static int
>  do_add_counters(struct net *net, void __user *user, unsigned int len,
>                int compat)
> @@ -1424,13 +1471,14 @@ do_add_counters(struct net *net, void __
>                goto free;
>        }
>
> -       write_lock_bh(&t->lock);
> +       mutex_lock(&t->lock);
>        private = t->private;
>        if (private->number != num_counters) {
>                ret = -EINVAL;
>                goto unlock_up_free;
>        }
>
> +       preempt_disable();
>        i = 0;
>        /* Choose the copy that is on our node */
>        loc_cpu_entry = private->entries[raw_smp_processor_id()];
> @@ -1439,8 +1487,9 @@ do_add_counters(struct net *net, void __
>                          add_counter_to_entry,
>                          paddc,
>                          &i);
> +       preempt_enable();
>  unlock_up_free:
> -       write_unlock_bh(&t->lock);
> +       mutex_unlock(&t->lock);
>        xt_table_unlock(t);
>        module_put(t->me);
>  free:
> --

I applied and tested the patch and saw no issues. oprofile results
confirm significant reduction in CPU cycles spent in ipt_do_table
while running hundreds of threads of netperf traffic. Thanks!

-Ranjit

> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: [RFC] iptables: lock free counters (v0.6)

[Rick Jones]

Stephen Hemminger wrote:
> The reader/writer lock in ip_tables is acquired in the critical path of
> processing packets and is one of the reasons just loading iptables can cause
> a 20% performance loss. The rwlock serves two functions:
> 
> 1) it prevents changes to table state (xt_replace) while table is in use.
>    This is now handled by doing rcu on the xt_table. When table is
>    replaced, the new table(s) are put in and the old one table(s) are freed
>    after RCU period.
> 
> 2) it provides synchronization when accesing the counter values.
>    This is now handled by swapping in new table_info entries for each cpu
>    then summing the old values, and putting the result back onto one
>    cpu.  On a busy system it may cause sampling to occur at different
>    times on each cpu, but no packet/byte counts are lost in the process.

I've taken this round for a spin on the 32-core setup.  I'd not previously 
applied Patrick's patches to remove the initialization, so my kludges to compile 
may have altered things, but assuming it was OK (convert the inits to 
__MUTEX_INITIALIZER to make the compiler happy) it appears that this change does 
very good things indeed for the "empty" case.  Where the 
2.6.29-rc2/unpatchednet-next showed a 50% drop (handwaving math) in the "empty" 
case compared to the "none" case (aka none is no iptables modules loaded, empty 
being what one gets after iptables --list) this patch shows what appears to be a 
much much smaller drop of less than 6%.

The original data can be seen at:

ftp://ftp.netperf.org/iptable_scaling/  in no_iptables and empty_iptables

and the data after this patch can be seen at:

ftp://ftp.netperf.org/hemminger/hemminger6/  in none and empty

while I have none of Eric's patches in this tree, just for grins I went ahead and 
ran "full" as well.

happy benchmarking,

rick jones

Re: [RFT 3/3] iptables: lock free counters

[Patrick McHardy]

Stephen Hemminger wrote:

> --- a/net/ipv4/netfilter/ip_tables.c	2009-01-29 11:09:20.720069979 -0800
> +++ b/net/ipv4/netfilter/ip_tables.c	2009-01-29 11:10:49.827070289 -0800
> @@ -347,9 +347,9 @@ ipt_do_table(struct sk_buff *skb,
>  	mtpar.family  = tgpar.family = NFPROTO_IPV4;
>  	tgpar.hooknum = hook;
>  
> -	read_lock_bh(&table->lock);
> +	rcu_read_lock_bh();
>  	IP_NF_ASSERT(table->valid_hooks & (1 << hook));
> -	private = table->private;
> +	private = rcu_dereference(table->private);
>  	table_base = (void *)private->entries[smp_processor_id()];
>  	e = get_entry(table_base, private->hook_entry[hook]);

I think this doesn't actually need the _bh rcu_read_lock() variant
since updates are never done in softirq context.

Re: [RFT 1/3] netfilter: change elements in x_tables

[Patrick McHardy]

Applied.

Re: [RFT 2/3] netfilter: remove unneeded initializations

[Patrick McHardy]

Stephen Hemminger wrote:

These first two patches look fine obviously. Do you want me to
already apply them?

Re: [RFT 2/3] netfilter: remove unneeded initializations

[Stephen Hemminger]

On Mon, 09 Feb 2009 16:37:23 +0100
Patrick McHardy <kaber@trash.net> wrote:

> Stephen Hemminger wrote:
> 
> These first two patches look fine obviously. Do you want me to
> already apply them?

yes. and there is an ebtables one as well.

Re: [RFT 2/3] netfilter: remove unneeded initializations

[Patrick McHardy]

Stephen Hemminger wrote:
> On Mon, 09 Feb 2009 16:37:23 +0100
> Patrick McHardy <kaber@trash.net> wrote:
> 
>> Stephen Hemminger wrote:
>>
>> These first two patches look fine obviously. Do you want me to
>> already apply them?
> 
> yes. and there is an ebtables one as well.

OK thanks, I'll apply RFT 1/3 and 2/3 and the one you just sent.

[PATCH] ebtables: remove unneeded initializations

[Stephen Hemminger]

The initialization of the lock element is not needed
since the lock is always initialized in ebt_register_table.

Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>

---
 net/bridge/netfilter/ebtable_broute.c |    1 -
 net/bridge/netfilter/ebtable_filter.c |    1 -
 net/bridge/netfilter/ebtable_nat.c    |    1 -
 3 files changed, 3 deletions(-)

--- a/net/bridge/netfilter/ebtable_broute.c	2009-02-02 15:06:29.824499691 -0800
+++ b/net/bridge/netfilter/ebtable_broute.c	2009-02-02 15:06:39.925749434 -0800
@@ -46,7 +46,6 @@ static struct ebt_table broute_table =
 	.name		= "broute",
 	.table		= &initial_table,
 	.valid_hooks	= 1 << NF_BR_BROUTING,
-	.lock		= __RW_LOCK_UNLOCKED(broute_table.lock),
 	.check		= check,
 	.me		= THIS_MODULE,
 };
--- a/net/bridge/netfilter/ebtable_filter.c	2009-02-02 15:06:29.800254518 -0800
+++ b/net/bridge/netfilter/ebtable_filter.c	2009-02-02 15:06:39.925749434 -0800
@@ -55,7 +55,6 @@ static struct ebt_table frame_filter =
 	.name		= "filter",
 	.table		= &initial_table,
 	.valid_hooks	= FILTER_VALID_HOOKS,
-	.lock		= __RW_LOCK_UNLOCKED(frame_filter.lock),
 	.check		= check,
 	.me		= THIS_MODULE,
 };
--- a/net/bridge/netfilter/ebtable_nat.c	2009-02-02 15:06:29.808250256 -0800
+++ b/net/bridge/netfilter/ebtable_nat.c	2009-02-02 15:06:39.925749434 -0800
@@ -55,7 +55,6 @@ static struct ebt_table frame_nat =
 	.name		= "nat",
 	.table		= &initial_table,
 	.valid_hooks	= NAT_VALID_HOOKS,
-	.lock		= __RW_LOCK_UNLOCKED(frame_nat.lock),
 	.check		= check,
 	.me		= THIS_MODULE,
 };

Re: [PATCH] ebtables: remove unneeded initializations

[Patrick McHardy]

Stephen Hemminger wrote:
> The initialization of the lock element is not needed
> since the lock is always initialized in ebt_register_table.

Also applied, thanks. I'll push out my current tree now, should be
on kernel.org in a few minutes.

Re: [RFT 2/3] netfilter: remove unneeded initializations

[Patrick McHardy]

Applied, thanks.