Skip to contentSkip to conversation

selftests/bpf: Fix arena_atomics selftest failure due to llvm change

PATCH Superseded Yonghong Song 3 participants 7 messages Aug 3, 2024 – Aug 12, 2024

Subsystems (3)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

PATCH v2 1/1 selftests/bpf: Fix arena_atomics selftest failure due to llvm change

Peilen Ye reported an issue ([1]) where for __sync_fetch_and_add(...) without return value like
__sync_fetch_and_add(&foo, 1);
llvm BPF backend generates locked insn e.g.
lock *(u32 *)(r1 + 0) += r2

If __sync_fetch_and_add(...) returns a value like
res = __sync_fetch_and_add(&foo, 1);
llvm BPF backend generates like
r2 = atomic_fetch_add((u32 *)(r1 + 0), r2)

But 'lock *(u32 *)(r1 + 0) += r2' caused a problem in jit
since proper barrier is not inserted based on __sync_fetch_and_add() semantics.

The above discrepancy is due to commit [2] where it tries to maintain backward compatability since before commit [2], __sync_fetch_and_add(...) generates lock insn in BPF backend.

Based on discussion in [1], now it is time to fix the above discrepancy so we can have proper barrier support in jit. llvm patch [3] made sure that __sync_fetch_and_add(...) always generates atomic_fetch_add(...) insns. Now 'lock *(u32 *)(r1 + 0) += r2' can only be generated by inline asm. The same for __sync_fetch_and_and(), __sync_fetch_and_or() and __sync_fetch_and_xor().

But the change in [3] caused arena_atomics selftest failure.

test_arena_atomics:PASS:arena atomics skeleton open 0 nsec
libbpf: prog 'and': BPF program load failed: Permission denied
libbpf: prog 'and': -- BEGIN PROG LOAD LOG --
arg#0 reference type('UNKNOWN ') size cannot be determined: -22
0: R1=ctx() R10=fp0
; if (pid != (bpf_get_current_pid_tgid() >> 32)) @ arena_atomics.c:87
0: (18) r1 = 0xffffc90000064000 ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4)
2: (61) r6 = *(u32 *)(r1 +0) ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
3: (85) call bpf_get_current_pid_tgid#14 ; R0_w=scalar()
4: (77) r0 >>= 32 ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
5: (5d) if r0 != r6 goto pc+11 ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0x)
; __sync_fetch_and_and(&and64_value, 0x011ull << 32); @ arena_atomics.c:91
6: (18) r1 = 0x100000000060 ; R1_w=scalar()
8: (bf) r1 = addr_space_cast(r1, 0, 1) ; R1_w=arena
9: (18) r2 = 0x1100000000 ; R2_w=0x1100000000
11: (db) r2 = atomic64_fetch_and((u64 *)(r1 +0), r2)
BPF_ATOMIC stores into R1 arena is not allowed
processed 9 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 -- END PROG LOAD LOG --
libbpf: prog 'and': failed to load: -13
libbpf: failed to load object 'arena_atomics'
libbpf: failed to load BPF skeleton 'arena_atomics': -13 test_arena_atomics:FAIL:arena atomics skeleton load unexpected error: -13 (errno 13)
#3 arena_atomics:FAIL

The reason of the failure is due to [4] where atomic{64,}_fetch_{and,or,xor}() are not allowed by arena addresses. Without llvm patch [3], the compiler will generate 'lock ...' insn and everything will work fine.

This patch fixed the problem by using inline asms. Instead of __sync_fetch_and_{and,or,xor}() functions, the inline asm with 'lock' insn is used and it will work with or without [3].
Note that three bpf programs ('and', 'or' and 'xor') are guarded with __BPF_FEATURE_ADDR_SPACE_CAST as well to ensure compilation failure for llvm <= 18 version. Note that for llvm <= 18 where addr_space_cast is not supported, all arena_atomics subtests are skipped with below message:
test_arena_atomics:SKIP:no ENABLE_ATOMICS_TESTS or no addr_space_cast support in clang #3 arena_atomics:SKIP

[1] https://lore.kernel.org/bpf/[email protected]/T/#mb68d67bc8f39e35a0c3db52468b9de59b79f021f
[2] https://github.com/llvm/llvm-project/commit/286daafd65129228e08a1d07aa4ca74488615744
[3] https://github.com/llvm/llvm-project/pull/101428
[4] d503a04f8bc0 ("bpf: Add support for certain atomics in bpf_arena to x86 JIT")

---
 .../selftests/bpf/progs/arena_atomics.c       | 63 ++++++++++++++++---
 1 file changed, 54 insertions(+), 9 deletions(-)

Changelog:
v1 -> v2:
- Add __BPF_FEATURE_ADDR_SPACE_CAST to guard newly added asm codes for llvm >= 19

tools/testing/selftests/bpf/progs/arena_atomics.c +54 -9
index bb0acd79d28a..dea54557fc00 100644
@@ -5,6 +5,7 @@
 #include <bpf/bpf_tracing.h>
 #include <stdbool.h>
 #include "bpf_arena_common.h"
+#include "bpf_misc.h"
 
 struct {
 	__uint(type, BPF_MAP_TYPE_ARENA);
@@ -85,10 +86,24 @@ int and(const void *ctx)
 {
 	if (pid != (bpf_get_current_pid_tgid() >> 32))
 		return 0;
-#ifdef ENABLE_ATOMICS_TESTS
+#if defined(ENABLE_ATOMICS_TESTS) && defined(__BPF_FEATURE_ADDR_SPACE_CAST)
 
-	__sync_fetch_and_and(&and64_value, 0x011ull << 32);
-	__sync_fetch_and_and(&and32_value, 0x011);
+	asm volatile(
+		"r1 = addr_space_cast(%[and64_value], 0, 1);"
+		"lock *(u64 *)(r1 + 0) &= %[val]"
+		:
+		: __imm_ptr(and64_value),
+		  [val]"r"(0x011ull << 32)
+		: "r1"
+	);
+	asm volatile(
+		"r1 = addr_space_cast(%[and32_value], 0, 1);"
+		"lock *(u32 *)(r1 + 0) &= %[val]"
+		:
+		: __imm_ptr(and32_value),
+		  [val]"w"(0x011)
+		: "r1"
+	);
 #endif
 
 	return 0;
@@ -102,9 +117,24 @@ int or(const void *ctx)
 {
 	if (pid != (bpf_get_current_pid_tgid() >> 32))
 		return 0;
-#ifdef ENABLE_ATOMICS_TESTS
-	__sync_fetch_and_or(&or64_value, 0x011ull << 32);
-	__sync_fetch_and_or(&or32_value, 0x011);
+#if defined(ENABLE_ATOMICS_TESTS) && defined(__BPF_FEATURE_ADDR_SPACE_CAST)
+
+	asm volatile(
+		"r1 = addr_space_cast(%[or64_value], 0, 1);"
+		"lock *(u64 *)(r1 + 0) |= %[val]"
+		:
+		: __imm_ptr(or64_value),
+		  [val]"r"(0x011ull << 32)
+		: "r1"
+	);
+	asm volatile(
+		"r1 = addr_space_cast(%[or32_value], 0, 1);"
+		"lock *(u32 *)(r1 + 0) |= %[val]"
+		:
+		: __imm_ptr(or32_value),
+		  [val]"w"(0x011)
+		: "r1"
+	);
 #endif
 
 	return 0;
@@ -118,9 +148,24 @@ int xor(const void *ctx)
 {
 	if (pid != (bpf_get_current_pid_tgid() >> 32))
 		return 0;
-#ifdef ENABLE_ATOMICS_TESTS
-	__sync_fetch_and_xor(&xor64_value, 0x011ull << 32);
-	__sync_fetch_and_xor(&xor32_value, 0x011);
+#if defined(ENABLE_ATOMICS_TESTS) && defined(__BPF_FEATURE_ADDR_SPACE_CAST)
+
+	asm volatile(
+		"r1 = addr_space_cast(%[xor64_value], 0, 1);"
+		"lock *(u64 *)(r1 + 0) ^= %[val]"
+		:
+		: __imm_ptr(xor64_value),
+		  [val]"r"(0x011ull << 32)
+		: "r1"
+	);
+	asm volatile(
+		"r1 = addr_space_cast(%[xor32_value], 0, 1);"
+		"lock *(u32 *)(r1 + 0) ^= %[val]"
+		:
+		: __imm_ptr(xor32_value),
+		  [val]"w"(0x011)
+		: "r1"
+	);
 #endif
 
 	return 0;
Signature · 1 line
2.43.0
#1 lore raw
Quoted 105 lines · Yonghong Song

Peilen Ye reported an issue ([1]) where for __sync_fetch_and_add(...) without return value like
__sync_fetch_and_add(&foo, 1);
llvm BPF backend generates locked insn e.g.
lock *(u32 *)(r1 + 0) += r2

If __sync_fetch_and_add(...) returns a value like
res = __sync_fetch_and_add(&foo, 1);
llvm BPF backend generates like
r2 = atomic_fetch_add((u32 *)(r1 + 0), r2)

But 'lock *(u32 *)(r1 + 0) += r2' caused a problem in jit
since proper barrier is not inserted based on __sync_fetch_and_add() semantics.

The above discrepancy is due to commit [2] where it tries to maintain backward compatability since before commit [2], __sync_fetch_and_add(...) generates lock insn in BPF backend.

Based on discussion in [1], now it is time to fix the above discrepancy so we can have proper barrier support in jit. llvm patch [3] made sure that __sync_fetch_and_add(...) always generates atomic_fetch_add(...) insns. Now 'lock *(u32 *)(r1 + 0) += r2' can only be generated by inline asm. The same for __sync_fetch_and_and(), __sync_fetch_and_or() and __sync_fetch_and_xor().

But the change in [3] caused arena_atomics selftest failure.

test_arena_atomics:PASS:arena atomics skeleton open 0 nsec
libbpf: prog 'and': BPF program load failed: Permission denied
libbpf: prog 'and': -- BEGIN PROG LOAD LOG --
arg#0 reference type('UNKNOWN ') size cannot be determined: -22
0: R1=ctx() R10=fp0
; if (pid != (bpf_get_current_pid_tgid() >> 32)) @ arena_atomics.c:87
0: (18) r1 = 0xffffc90000064000 ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4)
2: (61) r6 = *(u32 *)(r1 +0) ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
3: (85) call bpf_get_current_pid_tgid#14 ; R0_w=scalar()
4: (77) r0 >>= 32 ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
5: (5d) if r0 != r6 goto pc+11 ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0x)
; __sync_fetch_and_and(&and64_value, 0x011ull << 32); @ arena_atomics.c:91
6: (18) r1 = 0x100000000060 ; R1_w=scalar()
8: (bf) r1 = addr_space_cast(r1, 0, 1) ; R1_w=arena
9: (18) r2 = 0x1100000000 ; R2_w=0x1100000000
11: (db) r2 = atomic64_fetch_and((u64 *)(r1 +0), r2)
BPF_ATOMIC stores into R1 arena is not allowed
processed 9 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 -- END PROG LOAD LOG --
libbpf: prog 'and': failed to load: -13
libbpf: failed to load object 'arena_atomics'
libbpf: failed to load BPF skeleton 'arena_atomics': -13 test_arena_atomics:FAIL:arena atomics skeleton load unexpected error: -13 (errno 13)
#3 arena_atomics:FAIL

The reason of the failure is due to [4] where atomic{64,}_fetch_{and,or,xor}() are not allowed by arena addresses. Without llvm patch [3], the compiler will generate 'lock ...' insn and everything will work fine.

This patch fixed the problem by using inline asms. Instead of __sync_fetch_and_{and,or,xor}() functions, the inline asm with 'lock' insn is used and it will work with or without [3].
Note that three bpf programs ('and', 'or' and 'xor') are guarded with __BPF_FEATURE_ADDR_SPACE_CAST as well to ensure compilation failure for llvm <= 18 version. Note that for llvm <= 18 where addr_space_cast is not supported, all arena_atomics subtests are skipped with below message:
test_arena_atomics:SKIP:no ENABLE_ATOMICS_TESTS or no addr_space_cast support in clang #3 arena_atomics:SKIP

[1] https://lore.kernel.org/bpf/[email protected]/T/#mb68d67bc8f39e35a0c3db52468b9de59b79f021f
[2] https://github.com/llvm/llvm-project/commit/286daafd65129228e08a1d07aa4ca74488615744
[3] https://github.com/llvm/llvm-project/pull/101428
[4] d503a04f8bc0 ("bpf: Add support for certain atomics in bpf_arena to x86 JIT")

---
 .../selftests/bpf/progs/arena_atomics.c       | 63 ++++++++++++++++---
 1 file changed, 54 insertions(+), 9 deletions(-)

Changelog:
v1 -> v2:
- Add __BPF_FEATURE_ADDR_SPACE_CAST to guard newly added asm codes for llvm >= 19

tools/testing/selftests/bpf/progs/arena_atomics.c +8 -3
index bb0acd79d28a..dea54557fc00 100644
@@ -5,6 +5,7 @@
 #include <bpf/bpf_tracing.h>
 #include <stdbool.h>
 #include "bpf_arena_common.h"
+#include "bpf_misc.h"
 
 struct {
        __uint(type, BPF_MAP_TYPE_ARENA);
@@ -85,10 +86,24 @@ int and(const void *ctx)
 {
        if (pid != (bpf_get_current_pid_tgid() >> 32))
                return 0;
-#ifdef ENABLE_ATOMICS_TESTS
+#if defined(ENABLE_ATOMICS_TESTS) && defined(__BPF_FEATURE_ADDR_SPACE_CAST)
 
-       __sync_fetch_and_and(&and64_value, 0x011ull << 32);
-       __sync_fetch_and_and(&and32_value, 0x011);
+       asm volatile(
+               "r1 = addr_space_cast(%[and64_value], 0, 1);"
+               "lock *(u64 *)(r1 + 0) &= %[val]"
+               :
+               : __imm_ptr(and64_value),
+                 [val]"r"(0x011ull << 32)

tools/testing/selftests/bpf/progs/arena_atomics.c int and(const void *ctx) · line 106

Quoted 10 lines
tools/testing/selftests/bpf/progs/arena_atomics.c +10 -0
+               : "r1"
+       );
+       asm volatile(
+               "r1 = addr_space_cast(%[and32_value], 0, 1);"
+               "lock *(u32 *)(r1 + 0) &= %[val]"
+               :
+               : __imm_ptr(and32_value),
+                 [val]"w"(0x011)
+               : "r1"
+       );

Instead of inline asm there is a better way to do the same in C.
https://godbolt.org/z/71PYx1oqE

void foo(int a, _Atomic int *b)
{
*b += a;
}

generates:
lock *(u32 *)(r2 + 0) += r1

but
*b &= a;

crashes llvm :( with

<source>:3:5: error: unsupported atomic operation, please use 64 bit version

    3 |  *b &= a;

but works with -mcpu=v3

So let's make this test mcpu=v3 only and use normal C ?

pw-bot: cr

author reviewer
#2 lore raw
Quoted 118 lines · Alexei Starovoitov
Quoted 104 lines · Yonghong Song

Peilen Ye reported an issue ([1]) where for __sync_fetch_and_add(...) without return value like
__sync_fetch_and_add(&foo, 1);
llvm BPF backend generates locked insn e.g.
lock *(u32 *)(r1 + 0) += r2

If __sync_fetch_and_add(...) returns a value like
res = __sync_fetch_and_add(&foo, 1);
llvm BPF backend generates like
r2 = atomic_fetch_add((u32 *)(r1 + 0), r2)

But 'lock *(u32 *)(r1 + 0) += r2' caused a problem in jit
since proper barrier is not inserted based on __sync_fetch_and_add() semantics.

The above discrepancy is due to commit [2] where it tries to maintain backward compatability since before commit [2], __sync_fetch_and_add(...) generates lock insn in BPF backend.

Based on discussion in [1], now it is time to fix the above discrepancy so we can have proper barrier support in jit. llvm patch [3] made sure that __sync_fetch_and_add(...) always generates atomic_fetch_add(...) insns. Now 'lock *(u32 *)(r1 + 0) += r2' can only be generated by inline asm. The same for __sync_fetch_and_and(), __sync_fetch_and_or() and __sync_fetch_and_xor().

But the change in [3] caused arena_atomics selftest failure.

   test_arena_atomics:PASS:arena atomics skeleton open 0 nsec
   libbpf: prog 'and': BPF program load failed: Permission denied
   libbpf: prog 'and': -- BEGIN PROG LOAD LOG --
   arg#0 reference type('UNKNOWN ') size cannot be determined: -22
   0: R1=ctx() R10=fp0
   ; if (pid != (bpf_get_current_pid_tgid() >> 32)) @ arena_atomics.c:87
   0: (18) r1 = 0xffffc90000064000       ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4)
   2: (61) r6 = *(u32 *)(r1 +0)          ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
   3: (85) call bpf_get_current_pid_tgid#14      ; R0_w=scalar()
   4: (77) r0 >>= 32                     ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
   5: (5d) if r0 != r6 goto pc+11        ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0x)
   ; __sync_fetch_and_and(&and64_value, 0x011ull << 32); @ arena_atomics.c:91
   6: (18) r1 = 0x100000000060           ; R1_w=scalar()
   8: (bf) r1 = addr_space_cast(r1, 0, 1)        ; R1_w=arena
   9: (18) r2 = 0x1100000000             ; R2_w=0x1100000000
   11: (db) r2 = atomic64_fetch_and((u64 *)(r1 +0), r2)
   BPF_ATOMIC stores into R1 arena is not allowed
   processed 9 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
   -- END PROG LOAD LOG --
   libbpf: prog 'and': failed to load: -13
   libbpf: failed to load object 'arena_atomics'
   libbpf: failed to load BPF skeleton 'arena_atomics': -13
   test_arena_atomics:FAIL:arena atomics skeleton load unexpected error: -13 (errno 13)
   #3       arena_atomics:FAIL

The reason of the failure is due to [4] where atomic{64,}_fetch_{and,or,xor}() are not allowed by arena addresses. Without llvm patch [3], the compiler will generate 'lock ...' insn and everything will work fine.

This patch fixed the problem by using inline asms. Instead of __sync_fetch_and_{and,or,xor}() functions, the inline asm with 'lock' insn is used and it will work with or without [3].
Note that three bpf programs ('and', 'or' and 'xor') are guarded with __BPF_FEATURE_ADDR_SPACE_CAST as well to ensure compilation failure for llvm <= 18 version. Note that for llvm <= 18 where addr_space_cast is not supported, all arena_atomics subtests are skipped with below message:

   test_arena_atomics:SKIP:no ENABLE_ATOMICS_TESTS or no addr_space_cast support in clang
   #3 arena_atomics:SKIP

   [1] https://lore.kernel.org/bpf/[email protected]/T/#mb68d67bc8f39e35a0c3db52468b9de59b79f021f
   [2] https://github.com/llvm/llvm-project/commit/286daafd65129228e08a1d07aa4ca74488615744
   [3] https://github.com/llvm/llvm-project/pull/101428
   [4] d503a04f8bc0 ("bpf: Add support for certain atomics in bpf_arena to x86 JIT")
---
  .../selftests/bpf/progs/arena_atomics.c       | 63 ++++++++++++++++---
  1 file changed, 54 insertions(+), 9 deletions(-)

Changelog:
v1 -> v2:
- Add __BPF_FEATURE_ADDR_SPACE_CAST to guard newly added asm codes for llvm >= 19

tools/testing/selftests/bpf/progs/arena_atomics.c +8 -3
index bb0acd79d28a..dea54557fc00 100644
@@ -5,6 +5,7 @@
  #include <bpf/bpf_tracing.h>
  #include <stdbool.h>
  #include "bpf_arena_common.h"
+#include "bpf_misc.h"
 
  struct {
         __uint(type, BPF_MAP_TYPE_ARENA);
@@ -85,10 +86,24 @@ int and(const void *ctx)
  {
         if (pid != (bpf_get_current_pid_tgid() >> 32))
                 return 0;
-#ifdef ENABLE_ATOMICS_TESTS
+#if defined(ENABLE_ATOMICS_TESTS) && defined(__BPF_FEATURE_ADDR_SPACE_CAST)
 
-       __sync_fetch_and_and(&and64_value, 0x011ull << 32);
-       __sync_fetch_and_and(&and32_value, 0x011);
+       asm volatile(
+               "r1 = addr_space_cast(%[and64_value], 0, 1);"
+               "lock *(u64 *)(r1 + 0) &= %[val]"
+               :
+               : __imm_ptr(and64_value),
+                 [val]"r"(0x011ull << 32)

tools/testing/selftests/bpf/progs/arena_atomics.c int and(const void *ctx) · line 106

Quoted 10 lines
tools/testing/selftests/bpf/progs/arena_atomics.c +10 -0
+               : "r1"
+       );
+       asm volatile(
+               "r1 = addr_space_cast(%[and32_value], 0, 1);"
+               "lock *(u32 *)(r1 + 0) &= %[val]"
+               :
+               : __imm_ptr(and32_value),
+                 [val]"w"(0x011)
+               : "r1"
+       );

Instead of inline asm there is a better way to do the same in C.
https://godbolt.org/z/71PYx1oqE

Quoted 7 lines

void foo(int a, _Atomic int *b)
{
*b += a;
}

generates:
lock *(u32 *)(r2 + 0) += r1

If you use latest llvm-project with
https://github.com/llvm/llvm-project/pull/101428
included, the above code will generate like

$ clang --target=bpf -O2 -c t.c && llvm-objdump -d t.o
t.o:    file format elf64-bpf
Disassembly of section .text:
0000000000000000 <foo>:
       0:       c3 12 00 00 01 00 00 00 r1 = atomic_fetch_add((u32 *)(r2 + 0x0), r1)
       1:       95 00 00 00 00 00 00 00 exit

With -mcpu=v3 the same code can be generated.

Quoted 8 lines

but
*b &= a;

crashes llvm :( with

<source>:3:5: error: unsupported atomic operation, please use 64 bit version

     3 |  *b &= a;

It failed with the following llvm error message:
t.c:1:6: error: unsupported atomic operation, please use 64 bit version
1 | void foo(int a, _Atomic int *b)
| ^
fatal error: error in backend: Cannot select: t8: i64,ch = AtomicLoadAnd<(load store seq_cst (s32) on %ir.b)> t0, t4, t2
t4: i64,ch = CopyFromReg t0, Register:i64 %1

    t3: i64 = Register %1
  t2: i64,ch = CopyFromReg t0, Register:i64 %0
    t1: i64 = Register %0

In function: foo

Quoted 2 lines

but works with -mcpu=v3

Yes. it does work with -mcpu=v3:

$ clang --target=bpf -O2 -mcpu=v3 -c t.c && llvm-objdump -d --mcpu=v3 t.o

t.o:    file format elf64-bpf
Disassembly of section .text:
0000000000000000 <foo>:
       0:       c3 12 00 00 51 00 00 00 w1 = atomic_fetch_and((u32 *)(r2 + 0x0), w1) 1:       95 00 00 00 00 00 00 00 exit

NOTE: I need -mcpu=v3 for llvm-objdump to print asm code 'atomic_fetch_and' properly. Will double check this.

For code:
void foo(int a, _Atomic int *b)
{
*b &= a;
}

The initial IR generated by clang frontend is:

define dso_local void @foo(i32 noundef %a, ptr noundef %b) #0 { entry:
%a.addr = alloca i32, align 4
%b.addr = alloca ptr, align 8
store i32 %a, ptr %a.addr, align 4, !tbaa !3
store ptr %b, ptr %b.addr, align 8, !tbaa !7
%0 = load i32, ptr %a.addr, align 4, !tbaa !3
%1 = load ptr, ptr %b.addr, align 8, !tbaa !7
%2 = atomicrmw and ptr %1, i32 %0 seq_cst, align 4 %3 = and i32 %2, %0
ret void
}

Note that atomicrmw in the above. Eventually it optimized to

define dso_local void @foo(i32 noundef %a, ptr noundef %b) #0 { entry:
%0 = atomicrmw and ptr %b, i32 %a seq_cst, align 4 ret void
}

The 'atomicrmw' is the same IR as generated by __sync_fetch_and_*() and eventually will generate atomic_fetch_*() bpf insn. Discussed with Andrii, and
another option is to specify relaxed consistency, so llvm internal could translate it into locked insn. For example,

$ cat t1.c
#include <stdatomic.h>

void f(_Atomic int *i) {
__c11_atomic_fetch_and(i, 1, memory_order_relaxed);
}

# to have gnu/stubs-32.h in the current directory to make it compile
[[email protected] ~/tmp6]$ ls gnu
stubs-32.h
[[email protected] ~/tmp6]$ clang --target=bpf -O2 -I. -c -mcpu=v3 t1.c

The initial IR:
define dso_local void @f(ptr noundef %i) #0 { entry:
%i.addr = alloca ptr, align 8
%.atomictmp = alloca i32, align 4 %atomic-temp = alloca i32, align 4
store ptr %i, ptr %i.addr, align 8, !tbaa !3 %0 = load ptr, ptr %i.addr, align 8, !tbaa !3 store i32 1, ptr %.atomictmp, align 4, !tbaa !7 %1 = load i32, ptr %.atomictmp, align 4
%2 = atomicrmw and ptr %0, i32 %1 monotonic, align 4 store i32 %2, ptr %atomic-temp, align 4
%3 = load i32, ptr %atomic-temp, align 4, !tbaa !7 ret void
}

The IR right before machine code generation:

define dso_local void @f(ptr nocapture noundef %i) local_unnamed_addr #0 { entry:
%0 = atomicrmw and ptr %i, i32 1 monotonic, align 4
ret void
}

Maybe we could special process the above to generate a locked insn if
- atomicrmw operator
- monotonic (related) consistency
- return value is not used

So this will not violate original program semantics. Does this sound a reasonable apporach?

Quoted 4 lines

So let's make this test mcpu=v3 only and use normal C ?

pw-bot: cr

#3 lore raw
Quoted 140 lines · Alexei Starovoitov
Quoted 118 lines · Yonghong Song
Quoted 104 lines

Peilen Ye reported an issue ([1]) where for __sync_fetch_and_add(...) without return value like
__sync_fetch_and_add(&foo, 1);
llvm BPF backend generates locked insn e.g.
lock *(u32 *)(r1 + 0) += r2

If __sync_fetch_and_add(...) returns a value like
res = __sync_fetch_and_add(&foo, 1);
llvm BPF backend generates like
r2 = atomic_fetch_add((u32 *)(r1 + 0), r2)

But 'lock *(u32 *)(r1 + 0) += r2' caused a problem in jit
since proper barrier is not inserted based on __sync_fetch_and_add() semantics.

The above discrepancy is due to commit [2] where it tries to maintain backward compatability since before commit [2], __sync_fetch_and_add(...) generates lock insn in BPF backend.

Based on discussion in [1], now it is time to fix the above discrepancy so we can have proper barrier support in jit. llvm patch [3] made sure that __sync_fetch_and_add(...) always generates atomic_fetch_add(...) insns. Now 'lock *(u32 *)(r1 + 0) += r2' can only be generated by inline asm. The same for __sync_fetch_and_and(), __sync_fetch_and_or() and __sync_fetch_and_xor().

But the change in [3] caused arena_atomics selftest failure.

   test_arena_atomics:PASS:arena atomics skeleton open 0 nsec
   libbpf: prog 'and': BPF program load failed: Permission denied
   libbpf: prog 'and': -- BEGIN PROG LOAD LOG --
   arg#0 reference type('UNKNOWN ') size cannot be determined: -22
   0: R1=ctx() R10=fp0
   ; if (pid != (bpf_get_current_pid_tgid() >> 32)) @ arena_atomics.c:87
   0: (18) r1 = 0xffffc90000064000       ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4)
   2: (61) r6 = *(u32 *)(r1 +0)          ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
   3: (85) call bpf_get_current_pid_tgid#14      ; R0_w=scalar()
   4: (77) r0 >>= 32                     ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
   5: (5d) if r0 != r6 goto pc+11        ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0x)
   ; __sync_fetch_and_and(&and64_value, 0x011ull << 32); @ arena_atomics.c:91
   6: (18) r1 = 0x100000000060           ; R1_w=scalar()
   8: (bf) r1 = addr_space_cast(r1, 0, 1)        ; R1_w=arena
   9: (18) r2 = 0x1100000000             ; R2_w=0x1100000000
   11: (db) r2 = atomic64_fetch_and((u64 *)(r1 +0), r2)
   BPF_ATOMIC stores into R1 arena is not allowed
   processed 9 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
   -- END PROG LOAD LOG --
   libbpf: prog 'and': failed to load: -13
   libbpf: failed to load object 'arena_atomics'
   libbpf: failed to load BPF skeleton 'arena_atomics': -13
   test_arena_atomics:FAIL:arena atomics skeleton load unexpected error: -13 (errno 13)
   #3       arena_atomics:FAIL

