Skip to contentSkip to conversation

spinlocks: Replace test-and-set locks by ticket locks

PATCH New Christoph Muellner 5 participants 12 messages Apr 3, 2021 – Apr 5, 2021

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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
index faa9676..59e6af9 100644
@@ -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
#1 lore raw

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.

---
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
index faa9676..59e6af9 100644
@@ -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
index 4d1d9c0..7d86742 100644
@@ -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

#2 lore raw

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.

---
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
index faa9676..59e6af9 100644
@@ -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_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.

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
index 4d1d9c0..7d86742 100644
@@ -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

#3 lore raw

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.

---
 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
index faa9676..59e6af9 100644
@@ -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 -2
 typedef 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
index 4d1d9c0..7d86742 100644
@@ -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
#4 lore raw

PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks

In reply to Christoph Muellner
Quoted 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 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.

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
---
 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 -0

faa9676..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 -0

100644

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_BARRIER

lib/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

#5 lore raw

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 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.

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 the
spin_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 pack next_ticket and owner into one word because these can be separate "unsigned long" in spinlock_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,
Anup

Quoted 165 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 +0 -0

index
faa9676..59e6af9 100644

include/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 -0

4d1d9c0..7d86742
100644

lib/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_BARRIER

lib/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

#6 lore raw

PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks

In reply to Anup Patel
Quoted 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 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.

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 the spin_trylock() is currently not used anywhere in OpenSBI, I suggest:

1) We can drop the spin_trylock() API as separate patch
2) Implement classic ticket spinlock approach as described in Wikipedia using AMOADD instructions and barriers.

Do you prefer AMOADD? I think it's a better idea (csky only has
lr.w/sc.w, so it's my habit :P), I will update the Linux ticket-lock
patch:
https://lore.kernel.org/linux-riscv/1617201040-83905-4-git-send-email-guoren at kernel.org/T/#u

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;
 
        asm volatile (
-               "1:     lr.w    %0, %2          \n"
-               "       mv      %1, %0          \n"
-               "       addw    %0, %0, %3      \n"
-               "       sc.w    %0, %0, %2      \n"
-               "       bnez    %0, 1b          \n"
-               : "=&r" (tmp), "=&r" (lockval), "+A" (lock->lock)
+               "   amoadd.w    %0, %2, %1      \n"
+               : "=&r" (lockval), "+A" (lock->lock)
                : "r" (1 << TICKET_NEXT)
                : "memory");
 

Thx for the tip :)

Quoted 173 lines

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 160 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 -0

faa9676..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 -0

100644

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_BARRIER

lib/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/
#7 lore raw

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 locks

Quoted 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 locks

Quoted 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 new

ticket.

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 the
spin_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
index 90b7eaa950cf..435286ad342b 100644
@@ -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_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 154 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 +0 -0

index
faa9676..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 renamed from lib/sbi/riscv_locks.c +0 -0

4d1d9c0..7d86742
100644

lib/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_BARRIER

lib/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

ML: https://lore.kernel.org/linux-csky/

Regards,
Anup

#8 lore raw

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 locks

Quoted 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 locks

Quoted 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 new

ticket.

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 the
spin_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 25 lines

with:

arch/riscv/include/asm/spinlock.h +2 -7
index 90b7eaa950cf..435286ad342b 100644
@@ -22,15 +22,10 @@
 static inline void arch_spin_lock(arch_spinlock_t *lock)  {
        arch_spinlock_t lockval;
-       u32 tmp;
 
        asm volatile (
-               "1:     lr.w    %0, %2          \n"
-               "       mv      %1, %0          \n"
-               "       addw    %0, %0, %3      \n"
-               "       sc.w    %0, %0, %2      \n"
-               "       bnez    %0, 1b          \n"
-               : "=&r" (tmp), "=&r" (lockval), "+A" (lock->lock)
+               "   amoadd.w    %0, %2, %1      \n"
+               : "=&r" (lockval), "+A" (lock->lock)
                : "r" (1 << TICKET_NEXT)
                : "memory");
 
Quoted 7 lines

arch/riscv/include/asm/spinlock.h line 31

Quoted 1 line
arch/riscv/include/asm/spinlock.h +0 -0
 Thx for the tip :)

I was going to comment in LKML after we had it working here but it's good that you already noticed it.

I did not think much about spin_trylock() using atomic instructions but it will be nice if you can attempt that as well in your Linux patches.

All riscv amo instructions will write to the target address unconditionally and there is no cas instruction in riscv A-extension. So "lr/sc" is the only way for riscv to implement trylock.

look the codes below:
static inline int arch_spin_trylock(arch_spinlock_t *lock)

{
        u32 tmp, contended, res;

        do {
                asm volatile (
                "       lr.w    %0, %3          \n"
                __ASM_SRLIW    "%1, %0, %5      \n"
                __ASM_SLLIW    "%2, %0, %5      \n"
                "       or      %1, %2, %1      \n"
                "       li      %2, 0           \n"
                "       sub     %1, %1, %0      \n"
                "       bnez    %1, 1f          \n"
                "       addw    %0, %0, %4      \n"
                "       sc.w    %2, %0, %3      \n"
                "1:                             \n"
                : "=&r" (tmp), "=&r" (contended), "=&r" (res),
                  "+A" (lock->lock)
                : "r" (1 << TICKET_NEXT), "I" (TICKET_NEXT)
                : "memory");
        } while (res);

        if (!contended)
                __atomic_acquire_fence();

        return !contended;
}

When lock is up, trylock'll fail and the instructions progress is:

                "       lr.w    %0, %3          \n"
                "       srliw    "%1, %0, %5      \n"
                "       slliw    "%2, %0, %5      \n"
                "       or      %1, %2, %1      \n"
                "       li      %2, 0           \n"
                "       sub     %1, %1, %0      \n"
                "       bnez    %1, 1f          \n"
                "1:"
                return !contented;

1 lr.w + 5 ALUs + branch = 7 instructions
The most inconvenient about RISC-V is that there is no rotate shift instruction, I must use more instructions and registers to implement compare operation for the owner:next-ticket.

Quoted 187 lines
Quoted 179 lines
Quoted 163 lines

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 154 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 +0 -0

index
faa9676..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 renamed from lib/sbi/riscv_locks.c +0 -0

4d1d9c0..7d86742
100644

lib/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_BARRIER

lib/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

ML: https://lore.kernel.org/linux-csky/

Regards,
Anup

Signature · 4 lines
Best Regards
 Guo Ren

ML: https://lore.kernel.org/linux-csky/
#9 lore raw

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 locks

Quoted 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 locks

On 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 locks

Quoted 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 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.

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/#u

Quoted 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
index 90b7eaa950cf..435286ad342b 100644
@@ -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_ticket and owner into one word

because

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 implementing spin_trylock(), Right ??

Regards,
Anup

Quoted 5 lines
---
 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.h index
faa9676..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 renamed from lib/sbi/riscv_locks.c +0 -0

4d1d9c0..7d86742
100644

lib/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_BARRIER

lib/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

Quoted 8 lines
Quoted 5 lines

--
Best Regards
Guo Ren

ML: https://lore.kernel.org/linux-csky/

Regards,
Anup

--
Best Regards
Guo Ren

ML: https://lore.kernel.org/linux-csky/

#10 lore raw

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 locks

Quoted 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 locks

On 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 locks

Quoted 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 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.

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/#u

Quoted 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
index 90b7eaa950cf..435286ad342b 100644
@@ -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_ticket and owner into one word

because

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 implementing spin_trylock(), Right ??

Regards,
Anup

Quoted 5 lines
---
 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.h index
faa9676..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 renamed from lib/sbi/riscv_locks.c +0 -0

4d1d9c0..7d86742
100644

lib/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_BARRIER

lib/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

Quoted 8 lines
Quoted 5 lines

--
Best Regards
Guo Ren

ML: https://lore.kernel.org/linux-csky/

Regards,
Anup

--
Best Regards
Guo Ren

ML: https://lore.kernel.org/linux-csky/

#11 lore raw

PATCH 1/1 spinlocks: Replace test-and-set locks by ticket locks

In reply to Christoph Muellner
Quoted 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.

---
 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
index faa9676..59e6af9 100644
@@ -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
index 4d1d9c0..7d86742 100644
@@ -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/