HBPF – eBPF in Hardware(github.com)
github.com
HBPF – eBPF in Hardware
https://github.com/rprinz08/hBPF
26 comments
I mean, bytecode that runs on hardware is still hardware-independent, it's the hardware that have to conform to the bytecode's interface not the other way around. If every processor in existence had to accept x86 instruction streams as valid programs, x86 would be a hardware-independent VM.
The issue would be if there are multiple bytecode formats for different hardware.
The issue would be if there are multiple bytecode formats for different hardware.
Same thing happens with IO interfaces.
https://lwn.net/Articles/805235/
https://lwn.net/Articles/805235/
It's happened before; https://en.m.wikipedia.org/wiki/Java_processor has a whole list of JVM hardware. I suppose lisp machines might also count.
I’ve thought about this kind of co-evolution before and it seems to me it always leads to very sub optimal results. The problem is making a better solution is not economically feasible because all the software already exists.
A NIC company Netronome has had something like this (i.e. running physically on the NIC) as a product for a couple of years now. They have a NIC with lots of proprietary cores that with eBPF can be made to run user code.
To be useful for capture it needed an extra feature, ability to grab a synchronized hardware time counter value, and deliver to a user-space buffer. Writing to user space memory, for kernel bypass, at least once was an underdeveloped eBPF feature; don't know its current condition.
To be useful for capture it needed an extra feature, ability to grab a synchronized hardware time counter value, and deliver to a user-space buffer. Writing to user space memory, for kernel bypass, at least once was an underdeveloped eBPF feature; don't know its current condition.
This is really cool. I wonder about whether or not putting the ISA itself directly in hardware is the right path forward, versus "virtualizing" it and compiling the bytecode again down to (yet another) architecture. It's a much better fit for hardware than a lot of "virtual" ISAs, though. There are some reasons you might do this, but then again, reasons not to. Netronome uses this virtual approach instead of baking eBPF into their processors, from my cursory understanding. An advantage of that is agility; FPGAs are only so agile compared to a software compiler and on top of that new evolving features have impacts on things like clock frequency, testing, etc.
Beyond that there are also some big "what ifs" about eBPF; for example the fact it just uses the underlying Linux kernel memory model for concurrency. Maybe this is good. Maybe this is bad. I don't know. But it has a big impact on the underlying design of the memory subsystem for any real design. Intuitively I want to say the concurrency abstractions in eBPF should have always been much, much higher level from the start for reasons like this (for example, maybe it would have just been easier to flat-out introduce the concept of transactions, if you're already going to write a verifier to check every incoming program. This is much more difficult than what the verifier does today, but it's also a very well explored one and makes the machine memory model irrelevant. It's not the kind of stuff kernel developers do or think about, though...) But it's not, so it's still definitely something to think about. Do alternative vendors handle this already if they offload programs?
There is also the current state we're in where "what is a valid eBPF program" mostly just comes down to "whatever the Linux kernel says is a valid eBPF program", so you can probably get into situations where code emitted by Clang will work in one of the two, and not the another (note: you can already get into situations where Clang will emit code from valid input that the kernel then rejects, so this probably isn't a very difficult example to construct.) This project already has some differences in ABI versus Linux, though, so...
Overall this is still a really cool project, though. You'd have to do something like this to answer all the above, and it bills itself as an experiment. You could still have a lot of fun with this even ignoring all that. And it doesn't use Verilog. 10/10.
Beyond that there are also some big "what ifs" about eBPF; for example the fact it just uses the underlying Linux kernel memory model for concurrency. Maybe this is good. Maybe this is bad. I don't know. But it has a big impact on the underlying design of the memory subsystem for any real design. Intuitively I want to say the concurrency abstractions in eBPF should have always been much, much higher level from the start for reasons like this (for example, maybe it would have just been easier to flat-out introduce the concept of transactions, if you're already going to write a verifier to check every incoming program. This is much more difficult than what the verifier does today, but it's also a very well explored one and makes the machine memory model irrelevant. It's not the kind of stuff kernel developers do or think about, though...) But it's not, so it's still definitely something to think about. Do alternative vendors handle this already if they offload programs?
There is also the current state we're in where "what is a valid eBPF program" mostly just comes down to "whatever the Linux kernel says is a valid eBPF program", so you can probably get into situations where code emitted by Clang will work in one of the two, and not the another (note: you can already get into situations where Clang will emit code from valid input that the kernel then rejects, so this probably isn't a very difficult example to construct.) This project already has some differences in ABI versus Linux, though, so...
Overall this is still a really cool project, though. You'd have to do something like this to answer all the above, and it bills itself as an experiment. You could still have a lot of fun with this even ignoring all that. And it doesn't use Verilog. 10/10.
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.
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.
> 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.
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.
Oh, 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?
Because 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.
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.
> for example, maybe it would have just been easier to flat-out introduce the concept of transactions, if you're already going to write a verifier to check every incoming program
Could you elaborate on this? Loading the program is a one time operation. The actual evocation is dependent on the program type and its location in the kernel. I do not believe there is a blanket way to describe how eBPF interacts with the VM or its concurrency model.
To your second point about verification, yes this is something that is actively being worked on. with BTF and CO-RE we've made huge strides over module loading, however, and eBPF already has many advantages over use cases where people were forced to load bespoke kernel bypass modules.
Could you elaborate on this? Loading the program is a one time operation. The actual evocation is dependent on the program type and its location in the kernel. I do not believe there is a blanket way to describe how eBPF interacts with the VM or its concurrency model.
To your second point about verification, yes this is something that is actively being worked on. with BTF and CO-RE we've made huge strides over module loading, however, and eBPF already has many advantages over use cases where people were forced to load bespoke kernel bypass modules.
I mean that, instead of exposing atomic operations in the programming model (which are imperative constructs from the CPU to write to a memory location and require a notion of a memory model), the BPF virtual ISA could have just given you an ability to execute a series of high-level actions atomically or have them fail. It is basically a very small implementation of the ACI in ACID. This is only practical in this case because an eBPF program would need to be verified (by a trusted component; in this case the kernel verifier) before it can be executed anyway; any normal language with unverified, unrestricted semantics is too difficult to bolt transactions onto. You can just define a statically-determinable subset of programs that work and are accepted. This approach would have both upsides and downsides. The downsides include the need for more precise semantics, and an increase in verifier complexity (a lesser downside is an increase in compiler complexity to compile transactions to the underlying ISA; but I consider this 'lesser' because the verifier is more important, overall.) The upsides include a nicer programming model for users and independence from the underlying memory model in the processor, which gives you a lot of degrees of freedom to attack the problem.
I don't know what you would do in the case of like, livelock though. But I also don't know what the failure mode is if, say, the program I ran today always ran and hit some dynamic error, either e.g. in the case of livelock you have to eventually just kill the program to make any further forward progress, but this seems no different than if an eBPF program simply always failed due to dynamic constraints. If the program just keeps exploding you eventually have to back off... Another downside I guess is that it's probably hard to implement transactional models in raw RTL, like this project :)
But this is all just an idea. The thrust of it is to turn small exposures of the underlying processor semantics into higher-level compiler problems. I think this would work because you don't need to solve every compiler problem perfectly, just a small subset of them for a small set of domains. It doesn't really matter for Linux today because it just picked a common subset of the memory model for eBPF, but if anyone was to design a newer language for things like this in some new system, maybe some ideas like that are worthwhile. After all, CO-RE and related projects are about bringing "portability" to BPF programs. This is just an (somewhat logical) extension of that idea to the concurrent programming model. I don't need to worry about processor consistency models when I type "COMMIT TRANSACTION" in a SQL prompt, after all.
> To your second point about verification, yes this is something that is actively being worked on.
It's sort of hard to solve right now in the "Will this arbitrary C program work or not" sense, because the underlying toolchain and kernel implementation is evolving. I know there's a userspace verifier. What would be excellent is something like the ability to compile the kernel implementation of the verifier, but in userspace, so you could use it in CI. Does this already work, maybe?
I don't know what you would do in the case of like, livelock though. But I also don't know what the failure mode is if, say, the program I ran today always ran and hit some dynamic error, either e.g. in the case of livelock you have to eventually just kill the program to make any further forward progress, but this seems no different than if an eBPF program simply always failed due to dynamic constraints. If the program just keeps exploding you eventually have to back off... Another downside I guess is that it's probably hard to implement transactional models in raw RTL, like this project :)
But this is all just an idea. The thrust of it is to turn small exposures of the underlying processor semantics into higher-level compiler problems. I think this would work because you don't need to solve every compiler problem perfectly, just a small subset of them for a small set of domains. It doesn't really matter for Linux today because it just picked a common subset of the memory model for eBPF, but if anyone was to design a newer language for things like this in some new system, maybe some ideas like that are worthwhile. After all, CO-RE and related projects are about bringing "portability" to BPF programs. This is just an (somewhat logical) extension of that idea to the concurrent programming model. I don't need to worry about processor consistency models when I type "COMMIT TRANSACTION" in a SQL prompt, after all.
> To your second point about verification, yes this is something that is actively being worked on.
It's sort of hard to solve right now in the "Will this arbitrary C program work or not" sense, because the underlying toolchain and kernel implementation is evolving. I know there's a userspace verifier. What would be excellent is something like the ability to compile the kernel implementation of the verifier, but in userspace, so you could use it in CI. Does this already work, maybe?
Ah, that makes more sense. The byte code is an evolution and not a clean room design, and the focus has always been on remaining as close to the host ISA as possible. We've had several academics work on the verifier and most of the time the solutions allow for more programs to pass, but at the cost of far, far slower program loading (upwards of 30 minutes).
> I don't know what you would do in the case of like, livelock though.
The idea is we never allow this to happen by enforcing your use of locks and memory through helpers. Helpers are really the secret sauce to how we are able to enforce memory barriers, etc. without having the author think about them too much. Helpers are essentially the new syscall layer for the kernel with the advantage that they are far less expensive to add, and there's less complaining when it's later decided they were a bad decision... :) Of course, there will be bugs in eBPF, just as their are bugs in any other part of the kernel that will cause unexpected behavior.
You are right in that a different design might have been easier to verify and less error prone, but I think that eBPF overall has been very robust, and is still far better than what we had with loading kernel modules and letting people do whatever they want, or trying to create really rigid policies through syscalls and exposing internals through VFS.
It's sort of hard to solve right now in the "Will this arbitrary C program work or not" sense, because the underlying toolchain and kernel implementation is evolving. I know there's a userspace verifier. What would be excellent is something like the ability to compile the kernel implementation of the verifier, but in userspace, so you could use it in CI. Does this already work, maybe?
There are two issues with loading - the first is as you described, which is that the verifier sometimes reject programs that clang can build. The second is that sometimes there are issues resolving BTF and fixing up programs to run against the target ABI. Both of these problems are hard to solve and I have personally seen users run into this as a major pain point. It needs improvement. Verification in userland is definitely one way to improve this. No matter what though, the nature of sitting inside the kernel is that it's very hard to keep any sort of userland step in lockstep with the kernel, and so I think this will always be a hard problem to solve.
> I don't know what you would do in the case of like, livelock though.
The idea is we never allow this to happen by enforcing your use of locks and memory through helpers. Helpers are really the secret sauce to how we are able to enforce memory barriers, etc. without having the author think about them too much. Helpers are essentially the new syscall layer for the kernel with the advantage that they are far less expensive to add, and there's less complaining when it's later decided they were a bad decision... :) Of course, there will be bugs in eBPF, just as their are bugs in any other part of the kernel that will cause unexpected behavior.
You are right in that a different design might have been easier to verify and less error prone, but I think that eBPF overall has been very robust, and is still far better than what we had with loading kernel modules and letting people do whatever they want, or trying to create really rigid policies through syscalls and exposing internals through VFS.
It's sort of hard to solve right now in the "Will this arbitrary C program work or not" sense, because the underlying toolchain and kernel implementation is evolving. I know there's a userspace verifier. What would be excellent is something like the ability to compile the kernel implementation of the verifier, but in userspace, so you could use it in CI. Does this already work, maybe?
There are two issues with loading - the first is as you described, which is that the verifier sometimes reject programs that clang can build. The second is that sometimes there are issues resolving BTF and fixing up programs to run against the target ABI. Both of these problems are hard to solve and I have personally seen users run into this as a major pain point. It needs improvement. Verification in userland is definitely one way to improve this. No matter what though, the nature of sitting inside the kernel is that it's very hard to keep any sort of userland step in lockstep with the kernel, and so I think this will always be a hard problem to solve.
This is super cool. Is the idea that you could use this as part of a NIC and get higher performance than running eBPF in the kernel?
There are already NICs that have this feature. XDP can run in one of three modes. The firsts mode simply runs the program in the kernel stack and is either for testing or used in the worst case where you have no driver support. The primary mode is for the driver author to write in the invocation of the eBPF program and then implement all the resulting actions into the driver. The third mode is offload, where the eBPF program is loaded into a Smart NIC, FPGA device and the packet is processed without the need for DMA.
By far, the most popular form is running in the driver, which can get very close to line rate for most network cards. If you have any questions about this I'd be happy to go into more detail.
By far, the most popular form is running in the driver, which can get very close to line rate for most network cards. If you have any questions about this I'd be happy to go into more detail.
Most NICs have one or more CPUs to service offload engines. This could probably happen right now.
Hi are you the author? What would I need to study to be able to do stuff like this? Are there any specific books or courses you’d recommend? Thanks
If you have any questions about eBPF I'd be happy to answer them, I work on the kernel portion.
Is it possible to do stateful stuff like NAT in eBPF without having to reimplement conntrack? I think cilium does it but has to reimplement in using maps.
Not in an XDP program, it runs almost immediately after a packet has been rxed, and yes, Cilium does this by reimplementing similar logic in BPF. You could request new helpers for a SCHED_CLS type program though. The helpers don't exist today, but eBPF is use case driven, and if there is a good use case for it, it can go onto the roadmap.
Thanks! I did find this: https://lists.linuxfoundation.org/pipermail/iovisor-dev/2017... and some references to bpf_skb_ct_lookup/bpf_xdp_ct_lookup -- are these fully baked?
There isn't much in the way of books that really take you from design to implementation when it comes to CPU design but the nand2tetris book is a good place to start.
That is a broad question, going through a FPGA tutorial buying a small dev board. My first project was something similar to this, but a lot simpler.
Then we create hardware to run that bytecode.
(No criticism intended to the author, I guess the goal is just to have fun).