The reason of the failure is due to [4] where atomic{64,}_fetch_{and,or,xor}() are not allowed by arena addresses. Without llvm patch [3], the compiler will generate 'lock ...' insn and everything will work fine.

This patch fixed the problem by using inline asms. Instead of __sync_fetch_and_{and,or,xor}() functions, the inline asm with 'lock' insn is used and it will work with or without [3].
Note that three bpf programs ('and', 'or' and 'xor') are guarded with __BPF_FEATURE_ADDR_SPACE_CAST as well to ensure compilation failure for llvm <= 18 version. Note that for llvm <= 18 where addr_space_cast is not supported, all arena_atomics subtests are skipped with below message:

   test_arena_atomics:SKIP:no ENABLE_ATOMICS_TESTS or no addr_space_cast support in clang
   #3 arena_atomics:SKIP

   [1] https://lore.kernel.org/bpf/[email protected]/T/#mb68d67bc8f39e35a0c3db52468b9de59b79f021f
   [2] https://github.com/llvm/llvm-project/commit/286daafd65129228e08a1d07aa4ca74488615744
   [3] https://github.com/llvm/llvm-project/pull/101428
   [4] d503a04f8bc0 ("bpf: Add support for certain atomics in bpf_arena to x86 JIT")
---
  .../selftests/bpf/progs/arena_atomics.c       | 63 ++++++++++++++++---
  1 file changed, 54 insertions(+), 9 deletions(-)

