[PATCHv2 0/6] Use ticket locks for spinlocks

[PATCHv2 0/6] Use ticket locks for spinlocks

[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 has the following limitations:

- No ARM optimized xadd() implementation.  The generic implementation
  usign cmpxchg is probably sub-optimal.

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.

A quick survey of the interrupt disabling spin locks suggests that
this should not introduce significant extra interrupt latency (there
aren't many such locks and I don't think they're heavily contended)
but we are attempting to collect experimental evidence to support
this.

Performance results (using a earlier prototype) 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.

Changes in v2:
- Reimplemented in C, requiring only an arch-specific xadd() op
- Optimize spin_lock_recursive() to call spin_lock() since trylock
  loops are bad with ticket locks.

David

[PATCHv2 1/6] x86/hvm: don't include asm/spinlock.h

[David Vrabel]

asm/spinlock.h should not be included directly.

Signed-off-by: David Vrabel <david.vrabel@citrix.com>
---
 xen/arch/x86/hvm/hvm.c     |    1 -
 xen/arch/x86/hvm/svm/svm.c |    1 -
 xen/arch/x86/hvm/vmx/vmx.c |    1 -
 3 files changed, 3 deletions(-)

diff --git a/xen/arch/x86/hvm/hvm.c b/xen/arch/x86/hvm/hvm.c
index 4734d71..6937857 100644
--- a/xen/arch/x86/hvm/hvm.c
+++ b/xen/arch/x86/hvm/hvm.c
@@ -52,7 +52,6 @@
 #include <asm/xstate.h>
 #include <asm/traps.h>
 #include <asm/mc146818rtc.h>
-#include <asm/spinlock.h>
 #include <asm/mce.h>
 #include <asm/hvm/hvm.h>
 #include <asm/hvm/vpt.h>
diff --git a/xen/arch/x86/hvm/svm/svm.c b/xen/arch/x86/hvm/svm/svm.c
index b6e77cd..6734fb6 100644
--- a/xen/arch/x86/hvm/svm/svm.c
+++ b/xen/arch/x86/hvm/svm/svm.c
@@ -41,7 +41,6 @@
 #include <asm/msr.h>
 #include <asm/i387.h>
 #include <asm/iocap.h>
-#include <asm/spinlock.h>
 #include <asm/hvm/emulate.h>
 #include <asm/hvm/hvm.h>
 #include <asm/hvm/support.h>
diff --git a/xen/arch/x86/hvm/vmx/vmx.c b/xen/arch/x86/hvm/vmx/vmx.c
index e1c55ce..2a0610b 100644
--- a/xen/arch/x86/hvm/vmx/vmx.c
+++ b/xen/arch/x86/hvm/vmx/vmx.c
@@ -35,7 +35,6 @@
 #include <asm/types.h>
 #include <asm/debugreg.h>
 #include <asm/msr.h>
-#include <asm/spinlock.h>
 #include <asm/paging.h>
 #include <asm/p2m.h>
 #include <asm/mem_sharing.h>
-- 
1.7.10.4

[PATCHv2 2/6] x86/mtrr: include asm/atomic.h

[David Vrabel]

asm/atomic.h is needed but only included indirectly via
asm/spinlock.h.

Signed-off-by: David Vrabel <david.vrabel@citrix.com>
---
 xen/arch/x86/cpu/mtrr/main.c |    1 +
 1 file changed, 1 insertion(+)

diff --git a/xen/arch/x86/cpu/mtrr/main.c b/xen/arch/x86/cpu/mtrr/main.c
index f5d5317..030a911 100644
--- a/xen/arch/x86/cpu/mtrr/main.c
+++ b/xen/arch/x86/cpu/mtrr/main.c
@@ -36,6 +36,7 @@
 #include <xen/lib.h>
 #include <xen/smp.h>
 #include <xen/spinlock.h>
+#include <asm/atomic.h>
 #include <asm/mtrr.h>
 #include <asm/uaccess.h>
 #include <asm/processor.h>
-- 
1.7.10.4

[PATCHv2 3/6] xen: generic xadd() for ticket locks

[David Vrabel]

Provide a generic xadd() implementation for architectures that don't
provide one.

This is only temporary until arm/arm64 provides an xadd()
implementation.

Signed-off-by: David Vrabel <david.vrabel@citrix.com>
---
 xen/common/spinlock.c |   21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/xen/common/spinlock.c b/xen/common/spinlock.c
index 5fd8b1c..0c4289c 100644
--- a/xen/common/spinlock.c
+++ b/xen/common/spinlock.c
@@ -10,6 +10,27 @@
 #include <asm/processor.h>
 #include <asm/atomic.h>
 
+#ifndef xadd
+
+static u32 generic_xaddl(volatile u32 *ptr, u32 v)
+{
+    u32 old, new, prev;
+
+    old = read_atomic(ptr);
+    for(;;) {
+        new = old + v;
+        prev = cmpxchg(ptr, old, new);
+        if (prev == old)
+            break;
+        old = prev;
+    }
+    return old;
+}
+
+#define xadd(ptr, v) generic_xaddl((ptr), (v))
+
+#endif
+
 #ifndef NDEBUG
 
 static atomic_t spin_debug __read_mostly = ATOMIC_INIT(0);
-- 
1.7.10.4

[PATCHv2 4/6] x86: provide xadd()

[David Vrabel]

xadd() atomically adds a value and returns the previous value.  This
is needed to implement ticket locks.

Signed-off-by: David Vrabel <david.vrabel@citrix.com>
---
 xen/include/asm-x86/system.h |   29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/xen/include/asm-x86/system.h b/xen/include/asm-x86/system.h
index 7111329..1e6c6a8 100644
--- a/xen/include/asm-x86/system.h
+++ b/xen/include/asm-x86/system.h
@@ -117,6 +117,35 @@ static always_inline unsigned long __cmpxchg(
                                    (unsigned long)__n,sizeof(*(ptr)))); \
 })
 
