IETF 118 BPF WG summary
Hello everyone,
We had a productive BPF working group meeting at IETF 118, and we wanted to provide a summary to recap what was discussed.
*BPF ISA*
Dave Thaler provided an update on what's changed in the BPF ISA I-D since IETF 117. Those changes included (but were not necessarily limited to) the following:
- ABI-specific text was moved from this document into a separate ABI [0] document that has yet to be adopted into the WG.
- IANA considerations were added to the document:
- Permanent: Standards action or IESG Review
- Provisional: Specification required
- Historical: Specification required
- For listing instructions in the IANA registry, it was decided to keep them as a single table with multiple key fields.
- New instructions (signed division, signed modulo, move with sign extension, load with sign extension, unconditional byte swap, and 32-bit offset jumps) were added by Yonghong Song.
- A few other fixes and improvements provided by Will Hawkins, Jose Marchesi, and others.
After this update, the discussion moved to a topic for the BPF ISA document that has yet to be resolved: ISA RFC compliance. Dave pointed out that we still need to specify which instructions in the ISA are MUST, SHOULD, etc, to ensure interoperability. Several different options were presented, including having individual-instruction granularity, following the clang CPU versioning convention, and grouping instructions by logical functionality.
We did not obtain consensus at the conference on which was the best way forward. Some of the points raised include the following:
- Following the clang CPU versioning labels is somewhat arbitrary. It may not be appropriate to standardize around grouping that is a result of largely organic historical artifacts.
- If we decide to do logical grouping, there is a danger of bikeshedding. Looking at anecdotes from industry, some vendors such as Netronome elected to not support particular instructions for performance reasons.
Once this compliance question has been resolved, we expect that the ISA document will be ready to move to WG last call.
*BPF Memory Model and psABI*
Alexei Starovoitov presented the rough outline of a proposal for the BPF Memory Model, and clarified some of his views on the BPF psABI. The main thrust of the proposal was that the BPF MM should reflect that of hardware memory models such as ARM and x86, and be mirrored after the LKMM (Linux Kernel Memory Model), of which language MMs are a strict subset. Existing language MMs do not properly handle control dependencies, and suffer from issues such as OOTA (Out-of-Thin-Air) reads. The presentation outlined the control dependencies proposed for various types of BPF instructions, such as atomics, jumps, etc.
Overall the proposal seemed well received, though the issue of whether ABIs should be standardized was again resurfaced. When the WG was formed, the expectation was that such conventions would be captured in one or more Informational documents. This question will likely have to be resolved before an I-D could be adopted.
*Conclusion*
This was another very productive session. It's clear that we're almost ready to make a WG last call for the ISA document. Hopefully we can resolve the issue of compliance quickly. It's also great to see that the BPF MM and ABI standardization discussions are proceeding. It seemed that we all had rough consensus on the proposal for the BPF MM, so it would be great for us to get some of that written down into the existing ABI document.
Have a wonderful week, and we look forward to more progress!
Best,
David and Suresh
Quoted 2 lines · David Vernet
We had a productive BPF working group meeting at IETF 118, and we wanted to provide a summary to recap what was discussed.
David, this is a most excellent summary, thank you. (I wasn't there, I had a conflict)
Quoted 4 lines
subset. Existing language MMs do not properly handle control dependencies, and suffer from issues such as OOTA (Out-of-Thin-Air) reads. The presentation outlined the control dependencies proposed for various types of BPF instructions, such as atomics, jumps, etc.
I didn't know what an OOTA read was, but I think that hte first answer at:
https://stackoverflow.com/questions/42588079/what-is-out-of-thin-air-safety
explained it, but I just wnated to be sure that this was the same term.
I think that we don't expect compilers emitting BPF code to do things like the tearing example:
void threadA() {
g = 0xAB00; // "tearing"
g += 0x00CD;
}but an underlying BPF JIT might do this kind of thing, and of course, the reads could be anywhere, and the variable could be written by C-code (or RUST!).
--
Michael Richardson <[email protected]>, Sandelman Software Works
-= IPv6 IoT consulting =- *I*LIKE*TRAINS*
BPF ISA conformance groups
In reply to David VernetFrom David Vernet's WG summary:
Quoted 1 line
After this update, the discussion moved to a topic for the BPF ISA
document that has yet to be resolved:
Quoted 1 line
ISA RFC compliance. Dave pointed out that we still need to specify which
instructions in the ISA are
Quoted 1 line
MUST, SHOULD, etc, to ensure interoperability. Several different options
were presented, including
Quoted 1 line
having individual-instruction granularity, following the clang CPU
versioning convention, and grouping
Quoted 3 lines
instructions by logical functionality.
We did not obtain consensus at the conference on which was the best way
forward. Some of the points raised include the following:
Quoted 8 lines
- Following the clang CPU versioning labels is somewhat arbitrary. It may not be appropriate to standardize around grouping that is a result of largely organic historical artifacts.
- If we decide to do logical grouping, there is a danger of bikeshedding. Looking at anecdotes from industry, some vendors such as Netronome elected to not support particular instructions for performance reasons.
My sense of the feedback in general was to group instructions by logical functionality, and only create separate
conformance groups where there is some legitimate technical reason that a runtime might not want to support
a given set of instructions. Based on discussion during the meeting, here's a strawman set of conformance
groups to kick off discussion. I've tried to use short (like 6 characters or fewer) names for ease of display in
document tables, and potentially in command line options to tools that might want to use them.
A given runtime platform would be compliant to some set of the following conformance groups:
1. "basic": all instructions not covered by another group below.
2. "atomic": all Atomic operations. I think Christoph argued for this one in the meeting.
3. "divide": all division and modulo operations. Alexei said in the meeting that he'd heard demand for this one.
4. "legacy": all legacy packet access instructions (deprecated).
5. "map": 64-bit immediate instructions that deal with map fds or map indices.
6. "code": 64-bit immediate instruction that has a "code pointer" type.
7. "func": program-local functions.
Things that I *think* don't need a separate conformance group (can just be in "basic") include:
a. Call helper function by address or BTF ID. A runtime that doesn't support these simply won't expose any
such helper functions to BPF programs.
b. Platform variable instructions (dst = var_addr(imm)). A runtime that doesn't support this simply won't
expose any platform variables to BPF programs.
Comments? (Let the bikeshedding begin...)
Dave
Re: [Bpf] BPF ISA conformance groups
Quoted 36 lines · On Sat, Dec 02, 2023 at 11:51:50AM -0800…
Quoted 2 lines
From David Vernet's WG summary:
After this update, the discussion moved to a topic for the BPF ISAdocument that has yet to be resolved:
Quoted 1 line
ISA RFC compliance. Dave pointed out that we still need to specify which
instructions in the ISA are
Quoted 1 line
MUST, SHOULD, etc, to ensure interoperability. Several different options
were presented, including
Quoted 1 line
having individual-instruction granularity, following the clang CPU
versioning convention, and grouping
Quoted 3 lines
instructions by logical functionality.
We did not obtain consensus at the conference on which was the best way
forward. Some of the points raised include the following:
Quoted 8 lines
- Following the clang CPU versioning labels is somewhat arbitrary. It may not be appropriate to standardize around grouping that is a result of largely organic historical artifacts.
- If we decide to do logical grouping, there is a danger of bikeshedding. Looking at anecdotes from industry, some vendors such as Netronome elected to not support particular instructions for performance reasons.My sense of the feedback in general was to group instructions by logical functionality, and only create separate
conformance groups where there is some legitimate technical reason that a runtime might not want to support
a given set of instructions. Based on discussion during the meeting, here's a strawman set of conformance
groups to kick off discussion. I've tried to use short (like 6 characters or fewer) names for ease of display in
document tables, and potentially in command line options to tools that might want to use them.A given runtime platform would be compliant to some set of the following conformance groups:
Quoted 10 lines
1. "basic": all instructions not covered by another group below.
2. "atomic": all Atomic operations. I think Christoph argued for this one in the meeting.
3. "divide": all division and modulo operations. Alexei said in the meeting that he'd heard demand for this one.
4. "legacy": all legacy packet access instructions (deprecated).
5. "map": 64-bit immediate instructions that deal with map fds or map indices.
6. "code": 64-bit immediate instruction that has a "code pointer" type.
7. "func": program-local functions.
I thought for a while about whether this should be part of the basic conformance group, and talked through it with Jakub Kicinski. I do think it makes sense to keep it separate like this. For e.g. devices with Harvard architectures, it could get quite non-trivial for the verifier to determine whether accesses to arguments stored in special register are safe. Definitely not impossible, and overall very useful to support this, but in order to ease vendor adoption it's probably best to keep this separate.
Quoted 10 lines
Things that I *think* don't need a separate conformance group (can just be in "basic") include:
a. Call helper function by address or BTF ID. A runtime that doesn't support these simply won't expose any
such helper functions to BPF programs.
b. Platform variable instructions (dst =var_addr(imm)). A runtime that doesn't support this simply won't
expose any platform variables to BPF programs.Comments? (Let the bikeshedding begin...)
This list seems logical to me, though I do want to think a bit more about the maps one. Alexei, Christoph, anyone else? Now is the time to get aligned so we can get this to WG last call in plenty of time for IETF 119.
Thanks,
David
Re: [Bpf] BPF ISA conformance groups
Quoted 67 lines · David Vernet
Quoted 36 lines · On Sat, Dec 02, 2023 at 11:51:50AM -0800…
Quoted 2 lines
From David Vernet's WG summary:
After this update, the discussion moved to a topic for the BPF ISAdocument that has yet to be resolved:
Quoted 1 line
ISA RFC compliance. Dave pointed out that we still need to specify which
instructions in the ISA are
Quoted 1 line
MUST, SHOULD, etc, to ensure interoperability. Several different options
were presented, including
Quoted 1 line
having individual-instruction granularity, following the clang CPU
versioning convention, and grouping
Quoted 3 lines
instructions by logical functionality.
We did not obtain consensus at the conference on which was the best way
forward. Some of the points raised include the following:
Quoted 8 lines
- Following the clang CPU versioning labels is somewhat arbitrary. It may not be appropriate to standardize around grouping that is a result of largely organic historical artifacts.
- If we decide to do logical grouping, there is a danger of bikeshedding. Looking at anecdotes from industry, some vendors such as Netronome elected to not support particular instructions for performance reasons.My sense of the feedback in general was to group instructions by logical functionality, and only create separate
conformance groups where there is some legitimate technical reason that a runtime might not want to support
a given set of instructions. Based on discussion during the meeting, here's a strawman set of conformance
groups to kick off discussion. I've tried to use short (like 6 characters or fewer) names for ease of display in
document tables, and potentially in command line options to tools that might want to use them.A given runtime platform would be compliant to some set of the following conformance groups:
Quoted 10 lines
1. "basic": all instructions not covered by another group below.
2. "atomic": all Atomic operations. I think Christoph argued for this one in the meeting.
3. "divide": all division and modulo operations. Alexei said in the meeting that he'd heard demand for this one.
4. "legacy": all legacy packet access instructions (deprecated).
5. "map": 64-bit immediate instructions that deal with map fds or map indices.
6. "code": 64-bit immediate instruction that has a "code pointer" type.
7. "func": program-local functions.I thought for a while about whether this should be part of the basic conformance group, and talked through it with Jakub Kicinski. I do think it makes sense to keep it separate like this. For e.g. devices with Harvard architectures, it could get quite non-trivial for the verifier to determine whether accesses to arguments stored in special register are safe. Definitely not impossible, and overall very useful to support this, but in order to ease vendor adoption it's probably best to keep this separate.
Quoted 9 lines
Things that I *think* don't need a separate conformance group (can just be in "basic") include:
a. Call helper function by address or BTF ID. A runtime that doesn't support these simply won't expose any
such helper functions to BPF programs.
b. Platform variable instructions (dst =var_addr(imm)). A runtime that doesn't support this simply won't
expose any platform variables to BPF programs.
Quoted 3 lines
Quoted 1 line
Comments? (Let the bikeshedding begin...)
This list seems logical to me,
I think we should do just two categories: legacy and the rest, since any scheme will be flawed and infinite bikeshedding will ensue. For example, let's take a look at #2 atomic...
Should it include or exclude atomic_add insn ? It was added at the very beginning of BPF ISA and was used from day one. Without it it's impossible to count stats. The typical network or tracing use case needs to count events and one cannot do it without atomic increment. Eventually per-cpu maps were added as an alternative. I suspect any platform that supports #1 basic insn without atomic_add will not be practically useful.
Should atomic_add be a part of "basic" then? But it's atomic. Then what about atomic_fetch_add insn? It's pretty close semantically. Part of atomic or part of basic?
Another example, #3 divide. bpf cpu=v1 ISA only has unsigned div/mod. Eventually we added a signed version. Integer division is one of the slowest operations in a HW. Different cpus have different flavors of them 64/32 64/64 32/32, etc. All with different quirks. cpu=v1 had modulo insn because in tracing one often needs to do it to select a slot in a table, but in networking there is rarely a need. So bpf offload into netronome HW doesn't support it (iirc). Should div/mod signed/unsigned be a part of basic? or separate? Only 32 or 64 bit?
Hence my point: legacy and the rest (as of cpu=v4) are the only two categories we should have in _this_ version of the standard.
Rest assured we will add new insn in the coming months.
I suggest we figure out conformance groups for future insns at that time. That would be the time to argue and actually extract value out of discussion. Retroactive bike shedding is a bike shedding and nothing else.
Re: [Bpf] BPF ISA conformance groups
Quoted 7 lines
Hence my point: legacy and the rest (as of cpu=v4) are the only two categories we should have in _this_ version of the standard.
Rest assured we will add new insn in the coming months.
I suggest we figure out conformance groups for future insns at that time. That would be the time to argue and actually extract value out of discussion. Retroactive bike shedding is a bike shedding and nothing else.
If some existing implementations aren't supporting some of these instructions don't we need a way to make a profile that says that so that tools can know what they have to generate for things to work? That to my mind is the reason we would define the profiles.
Sincerely,
Watson
Quoted 5 lines
--
Bpf mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/bpf
Signature · 1 line
Astra mortemque praestare gradatim
Re: [Bpf] BPF ISA conformance groups
In reply to Alexei StarovoitovQuoted 68 lines · Alexei Starovoitov
Quoted 67 lines · David Vernet
Quoted 36 lines · On Sat, Dec 02, 2023 at 11:51:50AM -0800…
Quoted 2 lines
From David Vernet's WG summary:
After this update, the discussion moved to a topic for the BPF ISAdocument that has yet to be resolved:
Quoted 1 line
ISA RFC compliance. Dave pointed out that we still need to specify which
instructions in the ISA are
Quoted 1 line
MUST, SHOULD, etc, to ensure interoperability. Several different options
were presented, including
Quoted 1 line
having individual-instruction granularity, following the clang CPU
versioning convention, and grouping
Quoted 3 lines
instructions by logical functionality.
We did not obtain consensus at the conference on which was the best way
forward. Some of the points raised include the following:
Quoted 8 lines
- Following the clang CPU versioning labels is somewhat arbitrary. It may not be appropriate to standardize around grouping that is a result of largely organic historical artifacts.
- If we decide to do logical grouping, there is a danger of bikeshedding. Looking at anecdotes from industry, some vendors such as Netronome elected to not support particular instructions for performance reasons.My sense of the feedback in general was to group instructions by logical functionality, and only create separate
conformance groups where there is some legitimate technical reason that a runtime might not want to support
a given set of instructions. Based on discussion during the meeting, here's a strawman set of conformance
groups to kick off discussion. I've tried to use short (like 6 characters or fewer) names for ease of display in
document tables, and potentially in command line options to tools that might want to use them.A given runtime platform would be compliant to some set of the following conformance groups:
Quoted 10 lines
1. "basic": all instructions not covered by another group below.
2. "atomic": all Atomic operations. I think Christoph argued for this one in the meeting.
3. "divide": all division and modulo operations. Alexei said in the meeting that he'd heard demand for this one.
4. "legacy": all legacy packet access instructions (deprecated).
5. "map": 64-bit immediate instructions that deal with map fds or map indices.
6. "code": 64-bit immediate instruction that has a "code pointer" type.
7. "func": program-local functions.I thought for a while about whether this should be part of the basic conformance group, and talked through it with Jakub Kicinski. I do think it makes sense to keep it separate like this. For e.g. devices with Harvard architectures, it could get quite non-trivial for the verifier to determine whether accesses to arguments stored in special register are safe. Definitely not impossible, and overall very useful to support this, but in order to ease vendor adoption it's probably best to keep this separate.
Quoted 9 lines
Things that I *think* don't need a separate conformance group (can just be in "basic") include:
a. Call helper function by address or BTF ID. A runtime that doesn't support these simply won't expose any
such helper functions to BPF programs.
b. Platform variable instructions (dst =var_addr(imm)). A runtime that doesn't support this simply won't
expose any platform variables to BPF programs.
Quoted 6 lines
Quoted 3 lines
Quoted 1 line
Comments? (Let the bikeshedding begin...)
This list seems logical to me,
I think we should do just two categories: legacy and the rest, since any scheme will be flawed and infinite bikeshedding will ensue.
If we do this, then aren't we forcing every vendor that adds BPF support to support every single instruction if they want to be compliant?
Quoted 11 lines
For example, let's take a look at #2 atomic...
Should it include or excludeatomic_addinsn ? It was added at the very beginning of BPF ISA and was used from day one. Without it it's impossible to count stats. The typical network or tracing use case needs to count events and one cannot do it without atomic increment. Eventually per-cpu maps were added as an alternative. I suspect any platform that supports #1 basic insn withoutatomic_addwill not be practically useful.
Shouldatomic_addbe a part of "basic" then? But it's atomic. Then what aboutatomic_fetch_addinsn? It's pretty close semantically. Part of atomic or part of basic?
I think it's reasonable to expect that if you require an atomic add, that you may also require the other atomic instructions as well and that it would be logical to group them together, yes. I believe that Netronome supports all of the atomic instructions, as one example. If you're providing a BPF runtime in an environment where atomic adds are required, I think it stands to reason that you should probably support the other atomics as well, no?
Quoted 7 lines
Another example, #3 divide. bpf cpu=v1 ISA only has unsigned div/mod. Eventually we added a signed version. Integer division is one of the slowest operations in a HW. Different cpus have different flavors of them 64/32 64/64 32/32, etc. All with different quirks. cpu=v1 had modulo insn because in tracing one often needs to do it to select a slot in a table, but in networking there is rarely a need. So bpf offload into netronome HW doesn't support it (iirc).
Correct, my understanding is that BPF offload in netronome supports neither division nor modulo.
Quoted 9 lines
Should div/mod signed/unsigned be a part of basic? or separate? Only 32 or 64 bit?
Hence my point: legacy and the rest (as of cpu=v4) are the only two categories we should have in _this_ version of the standard.
Rest assured we will add new insn in the coming months.
I suggest we figure out conformance groups for future insns at that time. That would be the time to argue and actually extract value out of discussion. Retroactive bike shedding is a bike shedding and nothing else.
I wouldn't personally categorize this as retroactive _bikeshedding_. What we're trying to do is retroactive _grouping_, and I think what you're really arguing for is that grouping in general isn't necessary. So I think we should maybe take a step back and talk about what value it brings at a higher level to determine if the complexity / ambiguity of grouping is worth the benefit.
From my perspective, the reason that we want conformance groups is purely for compliance and cross compatibility. If someone has a BPF program that does some class of operations, then conformance groups inform them about whether their prog will be able to run on some vendor implementation of BPF. For example, if you're doing network packet filtering and doing some atomics, hashing, etc on a Netronome NIC, you'd like for it to be able to run on other NICs that implement offload as well. If a NIC isn't compliant with the atomics group, it won't be able to support your prog.
If we don't have conformance groups, I don't see how we can provide that guarantee. I think there's essentially a 0% chance that vendors will implement every instruction; nor should they have to. So if we just do "legacy" and "other", the grouping won't really tell a vendor or BPF developer anything other than what instructions are completely useless and should be avoided.
If we want to get rid of conformance groups that's fine and I do think there's an argument for it, but I think we need to discuss this in terms of compliance and not the grouping aspect.
FWIW, my perspective is that we should be aiming to enable compliance. I don't see any reason why a BPF prog that's offloaded to a NIC to do packet filtering shouldn't be able to e.g. run on multiple devices. That certainly won't be the case for every type of BPF program, but classifying groups of instructions does seem prudent.
RE: [Bpf] BPF ISA conformance groups
David Vernet <[email protected]> wrote:
[...]
Quoted 34 lines
Quoted 34 lines
Quoted 34 lines
Quoted 13 lines
A given runtime platform would be compliant to some set of the following conformance groups:
1. "basic": all instructions not covered by another group below.
2. "atomic": all Atomic operations. I think Christoph argued for this one in the meeting.
3. "divide": all division and modulo operations. Alexei said in the meeting that he'd heard demand for this one.
4. "legacy": all legacy packet access instructions (deprecated).
5. "map": 64-bit immediate instructions that deal with map fds or map indices.
6. "code": 64-bit immediate instruction that has a "code pointer" type.
7. "func": program-local functions.I thought for a while about whether this should be part of the basic conformance group, and talked through it with Jakub Kicinski. I do think it makes sense to keep it separate like this. For e.g. devices with Harvard architectures, it could get quite non-trivial for the verifier to determine whether accesses to arguments stored in special register are safe. Definitely not impossible, and overall very useful to support this, but in order to ease vendor adoption it's probably best to keep this separate.
Quoted 10 lines
Things that I *think* don't need a separate conformance group (can just be in "basic") include:
a. Call helper function by address or BTF ID. A runtime that doesn't support these simply won't expose any
such helper functions to BPF programs.
b. Platform variable instructions (dst =var_addr(imm)). A runtime that doesn't support this simply won't
expose any platform variables to BPF programs.Comments? (Let the bikeshedding begin...)
Quoted 7 lines
Quoted 4 lines
Quoted 1 line
This list seems logical to me,
I think we should do just two categories: legacy and the rest, since any scheme will be flawed and infinite bikeshedding will ensue.
If we do this, then aren't we forcing every vendor that adds BPF support to support every single instruction if they want to be compliant?
Right, indeed I think it could hinder BPF adoption if we required every single instruction in any hardware offload card that wanted to add BPF support.
Quoted 12 lines
Quoted 11 lines
For example, let's take a look at #2 atomic...
Should it include or excludeatomic_addinsn ? It was added at the very beginning of BPF ISA and was used from day one.
Without it it's impossible to count stats. The typical network or tracing use case needs to count events and one cannot do it without atomic increment. Eventually per-cpu maps were added as an alternative. I suspect any platform that supports #1 basic insn withoutatomic_addwill not be practically useful.
Shouldatomic_addbe a part of "basic" then? But it's atomic. Then what aboutatomic_fetch_addinsn? It's pretty close semantically. Part of atomic or part of basic?
Quoted 6 lines
I think it's reasonable to expect that if you require an atomic add, that you may also require the other atomic instructions as well and that it would be logical to group them together, yes. I believe that Netronome supports all of the atomic instructions, as one example. If you're providing a BPF runtime in an environment where atomic adds are required, I think it stands to reason that you should probably support the other atomics as well, no?
I agree.
Quoted 10 lines
Quoted 7 lines
Another example, #3 divide. bpf cpu=v1 ISA only has unsigned div/mod. Eventually we added a signed version. Integer division is one of the slowest operations in a HW. Different cpus have different flavors of them 64/32 64/64 32/32, etc. All with different quirks. cpu=v1 had modulo insn because in tracing one often needs to do it to select a slot in a table, but in networking there is rarely a need. So bpf offload into netronome HW doesn't support it (iirc).
Correct, my understanding is that BPF offload in netronome supports neither division nor modulo.
In my opinion, this is a valid technical reason to put them into a separate conformance group, to allow hardware offload cards to support BPF without requiring division/modulo which they might not have space or other budget for.
Quoted 8 lines
Quoted 8 lines
Should div/mod signed/unsigned be a part of basic? or separate? Only 32 or 64 bit?
Hence my point: legacy and the rest (as of cpu=v4) are the only two categories we should have in _this_ version of the standard. Rest assured we will add new insn in the coming months.
I suggest we figure out conformance groups for future insns at that time. That would be the time to argue and actually extract value out of
Quoted 4 lines
discussion.
Quoted 1 line
Retroactive bike shedding is a bike shedding and nothing else.
I wouldn't personally categorize this as retroactive _bikeshedding_.
_ bikeshedding_ typically refers to spending a disproportionate amount of time on trivial matters. The discussion here isn't about a trivial matter, in my view, it's about encouraging adoption of BPF in standardized ways that can be reasoned about and strike a reasonable balance between platform complexity/cost and user-perceivable complexity.
Quoted 15 lines
What we're trying to do is retroactive _grouping_, and I think what you're really arguing for is that grouping in general isn't necessary.
So I think we should maybe take a step back and talk about what value it brings at a higher level to determine if the complexity / ambiguity of grouping is worth the benefit.From my perspective, the reason that we want conformance groups is purely for compliance and cross compatibility. If someone has a BPF program that does some class of operations, then conformance groups inform them about whether their prog will be able to run on some vendor implementation of BPF. For example, if you're doing network packet filtering and doing some atomics, hashing, etc on a Netronome NIC, you'd like for it to be able to run on other NICs that implement offload as well. If a NIC isn't compliant with the atomics group, it won't be able to support your prog.
Quoted 5 lines
If we don't have conformance groups, I don't see how we can provide that guarantee. I think there's essentially a 0% chance that vendors will implement every instruction; nor should they have to. So if we just do "legacy" and "other", the grouping won't really tell a vendor or BPF developer anything other than what instructions are completely useless and should be avoided.
+1 to all of above.
Quoted 9 lines
If we want to get rid of conformance groups that's fine and I do think there's an argument for it, but I think we need to discuss this in terms of compliance and not the grouping aspect.
FWIW, my perspective is that we should be aiming to enable compliance. I don't see any reason why a BPF prog that's offloaded to a NIC to do packet filtering shouldn't be able to e.g. run on multiple devices.
That certainly won't be the case for every type of BPF program, but classifying groups of instructions does seem prudent.
I agree with David's assessment above.
Dave
Re: [Bpf] BPF ISA conformance groups
Quoted 13 lines · On Tue, Dec 12, 2023 at 2:01 PM <[email protected]> wrote:
Quoted 13 lines
Quoted 12 lines
For example, let's take a look at #2 atomic...
Should it include or excludeatomic_addinsn ? It was added at the very beginning of BPF ISA and was used from day one.
Without it it's impossible to count stats. The typical network or tracing use case needs to count events and one cannot do it without atomic increment. Eventually per-cpu maps were added as an alternative. I suspect any platform that supports #1 basic insn withoutatomic_addwill not be practically useful.
Shouldatomic_addbe a part of "basic" then? But it's atomic. Then what aboutatomic_fetch_addinsn? It's pretty close semantically. Part of atomic or part of basic?
Quoted 8 lines
Quoted 6 lines
I think it's reasonable to expect that if you require an atomic add, that you may also require the other atomic instructions as well and that it would be logical to group them together, yes. I believe that Netronome supports all of the atomic instructions, as one example. If you're providing a BPF runtime in an environment where atomic adds are required, I think it stands to reason that you should probably support the other atomics as well, no?
I agree.
Your logical reasoning is indeed correct and
I agree with it,
but reality is different :)
drivers/net/ethernet/netronome/nfp/bpf/jit.c:
static int mem_atomic8(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
{
if (meta->insn.imm != BPF_ADD)
return -EOPNOTSUPP;
return mem_xadd(nfp_prog, meta, true);
}It only supports atomic_add and no other atomics.
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
Another example, #3 divide. bpf cpu=v1 ISA only has unsigned div/mod. Eventually we added a signed version. Integer division is one of the slowest operations in a HW. Different cpus have different flavors of them 64/32 64/64 32/32, etc. All with different quirks. cpu=v1 had modulo insn because in tracing one often needs to do it to select a slot in a table, but in networking there is rarely a need. So bpf offload into netronome HW doesn't support it (iirc).
Quoted 6 lines
Quoted 2 lines
Correct, my understanding is that BPF offload in netronome supports neither division nor modulo.
In my opinion, this is a valid technical reason to put them into a separate conformance group, to allow hardware offload cards to support BPF without requiring division/modulo which they might not have space or other budget for.
Also logically correct and I agree with, but reality proves all of us wrong. netronome doesn't support modulo,
but it supports integer division when the verifier can determine property of the constant.BPF_ALU64 | BPF_DIV | BPF_K works for positive imm32,
but BPF_X works when the verifier is smart with plenty of quirks and subtle conditions.
It works with the help of cool math reciprocal_value_adv()
in include/linux/reciprocal_div.h
which converts div to shifts and muls.
So should div_K and div_X be in separate groups ?
Should mod_[K|X] be there as well or not?
To determine the grouping should we use logic or reality?
I'm arguing that whatever clean and logical grouping we can come up with it won't stand a test of real use.
Re: [Bpf] BPF ISA conformance groups
Quoted 29 lines · Alexei Starovoitov
Quoted 13 lines · On Tue, Dec 12, 2023 at 2:01 PM <[email protected]> wrote:
Quoted 13 lines
Quoted 12 lines
For example, let's take a look at #2 atomic...
Should it include or excludeatomic_addinsn ? It was added at the very beginning of BPF ISA and was used from day one.
Without it it's impossible to count stats. The typical network or tracing use case needs to count events and one cannot do it without atomic increment. Eventually per-cpu maps were added as an alternative. I suspect any platform that supports #1 basic insn withoutatomic_addwill not be practically useful.
Shouldatomic_addbe a part of "basic" then? But it's atomic. Then what aboutatomic_fetch_addinsn? It's pretty close semantically. Part of atomic or part of basic?Quoted 8 lines
Quoted 6 lines
I think it's reasonable to expect that if you require an atomic add, that you may also require the other atomic instructions as well and that it would be logical to group them together, yes. I believe that Netronome supports all of the atomic instructions, as one example. If you're providing a BPF runtime in an environment where atomic adds are required, I think it stands to reason that you should probably support the other atomics as well, no?
I agree.
Your logical reasoning is indeed correct and
I agree with it,
but reality is different :)
drivers/net/ethernet/netronome/nfp/bpf/jit.c:
static intmem_atomic8(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
Quoted 8 lines
{ if (meta->insn.imm != BPF_ADD) return -EOPNOTSUPP; return mem_xadd(nfp_prog, meta, true); }It only supports
atomic_addand no other atomics.
Ahh, I misunderstood when I discussed with Kuba. I guess they supported only atomic_add because packets can be delivered out of order. So fair enough on that point, but I still stand by the claim though that if you need one type of atomic, it's reasonable to infer that you may need all of them. I would be curious to hear how much work it would have been to add support for the others. If there was an atomic conformance group, maybe they would have.
Quoted 26 lines
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
Another example, #3 divide. bpf cpu=v1 ISA only has unsigned div/mod. Eventually we added a signed version. Integer division is one of the slowest operations in a HW. Different cpus have different flavors of them 64/32 64/64 32/32, etc. All with different quirks. cpu=v1 had modulo insn because in tracing one often needs to do it to select a slot in a table, but in networking there is rarely a need. So bpf offload into netronome HW doesn't support it (iirc).
Quoted 6 lines
Quoted 2 lines
Correct, my understanding is that BPF offload in netronome supports neither division nor modulo.
In my opinion, this is a valid technical reason to put them into a separate conformance group, to allow hardware offload cards to support BPF without requiring division/modulo which they might not have space or other budget for.
Also logically correct and I agree with, but reality proves all of us wrong. netronome doesn't support modulo,
but it supports integer division when the verifier can determine property of the constant.BPF_ALU64|BPF_DIV|BPF_Kworks for positive imm32,
butBPF_Xworks when the verifier is smart with plenty of quirks and subtle conditions.
It works with the help of cool mathreciprocal_value_adv()
ininclude/linux/reciprocal_div.h
which converts div to shifts and muls.
Quoted 2 lines
So should
div_Kanddiv_Xbe in separate groups ?
Should mod_[K|X] be there as well or not?
Also fair enough r.e. the positive imm32 division. I clearly should have read the netronome jit code. For devices I do agree with you that it's questionable whether whether compliance is realistic. But I think we just don't _really_ know at this point. And regardless, I do think there's value in providing some kind of structure to inform what classes of instructions should typically be provided when possible. I also wonder whether we need to consider the cost calculus for whether they would bother to support certain instructions if there was a conformance group. To the atomic point above, I would be surprised if it would have been hugely difficult to add support for the others for Netronome.
Also, I don't think we should only be looking at Netronome as the canonical example here. From my understanding, while there's still quite a bit of work to be done, a lot of Cilium progs can run on both Windows and Linux.
Quoted 1 line
To determine the grouping should we use logic or reality?
Let's bear in mind that "reality" in the context of this conversation is a single vendor. Part of the goal of the standard is to implement something that has broad applicability. So while reality is of course very relevant, I think we should also apply some degree of logic to inform future implementations.
Quoted 2 lines
I'm arguing that whatever clean and logical grouping we can come up with it won't stand a test of real use.
Well, maybe not for Netronome, or maybe not even for any vendor (though we have no way of knowing that yet), but what about for other contexts like Windows / Linux cross-platform compat?
The answer might be "no", but to go back to my previous message, if we're going to get rid of conformance groups I think we should at least be explicit that we're doing so because we don't think compliance is a realistic goal in general.
Re: [Bpf] BPF ISA conformance groups
Quoted 5 lines · David Vernet
Quoted 2 lines
It only supports
atomic_addand no other atomics.Ahh, I misunderstood when I discussed with Kuba. I guess they supported only
atomic_addbecause packets can be delivered out of order.
Not sure why it has anything to do with packets.
Quoted 6 lines
So fair
enough on that point, but I still stand by the claim though that if you need one type of atomic, it's reasonable to infer that you may need all of them. I would be curious to hear how much work it would have been to add support for the others. If there was an atomic conformance group, maybe they would have.
The netronome wasn't trying to offload this or that insn to be in compliance. Together, netronome and bpf folks decided to focus on a set of real XDP applications and try to offload as much as practical. At that time there were -mcpu=v1 and v2 insn sets only and offloading wasn't really working well. alu32 in llvm, verifier and nfp was added to make offload practical. Eventually it became -mcpu=v3.
So compliance with any future group (basic, atomic, etc) in ISA cannot be evaluated in isolation, because nfp is not compliant with -mcpu=v4 and not compliant with -mcpu=v1,
but works well with -mcpu=v3 while v3 is an extension of v1 and v2. Which is nonsensical from standard compliance pov.
netronome offload is a success because it demonstrated
how real production XDP applications can run in a NIC at speeds that traditional CPUs cannot dream of.
It's a success despite the complexity and ugliness of BPF ISA. It's working because practical applications compiled with -mcpu=v3 produce "compliant enough" bpf code.
Quoted 3 lines
Well, maybe not for Netronome, or maybe not even for any vendor (though we have no way of knowing that yet), but what about for other contexts like Windows / Linux cross-platform compat?
bpf on windows started similar to netronome. The goal was to demonstrate real cilium progs running on windows. And it was done. Since windows is a software there was no need to add or remove anything from ISA, but due to licensing the prevail verifier had to be used which doesn't support a whole bunch of things.
This software deficiencies of non-linux verifier shouldn't be dictating grouping of the insns in the standard.
If linux can do it, windows should be able to do it just as well. So I see no problem saying that bpf on windows will be non-compliant until they support all of -mcpu=v4 insns. It's a software project with a deterministic timeline.
The standard should focus on compatibility between
HW-ish offloads where no amount of software can add support for all of -mcpu=v4.
And here I believe compliance with "basic" is not practical. When nvme HW architects will get to implement "basic" ISA they might realize that it has too much.
Producing "conformance groups" without HW folks thinking through the implementation is not going to be a success.
I worry that it will have the opposite effect.
We'll have a standard with basic, atomic, etc.
Then folks will deliver this standard on the desk of HW architects. They will give it a try and will reject the idea of implementing BPF in HW, because not implementing "basic" would mean that this vendor
is not in compliance which means no business.
Hence the standard shouldn't overfocus on compliance and groups. Just legacy and the rest will do for nvme.
legacy means "don't bother looking at those".
the rest means "pls implement these insns because they are useful, their semantics and encoding is standardized,
but pick what makes sense for your use case and your HW".
And to make such HW offload a success we'd need to work together. compiler, kernel, run-time, hw folks.
"Here is a standard. Go implement it" won't work.
Re: [Bpf] BPF ISA conformance groups
Quoted 8 lines · Alexei Starovoitov
Quoted 5 lines · David Vernet
Quoted 2 lines
It only supports
atomic_addand no other atomics.Ahh, I misunderstood when I discussed with Kuba. I guess they supported only
atomic_addbecause packets can be delivered out of order.Not sure why it has anything to do with packets.
My understanding is that the ordering of packets is an impedance with the host's ordering model. If you offload a BPF program from the host which expects to see packets in order, and then issues some atomics which process the packets in order, it won't work on the device because the packets are delivered out of order. Kuba (cc'd) can give more details if he wants, but it doesn't really matter. The salient point is that the chip could have done all of the BPF atomic instructions and it wouldn't have been much more work to implement them.
Quoted 16 lines
Quoted 6 lines
So fair
enough on that point, but I still stand by the claim though that if you need one type of atomic, it's reasonable to infer that you may need all of them. I would be curious to hear how much work it would have been to add support for the others. If there was an atomic conformance group, maybe they would have.The netronome wasn't trying to offload this or that insn to be in compliance. Together, netronome and bpf folks decided to focus on a set of real XDP applications and try to offload as much as practical. At that time there were -mcpu=v1 and v2 insn sets only and offloading wasn't really working well. alu32 in llvm, verifier and nfp was added to make offload practical. Eventually it became -mcpu=v3.
So compliance with any future group (basic, atomic, etc) in ISA cannot be evaluated in isolation, because nfp is not compliant with -mcpu=v4 and not compliant with -mcpu=v1,
Quoted 8 lines
but works well with -mcpu=v3 while v3 is an extension of v1 and v2. Which is nonsensical from standard compliance pov.
netronome offload is a success because it demonstrated
how real production XDP applications can run in a NIC at speeds that traditional CPUs cannot dream of.
It's a success despite the complexity and ugliness of BPF ISA. It's working because practical applications compiled with -mcpu=v3 produce "compliant enough" bpf code.
Something I want to make sure is clearly spelled out: are you of the opinion that a program written for offload to a Netronome device cannot and should not ever be able to run on any other NIC with BPF offload?
Quoted 12 lines
Quoted 3 lines
Well, maybe not for Netronome, or maybe not even for any vendor (though we have no way of knowing that yet), but what about for other contexts like Windows / Linux cross-platform compat?
bpf on windows started similar to netronome. The goal was to demonstrate real cilium progs running on windows. And it was done. Since windows is a software there was no need to add or remove anything from ISA, but due to licensing the prevail verifier had to be used which doesn't support a whole bunch of things.
This software deficiencies of non-linux verifier shouldn't be dictating grouping of the insns in the standard.
Quoted 8 lines
If linux can do it, windows should be able to do it just as well. So I see no problem saying that bpf on windows will be non-compliant until they support all of -mcpu=v4 insns. It's a software project with a deterministic timeline.
The standard should focus on compatibility between HW-ish offloads where no amount of software can add support for all of -mcpu=v4.
I don't agree that there's no value in standardizing for the sake of software as well, but yes it's different than what we're trying to accomplish for hardware, and I agree that hardware is the main customer here.
Even if you assume that we should completely ignore software and focus on hardware compatibility though, that seems to be orthogonal to what you're proposing here. What compatibility are we guaranteeing if there's no compliance?
Quoted 11 lines
And here I believe compliance with "basic" is not practical. When nvme HW architects will get to implement "basic" ISA they might realize that it has too much.
Producing "conformance groups" without HW folks thinking through the implementation is not going to be a success.
I worry that it will have the opposite effect.
We'll have a standard with basic, atomic, etc.
Then folks will deliver this standard on the desk of HW architects. They will give it a try and will reject the idea of implementing BPF in HW, because not implementing "basic" would mean that this vendor
is not in compliance which means no business.
I don't know enough about how compliance informs the cost-calculus and decision making of HW vendors to really make an intelligent point here, but I have to imagine that there's an equally plausible scenario where a vendor will look at the non-legacy instructions and think, "There's no possible way we could support all of these instructions", and make the same decision? Why else would they be asking for a standard if not to have some guidelines of what to implement?
Quoted 6 lines
Hence the standard shouldn't overfocus on compliance and groups. Just legacy and the rest will do for nvme.
legacy means "don't bother looking at those".
the rest means "pls implement these insns because they are useful, their semantics and encoding is standardized,
but pick what makes sense for your use case and your HW".
How do we know the semantics of the instructions won't be prohibitively expensive or impractical for certain vendors? What value do we get out of dictating semantics in the standard if we're not expecting any of these programs to be cross-compatible anyways?
Quoted 2 lines
And to make such HW offload a success we'd need to work together. compiler, kernel, run-time, hw folks.
Which kernel? Which compiler? If we all need to be in the room every time a decision is made by any vendor, then what value is the standard even providing?
Quoted 1 line
"Here is a standard. Go implement it" won't work.
What is the point of a standard if not to say, "Here's what you should go implement"?
Re: [Bpf] BPF ISA conformance groups
Quoted 4 lines · David Vernet
Something I want to make sure is clearly spelled out: are you of the opinion that a program written for offload to a Netronome device cannot and should not ever be able to run on any other NIC with BPF offload?
It's certainly fine for vendors to try to replicate Netronome offload. The point is that it was done before any standard existed. If we add compliance groups to the standard now they won't fit netronome and won't help anyone trying to be compatible with it. See the point about compatibility with -mcpu=v3 and not v1.
Quoted 2 lines
Why else would they be asking for a standard if not to have some guidelines of what to implement?
Excellent question. I don't know why nvme folks need a standard. Lack of standard didn't stop netronome.
Quoted 5 lines
How do we know the semantics of the instructions won't be prohibitively expensive or impractical for certain vendors? What value do we get out of dictating semantics in the standard if we're not expecting any of these programs to be cross-compatible anyways?
and that's a problem. hw folks are not participating in this discussion. Without implementers there is little chance to have successful guidelines for compatibility levels.
per-instruction compatibility is already accomplished.
We don't need groups for that.
Quoted 4 lines
Quoted 1 line
"Here is a standard. Go implement it" won't work.
What is the point of a standard if not to say, "Here's what you should go implement"?
Rephrasing... "go implement it _all_" won't work. The standard has value without insn groups.
Every instruction has specific meaning and encoding. That's what compatibility is about. Both sw and hw need to perform that operation.
Re: [Bpf] BPF ISA conformance groups
Quoted 11 lines · Alexei Starovoitov
Quoted 4 lines · David Vernet
Something I want to make sure is clearly spelled out: are you of the opinion that a program written for offload to a Netronome device cannot and should not ever be able to run on any other NIC with BPF offload?
It's certainly fine for vendors to try to replicate Netronome offload. The point is that it was done before any standard existed. If we add compliance groups to the standard now they won't fit netronome and won't help anyone trying to be compatible with it. See the point about compatibility with -mcpu=v3 and not v1.
It's unfortunate that it would make Netronome non-compliant, but I think we should be looking more at what makes sense for future implementations when it comes to the standard. The claim is that future devices which are compliant would be able to have replicated offload implementations.
Quoted 5 lines
Quoted 2 lines
Why else would they be asking for a standard if not to have some guidelines of what to implement?
Excellent question. I don't know why nvme folks need a standard. Lack of standard didn't stop netronome.
Christoph? Any chance you can shed some light here?
Quoted 10 lines
Quoted 4 lines
How do we know the semantics of the instructions won't be prohibitively expensive or impractical for certain vendors? What value do we get out of dictating semantics in the standard if we're not expecting any of these programs to be cross-compatible anyways?
and that's a problem. hw folks are not participating in this discussion. Without implementers there is little chance to have successful guidelines for compatibility levels.
per-instruction compatibility is already accomplished.
We don't need groups for that.
I definitely agree that it would be nice to have hw folks included in these discussions. What I don't quite understand though is why it would be necessary to have them included in the discussion to decide on conformance groups, but not on instruction semantics.
Quoted 10 lines
Quoted 4 lines
Quoted 1 line
"Here is a standard. Go implement it" won't work.
What is the point of a standard if not to say, "Here's what you should go implement"?
Rephrasing... "go implement it _all_" won't work. The standard has value without insn groups.
Every instruction has specific meaning and encoding. That's what compatibility is about. Both sw and hw need to perform that operation.
I agree that there's value in instructions having specific meaning and encodings, but my worry is that (for device offload) the value would be minimized quite a bit if a developer writing a BPF offload program doesn't also have some knowledge or guarantee of what instructions vendors have actually implemented.
If we were to do away with conformance groups, then I as a BPF user would have the guarantee: "Any hw device which happens to implement the instructions in my program will behave in a predictable way". If that user doesn't know what instructions it can count on being actually available in devices, then they're going to end up just implementing the program for a single device anyways. At that point, how useful was it really to standardize on the semantics of the instructions? That user just as soon could have read the specifications for the device and implemented the prog according to the semantics that the vendor decided were most appropriate for them.
That said, I definitely agree that there's value in standardizing the semantics for _software_, because as you said, software can eventually just be fully compliant. What's less clear to me is how useful it is for device offload without conformance groups.
Re: [Bpf] BPF ISA conformance groups
Quoted 7 lines · David Vernet
Quoted 5 lines
Quoted 2 lines
Why else would they be asking for a standard if not to have some guidelines of what to implement?
Excellent question. I don't know why nvme folks need a standard. Lack of standard didn't stop netronome.
Christoph? Any chance you can shed some light here?
netronome is a single vendor implementation. You write for their device and the standard is what they accept. NVMe is an open, multi-vendor standard. You need to be able to write your code against the spec and run it on all devices (that implement the required features). NVMe also needs another open standard as the reference as it just can't point to a void.
Quoted 5 lines
I agree that there's value in instructions having specific meaning and encodings, but my worry is that (for device offload) the value would be minimized quite a bit if a developer writing a BPF offload program doesn't also have some knowledge or guarantee of what instructions vendors have actually implemented.
Absolutely.
Quoted 10 lines
If we were to do away with conformance groups, then I as a BPF user would have the guarantee: "Any hw device which happens to implement the instructions in my program will behave in a predictable way". If that user doesn't know what instructions it can count on being actually available in devices, then they're going to end up just implementing the program for a single device anyways. At that point, how useful was it really to standardize on the semantics of the instructions? That user just as soon could have read the specifications for the device and implemented the prog according to the semantics that the vendor decided were most appropriate for them.
We need the concept in the spec just to allow future extensability.
Re: [Bpf] BPF ISA conformance groups
Quoted 2 lines · Christoph Hellwig
We need the concept in the spec just to allow future extensability.
Completely agree that the concept of the groups is necessary.
I'm arguing that what was proposed:
1. "basic": all instructions not covered by another group below.
2. "atomic": all Atomic operations.
3. "divide": all division and modulo operations.
4. "legacy": all legacy packet access instructions (deprecated).
5. "map": 64-bit immediate instructions that deal with map fds or map indices.
6. "code": 64-bit immediate instruction that has a "code pointer" type.
7. "func": program-local functions.
logically makes sense, but might not work for HW
(based on the history of nfp offload).
imo "basic" and "legacy" won't work either.
So it's a lesser evil.
Anyway, let's look at:
| BPF_CALL | 0x8 | 0x0 | call helper | see Helper | | | | | function by address | functions | | | | | | (Section 3.3.1) | +----------+-------+-----+---------------------+-------------------+ | BPF_CALL | 0x8 | 0x1 | call PC += imm | see Program-local | | | | | | functions | | | | | | (Section 3.3.2) | +----------+-------+-----+---------------------+-------------------+ | BPF_CALL | 0x8 | 0x2 | call helper | see Helper | | | | | function by BTF ID | functions | | | | | | (Section 3.3.
Having separate category 7 for single insn BPF_CALL 0x8 0x1 while keeping 0x8 0x0 and 0x8 0x2 in "basic" seems just as logical as having atomic_add insn in "basic" instead of "atomic".
Then we have several kinds of ld_imm64. Sounds like the idea is to split 0x18 0x4 into "code" and the rest into "map" group? Is it logical or not?
Maybe we should do risc-v like group instead?
Just these 4:
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
- Integer Multiplication and Division
- Atomic Instructions
And that's it. The rest of risc-v groups have no equivalent in bpf isa.
RE: [Bpf] BPF ISA conformance groups
Quoted 45 lines
-----Original Message-----
From: Alexei Starovoitov <[email protected]>
Sent: Monday, December 18, 2023 5:15 PM
To: Christoph Hellwig <[email protected]>
Cc: David Vernet <[email protected]>; Dave Thaler <[email protected]>; [email protected]; bpf <[email protected]>; Jakub Kicinski <[email protected]>
Subject: Re: [Bpf] BPF ISA conformance groupsQuoted 2 lines · Christoph Hellwig
We need the concept in the spec just to allow future extensability.
Completely agree that the concept of the groups is necessary.
I'm arguing that what was proposed:
1. "basic": all instructions not covered by another group below.
2. "atomic": all Atomic operations.
3. "divide": all division and modulo operations.
4. "legacy": all legacy packet access instructions (deprecated).
5. "map": 64-bit immediate instructions that deal with map fds or map indices.
6. "code": 64-bit immediate instruction that has a "code pointer" type.
7. "func": program-local functions.logically makes sense, but might not work for HW (based on the history of nfp offload).
imo "basic" and "legacy" won't work either.
So it's a lesser evil.Anyway, let's look at:
| BPF_CALL | 0x8 | 0x0 | call helper | see Helper | | | | | function by address | functions | | | | | | (Section 3.3.1) | +----------+-------+-----+---------------------+-------------------+ | BPF_CALL | 0x8 | 0x1 | call PC += imm | see Program-local | | | | | | functions | | | | | | (Section 3.3.2) | +----------+-------+-----+---------------------+-------------------+ | BPF_CALL | 0x8 | 0x2 | call helper | see Helper | | | | | function by BTF ID | functions | | | | | | (Section 3.3.
Quoted 3 lines
Having separate category 7 for single insn
BPF_CALL0x80x1while keeping0x80x0and0x80x2in "basic" seems just as logical as havingatomic_addinsn in "basic" instead of "atomic".
If a platform exposes no helper functions, then 0x8 0x0 and 0x8 0x2 have no meaning and in my view don't need a separate conformance group since a program using them would fail the verifier anyway.
0x8 0x1 on the other hand wouldn't be invalid just due to the imm value, and so tools (compiler, verifier, whatever) need some other way to know whether it's supported, hence the conformance group.
Quoted 3 lines
Then we have several kinds of
ld_imm64. Sounds like the idea is to split0x180x4into "code" and the rest into "map" group?
Is it logical or not?
I don't know of another easy way for a tool like a compiler (LLVM, gcc, rust compiler, etc.) to know whether map instructions are legal or not.
That said, I think map_val() is problematic for a cross-platform compiler...
https://elixir.bootlin.com/linux/latest/source/Documentation/bpf/linux-notes.rst says "Linux only supports the 'map_val(map)' operation on array maps with a single element." Now if one platform supports it on one type of map and another platform doesn't, then the compiler has to magically know whether to allow this optimization (compared to requiring using a helper function to access the map value) or not.
Quoted 4 lines
Maybe we should do risc-v like group instead?
Just these 4:
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
If there's platforms that would support one of the above and not the other (are there?) then I agree splitting them would make sense.
Quoted 4 lines
- Integer Multiplication and Division
- Atomic InstructionsAnd that's it. The rest of risc-v groups have no equivalent in bpf isa.
Dave
Re: [Bpf] BPF ISA conformance groups
Quoted 46 lines · On Tue, Dec 19, 2023 at 10:10 AM <[email protected]> wrote:
Quoted 46 lines
-----Original Message-----
From: Alexei Starovoitov <[email protected]>
Sent: Monday, December 18, 2023 5:15 PM
To: Christoph Hellwig <[email protected]>
Cc: David Vernet <[email protected]>; Dave Thaler <[email protected]>; [email protected]; bpf <[email protected]>; Jakub Kicinski <[email protected]>
Subject: Re: [Bpf] BPF ISA conformance groupsQuoted 2 lines · Christoph Hellwig
We need the concept in the spec just to allow future extensability.
Completely agree that the concept of the groups is necessary.
I'm arguing that what was proposed:
1. "basic": all instructions not covered by another group below.
2. "atomic": all Atomic operations.
3. "divide": all division and modulo operations.
4. "legacy": all legacy packet access instructions (deprecated).
5. "map": 64-bit immediate instructions that deal with map fds or map indices.
6. "code": 64-bit immediate instruction that has a "code pointer" type.
7. "func": program-local functions.logically makes sense, but might not work for HW (based on the history of nfp offload).
imo "basic" and "legacy" won't work either.
So it's a lesser evil.Anyway, let's look at:
| BPF_CALL | 0x8 | 0x0 | call helper | see Helper | | | | | function by address | functions | | | | | | (Section 3.3.1) | +----------+-------+-----+---------------------+-------------------+ | BPF_CALL | 0x8 | 0x1 | call PC += imm | see Program-local | | | | | | functions | | | | | | (Section 3.3.2) | +----------+-------+-----+---------------------+-------------------+ | BPF_CALL | 0x8 | 0x2 | call helper | see Helper | | | | | function by BTF ID | functions | | | | | | (Section 3.3.
Quoted 7 lines
Quoted 3 lines
Having separate category 7 for single insn
BPF_CALL0x80x1while keeping0x80x0and0x80x2in "basic" seems just as logical as havingatomic_addinsn in "basic" instead of "atomic".If a platform exposes no helper functions, then
0x80x0and0x80x2have no meaning and in my view don't need a separate conformance group since a program using them would fail the verifier anyway.
Right, but bringing the verifier into the "compliance picture" makes the ISA standard incomplete.
Same can be said about nfp compliance. It's compliant with an ISA, but the verifier will reject things it doesn't support. The instruction groups need to be binary from compliance pov without external input.
I think if we move one call 8 1 into a separate group we better move all call flavors into the same group or have 3 groups for 3 different flavors of calls.
Quoted 11 lines
0x80x1on the other hand wouldn't be invalid just due to the imm value, and so tools (compiler, verifier, whatever) need some other way to know whether it's supported, hence the conformance group.Quoted 3 lines
Then we have several kinds of
ld_imm64. Sounds like the idea is to split0x180x4into "code" and the rest into "map" group?
Is it logical or not?I don't know of another easy way for a tool like a compiler (LLVM, gcc, rust compiler, etc.) to know whether map instructions are legal or not.
Quoted 6 lines
That said, I think
map_val()is problematic for a cross-platform compiler...
https://elixir.bootlin.com/linux/latest/source/Documentation/bpf/linux-notes.rst says "Linux only supports the 'map_val(map)' operation on array maps with a single element." Now if one platform supports it on one type of map and another platform doesn't, then the compiler has to magically know whether to allow this optimization (compared to requiring using a helper function to access the map value) or not.
Compiler has no idea.
All ld_imm64 and call insns look the same. The compiler emits them the same way.
The src_reg encoding is what libbpf does based on compiler relocations.
Then the verifier checks them differently and later JIT sees _all_ ld_imm64 as one type of instruction.
Same with call insn. To x86/arm64/riscv JITs there is only one BPF CALL insn.
Quoted 8 lines
Quoted 5 lines
Maybe we should do risc-v like group instead?
Just these 4:
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bitIf there's platforms that would support one of the above and not the other (are there?) then I agree splitting them would make sense.
nfp is an example. It kinda sorta supports 64-bit, but very much prefers 32.
All 32-bit architectures is another example.
They JIT nicely all 32-bit ops and struggle with 64.
Re: [Bpf] BPF ISA conformance groups
Quoted 4 lines · Alexei Starovoitov
Right, but bringing the verifier into the "compliance picture" makes the ISA standard incomplete.
Same can be said about nfp compliance. It's compliant with an ISA, but the verifier will reject things it doesn't support.
Yes, that's a good point. Especially for anything call related I think it's fine to say they are a mandatory part of the basic some coarse group, but a given program type might not support it, but that is enforced by the verifier as the compiler should not have to known about the program type.
Quoted 7 lines
All
ld_imm64and call insns look the same. The compiler emits them the same way.
Thesrc_regencoding is what libbpf does based on compiler relocations.Then the verifier checks them differently and later JIT sees _all_
ld_imm64as one type of instruction.
Same with call insn. To x86/arm64/riscv JITs there is only one BPF CALL insn.
Yup. Another case for ISA supported vs program type supported (and enforced by the verifier).
Re: [Bpf] BPF ISA conformance groups
Quoted 11 lines · Christoph Hellwig
Quoted 4 lines · Alexei Starovoitov
Right, but bringing the verifier into the "compliance picture" makes the ISA standard incomplete.
Same can be said about nfp compliance. It's compliant with an ISA, but the verifier will reject things it doesn't support.Yes, that's a good point. Especially for anything call related I think it's fine to say they are a mandatory part of the basic some coarse group, but a given program type might not support it, but that is enforced by the verifier as the compiler should not have to known about the program type.
Agreed as well.
Quoted 11 lines
Quoted 8 lines
All
ld_imm64and call insns look the same. The compiler emits them the same way.
Thesrc_regencoding is what libbpf does based on compiler relocations.Then the verifier checks them differently and later JIT sees _all_
ld_imm64as one type of instruction.
Same with call insn. To x86/arm64/riscv JITs there is only one BPF CALL insn.Yup. Another case for ISA supported vs program type supported (and enforced by the verifier).
+1
So how do we want to move forward here? It sounds like we're leaning toward's Alexei's proposal of having:
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
- Integer Multiplication and Division
- Atomic Instructions
And then either having 3 separate groups for the calls, or putting all 3 in the basic group? I'd lean towards the latter given that we're decoupling ISA compliance from the verifier, but don't feel strongly either way.
Re: [Bpf] BPF ISA conformance groups
Quoted 8 lines · David Vernet
So how do we want to move forward here? It sounds like we're leaning toward's Alexei's proposal of having:
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
- Integer Multiplication and Division
- Atomic Instructions
As in the 64-bit integer set would be an add-on to the first one which is the core set? In that case that's fine with me, but the above wording is a bit suboptimal.
Quoted 4 lines
And then either having 3 separate groups for the calls, or putting all 3 in the basic group? I'd lean towards the latter given that we're decoupling ISA compliance from the verifier, but don't feel strongly either way.
What would be the three different groups for the calls? I think just having the call instruction in the base group should be fine. We'll need to put in some wording that having support for any kind of call depends on the program type.
Re: [Bpf] BPF ISA conformance groups
Quoted 6 lines · Christoph Hellwig
Quoted 4 lines · David Vernet
So how do we want to move forward here? It sounds like we're leaning toward's Alexei's proposal of having:
Quoted 8 lines
Quoted 4 lines
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
- Integer Multiplication and Division
- Atomic InstructionsAs in the 64-bit integer set would be an add-on to the first one which is the core set? In that case that's fine with me, but the above wording is a bit suboptimal.
yes.
Here is how I was thinking about the grouping:
32-bit set: all 32-bit instructions those with BPF_ALU and BPF_JMP32 and load/store.
64-bit set: above plus BPF_ALU64 and BPF_JMP.
The idea is to allow for clean 32-bit HW offloads.
We can introduce a compiler flag that will only use such instructions and will error when 64-bit math is needed.
Details need to be thought through, of course.
Right now I'm not sure whether we need to reduce sizeof(void*) to 4 in such a case or normal 8 will still work, but from ISA perspective everything is ready. 32-bit subregisters fit well.
The compiler work plus additional verifier smartness is needed, but the end result should be very nice.
Offload of bpf programs into 32-bit embedded devices will be possible.
Quoted 9 lines
Quoted 4 lines
And then either having 3 separate groups for the calls, or putting all 3 in the basic group? I'd lean towards the latter given that we're decoupling ISA compliance from the verifier, but don't feel strongly either way.
What would be the three different groups for the calls? I think just having the call instruction in the base group should be fine. We'll need to put in some wording that having support for any kind of call depends on the program type.
+1
Re: [Bpf] BPF ISA conformance groups
Quoted 24 lines · Christoph Hellwig
Quoted 6 lines · David Vernet
Quoted 4 lines
So how do we want to move forward here? It sounds like we're leaning toward's Alexei's proposal of having:
Quoted 8 lines
Quoted 4 lines
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
- Integer Multiplication and Division
- Atomic InstructionsAs in the 64-bit integer set would be an add-on to the first one which is the core set? In that case that's fine with me, but the above wording is a bit suboptimal.
yes.
Here is how I was thinking about the grouping:
32-bit set: all 32-bit instructions those withBPF_ALUandBPF_JMP32and load/store.64-bit set: above plus
BPF_ALU64andBPF_JMP.
Quoted 10 lines
The idea is to allow for clean 32-bit HW offloads.
We can introduce a compiler flag that will only use such instructions and will error when 64-bit math is needed.
Details need to be thought through, of course.
Right now I'm not sure whether we need to reducesizeof(void*)to 4 in such a case or normal 8 will still work, but from ISA perspective everything is ready. 32-bit subregisters fit well.
The compiler work plus additional verifier smartness is needed, but the end result should be very nice.
Offload of bpf programs into 32-bit embedded devices will be possible.
This is very interesting.
Sounds like, on one hand, introducing ilp32 and lp64 C data models for BPF:
ilp32
int, long, pointers -> 32 bit
short -> 16 bit
char -> 8 bit
lp64
long, pointers -> 64 bit
int -> 32 bit
short -> 16 bit
char -> 8 bit
On the other hand, compiler flags -m32 and -m64 could determine what instruction groups are generated and what C data model is used:
-m32
Use ilp32 data model for C.
Use 32-bit instruction set.
-m64
Use lp64 data model for C.
Use both 32-bit (if/when alu32) and 64-bit instruction sets.
And perhaps introducing a bit in the ELF flags section identifying a 32-bit binary. Something like EF_BPF_32.
Would 64-bit ELF be used also in cases where BPF is offloaded to 32-bit devices?
Quoted 11 lines
Quoted 9 lines
Quoted 4 lines
And then either having 3 separate groups for the calls, or putting all 3 in the basic group? I'd lean towards the latter given that we're decoupling ISA compliance from the verifier, but don't feel strongly either way.
What would be the three different groups for the calls? I think just having the call instruction in the base group should be fine. We'll need to put in some wording that having support for any kind of call depends on the program type.
+1
Signature · 3 lines
Bpf mailing list [email protected] https://www.ietf.org/mailman/listinfo/bpf
Re: [Bpf] BPF ISA conformance groups
Quoted 56 lines · Jose E. Marchesi
Quoted 24 lines · Christoph Hellwig
Quoted 6 lines · David Vernet
Quoted 4 lines
So how do we want to move forward here? It sounds like we're leaning toward's Alexei's proposal of having:
Quoted 8 lines
Quoted 4 lines
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
- Integer Multiplication and Division
- Atomic InstructionsAs in the 64-bit integer set would be an add-on to the first one which is the core set? In that case that's fine with me, but the above wording is a bit suboptimal.
yes.
Here is how I was thinking about the grouping:
32-bit set: all 32-bit instructions those withBPF_ALUandBPF_JMP32and load/store.64-bit set: above plus
BPF_ALU64andBPF_JMP.Quoted 10 lines
The idea is to allow for clean 32-bit HW offloads.
We can introduce a compiler flag that will only use such instructions and will error when 64-bit math is needed.
Details need to be thought through, of course.
Right now I'm not sure whether we need to reducesizeof(void*)to 4 in such a case or normal 8 will still work, but from ISA perspective everything is ready. 32-bit subregisters fit well.
The compiler work plus additional verifier smartness is needed, but the end result should be very nice.
Offload of bpf programs into 32-bit embedded devices will be possible.This is very interesting.
Sounds like, on one hand, introducing ilp32 and lp64 C data models for BPF:
ilp32
int, long, pointers -> 32 bit
short -> 16 bit
char -> 8 bitlp64
long, pointers -> 64 bit
int -> 32 bit
short -> 16 bit
char -> 8 bitOn the other hand, compiler flags -m32 and -m64 could determine what instruction groups are generated and what C data model is used:
Review
Quoted 9 lines
(quoted diff) +0
-2-m32 Use ilp32 data model for C. Use 32-bit instruction set. -m64 Use lp64 data model for C. Use both 32-bit (if/when alu32) and 64-bit instruction sets.
This all seems reasonable to me.
Quoted 5 lines
And perhaps introducing a bit in the ELF flags section identifying a 32-bit binary. Something like
EF_BPF_32.Would 64-bit ELF be used also in cases where BPF is offloaded to 32-bit devices?
I expect it would be preferable to not use ELF-64 here, but I also don't think this is necessarily something we need to figure out now. Hopefully this is all stuff we can iron out once we start to really sink our teeth into the ABI doc.
RE: [Bpf] BPF ISA conformance groups
Quoted 47 lines
-----Original Message-----
From: David Vernet <[email protected]>
Sent: Tuesday, January 23, 2024 1:40 PM
To: Jose E. Marchesi <[email protected]>
Cc: Alexei Starovoitov <[email protected]>; Christoph Hellwig <[email protected]>; Dave Thaler <[email protected]>; [email protected]; bpf <[email protected]>; Jakub Kicinski <[email protected]>; [email protected]
Subject: Re: [Bpf] BPF ISA conformance groupsQuoted 2 lines · Jose E. Marchesi
Quoted 2 lines
On Mon, Jan 8, 2024 at 8:00 AM Christoph Hellwig <[email protected]>
Quoted 33 lines · wrote:
Quoted 32 lines
Quoted 6 lines · David Vernet
Quoted 4 lines
So how do we want to move forward here? It sounds like we're leaning toward's Alexei's proposal of having:
Quoted 8 lines
Quoted 4 lines
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
- Integer Multiplication and Division
- Atomic InstructionsAs in the 64-bit integer set would be an add-on to the first one which is the core set? In that case that's fine with me, but the above wording is a bit suboptimal.
yes.
Here is how I was thinking about the grouping:
32-bit set: all 32-bit instructions those withBPF_ALUandBPF_JMP32and load/store.64-bit set: above plus
BPF_ALU64andBPF_JMP.The idea is to allow for clean 32-bit HW offloads.
We can introduce a compiler flag that will only use such instructions and will error when 64-bit math is needed. Details need to be thought through, of course.
Right now I'm not sure whether we need to reducesizeof(void*)to 4 in such a case or normal 8 will still work, but from ISA perspective everything is ready. 32-bit subregisters fit well.
The compiler work plus additional verifier smartness is needed, but the end result should be very nice.
Offload of bpf programs into 32-bit embedded devices will be possible.
Quoted 3 lines
Quoted 1 line
This is very interesting.
this is necessarily something we need to figure out now. Hopefully this is all stuff we can iron out once we start to really sink our teeth into the ABI doc.
"Integer Multiplication and Division" in this thread doesn't seem to separate between 32-bit vs 64-bit. Is the proposal that multiplication/division is ok to require 64-bit operations? I had expected one rationale for the 32bit multiplication/division instructions is to accommodate 32-bit-only
implementations. So should we have separate groups for 32-bit vs
64-bit for the multiplication/division instructions?
Similar question goes for the atomic instructions, i.e., should we have separate conformance groups for 32-bit vs 64-bit atomics?
Dave
Re: [Bpf] BPF ISA conformance groups
Quoted 59 lines · On Tue, Jan 23, 2024 at 3:29 PM <[email protected]> wrote:
Quoted 48 lines
-----Original Message-----
From: David Vernet <[email protected]>
Sent: Tuesday, January 23, 2024 1:40 PM
To: Jose E. Marchesi <[email protected]>
Cc: Alexei Starovoitov <[email protected]>; Christoph Hellwig <[email protected]>; Dave Thaler <[email protected]>; [email protected]; bpf <[email protected]>; Jakub Kicinski <[email protected]>; [email protected]
Subject: Re: [Bpf] BPF ISA conformance groupsQuoted 2 lines · Jose E. Marchesi
Quoted 2 lines
On Mon, Jan 8, 2024 at 8:00 AM Christoph Hellwig <[email protected]>
Quoted 33 lines · wrote:
Quoted 32 lines
Quoted 6 lines · David Vernet
Quoted 4 lines
So how do we want to move forward here? It sounds like we're leaning toward's Alexei's proposal of having:
Quoted 8 lines
Quoted 4 lines
- Base Integer Instruction Set, 32-bit
- Base Integer Instruction Set, 64-bit
- Integer Multiplication and Division
- Atomic InstructionsAs in the 64-bit integer set would be an add-on to the first one which is the core set? In that case that's fine with me, but the above wording is a bit suboptimal.
yes.
Here is how I was thinking about the grouping:
32-bit set: all 32-bit instructions those withBPF_ALUandBPF_JMP32and load/store.64-bit set: above plus
BPF_ALU64andBPF_JMP.The idea is to allow for clean 32-bit HW offloads.
We can introduce a compiler flag that will only use such instructions and will error when 64-bit math is needed. Details need to be thought through, of course.
Right now I'm not sure whether we need to reducesizeof(void*)to 4 in such a case or normal 8 will still work, but from ISA perspective everything is ready. 32-bit subregisters fit well.
The compiler work plus additional verifier smartness is needed, but the end result should be very nice.
Offload of bpf programs into 32-bit embedded devices will be possible.Quoted 3 lines
Quoted 1 line
This is very interesting.
this is necessarily something we need to figure out now. Hopefully this is all stuff we can iron out once we start to really sink our teeth into the ABI doc.
"Integer Multiplication and Division" in this thread doesn't seem to separate between 32-bit vs 64-bit. Is the proposal that multiplication/division is ok to require 64-bit operations? I had expected one rationale for the 32bit multiplication/division instructions is to accommodate 32-bit-only
implementations. So should we have separate groups for 32-bit vs
64-bit for the multiplication/division instructions?
Quoted 2 lines
Similar question goes for the atomic instructions, i.e., should we have separate conformance groups for 32-bit vs 64-bit atomics?
risc-v defines only one group "M" for div/mul and another group "A" for atomics.
What it means that groups "base32 + M" means that only 32-bit mul is available while "base64 + M" means that both 32 and 64-bit alu is there.
Re: [Bpf] BPF ISA conformance groups
In reply to Alexei StarovoitovQuoted 5 lines · Alexei Starovoitov
Here is how I was thinking about the grouping:
32-bit set: all 32-bit instructions those withBPF_ALUandBPF_JMP32and load/store.64-bit set: above plus
BPF_ALU64andBPF_JMP.
Sound good, modulo the sets beeing exclusive or includig others, but that's really a semantic thing for the standard and doesn't have an affect on the implementations.
RE: [Bpf] BPF ISA conformance groups
In reply to Alexei StarovoitovAlexei Starovoitov <[email protected]> wrote:
[...]
Quoted 6 lines
Quoted 3 lines
Well, maybe not for Netronome, or maybe not even for any vendor (though we have no way of knowing that yet), but what about for other contexts like Windows / Linux cross-platform compat?
bpf on windows started similar to netronome. The goal was to demonstrate real cilium progs running on windows. And it was done.
The eBPF for Windows project's origin was independent of Cilium per se. The goal was to enable us to write BPF programs that worked on both Windows and Linux, rather than doing similar work separately which would double the work.
Once the work was far enough along, Cilium then became an interesting test case to use in a demo since it was popular and recognizeable.
Dave
Re: [Bpf] BPF ISA conformance groups
In reply to David VernetQuoted 5 lines · David Vernet
Quoted 2 lines
I think we should do just two categories: legacy and the rest, since any scheme will be flawed and infinite bikeshedding will ensue.
If we do this, then aren't we forcing every vendor that adds BPF support to support every single instruction if they want to be compliant?
Yes, you do. And if we have use cases and implementation restrictions that ask for not supporting some that would be the biggest reason to have more groups. I brough up some examples where we don't need e.g. atomics. I've not really heard from implementor that implementing the instructions is a burden for them, though.
Quoted 7 lines
I think it's reasonable to expect that if you require an atomic add, that you may also require the other atomic instructions as well and that it would be logical to group them together, yes. I believe that Netronome supports all of the atomic instructions, as one example. If you're providing a BPF runtime in an environment where atomic adds are required, I think it stands to reason that you should probably support the other atomics as well, no?
Agreed.
Quoted 5 lines
From my perspective, the reason that we want conformance groups is purely for compliance and cross compatibility. If someone has a BPF program that does some class of operations, then conformance groups inform them about whether their prog will be able to run on some vendor implementation of BPF.
Yes.
Quoted 5 lines
FWIW, my perspective is that we should be aiming to enable compliance. I don't see any reason why a BPF prog that's offloaded to a NIC to do packet filtering shouldn't be able to e.g. run on multiple devices. That certainly won't be the case for every type of BPF program, but classifying groups of instructions does seem prudent.
100% agreed.