[PATCH] spinlocks: Replace test-and-set locks by ticket locks
Xiang W
wxjstz at 126.com
Sun Apr 4 07:54:26 BST 2021
在 2021-04-04日的 06:04 +0000，Anup Patel写道：
> > -----Original Message-----
> > From: Christoph Muellner <cmuellner at linux.com>
> > Sent: 03 April 2021 21:53
> > To: opensbi at lists.infradead.org; Anup Patel <Anup.Patel at wdc.com>
> > Cc: Christoph Muellner <cmuellner at linux.com>
> > Subject: [PATCH] spinlocks: Replace test-and-set locks by ticket
> > locks
> >
> > Test-and-set locks don't provide fairness and are non-deterministic
> > (w.r.t.
> > the prediction of the future holder of a lock).
> > This can be a performance problem in case of lock contention.
> >
> > Let's change the implementation to use ticket locks, which
> > guarantee a fair
> > locking order (FIFO ordering).
> >
> > Ticket locks have two counters 'owner' and 'next'.
> > The counter 'owner' holds the ticket number of the current lock
> > owner.
> > The counter 'next' holds the latest free ticket number.
> >
> > The lock is free if both counters are equal. To acquire the lock,
> > the 'next'
> > counter is atomically incremented to obtain a new ticket.
> > The counter 'owner' is then polled until it becomes equal to the
> > new ticket.
> > To release a lock, one atomically increments the 'owner'
> > counter.
> >
> > The implementation uses a 32-bit wide struct, which consists of two
> > 16-bit
> > counters (owner and next). This is inspired by similar spinlock
> > implementations on other architectures.
> >
> > Note, that RISC-V lacks sub-word atomics, therefore we need to
> > circumvent
> > this limitation with additional instructions.
> > This implementation aims to reduce the instructions between the
> > LR/SC pairs
> > to minimize the chances of failing SCs. The cost of this approach
> > is, that we
> > spill more registers than necessary.
>
> The spin_trylock() can be tricky to implement with ticket approach.
> Since the
> spin_trylock() is currently not used anywhere in OpenSBI, I suggest:
>
> 1) We can drop the spin_trylock() API as separate patch
> 2) Implement classic ticket spinlock approach as described in
> Wikipedia
> using AMOADD instructions and barriers.
> 3) We don't need to pack next_ticket and owner into one word because
> these can be separate "unsigned long" in spinlock_t. I believe
> that
Under RV32 long is 4 bytes, and under RV64 long is 8 bytes. Different
instructions will be used for atomic operations, so I recommend using
u32
Regards,
Xiang W
> this packing only helps in implementing spin_trylock(), Right ??
>
> Regards,
> Anup
>
> > Signed-off-by: Christoph Muellner <cmuellner at linux.com>
> > ---
> > include/sbi/riscv_locks.h | 33 ++++++++++++-------
> > lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++----
> > ------
> > 2 files changed, 72 insertions(+), 28 deletions(-)
> >
> > diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h
> > index
> > faa9676..59e6af9 100644
> > --- a/include/sbi/riscv_locks.h
> > +++ b/include/sbi/riscv_locks.h
> > @@ -2,26 +2,37 @@
> > * SPDX-License-Identifier: BSD-2-Clause
> > *
> > * Copyright (c) 2019 Western Digital Corporation or its
> > affiliates.
> > - *
> > - * Authors:
> > - * Anup Patel <anup.patel at wdc.com>
> > + * Copyright (c) 2021 Christoph Müllner <cmuellner at linux.com>
> > */
> >
> > #ifndef __RISCV_LOCKS_H__
> > #define __RISCV_LOCKS_H__
> >
> > +#include <sbi/sbi_types.h>
> > +
> > +#define TICKET_SHIFT 16
> > +
> > typedef struct {
> > - volatile long lock;
> > -} spinlock_t;
> > +#ifdef __BIG_ENDIAN
> > + u16 next;
> > + u16 owner;
> > +#else
> > + u16 owner;
> > + u16 next;
> > +#endif
> > +} __aligned(4) spinlock_t;
> > +
> > +#define __SPIN_LOCK_UNLOCKED \
> > + (spinlock_t) { 0, 0 }
> >
> > -#define __RISCV_SPIN_UNLOCKED 0
> > +#define SPIN_LOCK_INIT(x) \
> > + x = __SPIN_LOCK_UNLOCKED
> >
> > -#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
> > +#define SPIN_LOCK_INITIALIZER \
> > + __SPIN_LOCK_UNLOCKED
> >
> > -#define SPIN_LOCK_INITIALIZER \
> > - { \
> > - .lock = __RISCV_SPIN_UNLOCKED, \
> > - }
> > +#define DEFINE_SPIN_LOCK(x) \
> > + spinlock_t SPIN_LOCK_INIT(x)
> >
> > int spin_lock_check(spinlock_t *lock);
> >
> > diff --git a/lib/sbi/riscv_locks.c b/lib/sbi/riscv_locks.c index
> > 4d1d9c0..7d86742
> > 100644
> > --- a/lib/sbi/riscv_locks.c
> > +++ b/lib/sbi/riscv_locks.c
> > @@ -2,44 +2,77 @@
> > * SPDX-License-Identifier: BSD-2-Clause
> > *
> > * Copyright (c) 2019 Western Digital Corporation or its
> > affiliates.
> > - *
> > - * Authors:
> > - * Anup Patel <anup.patel at wdc.com>
> > + * Copyright (c) 2021 Christoph Müllner <cmuellner at linux.com>
> > */
> >
> > #include <sbi/riscv_barrier.h>
> > #include <sbi/riscv_locks.h>
> >
> > -int spin_lock_check(spinlock_t *lock)
> > +static inline int spin_lock_unlocked(spinlock_t lock)
> > {
> > - return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1;
> > + return lock.owner == lock.next; }
> > +
> > +bool spin_lock_check(spinlock_t *lock)
> > +{
> > + RISCV_FENCE(r, rw);
> > + return !spin_lock_unlocked(*lock);
> > }
> >
> > int spin_trylock(spinlock_t *lock)
> > {
> > - int tmp = 1, busy;
> > + u32 inc = 1u << TICKET_SHIFT;
> > + u32 mask = 0xffffu << TICKET_SHIFT;
> > + u32 l0, tmp1, tmp2;
> >
> > __asm__ __volatile__(
> > - " amoswap.w %0, %2, %1\n"
> > RISCV_ACQUIRE_BARRIER
> > - : "=r"(busy), "+A"(lock->lock)
> > - : "r"(tmp)
> > + /* Get the current lock counters. */
> > + "1: lr.w.aq %0, %3\n"
> > + " slliw %2, %0, %6\n"
> > + " and %1, %0, %5\n"
> > + /* Is the lock free right now? */
> > + " bne %1, %2, 2f\n"
> > + " addw %0, %0, %4\n"
> > + /* Acquire the lock. */
> > + " sc.w.rl %0, %0, %3\n"
> > + " bnez %0, 1b\n"
> > + "2:"
> > + : "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
> > + : "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
> > : "memory");
> >
> > - return !busy;
> > + return !l0;
> > }
> >
> > void spin_lock(spinlock_t *lock)
> > {
> > - while (1) {
> > - if (spin_lock_check(lock))
> > - continue;
> > + u32 inc = 1u << TICKET_SHIFT;
> > + u32 mask = 0xffffu << TICKET_SHIFT;
> > + u32 l0, tmp1, tmp2;
> >
> > - if (spin_trylock(lock))
> > - break;
> > - }
> > + __asm__ __volatile__(
> > + /* Atomically increment the next ticket. */
> > + "0: lr.w.aq %0, %3\n"
> > + " addw %0, %0, %4\n"
> > + " sc.w.rl %0, %0, %3\n"
> > + " bnez %0, 0b\n"
> > +
> > + /* Did we get the lock? */
> > + "1: slliw %2, %0, %6\n"
> > + " and %1, %0, %5\n"
> > + " beq %1, %2, 2f\n"
> > +
> > + /* No, let's spin on the lock. */
> > + " lr.w.aq %0, %3\n"
> > + " j 1b\n"
> > + "2:"
> > + : "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
> > + : "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
> > + : "memory");
> > }
> >
> > void spin_unlock(spinlock_t *lock)
> > {
> > - __smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED);
> > + __smp_store_release(&lock->owner, lock->owner + 1);
> > }
> > +
> > --
> > 2.30.2
More information about the opensbi
mailing list