[PATCH] spinlocks: Replace test-and-set locks by ticket locks
Guo Ren
guoren at kernel.org
Mon Apr 5 06:39:29 BST 2021
On Sun, Apr 4, 2021 at 2:05 PM Anup Patel <Anup.Patel at wdc.com> wrote:
>
>
>
> > -----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.
Do you prefer AMOADD? I think it's a better idea (csky only has
lr.w/sc.w, so it's my habit :P), I will update the Linux ticket-lock
patch:
https://lore.kernel.org/linux-riscv/1617201040-83905-4-git-send-email-guoren@kernel.org/T/#u
with:
diff --git a/arch/riscv/include/asm/spinlock.h
b/arch/riscv/include/asm/spinlock.h
index 90b7eaa950cf..435286ad342b 100644
--- a/arch/riscv/include/asm/spinlock.h
+++ b/arch/riscv/include/asm/spinlock.h
@@ -22,15 +22,10 @@
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
arch_spinlock_t lockval;
- u32 tmp;
asm volatile (
- "1: lr.w %0, %2 \n"
- " mv %1, %0 \n"
- " addw %0, %0, %3 \n"
- " sc.w %0, %0, %2 \n"
- " bnez %0, 1b \n"
- : "=&r" (tmp), "=&r" (lockval), "+A" (lock->lock)
+ " amoadd.w %0, %2, %1 \n"
+ : "=&r" (lockval), "+A" (lock->lock)
: "r" (1 << TICKET_NEXT)
: "memory");
Thx for the tip :)
> 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
> 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
>
> --
> opensbi mailing list
> opensbi at lists.infradead.org
> http://lists.infradead.org/mailman/listinfo/opensbi
--
Best Regards
Guo Ren
ML: https://lore.kernel.org/linux-csky/
More information about the opensbi
mailing list