summaryrefslogtreecommitdiff
path: root/rust/kernel/alloc/allocator
diff options
context:
space:
mode:
authorEduard Zingerman <eddyz87@gmail.com>2026-10-26 16:38:22 -0700
committerAlexei Starovoitov <ast@kernel.org>2026-10-27 16:26:21 +0000
commit0c33d612bdd50aaeef263410739060827377d9c0 (patch)
tree23c98360b128da6e0c55874709258e29e45f2596 /rust/kernel/alloc/allocator
parentc463b378eae7fa4d8013d3ba7ca224f3a5098ec4 (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