From: Yonghong Song <yhs@fb.com>
To: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: bpf <bpf@vger.kernel.org>, Alexei Starovoitov <ast@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Kernel Team <kernel-team@fb.com>,
John Fastabend <john.fastabend@gmail.com>
Subject: Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor
Date: Tue, 1 Sep 2020 19:17:56 -0700 [thread overview]
Message-ID: <465da51a-793e-5ea0-85dc-56ab4f36ae34@fb.com> (raw)
In-Reply-To: <CAEf4Bzb89dz_Sjy14LjQSDWrQ=TpSHAfgf=_Sa=bWUKGqJHCgQ@mail.gmail.com>
On 9/1/20 1:07 PM, Andrii Nakryiko wrote:
> On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote:
>>
>> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12.
>> Compared to llvm 10, llvm 11 and 12 generates xor instruction which
>
> Does this mean that some perfectly working BPF programs will now fail
> to verify on older kernels, if compiled with llvm 11 or llvm 12? If
Right.
> yes, is there something that one can do to prevent Clang from using
> xor in such situations?
The xor is generated by the combination of llvm simplifyCFG and
instrCombine phase.
The following is a hack to prevent compiler from generating xor's.
diff --git a/tools/testing/selftests/bpf/progs/test_sk_assign.c
b/tools/testing/selftests/bpf/progs/test_sk_assi
gn.c
index 1ecd987005d2..b10ce8e9437e 100644
--- a/tools/testing/selftests/bpf/progs/test_sk_assign.c
+++ b/tools/testing/selftests/bpf/progs/test_sk_assign.c
@@ -97,15 +97,28 @@ handle_udp(struct __sk_buff *skb, struct
bpf_sock_tuple *tuple, bool ipv4)
__be16 dport;
int ret;
- tuple_len = ipv4 ? sizeof(tuple->ipv4) : sizeof(tuple->ipv6);
- if ((void *)tuple + tuple_len > (void *)(long)skb->data_end)
- return TC_ACT_SHOT;
+ if (ipv4) {
+ tuple_len = sizeof(tuple->ipv4);
+ if ((void *)tuple + tuple_len > (void *)(long)skb->data_end)
+ return TC_ACT_SHOT;
+
+ sk = bpf_sk_lookup_udp(skb, tuple, tuple_len,
BPF_F_CURRENT_NETNS, 0);
+ if (sk)
+ goto assign;
- sk = bpf_sk_lookup_udp(skb, tuple, tuple_len,
BPF_F_CURRENT_NETNS, 0);
- if (sk)
- goto assign;
+ dport = tuple->ipv4.dport;
+ } else {
+ tuple_len = sizeof(tuple->ipv6);
+ if ((void *)tuple + tuple_len > (void *)(long)skb->data_end)
+ return TC_ACT_SHOT;
+
+ sk = bpf_sk_lookup_udp(skb, tuple, tuple_len,
BPF_F_CURRENT_NETNS, 0);
+ if (sk)
+ goto assign;
+
+ dport = tuple->ipv6.dport;
+ }
- dport = ipv4 ? tuple->ipv4.dport : tuple->ipv6.dport;
if (dport != bpf_htons(4321))
return TC_ACT_OK;
@@ -129,18 +142,34 @@ handle_tcp(struct __sk_buff *skb, struct
bpf_sock_tuple *tuple, bool ipv4)
__be16 dport;
int ret;
- tuple_len = ipv4 ? sizeof(tuple->ipv4) : sizeof(tuple->ipv6);
- if ((void *)tuple + tuple_len > (void *)(long)skb->data_end)
- return TC_ACT_SHOT;
+ if (ipv4) {
+ tuple_len = sizeof(tuple->ipv4);
+ if ((void *)tuple + tuple_len > (void *)(long)skb->data_end)
+ return TC_ACT_SHOT;
- sk = bpf_skc_lookup_tcp(skb, tuple, tuple_len,
BPF_F_CURRENT_NETNS, 0);
- if (sk) {
- if (sk->state != BPF_TCP_LISTEN)
- goto assign;
- bpf_sk_release(sk);
+ sk = bpf_skc_lookup_tcp(skb, tuple, tuple_len,
BPF_F_CURRENT_NETNS, 0);
+ if (sk) {
+ if (sk->state != BPF_TCP_LISTEN)
+ goto assign;
+ bpf_sk_release(sk);
+ }
+
+ dport = tuple->ipv4.dport;
+ } else {
+ tuple_len = sizeof(tuple->ipv6);
+ if ((void *)tuple + tuple_len > (void *)(long)skb->data_end)
+ return TC_ACT_SHOT;
+
+ sk = bpf_skc_lookup_tcp(skb, tuple, tuple_len,
BPF_F_CURRENT_NETNS, 0);
+ if (sk) {
+ if (sk->state != BPF_TCP_LISTEN)
+ goto assign;
+ bpf_sk_release(sk);
+ }
+
+ dport = tuple->ipv6.dport;
}
- dport = ipv4 ? tuple->ipv4.dport : tuple->ipv6.dport;
if (dport != bpf_htons(4321))
return TC_ACT_OK;
The fundamental idea is the following. If you have code like
if (cond) { BLOCK1; } else { BLOCK2; }
BLOCK3;
if (cond) { BLOCK4; } else { BLOCK5; }
change the source code to
if (cond) { BLOCK1; BLOCK3; BLOCK4; }
else { BLOCK2; BLOCK3; BLOCK4; }
If the condition is used in two different places, the compiler
might do some transformation for control flow and later on
instr simplification decides to use xor in certain cases.
The new code has some code duplication. Not sure whether
we should refactor the code or just add some note to selftests
README.rst to describe this particular failure.
>
>> is not handled properly in verifier. The following illustrates the
>> problem:
>>
>> 16: (b4) w5 = 0
>> 17: ... R5_w=inv0 ...
>> ...
>> 132: (a4) w5 ^= 1
>> 133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
>> ...
>> 37: (bc) w8 = w5
>> 38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>> R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
>> ...
>> 41: (bc) w3 = w8
>> 42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
>> 45: (56) if w3 != 0x0 goto pc+1
>> ... R3_w=inv0 ...
>> 46: (b7) r1 = 34
>> 47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0)
>> 47: (0f) r7 += r1
>> 48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
>> 48: (b4) w9 = 0
>> 49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
>> 49: (69) r1 = *(u16 *)(r7 +0)
>> invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38)
>> R7 offset is outside of the packet
>>
>> At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative
>> value of w5. At insn 45, in reality the condition should be always false.
>> But due to conservative value for w3, the verifier evaluates it could be
>> true and this later leads to verifier failure complaining potential
>> packet out-of-bound access.
>>
>> This patch implemented proper XOR support in verifier.
>> In the above example, we have:
>> 132: R5=invP0
>> 132: (a4) w5 ^= 1
>> 133: R5_w=invP1
>> ...
>> 37: (bc) w8 = w5
>> ...
>> 41: (bc) w3 = w8
>> 42: R3_w=invP1
>> ...
>> 45: (56) if w3 != 0x0 goto pc+1
>> 47: R3_w=invP1
>> ...
>> processed 353 insns ...
>> and the verifier can verify the program successfully.
>>
>> Cc: John Fastabend <john.fastabend@gmail.com>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
>> kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
>> 1 file changed, 66 insertions(+)
>>
>
> [...]
>
next prev parent reply other threads:[~2020-09-02 2:18 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-08-25 6:46 [PATCH bpf-next 0/2] fix a verifier failure with xor Yonghong Song
2020-08-25 6:46 ` [PATCH bpf-next 1/2] bpf: " Yonghong Song
2020-08-26 1:58 ` Alexei Starovoitov
2020-08-26 3:36 ` Yonghong Song
2020-08-26 22:06 ` John Fastabend
2020-08-27 5:12 ` Alexei Starovoitov
2020-08-27 18:43 ` John Fastabend
2020-09-01 20:07 ` Andrii Nakryiko
2020-09-02 2:17 ` Yonghong Song [this message]
2020-09-02 5:27 ` John Fastabend
2020-09-02 5:43 ` Yonghong Song
2020-09-04 5:29 ` John Fastabend
2020-09-02 9:33 ` Toke Høiland-Jørgensen
2020-09-02 14:21 ` Alexei Starovoitov
2020-09-02 15:01 ` Toke Høiland-Jørgensen
2020-09-02 21:40 ` Alexei Starovoitov
2020-08-25 6:46 ` [PATCH bpf-next 2/2] selftests/bpf: add verifier tests for xor operation Yonghong Song
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=465da51a-793e-5ea0-85dc-56ab4f36ae34@fb.com \
--to=yhs@fb.com \
--cc=andrii.nakryiko@gmail.com \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=john.fastabend@gmail.com \
--cc=kernel-team@fb.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox