Ziv Chow 在微信群里问了个 verifier 的问题，一眼看上去肯定是 bpf 代码写得有问题，但是问题具体在哪里呢？

数组访问

如上图，crc16tab[key] 访问 crc16tab 数组时，在 bpf 里会转换成 bpf map 访问；因为 crc16tab 是一个长度为 256 的 u16 数组，需要消耗 512 字节的内存，因而无法保存在栈上。

所以，如果 verifier 判断寄存器的值没有有限最小值时，就会报上图中的错误。

可，明明已经 key & 0xFF 和 if (key > 255 || key < 0) 了，为什么还会报错呢？

快速验证 crc16tab 数组访问是没问题的

 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

static __always_inline
__u16 crc16(__u16 port)
{
    for (int i = 0; i < 6; i++) {
        port = (port << 8) ^ crc16tab[(port >> 10) & 0xff];
    }

    return port;
}

SEC("xdp")
int crc(struct xdp_md *ctx)
{
    struct ethhdr *eth = (typeof(eth)) ctx_ptr(ctx, data);
    struct iphdr *iph = (typeof(iph)) (eth + 1);
    struct tcphdr *tcph = (typeof(tcph)) (iph + 1);

    if ((void *)(tcph + 1) > ctx_ptr(ctx, data_end))
        return XDP_PASS;

    if (iph->protocol != IPPROTO_TCP || tcph->dest != bpf_htons(8080))
        return XDP_PASS;

    bpf_printk("crc16 of sport %d is %d\n", bpf_ntohs(tcph->source), crc16(tcph->source));

    return XDP_PASS;
}

跑起来后，可以看到输出：

1
2
3

$ sudo cat /sys/kernel/debug/tracing/trace_pipe
          <idle>-0       [006] .Ns21 380503.312159: bpf_trace_printk: crc16 of sport 64654 is 61704
          <idle>-0       [006] ..s21 380504.676875: bpf_trace_printk: crc16 of sport 64659 is 40765

那么，到底哪里出错了呢？

问题出在 for 循环

找 Ziv Chow 要了一下完整的计算 CRC16 的代码，大概如下：

 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

static __noinline
__u16 crc_16(__u64 port) {
    __u16 crc = 0;
    int key;

    for (int i = 0; i < 6; i++) {
        key = (int) ((crc >> 8) ^ (port >> i * 8 & 0xff)) & 0x00FF;
        if (key > 255 || key < 0) {
            return -1;
        }

        key = crc16tab[key];
        crc = (crc << 8) ^ key;
    }

    return crc;
}

static __always_inline
__u16 connection_crc_hash(__u32 src, __u16 src_port, __u32 dest, __u16 dest_port) {
    __u64 merge;
    __u16 crc;

    merge = ((__u64) src << 32) | dest;
    crc = crc_16(merge);
    merge = (__u64) (src_port) << 48|((__u64) crc << 32) | ((__u64) (dest_port) << 16) | ((__u64) (src_port));
    return crc_16(merge);
}

SEC("xdp")
int crc(struct xdp_md *ctx)
{
    struct ethhdr *eth = (typeof(eth)) ctx_ptr(ctx, data);
    struct iphdr *iph = (typeof(iph)) (eth + 1);
    struct tcphdr *tcph = (typeof(tcph)) (iph + 1);

    if ((void *)(tcph + 1) > ctx_ptr(ctx, data_end))
        return XDP_PASS;

    if (iph->protocol != IPPROTO_TCP || tcph->dest != bpf_htons(8080))
        return XDP_PASS;

    bpf_printk("crc16: %d\n", connection_crc_hash(iph->saddr, tcph->source, iph->daddr, tcph->dest));

    return XDP_PASS;
}

