riscv: Add qspinlock/qrwlock

From: Guo Ren <[email protected]>

To reduce assembly codes, let's merge duplicate codes into one (xchg_acquire, xchg_release, cmpxchg_release).

Signed-off-by Guo Ren <[email protected]>

Quoted 3 lines · On Sat, Mar 27, 2021 at 7:06 PM <[email protected]> wrote:

From: Guo Ren <[email protected]>

Quoted 4 lines

To reduce assembly codes, let's merge duplicate codes into one (xchg_acquire, xchg_release, cmpxchg_release).

Signed-off-by Guo Ren <[email protected]>

This is a nice cleanup, but I wonder if you can go even further by using the definitions from atomic-arch-fallback.h like arm64 and x86 do.

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

Signed-off-by Guo Ren <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Will Deacon <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Waiman Long <[email protected]>

Cc Arnd Bergmann <[email protected]>

Cc Anup Patel <[email protected]>

---
  kernel/Kconfig.locks       |  3 +++
  kernel/locking/qspinlock.c | 44 +++++++++++++++++++++-----------------
  2 files changed, 27 insertions(+), 20 deletions(-)

kernel/Kconfig.locks +3 -0

index 3de8fd11873b..d02f1261f73f 100644
@@ -239,6 +239,9 @@ config LOCK_SPIN_ON_OWNER
  config ARCH_USE_QUEUED_SPINLOCKS
  	bool
 
+config ARCH_USE_QUEUED_SPINLOCKS_XCHG32
+	bool
+
  config QUEUED_SPINLOCKS
  	def_bool y if ARCH_USE_QUEUED_SPINLOCKS
  	depends on SMP

kernel/locking/qspinlock.c +17 -20

index cbff6ba53d56..54de0632c6a8 100644
@@ -163,26 +163,6 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
  	WRITE_ONCE(lock->locked_pending, _Q_LOCKED_VAL);
  }
 
