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

[Tim Deegan <tim@xxxxxxx>]

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.

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