[Edited Message Follows]

Abstract

Atomic Forward Guarantee is required in many OS to touch contended variables. Linux queued-spinlock is the atomic forward guarantee user who solves the fairness and cache-line bouncing problems and ensures performance and size. RISC-V Linux has been trying to port qspinlock support since 2019, but it is pended on the RISC-V flexible LR/SC forward Guarantee issue. In this presentation, we will introduce the troubles caused by the LR/SC Forward Guarantee definition in the RISC-V ISA to Linux qspinlock and propose our solution. Use klitmus to define the LR/SC & cmpxchg forward progress guarantee cases, which gives clear guidelines for micro-architecture designers and software programmers. 

Motivation

The current LR/SC forward progress guarantee is written in RISC-V ISA spec - "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.

HART 0                    HART 1
loop:                         loop:                         # a0 = 0x4000 (hart0 & 1)
lr.w t0, (a0)               lr.w t0, (a0)               # Load-Reserve original value
sc.w t1, a2, (a0)       sc.w t1, a2, (a0)       # Store-Conditional for AMOSWAP
bnez t1, loop            bnez t1, loop            # Retry if store-conditional failed
move a0, t0              move a0, t0              # Return original value
ret                             ret

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. (Written in RISC-V ISA spec: "Eventual Success of Store-Conditional Instructions")

HART 0                   HART 1
loop:                       loop:                      # a0 = 0x4000 (hart0 & 1)
st.w zero, (a0)        lr.w t0, (a0)
j loop                      sc.w t1, a2, (a0)
                               bnez t1, loop
                               move a0, t0
                               ret

No Guarantee here! The current LR/SC forward progress guarantee is a weak definition. But Linux queued-spinlock needs forward progress guarantee.

Here is the comment written in Linux qspinlock.h:

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/asm-generic/qspinlock.h

"qspinlock relies on a far greater (compared to asm-generic/spinlock.h) set of atomic operations to behave well together, please audit them carefully to ensure they all have forward progress. Many atomic operations may default to cmpxchg() loops which will not have good forward progress properties on LL/SC architectures."

