Re: [PATCH v5 bpf-next 2/3] bpf: Relax precision marking in open coded iters and may_goto loop.

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2024-06-05 at 17:54 -0700, Alexei Starovoitov wrote:

[...]

This looks interesting, need a bit more time to think about it.
A few minor notes below.

[...]

> @@ -14704,6 +14705,165 @@ static u8 rev_opcode(u8 opcode)
>  	}
>  }
>  
> +/* Similar to mark_reg_unknown() and should only be called from cap_bpf path */
> +static void mark_unknown(struct bpf_reg_state *reg)
> +{
> +	u32 id = reg->id;
> +
> +	__mark_reg_unknown_imprecise(reg);
> +	reg->id = id;
> +}
> +/*
> + * Similar to regs_refine_cond_op(), but instead of tightening the range
> + * widen the upper bound of reg1 based on reg2 and
> + * lower bound of reg2 based on reg1.
> + */
> +static void widen_reg_bounds(struct bpf_reg_state *reg1,
> +			     struct bpf_reg_state *reg2,
> +			     u8 opcode, bool is_jmp32)
> +{
> +	switch (opcode) {
> +	case BPF_JGE:
> +	case BPF_JGT:
> +	case BPF_JSGE:
> +	case BPF_JSGT:
> +		opcode = flip_opcode(opcode);
> +		swap(reg1, reg2);
> +		break;
> +	default:
> +		break;
> +	}
> +
> +	switch (opcode) {
> +	case BPF_JLE:
> +		if (is_jmp32) {
> +			reg1->u32_max_value = reg2->u32_max_value;
> +			reg1->s32_max_value = S32_MAX;
> +			reg1->umax_value = U64_MAX;
> +			reg1->smax_value = S64_MAX;
> +
> +			reg2->u32_min_value = reg1->u32_min_value;
> +			reg2->s32_min_value = S32_MIN;
> +			reg2->umin_value = 0;
> +			reg2->smin_value = S64_MIN;
> +		} else {
> +			reg1->umax_value = reg2->umax_value;
> +			reg1->smax_value = S64_MAX;
> +			reg1->u32_max_value = U32_MAX;
> +			reg1->s32_max_value = S32_MAX;
> +
> +			reg2->umin_value = reg1->umin_value;
> +			reg2->smin_value = S64_MIN;
> +			reg2->u32_min_value = U32_MIN;
> +			reg2->s32_min_value = S32_MIN;
> +		}
> +		reg1->var_off = tnum_unknown;
> +		reg2->var_off = tnum_unknown;
> +		break;

Just a random thought: suppose that one of the registers in question
is used as an index int the array of ints, and compiler increments it
using += 4. Would it be interesting to preserve alignment info in the
var_off in such case? (in other words, preserve known trailing zeros).

[...]

> @@ -15177,8 +15339,78 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>  	}
>  
>  	is_jmp32 = BPF_CLASS(insn->code) == BPF_JMP32;
> +	if (dst_reg->type != SCALAR_VALUE || src_reg->type != SCALAR_VALUE ||
> +	    /* Widen scalars only if they're constants */
> +	    !is_reg_const(dst_reg, is_jmp32) || !is_reg_const(src_reg, is_jmp32))
> +		do_widen = false;
> +	else if (reg_const_value(dst_reg, is_jmp32) == reg_const_value(src_reg, is_jmp32))
> +		/* And not equal */
> +		do_widen = false;
> +	else
> +		do_widen = (get_loop_entry(this_branch) ||
> +			    this_branch->may_goto_depth) &&
> +				/* Gate widen_reg() logic */
> +				env->bpf_capable;
> +
>  	pred = is_branch_taken(dst_reg, src_reg, opcode, is_jmp32);
> -	if (pred >= 0) {
> +
> +	if (do_widen && ((opcode == BPF_JNE && pred == 1) ||
> +			 (opcode == BPF_JEQ && pred == 0))) {
> +		/*
> +		 * != is too vague. let's try < and > and widen. Example:
> +		 *
> +		 * R6=2
> +		 * 21: (15) if r6 == 0x3e8 goto pc+14
> +		 * Predicted == not-taken, but < is also true
> +		 * 21: R6=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=999,var_off=(0x0; 0x3ff))
> +		 */
> +		int refine_pred;
> +		u8 opcode2 = BPF_JLT;
> +
> +		refine_pred = is_branch_taken(dst_reg, src_reg, BPF_JLT, is_jmp32);
> +		if (refine_pred == 1) {
> +			widen_reg(env, dst_reg, src_reg, BPF_JLT, is_jmp32, true);
> +
> +		} else {

nit: would it be possible to avoid second call to is_branch_taken()
     by checking that refine_pred == 0 and assuming opcode2 == BPF_JGE?

> +			opcode2 = BPF_JGT;
> +			refine_pred = is_branch_taken(dst_reg, src_reg, BPF_JGT, is_jmp32);
> +			if (refine_pred == 1)
> +				widen_reg(env, dst_reg, src_reg, BPF_JGT, is_jmp32, true);
> +		}
> +
> +		if (refine_pred == 1) {
> +			if (dst_reg->id)
> +				find_equal_scalars(this_branch, dst_reg);

I think it is necessary to do find_equal_scalars() for src_reg as well,
since widen_reg() could change both registers.

> +			if (env->log.level & BPF_LOG_LEVEL) {
> +				verbose(env, "Predicted %s, but %s is also true\n",
> +					opcode == BPF_JNE ? "!= taken" : "== not-taken",
> +					opcode2 == BPF_JLT ? "<" : ">");
> +				print_insn_state(env, this_branch->frame[this_branch->curframe]);
> +			}
> +			err = mark_chain_precision(env, insn->dst_reg);
> +			if (err)
> +				return err;
> +			if (has_src_reg) {
> +				err = mark_chain_precision(env, insn->src_reg);
> +				if (err)
> +					return err;
> +			}
> +			if (pred == 1)
> +				*insn_idx += insn->off;
> +			return 0;
> +		}
> +		/*
> +		 * No luck. Predicted dst != src taken or dst == src not-taken,
> +		 * but !(dst < src) and !(dst > src).
> +		 * Constants must have been negative.
> +		 */
> +	}
> +
> +	if (do_widen && (opcode == BPF_JNE || opcode == BPF_JEQ || opcode == BPF_JSET))
> +		/* widen_reg() algorithm works for <, <=, >, >= only */
> +		do_widen = false;
> +
> +	if (pred >= 0 && !do_widen) {
>  		/* If we get here with a dst_reg pointer type it is because
>  		 * above is_branch_taken() special cased the 0 comparison.
>  		 */

[...]