BPF Verifier bpf_patch_insn_data 当前实现分析

概述

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

BPF 程序的完整生命周期

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

┌─────────────────────────────────────────────────────────────────┐
│ 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. 编译阶段（用户空间）：
2. 用户使用 C 语言编写 BPF 程序
3. Clang/LLVM 编译为 BPF 字节码（类似汇编）

4. 生成 ELF 格式的 .o 文件

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

6. 用户空间工具（bpftool/libbpf）解析 .o 文件
7. 通过 bpf(BPF_PROG_LOAD, ...) 系统调用传递给内核

8. 内核接收原始的 BPF 字节码

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

10. Verifier 检查程序的安全性
11. 确保不会崩溃内核或访问非法内存

12. 这个阶段不修改指令，只是分析

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

14. 将抽象的 BPF 指令转换为可执行的形式
15. 插入安全检查
16. 优化和重写指令

17. 这个阶段会调用 bpf_patch_insn_data() 数千次

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

19. 将 BPF 字节码编译为本机机器码（x86_64/ARM64 等）

20. 提高运行时性能

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

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

为什么修补阶段是瓶颈？

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

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

---

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

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

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

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

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

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

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

Verifier 修补后的实际指令：

// 需要从实际的 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 程序可能有几十个这样的字段访问，每个都需要修补。

1. Helper 函数调用修复（Helper Call Fixup）
2. BPF 程序调用 helper 函数时使用的是函数 ID
3. verifier 需要将函数 ID 转换为实际的函数地址
4. 可能需要插入额外的参数检查和转换指令
5. 某些 helper 调用需要内联展开

具体例子：调用 bpf_map_lookup_elem()

// 用户编写的 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 字节码：

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

Verifier 修补后：

// 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）

1. 安全检查插入（Security Instrumentation）
2. 插入边界检查指令（防止越界访问）
3. 插入空指针检查
4. 插入除零检查
5. 插入栈溢出检查

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

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

编译后的 BPF 字节码：

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 修补后（插入边界检查）：

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 - 指针运算检查：确保指针运算不会溢出

1. 优化和重写（Optimization and Rewriting）
2. 常量折叠后的指令替换
3. 死代码消除
4. 跳转优化
5. 尾调用优化

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

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

编译后的 BPF 字节码：

r0 = 10
r0 += 20                       // r0 = 30
if r0 > 25 goto label_1        // 总是跳转
r0 = 0
exit
label_1:
r0 = 1
exit

Verifier 优化后：

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

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

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

1. 架构特定转换（Architecture-Specific Conversion）
2. 某些指令在特定架构上需要不同的实现
3. 32 位 vs 64 位的差异处理
4. 字节序转换

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

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

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

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

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

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

// x86_64: 可以直接使用
r1 = 0x123456789abcdef0

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

其他架构特定转换： - 字节序转换：网络字节序 ↔ 主机字节序

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

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

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

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

  // 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

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 程序使用连续数组存储指令：

原始程序（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 次，累积移动次数达到数千万次

代码实现分析

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

每次修补的平均开销：

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

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

总验证时间: 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. 内存带宽限制：
2. 每条 BPF 指令 = 8 字节
3. 移动 5,000 条指令 = 40 KB
4. 5,000 次修补 × 40 KB = 200 MB 数据移动

5. 即使内存带宽 10 GB/s，也需要 20 ms

6. 缓存失效：

7. 大块内存移动导致 CPU 缓存失效
8. 每次 memmove 都要重新加载数据到缓存

9. 缓存未命中的代价很高

10. 非对齐访问：

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

为什么 bpf_adj_branches 也很慢？

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. 每次修补移动数千条指令
3. 累积移动数千万次

4. 内存带宽和缓存失效

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

6. 每次修补遍历整个程序
7. 累积遍历数千万次

8. 分支预测失败

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

10. 频繁的内存重新分配

11. 可能触发内存复制

12. 累积效应：

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

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

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

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 函数