Changelog:
v1 -> v2:
- Add __BPF_FEATURE_ADDR_SPACE_CAST to guard newly added asm codes for llvm >= 19

tools/testing/selftests/bpf/progs/arena_atomics.c +8 -3
index bb0acd79d28a..dea54557fc00 100644
@@ -5,6 +5,7 @@
  #include <bpf/bpf_tracing.h>
  #include <stdbool.h>
  #include "bpf_arena_common.h"
+#include "bpf_misc.h"
 
  struct {
         __uint(type, BPF_MAP_TYPE_ARENA);
@@ -85,10 +86,24 @@ int and(const void *ctx)
  {
         if (pid != (bpf_get_current_pid_tgid() >> 32))
                 return 0;
-#ifdef ENABLE_ATOMICS_TESTS
+#if defined(ENABLE_ATOMICS_TESTS) && defined(__BPF_FEATURE_ADDR_SPACE_CAST)
 
-       __sync_fetch_and_and(&and64_value, 0x011ull << 32);
-       __sync_fetch_and_and(&and32_value, 0x011);
+       asm volatile(
+               "r1 = addr_space_cast(%[and64_value], 0, 1);"
+               "lock *(u64 *)(r1 + 0) &= %[val]"
+               :
+               : __imm_ptr(and64_value),
+                 [val]"r"(0x011ull << 32)

tools/testing/selftests/bpf/progs/arena_atomics.c int and(const void *ctx) · line 106

Quoted 10 lines
tools/testing/selftests/bpf/progs/arena_atomics.c +10 -0
+               : "r1"
+       );
+       asm volatile(
+               "r1 = addr_space_cast(%[and32_value], 0, 1);"
+               "lock *(u32 *)(r1 + 0) &= %[val]"
+               :
+               : __imm_ptr(and32_value),
+                 [val]"w"(0x011)
+               : "r1"
+       );

Instead of inline asm there is a better way to do the same in C.
https://godbolt.org/z/71PYx1oqE

Quoted 7 lines

void foo(int a, _Atomic int *b)
{
*b += a;
}

generates:
lock *(u32 *)(r2 + 0) += r1

If you use latest llvm-project with
https://github.com/llvm/llvm-project/pull/101428
included, the above code will generate like

$ clang --target=bpf -O2 -c t.c && llvm-objdump -d t.o
t.o:    file format elf64-bpf
Disassembly of section .text:
0000000000000000 <foo>:
       0:       c3 12 00 00 01 00 00 00 r1 = atomic_fetch_add((u32 *)(r2 + 0x0), r1)
       1:       95 00 00 00 00 00 00 00 exit
Quoted 1 line

With -mcpu=v3 the same code can be generated.

Same for current GCC.

Quoted 18 lines
Quoted 8 lines

but
*b &= a;

crashes llvm :( with

<source>:3:5: error: unsupported atomic operation, please use 64 bit version

     3 |  *b &= a;

It failed with the following llvm error message:
t.c:1:6: error: unsupported atomic operation, please use 64 bit version
1 | void foo(int a, _Atomic int *b)
| ^
fatal error: error in backend: Cannot select: t8: i64,ch = AtomicLoadAnd<(load store seq_cst (s32) on %ir.b)> t0, t4, t2
t4: i64,ch = CopyFromReg t0, Register:i64 %1

    t3: i64 = Register %1
  t2: i64,ch = CopyFromReg t0, Register:i64 %0
    t1: i64 = Register %0
Quoted 6 lines

In function: foo

Quoted 2 lines

but works with -mcpu=v3

Yes. it does work with -mcpu=v3:

In GCC if you specify -mcpu=v2 and use atomic built-ins you get workaround code in the form of libcalls (like calls to __atomic_fetch_and_4) which are of course of no use in BPF atm.

Quoted 10 lines
$ clang --target=bpf -O2 -mcpu=v3 -c t.c && llvm-objdump -d --mcpu=v3 t.o

t.o:    file format elf64-bpf
Disassembly of section .text:
0000000000000000 <foo>:
       0:       c3 12 00 00 51 00 00 00 w1 = atomic_fetch_and((u32 *)(r2 + 0x0), w1) 1:       95 00 00 00 00 00 00 00 exit

NOTE: I need -mcpu=v3 for llvm-objdump to print asm code 'atomic_fetch_and' properly. Will double check this.

The GNU binutils objdump will try to recognize instructions in the latest supported cpu version, unless an explicit option is passed to specify a particular ISA version:

$ bpf-unknown-none-objdump -M pseudoc -d foo.o

foo.o: file format elf64-bpfle

Disassembly of section .text:

0000000000000000 <foo>:
0: bf 11 20 00 00 00 00 00 r1 = (s32) r1
8: c3 12 00 00 51 00 00 00 w1=atomic_fetch_and((u32*)(r2+0),w1)
10: 95 00 00 00 00 00 00 00 exit

$ bpf-unknown-none-objdump -M v2,pseudoc -d foo.o

foo.o: file format elf64-bpfle

Disassembly of section .text:

0000000000000000 <foo>:
0: bf 11 20 00 00 00 00 00 r1=r1
8: c3 12 00 00 51 00 00 00 <unknown>
10: 95 00 00 00 00 00 00 00 exit

Quoted 36 lines

For code:
void foo(int a, _Atomic int *b)
{
*b &= a;
}

The initial IR generated by clang frontend is:

define dso_local void @foo(i32 noundef %a, ptr noundef %b) #0 { entry:
%a.addr = alloca i32, align 4
%b.addr = alloca ptr, align 8
store i32 %a, ptr %a.addr, align 4, !tbaa !3
store ptr %b, ptr %b.addr, align 8, !tbaa !7
%0 = load i32, ptr %a.addr, align 4, !tbaa !3
%1 = load ptr, ptr %b.addr, align 8, !tbaa !7
%2 = atomicrmw and ptr %1, i32 %0 seq_cst, align 4 %3 = and i32 %2, %0
ret void
}

Note that atomicrmw in the above. Eventually it optimized to

define dso_local void @foo(i32 noundef %a, ptr noundef %b) #0 { entry:
%0 = atomicrmw and ptr %b, i32 %a seq_cst, align 4 ret void
}

The 'atomicrmw' is the same IR as generated by __sync_fetch_and_*() and eventually will generate atomic_fetch_*() bpf insn.
Discussed with Andrii, and
another option is to specify relaxed consistency, so llvm internal could translate it into locked insn. For example,

Quoted 6 lines
$ cat t1.c
#include <stdatomic.h>

void f(_Atomic int *i) {
__c11_atomic_fetch_and(i, 1, memory_order_relaxed);
}

I think this makes sense. Currently we removed the GCC insns atomic_{add,or,xor,and} all together so the compiler is forced to implement them in terms of atomic_fetch_and_{add,or,xor,and} regardless of the memory ordering policy specified to the __sync_fetch_and_OP. So even if you specify relaxed memory ordered, the resulting ordering is whatever implied by the fetching operation.

Quoted 29 lines
# to have gnu/stubs-32.h in the current directory to make it compile
[[email protected] ~/tmp6]$ ls gnu
stubs-32.h
[[email protected] ~/tmp6]$ clang --target=bpf -O2 -I. -c -mcpu=v3 t1.c

The initial IR:
define dso_local void @f(ptr noundef %i) #0 { entry:
%i.addr = alloca ptr, align 8
%.atomictmp = alloca i32, align 4 %atomic-temp = alloca i32, align 4
store ptr %i, ptr %i.addr, align 8, !tbaa !3 %0 = load ptr, ptr %i.addr, align 8, !tbaa !3 store i32 1, ptr %.atomictmp, align 4, !tbaa !7 %1 = load i32, ptr %.atomictmp, align 4
%2 = atomicrmw and ptr %0, i32 %1 monotonic, align 4 store i32 %2, ptr %atomic-temp, align 4
%3 = load i32, ptr %atomic-temp, align 4, !tbaa !7 ret void
}

