Skip to contentSkip to conversation

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

PATCH New Christoph Muellner 4 participants 13 messages Apr 6, 2021 – Apr 9, 2021 RISC-V

lore
Share & tools
lore
#0 lore raw

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

This patch series replaces the test-and-set spinlock implementation of OpenSBI with ticket locks.

Test-and-set locks don't provide fairness and are non-deterministic (w.r.t. the prediction of the future holder of a lock). This can be a performance problem in case of lock contention (e.g. consumers continuously steal the lock from a single producer).

Let's change the implementation to use ticket locks, which guarantee a fair locking order (FIFO ordering).

Ticket locks have two counters 'owner' and 'next'.
The counter 'owner' holds the ticket number of the current lock owner. The counter 'next' holds the latest free ticket number.

The lock is free if both counters are equal. To acquire the lock, the 'next' counter is atomically incremented (fetch-and-inc) to obtain a new ticket. The counter 'owner' is then polled until it becomes equal to the new ticket. To release a lock, one atomically increments the 'owner' counter.

This patchset has been tested on RV64 and RV32 against self-written unit tests (to ensure the 16-bit overflow is correct) and against the Linux kernel (by exchanging the kernel's spinlock implementation with the one from this patchset).

Note, that RISC-V lacks sub-word atomics, therefore we need to circumvent this limitation with additional instructions.

v3:
* Replace LR/SC sequence by AMOADD in spin_lock()
* Add cover letter

v2:
* Fixing RV32 support
* Address comments from Jessica

Christoph Muellner (3):
include: types: Add __aligned(x) to define the minimum alignement
spinlocks: Allow direct initialization via SPIN_LOCK_INIT()
spinlocks: Replace test-and-set locks by ticket locks

 include/sbi/riscv_locks.h | 33 ++++++++++++-------
 include/sbi/sbi_types.h   |  1 +
 lib/sbi/riscv_locks.c     | 67 +++++++++++++++++++++++++++++----------
 lib/sbi/sbi_fifo.c        |  2 +-
 4 files changed, 74 insertions(+), 29 deletions(-)
Signature · 1 line
2.30.2
#1 lore raw

PATCH v3 1/3 include: types: Add __aligned(x) to define the minimum alignement

The __aligned(x) macro is a common wrapper around compiler's aligned attribute, which allow to define the minimum alignement of a data type. Let's add this macro.

---
 include/sbi/sbi_types.h | 1 +
 1 file changed, 1 insertion(+)
include/sbi/sbi_types.h +1 -0
index 0952d5c..38e3565 100644
@@ -63,6 +63,7 @@ typedef unsigned long		physical_size_t;
 
 #define __packed		__attribute__((packed))
 #define __noreturn		__attribute__((noreturn))
+#define __aligned(x)		__attribute__((aligned(x)))
 
 #define likely(x) __builtin_expect((x), 1)
 #define unlikely(x) __builtin_expect((x), 0)
Signature · 1 line
2.30.2
#2 lore raw

PATCH v3 1/3 include: types: Add __aligned(x) to define the minimum alignement

Quoted 12 lines

-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 1/3] include: types: Add __aligned(x) to define the minimum alignement

Quoted 5 lines

The __aligned(x) macro is a common wrapper around compiler's aligned attribute, which allow to define the minimum alignement of a data type. Let's add this macro.

Looks good to me.

Thanks,
Anup

Quoted 18 lines
---
 include/sbi/sbi_types.h | 1 +
 1 file changed, 1 insertion(+)
include/sbi/sbi_types.h index renamed from include/sbi/sbi_types.h +0 -0

0952d5c..38e3565 100644

include/sbi/sbi_types.h +1 -1
@@ -63,6 +63,7 @@ typedef unsigned long		physical_size_t;
 
 #define __packed		__attribute__((packed))
 #define __noreturn		__attribute__((noreturn))
+#define __aligned(x)		__attribute__((aligned(x)))
 
 #define likely(x) __builtin_expect((x), 1)  #define unlikely(x)
 __builtin_expect((x), 0)
--

2.30.2

Applied
#3 lore raw

PATCH v3 1/3 include: types: Add __aligned(x) to define the minimum alignement