/* 调整子程序起始位置 - 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 次修补：移动 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 热点分析：

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. 程序规模较小（几百条指令）
3. 修补次数不多（几十次）

4. 简单的数组实现足够用

5. 数组实现的优势：

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

现在的问题

1. 现代 BPF 程序越来越复杂：
2. 指令数可达数万条
3. 修补次数可达数千甚至数万次

4. O(N*M) 复杂度变得无法接受

5. 数组实现的劣势：

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

---

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

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

当前实现（数组）

修补位置 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 次

预计时间：数十秒

理想实现（链表）

修补阶段（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. 修补是最频繁的操作：
2. convert_ctx_accesses：每个上下文访问都可能修补
3. fixup_bpf_calls：每个 helper 调用都可能修补

4. do_misc_fixups：各种优化和修复

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

6. 移动指令数组
7. 调整跳转偏移

8. 移动辅助数据

9. 累积效应：

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

与其他操作的对比

验证时间分布（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 次数。

当前问题：

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

批量修补方案：

收集所有修补操作：
  - 位置 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 设计：

/* 批量修补条目 */
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);

实现步骤：

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;
}

为什么从后往前修补？

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

原始程序：
位置: 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. 不是所有修补都能批量化：
2. 某些修补依赖前面修补的结果

3. 只能批量化同一阶段的修补（如 convert_ctx_accesses）

4. 批量化的开销：

5. 需要排序（O(M log M)）
6. 需要额外的内存存储批次

7. 需要更复杂的偏移计算

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

9. 假设只有 30% 的修补可以批量化
10. 5,000 次修补 → 1,500 次可批量，3,500 次仍然单独
11. 提升：1,500 / 5,000 = 30% 的修补操作被优化
12. 整体提升：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），修补操作在间隙处进行，只需移动间隙而不是整个数组。

数据结构：

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

工作原理：

初始状态（间隙在开头）：
[____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）存储指令块，每个节点存储一小段连续指令。

数据结构：

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;
};

工作原理：

        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）

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

数据结构：

#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;
};

工作原理：

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（写时复制）+ 版本链

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

数据结构：

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;
};

工作原理：

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)

示例：

修补序列：位置 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 处理

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

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

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

---

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

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

数据结构：

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

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

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

结论：过度优化，不推荐

---

最终推荐：链表方案

理由：

1. 彻底解决问题：
2. O(M+N) vs O(N×M)

3. 理论最优（除了 Rope，但 Rope 太复杂）

4. 实现复杂度可接受：

5. 比 Rope 简单得多
6. 比 COW 简单

7. 比分块数组略复杂，但收益大得多

8. 社区认可：

9. 2019 年 Jiong Wang RFC
10. 2019 年 Andrii Nakryiko 建议

11. 历史失败是工程问题，不是方案问题

12. 性能提升显著：

13. 30-40% 验证时间减少

14. 其他方案提升有限

15. 无需额外功能：

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

其他方案的定位：

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

行动建议：

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

---

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

