BPF: A New Type of Software • Hacker News Board

Re: BPF: A New Type of Software

#71

Post by dathinab » Tue, Dec 03, 2019, 2:30 PM UTC

kbumsik wrote: post #31

andbberger wrote: post #30

Earlier quoted context omitted.

How is that possible?? If true, that would imply BPF programs are not Turing complete.

You are right, eBPF is non-Turing complete. To be precise I heard that the kernel eBPF verifier ensures the flow of a BPF program is a kind of a DAG (no cycles = no loops). So eBPF VM is definitely not a general-purpose machine.

Actually they now allow bounded loops (such which you could theoretically unroll complete). It's mentioned in the talk, too. There is also a limit on the number of instructions a program can have I wonder if bounded loops multiply the "numbe of instructions" per iteration with the upper bound of t the number of persons for this?

Re: BPF: A New Type of Software

#72

Post by manyworlds » Tue, Dec 03, 2019, 2:33 PM UTC

This is less about BPF vs native code, and more about the process model vs the event based model of application programming.

Event based handling is inherently more efficient because it runs in the context of the caller, instead of requiring its own context like in process-based applications.

This is the main reason why file system code in the kernel is more efficient than file system servers running in a different process, eg via FUSE. No context switching

Re: BPF: A New Type of Software

#73

Post by manyworlds » Tue, Dec 03, 2019, 2:37 PM UTC

StreamBright wrote: post #68

baybal2 wrote: post #15

Question from me, why reinvent the bicycle and not just write proper kernel modules in C?

I guess you are missing the point by 100000 miles. The whole point of BPF is the avoid writing a C kernel module and pull in the entire problem domain of C programs running in Ring0. this was called out explicitly in the video.

He’s not off the mark completely, you can maintain production safety by using a BPF->kernel module compiler. Unnecessary to have an entire JIT infrastructure in the kernel just to get the safety benefits of BPF.

Re: BPF: A New Type of Software

#74

Post by rhencke » Tue, Dec 03, 2019, 2:45 PM UTC

sho_hn wrote: post #61

ClumsyPilot wrote: post #48

This looks very similar to webassembly work going on right now, both use a secure VM, and both run in kernel space. Would webassembly be a more general purpose way of accomplishing something like this?

webassembly "runs in kernel space"?

Yes, though it's early days yet. See:

https://github.com/wasmerio/kernel-wasm

Re: BPF: A New Type of Software

#75

Post by justusthane » Tue, Dec 03, 2019, 2:50 PM UTC

ignoramous wrote: post #24

rusk wrote: post #19

Earlier quoted context omitted.

Real-time, low latency, network-based applications. At the pace of network events, CPU is still very fast by perhaps at least order of magnitude. However, latency introduced by system calls is significant. This allows you to run certain classes of application in kernel space with these overheads largely mitigated. Principally it's monitoring and "observability" applications, but apparently it's much more flexible now…

> Principally it's monitoring and "observability" applications, but apparently it's much more flexible now than it has been historically ... Yep: Here's a bredangregg presentation on the topic: https://www.youtube-nocookie.com/embed/7pmXdG8-7WU

That's exactly what the linked article is.

Re: BPF: A New Type of Software

#76

Post by cfors » Tue, Dec 03, 2019, 3:03 PM UTC

andbberger wrote: post #30

kbumsik wrote: post #22

Earlier quoted context omitted.

> "if this exceeds some limits or bogs down system for more than X milliseconds, disable and give error". AFAIK indefinite loops in a BPF are not allowed: The kernel eBPF verifier will reject to load such programs. So the execution time of BPF programs will not be variable time and will be predictive. I'm not sure if users need to care about the cases of long execution times when no loops are allowed.

How is that possible?? If true, that would imply BPF programs are not Turing complete.

Brendan Gregg talks about it in the talk in the link at 17:50.

Here is a short transcription (not verbatim):

> People have asked if BPF is Turing Complete. Is is possible to have a BPF program that can run BPF programs? We have had some serious discussions, as are we there yet. And the answer is no. The answer is no because the verifier rejects unbounded loops and so that there is some things that are not possible. There are bounded loops in BPF now.

Re: BPF: A New Type of Software

#77

Post by smartmic » Tue, Dec 03, 2019, 3:04 PM UTC

I do not know much about kernels and OS architecture. But I am wondering how this relates to the idea of GNU Hurd. Wasn't its concept also about microkernel-based design?

Re: BPF: A New Type of Software

#78

Post by nicoburns » Tue, Dec 03, 2019, 3:08 PM UTC

manyworlds wrote: post #69

nicoburns wrote: post #57

Earlier quoted context omitted.

> One is suitable for embedding into a kernel, the other isn't. I'd be very surprised if the linux kernel doesn't eventually get web assembly support.

Doubtful. Webassembly is Turing complete, BPF isn’t. Running untrusted unbounded code in the kernel is not smart. BPF was invented with kernel constraints in mind, webassembly was invented with browser constraints in mind. Completely different use cases

> Running untrusted unbounded code in the kernel is not smart.

Well currently we run code (e.g. drivers) as trusted full-permission code. Surely, web-assembly would be better than this from a security perspective.

Re: BPF: A New Type of Software

#79

Post by hackworks » Tue, Dec 03, 2019, 3:09 PM UTC

eBPF can be viewed as a mechanism to safely run user code in kernel since it uses a DSL and a compiler before the byte code is executed in kernel. This opens up doors for running performance critical functionality in kernel without having to bundle it with the kernel or very tightly coupled with the kernel version.

Optimizing FUSE is an example: https://extfuse.github.io/

I expect custom security auditing software, reverse proxies, firewalls with rule engines implemented in eBPF in the coming future. This will avoid having to copy dates across kernel and user boundary and the switching overheads.

Re: BPF: A New Type of Software

#80

Post by ajor » Tue, Dec 03, 2019, 3:17 PM UTC

GrayShade wrote: post #3

Brendan has a lot of great content that gets posted here regularly: http://www.brendangregg.com/ (I'm still trying find the time to get through it though). There's also https://github.com/iovisor/bcc#tools as an easy way to get started using BPF.

I'd also recommend looking at bpftrace[1], which provides a simple DSL specifically for writing BPF programs and attaching them to events. (Disclaimer: I started the project)

[1] https://github.com/iovisor/bpftrace/blob/master/docs/tutoria...