Quoted 27 lines

-----Original Message-----
From: Anup Patel
Sent: 06 April 2021 10:36
To: Christoph Muellner <[email protected]>;
opensbi at lists.infradead.org; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Subject: RE: [PATCH v3 1/3] include: types: Add __aligned(x) to define the minimum alignement

Quoted 14 lines

-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 1/3] include: types: Add __aligned(x) to define the minimum alignement

The __aligned(x) macro is a common wrapper around compiler's aligned attribute, which allow to define the minimum alignement of a data type. Let's add this macro.

Quoted 5 lines
Quoted 1 line

Looks good to me.

Applied this patch to the riscv/opensbi repo

Regards,
Anup

Quoted 22 lines

Thanks,
Anup

Quoted 18 lines
---
 include/sbi/sbi_types.h | 1 +
 1 file changed, 1 insertion(+)
include/sbi/sbi_types.h index renamed from include/sbi/sbi_types.h +0 -0

0952d5c..38e3565 100644

include/sbi/sbi_types.h +1 -1
@@ -63,6 +63,7 @@ typedef unsigned long		physical_size_t;
 
 #define __packed		__attribute__((packed))
 #define __noreturn		__attribute__((noreturn))
+#define __aligned(x)		__attribute__((aligned(x)))
 
 #define likely(x) __builtin_expect((x), 1)  #define unlikely(x)
 __builtin_expect((x), 0)
--

2.30.2

#4 lore raw

PATCH v3 2/3 spinlocks: Allow direct initialization via SPIN_LOCK_INIT()

In reply to Christoph Muellner

The current implementation of SPIN_LOCK_INIT() provides the spinlock to be initialized as reference. This does not allow a direct initialization of the spinlock object at the creation site.

Let's pass the spinlock directly instead (like Linux does as well) and adjust all users of the macro (in fact there is only one user).

---
 include/sbi/riscv_locks.h | 2 +-
 lib/sbi/sbi_fifo.c        | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)
include/sbi/riscv_locks.h +1 -1
index 55da7c0..faa9676 100644
@@ -16,7 +16,7 @@ typedef struct {
 
 #define __RISCV_SPIN_UNLOCKED 0
 
-#define SPIN_LOCK_INIT(_lptr) (_lptr)->lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
 
 #define SPIN_LOCK_INITIALIZER                  \
 	{                                      \
lib/sbi/sbi_fifo.c +1 -1
index 8d1dbf0..2a5c012 100644
@@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void *queue_mem, u16 entries,
 	fifo->queue	  = queue_mem;
 	fifo->num_entries = entries;
 	fifo->entry_size  = entry_size;
-	SPIN_LOCK_INIT(&fifo->qlock);
+	SPIN_LOCK_INIT(fifo->qlock);
 	fifo->avail = fifo->tail = 0;
 	sbi_memset(fifo->queue, 0, (size_t)entries * entry_size);
 }
Signature · 1 line
2.30.2
#5 lore raw

PATCH v3 2/3 spinlocks: Allow direct initialization via SPIN_LOCK_INIT()

Quoted 12 lines

-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 2/3] spinlocks: Allow direct initialization via SPIN_LOCK_INIT()

Quoted 8 lines

The current implementation of SPIN_LOCK_INIT() provides the spinlock to be initialized as reference. This does not allow a direct initialization of the spinlock object at the creation site.

Let's pass the spinlock directly instead (like Linux does as well) and adjust all users of the macro (in fact there is only one user).

Looks good to me.

Thanks,
Anup

Quoted 33 lines
---
 include/sbi/riscv_locks.h | 2 +-
 lib/sbi/sbi_fifo.c        | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)
include/sbi/riscv_locks.h index renamed from include/sbi/riscv_locks.h +0 -0

55da7c0..faa9676 100644

