Prototype ticket locks
RFC PATCH 1/1 Prototype ticket locks
Use ticket locks for spin locks instead of the current byte locks. Ticket locks are fair. This is an important property for hypervisor locks.
This prototype has the following limitations:
- Only 256 CPUs (8 bit tickets).
- Broken lock profiling.
- x86 only.
Note that spin_lock_irq() and spin_lock_irqsave() now spin with irqs disabled (previously, they would spin with irqs enabled if possible). This is required to prevent deadlocks when the irq handler tries to take the same lock with a higher ticket.
Performance results of aggregate network throughput between 20 VIF pairs shows good improvements.
http://xenbits.xen.org/people/dvrabel/3336.png
This benchmark is limited by contention on the map track lock.
--- xen/common/spinlock.c | 26 ++--------------- xen/include/asm-x86/spinlock.h | 60 ++++++++++++++++++++++++++++++++-------- 2 files changed, 52 insertions(+), 34 deletions(-)
xen/common/spinlock.c +3 -23
@@ -120,12 +120,7 @@ void _spin_lock(spinlock_t *lock)LOCK_PROFILE_VAR ;check_lock (&lock->debug); -while (unlikely (!_raw_spin_trylock (&lock->raw)) ) - { -LOCK_PROFILE_BLOCK ; -while (likely (_raw_spin_is_locked (&lock->raw)) ) -cpu_relax (); - } +_raw_spin_lock (&lock->raw);LOCK_PROFILE_GOT ;preempt_disable (); }
@@ -136,15 +131,7 @@ void _spin_lock_irq(spinlock_t *lock)ASSERT (local_irq_is_enabled ());local_irq_disable (); -check_lock (&lock->debug); -while (unlikely (!_raw_spin_trylock (&lock->raw)) ) - { -LOCK_PROFILE_BLOCK ; -local_irq_enable (); -while (likely (_raw_spin_is_locked (&lock->raw)) ) -cpu_relax (); -local_irq_disable (); - } +_raw_spin_lock (&lock->raw);LOCK_PROFILE_GOT ;preempt_disable (); }
@@ -156,14 +143,7 @@ unsigned long _spin_lock_irqsave(spinlock_t *lock)local_irq_save (flags);check_lock (&lock->debug); -while (unlikely (!_raw_spin_trylock (&lock->raw)) ) - { -LOCK_PROFILE_BLOCK ; -local_irq_restore (flags); -while (likely (_raw_spin_is_locked (&lock->raw)) ) -cpu_relax (); -local_irq_disable (); - } +_raw_spin_lock (&lock->raw);LOCK_PROFILE_GOT ;preempt_disable ();return flags;
xen/include/asm-x86/spinlock.h +49 -11
78 lines not on this page · raw message
Signature · 1 line
1.7.10.4
Quoted 4 lines
Quoted 1 line
Quoted 1 line · On 03.02.15 at 12:50, <[email protected]> wrote:
Use ticket locks for spin locks instead of the current byte locks. Ticket locks are fair. This is an important property for hypervisor locks.
Isn't Linux moving to queue locks? Shouldn't we skip the intermediate step then, not the least because they will cause problems when Xen itself gets run virtualized?
Quoted 9 lines
This prototype has the following limitations:
- Only 256 CPUs (8 bit tickets).
- Broken lock profiling.
- x86 only.Note that
spin_lock_irq()andspin_lock_irqsave()now spin with irqs disabled (previously, they would spin with irqs enabled if possible). This is required to prevent deadlocks when the irq handler tries to take the same lock with a higher ticket.
That's another pretty undesirable property (albeit it's not a strict implication of using ticket locks - one can make them work with interrupts getting properly re-enabled while spinning).
It was for these reasons that so far I didn't go and steal Linux'es ticket lock implementation (and I think you should at least mention the origin in the description).
xen/include/asm-x86/spinlock.h line 10
Quoted 9 lines
xen/include/asm-x86/spinlock.h +1
-1@@ -6,29 +6,67 @@#include <asm/atomic.h> typedef struct { -volatile s16 lock; +volatile u16 lock; }raw_spinlock_t ;
With this, you can't ...
xen/include/asm-x86/spinlock.h line 16
Quoted 3 lines
xen/include/asm-x86/spinlock.h +3
-0+static always_inline int _raw_spin_is_locked(raw_spinlock_t *lock) +{ +int tmp = *(volatile signed int *)(&lock->lock);
... do this. One of the many cases where using casts hides bugs.
As to the rest of the change - if we went the ticket lock route, I think we should use Linux'es newer, asm()-less implementation, which would hopefully also make it easier to use the same code for ARM.
Jan
Quoted 8 lines · Jan Beulich
Quoted 4 lines
Quoted 1 line
Quoted 1 line · On 03.02.15 at 12:50, <[email protected]> wrote:
Use ticket locks for spin locks instead of the current byte locks. Ticket locks are fair. This is an important property for hypervisor locks.
Isn't Linux moving to queue locks? Shouldn't we skip the intermediate step then, not the least because they will cause problems when Xen itself gets run virtualized?
ticket locks are trivial. Why should we wait for the mythical future where someone implements queue locks to actually get better/fairer locks?
I also don't think the characteristics of queue locks vs ticket locks are really any different in a virtualized guest. FWIW, the latest Linux queue lock series falls back to byte locks in non-PV-aware guests.
Quoted 5 lines
Quoted 5 lines
This prototype has the following limitations:
- Only 256 CPUs (8 bit tickets).
- Broken lock profiling.
- x86 only.
Quoted 8 lines
Quoted 4 lines
Note that
spin_lock_irq()andspin_lock_irqsave()now spin with irqs disabled (previously, they would spin with irqs enabled if possible). This is required to prevent deadlocks when the irq handler tries to take the same lock with a higher ticket.That's another pretty undesirable property (albeit it's not a strict implication of using ticket locks - one can make them work with interrupts getting properly re-enabled while spinning).
I've seen too many Linux deadlocks caused be re-enabling irqs while spinning to consider this a good idea. The ticket stealing stuff that Suse kernels do doesn't play nice with rw locks or certain hand rolled synchronization code (in short, if the interrupt spins on something other than a ticket lock it breaks).
Quoted 3 lines
It was for these reasons that so far I didn't go and steal Linux'es ticket lock implementation (and I think you should at least mention the origin in the description).
Sorry, this was taken (almost as-is) from Nick Piggin's Linux implementation.
David
Quoted 8 lines
Quoted 1 line
Quoted 1 line · On 03.02.15 at 16:01, <[email protected]> wrote:
Quoted 6 lines · Jan Beulich
Quoted 5 lines
Quoted 1 line
Quoted 1 line · On 03.02.15 at 12:50, <[email protected]> wrote:
Note that
spin_lock_irq()andspin_lock_irqsave()now spin with irqs disabled (previously, they would spin with irqs enabled if possible). This is required to prevent deadlocks when the irq handler tries to take the same lock with a higher ticket.
Quoted 6 lines
Quoted 3 lines
That's another pretty undesirable property (albeit it's not a strict implication of using ticket locks - one can make them work with interrupts getting properly re-enabled while spinning).
I've seen too many Linux deadlocks caused be re-enabling irqs while spinning to consider this a good idea.
And I've heard too many complaints on interrupt latency not care.
Quoted 4 lines
The ticket stealing stuff that
Suse kernels do doesn't play nice with rw locks or certain hand rolled synchronization code (in short, if the interrupt spins on something other than a ticket lock it breaks).
The original version indeed had such a problem, but I don't think the current version has anymore.
Jan