First, LR/SC requirement in qspinlock when NR_CPUS < 16K.
static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
{
...
        return (u32)xchg16_relaxed(&lock->tail,
                                 tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET;
}

RISC-V doesn’t have the sub-word amoswap, so use LR/SC equivalent:
static inline ulong __xchg16_relaxed(ulong new, void *ptr)
{
        ulong ret, tmp;
        ulong shif = ((ulong)ptr & 2) ? 16 : 0;
        ulong mask = 0xffff << shif;
        ulong *__ptr = (ulong *)((ulong)ptr & ~2);

        __asm__ __volatile__ (
                "0: lr.w %0, %2\n"
                " and %1, %0, %z3\n"
                " or %1, %1, %z4\n"
                " sc.w %1, %1, %2\n"
                " bnez %1, 0b\n"
                : "=&r" (ret), "=&r" (tmp), "+A" (*__ptr)
                : "rJ" (~mask), "rJ" (new << shif)
                : "memory");
        return (ulong)((ret & mask) >> shif);
}
We need a strong level of forward progress guarantee here to make xchg16 like an AMO to contend with a single-store instruction.

Second, cmpxchg forward progress guarantee requirement in qspinlock when NR_CPUS >= 16K.
#define __cmpxchg_relaxed(ptr, old, new, size) \
({ \
…
                __asm__ __volatile__ ( \
                        "0:    lr.w  %0, %2\n" \
                        " bne %0, %z3, 1f\n" \
                        "       sc.w %1, %z4, %2\n" \
                        " bnez %1, 0b\n" \
                        "1:\n" \
                        : "=&r" (__ret), "=&r" (__rc), "+A" (*__ptr) \
                        : "rJ" ((long)__old), "rJ" (__new) \
                        : "memory"); \

Linux cmpxchg is the CAS primitive, and RISC-V uses LR/SC equivalent.

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_relaxed(&lock->val, val, new);
                if (old == val)
                        break;
                val = old;
        }
        return old;
}

The second cmpxchg should cause a loop break in any contended situation!

Proposal for discussion:

In current riscv spec: “A” Standard Extension for Atomic Instructions - Load-Reserved/Store-Conditional Instructions

"The failure code with value 1 is reserved to encode an unspecified failure. Other failure codes are reserved at this time, and portable software should only assume the failure code will be non-zero. We reserve a failure code of 1 to mean “unspecified” so that simple implementations may return this value using the existing mux required for the SLT/SLTU instructions. More specific failure codes might be defined in future versions or extensions to the ISA."

Add a failure code of 2 to store-conditional instruction:

Store-conditional returns local failure code

0 - Success
1 - Failure with an unspecified reason (Include cache coherency reason)
2 - Failure with a local event (interrupts/traps)

Then, define three forward progress guarantee levels:

Level 1 (Weak) - SC returns 0/1/2
Level 2 (Strong) - SC returns 0/2, never returns 1.
Level 3 (Absolute) - SC returns 0, never returns 1/2.

Litmus Tests for (Level 1~3, cmpxchg forward progress guarantee)

Level 3 - Absolute:
RISCV LEVEL3-LR-SC
{
0:x5=x;
1:x5=x;
}
 P0                      | P1 ;
 ori x6,x0,1          | ori x6,x0,2 ;
 lr.w x7,0(x5)        | st.w x6,0(x5) ;
 sc.w x8,x6,0(x5) | ;
forall
(x=1 /\ 0:x7=2 /\ 0:x8 = 0) \/
(x=2 /\ 0:x7=0 /\ 0:x8 = 0)
Make LR/SC behave like one atomic instruction.

Level 2 - Strong:

RISCV LEVEL3-LR-SC
{
0:x5=x;
1:x5=x;
}
 P0                      | P1 ;
 ori x6,x0,1          | ori x6,x0,2 ;
 lr.w x7,0(x5)        | st.w x6,0(x5) ;
 sc.w x8,x6,0(x5) | ;
forall
(x=1 /\ 0:x7=2 /\ 0:x8 = 0) \/
(x=2 /\ 0:x7=2 /\ 0:x8 = 2) \/
(x=2 /\ 0:x7=0 /\ 0:x8 = 0) \/
(x=2 /\ 0:x7=0 /\ 0:x8 = 2)
Only local event makes Store-Conditional fail.

Level 1 - Weak:
RISCV LEVEL1-LR-SC
{
0:x5=x;
1:x5=x;
}
 P0                       | P1 ;
 ori x6,x0,1           | ori x6,x0,2 ;
 lr.w x7,0(x5)        | st.w x6,0(x5) ;
 sc.w x8,x6,0(x5) | ;
forall
(x=1 /\ 0:x7=2 /\ 0:x8 = 0) \/
(x=2 /\ 0:x7=0 /\ 0:x8 = 1) \/
(x=2 /\ 0:x7=0 /\ 0:x8 = 2) \/
(x=2 /\ 0:x7=2 /\ 0:x8 = 2) \/
(x=2 /\ 0:x7=0 /\ 0:x8 = 0)
No forward progress guarantee.

cmpxchg forward progress guarantee:

RISCV LEVE_3-LR-LR-SC (Absolute Level)
{
0:x5=x;
1:x5=x;
}

 P0                      | P1 ;
 ori x6,x0,1          | ori x6,x0,2 ;
 lr.w x7,0(x5)       | st.w x6,0(x5) ;
 bnez x6, 1f         | ;
 nop                     | ;
1:                         | ;
 lr.w x8,0(x5)        | ;
 sc.w x9,x6,0(x5)  | ;
forall
(x=1 /\ 0:x7=2 /\ 0:x8=2 /\ 0:x9=0) \/
(x=2 /\ 0:x7=0 /\ 0:x8=0 /\ 0:x9=0)

RISCV LEVEL_2-LR-LR-SC (Strong Level)
{
0:x5=x;
1:x5=x;
}

 P0                      | P1 ;
 ori x6,x0,1          | ori x6,x0,2 ;
 lr.w x7,0(x5)       | st.w x6,0(x5) ;
 bnez x6, 1f         | ;
 nop                     | ;
1:                         | ;
 lr.w x8,0(x5)        | ;
 sc.w x9,x6,0(x5) | ;
forall
(x=1 /\ 0:x7=2 /\ 0:x8=2 /\ 0:x9=0) \/
(x=1 /\ 0:x7=0 /\ 0:x8=2 /\ 0:x9=0) \/
(x=2 /\ 0:x7=0 /\ 0:x8=2 /\ 0:x9=2) \/
(x=2 /\ 0:x7=2 /\ 0:x8=2 /\ 0:x9=2) \/
(x=2 /\ 0:x7=0 /\ 0:x8=0 /\ 0:x9=2) \/
(x=2 /\ 0:x7=0 /\ 0:x8=0 /\ 0:x9=0)

Here is the presentation for detail:

https://docs.google.com/presentation/d/1UudBcj4cL_cjJexMpZNF9ppRzYxeYqsdBotIvU7sO2Q/edit?usp=sharing

[Edited Message Follows]

Derek,

Thx for sharing the presentation with us; I spent some time chewing. So the reply is late.

--- The problems of qspinlock ---

The Linux queued-spinlock utilizes the lock_pending and mcs_spinlock mechanisms to reduce the struct qspinlock into 4 bytes. (The size requirement of Linux for generic spinlock.) The current version of queued-spinlock has split struct qspinlock into two parts: locked_pending and tail (for mcs_spinlock). And in terms of software design, they are considered half-word isolated, which also means that the author of qspinlock will not make any promises when lock_pending affects xchg_tail (I have updated [1] pages 6 & 7 to explain this problem in detail).

This is a challenge for RISC-V and IBM Power, which don't have the sub-word atomic instructions. (I also see that x86 is using BINARY_RMW (bit atomic) instead of AMOOR.W to optimize the queued_fetch_set_pending_acquire() function), which makes me deeply disturbed (ps: the author of qspinlock is from x86).

--- Power's experience can't clear my concerns ---
Firstly, riscv has AMO instructions, while Power is a pure LR/SC architecture. At this point, the two are fundamentally different. The current RISC-V spec states that there is no forward guarantee between LR/SC and "AMO or store" (refer to [1] page 4). This implies that RISC-V AMO and LR/SC implementation are separate and unequal. This leads to a significant asymmetry in the riscv-Linux atomic RMW & CAS primitives. IBM Power is based on pure LR/SC instructions, at least power-Linux atomic RMW & CAS primitives are balanced.

Secondly, the cloud server scenario of Power's 240 cores 1920 threads cannot cover all qspinlock situations. Because qspinlock has four working states (uncontended, pending, uncontended queue, contended queue), it will enter the contended queue state when there are too many contended harts. The lock_pending contention has ended, and qspinlock is stable in the xchg_tail contended queue state. So it isn't a target situation for the topic.

The frequent switching between the states of uncontended, pending, and uncontended queues is the problem. For example, in an embedded SoC scenario, two sockets (2cores/socket non-SMT) are interconnected through PCI-E CCIX to form 2 NUMA nodes SMP (the NUMA interconnect performance of the system is not good, and there is a significant latency). A strong guarantee level can help CPU hold the cacheline during qspinlock xchg_tail, avoiding NUMA cacheline dancing overhead caused by retries. Because the core speed is much higher than the NUMA interconnect, locking the cacheline for some cycles within the internal is acceptable.
Finally, I would like to ask a question: There are no atomic transactions in IBM Power OpenAXON's SMP interconnect (similar to Atomic Transactions in AMBA CHI: Atomic, AtomicFetch, AtomicSwap, AtomicCmpare), right?

--- About "add new SC failure code" ---

Due to the conflict between "Absolute Guarantee" and "LR generates Load page-fault exception in the spec," I gave up the absolute level (updated [1] pages 12, 13). Now my proposal only wants to define Strong Level in the spec explicitly. This is not to pull RISC-V back to a strong guarantee but to define both Weak and Strong in the ISA spec, just like we've done for RVWMO and RVTSO. The spec hints at a Strong Guarantee (see [1] pages 10, 11). And [1] page 9 points out the current Strong Guarantee has had hardware implementations. So, why can't we define a Strong Guarantee?

Compared with the text description, using litmus to define strong and weak levels may be more transparent and easier to understand. Hence, the proposal introduces a new SC failure code and three litmus HAND cases (STRONG_LR-SC, WEAK_LR-SC, CAS_LR-LR -SC).

The problem with RISC-V's guarantee is that it splits LR/SC and AMO (which is not IBM Power-friendly). The specification should require that LR/SC and AMO maintain the same guarantee level. If LR/SC is a weak guarantee, the CPU vendor should decompose AMO into LR+SC+BNEZ instead of implementing the guaranteed AMO.

Finally, I suggest clearly defining Weak and Strong levels in the ISA spec, and AMO and LR/SC should have the same guarantee level. The software should be designed according to the weak guarantee for better compatibility and performance (Similar to RVWMO & RVTSO).

--- About cmpxchg forward progress guarantee ---
I mentioned on [1] pages 15 and 16 how to implement the CMPXCHG guarantee further. In CAS_LR-LR-SC, LR/SC could contain multiple LR instructions with the same address. During lrscCycles - Backoffs, if you encounter another LR instruction with the same address, it will be regarded as a regular load instruction. The cacheline is still an exclusive/modified state and does not enter the Backoff process until it encounters SC or cycles out.

--- About transactional memory requirement ---
I agree that no/weak guarantee atomic could gain performance benefits, and could we leave it to the T-extension? T-extension still needs traditional AMO to implement the slow path)

[1] https://docs.google.com/presentation/d/1UudBcj4cL_cjJexMpZNF9ppRzYxeYqsdBotIvU7sO2Q/edit?usp=sharing

Best Regards

Guo Ren