include/sbi/riscv_locks.h +1 -1
@@ -16,7 +16,7 @@ typedef struct {
 
 #define __RISCV_SPIN_UNLOCKED 0
 
-#define SPIN_LOCK_INIT(_lptr) (_lptr)->lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
 
 #define SPIN_LOCK_INITIALIZER                  \
 	{                                      \
lib/sbi/sbi_fifo.c index 8d1dbf0..2a5c012 renamed from lib/sbi/sbi_fifo.c +0 -0

100644

lib/sbi/sbi_fifo.c +1 -2
@@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void
 *queue_mem, u16 entries,
 	fifo->queue	  = queue_mem;
 	fifo->num_entries = entries;
 	fifo->entry_size  = entry_size;
-	SPIN_LOCK_INIT(&fifo->qlock);
+	SPIN_LOCK_INIT(fifo->qlock);
 	fifo->avail = fifo->tail = 0;
 	sbi_memset(fifo->queue, 0, (size_t)entries * entry_size);  }
--

2.30.2

Applied
#6 lore raw

PATCH v3 2/3 spinlocks: Allow direct initialization via SPIN_LOCK_INIT()

Quoted 27 lines

-----Original Message-----
From: Anup Patel
Sent: 06 April 2021 10:37
To: Christoph Muellner <[email protected]>;
opensbi at lists.infradead.org; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Subject: RE: [PATCH v3 2/3] spinlocks: Allow direct initialization via SPIN_LOCK_INIT()

Quoted 14 lines

-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 2/3] spinlocks: Allow direct initialization via SPIN_LOCK_INIT()

The current implementation of SPIN_LOCK_INIT() provides the spinlock to be initialized as reference. This does not allow a direct initialization of the spinlock object at the creation site.

Quoted 8 lines
Quoted 4 lines

Let's pass the spinlock directly instead (like Linux does as well) and adjust all users of the macro (in fact there is only one user).

Looks good to me.

Replaced patch subject prefix "spinlocks:" with "lib: sbi:"

Applied this patch to the riscv/opensbi repo

Regards,
Anup

Quoted 39 lines

Thanks,
Anup

Quoted 35 lines
---
 include/sbi/riscv_locks.h | 2 +-
 lib/sbi/sbi_fifo.c        | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)
include/sbi/riscv_locks.h +0 -0

index
55da7c0..faa9676 100644

include/sbi/riscv_locks.h +1 -1
@@ -16,7 +16,7 @@ typedef struct {
 
 #define __RISCV_SPIN_UNLOCKED 0
 
-#define SPIN_LOCK_INIT(_lptr) (_lptr)->lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
 
 #define SPIN_LOCK_INITIALIZER                  \
 	{                                      \
lib/sbi/sbi_fifo.c index renamed from lib/sbi/sbi_fifo.c +0 -0

8d1dbf0..2a5c012
100644

lib/sbi/sbi_fifo.c +1 -2
@@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void
 *queue_mem, u16 entries,
 	fifo->queue	  = queue_mem;
 	fifo->num_entries = entries;
 	fifo->entry_size  = entry_size;
-	SPIN_LOCK_INIT(&fifo->qlock);
+	SPIN_LOCK_INIT(fifo->qlock);
 	fifo->avail = fifo->tail = 0;
 	sbi_memset(fifo->queue, 0, (size_t)entries * entry_size);  }
--

2.30.2

#7 lore raw

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

In reply to Christoph Muellner

Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).

The implementation uses a 32-bit wide struct, which consists of two 16-bit counters (owner and next). This is inspired by similar spinlock implementations on other architectures.
This allows that the code works for both, RV32 and RV64.

---
 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..492935f 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;
+#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+       u16 next;
+       u16 owner;
+#else
+       u16 owner;
+       u16 next;
+#endif
+} __aligned(4) spinlock_t;
+
+#define __SPIN_LOCK_UNLOCKED	\
+	(spinlock_t) { 0, 0 }
 
-#define __RISCV_SPIN_UNLOCKED 0
+#define SPIN_LOCK_INIT(x)	\
+	x = __SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INITIALIZER	\
+	__SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INITIALIZER                  \
-	{                                      \
-		.lock = __RISCV_SPIN_UNLOCKED, \
-	}
+#define DEFINE_SPIN_LOCK(x)	\
+	spinlock_t SPIN_LOCK_INIT(x)
 
 int spin_lock_check(spinlock_t *lock);
 
lib/sbi/riscv_locks.c +50 -17

94 lines not on this page · raw message

