循环操作是一件奢侈的事情

写过 BPF 程序的开发者大多碰到过一个比较头疼的问题：写了一个循环操作，但是加载的时候 verifier 毫不留情地将其拒绝了。参考文档 [1] 比较好地描述了这个问题。为什么 verifier 要如此排斥循环操作呢 ？原因很简单，就是为了更严格的安全性：verifier 必须保证 BPF 程序的所有操作必须在有限时间（bounded time）内完成。

大多数时候我们写一段代码，其循环语句可能是：

1
2
3

int n = get_loop_times_from_other_conditions();

for (int i = 0; i < n; i++) { /* do stuff*/ }

如上简单的代码，假如 n 是一个变量，那么 verifier 其实很难通过静态分析极其精确得出 for 循环可以在有限时间内结束。在恶意场景下，BPF 程序可以制造出一个无限循环的 loops 对系统造成 DDoS 攻击。因此，为了严格的安全性，verifier 在一开始就禁止使用任何形式的 loops。

为了 work around，BPF 开发者只能将 loops 进行展开，通常是利用 #pragma unroll 的编译器指示将一段循环操作进行展开（当然，更简单的方式就是人为进行循环展开）。

所谓循环展开，其实就是在编译期内将 loops 改写成非循环语句（最好是固定次数的 loops），比如：

1
2
3
4
5
6
7
8
9

SEC("tp/syscalls/sys_enter_write")
int handle_tp(void *ctx)
{
#pragma unroll
    for (int i = 0; i < 100; i++) {
        bpf_printk("Hello");
    }
    return 0;
}

这段代码将会把 for{} 展开为：

1
2
3
4
5

...
bpf_printk("Hello");
bpf_printk("Hello");
bpf_printk("Hello");
...

经过这么一折腾，我们成功地 “骗” 过了 verifier，将 BPF 程序加载进了内核。此时我们可以用 bpftool 查看加载的 BPF代码：

1
2
3
4
5
6
7
8
9

# bpftool prog show
43: tracepoint  name handle_tp  tag 638322ab8648162a  gpl
	loaded_at 2022-05-13T11:02:56+0800  uid 0
	xlated 3216B  jited 2015B  memlock 4096B  map_ids 26
	btf_id 137
	pids bootstrap(34863)
	
# bpftool prog dump xlated id 43
....

此时我们可以看到代码中大量的 bpf_printk() 调用。如果我们再执行：

1
2

# bpftool prog dump xlated id 43 | grep bpf_trace_printk | wc -l
100

非常符合直觉地得到 100。也就是说，原先的 loops 最终转换成了 100 句 bpf_printk() 调用。

但是，循环展开很明显带来了另一个问题：指令数的增加。verifier 对于 BPF 程序的指令数量同样有硬约束（Linux 5.2 内核之前这个约束是 4096 条指令）。所以，虽然我们可以用 unroll 展开循环，但对于循环的整体次数是有较大约束的。

Bounded Loops 的到来

Linux 5.2 之后，内核将 BPF 程序的指令数量大幅提升到了 1 million，这个巨大的提升由此带来了一个改进：verifier 支持 bounded-loops。这意味着，我们在大多数时候将无需使用 #pragma unroll 来展开循环。

针对我们上面的例子，我们可以愉快地去掉 #pragma unroll，同样可以让 verifier 接受我们的 BPF 程序。

verifier 通过模拟 loops 的运行状态，从而判断 loops 是否能够在有限时间内结束运行。但是这个判断并不一定准确，有些时候，哪怕从代码角度来看，loops 是安全的，verifier 可能也会将其拒绝（这时候可能还得适当地使用 unroll 才能绕过这个问题）。

bpf_loop helper 函数

参考文档 [2] 提供了一种更为愉快地处理 BPF 循环操作的方式：引入安全的 bpf_loop helper 函数：

1
2

long bpf_loop(u32 iterations, long (*loop_fn)(u32 index, void *ctx),
    		  void *ctx, u64 flags);

bpf_loop() 给我们一个最显著的特点就是：loops 变得更为智能。bpf_loop() 通过接收一个 static 函数 loop_fn() 和 iterations，可让 loop_fn 执行 iterations 次。其中，loop_fn() 中的 index 代表当前迭代的 index，ctx 是一个指向栈的值，而 flags 当前阶段总为 0。

通过查阅内核代码，我们愉快地发现 5.17 内核已经合并了这个特性。让我们来尝鲜来体验一下。我所使用测试系统是 Ubuntu 22.04，读者可以通过安装 ubuntu 的 release kernel deb 包来升级 kernel。如果不喜欢用烦人的命令行界面，也可以使用 GUI 的 mainline 来更新内核。记得做好版本备份。

我们可以写这么一小段代码（没有什么特别含义，纯粹只是测试一下）测试一下：

 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

#include "vmlinux.h"
#include <bpf/bpf_helpers.h>
#include <bpf/bpf_tracing.h>

char __license[] SEC("license") = "GPL";

/* foo 必须是一个 static 函数，否则会出错 */
static long foo(u32 index, void *ctx)
{
    u64 id = *(u64 *)ctx;
    if (id > 10000) {
        bpf_printk("[%d] hello, its pid is > 10000", index);
    } else {
        bpf_printk("[%d] hello, its pid is <= 10000", index);
    }

    return 0;
}

SEC("kprobe/sys_execve")
int BPF_KPROBE(sys_execve)
{
    int loop_times = 2;
    u64 id = bpf_get_current_pid_tgid();
    if (id > 10000) {
        loop_times = 10;
    } else {
        loop_times = 1;
    }

    /* 将 id 传入 foo() 中 */
    bpf_loop(loop_times, foo, &id, 0);
    return 0;
}

编译加载运行，我们可以看到这段代码被 verifier 成功验证通过并执行了！

verifier 的严格与仁慈

verifier 之所以在一开始禁止任何形式的循环操作，本质上是想让所有 BPF 程序一定会在有限时间内结束运行，从而不会在内核中制造一个无限循环。但是，判断程序是否能在有限时间内结束其实是一个停机问题，这在理论上就是不可判定。为了简化这个问题，verifier 一开始非常严格，禁止任何形式的循环操作。

后面，由于 verifier 的改进：可以模拟 loops 的执行状态并判断其 loops 是否可在最大指令数量允许之内的某个最大上界内结束运行。但是，这样的模拟还是存在局限性：交给 verifier 的 BPF 指令太过于底层，丧失了很多编程语言内 High Level 的信息，导致 verifier 有时候并不能有效判断一个 loops 是否安全（哪怕从代码角度来看 loops 是安全的）。

bpf_loop() helper 函数的出现则有效解决了这一问题。它其实提供了一种机制：将 loops 本身从 BPF 代码中剥离，嵌入到内核 BPF 实现之中。这样一来，BPF 开发者写的是没有循环的代码，而最终的循环操作交给内核帮你执行。由此，verifier 日渐 “仁慈” ，而 BPF 开发者也日渐幸福。

参考

  1. Bounded loops in BPF for the 5.3 kernel
  2. A different approach to BPF loops