[Xen-devel] [RFC PATCHv1] Prototype ticket locks

[David Vrabel <david.vrabel@xxxxxxxxxx>]

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@xxxxxxxxxx>
---
 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


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel