Show HN: 内核中的 DOOM，或 eBPF 中的纤程

# 内核中的DOOM，或eBPF中的纤程 来源：https://ayles.github.io/doom-in-kernel/ 2026年9月9日 阅读约30分钟 DOOM本不应该在eBPF中运行。Linux理应在执行其第一条指令前就拒绝这样的程序。 BPF的栈很小，只有五个参数寄存器，调用深度有限。递归是被禁止的。循环必须是有限的——不仅仅因为程序员这么说，而是要能用验证器可以证明的术语来表达。你不能简单地将指针存储在内存中，以后再加载并解引用：内核必须记住它从哪里来，以及它被允许访问什么。 然而，未经修改的Linux内核接受了我的BPF对象，用标准验证器检查它，并通过标准JIT运行它。DOOM的初始化、游戏逻辑和渲染都在内核中执行。一个游戏时钟周期，包括完整的帧，在单次BPF调用中完成。用户空间提供WAD文件和键盘输入，然后获得一个指向完成帧缓冲区的指针。 首先，简单介绍一下eBPF。它允许用户提供的程序在Linux内核中运行，而无需内核模块。程序被编译为针对小型寄存器机器的字节码，通过 `bpf(2)` 系统调用加载，并附加到一个钩子上——例如传入的数据包或系统调用跟踪点。内核的JIT将字节码编译为机器码，在钩子触发时运行。但在程序运行之前，验证器必须接受它。这就是上面约束的来源：验证器无法证明安全的代码会被拒绝。正是这种检查，而非字节码本身，使得在eBPF中运行DOOM看起来不可能。 该项目名为BPF Capsule (https://github.com/ayles/bpf-capsule)。它是一个编译器和运行时，用于在普通BPF中运行大型C程序，无需内核补丁，也无需用户空间的独立虚拟机。最古老的支持目标配置是Linux 5.15。配置决定了编译器可以使用哪些内核功能。我已在x86-64和arm64上加载并运行了这些程序。 当然，没人需要在内核里玩游戏。但复杂的应用逻辑在那里很有用：例如，解析数据包或维护其统计信息。当这样的程序不符合eBPF的约束时，必须简化并手动重写，直到验证器满意为止。Capsule探索了另一条路径：它接受C、C++或 `no_std` Rust代码，并将其转换成普通Linux接受的形式。 DOOM在这里不是应用本身，而是这种方法的压力测试。Lua、QuickJS、SQLite、zlib、wasm3、llama2.c、 `no_std` Rust和CPython 3.14今天都运行在相同的方案上，而Lua和Python直接从XDP检查实时数据包。本文将追踪从手动精简移植，到慢速解释器，再到区域和纤程的路径——并衡量它们在运行时所付出的代价。 你可以在任何支持的内核上用一条命令尝试。你需要Nix和一个WAD文件——出于显而易见的原因，WAD文件不在仓库中——其余的要求在README (https://github.com/ayles/bpf-capsule/blob/6733c4531f06f95a32a35c2084b3dcf1a4263746/README.md#build) 中： ``` $ sudo nix run github:ayles/bpf-capsule#doom -- /path/to/doom1.wad tty ``` 诀窍在于呈现给验证器的程序形状。首先，我让DOOM编译成BPF并在完全没有验证器的情况下运行。然后，我删掉了内核不喜欢的所有东西，对指针撒了谎，并将循环强制为一种特殊形式。当这也不再扩展时，我在eBPF内部编写了一个虚拟机。当前基于区域、纤程和软件栈的机器就是由此发展而来。 这些方法一个接一个地失效，而每一次失败都提示了下一步必须构建什么。 打开录像。(https://ayles.github.io/doom-in-kernel/doom-capsule.mp4) *游戏看起来特别像素化，因为帧是通过终端字符在SSH上渲染的。DOOM运行在左侧的内核BPF JIT中。右侧是真实的 `bpf_dispatch_output_scalar_*` 函数的示例：Capsule将区域打包进去的物理函数。* ## 为何这本应不可能 理论上，eBPF是一种带有LLVM后端的小型寄存器架构。听起来很简单：写C，运行 `clang -target bpf`，就能得到一个内核可以加载的对象。 实践中，“写C”意味着同时使用两种相当不同的语言。LLVM理解一种，Linux验证器理解另一种。 在研究Perforator (https://github.com/yandex/perforator) 时，我深入熟悉了那条边界。正是在那里，我对当前BPF栈积累了足够的挫败感，才走到这一步。 在加载程序之前，验证器会进行符号执行。对于每个寄存器，它跟踪的不仅是一个值或范围，还有一个含义：一个普通数字（`SCALAR_VALUE`）、指向栈、数据包数据、映射值或 `bpf_arena` 的指针。它探索分支、合并状态，并证明两件事：每次内存访问都是允许的，以及每条执行路径最终都会终止。 这产生了一些普通程序几乎不会注意到的约束： - `r1` 到 `r5` 是经典ABI中全部的参数寄存器； - 调用图必须是无环的，并且调用深度有限； - 沿着调用链只有512字节的栈可用； - 一个加载的程序最多可包含256个BPF函数； - 处理大约一百万条指令后，验证器会放弃。 最后一个限制不是执行时间限制。即使是一个短循环，如果分析器必须用足够多的不同状态重新访问它，也可能耗尽预算。有限循环本身是合法的；问题始于内核无法证明其边界或必须枚举太多可能性时。 内存则更为有趣。对于CPU来说，指针最终只是一个数字。对于验证器来说，它是一个带有履历的数字。它可能知道 `r10 - 8` 指向一个有效的BPF栈槽，或者 `data + n` 在检查 `data_end` 后仍留在数据包内。将该指针作为普通64位存储在映射中再加载回来，CPU得到的是相同的地址，而验证器得到的却是一个没有权限解引用的数字。 普通的C程序不断将指针放入结构体，将这些结构体传递给多个函数，并在很久之后才加载指针。在那条路径的某个地方，验证器丢失了证明。 ### 一个最近的LLVM示例 在C中编写有效的边界检查是不够的：内核看到的是优化后的代码。这是一个真实的用于数据包处理的BPF代码片段 (https://github.com/ayles/bpf-capsule/blob/6733c4531f06f95a32a35c2084b3dcf1a4263746/examples/lua-xdp/lua_xdp_runtime.c)： ``` size_t at = offset + index; asm volatile("" : "+r"(at)); at &= PACKET_CAPACITY - 1; if (data + at + 1 > data_end) return -1; byte = data[at]; ``` 掩码约束了 `at`，随后的比较证明了数据包边界。然而，在流水线后期，LLVM可以根据从可恢复的循环帧加载的原始 `offset` 和 `index` 再次表示索引。这两种形式对于CPU来说意味着同一件事。在一种形式下，受支持的Linux 5.15配置中的旧验证器在访问旁边看到一个有界的索引；而在另一种形式下，它失去了所需的证明。空的内联汇编CPU不需要，也不产生任何BPF指令。它的存在是为了让LLVM保留内核理解的确切数据依赖关系。 这是介于C和机器之间的令人不快的第三种语言：有时程序不仅要安全，还要以可识别的形状将安全证明通过优化器传递下去。 ## 首先，生成任何BPF 在涉及内核之前，有一个中间步骤：将DOOM编译成BPF，并在用户空间虚拟机中运行该对象。没有验证器，代码生成错误就可以与证明安全性的失败分开。 我的实验基于PureDOOM (https://github.com/Daivuk/PureDOOM)，这是一个移植版本，将整个引擎打包在一个C头文件中，并暴露一个简短的嵌入接口。对于这样的实验很方便，同时让DOOM本身几乎是普通的C。 即使没有验证器，任意C代码也不会自动变成BPF。经典ABI没有地方放第六个参数，BPF既没有浮点运算也没有间接调用。大型结构体返回值、可变大小的 `memcpy` 和一些128位算术也需要降低复杂度。我还必须扩展uBPF的程序计数器，并添加缺失的指令、段和ELF重定位。 BPF全局变量不会变成普通的进程内存：`.data` 和 `.bss` 变成了映射值，而ELF重定位告诉加载器代码中每个地址引用的是哪个映射以及哪个偏移量。 经过这些更改，DOOM在uBPF中运行了。在那里栈不是根本障碍：虚拟机的帧大小和总内存预留可以简单地增加。这证明了LLVM可以生成可工作的BPF代码，但没有说明真正的内核是否会接受它。 以前已经有人在用户空间BPF机器中运行过DOOM。一个例子是Fly out of the nest——一个DOOM的BPF移植 (https://lpc.events/event/18/contributions/1936/)，它使用了自己的νBPF虚拟机。在虚拟机内部，你可以更改机器的规则。我的目标不同：一个对象能被普通的Linux验证器接受，并被普通的内核BPF JIT执行。 ## 用剪刀移植 下一步是将程序加载到真正的内核中。uBPF的自由到此为止：我无法增加512字节的帧、调用深度或验证器预算。第一次尝试尽可能直接——采用PureDOOM并删除所有不符合要求的东西。原生构建保持为参考，以便以后可以逐字节比较帧。 那个时期的Git历史读起来就像一个截肢记录： - `移除声音`； - `移除参数解析和演示回放`； - `移除网络`； - `移除文件I/O`； - `移除内部gettime调用`； - `移除动态内存分配`； - `修复一些函数以接受5个或更少参数`； - `移除间接调用`； - `消除递归；疯狂内联这段代码`。 DOOM中函数指针无处不在：动作表、思考者函数、渲染器回调。我用一个 `indirect_call.c` 替换了它们，其中包含一个针对每个已知目标的比较链。未知目标会结束游戏，而递归的BSP遍历变成了一个数组和一个手动栈。 然后必须内联函数以适应真正的BPF栈和调用深度限制。这很快变成了死胡同。内联减少了深度，但增加了同时存活的值的数量和寄存器溢出的数量。阻止内联，单个函数就合适了，但调用图仍然太深，偶尔还有递归。再多一层内联只是改变了程序首先遇到哪个限制。 在某个时刻，很明显我不再是在移植DOOM。我是在手动完成编译器的工作。有用的结果与其说是一个可工作的二进制文件，不如说是一系列机械转换的清单。 第一个LLVM pass包含了两个技巧。一个试图使任意内存访问被验证器接受。另一个强制每个循环都遵循内核可以证明的一种形式。几乎整个项目最终都是从这两个技巧发展而来的。那时，这显然是一个项目，而不是一个消遣：它有了一个仓库，我将整个构造命名为BPF Capsule。 ## 技巧一：清洗指针 问题看起来是这样的。DOOM将一个真实的指针存储在堆或全局结构体中，然后在多次调用后加载并解引用它。CPU得到相同的64位。加载后，验证器看到的是一个普通数字：指针的来源和允许的边界消失了。对真实BPF栈的特殊处理无济于事；DOOM的任意堆将无法容纳在512字节内。 在访问之前，这个数字必须再次绑定到内核已知的对象。听起来减去 `.data` 或 `.bss` 的起始地址应该就足够了。但对验证器来说，第一个值是标量，第二个是从ELF重定位获得的 `PTR_TO_MAP_VALUE`。内核禁止 `scalar - pointer`。 反转减法也无济于事。对于CPU，`end_ptr - x` 是距离段末尾的一小段距离。但验证器不知道 `x` 包含来自同一映射的地址：它看到的是一个巨大或未知的指针偏移，超出了 `BPF_MAX_VAR_OFF`（`2^29`）允许的范围。之后再化简两个基数为时已晚；第一个操作已经被禁止了。 因此，同一个段基数必须以两种形式存在——双重分账簿记。一个清洗过的副本可以从未知地址中减去，而原始副本仍然携带其验证器履历，可以在检查结果后使用： ``` x, 从内存加载 .data的起始地址 (PTR_TO_MAP_VALUE) | | | | 清洗 | | | 标量基数 <-----------+ | | | | +--> 偏移量 = x - 基数 | | | 检查 0 <= 偏移量 <= 大小 - 宽度 | | | +--> 基数 + 偏移量 <-----------+ | v .data 中的有效地址 ``` 第一个工作版本清洗了一个相当粗糙的基数。这个pass在一个映射中创建了一个名为 `globalConv` 的 `volatile` 单元，以及一个大致如下函数： ``` void *bpf_ptr_to_scalar(void *ptr) { globalConv = ptr; return globalConv; } ``` 随程序一起提供了一个BTF类型表。它故意告诉内核这个函数不接受参数并返回 `u64`，即使机器码使用了 `r1`。因此，对映射的存储看起来就像存储一个普通数字，调用者也收到了一个标量。注释很诚实：`欺骗验证器认为没有参数`。 段基数需要另一个丑陋的技巧。pass在 `.data` 和 `.bss` 的开头都插入了一个合成全局变量；对它的引用成为加载后相应映射的真实基数。起初，段大小是通过对LLVM全局变量求和计算的，但最终的布局和对齐直到ELF生成时才存在。在这个实验最后留存的版本中，计算结果被两个硬编码常量简单地覆盖了。 然后，比较约束了标量 `offset`，将其加到未触及的基数上再次产生一个 `PTR_TO_MAP_VALUE`。每个不确定的读或写都增长了一个路由器： ``` 未知地址 | +-- 在 .data 内？ --> 已知基数 + 已检查的偏移量 +-- 在 .bss 内？ --> 已知基数 + 已检查的偏移量 `-- 其他位置 --> 故障 ``` 这对单个段足够了，但对所有内存还不够。指向BPF栈的指针无法通过映射完成同样的往返：内核要么看到指针泄漏，要么返回一个无用的标量。因此，地址被占用的、在调用后仍然存在的局部变量仍然需要单独的存储。 一旦内存访问开始通过，验证器就转向了循环，并将其百万条指令预算花在了那里。 ## 技巧二：一个计数器统治一切 第一个循环pass用 `bpf_iter_num_new/next/destroy` 包装每个循环，并设置一个巨大的紧急边界。然后它变得更加激进：循环中推进的每个计数器和指针都通过一个单独的迭代数字 `n` 来表达。 如果源代码循环同时推进 `i`、`j` 和 `p`，转换后的循环会重建它们： ``` i = i0 + n * i_step j = j0 + n * j_step p = p0 + n * p_step ``` 验证器看到的是一个有界的迭代器，而不是一簇相关的循环变量——LLVM IR中的PHI节点。在一个干净的例子中这看起来很棒。然而，在 `-O2` 之后，IR包含了减法、窄计数器、几个...