+static always_inline unsigned long __xadd(
+    volatile void *ptr, unsigned long v, int size)
+{
+    switch ( size )
+    {
+    case 1:
+        asm volatile ( "lock; xaddb %b0,%1"
+                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
+        return v;
+    case 2:
+        asm volatile ( "lock; xaddw %w0,%1"
+                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
+        return v;
+    case 4:
+        asm volatile ( "lock; xaddl %k0,%1"
+                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
+        return v;
+    case 8:
+        asm volatile ( "lock; xaddq %q0,%1"
+                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
+        return v;
+    }
+    return 0;
+}
+
+#define xadd(ptr, v) ({                                         \
+            __xadd((ptr), (unsigned long)(v), sizeof(*(ptr)));  \
+        })
+
 /*
  * Both Intel and AMD agree that, from a programmer's viewpoint:
  *  Loads cannot be reordered relative to other loads.
-- 
1.7.10.4

[PATCHv2 5/6] xen: use ticket locks for spin locks

[David Vrabel]

Replace the byte locks with ticket locks.  Ticket locks are: a) fair;
and b) peform better when contented since they spin without an atomic
operation.

The lock is split into two ticket values: head and tail.  A locker
acquires a ticket by (atomically) increasing tail and using the
previous tail value.  A CPU holds the lock if its ticket == head.  The
lock is released by increasing head.

Architectures need only provide an xadd() implementation.

Signed-off-by: David Vrabel <david.vrabel@citrix.com>
---
 xen/common/spinlock.c      |   80 +++++++++++++++++++++-----------------------
 xen/include/xen/spinlock.h |   16 ++++++---
 2 files changed, 50 insertions(+), 46 deletions(-)

diff --git a/xen/common/spinlock.c b/xen/common/spinlock.c
index 0c4289c..99163c5 100644
--- a/xen/common/spinlock.c
+++ b/xen/common/spinlock.c
@@ -138,14 +138,17 @@ void spin_debug_disable(void)
 
 void _spin_lock(spinlock_t *lock)
 {
+    spinlock_tickets_t tickets = { .tail = 1, };
     LOCK_PROFILE_VAR;
 
     check_lock(&lock->debug);
-    while ( unlikely(!_raw_spin_trylock(&lock->raw)) )
+    tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
+    if ( tickets.tail != read_atomic(&lock->tickets.head) )
     {
         LOCK_PROFILE_BLOCK;
-        while ( likely(_raw_spin_is_locked(&lock->raw)) )
+        do {
             cpu_relax();
+        } while ( tickets.tail != read_atomic(&lock->tickets.head) );
     }
     LOCK_PROFILE_GOT;
     preempt_disable();
@@ -153,40 +156,17 @@ void _spin_lock(spinlock_t *lock)
 
 void _spin_lock_irq(spinlock_t *lock)
 {
-    LOCK_PROFILE_VAR;
-
     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();
-    }
-    LOCK_PROFILE_GOT;
-    preempt_disable();
+    _spin_lock(lock);
 }
 
 unsigned long _spin_lock_irqsave(spinlock_t *lock)
 {
     unsigned long flags;
-    LOCK_PROFILE_VAR;
 
     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();
-    }
-    LOCK_PROFILE_GOT;
-    preempt_disable();
+    _spin_lock(lock);
     return flags;
 }
 
@@ -194,35 +174,44 @@ void _spin_unlock(spinlock_t *lock)
 {
     preempt_enable();
     LOCK_PROFILE_REL;
-    _raw_spin_unlock(&lock->raw);
+    lock->tickets.head++;
 }
 
 void _spin_unlock_irq(spinlock_t *lock)
 {
-    preempt_enable();
-    LOCK_PROFILE_REL;
-    _raw_spin_unlock(&lock->raw);
+    _spin_unlock(lock);
     local_irq_enable();
 }
 
 void _spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags)
 {
-    preempt_enable();
-    LOCK_PROFILE_REL;
-    _raw_spin_unlock(&lock->raw);
+    _spin_unlock(lock);
     local_irq_restore(flags);
 }
 
+static int __spin_is_locked(spinlock_t *lock)
+{
+    return lock->tickets.head != lock->tickets.tail;
+}
+
 int _spin_is_locked(spinlock_t *lock)
 {
     check_lock(&lock->debug);
-    return _raw_spin_is_locked(&lock->raw);
+    return __spin_is_locked(lock);
 }
 
 int _spin_trylock(spinlock_t *lock)
 {
+    spinlock_tickets_t old, new;
+
     check_lock(&lock->debug);
-    if ( !_raw_spin_trylock(&lock->raw) )
+    old.head_tail = read_atomic(&lock->tickets.head_tail);
+    if ( old.head != old.tail )
+        return 0;
+    new = old;
+    new.tail++;
+    if ( cmpxchg(&lock->tickets.head_tail, old.head_tail, new.head_tail)
+         != old.head_tail )
         return 0;
 #ifdef LOCK_PROFILE
     if (lock->profile)
@@ -239,7 +228,7 @@ void _spin_barrier(spinlock_t *lock)
     u64      loop = 0;
 
     check_barrier(&lock->debug);
-    do { smp_mb(); loop++;} while ( _raw_spin_is_locked(&lock->raw) );
+    do { smp_mb(); loop++;} while ( __spin_is_locked(lock) );
     if ((loop > 1) && lock->profile)
     {
         lock->profile->time_block += NOW() - block;
@@ -247,14 +236,14 @@ void _spin_barrier(spinlock_t *lock)
     }
 #else
     check_barrier(&lock->debug);
-    do { smp_mb(); } while ( _raw_spin_is_locked(&lock->raw) );
+    do { smp_mb(); } while ( __spin_is_locked(lock) );
 #endif
     smp_mb();
 }
 
 int _spin_trylock_recursive(spinlock_t *lock)
 {
-    int cpu = smp_processor_id();
+    unsigned int cpu = smp_processor_id();
 
     /* Don't allow overflow of recurse_cpu field. */
     BUILD_BUG_ON(NR_CPUS > 0xfffu);
@@ -277,8 +266,17 @@ int _spin_trylock_recursive(spinlock_t *lock)
 
 void _spin_lock_recursive(spinlock_t *lock)
 {
-    while ( !spin_trylock_recursive(lock) )
-        cpu_relax();
+    unsigned int cpu = smp_processor_id();
+
+    if ( likely(lock->recurse_cpu != cpu) )
+    {
+        spin_lock(lock);
+        lock->recurse_cpu = cpu;
+    }
+
+    /* We support only fairly shallow recursion, else the counter overflows. */
+    ASSERT(lock->recurse_cnt < 0xfu);
+    lock->recurse_cnt++;
 }
 
 void _spin_unlock_recursive(spinlock_t *lock)
diff --git a/xen/include/xen/spinlock.h b/xen/include/xen/spinlock.h
index eda9b2e..bafbc74 100644
--- a/xen/include/xen/spinlock.h
+++ b/xen/include/xen/spinlock.h
@@ -80,8 +80,7 @@ struct lock_profile_qhead {
     static struct lock_profile *__lock_profile_##name                         \
     __used_section(".lockprofile.data") =                                     \
     &__lock_profile_data_##name
-#define _SPIN_LOCK_UNLOCKED(x) { _RAW_SPIN_LOCK_UNLOCKED, 0xfffu, 0,          \
-                                 _LOCK_DEBUG, x }
+#define _SPIN_LOCK_UNLOCKED(x) { { 0 }, 0xfffu, 0, _LOCK_DEBUG, x }
 #define SPIN_LOCK_UNLOCKED _SPIN_LOCK_UNLOCKED(NULL)
 #define DEFINE_SPINLOCK(l)                                                    \
     spinlock_t l = _SPIN_LOCK_UNLOCKED(NULL);                                 \
@@ -117,8 +116,7 @@ extern void spinlock_profile_reset(unsigned char key);
 
 struct lock_profile_qhead { };
 
-#define SPIN_LOCK_UNLOCKED                                                    \
-    { _RAW_SPIN_LOCK_UNLOCKED, 0xfffu, 0, _LOCK_DEBUG }
+#define SPIN_LOCK_UNLOCKED { { 0 }, 0xfffu, 0, _LOCK_DEBUG }
 #define DEFINE_SPINLOCK(l) spinlock_t l = SPIN_LOCK_UNLOCKED
 
 #define spin_lock_init_prof(s, l) spin_lock_init(&((s)->l))
@@ -127,8 +125,16 @@ struct lock_profile_qhead { };
 
 #endif
 
+typedef union {
+    u32 head_tail;
+    struct {
+        u16 head;
+        u16 tail;
+    };
+} spinlock_tickets_t;
+
 typedef struct spinlock {
-    raw_spinlock_t raw;
+    spinlock_tickets_t tickets;
     u16 recurse_cpu:12;
     u16 recurse_cnt:4;
     struct lock_debug debug;
-- 
1.7.10.4

[PATCHv2 6/6] x86, arm: remove asm/spinlock.h from all architectures

[David Vrabel]

Now that all architecture use a common ticket lock implementation for
spinlocks, remove the architecture specific byte lock implementations.

Signed-off-by: David Vrabel <david.vrabel@citrix.com>
---
 xen/arch/arm/README.LinuxPrimitives  |   28 ---------------
 xen/include/asm-arm/arm32/spinlock.h |   66 ----------------------------------
 xen/include/asm-arm/arm64/spinlock.h |   63 --------------------------------
 xen/include/asm-arm/spinlock.h       |   23 ------------
 xen/include/asm-x86/spinlock.h       |   37 -------------------
 xen/include/xen/spinlock.h           |    1 -
 6 files changed, 218 deletions(-)
 delete mode 100644 xen/include/asm-arm/arm32/spinlock.h
 delete mode 100644 xen/include/asm-arm/arm64/spinlock.h
 delete mode 100644 xen/include/asm-arm/spinlock.h
 delete mode 100644 xen/include/asm-x86/spinlock.h

diff --git a/xen/arch/arm/README.LinuxPrimitives b/xen/arch/arm/README.LinuxPrimitives
index 7f33fc7..3115f51 100644
--- a/xen/arch/arm/README.LinuxPrimitives
+++ b/xen/arch/arm/README.LinuxPrimitives
@@ -25,16 +25,6 @@ linux/arch/arm64/include/asm/atomic.h   xen/include/asm-arm/arm64/atomic.h
 
 ---------------------------------------------------------------------
 
-spinlocks: last sync @ v3.16-rc6 (last commit: 95c4189689f9)
-
-linux/arch/arm64/include/asm/spinlock.h xen/include/asm-arm/arm64/spinlock.h
-
-Skipped:
-  5686b06 arm64: lockref: add support for lockless lockrefs using cmpxchg
-  52ea2a5 arm64: locks: introduce ticket-based spinlock implementation
-
----------------------------------------------------------------------
-
 mem*: last sync @ v3.16-rc6 (last commit: d875c9b37240)
 
 linux/arch/arm64/lib/memchr.S           xen/arch/arm/arm64/lib/memchr.S
@@ -103,24 +93,6 @@ linux/arch/arm/include/asm/atomic.h     xen/include/asm-arm/arm32/atomic.h
 
 ---------------------------------------------------------------------
 
-spinlocks: last sync: 15e7e5c1ebf5
-
-linux/arch/arm/include/asm/spinlock.h   xen/include/asm-arm/arm32/spinlock.h
-
-*** Linux has switched to ticket locks but we still use bitlocks.
-
-resync to v3.14-rc7:
-
-  7c8746a ARM: 7955/1: spinlock: ensure we have a compiler barrier before sev
-  0cbad9c ARM: 7854/1: lockref: add support for lockless lockrefs using cmpxchg64
-  9bb17be ARM: locks: prefetch the destination word for write prior to strex
-  27a8479 ARM: smp_on_up: move inline asm ALT_SMP patching macro out of spinlock.
-  00efaa0 ARM: 7812/1: rwlocks: retry trylock operation if strex fails on free lo
-  afa31d8 ARM: 7811/1: locks: use early clobber in arch_spin_trylock
-  73a6fdc ARM: spinlock: use inner-shareable dsb variant prior to sev instruction
-
----------------------------------------------------------------------
-
 mem*: last sync @ v3.16-rc6 (last commit: d98b90ea22b0)
 
 linux/arch/arm/lib/copy_template.S      xen/arch/arm/arm32/lib/copy_template.S
diff --git a/xen/include/asm-arm/arm32/spinlock.h b/xen/include/asm-arm/arm32/spinlock.h
deleted file mode 100644
index bc0343c..0000000
--- a/xen/include/asm-arm/arm32/spinlock.h
+++ /dev/null
@@ -1,66 +0,0 @@
-#ifndef __ASM_ARM32_SPINLOCK_H
-#define __ASM_ARM32_SPINLOCK_H
-
-static inline void dsb_sev(void)
-{
-    __asm__ __volatile__ (
-        "dsb\n"
-        "sev\n"
-        );
-}
-
-typedef struct {
-    volatile unsigned int lock;
-} raw_spinlock_t;
-
-#define _RAW_SPIN_LOCK_UNLOCKED { 0 }
-
-#define _raw_spin_is_locked(x)          ((x)->lock != 0)
-
-static always_inline void _raw_spin_unlock(raw_spinlock_t *lock)
-{
-    ASSERT(_raw_spin_is_locked(lock));
-
-    smp_mb();
-
-    __asm__ __volatile__(
-"   str     %1, [%0]\n"
-    :
-    : "r" (&lock->lock), "r" (0)
-    : "cc");
-
-    dsb_sev();
-}
-
-static always_inline int _raw_spin_trylock(raw_spinlock_t *lock)
-{
-    unsigned long contended, res;
-
-    do {
-        __asm__ __volatile__(
-    "   ldrex   %0, [%2]\n"
-    "   teq     %0, #0\n"
-    "   strexeq %1, %3, [%2]\n"
-    "   movne   %1, #0\n"
-        : "=&r" (contended), "=r" (res)
-        : "r" (&lock->lock), "r" (1)
-        : "cc");
-    } while (res);
-
-    if (!contended) {
-        smp_mb();
-        return 1;
-    } else {
-        return 0;
-    }
-}
-
-#endif /* __ASM_SPINLOCK_H */
-/*
- * Local variables:
- * mode: C
- * c-file-style: "BSD"
- * c-basic-offset: 4
- * indent-tabs-mode: nil
- * End:
- */
diff --git a/xen/include/asm-arm/arm64/spinlock.h b/xen/include/asm-arm/arm64/spinlock.h
deleted file mode 100644
index 5ae034d..0000000
--- a/xen/include/asm-arm/arm64/spinlock.h
+++ /dev/null
@@ -1,63 +0,0 @@
-/*
- * Derived from Linux arch64 spinlock.h which is:
- * Copyright (C) 2012 ARM Ltd.
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-#ifndef __ASM_ARM64_SPINLOCK_H
-#define __ASM_ARM64_SPINLOCK_H
-
-typedef struct {
-    volatile unsigned int lock;
-} raw_spinlock_t;
-
-#define _RAW_SPIN_LOCK_UNLOCKED { 0 }
-
-#define _raw_spin_is_locked(x)          ((x)->lock != 0)
-
-static always_inline void _raw_spin_unlock(raw_spinlock_t *lock)
-{
-    ASSERT(_raw_spin_is_locked(lock));
-
-    asm volatile(
-        "       stlr    %w1, %0\n"
-        : "=Q" (lock->lock) : "r" (0) : "memory");
-}
-
-static always_inline int _raw_spin_trylock(raw_spinlock_t *lock)
-{
-    unsigned int tmp;
-
-    asm volatile(
-        "2:     ldaxr   %w0, %1\n"
-        "       cbnz    %w0, 1f\n"
-        "       stxr    %w0, %w2, %1\n"
-        "       cbnz    %w0, 2b\n"
-        "1:\n"
-        : "=&r" (tmp), "+Q" (lock->lock)
-        : "r" (1)
-        : "cc", "memory");
-
-    return !tmp;
-}
-
-#endif /* __ASM_SPINLOCK_H */
-/*
- * Local variables:
- * mode: C
- * c-file-style: "BSD"
- * c-basic-offset: 4
- * indent-tabs-mode: nil
- * End:
- */
diff --git a/xen/include/asm-arm/spinlock.h b/xen/include/asm-arm/spinlock.h
deleted file mode 100644
index a064f73..0000000
--- a/xen/include/asm-arm/spinlock.h
+++ /dev/null
@@ -1,23 +0,0 @@
-#ifndef __ASM_SPINLOCK_H
-#define __ASM_SPINLOCK_H
-
-#include <xen/config.h>
-#include <xen/lib.h>
-
-#if defined(CONFIG_ARM_32)
-# include <asm/arm32/spinlock.h>
-#elif defined(CONFIG_ARM_64)
-# include <asm/arm64/spinlock.h>
-#else
-# error "unknown ARM variant"
-#endif
-
-#endif /* __ASM_SPINLOCK_H */
-/*
- * Local variables:
- * mode: C
- * c-file-style: "BSD"
- * c-basic-offset: 4
- * indent-tabs-mode: nil
- * End:
- */
diff --git a/xen/include/asm-x86/spinlock.h b/xen/include/asm-x86/spinlock.h
deleted file mode 100644
index 757e20b..0000000
--- a/xen/include/asm-x86/spinlock.h
+++ /dev/null
@@ -1,37 +0,0 @@
-#ifndef __ASM_SPINLOCK_H
-#define __ASM_SPINLOCK_H
-
-#include <xen/config.h>
-#include <xen/lib.h>
-#include <asm/atomic.h>
-
-typedef struct {
-    volatile s16 lock;
-} raw_spinlock_t;
-
-#define _RAW_SPIN_LOCK_UNLOCKED /*(raw_spinlock_t)*/ { 1 }
-
-#define _raw_spin_is_locked(x) ((x)->lock <= 0)
-
-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" );
-}
-
-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);
-}
-
-#define _raw_read_unlock(l) \
-    asm volatile ( "lock; dec%z0 %0" : "+m" ((l)->lock) :: "memory" )
-
-#endif /* __ASM_SPINLOCK_H */
diff --git a/xen/include/xen/spinlock.h b/xen/include/xen/spinlock.h
index bafbc74..311685a 100644
--- a/xen/include/xen/spinlock.h
+++ b/xen/include/xen/spinlock.h
@@ -2,7 +2,6 @@
 #define __SPINLOCK_H__
 
 #include <asm/system.h>
