SCEV needs to find an exit condition that dominates a loop's backedge; such conditions bound every loop iteration. Compute the immediate dominator tree as a prerequisite for identifying such conditions. Use the iterative reverse-postorder algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper et al. Signed-off-by: Eduard Zingerman --- include/linux/bpf_verifier.h | 8 +++ kernel/bpf/Makefile | 2 +- kernel/bpf/loops.c | 158 +++++++++++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 8 ++- 4 files changed, 174 insertions(+), 2 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index bd7733fbe930..59c0670af0e9 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -650,6 +650,11 @@ struct bpf_iarray { u32 items[]; }; +#define iarray_for_each(item, arr) \ + for (int ___idx = 0; \ + ___idx < (arr)->cnt && ({ item = (arr)->items[___idx]; 1; }); \ + ___idx++) + struct bpf_insn_aux_data { union { enum bpf_reg_type ptr_type; /* pointer type for load/store insns */ @@ -1112,6 +1117,7 @@ struct bpf_verifier_env { u32 scc_cnt; struct bpf_iarray *succ; struct bpf_iarray *gotox_tmp_buf; + int *idoms; }; static inline struct bpf_func_info_aux *subprog_aux(struct bpf_verifier_env *env, int subprog) @@ -1888,4 +1894,6 @@ int bpf_insn_def32(struct bpf_prog *prog, struct bpf_insn *insn); int bpf_flip_opcode(u32 opcode); u8 bpf_rev_opcode(u8 opcode); +int bpf_compute_idoms(struct bpf_verifier_env *env); + #endif /* _LINUX_BPF_VERIFIER_H */ diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile index c1f9b0d3468d..6210601eb40b 100644 --- a/kernel/bpf/Makefile +++ b/kernel/bpf/Makefile @@ -6,7 +6,7 @@ cflags-nogcse-$(CONFIG_X86)$(CONFIG_CC_IS_GCC) := -fno-gcse endif CFLAGS_core.o += -Wno-override-init $(cflags-nogcse-yy) -obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o cnum.o log.o token.o liveness.o const_fold.o diagnostics.o +obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o cnum.o log.o token.o liveness.o const_fold.o diagnostics.o loops.o obj-$(CONFIG_BPF_SYSCALL) += bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o bpf_insn_array.o diff --git a/kernel/bpf/loops.c b/kernel/bpf/loops.c new file mode 100644 index 000000000000..0db823ee42f7 --- /dev/null +++ b/kernel/bpf/loops.c @@ -0,0 +1,158 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ + +#include +#include +#include + +static struct bpf_iarray **compute_predecessors(struct bpf_verifier_env *env) +{ + struct bpf_iarray *succ, *preds, **result; + struct bpf_prog *prog = env->prog; + u32 *num_preds, i, s, len = prog->len; + struct bpf_insn *insn; + size_t sz; + void *tmp; + + num_preds = kvcalloc(prog->len, sizeof(u32), GFP_KERNEL_ACCOUNT); + if (!num_preds) + return NULL; + + /* + * 'result' layout: + * - array of pointers (struct bpf_iarray *)[len] + * - struct bpf_iarray one after another + */ + sz = size_mul(len, sizeof(*result) + sizeof(**result)); + for (i = 0; i < len; i++) { + insn = env->prog->insnsi + i; + succ = bpf_insn_successors(env, i); + sz = size_add(sz, array_size(succ->cnt, sizeof(*succ->items))); + iarray_for_each(s, succ) { + num_preds[s]++; + } + if (bpf_is_ldimm64(insn)) + i++; + } + + result = kvzalloc(sz, GFP_KERNEL_ACCOUNT); + if (!result) { + kvfree(num_preds); + return NULL; + } + + tmp = (void *)&result[len]; + for (i = 0; i < len; i++) { + result[i] = tmp; + tmp += struct_size(result[i], items, num_preds[i]); + } + + for (i = 0; i < len; i++) { + insn = env->prog->insnsi + i; + succ = bpf_insn_successors(env, i); + iarray_for_each(s, succ) { + preds = result[s]; + preds->items[preds->cnt++] = i; + } + if (bpf_is_ldimm64(insn)) + i++; + } + + kvfree(num_preds); + return result; +} + +static int idoms_intersect(struct bpf_verifier_env *env, int a, int b) +{ + int *postorder_nums = env->cfg.postorder_nums; + int *idoms = env->idoms; + + while (a != b) { + while (postorder_nums[a] < postorder_nums[b]) { + a = idoms[a]; + } + while (postorder_nums[b] < postorder_nums[a]) { + b = idoms[b]; + } + } + return a; +} + +/* See "A Simple, Fast Dominance Algorithm" by Cooper et al. for details. */ +static int compute_subprog_idoms(struct bpf_verifier_env *env, struct bpf_iarray **preds, + int subprog_idx) +{ + struct bpf_subprog_info *subprog = &env->subprog_info[subprog_idx]; + int start = subprog->start; + int po_first = subprog->postorder_start; + int po_last = (subprog + 1)->postorder_start - 1; + int *idoms = env->idoms; + int po_num, pred; + u32 work = 0; + bool changed; + + idoms[start] = start; + changed = true; + do { + changed = false; + /* + * Iterate in reverse postorder, skipping the subprog entry: + * insn_postorder[po_last] is the subprogram entry. + */ + for (po_num = po_last - 1; po_num >= po_first; po_num--) { + int idx = env->cfg.insn_postorder[po_num]; + int new_idom = -1; + + iarray_for_each(pred, preds[idx]) { + if (++work % 1024 == 0) { + if (signal_pending(current)) + return -EAGAIN; + cond_resched(); + } + + if (idoms[pred] == -1) + continue; + if (new_idom == -1) + new_idom = pred; + else + new_idom = idoms_intersect(env, pred, new_idom); + } + if (new_idom != -1 && idoms[idx] != new_idom) { + idoms[idx] = new_idom; + changed = true; + } + } + } while (changed); + idoms[start] = -1; + return 0; +} + +int bpf_compute_idoms(struct bpf_verifier_env *env) +{ + struct bpf_iarray **preds; + u32 len = env->prog->len; + int *idoms, i, err = 0; + + preds = compute_predecessors(env); + if (!preds) + return -ENOMEM; + + idoms = kvcalloc(len, sizeof(*idoms), GFP_KERNEL_ACCOUNT); + if (!idoms) { + kvfree(preds); + return -ENOMEM; + } + + env->idoms = idoms; + for (i = 0; i < len; i++) + idoms[i] = -1; + + for (i = 0; i < env->subprog_cnt; i++) { + err = compute_subprog_idoms(env, preds, i); + if (err) + break; + } + + kvfree(preds); + return err; +} diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 9260ee290072..5a29d05c523c 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -22872,13 +22872,14 @@ static void log_program(struct bpf_verifier_env *env) u64 pos, insn_pos; u32 i, j; - verbose(env, "Program dump (scc? insn#: live_regs_before):\n"); + verbose(env, "Program dump (scc? idom insn#: live_regs_before):\n"); for (i = 0; i < insn_cnt; ++i) { verbose_linfo(env, i, " ; "); if (env->insn_aux_data[i].scc) verbose(env, "%3d ", env->insn_aux_data[i].scc); else verbose(env, " "); + verbose(env, "%3d ", env->idoms[i]); verbose(env, "%3d: ", i); for (j = BPF_REG_0; j < BPF_REG_10; ++j) if (insn_aux[i].live_regs_before & BIT(j)) @@ -23103,6 +23104,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, prepare_subprog_args(env); + ret = bpf_compute_idoms(env); + if (ret < 0) + goto skip_full_check; + ret = bpf_compute_live_registers(env); if (ret < 0) goto skip_full_check; @@ -23266,6 +23271,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, kvfree(env->callx_edges); kvfree(env->func_ptrs); bpf_diag_free(env); + kvfree(env->idoms); kvfree(env); return ret; } -- 2.53.0