Signature · 1 line
2.30.2
#8 lore raw

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

? 2021-04-06?? 03:53 +0200?Christoph Muellner???

Quoted 139 lines

Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).

The implementation uses a 32-bit wide struct, which consists of two 16-bit counters (owner and next). This is inspired by similar spinlock implementations on other architectures.
This allows that the code works for both, RV32 and RV64.

---
 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..492935f 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;
+#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+       u16 next;
+       u16 owner;
+#else
+       u16 owner;
+       u16 next;
+#endif
+} __aligned(4) spinlock_t;
+
+#define __SPIN_LOCK_UNLOCKED	\
+	(spinlock_t) { 0, 0 }
 
-#define __RISCV_SPIN_UNLOCKED 0
+#define SPIN_LOCK_INIT(x)	\
+	x = __SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INITIALIZER	\
+	__SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INITIALIZER                  \
-	{                                      \
-		.lock = __RISCV_SPIN_UNLOCKED, \
-	}
+#define DEFINE_SPIN_LOCK(x)	\
+	spinlock_t SPIN_LOCK_INIT(x)
 
 int spin_lock_check(spinlock_t *lock);
 
lib/sbi/riscv_locks.c +30 -14
index 4d1d9c0..7e607b0 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;
+	unsigned long inc = 1u << TICKET_SHIFT;
+	unsigned long mask = 0xffffu << TICKET_SHIFT;
+	u32 l0, tmp1, tmp2;
 
 	__asm__ __volatile__(
-		"	amoswap.w %0, %2, %1\n" RISCV_ACQUIRE_BARRIER
-		: "=r"(busy), "+A"(lock->lock)
-		: "r"(tmp)
+		/* Get the current lock counters. */
+		"1:	lr.w.aq	%0, %3\n"
+		"	slli	%2, %0, %6\n"
+		"	and	%2, %2, %5\n"
+		"	and	%1, %0, %5\n"
+		/* Is the lock free right now? */
+		"	bne	%1, %2, 2f\n"
+		"	add	%0, %0, %4\n"
+		/* Acquire the lock. */
+		"	sc.w.rl	%0, %0, %3\n"
+		"	bnez	%0, 1b\n"
+		"2:"
+		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
 		: "memory");
 
-	return !busy;
+	return !l0;
 }
 
 void spin_lock(spinlock_t *lock)
 {
-	while (1) {
-		if (spin_lock_check(lock))
-			continue;
+	unsigned long inc = 1u << TICKET_SHIFT;
+	unsigned long mask = 0xffffu;
+	u32 l0, tmp1, tmp2;
 
-		if (spin_trylock(lock))

lib/sbi/riscv_locks.c line 61

Quoted 10 lines
lib/sbi/riscv_locks.c +8 -2
-			break;
-	}
+	__asm__ __volatile__(
+		/* Atomically increment the next ticket. */
+		"	amoadd.w.aqrl	%0, %4, %3\n"
+
+		/* Did we get the lock? */
+		"	srli	%1, %0, %6\n"
+		"	and	%1, %1, %5\n"
+		"1:	and	%2, %0, %5\n"

What we need to keep re-reading should be 'owner'

Regards,
Xiang W

Quoted 22 lines
lib/sbi/riscv_locks.c +12 -1
+		"	beq	%1, %2, 2f\n"
+
+		/* If not, then spin on the lock. */
+		"	lw	%0, %3\n"
+		RISCV_ACQUIRE_BARRIER
+		"	j	1b\n"
+		"2:"
+		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
+		: "memory");
 }
 
 void spin_unlock(spinlock_t *lock)
 {
-	__smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED);
+	__smp_store_release(&lock->owner, lock->owner + 1);
 }
+
Signature · 1 line
2.30.2
#9 lore raw

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

Quoted 140 lines · Xiang W

? 2021-04-06?? 03:53 +0200?Christoph Muellner???

Quoted 138 lines

Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).

The implementation uses a 32-bit wide struct, which consists of two 16-bit counters (owner and next). This is inspired by similar spinlock implementations on other architectures.
This allows that the code works for both, RV32 and RV64.

---
 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..492935f 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;
