Re: [BUG] optimizations for branch cause bpf verification to fail

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 





On 6/8/23 10:02 PM, Zhongqiu Duan wrote:
On Fri, Jun 9, 2023 at 5:26 AM Yonghong Song <yhs@xxxxxxxx> wrote:



On 6/8/23 12:52 PM, Zhongqiu Duan wrote:
Hello,  everyone.

Recently, I've been doing some work using eBPF techniques. A situation was
encountered in which a program was rejected by the verifier.

Iterate over different maps under different conditions. It should be a good idea
to use map-of-maps when there are lots of maps. I use if cond for a quick test.

It looks like this:

int foo(struct xdp_md *ctx)
{
     void *data_end = (void *)(long)ctx->data_end;
     void *data = (void *)(long)ctx->data;
     struct callback_ctx cb_data;

     cb_data.output = 0;

     if (data_end - data > 1024) {
         bpf_for_each_map_elem(&map1, cb, &cb_data, 0);
     } else {
         bpf_for_each_map_elem(&map2, cb, &cb_data, 0);
     }

     if (cb_data.output)
         return XDP_DROP;

     return XDP_PASS;
}

Compile by clang-15 with optimization level O2:

0000000000000000 <foo>:
;     void *data = (void *)(long)ctx->data;
0:       61 12 00 00 00 00 00 00 r2 = *(u32 *)(r1 + 0)
;     void *data_end = (void *)(long)ctx->data_end;
1:       61 13 04 00 00 00 00 00 r3 = *(u32 *)(r1 + 4)
;     if (data_end - data > 1024) {
2:       1f 23 00 00 00 00 00 00 r3 -= r2
3:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0 ll
5:       65 03 02 00 00 04 00 00 if r3 s> 1024 goto +2 <LBB0_2>
6:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0 ll
0000000000000040 <LBB0_2>:
8:       b7 02 00 00 00 00 00 00 r2 = 0
;     cb_data.output = 0;
9:       63 2a f8 ff 00 00 00 00 *(u32 *)(r10 - 8) = r2
10:       bf a3 00 00 00 00 00 00 r3 = r10
11:       07 03 00 00 f8 ff ff ff r3 += -8
12:       18 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r2 = 0 ll
14:       b7 04 00 00 00 00 00 00 r4 = 0
15:       85 00 00 00 a4 00 00 00 call 164
16:       b7 00 00 00 02 00 00 00 r0 = 2
;     if (cb_data.output)
17:       61 a1 f8 ff 00 00 00 00 r1 = *(u32 *)(r10 - 8)
; }
18:       15 01 01 00 00 00 00 00 if r1 == 0 goto +1 <LBB0_4>
19:       b7 00 00 00 01 00 00 00 r0 = 1
00000000000000a0 <LBB0_4>:
; }
20:       95 00 00 00 00 00 00 00 exit

When loading the prog, the verifier complained "tail_call abusing map_ptr".
The Compiler's optimizations look fine, so I took a quick look at the code of
the verifier.

The function record_func_map called by check_helper_call will ref the current
map in bpf_insn_aux_data of current insn. After the current branch ends,
pop stack and enter another branch, but the relevant state is not cleared.
This time, record_func_map set BPF_MAP_PTR_POISON as the map state.
At the start of set_map_elem_callback_state, poisoned state causing EINVAL.

Okay, I see. For the following code,

      if (data_end - data > 1024) {
          bpf_for_each_map_elem(&map1, cb, &cb_data, 0);
      } else {
          bpf_for_each_map_elem(&map2, cb, &cb_data, 0);
      }

the compiler changed to
      if (data_end - data > 1024)
        tmp = &map1;
      else
        tmp = &map2;
      bpf_for_each_map_elem(tmp, cb, &cb_data, 0);

Since the 'map' input of bpf_for_each_map_elem() has two choices,
verifier complains. This is to simplify the verifier for common cases.

To fix the issue, you can add
	asm volatile("" ::: "memory");
after each bpf_for_each_map_elem() call.

Eduard is working on a llvm solution to address such issues.


It will be helpful if you can provide a reproducible test case
so people can help you to double check whether it is a verifier
bug/limitation or not. It is hard to decide where is the problem
in verifier based on the above description.


Hi, Yonghong.

The complete example is as follows:

foo.c
---
/* SPDX-License-Identifier: GPL-2.0 */
#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>

struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __type(key, __u32);
    __type(value, __u32);
    __uint(max_entries, 1024);
} map1 SEC(".maps"), map2 SEC(".maps");

struct callback_ctx {
    int output;
};

static __u64 cb(struct bpf_map *map, __u32 *key, __u64 *val,
                struct callback_ctx *data)
{
    if (*key == 1) {
        data->output = 1;
        return 1; /* stop the iteration */
    }
    return 0;
}

SEC("xdp")
int foo(struct xdp_md *ctx)
{
    void *data_end = (void *)(long)ctx->data_end;
    void *data = (void *)(long)ctx->data;
    struct callback_ctx cb_data;

    cb_data.output = 0;

    if (data_end - data > 1024) {
        bpf_for_each_map_elem(&map1, cb, &cb_data, 0);
    } else {
        bpf_for_each_map_elem(&map2, cb, &cb_data, 0);
    }

    if (cb_data.output)
        return XDP_DROP;

    return XDP_PASS;
}

char _license[] SEC("license") = "GPL";
---

Environment: linux-6.3 clang-14.0.6 bpftool-7.2.0 libbpf-1.2

Steps to load:

clang -S -target bpf -Wno-visibility -Wall -Wno-unused-value -Wno-pointer-sign \
-Wno-compare-distinct-pointer-types -Werror -O2 -emit-llvm -c -g -o foo.ll foo.c
llc -march=bpf -filetype=obj -o foo.o foo.ll
sudo bpftool prog load foo.o /sys/fs/bpf/foo

Regards,
Zhongqiu


I'm not very familiar with BPF. If it is designed like this, it is
customary to add
options on the compiler side to avoid it, then please let me know.

Thanks,
Zhongqiu





[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux