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.
> */
[...]
