Re: [PATCH bpf-next 24/36] bpf: compute scalar evolution expressions for loops

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] bpf: NULL pointer dereference in compute_insn_scevs() for loops with exits_overflow
- [Medium] bpf: Incorrect SCEV modeling of BPF_END no-op conversions preserves truncated bits
--

commit 3c85c59367498a632c83889db787693adfac36e5
Author: Eduard Zingerman <eddyz87@gmail.com>
Subject: bpf: compute scalar evolution expressions for loops

This patch assigns algebraic expressions to loop variables (registers and
stack spills) to describe how their values evolve across iterations. The
analysis proceeds in two phases: computing expressions for one symbolic
iteration and converting backedge updates to recurrences.

> diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
> new file mode 100644
> index 0000000000000..396b0c776dfae
> --- /dev/null
> +++ b/kernel/bpf/scev.c
[ ... ]
> @@ -713,29 +713,25 @@ static int transfer(struct bpf_verifier_env *env, struct env *e, int idx)
[ ... ]
> +		case BPF_END:
> +			switch (insn->imm) {
> +			case 16: op = BSWAP16; break;
> +			case 32: op = BSWAP32; break;
> +			case 64: op = BSWAP64; break;
> +			default:
> +				goto mark_dst_unknown;
> +			}
> +
> +			if (class == BPF_ALU && x_or_k == BPF_TO_LE && insn->off == 0 && little_endian)
> +				op = 0; /* little-endian to little-endian is noop */

[Severity: Medium]
Can this skip the required 16-bit truncation semantics?

When a BPF_END instruction is a 16-bit endianness conversion (imm == 16)
and acts as a no-op on the current architecture, op is set to 0.

Because op is 0, the explicit truncation operation (like ZEXT16) is skipped
below. Only ZEXT32 is applied to the register:

kernel/bpf/scev.c:transfer() {
    id = reg2expr[dst];
    if (op)
        id = expr1(scev, op, reg2expr[dst]);

    if (class == BPF_ALU)
        id = expr1(scev, ZEXT32, id);
    ...
}

The verifier and hardware will still truncate the register to 16 bits,
zeroing bits 16-63. By skipping this in the algebraic model, does it
incorrectly preserve bits 16-31 of the original register?

> +			else if (class == BPF_ALU && x_or_k == BPF_TO_BE && insn->off == 0 && !little_endian)
> +				op = 0; /* big-endian to big-endian is noop */
> +			else if (class == BPF_ALU64 && x_or_k == 0 && insn->off == 0)
> +				/* always swap */;
> +			else
> +				goto mark_dst_unknown;
> +
> +			id = reg2expr[dst];
> +			if (op)
> +				id = expr1(scev, op, reg2expr[dst]);
> +
> +			if (class == BPF_ALU)
> +				id = expr1(scev, ZEXT32, id);
> +
> +			return replace_reg(scev, e, dst, id);
[ ... ]
> @@ -1172,13 +1172,13 @@ static void mark_latches(struct bpf_verifier_env *env)
> +	for (i = 0; i < len; i++) {
> +		loop = aux[i].loop;
> +		if (!loop)
> +			continue;
> +		aux[i].need_scev = true;
> +		if (loop->irreducible)
> +			continue;

[Severity: High]
Does this code result in a NULL pointer dereference when a loop has an
exits_overflow condition?

Loops with exits_overflow are not skipped here (unlike irreducible loops),
so their latches are marked with aux[latch].need_scev = true.

However, compute_scev_for_loop() bails out early for exits_overflow loops
and does not allocate a loop environment for the latch:

kernel/bpf/scev.c:compute_scev_for_loop() {
    if (cur_loop->irreducible || cur_loop->exits_overflow) {
        header_env = get_loop_env(scev, cur_header, cur_header);
        ...
        return 0;
    }
    ...
}

Later, when bpf_compute_scev() visits the latch, it calls
compute_insn_scevs(), passing the result of find_loop_env(). Since the
environment was never created, find_loop_env() returns NULL.

This results in einsn being NULL in compute_insn_scevs():

kernel/bpf/scev.c:compute_insn_scevs() {
    ...
    for (reg = 0; reg < REGS_NUM; reg++) {
        id = einsn->reg2expr[reg];
}

Should exits_overflow loops be skipped here similarly to irreducible loops?

> +		for (j = 0; j < loop->backedges_cnt; j++) {
> +			latch = loop->backedges[j].latch;
> +			if (latch >= 0)
> +				aux[latch].need_scev = true;
> +		}
> +	}
> +}

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260926-scev-minimal-rebase-v1-0-c8e5ab5ba79f@gmail.com?part=24