BPF Verifier bpf_patch_insn_data 当前实现分析

本文最后更新于：2026年1月22日 早上

BPF Verifier bpf_patch_insn_data 当前实现分析

概述

本文档详细分析 Linux 内核主线代码中 bpf_patch_insn_data() 函数的当前实现，解释为什么它成为 BPF 验证器的主要性能瓶颈（占用约 47% 的验证时间）。

BPF 程序的完整生命周期

在理解为什么需要修补指令之前，先了解 BPF 程序从编写到执行的完整流程：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
┌─────────────────────────────────────────────────────────────────┐
│ 1. 用户空间：编写和编译                                          │
└─────────────────────────────────────────────────────────────────┘
   用户编写 C 代码（使用 libbpf）
        ↓
   Clang/LLVM 编译为 BPF 字节码（.o 文件）
        ↓
   用户空间加载器（bpftool/libbpf）读取字节码
        ↓
   通过 bpf() 系统调用传递给内核

┌─────────────────────────────────────────────────────────────────┐
│ 2. 内核空间：验证和转换（⭐ 修补发生在这里）                     │
└─────────────────────────────────────────────────────────────────┘
   内核接收 BPF 字节码
        ↓
   ┌──────────────────────────────────────┐
   │ BPF Verifier 验证阶段                │
   │ - 检查程序安全性                      │
   │ - 跟踪寄存器状态                      │
   │ - 验证内存访问                        │
   │ - 检查循环和复杂度                    │
   └──────────────────────────────────────┘
        ↓
   ┌──────────────────────────────────────┐
   │ 指令修补阶段（⭐ 性能瓶颈）           │
   │ - convert_ctx_accesses()             │
   │ - fixup_bpf_calls()                  │
   │ - do_misc_fixups()                   │
   │ 每个阶段可能修补数千次                │
   └──────────────────────────────────────┘
        ↓
   验证通过，程序准备就绪
        ↓
   ┌──────────────────────────────────────┐
   │ JIT 编译（可选）                      │
   │ - 将 BPF 字节码编译为本机机器码       │
   │ - 提高执行性能                        │
   └──────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────┐
│ 3. 运行时：执行                                                  │
└─────────────────────────────────────────────────────────────────┘
   BPF 程序附加到内核事件（hook point）
        ↓
   事件触发时执行 BPF 程序
        ↓
   - JIT 模式：执行本机机器码（快）
   - 解释器模式：解释执行 BPF 字节码（慢）

关键阶段说明：

  1. 编译阶段（用户空间）：

    • 用户使用 C 语言编写 BPF 程序
    • Clang/LLVM 编译为 BPF 字节码（类似汇编）
    • 生成 ELF 格式的 .o 文件

  2. 加载阶段（用户空间 → 内核）：

    • 用户空间工具（bpftool/libbpf）解析 .o 文件
    • 通过 bpf(BPF_PROG_LOAD, ...) 系统调用传递给内核
    • 内核接收原始的 BPF 字节码

  3. 验证阶段（内核空间）：

    • Verifier 检查程序的安全性
    • 确保不会崩溃内核或访问非法内存
    • 这个阶段不修改指令，只是分析

  4. 修补阶段（内核空间）⭐ 性能瓶颈所在：

    • 将抽象的 BPF 指令转换为可执行的形式
    • 插入安全检查
    • 优化和重写指令
    • 这个阶段会调用 bpf_patch_insn_data() 数千次

  5. JIT 编译阶段（内核空间，可选）：

    • 将 BPF 字节码编译为本机机器码（x86_64/ARM64 等）
    • 提高运行时性能

  6. 执行阶段（内核空间）：

    • BPF 程序附加到内核 hook 点（如网络包处理、系统调用跟踪等）
    • 事件触发时执行 BPF 程序

为什么修补阶段是瓶颈？

  • 对于简单程序：验证 + 修补可能只需要几毫秒
  • 对于复杂程序（如 pyperf180）：
    • 验证阶段：约 250ms
    • 修补阶段：约 220ms（占 47%） ⭐
    • JIT 编译：约 10ms

修补阶段占用了近一半的加载时间，这就是为什么优化 bpf_patch_insn_data() 如此重要。

为什么 BPF Verifier 需要修补指令？

在上述流程的修补阶段，verifier 需要对验证通过的 BPF 字节码进行转换和增强。修补（patch）指令的主要原因包括：

  1. 上下文访问转换（Context Access Conversion）

    • 用户编写的 BPF 程序使用抽象的上下文结构（如 struct __sk_buff）
    • 内核需要将这些抽象访问转换为实际的内核结构访问
    • 一个简单的字段访问可能需要展开成多条指令

    具体例子：访问网络包数据指针

    1
    2
    3
    4
    5
    // 用户编写的 BPF 代码
    int bpf_prog(struct __sk_buff *skb) {
        void *data = (void *)(long)skb->data;  // 抽象访问
        // ...
    }

    编译后的 BPF 字节码（简化）：

    1
    r1 = *(u32 *)(r1 + offsetof(__sk_buff, data))  // 1 条指令

    Verifier 修补后的实际指令：

    1
    2
    3
    4
    5
    // 需要从实际的 struct sk_buff 中加载
    r2 = *(u64 *)(r1 + offsetof(sk_buff, head))     // 加载 head 指针
    r3 = *(u16 *)(r1 + offsetof(sk_buff, data))     // 加载 data 偏移
    r3 <<= 0                                         // 零扩展
    r1 = r2 + r3                                     // 计算实际地址

    1 条抽象指令 → 4 条实际指令，需要调用 bpf_patch_insn_data() 将 1 条指令替换为 4 条。

    类似的转换还包括：

    • skb->len → 从 sk_buff->len 加载
    • skb->protocol → 从 sk_buff->protocol 加载并转换字节序
    • skb->mark → 从 sk_buff->mark 加载

    一个典型的网络 BPF 程序可能有几十个这样的字段访问，每个都需要修补。

  2. Helper 函数调用修复（Helper Call Fixup）

    • BPF 程序调用 helper 函数时使用的是函数 ID
    • verifier 需要将函数 ID 转换为实际的函数地址
    • 可能需要插入额外的参数检查和转换指令
    • 某些 helper 调用需要内联展开

    具体例子：调用 bpf_map_lookup_elem()

    1
    2
    3
    4
    5
    6
    7
    8
    // 用户编写的 BPF 代码
    struct bpf_map_def my_map = { ... };

    int bpf_prog(struct __sk_buff *skb) {
        int key = 0;
        void *value = bpf_map_lookup_elem(&my_map, &key);
        // ...
    }

    编译后的 BPF 字节码：

    1
    2
    3
    r1 = map_fd                    // map 文件描述符
    r2 = fp - 4                    // key 的栈地址
    call BPF_FUNC_map_lookup_elem  // helper 函数 ID

    Verifier 修补后：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 1. 将 map_fd 转换为内核 map 指针
    r1 = <map_ptr>                 // 直接使用内核指针

    // 2. 参数已经准备好
    r2 = fp - 4

    // 3. 将函数 ID 替换为实际函数地址
    call <bpf_map_lookup_elem_addr>  // 实际函数地址

    // 4. 可能插入返回值检查
    if r0 == 0 goto error          // 空指针检查（某些情况）

    某些 helper 函数还需要更复杂的转换：

    • bpf_probe_read() → 可能内联为多条内存访问指令
    • bpf_get_current_task() → 直接访问 per-CPU 变量
    • bpf_ktime_get_ns() → 可能内联为 RDTSC 指令（x86_64）

  3. 安全检查插入（Security Instrumentation）

    • 插入边界检查指令（防止越界访问）
    • 插入空指针检查
    • 插入除零检查
    • 插入栈溢出检查

    具体例子：数组访问边界检查

    1
    2
    3
    4
    5
    6
    7
    // 用户编写的 BPF 代码
    int bpf_prog(struct __sk_buff *skb) {
        char buf[64];
        int idx = skb->len % 64;
        buf[idx] = 1;  // 数组访问
        // ...
    }

    编译后的 BPF 字节码：

    1
    2
    3
    4
    5
    r1 = *(u32 *)(r1 + offsetof(__sk_buff, len))
    r1 &= 63                       // idx = len % 64
    r2 = fp - 64                   // buf 的地址
    r2 += r1                       // buf + idx
    *(u8 *)(r2 + 0) = 1           // buf[idx] = 1

    Verifier 修补后（插入边界检查）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    r1 = *(u32 *)(r1 + offsetof(__sk_buff, len))
    r1 &= 63

    // ⭐ 插入边界检查（verifier 添加）
    if r1 >= 64 goto error        // 确保 idx < 64

    r2 = fp - 64
    r2 += r1

    // ⭐ 插入栈访问检查（verifier 添加）
    if r2 < fp - 512 goto error   // 确保在栈范围内
    if r2 >= fp goto error

    *(u8 *)(r2 + 0) = 1

    原本 5 条指令 → 修补后 9 条指令

    其他安全检查例子：

    • 除零检查：r1 = r2 / r3 → 插入 if r3 == 0 goto error
    • 空指针检查：r1 = *(u64 *)r2 → 插入 if r2 == 0 goto error
    • 指针运算检查：确保指针运算不会溢出

  4. 优化和重写（Optimization and Rewriting）

    • 常量折叠后的指令替换
    • 死代码消除
    • 跳转优化
    • 尾调用优化

    具体例子：常量折叠和指令优化

    1
    2
    3
    4
    5
    6
    7
    8
    // 用户编写的 BPF 代码
    int bpf_prog(struct __sk_buff *skb) {
        int x = 10 + 20;           // 常量表达式
        if (x > 25) {              // 可以在编译时确定
            return 1;
        }
        return 0;
    }

    编译后的 BPF 字节码：

    1
    2
    3
    4
    5
    6
    7
    8
    r0 = 10
    r0 += 20                       // r0 = 30
    if r0 > 25 goto label_1        // 总是跳转
    r0 = 0
    exit
    label_1:
    r0 = 1
    exit

    Verifier 优化后：

    1
    2
    3
    4
    // 常量折叠 + 死代码消除
    r0 = 1                         // 直接返回 1
    exit
    // 删除了不可达的代码

    原本 6 条指令 → 优化后 2 条指令

    其他优化例子：

    • 跳转链优化：goto A; A: goto B → goto B
    • 无用跳转消除：goto next_insn → 删除
    • ALU 指令简化：r1 = r1 + 0 → 删除
    • 尾调用优化：将函数调用转换为跳转

  5. 架构特定转换（Architecture-Specific Conversion）

    • 某些指令在特定架构上需要不同的实现
    • 32 位 vs 64 位的差异处理
    • 字节序转换

    具体例子：64 位立即数加载

    BPF 指令集中，加载 64 位立即数需要特殊处理：

    1
    2
    // 用户编写的 BPF 代码
    void *ptr = (void *)0x123456789abcdef0ULL;  // 64 位地址

    编译后的 BPF 字节码（BPF_LD_IMM64）：

    1
    2
    // BPF_LD_IMM64 是一个特殊的双字指令
    r1 = 0x123456789abcdef0       // 占用 2 个指令槽

    在某些架构上，verifier 可能需要修补为：

    1
    2
    3
    4
    5
    6
    7
    // x86_64: 可以直接使用
    r1 = 0x123456789abcdef0

    // 32 位架构: 需要分两次加载
    r1 = 0x9abcdef0               // 低 32 位
    r1 <<= 32
    r1 |= 0x12345678              // 高 32 位

    其他架构特定转换：

    • 字节序转换：网络字节序 ↔ 主机字节序

      1
      2
      3
      // 用户代码: ntohs(skb->protocol)
      // 大端架构: 不需要转换
      // 小端架构: 需要插入 bswap 指令

    • 原子操作：不同架构的原子指令实现不同

      1
      2
      3
      // BPF 原子加法
      // x86_64: lock xadd
      // ARM64: ldxr/stxr 循环

    • 除法指令：某些架构没有硬件除法

      1
      2
      3
      // r1 = r2 / r3
      // 有硬件除法: 直接使用 div 指令
      // 无硬件除法: 调用软件除法函数

修补的频率：

  • 简单程序：几十次修补
  • 复杂程序（如 pyperf180）：数千甚至数万次修补
  • 每次修补可能将 1 条指令展开成多条指令

为什么修补是性能瓶颈：

  • 修补操作非常频繁（M 很大）
  • 每次修补都需要移动整个数组（O(N)）
  • 累积效应：O(N*M) 的时间复杂度

关键发现

  • 当前实现使用数组结构存储 BPF 指令
  • 每次修补都需要移动整个数组
  • 时间复杂度为 O(N*M)，其中 N 是指令数，M 是修补次数
  • 对于复杂程序（如 pyperf180），占用 46.99% 的验证时间

当前实现方案

核心流程

位置：kernel/bpf/verifier.c:21304

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
35
36
37
38
39
40
41
42
43
static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, 
                                            u32 off, 
                                            const struct bpf_insn *patch, 
                                            u32 len)
{
    struct bpf_prog *new_prog;
    struct bpf_insn_aux_data *new_data = NULL;

    // 步骤 1: 如果插入多条指令，重新分配 aux_data 数组
    if (len > 1) {
        new_data = vrealloc(env->insn_aux_data,
                           array_size(env->prog->len + len - 1,
                                     sizeof(struct bpf_insn_aux_data)),
                           GFP_KERNEL_ACCOUNT | __GFP_ZERO);
        if (!new_data)
            return NULL;
        env->insn_aux_data = new_data;
    }

    // 步骤 2: 修补指令（核心操作）
    new_prog = bpf_patch_insn_single(env->prog, off, patch, len);
    if (IS_ERR(new_prog)) {
        if (PTR_ERR(new_prog) == -ERANGE)
            verbose(env,
                "insn %d cannot be patched due to 16-bit range\n",
                env->insn_aux_data[off].orig_idx);
        return NULL;
    }
    
    // 步骤 3: 调整辅助数据
    adjust_insn_aux_data(env, new_prog, off, len);
    
    // 步骤 4: 调整子程序起始位置
    adjust_subprog_starts(env, off, len);
    
    // 步骤 5: 调整指令数组映射
    adjust_insn_arrays(env, off, len);
    
    // 步骤 6: 调整 poke 描述符
    adjust_poke_descs(new_prog, off, len);
    
    return new_prog;
}

调用统计

在 verifier.c 中，bpf_patch_insn_data 被调用 32 次，主要在以下场景：

  1. convert_ctx_accesses() - 上下文访问转换
  2. fixup_bpf_calls() - BPF 调用修复
  3. do_misc_fixups() - 其他修复

核心函数详解

1. bpf_patch_insn_single() - 主要瓶颈（占 27.72%）

位置：kernel/bpf/core.c:451

为什么是瓶颈？核心问题是数组插入操作的 O(N) 复杂度。

问题根源：数组中间插入的代价

BPF 程序使用连续数组存储指令：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
原始程序（10 条指令）：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

现在要在位置 3 插入 2 条新指令：
需要将位置 3 之后的所有指令向后移动 2 个位置

步骤 1: 移动指令（memmove）
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ ? │ ? │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
              ↑   ↑
            新空间

步骤 2: 插入新指令
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ A │ B │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
            新指令

移动的指令数 = 10 - 3 = 7 条

关键问题：

  • 每次修补都要移动修补点之后的所有指令
  • 对于 10,000 条指令的程序，在位置 1,000 修补，需要移动 9,000 条指令
  • 如果修补 5,000 次，累积移动次数达到数千万次

代码实现分析

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
                                       const struct bpf_insn *patch, u32 len)
{
    u32 insn_adj_cnt, insn_rest, insn_delta = len - 1;
    const u32 cnt_max = S16_MAX;
    struct bpf_prog *prog_adj;
    int err;

    /* 如果不需要扩展（len == 1），直接替换，O(1) */
    if (insn_delta == 0) {
        memcpy(prog->insnsi + off, patch, sizeof(*patch));
        return prog;
    }

    insn_adj_cnt = prog->len + insn_delta;

    /* 检查是否会导致跳转偏移溢出 */
    if (insn_adj_cnt > cnt_max &&
        (err = bpf_adj_branches(prog, off, off + 1, off + len, true)))
        return ERR_PTR(err);

    /* ⭐ 瓶颈 1: 重新分配程序内存
     * 可能触发内存复制，O(N)
     */
    prog_adj = bpf_prog_realloc(prog, bpf_prog_size(insn_adj_cnt), GFP_USER);
    if (!prog_adj)
        return ERR_PTR(-ENOMEM);

    prog_adj->len = insn_adj_cnt;

    /* 修补分 3 步 */
    insn_rest = insn_adj_cnt - off - len;  // 需要移动的指令数

    /* ⭐⭐⭐ 瓶颈 2: 移动指令数组（最大瓶颈）
     * 时间复杂度: O(insn_rest) = O(N - off)
     * 对于大程序，这是最耗时的操作
     */
    memmove(prog_adj->insnsi + off + len,    // 目标：修补点 + 新指令长度
            prog_adj->insnsi + off + 1,       // 源：修补点 + 1
            sizeof(*patch) * insn_rest);      // 大小：剩余指令数

    /* 复制新指令到修补位置，O(len) */
    memcpy(prog_adj->insnsi + off, patch, sizeof(*patch) * len);

    /* ⭐⭐ 瓶颈 3: 调整所有分支偏移
     * 需要遍历整个程序，O(N)
     * 检查每条跳转指令，调整受影响的偏移
     */
    BUG_ON(bpf_adj_branches(prog_adj, off, off + 1, off + len, false));

    /* 调整行信息，O(line_info_cnt) */
    bpf_adj_linfo(prog_adj, off, insn_delta);

    return prog_adj;
}

性能开销详细分析

假设程序有 N = 10,000 条指令，在位置 off = 3,000 修补，插入 len = 3 条指令：

操作 复杂度 实际操作数 占比 说明
memmove 指令 O(N - off) 7,000 条指令 ~60% 移动修补点后的所有指令
bpf_adj_branches O(N) 10,000 条指令 ~25% 遍历所有指令调整跳转
bpf_prog_realloc O(N) 10,000 条指令 ~10% 可能触发内存复制
memcpy 新指令 O(len) 3 条指令 <1% 复制新指令
bpf_adj_linfo O(L) L 个行信息 ~5% 调整行信息

总时间复杂度：O(N)

累积效应：为什么占 27.72% 的时间？

对于复杂程序（如 pyperf180），假设：

  • 程序长度：N = 10,000 条指令
  • 修补次数：M = 5,000 次
  • 平均修补位置：off_avg = N / 2 = 5,000

每次修补的平均开销：

1
2
平均移动指令数 = (N - off_avg) = 5,000 条
总移动次数 = M × 5,000 = 25,000,000 次指令移动

实际测试数据验证（pyperf180.bpf.o）：

1
2
3
4
5
6
总验证时间: 476.6 ms
bpf_patch_insn_single: 132.0 ms (27.72%)
  ├─ memmove: ~80 ms (60%)     ← 主要瓶颈
  ├─ bpf_adj_branches: ~33 ms (25%)
  ├─ bpf_prog_realloc: ~13 ms (10%)
  └─ 其他: ~6 ms (5%)

为什么 memmove 这么慢？

  1. 内存带宽限制：

    • 每条 BPF 指令 = 8 字节
    • 移动 5,000 条指令 = 40 KB
    • 5,000 次修补 × 40 KB = 200 MB 数据移动
    • 即使内存带宽 10 GB/s，也需要 20 ms

  2. 缓存失效：

    • 大块内存移动导致 CPU 缓存失效
    • 每次 memmove 都要重新加载数据到缓存
    • 缓存未命中的代价很高

  3. 非对齐访问：

    • memmove 可能涉及非对齐内存访问
    • 在某些架构上性能更差

为什么 bpf_adj_branches 也很慢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, u32 end_old, u32 end_new, bool probe)
{
    u32 i, insn_cnt = prog->len;
    struct bpf_insn *insn = prog->insnsi;
    
    /* ⭐ 遍历所有指令 */
    for (i = 0; i < insn_cnt; i++, insn++) {
        u8 code = insn->code;
        
        /* 跳过非跳转指令 */
        if ((BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32) ||
            BPF_OP(code) == BPF_CALL || BPF_OP(code) == BPF_EXIT)
            continue;
        
        /* 检查跳转目标是否受影响 */
        if (跳转目标在修补范围内) {
            /* 调整跳转偏移 */
            insn->off += delta;
        }
    }
}

为什么慢：

  • 必须遍历所有指令（O(N)）
  • 每次修补都要遍历一次
  • M 次修补 = M × N 次指令检查
  • 5,000 × 10,000 = 50,000,000 次检查

瓶颈总结

bpf_patch_insn_single 占 27.72% 的原因：

  1. memmove 指令数组（~60% 的时间）：

    • 每次修补移动数千条指令
    • 累积移动数千万次
    • 内存带宽和缓存失效

  2. bpf_adj_branches（~25% 的时间）：

    • 每次修补遍历整个程序
    • 累积遍历数千万次
    • 分支预测失败

  3. bpf_prog_realloc（~10% 的时间）：

    • 频繁的内存重新分配
    • 可能触发内存复制

  4. 累积效应：

    • 单次修补不慢（几微秒）
    • 但修补次数太多（数千次）
    • O(N) × M 次 = O(N×M) 总复杂度

核心问题：数组结构不适合频繁的中间插入操作！

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
                                       const struct bpf_insn *patch, u32 len)
{
    u32 insn_adj_cnt, insn_rest, insn_delta = len - 1;
    const u32 cnt_max = S16_MAX;
    struct bpf_prog *prog_adj;
    int err;

    /* 如果不需要扩展，直接替换 */
    if (insn_delta == 0) {
        memcpy(prog->insnsi + off, patch, sizeof(*patch));
        return prog;
    }

    insn_adj_cnt = prog->len + insn_delta;

    /* 检查是否会导致跳转偏移溢出 */
    if (insn_adj_cnt > cnt_max &&
        (err = bpf_adj_branches(prog, off, off + 1, off + len, true)))
        return ERR_PTR(err);

    /* 重新分配程序内存 ⭐ 可能触发内存复制 */
    prog_adj = bpf_prog_realloc(prog, bpf_prog_size(insn_adj_cnt), GFP_USER);
    if (!prog_adj)
        return ERR_PTR(-ENOMEM);

    prog_adj->len = insn_adj_cnt;

    /* 修补分 3 步：
     * 1) 移动后面的指令，为新指令腾出空间
     * 2) 注入新指令
     * 3) 调整分支偏移
     */
    insn_rest = insn_adj_cnt - off - len;

    /* ⭐⭐⭐ 主要瓶颈：移动修补点后的所有指令 */
    memmove(prog_adj->insnsi + off + len,    // 目标位置
            prog_adj->insnsi + off + 1,       // 源位置
            sizeof(*patch) * insn_rest);      // 移动大小 = (程序长度 - 修补位置 - 新指令数)

    /* 复制新指令到修补位置 */
    memcpy(prog_adj->insnsi + off, patch, sizeof(*patch) * len);

    /* ⭐⭐ 第二大瓶颈：调整所有分支偏移（遍历整个程序） */
    BUG_ON(bpf_adj_branches(prog_adj, off, off + 1, off + len, false));

    /* 调整行信息 */
    bpf_adj_linfo(prog_adj, off, insn_delta);

    return prog_adj;
}

性能开销：

  • memmove：O(N) - 移动修补点后的所有指令
  • bpf_adj_branches：O(N) - 遍历所有指令调整跳转
  • bpf_prog_realloc：O(N) - 可能触发内存复制

2. adjust_insn_aux_data() - 第三大瓶颈

位置：kernel/bpf/verifier.c:21221

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
static void adjust_insn_aux_data(struct bpf_verifier_env *env,
                                 struct bpf_prog *new_prog, u32 off, u32 cnt)
{
    struct bpf_insn_aux_data *data = env->insn_aux_data;
    struct bpf_insn *insn = new_prog->insnsi;
    u32 old_seen = data[off].seen;
    u32 prog_len;
    int i;

    /* 调整 OFF 位置的 aux info */
    data[off].zext_dst = insn_has_def32(insn + off + cnt - 1);

    if (cnt == 1)
        return;
    
    prog_len = new_prog->len;

    /* ⭐⭐⭐ 第三大瓶颈：移动 aux_data 数组 */
    memmove(data + off + cnt - 1, data + off,
            sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
    
    /* 初始化新插入的 aux_data */
    memset(data + off, 0, sizeof(struct bpf_insn_aux_data) * (cnt - 1));
    for (i = off; i < off + cnt - 1; i++) {
        /* 扩展 insni[off] 的 seen 计数到修补范围 */
        data[i].seen = old_seen;
        data[i].zext_dst = insn_has_def32(insn + i);
    }
}

性能开销：

  • memmove：O(N) - 移动修补点后的所有辅助数据
  • 循环初始化：O(cnt) - 通常 cnt 较小

3. 其他 adjust 函数

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
35
36
37
38
/* 调整子程序起始位置 - O(S)，S = 子程序数量 */
static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len)
{
    int i;
    if (len == 1)
        return;
    /* 遍历所有子程序 */
    for (i = 0; i <= env->subprog_cnt; i++) {
        if (env->subprog_info[i].start <= off)
            continue;
        env->subprog_info[i].start += len - 1;
    }
}

/* 调整指令数组映射 - O(A)，A = 指令数组映射数量 */
static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 off, u32 len)
{
    int i;
    if (len == 1)
        return;
    for (i = 0; i < env->insn_array_map_cnt; i++)
        bpf_insn_array_adjust(env->insn_array_maps[i], off, len);
}

/* 调整 poke 描述符 - O(P)，P = poke 描述符数量 */
static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
{
    struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
    int i, sz = prog->aux->size_poke_tab;
    struct bpf_jit_poke_descriptor *desc;

    for (i = 0; i < sz; i++) {
        desc = &tab[i];
        if (desc->insn_idx <= off)
            continue;
        desc->insn_idx += len - 1;
    }
}

性能瓶颈分析

1. 时间复杂度分析

假设一个程序有 N 条指令，需要进行 M 次修补：

1
2
3
4
5
6
7
第 1 次修补：移动 N 条指令
第 2 次修补：移动 N+1 条指令
第 3 次修补：移动 N+2 条指令
...
第 M 次修补：移动 N+M-1 条指令

总操作数 = N*M + M*(M-1)/2 ≈ O(N*M + M²)

对于复杂程序（如 pyperf180）：

  • N ≈ 10,000 条指令
  • M ≈ 5,000 次修补
  • 总操作数 ≈ 50,000,000 次指令移动

2. 每次修补的操作开销

操作 复杂度 占比 说明
memmove 指令数组 O(N) 27.72% 移动修补点后的所有指令
bpf_adj_branches O(N) ~10% 遍历所有指令调整跳转
memmove aux_data O(N) 13.43% 移动修补点后的所有辅助数据
vrealloc aux_data O(N) 5.84% 重新分配并复制（len > 1 时）
bpf_prog_realloc O(N) ~5% 重新分配程序内存
adjust_subprog_starts O(S) <1% S = 子程序数量
adjust_insn_arrays O(A) <1% A = 指令数组映射数量
adjust_poke_descs O(P) <1% P = poke 描述符数量

总复杂度：O(N) 每次修补

3. 实际性能数据（Baseline 测试）

