• Andrea Parri's avatar
    riscv, bpf: Make BPF_CMPXCHG fully ordered · e59db062
    Andrea Parri authored
    According to the prototype formal BPF memory consistency model
    discussed e.g. in [1] and following the ordering properties of
    the C/in-kernel macro atomic_cmpxchg(), a BPF atomic operation
    with the BPF_CMPXCHG modifier is fully ordered.  However, the
    current RISC-V JIT lowerings fail to meet such memory ordering
    property.  This is illustrated by the following litmus test:
    
    BPF BPF__MP+success_cmpxchg+fence
    {
     0:r1=x; 0:r3=y; 0:r5=1;
     1:r2=y; 1:r4=f; 1:r7=x;
    }
     P0                               | P1                                         ;
     *(u64 *)(r1 + 0) = 1             | r1 = *(u64 *)(r2 + 0)                      ;
     r2 = cmpxchg_64 (r3 + 0, r4, r5) | r3 = atomic_fetch_add((u64 *)(r4 + 0), r5) ;
                                      | r6 = *(u64 *)(r7 + 0)                      ;
    exists (1:r1=1 /\ 1:r6=0)
    
    whose "exists" clause is not satisfiable according to the BPF
    memory model.  Using the current RISC-V JIT lowerings, the test
    can be mapped to the following RISC-V litmus test:
    
    RISCV RISCV__MP+success_cmpxchg+fence
    {
     0:x1=x; 0:x3=y; 0:x5=1;
     1:x2=y; 1:x4=f; 1:x7=x;
    }
     P0                 | P1                          ;
     sd x5, 0(x1)       | ld x1, 0(x2)                ;
     L00:               | amoadd.d.aqrl x3, x5, 0(x4) ;
     lr.d x2, 0(x3)     | ld x6, 0(x7)                ;
     bne x2, x4, L01    |                             ;
     sc.d x6, x5, 0(x3) |                             ;
     bne x6, x4, L00    |                             ;
     fence rw, rw       |                             ;
     L01:               |                             ;
    exists (1:x1=1 /\ 1:x6=0)
    
    where the two stores in P0 can be reordered.  Update the RISC-V
    JIT lowerings/implementation of BPF_CMPXCHG to emit an SC with
    RELEASE ("rl") annotation in order to meet the expected memory
    ordering guarantees.  The resulting RISC-V JIT lowerings of
    BPF_CMPXCHG match the RISC-V lowerings of the C atomic_cmpxchg().
    
    Other lowerings were fixed via 20a759df ("riscv, bpf: make
    some atomic operations fully ordered").
    
    Fixes: dd642ccb ("riscv, bpf: Implement more atomic operations for RV64")
    Signed-off-by: default avatarAndrea Parri <parri.andrea@gmail.com>
    Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    Reviewed-by: default avatarPuranjay Mohan <puranjay@kernel.org>
    Acked-by: default avatarBjörn Töpel <bjorn@kernel.org>
    Link: https://lpc.events/event/18/contributions/1949/attachments/1665/3441/bpfmemmodel.2024.09.19p.pdf [1]
    Link: https://lore.kernel.org/bpf/20241017143628.2673894-1-parri.andrea@gmail.com
    e59db062
bpf_jit_comp64.c 55.5 KB