Re: BPF64: proposal of platform-independent hardware-friendly backwards-compatible eBPF alternative

[Alexander Nasonov <alnsn%yandex.ru@localhost>]

Poul-Henning Kamp wrote:
> A) How powerful do you want the downloaded bytecode to be ?
...
> There are basically two possible answers to A.
> 
> Either the downloaded code is "real", which means it can include
> loops, function calls etc. or it is a "toy" which relies on
> Brinch-Hansen's "all arrows point to the right" argument to prove
> that it will always terminate.

BPF can be easily modified to have functions and calls but it will
increase worst case execution complexity to quadratic and the stack
growth will have to be watched closely:

 - always jump forward (within the current function),
 - always call backwards (outside of the current function).

Backward jumps (within the current function) can be implemented
with some kind of slowly closing door. For instance, in packet
filtering, the first backward jump disables access to the first
byte, the second backward jump disables access to the second byte,
etc.

In general, it will require a special counter but BPFJIT compiler
should be able to spot simple loops that process at least one
byte on each iteration and minimise runtime overhead.

> ...
> The answer to that is that you can write them in /any/ programming
> language you want, as long as the interpreter for the resulting
> (byte-)code an spot attempts to jump backwards, and refuse to
> do so, if so configured.

I guess it will work for a simple single-pass interpreter that
generates bytecode as it reads source code but anything more
complicated may reshuffle bytecode and some forward jumps may
become backward jumps etc.

> And that is why I say: If we're going to do this, let us do
> it with Lua:  It's already in our tree and it will do the
> job nicely.

Lua is a good choice, IMO but we likely need a subset of Lua (e.g.
no metatables, no C or paused GC with a periodic lua_State rotations
to collect garbage).

Alex