Re: [RFC] bpf: verifier check for dead branch

[Yonghong Song <yhs@fb.com>]

On 8/10/20 6:54 AM, Jiri Olsa wrote:
> On Sun, Aug 09, 2020 at 06:21:01PM -0700, Yonghong Song wrote:
>>
>>
>> On 8/7/20 10:30 AM, Jiri Olsa wrote:
>>> hi,
>>> we have a customer facing some odd verifier fails on following
>>> sk_skb program:
>>>
>>>      0. r2 = *(u32 *)(r1 + data_end)
>>>      1. r4 = *(u32 *)(r1 + data)
>>>      2. r3 = r4
>>>      3. r3 += 42
>>>      4. r1 = 0
>>>      5. if r3 > r2 goto 8
>>>      6. r4 += 14
>>>      7. r1 = r4
>>>      8. if r3 > r2 goto 10
>>>      9. r2 = *(u8 *)(r1 + 9)
>>>     10. r0 = 0
>>>     11. exit
>>>
>>> The code checks if the skb data is big enough (5) and if it is,
>>> it prepares pointer in r1 (7), then there's again size check (8)
>>> and finally data load from r1 (9).
>>>
>>> It's and odd code, but apparently this is something that can
>>> get produced by clang.
>>
>> Could you provide a test case where clang generates the above code?
>> I would like to see whether clang can do a better job to avoid
>> such codes.
> 
> I get that code genrated by using recent enough upstream clang
> on the attached source.

Thanks for the test case. I can reproduce the issue. The following
is why this happens in llvm.
the pseudo IR code looks like
    data = skb->data
    data_end = skb->data_end
    comp = data + 42 > data_end
    ip = select "comp" nullptr "data + some offset"
          <=== select return one of nullptr or "data + some offset" 
based on "comp"
    if comp   // original skb_shorter condition
       ....
    ...
       = ip

In llvm, bpf backend "select" actually inlined "comp" to generate proper
control flow. Therefore, comp is computed twice like below
    data = skb->data
    data_end = skb->data_end
    if (data + 42 > data_end) {
       ip = nullptr; goto block1;
    } else {
       ip = data + some_offset;
       goto block2;
    }
    ...
    if (data + 42 > data_end) // original skb_shorter condition

The issue can be workarounded the source. Just check data + 42 > 
data_end and if failure return. Then you will be able to assign
a value to "ip" conditionally.

Will try to fix this issue in llvm12 as well.
Thanks!


> 
> 	/opt/clang/bin/clang --version
> 	clang version 11.0.0 (https://github.com/llvm/llvm-project.git 4cbfb98eb362b0629d5d1cd113af4427e2904763)
> 	Target: x86_64-unknown-linux-gnu
> 	Thread model: posix
> 	InstalledDir: /opt/clang/bin
> 
> 	$ llvm-objdump -d verifier-cond-repro.o
> 
> 	verifier-cond-repro.o:  file format ELF64-BPF
> 
> 	Disassembly of section .text:
> 
> 	0000000000000000 my_prog:
> 	       0:       61 12 50 00 00 00 00 00 r2 = *(u32 *)(r1 + 80)
> 	       1:       61 14 4c 00 00 00 00 00 r4 = *(u32 *)(r1 + 76)
> 	       2:       bf 43 00 00 00 00 00 00 r3 = r4
> 	       3:       07 03 00 00 2a 00 00 00 r3 += 42
> 	       4:       b7 01 00 00 00 00 00 00 r1 = 0
> 	       5:       2d 23 02 00 00 00 00 00 if r3 > r2 goto +2 <LBB0_2>
> 	       6:       07 04 00 00 0e 00 00 00 r4 += 14
> 	       7:       bf 41 00 00 00 00 00 00 r1 = r4
> 
> 	0000000000000040 LBB0_2:
> 	       8:       2d 23 05 00 00 00 00 00 if r3 > r2 goto +5 <LBB0_5>
> 	       9:       71 12 09 00 00 00 00 00 r2 = *(u8 *)(r1 + 9)
> 	      10:       56 02 03 00 11 00 00 00 if w2 != 17 goto +3 <LBB0_5>
> 	      11:       b4 00 00 00 d2 04 00 00 w0 = 1234
> 	      12:       69 11 16 00 00 00 00 00 r1 = *(u16 *)(r1 + 22)
> 	      13:       16 01 01 00 d2 04 00 00 if w1 == 1234 goto +1 <LBB0_6>
> 
> 	0000000000000070 LBB0_5:
> 	      14:       b4 00 00 00 ff ff ff ff w0 = -1
> 
> 	0000000000000078 LBB0_6:
> 	      15:       95 00 00 00 00 00 00 00 exit
> 
> 
> thanks,
> jirka
> 
> 
> ---
> // Copyright (c) 2019 Tigera, Inc. All rights reserved.
> //
> // Licensed under the Apache License, Version 2.0 (the "License");
> // you may not use this file except in compliance with the License.
> // You may obtain a copy of the License at
> //
> //     https://urldefense.proofpoint.com/v2/url?u=http-3A__www.apache.org_licenses_LICENSE-2D2.0&d=DwIBAg&c=5VD0RTtNlTh3ycd41b3MUw&r=DA8e1B5r073vIqRrFz7MRA&m=bsFf5gOsaXXCIBYvnl6AK78aRCaFS1zhqvVCYbn4JBA&s=5MVLZXPlXMo2B2K5wDP5P3Lmn4-TQTKHvQfvZupEFvs&e=
> //
> // Unless required by applicable law or agreed to in writing, software
> // distributed under the License is distributed on an "AS IS" BASIS,
> // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> // See the License for the specific language governing permissions and
> // limitations under the License.
> 
> #include <stddef.h>
> #include <string.h>
> #include <linux/bpf.h>
> #include <linux/if_ether.h>
> #include <linux/if_packet.h>
> #include <linux/ip.h>
> #include <linux/ipv6.h>
> #include <linux/in.h>
> #include <linux/udp.h>
> #include <linux/tcp.h>
> #include <linux/pkt_cls.h>
> #include <sys/socket.h>
> #include <bpf/bpf_helpers.h>
> #include <bpf/bpf_endian.h>
> 
> #include <stddef.h>
> 
> #define INLINE inline __attribute__((always_inline))
> 
> #define skb_shorter(skb, len) ((void *)(long)(skb)->data + (len) > (void *)(long)skb->data_end)
> 
> #define ETH_IPV4_UDP_SIZE (14+20+8)
> 
> static INLINE struct iphdr *get_iphdr (struct __sk_buff *skb)
> {
> 	struct iphdr *ip = NULL;
> 	struct ethhdr *eth;
> 
> 	if (skb_shorter(skb, ETH_IPV4_UDP_SIZE))
> 		goto out;
> 
> 	eth = (void *)(long)skb->data;
> 	ip = (void *)(eth + 1);
> 
> out:
> 	return ip;
> }
> 
> int my_prog(struct __sk_buff *skb)
> {
> 	struct iphdr *ip = NULL;
> 	struct udphdr *udp;
> 	__u8 proto = 0;
> 
> 	if (!(ip = get_iphdr(skb)))
> 		goto out;
> 
> 	proto = ip->protocol;
> 
> 	if (proto != IPPROTO_UDP)
> 		goto out;
> 
> 	udp = (void*)(ip + 1);
> 
> 	if (udp->dest != 1234)
> 		goto out;
> 
> 	if (!udp)
> 		goto out;
> 
> 	return udp->dest;
> 
> out:
> 	return -1;
> }
>