+#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+       u16 next;
+       u16 owner;
+#else
+       u16 owner;
+       u16 next;
+#endif
+} __aligned(4) spinlock_t;
+
+#define __SPIN_LOCK_UNLOCKED \
+     (spinlock_t) { 0, 0 }
 
-#define __RISCV_SPIN_UNLOCKED 0
+#define SPIN_LOCK_INIT(x)    \
+     x = __SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INITIALIZER        \
+     __SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INITIALIZER                  \
-     {                                      \
-             .lock = __RISCV_SPIN_UNLOCKED, \
-     }
+#define DEFINE_SPIN_LOCK(x)  \
+     spinlock_t SPIN_LOCK_INIT(x)
 
 int spin_lock_check(spinlock_t *lock);
 
lib/sbi/riscv_locks.c +30 -13
index 4d1d9c0..7e607b0 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;
+     unsigned long inc = 1u << TICKET_SHIFT;
+     unsigned long mask = 0xffffu << TICKET_SHIFT;
+     u32 l0, tmp1, tmp2;
 
      __asm__ __volatile__(
-             "       amoswap.w %0, %2, %1\n" RISCV_ACQUIRE_BARRIER
-             : "=r"(busy), "+A"(lock->lock)
-             : "r"(tmp)
+             /* Get the current lock counters. */
+             "1:     lr.w.aq %0, %3\n"
+             "       slli    %2, %0, %6\n"
+             "       and     %2, %2, %5\n"
+             "       and     %1, %0, %5\n"
+             /* Is the lock free right now? */
+             "       bne     %1, %2, 2f\n"
+             "       add     %0, %0, %4\n"
+             /* Acquire the lock. */
+             "       sc.w.rl %0, %0, %3\n"
+             "       bnez    %0, 1b\n"
+             "2:"
+             : "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
+             : "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
              : "memory");
 
-     return !busy;
+     return !l0;
 }
 
 void spin_lock(spinlock_t *lock)
 {
-     while (1) {
-             if (spin_lock_check(lock))
-                     continue;
+     unsigned long inc = 1u << TICKET_SHIFT;
+     unsigned long mask = 0xffffu;
+     u32 l0, tmp1, tmp2;
 
Quoted 12 lines

lib/sbi/riscv_locks.c line 61

Quoted 11 lines
lib/sbi/riscv_locks.c +8 -3
-             if (spin_trylock(lock))
-                     break;
-     }
+     __asm__ __volatile__(
+             /* Atomically increment the next ticket. */
+             "       amoadd.w.aqrl   %0, %4, %3\n"
+
+             /* Did we get the lock? */
+             "       srli    %1, %0, %6\n"
+             "       and     %1, %1, %5\n"
+             "1:     and     %2, %0, %5\n"

What we need to keep re-reading should be 'owner'

Yes, the code is already doing that.

The "owner" is lower 16bits so "and %2, %0, %5\n" will
extract "owner" in %2. The %1 already has assigned ticket number.

Regards,
Anup

#10 lore raw

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

In reply to Christoph Muellner
Quoted 14 lines

-----Original Message-----
From: Christoph Muellner <[email protected]>
Sent: 06 April 2021 07:24
To: opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Xiang W <[email protected]>; Jessica Clarke <[email protected]>
Cc: Christoph Muellner <[email protected]>
Subject: [PATCH v3 3/3] spinlocks: Replace test-and-set locks by ticket locks

Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).

Quoted 6 lines

The implementation uses a 32-bit wide struct, which consists of two 16-bit counters (owner and next). This is inspired by similar spinlock implementations on other architectures.
This allows that the code works for both, RV32 and RV64.

Looks good to me.

Thanks,
Anup

Quoted 159 lines
---
 include/sbi/riscv_locks.h | 33 ++++++++++++-------
 lib/sbi/riscv_locks.c     | 67 +++++++++++++++++++++++++++++----------
 2 files changed, 72 insertions(+), 28 deletions(-)
include/sbi/riscv_locks.h index renamed from include/sbi/riscv_locks.h +0 -0

faa9676..492935f 100644

include/sbi/riscv_locks.h +22 -11
@@ -2,26 +2,37 @@
  * SPDX-License-Identifier: BSD-2-Clause
  *
  * Copyright (c) 2019 Western Digital Corporation or its affiliates.
- *
- * Authors:
- *   Anup Patel <[email protected]>
+ * Copyright (c) 2021 Christoph M?llner <[email protected]>
  */
 
 #ifndef __RISCV_LOCKS_H__
 #define __RISCV_LOCKS_H__
 
+#include <sbi/sbi_types.h>
+
+#define TICKET_SHIFT	16
+
 typedef struct {
-	volatile long lock;
-} spinlock_t;
+#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+       u16 next;
+       u16 owner;
+#else
+       u16 owner;
+       u16 next;
+#endif
+} __aligned(4) spinlock_t;
+
+#define __SPIN_LOCK_UNLOCKED	\
+	(spinlock_t) { 0, 0 }
 
