BPF 图数据结构

本文档描述了新式“图”数据结构（linked_list、rbtree）的实现细节，特别关注验证器对这些数据结构特定语义的实现。

尽管本文档中没有引用任何特定的验证器代码，但本文档假定读者对 BPF 验证器内部、BPF 映射和 BPF 程序编写有一般性了解。

请注意，本文档的目的是描述这些图数据结构的当前状态。此处不作或不暗示语义或 API 的任何稳定性保证。

引言

BPF 映射 API 历来是暴露各种类型数据结构供 BPF 程序使用的主要方式。一些数据结构与映射 API (HASH, ARRAY) 自然契合，而另一些则不然。因此，对于没有 BPF 经验的内核程序员来说，与后一类数据结构交互的程序可能难以理解。

幸运的是，一些曾导致必须使用 BPF 映射语义的限制已不再相关。随着 kfuncs、kptrs 和任意上下文 BPF 分配器的引入，现在可以实现 BPF 数据结构，其 API 和语义与内核其余部分暴露的 API 和语义更接近。

两种此类数据结构——linked_list 和 rbtree——有许多共同的验证细节。因为两者都有“根”（linked_list 的“头”）和“节点”，所以验证器代码和本文档将共同功能称为“graph_api”、“graph_root”、“graph_node”等。

除非另有说明，以下示例和语义适用于这两种图数据结构。

不稳定 API

使用 BPF 映射 API 实现的数据结构历来使用 BPF 辅助函数——无论是标准的映射 API 辅助函数（如 bpf_map_update_elem）还是特定于映射的辅助函数。新式图数据结构则使用 kfuncs 来定义其操作辅助函数。由于 kfuncs 没有稳定性保证，因此这些数据结构的 API 和语义可以以在必要时打破向后兼容性的方式演进。

新数据结构的根类型和节点类型在 uapi/linux/bpf.h 头文件中不透明地定义。

锁

新式数据结构是侵入式的，其定义类似于其原生内核对应物。

struct node_data {
  long key;
  long data;
  struct bpf_rb_node node;
};

struct bpf_spin_lock glock;
struct bpf_rb_root groot __contains(node_data, node);

linked_list 和 rbtree 的“根”类型都期望位于一个 map_value 中，该 map_value 也包含一个 bpf_spin_lock——在上面的示例中，两个全局变量都放置在单个值的 arraymap 中。验证器认为此 spin_lock 与 bpf_rb_root 相关联，因为它们都在同一个 map_value 中，并且在验证操作树的 BPF 程序时将强制要求持有正确的锁。由于此锁检查发生在验证时，因此没有运行时开销。

非拥有引用

动机

考虑以下 BPF 代码

struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n); /* PASSED */

bpf_spin_unlock(&lock);

从验证器的角度来看，从 bpf_obj_new 返回的指针 n 的类型为 PTR_TO_BTF_ID | MEM_ALLOC，其中 btf_id 为 struct node_data 且 ref_obj_id 非零。由于它持有 n，因此程序拥有被指向对象（由 n 指向的对象）的生命周期。BPF 程序必须在退出前传递所有权——要么通过 bpf_obj_drop （它 free 该对象），要么通过 bpf_rbtree_add 将其添加到 tree 中。

（示例中的 ACQUIRED 和 PASSED 注释分别表示“获取所有权”和“传递所有权”的语句）

所有权传递后，验证器应该如何处理 n？如果对象已通过 bpf_obj_drop free，答案很明显：验证器应该拒绝在 bpf_obj_drop 之后尝试访问 n 的程序，因为该对象不再有效。底层内存可能已被重用于其他分配、已解除映射等。

当所有权通过 bpf_rbtree_add 传递给 tree 时，答案就不那么明显了。验证器可以强制执行与 bpf_obj_drop 相同的语义，但这会导致具有有用、常见编码模式的程序被拒绝，例如：

int x;
struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n); /* PASSED */
x = n->data;
n->data = 42;

bpf_spin_unlock(&lock);

对 n->data 的读取和写入都将被拒绝。然而，验证器可以做得更好，利用两个细节：

  • 图数据结构 API 只能在持有与图根关联的 bpf_spin_lock 时使用

  • 两种图数据结构都具有指针稳定性

    • 因为图节点是通过 bpf_obj_new 分配的，并且从根添加/删除涉及操作节点结构的 bpf_{list,rb}_node 字段，所以在任一操作之后，图节点都将保持在相同的地址。