测试程序：pyperf180.bpf.o
内核版本：6.19.0-rc5
验证时间：0.4766 ± 0.0150 秒

perf 热点分析：

1
2
3
4
5
6
7
8
9
10
11
12
bpf_patch_insn_data: 46.99% 总验证时间 ⭐⭐⭐
├─ bpf_patch_insn_single: 27.72% (59%)
│  ├─ memmove (指令数组): 占大部分
│  └─ bpf_adj_branches: 遍历所有指令
├─ memmove (aux_data): 13.43% (28.6%)
└─ vrealloc: 5.84% (12.4%)

do_check: 45.89%
├─ check_helper_call: 9.58%
├─ check_cond_jmp_op: 7.39%
├─ states_equal: 7.06%
└─ ...

关键发现：

  • bpf_patch_insn_data 占用近 47% 的验证时间
  • 这证实了 Eduard Zingerman 的分析（他说约 40%）
  • 这是最大的性能瓶颈

4. 历史性能数据（Jiong Wang 2019）

极端大规模修补场景的测试数据：

修补次数 当前耗时 理想耗时 提升比例
15,000 3秒 <0.5秒 83%
45,000 29秒 <1秒 97%
95,000 125秒 <2秒 98%
195,000 712秒 <5秒 99%
1,000,000 5100秒 (1.4小时) <30秒 99%+

为什么这么设计？

历史原因

  1. BPF verifier 最初设计时：

    • 程序规模较小（几百条指令）
    • 修补次数不多（几十次）
    • 简单的数组实现足够用

  2. 数组实现的优势：

    • 简单直观，易于理解
    • 随机访问 O(1)
    • 内存连续，缓存友好

现在的问题

  1. 现代 BPF 程序越来越复杂：

    • 指令数可达数万条
    • 修补次数可达数千甚至数万次
    • O(N*M) 复杂度变得无法接受

  2. 数组实现的劣势：

    • 插入/删除操作 O(N)
    • 频繁的内存移动
    • 无法批量处理

具体例子：为什么这么慢？

场景：10,000 条指令的程序，需要修补 5,000 次

当前实现（数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
修补位置 1000：
  - memmove 9,000 条指令
  - 调整 10,000 条指令的跳转
  - memmove 9,000 个 aux_data

修补位置 2000：
  - memmove 8,001 条指令
  - 调整 10,001 条指令的跳转
  - memmove 8,001 个 aux_data

... (重复 5,000 次)

总操作数：
  - 指令移动：约 50,000,000 次
  - 跳转调整：约 50,000,000 次遍历
  - aux_data 移动：约 50,000,000 次

预计时间：数十秒

理想实现（链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
修补阶段（5,000 次）：
  - 每次修补：链表插入 O(1)
  - 总操作：5,000 次插入

线性化阶段（1 次）：
  - 遍历链表：O(N) = 10,000
  - 分配数组：O(N) = 10,000
  - 调整跳转：O(N) = 10,000

总操作数：约 35,000 次

预计时间：1-2 秒

性能提升：20-40 倍

为什么占 47% 的验证时间？

原因分析

  1. 修补是最频繁的操作：

    • convert_ctx_accesses：每个上下文访问都可能修补
    • fixup_bpf_calls：每个 helper 调用都可能修补
    • do_misc_fixups：各种优化和修复

  2. 每次修补都是 O(N) 操作：

    • 移动指令数组
    • 调整跳转偏移
    • 移动辅助数据

  3. 累积效应：

    • 对于复杂程序，M 很大
    • O(N*M) 的累积效应非常明显
    • 最终占据近一半的验证时间

与其他操作的对比

1
2
3
4
5
6
7
8
9
10
验证时间分布（pyperf180.bpf.o）：

bpf_patch_insn_data: 46.99% ⭐ 最大瓶颈
do_check: 45.89%
  ├─ check_helper_call: 9.58%
  ├─ check_cond_jmp_op: 7.39%
  ├─ states_equal: 7.06%
  ├─ copy_verifier_state: 4.71%
  └─ 其他: 17.15%
其他: 7.12%

关键观察：

  • bpf_patch_insn_data 单个函数占用 47%
  • do_check 包含多个子函数，总共占用 46%
  • 优化 bpf_patch_insn_data 的收益最明显

优化方向

当前实现的核心问题

  1. ✅ 简单直观：数组实现，易于理解
  2. ❌ O(N*M) 复杂度：每次修补都要移动整个数组
  3. ❌ 频繁内存操作：大量 memmove 和 realloc
  4. ❌ 重复遍历：每次都要调整跳转、子程序等
  5. ❌ 无法批量处理：一次只能修补一个位置

可能的优化方案

方案 1：批量修补 API

核心思路：将多个修补操作收集起来，排序后一次性处理，减少 memmove 次数。

当前问题：

1
2
3
4
5
修补位置 100：移动 9,900 条指令
修补位置 200：移动 9,801 条指令
修补位置 300：移动 9,703 条指令
...
总移动次数：数千万次

批量修补方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
收集所有修补操作：
  - 位置 100：插入 2 条指令
  - 位置 200：插入 3 条指令
  - 位置 300：插入 1 条指令
  - ...

按位置从后往前排序（重要！）：
  - 位置 300：插入 1 条指令
  - 位置 200：插入 3 条指令
  - 位置 100：插入 2 条指令

从后往前依次修补：
  1. 位置 300：移动 9,700 条指令（一次）
  2. 位置 200：移动 9,800 条指令（一次）
  3. 位置 100：移动 9,900 条指令（一次）

总移动次数：只移动 3 次，而不是每个位置都移动一次

API 设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 批量修补条目 */
struct bpf_patch_entry {
    u32 off;                    // 修补位置
    struct bpf_insn *patch;     // 新指令
    u32 len;                    // 新指令数量
};

/* 批量修补上下文 */
struct bpf_patch_batch {
    struct bpf_patch_entry *entries;  // 修补条目数组
    u32 count;                         // 条目数量
    u32 capacity;                      // 容量
};

/* 添加修补操作到批次 */
int bpf_patch_batch_add(struct bpf_patch_batch *batch, 
                        u32 off, 
                        const struct bpf_insn *patch, 
                        u32 len);

/* 一次性应用所有修补 */
struct bpf_prog *bpf_patch_batch_apply(struct bpf_verifier_env *env, 
                                       struct bpf_patch_batch *batch);

实现步骤：

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
struct bpf_prog *bpf_patch_batch_apply(struct bpf_verifier_env *env, 
                                       struct bpf_patch_batch *batch)
{
    // 1. 按位置从大到小排序（从后往前）
    sort(batch->entries, batch->count, compare_by_offset_desc);
    
    // 2. 计算最终程序长度
    u32 total_new_len = env->prog->len;
    for (i = 0; i < batch->count; i++)
        total_new_len += batch->entries[i].len - 1;
    
    // 3. 一次性分配足够的内存
    new_prog = bpf_prog_realloc(env->prog, total_new_len, GFP_USER);
    
    // 4. 从后往前依次修补（关键！）
    for (i = 0; i < batch->count; i++) {
        entry = &batch->entries[i];
        // 移动指令
        memmove(new_prog->insnsi + entry->off + entry->len,
                new_prog->insnsi + entry->off + 1,
                ...);
        // 复制新指令
        memcpy(new_prog->insnsi + entry->off, entry->patch, ...);
    }
    
    // 5. 只调整一次跳转偏移（而不是每次修补都调整）
    bpf_adj_branches_batch(new_prog, batch);
    
    // 6. 调整 aux_data、subprog 等（一次性）
    adjust_all_metadata(env, new_prog, batch);
    
    return new_prog;
}

为什么从后往前修补？

关键原因：保持前面位置的偏移不变！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
原始程序：
位置: 0   100   200   300   400
      |    |     |     |     |
      [====|=====|=====|=====|====]

如果从前往后修补：
1. 修补位置 100 → 位置 200 变成 202，位置 300 变成 302
2. 修补位置 202 → 位置 302 变成 305
3. 修补位置 305 → 需要不断更新后续位置！

如果从后往前修补：
1. 修补位置 300 → 位置 100、200 不变
2. 修补位置 200 → 位置 100 不变
3. 修补位置 100 → 完成！

性能提升分析：

假设 5,000 次修补操作：

操作 当前实现 批量修补 提升
memmove 次数 5,000 次 1 次（或少量） 99%
bpf_adj_branches 5,000 次 1 次 99%
内存分配 5,000 次 1 次 99%

但实际提升只有 10-15%，为什么？

  1. 不是所有修补都能批量化：

    • 某些修补依赖前面修补的结果
    • 只能批量化同一阶段的修补（如 convert_ctx_accesses）

  2. 批量化的开销：

    • 需要排序（O(M log M)）
    • 需要额外的内存存储批次
    • 需要更复杂的偏移计算

  3. 实际可批量化的比例：

    • 假设只有 30% 的修补可以批量化
    • 5,000 次修补 → 1,500 次可批量，3,500 次仍然单独
    • 提升：1,500 / 5,000 = 30% 的修补操作被优化
    • 整体提升：30% × 47% = 14%

优势：

  • 改动相对较小，不需要重构核心数据结构
  • 可以逐步实施（先优化一个阶段，再扩展到其他阶段）
  • 风险可控，容易测试

劣势：

  • 提升有限（10-15%）
  • 不能解决根本问题（数组结构）
  • 实现仍然有一定复杂度

方案 2：链表 + 延迟线性化

核心思路：使用链表存储指令，修补时只需链表插入（O(1)），最后统一线性化为数组。

当前问题：数组插入 = O(N)，M 次修补 = O(N×M)

链表方案：链表插入 = O(1)，M 次修补 = O(M)，最后线性化 = O(N)，总计 = O(M + N)

方案 3：Gap Buffer（间隙缓冲区）

核心思路：在数组中维护一个”间隙”（gap），修补操作在间隙处进行，只需移动间隙而不是整个数组。

数据结构：

1
2
3
4
5
6
7
struct bpf_gap_buffer {
    struct bpf_insn *buffer;     /* 指令缓冲区 */
    int capacity;                 /* 总容量 */
    int gap_start;                /* 间隙起始位置 */
    int gap_end;                  /* 间隙结束位置 */
    int length;                   /* 实际指令数（不含间隙） */
};

工作原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
初始状态（间隙在开头）：
[____gap____][0][1][2][3][4][5][6][7][8][9]
 ↑          ↑
gap_start  gap_end

在位置 3 修补（移动间隙到位置 3）：
[0][1][2][____gap____][3][4][5][6][7][8][9]
         ↑          ↑
    gap_start  gap_end

插入新指令（在间隙中插入）：
[0][1][2][A][B][C][__gap__][3][4][5][6][7][8][9]
                  ↑       ↑
             gap_start  gap_end

性能分析：

  • 单次修补：O(|new_pos - gap_pos|) - 移动间隙的代价
  • 如果修补位置集中：接近 O(1)
  • 如果修补位置分散：退化为 O(N)
  • 平均情况：O(N/2) 每次修补

优势：

  • 实现相对简单（比链表简单）
  • 内存连续，缓存友好
  • 如果修补位置有局部性，性能很好

劣势：

  • 最坏情况仍是 O(N×M)
  • 需要预分配额外空间（间隙）
  • 不如链表彻底

适用场景：

  • 修补位置有局部性（如连续修补）
  • 不想引入链表的复杂性
  • 作为过渡方案

方案 4：Rope（绳索）数据结构

核心思路：使用平衡树（如 B-tree）存储指令块，每个节点存储一小段连续指令。

数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
struct bpf_rope_node {
    struct bpf_rope_node *left, *right;
    struct bpf_insn *insns;      /* 指令块 */
    int count;                    /* 指令数 */
    int weight;                   /* 左子树的总指令数 */
    int height;                   /* 树高度（用于平衡） */
};

struct bpf_rope {
    struct bpf_rope_node *root;
    int total_count;
};

工作原理：

1
2
3
4
5
6
7
8
9
10
11
12
        Root (weight=5)
       /              \
   Node1 (5条)      Node2 (weight=3)
   [0][1][2][3][4]  /              \
               Node3 (3条)      Node4 (2条)
               [5][6][7]        [8][9]

在位置 6 插入 3 条指令：
1. 找到位置 6（在 Node3 中）
2. 分裂 Node3 为 [5][6] 和 [7]
3. 插入新节点 [A][B][C]
4. 重新平衡树

性能分析：

  • 单次修补：O(log N) - 树的高度
  • M 次修补：O(M log N)
  • 线性化：O(N) - 遍历树

优势：

  • 理论上最优：O(M log N + N)
  • 支持高效的随机访问
  • 可以支持更多操作（如删除、查询）

劣势：

  • 实现非常复杂（需要平衡树算法）
  • 内存开销大（树节点 + 指针）
  • 缓存不友好（指针跳转）
  • 过度设计（对 BPF verifier 来说）

适用场景：

  • 需要频繁随机访问
  • 需要支持复杂操作
  • 性能要求极高

方案 5：分块数组（Chunked Array）

核心思路：将指令分成固定大小的块，修补时只需移动块内的指令。

数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
#define CHUNK_SIZE 256  /* 每块 256 条指令 */

struct bpf_chunk {
    struct bpf_insn insns[CHUNK_SIZE];
    int count;                    /* 实际指令数 */
    struct bpf_chunk *next;
};

struct bpf_chunked_array {
    struct bpf_chunk *head;
    int chunk_count;
    int total_count;
};

工作原理：

1
2
3
4
5
6
7
Chunk 0 (256条)  Chunk 1 (256条)  Chunk 2 (100条)
[0...255]    →   [256...511]  →   [512...611]

