> Hi ARM experts,

Hi Thomas, not at all an ARM expert... :)
but I think I understand the code.

> I am trying to understand how CAS is implemented on arm; in particular, 
> "MacroAssembler::atomic_cas_bool":

> MacroAssembler::atomic_cas_bool

> ```
>     assert_different_registers(tmp_reg, oldval, newval, base);
>     Label loop;
>     bind(loop);
> A   ldrex(tmp_reg, Address(base, offset));
> B   subs(tmp_reg, tmp_reg, oldval);
> C   strex(tmp_reg, newval, Address(base, offset), eq);
> D   cmp(tmp_reg, 1, eq);
> E   b(loop, eq);
> F   cmp(tmp_reg, 0);
>     if (tmpreg == noreg) {
>       pop(tmp_reg);
>     }
> ```

> It uses LDREX and STREX to perform a cas of *(base+offset) from oldval to 
> newval. It does so in a loop. The code distinguishes two failures: STREX 
> failing, and a "semantically failed" CAS.

> Here is what I think this code does:

> A) LDREX: tmp=*(base+offset)
> B) tmp -= oldvalue
>    If *(base+offset) was unchanged, tmp_reg is now 0 and Z is 1
> C) If Z is 1: STREX the new value: *(base+offset)=newval. Otherwise, omit.
>    After this, if the store succeeded, tmp_reg is 0, if the store failed its 
> 1.
> D) Here, tmp_reg is: 0 if the store succeeded, 1 if it failed, 1...n if 
> *(base+offset) had been modified before LDREX.
>    We now compare with 1 and ...
> E) ...repeat the loop if tmp_reg was 1

> So we loop until either *(base+offset) had been changed to some other value 
> concurrently before out LDREX. Or until our store succeeded.

> I wondered what the loop guards against. And why it would be okay sometimes 
> to omit it.

The loop is needed to try again if the reservation was lost until the STREX 
succeeds or *(base+offset) != oldvalue.

So there are two cases. The loop is left iff

(1) *(base+offset) != oldvalue
(2) the STREX succeeded

First it is important to understand that C, D, E are only executed if at B the 
eq-condition is set to true.
This is based on the "Conditional Execution" feature of ARM: execution of most 
instructions can be made dependent on a condition (see 
https://developer.arm.com/documentation/den0013/d/ARM-Thumb-Unified-Assembly-Language-Instructions/Instruction-set-basics/Conditional-execution?lang=en)

So in case (1) C, D, E are not executed because B indicates that *(base+offset) 
and oldvalue are not-eq and the loop is left.

In case (2) C, D, E are executed. At C, if the reservation from A still exists, 
tmp_reg will be set to 0 otherwise to 1. At E the branch is taken if D 
indicated tmp_reg == 1 (reservation was lost) otherwise the loop is left.

Cheers, Richard.

From: porters-dev <porters-dev-r...@openjdk.org> on behalf of Thomas Stüfe 
<thomas.stu...@gmail.com>
Date: Saturday, 11. March 2023 at 11:19
To: porters-dev@openjdk.org <porters-dev@openjdk.org>, 
aarch32-port-...@openjdk.org <aarch32-port-...@openjdk.org>
Subject: Question about CAS via LDREX/STREX on 32-bit arm
Hi ARM experts,

I am trying to understand how CAS is implemented on arm; in particular, 
"MacroAssembler::atomic_cas_bool":

MacroAssembler::atomic_cas_bool

```
    assert_different_registers(tmp_reg, oldval, newval, base);
    Label loop;
    bind(loop);
A   ldrex(tmp_reg, Address(base, offset));
B   subs(tmp_reg, tmp_reg, oldval);
C   strex(tmp_reg, newval, Address(base, offset), eq);
D   cmp(tmp_reg, 1, eq);
E   b(loop, eq);
F   cmp(tmp_reg, 0);
    if (tmpreg == noreg) {
      pop(tmp_reg);
    }
```

It uses LDREX and STREX to perform a cas of *(base+offset) from oldval to 
newval. It does so in a loop. The code distinguishes two failures: STREX 
failing, and a "semantically failed" CAS.
Here is what I think this code does:

A) LDREX: tmp=*(base+offset)
B) tmp -= oldvalue
   If *(base+offset) was unchanged, tmp_reg is now 0 and Z is 1
C) If Z is 1: STREX the new value: *(base+offset)=newval. Otherwise, omit.
   After this, if the store succeeded, tmp_reg is 0, if the store failed its 1.
D) Here, tmp_reg is: 0 if the store succeeded, 1 if it failed, 1...n if 
*(base+offset) had been modified before LDREX.
   We now compare with 1 and ...
E) ...repeat the loop if tmp_reg was 1

So we loop until either *(base+offset) had been changed to some other value 
concurrently before out LDREX. Or until our store succeeded.

I wondered what the loop guards against. And why it would be okay sometimes to 
omit it.

IIUC, STREX fails if the core did lose its exclusive access to the memory 
location since the LDREX. This can be one of three things, right? :
- another core slipped in an LDREX+STREX to the same location between our LDREX 
and STREX
- Or we context switched to another thread or process. I assume it does a CLREX 
then, right? Because how could you prevent a sequence like "LDREX(p1) -> switch 
-> LDREX(p2) -> switch back STREX(p1)" - if I understand the ARM manual [1] 
correctly, a STREX to a different location than the preceding LDREX is 
undefined.
- Or we had a signal after LDREX and did a second LDREX in the signal handler. 
Does the kernel do a CLREX when invoking a signal handler?

More questions:

- If I got it right, at (D), tmp_reg value "1" has two meanings: either STREX 
failed or some thread increased the value concurrently by 1. We repeat the loop 
either way. Is this just accepted behavior? Increasing by 1 is maybe not that 
rare.

- If I understood this correctly, the loop guards us mainly against context 
switches. Without the loop a context switch would count as a "semantically 
failed" CAS. Why would that be okay? Should we not do this loop always?

- Do we not need an explicit CLREX after the operation? Or does the STREX also 
clear the hardware monitor? Or does it just not matter?

- We have VM_Version::supports_ldrex(). Code seems to me sometimes guarded by 
this (e.g MacroAssembler::atomic_cas_bool), sometimes code just executes 
ldrex/strex (e.g. the one-shot path of MacroAssembler::cas_for_lock_acquire). 
Am I mistaken? Or is LDREX now generally available? Does ARMv6 mean STREX and 
LDREX are available?


Thanks a lot!

Cheers, Thomas


Reply via email to