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

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

[Christoph Muellner]

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(-)

-- 
2.30.2

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

[Christoph Muellner]

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

Signed-off-by: Christoph Muellner <cmuellner@linux.com>
---
 include/sbi/sbi_types.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/include/sbi/sbi_types.h b/include/sbi/sbi_types.h
index 0952d5c..38e3565 100644
--- a/include/sbi/sbi_types.h
+++ b/include/sbi/sbi_types.h
@@ -63,6 +63,7 @@ typedef unsigned long		physical_size_t;
 
 #define __packed		__attribute__((packed))
 #define __noreturn		__attribute__((noreturn))
+#define __aligned(x)		__attribute__((aligned(x)))
 
 #define likely(x) __builtin_expect((x), 1)
 #define unlikely(x) __builtin_expect((x), 0)
-- 
2.30.2

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

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

Signed-off-by: Christoph Muellner <cmuellner@linux.com>
---
 include/sbi/riscv_locks.h | 2 +-
 lib/sbi/sbi_fifo.c        | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h
index 55da7c0..faa9676 100644
--- a/include/sbi/riscv_locks.h
+++ b/include/sbi/riscv_locks.h
@@ -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                  \
 	{                                      \
diff --git a/lib/sbi/sbi_fifo.c b/lib/sbi/sbi_fifo.c
index 8d1dbf0..2a5c012 100644
--- a/lib/sbi/sbi_fifo.c
+++ b/lib/sbi/sbi_fifo.c
@@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void *queue_mem, u16 entries,
 	fifo->queue	  = queue_mem;
 	fifo->num_entries = entries;
 	fifo->entry_size  = entry_size;
-	SPIN_LOCK_INIT(&fifo->qlock);
+	SPIN_LOCK_INIT(fifo->qlock);
 	fifo->avail = fifo->tail = 0;
 	sbi_memset(fifo->queue, 0, (size_t)entries * entry_size);
 }
-- 
2.30.2

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

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

Signed-off-by: Christoph Muellner <cmuellner@linux.com>
---
 include/sbi/riscv_locks.h | 33 ++++++++++++-------
 lib/sbi/riscv_locks.c     | 67 +++++++++++++++++++++++++++++----------
 2 files changed, 72 insertions(+), 28 deletions(-)

diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h
index faa9676..492935f 100644
--- a/include/sbi/riscv_locks.h
+++ b/include/sbi/riscv_locks.h
@@ -2,26 +2,37 @@
  * SPDX-License-Identifier: BSD-2-Clause
  *
  * Copyright (c) 2019 Western Digital Corporation or its affiliates.
- *
- * Authors:
- *   Anup Patel <anup.patel@wdc.com>
+ * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
  */
 
 #ifndef __RISCV_LOCKS_H__
 #define __RISCV_LOCKS_H__
 
+#include <sbi/sbi_types.h>
+
+#define TICKET_SHIFT	16
+
 typedef struct {
-	volatile long lock;
-} spinlock_t;
+#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);
 
diff --git a/lib/sbi/riscv_locks.c b/lib/sbi/riscv_locks.c
index 4d1d9c0..7e607b0 100644
--- a/lib/sbi/riscv_locks.c
+++ b/lib/sbi/riscv_locks.c
@@ -2,44 +2,77 @@
  * SPDX-License-Identifier: BSD-2-Clause
  *
  * Copyright (c) 2019 Western Digital Corporation or its affiliates.
- *
- * Authors:
- *   Anup Patel <anup.patel@wdc.com>
+ * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
  */
 
 #include <sbi/riscv_barrier.h>
 #include <sbi/riscv_locks.h>
 
-int spin_lock_check(spinlock_t *lock)
+static inline int spin_lock_unlocked(spinlock_t lock)
 {
-	return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1;
+        return lock.owner == lock.next;
+}
+
+bool spin_lock_check(spinlock_t *lock)
+{
+	RISCV_FENCE(r, rw);
+	return !spin_lock_unlocked(*lock);
 }
 
 int spin_trylock(spinlock_t *lock)
 {
-	int tmp = 1, busy;
+	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)
+		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
+		: "memory");
 }
 
 void spin_unlock(spinlock_t *lock)
 {
-	__smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED);
+	__smp_store_release(&lock->owner, lock->owner + 1);
 }
+
-- 
2.30.2

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

[Xiang W]

