Re: BPF64: proposal of platform-independent hardware-friendly backwards-compatible eBPF alternative

On Tue, 10 Sep 2024 14:41:20 +0000
"Gavin D. Howard" <gavin@gavinhoward.com> wrote:

> Hello,
> 
> New user here, not a contributor.
> 
> > Ensuring kernel stability? Just don't allow arbitrary pointers,
> > like original BPF. Guaranteed termination time? It's possible if
> > you place some restrictions. For example, don't allow backward
> > jumps but allow function calls - in case of stack overflow,
> > terminate program. Really need backward jumps? Let's analyze for
> > what purpose. You'll find these are needed for loops on packet
> > contents. Solve it but supporting loops in "hardware"-controlled
> > loops, which can't be infinite.  
> 
> If I understand Turing-completeness correctly, the "no backward jumps
> but allow recursion and quit on stack overflow" is exactly equivalent
> to having non-infinite loops.

Sure, but then look at practical usefulness: suppose you have stack of
32 frames (current limit of eBPF and BPF64). Then you can have only 31
iterations on a loop, loosing ability to call more functions from loop
body.

> I'm not entirely sure, but I think the lack of backwards jumps would
> be "simple" to check on LLVM IR: just make sure that a basic block
> does not jump, directly or indirectly, to a basic block that
> dominates it. [1]
> 
> [1]: https://en.wikipedia.org/wiki/Dominator_(graph_theory)
> 
> And then the stack overflow mechanic would be an entirely runtime
> check, which is safer than pure static checking.
> 
> But the good thing about this is that FreeBSD could use LLVM IR as the
> BPF64 language, which means any language that compiles to LLVM is a
> possible target.
> 
> As for restricting access, I think it would be possible to check the
> instructions in LLVM IR for any unsafe instructions or calls to
> restricted functions.
> 
> The downsides:
> 
> * Someone would need to write an LLVM analyze pass or whatever they're
>   called. Maybe more than one.
> * The kernel would need the ability to compile LLVM IR, making LLVM
> part of the Ring 0 domain.
> 	* Either that, or someone builds an LLVM-to-bytecode
> translator.

Well, using LLVM were supposed for higher-level languages when
bytecode is no longer experimental, utilizing full power of optimizer,
but for direct using... let's see how they use it in Linux currently:

1) you write .c code, relatively low-level/restricted, with eBPF .h-s
2) clang turns .c into LLVM IR file (yes, this step is separate, may be
   things has changed since then, but at least it was so)
3) file with LLVM IR turned to eBPF bytecode in ELF file
4) ELF .o loaded by ip(8) or specialized loader into kernel
5) verifier checks it and most probably will return error to you :)
6) bytecode is JIT-compiled in kernel and then may be run

Linux people are in mood "let's throw more man-months instead of
thinking of better design", eBPF infrastructure consists of hundreds of
thousandls lines of code, but seems that utilizing LLVM IR directly
required too much resources even from them so was rejected.

> 	* But the analysis pass(es) must still live in the kernel.
> * There would need to be tutorials or some docs on how to write
> whatever language so that backwards jumps are avoided.

So BPF64 took simplicity pass: while you have tutorials etc. it's still
very hard to write (non-toy) code that passes verifier. I think a
language where you do not need backward jumps but have usable
constructs (so you just can't write bad code), even BAW, is a better
way to go than try to train people to fight with unnecessary Cerber.

> Please take my words with a full dose of salt; I'm not an expert on
> this or on FreeBSD goals.

BPF64 is not FreeBSD-only, you can see several non-FreeBSD mailing lists
here. It can be cross-platform and independent enough to be implemented
in e.g. network card or switch, for performance - having more registers
allows to achieve better results then eBPF for same goal.


-- 
WBR, @nuclight