[PATCH] spinlocks: Replace test-and-set locks by ticket locks
Guo Ren
guoren at kernel.org
Mon Apr 5 07:52:36 BST 2021
On Mon, Apr 5, 2021 at 2:03 PM Anup Patel <Anup.Patel at wdc.com> wrote:
>
>
>
> > -----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.
All riscv amo instructions will write to the target address
unconditionally and there is no cas instruction in riscv A-extension.
So "lr/sc" is the only way for riscv to implement trylock.
look the codes below:
static inline int arch_spin_trylock(arch_spinlock_t *lock)
{
u32 tmp, contended, res;
do {
asm volatile (
" lr.w %0, %3 \n"
__ASM_SRLIW "%1, %0, %5 \n"
__ASM_SLLIW "%2, %0, %5 \n"
" or %1, %2, %1 \n"
" li %2, 0 \n"
" sub %1, %1, %0 \n"
" bnez %1, 1f \n"
" addw %0, %0, %4 \n"
" sc.w %2, %0, %3 \n"
"1: \n"
: "=&r" (tmp), "=&r" (contended), "=&r" (res),
"+A" (lock->lock)
: "r" (1 << TICKET_NEXT), "I" (TICKET_NEXT)
: "memory");
} while (res);
if (!contended)
__atomic_acquire_fence();
return !contended;
}
When lock is up, trylock'll fail and the instructions progress is:
" lr.w %0, %3 \n"
" srliw "%1, %0, %5 \n"
" slliw "%2, %0, %5 \n"
" or %1, %2, %1 \n"
" li %2, 0 \n"
" sub %1, %1, %0 \n"
" bnez %1, 1f \n"
"1:"
return !contented;
1 lr.w + 5 ALUs + branch = 7 instructions
The most inconvenient about RISC-V is that there is no rotate shift
instruction, I must use more instructions and registers to implement
compare operation for the owner:next-ticket.
>
> >
> > > 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
--
Best Regards
Guo Ren
ML: https://lore.kernel.org/linux-csky/
More information about the opensbi
mailing list