Ziv Chow 在微信群里问了个 verifier 的问题，一眼看上去肯定是 bpf 代码写得有问题，但是问题具体在哪里呢？
数组访问
如上图，crc16tab[key] 访问 crc16tab 数组时，在 bpf 里会转换成 bpf map 访问；因为 crc16tab 是一个长度为 256 的 u16 数组，需要消耗 512 字节的内存，因而无法保存在栈上。
所以，如果 verifier 判断寄存器的值没有有限最小值时，就会报上图中的错误。
可，明明已经 key & 0xFF 和 if (key > 255 || key < 0) 了，为什么还会报错呢？
快速验证 crc16tab 数组访问是没问题的
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;
}
跑起来后，可以看到输出：
$ 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 的代码，大概如下：
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 报错:
...
; 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 精简一下：
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 循环复用寄存器
意即，每次循环都进行一次函数调用：
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: 强行阻止编译器复用寄存器
/* 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;
}
如此一来，便可省掉 6 次函数调用。
总结
过不了 verifier 的问题总是那么恼人，而且需要耗费大量时间去分析 verifier log，才能找到问题所在。
而想要解决这个问题，还需要对编译器有一定的理解，才能找到解决方案。
完整代码：learn-by-example xdp-crc[1]。
learn-by-example xdp-crc: https://github.com/Asphaltt/learn-by-example/tree/main/ebpf/xdp-crc