在位置 300 修补（在 Chunk 1 中）：
1. 找到 Chunk 1
2. 只需移动 Chunk 1 内的指令（256 - 44 = 212 条）
3. 如果 Chunk 1 满了，分裂为两个 Chunk

性能分析：

  • 单次修补：O(CHUNK_SIZE) - 最多移动一个块
  • M 次修补：O(M × CHUNK_SIZE)
  • 如果 CHUNK_SIZE = 256，比 O(N) 快很多

优势：

  • 实现简单（比链表简单）
  • 性能可预测
  • 内存局部性好（块内连续）
  • 可以调整 CHUNK_SIZE 平衡性能和内存

劣势：

  • 不如链表彻底（仍需移动）
  • 需要选择合适的 CHUNK_SIZE
  • 块之间需要链表连接

适用场景：

  • 折中方案（性能 vs 复杂度）
  • 不想引入完整链表
  • 作为渐进式优化

方案 6：Copy-on-Write（写时复制）+ 版本链

核心思路：每次修补创建新版本，使用版本链记录变化，最后合并。

数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
struct bpf_patch_delta {
    u32 offset;                   /* 修补位置 */
    struct bpf_insn *patch;       /* 新指令 */
    u32 len;                      /* 新指令数 */
    struct bpf_patch_delta *next;
};

struct bpf_versioned_prog {
    struct bpf_prog *base;        /* 基础版本 */
    struct bpf_patch_delta *deltas;  /* 修补链 */
    int delta_count;
};

工作原理：

1
2
3
4
5
6
7
8
Base: [0][1][2][3][4][5][6][7][8][9]

Delta 1: offset=3, patch=[A][B], len=2
Delta 2: offset=7, patch=[C], len=1
Delta 3: offset=1, patch=[D][E][F], len=3

最后合并：
[0][D][E][F][1][2][A][B][3][4][5][6][C][7][8][9]

性能分析：

  • 单次修补：O(1) - 只记录 delta
  • M 次修补：O(M)
  • 合并：O(N + M) - 应用所有 delta

优势：

  • 修补阶段极快（O(1)）
  • 可以回滚（保留历史版本）
  • 可以批量优化 delta

劣势：

  • 合并阶段复杂（需要处理重叠）
  • 内存开销大（保存所有 delta）
  • 实现复杂度中等

适用场景：

  • 需要支持回滚
  • 修补次数非常多
  • 可以延迟合并

数据结构对比总结

方案 时间复杂度 空间复杂度 实现复杂度 缓存友好 推荐度
当前数组 O(N×M) O(N) 简单 ✅ 很好 ❌ 太慢
链表 O(M+N) O(N) 中等 ❌ 差 ⭐⭐⭐⭐⭐ 最推荐
Gap Buffer O(N×M/2) O(N+gap) 简单 ✅ 好 ⭐⭐⭐ 折中
Rope O(M log N + N) O(N + 树开销) 很复杂 ❌ 差 ⭐⭐ 过度设计
分块数组 O(M×CHUNK) O(N) 简单 ✅ 较好 ⭐⭐⭐⭐ 不错
COW + 版本链 O(M+N) O(N+M) 中等 ✅ 好 ⭐⭐⭐ 有潜力

详细分析：为什么链表仍是最佳选择？

1. Gap Buffer 的问题

理论：如果修补位置集中，性能接近 O(1)

现实：BPF verifier 的修补位置分散

  • convert_ctx_accesses()：遍历整个程序
  • fixup_bpf_calls()：遍历整个程序
  • do_misc_fixups()：遍历整个程序

结果：间隙需要频繁移动，退化为 O(N×M)

示例：

1
2
3
修补序列：位置 100 → 500 → 200 → 800 → 300
每次都需要移动间隙，累积移动：
|500-100| + |200-500| + |800-200| + |300-800| = 400 + 300 + 600 + 500 = 1800 条指令

2. Rope 的问题

理论：O(M log N) 很优秀

现实：

  • 实现复杂度太高（需要 AVL 树或红黑树）
  • 内存开销大（每个节点需要指针、高度等元数据）
  • 缓存不友好（树节点分散在内存中）
  • 对于 BPF verifier，O(M log N) vs O(M) 差异不大

计算：

  • N = 10,000, M = 5,000
  • Rope: O(5,000 × log 10,000) ≈ O(5,000 × 13) = 65,000
  • 链表: O(5,000 + 10,000) = 15,000
  • 链表仍然快 4 倍，且实现简单得多

3. 分块数组的问题

理论：O(M × CHUNK_SIZE) 比 O(N×M) 好

现实：

  • 仍然需要移动（只是少一些）
  • 需要选择合适的 CHUNK_SIZE（太小：块太多，太大：移动太多）
  • 块之间需要链表连接（引入链表复杂度）

计算：

  • CHUNK_SIZE = 256
  • 平均每次修补移动 128 条指令
  • M = 5,000 次修补
  • 总移动：5,000 × 128 = 640,000 条指令
  • 链表：0 次移动（只有指针操作）

结论：分块数组是折中方案，但不如链表彻底

4. COW + 版本链的问题

理论：修补阶段 O(1)，合并阶段 O(M+N)

现实：

  • 合并阶段需要处理重叠的 delta（复杂）
  • 内存开销大（保存所有 delta）
  • 不需要回滚功能（BPF verifier 不需要）

示例：重叠 delta 处理

1
2
3
4
5
6
7
Delta 1: offset=3, len=2  → [3, 4]
Delta 2: offset=4, len=3  → [4, 5, 6]  ← 与 Delta 1 重叠！

合并时需要：
1. 检测重叠
2. 调整偏移
3. 合并指令

结论：复杂度不值得，链表更简单

混合方案：链表 + 分块优化

核心思路：结合链表和分块的优势

数据结构：

1
2
3
4
5
6
struct bpf_chunk_node {
    struct bpf_chunk_node *next;
    struct bpf_insn insns[CHUNK_SIZE];  /* 固定大小的块 */
    int count;                           /* 实际指令数 */
    int orig_start_idx;                  /* 原始起始索引 */
};

优势：

  • 链表的 O(1) 插入
  • 分块的缓存友好性
  • 减少链表节点数（每个节点存多条指令）

劣势：

  • 实现更复杂
  • 块内仍需移动（如果块满了）
  • 收益有限（链表已经够快）

结论：过度优化，不推荐

最终推荐：链表方案

理由：

  1. 彻底解决问题：

    • O(M+N) vs O(N×M)
    • 理论最优（除了 Rope，但 Rope 太复杂）

  2. 实现复杂度可接受：

    • 比 Rope 简单得多
    • 比 COW 简单
    • 比分块数组略复杂，但收益大得多

  3. 社区认可：

    • 2019 年 Jiong Wang RFC
    • 2019 年 Andrii Nakryiko 建议
    • 历史失败是工程问题，不是方案问题

  4. 性能提升显著：

    • 30-40% 验证时间减少
    • 其他方案提升有限

  5. 无需额外功能：

    • 不需要回滚（COW）
    • 不需要复杂查询（Rope）
    • 只需要高效插入和最后线性化

其他方案的定位：

  • Gap Buffer：如果不想引入链表，可以作为过渡方案（10-15% 提升）
  • 分块数组：同上，折中方案
  • Rope：过度设计，不推荐
  • COW：不需要回滚功能，不推荐

行动建议：

  1. 首选：直接实施链表方案（18 个补丁）
  2. 备选：如果担心风险，先实施 Gap Buffer 或分块数组（2-3 个补丁），但要明确这只是过渡方案
  3. 不推荐：Rope 和 COW（复杂度不值得）

数据结构设计（基于 Andrii Nakryiko 2019 年建议）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 可修补的指令节点（链表节点） */
struct bpf_patchable_insn {
    struct bpf_patchable_insn *next;  // 下一个节点
    struct bpf_insn insn;              // BPF 指令
    int orig_idx;                      // 原始索引（用户程序中的位置）
    int new_idx;                       // 新索引（线性化后的位置，初始为 -1）
};

/* 修补器上下文 */
struct bpf_patcher {
    struct bpf_patchable_insn *head;   // 链表头
    int *orig_to_node;                 // 原始索引 → 节点指针的映射
    int orig_cnt;                      // 原始指令数
    int total_cnt;                     // 当前总指令数（包括新增的）
};

工作流程：

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
35
36
37
阶段 1: 初始化（将数组转换为链表）
原始程序（数组）：
[0] [1] [2] [3] [4] [5] ...

转换为链表：
head → [0] → [1] → [2] → [3] → [4] → [5] → NULL
       ↑     ↑     ↑     ↑     ↑     ↑
    orig_to_node[0..5] 指向对应节点

阶段 2: 修补（链表插入，O(1)）
在位置 2 插入 3 条新指令 [A][B][C]：

1. 找到位置 2 的节点（通过 orig_to_node[2]）
2. 创建新节点 [A][B][C]
3. 链表插入：
   head → [0] → [1] → [2] → [A] → [B] → [C] → [3] → [4] → [5] → NULL
                       ↑
                    orig_to_node[2] 仍指向原始节点 [2]

关键：orig_to_node 映射不变！后续修补仍然能找到正确位置。

阶段 3: 线性化（遍历链表，生成最终数组）
遍历链表，分配 new_idx：
[0]:new_idx=0 → [1]:new_idx=1 → [2]:new_idx=2 → [A]:new_idx=3 
→ [B]:new_idx=4 → [C]:new_idx=5 → [3]:new_idx=6 → [4]:new_idx=7 
→ [5]:new_idx=8

生成最终数组：
[0] [1] [2] [A] [B] [C] [3] [4] [5]

阶段 4: 跳转调整（只需一次）
遍历所有指令，根据 orig_idx → new_idx 映射调整跳转：
if (insn->code == JMP) {
    target_orig_idx = insn->orig_idx + insn->off;
    target_new_idx = orig_to_node[target_orig_idx]->new_idx;
    insn->off = target_new_idx - insn->new_idx;
}

性能对比：

操作 当前实现（数组） 链表方案 提升
单次修补 O(N) memmove O(1) 链表插入 N 倍
M 次修补 O(N×M) O(M) N 倍
跳转调整 M 次，每次 O(N) 1 次，O(N) M 倍
线性化 不需要 1 次，O(N) 新增开销
总复杂度 O(N×M) O(M + N) 显著

实际性能提升（pyperf180，N=10,000, M=5,000）：

  • 当前：O(10,000 × 5,000) = 50,000,000 操作
  • 链表：O(5,000 + 10,000) = 15,000 操作
  • 理论提升：3,333 倍
  • 实际提升：30-40%（因为还有其他开销，如 do_check 占 46%）

为什么 2019 年 Jiong Wang 的链表方案未合入？

  1. 维护者担心风险（Alexei Starovoitov）：

    “tbh sounds scary. We had so many bugs in the patch_insn over years.”

    • patch_insn 历史上有很多 bug
    • 大规模重构容易引入新 bug
    • 影响所有 BPF 程序，后果严重

  2. 实现复杂度高：

    • line info 调整：Jiong 在 RFC 中承认实现困难

      “line info I need some careful implementation and I failed to have clean code for this during linearization”

      • RFC 版本中 line info 处理不完善
      • 线性化阶段的 line info 调整代码不够干净
    • subprog info 调整：需要处理子程序被删除的情况
      • RFC 中这部分实现也不完整
      • 子程序边界调整的边界情况复杂
    • 需要处理各种边界情况
    • 代码审查困难，RFC 代码质量不够高

  3. 测试覆盖困难：

    • 需要大量测试用例
    • 需要伪随机测试验证等价性
    • 难以保证所有场景都正确

  4. 方案分歧：

    • Jiong 提出链表方案
    • Alexei 提出更复杂的基本块方案
    • 讨论转向更彻底的重构，但更复杂

  5. 缺乏持续推动：

    • Jiong 发布 RFC 后没有继续迭代
    • 没有 v2/v3 版本
    • 社区没有其他人接手

  6. 优先级不够：

    • 虽然有性能问题，但不是致命的
    • 大多数程序验证时间可接受
    • 有更紧急的功能需要实现

如果要实现链表方案，需要：

  • 充分的测试覆盖（包括伪随机测试）
  • 渐进式实施（先实现核心，再扩展）
  • 与维护者充分沟通，获得支持
  • 准备好迭代多个版本
  • 证明与现有实现等价

优势：

  • 彻底解决性能问题（30-40% 提升）
  • 理论上最优的方案
  • 有社区讨论基础（2019 年 RFC）

劣势：

  • 实现复杂，风险高
  • 需要大量测试
  • 可能需要数月时间
  • 历史上未成功的先例

方案 3：基本块（Basic Block）方案（Alexei 2022 提出）

  • 目标：使用编译器技术，将程序分割为基本块
  • 预期提升：可能更高，但实现复杂
  • 风险：非常高
  • 状态：仅讨论，未实现

什么是基本块（Basic Block）？

基本块是编译器理论中的概念，指的是一段顺序执行的指令序列，具有以下特点：

  • 单一入口：只能从第一条指令进入
  • 单一出口：只能从最后一条指令退出
  • 顺序执行：中间没有跳转指令（除了最后一条）

基本块示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
程序：
  0: r1 = 10          ← BB1 开始
  1: r2 = 20
  2: r3 = r1 + r2
  3: if r3 > 30 goto 6  ← BB1 结束（跳转）
  4: r4 = r3 * 2      ← BB2 开始
  5: goto 7           ← BB2 结束（跳转）
  6: r4 = r3 / 2      ← BB3 开始和结束（单条指令）
  7: exit             ← BB4 开始和结束

基本块划分：
  BB1: [0, 1, 2, 3]   - 顺序执行，以条件跳转结束
  BB2: [4, 5]         - 顺序执行，以无条件跳转结束
  BB3: [6]            - 单条指令
  BB4: [7]            - 退出指令

