[PATCH] spinlocks: Replace test-and-set locks by ticket locks
Anup Patel
Anup.Patel at wdc.com
Mon Apr 5 07:03:20 BST 2021
> -----Original Message-----
> From: Guo Ren <guoren at kernel.org>
> Sent: 05 April 2021 11:09
> To: Anup Patel <Anup.Patel at wdc.com>
> Cc: Christoph Muellner <cmuellner at linux.com>; opensbi at lists.infradead.org
> Subject: Re: [PATCH] spinlocks: Replace test-and-set locks by ticket locks
>
> 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 at kernel.org/T/#u
It's generally easier to think in-terms of LR/SC on any architecture but the
AMO instructions always scale better in-terms of HW implementation.
>
> 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 :)
I was going to comment in LKML after we had it working here but it's good
that you already noticed it.
I did not think much about spin_trylock() using atomic instructions but it
will be nice if you can attempt that as well in your Linux patches.
>
> > 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/
Regards,
Anup
More information about the opensbi
mailing list