summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/linux/bpf_verifier.h10
-rw-r--r--kernel/bpf/scev.c86
-rw-r--r--kernel/bpf/verifier.c49
3 files changed, 143 insertions, 2 deletions
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index d760d2283ac5..308e779c3f74 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -708,6 +708,9 @@ struct bpf_loop_exit {
int to; /* instruction outside the loop */
};
+/* SCEV/widening register space: r0..r10 plus every stack slot of a frame. */
+#define BPF_SCEV_REGS_NUM (MAX_BPF_REG + MAX_BPF_STACK_SLOTS)
+
struct bpf_loop {
struct bpf_backedge backedges[MAX_BACKEDGES];
/* edges exiting from this loop, includes edges from nested loops */
@@ -717,6 +720,12 @@ struct bpf_loop {
bool irreducible;
bool backedges_overflow;
bool exits_overflow;
+ /*
+ * Loop-entry registers used to compute stack addresses for loads,
+ * stores and calls requiring fixed stack offsets, in this and nested
+ * loops.
+ */
+ unsigned long store_base_regs[BITS_TO_LONGS(BPF_SCEV_REGS_NUM)];
};
struct bpf_insn_aux_data {
@@ -1876,6 +1885,7 @@ int bpf_stack_liveness_init(struct bpf_verifier_env *env);
void bpf_stack_liveness_free(struct bpf_verifier_env *env);
int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st);
const unsigned long *bpf_may_write_mask(struct bpf_verifier_env *env, u32 insn_idx);
+bool bpf_needs_fixed_stack_off(struct bpf_verifier_env *env, int insn_idx);
bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 spi);
int bpf_compute_live_registers(struct bpf_verifier_env *env);
diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index 05dd8e439609..adad32d8cb12 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -10,7 +10,7 @@
#include <linux/tnum.h>
#include <linux/overflow.h>
-#define REGS_NUM (MAX_BPF_REG + MAX_BPF_STACK_SLOTS)
+#define REGS_NUM BPF_SCEV_REGS_NUM
#define UNKNOWN_EXPR_ID 0
#define OPAQUE_EXPR_ID 1
@@ -1100,6 +1100,70 @@ static void reset_scevs_at_indirect_writes(struct bpf_verifier_env *env, struct
}
}
+/*
+ * Collect loop-entry registers referenced by expr 'id', best effort.
+ * DEPTH_LIMIT may leave dependencies unrecorded. This mask only avoids
+ * widening that would lose stack-access precision; missing dependencies
+ * may cause false rejections, but this is not a soundness issue.
+ */
+static void or_expr_regs(struct bpf_verifier_env *env, u32 id, unsigned long *mask)
+{
+ struct scev *scev = env->scev;
+ u32 order;
+
+ scev->stack_sz = 0;
+ expr_stack_push(scev, id);
+ while (expr_next(scev, &id, &order)) {
+ if ((order & PRE) && scev->exprs[id].op == REG)
+ __set_bit(scev->exprs[id].params[0], mask);
+ }
+}
+
+/* Mask of argument registers (R1..R5) a call at 'idx' passes by register. */
+static u16 call_params_mask(struct bpf_verifier_env *env, int idx)
+{
+ struct bpf_insn *insn = &env->prog->insnsi[idx];
+ struct bpf_call_summary cs;
+ int n = bpf_get_call_summary(env, insn, &cs) ? cs.arg_slot_cnt : MAX_BPF_FUNC_REG_ARGS;
+
+ return n ? GENMASK(BPF_REG_1 + n - 1, BPF_REG_1) : 0;
+}
+
+/*
+ * For instructions like:
+ * - *(u64 *)(rBase + off) = rX
+ * - rX = *(u64 *)(rBase + off)
+ * - calls that construct objects on stack (e.g. dynptr_from_mem(rBase, ...))
+ * When 'rBase' can be a stack pointer and is derived from some registers Rs
+ * defined at loop entry, record Rs into 'mask'.
+ */
+static void collect_store_base_regs(struct bpf_verifier_env *env,
+ struct env *cur_env, int idx, unsigned long *mask)
+{
+ struct bpf_insn_aux_data *aux = env->insn_aux_data;
+ struct bpf_insn *insn = &env->prog->insnsi[idx];
+ u8 class = BPF_CLASS(insn->code);
+ u8 size = BPF_SIZE(insn->code);
+ u16 base_regs = 0;
+ u32 r;
+
+ if (size == BPF_W || size == BPF_DW) {
+ if ((class == BPF_STX || class == BPF_ST) && insn->dst_reg != BPF_REG_FP)
+ base_regs |= BIT(insn->dst_reg);
+ else if (class == BPF_LDX && insn->src_reg != BPF_REG_FP)
+ base_regs |= BIT(insn->src_reg);
+ }
+
+ if (class == BPF_JMP && BPF_OP(insn->code) == BPF_CALL &&
+ bpf_needs_fixed_stack_off(env, idx))
+ base_regs |= call_params_mask(env, idx);
+
+ base_regs &= aux[idx].stack_ptrs;
+ for (r = 0; r < MAX_BPF_REG; r++)
+ if (base_regs & BIT(r))
+ or_expr_regs(env, cur_env->reg2expr[r], mask);
+}
+
/* Find the topmost loop header containing idx inside cur_header, or -1 if none. */
static int topmost_nested_loop(struct bpf_verifier_env *env, int idx, int cur_header)
{
@@ -1184,6 +1248,7 @@ static int compute_scev_for_loop(struct bpf_verifier_env *env, int cur_header)
struct bpf_iarray *succ;
bool log_level2 = env->log.level & BPF_LOG_LEVEL2;
int s, i, err, idx, succ_idx;
+ u32 r;
if (log_level2)
bpf_log(&env->log, "Computing SCEV for loop at %d:\n", cur_header);
@@ -1197,6 +1262,7 @@ static int compute_scev_for_loop(struct bpf_verifier_env *env, int cur_header)
if (!header_env)
return -ENOMEM;
/* The freshly allocated environment has all expressions unknown. */
+ bitmap_fill(cur_loop->store_base_regs, REGS_NUM);
header_env->empty = false;
return 0;
}
@@ -1233,6 +1299,9 @@ static int compute_scev_for_loop(struct bpf_verifier_env *env, int cur_header)
*/
if (log_level2)
memcpy(old_env, cur_env, sizeof(*old_env));
+ /* Pull the nested loop's stack-store base dependencies up. */
+ for_each_set_bit(r, nested_loop->store_base_regs, BPF_SCEV_REGS_NUM)
+ or_expr_regs(env, cur_env->reg2expr[r], cur_loop->store_base_regs);
forget_non_invariants(env, cur_env, idx);
if (log_level2)
log_env_changes(env, LOG_AT_TRANSFER, old_env, cur_env, idx);
@@ -1254,6 +1323,7 @@ static int compute_scev_for_loop(struct bpf_verifier_env *env, int cur_header)
for (;;) {
if (log_level2)
memcpy(old_env, cur_env, sizeof(*old_env));
+ collect_store_base_regs(env, cur_env, idx, cur_loop->store_base_regs);
err = transfer(env, cur_env, idx);
if (err)
goto out;
@@ -2451,6 +2521,7 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta
for (r = 0; r < REGS_NUM; r++) {
struct bpf_reg_state *reg;
u32 ra, r_scev, r_expr;
+ bool spill_base = false;
if (!scev_reg_alive(env, st, r))
continue;
@@ -2472,6 +2543,11 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta
/* If SCEV for r is (linear <reg> <slope>) */
if (is_simple_linear(scev, r_scev, &base_reg, &slope_imm) &&
reg && is_widenable_reg_type(reg)) {
+ /* Spills at varying offsets lose precision */
+ if (test_bit(r, loop->store_base_regs)) {
+ spill_base = true;
+ goto cant_widen;
+ }
continue;
}
@@ -2481,15 +2557,21 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta
/* (any 1 (any 2 (any 3 4))) */
if (is_widenable_any(env, cur_func, header_env, r, r_scev)) {
+ if (test_bit(r, loop->store_base_regs)) {
+ spill_base = true;
+ goto cant_widen;
+ }
continue;
}
-
+cant_widen:
if (log->level & BPF_LOG_LEVEL2) {
r_expr = header_env->reg2expr[r];
bpf_log(log, "loop header at %d, can't widen ", insn_idx);
log_reg(env, r);
bpf_log(log, ", expr is ");
log_expr(env, r_expr);
+ if (spill_base)
+ bpf_log(log, ", requires exact stack-offset tracking");
bpf_log(log, "\n");
}
return 0;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a597a8c18972..2f190abe3448 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14257,6 +14257,55 @@ static bool kfunc_spin_allowed(struct bpf_verifier_env *env, s32 func_id, s16 of
return *kfunc.flags & KF_SPINLOCK_SAFE;
}
+/*
+ * True if insn calls a helper/kfunc that requires one of its arguments to
+ * be a stack pointer with a constant offset.
+ */
+bool bpf_needs_fixed_stack_off(struct bpf_verifier_env *env, int insn_idx)
+{
+ const struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
+ const struct bpf_func_proto *fn;
+ struct bpf_kfunc_desc *desc;
+ u32 *flags, btf_id;
+ int i;
+
+ if (bpf_helper_call(insn)) {
+ if (bpf_get_helper_proto(env, insn->imm, &fn) < 0)
+ return false;
+ } else if (bpf_pseudo_kfunc_call(insn)) {
+ desc = find_kfunc_desc(env->prog, insn->imm, insn->off);
+ if (!desc)
+ return false;
+ fn = &desc->proto;
+ } else {
+ return false;
+ }
+
+ /* Both initialized and uninitialized stack dynptrs need a fixed offset. */
+ for (i = 0; i < ARRAY_SIZE(fn->arg_type); i++)
+ if (arg_type_is_dynptr(fn->arg_type[i]))
+ return true;
+
+ /* vmlinux kfuncs only */
+ if (!bpf_pseudo_kfunc_call(insn) || insn->off != 0)
+ return false;
+ btf_id = insn->imm;
+
+ flags = btf_kfunc_flags(btf_vmlinux, btf_id, env->prog);
+ if (flags && (*flags & (KF_ITER_NEW | KF_ITER_NEXT | KF_ITER_DESTROY)))
+ return true;
+
+ if (btf_id == special_kfunc_list[KF_bpf_res_spin_lock] ||
+ btf_id == special_kfunc_list[KF_bpf_res_spin_unlock] ||
+ btf_id == special_kfunc_list[KF_bpf_res_spin_lock_irqsave] ||
+ btf_id == special_kfunc_list[KF_bpf_res_spin_unlock_irqrestore] ||
+ btf_id == special_kfunc_list[KF_bpf_local_irq_save] ||
+ btf_id == special_kfunc_list[KF_bpf_local_irq_restore])
+ return true;
+
+ return false;
+}
+
static bool is_sync_callback_calling_kfunc(u32 btf_id)
{
return is_bpf_rbtree_add_kfunc(btf_id);
generated by cgit v1.2.3 (git 2.0.4) at 2026-10-30 20:44:54 +0000