From: Alexei Starovoitov r1 = r6 r1 &= 255 if r1 > 29 goto out /* r6 is used */ Scalar evolution tells refine_linked_regs() that r6 and r1 are equal in their low 8 bits. For other registers it is 16, 32 or 64 bits. The function intersects the two by hand: are they equal in all bits because both fit, do the known bits overlap, the 32-bit ranges, the 64-bit ranges, the reduction, and back to the saved register if nothing is left. The next patches compute the value of an expression in scev.c. A value can be known from more than one source there, what a register holds and what the operands give, in a number of bits each. The sources are intersected by the same rules. Move the rules into scalar_intersect(dst, src, bits), an operation on struct scalar like scalar_add() and scalar_alu(). No functional change. Signed-off-by: Alexei Starovoitov --- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 70 ++++++++++++++++++++++-------------- 2 files changed, 45 insertions(+), 26 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 15528f3a352e..516e704c3d7d 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -2071,6 +2071,7 @@ void scalar_set_const(struct scalar *s, u64 imm); void scalar_add(struct scalar *dst, const struct scalar *a, const struct scalar *b); void scalar_alu(struct scalar *dst, const struct scalar *src, const struct bpf_insn *insn); void scalar_zext32(struct scalar *s); +bool scalar_intersect(struct scalar *dst, const struct scalar *src, u32 bits); void scalar_union(struct scalar *acc, const struct scalar *src); int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, const struct scalar *range); diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 9721530636e3..47ed36292e1b 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -19394,6 +19394,46 @@ static bool scalars_fit_in_bits(const struct scalar *a, const struct scalar *b, cnum64_smin(b->r64) >= -smax - 1 && cnum64_smax(b->r64) <= smax); } +/* + * The values of @dst and @src are equal in their low @bits bits: @dst becomes the intersection. + * False: @dst is left as it is. Fewer than 32 bits say nothing about a range. Or the intersection + * is empty: no execution gets here with these values, the path is infeasible. + */ +bool scalar_intersect(struct scalar *dst, const struct scalar *src, u32 bits) +{ + struct tnum a = dst->var_off, b = src->var_off; + struct scalar s = *dst; + + if (scalars_fit_in_bits(dst, src, bits)) + bits = 64; + if (bits < 32) + return false; + if (bits < 64) { + a = tnum_subreg(a); + b = tnum_subreg(b); + } + /* tnum_intersect() of two tnums that don't overlap is not empty */ + if (!tnum_overlap(a, b)) + return false; + /* + * Equal in 64 bits is equal in the low 32 bits too. 'if w1 s> 200' on a zero extended int + * refines nothing but the 32-bit range. + */ + s.r32 = cnum32_intersect(dst->r32, src->r32); + if (bits == 64) { + s.r64 = cnum64_intersect(dst->r64, src->r64); + s.var_off = tnum_intersect(a, b); + } else { + s.var_off = tnum_with_subreg(dst->var_off, tnum_intersect(a, b)); + } + scalar_bounds_sync(&s); + if (scalar_is_empty(&s) || const_tnum_range_mismatch(&s) || + const_tnum_range_mismatch_32(&s)) + return false; + *dst = s; + return true; +} + /* * The state of the SCEV register @r. As in check_stack_read_fixed_off() a fill of @bits bits from * byte @fill_off of the slot reads the low bits of the spill. @@ -19494,7 +19534,7 @@ static void refine_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier int idx, u32 regno) { struct bpf_func_state *frame = vstate->frame[vstate->curframe], *linked_frame; - struct bpf_reg_state *reg, *base_reg, implied, saved; + struct bpf_reg_state *reg, *base_reg, implied; u32 pos, linked_regno, fill_off, bits; int base_regno; s64 delta; @@ -19527,33 +19567,11 @@ static void refine_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier add_scalar_to_reg(&implied, delta); if (base_regno >= 0) { base_reg = scev_reg_for_fill(frame, base_regno, 0, 64); - if (base_reg && bits == 64 && recompute_ptr(env, reg, base_reg, &implied)) - goto scratch; - continue; - } - if (scalars_fit_in_bits(scalar_of(reg), scalar_of(&implied), bits)) - bits = 64; - if (bits < 32) - continue; - /* tnum_intersect() of two tnums that don't overlap is not empty */ - if (!tnum_overlap(bits == 32 ? tnum_subreg(reg->var_off) : reg->var_off, - bits == 32 ? tnum_subreg(implied.var_off) : implied.var_off)) - continue; - saved = *reg; - /* - * Equal in 64 bits is equal in the low 32 bits too. 'if w1 s> 200' on a zero - * extended int refines nothing but the 32-bit range. - */ - scalars_refine_cond_op(scalar_of(reg), scalar_of(&implied), BPF_JEQ, true); - if (bits == 64) - scalars_refine_cond_op(scalar_of(reg), scalar_of(&implied), BPF_JEQ, false); - reg_bounds_sync(reg); - if (reg_is_empty(reg) || const_tnum_range_mismatch(scalar_of(reg)) || - const_tnum_range_mismatch_32(scalar_of(reg))) { - *reg = saved; + if (!base_reg || bits < 64 || !recompute_ptr(env, reg, base_reg, &implied)) + continue; + } else if (!scalar_intersect(scalar_of(reg), scalar_of(&implied), bits)) { continue; } -scratch: if (linked_regno < MAX_BPF_REG) mark_reg_scratched(env, linked_regno); else if (linked_frame == frame) -- 2.55.0