? 2021-04-06?? 03:53 +0200?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.
> 
> Signed-off-by: Christoph Muellner <cmuellner@linux.com>
> ---
>  include/sbi/riscv_locks.h | 33 ++++++++++++-------
>  lib/sbi/riscv_locks.c     | 67 +++++++++++++++++++++++++++++------
> ----
>  2 files changed, 72 insertions(+), 28 deletions(-)
> 
> diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h
> index faa9676..492935f 100644
> --- a/include/sbi/riscv_locks.h
> +++ b/include/sbi/riscv_locks.h
> @@ -2,26 +2,37 @@
>   * SPDX-License-Identifier: BSD-2-Clause
>   *
>   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> - *
> - * Authors:
> - *   Anup Patel <anup.patel@wdc.com>
> + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
>   */
>  
>  #ifndef __RISCV_LOCKS_H__
>  #define __RISCV_LOCKS_H__
>  
> +#include <sbi/sbi_types.h>
> +
> +#define TICKET_SHIFT	16
> +
>  typedef struct {
> -	volatile long lock;
> -} spinlock_t;
> +#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);
>  
> diff --git a/lib/sbi/riscv_locks.c b/lib/sbi/riscv_locks.c
> index 4d1d9c0..7e607b0 100644
> --- a/lib/sbi/riscv_locks.c
> +++ b/lib/sbi/riscv_locks.c
> @@ -2,44 +2,77 @@
>   * SPDX-License-Identifier: BSD-2-Clause
>   *
>   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> - *
> - * Authors:
> - *   Anup Patel <anup.patel@wdc.com>
> + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
>   */
>  
>  #include <sbi/riscv_barrier.h>
>  #include <sbi/riscv_locks.h>
>  
> -int spin_lock_check(spinlock_t *lock)
> +static inline int spin_lock_unlocked(spinlock_t lock)
>  {
> -	return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1;
> +        return lock.owner == lock.next;
> +}
> +
> +bool spin_lock_check(spinlock_t *lock)
> +{
> +	RISCV_FENCE(r, rw);
> +	return !spin_lock_unlocked(*lock);
>  }
>  
>  int spin_trylock(spinlock_t *lock)
>  {
> -	int tmp = 1, busy;
> +	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"
What we need to keep re-reading should be 'owner'

Regards,
Xiang W

> +		"	beq	%1, %2, 2f\n"
> +
> +		/* If not, then spin on the lock. */
> +		"	lw	%0, %3\n"
> +		RISCV_ACQUIRE_BARRIER
> +		"	j	1b\n"
> +		"2:"
> +		: "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock)
> +		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
> +		: "memory");
>  }
>  
>  void spin_unlock(spinlock_t *lock)
>  {
> -	__smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED);
> +	__smp_store_release(&lock->owner, lock->owner + 1);
>  }
> +
> -- 
> 2.30.2
> 
> 

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

[Anup Patel]

