Re: [Xen-devel] [PATCHv4 3/5] xen: use ticket locks for spin locks

[Tim Deegan <tim@xxxxxxx>]

At 15:37 +0100 on 11 May (1431358623), 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.
> 
> 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.
> 
> Architectures need only provide arch_fetch_and_add() and two barriers:
> arch_lock_acquire_barrier() and arch_lock_release_barrier().
> 
> Signed-off-by: David Vrabel <david.vrabel@xxxxxxxxxx>

Looking good.  I have two nits about comments, and one bug, which I
missed in the last version:

>  int _spin_trylock(spinlock_t *lock)
>  {
> +    spinlock_tickets_t old, new;
> +
>      check_lock(&lock->debug);
> -    if ( !_raw_spin_trylock(&lock->raw) )
> +    old = observe_lock(&lock->tickets);
> +    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 )
> +    {
> +        /*
> +         * cmpxchg() is a full barrier so no need for an
> +         * arch_lock_acquire_barrier().
> +         */

This comment belongs in the other branch, where we have taken the lock.

> +        return 0;
> +    }
>  #ifdef LOCK_PROFILE
>      if (lock->profile)
>          lock->profile->time_locked = NOW();
> @@ -213,27 +219,32 @@ int _spin_trylock(spinlock_t *lock)
>  
>  void _spin_barrier(spinlock_t *lock)
>  {
> +    spinlock_tickets_t sample;
>  #ifdef LOCK_PROFILE
>      s_time_t block = NOW();
> -    u64      loop = 0;
> +#endif
>  
>      check_barrier(&lock->debug);
> -    do { smp_mb(); loop++;} while ( _raw_spin_is_locked(&lock->raw) );
> -    if ((loop > 1) && lock->profile)
> +    smp_mb();
> +    sample = observe_lock(&lock->tickets);
> +    if ( sample.head != sample.tail )
>      {
> -        lock->profile->time_block += NOW() - block;
> -        lock->profile->block_cnt++;
> -    }
> -#else
> -    check_barrier(&lock->debug);
> -    do { smp_mb(); } while ( _raw_spin_is_locked(&lock->raw) );
> +        while ( observe_head(&lock->tickets) != sample.tail )

This test should be "observe_head(&lock->tickets) == sample.head",
i.e. wait until the thread that held the lock has released it.
Checking for it to reach the tail is unnecessary (other threads that
were queueing for the lock at the sample time don't matter) and
dangerous (on a contended lock head might pass sample.tail without us
happening to observe it being == ).

> +            cpu_relax();
> +#ifdef LOCK_PROFILE
> +        if ( lock->profile )
> +        {
> +            lock->profile->time_block += NOW() - block;
> +            lock->profile->block_cnt++;
> +        }
>  #endif
> +    }
>      smp_mb();
>  }
[...]
> --- a/xen/include/asm-x86/system.h
> +++ b/xen/include/asm-x86/system.h
> @@ -185,6 +185,9 @@ static always_inline unsigned long __xadd(
>  #define set_mb(var, value) do { xchg(&var, value); } while (0)
>  #define set_wmb(var, value) do { var = value; wmb(); } while (0)
>  
> +#define arch_lock_acquire_barrier() barrier()
> +#define arch_lock_release_barrier() barrier()

This could do with a comment explaining why they're not smp_mb().

Summarizing the last thread: on x86 the only reordering is of reads
with older writes.  In the lock case, the read in observe_head() can
only be reordered with writes that precede it, and moving a write
_into_ a locked section is OK.  In the release case, the write in
add_sized() can only be reordered with reads that follow it, and
hoisting a read _into_ a locked region is OK.

Cheers,

Tim.

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