spinlocks: Replace test-and-set locks by ticket locks
v3 cover spinlocks: Replace test-and-set locks by ticket locks
This patch series replaces the test-and-set spinlock implementation of OpenSBI with 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 (e.g. consumers continuously steal the lock from a single producer).
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 (fetch-and-inc) 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.
This patchset has been tested on RV64 and RV32 against self-written unit tests (to ensure the 16-bit overflow is correct) and against the Linux kernel (by exchanging the kernel's spinlock implementation with the one from this patchset).
Note, that RISC-V lacks sub-word atomics, therefore we need to circumvent this limitation with additional instructions.
v3:
* Replace LR/SC sequence by AMOADD in spin_lock()
* Add cover letter
v2:
* Fixing RV32 support
* Address comments from Jessica
Christoph Muellner (3):
include: types: Add __aligned(x) to define the minimum alignement
spinlocks: Allow direct initialization via SPIN_LOCK_INIT()
spinlocks: Replace test-and-set locks by ticket locks
include/sbi/riscv_locks.h | 33 ++++++++++++------- include/sbi/sbi_types.h | 1 + lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++---------- lib/sbi/sbi_fifo.c | 2 +- 4 files changed, 74 insertions(+), 29 deletions(-)
Signature · 1 line
2.30.2
PATCH v3 1/3 include: types: Add __aligned(x) to define the minimum alignement
The __aligned(x) macro is a common wrapper around compiler's aligned attribute, which allow to define the minimum alignement of a data type. Let's add this macro.
--- include/sbi/sbi_types.h | 1 + 1 file changed, 1 insertion(+)
include/sbi/sbi_types.h +1 -0
@@ -63,6 +63,7 @@ typedef unsigned long physical_size_t;#define __packed __attribute__((packed))#define __noreturn __attribute__((noreturn)) +#define __aligned (x) __attribute__((aligned(x)))#define likely (x) __builtin_expect((x), 1)#define unlikely (x) __builtin_expect((x), 0)
Signature · 1 line
2.30.2
PATCH v3 1/3 include: types: Add __aligned(x) to define the minimum alignement
Quoted 12 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 1/3] include: types: Add__aligned(x)to define the minimum alignement
Quoted 5 lines
The
__aligned(x)macro is a common wrapper around compiler's aligned attribute, which allow to define the minimum alignement of a data type. Let's add this macro.Signed-off-by Christoph Muellner <[email protected]>
Looks good to me.
Thanks,
Anup
Quoted 18 lines
--- include/sbi/sbi_types.h | 1 + 1 file changed, 1 insertion(+)include/sbi/sbi_types.h index renamed from include/sbi/sbi_types.h +0
-00952d5c..38e3565 100644
include/sbi/sbi_types.h +1
-1@@ -63,6 +63,7 @@ typedef unsigned long physical_size_t;#define __packed __attribute__((packed))#define __noreturn __attribute__((noreturn)) +#define __aligned (x) __attribute__((aligned(x)))#define likely (x) __builtin_expect((x), 1) #define unlikely(x)__builtin_expect ((x),0 ) --2.30.2
Anup Patel
AppliedPATCH v3 1/3 include: types: Add __aligned(x) to define the minimum alignement
Quoted 27 lines
-----Original Message-----
From: Anup Patel
Sent: 06 April 2021 10:36
To: Christoph Muellner <[email protected]>;
opensbi at lists.infradead.org; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Subject: RE: [PATCH v3 1/3] include: types: Add__aligned(x)to define the minimum alignementQuoted 14 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 1/3] include: types: Add__aligned(x)to define the minimum alignementThe
__aligned(x)macro is a common wrapper around compiler's aligned attribute, which allow to define the minimum alignement of a data type. Let's add this macro.
Quoted 5 lines
Quoted 1 line
Signed-off-by Christoph Muellner <[email protected]>Looks good to me.
Reviewed-by Anup Patel <[email protected]>
Applied this patch to the riscv/opensbi repo
Regards,
Anup
Quoted 22 lines
Thanks,
AnupQuoted 18 lines
--- include/sbi/sbi_types.h | 1 + 1 file changed, 1 insertion(+)include/sbi/sbi_types.h index renamed from include/sbi/sbi_types.h +0
-00952d5c..38e3565 100644
include/sbi/sbi_types.h +1
-1@@ -63,6 +63,7 @@ typedef unsigned long physical_size_t;#define __packed __attribute__((packed))#define __noreturn __attribute__((noreturn)) +#define __aligned (x) __attribute__((aligned(x)))#define likely (x) __builtin_expect((x), 1) #define unlikely(x)__builtin_expect ((x),0 ) --2.30.2
PATCH v3 2/3 spinlocks: Allow direct initialization via SPIN_LOCK_INIT()
In reply to Christoph MuellnerThe current implementation of SPIN_LOCK_INIT() provides the spinlock to be initialized as reference. This does not allow a direct initialization of the spinlock object at the creation site.
Let's pass the spinlock directly instead (like Linux does as well) and adjust all users of the macro (in fact there is only one user).
--- include/sbi/riscv_locks.h | 2 +- lib/sbi/sbi_fifo.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)
include/sbi/riscv_locks.h +1 -1
@@ -16,7 +16,7 @@ typedef struct {#define __RISCV_SPIN_UNLOCKED 0 -#define SPIN_LOCK_INIT (_lptr) (_lptr)->lock = __RISCV_SPIN_UNLOCKED +#define SPIN_LOCK_INIT (x) (x).lock = __RISCV_SPIN_UNLOCKED#define SPIN_LOCK_INITIALIZER \ { \
lib/sbi/sbi_fifo.c +1 -1
@@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void *queue_mem, u16 entries, fifo->queue = queue_mem; fifo->num_entries = entries; fifo->entry_size = entry_size; -SPIN_LOCK_INIT (&fifo->qlock); +SPIN_LOCK_INIT (fifo->qlock); fifo->avail = fifo->tail =0 ;sbi_memset (fifo->queue,0 , (size_t )entries * entry_size); }
Signature · 1 line
2.30.2
PATCH v3 2/3 spinlocks: Allow direct initialization via SPIN_LOCK_INIT()
Quoted 12 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 2/3] spinlocks: Allow direct initialization viaSPIN_LOCK_INIT()
Quoted 8 lines
The current implementation of
SPIN_LOCK_INIT()provides the spinlock to be initialized as reference. This does not allow a direct initialization of the spinlock object at the creation site.Let's pass the spinlock directly instead (like Linux does as well) and adjust all users of the macro (in fact there is only one user).
Signed-off-by Christoph Muellner <[email protected]>
Looks good to me.
Thanks,
Anup
Quoted 33 lines
--- include/sbi/riscv_locks.h | 2 +- lib/sbi/sbi_fifo.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)include/sbi/riscv_locks.h index renamed from include/sbi/riscv_locks.h +0
-055da7c0..faa9676 100644
include/sbi/riscv_locks.h +1
-1@@ -16,7 +16,7 @@ typedef struct {#define __RISCV_SPIN_UNLOCKED 0 -#define SPIN_LOCK_INIT (_lptr) (_lptr)->lock = __RISCV_SPIN_UNLOCKED +#define SPIN_LOCK_INIT (x) (x).lock = __RISCV_SPIN_UNLOCKED#define SPIN_LOCK_INITIALIZER \ { \lib/sbi/sbi_fifo.c index 8d1dbf0..2a5c012 renamed from lib/sbi/sbi_fifo.c +0
-0100644
lib/sbi/sbi_fifo.c +1
-2@@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void *queue_mem, u16 entries, fifo->queue = queue_mem; fifo->num_entries = entries; fifo->entry_size = entry_size; -SPIN_LOCK_INIT (&fifo->qlock); +SPIN_LOCK_INIT (fifo->qlock); fifo->avail = fifo->tail =0 ;sbi_memset (fifo->queue,0 , (size_t )entries * entry_size); } --2.30.2
Anup Patel
AppliedPATCH v3 2/3 spinlocks: Allow direct initialization via SPIN_LOCK_INIT()
Quoted 27 lines
-----Original Message-----
From: Anup Patel
Sent: 06 April 2021 10:37
To: Christoph Muellner <[email protected]>;
opensbi at lists.infradead.org; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Subject: RE: [PATCH v3 2/3] spinlocks: Allow direct initialization viaSPIN_LOCK_INIT()Quoted 14 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 2/3] spinlocks: Allow direct initialization viaSPIN_LOCK_INIT()The current implementation of
SPIN_LOCK_INIT()provides the spinlock to be initialized as reference. This does not allow a direct initialization of the spinlock object at the creation site.
Quoted 8 lines
Quoted 4 lines
Let's pass the spinlock directly instead (like Linux does as well) and adjust all users of the macro (in fact there is only one user).
Signed-off-by Christoph Muellner <[email protected]>Looks good to me.
Reviewed-by Anup Patel <[email protected]>
Replaced patch subject prefix "spinlocks:" with "lib: sbi:"
Applied this patch to the riscv/opensbi repo
Regards,
Anup
Quoted 39 lines
Thanks,
AnupQuoted 35 lines
--- include/sbi/riscv_locks.h | 2 +- lib/sbi/sbi_fifo.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)include/sbi/riscv_locks.h +0
-0index
55da7c0..faa9676 100644include/sbi/riscv_locks.h +1
-1@@ -16,7 +16,7 @@ typedef struct {#define __RISCV_SPIN_UNLOCKED 0 -#define SPIN_LOCK_INIT (_lptr) (_lptr)->lock = __RISCV_SPIN_UNLOCKED +#define SPIN_LOCK_INIT (x) (x).lock = __RISCV_SPIN_UNLOCKED#define SPIN_LOCK_INITIALIZER \ { \lib/sbi/sbi_fifo.c index renamed from lib/sbi/sbi_fifo.c +0
-08d1dbf0..2a5c012
100644lib/sbi/sbi_fifo.c +1
-2@@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void *queue_mem, u16 entries, fifo->queue = queue_mem; fifo->num_entries = entries; fifo->entry_size = entry_size; -SPIN_LOCK_INIT (&fifo->qlock); +SPIN_LOCK_INIT (fifo->qlock); fifo->avail = fifo->tail =0 ;sbi_memset (fifo->queue,0 , (size_t )entries * entry_size); } --2.30.2
PATCH v3 3/3 spinlocks: Replace test-and-set locks by ticket locks
In reply to Christoph MuellnerReplace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).
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.
This allows that the code works for both, RV32 and RV64.
--- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++---------- 2 files changed, 72 insertions(+), 28 deletions(-)
include/sbi/riscv_locks.h +22 -11
@@ -2,26 +2,37 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #ifndef __RISCV_LOCKS_H__#define __RISCV_LOCKS_H__ +#include <sbi/sbi_types.h> + +#define TICKET_SHIFT 16 +typedef struct { -volatile long lock; -}spinlock_t ; +#if __BYTE_ORDER__ == __ORDER_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);
lib/sbi/riscv_locks.c +50 -17
94 lines not on this page · raw message
Signature · 1 line
2.30.2
PATCH v3 3/3 spinlocks: Replace test-and-set locks by ticket locks
? 2021-04-06?? 03:53 +0200?Christoph Muellner???
Quoted 139 lines
Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).
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.
This allows that the code works for both, RV32 and RV64.Signed-off-by Christoph Muellner <[email protected]>--- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++------ ---- 2 files changed, 72 insertions(+), 28 deletions(-)include/sbi/riscv_locks.h +22
-11@@ -2,26 +2,37 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #ifndef __RISCV_LOCKS_H__#define __RISCV_LOCKS_H__ +#include <sbi/sbi_types.h> + +#define TICKET_SHIFT 16 +typedef struct { -volatile long lock; -}spinlock_t ; +#if __BYTE_ORDER__ == __ORDER_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);lib/sbi/riscv_locks.c +30
-14@@ -2,44 +2,77 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #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; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long 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" +" slli %2, %0, %6\n" +" and %2, %2, %5\n" +" and %1, %0, %5\n" +/* Is the lock free right now? */ +" bne %1, %2, 2f\n" +" add %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 ; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long mask =0xffffu ; +u32 l0, tmp1, tmp2; -if (spin_trylock (lock))
lib/sbi/riscv_locks.c line 61
Quoted 10 lines
lib/sbi/riscv_locks.c +8
-2-break ; - } + __asm__ __volatile__( +/* Atomically increment the next ticket. */ +" amoadd.w.aqrl %0, %4, %3\n" + +/* Did we get the lock? */ +" srli %1, %0, %6\n" +" and %1, %1, %5\n" + "1: and %2, %0, %5\n"
What we need to keep re-reading should be 'owner'
Regards,
Xiang W
Quoted 22 lines
lib/sbi/riscv_locks.c +12
-1+" beq %1, %2, 2f\n" + +/* If not, then spin on the lock. */ +" lw %0, %3\n" +RISCV_ACQUIRE_BARRIER +" 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 ); } +Signature · 1 line
2.30.2
PATCH v3 3/3 spinlocks: Replace test-and-set locks by ticket locks
Quoted 140 lines · Xiang W
? 2021-04-06?? 03:53 +0200?Christoph Muellner???
Quoted 138 lines
Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).
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.
This allows that the code works for both, RV32 and RV64.Signed-off-by Christoph Muellner <[email protected]>--- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++------ ---- 2 files changed, 72 insertions(+), 28 deletions(-)include/sbi/riscv_locks.h +22
-11@@ -2,26 +2,37 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #ifndef __RISCV_LOCKS_H__#define __RISCV_LOCKS_H__ +#include <sbi/sbi_types.h> + +#define TICKET_SHIFT 16 +typedef struct { -volatile long lock; -}spinlock_t ; +#if __BYTE_ORDER__ == __ORDER_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);lib/sbi/riscv_locks.c +30
-13@@ -2,44 +2,77 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #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; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long 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" +" slli %2, %0, %6\n" +" and %2, %2, %5\n" +" and %1, %0, %5\n" +/* Is the lock free right now? */ +" bne %1, %2, 2f\n" +" add %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 ; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long mask =0xffffu ; +u32 l0, tmp1, tmp2;
Quoted 12 lines
lib/sbi/riscv_locks.c line 61
Quoted 11 lines
lib/sbi/riscv_locks.c +8
-3-if (spin_trylock (lock)) -break ; - } + __asm__ __volatile__( +/* Atomically increment the next ticket. */ +" amoadd.w.aqrl %0, %4, %3\n" + +/* Did we get the lock? */ +" srli %1, %0, %6\n" +" and %1, %1, %5\n" + "1: and %2, %0, %5\n"What we need to keep re-reading should be 'owner'
Yes, the code is already doing that.
The "owner" is lower 16bits so "and %2, %0, %5\n" will
extract "owner" in %2. The %1 already has assigned ticket number.
Regards,
Anup
PATCH v3 3/3 spinlocks: Replace test-and-set locks by ticket locks
In reply to Christoph MuellnerQuoted 14 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 3/3] spinlocks: Replace test-and-set locks by ticket locksReplace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).
Quoted 6 lines
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.
This allows that the code works for both, RV32 and RV64.Signed-off-by Christoph Muellner <[email protected]>
Looks good to me.
Thanks,
Anup
Quoted 159 lines
--- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++---------- 2 files changed, 72 insertions(+), 28 deletions(-)include/sbi/riscv_locks.h index renamed from include/sbi/riscv_locks.h +0
-0faa9676..492935f 100644
include/sbi/riscv_locks.h +22
-11@@ -2,26 +2,37 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #ifndef __RISCV_LOCKS_H__#define __RISCV_LOCKS_H__ +#include <sbi/sbi_types.h> + +#define TICKET_SHIFT 16 +typedef struct { -volatile long lock; -}spinlock_t ; +#if __BYTE_ORDER__ == __ORDER_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);lib/sbi/riscv_locks.c index 4d1d9c0..7e607b0 renamed from lib/sbi/riscv_locks.c +0
-0100644
lib/sbi/riscv_locks.c +11
-7@@ -2,44 +2,77 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #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; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long mask =0xffffu <<TICKET_SHIFT ; +u32 l0, tmp1, tmp2; __asm__ __volatile__( - " amoswap.w %0, %2, %1\n"
RISCV_ACQUIRE_BARRIERlib/sbi/riscv_locks.c +38
-11- : "=r"(busy), "+A"(lock->lock) - : "r"(tmp) +/* Get the current lock counters. */ +"1: lr.w.aq %0, %3\n" +" slli %2, %0, %6\n" +" and %2, %2, %5\n" +" and %1, %0, %5\n" +/* Is the lock free right now? */ +" bne %1, %2, 2f\n" +" add %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 ; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long mask =0xffffu ; +u32 l0, tmp1, tmp2; -if (spin_trylock (lock)) -break ; - } + __asm__ __volatile__( +/* Atomically increment the next ticket. */ +" amoadd.w.aqrl %0, %4, %3\n" + +/* Did we get the lock? */ +" srli %1, %0, %6\n" +" and %1, %1, %5\n" +"1: and %2, %0, %5\n" +" beq %1, %2, 2f\n" + +/* If not, then spin on the lock. */ +" lw %0, %3\n" +RISCV_ACQUIRE_BARRIER +" 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
PATCH v3 3/3 spinlocks: Replace test-and-set locks by ticket locks
In reply to Christoph Muellner? 2021-04-06?? 03:53 +0200?Christoph Muellner???
Quoted 157 lines
Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).
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.
This allows that the code works for both, RV32 and RV64.Signed-off-by Christoph Muellner <[email protected]>--- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++------ ---- 2 files changed, 72 insertions(+), 28 deletions(-)include/sbi/riscv_locks.h +22
-11@@ -2,26 +2,37 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #ifndef __RISCV_LOCKS_H__#define __RISCV_LOCKS_H__ +#include <sbi/sbi_types.h> + +#define TICKET_SHIFT 16 +typedef struct { -volatile long lock; -}spinlock_t ; +#if __BYTE_ORDER__ == __ORDER_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);lib/sbi/riscv_locks.c +46
-16@@ -2,44 +2,77 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #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; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long 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" +" slli %2, %0, %6\n" +" and %2, %2, %5\n" +" and %1, %0, %5\n" +/* Is the lock free right now? */ +" bne %1, %2, 2f\n" +" add %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 ; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long mask =0xffffu ; +u32 l0, tmp1, tmp2; -if (spin_trylock (lock)) -break ; - } + __asm__ __volatile__( +/* Atomically increment the next ticket. */ +" amoadd.w.aqrl %0, %4, %3\n" + +/* Did we get the lock? */ +" srli %1, %0, %6\n" +" and %1, %1, %5\n" +"1: and %2, %0, %5\n" +" beq %1, %2, 2f\n" + +/* If not, then spin on the lock. */ +" lw %0, %3\n" +RISCV_ACQUIRE_BARRIER +" j 1b\n" +"2:" + : "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
lib/sbi/riscv_locks.c line 78
Quoted 10 lines
lib/sbi/riscv_locks.c +4
-1+ : "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 ); } +
Looks good to me.
Anup Patel
AppliedPATCH v3 3/3 spinlocks: Replace test-and-set locks by ticket locks
Quoted 180 lines
-----Original Message-----
From: Xiang W <[email protected]>
Sent: 06 April 2021 11:20
To: Christoph Muellner <[email protected]>;
opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Jessica Clarke <[email protected]>
Subject: Re: [PATCH v3 3/3] spinlocks: Replace test-and-set locks by ticket locks? 2021-04-06?? 03:53 +0200?Christoph Muellner???
Quoted 95 lines
Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).
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.
This allows that the code works for both, RV32 and RV64.Signed-off-by Christoph Muellner <[email protected]>--- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++------ ---- 2 files changed, 72 insertions(+), 28 deletions(-)include/sbi/riscv_locks.h +22
-11@@ -2,26 +2,37 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #ifndef __RISCV_LOCKS_H__#define __RISCV_LOCKS_H__ +#include <sbi/sbi_types.h> + +#define TICKET_SHIFT 16 +typedef struct { -volatile long lock; -}spinlock_t ; +#if __BYTE_ORDER__ == __ORDER_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);lib/sbi/riscv_locks.c index renamed from lib/sbi/riscv_locks.c +0
-04d1d9c0..7e607b0 100644
lib/sbi/riscv_locks.c +7
-5@@ -2,44 +2,77 @@* SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. -* -* Authors: -* Anup Patel <[email protected]> +* Copyright (c) 2021 Christoph M?llner <[email protected]> */ #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); }lib/sbi/riscv_locks.c line 23
Quoted 10 lines
lib/sbi/riscv_locks.c +3
-2int spin_trylock (spinlock_t *lock) { -int tmp =1 , busy; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long mask =0xffffu <<TICKET_SHIFT ; +u32 l0, tmp1, tmp2; __asm__ __volatile__( - " amoswap.w %0, %2, %1\n"
RISCV_ACQUIRE_BARRIERQuoted 50 lines
lib/sbi/riscv_locks.c +34
-9- : "=r"(busy), "+A"(lock->lock) - : "r"(tmp) +/* Get the current lock counters. */ +"1: lr.w.aq %0, %3\n" +" slli %2, %0, %6\n" +" and %2, %2, %5\n" +" and %1, %0, %5\n" +/* Is the lock free right now? */ +" bne %1, %2, 2f\n" +" add %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 ; +unsigned long inc =1u <<TICKET_SHIFT ; +unsigned long mask =0xffffu ; +u32 l0, tmp1, tmp2; -if (spin_trylock (lock)) -break ; - } + __asm__ __volatile__( +/* Atomically increment the next ticket. */ +" amoadd.w.aqrl %0, %4, %3\n" + +/* Did we get the lock? */ +" srli %1, %0, %6\n" +" and %1, %1, %5\n" +"1: and %2, %0, %5\n" +" beq %1, %2, 2f\n" + +/* If not, then spin on the lock. */ +" lw %0, %3\n" +RISCV_ACQUIRE_BARRIER +" j 1b\n" +"2:" + : "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)lib/sbi/riscv_locks.c line 78
Quoted 10 lines
lib/sbi/riscv_locks.c +4
-1+ : "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 ); } +Looks good to me.
Quoted 1 line
Reviewed-by Xiang W <[email protected]>
Replaces patch subject prefix "spinlocks:" with "lib: sbi:"
Applied this patch to the riscv/opensbi repo
Regards,
Anup