Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

From the title I was sure this was going to be about the branch forward only pattern used in the Gripen, that John Carmack has briefly written about. In that pattern, there's a top-level loop, but other than that, no looping constructs or other backward-branches are permitted anywhere in the codebase.

* http://lambda-the-ultimate.org/node/5362

* https://news.ycombinator.com/item?id=22192656



A popular example given for this is often pcap/tcpdump filters— for perf reasons they have to be executed by the kernel, but because they're an untrusted user "program" being run in kernel space, they can only ever jump forward, ensuring an upper bound on their runtime.

See: https://en.wikipedia.org/wiki/Berkeley_Packet_Filter

That said, it looks like as of Linux 5.3+, there are certain bounded loops that are permissible: https://lwn.net/Articles/794934/


This sounds very interesting.

What exactly would be a backward-branch? Are function calls allowed (I feel like they have to be)?

Are there any code snippets for this style?


According to Carmack subroutine calls are also disallowed. See https://web.archive.org/web/20210226152857/http://lambda-the...

This sounds very much like programming a traditional Programmable Logic Controller (PLC).


Seems curious to ban functions. If you ban function-pointers then you can statically ensure there's no recursion (including mutual recursion). At that point, all function calls are in principle able to be inlined, so any backtracking is merely a compiler-level implementation detail.

iirc, OpenCL C does something similar, banning function pointers and recursion (including mutual recursion), although it does so for different reasons than this pattern.


Well, a flight control computer is not too different from a PLC.


It seems to me that this would be best ensured by writing the codebase in a custom language the compiler of which would put a loop around the whole code but the language itself wouldn't have loops. This could be yet another instance of "patterns mean 'I've run out of language'".




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: