Solana BPF v2

[jackcmay]

Problem

Solana Bytecode Format is a variation of eBPF. Some of the architectural requirements are different from eBPF and what Solana needs. A new version 2 is needed to move away from BPF and meet the specific needs of Solana

Proposed Solution

• #34258
  • BTF ELF-section parsing
  • Static type inference
  • Instruction stream verification
• Dynamic linking / dynamic dispatch
• Decide about implicit vs explicit sign extension in 32bit ALU operations (Sign Extension in SBPFv2 #32924)
• ISA changes: LLVM changes related to BPFv2 #34250
• Reduce the overhead for the loader at runtime, by letting the linker concatenate sections to become consecutive in virtual address space (elf: avoid copying read only sections rbpf#284 and elf: add support for rodata sections already aligned to MM_PROGRAM_START rbpf#301)
• Restrict the control flow:
  • Only symbols registered in the ELF or referenced by call are valid destinations for callx. (Refactor - Restrict callx to registered functions rbpf#397 and Refactor - Unify call and callx error handlers in JIT rbpf#439)
  • Functions can not start in the middle of a lddw instruction (Fix - Makes functions starting in the middle of lddw fail verification in SBFv2 rbpf#440)
  • Jumps have to stay within a function, only call / callx can reach other functions. (Verifier - Stricter control flow rbpf#454)
  • Forbids the fall-through at the end of a function, which now must be a unconditional-jump back into the function. (Feature - Restricts the final instruction in each function to be diverted rbpf#522)
• toolchain administration
  • New target triple SBFv2
  • New or featurized llvm backend
  • New tool cargo-build-sbf
  • Tooling changes to specify version (default to v1 for now, eventually to v2), eg. cargo build-sbf --arch=sbfv2

From a documentation perspective SBFv2 will still be referred to as "SBF" and when calling tools like cargo build-sbf a default arch will be provided, v1 initially, then a switch over to v2.

[jackcmay]

FYI @Lichtso @dmakarov

[Lichtso]

I have been thinking, that instead of adding a few new instructions and removing some others from BPF, it might be better to go with a portable-code approach directly.

We are breaking compatibility with BPF in a major anyway and we want to support other native architectures besides x86-64, such as ARMv8 AArch64 and maybe SPIR-V. These would require an entire data flow analysis and register allocation at least, because they are so different from x86-64 in their data-flow style and would not work as well as the current BPF to x86-64 conversion.

Furthermore, we could think a lot more about the final conversion steps and e.g. do things which BPF is not meant for like:

• Staying in SSA or implicit operand addressing to simplify register allocation and avoid the need for data flow analysis
• Staying in structured programming to avoid the need for control flow analysis
• Variable length instruction encoding and text section compression
• Prefetch-like hits for address translation
• Hints for loop vectorization
• Wide range of data encodings such as 128-, 256-, 512-bit values and vectors

[dmakarov]

I have been thinking, that instead of adding a few new instructions and removing some others from BPF, it might be better to go with a portable-code approach directly.

What does this mean in practical terms? What other changes to the BPF instruction set would you suggest (for now considering only supporting non-x86 ISAs)? Maybe some BPF instructions do not map directly to ARM instructions, but is it so radical that we need to redefine the BPF instruction set completely?

[Lichtso]

For the current BPF to x86-64 conversion it is really hard to do any optimizations, because most rely on static analysis that would not be necessary if that information was not thrown away by the previous compilation step.

For ARMv8 AArch64: It has almost double the registers (31) that x86-64 (16) and BPF (11) have. So not to waste them requires an entire reallocation of the registers and reorganization of the stack spilling. Again requiring a data flow and control flow analysis beforehand. All of this could also be skipped if we would not compile down to a specific register set in the first place.

For SPIR-V: The entire architecture works completely different. While you still program on what is seemingly a single thread, it is executed in bundles of 32 or 64 threads in lockstep. So control-flow-divergence has to be minimized. Also there are much more registers (thousands) for cheap context switching, but almost no cache in turn. Data is best touched only once.

[Lichtso]

What does this mean in practical terms?
redefine the BPF instruction set completely?

What I suggest is not to fork & modify BPF any further but use something else entirely.
So far I looked at WASM and GNU lightning. Designing our own from scratch is also possible.

[dmakarov]

We could change the BPF registers to unlimited number of virtual registers and do the register allocation at run-time. It would add some overhead, of course. I'm not sure it's possible to come up with an instruction set that would map to all real machine instruction sets equally well. Java bytecode is not quite a good example, and optimizing it works well for long running server applications.

SPIR-V also requires a different programming model. It seems one cannot take an arbitrary rust program and compile it for execution on SPIR-V.

[dmakarov]

What does this mean in practical terms?
redefine the BPF instruction set completely?

What I suggest is not to fork & modify BPF any further but use something else entirely. So far I looked at WASM and GNU lightning. Designing our own from scratch is also possible.

I agree this is indeed something to think about.

[Lichtso]

SPIR-V also requires a different programming model. It seems one cannot take an arbitrary rust program and compile it for execution on SPIR-V.

Definitely, while there have been some funny trials such as rust-gpu, we would really need to think the "more parallelism" thing through from end-to-end throughout the entire ecosystem, not just the VM and ISA.

We could change the BPF registers to unlimited number of virtual registers and do the register allocation at run-time.

You mean as a form of SSA, right?
What about an implicit operand addressing like a stack (FILO) or queue (FIFO) machine.
These might even reach a better instruction encoding as they don't need to encode their destination operands.

I'm not sure it's possible to come up with an instruction set that would map to all real machine instruction sets equally well. Java bytecode is not quite a good example, and optimizing it works well for long running server applications.

That is the reason why I mentioned WASM. It has its shortcomings, but it works well over a wide range of hardware architectures.

[dmakarov]

You mean as a form of SSA, right? What about an implicit operand addressing like a stack (FILO) or queue (FIFO)

Yes, this essentially echoes your suggestion of staying in SSA. By stack machine you mean we would redefine BPF abstract machine to be a stack machine the same as Java VM? I guess it's a possibility, but then we really need a good run-time binary translator (in rbpf) to optimize the code. I'm not sure why you're so concerned with instruction encoding -- is it to reduce the code size of on-chain programs?

[Lichtso]

is it to reduce the code size of on-chain programs?

Yes, I think the BPF 8-byte fixed instruction size is terribly wasteful. It might not be a concern for the Linux kernel, for us however, program size is limited by account size.

would redefine BPF abstract machine to be a stack machine

The queue (FIFO) variant might also do the trick and be more straight forward as the instruction schedule can stay in the same order.

Let's say we have a SSA form like this:

...
%3824 = add %3818, %3821
%3825 = add %3815, %3823
%3826 = mul %3824, %3825

To convert to the queue machine representation you simply:

• Remove the destination operand as that implicitly is defined by the instruction index.
• Encode the source operands as relative to the instruction index of the next instruction.

...
add %5, %2
add %9, %1
mul %1, %0

Not only does it need no destination operands, but also the numeric value of the source operands is bounded.
The instruction scheduler can achieve staying in the window of possible relative operand addresses with the same strategy as it uses for the window of possible short jumps.

[jackcmay]

There is room for both here, I think we should formally move away from "BPF" anyway. In the shorter term, the proposed changes described in this issue's description can provide benefits as well as pave the way for a more flexible evolution path for other SBF formats. Aka, SBFvX doesn't have to be anything like SBFv1 or 2.

[jackcmay]

@dmakarov How long do you think the last 4 items in the issue description would take to implement?

[dmakarov]

@dmakarov How long do you think the last 4 items in the issue description would take to implement?

The support for signed division I think we already have enabled in the llvm backend (i'll have to double check).

I started implementing the variable stack size and I believe the remaining work is in RBPF only. The same as now the programs do not manage the stack pointer, but RBPF does, I want to make RBPF manage both frame pointer and stack pointers. On the compiler side there will be only one additional instruction generated in function prologue and epilogue, that communicates the stack size to RBPF. The RBPF at run-time updates its internal data structures managing the frame and stack pointers, without exposing this to the executing program. Both frame and stack pointer are need to know the boundaries of the variable stack frame at all times. I estimate I would need another week to finish this work (but not this current week probably).