eBPF Compatibility

[Lichtso]

Based on the discussions on Discord, Slack and the linked SIMDs this is an aggregation of all the things related to the aspiration of the ISA becoming compatible with eBPF.

Bytecode

1. Implement the JMP32 instruction class and the SDIV and SMOD instructions
2. Encode callx call target in the dst reg instead of the immediate value
3. Split call and syscall by src reg instead of by opcode
4. syscall encodes a hash value in the immediate field (SIMD-0178)
5. Remove the PQR arithmetic instructions (SIMD-0174)

Assembly

1. Syntax
2. Mnemonics
3. Directives

ELF container

1. Version discrimination against SBPFv0 would need to be decided
2. Change the file type from shared lib to object e_type = ET_REL
3. Back to e_machine = EM_BPF
4. Eliminate relocations with static syscalls (SIMD-0178)
5. Only parse the ELF header, no program headers or section headers (SIMD-0189)
6. Abandon (SIMD-0179): restrictions on unstructured cross function control flow

Linker

Do fat-LTO in bpf-linker: Compile everything to LLVM bincode, then have the linker combine these and lower them further into bytecode

1. pre-applying all relocations for static syscalls in the linker ("take relocation code in aya and move it to bpf-linker")
2. adjust the address space layout
3. adjust the ELF container
4. find stack size requirement of each function and inject an additional instruction (add64 r10, -stack_frame_bytes) in the function preamble (SIMD-0166)

Changes required on upstream

1. Aggregate return types
2. Allow multiple returns
3. More than 5 arguments with a sub ABI, maybe?

[LucasSte]

Are we still going to support dynamic stack frames?

[LucasSte]

We need to allow multiple returns, not only aggregate return types.

Also, we would need to check if we can upstream the code generation improvements I did recently.

[LucasSte]

Some other things are tuned for SBF, like the threshold for memops.

We also have our own implementation of compiler builtins to be compatible with static syscalls.

[LucasSte]

The BPF target also supports JSET: llvm/llvm-project#73161

Although we can make the VM compatible with BPF, we have no control of its design choices and the newer instructions that might be added. We can remain relatively stable for some time, but ultimately we'll need to catch up with the BPF changes.

My question is whether it is worth the effort to keep catching up with BPF changes, assuming that will require constant VM updates, program versioning and feature gates?

[deanmlittle]

jset works right now with a v0 program. you only disabled it in your compiler tooling, not the actual vm.

[LucasSte]

Yes, you are right. I missed it when it was added to the compiler.

For now, I don't think it is worth emitting that instruction, because it does not have an opposite. In our fork, we enabled branch analysis, which allows LLVM to calculate jump frequencies and prefer fall through instead of jumps for basic blocks that are executed together. One of the premisses for that to work is being able to reverse the jump condition. The analysis we enabled has had a positive impact in decreasing CUs for compiled programs. Bringing JSET to the compiler would mean turning that optimization off.

One of the disadvantages of using the upstream BPF compiler (this is different than maintaining eBPF compatibility) is that its code generation is not good. The LLVM BPF target deliberately disables optimizations and transforms the code to appease the kernel verifier, which is stricter than ours. In my view, that would be a regression.

@deanmlittle you seem to be very interested in the compiler part, if you are interested I can show you how the toolchain works and perhaps you can also propose other improvements in our code generation.

[deanmlittle]

it is actually a very good instruction that saves CUs on a system program ID comparison!

[LucasSte]

it is actually a very good instruction that saves CUs on a system program ID comparison!

What would that comparison look like? Won't you need four compares either way?

[LucasSte]

Also missing: sdiv and smod.

[LucasSte]

Given that the pressure for less CUs in contracts keeps mounting, since users pay for CUs, I wonder if sticking to the BPF standard won't be a liability for us and hinder our innovation capacity.

One of the examples I can give is the number of registers. If we could, for instance, increase the number of registers to 16 (16 is simply to avoid leaving from the BPF ISA standard), we would drastically decrease the CU consumption of contracts. This change is not costly to the validator and easy to implement in the compiler.

[LucasSte]

eBPF allows jumps with 32 bit offsets: https://github.com/anza-xyz/llvm-project/blob/0c30adaa95a6c007f6210d41735371f25c4c91ed/llvm/lib/Target/BPF/BPFInstrInfo.td#L637-L647

[LucasSte]

It looks like eBPF wants to support predicated instructions, like may_goto. My guess is that they want to leverage x86 or arm's instructions that jump if a register is set.

anza-xyz/llvm-project@0e0bfac

All these changes make me wonder how much our effort is worth into pursuing eBPF compatibility. Clearly, the way eBPF is heading not necessarily benefits us, and pile up our VM backlog just to catch up with them.

[LucasSte]

PS: may_goto is a new opcode.

[LucasSte]

eBPF default CPU is v3. The next version v4 also has sign extend loads and sign extend mov:

anza-xyz/llvm-project@6c412b6

[LucasSte]

Change the file type from shared lib to object e_type = ET_REL

Give that we'll need to implement the linker ourselves, I don't think we need to change the file type. That is better for compatibility with tooling.