diff options
| author | Eduard Zingerman <eddyz87@gmail.com> | 2026-10-26 16:38:22 -0700 |
|---|---|---|
| committer | Alexei Starovoitov <ast@kernel.org> | 2026-10-27 16:26:21 +0000 |
| commit | 0c33d612bdd50aaeef263410739060827377d9c0 (patch) | |
| tree | 23c98360b128da6e0c55874709258e29e45f2596 /rust/kernel/alloc/allocator | |
| parent | c463b378eae7fa4d8013d3ba7ca224f3a5098ec4 (diff) | |
bpf: Do not intersect with current register range on clamp
scev.c:bpf_clamp_scev_regs() is called each time verifier returns to a
loop header via a backedge. It's purpose is to re-establish computed
variable ranges for registers with linear SCEVs.
It can be defined as:
- For each register R with linear SCEV compute:
- loop_range(R) := entry_range(R) * iterations_count
- range(R) := range(R) ∩ loop_range(R)
Such formulation is necessary to avoid ranges over-approximation in
examples like below:
r1 = 0; SCEVs: r1 = (linear r1 1)
r3 = 0; r3 = (linear r3 1)
loop: r3 += 1;
r1 += 1;
if r1 < 5 goto loop;
r0 = 0;
exit;
- At loop entry r3 is widened to be in a range r3 ∈ {0,1,2,3,4}.
- After increment it becomes r3 ∈ {1,2,3,4,5}.
- On a second iteration the bpf_clamp_scev_regs() forces r3 to become
r3 ∈ {1,2,3,4}. W/o clamping logic r3 range wouldn't shrink
preventing loop from converging in states.c:states_equal().
However, intersection logic might lead to assigning an empty range to
a register, as in example below:
r1 = 0; verification
r3 = 0; path
loop: r3 += 1; | <---------.
if r3 != 5 goto +0; | r3 ∈ {5} |
r1 += 1; | |
if r1 != 5 goto loop; '-----------'
r0 = 0;
exit;
- At header r3 ∈ {0,1,2,3,4}.
- While exploring the branch `if r3 != 5 goto ...` with r3 ∈ {5}.
- On a second iteration:
r3 := {0,1,2,3,4} ∩ {5} = ∅
Which stops verification with the following error:
verifier bug: scev clamp produced empty range for r3
Technically this means that the current verification path is
impossible at runtime and should not be traced further.
This commit mitigates the above by removing the intersection logic,
the function is now defined as:
- For each register R with linear SCEV compute:
- range(R) := entry_range(R) * iterations_count
This is still sound, provided that SCEV expressions loop execution
counts are correct.
Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261026-scev-simpler-clamp-v2-2-f373aec9825f@gmail.com
Diffstat (limited to 'rust/kernel/alloc/allocator')
0 files changed, 0 insertions, 0 deletions