Alexei 提出的基本块方案思路：

  1. 分割阶段：将 BPF 程序分割为基本块

    1
    原始程序 → [BB1, BB2, BB3, ..., BBn]

  2. 跳转转换：将相对偏移转换为基本块索引

    1
    2
    原始：if r3 > 30 goto +3  (相对偏移)
    转换：if r3 > 30 goto BB3 (基本块索引)

  3. 修补阶段：在基本块内部修补，无需调整跳转

    1
    2
    3
    4
    修补 BB2 内的指令：
    - 只需要移动 BB2 内的指令
    - 不需要调整其他基本块的跳转
    - 因为跳转目标是基本块索引，不是偏移

  4. 重建阶段：从基本块重建完整程序

    1
    2
    3
    [BB1, BB2, BB3, ...] → 最终程序
    - 计算每个基本块的起始位置
    - 将基本块索引转换回相对偏移

基本块方案的优势：

  1. 修补局部化：

    • 修补只影响单个基本块
    • 不需要移动其他基本块的指令
    • 减少 memmove 的范围

  2. 跳转调整延迟：

    • 修补时不需要调整跳转
    • 只在最后重建时统一调整
    • 避免重复遍历

  3. 更好的缓存局部性：

    • 基本块通常较小
    • 修补操作更集中

基本块方案的劣势：

  1. 实现极其复杂：

    • 需要实现基本块分析算法
    • 需要维护基本块图（Control Flow Graph）
    • 需要处理各种边界情况

  2. 数据结构复杂：

    • 需要维护基本块数组
    • 需要维护跳转映射表
    • 需要处理基本块的分裂和合并

  3. 调试困难：

    • 中间表示更抽象
    • 错误更难定位
    • 测试覆盖困难

  4. 风险极高：

    • 影响 verifier 核心逻辑
    • 容易引入难以发现的 bug
    • 维护成本高

为什么基本块方案未实现？

  1. 过度设计：对于 BPF verifier 的需求来说太复杂
  2. 风险太高：Alexei 自己都说 “sounds scary”
  3. 投入产出比：实现成本远高于预期收益
  4. 有更简单的方案：链表方案已经足够好

对比：链表方案 vs 基本块方案

特性 链表方案 基本块方案
实现复杂度 中等 极高
性能提升 30-40% 可能 40-50%
风险 高 极高
维护成本 中等 很高
社区接受度 有先例（Jiong Wang RFC） 仅讨论
推荐度 可考虑 不推荐

参考资料

  1. 2019年讨论 - Jiong Wang 的链表方案
    https://lore.kernel.org/bpf/CAEf4BzYDAVUgajz4=dRTu5xQDddp5pi2s=T1BdFmRLZjOwGypQ@mail.gmail.com/

  2. 2022年讨论 - Eduard Zingerman 的优化建议
    https://lore.kernel.org/bpf/CAEf4BzY_E8MSL4mD0UPuuiDcbJhh9e2xQo2=5w+ppRWWiYSGvQ@mail.gmail.com/

  3. 2026年反馈 - Eduard 指出 bpf_patch_insn_data 占用 40% 时间
    https://www.spinics.net/lists/kernel/msg6011549.html

  4. Baseline 测试结果
    linux/BASELINE_RESULTS.txt

  5. 历史 Patch 分析
    linux/HISTORICAL_PATCHES_STATUS.txt
    linux/WHY_NOT_MERGED.txt

总结

当前 bpf_patch_insn_data 实现：

  • 使用数组存储指令
  • 每次修补都移动整个数组
  • 时间复杂度 O(N*M)
  • 占用 47% 的验证时间

性能瓶颈根源：

  • memmove 指令数组：27.72%
  • memmove aux_data：13.43%
  • vrealloc：5.84%

优化潜力：

  • 批量修补：10-15% 提升
  • 链表重构：30-40% 提升（对复杂程序）

历史教训：

  • 2019 年 Jiong Wang 的链表方案未合入（风险太高，缺乏持续推动）
  • 2022 年 Alexei 提出基本块方案未实现（过度复杂，风险极高）
  • 基本块方案虽然理论上更优，但实现成本远超收益
  • 需要采用渐进式、低风险的优化策略

推荐的优化路径

基于以上分析和历史教训，必须面对一个现实：

核心问题：数组结构根本不适合频繁的中间插入操作

  • 批量修补 API 只是减少 memmove 次数，但每次仍是 O(N)
  • 无论如何优化，只要使用数组，就绕不开读写和扩容的性能瓶颈
  • 链表方案是唯一能彻底解决问题的方案

方案对比：治标 vs 治本

特性 批量修补 API 链表方案
本质 治标：减少操作次数 治本：改变数据结构
memmove 仍需要，只是次数少 完全避免
单次修补 O(N) O(1)
M 次修补 O(N×M/k)，k=批次数 O(M)
数组读写 仍然频繁 只在最后线性化
数组扩容 仍然需要 只在最后一次
性能提升 10-15%（治标） 30-40%（治本）
根本问题 未解决 已解决

结论：批量修补只是权宜之计，链表方案才是正确方向。

推荐方案：直接实施链表方案

为什么必须选择链表方案？

  1. 这是唯一的根本解决方案：

    • 数组结构的性能瓶颈无法通过小修小补解决
    • 批量修补只是延缓问题，不能解决问题
    • 链表是唯一能将 O(N×M) 降低到 O(M+N) 的方案

  2. 历史失败的原因可以克服：

    • Jiong Wang RFC 失败的主要原因：
      • ❌ line info 实现不完善 → ✅ 可以重新设计
      • ❌ subprog info 处理不完整 → ✅ 可以完善
      • ❌ 缺乏持续推动 → ✅ 我们可以持续投入
      • ❌ 测试覆盖不足 → ✅ 可以补充测试
    • 这些都是工程问题，不是方案本身的问题

  3. 社区已有讨论基础：

    • 2019 年 Jiong Wang RFC
    • 2019 年 Andrii Nakryiko 的改进建议
    • 2022 年 Eduard Zingerman 的讨论
    • 2026 年 Eduard 再次建议优化
    • 社区认可这个方向，只是缺少完善的实现

  4. 投入产出比最高：

    • 批量修补：2 个月，10-15% 提升，但问题仍在
    • 链表方案：6 个月，30-40% 提升，彻底解决
    • 长期看，链表方案的投入产出比更高

实施策略：渐进式链表方案

不要重蹈 Jiong Wang 的覆辙，采用渐进式实施：

阶段 1：核心链表实现（2 个月）

目标：实现基本的链表修补功能，暂不处理复杂场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
第 1-2 周：设计和数据结构
- 定义 bpf_patchable_insn 和 bpf_patcher 结构
- 设计 API 接口
- 编写设计文档

第 3-4 周：核心功能实现
- 实现链表创建（数组 → 链表）
- 实现链表修补（插入节点）
- 实现线性化（链表 → 数组）
- 实现基本的跳转调整

第 5-6 周：基础测试
- 在简单的 BPF 程序上测试
- 验证功能正确性
- 暂不处理 line info、subprog info
- 只验证核心逻辑

第 7-8 周：性能测试和调优
- 在 pyperf180 上测试性能
- 对比 baseline
- 修复性能问题

成功标准：

  • 简单程序验证正确
  • 性能提升 > 20%
  • 为下一阶段打好基础

阶段 2：完善元数据处理（2 个月）

目标：解决 Jiong Wang RFC 中的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
第 9-10 周：line info 处理
- 研究当前 line info 调整逻辑
- 设计链表版本的 line info 调整
- 实现并测试

第 11-12 周：subprog info 处理
- 研究子程序边界调整
- 处理子程序被删除的情况
- 实现并测试

第 13-14 周：其他元数据
- poke descriptors
- insn_array_maps
- 其他辅助数据

第 15-16 周：集成测试
- 运行所有 selftests
- 修复发现的问题
- 确保功能完整

成功标准：

  • 所有元数据正确处理
  • 所有 selftests 通过
  • 无功能回归

阶段 3：测试和优化（1-2 个月）

目标：充分测试，确保可以合入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
第 17-18 周：伪随机测试
- 实现伪随机测试框架
- 验证链表方案与数组方案等价
- 覆盖各种修补场景

第 19-20 周：压力测试
- 测试大规模程序（10 万条指令）
- 测试极端修补场景（10 万次修补）
- 测试内存使用

第 21-22 周：性能优化
- 根据 perf 数据优化热点
- 减少内存分配
- 优化缓存局部性

第 23-24 周：文档和代码审查
- 完善代码注释
- 编写设计文档
- 内部代码审查

成功标准：

  • 通过所有测试
  • 性能提升 30-40%
  • 代码质量高，易于审查

阶段 4：社区提交和迭代（1-2 个月）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
第 25-26 周：准备补丁
- 拆分为合理的补丁系列
- 编写详细的 commit message
- 准备性能数据

第 27-28 周：提交和响应
- 提交到 bpf-next
- 及时响应审查意见
- 准备好迭代多个版本

第 29-30 周：迭代和合入
- 根据反馈修改
- 提交 v2、v3...
- 最终合入

关键成功因素

  1. 解决 RFC 中的具体问题：

    • line info：必须有干净的实现
    • subprog info：必须处理所有边界情况
    • 不能留下未完成的部分

  2. 充分的测试覆盖：

    • 功能测试：所有 selftests
    • 等价性测试：伪随机测试
    • 压力测试：大规模程序
    • 性能测试：详细的 perf 数据

  3. 与维护者充分沟通：

    • 提前发 RFC 征求意见
    • 展示清晰的设计和收益
    • 及时响应审查意见
    • 准备好长期投入

  4. 渐进式实施：

    • 不要一次性提交所有代码
    • 先提交核心功能
    • 再逐步完善
    • 每一步都充分测试

风险和应对

风险 1：实现比预期复杂

  • 应对：渐进式实施，每个阶段都可以独立评估
  • 如果某个阶段遇到困难，可以调整计划

风险 2：维护者不接受

  • 应对：提前沟通，展示清晰的收益数据
  • 强调这是唯一的根本解决方案
  • 参考历史讨论，说明如何解决之前的问题

风险 3：引入新的 bug

  • 应对：充分的测试覆盖
  • 伪随机测试验证等价性
  • 渐进式合入，每一步都验证

风险 4：时间投入过长

  • 应对：6 个月的时间投入是值得的
  • 彻底解决问题，长期收益大
  • 可以分阶段评估，及时调整

为什么不推荐批量修补 API？

虽然批量修补风险更低，但：

  1. 治标不治本：

    • 仍然使用数组，性能瓶颈仍在
    • 只是减少操作次数，不能改变 O(N) 的本质
    • 10-15% 的提升不够显著

  2. 浪费时间：

    • 花 2 个月实现批量修补
    • 发现效果有限，还是要做链表
    • 总共花 8 个月，不如直接花 6 个月做链表

  3. 代码债务：

    • 批量修补的代码最终会被链表方案替换
    • 维护两套代码增加复杂度
    • 不如直接做正确的事情

总结：必须选择链表方案

核心观点：

  • 数组结构的性能瓶颈无法通过小修小补解决
  • 链表方案是唯一能彻底解决问题的方案
  • 历史失败的原因是工程问题，不是方案问题
  • 采用渐进式实施，可以降低风险

行动计划：

  • 直接实施链表方案（6 个月）
  • 渐进式实施，分 4 个阶段
  • 充分测试，确保质量
  • 与社区保持沟通

预期结果：

  • 彻底解决 bpf_patch_insn_data 的性能瓶颈
  • 验证时间减少 30-40%
  • 为 BPF 社区做出重要贡献
  • 建立技术信誉

核心原则：

  1. 做正确的事情，而不是简单的事情
  2. 治本，而不是治标
  3. 长期投入，而不是短期收益
  4. 渐进式实施，降低风险
  5. 充分测试，确保质量

文档版本：v1.0
日期：2026-01-22
作者：Qiliang Yuan realwujing@gmail.com
测试环境：Linux 6.19.0-rc5

Patch Series 规划（18 个补丁）- 复用现有函数名

设计原则

复用现有函数名，修改实现：

  • ✅ 保持 API 兼容性
  • ✅ 减少代码变更
  • ✅ 更容易审查
  • ✅ 更容易理解

可复用的现有函数：

  1. adjust_insn_aux_data() - 调整 aux_data
  2. adjust_subprog_starts() - 调整子程序
  3. adjust_insn_arrays() - 调整指令数组
  4. adjust_poke_descs() - 调整 poke 描述符
  5. bpf_patch_insn_data() - 主入口函数

总览

阶段 补丁数 周期 目标
阶段 1：核心实现 8 1-8 周 链表基础功能 + RFC
阶段 2：元数据处理 6 9-16 周 完整功能 + V1
阶段 3：优化测试 4 17-24 周 性能优化 + 合入

阶段 1：核心链表实现（Patch 1-8）

1. bpf: introduce patchable instruction data structures

文件：include/linux/bpf_verifier.h

内容：定义链表节点和修补器结构（新增）

1
2
3
4
5
6
7
8
9
10
11
struct bpf_patchable_insn {
    struct bpf_patchable_insn *next;
    struct bpf_insn insn;
    int orig_idx, new_idx;
};

struct bpf_patcher {
    struct bpf_patchable_insn *head;
    struct bpf_patchable_insn **orig_to_node;
    int orig_cnt, total_cnt;
};

2. bpf: add patcher initialization and cleanup helpers

文件：kernel/bpf/verifier.c

内容：新增辅助函数（不复用，因为是新概念）

1
2
3
4
5
6
7
8
9
10
11
/* 新增：分配链表节点 */
static __maybe_unused struct bpf_patchable_insn *
alloc_patchable_insn(struct bpf_insn *insn, int orig_idx);

/* 新增：初始化 patcher（将数组转换为链表） */
static __maybe_unused int 
init_patcher(struct bpf_patcher *patcher, struct bpf_prog *prog);

/* 新增：释放 patcher */
static __maybe_unused void 
free_patcher(struct bpf_patcher *patcher);

说明：这些是链表特有的概念，当前代码中不存在对应函数，必须新增。

3. bpf: implement linked list instruction patching

文件：kernel/bpf/verifier.c

内容：新增链表修补函数

1
2
3
4
/* 新增：在链表中修补指令（O(1) 插入操作） */
static __maybe_unused int 
patch_insn_list(struct bpf_patcher *patcher, u32 off, 
                const struct bpf_insn *patch, u32 len);

说明：这是链表修补的核心函数，实现 O(1) 的插入操作，当前代码中不存在对应函数。

4. bpf: implement program linearization

文件：kernel/bpf/verifier.c

内容：新增线性化函数

1
2
3
/* 新增：链表 → 数组（线性化） */
static __maybe_unused struct bpf_prog *
linearize_patcher(struct bpf_patcher *patcher);

说明：将链表转换回数组，这是链表方案特有的步骤，当前代码中不存在对应函数。

5. bpf: implement jump offset adjustment for linked list

文件：kernel/bpf/verifier.c

内容：新增跳转调整函数

1
2
3
/* 新增：调整跳转偏移（链表版本，使用 orig_idx → new_idx 映射） */
static __maybe_unused int 
adjust_branches_list(struct bpf_patcher *patcher, struct bpf_prog *prog);

说明：链表版本的跳转调整，使用 orig_idx → new_idx 映射，与数组版本的 bpf_adj_branches() 逻辑不同，必须新增。

6. bpf: add new bpf_patch_insn_data_list() API

文件：kernel/bpf/verifier.c

内容：实现完整的链表版本主函数，移除前面函数的 __maybe_unused

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
35
36
37
38
39
40
41
/* 新增：链表版本的主函数（临时名称，Patch 7 会整合到 bpf_patch_insn_data） */
static __maybe_unused struct bpf_prog *
bpf_patch_insn_data_list(struct bpf_verifier_env *env,
                        u32 off, const struct bpf_insn *patch, u32 len)
{
    struct bpf_patcher patcher;
    struct bpf_prog *new_prog;
    int ret;
    
    /* 初始化：数组 → 链表 */
    ret = init_patcher(&patcher, env->prog);
    if (ret)
        return NULL;
    
    /* 修补：O(1) 链表插入 */
    ret = patch_insn_list(&patcher, off, patch, len);
    if (ret) {
        free_patcher(&patcher);
        return NULL;
    }
    
    /* 线性化：链表 → 数组 */
    new_prog = linearize_patcher(&patcher);
    if (!new_prog) {
        free_patcher(&patcher);
        return NULL;
    }
    
    /* 调整跳转：只需一次 */
    ret = adjust_branches_list(&patcher, new_prog);
    if (ret) {
        bpf_prog_free(new_prog);
        free_patcher(&patcher);
        return NULL;
    }
    
    /* 清理 */
    free_patcher(&patcher);
    
    return new_prog;
}

注意：

  • 此时移除 Patch 2-5 中函数的 __maybe_unused（因为已被使用）
  • 这个函数本身仍标记 __maybe_unused（Patch 7 才使用）

7. bpf: add CONFIG_BPF_VERIFIER_LINKED_LIST option

文件：kernel/bpf/Kconfig, kernel/bpf/verifier.c

内容：添加编译选项，复用 bpf_patch_insn_data() 函数名

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
35
36
37
// Kconfig
config BPF_VERIFIER_LINKED_LIST
    bool "Use linked list for instruction patching"
    default n

// verifier.c - 复用函数名，切换实现
static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env,
                                            u32 off,
                                            const struct bpf_insn *patch,
                                            u32 len)
{
#ifdef CONFIG_BPF_VERIFIER_LINKED_LIST
    return bpf_patch_insn_data_list(env, off, patch, len);
#else
    /* 保持旧实现 */
    struct bpf_prog *new_prog;
    struct bpf_insn_aux_data *new_data = NULL;
    
    if (len > 1) {
        new_data = vrealloc(env->insn_aux_data, ...);
        if (!new_data)
            return NULL;
        env->insn_aux_data = new_data;
    }
    
    new_prog = bpf_patch_insn_single(env->prog, off, patch, len);
    if (IS_ERR(new_prog))
        return NULL;
    
    adjust_insn_aux_data(env, new_prog, off, len);
    adjust_subprog_starts(env, off, len);
    adjust_insn_arrays(env, off, len);
    adjust_poke_descs(new_prog, off, len);
    
    return new_prog;
#endif
}

关键：

  • 复用 bpf_patch_insn_data() 函数名
  • 通过 #ifdef 切换实现
  • 移除 bpf_patch_insn_data_list() 的 __maybe_unused

8. selftests/bpf: add basic tests

文件：tools/testing/selftests/bpf/prog_tests/verifier_patch_list.c

内容：基础功能测试

阶段 2：元数据处理（Patch 9-14）

9. bpf: refactor adjust_insn_aux_data for linked list

文件：kernel/bpf/verifier.c

内容：复用 adjust_insn_aux_data() 函数名，修改实现

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
#ifdef CONFIG_BPF_VERIFIER_LINKED_LIST

/* 复用函数名，链表版本的实现 */
static void adjust_insn_aux_data(struct bpf_verifier_env *env,
                                 struct bpf_prog *new_prog, u32 off, u32 cnt)
{
    /* 链表版本：在线性化时一次性调整 */
    struct bpf_insn_aux_data *data = env->insn_aux_data;
    struct bpf_insn *insn = new_prog->insnsi;
    u32 prog_len = new_prog->len;
    int i;
    
    /* 使用 orig_idx → new_idx 映射调整 */
    for (i = 0; i < prog_len; i++) {
        /* 根据映射调整 aux_data */
    }
}

#else

/* 保持旧实现 */
static void adjust_insn_aux_data(struct bpf_verifier_env *env,
                                 struct bpf_prog *new_prog, u32 off, u32 cnt)
{
    /* 数组版本：每次修补都调整 */
    struct bpf_insn_aux_data *data = env->insn_aux_data;
    ...
    memmove(data + off + cnt - 1, data + off, ...);
    ...
}

#endif

关键：

  • 复用 adjust_insn_aux_data() 函数名
  • 修改函数实现（链表版本）
  • 保持函数签名不变

10. bpf: add line info adjustment for linked list

文件：kernel/bpf/verifier.c

内容：新增 line info 调整（当前代码中 line info 调整在 bpf_adj_linfo() 中，但在 kernel/bpf/core.c）

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
#ifdef CONFIG_BPF_VERIFIER_LINKED_LIST

/* 新增：line info 调整（链表版本） */
static int adjust_line_info_list(struct bpf_patcher *patcher,
                                 struct bpf_prog *prog)
{
    /* 使用 orig_idx → new_idx 映射调整 line info */
}

/* 在 bpf_patch_insn_data_list() 中调用 */
static struct bpf_prog *bpf_patch_insn_data_list(...)
{
    ...
    new_prog = linearize_patcher(&patcher);
    
    /* 调整 line info */
    ret = adjust_line_info_list(&patcher, new_prog);
    if (ret) {
        bpf_prog_free(new_prog);
        free_patcher(&patcher);
        return NULL;
    }
    ...
}

#endif

说明：当前代码中 bpf_adj_linfo() 在 kernel/bpf/core.c 中，我们需要在 verifier.c 中新增链表版本。

11. bpf: refactor adjust_subprog_starts for linked list

文件：kernel/bpf/verifier.c

内容：复用 adjust_subprog_starts() 函数名

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
#ifdef CONFIG_BPF_VERIFIER_LINKED_LIST

/* 复用函数名，链表版本 */
static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len)
{
    /* 链表版本：使用 orig_idx → new_idx 映射 */
    int i;
    for (i = 0; i <= env->subprog_cnt; i++) {
        /* 根据映射调整子程序起始位置 */
    }
}

#else

/* 保持旧实现 */
static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len)
{
    int i;
    if (len == 1)
        return;
    for (i = 0; i <= env->subprog_cnt; i++) {
        if (env->subprog_info[i].start <= off)
            continue;
        env->subprog_info[i].start += len - 1;
    }
}

#endif

12. bpf: refactor adjust_poke_descs for linked list

文件：kernel/bpf/verifier.c

内容：复用 adjust_poke_descs() 函数名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifdef CONFIG_BPF_VERIFIER_LINKED_LIST

/* 复用函数名，链表版本 */
static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
{
    /* 链表版本：使用映射调整 */
}

#else

/* 保持旧实现 */
static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
{
    struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
    int i, sz = prog->aux->size_poke_tab;
    
    for (i = 0; i < sz; i++) {
        if (tab[i].insn_idx <= off)
            continue;
        tab[i].insn_idx += len - 1;
    }
}

#endif

13. bpf: refactor adjust_insn_arrays for linked list

文件：kernel/bpf/verifier.c

内容：复用 adjust_insn_arrays() 函数名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifdef CONFIG_BPF_VERIFIER_LINKED_LIST

/* 复用函数名，链表版本 */
static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 off, u32 len)
{
    /* 链表版本：使用映射调整 */
}

#else

/* 保持旧实现 */
static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 off, u32 len)
{
    int i;
    if (len == 1)
        return;
    for (i = 0; i < env->insn_array_map_cnt; i++)
        bpf_insn_array_adjust(env->insn_array_maps[i], off, len);
}

#endif

14. selftests/bpf: add comprehensive tests

文件：tools/testing/selftests/bpf/prog_tests/verifier_patch_list.c

内容：测试所有元数据场景

阶段 3：优化和测试（Patch 15-18）

15. selftests/bpf: add equivalence test

文件：tools/testing/selftests/bpf/prog_tests/verifier_patch_equiv.c

内容：伪随机测试，验证等价性

16. selftests/bpf: add stress test

文件：tools/testing/selftests/bpf/prog_tests/verifier_patch_stress.c

内容：大规模测试

17. bpf: optimize memory allocation

文件：kernel/bpf/verifier.c

内容：内存池优化

18. bpf: remove array-based patching implementation

文件：kernel/bpf/Kconfig, kernel/bpf/verifier.c, kernel/bpf/core.c

内容：

  • 删除 CONFIG_BPF_VERIFIER_LINKED_LIST 选项
  • 删除所有 #ifdef / #else 分支
  • 只保留链表实现
  • 删除旧代码（约 300 行）：
    • bpf_patch_insn_single() 及相关函数
    • 数组版本的 adjust_* 函数
  • 保留所有函数名：
    • bpf_patch_insn_data() - 链表实现
    • adjust_insn_aux_data() - 链表实现
    • adjust_subprog_starts() - 链表实现
    • adjust_insn_arrays() - 链表实现
    • adjust_poke_descs() - 链表实现

最终代码：

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
/* 最终只保留链表实现，函数名不变 */
static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env,
                                            u32 off,
                                            const struct bpf_insn *patch,
                                            u32 len)
{
    /* 链表实现 */
    return bpf_patch_insn_data_list(env, off, patch, len);
}

static void adjust_insn_aux_data(struct bpf_verifier_env *env,
                                 struct bpf_prog *new_prog, u32 off, u32 cnt)
{
    /* 链表实现 */
}

static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len)
{
    /* 链表实现 */
}

static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 off, u32 len)
{
    /* 链表实现 */
}

static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
{
    /* 链表实现 */
}

复用函数名总结

函数名 当前存在 操作 说明
bpf_patch_insn_data() ✅ 复用 主入口，通过 #ifdef 切换实现
adjust_insn_aux_data() ✅ 复用 修改实现，使用 orig_idx → new_idx 映射
adjust_subprog_starts() ✅ 复用 修改实现，使用 orig_idx → new_idx 映射
adjust_insn_arrays() ✅ 复用 修改实现，使用 orig_idx → new_idx 映射
adjust_poke_descs() ✅ 复用 修改实现，使用 orig_idx → new_idx 映射
alloc_patchable_insn() ❌ 新增 链表节点分配（链表特有概念）
init_patcher() ❌ 新增 初始化 patcher（数组 → 链表）
free_patcher() ❌ 新增 清理 patcher
patch_insn_list() ❌ 新增 链表修补（O(1) 插入）
linearize_patcher() ❌ 新增 线性化（链表 → 数组）
adjust_branches_list() ❌ 新增 跳转调整（链表版本）
adjust_line_info_list() ❌ 新增 line info 调整（链表版本）
bpf_patch_insn_data_list() ❌ 临时 临时函数名，Patch 18 删除

复用策略：

  • ✅ 5 个核心函数复用：保持 API 兼容性，只修改内部实现
  • ❌ 7 个新增函数：链表特有概念，必须新增
  • 🔄 1 个临时函数：bpf_patch_insn_data_list() 在 Patch 18 会被删除

优势：

  • ✅ 最大化复用现有函数名（5/13 = 38%）
  • ✅ 保持 API 兼容性
  • ✅ 更容易审查（函数名熟悉）
  • ✅ 更容易理解（概念一致）
  • ✅ 减少代码变更量

为什么不能复用更多？

  1. 链表特有概念：

    • init_patcher() / free_patcher() - 数组方案不需要
    • patch_insn_list() - 链表插入逻辑完全不同
    • linearize_patcher() - 数组方案不需要线性化

  2. 实现逻辑差异：

    • adjust_branches_list() - 使用 orig_idx → new_idx 映射，与 bpf_adj_branches() 逻辑完全不同
    • adjust_line_info_list() - 链表版本的 line info 调整

  3. 临时过渡：

    • bpf_patch_insn_data_list() - 在 Patch 7-17 期间作为 #ifdef 分支，Patch 18 删除

