Skip to contentSkip to conversation

R11 is invalid with LLVM 12 and later

DISCUSSION Paul Chaignon 2 participants 5 messages Aug 9, 2021 – Aug 12, 2021 BPF

lore
Share & tools
lore
#0 lore raw

Hello,

While trying to use LLVM 12.0.0 in Cilium, we've noticed that it can generate invalid BPF bytecode:

    $ clang --version
    Ubuntu clang version 12.0.0-++20210409092622+fa0971b87fb2-1~exp1~20210409193326.73
    Target: x86_64-pc-linux-gnu
    Thread model: posix
    InstalledDir: /usr/bin
    $ make -C bpf -j6 KERNEL=419
    $ llvm-objdump -D -section=2/20 bpf/bpf_lxc.o | grep -i r11
         171:   7b ba 18 ff 00 00 00 00 *(u64 *)(r10 - 232) = r11
         436:   79 ab 18 ff 00 00 00 00 r11 = *(u64 *)(r10 - 232)
         484:   bf 8b 00 00 00 00 00 00 r11 = r8

That bytecode is of course rejected by the verifier:

171: (7b) *(u64 *)(r10 -232) = r11
R11 is invalid

LLVM 12.0.1 and latest LLVM sources (e.g., commit 2b4a1d4b from today) have the same issue. We've bisected it to LLVM commit 552c6c23 ("PR44406: Follow behavior of array bound constant folding in more recent versions of GCC."), but that could just be the commit where the regression was exposed in Cilium's case.

--
Paul

#1 lore raw
Quoted 16 lines · Paul Chaignon

Hello,

While trying to use LLVM 12.0.0 in Cilium, we've noticed that it can generate invalid BPF bytecode:

     $ clang --version
     Ubuntu clang version 12.0.0-++20210409092622+fa0971b87fb2-1~exp1~20210409193326.73
     Target: x86_64-pc-linux-gnu
     Thread model: posix
     InstalledDir: /usr/bin
     $ make -C bpf -j6 KERNEL=419
     $ llvm-objdump -D -section=2/20 bpf/bpf_lxc.o | grep -i r11
          171:   7b ba 18 ff 00 00 00 00 *(u64 *)(r10 - 232) = r11
          436:   79 ab 18 ff 00 00 00 00 r11 = *(u64 *)(r10 - 232)
          484:   bf 8b 00 00 00 00 00 00 r11 = r8
Quoted 4 lines

That bytecode is of course rejected by the verifier:

171: (7b) *(u64 *)(r10 -232) = r11
R11 is invalid

Thanks for reporting. I can reproduce the problem and will take a look soon.

Quoted 10 lines

LLVM 12.0.1 and latest LLVM sources (e.g., commit 2b4a1d4b from today) have the same issue. We've bisected it to LLVM commit 552c6c23 ("PR44406: Follow behavior of array bound constant folding in more recent versions of GCC."), but that could just be the commit where the regression was exposed in Cilium's case.

--
Paul

#2 lore raw
Quoted 19 lines · Yonghong Song
Quoted 16 lines · Paul Chaignon

Hello,

While trying to use LLVM 12.0.0 in Cilium, we've noticed that it can generate invalid BPF bytecode:

     $ clang --version
     Ubuntu clang version 12.0.0-++20210409092622+fa0971b87fb2-1~exp1~20210409193326.73
     Target: x86_64-pc-linux-gnu
     Thread model: posix
     InstalledDir: /usr/bin
     $ make -C bpf -j6 KERNEL=419
     $ llvm-objdump -D -section=2/20 bpf/bpf_lxc.o | grep -i r11
          171:   7b ba 18 ff 00 00 00 00 *(u64 *)(r10 - 232) = r11
          436:   79 ab 18 ff 00 00 00 00 r11 = *(u64 *)(r10 - 232)
          484:   bf 8b 00 00 00 00 00 00 r11 = r8
Quoted 13 lines
Quoted 4 lines

That bytecode is of course rejected by the verifier:

     171: (7b) *(u64 *)(r10 -232) = r11
     R11 is invalid

Thanks for reporting. I can reproduce the problem and will take a look soon.

Quoted 6 lines

LLVM 12.0.1 and latest LLVM sources (e.g., commit 2b4a1d4b from today) have the same issue. We've bisected it to LLVM commit 552c6c23 ("PR44406: Follow behavior of array bound constant folding in more recent versions of GCC."), but that could just be the commit where the regression was exposed in Cilium's case.

The above commit is indeed responsible. With the above commit, the variable length array compile time evaluation becomes conservative. For cilium function dsr_reply_icmp4 in nodeport.h
const __u32 l3_max = MAX_IPOPTLEN + sizeof(*ip4) + orig_dgram; __u8 tmp[l3_max];

I didn't try to compile with/without the above commit, the following is the thesis.

Before the above commit, llvm evaluates the expression
MAX_IPOPTLEN + sizeof(*ip4) + orig_dgram
and concludes that l3_max is a constant so tmp can be allocated on stack with fixed size.

With the above commit, llvm becomes conservative to evaluate the expression at compile time. So above l3_max becomes a non-constant variable and tmp becomes a variable length array. Since it becomes a variable length array, the hidden stack pointer "r11" is used and this caused a problem in verifier.

To workaround the issue, simply define "tmp" with
__u8 tmp[68];
But that is not for from user experience. I guess we can do:
1. for BPF target, let us still do aggressive constant folding in compile time in clang, basically restores to pre-commit-552c6c23 level for BPF programs.
2. provide an error message if r11 is generated in final code.

Will come back to this thread once I got concrete patches. Thanks!

Quoted 4 lines
Quoted 4 lines
Signature · 2 lines
-- 
Paul
#3 lore raw
Quoted 2 lines · Yonghong Song
Quoted 1 line · Yonghong Song

On 8/9/21 8:12 AM, Paul Chaignon wrote:

[...]

Quoted 27 lines
Quoted 5 lines
Quoted 5 lines

LLVM 12.0.1 and latest LLVM sources (e.g., commit 2b4a1d4b from today) have the same issue. We've bisected it to LLVM commit 552c6c23 ("PR44406: Follow behavior of array bound constant folding in more recent versions of GCC."), but that could just be the commit where the regression was exposed in Cilium's case.

The above commit is indeed responsible. With the above commit, the variable length array compile time evaluation becomes conservative. For cilium function dsr_reply_icmp4 in nodeport.h
const __u32 l3_max = MAX_IPOPTLEN + sizeof(*ip4) + orig_dgram; __u8 tmp[l3_max];

I didn't try to compile with/without the above commit, the following is the thesis.

Before the above commit, llvm evaluates the expression
MAX_IPOPTLEN + sizeof(*ip4) + orig_dgram
and concludes that l3_max is a constant so tmp can be allocated on stack with fixed size.

With the above commit, llvm becomes conservative to evaluate the expression at compile time. So above l3_max becomes a non-constant variable and tmp becomes a variable length array. Since it becomes a variable length array, the hidden stack pointer "r11" is used and this caused a problem in verifier.

Quoted 2 lines

To workaround the issue, simply define "tmp" with
__u8 tmp[68];

Thanks Yonghong! I've tested this workaround on the Cilium codebase with all of our tested configurations. I'm not seeing this R11 issue in this BPF program or anywhere else anymore.

Quoted 7 lines

But that is not for from user experience. I guess we can do:
1. for BPF target, let us still do aggressive constant folding in compile time in clang, basically restores to pre-commit-552c6c23 level for BPF programs.
2. provide an error message if r11 is generated in final code.

Will come back to this thread once I got concrete patches. Thanks!

I'm happy to run any patch you have through the Cilium CI if that helps.

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Signature · 2 lines
-- 
Paul
#4 lore raw
Quoted 33 lines · Paul Chaignon
Quoted 2 lines · Yonghong Song
Quoted 1 line · Yonghong Song

On 8/9/21 8:12 AM, Paul Chaignon wrote:

[...]

Quoted 27 lines
Quoted 5 lines
Quoted 5 lines

LLVM 12.0.1 and latest LLVM sources (e.g., commit 2b4a1d4b from today) have the same issue. We've bisected it to LLVM commit 552c6c23 ("PR44406: Follow behavior of array bound constant folding in more recent versions of GCC."), but that could just be the commit where the regression was exposed in Cilium's case.

The above commit is indeed responsible. With the above commit, the variable length array compile time evaluation becomes conservative. For cilium function dsr_reply_icmp4 in nodeport.h

   const __u32 l3_max = MAX_IPOPTLEN + sizeof(*ip4) + orig_dgram;
   __u8 tmp[l3_max];

I didn't try to compile with/without the above commit, the following is the thesis.

Before the above commit, llvm evaluates the expression
MAX_IPOPTLEN + sizeof(*ip4) + orig_dgram
and concludes that l3_max is a constant so tmp can be allocated on stack with fixed size.

With the above commit, llvm becomes conservative to evaluate the expression at compile time. So above l3_max becomes a non-constant variable and tmp becomes a variable length array. Since it becomes a variable length array, the hidden stack pointer "r11" is used and this caused a problem in verifier.

Quoted 6 lines
Quoted 2 lines

To workaround the issue, simply define "tmp" with

    __u8 tmp[68];

Thanks Yonghong! I've tested this workaround on the Cilium codebase with all of our tested configurations. I'm not seeing this R11 issue in this BPF program or anywhere else anymore.

That is great!

Quoted 10 lines
Quoted 8 lines

But that is not for from user experience. I guess we can do:
1. for BPF target, let us still do aggressive constant folding in compile time in clang, basically restores to pre-commit-552c6c23 level for BPF programs.
2. provide an error message if r11 is generated in final code.

Will come back to this thread once I got concrete patches. Thanks!

I'm happy to run any patch you have through the Cilium CI if that helps.

Thanks for testing. Could you help try whether the patch https://reviews.llvm.org/D107882 can fix the problem or not? You might need to add -Wno-gnu-folding-constant to silence
array size constant folding warnings.
If this indeed fix the cilium, could you add a comment
to the above llvm patch?

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Signature · 2 lines
-- 
Paul