[AArch64]: Atomic Exchange Allows Reordering past Acquire Fence

[lukeg101]

Consider the following litmus test that exposes buggy behaviour (this is a nasty bug):

C test

{ *x = 0; *y = 0; } // fixed initial state where x and y are 0

P0 (atomic_int* y,atomic_int* x) {
  atomic_store_explicit(x,1,memory_order_relaxed);
  atomic_thread_fence(memory_order_release);
  atomic_store_explicit(y,1,memory_order_relaxed);
}
P1 (atomic_int* y,atomic_int* x) {
  atomic_exchange_explicit(y,2,memory_order_release);
  atomic_thread_fence(memory_order_acquire);
  int r0 = atomic_load_explicit(x,memory_order_relaxed);
}

exists (P1:r0=0 /\ y=2)

where 'P0:r0 = 0' means thread P0, local variable r0 has value 0.

When simulating this test under the C/C++ model from its initial state, the outcome of execution in the exists clause is forbidden by the source model. The allowed outcomes are:

{ P1:r0=0; y=1; }
{ P1:r0=1; y=1; }
{ P1:r0=1; y=2; }

If we compile this with clang trunk for armv8.2-a using -O2 (https://godbolt.org/z/Grha1988f), we get the following test:

AArch64 test

{ [P1_r0]=0;[x]=0;[y]=0;
  uint64_t %P0_x=x; uint64_t %P0_y=y;
  uint64_t %P1_P1_r0=P1_r0;uint64_t %P1_x=x;uint64_t %P1_y=y }

  P0                |  P1                    ;
   MOV W9,#1        |   MOV W9,#2            ;
   STR W9,[X%P0_x]  |   SWP W9, WZR, [X%P1_y];
   DMB ISH          |   DMB ISHLD            ;
   STR W9,[X%P0_y]  |   LDR W8,[X%P1_x]      ;
   RET              |   STR W8,[X%P1_P1_r0]  ;
                    |   RET                  ;


exists (P1_r0=0 /\ [y]=2)

Which under the aarch64 model permits the following outcomes:

{ P1:r0=0; [y]=1; }
{ P1:r0=0; [y]=2; } <-- Forbidden by source model, a bug!
{ P1:r0=1; [y]=1; }
{ P1:r0=1; [y]=2; }

So what is going on? The SWP instruction as introduced in armv8.2-a with LSE is not regarded as doing a read for the acquire fence when the destination register is the zero register. In this case the write to y can be reordered past the DMB ISHLD fence so that we observe the load of x on P1 before the store to y. This results in the outcome {P1_r0 = 0; y=2} when the load of x on P1 occurs before the write of x on P0, and the write to y on P1 occurs after the store to y on P0.

This is caused by the LLVM dead register definitions pass, that zeros out the destination register of SWP, since it is not used in the source program. This optimisation is applied at -O1 and above, and hence we do not observe this bug with clang -O0. This does not occur in GCC (see Godbolt above), since the destination register is not zero'd out.

My advice is to not apply this optimisation to SWP so that the destination register is not zero'd out like in clang -O0

The official Arm AArch64 memory model has been updated to reflect this - hence my catching it now.

So what does this mean? Well it means there are thread-local optimisations that are influencing the semantics of concurrent programs. This is a standard re-ordering bug as far as concurrency is concerned, but you can only observe this when you don't keep the value of the atomic_exchange around to observe it. In other words it is a new class of heisenbug! This raises questions of whether there are more bugs like this.

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Consider the following litmus test that exposes buggy behaviour (this is a nasty bug): ``` C test

{ *x = 0; *y = 0; } // fixed initial state where x and y are 0

P0 (atomic_int* y,atomic_int* x) {
atomic_store_explicit(x,1,memory_order_relaxed);
atomic_thread_fence(memory_order_release);
atomic_store_explicit(y,1,memory_order_relaxed);
}
P1 (atomic_int* y,atomic_int* x) {
atomic_exchange_explicit(y,2,memory_order_release);
atomic_thread_fence(memory_order_acquire);
int r0 = atomic_load_explicit(x,memory_order_relaxed);
}

exists (P1:r0=0 /\ y=2)

where 'P0:r0 = 0' means thread P0, local variable r0 has value 0.

When simulating this test under the C/C++ model from its initial state, the outcome of execution in the exists clause is forbidden by the source model. The allowed outcomes are:

{ P1:r0=0; y=1; }
{ P1:r0=1; y=1; }
{ P1:r0=1; y=2; }

If we compile this with clang trunk for armv8.2-a using -O2 (https://godbolt.org/z/Grha1988f), we get the following test:

AArch64 test

{ [P1_r0]=0;[x]=0;[y]=0;
uint64_t %P0_x=x; uint64_t %P0_y=y;
uint64_t %P1_P1_r0=P1_r0;uint64_t %P1_x=x;uint64_t %P1_y=y }

P0 | P1 ;
MOV W9,#1 | MOV W9,#2 ;
STR W9,[X%P0_x] | SWP W9, WZR, [X%P1_y] ;
DMB ISH | DMB ISHLD ;
STR W9,[X%P0_y] | LDR W8,[X%P1_x] ;
RET | STR W8,[X%P1_P1_r0] ;
| RET ;

exists (P1_r0=0 /\ [y]=2)

Which under the aarch64 model permits the following outcomes:

{ P1:r0=0; [y]=1; }
{ P1:r0=0; [y]=2; } <-- Forbidden by source model, a bug!
{ P1:r0=1; [y]=1; }
{ P1:r0=1; [y]=2; }

So what is going on? The SWP instruction as introduced in armv8.2-a with LSE is not regarded as doing a read when the destination register is the zero register. In this case the write to y can be reordered past the `DMB ISHLD` fence so that we observe the load of x on P1 before the store to y. This results in the outcome `{P1_r0 = 0; y=2}` when the load of x on P1 occurs before the write of x on P0, and the write to y on P1 occurs after the store to y on P0.

This is caused by the LLVM dead register definitions [pass](https://llvm.org/docs/doxygen/AArch64DeadRegisterDefinitionsPass_8cpp_source.html), that zeros out the destination register of SWP, since it is not used in the source program. This optimisation is applied at `-O1` and above, and hence we do not observe this bug with `clang -O0`. This does not occur in GCC (see Godbolt above), since the destination register is not zero'd out. 

My advice is to not apply this optimisation to `SWP` so that the destination register is not zero'd out like in clang `-O0`

The official Arm AArch64 memory model has been updated to reflect this - hence my catching it now.

So what does this mean? Well it means there are thread-local optimisations that are influencing the semantics of concurrent programs. This is a standard re-ordering bug as far as concurrency is concerned, but you can only observe this when you don't keep the value of the `compare_exchange` around to observe it. In other words it is a [heisenbug](https://en.wikipedia.org/wiki/Heisenbug)! This raises questions of whether there are more bugs like this.



</details>

[lukeg101]

This applies to int, int8_t, int16_t, int32_t, int64_t, but not __int128_t
https://godbolt.org/z/xTKx4s3be

[statham-arm]

Hmmm. Are you sure of the diagnosis? I can't make it match the ARMARM.

In the ARMARM (version DDI 0487J.a), the AArch64 SWP instruction is documented in §C6.2.368, and it comes in four variants: SWP, SWPA, SWPL, SWPAL. The A variants have acquire semantics and the L variants have release semantics. As you say, the acquire semantics are conditional on the destination register not being WZR or XZR.

The litmus test in your comment above includes plain SWP, which has neither acquire nor release semantics. But in your godbolt link, both clang and gcc are generating SWPL, so that's already a mismatch. But SWPL only has release semantics, not acquire, regardless of whether the destination register is wzr.

So if this example needs the swap instruction to have release semantics, then it should have them unconditionally, because it's a SWPL; zeroing the destination register shouldn't make a difference. On the other hand, if it needs to have acquire semantics, then it unconditionally won't have them, because it's not SWPA or SWPAL – and I'd expect that to be true of both the clang and gcc output.

And the dead register definitions pass does check whether the predicate atomicBarrierDroppedOnZero applies to the opcode, and inhibits the change if so. SWPA and SWPAL are included in that. That looks correct to me: it's OK to make the change in SWP and SWPL.

Can you explain a bit more?

[lukeg101]

Hi @statham-arm,
Thanks for looking into this, I can clarify these points one by one :)

The A variants have acquire semantics and the L variants have release semantics.

Surprisingly the official Arm AArch64 model permits the buggy behaviour regardless of the memory order specified by the instruction when the destination register is zero'd. The bug however disappears if any other register is used.

Consider the test that reflects the Godbolt code (using SWPL):

AArch64 test

{ [P1_r0]=0;[x]=0;[y]=0;uint64_t %P0_x=x;uint64_t %P0_y=y;uint64_t %P1_P1_r0=P1_r0;uint64_t %P1_x=x;uint64_t %P1_y=y }

  P0                |  P1                    ;
   MOV W9,#1        |   MOV W9,#2            ;
   STR W9,[X%P0_x]  |   SWPL W9, WZR,[X%P1_y];
   DMB ISH          |   DMB ISHLD            ;
   STR W9,[X%P0_y]  |   LDR W8,[X%P1_x]      ;
                    |   STR W8,[X%P1_P1_r0]  ;
                    |                        ;


exists (P1_r0=0 /\ [y]=2)

when simulated under the Arm AArch64 model we get the following outcomes:

{ [P1_r0]=0; [y]=1; }
{ [P1_r0]=0; [y]=2; } <-- bug forbidden by source model.
{ [P1_r0]=1; [y]=1; }
{ [P1_r0]=1; [y]=2; }

The same holds for any use of A/L/AL/non-atomic. The presence of the zero register overwrites any memory ordering specified.

However if we change the destination register of SWPL to any register other than zero, then we do not observe the bug:

AArch64 test

{ [P1_r0]=0;[x]=0;[y]=0;uint64_t %P0_x=x;uint64_t %P0_y=y;uint64_t %P1_P1_r0=P1_r0;uint64_t %P1_x=x;uint64_t %P1_y=y }

  P0                |  P1                    ;
   MOV W9,#1        |   MOV W9,#2            ;
   STR W9,[X%P0_x]  |   SWPL W9, W15,[X%P1_y];
   DMB ISH          |   DMB ISHLD            ;
   STR W9,[X%P0_y]  |   LDR W8,[X%P1_x]      ;
   RET              |   STR W8,[X%P1_P1_r0]  ;
                    |   RET                  ;


exists (P1_r0=0 /\ [y]=2)

and its outcomes allowed by AArch64:

{ [P1_r0]=0; [y]=1; }
{ [P1_r0]=1; [y]=1; }
{ [P1_r0]=1; [y]=2; }

it's OK to make the change in SWP and SWPL.

As a result of the above I understand this to mean SWPL in this case should not make the change.

Further, if we set the memory order to the atomic_exchange to memory_order_relaxed, then a SWP is generated (https://godbolt.org/z/6o434YxoY). Which suffers the same fate as the above - so SWP should not make the change either.

Does this make sense? I'm happy to talk more :)

[statham-arm]

Off-list you pointed to herd/herdtools7#683 as related to this, which includes a comment that clarified things a bit for me: it said that SWP instructions targeting zr are not "regarded as a read for the purposes of DMB.LD".

I think that's the hole in my previous analysis: it's not just about whether this instruction itself has acquire or release semantics, it's also about whether its effect has to be sequenced before/after other instructions that have acquire/release semantics.

Thanks, I think that's clearer now. I agree that it looks as if SWP and SWPL should be added to the list of instructions in AArch64's atomicBarrierDroppedOnZero predicate, or (if we feel that that's not technically accurate given the name of that predicate) to some new additional list that will still inhibit removing the destination register in AArch64DeadRegisterDefinitionsPass.cpp.

[lukeg101]

Thanks Simon! I should note a similar bug arose several years ago with regards to the LD<OP> and ST<OP> instructions also added with LSE. Further, CAS also has this issue, but I could not find a bug the current C/C++ mappings to AArch64. If you create a new list, we could group all of these instructions together in that list for clarity as you mention :)

[gonzalobg]

The lowering from LLVM atomic exchange to SWAP with RZ on Arm is unsound, since the Arm ISA states that when RZ is used, SWAP is "a store" and not "an exchange".

Beyond fixing the bug, the source code should have documentation to prevent future developers from trying to perform this optimization (related to #69503, which proposes documenting this for atomicrmw add, in which lowerings to LDADD with RZ or to STADD are unsound for the same reasons).

[pratlucas]

I've posted the PR #102139 with a fix for SWP. It uses an existing atomicReadDroppedOnZero function from the pass' code, which is well documented and covers the same scenario for the LD<Op> variants.

The CAS instructions are not affected by this issue, as their output operand is tied to the corresponding source operand, causing the pass to ignore them.