最终状态（Patch 18 后）：

  • 只保留 5 个复用的函数名 + 7 个新增函数
  • 删除 bpf_patch_insn_data_list() 和所有旧数组实现
  • 总计 12 个函数，其中 5 个是复用的函数名

Bisectability 保证

关键技术：

  1. Patch 1-6：使用 __maybe_unused 标记
  2. Patch 7-17：新代码在 #ifdef CONFIG_BPF_VERIFIER_LINKED_LIST 内
  3. Patch 18：删除 #ifdef 和旧代码

编译验证：每个补丁测试两种配置

  • CONFIG_BPF_VERIFIER_LINKED_LIST=n（默认）
  • CONFIG_BPF_VERIFIER_LINKED_LIST=y（测试）

详细实现指南

Patch 1: 数据结构定义

修改文件：include/linux/bpf_verifier.h

添加内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 链表节点：可修补的指令 */
struct bpf_patchable_insn {
    struct bpf_patchable_insn *next;  /* 下一个节点 */
    struct bpf_insn insn;              /* BPF 指令 */
    int orig_idx;                      /* 原始索引（用户程序中的位置） */
    int new_idx;                       /* 新索引（线性化后的位置，初始为 -1） */
};

/* 修补器上下文 */
struct bpf_patcher {
    struct bpf_patchable_insn *head;   /* 链表头 */
    struct bpf_patchable_insn **orig_to_node;  /* 原始索引 → 节点指针的映射 */
    int orig_cnt;                      /* 原始指令数 */
    int total_cnt;                     /* 当前总指令数（包括新增的） */
};

编译验证：

1
make kernel/bpf/verifier.o  # 应该编译通过

Patch 2-6: 核心函数实现

详细实现代码见上文 Patch 2-6 的描述。每个 patch 添加后都要验证编译通过。

Patch 7: CONFIG 选项

详细实现见上文 Patch 7 的描述。关键是通过 #ifdef 切换实现，默认使用旧实现。

Patch 9-13: 元数据处理

每个 patch 都在 #ifdef CONFIG_BPF_VERIFIER_LINKED_LIST 内添加新实现，保持旧实现不变。

Patch 18: 删除旧实现

删除所有 #ifdef 分支和旧代码，只保留链表实现。详细见上文描述。

实现检查清单

Patch 1/18: bpf: introduce patchable instruction data structures

文件修改：

  • include/linux/bpf_verifier.h - 添加 struct bpf_patchable_insn
  • include/linux/bpf_verifier.h - 添加 struct bpf_patcher

编译验证：

  • make kernel/bpf/verifier.o - 编译通过
  • 无编译警告
  • 无编译错误

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 代码注释完整
  • 数据结构对齐正确

Commit Message：

  • Subject 简洁明了（<50 字符）
  • Body 解释为什么需要这些数据结构
  • 包含 Signed-off-by: Qiliang Yuan <realwujing@gmail.com>

Patch 2/18: bpf: add patcher initialization and cleanup helpers

文件修改：

  • kernel/bpf/verifier.c - 添加 alloc_patchable_insn()
  • kernel/bpf/verifier.c - 添加 init_patcher()
  • kernel/bpf/verifier.c - 添加 free_patcher()

编译验证：

  • make kernel/bpf/verifier.o - 编译通过
  • 无 “unused function” 警告（使用 __maybe_unused）
  • 内存分配使用正确的 GFP 标志

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 错误处理完整（内存分配失败）
  • 资源清理正确（free_patcher）
  • 函数注释完整

功能验证：

  • init_patcher() 正确将数组转换为链表
  • orig_to_node 映射正确建立
  • free_patcher() 无内存泄漏

Commit Message：

  • Subject: “bpf: add patcher initialization and cleanup helpers”
  • Body 解释数组 → 链表转换的必要性
  • 说明使用 __maybe_unused 的原因
  • 签名完整

Patch 3/18: bpf: implement linked list instruction patching

文件修改：

  • kernel/bpf/verifier.c - 添加 patch_insn_list()

编译验证：

  • make kernel/bpf/verifier.o - 编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 边界检查完整（off 有效性）
  • 错误处理完整（内存分配失败）
  • 函数注释说明 O(1) 复杂度

功能验证：

  • len == 1 时正确替换指令
  • len > 1 时正确插入多条指令
  • 链表指针正确维护
  • total_cnt 正确更新

Commit Message：

  • Subject: “bpf: implement linked list instruction patching”
  • Body 强调 O(1) 插入 vs O(N) memmove
  • 签名完整

Patch 4/18: bpf: implement program linearization

文件修改：

  • kernel/bpf/verifier.c - 添加 linearize_patcher()

编译验证：

  • make kernel/bpf/verifier.o - 编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 内存分配使用 bpf_prog_realloc()
  • 错误处理完整
  • 函数注释说明线性化过程

功能验证：

  • new_idx 正确分配（从 0 开始递增）
  • 指令正确复制到新数组
  • 程序长度正确（new_prog->len == patcher->total_cnt）

Commit Message：

  • Subject: “bpf: implement program linearization”
  • Body 解释链表 → 数组转换
  • 签名完整

Patch 5/18: bpf: implement jump offset adjustment for linked list

文件修改：

  • kernel/bpf/verifier.c - 添加 adjust_branches_list()

编译验证：

  • make kernel/bpf/verifier.o - 编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 跳转类型判断正确（JMP/JMP32）
  • 边界检查完整
  • 函数注释说明使用 orig_idx → new_idx 映射

功能验证：

  • 条件跳转偏移正确调整
  • 无条件跳转偏移正确调整
  • 新增指令（orig_idx == -1）正确跳过
  • 跳转目标越界检查

Commit Message：

  • Subject: “bpf: implement jump offset adjustment for linked list”
  • Body 解释为什么只需调整一次（vs 每次修补都调整）
  • 签名完整

Patch 6/18: bpf: add new bpf_patch_insn_data_list() API

文件修改：

  • kernel/bpf/verifier.c - 添加 bpf_patch_insn_data_list()
  • kernel/bpf/verifier.c - 移除 Patch 2-5 函数的 __maybe_unused

编译验证：

  • make kernel/bpf/verifier.o - 编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 错误处理完整（每个步骤）
  • 资源清理正确（失败时释放 patcher 和 new_prog）
  • 函数注释说明完整流程

功能验证：

  • 初始化成功
  • 修补成功
  • 线性化成功
  • 跳转调整成功
  • 错误路径正确清理资源

Commit Message：

  • Subject: “bpf: add new bpf_patch_insn_data_list() API”
  • Body 说明这是链表方案的主入口
  • 说明仍标记 __maybe_unused（Patch 7 才使用）
  • 签名完整

Patch 7/18: bpf: add CONFIG_BPF_VERIFIER_LINKED_LIST option

文件修改：

  • kernel/bpf/Kconfig - 添加 CONFIG_BPF_VERIFIER_LINKED_LIST
  • kernel/bpf/verifier.c - 修改 bpf_patch_insn_data() 添加 #ifdef
  • kernel/bpf/verifier.c - 移除 bpf_patch_insn_data_list() 的 __maybe_unused

编译验证：

  • make defconfig && ./scripts/config -d BPF_VERIFIER_LINKED_LIST && make kernel/bpf/verifier.o - 编译通过（默认配置）
  • ./scripts/config -e BPF_VERIFIER_LINKED_LIST && make kernel/bpf/verifier.o - 编译通过（启用链表）
  • 两种配置都无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • Kconfig 帮助文本清晰
  • #ifdef 分支清晰
  • 默认配置保持旧行为（default n）

功能验证：

  • CONFIG=n 时使用数组实现
  • CONFIG=y 时使用链表实现
  • 两种配置都能正常工作

Commit Message：

  • Subject: “bpf: add CONFIG_BPF_VERIFIER_LINKED_LIST option”
  • Body 说明这是实验性功能，默认关闭
  • 说明如何测试两种实现
  • 签名完整

Patch 8/18: selftests/bpf: add basic tests

文件修改：

  • tools/testing/selftests/bpf/config - 添加 CONFIG_BPF_VERIFIER_LINKED_LIST=y
  • tools/testing/selftests/bpf/prog_tests/verifier_patch_list.c - 新增测试

编译验证：

  • make -C tools/testing/selftests/bpf - 编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 测试用例覆盖基本场景
  • 测试代码有 #ifdef 保护

功能验证：

  • 简单程序验证通过
  • 单条指令替换测试
  • 多条指令插入测试
  • 跳转调整测试
  • 测试通过率 100%

Commit Message：

  • Subject: “selftests/bpf: add basic tests for linked list patching”
  • Body 说明测试覆盖范围
  • 签名完整

Patch 9/18: bpf: adjust insn_aux_data for linked list patching

文件修改：

  • kernel/bpf/verifier.c - 在 #ifdef 内添加 adjust_insn_aux_data_list()
  • kernel/bpf/verifier.c - 修改 bpf_patch_insn_data_list() 调用新函数

编译验证：

  • 两种配置都编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 使用 orig_idx → new_idx 映射
  • 错误处理完整
  • 函数注释说明与数组版本的区别

功能验证：

  • aux_data 正确调整
  • seen 标志正确传播
  • zext_dst 正确设置

Commit Message：

  • Subject: “bpf: adjust insn_aux_data for linked list patching”
  • Body 说明如何使用映射调整 aux_data
  • 签名完整

Patch 10/18: bpf: add line info adjustment for linked list

文件修改：

  • kernel/bpf/verifier.c - 在 #ifdef 内添加 adjust_line_info_list()
  • kernel/bpf/verifier.c - 修改 bpf_patch_insn_data_list() 调用新函数

编译验证：

  • 两种配置都编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 使用 orig_idx → new_idx 映射
  • 错误处理完整
  • 函数注释说明 line info 调整逻辑

功能验证：

  • Line info 正确调整
  • 行号映射正确
  • 调试信息完整

Commit Message：

  • Subject: “bpf: add line info adjustment for linked list”
  • Body 说明这解决了 Jiong Wang RFC 中的问题
  • 签名完整

Patch 11/18: bpf: refactor adjust_subprog_starts for linked list

文件修改：

  • kernel/bpf/verifier.c - 在 #ifdef 内添加链表版本
  • kernel/bpf/verifier.c - 保持 #else 分支的旧实现

编译验证：

  • 两种配置都编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 使用 orig_idx → new_idx 映射
  • 处理子程序被删除的情况
  • 函数注释说明边界情况

功能验证：

  • 子程序起始位置正确调整
  • 子程序边界正确
  • 多子程序场景正确

Commit Message：

  • Subject: “bpf: refactor adjust_subprog_starts for linked list”
  • Body 说明如何处理子程序边界
  • 签名完整

Patch 12/18: bpf: refactor adjust_poke_descs for linked list

文件修改：

  • kernel/bpf/verifier.c - 在 #ifdef 内添加链表版本
  • kernel/bpf/verifier.c - 保持 #else 分支的旧实现

编译验证：

  • 两种配置都编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 使用 orig_idx → new_idx 映射
  • 错误处理完整

功能验证：

  • Poke 描述符正确调整
  • 尾调用场景正确

Commit Message：

  • Subject: “bpf: refactor adjust_poke_descs for linked list”
  • Body 说明 poke 描述符的作用
  • 签名完整

Patch 13/18: bpf: refactor adjust_insn_arrays for linked list

文件修改：

  • kernel/bpf/verifier.c - 在 #ifdef 内添加链表版本
  • kernel/bpf/verifier.c - 保持 #else 分支的旧实现

编译验证：

  • 两种配置都编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 使用 orig_idx → new_idx 映射
  • 错误处理完整

功能验证：

  • 指令数组映射正确调整
  • 多个数组场景正确

Commit Message：

  • Subject: “bpf: refactor adjust_insn_arrays for linked list”
  • Body 说明指令数组映射的作用
  • 签名完整

Patch 14/18: selftests/bpf: add comprehensive tests

文件修改：

  • tools/testing/selftests/bpf/prog_tests/verifier_patch_list.c - 扩展测试

编译验证：

  • make -C tools/testing/selftests/bpf - 编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 测试覆盖所有元数据场景

功能验证：

  • aux_data 测试通过
  • line info 测试通过
  • subprog 测试通过
  • poke 描述符测试通过
  • insn_arrays 测试通过
  • 所有 selftests 通过

Commit Message：

  • Subject: “selftests/bpf: add comprehensive tests for metadata”
  • Body 列出测试覆盖的场景
  • 签名完整

Patch 15/18: selftests/bpf: add equivalence test

文件修改：

  • tools/testing/selftests/bpf/prog_tests/verifier_patch_equiv.c - 新增伪随机测试

编译验证：

  • make -C tools/testing/selftests/bpf - 编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 伪随机测试框架完整
  • 测试可重现（固定种子）

功能验证：

  • 数组实现 vs 链表实现结果一致
  • 测试覆盖各种修补场景
  • 测试覆盖各种程序大小
  • 1000+ 次随机测试通过

Commit Message：

  • Subject: “selftests/bpf: add equivalence test for array vs linked list”
  • Body 说明伪随机测试的重要性
  • 签名完整

Patch 16/18: selftests/bpf: add stress test

文件修改：

  • tools/testing/selftests/bpf/prog_tests/verifier_patch_stress.c - 新增压力测试

编译验证：

  • make -C tools/testing/selftests/bpf - 编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 压力测试场景完整

功能验证：

  • 大规模程序测试（10 万条指令）
  • 极端修补场景（10 万次修补）
  • 内存使用测试（无泄漏）
  • 性能测试（验证提升）

Commit Message：

  • Subject: “selftests/bpf: add stress test for large programs”
  • Body 说明测试的极端场景
  • 签名完整

Patch 17/18: bpf: optimize memory allocation in patcher