The IR right before machine code generation:

define dso_local void @f(ptr nocapture noundef %i) local_unnamed_addr #0 { entry:
%0 = atomicrmw and ptr %i, i32 1 monotonic, align 4
ret void
}

Quoted 8 lines

Maybe we could special process the above to generate a locked insn if
- atomicrmw operator
- monotonic (related) consistency
- return value is not used

So this will not violate original program semantics. Does this sound a reasonable apporach?

Whether monotonic consistency is desired (ordered writes) can be probably deduced from the memory_order_* flag of the built-ins, but I don't know what atomiccrmw is... what is it in non-llvm terms?

Quoted 4 lines
Quoted 4 lines

So let's make this test mcpu=v3 only and use normal C ?

pw-bot: cr

author reviewer
#4 lore raw
Quoted 172 lines · Jose E. Marchesi
Quoted 138 lines · Alexei Starovoitov
Quoted 118 lines · Yonghong Song
Quoted 104 lines

Peilen Ye reported an issue ([1]) where for __sync_fetch_and_add(...) without return value like

    __sync_fetch_and_add(&foo, 1);
llvm BPF backend generates locked insn e.g.
    lock *(u32 *)(r1 + 0) += r2

If __sync_fetch_and_add(...) returns a value like

    res = __sync_fetch_and_add(&foo, 1);
llvm BPF backend generates like
    r2 = atomic_fetch_add((u32 *)(r1 + 0), r2)

But 'lock *(u32 *)(r1 + 0) += r2' caused a problem in jit
since proper barrier is not inserted based on __sync_fetch_and_add() semantics.

The above discrepancy is due to commit [2] where it tries to maintain backward compatability since before commit [2], __sync_fetch_and_add(...) generates lock insn in BPF backend.

Based on discussion in [1], now it is time to fix the above discrepancy so we can have proper barrier support in jit. llvm patch [3] made sure that __sync_fetch_and_add(...) always generates atomic_fetch_add(...) insns. Now 'lock *(u32 *)(r1 + 0) += r2' can only be generated by inline asm. The same for __sync_fetch_and_and(), __sync_fetch_and_or() and __sync_fetch_and_xor().

But the change in [3] caused arena_atomics selftest failure.

    test_arena_atomics:PASS:arena atomics skeleton open 0 nsec
    libbpf: prog 'and': BPF program load failed: Permission denied
    libbpf: prog 'and': -- BEGIN PROG LOAD LOG --
    arg#0 reference type('UNKNOWN ') size cannot be determined: -22
    0: R1=ctx() R10=fp0
    ; if (pid != (bpf_get_current_pid_tgid() >> 32)) @ arena_atomics.c:87
    0: (18) r1 = 0xffffc90000064000       ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4)
    2: (61) r6 = *(u32 *)(r1 +0)          ; R1_w=map_value(map=arena_at.bss,ks=4,vs=4) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
    3: (85) call bpf_get_current_pid_tgid#14      ; R0_w=scalar()
    4: (77) r0 >>= 32                     ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
    5: (5d) if r0 != r6 goto pc+11        ; R0_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0x)
    ; __sync_fetch_and_and(&and64_value, 0x011ull << 32); @ arena_atomics.c:91
    6: (18) r1 = 0x100000000060           ; R1_w=scalar()
    8: (bf) r1 = addr_space_cast(r1, 0, 1)        ; R1_w=arena
    9: (18) r2 = 0x1100000000             ; R2_w=0x1100000000
    11: (db) r2 = atomic64_fetch_and((u64 *)(r1 +0), r2)
    BPF_ATOMIC stores into R1 arena is not allowed
    processed 9 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
    -- END PROG LOAD LOG --
    libbpf: prog 'and': failed to load: -13
    libbpf: failed to load object 'arena_atomics'
    libbpf: failed to load BPF skeleton 'arena_atomics': -13
    test_arena_atomics:FAIL:arena atomics skeleton load unexpected error: -13 (errno 13)
    #3       arena_atomics:FAIL

The reason of the failure is due to [4] where atomic{64,}_fetch_{and,or,xor}() are not allowed by arena addresses. Without llvm patch [3], the compiler will generate 'lock ...' insn and everything will work fine.

This patch fixed the problem by using inline asms. Instead of __sync_fetch_and_{and,or,xor}() functions, the inline asm with 'lock' insn is used and it will work with or without [3].
Note that three bpf programs ('and', 'or' and 'xor') are guarded with __BPF_FEATURE_ADDR_SPACE_CAST as well to ensure compilation failure for llvm <= 18 version. Note that for llvm <= 18 where addr_space_cast is not supported, all arena_atomics subtests are skipped with below message:

    test_arena_atomics:SKIP:no ENABLE_ATOMICS_TESTS or no addr_space_cast support in clang
    #3 arena_atomics:SKIP

    [1] https://lore.kernel.org/bpf/[email protected]/T/#mb68d67bc8f39e35a0c3db52468b9de59b79f021f
    [2] https://github.com/llvm/llvm-project/commit/286daafd65129228e08a1d07aa4ca74488615744
    [3] https://github.com/llvm/llvm-project/pull/101428
    [4] d503a04f8bc0 ("bpf: Add support for certain atomics in bpf_arena to x86 JIT")
---
   .../selftests/bpf/progs/arena_atomics.c       | 63 ++++++++++++++++---
   1 file changed, 54 insertions(+), 9 deletions(-)

Changelog:
v1 -> v2:
- Add __BPF_FEATURE_ADDR_SPACE_CAST to guard newly added asm codes for llvm >= 19

tools/testing/selftests/bpf/progs/arena_atomics.c +8 -3
index bb0acd79d28a..dea54557fc00 100644
@@ -5,6 +5,7 @@
   #include <bpf/bpf_tracing.h>
   #include <stdbool.h>
   #include "bpf_arena_common.h"
