iptables very slow after commit784544739a25c30637397ace5489eeb6e15d7d49
Subsystems (4)
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Lai JiangshanQuoted 20 lines · On Tue, 21 Apr 2009 13:22:27 +0800 Lai Jiangshan <[email protected]> wrote:
Quoted 19 lines · Eric Dumazet
Quoted 17 lines · Lai Jiangshan
Quoted 4 lines · Stephen Hemminger
net/netfilter/x_tables.c +4
-0+/** +* xt_table_info_rdlock_bh - recursive read lock for xt table info +* +* Table processing calls this to hold off any changes to table net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 697
Quoted 10 lines
net/netfilter/x_tables.c +10
-0+* (on current CPU). Always leaves with bottom half disabled. +* If called recursively, then assumes bh/preempt already disabled. +*/ +void xt_info_rdlock_bh (void ) +{ +struct xt_info_lock *lock; + +preempt_disable (); + lock = &__get_cpu_var (xt_info_locks); +if (likely (++lock->depth ==0 ))Maybe I missed something. I think softirq may be still enabled here. So what happen when
xt_info_rdlock_bh()called recursively here?
Quoted 5 lines
Quoted 2 lines
well, first time its called, you are right softirqs are enabled until the point we call
spin_lock_bh(), right after this line :
xt_info_rdlock_bh()called recursively here will enter the critical region without &__get_cpu_var(xt_info_locks)->lock.
NO spin_lock_bh always does a preempt_disable
xt_info_rdlock_bh (depth = -1)
+1 preempt_disable
spin_lock_bh
+1 preempt_disable
-1 preempt_enable_no_resched
---
+1
Second call preempt_count=1 (depth = 0)
xt_info_rdlock_bh
+1 preempt_disable
-1 preempt_enable_no_resched
---
Result is preempt_count=1 (depth = 1)
Now lets do unlocks
xt_info_rdunlock_bh preempt_count=1 depth=1
does nothing
xt_info_rdunlock_bh preempt_count=1 depth = 0
-1 spin_unlock_bh
Resulting preempt_count=0 depth = -1
Same as starting point.
Quoted 9 lines
Because
xt_info_rdlock_bh()called recursively here seeslock->depth>= 0, and "++lock->depth == 0" is false.Quoted 6 lines
Quoted 4 lines
Review
Quoted 4 lines
(quoted diff) +2
-0+ spin_lock_bh(&lock->lock); + preempt_enable_no_resched();After this line, both softirqs and preempt are disabled.
No. spin_lock_bh on first pass does this.
Quoted 27 lines
Quoted 8 lines
Future calls to this function temporarly raise preemptcount and decrease it. (Null effect)
Quoted 5 lines
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 702
Quoted 3 lines
net/netfilter/x_tables.c +3
-0+} +EXPORT_SYMBOL_GPL (xt_info_rdlock_bh); +Is this OK for you:
Quoted 14 lines
Quoted 5 lines
void
xt_info_rdlock_bh(void){ struct xt_info_lock *lock; local_bh_disable();well, Stephen was trying to not change preempt count for the 2nd, 3rd, 4th?... invocation of this function. This is how I understood the code.
Quoted 5 lines
lock = &__get_cpu_var(xt_info_locks); if (likely(++lock->depth == 0)) spin_lock(&lock->lock); }Sorry for it.
Is this OK:void
xt_info_rdlock_bh(void)
Quoted 10 lines
{
struct xt_info_lock *lock;
local_bh_disable();
lock = &__get_cpu_var(xt_info_locks);
if (likely(++lock->depth == 0))
spin_lock(&lock->lock);
else
local_bh_enable();
}Unnecessary.
Quoted 4 lines
I did not think things carefully enough, and I do know nothing about ip/ip6/arp.
Lai
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 13 lines · Stephen Hemminger
Quoted 2 lines
xt_info_rdlock_bh()called recursively here will enter the critical region without &__get_cpu_var(xt_info_locks)->lock.NO
spin_lock_bhalways does apreempt_disable
xt_info_rdlock_bh(depth = -1)
+1preempt_disable
spin_lock_bh
+1preempt_disable
-1preempt_enable_no_resched
---
+1
Quoted 6 lines
Second call preempt_count=1 (depth = 0)
xt_info_rdlock_bh
+1preempt_disable
-1preempt_enable_no_resched
---
I think I had made you mistook my email.
The preempt_count is correct, but I thought about lock-save:
we must hold &__get_cpu_var(xt_info_locks)->lock when we enter the read-side critical region.
--------------------xt_info_rdlock_bh() (depth = -1)
preempt_disable()
depth++
==========>interrupt here
==========>
==========>xt_info_rdlock_bh() (depth = 0)
==========> preempt_disable() ==========> depth++ ==========> preempt_enable_no_resched()
==========>
==========>enter the read-side critical region *without* lock. ==========> it may get trashy data.
==========>
==========>xt_info_rdunlock_bh()
==========>
==========>interrupt return.
spin_lock_bh()
preempt_enable_no_resched()
enter the read-side critical region *with* lock.
xt_info_rdunlock_bh().
----------------------
So I asked:
Quoted 7 lines
+void
xt_info_rdlock_bh(void)net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 697
Quoted 6 lines
net/netfilter/x_tables.c +6
-0+{ +struct xt_info_lock *lock; + +preempt_disable (); + lock = &__get_cpu_var (xt_info_locks); +if (likely (++lock->depth ==0 ))
So what happen when xt_info_rdlock_bh() called recursively here?
Quoted 5 lines
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 702
Quoted 5 lines
net/netfilter/x_tables.c +5
-0+spin_lock_bh (&lock->lock); +preempt_enable_no_resched (); +} +EXPORT_SYMBOL_GPL (xt_info_rdlock_bh); +
----------
Is this OK? (Now I suppose we can enter the read-side critical region in irq context)
void xt_info_rdlock_bh(void)
{
unsigned long flags;
struct xt_info_lock *lock;
local_irq_save(flags);
lock = &__get_cpu_var(xt_info_locks);
if (likely(++lock->depth == 0))
spin_lock_bh(&lock->lock);
local_irq_restore(flags);
}Lai
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Hi.
Quoted 21 lines · Lai Jiangshan
Quoted 7 lines
+void
xt_info_rdlock_bh(void)net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 697
Quoted 6 lines
net/netfilter/x_tables.c +6
-0+{ +struct xt_info_lock *lock; + +preempt_disable (); + lock = &__get_cpu_var (xt_info_locks); +if (likely (++lock->depth ==0 ))So what happen when
xt_info_rdlock_bh()called recursively here?Quoted 5 lines
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 702
Quoted 5 lines
net/netfilter/x_tables.c +5
-0+spin_lock_bh (&lock->lock); +preempt_enable_no_resched (); +} +EXPORT_SYMBOL_GPL (xt_info_rdlock_bh); +----------
Is this OK? (Now I suppose we can enter the read-side critical region in irq context)void
xt_info_rdlock_bh(void)
Quoted 10 lines
{
unsigned long flags;
struct xt_info_lock *lock;
local_irq_save(flags);
lock = &__get_cpu_var(xt_info_locks);
if (likely(++lock->depth == 0))
spin_lock_bh(&lock->lock);
local_irq_restore(flags);
}Netfilter as long as other generic network pathes are never accessed from interrupt context, but your analysis looks right for the softirq case.
Stephen, should preempt_disable() be replaced with local_bh_disable() to prevent softirq to race on the same cpu for the lock's depth field? Or can it be made atomic?
Signature · 1 line
Evgeniy Polyakov
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 5 lines · Evgeniy Polyakov
Netfilter as long as other generic network pathes are never accessed from interrupt context, but your analysis looks right for the softirq case.
A question:
softirq is always not nesting. Why we need recursive lock?
Lai.
David Miller
maintainerRe: [PATCH] netfilter: use per-cpu recursive lock (v11)
From: Lai Jiangshan <[email protected]>
Date: Tue, 21 Apr 2009 16:42:40 +0800
Quoted 1 line
softirq is always not nesting. Why we need recursive lock?
Netfilter itself, is nesting.
When using bridging netfilter, iptables can be entered twice in the same call chain.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Evgeniy PolyakovQuoted 33 lines · Evgeniy Polyakov
Hi.
Quoted 19 lines · Lai Jiangshan
Quoted 7 lines
+void
xt_info_rdlock_bh(void)Review
Quoted 6 lines
(quoted diff) +6
-0+{ + struct xt_info_lock *lock; + + preempt_disable(); + lock = &__get_cpu_var(xt_info_locks); + if (likely(++lock->depth == 0))So what happen when
xt_info_rdlock_bh()called recursively here?Quoted 5 lines
Review
Quoted 5 lines
(quoted diff) +5
-0+ spin_lock_bh(&lock->lock); + preempt_enable_no_resched(); +} +EXPORT_SYMBOL_GPL(xt_info_rdlock_bh); +----------
Is this OK? (Now I suppose we can enter the read-side critical region in irq context)void
xt_info_rdlock_bh(void)Quoted 10 lines
{ unsigned long flags; struct xt_info_lock *lock; local_irq_save(flags); lock = &__get_cpu_var(xt_info_locks); if (likely(++lock->depth == 0)) spin_lock_bh(&lock->lock); local_irq_restore(flags); }
Quoted 8 lines
Netfilter as long as other generic network pathes are never accessed from interrupt context, but your analysis looks right for the softirq case.
Stephen, should
preempt_disable()be replaced withlocal_bh_disable()to prevent softirq to race on the same cpu for the lock's depth field? Or can it be made atomic?
Maybe just dont care about calling several time local_bh_disable() (since we were doing this in previous kernels anyway, we used to call read_lock_bh())
This shortens fastpath, is faster than local_irq_save()/local_irq_restore(), and looks better.
void xt_info_rdlock_bh(void)
{
struct xt_info_lock *lock;
local_bh_disable(); lock = &__get_cpu_var(xt_info_locks);
if (likely(++lock->depth == 0))
spin_lock(&lock->lock);
}
void xt_info_rdunlock_bh(void)
{
struct xt_info_lock *lock = &__get_cpu_var(xt_info_locks);
BUG_ON(lock->depth < 0);
if (likely(--lock->depth < 0))
spin_unlock(&lock->lock);
local_bh_enable();
}Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 5 lines · Eric Dumazet
Maybe just dont care about calling several time
local_bh_disable()(since we were doing this in previous kernels anyway, we used to callread_lock_bh())This shortens fastpath, is faster than local_irq_save()/local_irq_restore(), and looks better.
Yeah, given that non-nested locking is more likely condition, it will be even faster than preemption case.
Quoted 21 lines
void
xt_info_rdlock_bh(void){ struct xt_info_lock *lock; local_bh_disable();(quoted diff) +0
-0lock = &__get_cpu_var(xt_info_locks); if (likely(++lock->depth == 0)) spin_lock(&lock->lock);}
void
xt_info_rdunlock_bh(void){ struct xt_info_lock *lock = &__get_cpu_var(xt_info_locks); BUG_ON(lock->depth < 0); if (likely(--lock->depth < 0)) spin_unlock(&lock->lock); local_bh_enable(); }
Signature · 1 line
Evgeniy Polyakov
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Eric DumazetQuoted 57 lines · Eric Dumazet
Quoted 32 lines · Evgeniy Polyakov
Hi.
Quoted 19 lines · Lai Jiangshan
Quoted 7 lines
+void
xt_info_rdlock_bh(void)Review
Quoted 6 lines
(quoted diff) +6
-0+{ + struct xt_info_lock *lock; + + preempt_disable(); + lock = &__get_cpu_var(xt_info_locks); + if (likely(++lock->depth == 0))So what happen when
xt_info_rdlock_bh()called recursively here?Quoted 5 lines
Review
Quoted 5 lines
(quoted diff) +5
-0+ spin_lock_bh(&lock->lock); + preempt_enable_no_resched(); +} +EXPORT_SYMBOL_GPL(xt_info_rdlock_bh); +----------
Is this OK? (Now I suppose we can enter the read-side critical region in irq context)void
xt_info_rdlock_bh(void)Quoted 10 lines
{ unsigned long flags; struct xt_info_lock *lock; local_irq_save(flags); lock = &__get_cpu_var(xt_info_locks); if (likely(++lock->depth == 0)) spin_lock_bh(&lock->lock); local_irq_restore(flags); }Quoted 8 lines
Netfilter as long as other generic network pathes are never accessed from interrupt context, but your analysis looks right for the softirq case.
Stephen, should
preempt_disable()be replaced withlocal_bh_disable()to prevent softirq to race on the same cpu for the lock's depth field? Or can it be made atomic?Maybe just dont care about calling several time
local_bh_disable()(since we were doing this in previous kernels anyway, we used to callread_lock_bh())This shortens fastpath, is faster than local_irq_save()/local_irq_restore(), and looks better.
void
xt_info_rdlock_bh(void){ struct xt_info_lock *lock; local_bh_disable();(quoted diff) +0
-0lock = &__get_cpu_var(xt_info_locks); if (likely(++lock->depth == 0)) spin_lock(&lock->lock);
Quoted 1 line
}
This two functions is OK. But...
Quoted 12 lines
void
xt_info_rdunlock_bh(void){ struct xt_info_lock *lock = &__get_cpu_var(xt_info_locks); BUG_ON(lock->depth < 0); if (likely(--lock->depth < 0)) spin_unlock(&lock->lock); local_bh_enable(); }
David said:
Netfilter itself, is nesting.
When using bridging netfilter, iptables can be entered twice in the same call chain.
And Stephen said:
In this version, I was trying to use/preserve the optimizations that are done in spin_unlock_bh().
So:
void xt_info_rdlock_bh(void)
{
struct xt_info_lock *lock;
preempt_disable();
lock = &__get_cpu_var(xt_info_locks);
if (likely(lock->depth < 0))
spin_lock_bh(&lock->lock);
/* softirq is disabled now */
++lock->depth;
preempt_enable_no_resched();
}xt_info_rdunlock_bh() is the same as v11.
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Eric DumazetQuoted 19 lines · Eric Dumazet
Quoted 17 lines · Lai Jiangshan
Quoted 4 lines · Stephen Hemminger
net/netfilter/x_tables.c +4
-0+/** +* xt_table_info_rdlock_bh - recursive read lock for xt table info +* +* Table processing calls this to hold off any changes to table net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 697
Quoted 10 lines
net/netfilter/x_tables.c +10
-0+* (on current CPU). Always leaves with bottom half disabled. +* If called recursively, then assumes bh/preempt already disabled. +*/ +void xt_info_rdlock_bh (void ) +{ +struct xt_info_lock *lock; + +preempt_disable (); + lock = &__get_cpu_var (xt_info_locks); +if (likely (++lock->depth ==0 ))Maybe I missed something. I think softirq may be still enabled here. So what happen when
xt_info_rdlock_bh()called recursively here?
Quoted 4 lines
well, first time its called, you are right softirqs are enabled until the point we call
spin_lock_bh(), right after this line :
Which context can enter the critical region?
Can irq and softirq? or softirq only?
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Stephen HemmingerQuoted 20 lines · Stephen Hemminger
This version of
x_tables(ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested. It is sort of like existingkernel_lock,rwlock_tand even old 2.4 brlock."Reader" is ip/arp/ip6 tables rule processing which runs per-cpu. It needs to ensure that the rules are not being changed while packet is being processed.
"Writer" is used in two cases: first is replacing rules in which case all packets in flight have to be processed before rules are swapped, then counters are read from the old (stale) info. Second case is where counters need to be read on the fly, in this case all CPU's are blocked from further rule processing until values are aggregated.
The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of
synchronize_net()(in 2.6.30-rc2).
Quoted 4 lines
The mutex that was added for 2.6.30 in
xt_tableis unnecessary since there already is a mutex for xt[af].mutex that is held.Signed-off-by Stephen Hemminger <[email protected]
I reviewed this patch believe its in quite good shape, thanks Stephen.
Then I tested it on a x86_32 8 cpus machine and got no obvious problem.
Hopefully, next rcu_bh (or whatever name is used) will permit us to switch back to pure RCU in 2.6.31
oprofile snapshot of a tbench session, with light iptables rules. (4 rules in INPUT chain, 3 rules on OUTPUT)
xt_info_rdlock_bh() uses 0.6786 % of cpuxt_info_rdunlock_bh() uses 0.1743 % of cpu
CPU: Core 2, speed 3000.77 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 100000
samples cum. samples % cum. % symbol name 1248350 1248350 11.3285 11.3285 copy_from_user 534049 1782399 4.8464 16.1749 copy_to_user 480898 2263297 4.3641 20.5390 __schedule 325581 2588878 2.9546 23.4936 ipt_do_table 312697 2901575 2.8377 26.3312 tcp_ack 309381 3210956 2.8076 29.1388 tcp_sendmsg 248238 3459194 2.2527 31.3915 tcp_v4_rcv 230405 3689599 2.0909 33.4824 tcp_transmit_skb 220638 3910237 2.0022 35.4847 ip_queue_xmit 217099 4127336 1.9701 37.4548 tcp_recvmsg 175885 4303221 1.5961 39.0509 tcp_rcv_established 173112 4476333 1.5710 40.6219 __switch_to 165138 4641471 1.4986 42.1205 sysenter_past_esp 149367 4790838 1.3555 43.4759 dst_release 138619 4929457 1.2579 44.7339 sched_clock_cpu 132724 5062181 1.2044 45.9383 lock_sock_nested 121353 5183534 1.1013 47.0396 nf_iterate 119205 5302739 1.0818 48.1214 netif_receive_skb 118859 5421598 1.0786 49.2000 release_sock 112597 5534195 1.0218 50.2218 __inet_lookup_established 112195 5646390 1.0181 51.2399 sys_socketcall 110018 5756408 0.9984 52.2383 tcp_write_xmit 106466 5862874 0.9662 53.2045 __alloc_skb 93386 5956260 0.8475 54.0519 dev_queue_xmit 89229 6045489 0.8097 54.8617 tcp_event_data_recv 85972 6131461 0.7802 55.6418 local_bh_enable 82882 6214343 0.7521 56.3940 skb_release_data 80898 6295241 0.7341 57.1281 ip_rcv 76380 6371621 0.6931 57.8213 skb_copy_datagram_iovec 74782 6446403 0.6786 58.4999 xt_info_rdlock_bh 73593 6519996 0.6678 59.1677 mod_timer 72884 6592880 0.6614 59.8291 sock_recvmsg 71789 6664669 0.6515 60.4806 __copy_skb_header 70560 6735229 0.6403 61.1209 fget_light 68756 6803985 0.6239 61.7449 get_page_from_freelist 68378 6872363 0.6205 62.3654 put_page 68042 6940405 0.6175 62.9829 ip_finish_output 67618 7008023 0.6136 63.5965 page_address 64894 7072917 0.5889 64.1854 tcp_cleanup_rbuf
Quoted 10 lines
---
CHANGES
- optimize for UP
- disable bottom half ininfo_rdlock
- prevent preempt count overflow
- turn off lockdep in writer to avoid bogus warning
- optimizeunlock_bh
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
On Tue, Apr 21, 2009 at 06:59:29AM +0200, Eric Dumazet wrote:
[ . . . ]
Quoted 2 lines
Hopefully, next
rcu_bh(or whatever name is used) will permit us to switch back to pure RCU in 2.6.31
My excursion in to rcu_fgp can be thought of as a training exercise for doing this, though perhaps others are also working on an upgraded rcu_bh as well.
Thanx, Paul
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Stephen HemmingerMy silly opinion about lockdep in this patch:
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 672
Quoted 3 lines
net/netfilter/x_tables.c +3
-0+ +struct xt_info_lock { +spinlock_t lock;
+ struct lock_class_key key;
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 680
Quoted 8 lines
net/netfilter/x_tables.c +8
-0+int depth;/* # readers - 1 */ +}; +static DEFINE_PER_CPU(struct xt_info_lock, xt_info_locks); + + +static inline void xt_info_lock_init (struct xt_info_lock *lock) +{ +spin_lock_init (&lock->lock);
+ lockdep_set_class(&lock->lock, &lock->key);
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 683
Quoted 3 lines
net/netfilter/x_tables.c +3
-0+ lock->depth =-1 ; +} +
And remove lockdep_xxx()s.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Stephen HemmingerOk, so others already pointed out how dangerous/buggy this looks, but I'd like to strengthen that a bit more:
Quoted 9 lines · Stephen Hemminger
net/netfilter/x_tables.c +9
-0+ +/** +* xt_table_info_rdlock_bh - recursive read lock for xt table info +* +* Table processing calls this to hold off any changes to table +* (on current CPU). Always leaves with bottom half disabled. +* If called recursively, then assumes bh/preempt already disabled. +*/ +void xt_info_rdlock_bh (void )
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 701
Quoted 10 lines
net/netfilter/x_tables.c +10
-0+{ +struct xt_info_lock *lock; + +preempt_disable (); + lock = &__get_cpu_var (xt_info_locks); +if (likely (++lock->depth ==0 )) +spin_lock_bh (&lock->lock); +preempt_enable_no_resched (); +} +EXPORT_SYMBOL_GPL (xt_info_rdlock_bh);
This function is FUCKED UP.
It's total crap for several reasons"
- the already-mentioned race with bottom half locking.
If bottom halfs aren't already disabled, then if a bottom half comes in after the "++lock->depth" and before the spin_lock_bh(), then you will have no locking AT ALL for the processing of that bottom half - it will just increment the lock depth again, and nobody will have locked anything at all.
And if for some reason, you can prove that bottom half processing is already disabled, then ALL THAT OTHER CRAP is just that - CRAP. The whole preemption disabling, the whole "_bh()" thing, everything.
So either it's horribly buggy, or it's horribly broken and pointless. Take your pick.
- the total lack of comments. Why does that "count" protect anything? It's not a recursive lock, since there is no ownership (two independent accessors could call this and both "get" the lock), so you had damn well better create some big-ass comments about why it's ok in this case, and what the rules are that make it ok.
So DON'T GO AROUND CALLING IT A RECURSIVE LOCK! Don't write comments that are TOTAL AND UTTER SH*T! Just DON'T!
It's a "reader lock". It's not "recursive". It never was recursive, it never will be, and calling it that is just a sign that whoever wrote the function is a moron and doesn't know what he is doing. STOP DOING THIS!
- that _idiotic_ "preempt_enable_no_resched()". F*ck me, but the comment already says that preemption is disabled when exiting, so why does it even bother to enable it? Why play those mindless games with preemption counts, knowing that they are bogus?
Do it readably. Disable preemption first, and just re-enable it at UNLOCK time. No odd pseudo-reenables anywhere.
Oh, I know very well that the spli-locking will disable preemption, so it's "correct" to play those games, but the point is, it's just damn stupid and annoying. It just makes the source code actively _misleading_ to see crap like that - it looks like you enabled preemption, when in fact the code very much on purpose does _not_ enable preemption at all.
In other words, I really REALLY hate that patch. I think it looks slightly better than Eric Dumazet's original patch (at least the locking subtlety is now in a function of its own and _could_ be commented upon sanely and if it wasn't broken it might be acceptable), but quite frankly, I'd still horribly disgusted with the crap.
Why are you doing this insane thing? If you want a read-lock, just use the damned read-write locks already! Ad far as I can tell, this lock is in _no_ way better than just using those counting reader-writer locks, except it is open-coded and looks buggy.
There is basically _never_ a good reason to re-implement locking
primitives: you'll just introduce bugs. As proven very ably by the amount of crap above in what is supposed to be a very simple function.
If you want a counting read-lock (in _order_ to allow recursion, but not because the lock itself is somehow recursive!), then that function should look like this:
void xt_info_rdlock_bh(void)
{
struct xt_info_lock *lock
local_bh_disable();
lock = &__get_cpu_var(xt_info_locks);
read_lock(&lock->lock);
}And then the "unlock" should be the reverse. No games, no crap, and hopefully then no bugs. And if you do it that way, you don't even need the comments, although quite frankly, it probably makes a lot of sense to talk about the interaction between "local_bh_disable()" and the preempt count, and why you're not using "read_lock_bh()".
And if you don't want a read-lock, then fine - don't use a read-lock, do something else. But then don't just re-implement it (badly) either and call it something else!
Linus
PS: Ingo, why do the *_bh() functions in kernel/spinlock.c do _both_ a "local_bh_disable()" and a "preempt_disable()"? BH disable should disable preemption too, no? Or am I confused? In which case we need that in the above rdlock_bh too.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 109 lines · On Tue, 21 Apr 2009 09:13:52 -0700 (PDT) Linus Torvalds…
Ok, so others already pointed out how dangerous/buggy this looks, but I'd like to strengthen that a bit more:
Quoted 9 lines · Stephen Hemminger
net/netfilter/x_tables.c +9
-0+ +/** +* xt_table_info_rdlock_bh - recursive read lock for xt table info +* +* Table processing calls this to hold off any changes to table +* (on current CPU). Always leaves with bottom half disabled. +* If called recursively, then assumes bh/preempt already disabled. +*/ +void xt_info_rdlock_bh (void )net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 701
Quoted 10 lines
net/netfilter/x_tables.c +10
-0+{ +struct xt_info_lock *lock; + +preempt_disable (); + lock = &__get_cpu_var (xt_info_locks); +if (likely (++lock->depth ==0 )) +spin_lock_bh (&lock->lock); +preempt_enable_no_resched (); +} +EXPORT_SYMBOL_GPL (xt_info_rdlock_bh);This function is FUCKED UP.
It's total crap for several reasons"
- the already-mentioned race with bottom half locking.
If bottom halfs aren't already disabled, then if a bottom half comes in after the "++lock->depth" and before the
spin_lock_bh(), then you will have no locking AT ALL for the processing of that bottom half - it will just increment the lock depth again, and nobody will have locked anything at all.And if for some reason, you can prove that bottom half processing is already disabled, then ALL THAT OTHER CRAP is just that - CRAP. The whole preemption disabling, the whole "
_bh()" thing, everything.So either it's horribly buggy, or it's horribly broken and pointless. Take your pick.
- the total lack of comments. Why does that "count" protect anything? It's not a recursive lock, since there is no ownership (two independent accessors could call this and both "get" the lock), so you had damn well better create some big-ass comments about why it's ok in this case, and what the rules are that make it ok.
So DON'T GO AROUND CALLING IT A RECURSIVE LOCK! Don't write comments that are TOTAL AND UTTER SH*T! Just DON'T!
It's a "reader lock". It's not "recursive". It never was recursive, it never will be, and calling it that is just a sign that whoever wrote the function is a moron and doesn't know what he is doing. STOP DOING THIS!
- that _idiotic_ "
preempt_enable_no_resched()". F*ck me, but the comment already says that preemption is disabled when exiting, so why does it even bother to enable it? Why play those mindless games with preemption counts, knowing that they are bogus?Do it readably. Disable preemption first, and just re-enable it at UNLOCK time. No odd pseudo-reenables anywhere.
Oh, I know very well that the spli-locking will disable preemption, so it's "correct" to play those games, but the point is, it's just damn stupid and annoying. It just makes the source code actively _misleading_ to see crap like that - it looks like you enabled preemption, when in fact the code very much on purpose does _not_ enable preemption at all.
In other words, I really REALLY hate that patch. I think it looks slightly better than Eric Dumazet's original patch (at least the locking subtlety is now in a function of its own and _could_ be commented upon sanely and if it wasn't broken it might be acceptable), but quite frankly, I'd still horribly disgusted with the crap.
Why are you doing this insane thing? If you want a read-lock, just use the damned read-write locks already! Ad far as I can tell, this lock is in _no_ way better than just using those counting reader-writer locks, except it is open-coded and looks buggy.
There is basically _never_ a good reason to re-implement locking
primitives: you'll just introduce bugs. As proven very ably by the amount of crap above in what is supposed to be a very simple function.If you want a counting read-lock (in _order_ to allow recursion, but not because the lock itself is somehow recursive!), then that function should look like this:
void xt_info_rdlock_bh(void) { struct xt_info_lock *lock local_bh_disable(); lock = &__get_cpu_var(xt_info_locks); read_lock(&lock->lock); }And then the "unlock" should be the reverse. No games, no crap, and hopefully then no bugs. And if you do it that way, you don't even need the comments, although quite frankly, it probably makes a lot of sense to talk about the interaction between "
local_bh_disable()" and the preempt count, and why you're not using "read_lock_bh()".And if you don't want a read-lock, then fine - don't use a read-lock, do something else. But then don't just re-implement it (badly) either and call it something else!
Quoted 6 lines
Linus
PS: Ingo, why do the
*_bh()functions inkernel/spinlock.cdo _both_ a "local_bh_disable()" and a "preempt_disable()"? BH disable should disable preemption too, no? Or am I confused? In which case we need that in the aboverdlock_bhtoo.
Ah a nice day, with Linus giving constructive feedback. Too bad he has to channel it out of the dark side.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 3 lines · Stephen Hemminger
Ah a nice day, with Linus giving constructive feedback. Too bad he has to channel it out of the dark side.
I already flamed that patch at least once before. People didn't react.
What do I have to do to make people listen? I'm sorry, but I'm not going to send you flowers with a card saying "Hope you do better next time!".
I realize that the flowers might be friendlier, but I have absolutely no incentive to be friendly to just bad code. I have even _less_ incentive when my first "that sucks" is apparently totally ignored. So now I spelled it out why it sucks, but I sure as hell didn't have any reason to be polite about it.
Linus
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Linus TorvaldsQuoted 4 lines · Linus Torvalds
PS: Ingo, why do the
*_bh()functions inkernel/spinlock.cdo _both_ a "local_bh_disable()" and a "preempt_disable()"? BH disable should disable preemption too, no? Or am I confused? In which case we need that in the aboverdlock_bhtoo.
i think there might be (are?) uses of:
spin_lock_bh(&some->lock); ... spin_unlock(&some->lock); ... local_bh_enable();
So we have to have two preemption control levels for that, as there's no knowledge at the spin_lock_bh() place whether it will be followed by a spin_unlock_bh() [in which case it would be safe to do SOFTIRQ_OFFSET only] - or by a spin_unlock() + local_bh_enable() pair..
[ That locking pattrn even makes a certain amount of sense: keep the
lock held for a short amount of time - then weaken locking to bh context exclusion only. ]
What we could do is an optimization to do a compound increase the preempt count by SOFTIRQ_OFFSET+1 - instead of a local_bh_disable()
+ preempt_disable()? Symmetrically we could do a compound decrease in the unlock case.
It might even be called: local_bh_preempt_disable() or so?
Ingo
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Linus TorvaldsSubject: netfilter: use per-cpu recursive lock (v12)
This version of x_tables (ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.
The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of synchronize_net() (in 2.6.30-rc2).
The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.
I don't like the NR_CPUS preempt count kludge, it is working around an issue that should be handled in a more generic way.
---
CHANGES
- go back to read/write lock
- reader case is now inline
- more comments
- always disables bottom half
- only play preempt count mindgames if really necessary
- add lockdep keys
include/linux/netfilter/x_tables.h | 42 ++++++++++++-- net/ipv4/netfilter/arp_tables.c | 110 ++++++++----------------------------- net/ipv4/netfilter/ip_tables.c | 110 +++++++------------------------------ net/ipv6/netfilter/ip6_tables.c | 108 ++++++++---------------------------- net/netfilter/x_tables.c | 77 ++++++++++++++++++------- 5 files changed, 165 insertions(+), 282 deletions(-)
include/linux/netfilter/x_tables.h +37 -5
@@ -354,9 +354,6 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -struct mutex lock; -/* Man behind the curtain... */ struct xt_table_info *private;
@@ -434,8 +431,43 @@ extern void xt_proto_fini(struct net *neextern 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); + + +/* +* Per-CPU read/write lock. This makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since write must iterate over all +* possible CPU's. Readers read lock their per-cpu lock, and writers +* write lock on all CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing rules +* all packets in flight have to be processed before rules are swapped, +* then counters are read from the old (stale) info. +* +*/ +DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +local_bh_disable (); +read_lock (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_rdunlock_bh (void ) +{ +read_unlock_bh (&__get_cpu_var (xt_info_locks)); +} + +extern void xt_info_wrlock_bh (void ); +extern void xt_info_wrunlock_bh (void );/* * This helper is performance critical and must be inlined
net/ipv4/netfilter/ip_tables.c +23 -87
169 lines not on this page · raw message
net/netfilter/x_tables.c +55 -22
117 lines not on this page · raw message
net/ipv6/netfilter/ip6_tables.c +25 -83
166 lines not on this page · raw message
net/ipv4/netfilter/arp_tables.c +25 -85
173 lines not on this page · raw message
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 6 lines · Stephen Hemminger
net/netfilter/x_tables.c +6
-0+void xt_info_wrlock_bh (void ) +{ +unsigned int i; + +local_bh_disable (); +for_each_possible_cpu (i) {
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 683
Quoted 10 lines
net/netfilter/x_tables.c +10
-0+write_lock (&per_cpu (xt_info_locks, i)); +#if NR_CPUS > (PREEMPT_MASK -1 ) +/* +* Since spin_lock disables preempt, the following is +* required to avoid overflowing the preempt counter +*/ +preempt_enable_no_resched (); +#endif + } +}
hm, this is rather ugly and it will make a lot of instrumentation code explode.
Why not use the obvious solution: a _single_ wrlock for global access and read_can_lock() plus per cpu locks in the fastpath?
That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized - on NUMA too) - and we will hold at most 1-2 locks at once!
Something like:
__cacheline_aligned DEFINE_RWLOCK(global_wrlock);
DEFINE_PER_CPU(rwlock_t local_lock);
void local_read_lock(void)
{
again:
read_lock(&per_cpu(local_lock, this_cpu));
if (unlikely(!read_can_lock(&global_wrlock))) {
read_unlock(&per_cpu(local_lock, this_cpu));
/*
* Just wait for any global write activity:
*/
read_unlock_wait(&global_wrlock);
goto again;
}
}
void global_write_lock(void)
{
write_lock(&global_wrlock);
for_each_possible_cpu(i)
write_unlock_wait(&per_cpu(local_lock, i));
}Note how nesting friendly this construct is: we dont actually _hold_ NR_CPUS locks all at once, we simply cycle through all CPUs and make sure they have our attention.
No preempt overflow. No lockdep explosion. A very fast and scalable read path.
Okay - we need to implement read_unlock_wait() and write_unlock_wait() which is similar to spin_unlock_wait(). The trivial first-approximation is:
read_unlock_wait(x)
{
read_lock(x);
read_unlock(x);
}
write_unlock_wait(x)
{
write_lock(x);
write_unlock(x);
}Hm?
Ingo
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 3 lines · Ingo Molnar
Why not use the obvious solution: a _single_ wrlock for global access and
read_can_lock()plus per cpu locks in the fastpath?
Obvious is not the qualifier I would use :)
Brilliant yes :)
Quoted 7 lines
That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized - on NUMA too) - and we will hold at most 1-2 locks at once!
Something like:
Quoted 9 lines
__cacheline_aligned DEFINE_RWLOCK(global_wrlock);
DEFINE_PER_CPU(rwlock_t local_lock);
void local_read_lock(void)
{
again:
read_lock(&per_cpu(local_lock, this_cpu));Hmm... here we can see global_wrlock locked by on writer, while this cpu already called local_read_lock(), and calls again this function -> Deadlock, because we hold our local_lock locked.
Quoted 30 lines
if (unlikely(!read_can_lock(&global_wrlock))) { read_unlock(&per_cpu(local_lock, this_cpu)); /* * Just wait for any global write activity: */ read_unlock_wait(&global_wrlock); goto again; } } void global_write_lock(void) { write_lock(&global_wrlock); for_each_possible_cpu(i) write_unlock_wait(&per_cpu(local_lock, i)); }Note how nesting friendly this construct is: we dont actually _hold_
NR_CPUSlocks all at once, we simply cycle through all CPUs and make sure they have our attention.No preempt overflow. No lockdep explosion. A very fast and scalable read path.
Okay - we need to implement
read_unlock_wait()andwrite_unlock_wait()which is similar tospin_unlock_wait(). The trivial first-approximation is:
Quoted 12 lines
read_unlock_wait(x)
{
read_lock(x);
read_unlock(x);
}
write_unlock_wait(x)
{
write_lock(x);
write_unlock(x);
}Very interesting and could be changed to use spinlock + depth per cpu.
-> we can detect recursion and avoid the deadlock, and we only use one atomic operation per lock/unlock pair in fastpath (this was the reason we tried hard to use a percpu spinlock during this thread)
__cacheline_aligned DEFINE_RWLOCK(global_wrlock);
struct ingo_local_lock {
spinlock_t lock;
int depth;
};DEFINE_PER_CPU(struct ingo_local_lock local_lock);
void local_read_lock(void)
{
struct ingo_local_lock *lck;
local_bh_and_preempt_disable();
lck = &get_cpu_var(local_lock);
if (++lck->depth > 0) /* already locked */
return;
again:
spin_lock(&lck->lock);
if (unlikely(!read_can_lock(&global_wrlock))) {
spin_unlock(&lck->lock);
/*
* Just wait for any global write activity:
*/
read_unlock_wait(&global_wrlock);
goto again;
}
}void global_write_lock(void)
{
write_lock(&global_wrlock);
for_each_possible_cpu(i)
spin_unlock_wait(&per_cpu(local_lock, i));
}Hmm ?
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 8 lines · Eric Dumazet
Quoted 3 lines · Ingo Molnar
Why not use the obvious solution: a _single_ wrlock for global access and
read_can_lock()plus per cpu locks in the fastpath?Obvious is not the qualifier I would use :)
Brilliant yes :)
thanks :)
Quoted 11 lines
Quoted 11 lines
That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized
- on NUMA too) - and we will hold at most 1-2 locks at once!Something like:
__cacheline_aligned DEFINE_RWLOCK(global_wrlock); DEFINE_PER_CPU(rwlock_t local_lock);
Quoted 8 lines
Quoted 4 lines
void local_read_lock(void) { again: read_lock(&per_cpu(local_lock, this_cpu));Hmm... here we can see
global_wrlocklocked by on writer, while this cpu already calledlocal_read_lock(), and calls again this function -> Deadlock, because we hold ourlocal_locklocked.
Yeah, indeed.
I wasnt really concentrating on the nested case, i was concentrating on the scalability and lock nesting angle. I think the code submitted here looks rather incestous in that regard.
Allowing nested locking _on the same CPU_ is asking for trouble. Use short critical sections and if there's any exclusion needed, use an irq-safe lock or a softirq-safe lock. Problem solved.
Quoted 40 lines
Very interesting and could be changed to use spinlock + depth per cpu.
-> we can detect recursion and avoid the deadlock, and we only use one atomic operation per lock/unlock pair in fastpath (this was the reason we tried hard to use a percpu spinlock during this thread)
__cacheline_alignedDEFINE_RWLOCK(global_wrlock);struct ingo_local_lock { spinlock_t lock; int depth; };
DEFINE_PER_CPU(struct ingo_local_lock local_lock);void
local_read_lock(void){ struct ingo_local_lock *lck; local_bh_and_preempt_disable(); lck = &get_cpu_var(local_lock); if (++lck->depth > 0) /* already locked */ return; again: spin_lock(&lck->lock); if (unlikely(!read_can_lock(&global_wrlock))) { spin_unlock(&lck->lock); /* * Just wait for any global write activity: */ read_unlock_wait(&global_wrlock); goto again; } }void
global_write_lock(void)
Quoted 8 lines
{ write_lock(&global_wrlock); for_each_possible_cpu(i) spin_unlock_wait(&per_cpu(local_lock, i)); }Hmm ?
Yeah, this looks IRQ-nesting safe. But i really have to ask: why does this code try so hard to allow same-CPU nesting?
Nesting on the same CPU is _bad_ for several reasons:
1) Performance: it rips apart critical sections cache-wise. Instead of a nice:
C1 ... C2 ... C3 ... C4
serial sequence of critical sections, we get:
C1A ... ( C2 ) ... C1B ... C3 ... C4
Note that C1 got "ripped apart" into C1A and C1B with C2 injected
- reducing cache locality between C1A and C1B. We have to execute C1B no matter what, so we didnt actually win anything in terms of total work to do, by processing C2 out of order.
[ Preemption of work (which this kind of nesting is really about)
is _the anti-thesis of performance_, and we try to delay it as much as possible and we try to batch up as much as possible. For example the CPU scheduler will try _real_ hard to not preempt a typical workload, as long as external latency boundaries allow that. ]
2) Locking complexity and robustness. Nested locking is rank #1 in terms of introducing regressions into the kernel.
3) Instrumentation/checking complexity. Checking locking dependencies is good and catches a boatload of bugs before they hit upstream, and nested locks are supported but cause an exponential explosion in terms of dependencies to check.
Also, whenever instrumentation explodes is typically the sign of some true, physical complexity that has been introduced into the code. So it often is a canary for a misdesign at a fundamental level, not a failure in the instrumentation framework.
In the past i saw lock nesting often used as a wrong solution when the critical sections were too long (causing too long latencies for critical work - e.g. delaying hardirq completion processing unreasonably), or just plain out of confusion about the items above.
I dont know whether that's the case here - it could be one of the rare exceptions calling for a new locking primitive (which should then be introduced at the core kernel level IMHO) - i dont know the code that well.
Ingo
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 128 lines · Ingo Molnar
Quoted 6 lines · Eric Dumazet
Quoted 2 lines · Ingo Molnar
Why not use the obvious solution: a _single_ wrlock for global access and
read_can_lock()plus per cpu locks in the fastpath?Obvious is not the qualifier I would use :)
Brilliant yes :)
thanks :)
Quoted 11 lines
Quoted 11 lines
That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized
- on NUMA too) - and we will hold at most 1-2 locks at once!Something like:
__cacheline_aligned DEFINE_RWLOCK(global_wrlock); DEFINE_PER_CPU(rwlock_t local_lock);Quoted 7 lines
Quoted 4 lines
void local_read_lock(void) { again: read_lock(&per_cpu(local_lock, this_cpu));Hmm... here we can see
global_wrlocklocked by on writer, while this cpu already calledlocal_read_lock(), and calls again this function -> Deadlock, because we hold ourlocal_locklocked.Yeah, indeed.
I wasnt really concentrating on the nested case, i was concentrating on the scalability and lock nesting angle. I think the code submitted here looks rather incestous in that regard.
Allowing nested locking
_onthe sameCPU_is asking for trouble. Use short critical sections and if there's any exclusion needed, use an irq-safe lock or a softirq-safe lock. Problem solved.Quoted 40 lines
Very interesting and could be changed to use spinlock + depth per cpu.
-> we can detect recursion and avoid the deadlock, and we only use one atomic operation per lock/unlock pair in fastpath (this was the reason we tried hard to use a percpu spinlock during this thread)
__cacheline_alignedDEFINE_RWLOCK(global_wrlock);struct ingo_local_lock { spinlock_t lock; int depth; };
DEFINE_PER_CPU(struct ingo_local_lock local_lock);void
local_read_lock(void){ struct ingo_local_lock *lck; local_bh_and_preempt_disable(); lck = &get_cpu_var(local_lock); if (++lck->depth > 0) /* already locked */ return; again: spin_lock(&lck->lock); if (unlikely(!read_can_lock(&global_wrlock))) { spin_unlock(&lck->lock); /* * Just wait for any global write activity: */ read_unlock_wait(&global_wrlock); goto again; } }void
global_write_lock(void)Quoted 8 lines
{ write_lock(&global_wrlock); for_each_possible_cpu(i) spin_unlock_wait(&per_cpu(local_lock, i)); }Hmm ?
Yeah, this looks IRQ-nesting safe. But i really have to ask: why does this code try so hard to allow same-CPU nesting?
Nesting on the same CPU is _bad_ for several reasons:
1) Performance: it rips apart critical sections cache-wise. Instead of a nice:
C1 ... C2 ... C3 ... C4serial sequence of critical sections, we get:
C1A ... ( C2 ) ... C1B ... C3 ... C4Note that C1 got "ripped apart" into C1A and C1B with C2 injected
- reducing cache locality between C1A and C1B. We have to execute C1B no matter what, so we didnt actually win anything in terms of total work to do, by processing C2 out of order.[ Preemption of work (which this kind of nesting is really about)
is_theanti-thesis ofperformance_, and we try to delay it as much as possible and we try to batch up as much as possible. For example the CPU scheduler will try _real_ hard to not preempt a typical workload, as long as external latency boundaries allow that. ]2) Locking complexity and robustness. Nested locking is rank #1 in terms of introducing regressions into the kernel.
3) Instrumentation/checking complexity. Checking locking dependencies is good and catches a boatload of bugs before they hit upstream, and nested locks are supported but cause an exponential explosion in terms of dependencies to check.
Also, whenever instrumentation explodes is typically the sign of some true, physical complexity that has been introduced into the code. So it often is a canary for a misdesign at a fundamental level, not a failure in the instrumentation framework.
Quoted 5 lines
In the past i saw lock nesting often used as a wrong solution when the critical sections were too long (causing too long latencies for critical work - e.g. delaying hardirq completion processing unreasonably), or just plain out of confusion about the items above.
I agree with all this Ingo.
Quoted 4 lines
I dont know whether that's the case here - it could be one of the rare exceptions calling for a new locking primitive (which should then be introduced at the core kernel level IMHO) - i dont know the code that well.
The netfilter case is real simple Ingo, (note I did not use "obvious" here ;) )
netfilter in 2.6.2[0-9] used :
CPU 1
sofirq handles one packet from a NIC
ipt_do_table() /* to handle INPUT table for example, or FORWARD */ read_lock_bh(&a_central_and_damn_rwlock)
... parse rules
-> calling some netfilter sub-function
re-entering network IP stack to send some packet (say a RST packet)
...
ipt_do_table() /* to handle OUPUT table rules for example */ read_lock_bh() ; /* WE RECURSE here, but once in a while (if ever) */
This is one of the case, but other can happens with virtual networks, tunnels, ... and so on. (Stephen had some cases with KVM if I remember well)
If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.
I was pleased by your locking schem, that was *very* interesting, even if not yet ready.
1) We can discuss of how bad recursion is.
We know loopback_xmit() could be way faster if we could avoid queeing packet to softirq handler.
(Remember you and I suggested this patch some months ago ? Please remember David rejected this because of recursion and possibility to overflow stack)
So yes, people are aware of recursion problems.
2) We can discuss how bad rwlocks are
We did lot of work on last months to delete some of rwlocks we had in kernel. UDP stack for example dont use them anymore.
We tried to delete them on x_tables, but we must take care of ipt_do_table() nesting, that is legal on 2.6.30.
Maybe netfilter guys can work to avoid this nesting on 2.6.31,
I dont know how hard it is, definitly not 2.6.30 material.
Solutions were discussed many times and Stephen provided 13 versions of the patch. If this was that obvious, one or two iterations would have been OK.
3) About last patch (v13)
Stephen did not agreed with you (well... maybe after all ..), he only submitted again a previous version.
With linux-2.6.2[0-9], "iptables -L" used to block all cpus from entering netfilter because we did a write_lock_bh() on the central rwlock while folding counters.
On v13, we dont try to freeze whole x_table context, but cpu per cpu. Thats a minor change against previous versions, and should not lead to strange application behavior. Its so much scalable that we should accept this change.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
On 22-04-2009 10:53, Eric Dumazet wrote:
...
Quoted 3 lines
If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.
Right, looks like 100% (Scandinavian?!) troll. I wonder where is the admin of this mess...
Jarek P.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 9 lines · Jarek Poplawski
On 22-04-2009 10:53, Eric Dumazet wrote:
...Quoted 4 lines
If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.
Right, looks like 100% (Scandinavian?!) troll. I wonder where is the admin of this mess...
You might disagree with me on an honest technical basis, but note that this kind of childish, knee-jerk reaction against dissenting people is what gives netdev its bad reputation.
Ingo
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 10 lines · Ingo Molnar
Quoted 7 lines · Jarek Poplawski
On 22-04-2009 10:53, Eric Dumazet wrote:
...Quoted 4 lines
If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.
Quoted 6 lines
Quoted 2 lines
Right, looks like 100% (Scandinavian?!) troll. I wonder where is the admin of this mess...
You might disagree with me on an honest technical basis, but note that this kind of childish, knee-jerk reaction against dissenting people is what gives netdev its bad reputation.
How did you find I disagree with you? There was nothing about you, neither anything technical. Actually, I forgot to mention I agree with Eric about your locking proposal.
Jarek P.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Eric DumazetQuoted 15 lines · Eric Dumazet
netfilter in 2.6.2[0-9] used :
CPU 1
sofirq handles one packet from a NIC
ipt_do_table()/* to handle INPUT table for example, or FORWARD */read_lock_bh(&a_central_and_damn_rwlock)
... parse rules
-> calling some netfilter sub-function
re-entering network IP stack to send some packet (say a RST packet)
...
ipt_do_table()/* to handle OUPUT table rules for example */read_lock_bh(); /* WE RECURSE here, but once in a while (if ever) */
Quoted 8 lines
This is one of the case, but other can happens with virtual networks, tunnels, ... and so on. (Stephen had some cases with KVM if I remember well)
If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.
Again ... i dont know this code well, but you yourself describe it as "a_central_and_damn_rwlock" above.
"Central and damn" locks of any type, anywhere tend to cause such trouble.
Often they are mini-BKL's in the making. Here's some historic patterns:
1- First there's a convenient lock around a popular and useful
piece of data and code.
2- As popularity (and reach of code) grows, and some non-trivial
interaction ensues, a little bit of self-recursion is added to the mix (this is often easier to do than to fix the root cause of the problem) - making critical sections even easier to grow in size.
3- Then attempts are made to make it scale all (it's a popular
piece of code), it's extended along a per-cpu axis, but complexity of locking explode by taking a ton of locks all at once. The solution: yell at the lock validator for not allowing this (or for exploding due to the sheer mathematically large complexity of the locking rules). Frequent requests for an exclusion from those pesky validations are made, and various hacks are done to work it around. It's all the fault of the lock validator, of course.
4- At this point it's rarely a clean, tidy data lock anymore - it
tends to grow into a code lock nobody really knows how it works, except that it better be taken more often than not, badness may ensue otherwise. Nobody really knows when to take it, only that it should be taken widely enough, that it should be recursive enough to call even _more_ code from under it. Efforts to reduce critical section length are rebuffed with: "this adds unlocking and relocking overhead". And it should then all scale as well.
5- In the end it's a lock everyone curses but nobody is able to fix
anymore. "If it was easy to fix we'd have fixed it long ago already" kind of fatalist thinking becomes widespread.
We saw many examples of this in the past: beyond the BKL (which is a bit special as its more of an UP legacy - but which hurt us the most), we had the tasklist_lock which was problematic for a long time, then there's also the reiser3 locking which was extremely monolithic. [ i'm only naming safe examples here, where nobody will flame me =B-) ]
Whether this particular case applies is up to you. I see certain matches up to phase 3 or so - but i also see certain dissimilarities as well. Nor do i claim that it's easy to fix or improve.
Ingo
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Eric DumazetQuoted 4 lines · Eric Dumazet
If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.
You don't _understand_ do you?
There is a huge difference between recursive code, and a recursive lock.
The netfilter code may need to occasionally re-enter itself. Nobody ever contested _that_ part.
What I have disagreed with the whole time is
(a) doing local ad-hoc locking primitives without any comments what-so-ever.
(b) Doing them _wrong_ in many cases
(c) Calling the _lock_ a "recursive" lock.
The fact that a lock works with recursion doesn't make it "recursive". That generally has a very special meaning for locking primitives, and means something else.
In contrast, a read-write lock actually has known properties, and we have existing locking mechanisms for those. And we call them read-write locks DESPITE THE FACT that the reading part can be done recursively.
If you call a read-write lock a "recursive" lock, then you're a moron. It simply is _not_ a recursive lock. And neither is the lock you actually implemented, even though you (and Stephen) continually call it that.
SO STOP CALLING IT A RECURSIVE LOCK. Look at your very own code: you can actually only use that lock in a recursive context in a _very_ specific place. Notice how it's only "recursive" when taken in the per-CPU context, but _not_ recursive when the filter-updating code ("writer") takes it?
Do you understand now? It really shouldn't be so hard for you.
Naming is important. Locking is important. You did both things wrong. You named your locks something incorrect and mis-leading that didn't actually describe them, and you did your own private locking code without then documenting what the rules for this special lock were.
Maybe in your world that's ok. But no, in mine it's not. I've seen too many damn _non-functioning_ locks to ever want to see stuff like that again.
Linus
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 41 lines · Linus Torvalds
Quoted 3 lines · Eric Dumazet
If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.
You don't _understand_ do you?
There is a huge difference between recursive code, and a recursive lock.
The netfilter code may need to occasionally re-enter itself. Nobody ever contested _that_ part.
What I have disagreed with the whole time is
(a) doing local ad-hoc locking primitives without any comments what-so-ever.
(b) Doing them _wrong_ in many cases
(c) Calling the _lock_ a "recursive" lock.
The fact that a lock works with recursion doesn't make it "recursive". That generally has a very special meaning for locking primitives, and means something else.
In contrast, a read-write lock actually has known properties, and we have existing locking mechanisms for those. And we call them read-write locks DESPITE THE FACT that the reading part can be done recursively.
If you call a read-write lock a "recursive" lock, then you're a moron. It simply is _not_ a recursive lock. And neither is the lock you actually implemented, even though you (and Stephen) continually call it that.
SO STOP CALLING IT A RECURSIVE LOCK. Look at your very own code: you can actually only use that lock in a recursive context in a _very_ specific place. Notice how it's only "recursive" when taken in the per-CPU context, but _not_ recursive when the filter-updating code ("writer") takes it?
Do you understand now? It really shouldn't be so hard for you.
Quoted 10 lines
Naming is important. Locking is important. You did both things wrong. You named your locks something incorrect and mis-leading that didn't actually describe them, and you did your own private locking code without then documenting what the rules for this special lock were.
Maybe in your world that's ok. But no, in mine it's not. I've seen too many damn _non-functioning_ locks to ever want to see stuff like that again.
Linus,
I actually sent *one* buggy patch, and you already gave your feedback and NACK.
Fine
I even relayed this to Stephen suggesting him not calling this a recursive lock. (Note how I use 'suggesting' here)
So, what do you want from me ? Should I copy 100 times :
"I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron."
...
OK done
Can we now proceed and continue ?
Thank you
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 3 lines · Eric Dumazet
I actually sent *one* buggy patch, and you already gave your feedback and NACK.
Actually, the thing is, I don't even think your original patch was even buggy. The bug crept in later. I NAK'ed it not because it was buggy, but because of the ad-hoc'ness and the naming. Really.
And I actually even said so in my original rant:
'The fact that code "happens to work by mistake" (and I'm not saying that
your does - but it might just because of the per-cpu'ness of it [..]'
because your original patch still had the
rcu_read_lock_bh();
in place before the whole
rl = &__get_cpu_var(arp_tables_lock); if (likely(rl->count++ == 0)) spin_lock(&rl->lock);
and that should have protected against both BH callers and preemption.
So I actually believe that your original patch probably worked fine (but as I said in my reaction to it, I thought it was almost by mistake and I wasn't going to review it)
So the actual _bug_ crept in later, when the RCU lock was removed, and the lock was cleaned up and separated into a function of its own.
And in fact, that is kind of my point: "uncommented locking with ad-hoc semantics is very fragile". Even _correct_ code ends up not being correct in the long run, because people don't realize all the subtle issues.
Quoted 4 lines
I even relayed this to Stephen suggesting him not calling this a recursive lock. (Note how I use 'suggesting' here)
So, what do you want from me ? Should I copy 100 times :
So I consider this thread ended from a technical standpoint.
[ That said, I will not be at all shocked to hear if people decide later
that the RCU method was better after all, and that even the per-cpu rwlock or spinlock is just too expensive. ]
My problem today (apart from the relatively minor issue of also wanting to get the commit log fixed up) is just that I see emails from you finding my reaction shocking and from Jarek Poplawski that seem to still think that I'm a troll.
Just because I pointed out real technical problems? Is that shocking or trolling?
Really - please go back to my _original_ email. No, it was not polite. But here's another quote from it:
"Because even if it works today, it's just a bug waiting to happen."
and dammit, I sent that out _before_ the very next version of the patch that actually _did_ introduce that exact bug.
So dammit - what part of my email was "shocking" or "trolling"? The part where I was right? Or what?
Linus
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Linus Torvalds wrote, On 04/22/2009 07:18 PM:
...
Quoted 7 lines
My problem today (apart from the relatively minor issue of also wanting to get the commit log fixed up) is just that I see emails from you finding my reaction shocking and from Jarek Poplawski that seem to still think that I'm a troll.
Just because I pointed out real technical problems? Is that shocking or trolling?
Very funny! For newbies only: http://en.wikipedia.org/wiki/Troll_(Internet)
Actually, I admit you could be the best "Ozzy" Osbourne imposter instead. (At least at netdev.) Stephen's words seem to fit very well:
Quoted 2 lines
Ah a nice day, with Linus giving constructive feedback. Too bad he has to channel it out of the dark side.
Jarek P.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Eric DumazetQuoted 4 lines · Eric Dumazet
If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.
Btw., i didnt find Linus's reaction shocking at all, nor did i understand it as any criticism of prior (and future) good work of the people involved. I found it to be what it was: a forceful (because repeated) criticism of a bad patch.
Ingo
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Ingo MolnarQuoted 14 lines · On Tue, 21 Apr 2009 21:10:07 +0200 Ingo Molnar <[email protected]> wrote:
Quoted 11 lines · Stephen Hemminger
net/netfilter/x_tables.c +11
-0+void xt_info_wrlock_bh (void ) +{ +unsigned int i; + +local_bh_disable (); +for_each_possible_cpu (i) { +write_lock (&per_cpu (xt_info_locks, i)); +#if NR_CPUS > (PREEMPT_MASK -1 ) +/* +* Since spin_lock disables preempt, the following is +* required to avoid overflowing the preempt counter
Quoted 8 lines
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 683
Quoted 5 lines
net/netfilter/x_tables.c +5
-0+*/ +preempt_enable_no_resched (); +#endif + } +}hm, this is rather ugly and it will make a lot of instrumentation code explode.
Better general solutions:
* use raw_spin_lock
* increase PREEMPT_BITS on 64 bit machine and limit to 128 CPU or less on 32 bit
* get rid of default preempt_disable in spin_lock
You choose. It is a general problem.
Quoted 20 lines
Why not use the obvious solution: a _single_ wrlock for global access and
read_can_lock()plus per cpu locks in the fastpath?That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized - on NUMA too) - and we will hold at most 1-2 locks at once!
Something like:
__cacheline_aligned DEFINE_RWLOCK(global_wrlock); DEFINE_PER_CPU(rwlock_t local_lock); void local_read_lock(void) { again: read_lock(&per_cpu(local_lock, this_cpu)); if (unlikely(!read_can_lock(&global_wrlock))) {
Quoted 8 lines
read_unlock(&per_cpu(local_lock, this_cpu)); /* * Just wait for any global write activity: */ read_unlock_wait(&global_wrlock); goto again; } }
Quit trying to be so damn f*cking cool. We don't build the software for locking instrumentation. Locking instrumentation needs to serve the kernel, not the other way around.
Your version fails for the case of nested local rules. Which was the whole reason I switched to read/writer locks.
CPU 1 CPU 2
local_read_lock
... global_write_lock
local_read_lock
Stuck...
CPU 2 is waiting for CPU 1 to get out of its nested table processing CPU 1 is waiting for write lock to get done
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 26 lines · Stephen Hemminger
Quoted 17 lines
That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized
- on NUMA too) - and we will hold at most 1-2 locks at once!Something like:
__cacheline_aligned DEFINE_RWLOCK(global_wrlock); DEFINE_PER_CPU(rwlock_t local_lock); void local_read_lock(void) { again: read_lock(&per_cpu(local_lock, this_cpu)); if (unlikely(!read_can_lock(&global_wrlock))) {Quoted 8 lines
read_unlock(&per_cpu(local_lock, this_cpu)); /* * Just wait for any global write activity: */ read_unlock_wait(&global_wrlock); goto again; } }
Quoted 1 line
Quit trying to be so damn f*cking cool. [...]
You make it quite hard to give reasonable feedback to your code :-/ First you attack me personally here, then - 30 minutes later - in the next iteration of your patch, you do:
+ /* wait for each other cpu to see new table */
+ for_each_possible_cpu(i)
+ if (i != smp_processor_id()) {
+ xt_info_wrlock(i);
+ xt_info_wrunlock(i);
+ }
... which i have not seen in your previous patch and which looks awfully similar to the write_lock_wait() based primitive i suggested.
( Just open-coded in an ugly fashion and slower than a real, proper
wait-unlock would be, because it dirties all those locks needlessly. )
So you must have agreed with me to a certain degree - i just dont see that in any of the discussion. (you seem to totally disagree with me to the level of ridiculing me.) Which makes it hard to discuss this on a rational basis.
Quoted 1 line
Your version fails for the case of nested local rules. [...]
Yes, as Eric pointed it out, more than an hour before your reply. I find the nesting uninteresting (in fact i find it harmful - see my reply to Eric). If you were only interested in nesting then a plain old-fashioned rwlock would have done the job.
The detail that is interesting here is how to avoid the global rwlock cacheline bounce - not the recursion. (the same-CPU recursion is avoidable via proper design or workaround-able via a counter in so many ways)
Anyway, i'm back into lurker mode.
Ingo
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Stephen HemmingerQuoted 7 lines · Stephen Hemminger
net/netfilter/x_tables.c +7
-0+void xt_info_wrunlock_bh (void ) +__releases (xt_info_lock) +{ +unsigned int i; + +for_each_possible_cpu (i) { +#if NR_CPUS > (PREEMPT_MASK -1 )
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 702
Quoted 10 lines
net/netfilter/x_tables.c +10
-0+/* +* Spin_unlock calls preempt_enable, but since we had +* to adjust the count in xt_info_wrlock_bh, do it again +*/ +preempt_disable (); +#endif +write_unlock (&per_cpu (xt_info_locks, i)); + } +local_bh_enable (); +}
In the global/local lock scheme i proposed this would become:
global_write_unlock(void)
{
write_unlock(&global_lock);
}As we dont hold the local locks during the write-locked critical section. No loop needed over CPUs, no preempt nesting complications, no lockdep complications, etc.
Ingo
PATCH 1/1 netfilter: use per-cpu recursive lock (v13)
This version of x_tables (ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.
The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of synchronize_net() (in 2.6.30-rc2).
The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.
---
CHANGES
- reader and write now inline
- only acquire one cpu write lock at a time
- write lock pushed down into get_counters
include/linux/netfilter/x_tables.h | 50 +++++++++++++-- net/ipv4/netfilter/arp_tables.c | 121 ++++++++++--------------------------- net/ipv4/netfilter/ip_tables.c | 120 +++++++++--------------------------- net/ipv6/netfilter/ip6_tables.c | 120 ++++++++++-------------------------- net/netfilter/x_tables.c | 55 +++++++++------- 5 files changed, 174 insertions(+), 292 deletions(-)
include/linux/netfilter/x_tables.h +45 -5
@@ -354,9 +354,6 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -struct mutex lock; -/* Man behind the curtain... */ struct xt_table_info *private;
@@ -434,8 +431,51 @@ extern void xt_proto_fini(struct net *neextern 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); + + +/* +* Per-CPU read/write lock. This makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since write must iterate over all +* possible CPU's. Readers read lock their per-cpu lock, and writers +* write lock on all CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing rules +* all packets in flight have to be processed before rules are swapped, +* then counters are read from the old (stale) info. +* +*/ +DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +local_bh_disable (); +read_lock (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_rdunlock_bh (void ) +{ +read_unlock_bh (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_wrlock (unsigned int cpu) +{ +write_lock (&per_cpu (xt_info_locks, cpu)); +} + +static inline void xt_info_wrunlock (unsigned int cpu) +{ + +write_unlock (&per_cpu (xt_info_locks, cpu)); +}/* * This helper is performance critical and must be inlined
net/ipv4/netfilter/ip_tables.c +31 -89
204 lines not on this page · raw message
net/netfilter/x_tables.c +30 -25
96 lines not on this page · raw message
net/ipv6/netfilter/ip6_tables.c +35 -85
204 lines not on this page · raw message
net/ipv4/netfilter/arp_tables.c +33 -88
210 lines not on this page · raw message
Re: [PATCH] netfilter: use per-cpu recursive lock (v13)
Quoted 11 lines · Stephen Hemminger
This version of
x_tables(ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of
synchronize_net()(in 2.6.30-rc2).The mutex that was added for 2.6.30 in
xt_tableis unnecessary since there already is a mutex for xt[af].mutex that is held.
Looks good from a concurrency viewpoint!
Quoted 6 lines
Signed-off-by Stephen Hemminger <[email protected]---
CHANGES
- reader and write now inline
- only acquire one cpu write lock at a time
This is very good -- gets rid of problems with preemption nesting depth limitations and lockdep limitations. In addition, it gets rid of the period of time during which all packet processing might otherwise be blocked. Not a big deal on a small machine, but could be a real problem on a large one.
Very cool!!!
Quoted 45 lines
- write lock pushed down into
get_countersinclude/linux/netfilter/x_tables.h | 50 +++++++++++++-- net/ipv4/netfilter/arp_tables.c | 121 ++++++++++--------------------------- net/ipv4/netfilter/ip_tables.c | 120 +++++++++--------------------------- net/ipv6/netfilter/ip6_tables.c | 120 ++++++++++-------------------------- net/netfilter/x_tables.c | 55 +++++++++------- 5 files changed, 174 insertions(+), 292 deletions(-)include/linux/netfilter/x_tables.h +18
-5@@ -354,9 +354,6 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -struct mutex lock; -/* Man behind the curtain... */ struct xt_table_info *private;@@ -434,8 +431,51 @@ extern void xt_proto_fini(struct net *neextern 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); + + +/* +* Per-CPU read/write lock. This makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since write must iterate over all +* possible CPU's. Readers read lock their per-cpu lock, and writers +* write lock on all CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing rules
include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *ne · line 461
Quoted 10 lines
include/linux/netfilter/x_tables.h +10
-0+* all packets in flight have to be processed before rules are swapped, +* then counters are read from the old (stale) info. +* +*/ +DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +local_bh_disable (); +read_lock (&__get_cpu_var (xt_info_locks));
Good, you do indeed need to prevent migration before you acquire this CPU's lock. Otherwise, you could have more than one CPU attempting to update the same counter.
Quoted 47 lines
include/linux/netfilter/x_tables.h +17
-0+} + +static inline void xt_info_rdunlock_bh (void ) +{ +read_unlock_bh (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_wrlock (unsigned int cpu) +{ +write_lock (&per_cpu (xt_info_locks, cpu)); +} + +static inline void xt_info_wrunlock (unsigned int cpu) +{ + +write_unlock (&per_cpu (xt_info_locks, cpu)); +}/* * This helper is performance critical and must be inlined net/ipv4/netfilter/ip_tables.c +4
-6@@ -338,10 +338,9 @@ ipt_do_table(struct sk_buff *skb, tgpar.hooknum = hook;IP_NF_ASSERT (table->valid_hooks & (1 << hook)); - -rcu_read_lock_bh (); - private =rcu_dereference (table->private); - table_base =rcu_dereference (private->entries[smp_processor_id ()]); +xt_info_rdlock_bh (); + private = table->private; + table_base = private->entries[smp_processor_id ()]; e =get_entry (table_base, private->hook_entry[hook]);@@ -436,8 +435,7 @@ ipt_do_table(struct sk_buff *skb, e = (void *)e + e->next_offset; } }while (!hotdrop); - -rcu_read_unlock_bh (); +xt_info_rdunlock_bh ();#ifdef DEBUG_ALLOW_ALL return NF_ACCEPT ;
net/ipv4/netfilter/ip_tables.c get_counters(const struct xt_table_info · line 900
Quoted 4 lines
net/ipv4/netfilter/ip_tables.c +0
-1@@ -897,89 +895,39 @@ get_counters(const struct xt_table_info/* 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.
Good. Of course, the reason we care about preemption here is that otherwise some other task could mess up this CPU's counters.
Bad for real-time response, but then again, what the heck are you doing updating netfilter rules while a system is running a real-time workload?
Quoted 205 lines
net/ipv4/netfilter/ip_tables.c +27
-82*/ - curcpu =raw_smp_processor_id (); +local_bh_disable (); + curcpu =smp_processor_id (); i =0 ; +xt_info_wrlock (curcpu);IPT_ENTRY_ITERATE (t->entries[curcpu], t->size, set_entry_to_counter, counters, &i); +xt_info_wrunlock (curcpu);for_each_possible_cpu (cpu) {if (cpu == curcpu)continue ; i =0 ; +xt_info_wrlock (cpu);IPT_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, counters, &i); +xt_info_wrunlock (cpu); } - -} - -/* 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;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 @@ -988,30 +936,11 @@ static struct xt_counters * alloc_counte counters =vmalloc_node (countersize,numa_node_id ());if (counters ==NULL ) - goto nomem; +return ERR_PTR (-ENOMEM ); - 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); +get_counters (private, counters);return counters; - - free_counters: -vfree (counters); - nomem: -return ERR_PTR (-ENOMEM ); } static int@@ -1377,11 +1306,23 @@ 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) +{ +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) { -unsigned int i; +unsigned int i, curcpu;struct xt_counters_info tmp;struct xt_counters *paddc;unsigned int num_counters;@@ -1437,25 +1378,26 @@ do_add_counters(struct net *net, void __ goto free; } -mutex_lock (&t->lock); +local_bh_disable (); 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 ()]; + curcpu =smp_processor_id (); + loc_cpu_entry = private->entries[curcpu]; +xt_info_wrlock (curcpu);IPT_ENTRY_ITERATE (loc_cpu_entry, private->size, add_counter_to_entry, paddc, &i); -preempt_enable (); +xt_info_wrunlock (curcpu); unlock_up_free: -mutex_unlock (&t->lock); +local_bh_enable ();xt_table_unlock (t);module_put (t->me); free:net/netfilter/x_tables.c +0
-14@@ -625,20 +625,6 @@ 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)
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 666
Quoted 5 lines
net/netfilter/x_tables.c +2
-0@@ -676,32 +662,43 @@ void xt_compat_unlock(u_int8_t af)EXPORT_SYMBOL_GPL (xt_compat_unlock);#endif +DEFINE_PER_CPU (rwlock_t, xt_info_locks); +EXPORT_PER_CPU_SYMBOL_GPL (xt_info_locks);
Hmmm... Not sure I want to know what module uses this.
Ah, that is right -- a bunch of the comms stack can be built as a module.
Quoted 5 lines
net/netfilter/x_tables.c +2
-0+ +struct xt_table_info * xt_replace_table(struct xt_table *table, unsigned int num_counters,
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 679
Quoted 10 lines
net/netfilter/x_tables.c +3
-2struct xt_table_info *newinfo, int *error) { - struct xt_table_info *oldinfo, *private; + unsigned int i; +struct xt_table_info *private;/* Do the substitution. */ -mutex_lock (&table->lock); +local_bh_disable ();
Good, disabling preemption prevents other readers from messing with this CPU's local state.
Quoted 16 lines
net/netfilter/x_tables.c +1
-6private = 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); -mutex_unlock (&table->lock); +local_bh_enable (); *error = -EAGAIN ;return NULL ; } - oldinfo = private; -rcu_assign_pointer (table->private, newinfo); - newinfo->initial_entries = oldinfo->initial_entries; -mutex_unlock (&table->lock); -synchronize_net ();
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 698
Quoted 10 lines
net/netfilter/x_tables.c +9
-1-return oldinfo; + table->private = newinfo; + newinfo->initial_entries = private->initial_entries; + +/* wait for each other cpu to see new table */ +for_each_possible_cpu (i) +if (i !=smp_processor_id ()) { +xt_info_wrlock (i); +xt_info_wrunlock (i); + }
And the above loop acts sort of like a lock-based synchronize_rcu().
Quoted 57 lines
net/netfilter/x_tables.c +13
-2+local_bh_enable (); + +return private; }EXPORT_SYMBOL_GPL (xt_replace_table);@@ -734,7 +731,6 @@ struct xt_table *xt_register_table(struc/* Simplifies replace_table code. */ table->private = bootstrap; -mutex_init (&table->lock);if (!xt_replace_table (table,0 , newinfo, &ret)) goto unlock;@@ -1147,7 +1143,16 @@ static struct pernet_operations xt_net_ostatic int __init xt_init (void ) { -int i, rv; +unsigned int i; +int rv; +static struct lock_class_key xt_lock_key[NR_CPUS ]; + +for_each_possible_cpu (i) { +rwlock_t *lock = &per_cpu (xt_info_locks, i); + +rwlock_init (lock); +lockdep_set_class (lock, xt_lock_key+i); + } xt =kmalloc (sizeof (struct xt_af ) *NFPROTO_NUMPROTO ,GFP_KERNEL );if (!xt)net/ipv6/netfilter/ip6_tables.c +4
-4@@ -365,9 +365,9 @@ ip6t_do_table(struct sk_buff *skb,IP_NF_ASSERT (table->valid_hooks & (1 << hook)); -rcu_read_lock_bh (); - private =rcu_dereference (table->private); - table_base =rcu_dereference (private->entries[smp_processor_id ()]); +xt_info_rdlock_bh (); + private = table->private; + table_base = private->entries[smp_processor_id ()]; e =get_entry (table_base, private->hook_entry[hook]);@@ -466,7 +466,7 @@ ip6t_do_table(struct sk_buff *skb,#ifdef CONFIG_NETFILTER_DEBUG ((struct ip6t_entry *)table_base)->comefrom =NETFILTER_LINK_POISON ;#endif -rcu_read_unlock_bh (); +xt_info_rdunlock_bh ();#ifdef DEBUG_ALLOW_ALL return NF_ACCEPT ;
net/ipv6/netfilter/ip6_tables.c get_counters(const struct xt_table_info · line 931
Quoted 8 lines
net/ipv6/netfilter/ip6_tables.c +2
-2@@ -926,87 +926,40 @@ get_counters(const struct xt_table_info/* 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 (); +local_bh_disable (); + curcpu =smp_processor_id ();
Same story, but for IPv6.
Quoted 212 lines
net/ipv6/netfilter/ip6_tables.c +29
-79i =0 ; +xt_info_wrlock (curcpu);IP6T_ENTRY_ITERATE (t->entries[curcpu], t->size, set_entry_to_counter, counters, &i); +xt_info_wrunlock (curcpu); +for_each_possible_cpu (cpu) {if (cpu == curcpu)continue ; i =0 ; +xt_info_wrlock (cpu);IP6T_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, counters, &i); +xt_info_wrunlock (cpu); } -} - -/* 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;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 @@ -1015,30 +968,11 @@ static struct xt_counters *alloc_counter counters =vmalloc_node (countersize,numa_node_id ());if (counters ==NULL ) - goto nomem; - - info =xt_alloc_table_info (private->size); -if (!info) - goto free_counters; - -clone_counters (info, private); +return ERR_PTR (-ENOMEM ); -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); +get_counters (private, counters);return counters; - - free_counters: -vfree (counters); - nomem: -return ERR_PTR (-ENOMEM ); } static int@@ -1405,11 +1339,24 @@ 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 ip6t_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) { -unsigned int i; +unsigned int i, curcpu;struct xt_counters_info tmp;struct xt_counters *paddc;unsigned int num_counters;@@ -1465,25 +1412,28 @@ do_add_counters(struct net *net, void __ goto free; } -mutex_lock (&t->lock); + +local_bh_disable (); 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 ()]; + curcpu =smp_processor_id (); +xt_info_wrlock (curcpu); + loc_cpu_entry = private->entries[curcpu];IP6T_ENTRY_ITERATE (loc_cpu_entry, private->size, add_counter_to_entry, paddc, &i); -preempt_enable (); +xt_info_wrunlock (curcpu); + unlock_up_free: -mutex_unlock (&t->lock); +local_bh_enable ();xt_table_unlock (t);module_put (t->me); free:net/ipv4/netfilter/arp_tables.c +5
-5@@ -253,9 +253,9 @@ unsigned int arpt_do_table(struct sk_buf indev = in ? in->name : nulldevname; outdev = out ? out->name : nulldevname; -rcu_read_lock_bh (); - private =rcu_dereference (table->private); - table_base =rcu_dereference (private->entries[smp_processor_id ()]); +xt_info_rdlock_bh (); + private = table->private; + table_base = private->entries[smp_processor_id ()]; e =get_entry (table_base, private->hook_entry[hook]); back =get_entry (table_base, private->underflow[hook]);@@ -273,6 +273,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 ); t =arpt_get_target (e);@@ -328,8 +329,7 @@ unsigned int arpt_do_table(struct sk_buf e = (void *)e + e->next_offset; } }while (!hotdrop); - -rcu_read_unlock_bh (); +xt_info_rdunlock_bh ();if (hotdrop)return NF_DROP ;
net/ipv4/netfilter/arp_tables.c static void get_counters(const struct xt · line 715
Quoted 7 lines
net/ipv4/netfilter/arp_tables.c +1
-2@@ -711,88 +711,39 @@ static void get_counters(const struct xt/* 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 (); +local_bh_disable ();
Same story, but for ARP.
Quoted 178 lines
net/ipv4/netfilter/arp_tables.c +27
-81+ curcpu =smp_processor_id (); i =0 ; +xt_info_wrlock (curcpu);ARPT_ENTRY_ITERATE (t->entries[curcpu], t->size, set_entry_to_counter, counters, &i); +xt_info_wrunlock (curcpu);for_each_possible_cpu (cpu) {if (cpu == curcpu)continue ; i =0 ; +xt_info_wrlock (cpu);ARPT_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, counters, &i); +xt_info_wrunlock (cpu); } -} - - -/* 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;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 @@ -802,30 +753,11 @@ static struct xt_counters *alloc_counter counters =vmalloc_node (countersize,numa_node_id ());if (counters ==NULL ) - goto nomem; - - info =xt_alloc_table_info (private->size); -if (!info) - goto free_counters; - -clone_counters (info, private); +return ERR_PTR (-ENOMEM ); -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); +get_counters (private, counters);return counters; - - free_counters: -vfree (counters); - nomem: -return ERR_PTR (-ENOMEM ); } static int copy_entries_to_user(unsigned int total_size,@@ -1165,10 +1097,23 @@ static int do_replace(struct net *net, vreturn 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 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) { -unsigned int i; +unsigned int i, curcpu;struct xt_counters_info tmp;struct xt_counters *paddc;unsigned int num_counters;@@ -1224,26 +1169,26 @@ static int do_add_counters(struct net *n goto free; } -mutex_lock (&t->lock); +local_bh_disable (); 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 ()]; + curcpu =smp_processor_id (); + loc_cpu_entry = private->entries[curcpu]; +xt_info_wrlock (curcpu);ARPT_ENTRY_ITERATE (loc_cpu_entry, private->size, add_counter_to_entry, paddc, &i); -preempt_enable (); +xt_info_wrunlock (curcpu); unlock_up_free: -mutex_unlock (&t->lock); - +local_bh_enable ();xt_table_unlock (t);module_put (t->me); free:
Re: [PATCH] netfilter: use per-cpu recursive lock (v13)
In reply to Stephen HemmingerQuoted 9 lines · Stephen Hemminger
This version of
x_tables(ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of
synchronize_net()(in 2.6.30-rc2).
Quoted 4 lines
The mutex that was added for 2.6.30 in
xt_tableis unnecessary since there already is a mutex for xt[af].mutex that is held.Signed-off-by Stephen Hemminger <[email protected]
Tested today on various machines and no problem so far tbench/oprofile results, 3.7236% cpu spent in ipt_do_table, and 0.84% used on read_lock/read_unlock
c04a5c30 <ipt_do_table>: /* ipt_do_table total: 217134 3.7236 */
...
349 0.0060 :c04a5ccc: call c04ce380 <_read_lock>
23914 0.4101 :c04a5cd1: mov 0xc(%edi),%eax
...
:c04a5ecb: call c04ce5f0 <_read_unlock_bh>
25279 0.4335 :c04a5ed0: cmpb $0x0,-0xd(%ebp)"iptables -L" fetches its data very fast too.
150 us on a 8 cpus machine, small firewall rules.
400-700 us on same machine, 1000 fw rules set (160000 bytes per cpu)
depending on network trafic (from light to flood)
Thanks
Quoted 14 lines
---
CHANGES
- reader and write now inline
- only acquire one cpu write lock at a time
- write lock pushed down intoget_countersinclude/linux/netfilter/x_tables.h | 50 +++++++++++++-- net/ipv4/netfilter/arp_tables.c | 121 ++++++++++--------------------------- net/ipv4/netfilter/ip_tables.c | 120 +++++++++--------------------------- net/ipv6/netfilter/ip6_tables.c | 120 ++++++++++-------------------------- net/netfilter/x_tables.c | 55 +++++++++------- 5 files changed, 174 insertions(+), 292 deletions(-)
Re: [PATCH] netfilter: use per-cpu recursive lock (v13)
In reply to Stephen HemmingerQuoted 3 lines · Stephen Hemminger
This version of
x_tables(ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.
Ack on the code.
But the comment is _still_ crap. Please update. It's not a recursive lock, as clearly shown by the code itself. It's a per-cpu read-write lock, and only the reader is "recursive" (but that's how read-write locks with in Linux, and that has nothing to do with anything).
So make the explanations match the code and the intent. Write it something like
This version of x_tables (ip/ip6/arp) locking uses a per-cpu reader-writer lock lock where the readers can nest.
and don't confuse it with incorrect commit messages. The lock is very much not recursive - on purpose - for half the people taking it.
[ That, btw, was always true, even in the original random open-coded
version. Because you can't actually do a real recursive lock without having notion of "current ownership" either by making the count be <per-thread,per-lock> - like the BKL - or by saving the ownership information in the lock. A plain counter simply doesn't do it. ]
Linus
PATCH 1/1 netfilter: use per-CPU recursive lock {XIV}
In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.
But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.
So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.
The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.
---
What hath changed over the last two setting suns:
* more words, mostly correct...
* no need to locketh for writeh on current cpu tis always so
* the locking of all cpu's on replace is always done as part of the get_counters cycle, so the sychronize swip in replace tables is gone with only a comment remaing
include/linux/netfilter/x_tables.h | 55 ++++++++++++++-- net/ipv4/netfilter/arp_tables.c | 125 ++++++++++-------------------------- net/ipv4/netfilter/ip_tables.c | 126 ++++++++++--------------------------- net/ipv6/netfilter/ip6_tables.c | 123 ++++++++++-------------------------- net/netfilter/x_tables.c | 55 ++++++++-------- 5 files changed, 188 insertions(+), 296 deletions(-)
include/linux/netfilter/x_tables.h +50 -5
@@ -354,9 +354,6 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -struct mutex lock; -/* Man behind the curtain... */ struct xt_table_info *private;
@@ -434,8 +431,56 @@ extern void xt_proto_fini(struct net *neextern 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); + +/* +* Per-CPU read/write lock associated with per-cpu table entries. +* This is not a general solution but makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since update must lock all +* possible CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. In some cases, the read lock will be acquired +* twice on the same CPU; this is okay because read locks handle nesting. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing tables +* any readers that are using the old tables have to complete +* before freeing the old table. This is handled by reading +* as a side effect of reading counters +*/ +DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +/* +* Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks)) +* because need to ensure that preemption is disable before +* acquiring per-cpu-variable, so do it as a two step process +*/ +local_bh_disable (); +read_lock (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_rdunlock_bh (void ) +{ +read_unlock_bh (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_wrlock (unsigned int cpu) +{ +write_lock (&per_cpu (xt_info_locks, cpu)); +} + +static inline void xt_info_wrunlock (unsigned int cpu) +{ + +write_unlock (&per_cpu (xt_info_locks, cpu)); +}/* * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +36 -89
215 lines not on this page · raw message
net/ipv4/netfilter/ip_tables.c +35 -91
211 lines not on this page · raw message
net/ipv6/netfilter/ip6_tables.c +37 -86
208 lines not on this page · raw message
net/netfilter/x_tables.c +30 -25
96 lines not on this page · raw message
Re: [PATCH] netfilter: use per-CPU recursive lock {XIV}
Quoted 14 lines · Stephen Hemminger
In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.
But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.
So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.
Quoted 7 lines
The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.
Signed-off-by Stephen Hemminger <[email protected]>
Philip Davis of the university’s School of English said :
"Shakespeare surprises the brain and catches it off guard in a manner that produces a sudden burst of activity - a sense of drama created out of the simplest of things."
http://www.physorg.com/news85664210.html
Quoted 24 lines
---
What hath changed over the last two setting suns:
* more words, mostly correct...* no need to locketh for writeh on current cpu tis always so
* the locking of all cpu's on replace is always done as part of the
get_counterscycle, so the sychronize swip in replace tables is gone with only a comment remainginclude/linux/netfilter/x_tables.h | 55 ++++++++++++++-- net/ipv4/netfilter/arp_tables.c | 125 ++++++++++-------------------------- net/ipv4/netfilter/ip_tables.c | 126 ++++++++++--------------------------- net/ipv6/netfilter/ip6_tables.c | 123 ++++++++++-------------------------- net/netfilter/x_tables.c | 55 ++++++++-------- 5 files changed, 188 insertions(+), 296 deletions(-)static int
__initxt_init(void)
{
net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1148
Quoted 4 lines
net/netfilter/x_tables.c +3
-1-int i, rv; +unsigned int i; +int rv; +static struct lock_class_key xt_lock_key[NR_CPUS ];
Could we avoid this [NR_CPUS] thing ?
net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1155
Quoted 7 lines
net/netfilter/x_tables.c +7
-0+ +for_each_possible_cpu (i) { +rwlock_t *lock = &per_cpu (xt_info_locks, i); + +rwlock_init (lock); +lockdep_set_class (lock, xt_lock_key+i); + }
Did you tried :
static DECLARE_PER_CPU(struct lock_class_key, xt_locks_key);
static int __init xt_init(void)
{
unsigned int i;
int rv;
for_each_possible_cpu(i) {
rwlock_t *lock = &per_cpu(xt_info_locks, i);
rwlock_init(lock);
lockdep_set_class(lock, &per_cpu(&xt_locks_key, i));
}...
Thanks
Re: [PATCH] netfilter: use per-CPU recursive lock {XIV}
Quoted 14 lines · Eric Dumazet
Quoted 13 lines · Stephen Hemminger
In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant
did replace the tables. This sucketh and caused the single
lock to fly back and forth like a poor errant boy.But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.
So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.
Quoted 5 lines
Quoted 5 lines
The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.
Hehe.
Quoted 20 lines
net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1148
Quoted 6 lines
static int
__initxt_init(void)
{net/netfilter/x_tables.c +3
-1-int i, rv; +unsigned int i; +int rv; +static struct lock_class_key xt_lock_key[NR_CPUS ];Could we avoid this [
NR_CPUS] thing ?net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1155
Quoted 7 lines
net/netfilter/x_tables.c +7
-0+ +for_each_possible_cpu (i) { +rwlock_t *lock = &per_cpu (xt_info_locks, i); + +rwlock_init (lock); +lockdep_set_class (lock, xt_lock_key+i); + }Did you tried :
Quoted 1 line
static
DECLARE_PER_CPU(struct lock_class_key, xt_locks_key);
Either way is fine with me, I'll wait for Stephen to state his opinion. --
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-CPU recursive lock {XIV}
In reply to Eric DumazetQuoted 74 lines · On Fri, 24 Apr 2009 06:58:39 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 14 lines · Stephen Hemminger
In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.
But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.
So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.
Quoted 7 lines
The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.
Signed-off-by Stephen Hemminger <[email protected]>Philip Davis of the university’s School of English said :
"Shakespeare surprises the brain and catches it off guard in a manner that produces a sudden burst of activity - a sense of drama created out of the simplest of things."
http://www.physorg.com/news85664210.html
Quoted 24 lines
---
What hath changed over the last two setting suns:
* more words, mostly correct...* no need to locketh for writeh on current cpu tis always so
* the locking of all cpu's on replace is always done as part of the
get_counterscycle, so the sychronize swip in replace tables is gone with only a comment remainginclude/linux/netfilter/x_tables.h | 55 ++++++++++++++-- net/ipv4/netfilter/arp_tables.c | 125 ++++++++++-------------------------- net/ipv4/netfilter/ip_tables.c | 126 ++++++++++--------------------------- net/ipv6/netfilter/ip6_tables.c | 123 ++++++++++-------------------------- net/netfilter/x_tables.c | 55 ++++++++-------- 5 files changed, 188 insertions(+), 296 deletions(-)static int
__initxt_init(void)
{net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1148
Quoted 4 lines
net/netfilter/x_tables.c +3
-1-int i, rv; +unsigned int i; +int rv; +static struct lock_class_key xt_lock_key[NR_CPUS ];Could we avoid this [
NR_CPUS] thing ?net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1155
Quoted 7 lines
net/netfilter/x_tables.c +7
-0+ +for_each_possible_cpu (i) { +rwlock_t *lock = &per_cpu (xt_info_locks, i); + +rwlock_init (lock); +lockdep_set_class (lock, xt_lock_key+i); + }Did you tried :
Quoted 2 lines
static
DECLARE_PER_CPU(struct lock_class_key, xt_locks_key);
The lock keys are really only used by lock dep, and I thought per cpu space was more scarce on some arch.
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-CPU recursive lock {XIV}
Stephen Hemminger wrote, On 04/24/2009 06:18 PM:
Quoted 72 lines
Quoted 69 lines · On Fri, 24 Apr 2009 06:58:39 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 14 lines · Stephen Hemminger
In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.
But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.
So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.
Quoted 7 lines
The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.
Signed-off-by Stephen Hemminger <[email protected]>Philip Davis of the university’s School of English said :
"Shakespeare surprises the brain and catches it off guard in a manner that produces a sudden burst of activity - a sense of drama created out of the simplest of things."
http://www.physorg.com/news85664210.html
Quoted 22 lines
---
What hath changed over the last two setting suns:
* more words, mostly correct...* no need to locketh for writeh on current cpu tis always so
* the locking of all cpu's on replace is always done as part of the
get_counterscycle, so the sychronize swip in replace tables is gone with only a comment remainginclude/linux/netfilter/x_tables.h | 55 ++++++++++++++-- net/ipv4/netfilter/arp_tables.c | 125 ++++++++++-------------------------- net/ipv4/netfilter/ip_tables.c | 126 ++++++++++--------------------------- net/ipv6/netfilter/ip6_tables.c | 123 ++++++++++-------------------------- net/netfilter/x_tables.c | 55 ++++++++-------- 5 files changed, 188 insertions(+), 296 deletions(-)static int
__initxt_init(void)
{net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1148
Quoted 4 lines
net/netfilter/x_tables.c +3
-1-int i, rv; +unsigned int i; +int rv; +static struct lock_class_key xt_lock_key[NR_CPUS ];Could we avoid this [
NR_CPUS] thing ?net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1155
Quoted 7 lines
net/netfilter/x_tables.c +7
-0+ +for_each_possible_cpu (i) { +rwlock_t *lock = &per_cpu (xt_info_locks, i); + +rwlock_init (lock); +lockdep_set_class (lock, xt_lock_key+i); + }Did you tried :
Quoted 6 lines
Quoted 2 lines
static
DECLARE_PER_CPU(struct lock_class_key, xt_locks_key);The lock keys are really only used by lock dep, and I thought per cpu space was more scarce on some arch.
Maybe I'm wrong but after this change: "- only acquire one cpu write lock at a time" lockdep_set_class() might be unnecessary. Alas I'm not able to test it.
Jarek P.
PATCH 1/1 netfilter: iptables no lockdep is needed..
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
--- net/netfilter/x_tables.c | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-)
net/netfilter/x_tables.c +2 -7
@@ -1145,14 +1145,9 @@ static int __init xt_init(void) {unsigned int i;int rv; -static struct lock_class_key xt_lock_key[NR_CPUS ]; -for_each_possible_cpu (i) { -rwlock_t *lock = &per_cpu (xt_info_locks, i); - -rwlock_init (lock); -lockdep_set_class (lock, xt_lock_key+i); - } +for_each_possible_cpu (i) +rwlock_init (&per_cpu (xt_info_locks, i)); xt =kmalloc (sizeof (struct xt_af ) *NFPROTO_NUMPROTO ,GFP_KERNEL );if (!xt)
Re: [PATCH] netfilter: iptables no lockdep is needed..
Quoted 4 lines · Stephen Hemminger
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>
Very nice! I guess this Shakespeare guy Will sign off this all too. ;-)
Thanks,
Jarek P.
Quoted 24 lines
--- net/netfilter/x_tables.c | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-)net/netfilter/x_tables.c +2
-7@@ -1145,14 +1145,9 @@ static int __init xt_init(void) {unsigned int i;int rv; -static struct lock_class_key xt_lock_key[NR_CPUS ]; -for_each_possible_cpu (i) { -rwlock_t *lock = &per_cpu (xt_info_locks, i); - -rwlock_init (lock); -lockdep_set_class (lock, xt_lock_key+i); - } +for_each_possible_cpu (i) +rwlock_init (&per_cpu (xt_info_locks, i)); xt =kmalloc (sizeof (struct xt_af ) *NFPROTO_NUMPROTO ,GFP_KERNEL );if (!xt)
PATCH 1/1 netfilter: use per-CPU recursive lock {XV}
In reply to Stephen HemmingerFrom: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>
So far, so good, should be ready for inclusion now, nobody complained :)
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
Thanks to all for your help and patience
[PATCH] netfilter: use per-CPU recursive lock {XV}
In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.
But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.
So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.
The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.
---
What hath changed over the last two setting suns:
* more words, mostly correct...
* no need to locketh for writeh on current cpu tis always so
* the locking of all cpu's on replace is always done as part of the get_counters cycle, so the sychronize swip in replace tables is gone with only a comment remaing
* Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
include/linux/netfilter/x_tables.h | 55 ++++++++++- net/ipv4/netfilter/arp_tables.c | 125 +++++++------------------- net/ipv4/netfilter/ip_tables.c | 126 +++++++-------------------- net/ipv6/netfilter/ip6_tables.c | 123 +++++++------------------- net/netfilter/x_tables.c | 50 +++++----- 5 files changed, 183 insertions(+), 296 deletions(-)
include/linux/netfilter/x_tables.h +50 -5
@@ -354,9 +354,6 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -struct mutex lock; -/* Man behind the curtain... */ struct xt_table_info *private;
@@ -434,8 +431,56 @@ extern void xt_proto_fini(struct net *net, u_int8_t af);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); + +/* +* Per-CPU read/write lock associated with per-cpu table entries. +* This is not a general solution but makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since update must lock all +* possible CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. In some cases, the read lock will be acquired +* twice on the same CPU; this is okay because read locks handle nesting. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing tables +* any readers that are using the old tables have to complete +* before freeing the old table. This is handled by reading +* as a side effect of reading counters +*/ +DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +/* +* Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks)) +* because need to ensure that preemption is disable before +* acquiring per-cpu-variable, so do it as a two step process +*/ +local_bh_disable (); +read_lock (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_rdunlock_bh (void ) +{ +read_unlock_bh (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_wrlock (unsigned int cpu) +{ +write_lock (&per_cpu (xt_info_locks, cpu)); +} + +static inline void xt_info_wrunlock (unsigned int cpu) +{ + +write_unlock (&per_cpu (xt_info_locks, cpu)); +}/* * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +36 -89
215 lines not on this page · raw message
net/ipv4/netfilter/ip_tables.c +35 -91
211 lines not on this page · raw message
net/ipv6/netfilter/ip6_tables.c +37 -86
208 lines not on this page · raw message
net/netfilter/x_tables.c +25 -25
91 lines not on this page · raw message
Re: [PATCH] netfilter: use per-CPU recursive lock {XV}
Quoted 9 lines · * Eric Dumazet ([email protected]) wrote:
From: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>So far, so good, should be ready for inclusion now, nobody complained :)
Quoted 7 lines
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
Thanks to all for your help and patience
[PATCH] netfilter: use per-CPU recursive lock {XV}
Hi Eric,
Please... could you rename this patch according to Linus'comments ?
Suitable name would probably be :
[PATCH] netfilter: use bh disabling with per-cpu read-write lock
Quoted 76 lines
In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.
But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.
So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.
The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.
Signed-off-by Stephen Hemminger <[email protected]>Signed-off-by Eric Dumazet <[email protected]>---
What hath changed over the last two setting suns:* more words, mostly correct...
* no need to locketh for writeh on current cpu tis always so
* the locking of all cpu's on replace is always done as part of the
get_counterscycle, so the sychronize swip in replace tables is gone with only a comment remaing* Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
include/linux/netfilter/x_tables.h | 55 ++++++++++- net/ipv4/netfilter/arp_tables.c | 125 +++++++------------------- net/ipv4/netfilter/ip_tables.c | 126 +++++++-------------------- net/ipv6/netfilter/ip6_tables.c | 123 +++++++------------------- net/netfilter/x_tables.c | 50 +++++----- 5 files changed, 183 insertions(+), 296 deletions(-)include/linux/netfilter/x_tables.h +11
-5@@ -354,9 +354,6 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -struct mutex lock; -/* Man behind the curtain... */ struct xt_table_info *private;@@ -434,8 +431,56 @@ extern void xt_proto_fini(struct net *net, u_int8_t af);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); + +/* +* Per-CPU read/write lock associated with per-cpu table entries. +* This is not a general solution but makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since update must lock all +* possible CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. In some cases, the read lock will be acquired
include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 454
Quoted 10 lines
include/linux/netfilter/x_tables.h +10
-0+* twice on the same CPU; this is okay because read locks handle nesting. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing tables +* any readers that are using the old tables have to complete +* before freeing the old table. This is handled by reading +* as a side effect of reading counters
Stating that the write lock must _always_ be taken with bh disabled might not hurt here.
Quoted 50 lines
include/linux/netfilter/x_tables.h +29
-0+*/ +DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +/* +* Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks)) +* because need to ensure that preemption is disable before +* acquiring per-cpu-variable, so do it as a two step process +*/ +local_bh_disable (); +read_lock (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_rdunlock_bh (void ) +{ +read_unlock_bh (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_wrlock (unsigned int cpu) +{ +write_lock (&per_cpu (xt_info_locks, cpu)); +} + +static inline void xt_info_wrunlock (unsigned int cpu) +{ + +write_unlock (&per_cpu (xt_info_locks, cpu)); +}/* * This helper is performance critical and must be inlined net/ipv4/netfilter/arp_tables.c +3
-3@@ -253,9 +253,9 @@ unsigned int arpt_do_table(struct sk_buff *skb, indev = in ? in->name : nulldevname; outdev = out ? out->name : nulldevname; -rcu_read_lock_bh (); - private =rcu_dereference (table->private); - table_base =rcu_dereference (private->entries[smp_processor_id ()]); +xt_info_rdlock_bh (); + private = table->private; + table_base = private->entries[smp_processor_id ()]; e =get_entry (table_base, private->hook_entry[hook]); back =get_entry (table_base, private->underflow[hook]);
net/ipv4/netfilter/arp_tables.c unsigned int arpt_do_table(struct sk_buff *skb, · line 276
Quoted 4 lines
net/ipv4/netfilter/arp_tables.c +1
-0@@ -273,6 +273,7 @@ unsigned int arpt_do_table(struct sk_buff *skb, hdr_len =sizeof (*arp) + (2 *sizeof (struct in_addr )) + (2 * skb->dev->addr_len); +
This is not a whitespace cleanup patch.
net/ipv4/netfilter/arp_tables.c unsigned int arpt_do_table(struct sk_buff *skb, · line 331
Quoted 8 lines
net/ipv4/netfilter/arp_tables.c +0
-1ADD_COUNTER (e->counters, hdr_len,1 ); t =arpt_get_target (e);@@ -328,8 +329,7 @@ unsigned int arpt_do_table(struct sk_buff *skb, e = (void *)e + e->next_offset; } }while (!hotdrop); -
Whitespace cleanup ?
Quoted 54 lines
net/ipv4/netfilter/arp_tables.c +8
-25-rcu_read_unlock_bh (); +xt_info_rdunlock_bh ();if (hotdrop)return NF_DROP ;@@ -711,9 +711,12 @@ static void get_counters(const struct xt_table_info *t,/* 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. +* +* Bottom half has to be disabled to prevent deadlock +* if new softirq were to run and call ipt_do_table */ - curcpu =raw_smp_processor_id (); +local_bh_disable (); + curcpu =smp_processor_id (); i =0 ; ARPT_ENTRY_ITERATE(t->entries[curcpu],@@ -726,73 +729,22 @@ static void get_counters(const struct xt_table_info *t,if (cpu == curcpu)continue ; i =0 ; +xt_info_wrlock (cpu);ARPT_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, counters, &i); +xt_info_wrunlock (cpu); } -} - - -/* 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; -
net/ipv4/netfilter/arp_tables.c static void get_counters(const struct xt_table_info *t, · line 741
Quoted 10 lines
net/ipv4/netfilter/arp_tables.c +0
-8-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 (); }
Did you really need to move add_counter_to_entry and put_counters in this patch ? This also seems more like a cleanup to me, if it is even one. It does make the patch harder to follow though.
Quoted 544 lines
net/ipv4/netfilter/arp_tables.c +24
-52-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;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 @@ -802,30 +754,11 @@ static struct xt_counters *alloc_counters(struct xt_table *table) counters =vmalloc_node (countersize,numa_node_id ());if (counters ==NULL ) - goto nomem; - - 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 */ +return ERR_PTR (-ENOMEM ); -get_counters (info, counters); -put_counters (private, counters); -mutex_unlock (&table->lock); - -xt_free_table_info (info); +get_counters (private, counters);return counters; - - free_counters: -vfree (counters); - nomem: -return ERR_PTR (-ENOMEM ); } static int copy_entries_to_user(unsigned int total_size,@@ -1094,8 +1027,9 @@ static int __do_replace(struct net *net, const char *name, (newinfo->number <= oldinfo->initial_entries))module_put (t->me); -/* Get the old counters. */ +/* Get the old counters, and synchronize with replace */ get_counters (oldinfo, counters); +/* Decrease module usage counts and free resource */ loc_cpu_old_entry = oldinfo->entries[raw_smp_processor_id ()]; ARPT_ENTRY_ITERATE(loc_cpu_old_entry, oldinfo->size, cleanup_entry,@@ -1165,10 +1099,23 @@ static int do_replace(struct net *net, void __user *user, unsigned int len)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 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) { -unsigned int i; +unsigned int i, curcpu;struct xt_counters_info tmp;struct xt_counters *paddc;unsigned int num_counters;@@ -1224,26 +1171,26 @@ static int do_add_counters(struct net *net, void __user *user, unsigned int len, goto free; } -mutex_lock (&t->lock); +local_bh_disable (); 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 ()]; + curcpu =smp_processor_id (); + loc_cpu_entry = private->entries[curcpu]; +xt_info_wrlock (curcpu);ARPT_ENTRY_ITERATE (loc_cpu_entry, private->size, add_counter_to_entry, paddc, &i); -preempt_enable (); +xt_info_wrunlock (curcpu); unlock_up_free: -mutex_unlock (&t->lock); - +local_bh_enable ();xt_table_unlock (t);module_put (t->me); free:net/ipv4/netfilter/ip_tables.c +35
-91@@ -338,10 +338,9 @@ ipt_do_table(struct sk_buff *skb, tgpar.hooknum = hook;IP_NF_ASSERT (table->valid_hooks & (1 << hook)); - -rcu_read_lock_bh (); - private =rcu_dereference (table->private); - table_base =rcu_dereference (private->entries[smp_processor_id ()]); +xt_info_rdlock_bh (); + private = table->private; + table_base = private->entries[smp_processor_id ()]; e =get_entry (table_base, private->hook_entry[hook]);@@ -436,8 +435,7 @@ ipt_do_table(struct sk_buff *skb, e = (void *)e + e->next_offset; } }while (!hotdrop); - -rcu_read_unlock_bh (); +xt_info_rdunlock_bh ();#ifdef DEBUG_ALLOW_ALL return NF_ACCEPT ;@@ -896,10 +894,13 @@ get_counters(const struct xt_table_info *t,/* 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. +* with data used by 'current' CPU. +* +* Bottom half has to be disabled to prevent deadlock +* if new softirq were to run and call ipt_do_table */ - curcpu =raw_smp_processor_id (); +local_bh_disable (); + curcpu =smp_processor_id (); i =0 ; IPT_ENTRY_ITERATE(t->entries[curcpu],@@ -912,74 +913,22 @@ get_counters(const struct xt_table_info *t,if (cpu == curcpu)continue ; i =0 ; +xt_info_wrlock (cpu);IPT_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, counters, &i); +xt_info_wrunlock (cpu); } - -} - -/* 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;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 @@ -988,30 +937,11 @@ static struct xt_counters * alloc_counters(struct xt_table *table) counters =vmalloc_node (countersize,numa_node_id ());if (counters ==NULL ) - goto nomem; +return ERR_PTR (-ENOMEM ); - 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); +get_counters (private, counters);return counters; - - free_counters: -vfree (counters); - nomem: -return ERR_PTR (-ENOMEM ); } static int@@ -1306,8 +1236,9 @@ __do_replace(struct net *net, const char *name, unsigned int valid_hooks, (newinfo->number <= oldinfo->initial_entries))module_put (t->me); -/* Get the old counters. */ +/* Get the old counters, and synchronize with replace */ 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,@@ -1377,11 +1308,23 @@ do_replace(struct net *net, void __user *user, unsigned int len)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) +{ +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) { -unsigned int i; +unsigned int i, curcpu;struct xt_counters_info tmp;struct xt_counters *paddc;unsigned int num_counters;@@ -1437,25 +1380,26 @@ do_add_counters(struct net *net, void __user *user, unsigned int len, int compat goto free; } -mutex_lock (&t->lock); +local_bh_disable (); 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 ()]; + curcpu =smp_processor_id (); + loc_cpu_entry = private->entries[curcpu]; +xt_info_wrlock (curcpu);IPT_ENTRY_ITERATE (loc_cpu_entry, private->size, add_counter_to_entry, paddc, &i); -preempt_enable (); +xt_info_wrunlock (curcpu); unlock_up_free: -mutex_unlock (&t->lock); +local_bh_enable ();xt_table_unlock (t);module_put (t->me); free:net/ipv6/netfilter/ip6_tables.c +29
-81@@ -365,9 +365,9 @@ ip6t_do_table(struct sk_buff *skb,IP_NF_ASSERT (table->valid_hooks & (1 << hook)); -rcu_read_lock_bh (); - private =rcu_dereference (table->private); - table_base =rcu_dereference (private->entries[smp_processor_id ()]); +xt_info_rdlock_bh (); + private = table->private; + table_base = private->entries[smp_processor_id ()]; e =get_entry (table_base, private->hook_entry[hook]);@@ -466,7 +466,7 @@ ip6t_do_table(struct sk_buff *skb,#ifdef CONFIG_NETFILTER_DEBUG ((struct ip6t_entry *)table_base)->comefrom =NETFILTER_LINK_POISON ;#endif -rcu_read_unlock_bh (); +xt_info_rdunlock_bh ();#ifdef DEBUG_ALLOW_ALL return NF_ACCEPT ;@@ -926,9 +926,12 @@ get_counters(const struct xt_table_info *t,/* 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. +* +* Bottom half has to be disabled to prevent deadlock +* if new softirq were to run and call ipt_do_table */ - curcpu =raw_smp_processor_id (); +local_bh_disable (); + curcpu =smp_processor_id (); i =0 ; IP6T_ENTRY_ITERATE(t->entries[curcpu],@@ -941,72 +944,22 @@ get_counters(const struct xt_table_info *t,if (cpu == curcpu)continue ; i =0 ; +xt_info_wrlock (cpu);IP6T_ENTRY_ITERATE (t->entries[cpu], t->size, add_entry_to_counter, counters, &i); +xt_info_wrunlock (cpu); } -} - -/* 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;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 @@ -1015,30 +968,11 @@ static struct xt_counters *alloc_counters(struct xt_table *table) counters =vmalloc_node (countersize,numa_node_id ());if (counters ==NULL ) - goto nomem; +return ERR_PTR (-ENOMEM ); - 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); +get_counters (private, counters);return counters; - - free_counters: -vfree (counters); - nomem: -return ERR_PTR (-ENOMEM ); } static int@@ -1334,8 +1268,9 @@ __do_replace(struct net *net, const char *name, unsigned int valid_hooks, (newinfo->number <= oldinfo->initial_entries))module_put (t->me); -/* Get the old counters. */ +/* Get the old counters, and synchronize with replace */ get_counters (oldinfo, counters); +/* Decrease module usage counts and free resource */ loc_cpu_old_entry = oldinfo->entries[raw_smp_processor_id ()]; IP6T_ENTRY_ITERATE(loc_cpu_old_entry, oldinfo->size, cleanup_entry,@@ -1405,11 +1340,24 @@ do_replace(struct net *net, void __user *user, unsigned int len)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 ip6t_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) { -unsigned int i; +unsigned int i, curcpu;struct xt_counters_info tmp;struct xt_counters *paddc;unsigned int num_counters;
net/ipv6/netfilter/ip6_tables.c do_add_counters(struct net *net, void __user *user, unsigned int len, · line 1416
Quoted 5 lines
net/ipv6/netfilter/ip6_tables.c +1
-1@@ -1465,25 +1413,28 @@ do_add_counters(struct net *net, void __user *user, unsigned int len, goto free; } -mutex_lock (&t->lock); +
Incorrect whiteline added.
Quoted 12 lines
net/ipv6/netfilter/ip6_tables.c +2
-2+local_bh_disable (); 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 ()]; + curcpu =smp_processor_id ();
net/ipv6/netfilter/ip6_tables.c do_add_counters(struct net *net, void __user *user, unsigned int len, · line 1435
Quoted 10 lines
net/ipv6/netfilter/ip6_tables.c +4
-1+xt_info_wrlock (curcpu); + loc_cpu_entry = private->entries[curcpu];IP6T_ENTRY_ITERATE (loc_cpu_entry, private->size, add_counter_to_entry, paddc, &i); -preempt_enable (); +xt_info_wrunlock (curcpu); +
Inconsistent whiteline.
Quoted 57 lines
net/ipv6/netfilter/ip6_tables.c +1
-1unlock_up_free: -mutex_unlock (&t->lock); +local_bh_enable ();xt_table_unlock (t);module_put (t->me); free:net/netfilter/x_tables.c +7
-16@@ -625,20 +625,6 @@ void xt_free_table_info(struct xt_table_info *info) }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)@@ -676,32 +662,43 @@ void xt_compat_unlock(u_int8_t af)EXPORT_SYMBOL_GPL (xt_compat_unlock);#endif +DEFINE_PER_CPU (rwlock_t, xt_info_locks); +EXPORT_PER_CPU_SYMBOL_GPL (xt_info_locks); + +struct xt_table_info *xt_replace_table (struct xt_table *table,unsigned int num_counters,struct xt_table_info *newinfo,int *error) { -struct xt_table_info *oldinfo, *private; +struct xt_table_info *private;/* Do the substitution. */ -mutex_lock (&table->lock); +local_bh_disable (); 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);
net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 689
Quoted 10 lines
net/netfilter/x_tables.c +1
-5-mutex_unlock (&table->lock); +local_bh_enable (); *error = -EAGAIN ;return NULL ; } - oldinfo = private; -rcu_assign_pointer (table->private, newinfo); - newinfo->initial_entries = oldinfo->initial_entries; -mutex_unlock (&table->lock);
Whiteline.....
Mathieu
Quoted 38 lines
net/netfilter/x_tables.c +17
-4-synchronize_net (); -return oldinfo; + table->private = newinfo; + newinfo->initial_entries = private->initial_entries; + +/* +* Even though table entries have now been swapped, other CPU's +* may still be using the old entries. This is okay, because +* resynchronization happens because of the locking done +* during the get_counters() routine. +*/ +local_bh_enable (); + +return private; }EXPORT_SYMBOL_GPL (xt_replace_table);@@ -734,7 +731,6 @@ struct xt_table *xt_register_table(struct net *net, struct xt_table *table,/* Simplifies replace_table code. */ table->private = bootstrap; -mutex_init (&table->lock);if (!xt_replace_table (table,0 , newinfo, &ret)) goto unlock;@@ -1147,7 +1143,11 @@ static struct pernet_operations xt_net_ops = {static int __init xt_init (void ) { -int i, rv; +unsigned int i; +int rv; + +for_each_possible_cpu (i) +rwlock_init (&per_cpu (xt_info_locks, i)); xt =kmalloc (sizeof (struct xt_af ) *NFPROTO_NUMPROTO ,GFP_KERNEL );if (!xt)
Signature · 2 lines
Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
Re: [PATCH] netfilter: use per-CPU recursive lock {XV}
Quoted 14 lines · On Sun, 26 Apr 2009 14:56:46 -0400 Mathieu Desnoyers…
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:
From: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>So far, so good, should be ready for inclusion now, nobody complained :)
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
Quoted 8 lines
Quoted 3 lines
Thanks to all for your help and patience
[PATCH] netfilter: use per-CPU recursive lock {XV}
Hi Eric,
Suitable name would probably be :
But Linus is trying to delude himself.
This usage is recursive even if he doesn't like the terminology. The same CPU has to be able to reacquire the read lock without deadlocking. If reader/writer locks were implemented in a pure writer gets priority method, then this code would break! So yes read locks can be used recursively now in Linux, but if the were implemented differently then this code would break. For example, the -rt kernel turns all read/write locks into mutexs, so the -rt kernel developers will have to address this.
Re: [PATCH] netfilter: use per-CPU recursive lock {XV}
Quoted 17 lines · * Stephen Hemminger ([email protected]) wrote:
Quoted 14 lines · On Sun, 26 Apr 2009 14:56:46 -0400 Mathieu Desnoyers…
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:
From: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>So far, so good, should be ready for inclusion now, nobody complained :)
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
Quoted 8 lines
Quoted 8 lines
Quoted 3 lines
Thanks to all for your help and patience
[PATCH] netfilter: use per-CPU recursive lock {XV}
Hi Eric,
Suitable name would probably be :
Hi Stephen,
[I see that you have cutted my name proposal from the original email, which might make it difficult for others to follow. I will assume you did it by mistake.]
(re-added)
[PATCH] netfilter: use bh disabling with per-cpu read-write lock
Quoted 10 lines
But Linus is trying to delude himself.
This usage is recursive even if he doesn't like the terminology. The same CPU has to be able to reacquire the read lock without deadlocking. If reader/writer locks were implemented in a pure writer gets priority method, then this code would break! So yes read locks can be used recursively now in Linux, but if the were implemented differently then this code would break. For example, the -rt kernel turns all read/write locks into mutexs, so the -rt kernel developers will have to address this.
Reading Documentation/spinlocks.txt, which states the lock usage guidelines :
"Note that you can be clever with read-write locks and interrupts. For example, if you know that the interrupt only ever gets a read-lock, then you can use a non-irq version of read locks everywhere - because they don't block on each other (and thus there is no dead-lock wrt interrupts. But when you do the write-lock, you have to use the irq-safe version."
So it's assumed in the kernel-wide read lock usage that nested read locks are OK. I'm adding Thomas and Steven in CC, but I'm quite sure they must have dealt with nested read-lock transformation into mutexes by detecting nesting in some way in -rt. But I'll let them confirm this.
So I don't see why you are dreaming about a different semantic than the one of the primitives you are using. I guess I'll leave the semantics to you. I just find it astonishing that you persist saying that everbody is wrong on a topic like semantic, which is in the end a mean to communicate ideas clearly within the overall community you disagree with.
Good luck !
Mathieu
Signature · 2 lines
Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
Re: [PATCH] netfilter: use per-CPU recursive lock {XV}
In reply to Stephen HemmingerQuoted 28 lines · Stephen Hemminger
Quoted 14 lines · On Sun, 26 Apr 2009 14:56:46 -0400 Mathieu Desnoyers…
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:
From: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>So far, so good, should be ready for inclusion now, nobody complained :)
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
Quoted 8 lines
Quoted 3 lines
Thanks to all for your help and patience
[PATCH] netfilter: use per-CPU recursive lock {XV}
Hi Eric,
Suitable name would probably be :
But Linus is trying to delude himself.
Quoted 7 lines
This usage is recursive even if he doesn't like the terminology. The same CPU has to be able to reacquire the read lock without deadlocking. If reader/writer locks were implemented in a pure writer gets priority method, then this code would break! So yes read locks can be used recursively now in Linux, but if the were implemented differently then this code would break. For example, the -rt kernel turns all read/write locks into mutexs, so the -rt kernel developers will have to address this.
A recursive lock has the property:
lock()
{
if (lock->owner == current) {
lock->depth++;
return;}
/* regular lock stuff */
}
unlock()
{
if (!--lock->depth)
/* regular unlock */ }
non of the linux kernel locking primitives have this -- with the possible exception of the cpu-hotplug lock.
What rwlock_t has, is reader bias to the point where you can utterly starve writers, with the side effect that you can obtain multiple read ownerships without causing a deadlock.
This is not what is called a recursive lock. A recursive lock would have each owner only once, this rwlock_t thing is simply so unfair that it can have unlimited owners, including multiple copies of the same one.
rwsem has fifo fairness, and therefore can deadlock in this scenario, suppose thread A does a read, thread B tries a write and blocks, then thread A recurses and tries to obtain another read ownership -- deadlock, as the FIFO fairness will demand the second read ownership will wait on the pending writer, which will wait on the outstanding read owner.
Now if rwsem were a fifo-fair recursive lock, the above would not deadlock, since it would detect that the task already had (read) ownership and simply increment the depth, instead of trying to acquire a second ownership.
This is all common and well understood terminology, not something Linus invented just to harras you with.
Generally speaking we do not condone recursive locking strategies -- and afaik reiserfs (as per the BKL) and the network code (as per abusing rwlock_t unfairness) are the only offenders.
Like Linus stated, recursive locking is generally poor taste and indicates you basically gave up on trying to find a proper locking scheme. We should very much work towards getting rid of these abberations instead of adding new ones.
Linus is very much right on what he said, and you calling him delusional only high-lights your ignorance on the issue.
[ PS. -rt implements rwlock_t as a proper recursive lock (either a mutex
or a full multi-owner reader-writer lock with PI fairness) so if anybody abuses rwlock_t unfairness in a way that is not strict owner recursive we have a problem. ]
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 46 lines · On Mon, 27 Apr 2009 19:44:57 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 28 lines · Stephen Hemminger
Quoted 14 lines · On Sun, 26 Apr 2009 14:56:46 -0400 Mathieu Desnoyers…
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:
From: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>So far, so good, should be ready for inclusion now, nobody complained :)
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
Quoted 8 lines
Quoted 3 lines
Thanks to all for your help and patience
[PATCH] netfilter: use per-CPU recursive lock {XV}
Hi Eric,
Suitable name would probably be :
But Linus is trying to delude himself.
Quoted 7 lines
This usage is recursive even if he doesn't like the terminology. The same CPU has to be able to reacquire the read lock without deadlocking. If reader/writer locks were implemented in a pure writer gets priority method, then this code would break! So yes read locks can be used recursively now in Linux, but if the were implemented differently then this code would break. For example, the -rt kernel turns all read/write locks into mutexs, so the -rt kernel developers will have to address this.
A recursive lock has the property:
lock()
{if (lock->owner == current) { lock->depth++; return;}
Quoted 8 lines
/* regular lock stuff */
}
unlock()
{
if (!--lock->depth)/* regular unlock */ }
Only on Linux, and only because you look at locking from the point of view of the magic variable "current" process point of view.
Quoted 6 lines
non of the linux kernel locking primitives have this -- with the possible exception of the cpu-hotplug lock.
What
rwlock_thas, is reader bias to the point where you can utterly starve writers, with the side effect that you can obtain multiple read ownerships without causing a deadlock.
But what happens when this side effect disappears?
Quoted 11 lines
This is not what is called a recursive lock. A recursive lock would have each owner only once, this
rwlock_tthing is simply so unfair that it can have unlimited owners, including multiple copies of the same one.rwsem has fifo fairness, and therefore can deadlock in this scenario, suppose thread A does a read, thread B tries a write and blocks, then thread A recurses and tries to obtain another read ownership -- deadlock, as the FIFO fairness will demand the second read ownership will wait on the pending writer, which will wait on the outstanding read owner.
Quoted 7 lines
Now if rwsem were a fifo-fair recursive lock, the above would not deadlock, since it would detect that the task already had (read) ownership and simply increment the depth, instead of trying to acquire a second ownership.
This is all common and well understood terminology, not something Linus invented just to harras you with.
In Documentation/ ? online ? Where is the definition? The only reference I se is indirectly in DocBook/kernel-locking.tmpl.
Quoted 8 lines
Generally speaking we do not condone recursive locking strategies -- and afaik reiserfs (as per the BKL) and the network code (as per abusing
rwlock_tunfairness) are the only offenders.Like Linus stated, recursive locking is generally poor taste and indicates you basically gave up on trying to find a proper locking scheme. We should very much work towards getting rid of these abberations instead of adding new ones.
The people complaining about naming never seem to be the ones providing workable suggestions or patches.
Quoted 7 lines
Linus is very much right on what he said, and you calling him delusional only high-lights your ignorance on the issue.
[ PS. -rt implements
rwlock_tas a proper recursive lock (either a mutex
or a full multi-owner reader-writer lock with PI fairness) so if anybody abusesrwlock_tunfairness in a way that is not strict owner recursive we have a problem. ]
Name it "dog's breath locking" for all I care. I am not bothering with arguments over names; there is real work to do elsewhere.
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 8 lines · Stephen Hemminger
Quoted 6 lines
non of the linux kernel locking primitives have this -- with the possible exception of the cpu-hotplug lock.
What
rwlock_thas, is reader bias to the point where you can utterly starve writers, with the side effect that you can obtain multiple read ownerships without causing a deadlock.But what happens when this side effect disappears?
Then well written code works, badly written code breaks.
Quoted 7 lines
Quoted 4 lines
[...]
This is all common and well understood terminology, not something Linus invented just to harras you with.
In
Documentation/? online ? Where is the definition? The only reference I se is indirectly in DocBook/kernel-locking.tmpl.
Sure, see:
Quoted 5 lines
Quoted 5 lines
Generally speaking we do not condone recursive locking strategies -- and afaik reiserfs (as per the BKL) and the network code (as per abusing
rwlock_tunfairness) are the only offenders.
Quoted 7 lines
Quoted 4 lines
Like Linus stated, recursive locking is generally poor taste and indicates you basically gave up on trying to find a proper locking scheme. We should very much work towards getting rid of these abberations instead of adding new ones.
The people complaining about naming never seem to be the ones providing workable suggestions or patches.
The thing is, while you now have named your locking primitive correctly, you are still abusing it by using it recursively.
So it's not 'just about naming'. You should not use read-locks as recursive locks. It's poor code.
Ingo
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 19 lines · On Mon, 27 Apr 2009 20:54:23 +0200 Ingo Molnar <[email protected]> wrote:
Quoted 8 lines · Stephen Hemminger
Quoted 6 lines
non of the linux kernel locking primitives have this -- with the possible exception of the cpu-hotplug lock.
What
rwlock_thas, is reader bias to the point where you can utterly starve writers, with the side effect that you can obtain multiple read ownerships without causing a deadlock.But what happens when this side effect disappears?
Then well written code works, badly written code breaks.
Quoted 5 lines
Quoted 4 lines
[...]
This is all common and well understood terminology, not something Linus invented just to harras you with.
Quoted 6 lines
Quoted 2 lines
In
Documentation/? online ? Where is the definition? The only reference I se is indirectly in DocBook/kernel-locking.tmpl.Sure, see:
All those references support my argument that the lock is being used recursively in this case. It is being acquired multiple times by the same CPU. This is not new, it has always been acquired multiple times, so my change does not break anything.
If other implementations of reader locks to not nest the same way, then on those system iptables can deadlock. Nothing was changed by this.
Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Generally speaking we do not condone recursive locking strategies -- and afaik reiserfs (as per the BKL) and the network code (as per abusing
rwlock_tunfairness) are the only offenders.Like Linus stated, recursive locking is generally poor taste and indicates you basically gave up on trying to find a proper locking scheme. We should very much work towards getting rid of these abberations instead of adding new ones.
Quoted 8 lines
Quoted 2 lines
The people complaining about naming never seem to be the ones providing workable suggestions or patches.
The thing is, while you now have named your locking primitive correctly, you are still abusing it by using it recursively.
So it's not 'just about naming'. You should not use read-locks as recursive locks. It's poor code.
If you don't like the proposal please, think of a better alternative. Not just pseudo code that is broken with handwaving arguments.
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 3 lines · Stephen Hemminger
All those references support my argument that the lock is being used recursively in this case.
What's so hard between understanding the difference between "used recursively" and "recursive lock"?
THEY MEAN TWO TOTALLY DIFFERENT THINGS!
The fact that you don't seem to understand that is one of the things I've been complaining about all along.
So here's a final set of clue-bat:
Clue bat #1:
- "can be used in a recursive context" is not the same as "is recursive".
Analogy time: Look at "strtok_r()", and the difference between that and "strtok()". "strtok_r()" can be used in a threaded environment. Does that mean that 'strtok_r()' is threaded? No. When you call 'strtok_r()', it's still signle-threaded - it's just that it _can_ be called in a threaded environment and then still has sane semantics.
Now, replace "threaded" with "recursive". Do you get it?
Clue bat #2:
- a lock that can count does not mean that it is recursive.
Counting and recursion are TWO TOTALLY DIFFERENT ISSUES. The "countingness" means that there can be multiple users inside of it, and that, in turn, implies that maybe it can be used in a recursive context. But again, counting and recursion are not about the same thing at all.
Put another way: a read-write lock is not a "recursive lock" despite the fact that you can recursively take the lock for reading. It just happens to count readers, and allow more than one (from _any_ context, not just from the "same context").
Clue bat #3:
- A recursive lock is very much _about_ recursion. It is explicitly about the fact that the _same_ thread re-enters the lock, not about another thread being in the locked region at the same time.
See the difference? Big, big difference. A recursive lock will lock out other thread contexts, even if it allows the current one to recurse. Notice how the _only_ thing a recursive lock allows is that recursive behavior, and nothing else.
IOW, a "recursive lock" is explicitly designed for recursion. But that doesn't mean that recursive algorithms cannot use functions that aren't.
Can you use "memcpy()" in a recursive algorithm? Yes. Does that mean that "memcpy()" is suddenly a "recursive memory copy"? No.
See the difference?
Clue bat #3:
- if you do not understand the difference between these two things, don't then try to claim that somebody _else_ who does understand it is "deluding himself".
Analogy time: Ethernet and a modem line can both get you on the internet. Now, let's say that Mr Peter Paste-Eater has heard of ethernet, and knows you can get on the internet with an ethernet connection, but he happens to use a modem line to do it.
Now, Peter Paste-Eater talks to you, and tells you he is connecting to the internet with ethernet, and proudly shows you his serial line and modem, and tells you how he uses ethernet to get onto the internet. You correct him, and tell him it's not ethernet. He argues for several days about how he gets on the internet, and that it must thus be ethernet, and that you're obviously just "deluding yourself".
Now, can you see why people react badly to you talking about "recursive locks"? You're acting like Peter Paste-Eater calling his serial line ethernet. The fact that two _different_ things can be used for the same end result DOES NOT MAKE THEM THE SAME THING.
In other words:
- "Recursive locks" are different from reader-writer locks.
- The ability to count is different from recursion, although in a lock it can obviously be _related_ to whether it can be used in a recursive environment or not. If you don't have a counter, you probably cannot recurse, but it's also not true that a counter implies that you always can.
A traditional counting lock is the old-fasioned 'semaphore' we have, where the count allows for more than just simple mutual exclusion, and is used when you might want to allow concurrency, but need to limit it to some number 'n' (although, almost always, n==1)
- What the netfilter code wants is simply not a recursive lock. It wants a form of locking that allows recursive _use_, but as mentioned, that is totally and utterly irrelevant from what we call it.
You _could_ use a recursive lock for it. BUT NONE OF THE PATCHES THAT HAVE EVER BEEN POSTED HAVE BEEN RECURSIVE LOCKS! Nada. None. Zero. Zilch.
So don't talk about recursive locks.
Get it? Finally? Or are you going to continue to be that Paste-Eater guy who refuses to understand that he is talking about something else than ethernet?
Linus
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 8 lines · Linus Torvalds
Clue bat #1:
Clue bat #2:
Clue bat #3:
Clue bat #3:
Note to self: learn to count beyond three one of these days.
Linus
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
In reply to Linus TorvaldsHi.
Quoted 10 lines · Linus Torvalds
Quoted 2 lines
All those references support my argument that the lock is being used recursively in this case.
What's so hard between understanding the difference between "used recursively" and "recursive lock"?
THEY MEAN TWO TOTALLY DIFFERENT THINGS!
The fact that you don't seem to understand that is one of the things I've been complaining about all along.
Just ot be sure readers will not lose the discssion topic: do you object against naming or realizaion? If its about the former, does 'dog's breath lock' proposed by Stephen fit?
Signature · 1 line
Evgeniy Polyakov
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 3 lines · Evgeniy Polyakov
Just ot be sure readers will not lose the discssion topic: do you object against naming or realizaion?
I said _long_ ago that I thought the patch was fine.
What I object to is people mis-representing the lock, and apparently having a really hard time admitting that having a good grounding in networking doesn't necessarily mean that you know everything about something as basic as locking.
Quoted 2 lines
If its about the former, does 'dog's breath lock' proposed by Stephen fit?
Is that just an attempt to avoid admitting that they were wrong about lock naming? And then trying to trivialize it by calling things by a _different_ wrong name, but silly enough that they hope people won't call them on it?
Why not just use the correct name? I think it was Mathieu that just suggested:
[PATCH] netfilter: use bh disabling with per-cpu read-write lock
or just call it "netfilter: use per-CPU read-write lock".
Why are people so against calling things by their correct names? Why do certain network people seem to force a stupid and incorrect description, when they have been told (a) that it's wrong and (b) why it's wrong several times?
What's so hard with just doing the TechnicallyRightThing(tm) and describing it as such?
And btw - don't get me wrong. There are _other_ ways to do that locking too. You don't have to use a rwlock. You can do it with explicit counting, the way Eric's original patch did. But it would be wrong to call that one "recursive lock" too.
Or you _could_ use a recursive lock, but nobody has actually posted such patches. It would work. No question about it. And if it actually _were_ a recursive lock, I wouldn't have objected about the description saying it is (although I would probably have objected to it being unnecessarily complex, when a simpler rwlock or the explicit count thing would be sufficient).
But since the current simple patch is using a rwlock, why not just say that? Why call it something incorrect ("recursive lock") or nonsensical ("dog's breath lock").
As I tried to explain with an analogy, networking people would (quite correctly) object to me calling a serial line an "ethernet cable". Why is it so hard for netfilter people to then see why it's wrong to call a rwlock a "recursive lock".
I mean, guys, if you don't want to read up on decades of locking work, just google for it. Google for "recursive lock" (_with_ the quotes). At least for me, the very first hit gives a reasonable explanation for it, and it says:
"POSIX allows mutexes to be recursive. That means the same thread can
lock the same mutex twice and won't deadlock."
and realize that the "same thread" part is very much a keyword, not juat a random implementation detail (the first answer to the question is better than the question, but even the question at the top really does get at the basics).
And please do realize that neither rwlocks nor the counting locks from Dumazet's original patch do that. Never did. They simply aren't recursive locks.
So just don't call them that. But is "dog's breath" any better? Yes, maybe it's less _misleading_, but it sure as hell isn't any more descriptive.
Linus
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 14 lines · On Mon, 27 Apr 2009 13:58:48 -0700 (PDT) Linus Torvalds…
Quoted 3 lines · Evgeniy Polyakov
Just ot be sure readers will not lose the discssion topic: do you object against naming or realizaion?
I said _long_ ago that I thought the patch was fine.
What I object to is people mis-representing the lock, and apparently having a really hard time admitting that having a good grounding in networking doesn't necessarily mean that you know everything about something as basic as locking.
Quoted 7 lines
Quoted 2 lines
If its about the former, does 'dog's breath lock' proposed by Stephen fit?
Is that just an attempt to avoid admitting that they were wrong about lock naming? And then trying to trivialize it by calling things by a _different_ wrong name, but silly enough that they hope people won't call them on it?
The part that concerns me is that the reader lock used in a nested manner on same cpu may still be broken on -rt. Other than that it is just language lawyering; violent agreement that the lock gets used multiple times by same CPU. I never had the occasion to address this before
(and avoided such usage), but this legacy code exists and needs to be dealt with.
Quoted 6 lines
Why not just use the correct name? I think it was Mathieu that just suggested:
[PATCH] netfilter: use bh disabling with per-cpu read-write lock
or just call it "netfilter: use per-CPU read-write lock".
[PATCH] netfilter: Ceci n'est pas une serrure récurrente
I don't care. I don't care. Don't you get the point yet.
Quoted 5 lines
Why are people so against calling things by their correct names? Why do certain network people seem to force a stupid and incorrect description, when they have been told (a) that it's wrong and (b) why it's wrong several times?
Because meaning comes from context, and my meaning comes from different context. So we disagree on correct names.
Quoted 37 lines
What's so hard with just doing the TechnicallyRightThing(tm) and describing it as such?
And btw - don't get me wrong. There are _other_ ways to do that locking too. You don't have to use a rwlock. You can do it with explicit counting, the way Eric's original patch did. But it would be wrong to call that one "recursive lock" too.
Or you _could_ use a recursive lock, but nobody has actually posted such patches. It would work. No question about it. And if it actually _were_ a recursive lock, I wouldn't have objected about the description saying it is (although I would probably have objected to it being unnecessarily complex, when a simpler rwlock or the explicit count thing would be sufficient).
But since the current simple patch is using a rwlock, why not just say that? Why call it something incorrect ("recursive lock") or nonsensical ("dog's breath lock").
As I tried to explain with an analogy, networking people would (quite correctly) object to me calling a serial line an "ethernet cable". Why is it so hard for netfilter people to then see why it's wrong to call a rwlock a "recursive lock".
I mean, guys, if you don't want to read up on decades of locking work, just google for it. Google for "recursive lock" (_with_ the quotes). At least for me, the very first hit gives a reasonable explanation for it, and it says:
"POSIX allows mutexes to be recursive. That means the same thread can
lock the same mutex twice and won't deadlock."and realize that the "same thread" part is very much a keyword, not juat a random implementation detail (the first answer to the question is better than the question, but even the question at the top really does get at the basics).
Quoted 8 lines
And please do realize that neither rwlocks nor the counting locks from Dumazet's original patch do that. Never did. They simply aren't recursive locks.
So just don't call them that. But is "dog's breath" any better? Yes, maybe it's less _misleading_, but it sure as hell isn't any more descriptive.
Linus
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 3 lines · Stephen Hemminger
The part that concerns me is that the reader lock used in a nested manner on same cpu may still be broken on -rt.
I think that's a valid concern, and I don't actually object to not using a rwlock, but using the "explicit counting + spinlock" that we had at one point. It _might_ even be faster, since a spinlock can be faster than a rwlock, and the (rare) case where you recurse you can then avoid the atomic entirely.
But EVEN IF YOU DO THAT, it's still wrong to call it a "recursive lock". Because it still wouldn't be one.
That's kind of my point, and always has been. It was why I objected to the original patch description by Dumazet. It wasn't a recursive lock back then _either_. For all the reasons I tried to explain to you, and you seem to not care about.
Btw, if you do use the "explicit count" case, then please please please make sure it's documented and bug-free. And dammit, correct documentation in this case very much talks about how it is _not_ a "recursive lock", but a spinlock that then has an explicit counter that avoids taking the lock entirely in one very specific path (that happens to be recursive).
The thing is, using a rwlock kind of implicitly documents all of that, because you can tell somebody who doesn't even read the code that it's a "per-cpu rwlock", and they then know what the semantics are (given that they know the kernel semantics for locking in the first place).
But once you start doing your own locking rules, you really have to explain why it works, and what it does. And you do have to be very careful, because it's so easy to get locking wrong.
Quoted 1 line
I don't care. I don't care. Don't you get the point yet.
If you don't care about the naming, then use the right one.
And if you don't care about the naming, why do you then say I'm deluding myself, when I'm _correct_, and I _do_ happen to care about correct naming.
Locking really is important. Code that gets locking wrong breaks in really subtle and nasty ways. And it sadly tends to "work" in testing, since the breakage cases require just the right timing. So locking should be robust and as "obviously correct" as possible.
And naming really is important. Misnaming things makes people make assumptions that aren't true. If you talk about recursive locks, it should be reasonable that people who know how recursive locks work would then make assumptions about them. If the code then doesn't actually match those rules, that's bad.
It's like having a comment in front of a piece of code that says something totally different than what the code actually does. It's _bad_. That's why naming matters so much - because naming is commentary. If you mis-name things on purpose, it's simply a bug.
Do _you_ get the point?
You _do_ care about bugs, don't you?
Linus
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 6 lines · Linus Torvalds
Btw, if you do use the "explicit count" case, then please please please make sure it's documented and bug-free. And dammit, correct documentation in this case very much talks about how it is _not_ a "recursive lock", but a spinlock that then has an explicit counter that avoids taking the lock entirely in one very specific path (that happens to be recursive).
So, just as an example, I would not object to the counter approach, as long as it really talks about the issues, and why it works (and as long that doesn't call the locks "recursive locks").
So if you are just nervous about rwlocks, then something like this might work (needs testing, and other people to sanity-check it).
I left the commentary about "readers" and "writers", because in many ways it's correct, and what the code actually does is very much to emulate a reader-writer lock. I put quotes around the uses in the comments to high-light that it largely _acts_ as a reader-writer lock.
Now, it would actually be a really _bad_ reader-writer lock in general, exactly because it's not very "atomic" (ie this would be a truly sucky and broken lock if we didn't have the strict per-cpu usage rules).
So it just so happens that the per-cpu'ness of the lock, together with the very limited way in which it is used, make that sucky implementation possible - and indeed possibly faster than the standard (and generic) kernel rwlock implementation.
So it's basically a special-case rwlock that happens to work due to the specific rules.
And exactly because it really wouldn't work in the absense of those rules, those rules really do need to have big comments on them so that people don't then later forget about the limitations.
BTW: THIS IS TOTALLY UNTESTED. I just cut-and-pasted the existing rwlock version from one of the later patches, used the counting approach from one of the earlier ones, and basically just added what I think would be minimal required comments for this special case. All of it was written inside the mail reader, none of it has been compiled or tested in any other way.
Because it's exactly the "lock semantics awareness" that I think is so important here (and that's why all the naming and commentary is so critical).
Btw, the "counter" could probably be just a single bit, since apparently the nesting level is always supposed to be just one. I made it "unsigned char" just because sometimes spinlocks can be small, and it seemed the simplest type. But perhaps it would be better as an "unsigned int", since some architectures potentially could do that faster (eg old alphas).
Linus
---
/*
* Per-CPU spinlock associated with per-cpu table entries, and
* with a counter for the "reading" side that allows a recursive
* reader to avoid taking the lock and deadlocking.
*
* "reading" is used by ip/arp/ip6 tables rule processing which runs per-cpu.
* It needs to ensure that the rules are not being changed while the packet
* is being processed. In some cases, the read lock will be acquired
* twice on the same CPU; this is okay because of the count.
*
* The write lock is used in two cases:
* 1. reading counter values
* all rule processing need to be stopped and the per-CPU values are summed.
*
* 2. replacing tables
* any readers that are using the old tables have to complete
* before freeing the old table. This is handled by reading
* as a side effect of reading counters
*/
struct xt_info_lock {
spin_lock_t lock;
unsigned char readers;
};DECLARE_PER_CPU(struct xt_info_lock, xt_info_locks);
/*
* Note: we need to ensure that preemption is disabled before acquiring
* the per-cpu-variable, so we do it as a two step process rather than
* using "spin_lock_bh()".
*
* We _also_ need to disable bottom half processing before updating our
* nesting count, to make sure that the only kind of re-entrancy is this
* code being called by itself: since the count+lock is not an atomic
* operation, we can allow no races.
*
* _Only_ that special combination of being per-cpu and never getting
* re-entered asynchronously means that the count is safe. */
static inline void xt_info_rdlock_bh(void)
{
struct xt_info_lock *lock;
local_bh_disable();
lock = &__get_cpu_var(xt_info_locks);
if (!lock->readers++)
spin_lock(&lock->lock);
}static inline void xt_info_rdunlock_bh(void)
{
struct xt_info_lock *lock;
lock = &__get_cpu_var(xt_info_locks);
if (!--lock->readers)
spin_unlock(&lock->lock);
}/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. This must be called with bottom half
* processing (and thus also preemption) disabled.
*/
static inline void xt_info_wrlock(unsigned int cpu)
{
spin_lock(&per_cpu(xt_info_locks, cpu).lock);
}static inline void xt_info_wrunlock(unsigned int cpu)
{
spin_unlock(&per_cpu(xt_info_locks, cpu).lock);
}Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 2 lines · Linus Torvalds
BTW: THIS IS TOTALLY UNTESTED.
Gaah. I should have read through it one more time before sending.
Quoted 8 lines
static inline void
xt_info_rdunlock_bh(void){ struct xt_info_lock *lock; lock = &__get_cpu_var(xt_info_locks); if (!--lock->readers) spin_unlock(&lock->lock); }
This one was missing the "local_bh_enable()" at the end.
There may be other bugs, but that's the one I noticed immediately when reading what I sent out. Oops.
Linus
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 15 lines · Linus Torvalds
Quoted 1 line · Linus Torvalds
BTW: THIS IS TOTALLY UNTESTED.
Gaah. I should have read through it one more time before sending.
Quoted 8 lines
static inline void
xt_info_rdunlock_bh(void){ struct xt_info_lock *lock; lock = &__get_cpu_var(xt_info_locks); if (!--lock->readers) spin_unlock(&lock->lock); }
Quoted 4 lines
This one was missing the "
local_bh_enable()" at the end.There may be other bugs, but that's the one I noticed immediately when reading what I sent out. Oops.
I am not sure my day job will permit me to polish a patch mixing all the bits and comments. But I am glad we eventually got back spinlocks which are probably better than rwlocks for implementing this stuff.
Instead of submitting a full patch again, we could first submit a new
include file containg all comments and inline functions ?
This include file could be local to netfilter, with a big stick on it to forbids its use on other areas (No changes in Documentation/ )
Then, as soon as we can go back to pure RCU solution, we can safely delete this controversial-locking-nesting-per-cpu-thing ?
Instead of local/global name that Paul suggested, that was about 'global' locking all locks at the same time. Not any more the good name IMHO
Maybe something like local/remote or owner/foreigner ?
xt_info_owner_lock_bh(), xt_info_owner_unlock_bh() xt_info_foreigner_lock(), xt_info_foreigner_unlock()
One comment about this comment you wrote :
/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. This must be called with bottom half
* processing (and thus also preemption) disabled.
*/
static inline void xt_info_wrlock(unsigned int cpu)
{
spin_lock(&per_cpu(xt_info_locks, cpu).lock);
}static inline void xt_info_wrunlock(unsigned int cpu)
{
spin_unlock(&per_cpu(xt_info_locks, cpu).lock);
}Its true that BH should be disabled if caller runs on the cpu it wants to lock.
For other ones (true foreigners), there is
no requirement about BH (current cpu could be interrupted by a softirq and packets could fly)
We could use following construct and not require disabling BH more than a short period of time.
(But preemption disabled for the whole duration)
preempt_disable(); // could be cpu_migration_disable();
int curcpu = smp_processor_id();
/*
* Gather stats for current cpu : must disable BH
* before trying to lock.
*/local_bh_disable();xt_info_wrlock(curcpu);
// copy stats of this cpu on my private data (not shown here) xt_info_wrunlock(curcpu);local_bh_enable();
for_each_possible_cpu(cpu) {
if (cpu == curcpu)
continue;
xt_info_wrlock(cpu);
// fold stats of "cpu" on my private data (not shown here)
xt_info_wrunlock((cpu);
}preempt_enable(); // could be cpu_migration_enable();
So your initial comment could be changed to :
/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. If caller is about to lock its own lock,
* he must have disabled BH before. For other cpus, no special
* care but preemption disabled to guarantee no cpu migration. */
Back to work now :)
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
David Miller
maintainerRe: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
From: Eric Dumazet <[email protected]>
Date: Tue, 28 Apr 2009 08:58:05 +0200
Quoted 4 lines
I am not sure my day job will permit me to polish a patch mixing all the bits and comments. But I am glad we eventually got back spinlocks which are probably better than rwlocks for implementing this stuff.
Quoted 8 lines
Instead of submitting a full patch again, we could first submit a new
include file containg all comments and inline functions ?This include file could be local to netfilter, with a big stick on it to forbids its use on other areas (No changes in
Documentation/)Then, as soon as we can go back to pure RCU solution, we can safely delete this controversial-locking-nesting-per-cpu-thing ?
I say we merge Linus's locking idea into the XV patch, fixup the commit message wording, and move on with life.
For something that's going to get deleted as soon as the faster grace period RCU stuff is available, it has consumed an inordinate amount of our time :-)
I might take a stab at this before hittng bed tonight, no promises :)
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 16 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Tue, 28 Apr 2009 08:58:05 +0200Quoted 4 lines
I am not sure my day job will permit me to polish a patch mixing all the bits and comments. But I am glad we eventually got back spinlocks which are probably better than rwlocks for implementing this stuff.
Quoted 8 lines
Instead of submitting a full patch again, we could first submit a new
include file containg all comments and inline functions ?This include file could be local to netfilter, with a big stick on it to forbids its use on other areas (No changes in
Documentation/)Then, as soon as we can go back to pure RCU solution, we can safely delete this controversial-locking-nesting-per-cpu-thing ?
Quoted 6 lines
I say we merge Linus's locking idea into the XV patch, fixup the commit message wording, and move on with life.
For something that's going to get deleted as soon as the faster grace period RCU stuff is available, it has consumed an inordinate amount of our time :-)
One more reason to factor out this code into general locking code.
The latest code looks a bit similar to the old big-reader-locks hack (which got dropped for good many eons ago and with which i deny any involvement with, such as having authored it. [oh, did i say that out loud? crap.]), implemented cleanly and properly.
IMHO this locking construct should be considered for linux/local_lock.h and kernel/local_lock.c. Even if the netfilter code drops its use soon afterwards ;-)
[ The _only_ thing i am worried about is the apparent fact that
there's so much confusion about recursion versus read-access. Recursion might be hard to factor out of the netfilter code, and maybe it's not even possible realistically (we fought years with the BKL and are still fighting it) but if its harms are not even _realized_ that difficult task turns into an impossible task ;-) ]
Ingo
David Miller
maintainerRe: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
From: Ingo Molnar <[email protected]>
Date: Tue, 28 Apr 2009 14:40:33 +0200
Quoted 3 lines
IMHO this locking construct should be considered for
linux/local_lock.handkernel/local_lock.c. Even if the netfilter code drops its use soon afterwards ;-)
If you can show me have to pass a per-cpu variable (the variable, not a dereference of it) as an argument to an inline function, I'll implement this :-)
It has to be dereferenced after local_bh_disable() for the read side acquisition.
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 7 lines · * David Miller ([email protected]) wrote:
From: Ingo Molnar <[email protected]>
Date: Tue, 28 Apr 2009 14:40:33 +0200Quoted 3 lines
IMHO this locking construct should be considered for
linux/local_lock.handkernel/local_lock.c. Even if the netfilter code drops its use soon afterwards ;-)
Quoted 6 lines
If you can show me have to pass a per-cpu variable (the variable, not a dereference of it) as an argument to an inline function, I'll implement this :-)
It has to be dereferenced after
local_bh_disable()for the read side acquisition.
The local_bh_disable() could be outside of the locking construct. This would make it easier to adapt it to various users (irq disable, bh disable, preempt disable) depending on the contexts from which they much be protected.
And if it still does not work for some reason, using a #define is discouraged, but could work.
Mathieu
Signature · 2 lines
Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
David Miller
maintainerRe: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
From: Mathieu Desnoyers <[email protected]>
Date: Tue, 28 Apr 2009 09:52:19 -0400
Quoted 7 lines
The
local_bh_disable()could be outside of the locking construct. This would make it easier to adapt it to various users (irq disable, bh disable, preempt disable) depending on the contexts from which they much be protected.And if it still does not work for some reason, using a #define is discouraged, but could work.
That's what I was hoping to avoid, things like macros and having the callers of this thing expand the two parts of the operation.
What's the point in making this generic if it ends up being ugly as hell?
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 8 lines · * David Miller ([email protected]) wrote:
From: Mathieu Desnoyers <[email protected]>
Date: Tue, 28 Apr 2009 09:52:19 -0400Quoted 5 lines
The
local_bh_disable()could be outside of the locking construct. This would make it easier to adapt it to various users (irq disable, bh disable, preempt disable) depending on the contexts from which they much be protected.
Quoted 8 lines
Quoted 2 lines
And if it still does not work for some reason, using a #define is discouraged, but could work.
That's what I was hoping to avoid, things like macros and having the callers of this thing expand the two parts of the operation.
What's the point in making this generic if it ends up being ugly as hell?
.. and what's the point in making it generic if it can be replaced by a proper RCU implementation ? :-) I am not convinced of the added value we get in making it a generic header this soon. I would wait for other users to express similar needs, otherwise this could soon become an orphaned piece of locking code.
Mathieu
Signature · 2 lines
Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
David Miller
maintainerRe: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
From: Mathieu Desnoyers <[email protected]>
Date: Tue, 28 Apr 2009 10:49:20 -0400
Quoted 5 lines
.. and what's the point in making it generic if it can be replaced by a proper RCU implementation ? :-) I am not convinced of the added value we get in making it a generic header this soon. I would wait for other users to express similar needs, otherwise this could soon become an orphaned piece of locking code.
That is my opinion as well.
Anyways, here is a patch that builds, I haven't started working on the commit message yet.
include/linux/netfilter/x_tables.h +73 -5
@@ -354,9 +354,6 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -struct mutex lock; -/* Man behind the curtain... */ struct xt_table_info *private;
@@ -434,8 +431,79 @@ extern void xt_proto_fini(struct net *net, u_int8_t af);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); + +/* +* Per-CPU spinlock associated with per-cpu table entries, and +* with a counter for the "reading" side that allows a recursive +* reader to avoid taking the lock and deadlocking. +* +* "reading" is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while the packet +* is being processed. In some cases, the read lock will be acquired +* twice on the same CPU; this is okay because of the count. +* +* The write lock is used in two cases: +* 1. reading counter values +* all rule processing need to be stopped and the per-CPU values are summed. +* +* 2. replacing tables +* any readers that are using the old tables have to complete +* before freeing the old table. This is handled by reading +* as a side effect of reading counters +*/ +struct xt_info_lock { +spinlock_t lock; +unsigned char readers; +}; +DECLARE_PER_CPU(struct xt_info_lock, xt_info_locks); + +/* +* Note: we need to ensure that preemption is disabled before acquiring +* the per-cpu-variable, so we do it as a two step process rather than +* using "spin_lock_bh()". +* +* We _also_ need to disable bottom half processing before updating our +* nesting count, to make sure that the only kind of re-entrancy is this +* code being called by itself: since the count+lock is not an atomic +* operation, we can allow no races. +* +* _Only_ that special combination of being per-cpu and never getting +* re-entered asynchronously means that the count is safe. +*/ +static inline void xt_info_rdlock_bh (void ) +{ +struct xt_info_lock *lock; + +local_bh_disable (); + lock = &__get_cpu_var (xt_info_locks); +if (!lock->readers++) +spin_lock (&lock->lock); +} + +static inline void xt_info_rdunlock_bh (void ) +{ +struct xt_info_lock *lock; + + lock = &__get_cpu_var (xt_info_locks); +if (!--lock->readers) +spin_unlock (&lock->lock); +local_bh_enable (); +} + +/* +* The "writer" side needs to get exclusive access to the lock, +* regardless of readers. This must be called with bottom half +* processing (and thus also preemption) disabled. +*/ +static inline void xt_info_wrlock (unsigned int cpu) +{ +spin_lock (&per_cpu (xt_info_locks, cpu).lock); +} + +static inline void xt_info_wrunlock (unsigned int cpu) +{ +spin_unlock (&per_cpu (xt_info_locks, cpu).lock); +}/* * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +36 -89
215 lines not on this page · raw message
net/ipv4/netfilter/ip_tables.c +35 -91
211 lines not on this page · raw message
net/ipv6/netfilter/ip6_tables.c +37 -86
208 lines not on this page · raw message
net/netfilter/x_tables.c +25 -25
91 lines not on this page · raw message
PATCH 1/1 netfilter: revised locking for x_tables
The x_tables are organized with a table structure and a per-cpu copies of the counters and rules. On older kernels there was a reader/writer lock per table which was a performance bottleneck. In 2.6.30-rc, this was converted to use RCU and the counters/rules which solved the performance problems for do_table but made replacing rules much slower because of the necessary RCU grace period.
This version uses a per-cpu set of spinlocks and counters to allow to table processing to proceed without the cache thrashing of a global reader lock and keeps the same performance for table updates.
---
Probably same as dave/linus but with different comments.
include/linux/netfilter/x_tables.h | 73 +++++++++++++++++++-- net/ipv4/netfilter/arp_tables.c | 125 ++++++++++-------------------------- net/ipv4/netfilter/ip_tables.c | 126 ++++++++++--------------------------- net/ipv6/netfilter/ip6_tables.c | 123 ++++++++++-------------------------- net/netfilter/x_tables.c | 53 ++++++++------- 5 files changed, 204 insertions(+), 296 deletions(-)
include/linux/netfilter/x_tables.h +68 -5
@@ -354,9 +354,6 @@ struct xt_table/* What hooks you will enter on */ unsigned int valid_hooks; -/* Lock for the curtain */ -struct mutex lock; -/* Man behind the curtain... */ struct xt_table_info *private;
@@ -434,8 +431,74 @@ extern void xt_proto_fini(struct net *neextern 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); + +/* +* Per-CPU spinlock associated with per-cpu table entries, and +* with a counter for the "reading" side that allows a recursive +* reader to avoid taking the lock and deadlocking. +* +* "reading" is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while the packet +* is being processed. In some cases, the read lock will be acquired +* twice on the same CPU; this is okay because of the count. +* +* "writing" is used when reading counters. +* During replace any readers that are using the old tables have to complete +* before freeing the old table. This is handled by the write locking +* necessary for reading the counters. +*/ +struct xt_info_lock { +spinlock_t lock; +unsigned char readers; +}; +DECLARE_PER_CPU(struct xt_info_lock, xt_info_locks); + +/* +* Note: we need to ensure that preemption is disabled before acquiring +* the per-cpu-variable, so we do it as a two step process rather than +* using "spin_lock_bh()". +* +* We _also_ need to disable bottom half processing before updating our +* nesting count, to make sure that the only kind of re-entrancy is this +* code being called by itself: since the count+lock is not an atomic +* operation, we can allow no races. +* +* _Only_ that special combination of being per-cpu and never getting +* re-entered asynchronously means that the count is safe. +*/ +static inline void xt_info_rdlock_bh (void ) +{ +struct xt_info_lock *lock; + +local_bh_disable (); + lock = &__get_cpu_var (xt_info_locks); +if (!lock->readers++) +spin_lock (&lock->lock); +} + +static inline void xt_info_rdunlock_bh (void ) +{ +struct xt_info_lock *lock = &__get_cpu_var (xt_info_locks); + +if (!--lock->readers) +spin_unlock (&lock->lock); +local_bh_enable (); +} + +/* +* The "writer" side needs to get exclusive access to the lock, +* regardless of readers. This must be called with bottom half +* processing (and thus also preemption) disabled. +*/ +static inline void xt_info_wrlock (unsigned int cpu) +{ +spin_lock (&per_cpu (xt_info_locks, cpu).lock); +} + +static inline void xt_info_wrunlock (unsigned int cpu) +{ +spin_unlock (&per_cpu (xt_info_locks, cpu).lock); +}/* * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +36 -89
215 lines not on this page · raw message
net/ipv4/netfilter/ip_tables.c +35 -91
211 lines not on this page · raw message
net/ipv6/netfilter/ip6_tables.c +37 -86
208 lines not on this page · raw message
net/netfilter/x_tables.c +28 -25
94 lines not on this page · raw message
Re: [PATCH] netfilter: revised locking for x_tables
Ack.
It could do with the update from Eric about how non-current CPU writelocks only require preemp-disable around get_counters() (and then the local_bh_disable() only around the current-CPU case).
I _think_ get_counters() is the only case that can use that optimization, but it's quite possible that it's worth doing especially for machines with lots of cores, if BH latency is an issue (and it might be).
Of course, for the lots-and-lots of cores case, even the preemption disable might be an issue. And then it really does get much more complicated. At that point, you probably want the RCU thing.
Linus
Re: [PATCH] netfilter: revised locking for x_tables
Quoted 6 lines · Linus Torvalds
Ack.
It could do with the update from Eric about how non-current CPU writelocks only require preemp-disable around
get_counters()(and then thelocal_bh_disable()only around the current-CPU case).
Btw, regardless, that's an incremental improvement, and does not negate the "Ack" part.
Linus
Re: [PATCH] netfilter: revised locking for x_tables
From: Linus Torvalds <[email protected]>
Date: Tue, 28 Apr 2009 09:55:32 -0700 (PDT)
Quoted 10 lines · Linus Torvalds
Quoted 6 lines
Ack.
It could do with the update from Eric about how non-current CPU writelocks only require preemp-disable around
get_counters()(and then thelocal_bh_disable()only around the current-CPU case).Btw, regardless, that's an incremental improvement, and does not negate the "Ack" part.
I've applied this, thanks everyone!
Re: [PATCH] netfilter: revised locking for x_tables
Quoted 1 line · David Miller
I've applied this, thanks everyone!
I see the patch is already in Linus's tree that I just git pulled. Tested for 200 iptables rules ... as fast as before the slow down.
real 0m0.211s user 0m0.060s sys 0m0.144s
Thank you all for fixing this bug!
Quoted 6 lines · Rafael J. Wysocki
Bug-Entry : http://bugzilla.kernel.org/show_bug.cgi?id=13118
Subject : iptables very slow after commit784544739a25c30637397ace5489eeb6e15d7d49
Submitter : Jeff Chua <[email protected]>
Date : 2009-04-10 16:05 (16 days old)
References : http://lkml.org/lkml/2009/4/10/111
Rafael, it's fixed. Please close the case.
Thanks,
Jeff.
David Miller
maintainerRe: [PATCH] netfilter: revised locking for x_tables
From: Jeff Chua <[email protected]>
Date: Thu, 30 Apr 2009 11:26:40 +0800
Quoted 11 lines · David Miller
Quoted 1 line
I've applied this, thanks everyone!
I see the patch is already in Linus's tree that I just git pulled. Tested for 200 iptables rules ... as fast as before the slow down.
real 0m0.211s user 0m0.060s sys 0m0.144sThank you all for fixing this bug!
Thanks for testing.
PATCH 1/1 netfilter: use likely() in xt_info_rdlock_bh()
In reply to David MillerQuoted 6 lines · David Miller
From: Linus Torvalds <[email protected]>
Date: Tue, 28 Apr 2009 09:55:32 -0700 (PDT)Quoted 3 lines · Linus Torvalds
Quoted 2 lines
Ack.
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
It could do with the update from Eric about how non-current CPU writelocks only require preemp-disable around
get_counters()(and then thelocal_bh_disable()only around the current-CPU case).Btw, regardless, that's an incremental improvement, and does not negate the "Ack" part.
I've applied this, thanks everyone!
Small followup on this one, since the likely() were forgotten. (I trimmed down CCed list, which was insane)
It makes a difference on my x86_32 machine, gcc-4.4.0
Thank you
[PATCH] netfilter: use likely() in xt_info_rdlock_bh()
---
include/linux/netfilter/x_tables.h +2 -2
@@ -472,7 +472,7 @@ static inline void xt_info_rdlock_bh(void)local_bh_disable (); lock = &__get_cpu_var (xt_info_locks); -if (!lock->readers++) +if (likely (!lock->readers++))spin_lock (&lock->lock); }
@@ -480,7 +480,7 @@ static inline void xt_info_rdunlock_bh(void) {struct xt_info_lock *lock = &__get_cpu_var (xt_info_locks); -if (!--lock->readers) +if (likely (!--lock->readers))spin_unlock (&lock->lock);local_bh_enable (); }
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use likely() in xt_info_rdlock_bh()
From: Eric Dumazet <[email protected]>
Date: Fri, 01 May 2009 10:38:20 +0200
Quoted 3 lines
[PATCH] netfilter: use
likely()inxt_info_rdlock_bh()Signed-off-by Eric Dumazet <[email protected]>
Applied.
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
In reply to David MillerQuoted 7 lines · David Miller
From: Ingo Molnar <[email protected]>
Date: Tue, 28 Apr 2009 14:40:33 +0200Quoted 3 lines
IMHO this locking construct should be considered for
linux/local_lock.handkernel/local_lock.c. Even if the netfilter code drops its use soon afterwards ;-)
Quoted 6 lines
If you can show me have to pass a per-cpu variable (the variable, not a dereference of it) as an argument to an inline function, I'll implement this :-)
It has to be dereferenced after
local_bh_disable()for the read side acquisition.
The way I did this in treercu.c was to create an array of references to the per-CPU data in question. Not necessarily recommended, but one way of doing it. That said, one could argue that we should wait until we have at least three users before creating a generic primitive.
And I just know that I am going to regret this deeply, but I cannot resist posting the following URL:
http://en.wikipedia.org/wiki/Wikipedia:Avoid_Parkinson's_Bicycle_Shed_Effect
Thanx, Paul
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 11 lines · Paul E. McKenney
Quoted 6 lines
If you can show me have to pass a per-cpu variable (the variable, not a dereference of it) as an argument to an inline function, I'll implement this :-)
It has to be dereferenced after
local_bh_disable()for the read side acquisition.The way I did this in
treercu.cwas to create an array of references to the per-CPU data in question. Not necessarily recommended, but one way of doing it. That said, one could argue that we should wait until we have at least three users before creating a generic primitive.
The new percpu allocator allows you to create a per cpu pointer and pass it to functions.
per_cpu_ptr(pointer,cpu) is used to select an instance.
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
In reply to Eric DumazetQuoted 3 lines · Eric Dumazet
Instead of submitting a full patch again, we could first submit a new
include file containg all comments and inline functions ?
Well, I actually already suggested to David that he should just merge the last patch I saw floating around (with the "recursive" -> "readwrite" fix in the comment ;), so that we can at least get the basic issue fixed, and then we can tweak it a bit with smaller patches flying around.
And at least right now, the difference between the rwlock and the "count+spinlock" should be basically almost unnoticeable, and a very small implementation issue. They're entirely interchangeable, after all.
Quoted 5 lines
This include file could be local to netfilter, with a big stick on it to forbids its use on other areas (No changes in
Documentation/)Then, as soon as we can go back to pure RCU solution, we can safely delete this controversial-locking-nesting-per-cpu-thing ?
I don't have any strogn preferences, but I'd almost prefer to not abstract things out even that much. It's already pretty well hidden inside <netfilter/x_tables.h>, I'd hate to add a new file just for this.
As to just adding more commenting that it must not be used anywhere else, I certainly agree with that.
Quoted 5 lines
Instead of local/global name that Paul suggested, that was about 'global' locking all locks at the same time. Not any more the good name IMHO
Maybe something like local/remote or owner/foreigner ?
local/remote works for me, and yes, since we only take the remote side one CPU at a time, I guess "global" is misleading. But "owner/foreigner" sounds pretty odd.
Quoted 8 lines
One comment about this comment you wrote :
/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. This must be called with bottom half
* processing (and thus also preemption) disabled.
*/
Quoted 5 lines
Its true that BH should be disabled if caller runs on the cpu it wants to lock.
For other ones (true foreigners), there is
no requirement about BH (current cpu could be interrupted by a softirq and packets could fly)
Yes. Other CPU's just require preemption protection.
Quoted 17 lines
We could use following construct and not require disabling BH more than a short period of time.
(But preemption disabled for the whole duration)
preempt_disable(); // could becpu_migration_disable();int curcpu =
smp_processor_id();
/*
* Gather stats for current cpu : must disable BH
* before trying to lock.
*/local_bh_disable();xt_info_wrlock(curcpu);
// copy stats of this cpu on my private data (not shown here)xt_info_wrunlock(curcpu);local_bh_enable();
Quoted 8 lines
for_each_possible_cpu(cpu) { if (cpu == curcpu) continue; xt_info_wrlock(cpu); // fold stats of "cpu" on my private data (not shown here) xt_info_wrunlock((cpu); }
preempt_enable(); // could becpu_migration_enable();
Agreed.
Quoted 8 lines
So your initial comment could be changed to :
/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. If caller is about to lock its own lock,
* he must have disabled BH before. For other cpus, no special
* care but preemption disabled to guarantee no cpu migration. */
Ack.
Linus
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
In reply to Linus TorvaldsQuoted 5 lines · Linus Torvalds
I left the commentary about "readers" and "writers", because in many ways it's correct, and what the code actually does is very much to emulate a reader-writer lock. I put quotes around the uses in the comments to high-light that it largely _acts_ as a reader-writer lock.
Btw, I think it was Paul who pointed out that technically it's probably better to call them "local" and "global" lockers instead of "readers" and "writers".
That also probably clarifies the rules on when you use one over the other (ie reading off all the statistics is a "global" operation, as is obviously replacing the tables).
Of course, "readers" and "writers" is something most Linux lock people are more used to. Or "brlock" for the old-timers, but that involves a heavy dose of bad taste. The new use is much nicer, especially since it never takes the global lock on _all_ cpu's (which was really a killer in so many ways).
Linus
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 11 lines · Linus Torvalds
Quoted 5 lines · Linus Torvalds
I left the commentary about "readers" and "writers", because in many ways it's correct, and what the code actually does is very much to emulate a reader-writer lock. I put quotes around the uses in the comments to high-light that it largely _acts_ as a reader-writer lock.
Btw, I think it was Paul who pointed out that technically it's probably better to call them "local" and "global" lockers instead of "readers" and "writers".
exclusive vs non-exclusive is what the literature would call them in most cases I think.
Quoted 11 lines
That also probably clarifies the rules on when you use one over the other (ie reading off all the statistics is a "global" operation, as is obviously replacing the tables).
Of course, "readers" and "writers" is something most Linux lock people are more used to. Or "brlock" for the old-timers, but that involves a heavy dose of bad taste. The new use is much nicer, especially since it never takes the global lock on _all_ cpu's (which was really a killer in so many ways).
Linus
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
Quoted 9 lines · Peter Zijlstra
Quoted 8 lines · Linus Torvalds
Quoted 5 lines · Linus Torvalds
I left the commentary about "readers" and "writers", because in many ways it's correct, and what the code actually does is very much to emulate a reader-writer lock. I put quotes around the uses in the comments to high-light that it largely _acts_ as a reader-writer lock.
Quoted 6 lines
Quoted 3 lines
Btw, I think it was Paul who pointed out that technically it's probably better to call them "local" and "global" lockers instead of "readers" and "writers".
exclusive vs non-exclusive is what the literature would call them in most cases I think.
I would argue that the non-exclusive category includes both reader-writer locking and local-global locking. That said, we have an unusual variant of local-global in this case, as the global processing acquires only one of the locks at a time.
Thanx, Paul
Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}
In reply to Linus TorvaldsQuoted 18 lines · Linus Torvalds
Clue bat #3 [sic #4]:
- if you do not understand the difference between these two things, don't then try to claim that somebody _else_ who does understand it is "deluding himself".
Analogy time: Ethernet and a modem line can both get you on the internet. Now, let's say that Mr Peter Paste-Eater has heard of ethernet, and knows you can get on the internet with an ethernet connection, but he happens to use a modem line to do it.
Now, Peter Paste-Eater talks to you, and tells you he is connecting to the internet with ethernet, and proudly shows you his serial line and modem, and tells you how he uses ethernet to get onto the internet. You correct him, and tell him it's not ethernet. He argues for several days about how he gets on the internet, and that it must thus be ethernet, and that you're obviously just "deluding yourself".
Quoted 3 lines
Now, can you see why people react badly to you talking about "recursive locks"? You're acting like Peter Paste-Eater calling his serial line ethernet.
It could be worse. He could be running Ethernet over serial, e.g. L2TP. Or his serial line is a TP cable with RJ45 plugs - consumers like to call that Ethernet (cable) too.
Re: [PATCH] netfilter: use per-CPU recursive lock {XV}
In reply to Eric DumazetQuoted 13 lines · * Eric Dumazet ([email protected]) wrote:
From: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>So far, so good, should be ready for inclusion now, nobody complained :)
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
[...]
Quoted 21 lines
include/linux/netfilter/x_tables.h +21
-0+/* +* Per-CPU read/write lock associated with per-cpu table entries. +* This is not a general solution but makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since update must lock all +* possible CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. In some cases, the read lock will be acquired +* twice on the same CPU; this is okay because read locks handle nesting. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing tables +* any readers that are using the old tables have to complete +* before freeing the old table. This is handled by reading +* as a side effect of reading counters +*/
include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 465
Quoted 10 lines
include/linux/netfilter/x_tables.h +10
-0+DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +/* +* Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks)) +* because need to ensure that preemption is disable before +* acquiring per-cpu-variable, so do it as a two step process +*/ +local_bh_disable ();
Why do you need to disable bottom halves on the read-side ? You could probably just disable preemption, given this lock is nestable on the read-side anyway. Or I'm missing something obvious ?
Quoted 9 lines
include/linux/netfilter/x_tables.h +8
-0+read_lock (&__get_cpu_var (xt_info_locks)); +} + +static inline void xt_info_rdunlock_bh (void ) +{ +read_unlock_bh (&__get_cpu_var (xt_info_locks)); +} +
include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 483
Quoted 10 lines
include/linux/netfilter/x_tables.h +10
-0+static inline void xt_info_wrlock (unsigned int cpu) +{ +write_lock (&per_cpu (xt_info_locks, cpu)); +} + +static inline void xt_info_wrunlock (unsigned int cpu) +{ + +write_unlock (&per_cpu (xt_info_locks, cpu)); +}
[...]
Mathieu
Signature · 2 lines
Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
Re: [PATCH] netfilter: use per-CPU recursive lock {XV}
Quoted 41 lines · Mathieu Desnoyers
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:
From: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>So far, so good, should be ready for inclusion now, nobody complained :)
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
[...]
Quoted 27 lines
include/linux/netfilter/x_tables.h +27
-0+/* +* Per-CPU read/write lock associated with per-cpu table entries. +* This is not a general solution but makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since update must lock all +* possible CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. In some cases, the read lock will be acquired +* twice on the same CPU; this is okay because read locks handle nesting. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing tables +* any readers that are using the old tables have to complete +* before freeing the old table. This is handled by reading +* as a side effect of reading counters +*/ +DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +/* +* Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks))
Quoted 8 lines
include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 465
Quoted 4 lines
include/linux/netfilter/x_tables.h +4
-0+* because need to ensure that preemption is disable before +* acquiring per-cpu-variable, so do it as a two step process +*/ +local_bh_disable ();Why do you need to disable bottom halves on the read-side ? You could probably just disable preemption, given this lock is nestable on the read-side anyway. Or I'm missing something obvious ?
It may not be obvious, but subject already raised on this list, so I'll try to be as precise as possible (But may be wrong on some points, I'll let Patrick correct me if necessary)
ipt_do_table() is not a readonly function returning a verdict.
1) It handles a stack (check how is used next->comefrom) that seems to be stored on rules themselves. (This is how I understand this code) This is safe as each cpu has its own copy of rules/counters, and BH protected.
2) It also updates two 64 bit counters (bytes/packets) on each matched rule.
3) Some netfilter matches/targets probably rely on the fact their handlers are run with BH disabled by their caller (ipt_do_table()/arp/ip6...)
These must be BH protected (and preempt disabled too), or else :
1) A softirq could interrupt a process in the middle of ipt_do_table() and corrupt its "stack".
2) A softirq could interrupt a process in ipt_do_table() in the middle of the ADD_COUNTER(). Some counters could be corrupted.
3) Some netfiler extensions would break.
Previous linux versions already used a read_lock_bh() here, on a single and shared rwlock, there is nothing new on this BH locking AFAIK.
Thank you
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] netfilter: use per-CPU recursive lock {XV}
Quoted 74 lines · * Eric Dumazet ([email protected]) wrote:
Quoted 41 lines · Mathieu Desnoyers
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:
From: Stephen Hemminger <[email protected]>
Quoted 4 lines
Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.
Signed-off-by Stephen Hemminger <[email protected]>So far, so good, should be ready for inclusion now, nobody complained :)
I include the final patch, merge of your last two patches.
David, could you please review it once again and apply it if it's OK ?
[...]
Quoted 27 lines
include/linux/netfilter/x_tables.h +27
-0+/* +* Per-CPU read/write lock associated with per-cpu table entries. +* This is not a general solution but makes reader locking fast since +* there is no shared variable to cause cache ping-pong; but adds an +* additional write-side penalty since update must lock all +* possible CPU's. +* +* Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu. +* It needs to ensure that the rules are not being changed while packet +* is being processed. In some cases, the read lock will be acquired +* twice on the same CPU; this is okay because read locks handle nesting. +* +* Write lock is used in two cases: +* 1. reading counter values +* all readers need to be stopped and the per-CPU values are summed. +* +* 2. replacing tables +* any readers that are using the old tables have to complete +* before freeing the old table. This is handled by reading +* as a side effect of reading counters +*/ +DECLARE_PER_CPU (rwlock_t, xt_info_locks); + +static inline void xt_info_rdlock_bh (void ) +{ +/* +* Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks)) Quoted 8 lines
include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 465
Quoted 4 lines
include/linux/netfilter/x_tables.h +4
-0+* because need to ensure that preemption is disable before +* acquiring per-cpu-variable, so do it as a two step process +*/ +local_bh_disable ();Why do you need to disable bottom halves on the read-side ? You could probably just disable preemption, given this lock is nestable on the read-side anyway. Or I'm missing something obvious ?
It may not be obvious, but subject already raised on this list, so I'll try to be as precise as possible (But may be wrong on some points, I'll let Patrick correct me if necessary)
ipt_do_table()is not a readonly function returning a verdict.1) It handles a stack (check how is used
next->comefrom) that seems to be stored on rules themselves. (This is how I understand this code) This is safe as each cpu has its own copy of rules/counters, and BH protected.2) It also updates two 64 bit counters (bytes/packets) on each matched rule.
3) Some netfilter matches/targets probably rely on the fact their handlers are run with BH disabled by their caller (ipt_do_table()/arp/ip6...)
These must be BH protected (and preempt disabled too), or else :
1) A softirq could interrupt a process in the middle of
ipt_do_table()and corrupt its "stack".2) A softirq could interrupt a process in
ipt_do_table()in the middle of theADD_COUNTER(). Some counters could be corrupted.
Quoted 6 lines
3) Some netfiler extensions would break.
Previous linux versions already used a
read_lock_bh()here, on a single and shared rwlock, there is nothing new on this BH locking AFAIK.Thank you
Thanks for the explanation. It might help to document the role of bh disabling for the reader in a supplementary code comment, otherwise one might think it's been put there to match the bottom half disabling used on the write-side, which has the supplementary role of making sure bh will not deadlock (and this precise behavior is not needed usually on the read-side).
One more point :
* 1. reading counter values
* all readers need to be stopped and the per-CPU values are summed.
Maybe it's just me, but this sentence does not seem to clearly indicate that we have :
for_each_cpu()
write lock()
read data
write unlock()
One might interpret it as :
for_each_cpu()
write lock()
read data
for_each_cpu()
write unlock()
Or maybe it's just my understanding of English that's not perfect. Anyhow, rewording this sentence might not hurt. Something along the lines of :
"reading counter values
all readers are iteratively stopped to have their per-CPU values summed"
This is an important difference, as this behaves more like a RCU-based mechanism than a global per-cpu read/write lock where all the write locks would be taken at once.
Mathieu
Signature · 2 lines
Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
In reply to Linus TorvaldsQuoted 3 lines · Linus Torvalds
Ok, so others already pointed out how dangerous/buggy this looks, but I'd like to strengthen that a bit more:
I believe that at least some of this is naming...
Quoted 1 line · Stephen Hemminger
[ . . . ]
Quoted 19 lines
If you want a counting read-lock (in _order_ to allow recursion, but not because the lock itself is somehow recursive!), then that function should look like this:
void xt_info_rdlock_bh(void) { struct xt_info_lock *lock local_bh_disable(); lock = &__get_cpu_var(xt_info_locks); read_lock(&lock->lock); }And then the "unlock" should be the reverse. No games, no crap, and hopefully then no bugs. And if you do it that way, you don't even need the comments, although quite frankly, it probably makes a lot of sense to talk about the interaction between "
local_bh_disable()" and the preempt count, and why you're not using "read_lock_bh()".
Quoted 3 lines
And if you don't want a read-lock, then fine - don't use a read-lock, do something else. But then don't just re-implement it (badly) either and call it something else!
Sigh!!!
Part of the problem is that back in 1971, Courtois, Heymans, and Parnas foolishly named their article "Concurrent Control with 'Readers' and 'Writers'", which lead to the name "reader-writer lock". This started really biting around 1991, when Hsieh and Weihl created a reader-optimized lock similar to brlock, but with each of the per-CPU locks being exclusive rather than each being an rwlock.
The problem was that Hsieh's and Weihl's lock was more than just a reader-writer lock. It could also be used (and -was- used) as a local/global lock, where for example you acquire your own lock to make local changes, and acquire all of the locks to obtain a consistent view of global state. In which case, you would read-acquire the lock in order to write, and write-acquire the lock in order to read. Blech.
So, would it help if the function names names in this patch said something about "local" and "global" rather than "read" and "write"?
Thanx, Paul
Quoted 6 lines
Linus
PS: Ingo, why do the
*_bh()functions inkernel/spinlock.cdo _both_ a "local_bh_disable()" and a "preempt_disable()"? BH disable should disable preemption too, no? Or am I confused? In which case we need that in the aboverdlock_bhtoo.
Re: [PATCH] netfilter: use per-cpu recursive lock (v11)
Quoted 2 lines · Paul E. McKenney
I believe that at least some of this is naming...
Maybe.
I do agree that the way netfilter would use the lock is somewhat different from a normal 'reader-writer' lock, since this special case of readers is about a per-cpu thing.
Quoted 2 lines
So, would it help if the function names names in this patch said something about "local" and "global" rather than "read" and "write"?
Oh, I would have no problem at all with 'local' and 'global', in fact it would explain _why_ that read-write lock works.
The problem with naming I have is with the 'recursive' part. There is no ambiguity what-so-ever about what a "recursive lock" is (at least of the traditional kind), and the lock described here is not it.
So don't get me wrong - I could certainly live with a special lock in the networking. BUT:
- it had damn well be documented as to what it does, and why it works
- and it had better actually _work_, and not be buggy.
I suspect that using our regular reader-writer locks works well enough, and yes, it's probably worth making it really clear that the reader variety can only ever be used in the "local" form. That kind of is implied by the whole function, though.
And if somebody wants to open-code it as a per-cpu spinlock and a per-cpu 'local counter', I can live with that too, but at that point I want people to just be a lot more careful, and also document it a lot more.
Linus
Re: [PATCH] netfilter: use per-cpu recursive lock (v10)
In reply to Paul MackerrasQuoted 5 lines · Paul Mackerras
Quoted 2 lines · Paul E. McKenney
But a single CPU is acquiring one lock per CPU, so all the increments are to one CPU's
preempt_count. :-(
Quoted 7 lines
OK, I see, so a task can't take more than 255 spinlocks without overflowing the preempt count, which seems a bit limiting.
There are 6 free bits in the
preempt_countcurrently, so the preempt count could be expanded to 14 bits, which would be enough for all current systems. Beyond that I guess we could makepreempt_countbe a long and allow bigger counts on 64-bit architectures.
Or we use the trick Eric suggested and Steve employed in the most recent patch. ;-)
An alternative would be for the update code to acquire but one lock at a time, but this would likely require another lock to exclude other updaters and I believe would also require restructuring the count accumulation.
So Steve's current patch seems a bit less intrusive, overall.
Thanx, Paul
Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU (v3)
In reply to David MillerQuoted 5 lines · David Miller
I really think we should entertain the idea where we don't RCU quiesce when adding rules. That was dismissed as not workable because the new rule must be "visible" as soon as we return to userspace but let's get real, effectively it will be.
I never understood that dismissal.
The new rule _will_ be visible as we return to user space. It's just that old packets may still be in flight in other queues.
But that is true even _without_ the "synchronize_net()". The old packets just had to make it slightly further in the queueing - but as far as user space is concerned, there is absolutely _zero_ difference between the two. In both cases it may see packets queued with the old rules.
Quoted 2 lines
I almost cringed when the per-spinlock idea was proposed, but per-cpu rwlocks just takes things too far for my tastes.
I really personally would prefer the RCU approach too. I don't think rwlocks are any more cringe-worthy than spinlocks, although it is true that they tend to be slightly more expensive.
The pure RCU "just get rid of the unnecessary 'serialze_net()'" approach seems to be clearly superior to either.
Linus
Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU (v3)
In reply to David MillerQuoted 11 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Wed, 15 Apr 2009 23:07:29 +0200Quoted 7 lines
Well, it seems original patch was not so bad after all
http://lists.netfilter.org/pipermail/netfilter-devel/2006-January/023175.html
So change per-cpu spinlocks to per-cpu rwlocks
and use
read_lock()inipt_do_table()to allow recursion...
Quoted 7 lines
Grumble, one more barrier to getting rid of rwlocks in the whole tree. :-/
I really think we should entertain the idea where we don't RCU quiesce when adding rules. That was dismissed as not workable because the new rule must be "visible" as soon as we return to userspace but let's get real, effectively it will be.
We had to RCU quiesce to be sure old rules were not any more used before freeing them. Alternative is to defer freeing via call_rcu() but subject to OOM.
With 200 basic rules, size of rules table is about 40960 bytes per cpu. (88 pages taken on vmalloc virtual space on my 8 cpus machine)
0xfcaf8000-0xfcb03000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb04000-0xfcb0f000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb10000-0xfcb1b000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb1c000-0xfcb27000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb28000-0xfcb33000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb34000-0xfcb3f000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb40000-0xfcb4b000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb4c000-0xfcb57000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
This kind of monolithic huge object is hard to handle with RCU semantic, more suitable for handling set of small objects (struct file for example), even if RCU can have a backoff of 10000 elements in its queue...
Quoted 6 lines
If there are any stale object reference issues, we can use RCU object destruction to handle that kind of thing.
I almost cringed when the per-spinlock idea was proposed, but per-cpu rwlocks just takes things too far for my tastes.
In my humble opinion, this is a reasonnable compromise, and Stephen patch version 4 is ok for me.
Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU (v3)
Quoted 35 lines · Eric Dumazet
Quoted 11 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Wed, 15 Apr 2009 23:07:29 +0200Quoted 7 lines
Well, it seems original patch was not so bad after all
http://lists.netfilter.org/pipermail/netfilter-devel/2006-January/023175.html
So change per-cpu spinlocks to per-cpu rwlocks
and use
read_lock()inipt_do_table()to allow recursion...Quoted 7 lines
Grumble, one more barrier to getting rid of rwlocks in the whole tree. :-/
I really think we should entertain the idea where we don't RCU quiesce when adding rules. That was dismissed as not workable because the new rule must be "visible" as soon as we return to userspace but let's get real, effectively it will be.
We had to RCU quiesce to be sure old rules were not any more used before freeing them. Alternative is to defer freeing via
call_rcu()but subject to OOM.With 200 basic rules, size of rules table is about 40960 bytes per cpu. (88 pages taken on vmalloc virtual space on my 8 cpus machine)
0xfcaf8000-0xfcb03000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb04000-0xfcb0f000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb10000-0xfcb1b000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb1c000-0xfcb27000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb28000-0xfcb33000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb34000-0xfcb3f000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb40000-0xfcb4b000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc 0xfcb4c000-0xfcb57000 45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
Quoted 3 lines
This kind of monolithic huge object is hard to handle with RCU semantic, more suitable for handling set of small objects (struct file for example), even if RCU can have a backoff of 10000 elements in its queue...
To be honest, the per-CPU-locking approach looks pretty good to me for this particular case. That said, the problem you mention above does have some straightforward solutions.
One solution to consider would be to do the call_rcu(), but to keep a counter of the number of calls, perhaps something like the following:
call_rcu(...);
if (++count > 50) {
synchronize_rcu();
count = 0;
}Of course, you might (or might not) need to atomically increment count, and you of course would want to replace the "50" with some symbolic constant, or perhaps even a variable whose value might be determined by the size of the object and/or the amount of memory available.
Would this help?
Quoted 8 lines
Quoted 5 lines
If there are any stale object reference issues, we can use RCU object destruction to handle that kind of thing.
I almost cringed when the per-spinlock idea was proposed, but per-cpu rwlocks just takes things too far for my tastes.
In my humble opinion, this is a reasonnable compromise, and Stephen patch version 4 is ok for me.
Again, the per-CPU-locking approach looks good to me, as well.
But if it turns out that we really do need an RCU implementation with really short grace periods (tens of microseconds typical latency on mid-range multiprocessors, those with SGI Altix systems would suffer a bit more), then it can be done. It would need to be yet another implementation of RCU for the following reasons:
o High update-side overhead (broadcast IPIs via
smp_call_function(). This is not a problem in this case, but would be a showstopper for (say) dcache. I don't know of any way of fixing this.
o Defeats power-conservation measures by waking up every CPU
at every grace period. (Might be fixable, for example, by using
the same dyntick tricks used by preemptable and hierarchical RCU. But not recommended for first implementation.)
o Poor update-side scalability. (Definitely fixable, but the
fix should be to the underlying smp_call_function() primitives.)
o No ability to share grace periods among concurrent
synchronize_rcu() primitves. (Definitely fixable, but not recommended until needed. Unlikely to be needed -- after all, if your grace period completes in 10 microseconds, just how many concurrent updates do you expect there to be???)
o No call_rcu() style primtive. (Definitely fixable, but not
recommended until needed. Besides, if the grace period only takes a few tens of microseconds, why exactly do you need an asynchronous interface?
If this is needed, one good starting point would be Mathieu Desnoyers's user-level RCU primitive. The main change would be replacing the POSIX signals with smp_call_function().
Yet again, I don't see a real problem with the per-CPU locking approach in this case, but anything to prevent Dave Miller from having to suffer the pain of hashed locks! (Can't say that I have ever used hashed locks myself, but I could imagine that they might impose cache-thrashing and deadlock issues.)
Thanx, Paul
David Miller
maintainerRe: [PATCH] netfilter: use per-cpu spinlock rather than RCU (v3)
In reply to Stephen HemmingerFrom: Stephen Hemminger <[email protected]>
Date: Tue, 14 Apr 2009 14:13:51 -0700
Quoted 9 lines
This is an alternative version of ip/ip6/arp tables locking using per-cpu locks. This avoids the overhead of
synchronize_net()during update but still removes the expensive rwlock in earlier versions.The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. The slow case involves acquiring the locks on all cpu's.
Quoted 4 lines
The mutex that was added for 2.6.30 in
xt_tableis unnecessary since there already is a mutex for xt[af].mutex that is held.Signed-off-by Stephen Hemminger <[email protected]>
Things seem to be winding down, good. :-)
I'll let Patrick McHardy merge this to me with his other pending netfilter fixes.
Thanks!
Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU
In reply to Eric DumazetQuoted 51 lines · On Tue, 14 Apr 2009 17:49:57 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 17 lines · Stephen Hemminger
Quoted 14 lines · On Tue, 14 Apr 2009 16:23:33 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 13 lines · Patrick McHardy
Quoted 12 lines · Stephen Hemminger
This is an alternative version of ip/ip6/arp tables locking using per-cpu locks. This avoids the overhead of
synchronize_net()during update but still removes the expensive rwlock in earlier versions.The idea for this came from an earlier version done by Eric Duzamet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. The slow case involves acquiring the locks on all cpu's.
The mutex that was added for 2.6.30 in
xt_tableis unnecessary since there already is a mutex for xt[af].mutex that is held.Quoted 6 lines
Quoted 4 lines
Quoted 3 lines
Quoted 2 lines
Tested basic functionality (add/remove/list), but don't have test cases for stress, ip6tables or arptables.
Thanks Stephen, I'll do some testing with ip6tables.
Here is the patch I cooked on top of Stephen one to get proper locking.
I see no demonstrated problem with locking in my version.
Yes, I did not crash any machine around there, should we wait for a bug report ? :)
Quoted 13 lines
The reader/writer race is already handled. On replace the race of
CPU 0 CPU 1
lock (iptables(1))
refer to oldinfo
swap in new info
foreach CPU
lock iptables(i)
(spin) unlock(iptables(1))
read oldinfo
unlock
...Quoted 2 lines
The point is my locking works, you just seem to feel more comfortable with a global "stop all CPU's" solution.
Oh right, I missed that
xt_replace_table()was *followed* by aget_counters()call, but I am pretty sure something is needed inxt_replace_table().A memory barrier at least (
smp_wmb())As soon as we do "
table->private= newinfo;", other cpus might fetch incorrect values fornewinfo->fields.
Quoted 8 lines
In the past, we had a write_lock_bh()/write_unlock_bh() pair that was doing this for us.
Then we hadrcu_assign_pointer()that also had this memory barrier implied.Even if
vmalloc()calls we do before callingxt_replace_table()probably already force barriers, add one for reference, just in case we change callers logic to callkmalloc()instead ofvmalloc()or whatever...
You are right, doing something with barrier would be safer there. How about using xchg?
@@ -682,26 +668,19 @@ xt_replace_table(struct xt_table *table,
struct xt_table_info *newinfo,
int *error)
{
- struct xt_table_info *oldinfo, *private;
+ struct xt_table_info *private;
/* Do the substitution. */
- 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);
- mutex_unlock(&table->lock);
*error = -EAGAIN;
return NULL;
}
- oldinfo = private;
- rcu_assign_pointer(table->private, newinfo);
- newinfo->initial_entries = oldinfo->initial_entries;
- mutex_unlock(&table->lock);
-
- synchronize_net();
- return oldinfo;
+ newinfo->initial_entries = private->initial_entries;
+ return xchg(&table->private, newinfo);
}
EXPORT_SYMBOL_GPL(xt_replace_table);
P.s: we all missed the ordering bug in the RCU version??
Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49
In reply to Paul E. McKenneyQuoted 28 lines · On Fri, 10 Apr 2009 21:15:33 -0700 "Paul E. McKenney"…
Quoted 17 lines · Linus Torvalds
Quoted 2 lines · David Miller
[ CC:'ing netfilter-devel and netdev... ]
I wonder if we should bring in the RCU people too, for them to tell you that the networking people are beign silly, and should not synchronize with the very heavy-handed
synchronize_net()but instead of doing synchronization (which is probably why adding a few hundred rules then takes several seconds - each synchronizes and that takes a timer tick or so), add the rules to be free'd on some rcu-freeing list for later freeing.
Quoted 6 lines
Or whatever. Paul?
synchronize_net()just callssynchronize_rcu(), and with that knowledge and a simplegit show 784544739a25c30637397ace5489eeb6e15d7d49I bet you can already tell people how to fix their performance issue.
Well, I am certainly happy to demonstrate my ignorance of the networking code by throwing out a few suggestions.
Quoted 6 lines
So, Dave and Steve, you might want to get out your barf bag before reading further. You have been warned! ;-)
1. Assuming that the
synchronize_net()is intended to guarantee
that the new rules will be in effect before returning to user space:
In this case it is to make sure that the old counter table is no longer being used by other cpu's receiving.
Quoted 17 lines
a. Split this functionality, so that there is a new
user-space primitive that installs a new rule, but without waiting. They provide an additional user-space primitive that waits for the rules to take effect. Then, when loading a long list of rules, load them using the non-waiting primitive, and wait at the end.b. As above, but provide a flag that says whether or not
to wait. Same general effect.But I am not seeing the direct connection between this patch and netfilter, so...
2. For the
xt_replace_table()case, it would be necessary to add an
rcu_headto thext_table_info, and replace each caller's direct calls toxt_free_table_info()withcall_rcu().
Quoted 8 lines
Now this has an issue in that the caller wants to return the final counter values. My assumption is that these values do not in fact need to be exact. If I am wrong about that, then my suggestion would lose the counts from late readers. I must defer to the networking guys as to whether this is acceptable or not. If not, more head-scratching would be required. (But it looks to me that the rule is being trashed, so who cares about the extra counts?)
The problem is that users want to account for every byte.
Quoted 4 lines
In addition, a malicious user might be able to force this to happen extremely frequently, running the system out of memory. One way to fix this is to invoke
synchronize_net()one out of 20 times or some such.
Malicious user == root, therefore don't care.
Quoted 5 lines
3. For the
alloc_counters()case, the comments indicate that we
really truly do want an atomic sampling of the counters. The counters are 64-bit entities, which is a bit inconvenient. Though people using this functionality are no doubt quite happy to never have to worry about overflow, I hasten to add!
And we need snapshot of all counters (which are not even an array but a skip list).
Quoted 90 lines
I will nevertheless suggest the following egregious hack to get a consistent sample of one counter for some other CPU:
a. Disable interrupts
b. Atomically exchange the bottom 32 bits of the
counter with the value zero.
c. Atomically exchange the top 32 bits of the counter
with the value zero.
d. Concatenate the values obtained in (b) and (c), which
is the snapshot value.
e. Re-enable interrupts. Yes, for each counter. Do it
for the honor of the -rt patchset. ;-)Disabling interrupts should make it impossible for the low-order 32 bits of the counter to overflow before we get around to zeroing the upper 32 bits. Yes, this is horribly paranoid, but please keep in mind that even my level of paranoia is not always sufficient to keep RCU working correctly. :-/
Architectures with 64-bit atomics can simply do a 64-bit exchange (or
cmpxchg(), for that matter).Now we still have the possibility that the other CPU is still hammering away on the counter that we just zeroed from a long-running RCU read-side critical section.
So, we also need to add an
rcu_headsomewhere, perhaps reuse the one inxt_table_info, create a second one, or squirrel one away somewhere else. As long as there is a way to get to the old counter values. And a flag to indicate that thercu_headis in use. It is socially irresponsible to pass a givenrcu_headtocall_rcu()before it has been invoked after the previous time it was passed tocall_rcu(). But you guys all knew that already.We replace the
synchronize_net()withcall_rcu(), more or less. Thecall_rcu()probably needs to be under the lock -- or at the very least, setting the flag saying that it is in use needs to be under the lock.The RCU callback function traverses the old counters one last time, adding their values to the new set of counters. No atomic exchange tricks are required this time, since all the RCU readers that could possibly have held a reference to the old set of counters must now be done. We now clear the flag, allowing the next counter snapshot to proceed.
OK, OK, Dave and Steve, I should have suggested that you get two barf bags. Maybe three. ;-)
Additional caveat: coward that I am, I looked only at the IPv4 code. There might well be additional complications in the arp and IPv6 code.
However, I do believe that something like this might actually work.
Thoughts?
Thanx, Paul
Quoted 30 lines
Linus
---
Quoted 13 lines
Quoted 13 lines
Quoted 10 lines · On Fri, 10 Apr 2009 17:15:52 +0800 (SGT) Jeff Chua <[email protected]>…
Adding 200 records in iptables took 6.0sec in 2.6.30-rc1 compared to 0.2sec in 2.6.29. I've bisected down this commit.
There are a few patches on top of the original patch. When I reverted the original commit + changing
rcu_read()torcu_read_bh(), it speeds up the inserts back to .2sec again.I'm loading all the firewall rules during boot-up and this 6 secs slowness is really not very nice to wait for.
Quoted 10 lines
Quoted 9 lines
The performance benefit during operation is more important. The load time is fixable. The problem is probably generic to any set of rules, but could you post some info about your configuration (like the rule set), and the system configuration (# of cpu's, config etc). --
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49
Quoted 67 lines · Stephen Hemminger
Quoted 28 lines · On Fri, 10 Apr 2009 21:15:33 -0700 "Paul E. McKenney"…
Quoted 17 lines · Linus Torvalds
Quoted 2 lines · David Miller
[ CC:'ing netfilter-devel and netdev... ]
I wonder if we should bring in the RCU people too, for them to tell you that the networking people are beign silly, and should not synchronize with the very heavy-handed
synchronize_net()but instead of doing synchronization (which is probably why adding a few hundred rules then takes several seconds - each synchronizes and that takes a timer tick or so), add the rules to be free'd on some rcu-freeing list for later freeing.
Quoted 6 lines
Or whatever. Paul?
synchronize_net()just callssynchronize_rcu(), and with that knowledge and a simplegit show 784544739a25c30637397ace5489eeb6e15d7d49I bet you can already tell people how to fix their performance issue.
Well, I am certainly happy to demonstrate my ignorance of the networking code by throwing out a few suggestions.
Quoted 6 lines
So, Dave and Steve, you might want to get out your barf bag before reading further. You have been warned! ;-)
1. Assuming that the
synchronize_net()is intended to guarantee
that the new rules will be in effect before returning to user space:In this case it is to make sure that the old counter table is no longer being used by other cpu's receiving.
Quoted 17 lines
a. Split this functionality, so that there is a new
user-space primitive that installs a new rule, but without waiting. They provide an additional user-space primitive that waits for the rules to take effect. Then, when loading a long list of rules, load them using the non-waiting primitive, and wait at the end.b. As above, but provide a flag that says whether or not
to wait. Same general effect.But I am not seeing the direct connection between this patch and netfilter, so...
2. For the
xt_replace_table()case, it would be necessary to add an
rcu_headto thext_table_info, and replace each caller's direct calls toxt_free_table_info()withcall_rcu().Quoted 8 lines
Now this has an issue in that the caller wants to return the final counter values. My assumption is that these values do not in fact need to be exact. If I am wrong about that, then my suggestion would lose the counts from late readers. I must defer to the networking guys as to whether this is acceptable or not. If not, more head-scratching would be required. (But it looks to me that the rule is being trashed, so who cares about the extra counts?)
Quoted 1 line
The problem is that users want to account for every byte.
Ah!!!
Is this particular code path one of the ones responsible for the slowdown?
Quoted 6 lines
Quoted 4 lines
In addition, a malicious user might be able to force this to happen extremely frequently, running the system out of memory. One way to fix this is to invoke
synchronize_net()one out of 20 times or some such.Malicious user == root, therefore don't care.
Sometimes things work out OK. ;-)
Quoted 8 lines
Quoted 5 lines
3. For the
alloc_counters()case, the comments indicate that we
really truly do want an atomic sampling of the counters. The counters are 64-bit entities, which is a bit inconvenient. Though people using this functionality are no doubt quite happy to never have to worry about overflow, I hasten to add!And we need snapshot of all counters (which are not even an array but a skip list).
OK. However, the code seems to swap in a new set of counters intended to account for subsequent packets. So I was assuming that "snapshot" meant that a given packet had to be accounted for precisely, but that it was OK to do so either in the old set or the new set, as long as it appeared in exactly one of the two sets.
If this assumption is accurate, then something like the following should work.
If my assumption is wrong, what exactly does this snapshot need to do?
Thanx, Paul
Quoted 90 lines
Quoted 90 lines
I will nevertheless suggest the following egregious hack to get a consistent sample of one counter for some other CPU:
a. Disable interrupts
b. Atomically exchange the bottom 32 bits of the
counter with the value zero.
c. Atomically exchange the top 32 bits of the counter
with the value zero.
d. Concatenate the values obtained in (b) and (c), which
is the snapshot value.
e. Re-enable interrupts. Yes, for each counter. Do it
for the honor of the -rt patchset. ;-)Disabling interrupts should make it impossible for the low-order 32 bits of the counter to overflow before we get around to zeroing the upper 32 bits. Yes, this is horribly paranoid, but please keep in mind that even my level of paranoia is not always sufficient to keep RCU working correctly. :-/
Architectures with 64-bit atomics can simply do a 64-bit exchange (or
cmpxchg(), for that matter).Now we still have the possibility that the other CPU is still hammering away on the counter that we just zeroed from a long-running RCU read-side critical section.
So, we also need to add an
rcu_headsomewhere, perhaps reuse the one inxt_table_info, create a second one, or squirrel one away somewhere else. As long as there is a way to get to the old counter values. And a flag to indicate that thercu_headis in use. It is socially irresponsible to pass a givenrcu_headtocall_rcu()before it has been invoked after the previous time it was passed tocall_rcu(). But you guys all knew that already.We replace the
synchronize_net()withcall_rcu(), more or less. Thecall_rcu()probably needs to be under the lock -- or at the very least, setting the flag saying that it is in use needs to be under the lock.The RCU callback function traverses the old counters one last time, adding their values to the new set of counters. No atomic exchange tricks are required this time, since all the RCU readers that could possibly have held a reference to the old set of counters must now be done. We now clear the flag, allowing the next counter snapshot to proceed.
OK, OK, Dave and Steve, I should have suggested that you get two barf bags. Maybe three. ;-)
Additional caveat: coward that I am, I looked only at the IPv4 code. There might well be additional complications in the arp and IPv6 code.
However, I do believe that something like this might actually work.
Thoughts?
Thanx, Paul
Quoted 30 lines
Linus
---
Quoted 13 lines
Quoted 13 lines
Quoted 10 lines · On Fri, 10 Apr 2009 17:15:52 +0800 (SGT) Jeff Chua <[email protected]>…
Adding 200 records in iptables took 6.0sec in 2.6.30-rc1 compared to 0.2sec in 2.6.29. I've bisected down this commit.
There are a few patches on top of the original patch. When I reverted the original commit + changing
rcu_read()torcu_read_bh(), it speeds up the inserts back to .2sec again.I'm loading all the firewall rules during boot-up and this 6 secs slowness is really not very nice to wait for.
Quoted 10 lines
Quoted 9 lines
The performance benefit during operation is more important. The load time is fixable. The problem is probably generic to any set of rules, but could you post some info about your configuration (like the rule set), and the system configuration (# of cpu's, config etc). --
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49
In reply to Paul E. McKenneyQuoted 4 lines · Paul E. McKenney
1. Assuming that the
synchronize_net()is intended to guarantee
that the new rules will be in effect before returning to user space:
Btw, I think that's a bad assumption.
The thing is, nobody can really care if the new rules are in effect or not, because the thing you race with is not the "return to user space" part, but the incoming packets.
And those incoming packets might have been incoming before the rules were set up too.
So I seriously doubt you need to synchronize with any returning to user space. What you want to synchronize with is then later actions that do things like turning on the interface that the rules are attached to etc!
So I would suggest:
- remove the synchronize_net() entirely. Replace it with just freeing the old rules using RCU.
- new packets will always end up seeing the new rules. That includes the case of somebody doing "ifconfig eth0 up" that enables a new source of packets, so there are no real security issues.
- if you enabled your network interfaces before you updated your packet filtering rules, you already had a window where packets would come in with the old rules, so doing a "synchronize_net()" in no way protects against any race conditions anyway.
Am I missing something?
Linus
Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney
1. Assuming that the
synchronize_net()is intended to guarantee
that the new rules will be in effect before returning to user space:Btw, I think that's a bad assumption.
It does indeed appear to be!
Quoted 20 lines
The thing is, nobody can really care if the new rules are in effect or not, because the thing you race with is not the "return to user space" part, but the incoming packets.
And those incoming packets might have been incoming before the rules were set up too.
So I seriously doubt you need to synchronize with any returning to user space. What you want to synchronize with is then later actions that do things like turning on the interface that the rules are attached to etc!
So I would suggest:
- remove the
synchronize_net()entirely. Replace it with just freeing the old rules using RCU.- new packets will always end up seeing the new rules. That includes the case of somebody doing "ifconfig eth0 up" that enables a new source of packets, so there are no real security issues.
Quoted 6 lines
- if you enabled your network interfaces before you updated your packet filtering rules, you already had a window where packets would come in with the old rules, so doing a "
synchronize_net()" in no way protects against any race conditions anyway.Am I missing something?
The issue at this point seems to be the need to get accurate snapshots of various counters -- there are a number of Linux networking users who need to account for every byte flowing through their systems. However, it is also necessary to update these counters very efficiently, given that they are updated on a per-packet basis. The current approach is as follows:
1. Install a new set of counters.
2. Wait for a grace period to elapse.
3. At this point, we know that all subsequent counting will happen
on the new set of counters.
4. Add the value of the old set of counters to the new set of
counters.
5. Copy the old set of counters up to user space.
So we get a good snapshot in #5, while #4 ensures that we don't lose any counts when taking future snapshots. Unfortunately, #2 hits us with grace-period latencies on the critical path.
We are going through the following possibilities:
o Stick with the current approach, and ask people to move to
new batch-oriented interfaces. However, a 30x decrease in performance is pretty grim, even for an old-style interface.
o Use various atomic tricks to get an immediate snapshot of the
old counters after step 1. Make step 3 use call_rcu() instead of synchronize_rcu(), and then step 4 happens off the critical path.
This approach moves the RCU grace period off of the critical path, but the atomic tricks are extremely ugly on 32-bit SMP machines. 32-bit UP machines and 64-bit machines are not too bad, though the 32-bit UP case does add preemption-disable overhead on the counter-update fastpath.
o Provide some sort of expedited synchronize_rcu(). This might
be able to decrease the hit from 30x down to maybe 5x. But I might need to do this for the fast-boot folks anyway, though I am first trying to get away with just speeding up synchronized_rcu(). Though I was not thinking in terms of 6x, let alone 30x.
Please note that this would not be a drop-in replacement for synchronize_rcu(). One would use synchronize_rcu_expedited() (or whatever) only when the system really could not get any useful work done while the grace period was in progress. The general approach would be to keep the whole machine busy trying to get the grace period done as soon as possible.
Thanx, Paul
Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49
Hi.
Quoted 3 lines · Paul E. McKenney
The issue at this point seems to be the need to get accurate snapshots of various counters -- there are a number of Linux networking users who need to account for every byte flowing through their systems. However,
If we add or change the rule we can not know if iptables' return to userspace does mean that rule started to act. There may be other queues already filled with the packets which could match the new rule (like receiving socket buffer). So effectively we want it to take effect very soon. What if there will be a timer which will synchronize RCU-added states, so if we update single rule - it will take effect in a second, and if we update bunch of them - during the delay second we pretty much can load them all.
Signature · 1 line
Evgeniy Polyakov
Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49
In reply to Paul E. McKenneyQuoted 87 lines · On Sat, 11 Apr 2009 17:34:45 -0700 "Paul E. McKenney"…
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney
1. Assuming that the
synchronize_net()is intended to guarantee
that the new rules will be in effect before returning to user space:Btw, I think that's a bad assumption.
It does indeed appear to be!
Quoted 20 lines
The thing is, nobody can really care if the new rules are in effect or not, because the thing you race with is not the "return to user space" part, but the incoming packets.
And those incoming packets might have been incoming before the rules were set up too.
So I seriously doubt you need to synchronize with any returning to user space. What you want to synchronize with is then later actions that do things like turning on the interface that the rules are attached to etc!
So I would suggest:
- remove the
synchronize_net()entirely. Replace it with just freeing the old rules using RCU.- new packets will always end up seeing the new rules. That includes the case of somebody doing "ifconfig eth0 up" that enables a new source of packets, so there are no real security issues.
Quoted 6 lines
- if you enabled your network interfaces before you updated your packet filtering rules, you already had a window where packets would come in with the old rules, so doing a "
synchronize_net()" in no way protects against any race conditions anyway.Am I missing something?
The issue at this point seems to be the need to get accurate snapshots of various counters -- there are a number of Linux networking users who need to account for every byte flowing through their systems. However, it is also necessary to update these counters very efficiently, given that they are updated on a per-packet basis. The current approach is as follows:
1. Install a new set of counters.
2. Wait for a grace period to elapse.
3. At this point, we know that all subsequent counting will happen
on the new set of counters.4. Add the value of the old set of counters to the new set of
counters.5. Copy the old set of counters up to user space.
So we get a good snapshot in #5, while #4 ensures that we don't lose any counts when taking future snapshots. Unfortunately, #2 hits us with grace-period latencies on the critical path.
We are going through the following possibilities:
o Stick with the current approach, and ask people to move to
new batch-oriented interfaces. However, a 30x decrease in performance is pretty grim, even for an old-style interface.o Use various atomic tricks to get an immediate snapshot of the
old counters after step 1. Make step 3 usecall_rcu()instead ofsynchronize_rcu(), and then step 4 happens off the critical path.This approach moves the RCU grace period off of the critical path, but the atomic tricks are extremely ugly on 32-bit SMP machines. 32-bit UP machines and 64-bit machines are not too bad, though the 32-bit UP case does add preemption-disable overhead on the counter-update fastpath.
o Provide some sort of expedited
synchronize_rcu(). This might
be able to decrease the hit from 30x down to maybe 5x. But I might need to do this for the fast-boot folks anyway, though I am first trying to get away with just speeding upsynchronized_rcu(). Though I was not thinking in terms of 6x, let alone 30x.
Quoted 8 lines
Please note that this would not be a drop-in replacement for
synchronize_rcu(). One would usesynchronize_rcu_expedited()(or whatever) only when the system really could not get any useful work done while the grace period was in progress. The general approach would be to keep the whole machine busy trying to get the grace period done as soon as possible.Thanx, Paul
We could also try:
* per-cpu spinlock on counters (instead of synchronize_net). When doing update, just acquire
lock on that cpu and futz with counters then. Overhead should still be less than 2.6.29 and earlier global rwlock
* synchonize_rcu/synchronize_net is more guarantee than needed?
* use on_each_cpu() somehow to do grace periood?
* Add a cond_resched() into net_rx_action which might cause rx processing to get out of rcu sooner? also in transmit packet scheduler.
Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49
Quoted 97 lines · Stephen Hemminger
Quoted 94 lines · On Sat, 11 Apr 2009 17:34:45 -0700 "Paul E. McKenney"…
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney
1. Assuming that the
synchronize_net()is intended to guarantee
that the new rules will be in effect before returning to user space:Btw, I think that's a bad assumption.
It does indeed appear to be!
Quoted 20 lines
The thing is, nobody can really care if the new rules are in effect or not, because the thing you race with is not the "return to user space" part, but the incoming packets.
And those incoming packets might have been incoming before the rules were set up too.
So I seriously doubt you need to synchronize with any returning to user space. What you want to synchronize with is then later actions that do things like turning on the interface that the rules are attached to etc!
So I would suggest:
- remove the
synchronize_net()entirely. Replace it with just freeing the old rules using RCU.- new packets will always end up seeing the new rules. That includes the case of somebody doing "ifconfig eth0 up" that enables a new source of packets, so there are no real security issues.
Quoted 6 lines
- if you enabled your network interfaces before you updated your packet filtering rules, you already had a window where packets would come in with the old rules, so doing a "
synchronize_net()" in no way protects against any race conditions anyway.Am I missing something?
The issue at this point seems to be the need to get accurate snapshots of various counters -- there are a number of Linux networking users who need to account for every byte flowing through their systems. However, it is also necessary to update these counters very efficiently, given that they are updated on a per-packet basis. The current approach is as follows:
1. Install a new set of counters.
2. Wait for a grace period to elapse.
3. At this point, we know that all subsequent counting will happen
on the new set of counters.4. Add the value of the old set of counters to the new set of
counters.5. Copy the old set of counters up to user space.
So we get a good snapshot in #5, while #4 ensures that we don't lose any counts when taking future snapshots. Unfortunately, #2 hits us with grace-period latencies on the critical path.
We are going through the following possibilities:
o Stick with the current approach, and ask people to move to
new batch-oriented interfaces. However, a 30x decrease in performance is pretty grim, even for an old-style interface.o Use various atomic tricks to get an immediate snapshot of the
old counters after step 1. Make step 3 usecall_rcu()instead ofsynchronize_rcu(), and then step 4 happens off the critical path.This approach moves the RCU grace period off of the critical path, but the atomic tricks are extremely ugly on 32-bit SMP machines. 32-bit UP machines and 64-bit machines are not too bad, though the 32-bit UP case does add preemption-disable overhead on the counter-update fastpath.
o Provide some sort of expedited
synchronize_rcu(). This might
be able to decrease the hit from 30x down to maybe 5x. But I might need to do this for the fast-boot folks anyway, though I am first trying to get away with just speeding upsynchronized_rcu(). Though I was not thinking in terms of 6x, let alone 30x.Please note that this would not be a drop-in replacement for
synchronize_rcu(). One would usesynchronize_rcu_expedited()(or whatever) only when the system really could not get any useful work done while the grace period was in progress. The general approach would be to keep the whole machine busy trying to get the grace period done as soon as possible.
Quoted 7 lines
Quoted 1 line
Thanx, Paul
We could also try:
* per-cpu spinlock on counters (instead ofsynchronize_net). When doing update, just acquire
lock on that cpu and futz with counters then. Overhead should still be less than 2.6.29 and earlier global rwlock
This one makes a lot of sense to me. The overhead of an uncontended lock is pretty small on most systems. This would also mean that you don't have to actually swap the counters, correct?
Quoted 1 line
* synchonize_rcu/synchronize_net is more guarantee than needed?
If you really do need to swap the counters themselves, you -might- also need call_rcu() to dispose of them. But it should possible to do that under the per-CPU lock instead.
Quoted 1 line
* use
on_each_cpu()somehow to do grace periood?
You could certainly use something like smp_call_function() to collect the other CPUs' counter values -- just disable interrupts across the increments for architectures that cannot atomically increment a 64-bit value. (And it only needs to be atomic with respect to an interrupt, not necessarily to some other CPU.)
Quoted 2 lines
* Add a
cond_resched()intonet_rx_actionwhich might cause rx processing to get out of rcu sooner? also in transmit packet scheduler.
This might help some, but would probably only give a few tens of percent improvement.
Thanx, Paul