Re: Self-XORing BPF registers is undefined behavior

On Mon, Jun 1, 2020 at 11:55 AM Edward Cree [off-list ref] wrote:

If it's an alias of BPF_XOR r,r, then the interpreter will surely still
 interpret it with the XOR code.  Unless you make the interpreter
 special-case this, in which case you've added an extra branch to every
 XOR the interpreter handles :(

You are right, the interpreter can be probably fixed in a different
way that doesn't introduce extra branches.

quoted

Given the increased popularity of Clang in the kernel these days, I
don't think it's a good idea for a single compiler to further diverge
from the standard.The standard in question isn't C89, but "--std=gnu89", which is

 whatever GCC says it is :grin:
So if GCC declares that some class of optimisations are not legal under
 --std=gnu89, then they're not legal and Clang has to adapt to that.

Hm, I never thought of such an approach to standards. This sounds like
a legitimate solution, which will however result in:
 - GCC developers saying "no, we won't do this", or
 - Clang developers saying "no, we won't do this"
, unless we present them with good reasons to do so.

Because the use-case is quite narrow, and prohibiting this
optimization may break other optimizations (at least in Clang), I
won't expect anyone spending time on making Clang compliant with
--std=gnu89 in this particular case.

quoted

I wouldn't call this particular use case "extremely annoying".

To be clear, what's "annoying" is the double-bind we're in as a result
 of trying to optimise the prologue for both JITs (whose semantics are
 whatever we define eBPF to be) and the interpreter (which has to be
 implemented with reasonable efficiency as C code).

quoted

If I understand correctly, these two instructions are only executed
once per program.
Are they really expected to impact performance that much?

If you have a very short program that's bound to a very frequent event,
 then they might.  But I don't have, and haven't seen, any numbers...

So we're back to the question how much people care about the
interpreter performance.

quoted

I don't have evidence that such a transformation is currently possible
for the BPF code in question, but all the building blocks are there,
so it's probably just a matter of time.

I'm not so sure.  Consider the following sequence of BPF instructions:
    xor r0, r0
    ld r0, 42
    xor r0, r0
    exit
I hope you'll agree that at entry to the second XOR, the value of r0 is
 not indeterminate.  So any optimisation the compiler does for the first
 XOR ("oh, we don't need to fill the existing regs[] values, we can just
 use whatever's already in whichever register we allocate") will need to
 be predicated on something that makes it only happen for the first XOR.
But the place it's doing this optimisation is in the interpreter, which
 is a big fetch-execute loop.  I don't think even Clang is smart enough
 to figure out "BPF programs always start with a prologue, I'll stick in
 something that knows which prologue the prog uses and branches to a
 statically compiled, optimised version thereof".
(If Clang *is* that smart, then it's too clever by half...)

I don't think Clang does this at the moment, but I can certainly
imagine it unrolling the first two iterations of the interpretation
loop (since the prologue instructions are known at compile time) and
replacing them with explicit XOR instructions.

I however suggest we get to the practical question of how to deal with
this issue in the long run.
Currently these error reports prevent us from testing BPF with syzbot,
so we're using https://github.com/google/kmsan/commit/69b987d53462a7f3b5a41c62eb731340b53165f8
to work around them.
This seems to be the easiest fix that doesn't affect JIT performance
and removes the UB.

Once KMSAN makes it to the mainline, we'll need to either come up with
a similar fix, or disable fuzzing BPF, which isn't what we want.

--
Alexander Potapenko
Software Engineer

Google Germany GmbH
Erika-Mann-Straße, 33
80636 München

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg