iptables: eliminate read/write lock (v0.4)
Subsystems (4)
cover iptables: eliminate read/write lock (v0.4)
More of Eric's suggestions, handle the case of aggregation of counters correctly. Unfortunately, can't easily make xt_add_counter inline because DEFINE_PER_CPU doesn't seem to export to modules correctly.
PATCH 1/6 netfilter: change elements in x_tables
Change to proper type on private pointer rather than anonymous void. Keep active elements on same cache line.
--- include/linux/netfilter/x_tables.h | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-)
include/linux/netfilter/x_tables.h +4 -5
@@ -349,9 +349,6 @@ struct xt_table {struct list_head list; -/* A unique name... */ -const char name[XT_TABLE_MAXNAMELEN ]; -/* What hooks you will enter on */ unsigned int valid_hooks;
@@ -359,13 +356,15 @@ struct xt_tablerwlock_t lock;/* Man behind the curtain... */ -//struct ip6t_table_info *private; -void *private; +struct xt_table_info *private;/* Set this to THIS_MODULE if you are a module, otherwise NULL */ struct module *me;u_int8_t af;/* address/protocol family */ + +/* A unique name... */ +const char name[XT_TABLE_MAXNAMELEN ]; };#include <linux/netfilter_ipv4.h>
PATCH 2/6 netfilter: remove unneeded initializations
In reply to Stephen HemmingerLater patches change the locking on xt_table and the initialization of the lock element is not needed since the lock is always initialized in xt_table_register anyway.
--- net/ipv4/netfilter/arptable_filter.c | 2 -- net/ipv4/netfilter/iptable_filter.c | 1 - net/ipv4/netfilter/iptable_mangle.c | 1 - net/ipv4/netfilter/iptable_raw.c | 1 - net/ipv4/netfilter/iptable_security.c | 1 - net/ipv4/netfilter/nf_nat_rule.c | 1 - net/ipv6/netfilter/ip6table_filter.c | 1 - net/ipv6/netfilter/ip6table_mangle.c | 1 - net/ipv6/netfilter/ip6table_raw.c | 1 - net/ipv6/netfilter/ip6table_security.c | 1 - 10 files changed, 11 deletions(-)
net/ipv4/netfilter/arptable_filter.c +0 -2
@@ -48,8 +48,6 @@ static structstatic struct xt_table packet_filter = { .name ="filter" , .valid_hooks =FILTER_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (packet_filter.lock), - .private =NULL , .me =THIS_MODULE , .af =NFPROTO_ARP , };
net/ipv4/netfilter/iptable_filter.c +0 -1
@@ -56,7 +56,6 @@ static structstatic struct xt_table packet_filter = { .name ="filter" , .valid_hooks =FILTER_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (packet_filter.lock), .me =THIS_MODULE , .af =AF_INET , };
net/ipv4/netfilter/iptable_raw.c +0 -1
@@ -39,7 +39,6 @@ static structstatic struct xt_table packet_raw = { .name ="raw" , .valid_hooks =RAW_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (packet_raw.lock), .me =THIS_MODULE , .af =AF_INET , };
net/ipv4/netfilter/iptable_security.c +0 -1
@@ -60,7 +60,6 @@ static structstatic struct xt_table security_table = { .name ="security" , .valid_hooks =SECURITY_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (security_table.lock), .me =THIS_MODULE , .af =AF_INET , };
net/ipv4/netfilter/nf_nat_rule.c +0 -1
@@ -61,7 +61,6 @@ static structstatic struct xt_table nat_table = { .name ="nat" , .valid_hooks =NAT_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (nat_table.lock), .me =THIS_MODULE , .af =AF_INET , };
net/ipv6/netfilter/ip6table_filter.c +0 -1
@@ -54,7 +54,6 @@ static structstatic struct xt_table packet_filter = { .name ="filter" , .valid_hooks =FILTER_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (packet_filter.lock), .me =THIS_MODULE , .af =AF_INET6 , };
net/ipv6/netfilter/ip6table_mangle.c +0 -1
@@ -60,7 +60,6 @@ static structstatic struct xt_table packet_mangler = { .name ="mangle" , .valid_hooks =MANGLE_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (packet_mangler.lock), .me =THIS_MODULE , .af =AF_INET6 , };
net/ipv6/netfilter/ip6table_raw.c +0 -1
@@ -38,7 +38,6 @@ static structstatic struct xt_table packet_raw = { .name ="raw" , .valid_hooks =RAW_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (packet_raw.lock), .me =THIS_MODULE , .af =AF_INET6 , };
net/ipv6/netfilter/ip6table_security.c +0 -1
@@ -59,7 +59,6 @@ static structstatic struct xt_table security_table = { .name ="security" , .valid_hooks =SECURITY_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (security_table.lock), .me =THIS_MODULE , .af =AF_INET6 , };
net/ipv4/netfilter/iptable_mangle.c +0 -1
@@ -67,7 +67,6 @@ static structstatic struct xt_table packet_mangler = { .name ="mangle" , .valid_hooks =MANGLE_VALID_HOOKS , - .lock =__RW_LOCK_UNLOCKED (packet_mangler.lock), .me =THIS_MODULE , .af =AF_INET , };
PATCH 3/6 ebtables: remove unneeded initializations
In reply to Stephen HemmingerThe initialization of the lock element is not needed since the lock is always initialized in ebt_register_table.
--- 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(-)
net/bridge/netfilter/ebtable_broute.c +0 -1
@@ -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, };
net/bridge/netfilter/ebtable_filter.c +0 -1
@@ -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, };
net/bridge/netfilter/ebtable_nat.c +0 -1
@@ -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, };
PATCH 4/6 netfilter: abstract xt_counters
In reply to Stephen HemmingerBreak out the parts of the x_tables code that manipulates counters so changes to locking are easier.
--- include/linux/netfilter/x_tables.h | 6 +++++- net/ipv4/netfilter/arp_tables.c | 9 +++++---- net/ipv4/netfilter/ip_tables.c | 9 +++++---- net/ipv6/netfilter/ip6_tables.c | 21 +++++++++++---------- net/netfilter/x_tables.c | 15 +++++++++++++++ 5 files changed, 41 insertions(+), 19 deletions(-)
include/linux/netfilter/x_tables.h +5 -1
@@ -105,13 +105,17 @@ struct _xt_align#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 {u_int64_t pcnt, bcnt;/* Packet and byte counters */ }; +extern void xt_add_counter (struct xt_counters *c,unsigned b,unsigned p); +extern void xt_sum_counter (struct xt_counters *t, +int cpu,const struct xt_counters *c); + +/* The argument to IPT_SO_ADD_COUNTERS. */ struct xt_counters_info {
net/ipv4/netfilter/arp_tables.c +5 -4
@@ -256,7 +256,7 @@ unsigned int arpt_do_table(struct sk_buf hdr_len =sizeof (*arp) + (2 *sizeof (struct in_addr )) + (2 * skb->dev->addr_len); -ADD_COUNTER (e->counters, hdr_len,1 ); +xt_add_counter (&e->counters, hdr_len,1 ); t =arpt_get_target (e);
@@ -662,10 +662,11 @@ static int translate_table(const char *n/* Gets counters. */ static inline int add_entry_to_counter (const struct arpt_entry *e, +int cpu,struct xt_counters total[],unsigned int *i) { -ADD_COUNTER (total[*i], e->counters.bcnt, e->counters.pcnt); +xt_sum_counter (total, cpu, &e->counters); (*i)++;return 0 ;
@@ -709,6 +710,7 @@ static void get_counters(const struct xtARPT_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, + cpu, counters, &i); }
@@ -1082,8 +1084,7 @@ static inline int add_counter_to_entry(sconst struct xt_counters addme[], unsigned int *i) { - - ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt); + xt_add_counter(&e->counters, addme[*i].bcnt, addme[*i].pcnt); (*i)++;return 0 ;
net/ipv4/netfilter/ip_tables.c +5 -4
@@ -366,7 +366,7 @@ ipt_do_table(struct sk_buff *skb,if (IPT_MATCH_ITERATE (e, do_match, skb, &mtpar) !=0 ) goto no_match; -ADD_COUNTER (e->counters,ntohs (ip->tot_len),1 ); +xt_add_counter (&e->counters,ntohs (ip->tot_len),1 ); t =ipt_get_target (e);IP_NF_ASSERT (t->u.kernel.target);
@@ -872,10 +872,11 @@ translate_table(const char *name,/* Gets counters. */ static inline int add_entry_to_counter (const struct ipt_entry *e, +int cpu,struct xt_counters total[],unsigned int *i) { -ADD_COUNTER (total[*i], e->counters.bcnt, e->counters.pcnt); +xt_sum_counter (total, cpu, &e->counters); (*i)++;return 0 ;
@@ -921,6 +922,7 @@ get_counters(const struct xt_table_infoIPT_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, + cpu, counters, &i); }
@@ -1327,8 +1329,7 @@ add_counter_to_entry(struct ipt_entry *e (long unsigned int )addme[*i].pcnt, (long unsigned int)addme[*i].bcnt);#endif - -ADD_COUNTER (e->counters, addme[*i].bcnt, addme[*i].pcnt); +xt_add_counter (&e->counters, addme[*i].bcnt, addme[*i].pcnt); (*i)++;return 0 ;
net/ipv6/netfilter/ip6_tables.c +11 -10
@@ -392,9 +392,9 @@ ip6t_do_table(struct sk_buff *skb,if (IP6T_MATCH_ITERATE (e, do_match, skb, &mtpar) !=0 ) goto no_match; -ADD_COUNTER (e->counters, -ntohs (ipv6_hdr (skb)->payload_len) + -sizeof (struct ipv6hdr ),1 ); +xt_add_counter (&e->counters, +ntohs (ipv6_hdr (skb)->payload_len) + +sizeof (struct ipv6hdr ),1 ); t =ip6t_get_target (e);IP_NF_ASSERT (t->u.kernel.target);
@@ -901,10 +901,11 @@ translate_table(const char *name,/* Gets counters. */ static inline int add_entry_to_counter (const struct ip6t_entry *e, +int cpu,struct xt_counters total[],unsigned int *i) { -ADD_COUNTER (total[*i], e->counters.bcnt, e->counters.pcnt); +xt_sum_counter (total, cpu, &e->counters); (*i)++;return 0 ;
@@ -948,10 +949,11 @@ get_counters(const struct xt_table_infocontinue ; i =0 ;IP6T_ENTRY_ITERATE (t->entries[cpu], - t->size, - add_entry_to_counter, - counters, - &i); + t->size, + add_entry_to_counter, + cpu, + counters, + &i); } }
@@ -1357,8 +1359,7 @@ add_counter_to_entry(struct ip6t_entry * (long unsigned int )addme[*i].pcnt, (long unsigned int)addme[*i].bcnt);#endif - -ADD_COUNTER (e->counters, addme[*i].bcnt, addme[*i].pcnt); +xt_add_counter (&e->counters, addme[*i].bcnt, addme[*i].pcnt); (*i)++;return 0 ;
net/netfilter/x_tables.c +15 -0
@@ -577,6 +577,21 @@ int xt_compat_target_to_user(struct xt_eEXPORT_SYMBOL_GPL (xt_compat_target_to_user);#endif +void xt_add_counter (struct xt_counters *c,unsigned b,unsigned p) +{ + c->bcnt += b; + c->pcnt += p; +} +EXPORT_SYMBOL_GPL (xt_add_counter); + +void xt_sum_counter (struct xt_counters *t,int cpu, +const struct xt_counters *c) +{ + t->pcnt += c->pcnt; + t->bcnt += c->bcnt; +} +EXPORT_SYMBOL_GPL (xt_sum_counter); +struct xt_table_info *xt_alloc_table_info (unsigned int size) {struct xt_table_info *newinfo;
Re: [PATCH 4/6] netfilter: abstract xt_counters
Quoted 188 lines · Stephen Hemminger
Break out the parts of the
x_tablescode that manipulates counters so changes to locking are easier.Signed-off-by Stephen Hemminger <[email protected]>--- include/linux/netfilter/x_tables.h | 6 +++++- net/ipv4/netfilter/arp_tables.c | 9 +++++---- net/ipv4/netfilter/ip_tables.c | 9 +++++---- net/ipv6/netfilter/ip6_tables.c | 21 +++++++++++---------- net/netfilter/x_tables.c | 15 +++++++++++++++ 5 files changed, 41 insertions(+), 19 deletions(-)include/linux/netfilter/x_tables.h +5
-1@@ -105,13 +105,17 @@ struct _xt_align#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 {u_int64_t pcnt, bcnt;/* Packet and byte counters */ }; +extern void xt_add_counter (struct xt_counters *c,unsigned b,unsigned p); +extern void xt_sum_counter (struct xt_counters *t, +int cpu,const struct xt_counters *c); + +/* The argument to IPT_SO_ADD_COUNTERS. */ struct xt_counters_info {net/ipv4/netfilter/arp_tables.c +5
-4@@ -256,7 +256,7 @@ unsigned int arpt_do_table(struct sk_buf hdr_len =sizeof (*arp) + (2 *sizeof (struct in_addr )) + (2 * skb->dev->addr_len); -ADD_COUNTER (e->counters, hdr_len,1 ); +xt_add_counter (&e->counters, hdr_len,1 ); t =arpt_get_target (e);@@ -662,10 +662,11 @@ static int translate_table(const char *n/* Gets counters. */ static inline int add_entry_to_counter (const struct arpt_entry *e, +int cpu,struct xt_counters total[],unsigned int *i) { -ADD_COUNTER (total[*i], e->counters.bcnt, e->counters.pcnt); +xt_sum_counter (total, cpu, &e->counters); (*i)++;return 0 ;@@ -709,6 +710,7 @@ static void get_counters(const struct xtARPT_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, + cpu, counters, &i); }@@ -1082,8 +1084,7 @@ static inline int add_counter_to_entry(sconst struct xt_counters addme[], unsigned int *i) { - - ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt); + xt_add_counter(&e->counters, addme[*i].bcnt, addme[*i].pcnt); (*i)++;return 0 ;net/ipv4/netfilter/ip_tables.c +5
-4@@ -366,7 +366,7 @@ ipt_do_table(struct sk_buff *skb,if (IPT_MATCH_ITERATE (e, do_match, skb, &mtpar) !=0 ) goto no_match; -ADD_COUNTER (e->counters,ntohs (ip->tot_len),1 ); +xt_add_counter (&e->counters,ntohs (ip->tot_len),1 ); t =ipt_get_target (e);IP_NF_ASSERT (t->u.kernel.target);@@ -872,10 +872,11 @@ translate_table(const char *name,/* Gets counters. */ static inline int add_entry_to_counter (const struct ipt_entry *e, +int cpu,struct xt_counters total[],unsigned int *i) { -ADD_COUNTER (total[*i], e->counters.bcnt, e->counters.pcnt); +xt_sum_counter (total, cpu, &e->counters); (*i)++;return 0 ;@@ -921,6 +922,7 @@ get_counters(const struct xt_table_infoIPT_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, + cpu, counters, &i); }@@ -1327,8 +1329,7 @@ add_counter_to_entry(struct ipt_entry *e (long unsigned int )addme[*i].pcnt, (long unsigned int)addme[*i].bcnt);#endif - -ADD_COUNTER (e->counters, addme[*i].bcnt, addme[*i].pcnt); +xt_add_counter (&e->counters, addme[*i].bcnt, addme[*i].pcnt); (*i)++;return 0 ;net/ipv6/netfilter/ip6_tables.c +11
-10@@ -392,9 +392,9 @@ ip6t_do_table(struct sk_buff *skb,if (IP6T_MATCH_ITERATE (e, do_match, skb, &mtpar) !=0 ) goto no_match; -ADD_COUNTER (e->counters, -ntohs (ipv6_hdr (skb)->payload_len) + -sizeof (struct ipv6hdr ),1 ); +xt_add_counter (&e->counters, +ntohs (ipv6_hdr (skb)->payload_len) + +sizeof (struct ipv6hdr ),1 ); t =ip6t_get_target (e);IP_NF_ASSERT (t->u.kernel.target);@@ -901,10 +901,11 @@ translate_table(const char *name,/* Gets counters. */ static inline int add_entry_to_counter (const struct ip6t_entry *e, +int cpu,struct xt_counters total[],unsigned int *i) { -ADD_COUNTER (total[*i], e->counters.bcnt, e->counters.pcnt); +xt_sum_counter (total, cpu, &e->counters); (*i)++;return 0 ;@@ -948,10 +949,11 @@ get_counters(const struct xt_table_infocontinue ; i =0 ;IP6T_ENTRY_ITERATE (t->entries[cpu], - t->size, - add_entry_to_counter, - counters, - &i); + t->size, + add_entry_to_counter, + cpu, + counters, + &i); } }@@ -1357,8 +1359,7 @@ add_counter_to_entry(struct ip6t_entry * (long unsigned int )addme[*i].pcnt, (long unsigned int)addme[*i].bcnt);#endif - -ADD_COUNTER (e->counters, addme[*i].bcnt, addme[*i].pcnt); +xt_add_counter (&e->counters, addme[*i].bcnt, addme[*i].pcnt); (*i)++;return 0 ;net/netfilter/x_tables.c +8
-0@@ -577,6 +577,21 @@ int xt_compat_target_to_user(struct xt_eEXPORT_SYMBOL_GPL (xt_compat_target_to_user);#endif +void xt_add_counter (struct xt_counters *c,unsigned b,unsigned p) +{ + c->bcnt += b; + c->pcnt += p; +} +EXPORT_SYMBOL_GPL (xt_add_counter); + +void xt_sum_counter(struct xt_counters *t, int cpu,
net/netfilter/x_tables.c int xt_compat_target_to_user(struct xt_e · line 597
Quoted 10 lines
net/netfilter/x_tables.c +7
-0+ const struct xt_counters *c) +{ + t->pcnt += c->pcnt; + t->bcnt += c->bcnt; +} +EXPORT_SYMBOL_GPL (xt_sum_counter); +struct xt_table_info *xt_alloc_table_info (unsigned int size) {struct xt_table_info *newinfo;
First I wondered if adding out of line xt_add_counter() could slow firewalls,
I did some testings, with tbench and a small iptables setup (about 16 matched rules per packet)
CPU: Core 2, speed 3000.11 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 100000
samples % symbol name 3166081 12.8996 ipt_do_table 2471426 10.0694 copy_from_user 1016717 4.1424 copy_to_user 902072 3.6753 schedule 687266 2.8001 xt_add_counter 589899 2.4034 tcp_sendmsg 579619 2.3615 tcp_ack 455883 1.8574 tcp_transmit_skb
c044d110 <xt_add_counter>: /* xt_add_counter total: 687266 2.8001 */
80675 0.3287 :c044d110: push %ebp
15574 0.0635 :c044d111: mov %esp,%ebp
2 8.1e-06 :c044d113: sub $0xc,%esp
39583 0.1613 :c044d116: mov %ebx,(%esp)
4387 0.0179 :c044d119: mov %edi,0x8(%esp)
1187 0.0048 :c044d11d: mov %esi,0x4(%esp)
1601 0.0065 :c044d121: mov $0xc068ae4c,%edi
38881 0.1584 :c044d126: mov %fs:0xc0688540,%ebx
5585 0.0228 :c044d12d: add %ebx,%edi
3910 0.0159 :c044d12f: incl (%edi)
133482 0.5438 :c044d131: xor %esi,%esi
32 1.3e-04 :c044d133: add %edx,0x8(%eax)
71181 0.2900 :c044d136: mov %ecx,%edx
7986 0.0325 :c044d138: adc %esi,0xc(%eax)
88695 0.3614 :c044d13b: xor %ecx,%ecx
15 6.1e-05 :c044d13d: add %edx,(%eax)
41496 0.1691 :c044d13f: adc %ecx,0x4(%eax)
52944 0.2157 :c044d142: incl (%edi)
30759 0.1253 :c044d144: mov (%esp),%ebx
20241 0.0825 :c044d147: mov 0x4(%esp),%esi
5662 0.0231 :c044d14b: mov 0x8(%esp),%edi
2288 0.0093 :c044d14f: leave
41100 0.1675 :c044d150: rettbench 8 results here, after all your patches applied :
Throughput 2331 MB/sec 8 procs
And if inlined :
Throughput 2359.06 MB/sec 8 procs
and if we check inlined code/costs we see :
2597 0.1719 :c048dfee: mov -0x64(%ebp),%edx
182 0.0120 :c048dff1: movzwl 0x2(%edx),%eax
524 0.0347 :c048dff5: mov %fs:0xc0688540,%ecx
7 4.6e-04 :c048dffc: add -0x70(%ebp),%ecx
2465 0.1632 :c048dfff: incl (%ecx)
9476 0.6273 :c048e001: addl $0x1,0x60(%edi)
10068 0.6665 :c048e005: adcl $0x0,0x64(%edi)
6543 0.4332 :c048e009: xor %edx,%edx
1 6.6e-05 :c048e00b: rol $0x8,%ax
234 0.0155 :c048e00f: movzwl %ax,%eax
2198 0.1455 :c048e012: add %eax,0x68(%edi)
80 0.0053 :c048e015: adc %edx,0x6c(%edi)
2858 0.1892 :c048e018: incl (%ecx)With upcoming work on fast percpu accesses, we might in the future see following code:
(no need for registers to compute address of variable)
mov -0x64(%ebp),%edx
movzwl 0x2(%edx),%eax
incl %fs:xt_counter_sequence
addl $0x1,0x60(%edi)
adcl $0x0,0x64(%edi)
xor %edx,%edx
rol $0x8,%ax
movzwl %ax,%eax
add %eax,0x68(%edi)
adc %edx,0x6c(%edi)
incl %fs:xt_counter_sequencePATCH 3/3 iptables: lock free counters (alternate version)
This is an alternative to earlier RCU/seqcount_t version of counters. The counters operate as usual without locking, but when counters are rotated around the CPU's entries. RCU is used in two ways, first to handle the counter rotation, second for replace.
--- include/linux/netfilter/x_tables.h | 10 +++- net/ipv4/netfilter/arp_tables.c | 73 +++++++++++++++++++++++++++--------- net/ipv4/netfilter/ip_tables.c | 68 ++++++++++++++++++++++++--------- net/ipv6/netfilter/ip6_tables.c | 75 ++++++++++++++++++++++++++----------- net/netfilter/x_tables.c | 43 +++++++++++++++------ 5 files changed, 197 insertions(+), 72 deletions(-)
include/linux/netfilter/x_tables.h +8 -2
@@ -353,7 +353,7 @@ struct xt_tableunsigned 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_infounsigned 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) \
net/ipv4/netfilter/ip_tables.c +50 -18
142 lines not on this page · raw message
net/netfilter/x_tables.c +31 -12
76 lines not on this page · raw message
net/ipv4/netfilter/arp_tables.c +55 -18
144 lines not on this page · raw message
net/ipv6/netfilter/ip6_tables.c +53 -22
145 lines not on this page · raw message
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
Quoted 5 lines · Stephen Hemminger
This is an alternative to earlier RCU/seqcount_t version of counters. The counters operate as usual without locking, but when counters are rotated around the CPU's entries. RCU is used in two ways, first to handle the counter rotation, second for replace.
Is it a working patch or just a prototype ?
Quoted 95 lines
Signed-off-by Stephen Hemminger <[email protected]>--- include/linux/netfilter/x_tables.h | 10 +++- net/ipv4/netfilter/arp_tables.c | 73 +++++++++++++++++++++++++++--------- net/ipv4/netfilter/ip_tables.c | 68 ++++++++++++++++++++++++--------- net/ipv6/netfilter/ip6_tables.c | 75 ++++++++++++++++++++++++++----------- net/netfilter/x_tables.c | 43 +++++++++++++++------ 5 files changed, 197 insertions(+), 72 deletions(-)include/linux/netfilter/x_tables.h +8
-2@@ -353,7 +353,7 @@ struct xt_tableunsigned 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_infounsigned 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) \net/ipv4/netfilter/ip_tables.c +20
-9@@ -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 ;@@ -892,45 +894,73 @@ set_entry_to_counter(const struct ipt_enreturn 0 ; } +static inline int +set_counter_to_entry (struct ipt_entry *e, +const struct ipt_counters total[], +unsigned int *i) +{ +SET_COUNTER (e->counters, total[*i].bcnt, total[*i].pcnt); + + (*i)++; +return 0 ; +} + +static void -get_counters (const struct xt_table_info *t, +get_counters (struct xt_table_info *t,struct xt_counters counters[]) {unsigned int cpu;unsigned int i;unsigned int curcpu; +struct ipt_entry *e; -/* Instead of clearing (by a previous call to memset()) -* the counters and using adds, we set the counters -* with data used by 'current' CPU -* We dont care about preemption here.
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 924
Quoted 10 lines
net/ipv4/netfilter/ip_tables.c +3
-3-*/ +preempt_disable (); curcpu =raw_smp_processor_id (); - + e = t->entries[curcpu]; i =0 ; - IPT_ENTRY_ITERATE(t->entries[curcpu], + IPT_ENTRY_ITERATE(e, t->size, set_entry_to_counter,
Hum, current cpu might be interrupted by NIC, since you only disabled preemption. set_entry_to_counter() might get garbage.
I suppose I already mentioned it :)
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 935
Quoted 11 lines
net/ipv4/netfilter/ip_tables.c +5
-0counters, &i);for_each_possible_cpu (cpu) { +void *p; +if (cpu == curcpu)continue ; + +/* Swizzle the values and wait */ + e->counters = ((struct xt_counters ) {0 ,0 });
I dont see what you want to do here...
e->counters is the counter associated with rule #0
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 938
Quoted 3 lines
net/ipv4/netfilter/ip_tables.c +3
-0+ p = t->entries[cpu]; +rcu_assign_pointer (t->entries[cpu], e); +synchronize_net ();
Oh well, not this synchronize_net() :)
This wont provide atomic sampling of counters for whole CPUS, and introduce large delays on big machines (NR_CPUS >= 64)
What problem do we want to solve here ?
Current iptables is able to do an atomic snapshot because of the rwlock.
If we really want to keep this feature (but get rid of rwlock), we might do the reverse with two seqlocks + RCU
One seqlock (seqlock_counters) to protect counter updates One seqlock (seqlock_rules) to protect rules changes
Ie :
ipt_do_table() doing :
{rcu_read_lockread_seqbegin(&table->seqlock_rules);
rcu fetch priv table pointer and work on it
do {
for all counters updates, use
do {
seq = read_seqbegin(table->seqlock_counters);
update counters
}
} while (!hotdrop);rcu_read_unlock()
}
for get_counter() (iptables -L)
writer doing a write_seqlock(&table->seqlock_counters), waiting one RCU grace period, {
get / sum all counters (no updates of counters are allowed)
}write_sequnlock();
for iptables_update/replace (iptables -A|I|D|R|Z|F...)
writer doing a write_seqlock(&table->seqlock_rules), waiting one RCU grace period, {
change rules/counters
}write_sequnlock();
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
Quoted 165 lines · Eric Dumazet
Quoted 5 lines · Stephen Hemminger
This is an alternative to earlier RCU/seqcount_t version of counters. The counters operate as usual without locking, but when counters are rotated around the CPU's entries. RCU is used in two ways, first to handle the counter rotation, second for replace.
Is it a working patch or just a prototype ?
Quoted 95 lines
Signed-off-by Stephen Hemminger <[email protected]>--- include/linux/netfilter/x_tables.h | 10 +++- net/ipv4/netfilter/arp_tables.c | 73 +++++++++++++++++++++++++++--------- net/ipv4/netfilter/ip_tables.c | 68 ++++++++++++++++++++++++--------- net/ipv6/netfilter/ip6_tables.c | 75 ++++++++++++++++++++++++++----------- net/netfilter/x_tables.c | 43 +++++++++++++++------ 5 files changed, 197 insertions(+), 72 deletions(-)include/linux/netfilter/x_tables.h +8
-2@@ -353,7 +353,7 @@ struct xt_tableunsigned 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_infounsigned 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) \net/ipv4/netfilter/ip_tables.c +20
-9@@ -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 ;@@ -892,45 +894,73 @@ set_entry_to_counter(const struct ipt_enreturn 0 ; } +static inline int +set_counter_to_entry (struct ipt_entry *e, +const struct ipt_counters total[], +unsigned int *i) +{ +SET_COUNTER (e->counters, total[*i].bcnt, total[*i].pcnt); + + (*i)++; +return 0 ; +} + +static void -get_counters (const struct xt_table_info *t, +get_counters (struct xt_table_info *t,struct xt_counters counters[]) {unsigned int cpu;unsigned int i;unsigned int curcpu; +struct ipt_entry *e; -/* Instead of clearing (by a previous call to memset()) -* the counters and using adds, we set the counters -* with data used by 'current' CPU -* We dont care about preemption here. net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 924
Quoted 10 lines
net/ipv4/netfilter/ip_tables.c +3
-3-*/ +preempt_disable (); curcpu =raw_smp_processor_id (); - + e = t->entries[curcpu]; i =0 ; - IPT_ENTRY_ITERATE(t->entries[curcpu], + IPT_ENTRY_ITERATE(e, t->size, set_entry_to_counter,Hum, current cpu might be interrupted by NIC, since you only disabled preemption.
set_entry_to_counter()might get garbage.
I suppose I already mentioned it :)net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 935
Quoted 11 lines
net/ipv4/netfilter/ip_tables.c +5
-0counters, &i);for_each_possible_cpu (cpu) { +void *p; +if (cpu == curcpu)continue ; + +/* Swizzle the values and wait */ + e->counters = ((struct xt_counters ) {0 ,0 });I dont see what you want to do here...
e->countersis the counter associated with rule #0net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 938
Quoted 3 lines
net/ipv4/netfilter/ip_tables.c +3
-0+ p = t->entries[cpu]; +rcu_assign_pointer (t->entries[cpu], e); +synchronize_net ();Oh well, not this
synchronize_net():)This wont provide atomic sampling of counters for whole CPUS, and introduce large delays on big machines (
NR_CPUS>= 64)What problem do we want to solve here ?
Current iptables is able to do an atomic snapshot because of the rwlock.
If we really want to keep this feature (but get rid of rwlock), we might do the reverse with two seqlocks + RCU
One seqlock (
seqlock_counters) to protect counter updates One seqlock (seqlock_rules) to protect rules changesIe :
ipt_do_table()doing :
{rcu_read_lockread_seqbegin(&table->seqlock_rules);
rcu fetch priv table pointer and work on it
do {
for all counters updates, use
Quoted 2 lines
do {
seq = read_seqbegin(table->seqlock_counters);Hum... reading my mail, this one can be done once only, at the beginning
Why then I suggested two different seqlocks, I am wondering :)
I need to think a litle bit more, we might do something to allow several "iptables -L" in //
maybe an atomic_t to protect counters would be ok :
Ie :
One atomic_t (counters_readers) to protect counter updates One seqlock (seqlock_rules) to protect rules changes
ipt_do_table() doing :
{
begin:read_seqbegin(&table->seqlock_rules); // it could loop but with BH enabled rcu_read_lock_bh();
while (atomic_read(&table->counters_readers) > 0) {
cpu_relax();
rcu_read_unlock_bh();
goto begin;
}
private = rcu_dereference(table->private);
...
do {
for all counters updates, use
do {
update counters
}
} while (!hotdrop);rcu_read_unlock_bh()
}
for get_counter() (iptables -L) atomic_inc(&table->counters_readers);
waiting one RCU grace period,
{
get / sum all counters (no updates of counters are allowed) }atomic_dec(&table->counters_readers)
for iptables_update/replace (iptables -A|I|D|R|Z|F...)
writer doing a write_seqlock(&table->seqlock_rules), waiting one RCU grace period, {
change rules/counters
}write_sequnlock();
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
In reply to Eric DumazetQuoted 141 lines · Eric Dumazet
Quoted 4 lines · Stephen Hemminger
This is an alternative to earlier RCU/seqcount_t version of counters. The counters operate as usual without locking, but when counters are rotated around the CPU's entries. RCU is used in two ways, first to handle the counter rotation, second for replace.
Is it a working patch or just a prototype ?
Quoted 95 lines
Signed-off-by Stephen Hemminger <[email protected]>--- include/linux/netfilter/x_tables.h | 10 +++- net/ipv4/netfilter/arp_tables.c | 73 +++++++++++++++++++++++++++--------- net/ipv4/netfilter/ip_tables.c | 68 ++++++++++++++++++++++++--------- net/ipv6/netfilter/ip6_tables.c | 75 ++++++++++++++++++++++++++----------- net/netfilter/x_tables.c | 43 +++++++++++++++------ 5 files changed, 197 insertions(+), 72 deletions(-)include/linux/netfilter/x_tables.h +8
-2@@ -353,7 +353,7 @@ struct xt_tableunsigned 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_infounsigned 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) \net/ipv4/netfilter/ip_tables.c +20
-9@@ -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 ;@@ -892,45 +894,73 @@ set_entry_to_counter(const struct ipt_enreturn 0 ; } +static inline int +set_counter_to_entry (struct ipt_entry *e, +const struct ipt_counters total[], +unsigned int *i) +{ +SET_COUNTER (e->counters, total[*i].bcnt, total[*i].pcnt); + + (*i)++; +return 0 ; +} + +static void -get_counters (const struct xt_table_info *t, +get_counters (struct xt_table_info *t,struct xt_counters counters[]) {unsigned int cpu;unsigned int i;unsigned int curcpu; +struct ipt_entry *e; -/* Instead of clearing (by a previous call to memset()) -* the counters and using adds, we set the counters -* with data used by 'current' CPU -* We dont care about preemption here. net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 924
Quoted 10 lines
net/ipv4/netfilter/ip_tables.c +3
-3-*/ +preempt_disable (); curcpu =raw_smp_processor_id (); - + e = t->entries[curcpu]; i =0 ; - IPT_ENTRY_ITERATE(t->entries[curcpu], + IPT_ENTRY_ITERATE(e, t->size, set_entry_to_counter,Hum, current cpu might be interrupted by NIC, since you only disabled preemption.
set_entry_to_counter()might get garbage.
I suppose I already mentioned it :)net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 935
Quoted 11 lines
net/ipv4/netfilter/ip_tables.c +5
-0counters, &i);for_each_possible_cpu (cpu) { +void *p; +if (cpu == curcpu)continue ; + +/* Swizzle the values and wait */ + e->counters = ((struct xt_counters ) {0 ,0 });I dont see what you want to do here...
e->countersis the counter associated with rule #0net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 938
Quoted 3 lines
net/ipv4/netfilter/ip_tables.c +3
-0+ p = t->entries[cpu]; +rcu_assign_pointer (t->entries[cpu], e); +synchronize_net ();Oh well, not this
synchronize_net():)
Quoted 2 lines
This wont provide atomic sampling of counters for whole CPUS, and introduce large delays on big machines (
NR_CPUS>= 64)
Why would this not provide the moral equivalent of atomic sampling? The code above switches to another counter set, and waits for a grace period. Shouldn't this mean that all CPUs that were incrementing the old set of counters have finished doing so, so that the aggregate count covers all CPUs that started their increments before the pointer switch? Same as acquiring a write lock, which would wait for all CPUs that started their increments before starting the write-lock acquisition. CPUs that started their increments after starting the write acquisition would not be accounted for in the total, same as the RCU approach.
Steve's approach does delay reading out the counters, but it avoids delaying any CPU trying to increment the counters.
So what am I missing here?
Thanx, Paul
Quoted 48 lines
What problem do we want to solve here ?
Current iptables is able to do an atomic snapshot because of the rwlock.
If we really want to keep this feature (but get rid of rwlock), we might do the reverse with two seqlocks + RCU
One seqlock (
seqlock_counters) to protect counter updates One seqlock (seqlock_rules) to protect rules changesIe :
ipt_do_table()doing :
{rcu_read_lockread_seqbegin(&table->seqlock_rules);
rcu fetch priv table pointer and work on it
do {
for all counters updates, usedo { seq = read_seqbegin(table->seqlock_counters); update counters }} while (!hotdrop);
rcu_read_unlock()
}for
get_counter()(iptables -L)
writer doing awrite_seqlock(&table->seqlock_counters), waiting one RCU grace period, {
get / sum all counters (no updates of counters are allowed)
}write_sequnlock();for iptables_update/replace (iptables -A|I|D|R|Z|F...)
writer doing awrite_seqlock(&table->seqlock_rules), waiting one RCU grace period, {
change rules/counters
}write_sequnlock();--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
Quoted 151 lines · Paul E. McKenney
Quoted 131 lines · Eric Dumazet
Quoted 4 lines · Stephen Hemminger
This is an alternative to earlier RCU/seqcount_t version of counters. The counters operate as usual without locking, but when counters are rotated around the CPU's entries. RCU is used in two ways, first to handle the counter rotation, second for replace.
Is it a working patch or just a prototype ?
Quoted 95 lines
Signed-off-by Stephen Hemminger <[email protected]>--- include/linux/netfilter/x_tables.h | 10 +++- net/ipv4/netfilter/arp_tables.c | 73 +++++++++++++++++++++++++++--------- net/ipv4/netfilter/ip_tables.c | 68 ++++++++++++++++++++++++--------- net/ipv6/netfilter/ip6_tables.c | 75 ++++++++++++++++++++++++++----------- net/netfilter/x_tables.c | 43 +++++++++++++++------ 5 files changed, 197 insertions(+), 72 deletions(-)include/linux/netfilter/x_tables.h +8
-2@@ -353,7 +353,7 @@ struct xt_tableunsigned 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_infounsigned 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) \net/ipv4/netfilter/ip_tables.c +20
-9@@ -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 ;@@ -892,45 +894,73 @@ set_entry_to_counter(const struct ipt_enreturn 0 ; } +static inline int +set_counter_to_entry (struct ipt_entry *e, +const struct ipt_counters total[], +unsigned int *i) +{ +SET_COUNTER (e->counters, total[*i].bcnt, total[*i].pcnt); + + (*i)++; +return 0 ; +} + +static void -get_counters (const struct xt_table_info *t, +get_counters (struct xt_table_info *t,struct xt_counters counters[]) {unsigned int cpu;unsigned int i;unsigned int curcpu; +struct ipt_entry *e; -/* Instead of clearing (by a previous call to memset()) -* the counters and using adds, we set the counters -* with data used by 'current' CPU -* We dont care about preemption here. net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 924
Quoted 10 lines
net/ipv4/netfilter/ip_tables.c +3
-3-*/ +preempt_disable (); curcpu =raw_smp_processor_id (); - + e = t->entries[curcpu]; i =0 ; - IPT_ENTRY_ITERATE(t->entries[curcpu], + IPT_ENTRY_ITERATE(e, t->size, set_entry_to_counter,Hum, current cpu might be interrupted by NIC, since you only disabled preemption.
set_entry_to_counter()might get garbage.
I suppose I already mentioned it :)net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 935
Quoted 11 lines
net/ipv4/netfilter/ip_tables.c +5
-0counters, &i);for_each_possible_cpu (cpu) { +void *p; +if (cpu == curcpu)continue ; + +/* Swizzle the values and wait */ + e->counters = ((struct xt_counters ) {0 ,0 });I dont see what you want to do here...
e->countersis the counter associated with rule #0Quoted 8 lines
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 938
Quoted 3 lines
net/ipv4/netfilter/ip_tables.c +3
-0+ p = t->entries[cpu]; +rcu_assign_pointer (t->entries[cpu], e); +synchronize_net ();Oh well, not this
synchronize_net():)This wont provide atomic sampling of counters for whole CPUS, and introduce large delays on big machines (
NR_CPUS>= 64)Why would this not provide the moral equivalent of atomic sampling? The code above switches to another counter set, and waits for a grace period. Shouldn't this mean that all CPUs that were incrementing the old set of counters have finished doing so, so that the aggregate count covers all CPUs that started their increments before the pointer switch? Same as acquiring a write lock, which would wait for all CPUs that started their increments before starting the write-lock acquisition. CPUs that started their increments after starting the write acquisition would not be accounted for in the total, same as the RCU approach.
Quoted 2 lines
Steve's approach does delay reading out the counters, but it avoids delaying any CPU trying to increment the counters.
I see your point, but this is not what Stephen implemented.
So.. CPU will increments which counters, if not delayed ?
How counters will be synced again after our 'iptables -L' finished ?
"iptable -L" is not supposed to miss some counters updates (only some packets
might be droped at NIC level because we spend time in the collection).
If packets matches some rules, we really want up2date counters.
Maybe we need for this collection an extra "cpu", to collect all increments that were done when CPUs where directed to a "secondary table/counters"
Quoted 3 lines
So what am I missing here?
Well, I saw one synchronize_net() inside the for_each_possible_cpu(cpu) loop. Say we have NR_CPUS=4096, how long will it takes to perform "iptables -L" ?
General/intuitive idea would be :
switch pointers to a newly allocated table (and zeroed counters) wait one RCU grace period
collect/sum all counters of "old" table + (all cpus) into user provided table restore previous table
wait one RCU grace perioddisable_bh()
collect/sum all counters of "new and temporary" table (all cpus) and reinject them into local cpu table (this cpu should not be interrupted) enable_bh()
This way, "iptables -L" is not too expensive and doesnt block packet processing at all.
Thanks Paul
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
Quoted 10 lines
Quoted 10 lines
Quoted 10 lines
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 924
Quoted 7 lines
net/ipv4/netfilter/ip_tables.c +2
-1+ e = t->entries[curcpu]; i =0 ; - IPT_ENTRY_ITERATE(t->entries[curcpu], + IPT_ENTRY_ITERATE(e, t->size, set_entry_to_counter,Hum, current cpu might be interrupted by NIC, since you only disabled preemption.
set_entry_to_counter()might get garbage.
I suppose I already mentioned it :)
Need to change preempt_disable to local_bh_disable.
Quoted 15 lines
Quoted 15 lines
Quoted 15 lines
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 935
Quoted 11 lines
net/ipv4/netfilter/ip_tables.c +5
-0counters, &i);for_each_possible_cpu (cpu) { +void *p; +if (cpu == curcpu)continue ; + +/* Swizzle the values and wait */ + e->counters = ((struct xt_counters ) {0 ,0 });I dont see what you want to do here...
e->countersis the counter associated with rule #0
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 938
Quoted 3 lines
net/ipv4/netfilter/ip_tables.c +3
-0+ p = t->entries[cpu]; +rcu_assign_pointer (t->entries[cpu], e); +synchronize_net ();Oh well, not this
synchronize_net():)This wont provide atomic sampling of counters for whole CPUS, and introduce large delays on big machines (
NR_CPUS>= 64)
For large number of CPU's it would be possible to allocate
a full set of ncpu-1 new counters, then swap them in and then do one synchronize net. Or instead of synchronize_net, maybe a "wait for CPU #n" to go through grace period.
Quoted 10 lines
Quoted 10 lines
Why would this not provide the moral equivalent of atomic sampling? The code above switches to another counter set, and waits for a grace period. Shouldn't this mean that all CPUs that were incrementing the old set of counters have finished doing so, so that the aggregate count covers all CPUs that started their increments before the pointer switch? Same as acquiring a write lock, which would wait for all CPUs that started their increments before starting the write-lock acquisition. CPUs that started their increments after starting the write acquisition would not be accounted for in the total, same as the RCU approach.
Quoted 6 lines
Quoted 2 lines
Steve's approach does delay reading out the counters, but it avoids delaying any CPU trying to increment the counters.
I see your point, but this is not what Stephen implemented.
So.. CPU will increments which counters, if not delayed ?
The concept is that only the sum of all the counters matters, not which CPU has the count.
Quoted 31 lines
How counters will be synced again after our 'iptables -L' finished ?
"iptable -L" is not supposed to miss some counters updates (only some packets
might be droped at NIC level because we spend time in the collection).
If packets matches some rules, we really want up2date counters.Maybe we need for this collection an extra "cpu", to collect all increments that were done when CPUs where directed to a "secondary table/counters"
Quoted 3 lines
So what am I missing here?
Well, I saw one
synchronize_net()inside thefor_each_possible_cpu(cpu)loop. Say we have NR_CPUS=4096, how long will it takes to perform "iptables -L" ?General/intuitive idea would be :
switch pointers to a newly allocated table (and zeroed counters) wait one RCU grace period
collect/sum all counters of "old" table + (all cpus) into user provided table restore previous table
wait one RCU grace perioddisable_bh()
collect/sum all counters of "new and temporary" table (all cpus) and reinject them into local cpu table (this cpu should not be interrupted)enable_bh()
Quoted 1 line
This way, "iptables -L" is not too expensive and doesnt block packet processing at all.
Pretty much what I said.
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
Quoted 13 lines · Stephen Hemminger
Quoted 13 lines
General/intuitive idea would be :
switch pointers to a newly allocated table (and zeroed counters) wait one RCU grace period
collect/sum all counters of "old" table + (all cpus) into user provided table restore previous table
wait one RCU grace perioddisable_bh()
collect/sum all counters of "new and temporary" table (all cpus) and reinject them into local cpu table (this cpu should not be interrupted)enable_bh()
Quoted 3 lines
Quoted 1 line
This way, "iptables -L" is not too expensive and doesnt block packet processing at all.
Pretty much what I said.
Cool then, sorry for misunderstanding your patch.
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
In reply to Eric DumazetQuoted 152 lines · Eric Dumazet
Quoted 151 lines · Paul E. McKenney
Quoted 131 lines · Eric Dumazet
Quoted 4 lines · Stephen Hemminger
This is an alternative to earlier RCU/seqcount_t version of counters. The counters operate as usual without locking, but when counters are rotated around the CPU's entries. RCU is used in two ways, first to handle the counter rotation, second for replace.
Is it a working patch or just a prototype ?
Quoted 95 lines
Signed-off-by Stephen Hemminger <[email protected]>--- include/linux/netfilter/x_tables.h | 10 +++- net/ipv4/netfilter/arp_tables.c | 73 +++++++++++++++++++++++++++--------- net/ipv4/netfilter/ip_tables.c | 68 ++++++++++++++++++++++++--------- net/ipv6/netfilter/ip6_tables.c | 75 ++++++++++++++++++++++++++----------- net/netfilter/x_tables.c | 43 +++++++++++++++------ 5 files changed, 197 insertions(+), 72 deletions(-)include/linux/netfilter/x_tables.h +8
-2@@ -353,7 +353,7 @@ struct xt_tableunsigned 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_infounsigned 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) \net/ipv4/netfilter/ip_tables.c +20
-9@@ -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 ;@@ -892,45 +894,73 @@ set_entry_to_counter(const struct ipt_enreturn 0 ; } +static inline int +set_counter_to_entry (struct ipt_entry *e, +const struct ipt_counters total[], +unsigned int *i) +{ +SET_COUNTER (e->counters, total[*i].bcnt, total[*i].pcnt); + + (*i)++; +return 0 ; +} + +static void -get_counters (const struct xt_table_info *t, +get_counters (struct xt_table_info *t,struct xt_counters counters[]) {unsigned int cpu;unsigned int i;unsigned int curcpu; +struct ipt_entry *e; -/* Instead of clearing (by a previous call to memset()) -* the counters and using adds, we set the counters -* with data used by 'current' CPU -* We dont care about preemption here. net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 924
Quoted 10 lines
net/ipv4/netfilter/ip_tables.c +3
-3-*/ +preempt_disable (); curcpu =raw_smp_processor_id (); - + e = t->entries[curcpu]; i =0 ; - IPT_ENTRY_ITERATE(t->entries[curcpu], + IPT_ENTRY_ITERATE(e, t->size, set_entry_to_counter,Hum, current cpu might be interrupted by NIC, since you only disabled preemption.
set_entry_to_counter()might get garbage.
I suppose I already mentioned it :)net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 935
Quoted 11 lines
net/ipv4/netfilter/ip_tables.c +5
-0counters, &i);for_each_possible_cpu (cpu) { +void *p; +if (cpu == curcpu)continue ; + +/* Swizzle the values and wait */ + e->counters = ((struct xt_counters ) {0 ,0 });I dont see what you want to do here...
e->countersis the counter associated with rule #0Quoted 8 lines
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 938
Quoted 3 lines
net/ipv4/netfilter/ip_tables.c +3
-0+ p = t->entries[cpu]; +rcu_assign_pointer (t->entries[cpu], e); +synchronize_net ();Oh well, not this
synchronize_net():)This wont provide atomic sampling of counters for whole CPUS, and introduce large delays on big machines (
NR_CPUS>= 64)Why would this not provide the moral equivalent of atomic sampling? The code above switches to another counter set, and waits for a grace period. Shouldn't this mean that all CPUs that were incrementing the old set of counters have finished doing so, so that the aggregate count covers all CPUs that started their increments before the pointer switch? Same as acquiring a write lock, which would wait for all CPUs that started their increments before starting the write-lock acquisition. CPUs that started their increments after starting the write acquisition would not be accounted for in the total, same as the RCU approach.
Quoted 6 lines
Quoted 2 lines
Steve's approach does delay reading out the counters, but it avoids delaying any CPU trying to increment the counters.
I see your point, but this is not what Stephen implemented.
So.. CPU will increments which counters, if not delayed ?
The new set installed by the rcu_assign_pointer().
Quoted 1 line
How counters will be synced again after our 'iptables -L' finished ?
The usual approach would be to have three sets of counters, one currently being incremented, one just removed from service, and the last one holding the cumulative value. After a synchronize_net() following removing a set from service, you add in the values in the previous set removed from service. Then you keep the new set for the next 'iptables -L'.
Quoted 3 lines
"iptable -L" is not supposed to miss some counters updates (only some packets
might be droped at NIC level because we spend time in the collection).
If packets matches some rules, we really want up2date counters.
No counter updates would be lost using the above method.
Quoted 3 lines
Maybe we need for this collection an extra "cpu", to collect all increments that were done when CPUs where directed to a "secondary table/counters"
It should be easier to maintain a third set of counters that hold the accumulated counts from the earlier instances of 'iptables -L'.
Quoted 4 lines
Quoted 1 line
So what am I missing here?
Well, I saw one
synchronize_net()inside thefor_each_possible_cpu(cpu)loop. Say we have NR_CPUS=4096, how long will it takes to perform "iptables -L" ?
Good point, the for_each_possible_cpu() was cut out -- I should have gone back and looked at the original patch.
Seems like it should be possible to do a single synchronize_net() after swizzling all the counters...
Quoted 12 lines
General/intuitive idea would be :
switch pointers to a newly allocated table (and zeroed counters) wait one RCU grace period
collect/sum all counters of "old" table + (all cpus) into user provided table restore previous table
wait one RCU grace perioddisable_bh()
collect/sum all counters of "new and temporary" table (all cpus) and reinject them into local cpu table (this cpu should not be interrupted)enable_bh()
Quoted 1 line
This way, "iptables -L" is not too expensive and doesnt block packet processing at all.
My thought would be:
o acquire some sort of mutex.
o switch counters to newly allocated (and zeroed) table (T1).
The old table being switched out is T2.
o wait one RCU grace period.
o Sum T2 into a single global counter (G).
o Free T2.
o Copy G to a local variable.
o release the mutex.
o Return the value of the local variable.
Then you can repeat, allocating a new table again and using the new value of G.
Which may well be what you are saying above,
Thanx, Paul
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
Quoted 223 lines · On Tue, 3 Feb 2009 13:10:00 -0800 "Paul E. McKenney"…
Quoted 152 lines · Eric Dumazet
Quoted 151 lines · Paul E. McKenney
Quoted 131 lines · Eric Dumazet
Quoted 4 lines · Stephen Hemminger
This is an alternative to earlier RCU/seqcount_t version of counters. The counters operate as usual without locking, but when counters are rotated around the CPU's entries. RCU is used in two ways, first to handle the counter rotation, second for replace.
Is it a working patch or just a prototype ?
Quoted 95 lines
Signed-off-by Stephen Hemminger <[email protected]>--- include/linux/netfilter/x_tables.h | 10 +++- net/ipv4/netfilter/arp_tables.c | 73 +++++++++++++++++++++++++++--------- net/ipv4/netfilter/ip_tables.c | 68 ++++++++++++++++++++++++--------- net/ipv6/netfilter/ip6_tables.c | 75 ++++++++++++++++++++++++++----------- net/netfilter/x_tables.c | 43 +++++++++++++++------ 5 files changed, 197 insertions(+), 72 deletions(-)include/linux/netfilter/x_tables.h +8
-2@@ -353,7 +353,7 @@ struct xt_tableunsigned 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_infounsigned 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) \net/ipv4/netfilter/ip_tables.c +20
-9@@ -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 ;@@ -892,45 +894,73 @@ set_entry_to_counter(const struct ipt_enreturn 0 ; } +static inline int +set_counter_to_entry (struct ipt_entry *e, +const struct ipt_counters total[], +unsigned int *i) +{ +SET_COUNTER (e->counters, total[*i].bcnt, total[*i].pcnt); + + (*i)++; +return 0 ; +} + +static void -get_counters (const struct xt_table_info *t, +get_counters (struct xt_table_info *t,struct xt_counters counters[]) {unsigned int cpu;unsigned int i;unsigned int curcpu; +struct ipt_entry *e; -/* Instead of clearing (by a previous call to memset()) -* the counters and using adds, we set the counters -* with data used by 'current' CPU -* We dont care about preemption here. net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 924
Quoted 10 lines
net/ipv4/netfilter/ip_tables.c +3
-3-*/ +preempt_disable (); curcpu =raw_smp_processor_id (); - + e = t->entries[curcpu]; i =0 ; - IPT_ENTRY_ITERATE(t->entries[curcpu], + IPT_ENTRY_ITERATE(e, t->size, set_entry_to_counter,Hum, current cpu might be interrupted by NIC, since you only disabled preemption.
set_entry_to_counter()might get garbage.
I suppose I already mentioned it :)net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 935
Quoted 11 lines
net/ipv4/netfilter/ip_tables.c +5
-0counters, &i);for_each_possible_cpu (cpu) { +void *p; +if (cpu == curcpu)continue ; + +/* Swizzle the values and wait */ + e->counters = ((struct xt_counters ) {0 ,0 });I dont see what you want to do here...
e->countersis the counter associated with rule #0Quoted 8 lines
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 938
Quoted 3 lines
net/ipv4/netfilter/ip_tables.c +3
-0+ p = t->entries[cpu]; +rcu_assign_pointer (t->entries[cpu], e); +synchronize_net ();Oh well, not this
synchronize_net():)This wont provide atomic sampling of counters for whole CPUS, and introduce large delays on big machines (
NR_CPUS>= 64)Why would this not provide the moral equivalent of atomic sampling? The code above switches to another counter set, and waits for a grace period. Shouldn't this mean that all CPUs that were incrementing the old set of counters have finished doing so, so that the aggregate count covers all CPUs that started their increments before the pointer switch? Same as acquiring a write lock, which would wait for all CPUs that started their increments before starting the write-lock acquisition. CPUs that started their increments after starting the write acquisition would not be accounted for in the total, same as the RCU approach.
Quoted 6 lines
Quoted 2 lines
Steve's approach does delay reading out the counters, but it avoids delaying any CPU trying to increment the counters.
I see your point, but this is not what Stephen implemented.
So.. CPU will increments which counters, if not delayed ?
The new set installed by the
rcu_assign_pointer().Quoted 1 line
How counters will be synced again after our 'iptables -L' finished ?
The usual approach would be to have three sets of counters, one currently being incremented, one just removed from service, and the last one holding the cumulative value. After a
synchronize_net()following removing a set from service, you add in the values in the previous set removed from service. Then you keep the new set for the next 'iptables -L'.Quoted 3 lines
"iptable -L" is not supposed to miss some counters updates (only some packets
might be droped at NIC level because we spend time in the collection).
If packets matches some rules, we really want up2date counters.No counter updates would be lost using the above method.
Quoted 3 lines
Maybe we need for this collection an extra "cpu", to collect all increments that were done when CPUs where directed to a "secondary table/counters"
It should be easier to maintain a third set of counters that hold the accumulated counts from the earlier instances of 'iptables -L'.
Quoted 4 lines
Quoted 1 line
So what am I missing here?
Well, I saw one
synchronize_net()inside thefor_each_possible_cpu(cpu)loop. Say we have NR_CPUS=4096, how long will it takes to perform "iptables -L" ?Good point, the
for_each_possible_cpu()was cut out -- I should have gone back and looked at the original patch.Seems like it should be possible to do a single
synchronize_net()after swizzling all the counters...Quoted 12 lines
General/intuitive idea would be :
switch pointers to a newly allocated table (and zeroed counters) wait one RCU grace period
collect/sum all counters of "old" table + (all cpus) into user provided table restore previous table
wait one RCU grace perioddisable_bh()
collect/sum all counters of "new and temporary" table (all cpus) and reinject them into local cpu table (this cpu should not be interrupted)enable_bh()Quoted 1 line
This way, "iptables -L" is not too expensive and doesnt block packet processing at all.
My thought would be:
o acquire some sort of mutex.
o switch counters to newly allocated (and zeroed) table (T1).
The old table being switched out is T2.o wait one RCU grace period.
o Sum T2 into a single global counter (G).
o Free T2.
o Copy G to a local variable.
Quoted 9 lines
o release the mutex.
o Return the value of the local variable.
Then you can repeat, allocating a new table again and using the new value of G.
Which may well be what you are saying above,
I was using the current CPU counter as the global counter G.
Quoted 1 line
Thanx, Paul
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
So, is this patch stream at a point where I should try running the 32-core netperf tests against it? And if so, against which tree should I try applying patches?
rick jones
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
In reply to Stephen HemmingerQuoted 230 lines · Stephen Hemminger
Quoted 227 lines · On Tue, 3 Feb 2009 13:10:00 -0800 "Paul E. McKenney"…
Quoted 152 lines · Eric Dumazet
Quoted 151 lines · Paul E. McKenney
Quoted 131 lines · Eric Dumazet
Quoted 4 lines · Stephen Hemminger
This is an alternative to earlier RCU/seqcount_t version of counters. The counters operate as usual without locking, but when counters are rotated around the CPU's entries. RCU is used in two ways, first to handle the counter rotation, second for replace.
Is it a working patch or just a prototype ?
Quoted 95 lines
Signed-off-by Stephen Hemminger <[email protected]>--- include/linux/netfilter/x_tables.h | 10 +++- net/ipv4/netfilter/arp_tables.c | 73 +++++++++++++++++++++++++++--------- net/ipv4/netfilter/ip_tables.c | 68 ++++++++++++++++++++++++--------- net/ipv6/netfilter/ip6_tables.c | 75 ++++++++++++++++++++++++++----------- net/netfilter/x_tables.c | 43 +++++++++++++++------ 5 files changed, 197 insertions(+), 72 deletions(-)include/linux/netfilter/x_tables.h +8
-2@@ -353,7 +353,7 @@ struct xt_tableunsigned 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_infounsigned 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) \net/ipv4/netfilter/ip_tables.c +20
-9@@ -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 ;@@ -892,45 +894,73 @@ set_entry_to_counter(const struct ipt_enreturn 0 ; } +static inline int +set_counter_to_entry (struct ipt_entry *e, +const struct ipt_counters total[], +unsigned int *i) +{ +SET_COUNTER (e->counters, total[*i].bcnt, total[*i].pcnt); + + (*i)++; +return 0 ; +} + +static void -get_counters (const struct xt_table_info *t, +get_counters (struct xt_table_info *t,struct xt_counters counters[]) {unsigned int cpu;unsigned int i;unsigned int curcpu; +struct ipt_entry *e; -/* Instead of clearing (by a previous call to memset()) -* the counters and using adds, we set the counters -* with data used by 'current' CPU -* We dont care about preemption here. net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 924
Quoted 10 lines
net/ipv4/netfilter/ip_tables.c +3
-3-*/ +preempt_disable (); curcpu =raw_smp_processor_id (); - + e = t->entries[curcpu]; i =0 ; - IPT_ENTRY_ITERATE(t->entries[curcpu], + IPT_ENTRY_ITERATE(e, t->size, set_entry_to_counter,Hum, current cpu might be interrupted by NIC, since you only disabled preemption.
set_entry_to_counter()might get garbage.
I suppose I already mentioned it :)net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 935
Quoted 11 lines
net/ipv4/netfilter/ip_tables.c +5
-0counters, &i);for_each_possible_cpu (cpu) { +void *p; +if (cpu == curcpu)continue ; + +/* Swizzle the values and wait */ + e->counters = ((struct xt_counters ) {0 ,0 });I dont see what you want to do here...
e->countersis the counter associated with rule #0Quoted 8 lines
net/ipv4/netfilter/ip_tables.c set_entry_to_counter(const struct ipt_en · line 938
Quoted 3 lines
net/ipv4/netfilter/ip_tables.c +3
-0+ p = t->entries[cpu]; +rcu_assign_pointer (t->entries[cpu], e); +synchronize_net ();Oh well, not this
synchronize_net():)This wont provide atomic sampling of counters for whole CPUS, and introduce large delays on big machines (
NR_CPUS>= 64)Why would this not provide the moral equivalent of atomic sampling? The code above switches to another counter set, and waits for a grace period. Shouldn't this mean that all CPUs that were incrementing the old set of counters have finished doing so, so that the aggregate count covers all CPUs that started their increments before the pointer switch? Same as acquiring a write lock, which would wait for all CPUs that started their increments before starting the write-lock acquisition. CPUs that started their increments after starting the write acquisition would not be accounted for in the total, same as the RCU approach.
Quoted 6 lines
Quoted 2 lines
Steve's approach does delay reading out the counters, but it avoids delaying any CPU trying to increment the counters.
I see your point, but this is not what Stephen implemented.
So.. CPU will increments which counters, if not delayed ?
The new set installed by the
rcu_assign_pointer().Quoted 1 line
How counters will be synced again after our 'iptables -L' finished ?
The usual approach would be to have three sets of counters, one currently being incremented, one just removed from service, and the last one holding the cumulative value. After a
synchronize_net()following removing a set from service, you add in the values in the previous set removed from service. Then you keep the new set for the next 'iptables -L'.Quoted 3 lines
"iptable -L" is not supposed to miss some counters updates (only some packets
might be droped at NIC level because we spend time in the collection).
If packets matches some rules, we really want up2date counters.No counter updates would be lost using the above method.
Quoted 3 lines
Maybe we need for this collection an extra "cpu", to collect all increments that were done when CPUs where directed to a "secondary table/counters"
It should be easier to maintain a third set of counters that hold the accumulated counts from the earlier instances of 'iptables -L'.
Quoted 4 lines
Quoted 1 line
So what am I missing here?
Well, I saw one
synchronize_net()inside thefor_each_possible_cpu(cpu)loop. Say we have NR_CPUS=4096, how long will it takes to perform "iptables -L" ?Good point, the
for_each_possible_cpu()was cut out -- I should have gone back and looked at the original patch.Seems like it should be possible to do a single
synchronize_net()after swizzling all the counters...Quoted 12 lines
General/intuitive idea would be :
switch pointers to a newly allocated table (and zeroed counters) wait one RCU grace period
collect/sum all counters of "old" table + (all cpus) into user provided table restore previous table
wait one RCU grace perioddisable_bh()
collect/sum all counters of "new and temporary" table (all cpus) and reinject them into local cpu table (this cpu should not be interrupted)enable_bh()Quoted 1 line
This way, "iptables -L" is not too expensive and doesnt block packet processing at all.
My thought would be:
o acquire some sort of mutex.
o switch counters to newly allocated (and zeroed) table (T1).
The old table being switched out is T2.o wait one RCU grace period.
o Sum T2 into a single global counter (G).
o Free T2.
o Copy G to a local variable.
o release the mutex.
o Return the value of the local variable.
Quoted 7 lines
Quoted 5 lines
Then you can repeat, allocating a new table again and using the new value of G.
Which may well be what you are saying above,
I was using the current CPU counter as the global counter G.
Sounds good, then! ;-)
Thanx, Paul
Re: [PATCH 3/3] iptables: lock free counters (alternate version)
This is the "interesting bits" of what I am testing. What it does is swap in new counters, sum, then put counter values back onto the current cpu.
The replace case is easier since the counters are "old" at that point.
net/ipv4/netfilter/ip_tables.c +78 -32
@@ -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,62 @@ get_counters(const struct xt_table_info counters, &i); } + +} + +/* Swap existing counter entries with new zeroed ones */ +static void swap_counters (struct xt_table_info *o,struct xt_table_info *n) +{ +unsigned int cpu; + +for_each_possible_cpu (cpu) { +void *p = o->entries[cpu]; +memset (n->entries[cpu],0 , n->size); + +rcu_assign_pointer (o->entries[cpu], n->entries[cpu]); + n->entries[cpu] = p; + } + +/* Wait until smoke has cleared */ +synchronize_net (); +} + +/* 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 +990,26 @@ 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; -/* First, sum counters... */ -write_lock_bh (&table->lock); +mutex_lock (&table->lock); +swap_counters (private, tmp);get_counters (private, counters); -write_unlock_bh (&table->lock); +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
@@ -1242,7 +1305,9 @@ __do_replace(struct net *net, const charmodule_put (t->me);/* Get the old counters. */ +synchronize_net ();get_counters (oldinfo, counters); +/* Decrease module usage counts and free resource */ loc_cpu_old_entry = oldinfo->entries[raw_smp_processor_id ()]; IPT_ENTRY_ITERATE(loc_cpu_old_entry, oldinfo->size, cleanup_entry,
@@ -1312,27 +1377,6 @@ do_replace(struct net *net, void __userreturn 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 +1437,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 +1453,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:
PATCH 5/6 netfilter: use sequence number synchronization for counters
In reply to Stephen HemmingerChange how synchronization is done on the iptables counters. Use seqcount wrapper instead of depending on reader/writer lock.
net/netfilter/x_tables.c +20 -2
@@ -577,18 +577,36 @@ int xt_compat_target_to_user(struct xt_eEXPORT_SYMBOL_GPL (xt_compat_target_to_user);#endif +static DEFINE_PER_CPU(seqcount_t, xt_counter_sequence); + +/* Update the counters on the current CPU. preempt must be disabled. */ void xt_add_counter (struct xt_counters *c,unsigned b,unsigned p) { +seqcount_t *seq = &__get_cpu_var (xt_counter_sequence); + +write_seqcount_begin (seq); c->bcnt += b; c->pcnt += p; +write_seqcount_end (seq); }EXPORT_SYMBOL_GPL (xt_add_counter); +/* Fetch counters on other CPU. */ void xt_sum_counter (struct xt_counters *t,int cpu,const struct xt_counters *c) { - t->pcnt += c->pcnt; - t->bcnt += c->bcnt; +seqcount_t *seq = &per_cpu (xt_counter_sequence, cpu); +unsigned start; +struct xt_counters v; + +/* Atomic fetch of counter value */ +do { + start =read_seqcount_begin (seq); + v = *c; + }while (read_seqcount_retry (seq, start)); + + t->pcnt += v.pcnt; + t->bcnt += v.bcnt; }EXPORT_SYMBOL_GPL (xt_sum_counter);
PATCH 6/6 netfilter: convert x_tables to use RCU
In reply to Stephen HemmingerReplace 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 synchronization was fixed by the previous patch. But still need to make sure table info isn't going away.
--- include/linux/netfilter/x_tables.h | 10 ++++++-- net/ipv4/netfilter/arp_tables.c | 16 ++++++------- net/ipv4/netfilter/ip_tables.c | 27 +++++++++++----------- net/ipv6/netfilter/ip6_tables.c | 16 ++++++------- net/netfilter/x_tables.c | 45 ++++++++++++++++++++++++++----------- 5 files changed, 70 insertions(+), 44 deletions(-)
include/linux/netfilter/x_tables.h +8 -2
@@ -356,8 +356,8 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -rwlock_t lock; +/* Lock for curtain */ +spinlock_t lock;/* Man behind the curtain... */ struct xt_table_info *private;
@@ -387,6 +387,12 @@ struct xt_table_infounsigned 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 ];
net/ipv4/netfilter/arp_tables.c +8 -8
@@ -237,8 +237,8 @@ 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; +rcu_read_lock_bh (); + private =rcu_dereference (table->private); table_base = (void *)private->entries[smp_processor_id ()]; e =get_entry (table_base, private->hook_entry[hook]); back =get_entry (table_base, private->underflow[hook]);
@@ -311,7 +311,7 @@ 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 ;
@@ -733,9 +733,9 @@ static inline struct xt_counters *alloc_return ERR_PTR (-ENOMEM );/* First, sum counters... */ -write_lock_bh (&table->lock); +local_bh_enable ();get_counters (private, counters); -write_unlock_bh (&table->lock); +local_bh_disable ();return counters; }
@@ -1149,8 +1149,8 @@ static int do_add_counters(struct net *n goto free; } -write_lock_bh (&t->lock); - private = t->private; +rcu_read_lock_bh (); + private =rcu_dereference (t->private);if (private->number != num_counters) { ret = -EINVAL ; goto unlock_up_free;
@@ -1165,7 +1165,7 @@ static int do_add_counters(struct net *n paddc, &i); unlock_up_free: -write_unlock_bh (&t->lock); +rcu_read_unlock_bh ();xt_table_unlock (t);module_put (t->me); free:
net/ipv4/netfilter/ip_tables.c +14 -13
@@ -66,11 +66,12 @@ do { \#endif /* -We keep a set of rules for each CPU, so we can avoid write-locking -them in the softirq when updating the counters and therefore -only need to read-lock in the softirq; doing a write_lock_bh() in user -context stops packets coming through and allows user context to read -the counters or update the rules. +We keep a set of rules for each CPU, so we can avoid locking +them in the softirq when updating the counters. We use a sequence +counter to keep the counters consistent and RCU to prevent +handle counters during replace operation. When reading the +counters, need to have bottom half and preempt disabled to +get a consistent data. Hence the start of any table is given by get_table() below. */
@@ -347,9 +348,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]);
@@ -445,7 +446,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 ;
@@ -944,9 +945,9 @@ static struct xt_counters * alloc_countereturn ERR_PTR (-ENOMEM );/* First, sum counters... */ -write_lock_bh (&table->lock); +local_bh_disable ();get_counters (private, counters); -write_unlock_bh (&table->lock); +local_bh_enable ();return counters; }
@@ -1394,8 +1395,8 @@ do_add_counters(struct net *net, void __ goto free; } -write_lock_bh (&t->lock); - private = t->private; +rcu_read_lock_bh (); + private =rcu_dereference (t->private);if (private->number != num_counters) { ret = -EINVAL ; goto unlock_up_free;
@@ -1410,7 +1411,7 @@ do_add_counters(struct net *net, void __ paddc, &i); unlock_up_free: -write_unlock_bh (&t->lock); +rcu_read_unlock_bh ();xt_table_unlock (t);module_put (t->me); free:
net/ipv6/netfilter/ip6_tables.c +8 -8
@@ -373,9 +373,9 @@ ip6t_do_table(struct sk_buff *skb, mtpar.family = tgpar.family =NFPROTO_IPV6 ; 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]);
@@ -474,7 +474,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 ;
@@ -973,9 +973,9 @@ static struct xt_counters *alloc_counterreturn ERR_PTR (-ENOMEM );/* First, sum counters... */ -write_lock_bh (&table->lock); +local_bh_disable ();get_counters (private, counters); -write_unlock_bh (&table->lock); +local_bh_enable ();return counters; }
@@ -1425,8 +1425,8 @@ do_add_counters(struct net *net, void __ goto free; } -write_lock_bh (&t->lock); - private = t->private; +rcu_read_lock_bh (); + private =rcu_dereference (t->private);if (private->number != num_counters) { ret = -EINVAL ; goto unlock_up_free;
@@ -1441,7 +1441,7 @@ do_add_counters(struct net *net, void __ paddc, &i); unlock_up_free: -write_unlock_bh (&t->lock); +rcu_read_unlock_bh ();xt_table_unlock (t);module_put (t->me); free:
net/netfilter/x_tables.c +32 -13
77 lines not on this page · raw message
Re: [PATCH 6/6] netfilter: convert x_tables to use RCU
Quoted 18 lines · Stephen Hemminger
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_inforeference was not in process of being changed. Sincext_table_infois 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 synchronization was fixed by the previous patch. But still need to make sure table info isn't going away.
Signed-off-by Stephen Hemminger <[email protected]>
Quoted 7 lines
--- include/linux/netfilter/x_tables.h | 10 ++++++-- net/ipv4/netfilter/arp_tables.c | 16 ++++++------- net/ipv4/netfilter/ip_tables.c | 27 +++++++++++----------- net/ipv6/netfilter/ip6_tables.c | 16 ++++++------- net/netfilter/x_tables.c | 45 ++++++++++++++++++++++++++----------- 5 files changed, 70 insertions(+), 44 deletions(-)
OK, I have a last comment Stephen
(I tested your patches on my dev machine and got nice results)
In net/ipv4/netfilter/ip_tables.c,get_counters() can be quite slow on large firewalls, and it is called from alloc_counters() with BH disabled, but also from __do_replace() without BH disabled.
So get_counters() first iterates on set_entry_to_counter() for current cpu but might be interrupted and we get bad results...
Solution is to always use seqcount_t protection, and no BH disabling at all.
Then, I wonder if all this is valid, since alloc_counters() might be supposed to perform an atomic snapshots of all counters. This was possible because of a write_lock_bh(), but does it make any sense to block all packets for such a long time ??? If this is a strong requirement, I am afraid we have to make other changes...
--- net/ipv4/netfilter/ip_tables.c | 25 +++---------------------- 1 files changed, 3 insertions(+), 22 deletions(-)
net/ipv4/netfilter/ip_tables.c +3 -22
@@ -900,25 +900,8 @@ get_counters(const struct xt_table_info *t, {unsigned int cpu;unsigned int i; -unsigned int curcpu; - -/* Instead of clearing (by a previous call to memset()) -* the counters and using adds, we set the counters -* with data used by 'current' CPU -* We dont care about preemption here. -*/ - curcpu =raw_smp_processor_id (); - - i =0 ; -IPT_ENTRY_ITERATE (t->entries[curcpu], - t->size, - set_entry_to_counter, - counters, - &i);for_each_possible_cpu (cpu) { -if (cpu == curcpu) -continue ; i =0 ; IPT_ENTRY_ITERATE(t->entries[cpu], t->size,
@@ -939,15 +922,12 @@ static struct xt_counters * alloc_counters(struct xt_table *table)(other than comefrom, which userspace doesn't care about). */ countersize =sizeof (struct xt_counters ) * private->number; - counters =vmalloc_node (countersize,numa_node_id ()); + counters =__vmalloc (countersize,GFP_KERNEL | __GFP_ZERO,PAGE_KERNEL );if (counters ==NULL )return ERR_PTR (-ENOMEM ); -/* First, sum counters... */ -local_bh_disable ();get_counters (private, counters); -local_bh_enable ();return counters; }
@@ -1209,7 +1189,8 @@ __do_replace(struct net *net, const char *name, unsigned int valid_hooks,void *loc_cpu_old_entry; ret =0 ; - counters =vmalloc (num_counters *sizeof (struct xt_counters )); + counters =__vmalloc (num_counters *sizeof (struct xt_counters ), +GFP_KERNEL | __GFP_ZERO,PAGE_KERNEL );if (!counters) { ret = -ENOMEM ; goto out;