+#include "bpf_misc.h"
 
   struct {
          __uint(type, BPF_MAP_TYPE_ARENA);
@@ -85,10 +86,24 @@ int and(const void *ctx)
   {
          if (pid != (bpf_get_current_pid_tgid() >> 32))
                  return 0;
-#ifdef ENABLE_ATOMICS_TESTS
+#if defined(ENABLE_ATOMICS_TESTS) && defined(__BPF_FEATURE_ADDR_SPACE_CAST)
 
-       __sync_fetch_and_and(&and64_value, 0x011ull << 32);
-       __sync_fetch_and_and(&and32_value, 0x011);
+       asm volatile(
+               "r1 = addr_space_cast(%[and64_value], 0, 1);"
+               "lock *(u64 *)(r1 + 0) &= %[val]"
+               :
+               : __imm_ptr(and64_value),
+                 [val]"r"(0x011ull << 32)

tools/testing/selftests/bpf/progs/arena_atomics.c int and(const void *ctx) · line 106

Quoted 10 lines
tools/testing/selftests/bpf/progs/arena_atomics.c +10 -0
+               : "r1"
+       );
+       asm volatile(
+               "r1 = addr_space_cast(%[and32_value], 0, 1);"
+               "lock *(u32 *)(r1 + 0) &= %[val]"
+               :
+               : __imm_ptr(and32_value),
+                 [val]"w"(0x011)
+               : "r1"
+       );

Instead of inline asm there is a better way to do the same in C.
https://godbolt.org/z/71PYx1oqE

Quoted 7 lines

void foo(int a, _Atomic int *b)

{
   *b += a;
}

generates:
lock *(u32 *)(r2 + 0) += r1

If you use latest llvm-project with
https://github.com/llvm/llvm-project/pull/101428
included, the above code will generate like

$ clang --target=bpf -O2 -c t.c && llvm-objdump -d t.o
t.o:    file format elf64-bpf
Disassembly of section .text:
0000000000000000 <foo>:
        0:       c3 12 00 00 01 00 00 00 r1 = atomic_fetch_add((u32 *)(r2 + 0x0), r1)
        1:       95 00 00 00 00 00 00 00 exit
Quoted 1 line

With -mcpu=v3 the same code can be generated.

Same for current GCC.

Quoted 13 lines
Quoted 7 lines

but
*b &= a;

crashes llvm :( with

<source>:3:5: error: unsupported atomic operation, please use 64 bit version

      3 |  *b &= a;

It failed with the following llvm error message:
t.c:1:6: error: unsupported atomic operation, please use 64 bit version
1 | void foo(int a, _Atomic int *b)
| ^
fatal error: error in backend: Cannot select: t8: i64,ch = AtomicLoadAnd<(load store seq_cst (s32) on %ir.b)> t0, t4, t2
t4: i64,ch = CopyFromReg t0, Register:i64 %1

Quoted 7 lines
     t3: i64 = Register %1
   t2: i64,ch = CopyFromReg t0, Register:i64 %0
     t1: i64 = Register %0

In function: foo

Quoted 1 line

but works with -mcpu=v3

Yes. it does work with -mcpu=v3:

In GCC if you specify -mcpu=v2 and use atomic built-ins you get workaround code in the form of libcalls (like calls to __atomic_fetch_and_4) which are of course of no use in BPF atm.

Quoted 8 lines
$ clang --target=bpf -O2 -mcpu=v3 -c t.c && llvm-objdump -d --mcpu=v3 t.o

t.o:    file format elf64-bpf
Disassembly of section .text:
0000000000000000 <foo>:
       0:       c3 12 00 00 51 00 00 00 w1 = atomic_fetch_and((u32 *)(r2 + 0x0), w1) 1:       95 00 00 00 00 00 00 00 exit

Quoted 5 lines
Quoted 2 lines

NOTE: I need -mcpu=v3 for llvm-objdump to print asm code 'atomic_fetch_and' properly. Will double check this.

The GNU binutils objdump will try to recognize instructions in the latest supported cpu version, unless an explicit option is passed to specify a particular ISA version:

Agree. As I mentioned in the above, I will take a look at this soon.

Quoted 67 lines
$ bpf-unknown-none-objdump -M pseudoc -d foo.o

foo.o: file format elf64-bpfle

Disassembly of section .text:

0000000000000000 <foo>:

    0:	bf 11 20 00 00 00 00 00 	r1 = (s32) r1
    8:	c3 12 00 00 51 00 00 00 	w1=atomic_fetch_and((u32*)(r2+0),w1)

10: 95 00 00 00 00 00 00 00 exit

$ bpf-unknown-none-objdump -M v2,pseudoc -d foo.o

foo.o: file format elf64-bpfle

Disassembly of section .text:

0000000000000000 <foo>:

    0:	bf 11 20 00 00 00 00 00 	r1=r1
    8:	c3 12 00 00 51 00 00 00 	<unknown>

10: 95 00 00 00 00 00 00 00 exit

Quoted 36 lines

For code:
void foo(int a, _Atomic int *b)
{
*b &= a;
}

The initial IR generated by clang frontend is:

define dso_local void @foo(i32 noundef %a, ptr noundef %b) #0 { entry:

   %a.addr = alloca i32, align 4
   %b.addr = alloca ptr, align 8
   store i32 %a, ptr %a.addr, align 4, !tbaa !3
   store ptr %b, ptr %b.addr, align 8, !tbaa !7
   %0 = load i32, ptr %a.addr, align 4, !tbaa !3
   %1 = load ptr, ptr %b.addr, align 8, !tbaa !7
   %2 = atomicrmw and ptr %1, i32 %0 seq_cst, align 4
   %3 = and i32 %2, %0
   ret void
}

Note that atomicrmw in the above. Eventually it optimized to

define dso_local void @foo(i32 noundef %a, ptr noundef %b) #0 { entry:
%0 = atomicrmw and ptr %b, i32 %a seq_cst, align 4 ret void
}

The 'atomicrmw' is the same IR as generated by __sync_fetch_and_*() and eventually will generate atomic_fetch_*() bpf insn.
Discussed with Andrii, and
another option is to specify relaxed consistency, so llvm internal could translate it into locked insn. For example,

Quoted 6 lines
$ cat t1.c
#include <stdatomic.h>
void f(_Atomic int *i) {
   __c11_atomic_fetch_and(i, 1, memory_order_relaxed);
}
Quoted 6 lines

I think this makes sense. Currently we removed the GCC insns atomic_{add,or,xor,and} all together so the compiler is forced to implement them in terms of atomic_fetch_and_{add,or,xor,and} regardless of the memory ordering policy specified to the __sync_fetch_and_OP. So even if you specify relaxed memory ordered, the resulting ordering is whatever implied by the fetching operation.

Encoding memory order constraints in BPF insn might be too complicated. I am not sure. But at least we could map different memory constraints into different insns so jit can add proper barrier for those insns.

Quoted 36 lines
Quoted 36 lines
# to have gnu/stubs-32.h in the current directory to make it compile
[[email protected] ~/tmp6]$ ls gnu
stubs-32.h
[[email protected] ~/tmp6]$ clang --target=bpf -O2 -I. -c -mcpu=v3 t1.c

The initial IR:
define dso_local void @f(ptr noundef %i) #0 { entry:
%i.addr = alloca ptr, align 8
%.atomictmp = alloca i32, align 4 %atomic-temp = alloca i32, align 4
store ptr %i, ptr %i.addr, align 8, !tbaa !3 %0 = load ptr, ptr %i.addr, align 8, !tbaa !3 store i32 1, ptr %.atomictmp, align 4, !tbaa !7 %1 = load i32, ptr %.atomictmp, align 4
%2 = atomicrmw and ptr %0, i32 %1 monotonic, align 4 store i32 %2, ptr %atomic-temp, align 4
%3 = load i32, ptr %atomic-temp, align 4, !tbaa !7 ret void
}

The IR right before machine code generation:

define dso_local void @f(ptr nocapture noundef %i) local_unnamed_addr #0 { entry:
%0 = atomicrmw and ptr %i, i32 1 monotonic, align 4
ret void
}