文件修改：

  • kernel/bpf/verifier.c - 优化内存分配

编译验证：

  • 两种配置都编译通过
  • 无编译警告

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 内存池实现正确
  • 无内存泄漏

功能验证：

  • 性能提升（减少 kmalloc 调用）
  • 功能正确（所有测试通过）

性能测试：

  • pyperf180.bpf.o 性能测试
  • 验证时间减少 30-40%
  • 内存使用合理

Commit Message：

  • Subject: “bpf: optimize memory allocation in patcher”
  • Body 说明优化方法和性能数据
  • 签名完整

Patch 18/18: bpf: remove array-based patching implementation

文件修改：

  • kernel/bpf/Kconfig - 删除 CONFIG_BPF_VERIFIER_LINKED_LIST
  • kernel/bpf/verifier.c - 删除所有 #ifdef 和 #else 分支
  • kernel/bpf/verifier.c - 删除旧的数组实现函数
  • kernel/bpf/core.c - 删除 bpf_patch_insn_single()

编译验证：

  • make kernel/bpf/verifier.o - 编译通过
  • make kernel/bpf/core.o - 编译通过
  • 无编译警告
  • 无未使用的函数

代码质量：

  • ./scripts/checkpatch.pl - 无警告
  • 代码简洁（删除约 300 行）
  • 无死代码

功能验证：

  • 所有 selftests 通过
  • 所有内核 BPF 测试通过
  • 无功能回归

性能测试：

  • pyperf180.bpf.o 最终性能测试
  • 验证时间减少 30-40%
  • 与 baseline 对比

文档更新：

  • 更新相关文档
  • 更新 commit message 引用

Commit Message：

  • Subject: “bpf: remove array-based patching and enable linked list by default”
  • Body 说明删除的代码量
  • Body 包含最终性能数据
  • Body 说明这是系列的最后一个补丁
  • 签名完整

整体验证清单

Bisectability 验证

  • 运行 bisectability 验证脚本
  • 每个补丁都能独立编译（两种配置）
  • 每个补丁都能独立运行
  • git bisect 可用

性能验证

  • Baseline 测试（Patch 1 之前）
  • 中期测试（Patch 8 之后）
  • 最终测试（Patch 18 之后）
  • 性能提升达到 30-40%

功能验证

  • 所有 BPF selftests 通过
  • 内核 BPF 测试套件通过
  • 无功能回归
  • 无内存泄漏

代码质量

  • 所有补丁通过 checkpatch.pl
  • 代码风格一致
  • 注释完整
  • 无死代码

文档

  • 设计文档完整
  • Commit message 清晰
  • 性能数据完整
  • 参考资料完整

社区准备

  • Cover letter 准备完成
  • 性能数据图表准备
  • 准备好回答审查意见
  • 准备好迭代多个版本

验证脚本

Bisectability 验证脚本

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#!/bin/bash
# verify_all_patches.sh

set -e

PATCHES=(
    "Patch 1: data structures"
    "Patch 2: init/cleanup"
    "Patch 3: patching"
    "Patch 4: linearization"
    "Patch 5: jump adjustment"
    "Patch 6: main API"
    "Patch 7: CONFIG option"
    "Patch 8: basic tests"
    "Patch 9: aux_data"
    "Patch 10: line info"
    "Patch 11: subprog"
    "Patch 12: poke descs"
    "Patch 13: insn arrays"
    "Patch 14: comprehensive tests"
    "Patch 15: equivalence test"
    "Patch 16: stress test"
    "Patch 17: optimization"
    "Patch 18: remove old code"
)

for i in {1..18}; do
    echo "========================================="
    echo "Testing ${PATCHES[$i-1]}"
    echo "========================================="
    
    # 应用补丁
    git checkout -b test-patch-$i
    git cherry-pick patch-$i
    
    # 测试配置 1（默认）
    echo "Testing with CONFIG_BPF_VERIFIER_LINKED_LIST=n"
    make defconfig
    ./scripts/config -d BPF_VERIFIER_LINKED_LIST
    make kernel/bpf/verifier.o || {
        echo "ERROR: Patch $i failed with CONFIG=n"
        exit 1
    }
    
    # 测试配置 2（启用，从 Patch 7 开始）
    if [ $i -ge 7 ]; then
        echo "Testing with CONFIG_BPF_VERIFIER_LINKED_LIST=y"
        ./scripts/config -e BPF_VERIFIER_LINKED_LIST
        make kernel/bpf/verifier.o || {
            echo "ERROR: Patch $i failed with CONFIG=y"
            exit 1
        }
    fi
    
    # 运行 checkpatch
    echo "Running checkpatch.pl"
    git format-patch -1 HEAD
    ./scripts/checkpatch.pl *.patch || {
        echo "WARNING: Patch $i has checkpatch warnings"
    }
    rm *.patch
    
    echo "Patch $i: OK"
    git checkout main
    git branch -D test-patch-$i
done

echo "========================================="
echo "All patches verified successfully!"
echo "========================================="

性能测试脚本

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
#!/bin/bash
# performance_test.sh

set -e

echo "Running performance tests..."

# Baseline
echo "Baseline (before patches):"
git checkout baseline
./scripts/run_baseline_benchmark.sh

# After Patch 8 (basic implementation)
echo "After Patch 8 (basic implementation):"
git checkout patch-8
./scripts/config -e BPF_VERIFIER_LINKED_LIST
make -j$(nproc)
./scripts/run_baseline_benchmark.sh

# After Patch 17 (optimized)
echo "After Patch 17 (optimized):"
git checkout patch-17
./scripts/config -e BPF_VERIFIER_LINKED_LIST
make -j$(nproc)
./scripts/run_baseline_benchmark.sh

# After Patch 18 (final)
echo "After Patch 18 (final):"
git checkout patch-18
make -j$(nproc)
./scripts/run_baseline_benchmark.sh

echo "Performance tests completed!"

提交策略

RFC（第 1-8 周）

1
2
3
4
5
6
7
[RFC PATCH 0/8] bpf: optimize verifier instruction patching with linked list

Cover Letter:
- 性能瓶颈（47%）
- 链表方案优势
- 初步性能数据
- 征求意见

V1（第 9-16 周）

1
2
3
4
5
6
7
[PATCH v1 0/14] bpf: optimize verifier instruction patching with linked list

Cover Letter:
- RFC 反馈处理
- 完整功能实现
- 详细性能数据
- 完整测试覆盖

V2-VN（第 17-24 周）

1
2
3
4
5
6
7
[PATCH v2 0/18] bpf: optimize verifier instruction patching with linked list

Cover Letter:
- V1 反馈处理
- 性能优化
- 压力测试
- 准备合入

代码变更统计

  • 新增代码：约 1,500 行（链表实现 + 测试）
  • 删除代码：约 300 行（旧数组实现）
  • 净增加：约 1,200 行

总结

修正后的方案保证：

  1. ✅ 每个补丁都能编译通过（两种配置）
  2. ✅ 每个补丁都能独立运行
  3. ✅ git bisect 可用
  4. ✅ 默认行为不变（直到 Patch 18）
  5. ✅ 可以 A/B 对比（Patch 7-17）

关键技术：

  • __maybe_unused 标记（Patch 1-6）
  • #ifdef CONFIG_BPF_VERIFIER_LINKED_LIST（Patch 7-17）
  • 渐进式启用（Patch 18 才默认启用）

这是 Linux 内核开发的标准做法，完全符合社区要求！

附录：数据结构选择决策树

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
问题：bpf_patch_insn_data 性能瓶颈（47% 验证时间）
  │
  ├─ 需求分析
  │   ├─ 频繁插入操作（M 次，M ≈ 5,000）
  │   ├─ 插入位置分散（遍历整个程序）
  │   ├─ 最后需要连续数组（JIT 编译需要）
  │   └─ 不需要回滚、复杂查询等额外功能
  │
  ├─ 候选方案
  │   │
  │   ├─ 1. 保持数组 + 批量修补
  │   │   ├─ 复杂度：O(N×M/k)，k = 批次数
  │   │   ├─ 提升：10-15%
  │   │   └─ 结论：❌ 治标不治本
  │   │
  │   ├─ 2. 链表 + 延迟线性化
  │   │   ├─ 复杂度：O(M+N)
  │   │   ├─ 提升：30-40%
  │   │   ├─ 实现：中等
  │   │   └─ 结论：✅ 最佳选择
  │   │
  │   ├─ 3. Gap Buffer
  │   │   ├─ 复杂度：O(N×M/2) 平均
  │   │   ├─ 提升：15-20%
  │   │   ├─ 实现：简单
  │   │   └─ 结论：⚠️ 折中方案（修补位置分散时退化）
  │   │
  │   ├─ 4. Rope（平衡树）
  │   │   ├─ 复杂度：O(M log N + N)
  │   │   ├─ 提升：35-45%
  │   │   ├─ 实现：很复杂
  │   │   └─ 结论：❌ 过度设计（复杂度不值得）
  │   │
  │   ├─ 5. 分块数组
  │   │   ├─ 复杂度：O(M×CHUNK_SIZE)
  │   │   ├─ 提升：20-25%
  │   │   ├─ 实现：简单
  │   │   └─ 结论：⚠️ 折中方案（仍需移动）
  │   │
  │   └─ 6. COW + 版本链
  │       ├─ 复杂度：O(M+N)
  │       ├─ 提升：30-40%
  │       ├─ 实现：中等
  │       └─ 结论：❌ 不需要回滚功能
  │
  └─ 最终决策：链表方案
      │
      ├─ 理由 1：彻底解决问题（O(M+N)）
      ├─ 理由 2：实现复杂度可接受
      ├─ 理由 3：社区有讨论基础
      ├─ 理由 4：性能提升显著（30-40%）
      └─ 理由 5：无需额外功能

附录：性能对比矩阵

理论性能（N=10,000, M=5,000）

方案 修补阶段 线性化阶段 总操作数 相对提升
当前数组 50,000,000 0 50,000,000 基准
批量修补 10,000,000 0 10,000,000 5×
链表 5,000 10,000 15,000 3,333×
Gap Buffer 25,000,000 0 25,000,000 2×
Rope 65,000 10,000 75,000 667×
分块数组 640,000 0 640,000 78×
COW 5,000 15,000 20,000 2,500×

实际性能（考虑常数因子和缓存）

方案 预期提升 实现难度 内存开销 缓存友好 综合评分
当前数组 0% ⭐ ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ❌
批量修补 10-15% ⭐⭐ ⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ⚠️
链表 30-40% ⭐⭐⭐ ⭐⭐⭐⭐ ⭐⭐ ✅
Gap Buffer 15-20% ⭐⭐ ⭐⭐⭐ ⭐⭐⭐⭐ ⚠️
Rope 35-45% ⭐⭐⭐⭐⭐ ⭐⭐ ⭐ ❌
分块数组 20-25% ⭐⭐ ⭐⭐⭐⭐ ⭐⭐⭐ ⚠️
COW 25-35% ⭐⭐⭐ ⭐⭐ ⭐⭐⭐ ⚠️

说明：

  • ⭐ 越多越好（实现难度除外，越少越好）
  • ✅ 推荐，⚠️ 可考虑，❌ 不推荐

附录：如果选择其他方案

如果选择 Gap Buffer

适用场景：

  • 不想引入链表复杂度
  • 修补位置有一定局部性
  • 作为过渡方案

实施计划（2 个补丁）：

  1. Patch 1: 实现 Gap Buffer 数据结构
  2. Patch 2: 替换 bpf_patch_insn_data 实现

预期收益：15-20% 提升

风险：治标不治本，最终可能还要做链表

如果选择分块数组

适用场景：

  • 想要折中方案
  • 不想完全放弃数组的缓存友好性
  • 可以接受中等提升

实施计划（3 个补丁）：

  1. Patch 1: 实现分块数据结构
  2. Patch 2: 实现分块修补逻辑
  3. Patch 3: 替换 bpf_patch_insn_data 实现

预期收益：20-25% 提升

风险：实现复杂度接近链表，但收益不如链表

为什么不推荐 Rope

理由：

  1. 实现复杂度太高（需要平衡树算法）
  2. 内存开销大（树节点元数据）
  3. 缓存不友好（指针跳转）
  4. 收益有限（O(M log N) vs O(M+N)，差异不大）
  5. 过度设计（BPF verifier 不需要这么复杂）

计算：

  • 链表实现：约 1,500 行代码
  • Rope 实现：约 3,000 行代码（包括平衡树）
  • 性能差异：链表 15,000 操作 vs Rope 75,000 操作
  • 链表仍然快 5 倍，且代码少一半

为什么不推荐 COW

理由：

  1. BPF verifier 不需要回滚功能
  2. 合并阶段处理重叠 delta 复杂
  3. 内存开销大（保存所有 delta）
  4. 收益与链表相当，但实现更复杂

如果需要回滚：

  • 可以考虑 COW
  • 但 BPF verifier 的验证是单向的，不需要回滚

文档版本：v1.1
日期：2026-01-22
作者：Qiliang Yuan realwujing@gmail.com
测试环境：Linux 6.19.0-rc5

更新日志：

  • v1.1 (2026-01-22): 添加其他数据结构方案对比分析（Gap Buffer、Rope、分块数组、COW）
  • v1.0 (2026-01-22): 初始版本，链表方案设计和 18 个补丁规划
linux > performance > bpf
#architect #bpf #fs #git #go #kernel #linux #log #perf #performance #sound #task #testing #tools #mm #net #struct #proc #security #bugs
BPF Verifier bpf_patch_insn_data 当前实现分析
https://realwujing.github.io/linux/performance/bpf/BPF_PATCH_INSN_DATA_CURRENT_IMPLEMENTATION/
作者
Wu Jing
发布于
2026年1月22日
许可协议