-#include <asm/spinlock.h>
 
 #ifndef NDEBUG
 struct lock_debug {
-- 
1.7.10.4

Re: [PATCHv2 1/6] x86/hvm: don't include asm/spinlock.h

[Andrew Cooper]

On 10/04/15 15:19, David Vrabel wrote:
> asm/spinlock.h should not be included directly.
>
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>

s/asm/xen/g instead of a straight delete?

Otherwise you are relying on pulling in xen/spinlock.h implicitly.

~Andrew

> ---
>  xen/arch/x86/hvm/hvm.c     |    1 -
>  xen/arch/x86/hvm/svm/svm.c |    1 -
>  xen/arch/x86/hvm/vmx/vmx.c |    1 -
>  3 files changed, 3 deletions(-)
>
> diff --git a/xen/arch/x86/hvm/hvm.c b/xen/arch/x86/hvm/hvm.c
> index 4734d71..6937857 100644
> --- a/xen/arch/x86/hvm/hvm.c
> +++ b/xen/arch/x86/hvm/hvm.c
> @@ -52,7 +52,6 @@
>  #include <asm/xstate.h>
>  #include <asm/traps.h>
>  #include <asm/mc146818rtc.h>
> -#include <asm/spinlock.h>
>  #include <asm/mce.h>
>  #include <asm/hvm/hvm.h>
>  #include <asm/hvm/vpt.h>
> diff --git a/xen/arch/x86/hvm/svm/svm.c b/xen/arch/x86/hvm/svm/svm.c
> index b6e77cd..6734fb6 100644
> --- a/xen/arch/x86/hvm/svm/svm.c
> +++ b/xen/arch/x86/hvm/svm/svm.c
> @@ -41,7 +41,6 @@
>  #include <asm/msr.h>
>  #include <asm/i387.h>
>  #include <asm/iocap.h>
> -#include <asm/spinlock.h>
>  #include <asm/hvm/emulate.h>
>  #include <asm/hvm/hvm.h>
>  #include <asm/hvm/support.h>
> diff --git a/xen/arch/x86/hvm/vmx/vmx.c b/xen/arch/x86/hvm/vmx/vmx.c
> index e1c55ce..2a0610b 100644
> --- a/xen/arch/x86/hvm/vmx/vmx.c
> +++ b/xen/arch/x86/hvm/vmx/vmx.c
> @@ -35,7 +35,6 @@
>  #include <asm/types.h>
>  #include <asm/debugreg.h>
>  #include <asm/msr.h>
> -#include <asm/spinlock.h>
>  #include <asm/paging.h>
>  #include <asm/p2m.h>
>  #include <asm/mem_sharing.h>

Re: [PATCHv2 2/6] x86/mtrr: include asm/atomic.h

[Andrew Cooper]

On 10/04/15 15:19, David Vrabel wrote:
> asm/atomic.h is needed but only included indirectly via
> asm/spinlock.h.
>
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>

Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>

> ---
>  xen/arch/x86/cpu/mtrr/main.c |    1 +
>  1 file changed, 1 insertion(+)
>
> diff --git a/xen/arch/x86/cpu/mtrr/main.c b/xen/arch/x86/cpu/mtrr/main.c
> index f5d5317..030a911 100644
> --- a/xen/arch/x86/cpu/mtrr/main.c
> +++ b/xen/arch/x86/cpu/mtrr/main.c
> @@ -36,6 +36,7 @@
>  #include <xen/lib.h>
>  #include <xen/smp.h>
>  #include <xen/spinlock.h>
> +#include <asm/atomic.h>
>  #include <asm/mtrr.h>
>  #include <asm/uaccess.h>
>  #include <asm/processor.h>

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[Andrew Cooper]

On 10/04/15 15:19, David Vrabel wrote:
> Replace the byte locks with ticket locks.  Ticket locks are: a) fair;
> and b) peform better when contented since they spin without an atomic
> operation.
>
> The lock is split into two ticket values: head and tail.  A locker
> acquires a ticket by (atomically) increasing tail and using the
> previous tail value.  A CPU holds the lock if its ticket == head.  The
> lock is released by increasing head.
>
> Architectures need only provide an xadd() implementation.
>
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>

While I think this implementation is fine for x86, ARM almost certainly
requires some smp barriers.

~Andrew

