Re: [Bpf] Review of draft-thaler-bpf-isa-01

[David Vernet <[e-mail]>]

On Tue, Aug 01, 2023 at 07:33:59PM -0700, Watson Ladd wrote:
> In reply to a long conversation:
> <snip>
> >
> > Could you please be specific which instruction in table 4 is not obvious?
> 
> The question isn't obvious, the question is unambigious, and C is not
> great for this. Maybe with a reference and some text it would get
> better.
> >
> > > >
> > > > > > The good news is I think this is very fixable although tedious.
> > > > > >
> > > > > > The other thornier issues are memory model etc. But the overall structure seems good
> > > > > > and the document overall makes sense.
> > > >
> > > > What do you mean by "memory model" ?
> > > > Do you see a reference to it ? Please be specific.
> > >
> > > No, and that's the problem. Section 5.2 talks about atomic operations.
> > > I'd expect that to be paired with a description of barriers so that
> > > these work, or a big warning about when you need to use them.
> >
> > That's a good suggestion.
> > A warning paragraph that BPF ISA does not have barrier instructions
> > is necessary.
> >
> > > For
> > > clarity I'm pretty unfamiliar with bpf as a technology, and it's
> > > possible that with more knowledge this would make sense. On looking
> > > back on that I don't even know if the memory space is flat, or
> > > segmented: can I access maps through a value set to dst+offset, or
> > > must I always used index? I'm just very confused.
> >
> > flat vs segmented is an orthogonal topic.
> > We definitely need to cover it in the architecture doc.
> > BPF WG charter requires us to produce it as Informational doc eventually.
> 
> Huh? If you access memory through specialized descriptors+offsets
> that's very different from arbitrary computations with addresses, even
> if they do trap. A little explanation might orient the reader to
> understand what is going on. As is I thought "ok, it's flat" and then
> saw the maps and really got thrown for a loop.
> 
> >
> > As far as memory model BPF adopts LKMM (Linux Kernel Memory Model).
> > https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p0124r7.html
> >
> > We can add a reference to it from BPF ISA doc, but since
> > there are no barrier instructions at the moment the memory model
> > statement would be premature.
> > The work on "BPF Memory Model" have been ongoing for quite some time.
> > For example see:
> > https://lpc.events/event/11/contributions/941/attachments/859/1667/bpf-memory-model.2020.09.22a.pdf
> >
> > BPF Memory Model is certainly an important topic, but out of scope for ISA.
> 
> I expect that an ISA defines the semantics of the instructions. Which
> absolutely includes the memory model.  Now maybe we're envisioning a
> different splitting of this information, but I don't see how it can't
> be at a different level if you want to give the instructions
> semantics.

Hello Watson,

Thank you for sharing your thoughts on the ISA standard document thus
far. I tend to agree with you that defining a memory model (including a
memory consistency model) is inevitable, and I think it will be critical
for ensuring source code compatibility between different BPF
implementations. That said, I'm not sure that it needs to be a blocker
to us ratifying this initial proposed standard (not that you said that
explicitly) for the ISA, for a couple of reasons.

Firstly and perhaps most importantly, there is a precedence for ISA
standards evolving, sometimes significantly, as the platforms and
ecosystems surrounding a standard mature. RISC-V is an excellent example
of this. The 2.0 version of the Unprivileged ISA standard [0] published
in 2019 included_many changes that were not present in the initial
publication [1] of the standard in 2011.

[0]: https://github.com/riscv/riscv-isa-manual/releases/download/Ratified-IMAFDQC/riscv-spec-20191213.pdf
[1]: https://people.eecs.berkeley.edu/~krste/papers/EECS-2011-62.pdf

Note, for example, that the RVWMO  (RISC-V Weak Memory Ordering) Memory
Consistency Model was not ratified until v2.0 of the standard, which was
8 years following the publication of v1. Subsection 2.8 in v1.0 does
describe a Memory Model, but it's very high level, and doesn't even
mention e.g. device I/O. This is despite the v1.0 publication describing
"Atomic Memory Operation Instructions" as follows (excluding the diagram
showing the encoding which I won't take the time to type out in
plaintext form):

> The atomic memory operation (AMO) instructions perform
> read-modify-write operations for multiprocessor synchronization and
> are encoded with an R-type instruction format. These AMO instructions
> atomically load a data value from the address in rs1, place the value
> into register rd, apply a binary operator to the loaded value and the
> value in rs2, then store the result back to the address in rs1. AMOs
> can either operate on 32-bit or 64-bit words in memory. For RV64,
> 32-bit AMOs always sign-extend the value placed in rd. The address
> held in rs1 must be naturally aligned to the size of the operand
> (i.e., eight-byte aligned for 64-bit words and four-byte aligned for
> 32-bit words). If the address is not naturally aligned, a misaligned
> address trap will be generated.  The operations supported are integer
> add, logical AND, logical OR, swap, and signed and unsigned integer
> maximum and minimum.

This is in contrast to v2.0, which dedicates the entirety of Chapter 8:
"A" Standard Extension for Atomic Instructions, Version 2.1 to
discussing and formalizing atomic instructions.

That's all to say, I don't think we need to have a full and "feature
complete" ISA standard for our initial ratification. Speaking for
myself, I think it would be prudent for us to actually hold off on
defining some of these finer points like the memory model until we've
had more time to think about what the proper memory model would look
like for BPF rather than just standardizing what industry has built thus
far.

What we _definitely_ need to think through completely in this early
stage is how we're going to enable extensions to the standard, because
no matter how much work we put into this version, we're inevitably going
to have to write extensions (not that you're claiming otherwise).

In my personal opinion, I think standardizing instruction encoding and
semantics is a reasonable first step. Which leads me to my other reason
why I don't think it's necessary to formally define a memory model for
v1:

One of the unique challenges we're going to have to work through as a
Working Group is how to collaborate between the IETF and Linux Kernel
communities. I think we're doing a great job so far, especially given
how things went at IETF 117, and that folks from both communities are
already engaging on the standard. That said, I am personally of the
opinion that we're most likely to succeed in figuring out an ideal
working relationship / culture for the WG if we can do so while
iterating on a standard that has a minimal amount of complexity, and a
lower likelihood of being contentious.

That of course doesn't mean that we should sacrifice the quality of
whatever standard(s) we write and ratify, but I think that if we can
write a standard that we agree is correct, self-contained, well-written,
and can be easily extended, but that is also "non-controversial" (e.g.
for the case of the ISA, defines instruction encodings that are
implemented by clang and gcc, and whose semantics are implemented by
Linux, Microsoft, Netronome, etc), that it may be prudent to take
advantage of that in these early days to flesh out how our WG will
operate when we have to write more open-ended and potentially
contentious parts of the standard such as the BPF memory model.

What do you think? Thanks again for sharing your thoughts, and for
participating in the WG.

- David