News for hackers. Stuff that matters.
Re:BPF: A New Type of Software by throwaway894345 on Tuesday December 03, 2019 @01:16PM (#21694951)
According to https://news.ycombinator.com/item?id=18496054, these programs have to halt? How does this system guarantee that the programs halt? Does this mean eBPF is not Turing complete?
Re:BPF: A New Type of Software by nwallin on Tuesday December 03, 2019 @01:49PM (#21695298)
The language itself is Turing complete, but the kernel will refuse to run a program that it cannot prove will halt.

There are three categories of programs; programs you can trivially prove will halt, programs you can trivially prove won't halt, and programs where it's difficult or impossible to prove whether or not will halt. The third category is what we call the halting problem. Only the first category will be run by the kernel.

The nitty gritty is that the only jumps which are allowed to go backwards are the end of a loop with a fixed number of iterations. All other jumps must jump forward.

This sounds like it's really limiting, but in practice there's not a whole lot of useful stuff you're unable to do.

Re:BPF: A New Type of Software by fireant on Wednesday December 04, 2019 @03:30PM (#21706577)
Could you create an unbounded loop by scheduling another BPF execution on the end of each program? I imagine something like a WASM runtime that would be split into multiple BPF programs on loops. Which would practically achieve https://github.com/nebulet/nebulet, right?
Re:BPF: A New Type of Software by cube2222 on Friday December 06, 2019 @02:39PM (#21725232)
This does actually mean that eBPF is not Turing complete, in that it can't simulate a Turing machine.

With a fixed number iterations (which also means fixed amount of memory) it's really just a finite state automata.

Re:BPF: A New Type of Software by ttctciyf on Tuesday December 03, 2019 @01:37PM (#21695166)
From the accompanying video (17:11)[1] it's not Turing complete "because the verifier rejects unbounded loops and so there is some things that are not possible. We do have bounded loops in BPF now."

1: https://youtu.be/7pmXdG8-7WU?t=1031

Re:BPF: A New Type of Software by sansnomme on Tuesday December 03, 2019 @11:59PM (#21699721)
Commonly known as total functional programming.

https://en.m.wikipedia.org/wiki/Total_functional_programming

Re:BPF: A New Type of Software by 4ad on Tuesday December 03, 2019 @01:18PM (#21694971)
Indeed, eBPF is not turing complete.
Re:BPF: A New Type of Software by rstuart4133 on Tuesday December 03, 2019 @07:12PM (#21698334)
It's the definition of Turning complete that's the problem. A Turning complete machine must be able to process countably infinite inputs. The halting problem arises from same thing. There is no halting problem if we restrict ourselves to programs that will stop in a bounded time (obviously).

In practice that means a true Turning machine can compute things that aren't actually computable in our Universe, or at least not by the bits of the Universe we understand well. I doubt any engineer will think that "this architecture can't in theory compute things not computable in this Universe" is a strong argument against it.