Re: [PATCH stable 6.6.y v3 1/4] bpf: Track equal scalars history on per-instruction level

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Flawed tracking of linked registers in collect_linked_regs() wastes array capacity, leading to silent clearing of valid scalar IDs and precision loss.
--

commit 1fe1c2de8417cc37930a0c9654b28c2004c45842
Author: Eduard Zingerman <eddyz87@gmail.com>
Subject: bpf: Track equal scalars history on per-instruction level

This commit tracks registers updated by collect_linked_regs() during
conditional jumps using jmp_history, and propagates precision via
backtrack_insn().

Link: https://lore.kernel.org/bpf/20240718202357.1746514-2-eddyz87@gmail.com
Closes: https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -14699,19 +14699,78 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>  	return true;
>  }
>  
> -static void find_equal_scalars(struct bpf_verifier_state *vstate,
> -			       struct bpf_reg_state *known_reg)
> +static void __collect_linked_regs(struct linked_regs *reg_set, struct bpf_reg_state *reg,
> +				  u32 id, u32 frameno, u32 spi_or_reg, bool is_reg)
>  {
> -	struct bpf_func_state *state;
> +	struct linked_reg *e;
> +
> +	if (reg->type != SCALAR_VALUE || reg->id != id)
> +		return;
> +
> +	e = linked_regs_push(reg_set);
> +	if (e) {
> +		e->frameno = frameno;
> +		e->is_reg = is_reg;
> +		e->regno = spi_or_reg;
> +	} else {
> +		reg->id = 0;
> +	}

[Severity: High]
When the array capacity is exhausted (which could happen prematurely due
to the duplication and cleanup issues mentioned below), this silently clears
reg->id = 0.

Could this precision loss cause the verifier to unnecessarily reject valid BPF
programs that rely on equal scalar precision propagation?

> +}
> +
> +/* For all R being scalar registers or spilled scalar registers
> + * in verifier state, save R in linked_regs if R->id == id.
> + * If there are too many Rs sharing same id, reset id for leftover Rs.
> + */
> +static void collect_linked_regs(struct bpf_verifier_state *vstate, u32 id,
> +				struct linked_regs *linked_regs)
> +{

[ ... ]

> +	for (i = vstate->curframe; i >= 0; i--) {
> +		func = vstate->frame[i];
> +		for (j = 0; j < BPF_REG_FP; j++) {
> +			reg = &func->regs[j];
> +			__collect_linked_regs(linked_regs, reg, id, i, j, true);
> +		}
> +		for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) {
> +			if (!is_spilled_reg(&func->stack[j]))
> +				continue;
> +			reg = &func->stack[j].spilled_ptr;
> +			__collect_linked_regs(linked_regs, reg, id, i, j, false);
> +		}
> +	}
> +
> +	if (linked_regs->cnt == 1)
> +		linked_regs->cnt = 0;
> +}

[Severity: High]
Does this correctly discard isolated registers if the array is already
populated?

If linked_regs already contains elements from a previous
collect_linked_regs() call for src_reg, adding a single isolated dst_reg
will increase the total count beyond 1. This bypasses the linked_regs->cnt == 1
cleanup logic, leaving the isolated register in the array and wasting capacity.

[ ... ]

> @@ -14899,6 +14899,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>  		return 0;
>  	}
>  
> +	/* Push scalar registers sharing same ID to jump history,
> +	 * do this before creating 'other_branch', so that both
> +	 * 'this_branch' and 'other_branch' share this history
> +	 * if parent state is created.
> +	 */
> +	if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
> +		collect_linked_regs(this_branch, src_reg->id, &linked_regs);
> +	if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
> +		collect_linked_regs(this_branch, dst_reg->id, &linked_regs);

[Severity: High]
If src_reg->id and dst_reg->id are identical, does this sequence append
all associated registers into linked_regs twice? Since LINKED_REGS_MAX is
only 6, this duplication might quickly exhaust the array capacity.

> +	if (linked_regs.cnt > 0) {
> +		err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
> +		if (err)
> +			return err;
> +	}

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1781194510.git.jt26wzz@gmail.com?part=1