Hacker News new | ask | show | jobs
by lucianbr 703 days ago
It's casually claiming to have solved the halting problem, at least within some limited but useful context. That should be impossible, and it turns out, it is.

I expect it can be solved within some limited contexts, but those contexts are not useful, at least not at the level of "generic kernel code".
2 comments
red_admiral 703 days ago
It solves the halting problem by not being Turing complete. I presume each eBPF runs in a context with bounded memory, requested up front, for one thing; it also disallows jumps unless you can prove the code still halts.
link
michaelt 703 days ago
eBPF started out as Berkeley Packet Filters. People wanted to be able to set up complex packet filters. Things like 'udp and src host 192.168.0.3 and udp[4:2]=0x0034 and udp[8:2]=0x0000 and udp[12]=0x01 and udp[18:2]=0x0001 and not src port 3956'

So BPF introduced a very limited bytecode, which is complex enough that it can express long filters with lots of and/or/brackets - but which is limited enough it's easy to check the program terminates and is crash-free. It's still quite limited - prior to ~2019, all loops had to be fully unrolled at compile time as the checker didn't support loops.

It turned out that, although limited, this worked pretty well for filtering packets - so later, when people wanted a way to filter all system calls they realised they could extend the battle-tested BPF system.

Nobody is claiming to have solved the halting problem.

link
lucianbr 703 days ago
Did you read the article? It says computers will not crash in the future due to updates. It literally says that in the very first line of the article.

> In the future, computers will not crash due to bad software updates, even those updates that involve kernel code. In the future, these updates will push eBPF code.

What you are claiming is completely different. A kind of "firewall" for syscalls. But updates to drivers and software must contain code and data. The author is not talking about updates to the firewall between drivers and the kernel, they talk about updating drivers themselves. It literally says "updates that involve kernel code". Will the kernel only consist of eBPF filtering bytecode? How could that possibly work?

link