/* 可修补的指令节点（链表节点） */
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: 初始化（将数组转换为链表）
原始程序（数组）：
[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."

2. patch_insn 历史上有很多 bug
3. 大规模重构容易引入新 bug

4. 影响所有 BPF 程序，后果严重

5. 实现复杂度高：

6. 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 调整代码不够干净
7. subprog info 调整：需要处理子程序被删除的情况
   • RFC 中这部分实现也不完整
   • 子程序边界调整的边界情况复杂
8. 需要处理各种边界情况

9. 代码审查困难，RFC 代码质量不够高

10. 测试覆盖困难：

11. 需要大量测试用例
12. 需要伪随机测试验证等价性

13. 难以保证所有场景都正确

14. 方案分歧：

15. Jiong 提出链表方案
16. Alexei 提出更复杂的基本块方案

17. 讨论转向更彻底的重构，但更复杂

18. 缺乏持续推动：

19. Jiong 发布 RFC 后没有继续迭代
20. 没有 v2/v3 版本

21. 社区没有其他人接手

22. 优先级不够：

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

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

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

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

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

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

什么是基本块（Basic Block）？

基本块是编译器理论中的概念，指的是一段顺序执行的指令序列，具有以下特点： - 单一入口：只能从第一条指令进入 - 单一出口：只能从最后一条指令退出 - 顺序执行：中间没有跳转指令（除了最后一条）

基本块示例：

程序：
  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 程序分割为基本块

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

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

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

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

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

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

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

基本块方案的优势：

1. 修补局部化：
2. 修补只影响单个基本块
3. 不需要移动其他基本块的指令

4. 减少 memmove 的范围

5. 跳转调整延迟：

6. 修补时不需要调整跳转
7. 只在最后重建时统一调整

8. 避免重复遍历

9. 更好的缓存局部性：

10. 基本块通常较小
11. 修补操作更集中

基本块方案的劣势：

1. 实现极其复杂：
2. 需要实现基本块分析算法
3. 需要维护基本块图（Control Flow Graph）

4. 需要处理各种边界情况

5. 数据结构复杂：

6. 需要维护基本块数组
7. 需要维护跳转映射表

8. 需要处理基本块的分裂和合并

9. 调试困难：

10. 中间表示更抽象
11. 错误更难定位

12. 测试覆盖困难

13. 风险极高：

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

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

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. 这是唯一的根本解决方案：
2. 数组结构的性能瓶颈无法通过小修小补解决
3. 批量修补只是延缓问题，不能解决问题

4. 链表是唯一能将 O(N×M) 降低到 O(M+N) 的方案

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

6. Jiong Wang RFC 失败的主要原因：
   • ❌ line info 实现不完善 → ✅ 可以重新设计
   • ❌ subprog info 处理不完整 → ✅ 可以完善
   • ❌ 缺乏持续推动 → ✅ 我们可以持续投入
   • ❌ 测试覆盖不足 → ✅ 可以补充测试

7. 这些都是工程问题，不是方案本身的问题

8. 社区已有讨论基础：

9. 2019 年 Jiong Wang RFC
10. 2019 年 Andrii Nakryiko 的改进建议
11. 2022 年 Eduard Zingerman 的讨论
12. 2026 年 Eduard 再次建议优化

13. 社区认可这个方向，只是缺少完善的实现

14. 投入产出比最高：

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

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

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

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

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

第 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 中的问题

第 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 个月）

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

第 17-18 周：伪随机测试
- 实现伪随机测试框架
- 验证链表方案与数组方案等价
- 覆盖各种修补场景

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

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

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

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

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

第 25-26 周：准备补丁
- 拆分为合理的补丁系列
- 编写详细的 commit message
- 准备性能数据

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

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

关键成功因素

1. 解决 RFC 中的具体问题：
2. line info：必须有干净的实现
3. subprog info：必须处理所有边界情况

4. 不能留下未完成的部分

5. 充分的测试覆盖：

6. 功能测试：所有 selftests
7. 等价性测试：伪随机测试
8. 压力测试：大规模程序

9. 性能测试：详细的 perf 数据

10. 与维护者充分沟通：

11. 提前发 RFC 征求意见
12. 展示清晰的设计和收益
13. 及时响应审查意见

14. 准备好长期投入

15. 渐进式实施：

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

风险和应对

风险 1：实现比预期复杂 - 应对：渐进式实施，每个阶段都可以独立评估 - 如果某个阶段遇到困难，可以调整计划

风险 2：维护者不接受 - 应对：提前沟通，展示清晰的收益数据 - 强调这是唯一的根本解决方案 - 参考历史讨论，说明如何解决之前的问题

风险 3：引入新的 bug - 应对：充分的测试覆盖 - 伪随机测试验证等价性 - 渐进式合入，每一步都验证

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

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

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

1. 治标不治本：
2. 仍然使用数组，性能瓶颈仍在
3. 只是减少操作次数，不能改变 O(N) 的本质

4. 10-15% 的提升不够显著

5. 浪费时间：

6. 花 2 个月实现批量修补
7. 发现效果有限，还是要做链表

8. 总共花 8 个月，不如直接花 6 个月做链表

9. 代码债务：

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

总结：必须选择链表方案

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

行动计划： - 直接实施链表方案（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 规划（19 个补丁）- 复用现有函数名

设计原则

复用现有函数名，修改实现： - ✅ 保持 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：优化测试与默认开启	5	17-24 周	性能优化 + 默认开启 + 合入

---

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

1. bpf: introduce patchable instruction data structures

文件：include/linux/bpf_verifier.h

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

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

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

/* 新增：分配链表节点 */
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

内容：新增链表修补函数

/* 新增：在链表中修补指令（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

内容：新增线性化函数

/* 新增：链表 → 数组（线性化） */
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

内容：新增跳转调整函数

/* 新增：调整跳转偏移（链表版本，使用 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

/* 新增：链表版本的主函数（临时名称，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() 函数名

// 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() 函数名，修改实现

#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）

#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() 函数名

#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() 函数名

#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() 函数名

#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-19）

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() - 链表实现

最终代码：

/* 最终只保留链表实现，函数名不变 */
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. 链表特有概念：
2. init_patcher() / free_patcher() - 数组方案不需要
3. patch_insn_list() - 链表插入逻辑完全不同

4. linearize_patcher() - 数组方案不需要线性化

5. 实现逻辑差异：

6. adjust_branches_list() - 使用 orig_idx → new_idx 映射，与 bpf_adj_branches() 逻辑完全不同

7. adjust_line_info_list() - 链表版本的 line info 调整

8. 临时过渡：

9. 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-18：新代码在 #ifdef CONFIG_BPF_VERIFIER_LINKED_LIST 内
3. Patch 19：删除 #ifdef 和旧代码

编译验证：每个补丁测试两种配置 - CONFIG_BPF_VERIFIER_LINKED_LIST=n（默认） - CONFIG_BPF_VERIFIER_LINKED_LIST=y（测试）

---

详细实现指南

Patch 1: 数据结构定义

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

添加内容：

/* 链表节点：可修补的指令 */
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;                     /* 当前总指令数（包括新增的） */
};

