3 ms·

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 pa

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 http://lambda-the-ultimate.org/node/5362 * https://news.ycombinator.com/item?id=22192656 https://news.ycombinator.com/item?id=22192656

jhgb 5y ago
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'".
cloogshicer 5y ago
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?
- kwhitefoot 5y ago
  According to Carmack subroutine calls are also disallowed. See https://web.archive.org/web/20210226152857/http://lambda-the-ultimate.org/node/5362 https://web.archive.org/web/20210226152857/http://lambda-the... This sounds very much like programming a traditional Programmable Logic Controller (PLC).
  - aaaaaaaaaaab 5y ago
    Well, a flight control computer is not too different from a PLC.
  - MaxBarraclough 5y ago
    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.
mikepurvis 5y ago
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 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/ https://lwn.net/Articles/794934/

jhgb 5y ago

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'".

cloogshicer 5y ago

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?

kwhitefoot 5y ago
According to Carmack subroutine calls are also disallowed. See https://web.archive.org/web/20210226152857/http://lambda-the-ultimate.org/node/5362 https://web.archive.org/web/20210226152857/http://lambda-the... This sounds very much like programming a traditional Programmable Logic Controller (PLC).
- aaaaaaaaaaab 5y ago
  Well, a flight control computer is not too different from a PLC.
- MaxBarraclough 5y ago
  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.

mikepurvis 5y ago

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 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/ https://lwn.net/Articles/794934/