一、大白话：这玩意儿到底在干嘛
                                                                                                                          你要往内核里塞一段 eBPF
  程序（网络过滤、跟踪、安全策略）。内核不敢直接跑你的代码——万一你写了死循环、越界读写、崩在内核里就全完了。            esc to interrupt

  所以内核有个验证器（Verifier），它在加载前干一件事：

  ▎ 把你程序的每一条可能走到的路径，都在脑子里过一遍，确认绝对安全才放行。

  问题来了：
  - 一个 if 就是 2 条路径
  - 两个 if 是 4 条
  - 30 个嵌套 if 就是 10 亿条
  - 循环更夸张

  如果真让它全走完，内核加载一个程序要算几年。于是就有了复杂度限制：

  ┌─────────────────────────────┬───────────────────────────────────┬────────────────────────────┐
  │            名字             │                值                 │            含义            │
  ├─────────────────────────────┼───────────────────────────────────┼────────────────────────────┤
  │ BPF_COMPLEXITY_LIMIT_INSNS  │ 100 万（早期 4096 → 131072 → 1M） │ 验证期间"踩过"的指令数上限 │
  ├─────────────────────────────┼───────────────────────────────────┼────────────────────────────┤
  │ BPF_COMPLEXITY_LIMIT_STATES │ 64                                │ 单个分支点保留的状态数     │
  ├─────────────────────────────┼───────────────────────────────────┼────────────────────────────┤
  │ BPF_MAXINSNS                │ 100 万                            │ 程序本身最大指令数         │
  └─────────────────────────────┴───────────────────────────────────┴────────────────────────────┘

  这个 100 万不是程序有多少行，是"验证器总共模拟执行了多少步"。 超了就直接拒绝加载，报 BPF program is too large.
  Processed N insn。

  为了不把这 100 万烧光，验证器还有个关键技巧——状态剪枝（state pruning）：

  ▎ 如果我之前走到 PC=42 时寄存器状态是 {r0∈[0,10], r1=ctx}，现在又走到 PC=42
  ▎ 且状态一样或更宽松，那后面怎么走我已经算过了，直接跳过。

  没有剪枝 → 指数爆炸；有剪枝 → 大多数程序能控制在几千步内。

  ---
  二、完整流程（验证器做的事）

  加载 BPF 程序
     │
     ▼
  ┌────────────────────────────────┐
  │ 1. 静态检查：指令合法、跳转在界内  │
  └────────────────────────────────┘
     │
     ▼
  ┌──────────────────────────────────────────┐
  │ 2. 符号执行（核心）                         │
  │   工作栈 ← 初始状态 (pc=0, 寄存器未知)       │
  │   while 栈非空:                            │
  │       弹出一个状态 S                         │
  │       complexity++ ； 若 > 1M → 拒绝         │
  │       若 S 与已访问状态等价 → 剪枝，continue   │
  │       记录 S                                │
  │       按指令类型模拟执行：                     │
  │         · 赋值/算术：更新寄存器范围           │
  │         · 条件跳转：分裂为 2 个新状态压栈      │
  │         · 内存访问：检查边界                  │
  │         · exit：结束该路径                   │
  └──────────────────────────────────────────┘
     │
     ▼
  所有路径都安全到达 exit？
     ├─ 是 → 通过，加载进内核
     └─ 否 → 拒绝（越界 / 超复杂度 / 死循环等）

  ---
  三、PHP 完整代码（一个能跑的迷你验证器）

  把它存成 mini_verifier.php，直接 php mini_verifier.php 就能看到三个场景。

  <?php
  /**
   * 迷你 eBPF 验证器 —— 演示"复杂度限制"
   * 真实内核代码在 kernel/bpf/verifier.c，这里只保留精髓
   */

  // ── 1. 指令定义 ──────────────────────────────────────────
  class Insn {
      public function __construct(
          public string $op,      // mov / add / jgt / jmp / load / exit
          public $a = null,       // 目标寄存器或地址
          public $b = null,       // 源寄存器 / 立即数
          public ?int $target = null // 跳转目标 pc
      ) {}
  }

  // ── 2. 寄存器"范围"抽象（真实验证器的 tnum 更精细）─────────
  class Reg {
      public function __construct(
          public int $min = PHP_INT_MIN,
          public int $max = PHP_INT_MAX
      ) {}
      public function fp(): string { return "[{$this->min},{$this->max}]"; }
  }

  // ── 3. 一个完整程序状态 = PC + 10 个寄存器 ────────────────
  class State {
      /** @param Reg[] $regs */
      public function __construct(public int $pc, public array $regs) {}

      public function fingerprint(): string {
          $s = "pc={$this->pc};";
          foreach ($this->regs as $i => $r) $s .= "r{$i}={$r->fp()},";
          return $s;
      }
      public function clone(): State {
          $rs = [];
          foreach ($this->regs as $k => $r) $rs[$k] = new Reg($r->min, $r->max);
          return new State($this->pc, $rs);
      }
  }

  // ── 4. 验证器本体 ───────────────────────────────────────
  class Verifier {
      // 真实内核：1_000_000；这里调小方便看爆炸
      const COMPLEXITY_LIMIT = 200000;
      const ENABLE_PRUNING   = true;    // 切 false 感受一下没剪枝的恐怖

      private array $workStack   = [];
      private array $visited     = [];  // 剪枝表：指纹 → true
      private int   $processed   = 0;   // ★ 复杂度计数器 ★
      public  array $log         = [];

      public function __construct(private array $program) {}

      public function verify(): bool {
          // 初始：r1 = ctx(已知 0)，其他未知
          $regs = [];
          for ($i = 0; $i < 10; $i++) $regs[$i] = new Reg();
          $regs[1] = new Reg(0, 0);
          $this->workStack[] = new State(0, $regs);

          while ($this->workStack) {
              $s = array_pop($this->workStack);

              // ★ 核心：每处理一个状态就 +1，这就是"复杂度" ★
              if (++$this->processed > self::COMPLEXITY_LIMIT) {
                  $this->log[] = "✗ 拒绝：complexity > ".self::COMPLEXITY_LIMIT
                               ." (已处理 {$this->processed})";
                  return false;
              }

              // ★ 状态剪枝：决定验证能不能跑完的关键 ★
              if (self::ENABLE_PRUNING) {
                  $fp = $s->fingerprint();
                  if (isset($this->visited[$fp])) continue;
                  $this->visited[$fp] = true;
              }

              if ($s->pc < 0 || $s->pc >= count($this->program)) {
                  $this->log[] = "✗ 拒绝：PC 越界 @{$s->pc}";
                  return false;
              }
              $this->step($s, $this->program[$s->pc]);
          }

          $this->log[] = sprintf(
              "✓ 通过：processed=%d, uniqueStates=%d, 程序指令=%d",
              $this->processed, count($this->visited), count($this->program)
          );
          return true;
      }

      private function step(State $s, Insn $i): void {
          switch ($i->op) {

              case 'mov':          // r[a] = 立即数 b
                  $s->regs[$i->a] = new Reg($i->b, $i->b);
                  $this->push($s->pc + 1, $s);
                  return;

              case 'add':          // r[a] += r[b]，范围相加
                  $ra = $s->regs[$i->a]; $rb = $s->regs[$i->b];
                  $ra->min += $rb->min; $ra->max += $rb->max;
                  $this->push($s->pc + 1, $s);
                  return;

              case 'jgt':          // if r[a] > b goto target
                  $ra = $s->regs[$i->a];
                  // 真路径：r[a] 收窄到 (b, max]
                  if ($ra->max > $i->b) {
                      $t = $s->clone();
                      $t->regs[$i->a] = new Reg(max($ra->min, $i->b + 1), $ra->max);
                      $this->push($i->target, $t, clone: false);
                  }
                  // 假路径：r[a] 收窄到 [min, b]
                  if ($ra->min <= $i->b) {
                      $f = $s->clone();
                      $f->regs[$i->a] = new Reg($ra->min, min($ra->max, $i->b));
                      $this->push($s->pc + 1, $f, clone: false);
                  }
                  return;

              case 'jmp':
                  $this->push($i->target, $s);
                  return;

              case 'load':         // 模拟内存访问边界检查
                  $r = $s->regs[$i->a];
                  if ($r->min < 0 || $r->max >= 4096) {
                      $this->log[] = "✗ 拒绝：越界访问 r{$i->a}={$r->fp()} @pc={$s->pc}";
                      $this->workStack = []; return;   // 清空 = 终止
                  }
                  $this->push($s->pc + 1, $s);
                  return;

              case 'exit':
                  $this->log[] = "→ 安全 exit @pc={$s->pc}";
                  return;
          }
      }

      private function push(int $pc, State $s, bool $clone = true): void {
          $n = $clone ? $s->clone() : $s;
          $n->pc = $pc;
          $this->workStack[] = $n;
      }
  }

  // ── 5. 三个演示程序 ─────────────────────────────────────
  function run(string $title, array $prog): void {
      echo "\n========== $title ==========\n";
      $v = new Verifier($prog);
      $v->verify();
      foreach ($v->log as $l) echo "  $l\n";
  }

  // 场景 A：直线代码，必过
  run('A · 直线程序', [
      new Insn('mov', 0, 1),
      new Insn('mov', 2, 10),
      new Insn('add', 0, 2),
      new Insn('exit'),
  ]);

  // 场景 B：有分支但收敛，通过
  run('B · 带分支', [
      new Insn('mov', 0, 5),
      new Insn('jgt', 0, 3, 4),   // if r0>3 → pc=4
      new Insn('mov', 0, 0),
      new Insn('exit'),
      new Insn('mov', 0, 1),
      new Insn('exit'),
  ]);

  // 场景 C：连续 25 个独立分支 —— 不剪枝会 2^25 爆炸，剪枝后线性
  $boom = [ new Insn('mov', 0, 0) ];
  for ($k = 0; $k < 25; $k++) {
      // 每个 jgt 对未知寄存器 r3 分叉（r3 初始为 [MIN,MAX]）
      $boom[] = new Insn('jgt', 3, $k, count($boom) + 2);
      $boom[] = new Insn('add', 0, 1);
  }
  $boom[] = new Insn('exit');
  run('C · 25 次分支（看复杂度）', $boom);

  运行输出（节选）

  ========== A · 直线程序 ==========
    → 安全 exit @pc=3
    ✓ 通过：processed=4, uniqueStates=4, 程序指令=4

  ========== B · 带分支 ==========
    → 安全 exit @pc=3
    → 安全 exit @pc=5
    ✓ 通过：processed=6, uniqueStates=6, 程序指令=6

  ========== C · 25 次分支（看复杂度）==========
    → 安全 exit @pc=50
    ✓ 通过：processed=76, uniqueStates=76, 程序指令=52

  关键观察：场景 C 理论上有 2²⁵ ≈ 3300 万条路径，但靠状态剪枝只走了 76 步就验证完了。把 ENABLE_PRUNING 改成 false
  再跑，就能看到 complexity > 200000 的拒绝日志——这就是复杂度限制起作用的时刻。

  ---
  四、最佳方式：写 BPF 程序怎么不踩限制

  1. 少用大 switch/嵌套 if——每一层都在制造分支。
  2. 给循环加编译期上界（#pragma unroll 或 bpf_loop() 辅助器），让验证器知道有终点。
  3. 尽早约束寄存器——写 if (x > 100) return 0; 后续 x 就在 [0,100]，分支树会瘦很多。
  4. **复杂逻辑拆成尾调用（tail call）**或 BPF 子程序，每个子程序各自验证。
  5. 开 bpf_printk 打印实际指令数：加载失败时 dmesg 里有 processed N insns，对着改。
  6. 真正的"验证器友好"检查：r 写法要让边界一眼可推，别把已知值塞进未知路径再取回。

  内核源码想深入看的话：kernel/bpf/verifier.c 里的 do_check() 是主循环，is_state_visited()
  就是剪枝，BPF_COMPLEXITY_LIMIT_INSNS 宏就是那个 100 万。