On Tue, Apr 6, 2021 at 8:45 AM Xiang W <wxjstz@126.com> wrote:
>
> ? 2021-04-06?? 03:53 +0200?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.
> >
> > Signed-off-by: Christoph Muellner <cmuellner@linux.com>
> > ---
> >  include/sbi/riscv_locks.h | 33 ++++++++++++-------
> >  lib/sbi/riscv_locks.c     | 67 +++++++++++++++++++++++++++++------
> > ----
> >  2 files changed, 72 insertions(+), 28 deletions(-)
> >
> > diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h
> > index faa9676..492935f 100644
> > --- a/include/sbi/riscv_locks.h
> > +++ b/include/sbi/riscv_locks.h
> > @@ -2,26 +2,37 @@
> >   * SPDX-License-Identifier: BSD-2-Clause
> >   *
> >   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> > - *
> > - * Authors:
> > - *   Anup Patel <anup.patel@wdc.com>
> > + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
> >   */
> >
> >  #ifndef __RISCV_LOCKS_H__
> >  #define __RISCV_LOCKS_H__
> >
> > +#include <sbi/sbi_types.h>
> > +
> > +#define TICKET_SHIFT 16
> > +
> >  typedef struct {
> > -     volatile long lock;
> > -} spinlock_t;
> > +#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);
> >
> > diff --git a/lib/sbi/riscv_locks.c b/lib/sbi/riscv_locks.c
> > index 4d1d9c0..7e607b0 100644
> > --- a/lib/sbi/riscv_locks.c
> > +++ b/lib/sbi/riscv_locks.c
> > @@ -2,44 +2,77 @@
> >   * SPDX-License-Identifier: BSD-2-Clause
> >   *
> >   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> > - *
> > - * Authors:
> > - *   Anup Patel <anup.patel@wdc.com>
> > + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
> >   */
> >
> >  #include <sbi/riscv_barrier.h>
> >  #include <sbi/riscv_locks.h>
> >
> > -int spin_lock_check(spinlock_t *lock)
> > +static inline int spin_lock_unlocked(spinlock_t lock)
> >  {
> > -     return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1;
> > +        return lock.owner == lock.next;
> > +}
> > +
> > +bool spin_lock_check(spinlock_t *lock)
> > +{
> > +     RISCV_FENCE(r, rw);
> > +     return !spin_lock_unlocked(*lock);
> >  }
> >
> >  int spin_trylock(spinlock_t *lock)
> >  {
> > -     int tmp = 1, busy;
> > +     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"
> What we need to keep re-reading should be 'owner'

Yes, the code is already doing that.

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

Regards,
Anup

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

[Anup Patel]

> -----Original Message-----
> From: Christoph Muellner <cmuellner@linux.com>
> Sent: 06 April 2021 07:24
> To: opensbi at lists.infradead.org; Anup Patel <Anup.Patel@wdc.com>; Guo
> Ren <guoren@kernel.org>; Xiang W <wxjstz@126.com>; Jessica Clarke
> <jrtc27@jrtc27.com>
> Cc: Christoph Muellner <cmuellner@linux.com>
> 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.
> 
> Signed-off-by: Christoph Muellner <cmuellner@linux.com>

Looks good to me.

Reviewed-by: Anup Patel <anup.patel@wdc.com>

Thanks,
Anup

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

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

[Anup Patel]

> -----Original Message-----
> From: Christoph Muellner <cmuellner@linux.com>
> Sent: 06 April 2021 07:24
> To: opensbi at lists.infradead.org; Anup Patel <Anup.Patel@wdc.com>; Guo
> Ren <guoren@kernel.org>; Xiang W <wxjstz@126.com>; Jessica Clarke
> <jrtc27@jrtc27.com>
> Cc: Christoph Muellner <cmuellner@linux.com>
> 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.
> 
> Let's pass the spinlock directly instead (like Linux does as well) and adjust all
> users of the macro (in fact there is only one user).
> 
> Signed-off-by: Christoph Muellner <cmuellner@linux.com>

Looks good to me.

Reviewed-by: Anup Patel <anup.patel@wdc.com>

Thanks,
Anup

> ---
>  include/sbi/riscv_locks.h | 2 +-
>  lib/sbi/sbi_fifo.c        | 2 +-
>  2 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h index
> 55da7c0..faa9676 100644
> --- a/include/sbi/riscv_locks.h
> +++ b/include/sbi/riscv_locks.h
> @@ -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                  \
>  	{                                      \
> diff --git a/lib/sbi/sbi_fifo.c b/lib/sbi/sbi_fifo.c index 8d1dbf0..2a5c012
> 100644
> --- a/lib/sbi/sbi_fifo.c
> +++ b/lib/sbi/sbi_fifo.c
> @@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void
> *queue_mem, u16 entries,
>  	fifo->queue	  = queue_mem;
>  	fifo->num_entries = entries;
>  	fifo->entry_size  = entry_size;
> -	SPIN_LOCK_INIT(&fifo->qlock);
> +	SPIN_LOCK_INIT(fifo->qlock);
>  	fifo->avail = fifo->tail = 0;
>  	sbi_memset(fifo->queue, 0, (size_t)entries * entry_size);  }
> --
> 2.30.2

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

[Anup Patel]

> -----Original Message-----
> From: Christoph Muellner <cmuellner@linux.com>
> Sent: 06 April 2021 07:24
> To: opensbi at lists.infradead.org; Anup Patel <Anup.Patel@wdc.com>; Guo
> Ren <guoren@kernel.org>; Xiang W <wxjstz@126.com>; Jessica Clarke
> <jrtc27@jrtc27.com>
> Cc: Christoph Muellner <cmuellner@linux.com>
> 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).
> 
> The implementation uses a 32-bit wide struct, which consists of two 16-bit
> counters (owner and next). This is inspired by similar spinlock
> implementations on other architectures.
> This allows that the code works for both, RV32 and RV64.
> 
> Signed-off-by: Christoph Muellner <cmuellner@linux.com>

Looks good to me.

Reviewed-by: Anup Patel <anup.patel@wdc.com>

Thanks,
Anup

> ---
>  include/sbi/riscv_locks.h | 33 ++++++++++++-------
>  lib/sbi/riscv_locks.c     | 67 +++++++++++++++++++++++++++++----------
>  2 files changed, 72 insertions(+), 28 deletions(-)
> 
> diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h index
> faa9676..492935f 100644
> --- a/include/sbi/riscv_locks.h
> +++ b/include/sbi/riscv_locks.h
> @@ -2,26 +2,37 @@
>   * SPDX-License-Identifier: BSD-2-Clause
>   *
>   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> - *
> - * Authors:
> - *   Anup Patel <anup.patel@wdc.com>
> + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
>   */
> 
>  #ifndef __RISCV_LOCKS_H__
>  #define __RISCV_LOCKS_H__
> 
> +#include <sbi/sbi_types.h>
> +
> +#define TICKET_SHIFT	16
> +
>  typedef struct {
> -	volatile long lock;
> -} spinlock_t;
> +#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);
> 
> diff --git a/lib/sbi/riscv_locks.c b/lib/sbi/riscv_locks.c index 4d1d9c0..7e607b0
> 100644
> --- a/lib/sbi/riscv_locks.c
> +++ b/lib/sbi/riscv_locks.c
> @@ -2,44 +2,77 @@
>   * SPDX-License-Identifier: BSD-2-Clause
>   *
>   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> - *
> - * Authors:
> - *   Anup Patel <anup.patel@wdc.com>
> + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
>   */
> 
>  #include <sbi/riscv_barrier.h>
>  #include <sbi/riscv_locks.h>
> 
> -int spin_lock_check(spinlock_t *lock)
> +static inline int spin_lock_unlocked(spinlock_t lock)
>  {
> -	return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1;
> +        return lock.owner == lock.next; }
> +
> +bool spin_lock_check(spinlock_t *lock)
> +{
> +	RISCV_FENCE(r, rw);
> +	return !spin_lock_unlocked(*lock);
>  }
> 
>  int spin_trylock(spinlock_t *lock)
>  {
> -	int tmp = 1, busy;
> +	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)
> +		: "r"(inc), "r"(mask), "I"(TICKET_SHIFT)
> +		: "memory");
>  }
> 
>  void spin_unlock(spinlock_t *lock)
>  {
> -	__smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED);
> +	__smp_store_release(&lock->owner, lock->owner + 1);
>  }
> +
> --
> 2.30.2

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

[Xiang W]

? 2021-04-06?? 03:53 +0200?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.
> 
> Signed-off-by: Christoph Muellner <cmuellner@linux.com>
> ---
>  include/sbi/riscv_locks.h | 33 ++++++++++++-------
>  lib/sbi/riscv_locks.c     | 67 +++++++++++++++++++++++++++++------
> ----
>  2 files changed, 72 insertions(+), 28 deletions(-)
> 
> diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h
> index faa9676..492935f 100644
> --- a/include/sbi/riscv_locks.h
> +++ b/include/sbi/riscv_locks.h
> @@ -2,26 +2,37 @@
>   * SPDX-License-Identifier: BSD-2-Clause
>   *
>   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> - *
> - * Authors:
> - *   Anup Patel <anup.patel@wdc.com>
> + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
>   */
>  
>  #ifndef __RISCV_LOCKS_H__
>  #define __RISCV_LOCKS_H__
>  
> +#include <sbi/sbi_types.h>
> +
> +#define TICKET_SHIFT	16
> +
>  typedef struct {
> -	volatile long lock;
> -} spinlock_t;
> +#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);
>  
> diff --git a/lib/sbi/riscv_locks.c b/lib/sbi/riscv_locks.c
> index 4d1d9c0..7e607b0 100644
> --- a/lib/sbi/riscv_locks.c
> +++ b/lib/sbi/riscv_locks.c
> @@ -2,44 +2,77 @@
>   * SPDX-License-Identifier: BSD-2-Clause
>   *
>   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> - *
> - * Authors:
> - *   Anup Patel <anup.patel@wdc.com>
> + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
>   */
>  
>  #include <sbi/riscv_barrier.h>
>  #include <sbi/riscv_locks.h>
>  
> -int spin_lock_check(spinlock_t *lock)
> +static inline int spin_lock_unlocked(spinlock_t lock)
>  {
> -	return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1;
> +        return lock.owner == lock.next;
> +}
> +
> +bool spin_lock_check(spinlock_t *lock)
> +{
> +	RISCV_FENCE(r, rw);
> +	return !spin_lock_unlocked(*lock);
>  }
>  
>  int spin_trylock(spinlock_t *lock)
>  {
> -	int tmp = 1, busy;
> +	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)
> +		: "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.