-#define __RISCV_SPIN_UNLOCKED 0
+#define SPIN_LOCK_INIT(x)	\
+	x = __SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INITIALIZER	\
+	__SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INITIALIZER                  \
-	{                                      \
-		.lock = __RISCV_SPIN_UNLOCKED, \
-	}
+#define DEFINE_SPIN_LOCK(x)	\
+	spinlock_t SPIN_LOCK_INIT(x)
 
 int spin_lock_check(spinlock_t *lock);
 
lib/sbi/riscv_locks.c index 4d1d9c0..7e607b0 renamed from lib/sbi/riscv_locks.c +0 -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;
+	unsigned long inc = 1u << TICKET_SHIFT;
+	unsigned long mask = 0xffffu << TICKET_SHIFT;
+	u32 l0, tmp1, tmp2;
 
 	__asm__ __volatile__(
-		"	amoswap.w %0, %2, %1\n"

RISCV_ACQUIRE_BARRIER

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"
+		"	slli	%2, %0, %6\n"
+		"	and	%2, %2, %5\n"
+		"	and	%1, %0, %5\n"
+		/* Is the lock free right now? */
+		"	bne	%1, %2, 2f\n"
+		"	add	%0, %0, %4\n"
+		/* Acquire the lock. */
+		"	sc.w.rl	%0, %0, %3\n"
+		"	bnez	%0, 1b\n"
+		"2:"
+		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
 		: "memory");
 
-	return !busy;
+	return !l0;
 }
 
 void spin_lock(spinlock_t *lock)
 {
-	while (1) {
-		if (spin_lock_check(lock))
-			continue;
+	unsigned long inc = 1u << TICKET_SHIFT;
+	unsigned long mask = 0xffffu;
+	u32 l0, tmp1, tmp2;
 
-		if (spin_trylock(lock))
-			break;
-	}
+	__asm__ __volatile__(
+		/* Atomically increment the next ticket. */
+		"	amoadd.w.aqrl	%0, %4, %3\n"
+
+		/* Did we get the lock? */
+		"	srli	%1, %0, %6\n"
+		"	and	%1, %1, %5\n"
+		"1:	and	%2, %0, %5\n"
+		"	beq	%1, %2, 2f\n"
+
+		/* If not, then spin on the lock. */
+		"	lw	%0, %3\n"
+		RISCV_ACQUIRE_BARRIER
+		"	j	1b\n"
+		"2:"
+		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
+		: "memory");
 }
 
 void spin_unlock(spinlock_t *lock)
 {
-	__smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED);
+	__smp_store_release(&lock->owner, lock->owner + 1);
 }
+
--

2.30.2

#11 lore raw

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

In reply to Christoph Muellner

? 2021-04-06?? 03:53 +0200?Christoph Muellner???

Quoted 157 lines

Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).

The implementation uses a 32-bit wide struct, which consists of two 16-bit counters (owner and next). This is inspired by similar spinlock implementations on other architectures.
This allows that the code works for both, RV32 and RV64.

---
 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..492935f 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;
+#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+       u16 next;
+       u16 owner;
+#else
+       u16 owner;
+       u16 next;
+#endif
+} __aligned(4) spinlock_t;
+
+#define __SPIN_LOCK_UNLOCKED	\
+	(spinlock_t) { 0, 0 }
 
