[RFC PATCHv1] Prototype ticket locks

[RFC PATCHv1] Prototype ticket locks

[David Vrabel]

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.

Signed-off-by: David Vrabel <david.vrabel@citrix.com>
---
 xen/common/spinlock.c          |   26 ++---------------
 xen/include/asm-x86/spinlock.h |   60 ++++++++++++++++++++++++++++++++--------
 2 files changed, 52 insertions(+), 34 deletions(-)

diff --git a/xen/common/spinlock.c b/xen/common/spinlock.c
index 5fd8b1c..7a56c79 100644
--- a/xen/common/spinlock.c
+++ b/xen/common/spinlock.c
@@ -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;
diff --git a/xen/include/asm-x86/spinlock.h b/xen/include/asm-x86/spinlock.h
index 757e20b..b2bdfef 100644
--- a/xen/include/asm-x86/spinlock.h
+++ b/xen/include/asm-x86/spinlock.h
@@ -6,29 +6,67 @@
 #include <asm/atomic.h>
 
 typedef struct {
-    volatile s16 lock;
+    volatile u16 lock;
 } raw_spinlock_t;
 
-#define _RAW_SPIN_LOCK_UNLOCKED /*(raw_spinlock_t)*/ { 1 }
+#define _RAW_SPIN_LOCK_UNLOCKED /*(raw_spinlock_t)*/ { 0 }
 
-#define _raw_spin_is_locked(x) ((x)->lock <= 0)
+static always_inline int _raw_spin_is_locked(raw_spinlock_t *lock)
+{
+    int tmp = *(volatile signed int *)(&lock->lock);
+
+    return (tmp & 0xff) != ((tmp >> 8) & 0xff);
+}
+
+static always_inline void _raw_spin_lock(raw_spinlock_t *lock)
+{
+    short inc = 0x0100;
+
+    asm volatile (
+        "lock xaddw %w0, %1\n"
+        "1:\t"
+        "cmpb %h0, %b0\n\t"
+        "je 2f\n\t"
+        "rep ; nop\n\t"
+        "movb %1, %b0\n\t"
+        /* don't need lfence here, because loads are in-order */
+        "jmp 1b\n"
+        "2:"
+        :"+Q" (inc), "+m" (lock->lock)
+        :
+        :"memory", "cc");
+}
 
 static always_inline void _raw_spin_unlock(raw_spinlock_t *lock)
 {
     ASSERT(_raw_spin_is_locked(lock));
     asm volatile (
-        "movw $1,%0" 
-        : "=m" (lock->lock) : : "memory" );
+        "lock incb %0"
+        :"+m" (lock->lock)
+        :
+        :"memory", "cc");
 }
 
 static always_inline int _raw_spin_trylock(raw_spinlock_t *lock)
 {
-    s16 oldval;
-    asm volatile (
-        "xchgw %w0,%1"
-        :"=r" (oldval), "=m" (lock->lock)
-        :"0" ((s16)0) : "memory" );
-    return (oldval > 0);
+    int tmp;
+    short new;
+
+    asm volatile(
+        "movw %2,%w0\n\t"
+        "cmpb %h0,%b0\n\t"
+        "jne 1f\n\t"
+        "movw %w0,%w1\n\t"
+        "incb %h1\n\t"
+        "lock ; cmpxchgw %w1,%2\n\t"
+        "1:"
+        "sete %b1\n\t"
+        "movzbl %b1,%0\n\t"
+        :"=&a" (tmp), "=Q" (new), "+m" (lock->lock)
+        :
+        : "memory", "cc");
+
+    return tmp;
 }
 
 #define _raw_read_unlock(l) \
-- 
1.7.10.4

Re: [RFC PATCHv1] Prototype ticket locks

[Jan Beulich]

>>> On 03.02.15 at 12:50, <david.vrabel@citrix.com> 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?

> 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.

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).

> --- a/xen/include/asm-x86/spinlock.h
> +++ b/xen/include/asm-x86/spinlock.h
> @@ -6,29 +6,67 @@
>  #include <asm/atomic.h>
>  
>  typedef struct {
> -    volatile s16 lock;
> +    volatile u16 lock;
>  } raw_spinlock_t;

With this, you can't ...

> +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

Re: [RFC PATCHv1] Prototype ticket locks

[David Vrabel]

On 03/02/15 13:55, Jan Beulich wrote:
>>>> On 03.02.15 at 12:50, <david.vrabel@citrix.com> 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.

>> 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.
> 
> 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).

> 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

Re: [RFC PATCHv1] Prototype ticket locks

[Jan Beulich]

>>> On 03.02.15 at 16:01, <david.vrabel@citrix.com> wrote:
> On 03/02/15 13:55, Jan Beulich wrote:
>>>>> On 03.02.15 at 12:50, <david.vrabel@citrix.com> wrote:
>>> 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.
>> 
>> 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.

> 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