summaryrefslogtreecommitdiff
path: root/kernel
diff options
context:
space:
mode:
Diffstat (limited to 'kernel')
-rw-r--r--kernel/bpf/verifier.c201
1 files changed, 110 insertions, 91 deletions
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8c1cf2eb6cbb..a431b7d50e1b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2788,8 +2788,13 @@ static void __reg_bound_offset(struct bpf_reg_state *reg)
reg->var_off = tnum_or(tnum_clear_subreg(var64_off), var32_off);
}
+static bool range_bounds_violation(struct bpf_reg_state *reg);
+
static void reg_bounds_sync(struct bpf_reg_state *reg)
{
+ /* If the input reg_state is invalid, we can exit early */
+ if (range_bounds_violation(reg))
+ return;
/* We might have learned new bounds from the var_off. */
__update_reg_bounds(reg);
/* We might have learned something about the sign bit. */
@@ -2804,39 +2809,55 @@ static void reg_bounds_sync(struct bpf_reg_state *reg)
__update_reg_bounds(reg);
}
+static bool range_bounds_violation(struct bpf_reg_state *reg)
+{
+ return (reg->umin_value > reg->umax_value || reg->smin_value > reg->smax_value ||
+ reg->u32_min_value > reg->u32_max_value ||
+ reg->s32_min_value > reg->s32_max_value);
+}
+
+static bool const_tnum_range_mismatch(struct bpf_reg_state *reg)
+{
+ u64 uval = reg->var_off.value;
+ s64 sval = (s64)uval;
+
+ if (!tnum_is_const(reg->var_off))
+ return false;
+
+ return reg->umin_value != uval || reg->umax_value != uval ||
+ reg->smin_value != sval || reg->smax_value != sval;
+}
+
+static bool const_tnum_range_mismatch_32(struct bpf_reg_state *reg)
+{
+ u32 uval32 = tnum_subreg(reg->var_off).value;
+ s32 sval32 = (s32)uval32;
+
+ if (!tnum_subreg_is_const(reg->var_off))
+ return false;
+
+ return reg->u32_min_value != uval32 || reg->u32_max_value != uval32 ||
+ reg->s32_min_value != sval32 || reg->s32_max_value != sval32;
+}
+
static int reg_bounds_sanity_check(struct bpf_verifier_env *env,
struct bpf_reg_state *reg, const char *ctx)
{
const char *msg;
- if (reg->umin_value > reg->umax_value ||
- reg->smin_value > reg->smax_value ||
- reg->u32_min_value > reg->u32_max_value ||
- reg->s32_min_value > reg->s32_max_value) {
- msg = "range bounds violation";
- goto out;
+ if (range_bounds_violation(reg)) {
+ msg = "range bounds violation";
+ goto out;
}
- if (tnum_is_const(reg->var_off)) {
- u64 uval = reg->var_off.value;
- s64 sval = (s64)uval;
-
- if (reg->umin_value != uval || reg->umax_value != uval ||
- reg->smin_value != sval || reg->smax_value != sval) {
- msg = "const tnum out of sync with range bounds";
- goto out;
- }
+ if (const_tnum_range_mismatch(reg)) {
+ msg = "const tnum out of sync with range bounds";
+ goto out;
}
- if (tnum_subreg_is_const(reg->var_off)) {
- u32 uval32 = tnum_subreg(reg->var_off).value;
- s32 sval32 = (s32)uval32;
-
- if (reg->u32_min_value != uval32 || reg->u32_max_value != uval32 ||
- reg->s32_min_value != sval32 || reg->s32_max_value != sval32) {
- msg = "const subreg tnum out of sync with range bounds";
- goto out;
- }
+ if (const_tnum_range_mismatch_32(reg)) {
+ msg = "const subreg tnum out of sync with range bounds";
+ goto out;
}
return 0;
@@ -16765,11 +16786,50 @@ static void find_good_pkt_pointers(struct bpf_verifier_state *vstate,
}));
}
+static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2,
+ u8 opcode, bool is_jmp32);
+static u8 rev_opcode(u8 opcode);
+
+/*
+ * Learn more information about live branches by simulating refinement on both branches.
+ * regs_refine_cond_op() is sound, so producing ill-formed register bounds for the branch means
+ * that branch is dead.
+ */
+static int simulate_both_branches_taken(struct bpf_verifier_env *env, u8 opcode, bool is_jmp32)
+{
+ /* Fallthrough (FALSE) branch */
+ regs_refine_cond_op(&env->false_reg1, &env->false_reg2, rev_opcode(opcode), is_jmp32);
+ reg_bounds_sync(&env->false_reg1);
+ reg_bounds_sync(&env->false_reg2);
+ /*
+ * If there is a range bounds violation in *any* of the abstract values in either
+ * reg_states in the FALSE branch (i.e. reg1, reg2), the FALSE branch must be dead. Only
+ * TRUE branch will be taken.
+ */
+ if (range_bounds_violation(&env->false_reg1) || range_bounds_violation(&env->false_reg2))
+ return 1;
+
+ /* Jump (TRUE) branch */
+ regs_refine_cond_op(&env->true_reg1, &env->true_reg2, opcode, is_jmp32);
+ reg_bounds_sync(&env->true_reg1);
+ reg_bounds_sync(&env->true_reg2);
+ /*
+ * If there is a range bounds violation in *any* of the abstract values in either
+ * reg_states in the TRUE branch (i.e. true_reg1, true_reg2), the TRUE branch must be dead.
+ * Only FALSE branch will be taken.
+ */
+ if (range_bounds_violation(&env->true_reg1) || range_bounds_violation(&env->true_reg2))
+ return 0;
+
+ /* Both branches are possible, we can't determine which one will be taken. */
+ return -1;
+}
+
/*
* <reg1> <op> <reg2>, currently assuming reg2 is a constant
*/
-static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2,
- u8 opcode, bool is_jmp32)
+static int is_scalar_branch_taken(struct bpf_verifier_env *env, struct bpf_reg_state *reg1,
+ struct bpf_reg_state *reg2, u8 opcode, bool is_jmp32)
{
struct tnum t1 = is_jmp32 ? tnum_subreg(reg1->var_off) : reg1->var_off;
struct tnum t2 = is_jmp32 ? tnum_subreg(reg2->var_off) : reg2->var_off;
@@ -16921,7 +16981,7 @@ static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_sta
break;
}
- return -1;
+ return simulate_both_branches_taken(env, opcode, is_jmp32);
}
static int flip_opcode(u32 opcode)
@@ -16992,8 +17052,8 @@ static int is_pkt_ptr_branch_taken(struct bpf_reg_state *dst_reg,
* -1 - unknown. Example: "if (reg1 < 5)" is unknown when register value
* range [0,10]
*/
-static int is_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2,
- u8 opcode, bool is_jmp32)
+static int is_branch_taken(struct bpf_verifier_env *env, struct bpf_reg_state *reg1,
+ struct bpf_reg_state *reg2, u8 opcode, bool is_jmp32)
{
if (reg_is_pkt_pointer_any(reg1) && reg_is_pkt_pointer_any(reg2) && !is_jmp32)
return is_pkt_ptr_branch_taken(reg1, reg2, opcode);
@@ -17031,7 +17091,7 @@ static int is_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_state *reg
}
/* now deal with two scalars, but not necessarily constants */
- return is_scalar_branch_taken(reg1, reg2, opcode, is_jmp32);
+ return is_scalar_branch_taken(env, reg1, reg2, opcode, is_jmp32);
}
/* Opcode that corresponds to a *false* branch condition.
@@ -17122,8 +17182,8 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state
/* u32_min_value is not equal to 0xffffffff at this point,
* because otherwise u32_max_value is 0xffffffff as well,
* in such a case both reg1 and reg2 would be constants,
- * jump would be predicted and reg_set_min_max() won't
- * be called.
+ * jump would be predicted and regs_refine_cond_op()
+ * wouldn't be called.
*
* Same reasoning works for all {u,s}{min,max}{32,64} cases
* below.
@@ -17230,49 +17290,15 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state
}
}
-/* Adjusts the register min/max values in the case that the dst_reg and
- * src_reg are both SCALAR_VALUE registers (or we are simply doing a BPF_K
- * check, in which case we have a fake SCALAR_VALUE representing insn->imm).
- * Technically we can do similar adjustments for pointers to the same object,
- * but we don't support that right now.
- */
-static int reg_set_min_max(struct bpf_verifier_env *env,
- struct bpf_reg_state *true_reg1,
- struct bpf_reg_state *true_reg2,
- struct bpf_reg_state *false_reg1,
- struct bpf_reg_state *false_reg2,
- u8 opcode, bool is_jmp32)
+/* Check for invariant violations on the registers for both branches of a condition */
+static int regs_bounds_sanity_check_branches(struct bpf_verifier_env *env)
{
int err;
- /* If either register is a pointer, we can't learn anything about its
- * variable offset from the compare (unless they were a pointer into
- * the same object, but we don't bother with that).
- */
- if (false_reg1->type != SCALAR_VALUE || false_reg2->type != SCALAR_VALUE)
- return 0;
-
- /* We compute branch direction for same SCALAR_VALUE registers in
- * is_scalar_branch_taken(). For unknown branch directions (e.g., BPF_JSET)
- * on the same registers, we don't need to adjust the min/max values.
- */
- if (false_reg1 == false_reg2)
- return 0;
-
- /* fallthrough (FALSE) branch */
- regs_refine_cond_op(false_reg1, false_reg2, rev_opcode(opcode), is_jmp32);
- reg_bounds_sync(false_reg1);
- reg_bounds_sync(false_reg2);
-
- /* jump (TRUE) branch */
- regs_refine_cond_op(true_reg1, true_reg2, opcode, is_jmp32);
- reg_bounds_sync(true_reg1);
- reg_bounds_sync(true_reg2);
-
- err = reg_bounds_sanity_check(env, true_reg1, "true_reg1");
- err = err ?: reg_bounds_sanity_check(env, true_reg2, "true_reg2");
- err = err ?: reg_bounds_sanity_check(env, false_reg1, "false_reg1");
- err = err ?: reg_bounds_sanity_check(env, false_reg2, "false_reg2");
+ err = reg_bounds_sanity_check(env, &env->true_reg1, "true_reg1");
+ err = err ?: reg_bounds_sanity_check(env, &env->true_reg2, "true_reg2");
+ err = err ?: reg_bounds_sanity_check(env, &env->false_reg1, "false_reg1");
+ err = err ?: reg_bounds_sanity_check(env, &env->false_reg2, "false_reg2");
return err;
}
@@ -17656,7 +17682,11 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
}
is_jmp32 = BPF_CLASS(insn->code) == BPF_JMP32;
- pred = is_branch_taken(dst_reg, src_reg, opcode, is_jmp32);
+ copy_register_state(&env->false_reg1, dst_reg);
+ copy_register_state(&env->false_reg2, src_reg);
+ copy_register_state(&env->true_reg1, dst_reg);
+ copy_register_state(&env->true_reg2, src_reg);
+ pred = is_branch_taken(env, dst_reg, src_reg, opcode, is_jmp32);
if (pred >= 0) {
/* If we get here with a dst_reg pointer type it is because
* above is_branch_taken() special cased the 0 comparison.
@@ -17720,27 +17750,16 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
return PTR_ERR(other_branch);
other_branch_regs = other_branch->frame[other_branch->curframe]->regs;
- if (BPF_SRC(insn->code) == BPF_X) {
- err = reg_set_min_max(env,
- &other_branch_regs[insn->dst_reg],
- &other_branch_regs[insn->src_reg],
- dst_reg, src_reg, opcode, is_jmp32);
- } else /* BPF_SRC(insn->code) == BPF_K */ {
- /* reg_set_min_max() can mangle the fake_reg. Make a copy
- * so that these are two different memory locations. The
- * src_reg is not used beyond here in context of K.
- */
- memcpy(&env->fake_reg[1], &env->fake_reg[0],
- sizeof(env->fake_reg[0]));
- err = reg_set_min_max(env,
- &other_branch_regs[insn->dst_reg],
- &env->fake_reg[0],
- dst_reg, &env->fake_reg[1],
- opcode, is_jmp32);
- }
+ err = regs_bounds_sanity_check_branches(env);
if (err)
return err;
+ copy_register_state(dst_reg, &env->false_reg1);
+ copy_register_state(src_reg, &env->false_reg2);
+ copy_register_state(&other_branch_regs[insn->dst_reg], &env->true_reg1);
+ if (BPF_SRC(insn->code) == BPF_X)
+ copy_register_state(&other_branch_regs[insn->src_reg], &env->true_reg2);
+
if (BPF_SRC(insn->code) == BPF_X &&
src_reg->type == SCALAR_VALUE && src_reg->id &&
!WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
generated by cgit v1.2.3 (git 2.0.4) at 2026-05-28 19:52:10 +0000