就是其中 key = crc16tab[key]; 这一行，导致 verifier 报错:

 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

    ...
    ; crc = crc_16(merge);
    31: (85) call pc+11
    caller:
     frame1: R6=scalar(id=2,smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff)) R7=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff)) R10=fp0
    callee:
     frame2: R1=scalar() R2=scalar(id=2,smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff)) R3=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R4=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff)) R10=fp0
    43: frame2: R1=scalar() R2=scalar(id=2,smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff)) R3=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R4=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff)) R10=fp0
    ; key = (int) ((crc >> 8) ^ (port >> i * 8 & 0xff)) & 0x00FF;
    43: (bf) r3 = r1                      ; frame2: R1=scalar(id=3) R3_w=scalar(id=3)
    44: (57) r3 &= 255                    ; frame2: R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))
    ; key = crc16tab[key];
    45: (67) r3 <<= 1                     ; frame2: R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=510,var_off=(0x0; 0x1fe))
    46: (18) r2 = 0xffff8f8b9a03051c      ; frame2: R2_w=map_value(map=.rodata,ks=4,vs=524,off=12)
    48: (18) r4 = 0xffff8f8b9a03051c      ; frame2: R4_w=map_value(map=.rodata,ks=4,vs=524,off=12)
    50: (0f) r4 += r3                     ; frame2: R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=510,var_off=(0x0; 0x1fe)) R4_w=map_value(map=.rodata,ks=4,vs=524,off=12,smin=smin32=0,smax=umax=smax32=umax32=510,var_off=(0x0; 0x1fe))
    51: (69) r3 = *(u16 *)(r4 +0)         ; frame2: R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff)) R4_w=map_value(map=.rodata,ks=4,vs=524,off=12,smin=smin32=0,smax=umax=smax32=umax32=510,var_off=(0x0; 0x1fe))
    ; key = (int) ((crc >> 8) ^ (port >> i * 8 & 0xff)) & 0x00FF;
    52: (bf) r4 = r1                      ; frame2: R1=scalar(id=3) R4_w=scalar(id=3)
    53: (77) r4 >>= 8                     ; frame2: R4_w=scalar(smin=0,smax=umax=0xffffffffffffff,var_off=(0x0; 0xffffffffffffff))
    ; key = (int) ((crc >> 8) ^ (port >> i * 8 & 0xff)) & 0x00FF;
    54: (57) r4 &= 255                    ; frame2: R4_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))
    55: (bf) r5 = r3                      ; frame2: R3_w=scalar(id=4,smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff)) R5_w=scalar(id=4,smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff))
    56: (77) r5 >>= 8                     ; frame2: R5_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))
    57: (af) r4 ^= r5                     ; frame2: R4_w=scalar() R5_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))
    ; crc = (crc << 8) ^ key;
    58: (67) r3 <<= 8                     ; frame2: R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=0xffff00,var_off=(0x0; 0xffff00))
    ; key = crc16tab[key];
    59: (67) r4 <<= 1                     ; frame2: R4_w=scalar(smax=0x7ffffffffffffffe,umax=0xfffffffffffffffe,smax32=0x7ffffffe,umax32=0xfffffffe,var_off=(0x0; 0xfffffffffffffffe))
    60: (18) r5 = 0xffff8f8b9a03051c      ; frame2: R5_w=map_value(map=.rodata,ks=4,vs=524,off=12)
    62: (0f) r5 += r4
    math between map_value pointer and register with unbounded min value is not allowed
    processed 41 insns (limit 1000000) max_states_per_insn 0 total_states 2 peak_states 2 mark_read 1

从下往上看，r4 ^= r5 破坏了 r4 的范围值，前面明明 r4 &= 255 做了范围检查。

再仔细分析，r5 += r4 是第二次循环中的 crc16tab 访问。而在第一次访问 crc16tab 前，r3 << 1 和 r3 &= 255 之间却没有类似 r3 ^= r5 的操作。

这又是为什么呢？

将 crc_16() 的 verifier log 精简一下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    r3 = r1                 ;; r3 = port
    r3 &= 255               ;; r3 = port & 0xff, 因为 crc = 0 且 counter = 0，所以优化掉了不少地方
    r3 <<= 1                ;; ???
    r2 = 0xffff8f8b9a03051c ;; r2 = &crc16tab
    r4 = 0xffff8f8b9a03051c ;; r4 = &crc16tab
    r4 += r3                ;; r4 = &crc16tab + (port & 0xff) * 2
    r3 = *(u16 *)(r4 +0)    ;; r3 = crc16tab[r4]
    r4 = r1                 ;; r4 = port
    r4 >>= 8                ;; r4 = port >> 8
    r4 &= 255               ;; r4 = (port >> 8) & 0xff
    r5 = r3                 ;; r5 = r3, crc16tab 取出的值
    r5 >>= 8                ;; r5 = r3 >> 8, 对应 crc >> 8
    r4 ^= r5                ;; r4 = r4 ^ r5, 对应 (crc >> 8) ^ ((port >> 8) & 0xff)
    r3 <<= 8                ;; r3 = r3 << 8, 对应 crc << 8
    r4 <<= 1                ;; ???
    r5 = 0xffff8f8b9a03051c ;; r5 = &crc16tab
    r5 += r4                ;; r5 = &crc16tab + (r4 << 1)

噢噢，原来第一次的 r3 ^= r5 的操作被优化掉了。

所以，要解决这问题，只需要确保 &= 255 在 ^= r5 之后便可。

解法1: 使用函数调用禁止 for 循环复用寄存器

意即，每次循环都进行一次函数调用：

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

static __noinline
__u32 __crc(__u32 crc, __u64 port, int i)
{
    return (crc << 8) ^ crc16tab[((crc >> 8) ^ (port >> i * 8)) & 0xff];
}

static __always_inline
__u16 crc16(__u64 port)
{
    __u32 crc = 0;

    for (int i = 0; i < 6; i++)
        crc = __crc(crc, port, i);

    return crc;
}

解法2: 使用 asm 强行阻止编译器寄存器乱序优化

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

/* make it look to compiler like value is read and written */
#define __sink(expr) asm volatile("" : "+g"(expr))

static __always_inline
__u32 __crc(__u32 crc, __u64 port, int i)
{
    __u64 key = (crc >> 8) ^ (port >> i * 8);
    __sink(key);
    return (crc << 8) ^ crc16tab[key & 0xff];
}

static __always_inline
__u16 crc16(__u64 port)
{
    __u32 crc = 0;

    for (int i = 0; i < 6; i++)
        crc = __crc(crc, port, i);

    return crc;
}

其中，__sink(key) 会让编译器认为 key 被读取和写入，从而会先完成 (crc >> 8) ^ (port >> i * 8) 的计算，再进行 crc16tab[key & 0xff] 的访问。

如此一来，便可省掉 6 次函数调用。

总结

过不了 verifier 的问题总是那么恼人，而且需要耗费大量时间去分析 verifier log，才能找到问题所在。

而想要解决这个问题，还需要对编译器有一定的理解，才能找到解决方案。

完整代码：learn-by-example xdp-crc。