spinlock: lockbreak cleanups
Subsystems (5)
RFC PATCH 1/2 spinlock: lockbreak cleanups
Hi,
These patches are not exactly complete yet (haven't tested many config combinations or converted other architectures), but I want to post it now to get consensus on whether and how to clean up the lockbreak stuff in particular.
It gets in the way because ticket spinlocks shouldn't be just repeating the low-level trylock to lock, because that never gives the locker a ticket, so the FIFO order is ruined.
So RFC.
---
The break_lock data structure and code for spinlocks is quite nasty. Not only does it double the size of a spinlock but it changes locking to a potentially less optimal trylock.
Put all of that under CONFIG_GENERIC_LOCKBREAK, and introduce a __raw_spin_is_contended that uses the lock data itself to determine whether there are waiters on the lock, to be used if CONFIG_GENERIC_LOCKBREAK is not set.
Rename need_lockbreak to spin_needbreak, make it use spin_is_contended to decouple it from the spinlock implementation, and make it typesafe (rwlocks do not have any need_lockbreak sites -- why do they even get bloated up with that break_lock then?).
After this, we can no longer spin on any locks with preempt enabled (unless that is done in arch code), but that (and spinning with interrupts enabled) is hackish anyway: if the lock happens to be called under a preempt or interrupt disabled section, then it is just going to have the same problems. The real fix is to keep critical sections short, and introduce fairer locks if there are starvation issues.
---
include/linux/sched.h +5 -15
@@ -1598,26 +1598,16 @@ extern int cond_resched_softirq(void);/* * Does a critical section need to be broken due to another -* task waiting?: +* task waiting?: (technically does not depend on CONFIG_PREEMPT, +* but a general need for low latency) */ -#if defined(CONFIG_PREEMPT ) && defined(CONFIG_SMP ) -# define need_lockbreak (lock) ((lock)->break_lock) +#ifdef CONFIG_PREEMPT +# define spin_needbreak (lock) spin_is_contended(lock)#else -# define need_lockbreak (lock) 0 +# define spin_needbreak (lock) 0#endif /* -* Does a critical section need to be broken due to another -* task waiting or preemption being signalled: -*/ -static inline int lock_need_resched (spinlock_t *lock) -{ -if (need_lockbreak (lock) ||need_resched ()) -return 1 ; -return 0 ; -} - -/* * Reevaluate whether the task has signals pending delivery. * Wake the task if so. * This is required every time the blocked sigset_t changes.
include/linux/spinlock.h +6 -0
@@ -120,6 +120,12 @@ do { \#define spin_is_locked (lock) __raw_spin_is_locked(&(lock)->raw_lock) +#ifdef CONFIG_GENERIC_LOCKBREAK +#define spin_is_contended (lock) ((lock)->break_lock) +#else +#define spin_is_contended (lock) __raw_spin_is_contended(&(lock)->raw_lock) +#endif +/** * spin_unlock_wait - wait until the spinlock gets unlocked * @lock: the spinlock in question.
fs/jbd/checkpoint.c +2 -1
@@ -347,7 +347,8 @@ restart:break ; } retry =__process_buffer (journal, jh, bhs,&batch_count); -if (!retry &&lock_need_resched (&journal->j_list_lock)){ +if (!retry && (need_resched () || +spin_needbreak (&journal->j_list_lock))) {spin_unlock (&journal->j_list_lock); retry =1 ;break ;
fs/jbd/commit.c +1 -1
@@ -265,7 +265,7 @@ write_out_data:put_bh (bh); } -if (lock_need_resched (&journal->j_list_lock)) { +if (need_resched () ||spin_needbreak (&journal->j_list_lock)) {spin_unlock (&journal->j_list_lock); goto write_out_data; }
fs/jbd2/checkpoint.c +2 -1
@@ -347,7 +347,8 @@ restart:break ; } retry =__process_buffer (journal, jh, bhs,&batch_count); -if (!retry &&lock_need_resched (&journal->j_list_lock)){ +if (!retry && (need_resched () || +spin_needbreak (&journal->j_list_lock))) {spin_unlock (&journal->j_list_lock); retry =1 ;break ;
fs/jbd2/commit.c +1 -1
@@ -265,7 +265,7 @@ write_out_data:put_bh (bh); } -if (lock_need_resched (&journal->j_list_lock)) { +if (need_resched () ||spin_needbreak (&journal->j_list_lock)) {spin_unlock (&journal->j_list_lock); goto write_out_data; }
include/linux/spinlock_up.h +2 -0
@@ -64,6 +64,8 @@ static inline void __raw_spin_unlock(raw# define __raw_spin_trylock (lock) ({ (void)(lock); 1; })#endif /* DEBUG_SPINLOCK */ +#define __raw_spin_is_contended (lock) (((void)(lock), 0)) +#define __raw_read_can_lock (lock) (((void)(lock), 1))#define __raw_write_can_lock (lock) (((void)(lock), 1))
kernel/sched.c +6 -10
@@ -4805,19 +4805,15 @@ EXPORT_SYMBOL(cond_resched);*/ int cond_resched_lock (spinlock_t *lock) { +int resched =need_resched () && system_state ==SYSTEM_RUNNING ;int ret =0 ; -if (need_lockbreak (lock)) { +if (spin_needbreak (lock) || resched) {spin_unlock (lock); -cpu_relax (); - ret =1 ; -spin_lock (lock); - } -if (need_resched () && system_state ==SYSTEM_RUNNING ) { -spin_release (&lock->dep_map,1 , _THIS_IP_); -_raw_spin_unlock (lock); -preempt_enable_no_resched (); -__cond_resched (); +if (resched &&need_resched ()) +__cond_resched (); +else +cpu_relax (); ret =1 ;spin_lock (lock); }
mm/memory.c +3 -5
@@ -516,8 +516,7 @@ again:if (progress >=32 ) { progress =0 ;if (need_resched () || -need_lockbreak (src_ptl) || -need_lockbreak (dst_ptl)) +spin_needbreak (src_ptl) ||spin_needbreak (dst_ptl))break ; }if (pte_none (*src_pte)) {
@@ -856,7 +855,7 @@ unsigned long unmap_vmas(struct mmu_gathtlb_finish_mmu (*tlbp, tlb_start, start);if (need_resched () || - (i_mmap_lock &&need_lockbreak (i_mmap_lock))) { + (i_mmap_lock &&spin_needbreak (i_mmap_lock))) {if (i_mmap_lock) { *tlbp =NULL ; goto out;
@@ -1838,8 +1837,7 @@ again: restart_addr =zap_page_range (vma, start_addr, end_addr - start_addr, details); - need_break =need_resched () || -need_lockbreak (details->i_mmap_lock); + need_break =need_resched () ||spin_needbreak (details->i_mmap_lock);if (restart_addr >= end_addr) {/* We have now completed this vma: mark it so */
arch/x86_64/Kconfig +5 -0
@@ -32,6 +32,11 @@ config GENERIC_TIME_VSYSCALL bool default y +config GENERIC_LOCKBREAK + bool + default y + depends on SMP && PREEMPT + config ZONE_DMA32 bool default y
include/linux/spinlock_types.h +2 -2
@@ -19,7 +19,7 @@ typedef struct { raw_spinlock_t raw_lock; -#if defined(CONFIG_PREEMPT) && defined(CONFIG_SMP) +#ifdef CONFIG_GENERIC_LOCKBREAK unsigned int break_lock; #endif #ifdef CONFIG_DEBUG_SPINLOCK
@@ -35,7 +35,7 @@ typedef struct { typedef struct { raw_rwlock_t raw_lock; -#if defined(CONFIG_PREEMPT) && defined(CONFIG_SMP) +#ifdef CONFIG_GENERIC_LOCKBREAK unsigned int break_lock; #endif #ifdef CONFIG_DEBUG_SPINLOCK
kernel/spinlock.c +1 -2
@@ -65,8 +65,7 @@ EXPORT_SYMBOL(_write_trylock);* even on CONFIG_PREEMPT, because lockdep assumes that interrupts are * not re-enabled during lock-acquire (which the preempt-spin-ops do): */ -#if !defined(CONFIG_PREEMPT ) || !defined(CONFIG_SMP ) || \ - defined(CONFIG_DEBUG_LOCK_ALLOC ) +#if !defined(CONFIG_GENERIC_LOCKBREAK ) || defined(CONFIG_DEBUG_LOCK_ALLOC ) void __lockfunc _read_lock(rwlock_t *lock) {
RFC PATCH 2/2 x86_64: FIFO ticket spinlocks
Introduce ticket lock spinlocks for x86-64 which are FIFO. The implementation is described in the comments. The straight-line lock/unlock instruction sequence is slightly slower than the dec based locks on modern x86 CPUs, however the difference is quite small on Core2 and Opteron when working out of cache, and becomes almost insignificant even on P4 when the lock misses cache. trylock is more significantly slower, but they are relatively rare.
The memory ordering of the lock does conform to Intel's standards, and the implementation has been reviewed by an Intel engineer.
XXX: numbers here
The algorithm also tells us how many CPUs are contending the lock, so lockbreak becomes trivial and we no longer waste 4 bytes per spinlock for it.
---
include/asm-x86_64/spinlock.h +57 -43
@@ -19,67 +19,81 @@static inline int __raw_spin_is_locked (raw_spinlock_t *lock) { -return *(volatile signed int *)(&(lock)->slock) <=0 ; +int tmp = *(volatile signed int *)(&(lock)->slock); + +return (((tmp >>8 ) &0xff ) != (tmp &0xff )); } -static inline void __raw_spin_lock (raw_spinlock_t *lock) +static inline int __raw_spin_is_contended (raw_spinlock_t *lock) { - asmvolatile ( -"\n1:\t" -LOCK_PREFIX " ; decl %0\n\t" -"jns 2f\n" -"3:\n" -"rep;nop\n\t" -"cmpl $0,%0\n\t" -"jle 3b\n\t" -"jmp 1b\n" -"2:\t" :"=m" (lock->slock) : :"memory" ); +int tmp = *(volatile signed int *)(&(lock)->slock); + +return (((tmp >>8 ) &0xff ) - (tmp &0xff )) >1 ; } -/* -* Same as __raw_spin_lock, but reenable interrupts during spinning. -*/ -#ifndef CONFIG_PROVE_LOCKING -static inline void __raw_spin_lock_flags (raw_spinlock_t *lock,unsigned long flags) +static inline void __raw_spin_lock (raw_spinlock_t *lock) { - asmvolatile ( -"\n1:\t" -LOCK_PREFIX " ; decl %0\n\t" -"jns 5f\n" -"testl $0x200, %1\n\t" /* interrupts were disabled? */ -"jz 4f\n\t" -"sti\n" -"3:\t" -"rep;nop\n\t" -"cmpl $0, %0\n\t" -"jle 3b\n\t" -"cli\n\t" +short inc =0x0100 ; + +/* +* Ticket locks are conceptually two bytes, one indicating the current +* head of the queue, and the other indicating the current tail. The +* lock is acquired by atomically noting the tail and incrementing it +* by one (thus adding ourself to the queue and noting our position), +* then waiting until the head becomes equal to the the initial value +* of the tail. +* +* This uses a 16-bit xadd to increment the tail and also load the +* position of the head, which takes care of memory ordering issues +* and should be optimal for the uncontended case. Note the tail must +* be in the high byte, otherwise the 16-bit wide increment of the low +* byte would carry up and contaminate the high byte. +*/ + + __asm__ __volatile__ ( +LOCK_PREFIX "xaddw %w0, %1\n" +"1:\t" +"cmpb %h0, %b0\n\t" +"je 2f\n\t" +"rep ; nop\n\t" +"movb %1, %b0\n\t" +"lfence\n\t" "jmp 1b\n" -"4:\t" -"rep;nop\n\t" -"cmpl $0, %0\n\t" -"jg 1b\n\t" -"jmp 4b\n" -"5:\n\t" - :"+m" (lock->slock) :"r" ((unsigned )flags) :"memory" ); +"2:" + :"+Q" (inc),"+m" (lock->slock) + : + :"memory" ,"cc" ); } -#endif + +#define __raw_spin_lock_flags (lock, flags) __raw_spin_lock(lock)static inline int __raw_spin_trylock (raw_spinlock_t *lock) { -int oldval; +short tmp; +short oldval; asmvolatile ( -"xchgl %0,%1" - :"=q" (oldval),"=m" (lock->slock) - :"0" (0 ) :"memory" ); +"movw %2,%w0\n\t" +"cmpb %h0, %b0\n\t" +"jne 1f\n\t" +"movw %w0,%w1\n\t" +"incb %h1\n\t" +LOCK_PREFIX "cmpxchgw %w1,%2\n\t" +"1:" + :"=a" (oldval),"=Q" (tmp),"+m" (lock->slock) + : + :"memory" ,"cc" ); -return oldval >0 ; +return ((oldval &0xff ) == ((oldval >>8 ) &0xff )); }static inline void __raw_spin_unlock (raw_spinlock_t *lock) { - asmvolatile ("movl $1,%0" :"=m" (lock->slock) ::"memory" ); + __asm__ __volatile__( +"incb %0" + :"+m" (lock->slock) + : + :"memory" ,"cc" ); }static inline void __raw_spin_unlock_wait (raw_spinlock_t *lock)
include/asm-x86_64/spinlock_types.h +1 -1
@@ -9,7 +9,7 @@ typedef struct {unsigned int slock; } raw_spinlock_t; -#define __RAW_SPIN_LOCK_UNLOCKED { 1 } +#define __RAW_SPIN_LOCK_UNLOCKED { 0 } typedef struct { unsigned int lock;
arch/x86_64/Kconfig +1 -2
@@ -34,8 +34,7 @@ config GENERIC_TIME_VSYSCALL config GENERIC_LOCKBREAK bool - default y - depends on SMP && PREEMPT + default n config ZONE_DMA32 bool
Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks
Quoted 3 lines
however the difference is quite small on Core2 and Opteron when working out of cache, and becomes almost insignificant even on P4 when the lock misses cache. trylock is more significantly slower, but they are relatively rare.
This has a 255 processor limit (worst case). That should probably be clearly documented for the future.
Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks
Quoted 6 lines · Alan Cox
Quoted 3 lines
however the difference is quite small on Core2 and Opteron when working out of cache, and becomes almost insignificant even on P4 when the lock misses cache. trylock is more significantly slower, but they are relatively rare.
This has a 255 processor limit (worst case). That should probably be clearly documented for the future.
Yeah good point. I added an #error for it.
Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks
In reply to Nick PigginQuoted 2 lines · Nick Piggin
[...] trylock is more significantly slower, but they are relatively rare.
trylock is the main thing that the spinlock debugging code uses, and SPINLOCK_DEBUG is frequently enabled by distro kernels. OTOH, the cost looks like to be +5 instructions, right? Still ...
Ingo
Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks
Quoted 9 lines · Ingo Molnar
Quoted 2 lines · Nick Piggin
[...] trylock is more significantly slower, but they are relatively rare.
trylock is the main thing that the spinlock debugging code uses, and
SPINLOCK_DEBUGis frequently enabled by distro kernels. OTOH, the cost looks like to be +5 instructions, right? Still ...
Which trylocks do you mean? The lockbreak spinlocks use trylock, but those are not used with the ticket version.
I wouldn't be against adding an option between either of the lock types, if there was value in it. But I would like to default ticket locks to "y", at least in -rc kernels, in order to see if performance goes down anywhere.
Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks
Quoted 7 lines · Nick Piggin
Quoted 6 lines · Ingo Molnar
Quoted 2 lines · Nick Piggin
[...] trylock is more significantly slower, but they are relatively rare.
Quoted 6 lines
Quoted 3 lines
trylock is the main thing that the spinlock debugging code uses, and
SPINLOCK_DEBUGis frequently enabled by distro kernels. OTOH, the cost looks like to be +5 instructions, right? Still ...Which trylocks do you mean? The lockbreak spinlocks use trylock, but those are not used with the ticket version.
the trylocks in lib/spinlock-debug.c:
static void __spin_lock_debug(spinlock_t *lock)
{
...
if (__raw_spin_trylock(&lock->raw_lock))
return;
...
void _raw_spin_lock(spinlock_t *lock)
{
debug_spin_lock_before(lock);
if (unlikely(!__raw_spin_trylock(&lock->raw_lock)))
__spin_lock_debug(lock);
debug_spin_lock_after(lock);}
am i missing something?
Ingo
Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks
Quoted 31 lines · Ingo Molnar
Quoted 7 lines · Nick Piggin
Quoted 6 lines · Ingo Molnar
Quoted 2 lines · Nick Piggin
[...] trylock is more significantly slower, but they are relatively rare.
Quoted 6 lines
Quoted 3 lines
trylock is the main thing that the spinlock debugging code uses, and
SPINLOCK_DEBUGis frequently enabled by distro kernels. OTOH, the cost looks like to be +5 instructions, right? Still ...Which trylocks do you mean? The lockbreak spinlocks use trylock, but those are not used with the ticket version.
the trylocks in
lib/spinlock-debug.c:static void
__spin_lock_debug(spinlock_t *lock)
{
...if (__raw_spin_trylock(&lock->raw_lock)) return; ... void _raw_spin_lock(spinlock_t *lock) { debug_spin_lock_before(lock); if (unlikely(!__raw_spin_trylock(&lock->raw_lock))) __spin_lock_debug(lock); debug_spin_lock_after(lock);
Quoted 3 lines
}
am i missing something?
No, I missed that. Yeah, that would get a bit slower, but I'm not sure if it would be a problem on a kernel where you have spinlock debuggin on anyway.
If it becomes a problem, we could perhaps do a version for ticket locks that first takes a ticket, and then is for up to a second before printing the stuck lock message. That would make the performance hit go away.
Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks
In reply to Nick PigginWhen you revamp everything I guess it would make the locks easier to read to just put them into a .S file? They're out of line anyways.
In general they look ok.
include/asm-x86_64/spinlock.h line 92
Quoted 5 lines
static inline void
__raw_spin_unlock(raw_spinlock_t *lock){include/asm-x86_64/spinlock.h +1
-1- asmvolatile ("movl $1,%0" :"=m" (lock->slock) ::"memory" ); + __asm__ __volatile__(
Minor nit: please don't use these underlined keywords. They just look ugly and asm volatile works as well.
-Andi
Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks
Quoted 5 lines · Andi Kleen
When you revamp everything I guess it would make the locks easier to read to just put them into a .S file? They're out of line anyways.
It is a bit tricky because of the way kernel/spinlock.c uses the the inline asm (that, and unlocks are inlined), and some of the debugging code.
Also, I'm not exactly sure what is the best way to clean up spinlocks, if it is even possible. I'm afraid to touch it more than I have to :)
Quoted 11 lines
In general they look ok.
include/asm-x86_64/spinlock.h line 92
Quoted 5 lines
static inline void
__raw_spin_unlock(raw_spinlock_t *lock){include/asm-x86_64/spinlock.h +1
-1- asmvolatile ("movl $1,%0" :"=m" (lock->slock) ::"memory" ); + __asm__ __volatile__(Minor nit: please don't use these underlined keywords. They just look ugly and asm volatile works as well.
OK, I like that better too. I didn't even realise I changed this because it is mechanical to do the __. That's good to know and I'll change my habit now.