-/*
- * xchg_tail - Put in the new queue tail code word & retrieve previous one
- * @lock : Pointer to queued spinlock structure
- * @tail : The new queue tail code word
- * Return: The previous queue tail code word
- *
- * xchg(lock, tail), which heads an address dependency
- *
- * p,*,* -> n,*,* ; prev = xchg(lock, node)
- */
-static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
-{
-	/*
-	 * We can use relaxed semantics since the caller ensures that the
-	 * MCS node is properly initialized before updating the tail.
-	 */
-	return (u32)xchg_relaxed(&lock->tail,
-				 tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET;
-}
-
  #else /* _Q_PENDING_BITS == 8 */
 
  /**

@@ -206,6 +186,30 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
  {
  	atomic_add(-_Q_PENDING_VAL + _Q_LOCKED_VAL, &lock->val);
  }
+#endif
+
+#if _Q_PENDING_BITS == 8 && !defined(CONFIG_ARCH_USE_QUEUED_SPINLOCKS_XCHG32)
+/*
+ * xchg_tail - Put in the new queue tail code word & retrieve previous one
+ * @lock : Pointer to queued spinlock structure
+ * @tail : The new queue tail code word
+ * Return: The previous queue tail code word
+ *
+ * xchg(lock, tail), which heads an address dependency
+ *
+ * p,*,* -> n,*,* ; prev = xchg(lock, node)
+ */
+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+	/*
+	 * We can use relaxed semantics since the caller ensures that the

Quoted 104 lines · On 3/27/21 2:06 PM, [email protected] wrote:

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

Signed-off-by Guo Ren <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Will Deacon <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Waiman Long <[email protected]>

Cc Arnd Bergmann <[email protected]>

Cc Anup Patel <[email protected]>

---
  kernel/Kconfig.locks       |  3 +++
  kernel/locking/qspinlock.c | 44 +++++++++++++++++++++-----------------
  2 files changed, 27 insertions(+), 20 deletions(-)

kernel/Kconfig.locks +3 -0

index 3de8fd11873b..d02f1261f73f 100644
@@ -239,6 +239,9 @@ config LOCK_SPIN_ON_OWNER
  config ARCH_USE_QUEUED_SPINLOCKS
      bool
 
+config ARCH_USE_QUEUED_SPINLOCKS_XCHG32
+     bool
+
  config QUEUED_SPINLOCKS
      def_bool y if ARCH_USE_QUEUED_SPINLOCKS
      depends on SMP

kernel/locking/qspinlock.c +24 -20

index cbff6ba53d56..54de0632c6a8 100644
@@ -163,26 +163,6 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
      WRITE_ONCE(lock->locked_pending, _Q_LOCKED_VAL);
  }
 
-/*
- * xchg_tail - Put in the new queue tail code word & retrieve previous one
- * @lock : Pointer to queued spinlock structure
- * @tail : The new queue tail code word
- * Return: The previous queue tail code word
- *
- * xchg(lock, tail), which heads an address dependency
- *
- * p,*,* -> n,*,* ; prev = xchg(lock, node)
- */
-static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
-{
-     /*
-      * We can use relaxed semantics since the caller ensures that the
-      * MCS node is properly initialized before updating the tail.
-      */
-     return (u32)xchg_relaxed(&lock->tail,
-                              tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET;
-}
-
  #else /* _Q_PENDING_BITS == 8 */
 
  /**

@@ -206,6 +186,30 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
  {
      atomic_add(-_Q_PENDING_VAL + _Q_LOCKED_VAL, &lock->val);
  }
+#endif
+
+#if _Q_PENDING_BITS == 8 && !defined(CONFIG_ARCH_USE_QUEUED_SPINLOCKS_XCHG32)
+/*
+ * xchg_tail - Put in the new queue tail code word & retrieve previous one
+ * @lock : Pointer to queued spinlock structure
+ * @tail : The new queue tail code word
+ * Return: The previous queue tail code word
+ *
+ * xchg(lock, tail), which heads an address dependency
+ *
+ * p,*,* -> n,*,* ; prev = xchg(lock, node)
+ */
+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+     /*
+      * We can use relaxed semantics since the caller ensures that the
+      * MCS node is properly initialized before updating the tail.
+      */
+     return (u32)xchg_relaxed(&lock->tail,
+                              tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET;
+}
+
+#else
 

kernel/locking/qspinlock.c static __always_inline void clear_pending_set_locked(struct qspinlock *lock) · line 215

Quoted 2 lines

kernel/locking/qspinlock.c +0 -0

  /**
   * xchg_tail - Put in the new queue tail code word & retrieve previous one

I don't have any problem adding a CONFIG_ARCH_USE_QUEUED_SPINLOCKS_XCHG32 config option to control that.

One minor nit:

#endif /* _Q_PENDING_BITS == 8 */

You should probably remove the comment at the trailing end of the corresponding "#endif" as it is now wrong.

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

Quoted 13 lines · On Sat, Mar 27, 2021 at 06:06:38PM +0000, [email protected] wrote:

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

Quoted 4 lines

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

So I really don't like this, this pushes complexity into the generic code for something that's really not needed.

Lots of RISC already implement sub-word atomics using word ll/sc. Obviously they're not sharing code like they should be :/ See for example arch/mips/kernel/cmpxchg.c.

Also, I really do think doing ticket locks first is a far more sensible step.

Quoted 19 lines · Peter Zijlstra

Quoted 13 lines · On Sat, Mar 27, 2021 at 06:06:38PM +0000, [email protected] wrote:

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

Quoted 4 lines

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

Quoted 6 lines

So I really don't like this, this pushes complexity into the generic code for something that's really not needed.

Lots of RISC already implement sub-word atomics using word ll/sc. Obviously they're not sharing code like they should be :/ See for example arch/mips/kernel/cmpxchg.c.

That is what the previous version of the patch set did, right?

I think this v4 is nicer because the code is already there in qspinlock.c and just gets moved around, and the implementation is likely more efficient this way. The mips version could be made more generic, but it is also less efficient than a simple xchg since it requires an indirect function call plus nesting a pair of loops instead in place of the single single ll/sc loop in the 32-bit xchg.

I think the weakly typed xchg/cmpxchg implementation causes more problems than it solves, and we'd be better off using a stronger version in general, with the 8-bit and 16-bit exchanges using separate helpers in the same way that the fixed-length cmpxchg64 is separate already, there are only a couple of instances for each of these in the kernel.

Unfortunately, there is roughly a 50:50 split between fixed 32-bit and long/pointer-sized xchg/cmpxchg users in the kernel, so making the interface completely fixed-type would add a ton of churn. I created an experimental patch for this, but it's probably not worth it.

Anyway, an additional 'funny' is that I suspect you cannot prove fwd progress of the entire primitive with any of this on. But who cares about details anyway.. :/

Quoted 3 lines · Peter Zijlstra

Anyway, an additional 'funny' is that I suspect you cannot prove fwd progress of the entire primitive with any of this on. But who cares about details anyway.. :/

What's the architectural guarantee on LL/SC progress for RISC-V ?

And what if you double loop it like cmpxchg() ?

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines · Peter Zijlstra

Anyway, an additional 'funny' is that I suspect you cannot prove fwd progress of the entire primitive with any of this on. But who cares about details anyway.. :/

What's the architectural guarantee on LL/SC progress for RISC-V ?

funct5    | aq | rl   | rs2 |  rs1  | funct3 | rd | opcode
     5          1    1      5       5         3        5          7
LR.W/D  ordering  0     addr    width   dest    AMO
SC.W/D  ordering  src  addr    width   dest    AMO

LR.W loads a word from the address in rs1, places the sign-extended value in rd, and registers a reservation set—a set of bytes that subsumes the bytes in the addressed word. SC.W conditionally writes a word in rs2 to the address in rs1: the SC.W succeeds only if the reservation is still valid and the reservation set contains the bytes being written. If the SC.W succeeds, the instruction writes the word in rs2 to memory, and it writes zero to rd. If the SC.W fails, the instruction does not write to memory, and it writes a nonzero value to rd. Regardless of success or failure, executing an SC.W instruction *invalidates any reservation held by this hart*.

More details, ref:
https://github.com/riscv/riscv-isa-manual

Quoted 26 lines · Guo Ren

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines · Peter Zijlstra

Anyway, an additional 'funny' is that I suspect you cannot prove fwd progress of the entire primitive with any of this on. But who cares about details anyway.. :/

What's the architectural guarantee on LL/SC progress for RISC-V ?

funct5    | aq | rl   | rs2 |  rs1  | funct3 | rd | opcode
     5          1    1      5       5         3        5          7
LR.W/D  ordering  0     addr    width   dest    AMO
SC.W/D  ordering  src  addr    width   dest    AMO

LR.W loads a word from the address in rs1, places the sign-extended value in rd, and registers a reservation set—a set of bytes that subsumes the bytes in the addressed word. SC.W conditionally writes a word in rs2 to the address in rs1: the SC.W succeeds only if the reservation is still valid and the reservation set contains the bytes being written. If the SC.W succeeds, the instruction writes the word in rs2 to memory, and it writes zero to rd. If the SC.W fails, the instruction does not write to memory, and it writes a nonzero value to rd. Regardless of success or failure, executing an SC.W instruction *invalidates any reservation held by this hart*.

Quoted 2 lines

More details, ref:
https://github.com/riscv/riscv-isa-manual

I think section "3.5.3.2 Reservability PMA" [1] would be a more relevant link, as this defines memory areas that either do or do not have forward progress guarantees, including this part:

"When LR/SC is used for memory locations marked RsrvNonEventual,
software should provide alternative fall-back mechanisms used when lack of progress is detected."

My reading of this is that if the example you tried stalls, then either the PMA is not RsrvEventual, and it is wrong to rely on ll/sc on this, or that the PMA is marked RsrvEventual but the implementation is buggy.

It also seems that the current "amoswap" based implementation would be reliable independent of RsrvEventual/RsrvNonEventual.

arm64 is already in the situation of having to choose between two cmpxchg() implementation at runtime to allow falling back to a slower but more general version, but it's best to avoid that if you can.

Arnd

[1] http://www.five-embeddev.com/riscv-isa-manual/latest/machine.html#atomicity-pmas

Quoted 35 lines · Arnd Bergmann

Quoted 26 lines · Guo Ren

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines · Peter Zijlstra

Anyway, an additional 'funny' is that I suspect you cannot prove fwd progress of the entire primitive with any of this on. But who cares about details anyway.. :/

What's the architectural guarantee on LL/SC progress for RISC-V ?

funct5    | aq | rl   | rs2 |  rs1  | funct3 | rd | opcode
     5          1    1      5       5         3        5          7
LR.W/D  ordering  0     addr    width   dest    AMO
SC.W/D  ordering  src  addr    width   dest    AMO

LR.W loads a word from the address in rs1, places the sign-extended value in rd, and registers a reservation set—a set of bytes that subsumes the bytes in the addressed word. SC.W conditionally writes a word in rs2 to the address in rs1: the SC.W succeeds only if the reservation is still valid and the reservation set contains the bytes being written. If the SC.W succeeds, the instruction writes the word in rs2 to memory, and it writes zero to rd. If the SC.W fails, the instruction does not write to memory, and it writes a nonzero value to rd. Regardless of success or failure, executing an SC.W instruction *invalidates any reservation held by this hart*.

Quoted 2 lines

More details, ref:
https://github.com/riscv/riscv-isa-manual

I think section "3.5.3.2 Reservability PMA" [1] would be a more relevant link, as this defines memory areas that either do or do not have forward progress guarantees, including this part:

Quoted 8 lines

"When LR/SC is used for memory locations marked RsrvNonEventual,
software should provide alternative fall-back mechanisms used when lack of progress is detected."

My reading of this is that if the example you tried stalls, then either the PMA is not RsrvEventual, and it is wrong to rely on ll/sc on this, or that the PMA is marked RsrvEventual but the implementation is buggy.

Yes, PMA just defines physical memory region attributes, But in our processor, when MMU is enabled (satp's value register > 2) in s-mode, it will look at our custom PTE's attributes BIT(63) ref [1]:

PTE format:

   | 63 | 62 | 61 | 60 | 59 | 58-8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0
     SO   C    B    SH   SE    RSW   D   A   G   U   X   W   R   V
     ^    ^    ^    ^    ^

BIT(63): SO - Strong Order
BIT(62): C - Cacheable
BIT(61): B - Bufferable
BIT(60): SH - Shareable
BIT(59): SE - Security

So the memory also could be RsrvNone/RsrvEventual.

[1] https://github.com/c-sky/csky-linux/commit/e837aad23148542771794d8a2fcc52afd0fcbf88

Quoted 4 lines

It also seems that the current "amoswap" based implementation would be reliable independent of RsrvEventual/RsrvNonEventual.

Yes, the hardware implementation of AMO could be different from LR/SC. AMO could use ACE snoop holding to lock the bus in hw coherency design, but LR/SC uses an exclusive monitor without locking the bus.

Quoted 4 lines

arm64 is already in the situation of having to choose between two cmpxchg() implementation at runtime to allow falling back to a slower but more general version, but it's best to avoid that if you can.

Current RISC-V needn't multiple versions to select, and all AMO & LR/SC has been defined in the spec.

RISC-V hasn't CAS instructions, and it uses LR/SC for cmpxchg. I don't think LR/SC would be slower than CAS, and CAS is just good for code size.

Quoted 3 lines

Arnd

Quoted 1 line

[1] http://www.five-embeddev.com/riscv-isa-manual/latest/machine.html#atomicity-pmas

--
Best Regards
Guo Ren

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

Quoted 59 lines · Guo Ren

Quoted 35 lines · Arnd Bergmann

Quoted 26 lines · Guo Ren

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines · Peter Zijlstra

Anyway, an additional 'funny' is that I suspect you cannot prove fwd progress of the entire primitive with any of this on. But who cares about details anyway.. :/

What's the architectural guarantee on LL/SC progress for RISC-V ?

funct5    | aq | rl   | rs2 |  rs1  | funct3 | rd | opcode
     5          1    1      5       5         3        5          7
LR.W/D  ordering  0     addr    width   dest    AMO
SC.W/D  ordering  src  addr    width   dest    AMO

LR.W loads a word from the address in rs1, places the sign-extended value in rd, and registers a reservation set—a set of bytes that subsumes the bytes in the addressed word. SC.W conditionally writes a word in rs2 to the address in rs1: the SC.W succeeds only if the reservation is still valid and the reservation set contains the bytes being written. If the SC.W succeeds, the instruction writes the word in rs2 to memory, and it writes zero to rd. If the SC.W fails, the instruction does not write to memory, and it writes a nonzero value to rd. Regardless of success or failure, executing an SC.W instruction *invalidates any reservation held by this hart*.

Quoted 2 lines

More details, ref:
https://github.com/riscv/riscv-isa-manual

I think section "3.5.3.2 Reservability PMA" [1] would be a more relevant link, as this defines memory areas that either do or do not have forward progress guarantees, including this part:

Quoted 8 lines

"When LR/SC is used for memory locations marked RsrvNonEventual,
software should provide alternative fall-back mechanisms used when lack of progress is detected."

My reading of this is that if the example you tried stalls, then either the PMA is not RsrvEventual, and it is wrong to rely on ll/sc on this, or that the PMA is marked RsrvEventual but the implementation is buggy.

Yes, PMA just defines physical memory region attributes, But in our processor, when MMU is enabled (satp's value register > 2) in s-mode, it will look at our custom PTE's attributes BIT(63) ref [1]:

PTE format:

   | 63 | 62 | 61 | 60 | 59 | 58-8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0
     SO   C    B    SH   SE    RSW   D   A   G   U   X   W   R   V
     ^    ^    ^    ^    ^

BIT(63): SO - Strong Order
BIT(62): C - Cacheable
BIT(61): B - Bufferable
BIT(60): SH - Shareable
BIT(59): SE - Security

Quoted 3 lines

So the memory also could be RsrvNone/RsrvEventual.

[1] https://github.com/c-sky/csky-linux/commit/e837aad23148542771794d8a2fcc52afd0fcbf88

Is this about your C-sky architecture or your RISC-V implementation.

If these PTE bits are in your RISC-V implementation then clearly your RISC-V implementation is not compliant with the RISC-V privilege spec because these bits are not defined in RISC-V privilege spec.

Regards,
Anup

Quoted 29 lines

Quoted 4 lines

It also seems that the current "amoswap" based implementation would be reliable independent of RsrvEventual/RsrvNonEventual.

Yes, the hardware implementation of AMO could be different from LR/SC. AMO could use ACE snoop holding to lock the bus in hw coherency design, but LR/SC uses an exclusive monitor without locking the bus.

Quoted 4 lines

arm64 is already in the situation of having to choose between two cmpxchg() implementation at runtime to allow falling back to a slower but more general version, but it's best to avoid that if you can.

Current RISC-V needn't multiple versions to select, and all AMO & LR/SC has been defined in the spec.

RISC-V hasn't CAS instructions, and it uses LR/SC for cmpxchg. I don't think LR/SC would be slower than CAS, and CAS is just good for code size.

Quoted 4 lines

Arnd

[1] http://www.five-embeddev.com/riscv-isa-manual/latest/machine.html#atomicity-pmas

--
Best Regards
Guo Ren

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

Quoted 5 lines · Arnd Bergmann

Quoted 3 lines · Guo Ren

Quoted 2 lines · Peter Zijlstra

What's the architectural guarantee on LL/SC progress for RISC-V ?

Quoted 8 lines

"When LR/SC is used for memory locations marked RsrvNonEventual,
software should provide alternative fall-back mechanisms used when lack of progress is detected."

My reading of this is that if the example you tried stalls, then either the PMA is not RsrvEventual, and it is wrong to rely on ll/sc on this, or that the PMA is marked RsrvEventual but the implementation is buggy.

Yes, PMA just defines physical memory region attributes, But in our processor, when MMU is enabled (satp's value register > 2) in s-mode, it will look at our custom PTE's attributes BIT(63) ref [1]:

PTE format:

   | 63 | 62 | 61 | 60 | 59 | 58-8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0
     SO   C    B    SH   SE    RSW   D   A   G   U   X   W   R   V
     ^    ^    ^    ^    ^

BIT(63): SO - Strong Order
BIT(62): C - Cacheable
BIT(61): B - Bufferable
BIT(60): SH - Shareable
BIT(59): SE - Security

So the memory also could be RsrvNone/RsrvEventual.

[1] https://github.com/c-sky/csky-linux/commit/e837aad23148542771794d8a2fcc52afd0fcbf88

Quoted 3 lines

It also seems that the current "amoswap" based implementation would be reliable independent of RsrvEventual/RsrvNonEventual.

Yes, the hardware implementation of AMO could be different from LR/SC. AMO could use ACE snoop holding to lock the bus in hw coherency design, but LR/SC uses an exclusive monitor without locking the bus.

RISC-V hasn't CAS instructions, and it uses LR/SC for cmpxchg. I don't think LR/SC would be slower than CAS, and CAS is just good for code size.

Quoted 23 lines · Guo Ren

Quoted 5 lines · Arnd Bergmann

Quoted 3 lines · Guo Ren

Quoted 2 lines · Peter Zijlstra

What's the architectural guarantee on LL/SC progress for RISC-V ?

Quoted 8 lines

"When LR/SC is used for memory locations marked RsrvNonEventual,
software should provide alternative fall-back mechanisms used when lack of progress is detected."

My reading of this is that if the example you tried stalls, then either the PMA is not RsrvEventual, and it is wrong to rely on ll/sc on this, or that the PMA is marked RsrvEventual but the implementation is buggy.

Yes, PMA just defines physical memory region attributes, But in our processor, when MMU is enabled (satp's value register > 2) in s-mode, it will look at our custom PTE's attributes BIT(63) ref [1]:

PTE format:

   | 63 | 62 | 61 | 60 | 59 | 58-8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0
     SO   C    B    SH   SE    RSW   D   A   G   U   X   W   R   V
     ^    ^    ^    ^    ^

Quoted 7 lines

BIT(63): SO - Strong Order
BIT(62): C - Cacheable
BIT(61): B - Bufferable
BIT(60): SH - Shareable
BIT(59): SE - Security

So the memory also could be RsrvNone/RsrvEventual.

I was not talking about RsrvNone, which would clearly mean that you cannot use lr/sc at all (trap would trap, right?), but "RsrvNonEventual", which would explain the behavior you described in an earlier reply:

| u32 a = 0x55aa66bb;
| u16 *ptr = &a;
|
| CPU0                       CPU1
| =========             =========
| xchg16(ptr, new)     while(1)
|                                     WRITE_ONCE(*(ptr + 1), x);
|
| When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

As I understand, this example must not cause a deadlock on a compliant hardware implementation when the underlying memory has RsrvEventual behavior, but could deadlock in case of RsrvNonEventual

Quoted 11 lines

[1] https://github.com/c-sky/csky-linux/commit/e837aad23148542771794d8a2fcc52afd0fcbf88

Quoted 3 lines

It also seems that the current "amoswap" based implementation would be reliable independent of RsrvEventual/RsrvNonEventual.

Yes, the hardware implementation of AMO could be different from LR/SC. AMO could use ACE snoop holding to lock the bus in hw coherency design, but LR/SC uses an exclusive monitor without locking the bus.

Quoted 3 lines

RISC-V hasn't CAS instructions, and it uses LR/SC for cmpxchg. I don't think LR/SC would be slower than CAS, and CAS is just good for code size.

What I meant here is that the current spinlock uses a simple amoswap, which presumably does not suffer from the lack of forward process you described.

Quoted 14 lines

Quoted 13 lines

[1]
https://github.com/c-sky/csky-linux/commit/e837aad23148542771794d8a2fcc
52afd0fcbf88> >

Quoted 2 lines

It also seems that the current "amoswap" based implementation would be reliable independent of RsrvEventual/RsrvNonEventual.

Yes, the hardware implementation of AMO could be different from LR/SC. AMO could use ACE snoop holding to lock the bus in hw coherency design, but LR/SC uses an exclusive monitor without locking the bus.

RISC-V hasn't CAS instructions, and it uses LR/SC for cmpxchg. I don't think LR/SC would be slower than CAS, and CAS is just good for code size.

Quoted 3 lines

What I meant here is that the current spinlock uses a simple amoswap, which presumably does not suffer from the lack of forward process you described.

Does that mean we should prevent using LR/SC (if RsrvNonEventual)?

Quoted 14 lines · NZDT Guo Ren

Quoted 14 lines

Quoted 13 lines

[1]
https://github.com/c-sky/csky-linux/commit/e837aad23148542771794d8a2fcc
52afd0fcbf88> >

Quoted 2 lines

It also seems that the current "amoswap" based implementation would be reliable independent of RsrvEventual/RsrvNonEventual.

Yes, the hardware implementation of AMO could be different from LR/SC. AMO could use ACE snoop holding to lock the bus in hw coherency design, but LR/SC uses an exclusive monitor without locking the bus.

RISC-V hasn't CAS instructions, and it uses LR/SC for cmpxchg. I don't think LR/SC would be slower than CAS, and CAS is just good for code size.

Quoted 5 lines

Quoted 3 lines

What I meant here is that the current spinlock uses a simple amoswap, which presumably does not suffer from the lack of forward process you described.

Does that mean we should prevent using LR/SC (if RsrvNonEventual)?

Let me provide another data-point, I'm working on a high-end highly speculative implementation with many concurrent instructions in flight - from my point of view both sorts of AMO (LR/SC and swap/add/etc) require me to grab a cache line in an exclusive modifiable state (so no difference there).

More importantly both sorts of AMO instructions (unlike most loads and stores) can't be speculated (not even LR because it changes hidden state, I found this out the hard way bringing up the kernel).

This means that both LR AND SC individually can't be executed until all speculation is resolved (that means that they happen really late in the execute path and block the resolution of the speculation of subsequent instructions) - equally a single amoswap/add/etc instruction can't happen until late in the execute path - so both require the same cache line state, but one of these sorts of events is better than two of them.

Which in short means that amoswap/add/etc is better for small things - small buzzy lock loops, while LR/SC is better for more complex things with actual processing between the LR and SC.

----

Another issue here is to consider is what happens when you hit one of these tight spinlocks when the branch target cache is empty and they fail (ie loop back and try again) - the default branch prediction, and resulting speculation, is (very) likely to be looping back, while hopefully most locks are not contended when you hit them and that speculation would be wrong - a spinlock like this may not be so good:

        li a0, 1

loop:
amoswap a1, a0, (a2)
beqz a1, loop
..... subsequent code

In my world with no BTC info the pipe fills with dozens of amoswaps, rather than the 'subsequent code'. While (in my world) code like this:

        li a0, 1

loop:
amoswap a1, a0, (a2)
bnez a1, 1f
.... subsequent code

1: j loop

would actually be better (in my world unconditional jump instructions are folded early and never see execution so they're sort of free, though they mess with the issue/decode rate). Smart compilers could move the "j loop" out of the way, while the double branch on failure is not a big deal since either the lock is still held (and you don't care if it's slow) or it's been released in which case the cache line has been stolen and the refetch of that cache line is going to dominate the next time around the loop

I need to stress here that this is how my architecture works, other's will of course be different though I expect that other heavily speculative architectures to have similar issues :-)

Paul Campbell
Moonbase Otago

Quoted 47 lines · Arnd Bergmann

Quoted 23 lines · Guo Ren

Quoted 5 lines · Arnd Bergmann

Quoted 3 lines · Guo Ren

Quoted 2 lines · Peter Zijlstra

What's the architectural guarantee on LL/SC progress for RISC-V ?

Quoted 8 lines

"When LR/SC is used for memory locations marked RsrvNonEventual,
software should provide alternative fall-back mechanisms used when lack of progress is detected."

My reading of this is that if the example you tried stalls, then either the PMA is not RsrvEventual, and it is wrong to rely on ll/sc on this, or that the PMA is marked RsrvEventual but the implementation is buggy.

Yes, PMA just defines physical memory region attributes, But in our processor, when MMU is enabled (satp's value register > 2) in s-mode, it will look at our custom PTE's attributes BIT(63) ref [1]:

PTE format:

   | 63 | 62 | 61 | 60 | 59 | 58-8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0
     SO   C    B    SH   SE    RSW   D   A   G   U   X   W   R   V
     ^    ^    ^    ^    ^

Quoted 7 lines

BIT(63): SO - Strong Order
BIT(62): C - Cacheable
BIT(61): B - Bufferable
BIT(60): SH - Shareable
BIT(59): SE - Security

So the memory also could be RsrvNone/RsrvEventual.

I was not talking about RsrvNone, which would clearly mean that you cannot use lr/sc at all (trap would trap, right?), but "RsrvNonEventual", which would explain the behavior you described in an earlier reply:

| u32 a = 0x55aa66bb;
| u16 *ptr = &a;
|
| CPU0                       CPU1
| =========             =========
| xchg16(ptr, new)     while(1)
|                                     WRITE_ONCE(*(ptr + 1), x);
|
| When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Quoted 4 lines

As I understand, this example must not cause a deadlock on a compliant hardware implementation when the underlying memory has RsrvEventual behavior, but could deadlock in case of RsrvNonEventual

Thx for the nice explanation:
- RsrvNonEventual - depends on software fall-back mechanisms, and
just I'm worried about.
- RsrvEventual - HW would provide the eventual success guarantee.

Quoted 12 lines

Quoted 12 lines

[1] https://github.com/c-sky/csky-linux/commit/e837aad23148542771794d8a2fcc52afd0fcbf88

Quoted 3 lines

It also seems that the current "amoswap" based implementation would be reliable independent of RsrvEventual/RsrvNonEventual.

Yes, the hardware implementation of AMO could be different from LR/SC. AMO could use ACE snoop holding to lock the bus in hw coherency design, but LR/SC uses an exclusive monitor without locking the bus.

Quoted 7 lines

Quoted 3 lines

RISC-V hasn't CAS instructions, and it uses LR/SC for cmpxchg. I don't think LR/SC would be slower than CAS, and CAS is just good for code size.

What I meant here is that the current spinlock uses a simple amoswap, which presumably does not suffer from the lack of forward process you described.

Does that mean we should prevent using LR/SC (if RsrvNonEventual)?

--
Best Regards
Guo Ren

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

Quoted 11 lines · Guo Ren

Quoted 6 lines · Arnd Bergmann

On Tue, Mar 30, 2021 at 4:26 AM Guo Ren <[email protected]> wrote:

As I understand, this example must not cause a deadlock on a compliant hardware implementation when the underlying memory has RsrvEventual behavior, but could deadlock in case of RsrvNonEventual

Thx for the nice explanation:
- RsrvNonEventual - depends on software fall-back mechanisms, and
just I'm worried about.
- RsrvEventual - HW would provide the eventual success guarantee.

In riscv-spec 8.3 Eventual Success of Store-Conditional Instructions

I found:
"As a consequence of the eventuality guarantee, if some harts in an execution environment are
executing constrained LR/SC loops, and no other harts or devices in the execution environment
execute an unconditional store or AMO to that reservation set, then at least one hart will
eventually exit its constrained LR/SC loop. *** By contrast, if other harts or devices continue to
write to that reservation set, it ***is not guaranteed*** that any hart will exit its LR/SC loop.*** "

Seems RsrvEventual couldn't solve the code's problem I've mentioned.

Quoted 13 lines · On Sat, Mar 27, 2021 at 06:06:38PM +0000, [email protected] wrote:

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

Quoted 4 lines

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

So I really don't like this, this pushes complexity into the generic code for something that's really not needed.

Lots of RISC already implement sub-word atomics using word ll/sc. Obviously they're not sharing code like they should be :/ See for example arch/mips/kernel/cmpxchg.c.

Also, I really do think doing ticket locks first is a far more sensible step.

Quoted 20 lines · Peter Zijlstra

Quoted 13 lines · On Sat, Mar 27, 2021 at 06:06:38PM +0000, [email protected] wrote:

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

Quoted 4 lines

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

Quoted 6 lines

So I really don't like this, this pushes complexity into the generic code for something that's really not needed.

Lots of RISC already implement sub-word atomics using word ll/sc. Obviously they're not sharing code like they should be :/ See for example arch/mips/kernel/cmpxchg.c.

I see, we've done two versions of this:
- Using cmpxchg codes from MIPS by Michael
- Re-write with assembly codes by Guo

But using the full-word atomic xchg instructions implement xchg16 has the semantic risk for atomic operations.

Quoted 2 lines

Also, I really do think doing ticket locks first is a far more sensible step.

NACK by Anup

Quoted 27 lines · Guo Ren

Quoted 26 lines · Peter Zijlstra

Quoted 13 lines · On Sat, Mar 27, 2021 at 06:06:38PM +0000, [email protected] wrote:

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

Quoted 4 lines

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

So I really don't like this, this pushes complexity into the generic code for something that's really not needed.

Lots of RISC already implement sub-word atomics using word ll/sc. Obviously they're not sharing code like they should be :/ See for example arch/mips/kernel/cmpxchg.c.

Quoted 6 lines

I see, we've done two versions of this:
- Using cmpxchg codes from MIPS by Michael
- Re-write with assembly codes by Guo

But using the full-word atomic xchg instructions implement xchg16 has the semantic risk for atomic operations.

What? -ENOPARSE

Quoted 4 lines

Quoted 3 lines

Also, I really do think doing ticket locks first is a far more sensible step.

NACK by Anup

Who's he when he's not sending NAKs ?

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

-----Original Message-----
From: Guo Ren <[email protected]>
Sent: 30 March 2021 08:44
To: Peter Zijlstra <[email protected]>
Cc: linux-riscv <[email protected]>; Linux Kernel Mailing List <[email protected]>; [email protected]; linux-arch <[email protected]>; Guo Ren <[email protected]>; Will Deacon <[email protected]>; Ingo Molnar <[email protected]>; Waiman Long <[email protected]>; Arnd Bergmann <[email protected]>; Anup Patel <[email protected]>
Subject: Re: [PATCH v4 3/4] locking/qspinlock: Add ARCH_USE_QUEUED_SPINLOCKS_XCHG32

Quoted 10 lines · Peter Zijlstra

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

Quoted 6 lines

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Do you mean the below implementation has live-lock risk?

(quoted diff) +14 -0

+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+       u32 old, new, val = atomic_read(&lock->val);
+
+       for (;;) {
+               new = (val & _Q_LOCKED_PENDING_MASK) | tail;
+               old = atomic_cmpxchg(&lock->val, val, new);
+               if (old == val)
+                       break;
+
+               val = old;
+       }
+       return old;
+}

Quoted 6 lines

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

Quote Waiman's comment [1] on xchg16 optimization:

"This optimization is needed to make the qspinlock achieve performance parity with ticket spinlock at light load."

[1] https://lore.kernel.org/kvm/1429901803-29771-6-git-send-email-
[email protected]/

So for a non-xhg16 machine:
- ticket-lock for small numbers of CPUs
- qspinlock for large numbers of CPUs

Okay, I'll put all of them into the next patch

Quoted 68 lines

-----Original Message-----
From: Guo Ren <[email protected]>
Sent: 30 March 2021 08:44
To: Peter Zijlstra <[email protected]>
Cc: linux-riscv <[email protected]>; Linux Kernel Mailing List <[email protected]>; [email protected]; linux-arch <[email protected]>; Guo Ren <[email protected]>; Will Deacon <[email protected]>; Ingo Molnar <[email protected]>; Waiman Long <[email protected]>; Arnd Bergmann <[email protected]>; Anup Patel <[email protected]>
Subject: Re: [PATCH v4 3/4] locking/qspinlock: Add ARCH_USE_QUEUED_SPINLOCKS_XCHG32

Quoted 10 lines · Peter Zijlstra

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

Quoted 6 lines

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Do you mean the below implementation has live-lock risk?

(quoted diff) +14 -0

+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+       u32 old, new, val = atomic_read(&lock->val);
+
+       for (;;) {
+               new = (val & _Q_LOCKED_PENDING_MASK) | tail;
+               old = atomic_cmpxchg(&lock->val, val, new);
+               if (old == val)
+                       break;
+
+               val = old;
+       }
+       return old;
+}

Quoted 6 lines

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

Quote Waiman's comment [1] on xchg16 optimization:

"This optimization is needed to make the qspinlock achieve performance parity with ticket spinlock at light load."

[1] https://lore.kernel.org/kvm/1429901803-29771-6-git-send-email-
[email protected]/

So for a non-xhg16 machine:
- ticket-lock for small numbers of CPUs
- qspinlock for large numbers of CPUs

Quoted 1 line

Okay, I'll put all of them into the next patch

I would suggest to have separate Kconfig opitons for ticket spinlock in Linux RISC-V which will be disabled by default. This means Linux RISC-V will use qspinlock by default and use ticket spinlock only when ticket spinlock kconfig is enabled.

Regards,
Anup

Sent: 30 March 2021 04:14

Quoted 3 lines

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

Quote Waiman's comment [1] on xchg16 optimization:

"This optimization is needed to make the qspinlock achieve performance parity with ticket spinlock at light load."

[1] https://lore.kernel.org/kvm/[email protected]/

So for a non-xhg16 machine:
- ticket-lock for small numbers of CPUs
- qspinlock for large numbers of CPUs

Okay, I'll put all of them into the next patch :P

Quoted 9 lines · Peter Zijlstra

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                     WRITE_ONCE(*(ptr + 1), x);

Quoted 5 lines

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Do you mean the below implementation has live-lock risk?

(quoted diff) +4 -0

+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+       u32 old, new, val = atomic_read(&lock->val);
+

Quoted 4 lines

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

Quote Waiman's comment [1] on xchg16 optimization:

"This optimization is needed to make the qspinlock achieve performance parity with ticket spinlock at light load."

[1] https://lore.kernel.org/kvm/[email protected]/

So for a non-xhg16 machine:
- ticket-lock for small numbers of CPUs
- qspinlock for large numbers of CPUs

Okay, I'll put all of them into the next patch :P

Quoted 26 lines · Guo Ren

Quoted 9 lines · Peter Zijlstra

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                     WRITE_ONCE(*(ptr + 1), x);

Quoted 5 lines

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Do you mean the below implementation has live-lock risk?

(quoted diff) +10 -0

+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+       u32 old, new, val = atomic_read(&lock->val);
+
+       for (;;) {
+               new = (val & _Q_LOCKED_PENDING_MASK) | tail;
+               old = atomic_cmpxchg(&lock->val, val, new);
+               if (old == val)
+                       break;
+

Review

Quoted 4 lines

(quoted diff) +4 -0

+               val = old;
+       }
+       return old;
+}

If there is a continuous stream of incoming spinlock takers, it is possible that some cpus may have to wait a long time to set the tail right. However, this should only happen on artificial workload. I doubt it will happen with real workload or with limit number of cpus.

Quoted 15 lines

Quoted 4 lines

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

Quote Waiman's comment [1] on xchg16 optimization:

"This optimization is needed to make the qspinlock achieve performance parity with ticket spinlock at light load."

[1] https://lore.kernel.org/kvm/[email protected]/

So for a non-xhg16 machine:
- ticket-lock for small numbers of CPUs
- qspinlock for large numbers of CPUs

Quoted 2 lines

Okay, I'll put all of them into the next patch :P

It is true that qspinlock may not offer much advantage when the number of cpus is small. It shines for systems with many cpus. You may use NR_CPUS to determine if the default should be ticket or qspinlock with user override. To determine the right NR_CPUS threshold, you may need to run on real SMP RISCV systems to find out.

Quoted 26 lines · Guo Ren

Quoted 9 lines · Peter Zijlstra

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                     WRITE_ONCE(*(ptr + 1), x);

Quoted 5 lines

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Do you mean the below implementation has live-lock risk?

(quoted diff) +10 -0

+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+       u32 old, new, val = atomic_read(&lock->val);
+
+       for (;;) {
+               new = (val & _Q_LOCKED_PENDING_MASK) | tail;
+               old = atomic_cmpxchg(&lock->val, val, new);
+               if (old == val)
+                       break;
+

Review

Quoted 4 lines

(quoted diff) +4 -0

+               val = old;
+       }
+       return old;
+}

If there is a continuous stream of incoming spinlock takers, it is possible that some cpus may have to wait a long time to set the tail right. However, this should only happen on artificial workload. I doubt it will happen with real workload or with limit number of cpus.

Quoted 15 lines

Quoted 4 lines

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

Quote Waiman's comment [1] on xchg16 optimization:

"This optimization is needed to make the qspinlock achieve performance parity with ticket spinlock at light load."

[1] https://lore.kernel.org/kvm/[email protected]/

So for a non-xhg16 machine:
- ticket-lock for small numbers of CPUs
- qspinlock for large numbers of CPUs

Quoted 2 lines

Okay, I'll put all of them into the next patch :P

It is true that qspinlock may not offer much advantage when the number of cpus is small. It shines for systems with many cpus. You may use NR_CPUS to determine if the default should be ticket or qspinlock with user override. To determine the right NR_CPUS threshold, you may need to run on real SMP RISCV systems to find out.

Quoted 10 lines · Peter Zijlstra

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

Quoted 6 lines

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Do you mean the below implementation has live-lock risk?

(quoted diff) +4 -0

+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+       u32 old, new, val = atomic_read(&lock->val);
+

Quoted 23 lines · Guo Ren

Quoted 10 lines · Peter Zijlstra

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

Quoted 6 lines

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Do you mean the below implementation has live-lock risk?

(quoted diff) +4 -0

+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+       u32 old, new, val = atomic_read(&lock->val);
+

Review

Quoted 10 lines

(quoted diff) +10 -0

+       for (;;) {
+               new = (val & _Q_LOCKED_PENDING_MASK) | tail;
+               old = atomic_cmpxchg(&lock->val, val, new);
+               if (old == val)
+                       break;
+
+               val = old;
+       }
+       return old;
+}

That entirely depends on the architecture (and cmpxchg() impementation).

There are a number of cases:

* architecture has cmpxchg() instruction (x86, s390, sparc, etc.).

- architecture provides fwd progress (x86)
- architecture requires backoff for progress (sparc)

* architecture does not have cmpxchg, and implements it using LL/SC.

and here things get *really* interesting, because while an architecture can have LL/SC fwd progress, that does not translate into cmpxchg() also having the same guarantees and all bets are off.

The real bummer is that C can do cmpxchg(), but there is no way it can do LL/SC. And even if we'd teach C how to do LL/SC, it couldn't be generic because architectures lacking it can't emulate it using cmpxchg() (there's a fun class of bugs there).

So while the above code might be the best we can do in generic code, it's really up to the architecture to make it work.

I just want to chime in here, there may be a better spot in the thread to mention this but, for OpenRISC I did implement some generic 8/16-bit xchg code which I have on my todo list somwhere to replace the other generic implementations like that in mips.

arch/openrisc/include/asm/cmpxchg.h

The idea would be that architectures just implement these methods:

long cmpxchg_u32(*ptr,old,new)
long xchg_u32(*ptr,val)

Then the rest of the generic header would implement cmpxchg.

Quoted 13 lines · Stafford Horne

I just want to chime in here, there may be a better spot in the thread to mention this but, for OpenRISC I did implement some generic 8/16-bit xchg code which I have on my todo list somwhere to replace the other generic implementations like that in mips.

arch/openrisc/include/asm/cmpxchg.h

The idea would be that architectures just implement these methods:

long cmpxchg_u32(*ptr,old,new)
long xchg_u32(*ptr,val)

Quoted 1 line

Then the rest of the generic header would implement cmpxchg.

I like the idea of generalizing it a little further. I'd suggest staying a little closer to the existing naming here though, as we already have cmpxchg() for the type-agnostic version, and cmpxchg64() for the fixed-length 64-bit version.

I think a nice interface between architecture-specific and architecture independent code would be to have architectures provide arch_cmpxchg32()/arch_xchg32() as the most basic version, as well as arch_cmpxchg8()/arch_cmpxchg16()/arch_xchg8()/arch_xchg16() if they have instructions for those.

The common code can then build cmpxchg16()/xchg16() on top of either the 16-bit or the 32-bit primitives, and build the cmpxchg()/xchg() wrapper around those (or alternatively we can decide to have them only deal with fixed-32-bit and long/pointer sized atomics).

Quoted 14 lines · Arnd Bergmann

Quoted 13 lines · Stafford Horne

I just want to chime in here, there may be a better spot in the thread to mention this but, for OpenRISC I did implement some generic 8/16-bit xchg code which I have on my todo list somwhere to replace the other generic implementations like that in mips.

arch/openrisc/include/asm/cmpxchg.h

The idea would be that architectures just implement these methods:

long cmpxchg_u32(*ptr,old,new)
long xchg_u32(*ptr,val)

Quoted 6 lines

Quoted 1 line

Then the rest of the generic header would implement cmpxchg.

I like the idea of generalizing it a little further. I'd suggest staying a little closer to the existing naming here though, as we already have cmpxchg() for the type-agnostic version, and cmpxchg64() for the fixed-length 64-bit version.

OK.

Quoted 5 lines

I think a nice interface between architecture-specific and architecture independent code would be to have architectures provide arch_cmpxchg32()/arch_xchg32() as the most basic version, as well as arch_cmpxchg8()/arch_cmpxchg16()/arch_xchg8()/arch_xchg16() if they have instructions for those.

Thanks for the name suggestions, it makes it easier for me.

Quoted 4 lines

The common code can then build cmpxchg16()/xchg16() on top of either the 16-bit or the 32-bit primitives, and build the cmpxchg()/xchg() wrapper around those (or alternatively we can decide to have them only deal with fixed-32-bit and long/pointer sized atomics).

Yeah, that was the idea.

-Stafford

Hi Stafford,

How do think add ARCH_USE_QUEUED_SPINLOCKS_XCHG32 in openrisc?

https://lore.kernel.org/linux-riscv/[email protected]/T/#u

Quoted 41 lines · Arnd Bergmann

Quoted 14 lines · Stafford Horne

Quoted 13 lines

I just want to chime in here, there may be a better spot in the thread to mention this but, for OpenRISC I did implement some generic 8/16-bit xchg code which I have on my todo list somwhere to replace the other generic implementations like that in mips.

arch/openrisc/include/asm/cmpxchg.h

The idea would be that architectures just implement these methods:

long cmpxchg_u32(*ptr,old,new)
long xchg_u32(*ptr,val)

Quoted 6 lines

Quoted 1 line

Then the rest of the generic header would implement cmpxchg.

I like the idea of generalizing it a little further. I'd suggest staying a little closer to the existing naming here though, as we already have cmpxchg() for the type-agnostic version, and cmpxchg64() for the fixed-length 64-bit version.

OK.

Quoted 5 lines

I think a nice interface between architecture-specific and architecture independent code would be to have architectures provide arch_cmpxchg32()/arch_xchg32() as the most basic version, as well as arch_cmpxchg8()/arch_cmpxchg16()/arch_xchg8()/arch_xchg16() if they have instructions for those.

Thanks for the name suggestions, it makes it easier for me.

Quoted 4 lines

The common code can then build cmpxchg16()/xchg16() on top of either the 16-bit or the 32-bit primitives, and build the cmpxchg()/xchg() wrapper around those (or alternatively we can decide to have them only deal with fixed-32-bit and long/pointer sized atomics).

Yeah, that was the idea.

-Stafford

Signature · 4 lines

Best Regards
 Guo Ren

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

Quoted 6 lines · Stafford Horne

I just want to chime in here, there may be a better spot in the thread to mention this but, for OpenRISC I did implement some generic 8/16-bit xchg code which I have on my todo list somwhere to replace the other generic implementations like that in mips.

Quoted 8 lines

arch/openrisc/include/asm/cmpxchg.h

The idea would be that architectures just implement these methods:

long cmpxchg_u32(*ptr,old,new)
long xchg_u32(*ptr,val)

Then the rest of the generic header would implement cmpxchg.

I like the idea of generalizing it a little further. I'd suggest staying a little closer to the existing naming here though, as we already have cmpxchg() for the type-agnostic version, and cmpxchg64() for the fixed-length 64-bit version.

I think a nice interface between architecture-specific and architecture independent code would be to have architectures provide arch_cmpxchg32()/arch_xchg32() as the most basic version, as well as arch_cmpxchg8()/arch_cmpxchg16()/arch_xchg8()/arch_xchg16() if they have instructions for those.

The common code can then build cmpxchg16()/xchg16() on top of either the 16-bit or the 32-bit primitives, and build the cmpxchg()/xchg() wrapper around those (or alternatively we can decide to have them only deal with fixed-32-bit and long/pointer sized atomics).

Quoted 28 lines · Arnd Bergmann

Quoted 6 lines · Stafford Horne

I just want to chime in here, there may be a better spot in the thread to mention this but, for OpenRISC I did implement some generic 8/16-bit xchg code which I have on my todo list somwhere to replace the other generic implementations like that in mips.

Quoted 8 lines

arch/openrisc/include/asm/cmpxchg.h

The idea would be that architectures just implement these methods:

long cmpxchg_u32(*ptr,old,new)
long xchg_u32(*ptr,val)

Then the rest of the generic header would implement cmpxchg.

I like the idea of generalizing it a little further. I'd suggest staying a little closer to the existing naming here though, as we already have cmpxchg() for the type-agnostic version, and cmpxchg64() for the fixed-length 64-bit version.

I think a nice interface between architecture-specific and architecture independent code would be to have architectures provide arch_cmpxchg32()/arch_xchg32() as the most basic version, as well as arch_cmpxchg8()/arch_cmpxchg16()/arch_xchg8()/arch_xchg16() if they have instructions for those.

Quoted 4 lines

The common code can then build cmpxchg16()/xchg16() on top of either the 16-bit or the 32-bit primitives, and build the cmpxchg()/xchg() wrapper around those (or alternatively we can decide to have them only deal with fixed-32-bit and long/pointer sized atomics).

I think these emulation codes are suitable for some architectures but not riscv.

We shouldn't export xchg16/cmpxchg16(emulated by lr.w/sc.w) in riscv, We should forbid these sub-word atomic primitive and lets the programmers consider their atomic design.

Quoted 6 lines · Guo Ren

Quoted 1 line · Arnd Bergmann

On Wed, Mar 31, 2021 at 12:35 AM Stafford Horne <[email protected]> wrote:

We shouldn't export xchg16/cmpxchg16(emulated by lr.w/sc.w) in riscv, We should forbid these sub-word atomic primitive and lets the programmers consider their atomic design.

Fair enough, having the generic sub-word emulation would be something that an architecture can select to use/export.

Since there are really only a handful of instances in the kernel that use the cmpxchg() or xchg() on u8/u16 variables, it would seem best to just disallow those completely

Interestingly, the s390 version using __sync_val_compare_and_swap() seems to produce nice output on all architectures that have atomic instructions, with any supported compiler, to the point where I think we could just use that to replace most of the inline-asm versions except for arm64:

#define cmpxchg(ptr, o, n)                                              \
({                                                                      \
        __typeof__(*(ptr)) __o = (o);                                   \
        __typeof__(*(ptr)) __n = (n);                                   \
        (__typeof__(*(ptr))) __sync_val_compare_and_swap((ptr),__o,__n);\
})

Not how gcc's acquire/release behavior of __sync_val_compare_and_swap() relates to what the kernel wants here.

The gcc documentation also recommends using the standard __atomic_compare_exchange_n() builtin instead, which would allow constructing release/acquire/relaxed versions as well, but I could not get it to produce equally good output. (possibly I was using it wrong)

Quoted 3 lines · Arnd Bergmann

Since there are really only a handful of instances in the kernel that use the cmpxchg() or xchg() on u8/u16 variables, it would seem best to just disallow those completely

Not going to happen. xchg16 is optimal for qspinlock and if we replace that with a cmpxchg loop on x86 we're regressing.

Quoted 6 lines

Interestingly, the s390 version using __sync_val_compare_and_swap() seems to produce nice output on all architectures that have atomic instructions, with any supported compiler, to the point where I think we could just use that to replace most of the inline-asm versions except for arm64:

Quoted 6 lines

#define cmpxchg(ptr, o, n)                                              \
({                                                                      \
        __typeof__(*(ptr)) __o = (o);                                   \
        __typeof__(*(ptr)) __n = (n);                                   \
        (__typeof__(*(ptr))) __sync_val_compare_and_swap((ptr),__o,__n);\
})

It generates the LL/SC loop, but doesn't do sensible optimizations when it's again used in a loop itself. That is, it generates a loop of a loop, just like what you'd expect, which is sub-optimal for LL/SC.

Quoted 7 lines

Not how gcc's acquire/release behavior of __sync_val_compare_and_swap() relates to what the kernel wants here.

The gcc documentation also recommends using the standard __atomic_compare_exchange_n() builtin instead, which would allow constructing release/acquire/relaxed versions as well, but I could not get it to produce equally good output. (possibly I was using it wrong)

I'm scared to death of the C11 crap, the compiler will 'optimize' them when it feels like it and use the C11 memory model rules for it, which are not compatible with the kernel rules.

But the same thing applies, it won't do the right thing for composites.

Quoted 3 lines · Arnd Bergmann

Since there are really only a handful of instances in the kernel that use the cmpxchg() or xchg() on u8/u16 variables, it would seem best to just disallow those completely

Not going to happen. xchg16 is optimal for qspinlock and if we replace that with a cmpxchg loop on x86 we're regressing.

Quoted 6 lines

Interestingly, the s390 version using __sync_val_compare_and_swap() seems to produce nice output on all architectures that have atomic instructions, with any supported compiler, to the point where I think we could just use that to replace most of the inline-asm versions except for arm64:

Quoted 6 lines

#define cmpxchg(ptr, o, n)                                              \
({                                                                      \
        __typeof__(*(ptr)) __o = (o);                                   \
        __typeof__(*(ptr)) __n = (n);                                   \
        (__typeof__(*(ptr))) __sync_val_compare_and_swap((ptr),__o,__n);\
})

It generates the LL/SC loop, but doesn't do sensible optimizations when it's again used in a loop itself. That is, it generates a loop of a loop, just like what you'd expect, which is sub-optimal for LL/SC.

Quoted 7 lines

Not how gcc's acquire/release behavior of __sync_val_compare_and_swap() relates to what the kernel wants here.

The gcc documentation also recommends using the standard __atomic_compare_exchange_n() builtin instead, which would allow constructing release/acquire/relaxed versions as well, but I could not get it to produce equally good output. (possibly I was using it wrong)

I'm scared to death of the C11 crap, the compiler will 'optimize' them when it feels like it and use the C11 memory model rules for it, which are not compatible with the kernel rules.

But the same thing applies, it won't do the right thing for composites.

Quoted 23 lines · Guo Ren

Quoted 10 lines · Peter Zijlstra

Quoted 8 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

Quoted 6 lines

Quoted 1 line

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Do you mean the below implementation has live-lock risk?

(quoted diff) +4 -0

+static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
+{
+       u32 old, new, val = atomic_read(&lock->val);
+

Review

Quoted 10 lines

(quoted diff) +10 -0

+       for (;;) {
+               new = (val & _Q_LOCKED_PENDING_MASK) | tail;
+               old = atomic_cmpxchg(&lock->val, val, new);
+               if (old == val)
+                       break;
+
+               val = old;
+       }
+       return old;
+}

That entirely depends on the architecture (and cmpxchg() impementation).

There are a number of cases:

* architecture has cmpxchg() instruction (x86, s390, sparc, etc.).

- architecture provides fwd progress (x86)
- architecture requires backoff for progress (sparc)

* architecture does not have cmpxchg, and implements it using LL/SC.

and here things get *really* interesting, because while an architecture can have LL/SC fwd progress, that does not translate into cmpxchg() also having the same guarantees and all bets are off.

The real bummer is that C can do cmpxchg(), but there is no way it can do LL/SC. And even if we'd teach C how to do LL/SC, it couldn't be generic because architectures lacking it can't emulate it using cmpxchg() (there's a fun class of bugs there).

So while the above code might be the best we can do in generic code, it's really up to the architecture to make it work.

Quoted 3 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

Quoted 6 lines

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

Quoted 5 lines · Peter Zijlstra

Quoted 3 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

Quoted 8 lines

Quoted 6 lines

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

No, it's not broken LR.W/SC.W. Quote <8.3 Eventual Success of Store-Conditional Instructions>:

"As a consequence of the eventuality guarantee, if some harts in an execution environment are executing constrained LR/SC loops, and no other harts or devices in the execution environment execute an unconditional store or AMO to that reservation set, then at least one hart will eventually exit its constrained LR/SC loop. By contrast, if other harts or devices continue to write to that reservation set, it is not guaranteed that any hart will exit its LR/SC loop."

So I think it's a feature of LR/SC. How does the above code (also use ll.w/sc.w to implement xchg16) running on arm64?

1: ldxr
eor
cbnz ... 2f
stxr
cbnz ... 1b // I think it would deadlock for arm64.

"LL/SC fwd progress" which you have mentioned could guarantee stxr success? How hardware could do that?

Anyway, given you have such a crap architecture (and here I thought RISC-V was supposed to be a modern design *sigh*), you had better go look at the sparc64 atomic implementation which has a software backoff for failed CAS in order to make fwd progress.

Quoted 4 lines · Peter Zijlstra

Anyway, given you have such a crap architecture (and here I thought RISC-V was supposed to be a modern design *sigh*), you had better go look at the sparc64 atomic implementation which has a software backoff for failed CAS in order to make fwd progress.

It wasn't supposed to be modern. It was supposed to use boring old ideas. Where it actually did that it is a great ISA, in parts where academics actually tried to come up with cool or state of the art ideas (interrupt handling, tlb shootdowns, the totally fucked up memory model) it turned into a trainwreck.

Gentlemen, please rethink your wording.
RISC-V is neither "crap" nor a "trainwreck", regardless if you like it or not.

Further, it is not the case that RISC-V has no guarantees at all. It just does not provide a forward progress guarantee for a synchronization implementation,
that writes in an endless loop to a memory location while trying to complete an LL/SC
loop on the same memory location at the same time.

Quoted 6 lines · Christoph Müllner

Further, it is not the case that RISC-V has no guarantees at all. It just does not provide a forward progress guarantee for a synchronization implementation,
that writes in an endless loop to a memory location while trying to complete an LL/SC
loop on the same memory location at the same time.

Userspace can DoS the kernel that way, see futex.

The comparison with sparc64 is not applicable, as sparc64 does not have LL/SC instructions.

Quoted 2 lines · Christoph Müllner

The comparison with sparc64 is not applicable, as sparc64 does not have LL/SC instructions.

Sparc64 has CAS, without hardware fwd progress. It has to do software backoff for failed CAS in order to do software fwd progress.

RISC-V defines LR/SC loops consisting of up to 16 instructions as constrained LR/SC loops. Such constrained LR/SC loops provide the required forward guarantees, that are expected (similar to what other architectures, like AArch64, have).

What RISC-V does not have is sub-word atomics and if required, we would have to implement them as LL/SC sequences. And yes, using atomic instructions is preferred over using LL/SC,

Quoted 4 lines · Christoph Müllner

RISC-V defines LR/SC loops consisting of up to 16 instructions as constrained LR/SC loops. Such constrained LR/SC loops provide the required forward guarantees, that are expected (similar to what other architectures, like AArch64, have).

The text quoted by others didn't seem to say such a thing, but whatever.

Quoted 3 lines

What RISC-V does not have is sub-word atomics and if required, we would have to implement them as LL/SC sequences. And yes, using atomic instructions is preferred over using LL/SC,

(psudo asm, can't be bothered to figure out the actual syntax)

        # setup r_and_mask, r_or_mask

.L1
LL r, [word]
AND r, r, r_and_mask
OR r, r, r_or_mask
SC r, [word]
JNE .L1

is what you need for LL/SC based xchg16, that's less than 16 instructions. If RISC-V guarantees fwd progress on that, good, write it like that and lets end this thread.

The fact that this is apparently hard, is not good.

Quoted 5 lines · Peter Zijlstra

Quoted 3 lines · Guo Ren

u32 a = 0x55aa66bb;
u16 *ptr = &a;

Quoted 8 lines

Quoted 6 lines

CPU0 CPU1
========= =========
xchg16(ptr, new) while(1)

                                    WRITE_ONCE(*(ptr + 1), x);

When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock.

Then I think your LL/SC is broken.

No, it's not broken LR.W/SC.W. Quote <8.3 Eventual Success of Store-Conditional Instructions>:

"As a consequence of the eventuality guarantee, if some harts in an execution environment are
executing constrained LR/SC loops, and no other harts or devices in the execution environment
execute an unconditional store or AMO to that reservation set, then at least one hart will
eventually exit its constrained LR/SC loop. By contrast, if other harts or devices continue to
write to that reservation set, it is not guaranteed that any hart will exit its LR/SC loop."

So I think it's a feature of LR/SC. How does the above code (also use ll.w/sc.w to implement xchg16) running on arm64?

1: ldxr
eor
cbnz ... 2f
stxr
cbnz ... 1b // I think it would deadlock for arm64.

"LL/SC fwd progress" which you have mentioned could guarantee stxr success? How hardware could do that?

Quoted 7 lines

That also means you really don't want to build super complex locking primitives on top, because that live-lock will percolate through.

Step 1 would be to get your architecute fixed such that it can provide fwd progress guarantees for LL/SC. Otherwise there's absolutely no point in building complex systems with it.

--
Best Regards
Guo Ren

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

Actually, "old" riscv standard does provide fwd progress ;-) In

	https://riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf

Section "7.2 Load-Reserved/Store-Conditional Instructions":

"""
One advantage of CAS is that it guarantees that some hart eventually makes progress, whereas an LR/SC atomic sequence could livelock indefinitely on some systems. To avoid this concern, we added an

architectural guarantee of forward progress to LR/SC atomic sequences. The restrictions on LR/SC sequence contents allows an implementation to **capture a cache line on the LR and complete the LR/SC sequence by holding off remote cache interventions for a bounded short time**. """

The guarantee is removed later due to "Earlier versions of this specification imposed a stronger starvation-freedom guarantee. However, the weaker livelock-freedom guarantee is sufficient to implement the C11 and C++11 languages, and is substantially easier to provide in some microarchitectural styles."

-----Original Message-----
From: Peter Zijlstra <[email protected]>
Sent: 29 March 2021 16:57
To: Guo Ren <[email protected]>
Cc: linux-riscv <[email protected]>; Linux Kernel Mailing List <[email protected]>; [email protected]; linux-arch <[email protected]>; Guo Ren <[email protected]>; Will Deacon <[email protected]>; Ingo Molnar <[email protected]>; Waiman Long <[email protected]>; Arnd Bergmann <[email protected]>; Anup Patel <[email protected]>
Subject: Re: [PATCH v4 3/4] locking/qspinlock: Add ARCH_USE_QUEUED_SPINLOCKS_XCHG32

Quoted 1 line · Guo Ren

On Mon, Mar 29, 2021 at 3:50 PM Peter Zijlstra <[email protected]>

Quoted 26 lines · wrote:

Quoted 20 lines · On Sat, Mar 27, 2021 at 06:06:38PM +0000, [email protected] wrote:

Quoted 13 lines

From: Guo Ren <[email protected]>

Some architectures don't have sub-word swap atomic instruction, they only have the full word's one.

The sub-word swap only improve the performance when:
NR_CPUS < 16K
* 0- 7: locked byte
* 8: pending
* 9-15: not used
* 16-17: tail index
* 18-31: tail cpu (+1)

Quoted 4 lines

The 9-15 bits are wasted to use xchg16 in xchg_tail.

Please let architecture select xchg16/xchg32 to implement xchg_tail.

Quoted 6 lines

So I really don't like this, this pushes complexity into the generic code for something that's really not needed.

Lots of RISC already implement sub-word atomics using word ll/sc. Obviously they're not sharing code like they should be :/ See for example arch/mips/kernel/cmpxchg.c.

Quoted 6 lines

I see, we've done two versions of this:
- Using cmpxchg codes from MIPS by Michael
- Re-write with assembly codes by Guo

But using the full-word atomic xchg instructions implement xchg16 has the semantic risk for atomic operations.

What? -ENOPARSE

Quoted 3 lines

Quoted 2 lines

Also, I really do think doing ticket locks first is a far more sensible step.

NACK by Anup

Who's he when he's not sending NAKs ?

We had discussions in the RISC-V platforms group about this. Over there, We had evaluated all spin lock approaches (ticket, qspinlock, etc) tried in Linux till now. It was concluded in those discussions that eventually we have to move to qspinlock (even if we moved to ticket spinlock temporarily) because qspinlock avoids cache line bouncing. Also, moving to qspinlock will be aligned with other major architectures supported in Linux (such as x86, ARM64)

Some of the organizations working on high-end RISC-V systems (> 32 CPUs) are interested in having an optimized spinlock implementation (just like other major architectures x86 and ARM64).

Based on above, Linux RISC-V should move to qspinlock.