> ---
>  xen/common/spinlock.c      |   80 +++++++++++++++++++++-----------------------
>  xen/include/xen/spinlock.h |   16 ++++++---
>  2 files changed, 50 insertions(+), 46 deletions(-)
>
> diff --git a/xen/common/spinlock.c b/xen/common/spinlock.c
> index 0c4289c..99163c5 100644
> --- a/xen/common/spinlock.c
> +++ b/xen/common/spinlock.c
> @@ -138,14 +138,17 @@ void spin_debug_disable(void)
>  
>  void _spin_lock(spinlock_t *lock)
>  {
> +    spinlock_tickets_t tickets = { .tail = 1, };
>      LOCK_PROFILE_VAR;
>  
>      check_lock(&lock->debug);
> -    while ( unlikely(!_raw_spin_trylock(&lock->raw)) )
> +    tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
> +    if ( tickets.tail != read_atomic(&lock->tickets.head) )
>      {
>          LOCK_PROFILE_BLOCK;
> -        while ( likely(_raw_spin_is_locked(&lock->raw)) )
> +        do {
>              cpu_relax();
> +        } while ( tickets.tail != read_atomic(&lock->tickets.head) );
>      }
>      LOCK_PROFILE_GOT;
>      preempt_disable();
> @@ -153,40 +156,17 @@ void _spin_lock(spinlock_t *lock)
>  
>  void _spin_lock_irq(spinlock_t *lock)
>  {
> -    LOCK_PROFILE_VAR;
> -
>      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();
> -    }
> -    LOCK_PROFILE_GOT;
> -    preempt_disable();
> +    _spin_lock(lock);
>  }
>  
>  unsigned long _spin_lock_irqsave(spinlock_t *lock)
>  {
>      unsigned long flags;
> -    LOCK_PROFILE_VAR;
>  
>      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();
> -    }
> -    LOCK_PROFILE_GOT;
> -    preempt_disable();
> +    _spin_lock(lock);
>      return flags;
>  }
>  
> @@ -194,35 +174,44 @@ void _spin_unlock(spinlock_t *lock)
>  {
>      preempt_enable();
>      LOCK_PROFILE_REL;
> -    _raw_spin_unlock(&lock->raw);
> +    lock->tickets.head++;
>  }
>  
>  void _spin_unlock_irq(spinlock_t *lock)
>  {
> -    preempt_enable();
> -    LOCK_PROFILE_REL;
> -    _raw_spin_unlock(&lock->raw);
> +    _spin_unlock(lock);
>      local_irq_enable();
>  }
>  
>  void _spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags)
>  {
> -    preempt_enable();
> -    LOCK_PROFILE_REL;
> -    _raw_spin_unlock(&lock->raw);
> +    _spin_unlock(lock);
>      local_irq_restore(flags);
>  }
>  
> +static int __spin_is_locked(spinlock_t *lock)
> +{
> +    return lock->tickets.head != lock->tickets.tail;
> +}
> +
>  int _spin_is_locked(spinlock_t *lock)
>  {
>      check_lock(&lock->debug);
> -    return _raw_spin_is_locked(&lock->raw);
> +    return __spin_is_locked(lock);
>  }
>  
>  int _spin_trylock(spinlock_t *lock)
>  {
> +    spinlock_tickets_t old, new;
> +
>      check_lock(&lock->debug);
> -    if ( !_raw_spin_trylock(&lock->raw) )
> +    old.head_tail = read_atomic(&lock->tickets.head_tail);
> +    if ( old.head != old.tail )
> +        return 0;
> +    new = old;
> +    new.tail++;
> +    if ( cmpxchg(&lock->tickets.head_tail, old.head_tail, new.head_tail)
> +         != old.head_tail )
>          return 0;
>  #ifdef LOCK_PROFILE
>      if (lock->profile)
> @@ -239,7 +228,7 @@ void _spin_barrier(spinlock_t *lock)
>      u64      loop = 0;
>  
>      check_barrier(&lock->debug);
> -    do { smp_mb(); loop++;} while ( _raw_spin_is_locked(&lock->raw) );
> +    do { smp_mb(); loop++;} while ( __spin_is_locked(lock) );
>      if ((loop > 1) && lock->profile)
>      {
>          lock->profile->time_block += NOW() - block;
> @@ -247,14 +236,14 @@ void _spin_barrier(spinlock_t *lock)
>      }
>  #else
>      check_barrier(&lock->debug);
> -    do { smp_mb(); } while ( _raw_spin_is_locked(&lock->raw) );
> +    do { smp_mb(); } while ( __spin_is_locked(lock) );
>  #endif
>      smp_mb();
>  }
>  
>  int _spin_trylock_recursive(spinlock_t *lock)
>  {
> -    int cpu = smp_processor_id();
> +    unsigned int cpu = smp_processor_id();
>  
>      /* Don't allow overflow of recurse_cpu field. */
>      BUILD_BUG_ON(NR_CPUS > 0xfffu);
> @@ -277,8 +266,17 @@ int _spin_trylock_recursive(spinlock_t *lock)
>  
>  void _spin_lock_recursive(spinlock_t *lock)
>  {
> -    while ( !spin_trylock_recursive(lock) )
> -        cpu_relax();
> +    unsigned int cpu = smp_processor_id();
> +
> +    if ( likely(lock->recurse_cpu != cpu) )
> +    {
> +        spin_lock(lock);
> +        lock->recurse_cpu = cpu;
> +    }
> +
> +    /* We support only fairly shallow recursion, else the counter overflows. */
> +    ASSERT(lock->recurse_cnt < 0xfu);
> +    lock->recurse_cnt++;
>  }
>  
>  void _spin_unlock_recursive(spinlock_t *lock)
> diff --git a/xen/include/xen/spinlock.h b/xen/include/xen/spinlock.h
> index eda9b2e..bafbc74 100644
> --- a/xen/include/xen/spinlock.h
> +++ b/xen/include/xen/spinlock.h
> @@ -80,8 +80,7 @@ struct lock_profile_qhead {
>      static struct lock_profile *__lock_profile_##name                         \
>      __used_section(".lockprofile.data") =                                     \
>      &__lock_profile_data_##name
> -#define _SPIN_LOCK_UNLOCKED(x) { _RAW_SPIN_LOCK_UNLOCKED, 0xfffu, 0,          \
> -                                 _LOCK_DEBUG, x }
> +#define _SPIN_LOCK_UNLOCKED(x) { { 0 }, 0xfffu, 0, _LOCK_DEBUG, x }
>  #define SPIN_LOCK_UNLOCKED _SPIN_LOCK_UNLOCKED(NULL)
>  #define DEFINE_SPINLOCK(l)                                                    \
>      spinlock_t l = _SPIN_LOCK_UNLOCKED(NULL);                                 \
> @@ -117,8 +116,7 @@ extern void spinlock_profile_reset(unsigned char key);
>  
>  struct lock_profile_qhead { };
>  
> -#define SPIN_LOCK_UNLOCKED                                                    \
> -    { _RAW_SPIN_LOCK_UNLOCKED, 0xfffu, 0, _LOCK_DEBUG }
> +#define SPIN_LOCK_UNLOCKED { { 0 }, 0xfffu, 0, _LOCK_DEBUG }
>  #define DEFINE_SPINLOCK(l) spinlock_t l = SPIN_LOCK_UNLOCKED
>  
>  #define spin_lock_init_prof(s, l) spin_lock_init(&((s)->l))
> @@ -127,8 +125,16 @@ struct lock_profile_qhead { };
>  
>  #endif
>  
> +typedef union {
> +    u32 head_tail;
> +    struct {
> +        u16 head;
> +        u16 tail;
> +    };
> +} spinlock_tickets_t;
> +
>  typedef struct spinlock {
> -    raw_spinlock_t raw;
> +    spinlock_tickets_t tickets;
>      u16 recurse_cpu:12;
>      u16 recurse_cnt:4;
>      struct lock_debug debug;

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[Boris Ostrovsky]

On 04/10/2015 10:19 AM, David Vrabel wrote:

> @@ -138,14 +138,17 @@ void spin_debug_disable(void)
>
>   void _spin_lock(spinlock_t *lock)
>   {
> +    spinlock_tickets_t tickets = { .tail = 1, };
>       LOCK_PROFILE_VAR;
>
>       check_lock(&lock->debug);
> -    while ( unlikely(!_raw_spin_trylock(&lock->raw)) )
> +    tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
> +    if ( tickets.tail != read_atomic(&lock->tickets.head) )
>       {
>           LOCK_PROFILE_BLOCK;
> -        while ( likely(_raw_spin_is_locked(&lock->raw)) )
> +        do {
>               cpu_relax();
> +        } while ( tickets.tail != read_atomic(&lock->tickets.head) );
>       }


Why do you use both 'if' and 'while"? I.e. why not just

while ( tickets.tail != read_atomic(&lock->tickets.head) )
{
	LOCK_PROFILE_BLOCK;
	cpu_relax();
}




>
> @@ -194,35 +174,44 @@ void _spin_unlock(spinlock_t *lock)
>   {
>       preempt_enable();
>       LOCK_PROFILE_REL;
> -    _raw_spin_unlock(&lock->raw);
> +    lock->tickets.head++;


Is it safe to do a plain increment here and a locked one?


-boris

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[David Vrabel]

On 10/04/2015 17:44, Boris Ostrovsky wrote:
> On 04/10/2015 10:19 AM, David Vrabel wrote:
> 
>> @@ -138,14 +138,17 @@ void spin_debug_disable(void)
>>
>>   void _spin_lock(spinlock_t *lock)
>>   {
>> +    spinlock_tickets_t tickets = { .tail = 1, };
>>       LOCK_PROFILE_VAR;
>>
>>       check_lock(&lock->debug);
>> -    while ( unlikely(!_raw_spin_trylock(&lock->raw)) )
>> +    tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
>> +    if ( tickets.tail != read_atomic(&lock->tickets.head) )
>>       {
>>           LOCK_PROFILE_BLOCK;
>> -        while ( likely(_raw_spin_is_locked(&lock->raw)) )
>> +        do {
>>               cpu_relax();
>> +        } while ( tickets.tail != read_atomic(&lock->tickets.head) );
>>       }
> 
> 
> Why do you use both 'if' and 'while"? I.e. why not just
> 
> while ( tickets.tail != read_atomic(&lock->tickets.head) )
> {
>     LOCK_PROFILE_BLOCK;
>     cpu_relax();
> }

We need to only call LOCK_PROFILE_BLOCK once when we start blocking.

>> @@ -194,35 +174,44 @@ void _spin_unlock(spinlock_t *lock)
>>   {
>>       preempt_enable();
>>       LOCK_PROFILE_REL;
>> -    _raw_spin_unlock(&lock->raw);
>> +    lock->tickets.head++;
> 
> 
> Is it safe to do a plain increment here and a locked one?

Yes. Only the lock holder writes to head.

David

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[Boris Ostrovsky]

On 04/10/2015 01:29 PM, David Vrabel wrote:
>
> On 10/04/2015 17:44, Boris Ostrovsky wrote:
>> On 04/10/2015 10:19 AM, David Vrabel wrote:
>>
>>> @@ -138,14 +138,17 @@ void spin_debug_disable(void)
>>>
>>>    void _spin_lock(spinlock_t *lock)
>>>    {
>>> +    spinlock_tickets_t tickets = { .tail = 1, };
>>>        LOCK_PROFILE_VAR;
>>>
>>>        check_lock(&lock->debug);
>>> -    while ( unlikely(!_raw_spin_trylock(&lock->raw)) )
>>> +    tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
>>> +    if ( tickets.tail != read_atomic(&lock->tickets.head) )
>>>        {
>>>            LOCK_PROFILE_BLOCK;
>>> -        while ( likely(_raw_spin_is_locked(&lock->raw)) )
>>> +        do {
>>>                cpu_relax();
>>> +        } while ( tickets.tail != read_atomic(&lock->tickets.head) );
>>>        }
>>
>> Why do you use both 'if' and 'while"? I.e. why not just
>>
>> while ( tickets.tail != read_atomic(&lock->tickets.head) )
>> {
>>      LOCK_PROFILE_BLOCK;
>>      cpu_relax();
>> }
> We need to only call LOCK_PROFILE_BLOCK once when we start blocking.

LOCK_PROFILE_BLOCK is a "one-shot" assignment. Once 'block' is set to 
NOW() it doesn't change anymore. So it will be updated only on the first 
iteration of the loop.

-boris

Re: [PATCHv2 1/6] x86/hvm: don't include asm/spinlock.h

[David Vrabel]

On 10/04/15 16:24, Andrew Cooper wrote:
> On 10/04/15 15:19, David Vrabel wrote:
>> asm/spinlock.h should not be included directly.
>>
>> Signed-off-by: David Vrabel <david.vrabel@citrix.com>
> 
> s/asm/xen/g instead of a straight delete?
> 
> Otherwise you are relying on pulling in xen/spinlock.h implicitly.

None of these files declare a spinlock so getting the header implicitly
is correct, IMO.

David

>>  xen/arch/x86/hvm/hvm.c     |    1 -
>>  xen/arch/x86/hvm/svm/svm.c |    1 -
>>  xen/arch/x86/hvm/vmx/vmx.c |    1 -

Re: [PATCHv2 1/6] x86/hvm: don't include asm/spinlock.h

[Andrew Cooper]

On 13/04/15 14:13, David Vrabel wrote:
> On 10/04/15 16:24, Andrew Cooper wrote:
>> On 10/04/15 15:19, David Vrabel wrote:
>>> asm/spinlock.h should not be included directly.
>>>
>>> Signed-off-by: David Vrabel <david.vrabel@citrix.com>
>> s/asm/xen/g instead of a straight delete?
>>
>> Otherwise you are relying on pulling in xen/spinlock.h implicitly.
> None of these files declare a spinlock so getting the header implicitly
> is correct, IMO.

In which case, good riddance.

Acked-by: Andrew Cooper <andrew.cooper3@citrix.com>

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[Ian Campbell]

On Fri, 2015-04-10 at 15:19 +0100, David Vrabel wrote:
> This is only temporary until arm/arm64 provides an xadd()
> implementation.

I'll assume that you aren't planning on doing this and add it to my own
TODO list. Although, I'm more than willing to be preempted by another
ARM dev...

> 
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>
> ---
>  xen/common/spinlock.c |   21 +++++++++++++++++++++
>  1 file changed, 21 insertions(+)
> 
> diff --git a/xen/common/spinlock.c b/xen/common/spinlock.c
> index 5fd8b1c..0c4289c 100644
> --- a/xen/common/spinlock.c
> +++ b/xen/common/spinlock.c
> @@ -10,6 +10,27 @@
>  #include <asm/processor.h>
>  #include <asm/atomic.h>
>  
> +#ifndef xadd
> +
> +static u32 generic_xaddl(volatile u32 *ptr, u32 v)
> +{
> +    u32 old, new, prev;
> +
> +    old = read_atomic(ptr);
> +    for(;;) {
> +        new = old + v;
> +        prev = cmpxchg(ptr, old, new);
> +        if (prev == old)
> +            break;
> +        old = prev;
> +    }
> +    return old;
> +}
> +
> +#define xadd(ptr, v) generic_xaddl((ptr), (v))
> +
> +#endif
> +
>  #ifndef NDEBUG
>  
>  static atomic_t spin_debug __read_mostly = ATOMIC_INIT(0);

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[David Vrabel]

On 14/04/15 14:17, Ian Campbell wrote:
> On Fri, 2015-04-10 at 15:19 +0100, David Vrabel wrote:
>> This is only temporary until arm/arm64 provides an xadd()
>> implementation.
> 
> I'll assume that you aren't planning on doing this and add it to my own
> TODO list. Although, I'm more than willing to be preempted by another
> ARM dev...

Thanks.  I'd hoped I could lift something from Linux but there's nothing
directly suited.

David

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[Ian Campbell]

On Tue, 2015-04-14 at 17:37 +0100, David Vrabel wrote:
> On 14/04/15 14:17, Ian Campbell wrote:
> > On Fri, 2015-04-10 at 15:19 +0100, David Vrabel wrote:
> >> This is only temporary until arm/arm64 provides an xadd()
> >> implementation.
> > 
> > I'll assume that you aren't planning on doing this and add it to my own
> > TODO list. Although, I'm more than willing to be preempted by another
> > ARM dev...
> 
> Thanks.  I'd hoped I could lift something from Linux but there's nothing
> directly suited.

I looked too and didn't find anything suitable. It should be pretty
trivial using ldrex and friends, I've added it to my list.

Ian.

Re: [PATCHv2 1/6] x86/hvm: don't include asm/spinlock.h

[Tim Deegan]

At 15:19 +0100 on 10 Apr (1428679192), David Vrabel wrote:
> asm/spinlock.h should not be included directly.
> 
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>

Reviewed-by: TIm Deegan <tim@xen.org>

Re: [PATCHv2 2/6] x86/mtrr: include asm/atomic.h

[Tim Deegan]

At 15:19 +0100 on 10 Apr (1428679193), David Vrabel wrote:
> asm/atomic.h is needed but only included indirectly via
> asm/spinlock.h.
> 
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>

Reviewed-by: Tim Deegan <tim@xen.org>

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[Tim Deegan]

At 15:19 +0100 on 10 Apr (1428679194), David Vrabel wrote:
> Provide a generic xadd() implementation for architectures that don't
> provide one.
> 
> This is only temporary until arm/arm64 provides an xadd()
> implementation.
> 
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>

The logic looks fine, but please:
 - add a comment explaining what it does; and
 - convert it to Xen coding style to match the rest of the file. 

With that,

Reviewed-by: Tim Deegan <tim@xen.org>

Cheers,

Tim.

> ---
>  xen/common/spinlock.c |   21 +++++++++++++++++++++
>  1 file changed, 21 insertions(+)
> 
> diff --git a/xen/common/spinlock.c b/xen/common/spinlock.c
> index 5fd8b1c..0c4289c 100644
> --- a/xen/common/spinlock.c
> +++ b/xen/common/spinlock.c
> @@ -10,6 +10,27 @@
>  #include <asm/processor.h>
>  #include <asm/atomic.h>
>  
> +#ifndef xadd
> +
> +static u32 generic_xaddl(volatile u32 *ptr, u32 v)
> +{
> +    u32 old, new, prev;
> +
> +    old = read_atomic(ptr);
> +    for(;;) {
> +        new = old + v;
> +        prev = cmpxchg(ptr, old, new);
> +        if (prev == old)
> +            break;
> +        old = prev;
> +    }
> +    return old;
> +}
> +
> +#define xadd(ptr, v) generic_xaddl((ptr), (v))
> +
> +#endif
> +
>  #ifndef NDEBUG
>  
>  static atomic_t spin_debug __read_mostly = ATOMIC_INIT(0);
> -- 
> 1.7.10.4
> 
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xen.org
> http://lists.xen.org/xen-devel

Re: [PATCHv2 4/6] x86: provide xadd()

[Tim Deegan]

At 15:19 +0100 on 10 Apr (1428679195), David Vrabel wrote:
> xadd() atomically adds a value and returns the previous value.  This
> is needed to implement ticket locks.
> 
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>
> ---
>  xen/include/asm-x86/system.h |   29 +++++++++++++++++++++++++++++
>  1 file changed, 29 insertions(+)
> 
> diff --git a/xen/include/asm-x86/system.h b/xen/include/asm-x86/system.h
> index 7111329..1e6c6a8 100644
> --- a/xen/include/asm-x86/system.h
> +++ b/xen/include/asm-x86/system.h
> @@ -117,6 +117,35 @@ static always_inline unsigned long __cmpxchg(
>                                     (unsigned long)__n,sizeof(*(ptr)))); \
>  })
>  
> +static always_inline unsigned long __xadd(
> +    volatile void *ptr, unsigned long v, int size)
> +{
> +    switch ( size )
> +    {
> +    case 1:
> +        asm volatile ( "lock; xaddb %b0,%1"
> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
> +        return v;
> +    case 2:
> +        asm volatile ( "lock; xaddw %w0,%1"
> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
> +        return v;
> +    case 4:
> +        asm volatile ( "lock; xaddl %k0,%1"
> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
> +        return v;
> +    case 8:
> +        asm volatile ( "lock; xaddq %q0,%1"
> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
> +        return v;
> +    }
> +    return 0;

ASSERT_UNREACHABLE(), rather?  And some appropriate BUILD_BUG_ON?

But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
exactly this (the difference being that those are also compiler
barriers where this is only a CPU barrier).  Should we be using it
instead?

Tim.

Re: [PATCHv2 4/6] x86: provide xadd()

[David Vrabel]

On 16/04/15 12:25, Tim Deegan wrote:
> At 15:19 +0100 on 10 Apr (1428679195), David Vrabel wrote:
>> xadd() atomically adds a value and returns the previous value.  This
>> is needed to implement ticket locks.
>>
>> Signed-off-by: David Vrabel <david.vrabel@citrix.com>
>> ---
>>  xen/include/asm-x86/system.h |   29 +++++++++++++++++++++++++++++
>>  1 file changed, 29 insertions(+)
>>
>> diff --git a/xen/include/asm-x86/system.h b/xen/include/asm-x86/system.h
>> index 7111329..1e6c6a8 100644
>> --- a/xen/include/asm-x86/system.h
>> +++ b/xen/include/asm-x86/system.h
>> @@ -117,6 +117,35 @@ static always_inline unsigned long __cmpxchg(
>>                                     (unsigned long)__n,sizeof(*(ptr)))); \
>>  })
>>  
>> +static always_inline unsigned long __xadd(
>> +    volatile void *ptr, unsigned long v, int size)
>> +{
>> +    switch ( size )
>> +    {
>> +    case 1:
>> +        asm volatile ( "lock; xaddb %b0,%1"
>> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
>> +        return v;
>> +    case 2:
>> +        asm volatile ( "lock; xaddw %w0,%1"
>> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
>> +        return v;
>> +    case 4:
>> +        asm volatile ( "lock; xaddl %k0,%1"
>> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
>> +        return v;
>> +    case 8:
>> +        asm volatile ( "lock; xaddq %q0,%1"
>> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
>> +        return v;
>> +    }
>> +    return 0;
> 
> ASSERT_UNREACHABLE(), rather?  And some appropriate BUILD_BUG_ON?
> 
> But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
> exactly this (the difference being that those are also compiler
> barriers where this is only a CPU barrier).  Should we be using it
> instead?

I wasn't aware of the GCC built-ins -- I'll try them out. I think asm
volatile is a compiler barrier though.

David

Re: [PATCHv2 4/6] x86: provide xadd()

[Tim Deegan]

At 12:38 +0100 on 16 Apr (1429187920), David Vrabel wrote:
> On 16/04/15 12:25, Tim Deegan wrote:
> > At 15:19 +0100 on 10 Apr (1428679195), David Vrabel wrote:
> >> xadd() atomically adds a value and returns the previous value.  This
> >> is needed to implement ticket locks.
> >>
> >> Signed-off-by: David Vrabel <david.vrabel@citrix.com>
> >> ---
> >>  xen/include/asm-x86/system.h |   29 +++++++++++++++++++++++++++++
> >>  1 file changed, 29 insertions(+)
> >>
> >> diff --git a/xen/include/asm-x86/system.h b/xen/include/asm-x86/system.h
> >> index 7111329..1e6c6a8 100644
> >> --- a/xen/include/asm-x86/system.h
> >> +++ b/xen/include/asm-x86/system.h
> >> @@ -117,6 +117,35 @@ static always_inline unsigned long __cmpxchg(
> >>                                     (unsigned long)__n,sizeof(*(ptr)))); \
> >>  })
> >>  
> >> +static always_inline unsigned long __xadd(
> >> +    volatile void *ptr, unsigned long v, int size)
> >> +{
> >> +    switch ( size )
> >> +    {
> >> +    case 1:
> >> +        asm volatile ( "lock; xaddb %b0,%1"
> >> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
> >> +        return v;
> >> +    case 2:
> >> +        asm volatile ( "lock; xaddw %w0,%1"
> >> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
> >> +        return v;
> >> +    case 4:
> >> +        asm volatile ( "lock; xaddl %k0,%1"
> >> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
> >> +        return v;
> >> +    case 8:
> >> +        asm volatile ( "lock; xaddq %q0,%1"
> >> +                       : "+r" (v), "+m" (*__xg((volatile void *)ptr)));
> >> +        return v;
> >> +    }
> >> +    return 0;
> > 
> > ASSERT_UNREACHABLE(), rather?  And some appropriate BUILD_BUG_ON?
> > 
> > But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
> > exactly this (the difference being that those are also compiler
> > barriers where this is only a CPU barrier).  Should we be using it
> > instead?
> 
> I wasn't aware of the GCC built-ins -- I'll try them out. I think asm
> volatile is a compiler barrier though.

Nope - you need to specify a "memory" clobber for that (as the otehr
similar ops in this file do).

Cheers,

Tim.

Re: [PATCHv2 4/6] x86: provide xadd()

[Jan Beulich]

>>> On 16.04.15 at 13:25, <tim@xen.org> wrote:
> But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
> exactly this (the difference being that those are also compiler
> barriers where this is only a CPU barrier).  Should we be using it
> instead?

I'm afraid that's useful only from gcc 4.5.x onwards; earlier versions
(on x86 at least) simply generate a function call relying on a library to
implement it.

Jan

Re: [PATCHv2 4/6] x86: provide xadd()

[Ian Campbell]

On Thu, 2015-04-16 at 12:25 +0100, Tim Deegan wrote:
> But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
> exactly this (the difference being that those are also compiler
> barriers where this is only a CPU barrier).  Should we be using it
> instead?

In general I'm of the opinion we should, because it makes my life easier
on ARM (and perhaps we should trust compiler folks...)

Big question though would be when it became available in gcc. I think
that's generally why Linux hasn't switched in many cases, or perhaps
(historical?) concerns about whether they are optimal enough.

Ian.

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[Tim Deegan]

At 15:19 +0100 on 10 Apr (1428679196), David Vrabel wrote:
> Replace the byte locks with ticket locks.  Ticket locks are: a) fair;
> and b) peform better when contented since they spin without an atomic
> operation.
> 
> The lock is split into two ticket values: head and tail.  A locker
> acquires a ticket by (atomically) increasing tail and using the
> previous tail value.  A CPU holds the lock if its ticket == head.  The
> lock is released by increasing head.
> 
> Architectures need only provide an xadd() implementation.

I like this.  Thanks for measuring the IRQ latency too -- that's the
most nervous-making part of the overall change. 

+1 to Andrew's comment about needing some more barriers on ARM.  In
particular read barriers during the spin and full acquire/release on
lock/unlock.

Should there be a follow-up patch that removes all the arch-specific
raw_spinlock_t stuff?  Or is it still in use somewhere else?

> +static int __spin_is_locked(spinlock_t *lock)
> +{
> +    return lock->tickets.head != lock->tickets.tail;
> +}

Maybe atomic_read the lock and do the comparison on the local value?
Just from an abundance of caution - can't think of an obvious reason
why this race should matter.

> +
>  int _spin_is_locked(spinlock_t *lock)
>  {
>      check_lock(&lock->debug);
> -    return _raw_spin_is_locked(&lock->raw);
> +    return __spin_is_locked(lock);
>  }
>  
>  int _spin_trylock(spinlock_t *lock)
>  {
> +    spinlock_tickets_t old, new;
> +
>      check_lock(&lock->debug);
> -    if ( !_raw_spin_trylock(&lock->raw) )
> +    old.head_tail = read_atomic(&lock->tickets.head_tail);

This is common enough that we might want a helper like:
static inline spinlock_tickets_t observe_lock (spinlock_tickets_t *l)
{
    smp_rmb();	
    return (spinlock_tickets_t) { .head_tail = read_atomic(&l->tickets.head_tail) };
}
(or some similar formulation that's actually valid C).

> @@ -239,7 +228,7 @@ void _spin_barrier(spinlock_t *lock)
>      u64      loop = 0;
>  
>      check_barrier(&lock->debug);
> -    do { smp_mb(); loop++;} while ( _raw_spin_is_locked(&lock->raw) );
> +    do { smp_mb(); loop++;} while ( __spin_is_locked(lock) );
>      if ((loop > 1) && lock->profile)
>      {
>          lock->profile->time_block += NOW() - block;
> @@ -247,14 +236,14 @@ void _spin_barrier(spinlock_t *lock)
>      }
>  #else
>      check_barrier(&lock->debug);
> -    do { smp_mb(); } while ( _raw_spin_is_locked(&lock->raw) );
> +    do { smp_mb(); } while ( __spin_is_locked(lock) );

For a contended lock this is potentially a lot stronger than the old
barrier: this waits until the lock is held _and_ no other CPU is waiting
for it.   I think what we need here is:
 - sample := observe_lock() 
 - if sample.head == sample.tail, exit immediately
 - else wait until observe_lock().head != sample.head

Cheers,

Tim.

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[David Vrabel]

On 16/04/15 13:03, Tim Deegan wrote:
> 
> Should there be a follow-up patch that removes all the arch-specific
> raw_spinlock_t stuff?  Or is it still in use somewhere else?

This is patch #6.

David

Re: [PATCHv2 4/6] x86: provide xadd()

[Tim Deegan]

At 12:49 +0100 on 16 Apr (1429188559), Jan Beulich wrote:
> >>> On 16.04.15 at 13:25, <tim@xen.org> wrote:
> > But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
> > exactly this (the difference being that those are also compiler
> > barriers where this is only a CPU barrier).  Should we be using it
> > instead?
> 
> I'm afraid that's useful only from gcc 4.5.x onwards; earlier versions
> (on x86 at least) simply generate a function call relying on a library to
> implement it.

Darn. :(

Tim.

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[Tim Deegan]

At 13:46 +0100 on 16 Apr (1429192004), David Vrabel wrote:
> On 16/04/15 13:03, Tim Deegan wrote:
> > 
> > Should there be a follow-up patch that removes all the arch-specific
> > raw_spinlock_t stuff?  Or is it still in use somewhere else?
> 
> This is patch #6.

So it is.  /me needs an eye test.  Sorry for the noise.

Tim.

Re: [PATCHv2 6/6] x86, arm: remove asm/spinlock.h from all architectures

[Tim Deegan]

At 15:19 +0100 on 10 Apr (1428679197), David Vrabel wrote:
> Now that all architecture use a common ticket lock implementation for
> spinlocks, remove the architecture specific byte lock implementations.
> 
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>

Reviewed-by: Tim Deegan <tim@xen.org>

Re: [PATCHv2 4/6] x86: provide xadd()

[Ian Campbell]

On Thu, 2015-04-16 at 13:49 +0100, Tim Deegan wrote:
> At 12:49 +0100 on 16 Apr (1429188559), Jan Beulich wrote:
> > >>> On 16.04.15 at 13:25, <tim@xen.org> wrote:
> > > But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
> > > exactly this (the difference being that those are also compiler
> > > barriers where this is only a CPU barrier).  Should we be using it
> > > instead?
> > 
> > I'm afraid that's useful only from gcc 4.5.x onwards; earlier versions
> > (on x86 at least) simply generate a function call relying on a library to
> > implement it.
> 
> Darn. :(

Might it still be a better generic fallback than the C/cmpxchg one?

On x86 you'd get the asm version, and on ARM you need 4.5.x onwards
anyway, plus in general the ARM folks seem to recommend using the
builtins more anyway.

Ian.

Re: [PATCHv2 4/6] x86: provide xadd()

[Jan Beulich]

>>> On 16.04.15 at 14:55, <ian.campbell@citrix.com> wrote:
> On Thu, 2015-04-16 at 13:49 +0100, Tim Deegan wrote:
>> At 12:49 +0100 on 16 Apr (1429188559), Jan Beulich wrote:
>> > >>> On 16.04.15 at 13:25, <tim@xen.org> wrote:
>> > > But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
>> > > exactly this (the difference being that those are also compiler
>> > > barriers where this is only a CPU barrier).  Should we be using it
>> > > instead?
>> > 
>> > I'm afraid that's useful only from gcc 4.5.x onwards; earlier versions
>> > (on x86 at least) simply generate a function call relying on a library to
>> > implement it.
>> 
>> Darn. :(
> 
> Might it still be a better generic fallback than the C/cmpxchg one?
> 
> On x86 you'd get the asm version, and on ARM you need 4.5.x onwards

Is that the case even for ARM32?

> anyway, plus in general the ARM folks seem to recommend using the
> builtins more anyway.

I assume you checked that 4.5.x actually expands said builtin for
ARM (as I only checked x86)?

If the answers to both are yes, then I certainly agree.

Jan

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[Jan Beulich]

>>> On 16.04.15 at 14:03, <tim@xen.org> wrote:
> At 15:19 +0100 on 10 Apr (1428679196), David Vrabel wrote:
>> Replace the byte locks with ticket locks.  Ticket locks are: a) fair;
>> and b) peform better when contented since they spin without an atomic
>> operation.
>> 
>> The lock is split into two ticket values: head and tail.  A locker
>> acquires a ticket by (atomically) increasing tail and using the
>> previous tail value.  A CPU holds the lock if its ticket == head.  The
>> lock is released by increasing head.
>> 
>> Architectures need only provide an xadd() implementation.
> 
> I like this.  Thanks for measuring the IRQ latency too -- that's the
> most nervous-making part of the overall change. 

While in general I like ticket locks too, the IRQ latency issue still
worries me, and the promised experimental evidence that this is
not an issue won't be able to fully eliminate that reservation. As
already said in response to the v1 posting, while this likely isn't a
primary usage scenario, running Xen itself as a guest of another
hypervisor will (by analogy with what we know about Linux)
immediately be known to be hampered by this. This isn't to say
that I'm opposed to this going in, all I've been trying to point out
is that we're set for another full re-work of spin locks if such a
use case ever became more important to any user of Xen.

Jan

Re: [PATCHv2 4/6] x86: provide xadd()

[Ian Campbell]

On Thu, 2015-04-16 at 14:19 +0100, Jan Beulich wrote:
> >>> On 16.04.15 at 14:55, <ian.campbell@citrix.com> wrote:
> > On Thu, 2015-04-16 at 13:49 +0100, Tim Deegan wrote:
> >> At 12:49 +0100 on 16 Apr (1429188559), Jan Beulich wrote:
> >> > >>> On 16.04.15 at 13:25, <tim@xen.org> wrote:
> >> > > But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
> >> > > exactly this (the difference being that those are also compiler
> >> > > barriers where this is only a CPU barrier).  Should we be using it
> >> > > instead?
> >> > 
> >> > I'm afraid that's useful only from gcc 4.5.x onwards; earlier versions
> >> > (on x86 at least) simply generate a function call relying on a library to
> >> > implement it.
> >> 
> >> Darn. :(
> > 
> > Might it still be a better generic fallback than the C/cmpxchg one?
> > 
> > On x86 you'd get the asm version, and on ARM you need 4.5.x onwards
> 
> Is that the case even for ARM32?

Erm, I thought so when I wrote it but now I think again I'm not actually
so sure.

> > anyway, plus in general the ARM folks seem to recommend using the
> > builtins more anyway.
> 
> I assume you checked that 4.5.x actually expands said builtin for
> ARM (as I only checked x86)?

No, I hadn't, I should though, you are right.

Ian.

Re: [PATCHv2 4/6] x86: provide xadd()

[Ian Campbell]

On Thu, 2015-04-16 at 15:07 +0100, Ian Campbell wrote:
> On Thu, 2015-04-16 at 14:19 +0100, Jan Beulich wrote:
> > >>> On 16.04.15 at 14:55, <ian.campbell@citrix.com> wrote:
> > > On Thu, 2015-04-16 at 13:49 +0100, Tim Deegan wrote:
> > >> At 12:49 +0100 on 16 Apr (1429188559), Jan Beulich wrote:
> > >> > >>> On 16.04.15 at 13:25, <tim@xen.org> wrote:
> > >> > > But also: AFAICS the GCC builtin __sync_fetch_and_add() does almost
> > >> > > exactly this (the difference being that those are also compiler
> > >> > > barriers where this is only a CPU barrier).  Should we be using it
> > >> > > instead?
> > >> > 
> > >> > I'm afraid that's useful only from gcc 4.5.x onwards; earlier versions
> > >> > (on x86 at least) simply generate a function call relying on a library to
> > >> > implement it.
> > >> 
> > >> Darn. :(
> > > 
> > > Might it still be a better generic fallback than the C/cmpxchg one?
> > > 
> > > On x86 you'd get the asm version, and on ARM you need 4.5.x onwards
> > 
> > Is that the case even for ARM32?
> 
> Erm, I thought so when I wrote it but now I think again I'm not actually
> so sure.
> 
> > > anyway, plus in general the ARM folks seem to recommend using the
> > > builtins more anyway.
> > 
> > I assume you checked that 4.5.x actually expands said builtin for
> > ARM (as I only checked x86)?
> 
> No, I hadn't, I should though, you are right.

If nm on libgcc.a is any indication (it should be?) then it expands on
arm64 but is an out of line function on arm32, so like Tim said: Darn. 

Ian.

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[Jan Beulich]

>>> On 10.04.15 at 16:19, <david.vrabel@citrix.com> wrote:
> +#define xadd(ptr, v) generic_xaddl((ptr), (v))

I think it is at least confusing to call the thing xadd (looking to be
size generic) and then expand to generic_xaddl (only supporting
32-bit operations), yet subsequently implementing a size-generic
xadd() for x86. Plus the extra parentheses should be removed
to not needlessly obfuscate things.

Jan

Re: [PATCHv2 6/6] x86, arm: remove asm/spinlock.h from all architectures

[Jan Beulich]

>>> On 10.04.15 at 16:19, <david.vrabel@citrix.com> wrote:
> Now that all architecture use a common ticket lock implementation for
> spinlocks, remove the architecture specific byte lock implementations.
> 
> Signed-off-by: David Vrabel <david.vrabel@citrix.com>
> ---
>  xen/arch/arm/README.LinuxPrimitives  |   28 ---------------
>  xen/include/asm-arm/arm32/spinlock.h |   66 ----------------------------------
>  xen/include/asm-arm/arm64/spinlock.h |   63 --------------------------------
>  xen/include/asm-arm/spinlock.h       |   23 ------------
>  xen/include/asm-x86/spinlock.h       |   37 -------------------
>  xen/include/xen/spinlock.h           |    1 -
>  6 files changed, 218 deletions(-)

For the non-ARM bits:
Acked-by: Jan Beulich <jbeulich@suse.com>

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[Ian Campbell]

On Thu, 2015-04-16 at 16:28 +0100, Jan Beulich wrote:
> >>> On 10.04.15 at 16:19, <david.vrabel@citrix.com> wrote:
> > +#define xadd(ptr, v) generic_xaddl((ptr), (v))
> 
> I think it is at least confusing to call the thing xadd (looking to be
> size generic) and then expand to generic_xaddl (only supporting
> 32-bit operations), yet subsequently implementing a size-generic
> xadd() for x86.

Indeed, and I went to build on arm32 prior to hacking up a proper xadd
and:

spinlock.c: In function ‘_spin_lock’:
spinlock.c:145:5: error: passing argument 1 of ‘generic_xaddl’ from incompatible pointer type [-Werror]
     tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
     ^
spinlock.c:15:12: note: expected ‘volatile u32 *’ but argument is of type ‘union spinlock_tickets_t *’
 static u32 generic_xaddl(volatile u32 *ptr, u32 v)
            ^

(I hope to knock up the arm asm version in the next hour or so, so you
may not care...)

Ian.


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

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[Ian Campbell]

On Fri, 2015-04-17 at 13:32 +0100, Ian Campbell wrote:
> On Thu, 2015-04-16 at 16:28 +0100, Jan Beulich wrote:
> > >>> On 10.04.15 at 16:19, <david.vrabel@citrix.com> wrote:
> > > +#define xadd(ptr, v) generic_xaddl((ptr), (v))
> > 
> > I think it is at least confusing to call the thing xadd (looking to be
> > size generic) and then expand to generic_xaddl (only supporting
> > 32-bit operations), yet subsequently implementing a size-generic
> > xadd() for x86.
> 
> Indeed, and I went to build on arm32 prior to hacking up a proper xadd
> and:

Slightly more surprisingly I also see something similar on arm64:

spinlock.c: In function ‘_spin_lock’:
spinlock.c:145:5: error: passing argument 1 of ‘generic_xaddl’ from
incompatible pointer type [-Werror]
     tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
     ^
spinlock.c:15:12: note: expected ‘volatile u32 *’ but argument is of
type ‘union spinlock_tickets_t *’
 static u32 generic_xaddl(volatile u32 *ptr, u32 v)
            ^
> (I hope to knock up the arm asm version in the next hour or so, so you
> may not care...)

ditto.



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

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[David Vrabel]

On 17/04/15 13:32, Ian Campbell wrote:
> On Thu, 2015-04-16 at 16:28 +0100, Jan Beulich wrote:
>>>>> On 10.04.15 at 16:19, <david.vrabel@citrix.com> wrote:
>>> +#define xadd(ptr, v) generic_xaddl((ptr), (v))
>>
>> I think it is at least confusing to call the thing xadd (looking to be
>> size generic) and then expand to generic_xaddl (only supporting
>> 32-bit operations), yet subsequently implementing a size-generic
>> xadd() for x86.
> 
> Indeed, and I went to build on arm32 prior to hacking up a proper xadd
> and:
> 
> spinlock.c: In function ‘_spin_lock’:
> spinlock.c:145:5: error: passing argument 1 of ‘generic_xaddl’ from incompatible pointer type [-Werror]
>      tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
>      ^
> spinlock.c:15:12: note: expected ‘volatile u32 *’ but argument is of type ‘union spinlock_tickets_t *’
>  static u32 generic_xaddl(volatile u32 *ptr, u32 v)
>             ^
> 
> (I hope to knock up the arm asm version in the next hour or so, so you
> may not care...)

Can you use

  git://xenbits.xen.org/people/dvrabel/xen.git ticketlocks-v3

as a base instead?

David

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

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[Ian Campbell]

On Fri, 2015-04-17 at 13:34 +0100, David Vrabel wrote:
> On 17/04/15 13:32, Ian Campbell wrote:
> > On Thu, 2015-04-16 at 16:28 +0100, Jan Beulich wrote:
> >>>>> On 10.04.15 at 16:19, <david.vrabel@citrix.com> wrote:
> >>> +#define xadd(ptr, v) generic_xaddl((ptr), (v))
> >>
> >> I think it is at least confusing to call the thing xadd (looking to be
> >> size generic) and then expand to generic_xaddl (only supporting
> >> 32-bit operations), yet subsequently implementing a size-generic
> >> xadd() for x86.
> > 
> > Indeed, and I went to build on arm32 prior to hacking up a proper xadd
> > and:
> > 
> > spinlock.c: In function ‘_spin_lock’:
> > spinlock.c:145:5: error: passing argument 1 of ‘generic_xaddl’ from incompatible pointer type [-Werror]
> >      tickets.head_tail = xadd(&lock->tickets, tickets.head_tail);
> >      ^
> > spinlock.c:15:12: note: expected ‘volatile u32 *’ but argument is of type ‘union spinlock_tickets_t *’
> >  static u32 generic_xaddl(volatile u32 *ptr, u32 v)
> >             ^
> > 
> > (I hope to knock up the arm asm version in the next hour or so, so you
> > may not care...)
> 
> Can you use
> 
>   git://xenbits.xen.org/people/dvrabel/xen.git ticketlocks-v3
> 
> as a base instead?

I tried that and it built and booted just fine on both arm32 and arm64.

I eyeballed the assembly produced via the use of __sync_fetch_and_add
(for _spin_lock only) and it is exactly what I would have written in my
own versions.

I was using gcc 4.8.3 in both cases. For arm64 I'm pretty sure we don't
want to consider anything earlier.

For arm32 I have also tried gcc 4.6.3 (Debian Wheezy's compiler) and it
built and booted, and eyeballing shows the same asm. I think that's the
earliest we really need to worry about.

IOW I'm not going to bother with custom versions of these functions on
ARM. If you wanted you could drop the #ifndef xadd from
asm-arm/system.h.

Perhaps it would be useful to add some of the info from my tests
reported above, or a reference to this mail, to the commit log?

in either case you can add:

        Acked-by: Ian Campbell <ian.campbell@citrix.com>

to the patch below. 

commit b08cf3fa4791d7ff0d01fb932192e02078ce670a
Author: David Vrabel <david.vrabel@citrix.com>
Date:   Thu Apr 16 15:31:18 2015 +0100

    arm: provide xadd()
    
    xadd() atomically adds a value and returns the previous value.  This
    is needed to implement ticket locks.
    
    This generic arm implementation uses the GCC __sync_fetch_and_add()
    builtin, but a arm32 or arm64 specific variant could be provided in the
    future (e.g., if required to support older versions of GCC).
    
    Signed-off-by: David Vrabel <david.vrabel@citrix.com>

diff --git a/xen/include/asm-arm/system.h b/xen/include/asm-arm/system.h
index ce3d38a..f037e84 100644
--- a/xen/include/asm-arm/system.h
+++ b/xen/include/asm-arm/system.h
@@ -51,6 +51,10 @@
 # error "unknown ARM variant"
 #endif
 
+#ifndef xadd
+#  define xadd(x, v) __sync_fetch_and_add(x, v)
+#endif
+
 extern struct vcpu *__context_switch(struct vcpu *prev, struct vcpu *next);
 
 #endif

Ian.



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

Re: [PATCHv2 3/6] xen: generic xadd() for ticket locks

[David Vrabel]

On 17/04/15 14:09, Ian Campbell wrote:
> On Fri, 2015-04-17 at 13:34 +0100, David Vrabel wrote:
>>
>> Can you use
>>
>>   git://xenbits.xen.org/people/dvrabel/xen.git ticketlocks-v3

git://xenbits.xen.org/people/dvrabel/xen.git ticketlock-v3

> I tried that and it built and booted just fine on both arm32 and arm64.
> 
> I eyeballed the assembly produced via the use of __sync_fetch_and_add
> (for _spin_lock only) and it is exactly what I would have written in my
> own versions.
> 
> I was using gcc 4.8.3 in both cases. For arm64 I'm pretty sure we don't
> want to consider anything earlier.
> 
> For arm32 I have also tried gcc 4.6.3 (Debian Wheezy's compiler) and it
> built and booted, and eyeballing shows the same asm. I think that's the
> earliest we really need to worry about.
> 
> IOW I'm not going to bother with custom versions of these functions on
> ARM. If you wanted you could drop the #ifndef xadd from
> asm-arm/system.h.
> 
> Perhaps it would be useful to add some of the info from my tests
> reported above, or a reference to this mail, to the commit log?
> 
> in either case you can add:
> 
>         Acked-by: Ian Campbell <ian.campbell@citrix.com>

Thanks, Ian!

David

Re: [PATCHv2 5/6] xen: use ticket locks for spin locks

[David Vrabel]

On 16/04/15 13:03, Tim Deegan wrote:
> 
>> +static int __spin_is_locked(spinlock_t *lock)
>> +{
>> +    return lock->tickets.head != lock->tickets.tail;
>> +}
> 
> Maybe atomic_read the lock and do the comparison on the local value?
> Just from an abundance of caution - can't think of an obvious reason
> why this race should matter.

I think it would be preferable to avoid giving the impression that
avoiding this race is important so I've left this as is (FWIW, the Linux
implementation is like this).

David