BPF 图数据结构

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

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

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

简介

BPF 映射 API 一直是暴露各种类型的数据结构以供 BPF 程序使用的主要方式。一些数据结构自然适合映射 API（HASH，ARRAY），其他则不太适合。因此，与后一组数据结构交互的程序对于没有先前 BPF 经验的内核程序员来说可能很难解析。

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

两个这样的数据结构 - linked_list 和 rbtree - 有许多共同的验证细节。由于两者都有“根”（linked_list 为“头”）和“节点”，验证器代码和本文档将通用功能称为“graph_api”、“graph_root”、“graph_node”等。

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

不稳定 API

使用 BPF 映射 API 实现的数据结构历史上一直使用 BPF 辅助函数 - 要么是像 bpf_map_update_elem 这样的标准映射 API 辅助函数，要么是特定于映射的辅助函数。新型图数据结构改为使用 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，具有 struct node_data 的 btf_id 和非零的 ref_obj_id。 因为它持有 n，所以程序拥有 pointee（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 的读取和写入都会被拒绝。 但是，通过利用两个细节，验证器可以做得更好

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

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

    • 由于图节点是用 bpf_obj_new 分配的，并且从根添加/删除涉及修改节点结构的 bpf_{list,rb}_node 字段，因此图节点在任何操作后都将保持在相同的地址。

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

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

详细信息

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

拥有引用

  • 此引用控制 pointee 的生命周期

  • pointee 的所有权必须通过将其传递给某些图 API kfunc 或通过 bpf_obj_drop 来“释放”，bpf_obj_drop 会 free pointee

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

  • 访问 pointee 的内存不会导致页面错误

非拥有引用

  • 此引用不拥有 pointee

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

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

  • 访问 pointee 的内存不会导致页面错误

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

为了防止这种逻辑违规，所有非拥有引用在临界区结束后都会被验证器失效。 这对于确保非拥有引用的“不会导致页面错误”属性是必要的。 因此，如果验证器没有使非拥有引用失效，则访问它将不会导致页面错误。

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

对 rbtree 中的节点的任何引用 _必须_ 是非拥有的，因为树控制着 pointee 的生命周期。 类似地，对不在 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 类型的 kfunc 也必须被视为非拥有引用的失效点。