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

通常，要装载到内核的 BPF 程序是用 C 语言编写的，但是这些程序运行的环境与 C 环境有明显的不同。BPF 虚拟机和相关的验证器为了使 BPF 代码安全运行，进行了越来越多的检查。BPF 的迭代器机制的新增突出了正在增加的功能，以及 BPF 给程序员带来的限制。

在程序加载时，BPF 验证器进行的诸多检查之一是为了确保程序在合理的时间内终止，这个过程需要模拟程序的执行。这个约束使得支持在 BPF 程序中循环成为一个挑战；直到 5.3 版本才开始可能使用循环。即使有了这个新增功能，也难以让验证器确信循环会终止；这导致了一些麻烦，比如新增如 bpf_loop() 等功能，通过将循环逻辑对一些简单情况放入内核的 C 代码中。

但是，并非所有问题都能通过像 bpf_loop() 这样的简单函数解决。在 BPF 程序中，许多循环只是遍历一系列对象，BPF 开发人员希望更便捷地执行这个操作。许多语言内建了一种遍历集合的概念，但是 C 语言没有。正如上面所述，BPF 并不实际是 C；来自 Andrii Nakryiko 的这组补丁，通过向 BPF 虚拟机增加迭代机制，再次强调了这个观点。

在支持迭代特殊类型概念的语言中，通常有一组方法用于实现新的迭代器类型；这些方法可以认为是开始迭代 start iteration、下一项 next item 和结束迭代 finish iteration。首次提出的 BPF 机制也遵循了这种模式。支持迭代的代码必须用真正的 C 语言编写在内核中，并且必须提供四个条件：

  • 首先是表示迭代器本身的结构类型；
  • 结构的大小必须是 8 字节的倍数；
  • 迭代器结构将具有如 bpf_iter_foo 这样的名称；
  • 包含迭代器用于保存其状态所需的所有数据。

new 函数（或构造函数 constructor ）必须称为 bpf_iter_foo_new()。它的第一个参数将是迭代器类型的结构（在 BPF 程序中必须声明和实例化）；它还可以接受任意数量的其他参数。这个函数应该初始化迭代器，然后返回零或者负的错误代码；如果初始化失败，必须仍然只会设置迭代器，以便后续的调用做正确的事情。

“下一项” 函数是 bpf_iter_foo_next()；它将迭代器作为其唯一的参数，并返回下一个元素的指针（无论迭代器支持的是什么类型）。即使只返回一个整数的迭代器也必须返回指向该整数的指针。返回一个 null 指针表示迭代完成 —— 或者发生了某种错误。

bpf_iter_foo_destroy() 函数（或析构函数 destructor）将迭代器结构的指针作为唯一的参数，并返回 void；它将完成迭代，并进行任何必要的清理。

所有这些函数都必须被声明为 kfuncs，并加上一些标志以表明其特殊作用。构造函数必须被标记为 KF_ITER_NEW，下一个函数必须被标记为 KF_ITER_NEXT|KF_ITER_NULL，析构函数必须被标记为 KF_ITER_DESTROY。

有了这种基础设施，验证器就可以对迭代器进行一些检查，首先是构造函数必须在任何其他操作之前被调用的要求。对下一个函数的调用将被检查，以确保程序正在寻找表示迭代结束的 null 结果。验证器确保在结束时调用了析构函数，并且在此之后，迭代器没有被访问。验证器还使用类型信息来进行检查，确保特定的迭代器类型只被传递给一组声明对那种类型进行处理的函数。

BPF 子系统对实现迭代器的 C 代码也有一些要求，包括在何时迭代之后，下一个函数必须返回 null 的规则。由于验证器不知道由迭代器驱动的循环可能运行多少次，因此其强制对 BPF 程序执行的指令数目进行限制的能力会被降低；迭代器必须做出帮助，不让程序无限期地运行。

该补丁组增加了一种机制，强制对迭代器类型（名称必须以 bpf_iter_开始）以及关联函数的命名，这些函数必须通过在迭代器类型名称后添加 _new()，_next() 或 _destroy() 来构造。还要检查每个函数的参数和返回类型；如果检查失败，那么这些函数的注册就会失败。

这个实现的一个好特性是，就验证器来说，迭代器完全是自我描述的。特别是，这意味着，在未来没有必要改变验证器本身来添加新的迭代器类型，只要它们符合这种模式。

作为示例，该系列包含了一个简单的数字迭代器，具体实现可以通过链接进行参看。数字迭代器只是逐个遍历一系列整数。在 BPF 代码中的用法示例看起来像这样：

1
2
3
4
5
6
7
8

struct bpf_iter_num it;
int *v;

bpf_iter_num_new(&it, 2, 5);
while ((v = bpf_iter_num_next(&it))) {
    bpf_printk("X = %d", *v);
}
bpf_iter_num_destroy(&it);

这段代码将执行循环体，并让 *v 的值持有从 2 到 4（包括）的值。

当然，以这种方式进行计数并不是非常激动人心；这已经可以通过 bpf_loop() 做到，或者对于像上述具有常量边界的情况，只需编写一个 for 循环就可以了。期望这个功能在扩展的调度类中有更先进的使用情景，但是在补丁发布中并没有详细说明。预计这将在该系列合并后出现；考虑到现在明显缺乏反对意见，看来这可能很快就会发生。

这组代码已经在 Linux 6.4 内核的 commit 23e403b32 中合入，提交的补丁将其成为 open-coded iterators，别名为 inline iterators。提交的简要说明如下：

在 BPF 世界中增加对开放编码（又名内联）迭代器的支持。这是逐步允许 BPF 程序具有更强大和更少限制的循环和迭代能力的下一个演变。

我们建立了一个框架来实现所有类型的迭代器（例如 cgroup，task，file 等迭代器），但是这个补丁集只实现了数字迭代器，用于实现符合人体工程学的 bpf_for() 样的结构。我们还增加了bpf_for_each()，这是一个通用的类似 foreach 的结构，只要我们坚持使用 bpf_iter_<type>_{new,next,destroy}() 的命名模式（现在我们在内核端强制执行），它将适用于任何类型的开放编码迭代器实现。

原文地址：https://lwn.net/Articles/926041/