编译验证：

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/19: add linked-list structures to avoid memmove during patching

文件修改： - [ ] 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/19: bpf/verifier: 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/19: bpf/verifier: 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/19: bpf/verifier: 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/19: bpf/verifier: 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/19: bpf/verifier: 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/19: bpf/verifier: 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/19: bpf/selftests: add initial linked-list patching 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: "bpf/selftests: add initial linked-list patching tests" - [ ] Body 说明测试覆盖范围 - [ ] 签名完整

---

Patch 9/19: bpf/verifier: 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/19: bpf/verifier: 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/19: bpf/verifier: 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/19: bpf/verifier: 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/19: bpf/verifier: 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/19: 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/19: 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/19: 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/19: bpf/verifier: 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/19: bpf/verifier: enable linked list patching by default

文件修改： - [ ] kernel/bpf/Kconfig - 将 CONFIG_BPF_VERIFIER_LINKED_LIST 的 default n 改为 default y 以默认启用链表补丁优化功能

编译验证： - [ ] make defconfig - 检查 .config 中 CONFIG_BPF_VERIFIER_LINKED_LIST=y - [ ] make kernel/bpf/verifier.o - 编译通过 - [ ] 无编译警告

代码质量： - [ ] ./scripts/checkpatch.pl - 无警告

功能验证： - [ ] 默认配置下所有 selftests 通过 - [ ] 确认使用的是链表实现路径

Commit Message： - [ ] Subject: "bpf: enable linked list patching by default" - [ ] Body 说明这是为了在彻底移除旧代码前进行更广泛的测试 - [ ] 签名完整

---

Patch 19/19: bpf/verifier: 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 验证脚本

#!/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: enable by default"
    "Patch 19: remove old code"
)

for i in {1..19}; 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 开始，到 Patch 18 结束）
    if [ $i -ge 7 ] && [ $i -le 18 ]; 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 "========================================="

性能测试脚本

#!/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 (enabled by default)
echo "After Patch 18 (enabled by default):"
git checkout patch-18
make -j$(nproc)
./scripts/run_baseline_benchmark.sh

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

echo "Performance tests completed!"

---

提交策略

RFC（第 1-8 周）

[RFC PATCH 0/8] bpf: optimize verifier instruction patching with linked list

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

V1（第 9-16 周）

[PATCH v1 0/14] bpf: optimize verifier instruction patching with linked list

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

V2-VN（第 17-24 周）

[PATCH v2 0/19] bpf: optimize verifier instruction patching with linked list

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

---

---

代码变更统计

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

---

总结

修正后的方案保证：

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

关键技术： - __maybe_unused 标记（Patch 1-6） - #ifdef CONFIG_BPF_VERIFIER_LINKED_LIST（Patch 7-18） - 渐进式启用（Patch 18 默认启用，Patch 19 彻底清理）

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

---

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

问题：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.2 (2026-01-30): 将补丁规划优化为 19 个，增加“默认开启”缓冲期（Patch 18），遵循内核渐进式演进策略 - v1.1 (2026-01-22): 添加其他数据结构方案对比分析（Gap Buffer、Rope、分块数组、COW） - v1.0 (2026-01-22): 初始版本，链表方案设计和 18 个补丁规划

---

💬 评论