bpf: add DAG fast-path in verifier to skip redundant state pruning The BPF verifier's state-equivalence loop (is_state_visited / states_equal) dominates load time for programs with acyclic control flow graphs (DAGs). In a DAG, every instruction is reached via exactly one path: no state is ever revisited, making state-pruning comparisons mathematically vacuous. This RFC proposes three components: 1. compute_dag_topo() -- replaces a simple is_acyclic_dag() bool. Uses Kahn's algorithm (O(V+E), O(V) space, no recursion) to detect back-edges AND preserve the topological visit order for use in (2). Handles BPF_JMP32, BPF_LD_IMM64 wide instructions, and falls back conservatively on BPF-to-BPF subprogram calls. 2. do_check_dag() -- fast-path verifier for confirmed-DAG programs. Critical correctness property: maintains a per-instruction state table (states[insn_cnt]) and, at every join point (in_degree > 1), calls merge_verifier_state() to conservatively merge all incoming paths BEFORE processing the instruction. This ensures the verifier never sees a register as initialized when any predecessor path left it NOT_INIT. Skips is_state_visited() / states_equal() entirely; provably safe because topological order guarantees each instruction is processed exactly once. 3. Full fallback: if compute_dag_topo() returns NULL (cyclic program, subprog, or allocation failure), or if do_check_dag() returns an error, the unmodified do_check() runs unchanged. Register-state correctness at join points ----------------------------------------- When paths A and B converge at instruction N, the verifier must hold the least precise state that is safe for both paths. Path A arrives at insn N: R2 = scalar [0, 5] Path B arrives at insn N: R2 = NOT_INIT merge_verifier_state() result: R2 = NOT_INIT -> verifier correctly rejects any use of R2 at N Without this merge (a flaw in naive linear-scan approaches), the verifier would see only the state from whichever path was processed last in memory order, potentially accepting a program that dereferences an uninitialized register at runtime. RFC design question: -------------------- do_check_dag()'s inner per-instruction verification step requires calling into do_check()'s inner loop logic, which is not currently factored as a callable sub-function. We propose two integration options and request maintainer guidance: Option A: Extract a verify_one_insn() helper from do_check()'s inner loop; do_check_dag() calls it per topological step. Option B: Add env->dag_mode flag to do_check(); when set, do_check() uses pre-populated env->dag_states[] and skips is_state_visited() comparisons (~20 lines added to do_check(), no code duplication). The state merge logic, DAG detection, and topological traversal are independent of this choice and are presented in full below. Benchmark data will be included in v1 once the integration approach is confirmed. Timing will be measured at BPF_PROG_LOAD syscall level with verifier-only isolation. Signed-off-by: Seunghyeon Lee --- Open Questions for Maintainers =============================== Q1 (Critical): Integration with do_check() inner loop Option A or B as described above? Q2: Scope Should this apply to all program types, or only XDP/TC where DAG programs (e.g., Cilium policy programs) are most common? Q3: Kconfig guard Is a CONFIG_BPF_DAG_OPT Kconfig symbol appropriate, or should this be unconditional given the O(V+E) overhead is negligible? Q4: Subprogram handling Current RFC falls back to full verifier for BPF_PSEUDO_CALL programs. Is per-subprog DAG analysis worth adding in a follow-up? --- include/linux/bpf.h | 3 + include/linux/bpf_verifier.h | 6 + kernel/bpf/verifier.c | 215 ++++++++++++++++++ tools/testing/selftests/bpf/test_dag_verify.c | 230 +++++++++++++++++++ 4 files changed, 454 insertions(+) diff --git a/include/linux/bpf.h b/include/linux/bpf.h --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -... @@ struct bpf_prog_aux { /* ... existing fields ... */ + unsigned int cfg_is_acyclic : 1; /* CFG has no back-edges (DAG) */ /* ... */ }; diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -... @@ +/* + * bpf_dag_info - output of compute_dag_topo(). + * + * @topo_order: topological visit order; topo_order[i] is the insn index + * of the i-th instruction in topological order. + * @in_degree: snapshot of original in-degree per instruction slot, + * taken before Kahn's traversal. Used by do_check_dag() + * to detect join points (in_degree[n] > 1). + * @insn_cnt: env->prog->len at computation time. + */ +struct bpf_dag_info { + int *topo_order; + int *in_degree; + int insn_cnt; +}; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -... @@ +static void free_dag_info(struct bpf_dag_info *dag) +{ + if (!dag) + return; + kfree(dag->topo_order); + kfree(dag->in_degree); + kfree(dag); +} + +/* + * compute_dag_topo() - detect acyclic CFG and return topological order. + * + * Implements Kahn's algorithm: repeatedly remove zero-in-degree nodes. + * If all nodes are processed (visited == insn_cnt), CFG has no back-edges. + * + * Returns allocated bpf_dag_info on success; caller must free_dag_info(). + * Returns NULL if cyclic, contains BPF-to-BPF calls, or on alloc failure. + * All NULL paths are safe: caller falls back to unmodified do_check(). + * + * Handles BPF_JMP, BPF_JMP32, BPF_LD_IMM64 wide instructions. + * Assumes check_cfg() has already run. + */ +static struct bpf_dag_info *compute_dag_topo(struct bpf_verifier_env *env) +{ + struct bpf_insn *insns = env->prog->insnsi; + int insn_cnt = env->prog->len; + struct bpf_dag_info *dag = NULL; + int *in_degree = NULL, *queue = NULL; + bool *is_dummy = NULL; + int head = 0, tail = 0, visited = 0, i; + + dag = kzalloc(sizeof(*dag), GFP_KERNEL); + in_degree = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL); + queue = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL); + is_dummy = kcalloc(insn_cnt, sizeof(bool), GFP_KERNEL); + if (!dag || !in_degree || !queue || !is_dummy) + goto fail; + + /* Pass 1: compute in-degrees for each instruction slot. */ + for (i = 0; i < insn_cnt; i++) { + struct bpf_insn *insn = &insns[i]; + u8 cls = BPF_CLASS(insn->code); + u8 op; + + /* + * BPF_LD_IMM64: two-slot wide instruction. + * The second (dummy) slot has no real edges; fall-through + * skips to slot i+2. + */ + if (insn->code == (BPF_LD | BPF_IMM | BPF_DW)) { + if (i + 1 < insn_cnt) + is_dummy[i + 1] = true; + if (i + 2 < insn_cnt) + in_degree[i + 2]++; + i++; + continue; + } + + if (cls != BPF_JMP && cls != BPF_JMP32) { + if (i + 1 < insn_cnt) + in_degree[i + 1]++; + continue; + } + + op = BPF_OP(insn->code); + + if (op == BPF_EXIT) + continue; + + /* BPF-to-BPF subprog call: fall back to full verifier. */ + if (op == BPF_CALL && insn->src_reg == BPF_PSEUDO_CALL) + goto fail; + + { + int tgt = i + 1 + insn->off; + if (tgt >= 0 && tgt < insn_cnt) + in_degree[tgt]++; + } + + if (op != BPF_JA && i + 1 < insn_cnt) + in_degree[i + 1]++; + } + + /* Snapshot in-degrees before Pass 3 modifies them. */ + dag->in_degree = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL); + if (!dag->in_degree) + goto fail; + memcpy(dag->in_degree, in_degree, insn_cnt * sizeof(int)); + + /* Pass 2: seed queue with zero-in-degree nodes. */ + for (i = 0; i < insn_cnt; i++) + if (in_degree[i] == 0) + queue[tail++] = i; + + /* Pass 3: Kahn's topological traversal. */ + while (head < tail) { + int node = queue[head++]; + struct bpf_insn *insn = &insns[node]; + u8 cls = BPF_CLASS(insn->code); + u8 op; + + visited++; + + if (is_dummy[node]) + continue; + + op = (cls == BPF_JMP || cls == BPF_JMP32) ? + BPF_OP(insn->code) : 0xff; + + if (op == BPF_EXIT) + continue; + + if (cls == BPF_JMP || cls == BPF_JMP32) { + int tgt = node + 1 + insn->off; + if (tgt >= 0 && tgt < insn_cnt) + if (--in_degree[tgt] == 0) + queue[tail++] = tgt; + if (op != BPF_JA && node + 1 < insn_cnt) + if (--in_degree[node + 1] == 0) + queue[tail++] = node + 1; + } else if (insn->code == (BPF_LD | BPF_IMM | BPF_DW)) { + if (node + 2 < insn_cnt) + if (--in_degree[node + 2] == 0) + queue[tail++] = node + 2; + } else { + if (node + 1 < insn_cnt) + if (--in_degree[node + 1] == 0) + queue[tail++] = node + 1; + } + } + + if (visited != insn_cnt) + goto fail; + + dag->topo_order = queue; + dag->insn_cnt = insn_cnt; + kfree(in_degree); + kfree(is_dummy); + return dag; + +fail: + kfree(queue); + kfree(in_degree); + kfree(is_dummy); + if (dag) { + kfree(dag->in_degree); + kfree(dag); + } + return NULL; +} + +/* + * dag_merge_state() - propagate verifier state to a successor instruction. + * + * First predecessor: copy state (establishes the baseline). + * Subsequent predecessors: conservative merge via merge_verifier_state(). + * + * If path A has R2 = scalar [0,5] and path B has R2 = NOT_INIT, + * the merged result is R2 = NOT_INIT. + * + * merge_verifier_state() is reused unchanged; no new merge semantics. + */ +static int dag_merge_state(struct bpf_verifier_env *env, + struct bpf_verifier_state **states, + int succ, + const struct bpf_verifier_state *from) +{ + if (succ < 0 || succ >= env->prog->len) + return -EINVAL; + + if (!states[succ]) { + states[succ] = kzalloc(sizeof(*states[succ]), GFP_KERNEL); + if (!states[succ]) + return -ENOMEM; + return copy_verifier_state(states[succ], from); + } + + return merge_verifier_state(env, states[succ], from); +} + +/* + * do_check_dag() - verifier fast-path for acyclic BPF programs. + * + * PRESERVES: all register type/bounds propagation, memory access checks, + * stack depth tracking, pointer type validation. + * SKIPS: is_state_visited() / states_equal() equivalence loop. + * + * Processes instructions in topological order (dag->topo_order[]). + * Maintains a per-instruction state table (states[insn_cnt]). + * At join points (dag->in_degree[node] > 1), conservatively merges + * all incoming states via dag_merge_state() BEFORE processing the + * instruction. + */ +static int do_check_dag(struct bpf_verifier_env *env, + const struct bpf_dag_info *dag) +{ + int insn_cnt = env->prog->len; + struct bpf_verifier_state **states; + int err = 0, i; + + states = kcalloc(insn_cnt, sizeof(*states), GFP_KERNEL); + if (!states) + return -ENOMEM; + + states[0] = kzalloc(sizeof(*states[0]), GFP_KERNEL); + if (!states[0]) { + err = -ENOMEM; + goto out; + } + err = init_verifier_state(env, states[0]); + if (err) + goto out; + + for (i = 0; i < insn_cnt; i++) { + int node = dag->topo_order[i]; + struct bpf_verifier_state *cur = states[node]; + struct bpf_insn *insn = &env->prog->insnsi[node]; + u8 cls = BPF_CLASS(insn->code); + u8 op = (cls == BPF_JMP || cls == BPF_JMP32) ? + BPF_OP(insn->code) : 0xff; + + if (!cur) + continue; + + /* + * RFC integration point (Open Question Q1). + * + * This is where the per-instruction verification call goes + * once the integration approach is confirmed by maintainers. + * The state merge logic above and below is independent of + * which option is chosen. + * + * Option A: extract verify_one_insn() from do_check(). + * Option B: add env->dag_mode; do_check() uses dag_states[] + * and skips is_state_visited() when flag is set. + */ + env->cur_state = cur; + if (err) + goto out; + + if (op == BPF_EXIT) + continue; + + if (cls == BPF_JMP || cls == BPF_JMP32) { + if (op == BPF_JA) { + err = dag_merge_state(env, states, + node + 1 + insn->off, cur); + } else { + err = dag_merge_state(env, states, + node + 1 + insn->off, cur); + if (!err) + err = dag_merge_state(env, states, + node + 1, cur); + } + } else if (insn->code == (BPF_LD | BPF_IMM | BPF_DW)) { + err = dag_merge_state(env, states, node + 2, cur); + } else { + err = dag_merge_state(env, states, node + 1, cur); + } + + if (err) + goto out; + } + +out: + for (i = 0; i < insn_cnt; i++) + if (states[i]) + free_verifier_state(states[i], false); + kfree(states); + return err; +} + +/* DAG fast-path hook in do_check_main() */ + { + struct bpf_dag_info *dag = compute_dag_topo(env); + if (dag) { + env->prog->aux->cfg_is_acyclic = 1; + ret = do_check_dag(env, dag); + free_dag_info(dag); + if (ret == 0) + goto out; + env->prog->aux->cfg_is_acyclic = 0; + ret = 0; + } + } + ret = do_check(env); +out: diff --git a/tools/testing/selftests/bpf/test_dag_verify.c b/tools/testing/selftests/bpf/test_dag_verify.c --- a/tools/testing/selftests/bpf/test_dag_verify.c +++ b/tools/testing/selftests/bpf/test_dag_verify.c @@ -0,0 +1,230 @@ +/* + * BPF verifier DAG optimization -- correctness test suite. + * + * Tests: + * 1. Simple DAG (single basic block): must PASS + * 2. OOB access: must REJECT (security preserved) + * 3. Uninitialized register: must REJECT + * 4. DAG with two-branch early-exit (no join): must PASS + * 5. Cyclic program: must PASS via full-verifier fallback + * 6. DAG with join point, R0 init on all paths: must PASS + * 7. DAG with join point, R0 uninit on one path: must REJECT + * (validates conservative merge_verifier_state() at join points) + */ + +#include +#include +#include +#include + +static const struct bpf_insn prog_simple_dag[] = { + BPF_MOV64_IMM(BPF_REG_0, 2), + BPF_EXIT_INSN(), +}; + +static const struct bpf_insn prog_oob_access[] = { + BPF_LD_IMM64(BPF_REG_1, 0xDEADBEEFULL), + BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, 0), + BPF_EXIT_INSN(), +}; + +static const struct bpf_insn prog_uninit_reg[] = { + BPF_MOV64_REG(BPF_REG_0, BPF_REG_9), + BPF_EXIT_INSN(), +}; + +/* + * insn 0: R1 = 1 + * insn 1: if R1 != 0 goto +2 -> insn 4 [path B] + * insn 2: R0 = 1 [path A: fall-through] + * insn 3: exit + * insn 4: R0 = 2 [path B] + * insn 5: exit + * No join point. Both paths exit independently. + */ +static const struct bpf_insn prog_dag_branch[] = { + BPF_MOV64_IMM(BPF_REG_1, 1), + BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, 2), + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 2), + BPF_EXIT_INSN(), +}; + +static const struct bpf_insn prog_cyclic[] = { + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_1, 10, -2), + BPF_MOV64_IMM(BPF_REG_0, 2), + BPF_EXIT_INSN(), +}; + +/* + * insn 0: R1 = 0 + * insn 1: if R1 == 0 goto +2 -> insn 4 [path A] + * insn 2: R0 = 1 [path B: R1 != 0] + * insn 3: goto +1 -> insn 5 + * insn 4: R0 = 2 [path A: R1 == 0] + * fall-through + * insn 5: exit <- JOIN POINT (in_degree = 2) + * + * Path A: 0->1(taken)->4->5 R0 = 2 + * Path B: 0->1(fall)->2->3->5 R0 = 1 + * Merge: R0 = scalar on both paths -> ACCEPT + */ +static const struct bpf_insn prog_dag_join_pass[] = { + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 2), + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_JMP_A(1), + BPF_MOV64_IMM(BPF_REG_0, 2), + BPF_EXIT_INSN(), +}; + +/* + * insn 0: R1 = 0 + * insn 1: if R1 == 0 goto +2 -> insn 4 [path A] + * insn 2: R0 = 1 [path B: R0 set] + * insn 3: goto +1 -> insn 5 + * insn 4: R2 = 99 [path A: R0 NOT set] + * fall-through + * insn 5: exit <- JOIN POINT + * + * Path A: R0 = NOT_INIT at insn 5 + * Path B: R0 = scalar at insn 5 + * Conservative merge: R0 = NOT_INIT -> REJECT + */ +static const struct bpf_insn prog_dag_join_reject[] = { + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 2), + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_JMP_A(1), + BPF_MOV64_IMM(BPF_REG_2, 99), + BPF_EXIT_INSN(), +}; + +void test_dag_verify(void) +{ + char log_buf[4096]; + int prog_fd; + + LIBBPF_OPTS(bpf_prog_load_opts, opts, + .log_buf = log_buf, + .log_size = sizeof(log_buf), + .log_level = 1, + ); + +#define LOAD(insns) \ + bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", \ + insns, ARRAY_SIZE(insns), &opts) + + prog_fd = LOAD(prog_simple_dag); + ASSERT_GT(prog_fd, 0, "test1: simple DAG must load"); + if (prog_fd > 0) close(prog_fd); + + prog_fd = LOAD(prog_oob_access); + ASSERT_LT(prog_fd, 0, "test2: OOB access must be REJECTED"); + + prog_fd = LOAD(prog_uninit_reg); + ASSERT_LT(prog_fd, 0, "test3: uninit register must be REJECTED"); + + prog_fd = LOAD(prog_dag_branch); + ASSERT_GT(prog_fd, 0, "test4: two-branch DAG must load"); + if (prog_fd > 0) close(prog_fd); + + prog_fd = LOAD(prog_cyclic); + ASSERT_GT(prog_fd, 0, "test5: cyclic must load via full-verifier fallback"); + if (prog_fd > 0) close(prog_fd); + + prog_fd = LOAD(prog_dag_join_pass); + ASSERT_GT(prog_fd, 0, "test6: join-point DAG (R0 init all paths) must load"); + if (prog_fd > 0) close(prog_fd); + + prog_fd = LOAD(prog_dag_join_reject); + ASSERT_LT(prog_fd, 0, + "test7: join-point DAG (R0 uninit on path A) must be REJECTED"); +#undef LOAD +}