Maybe we could special process the above to generate a locked insn if
- atomicrmw operator
- monotonic (related) consistency
- return value is not used

Quoted 5 lines
Quoted 2 lines

So this will not violate original program semantics. Does this sound a reasonable apporach?

Whether monotonic consistency is desired (ordered writes) can be probably deduced from the memory_order_* flag of the built-ins, but I don't know what atomiccrmw is... what is it in non-llvm terms?

The llvm language reference for atomicrmw:

  https://llvm.org/docs/LangRef.html#atomicrmw-instruction

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

So let's make this test mcpu=v3 only and use normal C ?

pw-bot: cr

#5 lore raw
Quoted 8 lines · Yonghong Song
Quoted 8 lines
Quoted 8 lines

Maybe we could special process the above to generate a locked insn if
- atomicrmw operator
- monotonic (related) consistency
- return value is not used

This sounds like a good idea, but...

Quoted 10 lines
Quoted 6 lines
Quoted 3 lines

So this will not violate original program semantics. Does this sound a reasonable apporach?

Whether monotonic consistency is desired (ordered writes) can be probably deduced from the memory_order_* flag of the built-ins, but I don't know what atomiccrmw is... what is it in non-llvm terms?

The llvm language reference for atomicrmw:

https://llvm.org/docs/LangRef.html#atomicrmw-instruction

I read it back and forth, but couldn't find whether it's ok for the backend to use stronger ordering insn when weaker ordering is specified in atomicrmw.
It's probably ok.
Otherwise atomicrmw with monotnic (memory_order_relaxed) and return value is used cannot be mapped to any bpf insn. x86 doesn't have monotonic either, but I suspect the backend still generates the code without any warnings.
Would be good to clarify before we proceed with the above plan.

author reviewer
#6 lore raw
Quoted 17 lines · Alexei Starovoitov
Quoted 6 lines · Yonghong Song
Quoted 6 lines
Quoted 6 lines

Maybe we could special process the above to generate a locked insn if
- atomicrmw operator
- monotonic (related) consistency
- return value is not used

This sounds like a good idea, but...

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

So this will not violate original program semantics. Does this sound a reasonable apporach?

Whether monotonic consistency is desired (ordered writes) can be probably deduced from the memory_order_* flag of the built-ins, but I don't know what atomiccrmw is... what is it in non-llvm terms?

The llvm language reference for atomicrmw:

https://llvm.org/docs/LangRef.html#atomicrmw-instruction

Quoted 8 lines

I read it back and forth, but couldn't find whether it's ok for the backend to use stronger ordering insn when weaker ordering is specified in atomicrmw.
It's probably ok.
Otherwise atomicrmw with monotnic (memory_order_relaxed) and return value is used cannot be mapped to any bpf insn. x86 doesn't have monotonic either, but I suspect the backend still generates the code without any warnings.

I did a little bit experiment for x86,

$ cat t.c
int foo;
void bar1(void) {
        __sync_fetch_and_add(&foo, 10);
}
int bar2(void) {
        return __sync_fetch_and_add(&foo, 10);
}
$ clang -O2 -I. -c t.c && llvm-objdump -d t.o

t.o: file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <bar1>:

       0: f0                            lock
       1: 83 05 00 00 00 00 0a          addl    $0xa, (%rip)            # 0x8 <bar1+0x8>
       8: c3                            retq
       9: 0f 1f 80 00 00 00 00          nopl    (%rax)

0000000000000010 <bar2>:

      10: b8 0a 00 00 00                movl    $0xa, %eax
      15: f0                            lock
      16: 0f c1 05 00 00 00 00          xaddl   %eax, (%rip)            # 0x1d <bar2+0xd>
      1d: c3                            retq

So without return value, __sync_fetch_and_add will generated locked add insn. With return value, 'lock xaddl' is used which should be similar to bpf atomic_fetch_add.

Another example,

$ cat t1.c
#include <stdatomic.h>

void f1(_Atomic int *i) {
__c11_atomic_fetch_and(i, 10, memory_order_relaxed);
}

void f2(_Atomic int *i) {
__c11_atomic_fetch_and(i, 10, memory_order_seq_cst);
}

void f3(_Atomic int *i) {
__c11_atomic_fetch_and(i, 10, memory_order_release);
}

_Atomic int f4(_Atomic int *i) {
return __c11_atomic_fetch_and(i, 10, memory_order_release);
}

$ clang -O2 -I. -c t1.c && llvm-objdump -d t1.o

t1.o: file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <f1>:

       0: f0                            lock
       1: 83 27 0a                      andl    $0xa, (%rdi)
       4: c3                            retq
       5: 66 66 2e 0f 1f 84 00 00 00 00 00      nopw    %cs:(%rax,%rax)

0000000000000010 <f2>:

      10: f0                            lock
      11: 83 27 0a                      andl    $0xa, (%rdi)
      14: c3                            retq
      15: 66 66 2e 0f 1f 84 00 00 00 00 00      nopw    %cs:(%rax,%rax)

0000000000000020 <f3>:

      20: f0                            lock
      21: 83 27 0a                      andl    $0xa, (%rdi)
      24: c3                            retq
      25: 66 66 2e 0f 1f 84 00 00 00 00 00      nopw    %cs:(%rax,%rax)

0000000000000030 <f4>:
30: 8b 07 movl (%rdi), %eax
32: 66 66 66 66 66 2e 0f 1f 84 00 00 00 00 00 nopw %cs:(%rax,%rax)
40: 89 c1 movl %eax, %ecx
42: 83 e1 0a andl $0xa, %ecx
45: f0 lock
46: 0f b1 0f cmpxchgl %ecx, (%rdi)
49: 75 f5 jne 0x40 <f4+0x10>
4b: c3 retq
$

In all cases without return value, for x86, 'lock andl' insn is generated regardless of the memory order constraint. This is similar to what we had before.

Although previous 'lock' encoding matches to x86 nicely.
But for ARM64 and for 'lock ...' bpf insn,
the generated insn won't have a barrier (acquire or release or both) semantics. So I guess that ARM64 wants to preserve the current hehavior:
- for 'lock ...' insn, no barrier,
- for 'atomic_fetch_add ...' insn, proper barrier.

For x86, for both 'lock ...' and 'atomic_fetch_add ...' will have proper barrier.

To keep 'lock ...' no-barrier required, user needs to specify memory_order_relaxed constraint. This will permit bpf backend to generate 'lock ...' insn.

Looks like x86 does check memory_order_relaxed to do some special processing:

X86CompressEVEX.cpp:  if (!TableChecked.load(std::memory_order_relaxed)) {
X86CompressEVEX.cpp:    TableChecked.store(true, std::memory_order_relaxed);
X86FloatingPoint.cpp:    if (!TABLE##Checked.load(std::memory_order_relaxed)) {                     \
X86FloatingPoint.cpp:      TABLE##Checked.store(true, std::memory_order_relaxed);                   \
X86InstrFMA3Info.cpp:  if (!TableChecked.load(std::memory_order_relaxed)) {
X86InstrFMA3Info.cpp:    TableChecked.store(true, std::memory_order_relaxed);
X86InstrFoldTables.cpp:  if (!FoldTablesChecked.load(std::memory_order_relaxed)) {
X86InstrFoldTables.cpp:    FoldTablesChecked.store(true, std::memory_order_relaxed);

So I guess that bpf can do similar thing to check memory_order_relaxed in IR and may generate different (more efficient insns) as needed.

Quoted 1 line

Would be good to clarify before we proceed with the above plan.