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

写过 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 程序。

verfier 通过模拟 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