-#define __RISCV_SPIN_UNLOCKED 0
+#define SPIN_LOCK_INIT(x)	\
+	x = __SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INITIALIZER	\
+	__SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INITIALIZER                  \
-	{                                      \
-		.lock = __RISCV_SPIN_UNLOCKED, \
-	}
+#define DEFINE_SPIN_LOCK(x)	\
+	spinlock_t SPIN_LOCK_INIT(x)
 
 int spin_lock_check(spinlock_t *lock);
 
lib/sbi/riscv_locks.c +46 -16
index 4d1d9c0..7e607b0 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;
+	unsigned long inc = 1u << TICKET_SHIFT;
+	unsigned long mask = 0xffffu << TICKET_SHIFT;
+	u32 l0, tmp1, tmp2;
 
 	__asm__ __volatile__(
-		"	amoswap.w %0, %2, %1\n" RISCV_ACQUIRE_BARRIER
-		: "=r"(busy), "+A"(lock->lock)
-		: "r"(tmp)
+		/* Get the current lock counters. */
+		"1:	lr.w.aq	%0, %3\n"
+		"	slli	%2, %0, %6\n"
+		"	and	%2, %2, %5\n"
+		"	and	%1, %0, %5\n"
+		/* Is the lock free right now? */
+		"	bne	%1, %2, 2f\n"
+		"	add	%0, %0, %4\n"
+		/* Acquire the lock. */
+		"	sc.w.rl	%0, %0, %3\n"
+		"	bnez	%0, 1b\n"
+		"2:"
+		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
 		: "memory");
 
-	return !busy;
+	return !l0;
 }
 
 void spin_lock(spinlock_t *lock)
 {
-	while (1) {
-		if (spin_lock_check(lock))
-			continue;
+	unsigned long inc = 1u << TICKET_SHIFT;
+	unsigned long mask = 0xffffu;
+	u32 l0, tmp1, tmp2;
 
-		if (spin_trylock(lock))
-			break;
-	}
+	__asm__ __volatile__(
+		/* Atomically increment the next ticket. */
+		"	amoadd.w.aqrl	%0, %4, %3\n"
+
+		/* Did we get the lock? */
+		"	srli	%1, %0, %6\n"
+		"	and	%1, %1, %5\n"
+		"1:	and	%2, %0, %5\n"
+		"	beq	%1, %2, 2f\n"
+
+		/* If not, then spin on the lock. */
+		"	lw	%0, %3\n"
+		RISCV_ACQUIRE_BARRIER
+		"	j	1b\n"
+		"2:"
+		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)

lib/sbi/riscv_locks.c line 78

Quoted 10 lines
lib/sbi/riscv_locks.c +4 -1
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
+		: "memory");
 }
 
 void spin_unlock(spinlock_t *lock)
 {
-	__smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED);
+	__smp_store_release(&lock->owner, lock->owner + 1);
 }
+

Looks good to me.

Applied
#12 lore raw

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

Quoted 180 lines

-----Original Message-----
From: Xiang W <[email protected]>
Sent: 06 April 2021 11:20
To: Christoph Muellner <[email protected]>;
opensbi at lists.infradead.org; Anup Patel <[email protected]>; Guo Ren <[email protected]>; Jessica Clarke <[email protected]>
Subject: Re: [PATCH v3 3/3] spinlocks: Replace test-and-set locks by ticket locks

? 2021-04-06?? 03:53 +0200?Christoph Muellner???

Quoted 95 lines

Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order).

The implementation uses a 32-bit wide struct, which consists of two 16-bit counters (owner and next). This is inspired by similar spinlock implementations on other architectures.
This allows that the code works for both, RV32 and RV64.

---
 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..492935f 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;
+#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+       u16 next;
+       u16 owner;
+#else
+       u16 owner;
+       u16 next;
+#endif
+} __aligned(4) spinlock_t;
+
+#define __SPIN_LOCK_UNLOCKED	\
+	(spinlock_t) { 0, 0 }
 
-#define __RISCV_SPIN_UNLOCKED 0
+#define SPIN_LOCK_INIT(x)	\
+	x = __SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED
+#define SPIN_LOCK_INITIALIZER	\
+	__SPIN_LOCK_UNLOCKED
 
