* [PATCH bpf-next] bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension
@ 2026-08-20 1:39 Yonghong Song
2026-08-20 2:33 ` bot+bpf-ci
2026-08-20 16:57 ` Eduard Zingerman
0 siblings, 2 replies; 4+ messages in thread
From: Yonghong Song @ 2026-08-20 1:39 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Eduard Zingerman, kernel-team
For the following test in
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c:
void alu32_negative_offset(void)
{
volatile char path[5];
volatile int offset = bpf_get_prandom_u32();
int off = offset;
if (off >= 5 && off < 10)
path[off - 5] = '.';
/* So compiler doesn't say: error: variable 'path' set but not used */
__sink(path[0]);
}
Without alu32 (-mcpu=v2), the test
verifier_linked_scalars/alu32_negative_offset will fail with llvm22 and
llvm23 like below.
3: (bf) r2 = r1 ; R1=scalar(id=1,...) R2=scalar(id=1,...)
4: (07) r2 += -5 ; R2=scalar(id=1-5,smin=-5,smax=0xfffffffa)
5: (67) r2 <<= 32 ; R2=scalar(smax=0x7fffffff00000000,...)
6: (77) r2 >>= 32 ; R2=scalar(smin=0,umax=0xffffffff,...)
7: (25) if r2 > 0x4 goto pc+5 ; R2=scalar(smin=0,smax=umax=4,...)
8: (bf) r2 = r10
9: (07) r2 += -5
10: (0f) r2 += r1 ; R1=scalar(id=1,smin=0,umax=0xffffffff)
; R2=fp(smin=-5,smax=0xfffffffa)
11: (b7) r1 = 46 ; R1=46
12: (73) *(u8 *)(r2 -5) = r1
invalid unbounded variable-offset write to stack R2
R1 is never narrowed down, so the address stays unbounded and the store
is rejected.
The test is okay for llvm21 with -mcpu=v2, see below:
3: (07) r1 += -5 ; R1=scalar(smin=-5,smax=0xfffffffa)
4: (67) r1 <<= 32 ; R1=scalar(smax=0x7fffffff00000000,...)
5: (77) r1 >>= 32 ; R1=scalar(smin=0,umax=0xffffffff,...)
6: (25) if r1 > 0x4 goto pc+5 ; R1=scalar(smin=0,smax=umax=4,...)
7: (bf) r2 = r10
8: (07) r2 += -5
9: (0f) r2 += r1 ; R2=fp(smin=-5,smax=-1)
10: (b7) r1 = 46 ; R1=46
11: (73) *(u8 *)(r2 +0) = r1 ; fp-8=ppppm???
To fix the test issue with llvm22 and llvm23, note that the shift pair
computes zext32(base + delta), which is exactly the relation
BPF_ADD_CONST32 describes. So keep the link alive across the first
shift and turn it from a 64-bit into a 32-bit one at the second, which
makes the -mcpu=v2 sequence track like an alu32 one.
Two conditions guard this. First, a 32-bit link requires the linked
value to fit into u32, because sync_linked_regs() zero extends the
bounds it propagates through such a link. linked_base_fits_u32() checks
that on the register state before the shift, mirroring the dst_umax
check the alu32 add path already does. Second, in between the two
shifts the register does not hold the value its id and delta describe,
so the second shift must have a single incoming edge, otherwise the
intermediate state could be checkpointed and another path pruned
against it.
With this, the llvm22 and llvm23 code verifies, R2 keeps its id through
both shifts and the jump narrows down R1:
3: (bf) r2 = r1 ; R1=scalar(id=1,...) R2=scalar(id=1,...)
4: (07) r2 += -5 ; R2=scalar(id=1-5,smin=-5,smax=0xfffffffa)
5: (67) r2 <<= 32 ; R2=scalar(id=1-5,smax=0x7fffffff00000000)
6: (77) r2 >>= 32 ; R2=scalar(id=1-5,smin=0,umax=0xffffffff)
7: (25) if r2 > 0x4 goto pc+5 ; R1=scalar(id=1,smin=5,smax=9,...)
; R2=scalar(id=1-5,smin=0,smax=4,...)
8: (bf) r2 = r10
9: (07) r2 += -5
10: (0f) r2 += r1 ; R2=fp(smin=0,smax=4)
11: (b7) r1 = 46 ; R1=46
12: (73) *(u8 *)(r2 -5) = r1 ; fp-8=ppppm???
The llvm21 log is unchanged, R1 carries no id there so the new code
does not apply to it.
Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
kernel/bpf/verifier.c | 50 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 50 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e421ea2b80c3..0fded097505e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15584,6 +15584,50 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
return 0;
}
+static bool linked_base_fits_u32(const struct bpf_reg_state *reg)
+{
+ if (reg->id & BPF_ADD_CONST32)
+ return true;
+ return reg_smin(reg) >= (s64)reg->delta &&
+ reg_smax(reg) <= (s64)U32_MAX + (s64)reg->delta;
+}
+
+static bool is_shift32_insn(const struct bpf_insn *insn, u8 op)
+{
+ return insn->code == (BPF_ALU64 | op | BPF_K) && insn->off == 0 && insn->imm == 32;
+}
+
+/* Handle "rX <<= 32; rX >>= 32", which zero extends the lower 32 bits. */
+static bool is_zext_pair_lsh(struct bpf_verifier_env *env, struct bpf_insn *insn,
+ const struct bpf_reg_state *dst_reg)
+{
+ struct bpf_insn *next;
+ int insn_idx = env->insn_idx;
+
+ if (!dst_reg->id || !is_shift32_insn(insn, BPF_LSH))
+ return false;
+ /* check_subprogs() guarantees a shift is never the last insn. */
+ next = &env->prog->insnsi[insn_idx + 1];
+ if (!is_shift32_insn(next, BPF_RSH) || next->dst_reg != insn->dst_reg)
+ return false;
+ /* Ensure the next insn has a single incoming edge. */
+ return !bpf_is_prune_point(env, insn_idx + 1);
+}
+
+static bool is_zext_pair_rsh(struct bpf_verifier_env *env, struct bpf_insn *insn,
+ const struct bpf_reg_state *dst_reg)
+{
+ struct bpf_insn *prev;
+ int insn_idx = env->insn_idx;
+
+ if (!dst_reg->id || insn_idx == 0 || env->prev_insn_idx != insn_idx - 1)
+ return false;
+ if (!is_shift32_insn(insn, BPF_RSH))
+ return false;
+ prev = &env->prog->insnsi[insn_idx - 1];
+ return is_shift32_insn(prev, BPF_LSH) && prev->dst_reg == insn->dst_reg;
+}
+
/* Handles ALU ops other than BPF_END, BPF_NEG and BPF_MOV: computes new min/max
* and var_off.
*/
@@ -15694,6 +15738,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
* alu32 ops will have zero-extended the result, making umax_value <= U32_MAX.
*/
u64 dst_umax = reg_umax(dst_reg);
+ bool base_fits_u32 = linked_base_fits_u32(dst_reg);
err = adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg);
if (err)
@@ -15743,6 +15788,11 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
dst_reg->id |= BPF_ADD_CONST64;
dst_reg->delta = off;
}
+ } else if (base_fits_u32 && is_zext_pair_lsh(env, insn, dst_reg)) {
+ /* Keep id and delta, the next insn completes the pair. */
+ } else if (is_zext_pair_rsh(env, insn, dst_reg)) {
+ if (dst_reg->id & BPF_ADD_CONST64)
+ dst_reg->id = (dst_reg->id & ~BPF_ADD_CONST64) | BPF_ADD_CONST32;
} else {
/*
* Make sure ID is cleared otherwise dst_reg min/max could be
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH bpf-next] bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension
2026-08-20 1:39 [PATCH bpf-next] bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension Yonghong Song
@ 2026-08-20 2:33 ` bot+bpf-ci
2026-08-20 16:57 ` Eduard Zingerman
1 sibling, 0 replies; 4+ messages in thread
From: bot+bpf-ci @ 2026-08-20 2:33 UTC (permalink / raw)
To: yonghong.song, bpf
Cc: ast, andrii, daniel, eddyz87, kernel-team, ast, andrii, daniel,
martin.lau, eddyz87, yonghong.song, clm, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 3050 bytes --]
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index e421ea2b80c3..0fded097505e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -15584,6 +15584,50 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> return 0;
> }
>
> +static bool linked_base_fits_u32(const struct bpf_reg_state *reg)
> +{
> + if (reg->id & BPF_ADD_CONST32)
> + return true;
> + return reg_smin(reg) >= (s64)reg->delta &&
> + reg_smax(reg) <= (s64)U32_MAX + (s64)reg->delta;
> +}
> +
> +static bool is_shift32_insn(const struct bpf_insn *insn, u8 op)
> +{
> + return insn->code == (BPF_ALU64 | op | BPF_K) && insn->off == 0 && insn->imm == 32;
> +}
> +
> +/* Handle "rX <<= 32; rX >>= 32", which zero extends the lower 32 bits. */
> +static bool is_zext_pair_lsh(struct bpf_verifier_env *env, struct bpf_insn *insn,
> + const struct bpf_reg_state *dst_reg)
> +{
> + struct bpf_insn *next;
> + int insn_idx = env->insn_idx;
> +
> + if (!dst_reg->id || !is_shift32_insn(insn, BPF_LSH))
> + return false;
> + /* check_subprogs() guarantees a shift is never the last insn. */
> + next = &env->prog->insnsi[insn_idx + 1];
> + if (!is_shift32_insn(next, BPF_RSH) || next->dst_reg != insn->dst_reg)
> + return false;
> + /* Ensure the next insn has a single incoming edge. */
> + return !bpf_is_prune_point(env, insn_idx + 1);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Is the comment accurate? In is_zext_pair_lsh(), the check
bpf_is_prune_point(env, insn_idx + 1) returns false when
env->insn_aux_data[idx].prune_point is not set, but not every merge point
gets that flag.
Looking at kernel/bpf/cfg.c, visit_gotox_insn() marks the gotox
instruction itself as a prune point, but marks each jump-table target with
mark_jmp_point() only, not mark_prune_point(). So an indirect-jump target
instruction can have many incoming edges (one per jump-table entry plus a
possible fall-through) while bpf_is_prune_point() returns false for it.
If such a target is the second shift of the pair, is_zext_pair_lsh()
would still return true even though the instruction has multiple incoming
edges.
The property actually being relied on appears to be "no verifier state is
checkpointed at insn_idx + 1", which does follow from
!bpf_is_prune_point(), since bpf_is_state_visited() in do_check() is
itself guarded by bpf_is_prune_point(). On an edge that arrives at the
second shift from somewhere other than the preceding first shift,
is_zext_pair_rsh() would fail its "env->prev_insn_idx != insn_idx - 1"
test and the id would be cleared as before.
Could the comment be reworded to state the actual invariant? For example:
"No state is checkpointed at insn_idx + 1, so the intermediate state
between the two shifts can never be pruned against."
> +}
[ ... ]
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/32322608718
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH bpf-next] bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension
2026-08-20 1:39 [PATCH bpf-next] bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension Yonghong Song
2026-08-20 2:33 ` bot+bpf-ci
@ 2026-08-20 16:57 ` Eduard Zingerman
2026-08-20 18:55 ` Yonghong Song
1 sibling, 1 reply; 4+ messages in thread
From: Eduard Zingerman @ 2026-08-20 16:57 UTC (permalink / raw)
To: Yonghong Song, bpf
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, kernel-team
On Wed, 2026-08-19 at 18:39 -0700, Yonghong Song wrote:
> For the following test in
> tools/testing/selftests/bpf/progs/verifier_linked_scalars.c:
>
> void alu32_negative_offset(void)
> {
> volatile char path[5];
> volatile int offset = bpf_get_prandom_u32();
> int off = offset;
>
> if (off >= 5 && off < 10)
> path[off - 5] = '.';
>
> /* So compiler doesn't say: error: variable 'path' set but not used */
> __sink(path[0]);
> }
>
> Without alu32 (-mcpu=v2), the test
> verifier_linked_scalars/alu32_negative_offset will fail with llvm22 and
> llvm23 like below.
>
> 3: (bf) r2 = r1 ; R1=scalar(id=1,...) R2=scalar(id=1,...)
> 4: (07) r2 += -5 ; R2=scalar(id=1-5,smin=-5,smax=0xfffffffa)
> 5: (67) r2 <<= 32 ; R2=scalar(smax=0x7fffffff00000000,...)
> 6: (77) r2 >>= 32 ; R2=scalar(smin=0,umax=0xffffffff,...)
> 7: (25) if r2 > 0x4 goto pc+5 ; R2=scalar(smin=0,smax=umax=4,...)
> 8: (bf) r2 = r10
> 9: (07) r2 += -5
> 10: (0f) r2 += r1 ; R1=scalar(id=1,smin=0,umax=0xffffffff)
> ; R2=fp(smin=-5,smax=0xfffffffa)
> 11: (b7) r1 = 46 ; R1=46
> 12: (73) *(u8 *)(r2 -5) = r1
> invalid unbounded variable-offset write to stack R2
>
> R1 is never narrowed down, so the address stays unbounded and the store
> is rejected.
>
> The test is okay for llvm21 with -mcpu=v2, see below:
>
> 3: (07) r1 += -5 ; R1=scalar(smin=-5,smax=0xfffffffa)
> 4: (67) r1 <<= 32 ; R1=scalar(smax=0x7fffffff00000000,...)
> 5: (77) r1 >>= 32 ; R1=scalar(smin=0,umax=0xffffffff,...)
> 6: (25) if r1 > 0x4 goto pc+5 ; R1=scalar(smin=0,smax=umax=4,...)
> 7: (bf) r2 = r10
> 8: (07) r2 += -5
> 9: (0f) r2 += r1 ; R2=fp(smin=-5,smax=-1)
> 10: (b7) r1 = 46 ; R1=46
> 11: (73) *(u8 *)(r2 +0) = r1 ; fp-8=ppppm???
>
> To fix the test issue with llvm22 and llvm23, note that the shift pair
> computes zext32(base + delta), which is exactly the relation
> BPF_ADD_CONST32 describes. So keep the link alive across the first
> shift and turn it from a 64-bit into a 32-bit one at the second, which
> makes the -mcpu=v2 sequence track like an alu32 one.
>
> Two conditions guard this. First, a 32-bit link requires the linked
> value to fit into u32, because sync_linked_regs() zero extends the
> bounds it propagates through such a link. linked_base_fits_u32() checks
> that on the register state before the shift, mirroring the dst_umax
> check the alu32 add path already does. Second, in between the two
> shifts the register does not hold the value its id and delta describe,
> so the second shift must have a single incoming edge, otherwise the
> intermediate state could be checkpointed and another path pruned
> against it.
>
> With this, the llvm22 and llvm23 code verifies, R2 keeps its id through
> both shifts and the jump narrows down R1:
>
> 3: (bf) r2 = r1 ; R1=scalar(id=1,...) R2=scalar(id=1,...)
> 4: (07) r2 += -5 ; R2=scalar(id=1-5,smin=-5,smax=0xfffffffa)
> 5: (67) r2 <<= 32 ; R2=scalar(id=1-5,smax=0x7fffffff00000000)
> 6: (77) r2 >>= 32 ; R2=scalar(id=1-5,smin=0,umax=0xffffffff)
> 7: (25) if r2 > 0x4 goto pc+5 ; R1=scalar(id=1,smin=5,smax=9,...)
> ; R2=scalar(id=1-5,smin=0,smax=4,...)
> 8: (bf) r2 = r10
> 9: (07) r2 += -5
> 10: (0f) r2 += r1 ; R2=fp(smin=0,smax=4)
> 11: (b7) r1 = 46 ; R1=46
> 12: (73) *(u8 *)(r2 -5) = r1 ; fp-8=ppppm???
>
> The llvm21 log is unchanged, R1 carries no id there so the new code
> does not apply to it.
>
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> ---
I think this is too tricky. A simpler thing is to rewrite the incoming
program as `w2 = w1; nop;` in place of two shifts. The CFG check would
still be necessary, though.
...
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH bpf-next] bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension
2026-08-20 16:57 ` Eduard Zingerman
@ 2026-08-20 18:55 ` Yonghong Song
0 siblings, 0 replies; 4+ messages in thread
From: Yonghong Song @ 2026-08-20 18:55 UTC (permalink / raw)
To: Eduard Zingerman, bpf
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, kernel-team
On 8/20/26 9:57 AM, Eduard Zingerman wrote:
> On Wed, 2026-08-19 at 18:39 -0700, Yonghong Song wrote:
>> For the following test in
>> tools/testing/selftests/bpf/progs/verifier_linked_scalars.c:
>>
>> void alu32_negative_offset(void)
>> {
>> volatile char path[5];
>> volatile int offset = bpf_get_prandom_u32();
>> int off = offset;
>>
>> if (off >= 5 && off < 10)
>> path[off - 5] = '.';
>>
>> /* So compiler doesn't say: error: variable 'path' set but not used */
>> __sink(path[0]);
>> }
>>
>> Without alu32 (-mcpu=v2), the test
>> verifier_linked_scalars/alu32_negative_offset will fail with llvm22 and
>> llvm23 like below.
>>
>> 3: (bf) r2 = r1 ; R1=scalar(id=1,...) R2=scalar(id=1,...)
>> 4: (07) r2 += -5 ; R2=scalar(id=1-5,smin=-5,smax=0xfffffffa)
>> 5: (67) r2 <<= 32 ; R2=scalar(smax=0x7fffffff00000000,...)
>> 6: (77) r2 >>= 32 ; R2=scalar(smin=0,umax=0xffffffff,...)
>> 7: (25) if r2 > 0x4 goto pc+5 ; R2=scalar(smin=0,smax=umax=4,...)
>> 8: (bf) r2 = r10
>> 9: (07) r2 += -5
>> 10: (0f) r2 += r1 ; R1=scalar(id=1,smin=0,umax=0xffffffff)
>> ; R2=fp(smin=-5,smax=0xfffffffa)
>> 11: (b7) r1 = 46 ; R1=46
>> 12: (73) *(u8 *)(r2 -5) = r1
>> invalid unbounded variable-offset write to stack R2
>>
>> R1 is never narrowed down, so the address stays unbounded and the store
>> is rejected.
>>
>> The test is okay for llvm21 with -mcpu=v2, see below:
>>
>> 3: (07) r1 += -5 ; R1=scalar(smin=-5,smax=0xfffffffa)
>> 4: (67) r1 <<= 32 ; R1=scalar(smax=0x7fffffff00000000,...)
>> 5: (77) r1 >>= 32 ; R1=scalar(smin=0,umax=0xffffffff,...)
>> 6: (25) if r1 > 0x4 goto pc+5 ; R1=scalar(smin=0,smax=umax=4,...)
>> 7: (bf) r2 = r10
>> 8: (07) r2 += -5
>> 9: (0f) r2 += r1 ; R2=fp(smin=-5,smax=-1)
>> 10: (b7) r1 = 46 ; R1=46
>> 11: (73) *(u8 *)(r2 +0) = r1 ; fp-8=ppppm???
>>
>> To fix the test issue with llvm22 and llvm23, note that the shift pair
>> computes zext32(base + delta), which is exactly the relation
>> BPF_ADD_CONST32 describes. So keep the link alive across the first
>> shift and turn it from a 64-bit into a 32-bit one at the second, which
>> makes the -mcpu=v2 sequence track like an alu32 one.
>>
>> Two conditions guard this. First, a 32-bit link requires the linked
>> value to fit into u32, because sync_linked_regs() zero extends the
>> bounds it propagates through such a link. linked_base_fits_u32() checks
>> that on the register state before the shift, mirroring the dst_umax
>> check the alu32 add path already does. Second, in between the two
>> shifts the register does not hold the value its id and delta describe,
>> so the second shift must have a single incoming edge, otherwise the
>> intermediate state could be checkpointed and another path pruned
>> against it.
>>
>> With this, the llvm22 and llvm23 code verifies, R2 keeps its id through
>> both shifts and the jump narrows down R1:
>>
>> 3: (bf) r2 = r1 ; R1=scalar(id=1,...) R2=scalar(id=1,...)
>> 4: (07) r2 += -5 ; R2=scalar(id=1-5,smin=-5,smax=0xfffffffa)
>> 5: (67) r2 <<= 32 ; R2=scalar(id=1-5,smax=0x7fffffff00000000)
>> 6: (77) r2 >>= 32 ; R2=scalar(id=1-5,smin=0,umax=0xffffffff)
>> 7: (25) if r2 > 0x4 goto pc+5 ; R1=scalar(id=1,smin=5,smax=9,...)
>> ; R2=scalar(id=1-5,smin=0,smax=4,...)
>> 8: (bf) r2 = r10
>> 9: (07) r2 += -5
>> 10: (0f) r2 += r1 ; R2=fp(smin=0,smax=4)
>> 11: (b7) r1 = 46 ; R1=46
>> 12: (73) *(u8 *)(r2 -5) = r1 ; fp-8=ppppm???
>>
>> The llvm21 log is unchanged, R1 carries no id there so the new code
>> does not apply to it.
>>
>> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
>> ---
> I think this is too tricky. A simpler thing is to rewrite the incoming
> program as `w2 = w1; nop;` in place of two shifts. The CFG check would
> still be necessary, though.
For just left and right shift, probably `w2 = w2; nop;`.
But this approach is indeed simpler and easier to understand.
Will explore.
>
> ...
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2026-08-20 18:55 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-08-20 1:39 [PATCH bpf-next] bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension Yonghong Song
2026-08-20 2:33 ` bot+bpf-ci
2026-08-20 16:57 ` Eduard Zingerman
2026-08-20 18:55 ` Yonghong Song
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.