BPF 验证器说程序超过 1M 指令

分享于2022年07月17日 c ebpf linux-kernel xdp-bpf 问答
【问题标题】:BPF 验证器说程序超过 1M 指令(BPF verifier says program exceeds 1M instruction)
【发布时间】:2022-07-10 21:19:28
【问题描述】:

对于下面的程序,我从验证器那里得到一个错误,说它超过了 1M 指令,即使它不应该。程序查找 HTTP 数据包的主机名。

#include 
#include 

struct server_name {
    char server_name[256];
    __u16 length;
};

#define MAX_SERVER_NAME_LENGTH 253
#define HEADER_LEN 6

SEC("xdp")
int collect_ips_prog(struct xdp_md *ctx) {
    char *data_end = (char *)(long)ctx->data_end;
    char *data = (char *)(long)ctx->data;
    int host_header_found = 0;

    for (__u16 i = 0; i <= 512 - HEADER_LEN; i++) {
        host_header_found = 0;

        if (data_end < data + HEADER_LEN) {
            goto end;
        }

        // Elf loader does not allow NULL terminated strings, so have to check each char manually
        if (data[0] == 'H' && data[1] == 'o' && data[2] == 's' && data[3] == 't' && data[4] == ':' && data[5] == ' ') {
            host_header_found = 1;
            data += HEADER_LEN;
            break;
        }

        data++;
    }

    if (host_header_found) {
        struct server_name sn = {"a", 0};

        for (__u16 j = 0; j < MAX_SERVER_NAME_LENGTH; j++) {
            if (data_end < data + 1) {
                goto end;
            }

            if (*data == '\r') {
                break;
            }

            sn.server_name[j] = *data++;
            sn.length++;
        }
    }

end:
    return XDP_PASS;
}

忽略 data 没有指向数据包的HTTP 有效负载的开头。这足以重现我看到的问题。

我收到以下错误:

; for (__u16 j = 0; j < MAX_SERVER_NAME_LENGTH; j++) {
76: (25) if r3 > 0xfb goto pc+3
77: (07) r3 += 1
78: (07) r4 += 8
79: (3d) if r1 >= r4 goto pc-15

from 79 to 65: R0_w=fp-189 R1=pkt_end(id=0,off=0,imm=0) R2=pkt(id=0,off=280,r=363,imm=0) R3_w=invP76 R4_w=pkt(id=0,off=363,r=363,imm=0) R5_w=inv(id=0,umin_value=1,umax_value=65536,var_off=(0x0; 0x1ffff)) R10=fp0 fp-8=??????mm fp-16=00000000 fp-24=00000000 fp-32=00000000 fp-40=00000000 fp-48=00000000 fp-56=00000000 fp-64=00000000 fp-72=00000000 fp-80=00000000 fp-88=00000000 fp-96=00000000 fp-104=00000000 fp-112=00000000 fp-120=00000000 fp-128=00000000 fp-136=00000000 fp-144=00000000 fp-152=00000000 fp-160=00000000 fp-168=00000000 fp-176=00000000 fp-184=00000000 fp-192=0000mmmm fp-200=mmmmmmmm fp-208=mmmmmmmm fp-216=mmmmmmmm fp-224=mmmmmmmm fp-232=mmmmmmmm fp-240=mmmmmmmm fp-248=mmmmmmmm fp-256=mmmmmmmm fp-264=mmmmmmmm
; if (*data == '\r') {
65: (bf) r4 = r2
66: (0f) r4 += r3
67: (71) r5 = *(u8 *)(r4 +6)
BPF program is too large. Processed 1000001 insn
processed 1000001 insns (limit 1000000) max_states_per_insn 34 total_states 10376 peak_states 7503 mark_read 3

这没有意义,因为在第二个 for 循环中最多应该有 20 条指令,如果达到最大迭代次数,这将产生最多 5060 条指令。我可以将 MAX_SERVER_NAME_LENGTH 减少到验证器通过的最小值是104。如果我注释掉 if (host_header_found) { 块,那么验证器就会成功。


【解决方案1】:

TL;DR. 您的程序过于复杂,验证器无法分析,因为它必须迭代超过 100 万条指令才能验证完整的程序。


验证器错误说明

BPF 程序太大。处理了1000001个insn

验证程序出错,因为它已经分析了 100 万条指令。因此它达到了极限并放弃了。

这个验证器错误确实有点误导。 BPF 程序实际上并不太大。验证者必须分析的指令数量与整个程序中的指令数量不同,因为 验证者必须分析程序中的每条路径 。因此,它可能会沿着不同的路径多次分析相同的指令。

这么小的程序怎么可能需要超过 1M 的分析指令?

验证器达到 100 万条指令,因为您的程序有很多不同的路径。实际上,您的程序有两个具有相当高界限的循环(506 和 253),它们本身包含几个条件(为了简化,每个循环约 2 个)。在最坏的情况下,验证者可能不得不分析通过这两个循环的所有可能路径上的每条指令。

我该如何解决?

您可以减小循环的大小(如您所想)以降低复杂性。您还可以简化循环体。

或者,您可以使用尾调用来中断您的程序。也许两个循环之间的一个尾调用就足以通过验证器。

  • XDP 卸载是否支持拖尾?
  • 您必须询问您的 NIC 供应商。如果是 Netronome,我上次检查(2 年前),他们没有。
  • 我的第一个循环有 506 次迭代,我的第二个循环有 253 次迭代。即使每个循环都进行了最大迭代,我也很困惑任何路径如何导致 1M 总指令。
  • @user2233706 不仅迭代次数是一个因素,而且如果可能的执行路径依赖于来自数据包和映射的外部数据,验证者还将检查该外部数据的排列。因此,对于数据包的大量排列,它可能会循环约 700 次迭代。添加额外的检查可能会有所帮助。例如,如果您在程序的早期就以无效输入从程序返回,则验证器不必为所有这些排列循环。所以尽量尽快退出,先处理任何错误情况。
  • @DylanReimerink 我认为这是个坏建议。验证者仍然需要检查程序中所有可能的路径,因此添加更多条件只会增加路径的数量。