On 7/29/24 6:28 PM, Alexei Starovoitov wrote:
On Mon, Jul 29, 2024 at 11:33 AM Peilin Ye <yepeilin@xxxxxxxxxx> wrote:Hi list! As we are looking at running sched_ext-style BPF scheduling on architectures with a more relaxed memory model (i.e. ARM), we would like to: 1. have fine-grained control over memory ordering in BPF (instead of defaulting to a full barrier), for performance reasons 2. pay closer attention to if memory barriers are being used correctly in BPF To that end, our main goal here is to support more types of memory barriers in BPF. While Paul E. McKenney et al. are working on the formalized BPF memory model [1], Paul agreed that it makes sense to support some basic types first. Additionally, we noticed an issue with the __sync_*fetch*() compiler built-ins related to memory ordering, which will be described in details below. I. We need more types of BPF memory barriers -------------------------------------------- Currently, when it comes to BPF memory barriers, our choices are effectively limited to: * compiler barrier: 'asm volatile ("" ::: "memory");' * full memory barriers implied by compiler built-ins like __sync_val_compare_and_swap() We need more. During offline discussion with Paul, we agreed we can start from: * load-acquire: __atomic_load_n(... memorder=__ATOMIC_ACQUIRE); * store-release: __atomic_store_n(... memorder=__ATOMIC_RELEASE);we would need inline asm equivalent too. Similar to kernel smp_load_acquire() macro.Theoretically, the BPF JIT compiler could also reorder instructions just like Clang or GCC, though it might not currently do so. If we ever developed a more optimizing BPF JIT compiler, it would also be nice to have an optimization barrier for it. However, Alexei Starovoitov has expressed that defining a BPF instruction with 'asm volatile ("" ::: "memory");' semantics might be tricky.It can be a standalone insn that is a compiler barrier only but that feels like a waste of an instruction. So depending how we end up encoding various real barriers there may be a bit to spend in such a barrier insn that is only a compiler barrier. In this case optimizing JIT barrier.II. Implicit barriers can get confusing --------------------------------------- We noticed that, as a bit of a surprise, the __sync_*fetch*() built-ins do not always imply a full barrier for BPF on ARM. For example, when using LLVM, the frequently-used __sync_fetch_and_add() can either imply "relaxed" (no barrier), or "acquire and release" (full barrier) semantics, depending on if its return value is used: Case (a): return value is used SEC("...") int64_t foo; int64_t func(...) { return __sync_fetch_and_add(&foo, 1); } For case (a), Clang gave us: 3: db 01 00 00 01 00 00 00 r0 = atomic_fetch_add((u64 *)(r1 + 0x0), r0) opcode (0xdb): BPF_STX | BPF_ATOMIC | BPF_DW imm (0x00000001): BPF_ADD | BPF_FETCH Case (b): return value is ignored SEC("...") int64_t foo; int64_t func(...) { __sync_fetch_and_add(&foo, 1); return foo; } For case (b), Clang gave us: 3: db 12 00 00 00 00 00 00 lock *(u64 *)(r2 + 0x0) += r1 opcode (0xdb): BPF_STX | BPF_ATOMIC | BPF_DW imm (0x00000000): BPF_ADD LLVM decided to drop BPF_FETCH, since the return value of __sync_fetch_and_add() is being ignored [2]. Now, if we take a look at emit_lse_atomic() in the BPF JIT compiler code for ARM64 (suppose that LSE atomic instructions are being used): case BPF_ADD: emit(A64_STADD(isdw, reg, src), ctx); break; <...> case BPF_ADD | BPF_FETCH: emit(A64_LDADDAL(isdw, src, reg, src), ctx); break; STADD is an alias for LDADD. According to [3]: * LDADDAL for case (a) has "acquire" plus "release" semantics * LDADD for case (b) "has neither acquire nor release semantics" This is pretty non-intuitive; a compiler built-in should not have inconsistent implications on memory ordering, and it is better not to require all BPF programmers to memorize this. GCC seems a bit ambiguous [4] on whether __sync_*fetch*() built-ins should always imply a full barrier. GCC considers these __sync_*() built-ins as "legacy", and introduced a new set of __atomic_*() built-ins ("Memory Model Aware Atomic Operations") [5] to replace them. These __atomic_*() built-ins are designed to be a lot more explicit on memory ordering, for example: type __atomic_fetch_add (type *ptr, type val, int memorder) This requires the programmer to specify a memory order type (relaxed, acquire, release...) via the "memorder" parameter. Currently in LLVM, for BPF, those __atomic_*fetch*() built-ins seem to be aliases to their __sync_*fetch*() counterparts (the "memorder" parameter seems effectively ignored), and are not fully supported.This sounds like a compiler bug. Yonghong, Jose, do you know what compilers do for other backends? Is it allowed to convert sycn_fetch_add into sync_add when fetch part is unused?
This behavior is introduced by the following llvm commit: https://github.com/llvm/llvm-project/commit/286daafd65129228e08a1d07aa4ca74488615744 Specifically the following commit message: ======= Similar to xadd, atomic xadd, xor and xxor (atomic_<op>) instructions are added for atomic operations which do not have return values. LLVM will check the return value for __sync_fetch_and_{add,and,or,xor}. If the return value is used, instructions atomic_fetch_<op> will be used. Otherwise, atomic_<op> instructions will be used. ====== Basically, if no return value, __sync_fetch_and_add() will use xadd insn. The decision is made at that time to maintain backward compatibility. For one example, in bcc https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L1444 we have #define lock_xadd(ptr, val) ((void)__sync_fetch_and_add(ptr, val)) Should we use atomic_fetch_*() always regardless of whether the return val is used or not? Probably, it should still work. Not sure what gcc does for this case.
III. Next steps --------------- Roughly, the scope of this work includes: * decide how to extend the BPF ISA (add new instructions and/or extend current ones)ldx/stx insns support MEM and MEMSX modifiers. Adding MEM_ACQ_REL feels like a natural fit. Better name? For barriers we would need a new insn. Not sure which class would fit the best. Maybe BPF_LD ? Another alternative for barriers is to use nocsr kfuncs. Then we have the freedom to make mistakes and fix them later. One kfunc per barrier would do. JITs would inline them into appropriate insns. In bpf progs they will be used just like in the kernel code smp_mb(), smp_rmb(), etc. I don't think compilers have to emit barriers from C code, so my preference is kfuncs atm.* teach LLVM and GCC to generate the new/extended instructions * teach the BPF verifier to understand them * teach the BPF JIT compiler to compile them * update BPF memory model and tooling * update IETF specification Additionally, for the issue described in the previous section, we need to: * check if GCC has the same behavior * at least clearly document the implied effects on BPF memory ordering of current __sync_*fetch*() built-ins (especially for architectures like ARM), as described * fully support the new __atomic_*fetch*() built-ins for BPF to replace the __sync_*fetch*() ones Any suggestions or corrections would be most welcome! Thanks, Peilin Ye [1] Instruction-Level BPF Memory Model https://docs.google.com/document/d/1TaSEfWfLnRUi5KqkavUQyL2tThJXYWHS15qcbxIsFb0/edit?usp=sharing [2] For more information, see LLVM commit 286daafd6512 ("[BPF] support atomic instructions"). Search for "LLVM will check the return value" in the commit message. [3] Arm Architecture Reference Manual for A-profile architecture (ARM DDI 0487K.a, ID032224), C6.2.149, page 2006 [4] https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html 6.58 Legacy __sync Built-in Functions for Atomic Memory Access "In most cases, these built-in functions are considered a full barrier." [5] https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html 6.59 Built-in Functions for Memory Model Aware Atomic Operations
