Re: [PATCH bpf-next v2 4/9] bpf: Introduce load-acquire and store-release instructions

[Peilin Ye <yepeilin@google.com>]

Hi Alexei,

On Wed, Feb 12, 2025 at 09:55:43PM -0800, Alexei Starovoitov wrote:
> > > > >   #define BPF_LOAD_ACQ   0x10
> > > > >   #define BPF_STORE_REL  0x20
> 
> so that was broken then,
> since BPF_SUB 0x10 ?
> 
> And original thing was also completely broken for
> BPF_ATOMIC_LOAD | BPF_RELAXED == 0x10 == BPF_SUB ?
> 
> so much for "lets define relaxed, acquire,
> release, acq_rel for completeness".
> :(
> 
> > > > why not 1 and 2 ?
> > >
> > > I just realized

To clarify, by "just realized" I meant I forgot BPF_ADD equals 0x00
until (I had coffee on) Monday :-)

I wouldn't call it completely broken though.  For full context,
initially I picked [1] 0x1 and 0xb in imm<4-7> because:

  * 0x1 is BPF_SUB in BPFArithOp<>, and atomic SUB is implemented using
    NEG + ADD, quoting a comment in LLVM source:

    // atomic_load_sub can be represented as a neg followed
    // by an atomic_load_add.

    Though admittedly atomic SUB _could_ have its own insn.

  * 0xb is BPF_MOV, which is not applicable for atomic (memory)
    operations, as already discussed

After discussing [2] this with Yonghong, I changed it to 0x1 and 0x2,
because 0x2 is BPF_MUL and we are unlikely to support atomic
multiplication.  Then, following your suggestion to discuss the encoding
on-list, I left this as an open topic in RFC v1 cover letter (then
documented it in PATCH v1 8/8 and v2 9/9).

TL;DR: I wasn't aware that you were against having "aliases" (I do still
believe it's safe to pick 0xb).

> > > that we can't do 1 and 2 because BPF_ADD | BPF_FETCH also equals
> > > 1.
> > >
> > > > All other bits are reserved and the verifier will make sure they're zero
> > >
> > > IOW, we can't tell if imm<4-7> is reserved or BPF_ADD (0x00).  What
> > > would you suggest?  Maybe:
> > >
> > >   #define BPF_ATOMIC_LD_ST 0x10
> > >
> > >   #define BPF_LOAD_ACQ      0x1
> > >   #define BPF_STORE_REL     0x2
> 
> This is also broken, since
> BPF_ATOMIC_LD_ST | BPF_LOAD_ACQ == 0x11 == BPF_SUB | BPF_FETCH.
> 
> BPF_SUB | BPF_FETCH is invalid at the moment,
> but such aliasing is bad.
> 
> > > ?
> >
> > Or, how about reusing 0xb in imm<4-7>:
> >
> >   #define BPF_ATOMIC_LD_ST 0xb0
> >
> >   #define BPF_LOAD_ACQ      0x1
> >   #define BPF_STORE_REL     0x2
> >
> > 0xb is BPF_MOV in BPFArithOp<>, and we'll never need it for BPF_ATOMIC.
> > Instead of moving values between registers, we now "move" values from/to
> > the memory - if I can think of it that way.
> 
> and BPF_ATOMIC_LD_ST | BPF_LOAD_ACQ would == BPF_MOV | BPF_FETCH ?
> 
> Not pretty and confusing.
> 
> BPF_FETCH modifier means that "do whatever opcode says to do,
> like add in memory, but also return the value into insn->src_reg"
> 
> Which doesn't fit this BPF_ATOMIC_LD_ST | BPF_LOAD_ACQ semantics
> which loads into _dst_reg_.

I think we can have different imm<0-3> "namespace"s depending on
different imm<4-7> values?  So that 0x1 in imm<0-3> means BPF_FETCH for
existing RMW operations, and BPF_LOAD_ACQ for loads/stores.

Just like (browsing instruction-set.rst) for "64-bit immediate
instructions", the imm field means different things depending on the
value in src_reg?