Reviewed-by: Xiang W <wxjstz@126.com>

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

[Anup Patel]

> -----Original Message-----
> From: Anup Patel
> Sent: 06 April 2021 10:36
> To: Christoph Muellner <cmuellner@linux.com>;
> opensbi at lists.infradead.org; Guo Ren <guoren@kernel.org>; Xiang W
> <wxjstz@126.com>; Jessica Clarke <jrtc27@jrtc27.com>
> Subject: RE: [PATCH v3 1/3] include: types: Add __aligned(x) to define the
> minimum alignement
> 
> 
> 
> > -----Original Message-----
> > From: Christoph Muellner <cmuellner@linux.com>
> > Sent: 06 April 2021 07:24
> > To: opensbi at lists.infradead.org; Anup Patel <Anup.Patel@wdc.com>; Guo
> > Ren <guoren@kernel.org>; Xiang W <wxjstz@126.com>; Jessica Clarke
> > <jrtc27@jrtc27.com>
> > Cc: Christoph Muellner <cmuellner@linux.com>
> > 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.
> >
> > Signed-off-by: Christoph Muellner <cmuellner@linux.com>
> 
> Looks good to me.
> 
> Reviewed-by: Anup Patel <anup.patel@wdc.com>

Applied this patch to the riscv/opensbi repo

Regards,
Anup

> 
> Thanks,
> Anup
> 
> > ---
> >  include/sbi/sbi_types.h | 1 +
> >  1 file changed, 1 insertion(+)
> >
> > diff --git a/include/sbi/sbi_types.h b/include/sbi/sbi_types.h index
> > 0952d5c..38e3565 100644
> > --- a/include/sbi/sbi_types.h
> > +++ b/include/sbi/sbi_types.h
> > @@ -63,6 +63,7 @@ typedef unsigned long		physical_size_t;
> >
> >  #define __packed		__attribute__((packed))
> >  #define __noreturn		__attribute__((noreturn))
> > +#define __aligned(x)		__attribute__((aligned(x)))
> >
> >  #define likely(x) __builtin_expect((x), 1)  #define unlikely(x)
> > __builtin_expect((x), 0)
> > --
> > 2.30.2

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

[Anup Patel]

> -----Original Message-----
> From: Anup Patel
> Sent: 06 April 2021 10:37
> To: Christoph Muellner <cmuellner@linux.com>;
> opensbi at lists.infradead.org; Guo Ren <guoren@kernel.org>; Xiang W
> <wxjstz@126.com>; Jessica Clarke <jrtc27@jrtc27.com>
> Subject: RE: [PATCH v3 2/3] spinlocks: Allow direct initialization via
> SPIN_LOCK_INIT()
> 
> 
> 
> > -----Original Message-----
> > From: Christoph Muellner <cmuellner@linux.com>
> > Sent: 06 April 2021 07:24
> > To: opensbi at lists.infradead.org; Anup Patel <Anup.Patel@wdc.com>; Guo
> > Ren <guoren@kernel.org>; Xiang W <wxjstz@126.com>; Jessica Clarke
> > <jrtc27@jrtc27.com>
> > Cc: Christoph Muellner <cmuellner@linux.com>
> > 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.
> >
> > Let's pass the spinlock directly instead (like Linux does as well) and
> > adjust all users of the macro (in fact there is only one user).
> >
> > Signed-off-by: Christoph Muellner <cmuellner@linux.com>
> 
> Looks good to me.
> 
> Reviewed-by: Anup Patel <anup.patel@wdc.com>

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

Applied this patch to the riscv/opensbi repo

Regards,
Anup

