bpf_dynptr_slice(&ptr, off, buffer, size) and bpf_dynptr_slice_rdwr()
return a pointer to the data of a dynptr. When the data is not contiguous,
for example in a non-linear skb, they copy it to 'buffer' and return
'buffer'. Usually the buffer is on the stack. For the verifier the result
is plain memory (PTR_TO_MEM), and an access through it is not an access to
the stack:
- A store makes wrong what the verifier tracks in the buffer: a known
scalar, a spilled pointer, a dynptr, an iterator, irq flags.
- A load gives the bytes of a spilled pointer or of a dynptr as a scalar.
- Both are possible after the frame of the buffer returned.
The accesses are safe while the buffer contains only unknown bytes, as it
does after the call. Thus keep this rule: the buffer contains no tracked
data while a slice that can be the buffer exists. The slice remembers the
frame, the offset and the size of its buffer. The verifier invalidates the
slice, read-only or not, at each event that breaks the rule:
event slices of the buffer
------------------------------------------------- --------------------
the prog stores to bytes of the buffer invalid
a dynptr, an iterator or irq flags are made there invalid
the frame of the buffer returns invalid
a helper or a kfunc fills the buffer no change
a store next to the buffer, a read of the buffer no change
Tracked data gets into a stack slot in check_stack_write(), also the bytes
of a new dynptr, iterator or irq flags. Thus one call there, and one call
in prepare_func_exit(), are sufficient. Each is one walk over the
registers, only in progs that have such a slice. Helpers and kfuncs leave
only unknown bytes: mark_raw_stack() goes around check_stack_write().
The range of the buffer is in the part of bpf_reg_state that the verifier
copies with the register and compares for pruning. A slice that is the
buffer of a second call passes its range on. Local, ringbuf and skb
metadata dynptrs never return the buffer: no range. A dynptr argument of a
global function counts as an skb dynptr.
The usual pattern only reads the buffer, and it continues to load:
if (p == buffer)
bpf_dynptr_write(&ptr, 0, buffer, sizeof(buffer), 0);
A prog that stores to the buffer and then uses the old slice is rejected:
"R7 invalid mem access 'scalar'". The diagnostics name the reason, and the
log shows the buffer of a slice: R7=mem(sz=8,buf=fp[0]-8+8).
Fixes: 66e3a13e7c2c ("bpf: Add bpf_dynptr_slice and bpf_dynptr_slice_rdwr")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261102170958.3586893-2-alexei.starovoitov@gmail.com
check_packet_access() accepts an access when umax + off + size <= range.
Thus 'range - umax' bytes from a packet pointer are in the packet, and
nothing can make umax smaller without a change of the range. For this
reason commit b88822d2584f ("bpf: Fix packet range of pointers sharing an
id") removed reg_bounds_sync() from the arithmetic on packet pointers.
At the head of a counted loop scalar evolution gives new bounds to a packet
pointer, in bpf_set_reg_range() and in bpf_reg_union(). The two functions
call reg_bounds_sync(). Then the step or var_off makes umax smaller.
r4 &= 0x38
if r4 > 50 goto 2f ; r4 is 0, 8 .. 48, but umax is 50
r6 = pkt
r6 += r4
r5 = r6
r5 += 8
if r5 > pkt_end goto 2f ; 8 bytes from r6 are in the packet
1: r0 = *(u16 *)(r6 + 0)
r6 += 8
r9 += 1
if r9 < 2 goto 1b
r6 umax range valid bytes
----------------------- ---- ----- ------------
in front of the loop 50 58 8
in all iterations 58 58 0
after the step of 8 56 58 2, incorrect
In the second iteration r6 can be pkt_end. The verifier accepts the prog,
and the prog reads 2 bytes after the packet. A kernel without scalar
evolution rejects it.
Make the range smaller by the same number as the largest offset.
The largest offset is smax, not umax. With 'r6 += -8' in the loop the
offset can be negative. Then umax is U64_MAX before and after
reg_bounds_sync(). The verifier rejects an access through such r6. It
accepts an access through 'r5 = r6; r5 += 8', and r5 has the range of r6.
All registers of a union have the same range, and bpf_reg_union() makes
sure of that for each register. Thus change the range one time, after the
last register. The range goes with the largest offset of all registers.
The range can also be a mark: the pointer is at pkt_end or beyond pkt_end.
The mark is for the pointer at the entry of the loop, not for all
iterations. Remove it when the pointer is widened. The arithmetic in the
loop removes the mark too. Thus the state that returns to the head was not
pruned, and the verifier made one more pass with the two branches of each
compare. Now the first pass examines the two branches. The verdict can
change only when no state returned to the head: the mark sent each path out
of the loop, and the other insns of the loop were dead code.
Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261030210950.1904640-2-alexei.starovoitov@gmail.com
Closes: https://lore.kernel.org/bpf/sashiko-outbox-187068@kernel.org/
A compare with pkt_end sets 'range' in all packet pointers that have the
same id. Then 'range - offset' bytes from the pointer are in the packet.
When a state returns to the head of a counted loop, bpf_clamp_scev_regs()
gives a new id to a packet pointer, and the offsets of all iterations. It
does not change the range. But the range is valid only together with the
old id and the old offsets.
1: ; R6=pkt(id=1,r=0,off=0..100)
r5 = r6
r5 += 100
if r5 > pkt_end goto 2f ; R6=pkt(id=1,r=200,off=0..100)
r6 += 100 ; R6=pkt(id=1,r=200,off=100..200)
r9 += 1
if r9 < 2 goto 1b ; clamp: R6=pkt(id=2,r=200,off=0..100)
after bytes from r6 that the verifier accepts
---------------------- ---------------------------------------
the compare 100, correct
r6 += 100 0, correct
the clamp 100, incorrect. Nothing compared this r6
Usually the verifier prunes the state at the head, and the range has no
effect. The verifier continues with the state when a different part of it
is not within the state at the head. A flag in a 32-bit spill is
sufficient. Then the prog reads and writes after pkt_end. A write to
skb_shared_info crashes the kernel.
Take the range that the pointer has at the entry of the loop. No compare in
the loop found this range, so it is valid in all iterations. The state at
the head has the same range, so the verifier prunes as before.
Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261027190314.1440199-15-alexei.starovoitov@gmail.com
When a state returns to the head of a counted loop, bpf_clamp_scev_regs()
replaces the range of each register that changes by a constant step. The
new range is the range over all iterations. The function calculates it from
the register in the state that entered the loop. For a pointer this range
is the range of its offsets.
A call in the loop can invalidate the pointer. bpf_skb_pull_data() does it
to packet pointers, bpf_ringbuf_discard() does it to ringbuf memory. Then
the register is an unknown scalar. Scalar evolution does not see that, and
the clamp gives the offsets of the pointer to the scalar.
r6 = bpf_ringbuf_reserve() ; R6=ringbuf_mem
r7 = r6
1: if first iteration goto 2f
r1 = map_value
r1 += r6 ; accepted: R6 is 0 or 1
r0 = *(u8 *)(r1 + 0)
goto 3f
2: bpf_ringbuf_discard(r7) ; R6=scalar()
3: r6 += 1
r9 += 1
if r9 < 2 goto 1b ; clamp: R6=scalar(umax=1)
At run time r6 is the address of the ringbuf memory plus 1. The prog adds
it to a pointer to a map value, and the kernel crashes in the access.
Do not clamp a register that has a different type than at the entry of the
loop. Such a state is not within the state at the head. Thus the verifier
continues with it, and r6 stays an unknown scalar.
Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261027190314.1440199-14-alexei.starovoitov@gmail.com
Scalar evolution widens counted loops. Since that change the verifier
rejects a loop over the per-cpu values of a map element:
SEC("iter/bpf_map_elem")
...
for (i = 0; i < n; i++) {
out[i] = *(__u32 *)pptr;
pptr += 8;
}
loop header at 12, widening r2 to 0..56 step 8
R2 invalid variable buffer offset: off=0, var_off=(0x0; 0x38)
pptr is a pointer to a buffer (PTR_TO_BUF). Scalar evolution replaces its
offset with the range over all iterations. But __check_buffer_access()
accepts only a constant offset. Thus a prog cannot use a widened
PTR_TO_BUF.
Do not widen it. Then the verifier verifies the loop one iteration at a
time, as it did before.
loop before SCEV with SCEV this patch
-------------------------------- ----------- ---------- ----------
counts in i, reads through pptr loads rejected loads
counts in p ('p < end'), no read 1M insns loads 1M insns
counts in p, reads through p 1M insns rejected 1M insns
The verifier cannot decide a comparison of two pointers to a buffer. Thus
it follows 'p < end' until the limit of 1M insns.
bpf_iter_bpf_percpu_array_map.c and bpf_iter_bpf_percpu_hash_map.c have the
first loop. They load today because num_cpus is volatile. The prog reads
the bound again in each iteration. Scalar evolution cannot count such a
loop, and it widens nothing.
Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261027190314.1440199-12-alexei.starovoitov@gmail.com
After 'r3 = r8; r3 += 4' the verifier knows that r3 == r8 + 4. The two
registers have the same id, and r3 keeps the difference in reg->delta. When
the prog compares one of them with a constant, sync_linked_regs()
calculates the range of the other register from the difference of the two
deltas.
At a loop head scalar evolution widens a register: it replaces the register
with its range over all iterations. Then the register is not linked to
other registers. scratch_widened_reg_id() clears reg->id, but it does not
clear reg->delta. A subsequent copy of the register gets the stale delta.
Then the range of the copy is incorrect by this delta.
r3 = r8
r3 += 4 ; R3=scalar(id=1+4)
1: ; r3 is widened: no id, delta is still 4
r4 = r3 ; id=2 and delta 4 in both
r4 += 1 ; R4=scalar(id=2+1)
if r3 > 10 goto 3f ; R3 <= 10, R4 = R3 + 1 - 4 <= 7
if r4 <= 7 goto 2f
... ; not verified, r4 is up to 11 here
The verifier does not verify code that can run. Use clear_scalar_id(). It
clears id and delta together. Move it to bpf_verifier.h, so that scev.c can
call it.
Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261027190314.1440199-8-alexei.starovoitov@gmail.com
- Print large 32-bit bounds without sign extension. - Omit 32-bit bounds when they coincide with 64-bit bounds. Before: loop header at ..., widening r0 to 0x80000000..0xffffffff (s32 0xffffffff80000000..-1) step 1 loop header at ..., widening r0 to 0..3 (s32 0..3) step 1 After: loop header at ..., widening r0 to 0x80000000..0xffffffff (s32 0x80000000..-1) step 1 loop header at ..., widening r0 to 0..3 step 1 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-6-f373aec9825f@gmail.com
The compiler can preserve an induction variable across a call by
copying it to a callee-saved register. For example:
w1 = 0;
loop:
w7 = w1;
call foo;
w1 = w7;
w1 += 2;
if w7 < 10 goto loop;
When building expressions for the loop body, each 32-bit move adds a
zero extension:
w7 = w1; r7 = (zext32 r1)
w1 = w7; r1 = (zext32 (zext32 r1))
w1 += 2; r1 = (zext32 (+ (zext32 (zext32 r1)) 2))
The existing ALU32 simplification rules allow recognizing the header
SCEV for r1 as:
(zext32 (linear r1 2))
Substituting this SCEV into r7's expression at the latch produces:
(zext32 (zext32 (linear r1 2)))
Add the simplification rule:
(zext32 (zext32 X)) -> (zext32 X)
This allows recognizing the saved induction variable in r7 as a
32-bit linear SCEV and computing the loop iteration bound.
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-5-f373aec9825f@gmail.com
The comment before `total_change` computation:
/*
* compute_backedge_taken_count() guarantees that 'total_change'
* does not overflow in 64-bit domain.
*/
total_change = initial + step * backedge_taken_count;
Is not true before the check:
if (backedge_taken_count >= U32_MAX - 1)
return false;
Move the check before `total_change` computation in order to reconcile
the code with comments. Old position is not a bug the check was
performed either way.
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-4-f373aec9825f@gmail.com
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