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

[Andrew Cooper <andrew.cooper3@citrix.com>]

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;