If I change PATCH v2 9/9 to say the following in instruction-set.rst:

  ```
  These operations are categorized based on the second lowest nibble
  (bits 4-7) of the 'imm' field:

  * ``ATOMIC_LD_ST`` indicates an atomic load or store operation (see
    `Atomic load and store operations`_).

  * All other defined values indicate an atomic read-modify-write
    operation, as described in the following section.
  ```

The section for loads/stores will have its own table explaining what
imm<0-3> means.

> How about:
> #define BPF_LOAD_ACQ 2
> #define BPF_STORE_REL 3
> 
> and only use them with BPF_MOV like
> 
> imm = BPF_MOV | BPF_LOAD_ACQ - is actual load acquire
> imm = BPF_MOV | BPF_STORE_REL - release
> 
> Thought 2 stands on its own,
> it's also equal to BPF_ADD | BPF_LOAD_ACQ
> which is kinda ugly,

> so I don't like to use 2 alone.

Totally agree - if we use 2 and 3 alone, zero in imm<4-7> would mean
"reserved" for load_acq/store_rel, and "BPF_ADD" for add/fetch_add.

> > Or, do we want to start to use the remaining bits of the imm field (i.e.
> > imm<8-31>) ?
> 
> Maybe.
> Sort-of.
> Since #define BPF_CMPXCHG     (0xf0 | BPF_FETCH)
> another option would be:
> 
> #define BPF_LOAD_ACQ 0x100
> #define BPF_STORE_REL 0x110
> 
> essentially extending op type to:
> BPF_ATOMIC_TYPE(imm)    ((imm) & 0x1f0)

Why, it sounds like a great idea!  If we extend the op_type field from
imm<4-7> to imm<4-11>, 256 numbers is more than we'll ever need?

After all we'd still need to worry about e.g. cmpwait_relaxed you
mentioned earlier.  I am guessing that we'll want to put it under
BPF_ATOMIC as well, since XCHG and CMPXCHG are here.  If we take your
approach, cmpwait_relaxed can be easily defined as e.g.:

  #define BPF_CMPWAIT_RELAXED   0x120

(FWIW, I was imagining a subtype/subclass flag in maybe imm<8-11> or
 imm<28-31> (or make it 8 bits for 256 subtypes/subclasses), so that 0x0
 means read-modify-write subclass, then 0x1 means maybe load/store
 subclass" etc.)

> All options are not great.
> I feel we need to step back.
> Is there an architecture that has sign extending load acquire ?

IIUC, if I grep the LLVM source like:

  $ git grep -B 100 -A 100 getExtendForAtomicOps -- llvm/lib/Target/ \
	| grep ISD::SIGN_EXTEND
  llvm/lib/Target/LoongArch/LoongArchISelLowering.h-    return ISD::SIGN_EXTEND;
  llvm/lib/Target/Mips/MipsISelLowering.h-      return ISD::SIGN_EXTEND;
  llvm/lib/Target/RISCV/RISCVISelLowering.h-    return ISD::SIGN_EXTEND;

So LoongArch, Mips and RISCV it seems?

Semi-related, but it would be non-trivial (if not infeasible) to support
both zext and sext load-acquire for LLVM BPF backend, because LLVM core
expects each arch to pick from SIGN_EXTEND, ZERO_EXTEND and ANY_EXTEND
for its atomic ops.  See my earlier investigation:

  https://github.com/llvm/llvm-project/pull/108636#issuecomment-2433844760

> Looks like arm doesn't, and I couldn't find any arch that does.
> Then maybe we should reconsider BPF_LDX/STX and use BPF_MODE
> to distinguish from normal ldx/stx
> 
> #define BPF_ACQ_REL 0xe0
> 
> BPF_LDX | BPF_ACQ_REL | BPF_W
> BPF_STX | BPF_ACQ_REL | BPF_W
> 
> ?

[1] https://github.com/llvm/llvm-project/pull/108636#issuecomment-2398916882
[2] https://github.com/llvm/llvm-project/pull/108636#discussion_r1815927568

Thanks,
Peilin Ye