spinlocks: Replace test-and-set locks by ticket locks
Subsystems (2)
PATCH 1/1 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.
--- 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 ; +#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);
lib/sbi/riscv_locks.c +50 -17
94 lines not on this page · raw message
Signature · 1 line
2.30.2
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
Jess
Quoted 50 lines · Christoph Muellner
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.
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 +1
-3@@ -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__
include/sbi/riscv_locks.h line 16
Quoted 10 lines
include/sbi/riscv_locks.h +5
-2#define __RISCV_LOCKS_H__ +#include <sbi/sbi_types.h> + +#define TICKET_SHIFT 16 + typedef struct { -volatile long lock; -}spinlock_t ; +#ifdef __BIG_ENDIAN
This looks wrong. Neither GCC nor Clang define that, and sometimes you can end up with __BIG_ENDIAN being 4321, __LITTLE_ENDIAN being 1234 and __BYTE_ORDER being one of the two (or I guess also 3421 for __PDP_ENDIAN). __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ is the portable way to check this across Clang and GCC without relying on anything other than built-in defines.
Quoted 62 lines
include/sbi/riscv_locks.h +16
-6+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 +10
-6@@ -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; +u32 inc =1u <<TICKET_SHIFT ;
lib/sbi/riscv_locks.c line 31
Quoted 10 lines
lib/sbi/riscv_locks.c +5
-3+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"
This, and addw below, require RV64.
Quoted 27 lines
lib/sbi/riscv_locks.c +14
-6+" 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 ;
lib/sbi/riscv_locks.c line 61
Quoted 10 lines
lib/sbi/riscv_locks.c +9
-1- } + __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"
Do you mean to be reading the success code from sc, which is guaranteed 0 the first time round due to the above loop?
lib/sbi/riscv_locks.c line 66
Quoted 5 lines
lib/sbi/riscv_locks.c +5
-0+" and %1, %0, %5\n" +" beq %1, %2, 2f\n" + +/* No, let's spin on the lock. */ +" lr.w.aq %0, %3\n"
Why lr? This is just an acquire load, no reservation needed, so just lw then fence, otherwise I imagine this will hurt performance on Rocket due to the way it implements the forward progress guarantee.
Quoted 15 lines
lib/sbi/riscv_locks.c +7
-1+ " 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
Jess
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
Quoted 57 lines · Jessica Clarke
Jess
Quoted 52 lines · Christoph Muellner
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.
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 +1
-3@@ -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__
Quoted 15 lines
include/sbi/riscv_locks.h line 16
Quoted 8 lines
include/sbi/riscv_locks.h +5
-2+#include <sbi/sbi_types.h> + +#define TICKET_SHIFT 16 + typedef struct { -volatile long lock; -}spinlock_t ; +#ifdef __BIG_ENDIANThis looks wrong. Neither GCC nor Clang define that, and sometimes you can end up with
__BIG_ENDIANbeing 4321,__LITTLE_ENDIANbeing 1234 and__BYTE_ORDERbeing one of the two (or I guess also 3421 for__PDP_ENDIAN).__BYTE_ORDER__==__ORDER_BIG_ENDIAN__is the portable way to check this across Clang and GCC without relying on anything other than built-in defines.
Ah, yes.
Quoted 65 lines
Quoted 65 lines
include/sbi/riscv_locks.h +16
-6+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 +12
-6@@ -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; +u32 inc =1u <<TICKET_SHIFT ; +u32 mask =0xffffu <<TICKET_SHIFT ; +u32 l0, tmp1, tmp2;
Quoted 9 lines
lib/sbi/riscv_locks.c line 31
Quoted 7 lines
lib/sbi/riscv_locks.c +3
-3__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"This, and addw below, require RV64.
I admit that I have not tested RV32.
Will do this as well.
Quoted 38 lines
Quoted 27 lines
lib/sbi/riscv_locks.c +14
-6+" 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 ;lib/sbi/riscv_locks.c line 61
Quoted 10 lines
lib/sbi/riscv_locks.c +9
-1- } + __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"
Quoted 2 lines
Do you mean to be reading the success code from sc, which is guaranteed 0 the first time round due to the above loop?
Plus, the sequence is wrong.
I messed up when I tried to make lock() and trylock() more similar, but my tests did not trigger this issue.
Quoted 9 lines
lib/sbi/riscv_locks.c line 66
Quoted 5 lines
lib/sbi/riscv_locks.c +5
-0+" and %1, %0, %5\n" +" beq %1, %2, 2f\n" + +/* No, let's spin on the lock. */ +" lr.w.aq %0, %3\n" Why lr? This is just an acquire load, no reservation needed, so just lw then fence, otherwise I imagine this will hurt performance on Rocket due to the way it implements the forward progress guarantee.
Good point.
Thanks for the review!
I will go back to do more testing, to not embarrass myself again.
Christoph
Quoted 18 lines
Quoted 15 lines
lib/sbi/riscv_locks.c +7
-2+ " 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 ); } + --Quoted 1 line
2.30.2
Jess
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
In reply to Christoph Muellner? 2021-04-03?? 18:23 +0200?Christoph Muellner???
Quoted 3 lines
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.
Why?
Quoted 53 lines
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.
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 +5
-3@@ -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 +
include/sbi/riscv_locks.h line 22
Quoted 10 lines
include/sbi/riscv_locks.h +7
-2typedef struct { -volatile long lock; -}spinlock_t ; +#ifdef __BIG_ENDIAN + u16 next; + u16 owner; +#else + u16 owner; + u16 next; +#endif
I recommend using two u32, which can streamline part of the code and make the code better understandable.
Quoted 125 lines
include/sbi/riscv_locks.h +10
-6+}__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@@ -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; +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 ); } +Signature · 1 line
2.30.2
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
In reply to Christoph MuellnerQuoted 30 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 03 April 2021 21:53
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH] spinlocks: Replace test-and-set locks by ticket locksTest-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.
Quoted 5 lines
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 this packing only helps in implementing spin_trylock(), Right ??
Regards,
Anup
Quoted 161 lines
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 index renamed from include/sbi/riscv_locks.h +0
-0faa9676..59e6af9 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 ; +#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);lib/sbi/riscv_locks.c index 4d1d9c0..7d86742 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; +u32 inc =1u <<TICKET_SHIFT ; +u32 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" +" 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
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
? 2021-04-04?? 06:04 +0000?Anup Patel???
Quoted 48 lines
Quoted 35 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 03 April 2021 21:53
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH] spinlocks: Replace test-and-set locks by ticket locksTest-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.Quoted 8 lines
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 thespin_trylock()is currently not used anywhere in OpenSBI, I suggest:
Quoted 7 lines
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 packnext_ticketand owner into one word because these can be separate "unsigned long" inspinlock_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
Quoted 170 lines
this packing only helps in implementing
spin_trylock(), Right ??Regards,
AnupQuoted 165 lines
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 +0
-0index
faa9676..59e6af9 100644include/sbi/riscv_locks.h +0
-0@@ -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/riscv_locks.h +21
-8+#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);lib/sbi/riscv_locks.c index renamed from lib/sbi/riscv_locks.c +0
-04d1d9c0..7d86742
100644lib/sbi/riscv_locks.c +0
-0@@ -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>lib/sbi/riscv_locks.c +10
-4-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_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" +" 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
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
In reply to Anup PatelQuoted 37 lines · Anup Patel
Quoted 31 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 03 April 2021 21:53
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH] spinlocks: Replace test-and-set locks by ticket locksTest-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.
Quoted 5 lines
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.
Quoted 6 lines
The
spin_trylock()can be tricky to implement with ticket approach. Since thespin_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
with:
(quoted diff) +0 -0
b/arch/riscv/include/asm/spinlock.h
index 90b7eaa950cf..435286ad342b 100644
arch/riscv/include/asm/spinlock.h +2 -7
@@ -22,15 +22,10 @@static inline void arch_spin_lock (arch_spinlock_t *lock) {arch_spinlock_t lockval; -u32 tmp; asmvolatile ( -"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 :)
Quoted 173 lines
3) We don't need to pack
next_ticketand owner into one word because these can be separate "unsigned long" inspinlock_t. I believe that this packing only helps in implementingspin_trylock(), Right ??Regards,
AnupQuoted 160 lines
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 index renamed from include/sbi/riscv_locks.h +0
-0faa9676..59e6af9 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 ; +#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);lib/sbi/riscv_locks.c index 4d1d9c0..7d86742 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; +u32 inc =1u <<TICKET_SHIFT ; +u32 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" +" 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 ); } + --Quoted 1 line
2.30.2
--
opensbi mailing list
opensbi at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/opensbi
Signature · 4 lines
Best Regards Guo Ren ML: https://lore.kernel.org/linux-csky/
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
Quoted 54 lines
-----Original Message-----
From: Guo Ren <[email protected]>
Sent: 05 April 2021 11:09
To: Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>; opensbi at lists.infradead.org
Subject: Re: [PATCH] spinlocks: Replace test-and-set locks by ticket locksQuoted 11 lines · Anup Patel
Quoted 11 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 03 April 2021 21:53
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH] spinlocks: Replace test-and-set locks by ticket locksQuoted 1 line
Quoted 1 line
Test-and-set locks don't provide fairness and are non-deterministic
(w.r.t.
Quoted 6 lines
Quoted 6 lines
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).
Quoted 7 lines
Quoted 7 lines
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 newticket.
Quoted 17 lines
Quoted 7 lines
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.
Quoted 5 lines
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 thespin_trylock()is currently not used anywhere in OpenSBI, I suggest:
Quoted 8 lines
Quoted 3 lines
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.
Quoted 16 lines
with:
arch/riscv/include/asm/spinlock.h +0
-3@@ -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"
arch/riscv/include/asm/spinlock.h line 31
Quoted 10 lines
arch/riscv/include/asm/spinlock.h +2
-4- " 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.
Quoted 178 lines
Quoted 162 lines
3) We don't need to pack
next_ticketand owner into one word because these can be separate "unsigned long" inspinlock_t. I believe that this packing only helps in implementingspin_trylock(), Right ??Regards,
AnupQuoted 154 lines
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 +0
-0index
faa9676..59e6af9 100644include/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 ; +#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);lib/sbi/riscv_locks.c index renamed from lib/sbi/riscv_locks.c +0
-04d1d9c0..7d86742
100644lib/sbi/riscv_locks.c +10
-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; +u32 inc =1u <<TICKET_SHIFT ; +u32 mask =0xffffu <<TICKET_SHIFT ; +u32 l0, tmp1, tmp2; __asm__ __volatile__( - " amoswap.w %0, %2, %1\n"
RISCV_ACQUIRE_BARRIERlib/sbi/riscv_locks.c +36
-9- : "=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" ); }Quoted 13 lines
Quoted 8 lines
void
spin_unlock(spinlock_t *lock)
{lib/sbi/riscv_locks.c +2
-2-__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
Quoted 5 lines
--
Best Regards
Guo Ren
Regards,
Anup
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
Quoted 92 lines · Anup Patel
Quoted 55 lines
-----Original Message-----
From: Guo Ren <[email protected]>
Sent: 05 April 2021 11:09
To: Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>; opensbi at lists.infradead.org
Subject: Re: [PATCH] spinlocks: Replace test-and-set locks by ticket locksQuoted 11 lines · Anup Patel
Quoted 11 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 03 April 2021 21:53
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH] spinlocks: Replace test-and-set locks by ticket locksQuoted 1 line
Quoted 1 line
Test-and-set locks don't provide fairness and are non-deterministic
(w.r.t.
Quoted 6 lines
Quoted 6 lines
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).
Quoted 7 lines
Quoted 7 lines
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 newticket.
Quoted 17 lines
Quoted 7 lines
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.
Quoted 5 lines
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 thespin_trylock()is currently not used anywhere in OpenSBI, I suggest:Quoted 8 lines
Quoted 3 lines
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/#uIt'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.
Quoted 25 lines
with:
arch/riscv/include/asm/spinlock.h +2
-7@@ -22,15 +22,10 @@static inline void arch_spin_lock (arch_spinlock_t *lock) {arch_spinlock_t lockval; -u32 tmp; asmvolatile ( -"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" );
Quoted 7 lines
arch/riscv/include/asm/spinlock.h line 31
Quoted 1 line
arch/riscv/include/asm/spinlock.h +0
-0Thx 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.
Quoted 187 lines
Quoted 179 lines
Quoted 163 lines
3) We don't need to pack
next_ticketand owner into one word because these can be separate "unsigned long" inspinlock_t. I believe that this packing only helps in implementingspin_trylock(), Right ??Regards,
AnupQuoted 154 lines
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 +0
-0index
faa9676..59e6af9 100644include/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 ; +#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);lib/sbi/riscv_locks.c index renamed from lib/sbi/riscv_locks.c +0
-04d1d9c0..7d86742
100644lib/sbi/riscv_locks.c +10
-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; +u32 inc =1u <<TICKET_SHIFT ; +u32 mask =0xffffu <<TICKET_SHIFT ; +u32 l0, tmp1, tmp2; __asm__ __volatile__( - " amoswap.w %0, %2, %1\n"
RISCV_ACQUIRE_BARRIERlib/sbi/riscv_locks.c +36
-9- : "=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" ); }Quoted 13 lines
Quoted 8 lines
void
spin_unlock(spinlock_t *lock)
{lib/sbi/riscv_locks.c +2
-2-__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/opensbiQuoted 5 lines
--
Best Regards
Guo RenRegards,
Anup
Signature · 4 lines
Best Regards Guo Ren ML: https://lore.kernel.org/linux-csky/
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
Quoted 116 lines
-----Original Message-----
From: Guo Ren <[email protected]>
Sent: 05 April 2021 12:23
To: Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>; opensbi at lists.infradead.org
Subject: Re: [PATCH] spinlocks: Replace test-and-set locks by ticket locksQuoted 13 lines · Anup Patel
Quoted 13 lines
-----Original Message-----
From: Guo Ren <[email protected]>
Sent: 05 April 2021 11:09
To: Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>;
opensbi at lists.infradead.org
Subject: Re: [PATCH] spinlocks: Replace test-and-set locks by ticket locksOn Sun, Apr 4, 2021 at 2:05 PM Anup Patel <[email protected]>
Quoted 14 lines · wrote:
Quoted 14 lines
Quoted 11 lines
Quoted 11 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 03 April 2021 21:53
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH] spinlocks: Replace test-and-set locks by ticket locksQuoted 2 lines
Quoted 2 lines
Test-and-set locks don't provide fairness and are
non-deterministic(w.r.t.
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
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.
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
The counter 'next' holds the latest free ticket number.
The lock is free if both counters are equal. To acquire the lock, the
'next'
Quoted 31 lines
Quoted 24 lines
Quoted 3 lines
Quoted 3 lines
counter is atomically incremented to obtain a new ticket. The counter 'owner' is then polled until it becomes equal to the new
ticket.
Quoted 13 lines
Quoted 7 lines
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.
Quoted 5 lines
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.
Quoted 7 lines
The
spin_trylock()can be tricky to implement with ticket approach. Since thespin_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.Quoted 6 lines
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-emai
l-
guoren at kernel.org/T/#uQuoted 2 lines
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.
Quoted 31 lines
Quoted 17 lines
with:
arch/riscv/include/asm/spinlock.h +0
-3@@ -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"arch/riscv/include/asm/spinlock.h line 31
Quoted 10 lines
arch/riscv/include/asm/spinlock.h +2
-4- " 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.
Quoted 5 lines
Quoted 2 lines
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.
spin_trylock() is not so common in Linux so I guess using LR/SC just for spin_trylock() should be fine. For other arch_spin_xyz() functions, we should prefer AMO instructions as much as possible.
Quoted 40 lines
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;
Quoted 3 lines
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.
You will not require shift instruction if "next_ticket" and "owner" are not packed into one word.
Regards,
Anup
Quoted 195 lines
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
3) We don't need to pack
next_ticketand owner into one wordbecause
Quoted 11 lines
Quoted 11 lines
Quoted 11 lines
these can be separate "unsigned long" in
spinlock_t. I believe that this packing only helps in implementingspin_trylock(), Right ??Regards,
AnupQuoted 5 lines
Signed-off-by Christoph Muellner <[email protected]>--- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++----------
Quoted 162 lines
Quoted 162 lines
Quoted 159 lines
Quoted 153 lines
2 files changed, 72 insertions(+), 28 deletions(-)(quoted diff) +0
-0
b/include/sbi/riscv_locks.hindex
faa9676..59e6af9 100644include/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 ; +#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);lib/sbi/riscv_locks.c index renamed from lib/sbi/riscv_locks.c +0
-04d1d9c0..7d86742
100644lib/sbi/riscv_locks.c +10
-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; +u32 inc =1u <<TICKET_SHIFT ; +u32 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" +" 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 ); } + --Quoted 1 line
2.30.2
--
opensbi mailing list
opensbi at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/opensbiQuoted 8 lines
Quoted 5 lines
--
Best Regards
Guo RenRegards,
Anup--
Best Regards
Guo Ren
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
Thanks for all the input!
I've just sent out a v2, which got proper testing and is thus reaching the minium
requirement of being correct on RV32/RV64 with qemu:
http://lists.infradead.org/pipermail/opensbi/2021-April/000783.html
Regarding the trylock() question: I'd keep it, because having that is a valid expectation
of a programmer.
The idea with AMOADD for spin_lock() is good. I will use that in a v3.
Thanks,
Christoph
Quoted 372 lines · Anup Patel
Quoted 117 lines
-----Original Message-----
From: Guo Ren <[email protected]>
Sent: 05 April 2021 12:23
To: Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>; opensbi at lists.infradead.org
Subject: Re: [PATCH] spinlocks: Replace test-and-set locks by ticket locksQuoted 13 lines · Anup Patel
Quoted 13 lines
-----Original Message-----
From: Guo Ren <[email protected]>
Sent: 05 April 2021 11:09
To: Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>;
opensbi at lists.infradead.org
Subject: Re: [PATCH] spinlocks: Replace test-and-set locks by ticket locksOn Sun, Apr 4, 2021 at 2:05 PM Anup Patel <[email protected]>
Quoted 14 lines · wrote:
Quoted 14 lines
Quoted 11 lines
Quoted 11 lines
-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 03 April 2021 21:53
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH] spinlocks: Replace test-and-set locks by ticket locksQuoted 2 lines
Quoted 2 lines
Test-and-set locks don't provide fairness and are
non-deterministic(w.r.t.
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
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.
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
The counter 'next' holds the latest free ticket number.
The lock is free if both counters are equal. To acquire the lock, the
'next'
Quoted 31 lines
Quoted 24 lines
Quoted 3 lines
Quoted 3 lines
counter is atomically incremented to obtain a new ticket. The counter 'owner' is then polled until it becomes equal to the new
ticket.
Quoted 13 lines
Quoted 7 lines
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.
Quoted 5 lines
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.
Quoted 7 lines
The
spin_trylock()can be tricky to implement with ticket approach. Since thespin_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.Quoted 6 lines
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-emai
l-
guoren at kernel.org/T/#uQuoted 2 lines
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.
Quoted 31 lines
Quoted 17 lines
with:
arch/riscv/include/asm/spinlock.h +0
-3@@ -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"arch/riscv/include/asm/spinlock.h line 31
Quoted 10 lines
arch/riscv/include/asm/spinlock.h +2
-4- " 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.
Quoted 5 lines
Quoted 2 lines
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.
spin_trylock()is not so common in Linux so I guess using LR/SC just forspin_trylock()should be fine. For otherarch_spin_xyz()functions, we should prefer AMO instructions as much as possible.Quoted 40 lines
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;Quoted 3 lines
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.
You will not require shift instruction if "
next_ticket" and "owner" are not packed into one word.Regards,
AnupQuoted 195 lines
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
3) We don't need to pack
next_ticketand owner into one wordbecause
Quoted 11 lines
Quoted 11 lines
Quoted 11 lines
these can be separate "unsigned long" in
spinlock_t. I believe that this packing only helps in implementingspin_trylock(), Right ??Regards,
AnupQuoted 5 lines
Signed-off-by Christoph Muellner <[email protected]>--- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++----------
Quoted 162 lines
Quoted 162 lines
Quoted 159 lines
Quoted 153 lines
2 files changed, 72 insertions(+), 28 deletions(-)(quoted diff) +0
-0
b/include/sbi/riscv_locks.hindex
faa9676..59e6af9 100644include/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 ; +#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);lib/sbi/riscv_locks.c index renamed from lib/sbi/riscv_locks.c +0
-04d1d9c0..7d86742
100644lib/sbi/riscv_locks.c +10
-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; +u32 inc =1u <<TICKET_SHIFT ; +u32 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" +" 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 ); } + --Quoted 1 line
2.30.2
--
opensbi mailing list
opensbi at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/opensbiQuoted 8 lines
Quoted 5 lines
--
Best Regards
Guo RenRegards,
Anup--
Best Regards
Guo Ren
PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks
In reply to Christoph MuellnerQuoted 138 lines · Christoph Muellner
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.
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 ; +#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);lib/sbi/riscv_locks.c +22
-9@@ -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; +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"
lib/sbi/riscv_locks.c line 47
Quoted 10 lines
lib/sbi/riscv_locks.c +4
-1+ "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)
Please use inline for spin_lock, spin_try_lock, spin_unlock.
Quoted 6 lines
lib/sbi/riscv_locks.c +2
-3{ -while (1 ) { -if (spin_lock_check (lock)) -continue ; +u32 inc =1u <<TICKET_SHIFT ; +u32 mask =0xffffu <<TICKET_SHIFT ;
lib/sbi/riscv_locks.c line 57
Quoted 10 lines
lib/sbi/riscv_locks.c +6
-3+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"
I think it's wrong for acquiring & releasing here. It should be:
lock - acquire
unlock - release
lib/sbi/riscv_locks.c line 61
Quoted 4 lines
lib/sbi/riscv_locks.c +4
-0+" bnez %0, 0b\n" + +/* Did we get the lock? */ +"1: slliw %2, %0, %6\n"
slliw only support for rv64, so you need use slli for rv32. ref:
https://lore.kernel.org/linux-riscv/1617201040-83905-4-git-send-email-guoren at kernel.org/T/#u
Quoted 26 lines
lib/sbi/riscv_locks.c +12
-2+" 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
Signature · 4 lines
Best Regards Guo Ren ML: https://lore.kernel.org/linux-csky/