本文地址：https://www.ebpf.top/post/bpf_five_loops

1. 前言

本文的主题是在 eBPF 技术中代码如何编写循环。

循环几乎是我们所能接触到的所有编程语言中的通用概念，但在 eBPF 中，它们可能要复杂一些。更不用说，截止到目前 eBPF 提供了5+ 种不同的循环方式 - 那么我们应该选用哪种循环方式以及如何使用呢？本文将给给你提供详细的解答。

2. eBPF 中为什么需要循环？

在编程中使用循环的主要动机很简单 — 降低程序的复杂性，尤其是需要对多个对象上执行特定操作时。 在 eBPF 中，有诸多的场景需要通过循环来实现，如：

  • 循环遍历系统调用 getdents64 中的目录条目
  • 迭代处理网络数据包头头部选项或嵌套头部信息
  • 循环遍历诸多的虚拟内存区域 （VMA）
  • 遍历特定 cgroups 内的进程

以下是 Linux 内核上游中不同循环功能时间线：

loop_timeline

在本文的以下部分中，我们将分别介绍每种实现方法。如果你打算跳过可以直接跳转到 GitHub 存储库中学习和测试。

3. 展开机制 Unrolling

在Linux 内核 v5.3 之前，eBPF 程序无法直接使用循环语句，这是因为循环需要指令前后跳转，这可能导致无限循环或者其他问题，而 BPF 验证器并不能处理这种情况。

在很长一段时间内，能够解决方法是使用 unroll 编译器指令展开循环 #pragma 该指令将它们转换为一系列串行执行的行指令。

bpf unrolling

通过 unroll 的方式简化了多次输入相同行的问题。

但是，那么这种方法有什么问题呢？

除了循环机制不太 “原生” 外，将循环转换为一系列串行指令还会显著增加 eBPF 程序的大小。换句话说，随着循环迭代次数的增加，生成的程序二进制文件的大小将也随着增加。这可能是一个问题，也可能不是问题，具体取决于在循环中执行的操作的复杂程度。

另一个问题是，当循环展开时，程序会受到 eBPF 指令集限制的约束，我们将在下一节中讨论。

4. 有界循环 Bounded Loop

从 Linux 内核 v5.3 开始，eBPF 验证器能够进行前后跟踪分支，将其作为检查所有可能的执行路径过程的一部分。

eBPF 验证器通过构建代表所有可能的执行路径的控制流图 （CFG） 来分析程序，然后跟踪每个路径 — 向前和向后。

有了验证器的加持，eBPF 也开始了对循环的支持，我们称之为 “有界循环”（bounded loops）。

bounded-loops

与展开的方式基本相同，只是移除了 unroll 指令，让代码编写更加自然。

那么这种方法有什么问题呢？

有界循环的主要问题是，除了处理循环之外，eBPF 验证器还需要确保程序保持在指令限制以下。换句话说，eBPF 程序可以执行的指令数量是有限制的，以确保它在合理的时间内完成。

💡在内核版本 5.3 之前，指令限制为 4096。然后在以后的版本中，此限制增加到 1M。早期版本突破限制的方式是使用尾部调用（tail call） 的方式

修订：支持 100 万指令的提交是在 5.2 版本，5.3 开始支持，提交参见 c04c0d2b968a

通过上面的简单示例，你可以通过将循环数 （NUM_LOOPS） 增加到 100万 来轻松达到此限制，这将产生以下错误：

1

BPF program is too large. Processed 1000001 insn

具有更复杂操作的循环需要更少的循环迭代才能超过该限制。

但是为什么甚至有指令限制呢？

eBPF 程序是在内核中执行的的，因此必须在合理的时间范围内释放 CPU，以允许系统执行其他任务。如果 eBPF 程序无法做到这一点，它可能会显着影响系统的性能，这可能导致网络中断、应用程序锁定或系统运行缓慢。

好的，但什么才算是指令呢？

在 eBPF 中，一条指令可以被视为大致等同于单个操作或机器指令。这可能包括：

  • 加载或存储数据（例如，将值加载到 register 中）；
  • 算术运算（例如 counter++）；
  • 比较（例如，i < NUM_LOOPS 在循环条件下）。

5. 循环辅助函数 Loop Helper

有时，我们确实需要在较大的范围内循环迭代，这可能比对有界循环施加的 100 万条指令限制更复杂。为了解决这个问题，内核版本 v5.17 引入了 bpf_loop 辅助函数。

此辅助函数允许最多 ~800 万次迭代，并且不受 eBPF 指令限制的约束，因为循环发生在辅助函数内，因此由内核管理。验证器只需要检查触发一次的回调函数的指令，因为辅助函数还确保循环始终终止，而无需验证器检查每次迭代。

帮助程序函数需要以下输入：

  1. 第一个参数：最大迭代次数（限制为 ~800 万次）；
  2. 第二个参数：为每次迭代调用的回调函数；
  3. 第三个参数 [可选]：允许将数据从主程序传递到回调函数的上下文变量；
  4. 第四个参数 [可选]：一个 “flags” 参数，当前未使用，但包含在未来的潜在用例中。

bpf_loop

6. [数字] 迭代器 Iterators

出于与引入 bpf_loop 辅助程序函数的原因类似的原因，在 Linux v6.4 中，添加了迭代器。更多信息可参考 Linux 6.4：BPF 通用迭代器机制。

迭代器主要目的是提供框架来实现各种迭代器（如 cgroups、tasks、files）。数值迭代器允许我们迭代一系列数字，从而使我们能够创建一个 for 循环。它有点黑客风格，但仍然可行。

这种方法的优点是，验证器不需要像有界循环那样检查每次迭代，也不需要像 bpf_loop 帮助程序那样的回调函数。

每个迭代器类型都有以下函数组成：

  • bpf_iter_<type>_new 函数初始化迭代器；
  • bpf_iter_<type>_next 函数获取下一个元素；
  • bpf_iter_<type>_destroy 迭代器清理函数。

例如，对于数字迭代器，则使用 bpf_iter_num_new、 bpf_iter_num_next 和 bpf_iter_num_destroy 函数。

bpf_iter

基于上些迭代器，libbpf 库提供了bpf_for辅助函数，以更自然的方式编写上述内容：

bpf_for

此外，还有一个 bpf_repeat 辅助函数：

bpf_repeat

上述所有涉及到的代码可以在 loop 代码样例找到。请注意，需要最低 Kernel 版本 v6.4，因为那是引入了数字迭代器。

7. ⭐️ 额外提示：Map 迭代器辅助函数

从 Linux v5.13 开始，我们还可以使用 bpf_for_each_map_elem 辅助函数来迭代 map，而不必为此使用循环。样例代码如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

static long callback_fn(struct bpf_map *map, const void *key, void *value, void *ctx)
{
    bpf_printk("context value: %s\n", *(char **)ctx);
    // delete elements with an odd key
    if (*(__u32 *)key % 2)
        bpf_map_delete_elem(map, key);
    return 0;
}

int program(void *ctx)
{
    /*
		...
    */

    char *context = "This string will pass to every callback call";
    long (*cb_p)(struct bpf_map *, const void *, void *, void *) = &callback_fn;
    bpf_for_each_map_elem(&my_map, cb_p, &context, 0);
}

8. 总结

希望本文能够给你在编写 eBPF 程序的时候，有所帮助。请继续 🐝 -ing！

如果你想更深入学习 eBPF 技术，欢迎加入 “eBPF 进阶群”。

原文地址： https://ebpfchirp.substack.com/p/loops-and-iterators-in-ebpf，有修改和调整

作者：Teodor J. Podobnik 2024.9.22