4 ms·
Speaking of alternative representations of eBPF programs, one thing I've noticed about eBPF is that it's particularly well suited to asymmetric number system (A
by KMag 5y ago
Speaking of alternative representations of eBPF programs, one thing I've noticed about eBPF is that it's particularly well suited to asymmetric number system (ANS)-based compression (such as Facebook's zstd). Asymmetric number systems require compression of buffers in the opposite order that they're decompressed. In eBPF, all branches need to jump forward, so if you're compressing the byte stream backwards, you always already know the offset in the compression stream of all valid branch targets.
You'd need a first pass to find branch targets, so that you only remember the necessary bookkeeping information for branch targets as you're compressing, and the representation of branch targets takes some more space (an offset plus internal state of the ANS state machine), but a combination of eBPF and ANS-based compression still seems like a good match for a bytecode that's executed while it's being decompressed.
The table-based variants of ANS seem particularly well suited to hardware/FPGA implementation. I remember some papers IBM published showing good results in improving POWER code density for embedded applications by building some hard-wired Huffman tree based decompression into the MMU.
- monocasa 5y ago> In eBPF, all branches need to jump forward, That was true of cBPF, but eBPF simply requires that the kernel's verifier could convert the control flow graph into a DAG. So notably certain types of bounded loops are allowed, and generally both back and forward branches are allowed.
- KMag 5y agoOh, interesting. But if the DAG requirement still stands, then it can still be converted into forward-only branches. Why not force that work into the bytecode compiler (or macro assembler) and simplify the kernel logic?
- monocasa 5y agoBecause bounded loops are functionally a compression scheme on the graph. It's a tradeoff for sure though. Personally (and going way off into the weeds, these are my thoughts and not at all representative of people working on BPF) I'd also like to see other schemes eventually that also don't necessarily require verifiable halting semantics for correctness. One example: something like io_uring, but instead there's a program running just barely in kernel space, accounted to the host user thread's scheduling, issuing new syscalls already on the kernel side of the syscall boundary.