-#define SPIN_LOCK_INITIALIZER                  \
-	{                                      \
-		.lock = __RISCV_SPIN_UNLOCKED, \
-	}
+#define DEFINE_SPIN_LOCK(x)	\
+	spinlock_t SPIN_LOCK_INIT(x)
 
 int spin_lock_check(spinlock_t *lock);
 
lib/sbi/riscv_locks.c index renamed from lib/sbi/riscv_locks.c +0 -0

4d1d9c0..7e607b0 100644

lib/sbi/riscv_locks.c +7 -5
@@ -2,44 +2,77 @@
  * SPDX-License-Identifier: BSD-2-Clause
  *
  * Copyright (c) 2019 Western Digital Corporation or its affiliates.
- *
- * Authors:
- *   Anup Patel <[email protected]>
+ * Copyright (c) 2021 Christoph M?llner <[email protected]>
  */
 
 #include <sbi/riscv_barrier.h>
 #include <sbi/riscv_locks.h>
 
-int spin_lock_check(spinlock_t *lock)
+static inline int spin_lock_unlocked(spinlock_t lock)
 {
-	return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1;
+        return lock.owner == lock.next; }
+
+bool spin_lock_check(spinlock_t *lock) {
+	RISCV_FENCE(r, rw);
+	return !spin_lock_unlocked(*lock);
 }

lib/sbi/riscv_locks.c line 23

Quoted 10 lines
lib/sbi/riscv_locks.c +3 -2
 
 int spin_trylock(spinlock_t *lock)
 {
-	int tmp = 1, busy;
+	unsigned long inc = 1u << TICKET_SHIFT;
+	unsigned long mask = 0xffffu << TICKET_SHIFT;
+	u32 l0, tmp1, tmp2;
 
 	__asm__ __volatile__(
-		"	amoswap.w %0, %2, %1\n"

RISCV_ACQUIRE_BARRIER

Quoted 50 lines
lib/sbi/riscv_locks.c +34 -9
-		: "=r"(busy), "+A"(lock->lock)
-		: "r"(tmp)
+		/* Get the current lock counters. */
+		"1:	lr.w.aq	%0, %3\n"
+		"	slli	%2, %0, %6\n"
+		"	and	%2, %2, %5\n"
+		"	and	%1, %0, %5\n"
+		/* Is the lock free right now? */
+		"	bne	%1, %2, 2f\n"
+		"	add	%0, %0, %4\n"
+		/* Acquire the lock. */
+		"	sc.w.rl	%0, %0, %3\n"
+		"	bnez	%0, 1b\n"
+		"2:"
+		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
 		: "memory");
 
-	return !busy;
+	return !l0;
 }
 
 void spin_lock(spinlock_t *lock)
 {
-	while (1) {
-		if (spin_lock_check(lock))
-			continue;
+	unsigned long inc = 1u << TICKET_SHIFT;
+	unsigned long mask = 0xffffu;
+	u32 l0, tmp1, tmp2;
 
-		if (spin_trylock(lock))
-			break;
-	}
+	__asm__ __volatile__(
+		/* Atomically increment the next ticket. */
+		"	amoadd.w.aqrl	%0, %4, %3\n"
+
+		/* Did we get the lock? */
+		"	srli	%1, %0, %6\n"
+		"	and	%1, %1, %5\n"
+		"1:	and	%2, %0, %5\n"
+		"	beq	%1, %2, 2f\n"
+
+		/* If not, then spin on the lock. */
+		"	lw	%0, %3\n"
+		RISCV_ACQUIRE_BARRIER
+		"	j	1b\n"
+		"2:"
+		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)

lib/sbi/riscv_locks.c line 78

Quoted 10 lines
lib/sbi/riscv_locks.c +4 -1
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
+		: "memory");
 }
 
 void spin_unlock(spinlock_t *lock)
 {
-	__smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED);
+	__smp_store_release(&lock->owner, lock->owner + 1);
 }
+

Looks good to me.

Quoted 1 line

Replaces patch subject prefix "spinlocks:" with "lib: sbi:"

Applied this patch to the riscv/opensbi repo

Regards,
Anup