因为任何添加或删除的程序都必须持有相关的 bpf_spin_lock，所以如果我们在该锁所限定的临界区内，我们知道在临界区结束之前，没有其他程序可以添加或删除。这与指针稳定性相结合意味着，在临界区结束之前，即使在用于传递所有权之后，我们也可以通过 n 安全地访问图节点。

验证器将此类引用视为非拥有引用。通过 bpf_obj_new 返回的引用因此被视为拥有引用。这两个术语目前仅在图节点和 API 的上下文中才有意义。

细节

让我们列举两种引用类型的属性。

拥有引用

  • 此引用控制被指向对象的生命周期

  • 被指向对象的所有权必须通过将其传递给某些图 API kfunc 或通过 bpf_obj_drop （其 free 被指向对象）来“释放”

    • 如果在程序结束前未释放，验证器将认为程序无效

  • 访问被指向对象的内存不会发生页面错误

非拥有引用

  • 此引用不拥有被指向对象

    • 它不能用于将图节点添加到图根，也不能通过 bpf_obj_drop free

  • 没有明确的生命周期控制，但可以根据非拥有引用的存在推断有效生命周期（参见下文解释）

  • 访问被指向对象的内存不会发生页面错误

从验证器的角度来看，非拥有引用只能存在于 spin_lock 和 spin_unlock 之间。为什么？在 spin_unlock 之后，另一个程序可以对数据结构执行任意操作，例如通过 bpf_obj_drop 删除和 free。对某个已被删除、free 且通过 bpf_obj_new 重用的内存块的非拥有引用将指向完全不同的东西。或者内存可能消失。

为了防止这种逻辑违反，验证器会在临界区结束后使所有非拥有引用失效。这是确保非拥有引用的“不会页面错误”属性所必需的。因此，如果验证器尚未使非拥有引用失效，访问它就不会发生页面错误。

目前，临界区内不允许使用 bpf_obj_drop，因此如果存在有效的非拥有引用，我们必然处于临界区内，并且可以得出结论，该引用的内存尚未被释放或被释放后重用。

对 rbtree 中节点的任何引用_必须_是非拥有的，因为树控制着被指向对象的生命周期。类似地，对不在 rbtree 中的节点的任何引用_必须_是拥有的。这产生了一个很好的特性：图 API 的添加/删除实现无需检查节点是否已添加（或已删除），因为所有权模型允许验证器通过简单地检查类型来防止这种状态有效。

然而，指针别名对上述“良好特性”提出了一个问题。考虑以下示例：

struct node_data *n, *m, *o, *p;
n = bpf_obj_new(typeof(*n));     /* 1 */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n);        /* 2 */
m = bpf_rbtree_first(&tree);     /* 3 */

o = bpf_rbtree_remove(&tree, n); /* 4 */
p = bpf_rbtree_remove(&tree, m); /* 5 */

bpf_spin_unlock(&lock);

bpf_obj_drop(o);
bpf_obj_drop(p); /* 6 */

假设在程序运行之前树是空的。如果我们在此处使用上面注释中的数字跟踪验证器状态变化：

  1. n 是一个拥有引用

  2. n 是一个非拥有引用，它已被添加到树中

  3. n 和 m 是非拥有引用，它们都指向同一个节点

  4. o 是一个拥有引用，n 和 m 是非拥有引用，它们都指向同一个节点

  5. o 和 p 是拥有引用，n 和 m 是非拥有引用，它们都指向同一个节点

  6. 发生了双重释放，因为 o 和 p 指向同一个节点，并且 o 在前一条语句中已被 free

状态 4 和 5 违反了我们的“良好特性”，因为存在指向不在 rbtree 中的节点的非拥有引用。由于此违反，语句 5 将尝试移除一个已移除的节点。状态 6 是危险的双重释放。

我们至少应该防止状态 6 的发生。如果我们也无法阻止状态 5，那么我们必须放弃我们的“良好特性”，并在运行时检查节点是否已被移除。

我们通过泛化 bpf_spin_unlock 的“使非拥有引用失效”行为并在 bpf_rbtree_remove 之后进行类似的失效处理来防止这两者。这里的逻辑是，任何图 API kfunc，如果它：

  • 接受一个任意节点参数

  • 将其从数据结构中移除

  • 返回对移除节点的拥有引用

都可能导致某个其他非拥有引用指向同一节点的状态。因此，remove 类型的 kfuncs 也必须被视为非拥有引用失效点。