|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Xen-devel] [PATCHv2 5/6] xen: use ticket locks for spin locks
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@xxxxxxxxxx>
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;
_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |