[PATCH bpf-next] [tools/bpf] workaround an alu32 sub-register spilling issue

[PATCH bpf-next] [tools/bpf] workaround an alu32 sub-register spilling issue

[Yonghong Song]

Currently, with latest llvm trunk, selftest test_progs failed
obj file test_seg6_loop.o with the following error
in verifier:
  infinite loop detected at insn 76
The byte code sequence looks like below, and noted
that alu32 has been turned off by default for better
generated codes in general:
      48:       w3 = 100
      49:       *(u32 *)(r10 - 68) = r3
      ...
  ;             if (tlv.type == SR6_TLV_PADDING) {
      76:       if w3 == 5 goto -18 <LBB0_19>
      ...
      85:       r1 = *(u32 *)(r10 - 68)
  ;     for (int i = 0; i < 100; i++) {
      86:       w1 += -1
      87:       if w1 == 0 goto +5 <LBB0_20>
      88:       *(u32 *)(r10 - 68) = r1

The main reason for verification failure is due to
partial spills at r10 - 68 for induction variable "i".

Current verifier only handles spills with 8-byte values.
The above 4-byte value spill to stack is treated to
STACK_MISC and its content is not saved. For the above example,
    w3 = 100
      R3_w=inv100 fp-64_w=inv1086626730498
    *(u32 *)(r10 - 68) = r3
      R3_w=inv100 fp-64_w=inv1086626730498
    ...
    r1 = *(u32 *)(r10 - 68)
      R1_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
      fp-64=inv1086626730498

To resolve this issue, verifier needs to be extended to
track sub-registers in spilling, or llvm needs to enhanced
to prevent sub-register spilling in register allocation
phase. The former will increase verifier complexity and
the latter will need some llvm "hacking".

Let us workaround this issue by declaring the induction
variable as "long" type so spilling will happen at non
sub-register level. We can revisit this later if sub-register
spilling causes similar or other verification issues.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 tools/testing/selftests/bpf/progs/test_seg6_loop.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/bpf/progs/test_seg6_loop.c b/tools/testing/selftests/bpf/progs/test_seg6_loop.c
index c4d104428643..69880c1e7700 100644
--- a/tools/testing/selftests/bpf/progs/test_seg6_loop.c
+++ b/tools/testing/selftests/bpf/progs/test_seg6_loop.c
@@ -132,8 +132,10 @@ static __always_inline int is_valid_tlv_boundary(struct __sk_buff *skb,
 	*pad_off = 0;
 
 	// we can only go as far as ~10 TLVs due to the BPF max stack size
+	// workaround: define induction variable "i" as "long" instead
+	// of "int" to prevent alu32 sub-register spilling.
 	#pragma clang loop unroll(disable)
-	for (int i = 0; i < 100; i++) {
+	for (long i = 0; i < 100; i++) {
 		struct sr6_tlv_t tlv;
 
 		if (cur_off == *tlv_off)
-- 
2.17.1

Re: [PATCH bpf-next] [tools/bpf] workaround an alu32 sub-register spilling issue

[Andrii Nakryiko]

On Sun, Nov 17, 2019 at 1:41 PM Yonghong Song <yhs@fb.com> wrote:
>
> Currently, with latest llvm trunk, selftest test_progs failed
> obj file test_seg6_loop.o with the following error
> in verifier:
>   infinite loop detected at insn 76
> The byte code sequence looks like below, and noted
> that alu32 has been turned off by default for better
> generated codes in general:
>       48:       w3 = 100
>       49:       *(u32 *)(r10 - 68) = r3
>       ...
>   ;             if (tlv.type == SR6_TLV_PADDING) {
>       76:       if w3 == 5 goto -18 <LBB0_19>
>       ...
>       85:       r1 = *(u32 *)(r10 - 68)
>   ;     for (int i = 0; i < 100; i++) {
>       86:       w1 += -1
>       87:       if w1 == 0 goto +5 <LBB0_20>
>       88:       *(u32 *)(r10 - 68) = r1
>
> The main reason for verification failure is due to
> partial spills at r10 - 68 for induction variable "i".
>
> Current verifier only handles spills with 8-byte values.
> The above 4-byte value spill to stack is treated to
> STACK_MISC and its content is not saved. For the above example,
>     w3 = 100
>       R3_w=inv100 fp-64_w=inv1086626730498
>     *(u32 *)(r10 - 68) = r3
>       R3_w=inv100 fp-64_w=inv1086626730498
>     ...
>     r1 = *(u32 *)(r10 - 68)
>       R1_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>       fp-64=inv1086626730498
>
> To resolve this issue, verifier needs to be extended to
> track sub-registers in spilling, or llvm needs to enhanced
> to prevent sub-register spilling in register allocation
> phase. The former will increase verifier complexity and
> the latter will need some llvm "hacking".
>
> Let us workaround this issue by declaring the induction
> variable as "long" type so spilling will happen at non
> sub-register level. We can revisit this later if sub-register
> spilling causes similar or other verification issues.
>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---

Acked-by: Andrii Nakryiko <andriin@fb.com>

>  tools/testing/selftests/bpf/progs/test_seg6_loop.c | 4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
>
> diff --git a/tools/testing/selftests/bpf/progs/test_seg6_loop.c b/tools/testing/selftests/bpf/progs/test_seg6_loop.c
> index c4d104428643..69880c1e7700 100644
> --- a/tools/testing/selftests/bpf/progs/test_seg6_loop.c
> +++ b/tools/testing/selftests/bpf/progs/test_seg6_loop.c
> @@ -132,8 +132,10 @@ static __always_inline int is_valid_tlv_boundary(struct __sk_buff *skb,
>         *pad_off = 0;
>
>         // we can only go as far as ~10 TLVs due to the BPF max stack size
> +       // workaround: define induction variable "i" as "long" instead
> +       // of "int" to prevent alu32 sub-register spilling.
>         #pragma clang loop unroll(disable)
> -       for (int i = 0; i < 100; i++) {
> +       for (long i = 0; i < 100; i++) {

hmm, seems like our compiler settings for selftests are more lax: long
i should be defined outside the loop

>                 struct sr6_tlv_t tlv;
>
>                 if (cur_off == *tlv_off)
> --
> 2.17.1
>

Re: [PATCH bpf-next] [tools/bpf] workaround an alu32 sub-register spilling issue

[Yonghong Song]

On 11/18/19 9:21 AM, Andrii Nakryiko wrote:
> On Sun, Nov 17, 2019 at 1:41 PM Yonghong Song <yhs@fb.com> wrote:
>>
>> Currently, with latest llvm trunk, selftest test_progs failed
>> obj file test_seg6_loop.o with the following error
>> in verifier:
>>    infinite loop detected at insn 76
>> The byte code sequence looks like below, and noted
>> that alu32 has been turned off by default for better
>> generated codes in general:
>>        48:       w3 = 100
>>        49:       *(u32 *)(r10 - 68) = r3
>>        ...
>>    ;             if (tlv.type == SR6_TLV_PADDING) {
>>        76:       if w3 == 5 goto -18 <LBB0_19>
>>        ...
>>        85:       r1 = *(u32 *)(r10 - 68)
>>    ;     for (int i = 0; i < 100; i++) {
>>        86:       w1 += -1
>>        87:       if w1 == 0 goto +5 <LBB0_20>
>>        88:       *(u32 *)(r10 - 68) = r1
>>
>> The main reason for verification failure is due to
>> partial spills at r10 - 68 for induction variable "i".
>>
>> Current verifier only handles spills with 8-byte values.
>> The above 4-byte value spill to stack is treated to
>> STACK_MISC and its content is not saved. For the above example,
>>      w3 = 100
>>        R3_w=inv100 fp-64_w=inv1086626730498
>>      *(u32 *)(r10 - 68) = r3
>>        R3_w=inv100 fp-64_w=inv1086626730498
>>      ...
>>      r1 = *(u32 *)(r10 - 68)
>>        R1_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>>        fp-64=inv1086626730498
>>
>> To resolve this issue, verifier needs to be extended to
>> track sub-registers in spilling, or llvm needs to enhanced
>> to prevent sub-register spilling in register allocation
>> phase. The former will increase verifier complexity and
>> the latter will need some llvm "hacking".
>>
>> Let us workaround this issue by declaring the induction
>> variable as "long" type so spilling will happen at non
>> sub-register level. We can revisit this later if sub-register
>> spilling causes similar or other verification issues.
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
> 
> Acked-by: Andrii Nakryiko <andriin@fb.com>
> 
>>   tools/testing/selftests/bpf/progs/test_seg6_loop.c | 4 +++-
>>   1 file changed, 3 insertions(+), 1 deletion(-)
>>
>> diff --git a/tools/testing/selftests/bpf/progs/test_seg6_loop.c b/tools/testing/selftests/bpf/progs/test_seg6_loop.c
>> index c4d104428643..69880c1e7700 100644
>> --- a/tools/testing/selftests/bpf/progs/test_seg6_loop.c
>> +++ b/tools/testing/selftests/bpf/progs/test_seg6_loop.c
>> @@ -132,8 +132,10 @@ static __always_inline int is_valid_tlv_boundary(struct __sk_buff *skb,
>>          *pad_off = 0;
>>
>>          // we can only go as far as ~10 TLVs due to the BPF max stack size
>> +       // workaround: define induction variable "i" as "long" instead
>> +       // of "int" to prevent alu32 sub-register spilling.
>>          #pragma clang loop unroll(disable)
>> -       for (int i = 0; i < 100; i++) {
>> +       for (long i = 0; i < 100; i++) {
> 
> hmm, seems like our compiler settings for selftests are more lax: long
> i should be defined outside the loop

clang default C standard support is gnu c11
https://clang.llvm.org/compatibility.html

That is why it won't issue warning. The warning is only issued for 
anything before c99/gnu99, e.g., gnu89.


> 
>>                  struct sr6_tlv_t tlv;
>>
>>                  if (cur_off == *tlv_off)
>> --
>> 2.17.1
>>

Re: [PATCH bpf-next] [tools/bpf] workaround an alu32 sub-register spilling issue

[Daniel Borkmann]

On 11/17/19 10:40 PM, Yonghong Song wrote:
> Currently, with latest llvm trunk, selftest test_progs failed
> obj file test_seg6_loop.o with the following error
> in verifier:
>    infinite loop detected at insn 76
> The byte code sequence looks like below, and noted
> that alu32 has been turned off by default for better
> generated codes in general:
>        48:       w3 = 100
>        49:       *(u32 *)(r10 - 68) = r3
>        ...
>    ;             if (tlv.type == SR6_TLV_PADDING) {
>        76:       if w3 == 5 goto -18 <LBB0_19>
>        ...
>        85:       r1 = *(u32 *)(r10 - 68)
>    ;     for (int i = 0; i < 100; i++) {
>        86:       w1 += -1
>        87:       if w1 == 0 goto +5 <LBB0_20>
>        88:       *(u32 *)(r10 - 68) = r1
> 
> The main reason for verification failure is due to
> partial spills at r10 - 68 for induction variable "i".
> 
> Current verifier only handles spills with 8-byte values.
> The above 4-byte value spill to stack is treated to
> STACK_MISC and its content is not saved. For the above example,
>      w3 = 100
>        R3_w=inv100 fp-64_w=inv1086626730498
>      *(u32 *)(r10 - 68) = r3
>        R3_w=inv100 fp-64_w=inv1086626730498
>      ...
>      r1 = *(u32 *)(r10 - 68)
>        R1_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>        fp-64=inv1086626730498
> 
> To resolve this issue, verifier needs to be extended to
> track sub-registers in spilling, or llvm needs to enhanced
> to prevent sub-register spilling in register allocation
> phase. The former will increase verifier complexity and
> the latter will need some llvm "hacking".
> 
> Let us workaround this issue by declaring the induction
> variable as "long" type so spilling will happen at non
> sub-register level. We can revisit this later if sub-register
> spilling causes similar or other verification issues.
> 
> Signed-off-by: Yonghong Song <yhs@fb.com>

Applied, thanks!