> 
> Thanks,
> Anup
> 
> > ---
> >  include/sbi/riscv_locks.h | 2 +-
> >  lib/sbi/sbi_fifo.c        | 2 +-
> >  2 files changed, 2 insertions(+), 2 deletions(-)
> >
> > diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h
> > index
> > 55da7c0..faa9676 100644
> > --- a/include/sbi/riscv_locks.h
> > +++ b/include/sbi/riscv_locks.h
> > @@ -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                  \
> >  	{                                      \
> > diff --git a/lib/sbi/sbi_fifo.c b/lib/sbi/sbi_fifo.c index
> > 8d1dbf0..2a5c012
> > 100644
> > --- a/lib/sbi/sbi_fifo.c
> > +++ b/lib/sbi/sbi_fifo.c
> > @@ -18,7 +18,7 @@ void sbi_fifo_init(struct sbi_fifo *fifo, void
> > *queue_mem, u16 entries,
> >  	fifo->queue	  = queue_mem;
> >  	fifo->num_entries = entries;
> >  	fifo->entry_size  = entry_size;
> > -	SPIN_LOCK_INIT(&fifo->qlock);
> > +	SPIN_LOCK_INIT(fifo->qlock);
> >  	fifo->avail = fifo->tail = 0;
> >  	sbi_memset(fifo->queue, 0, (size_t)entries * entry_size);  }
> > --
> > 2.30.2

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

[Anup Patel]

> -----Original Message-----
> From: Xiang W <wxjstz@126.com>
> Sent: 06 April 2021 11:20
> To: Christoph Muellner <cmuellner@linux.com>;
> opensbi at lists.infradead.org; Anup Patel <Anup.Patel@wdc.com>; Guo Ren
> <guoren@kernel.org>; Jessica Clarke <jrtc27@jrtc27.com>
> Subject: Re: [PATCH v3 3/3] spinlocks: Replace test-and-set locks by ticket
> locks
> 
> ? 2021-04-06?? 03:53 +0200?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.
> >
> > Signed-off-by: Christoph Muellner <cmuellner@linux.com>
> > ---
> >  include/sbi/riscv_locks.h | 33 ++++++++++++-------
> >  lib/sbi/riscv_locks.c     | 67 +++++++++++++++++++++++++++++------
> > ----
> >  2 files changed, 72 insertions(+), 28 deletions(-)
> >
> > diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h
> > index faa9676..492935f 100644
> > --- a/include/sbi/riscv_locks.h
> > +++ b/include/sbi/riscv_locks.h
> > @@ -2,26 +2,37 @@
> >   * SPDX-License-Identifier: BSD-2-Clause
> >   *
> >   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> > - *
> > - * Authors:
> > - *   Anup Patel <anup.patel@wdc.com>
> > + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
> >   */
> >
> >  #ifndef __RISCV_LOCKS_H__
> >  #define __RISCV_LOCKS_H__
> >
> > +#include <sbi/sbi_types.h>
> > +
> > +#define TICKET_SHIFT	16
> > +
> >  typedef struct {
> > -	volatile long lock;
> > -} spinlock_t;
> > +#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);
> >
> > diff --git a/lib/sbi/riscv_locks.c b/lib/sbi/riscv_locks.c index
> > 4d1d9c0..7e607b0 100644
> > --- a/lib/sbi/riscv_locks.c
> > +++ b/lib/sbi/riscv_locks.c
> > @@ -2,44 +2,77 @@
> >   * SPDX-License-Identifier: BSD-2-Clause
> >   *
> >   * Copyright (c) 2019 Western Digital Corporation or its affiliates.
> > - *
> > - * Authors:
> > - *   Anup Patel <anup.patel@wdc.com>
> > + * Copyright (c) 2021 Christoph M?llner <cmuellner@linux.com>
> >   */
> >
> >  #include <sbi/riscv_barrier.h>
> >  #include <sbi/riscv_locks.h>
> >
> > -int spin_lock_check(spinlock_t *lock)
> > +static inline int spin_lock_unlocked(spinlock_t lock)
> >  {
> > -	return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1;
> > +        return lock.owner == lock.next; }
> > +
> > +bool spin_lock_check(spinlock_t *lock) {
> > +	RISCV_FENCE(r, rw);
> > +	return !spin_lock_unlocked(*lock);
> >  }
> >
> >  int spin_trylock(spinlock_t *lock)
> >  {
> > -	int tmp = 1, busy;
> > +	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)
> > +		: "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.
> 
> Reviewed-by: Xiang W <wxjstz@126.com>

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

Applied this patch to the riscv/opensbi repo

Regards,
Anup