在 eBPF Talk: binary search 中，我们使用一个朴素的 for 循环实现了一个二分查找的 eBPF 程序，但是，这个程序通不过 verifier，报错 “R3 unbounded memory access, make sure to bounds check any such access”。

在这篇文章里，将分析 verifier log，找到问题所在，并解决这个问题。

复现问题

为了简化 verifier log，将 for 循环次数从 32 次改为 1 次，源代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#define DELAY_CIDR_CAPACITY 128

struct delay_cidr {
    __u32 start;
    __u32 end;
};

typedef struct {
    struct delay_cidr cidrs[DELAY_CIDR_CAPACITY];
} delay_cidrs_t;

static const volatile delay_cidrs_t delay_cidrs;
static const volatile __u32 delay_cidrs_len = 0;

static __always_inline bool
__should_delay_sip(__be32 ip)
{
    __u32 lo = 0;
    __u32 hi = delay_cidrs_len - 1;
    __u32 addr = bpf_ntohl(ip);

#pragma clang loop unroll(full)
    for (__u32 index = 0; index < 1; index++) {
        if (lo > hi)                    // Checking lo > hi for the end of binary search.
            return false;

        __u32 mid = (lo + hi) >> 1;
        if (mid >= DELAY_CIDR_CAPACITY) // It's required to do bound check for mid.
            return false;

        struct delay_cidr *cidr = (typeof(cidr))&delay_cidrs.cidrs[mid];
        if (addr >= cidr->start && addr <= cidr->end) {
            return true;
        }

        if (addr < cidr->start) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    return false;
}

最终得到完整的 verifier log 如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

load program: permission denied:
    0: R1=ctx(off=0,imm=0) R10=fp0
    ; int xdp_fn(struct xdp_md *ctx)
    0: (bf) r7 = r1                       ; R1=ctx(off=0,imm=0) R7_w=ctx(off=0,imm=0)
    1: (b7) r6 = 2                        ; R6_w=2
    ; void *data_end = ctx_ptr(ctx, data_end);
    2: (61) r2 = *(u32 *)(r7 +4)          ; R2_w=pkt_end(off=0,imm=0) R7_w=ctx(off=0,imm=0)
    ; void *data = ctx_ptr(ctx, data);
    3: (61) r3 = *(u32 *)(r7 +0)          ; R3_w=pkt(off=0,r=0,imm=0) R7_w=ctx(off=0,imm=0)
    ; if ((void *)(eth + 1) > data_end)
    4: (bf) r1 = r3                       ; R1_w=pkt(off=0,r=0,imm=0) R3_w=pkt(off=0,r=0,imm=0)
    5: (07) r1 += 14                      ; R1_w=pkt(off=14,r=0,imm=0)
    ; if ((void *)(eth + 1) > data_end)
    6: (2d) if r1 > r2 goto pc+54         ; R1_w=pkt(off=14,r=14,imm=0) R2_w=pkt_end(off=0,imm=0)
    ; if (eth->h_proto != bpf_htons(ETH_P_IP))
    7: (69) r4 = *(u16 *)(r3 +12)         ; R3_w=pkt(off=0,r=14,imm=0) R4_w=scalar(umax=65535,var_off=(0x0; 0xffff))
    ; if (eth->h_proto != bpf_htons(ETH_P_IP))
    8: (55) if r4 != 0x8 goto pc+52       ; R4_w=8
    9: (07) r3 += 34                      ; R3=pkt(off=34,r=14,imm=0)
    10: (2d) if r3 > r2 goto pc+50        ; R2=pkt_end(off=0,imm=0) R3=pkt(off=34,r=34,imm=0)
    ; if (iph->protocol != IPPROTO_ICMP)
    11: (71) r3 = *(u8 *)(r1 +9)          ; R1=pkt(off=14,r=34,imm=0) R3_w=scalar(umax=255,var_off=(0x0; 0xff))
    ; if (iph->protocol != IPPROTO_ICMP)
    12: (55) if r3 != 0x1 goto pc+48      ; R3_w=1
    ; ih = (typeof(ih))((void *)iph + (iph->ihl * 4));
    13: (71) r4 = *(u8 *)(r1 +0)          ; R1=pkt(off=14,r=34,imm=0) R4_w=scalar(umax=255,var_off=(0x0; 0xff))
    ; ih = (typeof(ih))((void *)iph + (iph->ihl * 4));
    14: (67) r4 <<= 2                     ; R4_w=scalar(umax=1020,var_off=(0x0; 0x3fc))
    15: (57) r4 &= 60                     ; R4_w=scalar(umax=60,var_off=(0x0; 0x3c))
    ; ih = (typeof(ih))((void *)iph + (iph->ihl * 4));
    16: (bf) r3 = r1                      ; R1=pkt(off=14,r=34,imm=0) R3_w=pkt(off=14,r=34,imm=0)
    17: (0f) r3 += r4                     ; R3_w=pkt(id=1,off=14,r=0,umax=60,var_off=(0x0; 0x3c)) R4_w=scalar(umax=60,var_off=(0x0; 0x3c))
    ; if ((void *)(ih + 1) > data_end)
    18: (bf) r4 = r3                      ; R3_w=pkt(id=1,off=14,r=0,umax=60,var_off=(0x0; 0x3c)) R4_w=pkt(id=1,off=14,r=0,umax=60,var_off=(0x0; 0x3c))
    19: (07) r4 += 8                      ; R4=pkt(id=1,off=22,r=0,umax=60,var_off=(0x0; 0x3c))
    ; if ((void *)(ih + 1) > data_end)
    20: (2d) if r4 > r2 goto pc+40        ; R2=pkt_end(off=0,imm=0) R4=pkt(id=1,off=22,r=22,umax=60,var_off=(0x0; 0x3c))
    ; if (ih->type != ICMP_ECHO)
    21: (71) r2 = *(u8 *)(r3 +0)          ; R2_w=scalar(umax=255,var_off=(0x0; 0xff)) R3=pkt(id=1,off=14,r=22,umax=60,var_off=(0x0; 0x3c))
    ; if (ih->type != ICMP_ECHO)
    22: (55) if r2 != 0x8 goto pc+38      ; R2_w=8
    ; if (!__should_delay_sip(iph->saddr))
    23: (61) r1 = *(u32 *)(r1 +12)        ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
    ; __u32 hi = delay_cidrs_len - 1;
    24: (18) r2 = 0xffff95285896e110      ; R2_w=map_value(off=0,ks=4,vs=1028,imm=0)
    26: (61) r2 = *(u32 *)(r2 +0)         ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
    ; __u32 hi = delay_cidrs_len - 1;
    27: (07) r2 += -1                     ; R2_w=scalar(smin=-1,smax=4294967294)
    28: (bf) r3 = r2                      ; R2_w=scalar(id=2,smin=-1,smax=4294967294) R3_w=scalar(id=2,smin=-1,smax=4294967294)
    29: (67) r3 <<= 32                    ; R3_w=scalar(smax=9223372032559808512,umax=18446744069414584320,var_off=(0x0; 0xffffffff00000000),s32_min=0,s32_max=0,u32_max=0)
    30: (77) r3 >>= 32                    ; R3=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
    ; if (mid >= DELAY_CIDR_CAPACITY) // It's required to do bound check for mid.
    31: (25) if r3 > 0xff goto pc+29      ; R3=scalar(umax=255,var_off=(0x0; 0xff))
    ;
    32: (dc) r1 = be32 r1                 ; R1_w=scalar()
    ; __u32 mid = (lo + hi) >> 1;
    33: (77) r2 >>= 1                     ; R2_w=scalar(umax=9223372036854775807,var_off=(0x0; 0x7fffffffffffffff))
    34: (57) r2 &= 2147483647             ; R2_w=scalar(umax=2147483647,var_off=(0x0; 0x7fffffff))
    ; struct delay_cidr *cidr = (typeof(cidr))&delay_cidrs.cidrs[mid];
    35: (67) r2 <<= 3                     ; R2_w=scalar(umax=17179869176,var_off=(0x0; 0x3fffffff8),s32_max=2147483640,u32_max=-8)
    36: (18) r3 = 0xffff95285896e114      ; R3_w=map_value(off=4,ks=4,vs=1028,imm=0)
    38: (0f) r3 += r2                     ; R2_w=scalar(umax=17179869176,var_off=(0x0; 0x3fffffff8),s32_max=2147483640,u32_max=-8) R3_w=map_value(off=4,ks=4,vs=1028,umax=17179869176,var_off=(0x0; 0x3fffffff8),s32_max=2147483640,u32_max=-8)
    ; if (addr >= cidr->start && addr <= cidr->end) {
    39: (61) r2 = *(u32 *)(r3 +0)
    R3 unbounded memory access, make sure to bounds check any such access
    verification time 2148 usec
    stack depth 0
    processed 38 insns (limit 1000000) max_states_per_insn 0 total_states 3 peak_states 3 mark_read 1

分析问题

直接分析以上 verifier log。

先分析其中的 r3 register

  1. 第 36 条 bpf insn r3 = 0xffff95285896e114，r3 register 里的值是 0xffff95285896e114，该地址指向了 .rodata bpf map value 里的 delay_cidrs.cidrs 数组。
  2. 第 38 条 bpf insn r3 += r2，将 r3 register 里的值加上 r2 register 里的值，目的是将 r3 register 里的地址指向 delay_cidrs.cidrs[mid]。
  3. 第 39 条 bpf insn r2 = *(u32 *)(r3 +0)，从 r3 register 里的地址上读取 4 个字节，存放到 r2 register 里，目的是将 r2 register 里的值设置为 delay_cidrs.cidrs[mid].start。

在第 38 条 bpf insn 中，因为 r2 register 的缘故，r3 register 的值的上限（umax=17179869176）超出了 verifier 里预定的上限 （1<<29 = 536870912）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// ${KERNEL}/include/linux/bpf_verifier.h

/* Maximum variable offset umax_value permitted when resolving memory accesses.
 * In practice this is far bigger than any realistic pointer offset; this limit
 * ensures that umax_value + (int)off + (int)size cannot overflow a u64.
 */
#define BPF_MAX_VAR_OFF (1 << 29)

// ${KERNEL}/kernel/bpf/verifier.c

/* check read/write into a memory region with possible variable offset */
static int check_mem_region_access(struct bpf_verifier_env *env, u32 regno,
                   int off, int size, u32 mem_size,
                   bool zero_size_allowed)
{
    // ...

    /* If we haven't set a max value then we need to bail since we can't be
     * sure we won't do bad things.
     * If reg->umax_value + off could overflow, treat that as unbounded too.
     */
    if (reg->umax_value >= BPF_MAX_VAR_OFF) {
        verbose(env, "R%d unbounded memory access, make sure to bounds check any such access\n",
            regno);
        return -EACCES;
    }
    // ...

    return 0;
}

后分析其中的 r2 register

从后往前，先找出 r2 register 赋值的地方（如第 24 条 bpf insn），然后再从该条 bpf insn 开始往后分析。

  1. 第 24 条 bpf insn r2 = 0xffff95285896e110，r2 register 里的值是 0xffff95285896e110，该地址指向了 .rodata bpf map value 里的 delay_cidrs_len。
  2. 第 26 条 bpf insn r2 = *(u32 *)(r2 +0)，从 r2 register 里的地址上读取 4 个字节，存放到 r2 register 里，目的是将 r2 register 里的值设置为 delay_cidrs_len。
  3. 第 27 条 bpf insn r2 += -1，将 r2 register 里的值减去 1，目的是将 r2 register 里的值设置为 delay_cidrs_len - 1，即是 hi 的值。
  4. 第 33 条 bpf insn r2 >>= 1，将 r2 register 里的值右移 1 位，目的是将 r2 register 里的值设置为 mid 的值，即 mid = (lo+hi) >> 1（因为 lo 是 0，所以被优化掉了）。
  5. 第 34 条 bpf insn r2 &= 2147483647，将 r2 register 里的值与 2147483647 = 0x7fffffff 做与运算，目的是将 r2 register 里的值确定在 0x0 ~ 0x7fffffff 之间，估计是因为上一条 bpf insn 做了右移操作。（不明白为什么要这么操作。）
  6. 第 35 条 bpf insn r2 <<= 3，将 r2 register 里的值左移 3 位。（不明白为什么要这么操作。）

P.S. 一些环境信息：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# clang --version
Homebrew clang version 15.0.7
Target: x86_64-apple-darwin22.4.0
Thread model: posix
InstalledDir: /usr/local/opt/llvm/bin
# lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 22.04.1 LTS
Release:    22.04
Codename:   jammy
# uname -r
6.2.0-060200rc8-generic

估计得以后研究了 clang 之后，才能搞清楚为什么会有第 34、35 条 bpf insn。

解决问题

不过，没完全搞懂所有 bpf insn 也没关系，猜测 r2 register 的状态变更都源于 .rodata bpf map value。

那么，解决办法就是使用 volatile 切断 r2 register 状态变更与 .rodata bpf map value 的关联。

不熟悉 volatile，不过知道可以用来：强行使用栈来保存变量。

也就是说，__u32 hi = delay_cidrs_len - 1; 变成 volatile __u32 hi = delay_cidrs_len - 1; 后，hi 变量的值就会被保存到栈上，而不是复用 r2 register 来保存。

因此，在 bpf verifier 里分析 r2 register 的状态变更时，就不会再受到 .rodata bpf map value 的影响了。

加了 volatile 后的 verifier log 如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

    ; volatile __u32 hi = delay_cidrs_len - 1; // Note: volatile is to avoid reusing R2 register.
    24: (18) r2 = 0xffff9527aee29110      ; R2_w=map_value(off=0,ks=4,vs=1028,imm=0)
    26: (61) r2 = *(u32 *)(r2 +0)         ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
    ; volatile __u32 hi = delay_cidrs_len - 1; // Note: volatile is to avoid reusing R2 register.
    27: (07) r2 += -1                     ; R2_w=scalar(smin=-1,smax=4294967294)
    ; volatile __u32 hi = delay_cidrs_len - 1; // Note: volatile is to avoid reusing R2 register.
    28: (63) *(u32 *)(r10 -4) = r2        ; R2_w=scalar(smin=-1,smax=4294967294) R10=fp0 fp-8=mmmm????
    ; if (lo > hi)                    // Checking lo > hi for the end of binary search.
    29: (61) r2 = *(u32 *)(r10 -4)        ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0
    ; __u32 mid = (lo + hi) >> 1;
    30: (61) r2 = *(u32 *)(r10 -4)        ; R2=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0
    ; if (mid >= DELAY_CIDR_CAPACITY) // It's required to do bound check for mid.
    31: (25) if r2 > 0xff goto pc+32      ; R2=scalar(umax=255,var_off=(0x0; 0xff))
    ;
    32: (dc) r1 = be32 r1                 ; R1_w=scalar()
    ;
    33: (77) r2 >>= 1                     ; R2_w=scalar(umax=127,var_off=(0x0; 0x7f))
    ; struct delay_cidr *cidr = (typeof(cidr))&delay_cidrs.cidrs[mid];
    34: (bf) r4 = r2                      ; R2_w=scalar(id=2,umax=127,var_off=(0x0; 0x7f)) R4_w=scalar(id=2,umax=127,var_off=(0x0; 0x7f))
    35: (67) r4 <<= 3                     ; R4_w=scalar(umax=1016,var_off=(0x0; 0x3f8))
    36: (18) r3 = 0xffff9527aee29114      ; R3_w=map_value(off=4,ks=4,vs=1028,imm=0)
    38: (0f) r3 += r4

其中：

  1. 第 28 条 bpf insn *(u32 *)(r10 -4) = r2，将 r2 register 里的值保存到栈上。
  2. 第 30 条 bpf insn r2 = *(u32 *)(r10 -4)，从栈上读取 4 个字节，存放到 r2 register 里。

这便是 volatile 带来的变化。

小结

以上，我们分析了 verifier log，找到了问题所在，并解决了这个问题。

使用 volatile 解决了问题，但是额外增加了栈的使用，会影响性能。

不过得到一条经验：使用 static const volatile 定义的常量进行运算的时候，最好使用 volatile 做一下变量缓存，避免 verifier 分析 register 状态变更时，受到 .rodata bpf map value 的影响。

P.S. demo 代码：eBPF binary search。