| Age | Commit message (Collapse) | Author |
|---|
|
The original pattern:
__msg("3: (85) call pc+{{[0-9]+}}\n")
Is ambigous, as this line is printed on the main verification pass as
well. Harden the test case by ensuring a __msg_next sequence matching
the stack use/def results specifically.
Fixes: 063c85f5d8c7 ("selftests/bpf: Tests for BTF-based global subprog stack liveness")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Link: https://lore.kernel.org/bpf/20261013-scev-minimal-v3-followups-v2-5-6d9d61965486@gmail.com
|
|
Verify that a frame pointer derived value does not induce stack
liveness effects, when passed as a scalar argument of a
global function.
Verify that a stack-based dynptr passed to a global function marks
live only corresponding 16 bytes.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Link: https://lore.kernel.org/bpf/20261013-scev-minimal-v3-followups-v2-4-6d9d61965486@gmail.com
|
|
Check that passing a stack pointer to a no-op global callee produces:
- use, def and may_def marks for a fixed-size memory argument.
- No stack effects for an untrusted BTF pointer argument.
This verifies that call effects follow the declared argument types
rather than the callee's body.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-44-bcba9bc53ac9@gmail.com
|
|
Tests for helper arguments whose access size or read/write effects
depend on the map:
- helper_map_output_known_size checks that for a known map access
MEM_WRITE | MEM_UNINIT produces a must_write mark.
- helper_map_output_merged_sizes checks that when maps with different
value sizes merge, MEM_WRITE | MEM_UNINIT produces use and may_def
marks over the maximum value size, without a def mark.
- helper_bloom_peek_input checks that for bpf_map_peek_elem()
on a bloom filter the buffer is treated as an input.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-43-bcba9bc53ac9@gmail.com
|
|
Check stack write tracking for atomic operations:
- Restored by 64-bit load-acquire, xchg, fetch_add and cmpxchg.
- Spilled by store-release and restored by a plain load.
- Restored from a caller's stack slot by xchg in a callee.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-42-bcba9bc53ac9@gmail.com
|
|
Liveness analysis should produce may_def marks for read-modify-write
atomic operations:
- lock *(u64 *)(r10 -8) += r1
- r1 = atomic64_fetch_add((u64 *)(r10 -8), r1)
- r1 = atomic64_xchg((u64 *)(r10 -8), r1)
- r0 = atomic64_cmpxchg((u64 *)(r10 -8), r0, r1)
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-41-bcba9bc53ac9@gmail.com
|
|
Branches to cover:
- per-insn writes (record_stack_access_off):
* off_cnt==1, fully covered slots -> def + may_def (equal)
* partial coverage -> may_def only (no def)
* off_cnt 2-4, precise offsets -> may_def only, per offset
- whole-frame writes:
* off_cnt==0 (offset lost) -> may_def SPIS_ALL
* ARG_IMPRECISE (frame lost) -> may_def SPIS_ALL per frame
- merge_instances():
* both passes touch a frame -> may_def union
* one pass leaves a frame untouched -> may_def preserved
- merge_may_write(): a callee's writes into ancestor frames are
summarized as may_def at the caller's call instruction
- analyze_subprog() -> may_def stack slot range
when callback is unknown.
Tests exercising them:
- may_write_two_precise_offsets - off_cnt 2-4 precise multi-offset
- imprecise_frame_write - cross-frame ARG_IMPRECISE write,
plus its caller-side summarization
- merge_preserves_may_write - map-value vs stack pointer at two
callsites: union is preserved when
one pass does not touch the frame
- must_write_not_same_slot - off_cnt==0 whole-frame may_def
- two_byte_write_no_kill - partial write, may_def without def
- kfunc_iter_stack_liveness - full-slot def == may_def
- helper_output_unknown_size - output size unknown to liveness,
may_def without use or def
- caller_stack_write,
conditional_stx_in_subprog,
shared_instance_must_write_overwrite
- callee writes summarized as may_def
at the call site
- bpf_loop_two_callbacks - call to unknown callback marks full
stack range as may_def.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-40-bcba9bc53ac9@gmail.com
|
|
Tests for multiple analyses performed by the verifier need the
verifier log to contain analysis results alongside the program
disassembly. This patch moves the log-level-2 program dump from
bpf_compute_live_registers() to a standalone function called from
bpf_check(), in order to provide a common logging function for such
analyses (and thus avoid printing program disassembly multiple times).
Rename the dump header from "Live regs before insn:" to
"Program dump (scc? insn#: live_regs_before):" and print available
source-line information before the corresponding instructions.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-22-bcba9bc53ac9@gmail.com
|
|
This computes exact liveness for the arguments of a call to a
subprogram instead of assuming that r1..r5 are read:
- For static subprograms compute use registers at the
bpf_compute_live_registers() fixpoint phase.
- For global subprograms use BTF information.
Add a separate pass doing try_btf_prepare_func_args() in order for
bpf_subprog_info->arg_slot_cnt to be available during
bpf_compute_live_registers().
The conservative liveness marks hindered SCEV widening logic on a set
of production programs.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-11-bcba9bc53ac9@gmail.com
|
|
Track stack slots that instructions may modify, in order to account
for such writes when constructing SCEV expressions.
Consume the may_write flag in arg_access_info separately from reads and
definite writes. Include partially covered slots and all candidate
offsets; imprecise writes mark whole candidate frames. Possible writes
do not kill liveness.
Merge analyzed instances as:
may_write(dst) |= may_write(src)
must_write(dst) &= must_write(src)
For each ancestor frame f, summarize callee writes at the callsite:
may_write(callsite, f) |= OR_{i in callee} may_write(i, f)
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-4-bcba9bc53ac9@gmail.com
|
|
Add tests for the stack budget of JITs with large stack support: a
single 2 KiB frame, with and without may_goto, four 512-byte frames
that fit the budget and five that do not, a 512-byte frame calling a
1536-byte static subprog, global subprog or bpf_loop() callback and the
same with eight bytes too many, variable offset writes reaching exactly
the budget and past it, a tail call made from a 1 KiB frame, and two
2 KiB frames on a private stack, where each frame gets the whole budget.
A program with a 2 KiB frame is checked to be rejected wherever the
budget is 512 bytes, and a 1 KiB frame is rejected in a program calling
bpf_clone_redirect() but accepted in one calling bpf_redirect().
Two tests run such programs: a tail call made from a subprog with a
1536-byte frame under a 240-byte caller into a program with a 2 KiB
frame, and a struct_ops program on a private stack calling a subprog
when both frames are 2 KiB.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-19-memxor@gmail.com
|
|
A number of tests pin the 512-byte stack limit: accesses just past it,
call chains that add up to more than it, private stack frames and
async callbacks that exceed it. Once a JIT raises the budget to 2 KiB
those programs load, so mark them __load_if_no_large_stack() and add a
counterpart at the 2 KiB boundary under __load_if_large_stack(), so
that each kernel runs the pair that matches its budget. The
combined-depth tests that were built from frames of a few hundred
bytes now chain five 480-byte frames, which exceeds both budgets and
keeps them valid on every architecture; the number of frames reported
in the error then differs, so those messages match any count. The C
tests are limited to 512 bytes per function by the compiler, hence the
chains. The callx stack depth tests, whose callee frames add up to 608
bytes, chain four 480-byte frames behind the callx target for the same
reason.
No kernel grants the larger budget yet, so the 512-byte tests still run
everywhere and the 2 KiB twins are skipped.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-16-memxor@gmail.com
|
|
The verifier checks every stack access and the combined depth of a call
chain against MAX_BPF_STACK, which is also the frame size of the
interpreter and the frame that JITs without subprogram tail call
support set up for tail-call targets. A JIT that lays out frames of any
size and lets a tail-called program set up its own frame does not need
that limit; it only needs the verifier to bound how much stack a
program uses in total.
Add bpf_jit_supports_large_stack() for a JIT to claim that, and give
each program its budget through bpf_prog_stack_limit(): MAX_BPF_STACK_JIT
when the JIT is requested, the program is not offloaded and the JIT
supports large stacks as well as tail calls from subprograms,
MAX_BPF_STACK otherwise. The latter is what lets a tail-called program
set up its own frame: without it, do_misc_fixups() gives every program
with tail calls a MAX_BPF_STACK frame, which a deeper frame verified
against the larger budget would overrun. The verifier keeps the budget
in env->stack_limit and uses it for the bounds of fixed and variable
offset stack accesses, for unprivileged stack pointer arithmetic and its
speculation limit, and for the combined and private stack depth checks.
A frame may use any part of its program's budget. The interpreter paths
keep MAX_BPF_STACK: a program whose main frame is deeper falls back to
the JIT-required path of bpf_prog_select_runtime() and one with deeper
subprogram frames is rejected when patching calls for the interpreter.
The extra stack that may_goto and the timed may_goto instrumentation
add below a frame is, as before, not counted against the budget of a
JITed program and rejected past MAX_BPF_STACK for an interpreted one.
Stack liveness treats a read through a pointer of unknown offset, or a
call passing a frame pointer to a subprogram, as reaching the whole
frame, and widens the masks of that frame to the deepest half-slot such
a read can cover. Bound that by the program's budget too: no access
past it is accepted, so a program kept at MAX_BPF_STACK carries masks
of two words for such frames, as before, instead of the eight that
MAX_BPF_STACK_JIT needs. The three selftests matching a whole-frame
read in the liveness log accept either depth.
bpf_clone_redirect() transmits from inside the program, and a tc egress
or lwt_xmit program that redirects to its own device runs again on top
of its own frame until the datapath's recursion limit drops the packet,
ten frames deep. Ten MAX_BPF_STACK frames fit the kernel stack as they
always did; ten MAX_BPF_STACK_JIT frames would not, so a program that
calls bpf_clone_redirect() keeps MAX_BPF_STACK. The redirect helpers
that transmit after the program has returned leave no frame behind and
do not affect the budget. Nesting through other attach points is not
accounted, as before.
The spill tracker of the liveness analysis follows no slot past the
budget either.
The capability is a boolean and the budget a single constant, in the
style of the other bpf_jit_supports_*() queries, rather than a per JIT
size: the budget is meant to be the same everywhere it is raised, so
that programs verify identically across those architectures.
No JIT declares support yet, so every program keeps its 512-byte budget.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-14-memxor@gmail.com
|
|
The verifier keeps a few structures whose size follows the deepest
frame a program may have: the backtracking and scratched-slot bitmaps,
the jump history slot index and the clamp of the liveness masks. They
are all expressed through MAX_BPF_STACK_SLOTS, which derives from
MAX_BPF_STACK, the frame size of the interpreter.
Introduce MAX_BPF_STACK_JIT, the stack budget a program may get on a
JIT that can lay out frames of any size, and derive those structures
from it so that a frame may be as deep as that budget. Nothing grants
the budget yet, so no program verifies differently; the only visible
change is that the liveness log prints a whole-frame read up to the new
depth, so the three selftests matching such reads are updated.
The spill tracker of the liveness analysis keeps a table entry per
instruction and tracked slot, so it follows more than the 64 slots of a
MAX_BPF_STACK frame only while that table stays within what 64 slots
need for the largest program; a subprog of a million instructions keeps
64, one of a quarter million may track all 256. This bounds the table
at its old worst case of 640 MiB instead of letting a single deep store
push it past what kvmalloc() serves.
The backtracking and scratched-slot bitmaps grow from one to four
words per frame, a fixed few hundred bytes per verifier environment.
tmp_str_buf, which formats a frame's slot list for the log, grows from
320 to 1408 bytes so that all 256 slots still fit, and the log's line
buffer from 1 to 2 KiB so that a line built from it is not cut; the
environment stays within its 64 KiB allocation. The liveness masks are
only as wide as the stack a frame uses, so most frames cost the same as
before; a frame that is read as a whole, through a pointer of unknown
offset or by bpf_loop() with two callbacks, now carries masks of eight
words, 192 bytes per instruction per frame instead of 48. Measured over
the 5075 selftest programs, that is 0.2% of the total peak verifier
memory: strobemeta_bpf_loop and pyperf600_bpf_loop grow by 11% (1.2 MiB
and 0.6 MiB), a few dozen small programs by 40 to 100 KiB each,
everything else is unchanged. The next patch bounds such reads by the
program's budget, so this cost is only paid once a JIT grants it.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-13-memxor@gmail.com
|
|
The liveness masks of a function instance are as wide as the deepest
half-slot the instance was seen to access. When the same instance is
analyzed again through another call site, the new pass may have settled
on a different width, and merge_instances() has to widen the original
before combining the two. Add a test where the first pass of a callee
reads through a pointer 248 bytes into the main frame and the second
one through a pointer of unknown offset, which reads the whole frame,
and check that the merged result keeps the whole-frame read. The
precise read stays within the first mask word on 64-bit, so the
whole-frame pass is wider under every stack budget and the merge has
to widen the masks; a deeper read would need two words already, which
is all a 512-byte whole-frame read needs on 64-bit, and the widening
would go untested there.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-12-memxor@gmail.com
|
|
The stack liveness analysis records a store as a "def" only for the
4-byte half-slots it covers completely, so a one or two byte store near
the top of the frame must not define anything. Add a test that reads
fp-8, stores one byte at fp-1 and two bytes at fp-4, and reads fp-8
again, expecting no def mark on either store and the second read to
still use fp-8.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-11-memxor@gmail.com
|
|
Exercise generic output buffers with and without CAP_PERFMON, using both
helpers and __uninit kfuncs. Check that initialized bytes stay readable
and lose stale value information, while invalid bytes remain unreadable
without permission to read uninitialized stack memory. Cover constant and
variable sizes, scalar spills, pointer spills, special stack objects, and
privileged variable offsets.
Add a kfunc that writes only the first byte of its output. Its runtime tests
read preinitialized bytes, checking both the written byte and an untouched
tail byte across a liveness checkpoint. Verify that the sysctl name helper
and uninitialized fixed and variable-sized kfunc outputs are accepted when
their contents are not read back.
Update existing __uninit readback expectations and exercise skb_load_bytes
with reduced capabilities. Even fully-writing generic outputs now preserve
invalid bytes in the verifier, so reading those bytes requires prior
initialization by the BPF program.
Use map_update_elem inputs for helper_arg_fallback_keeps_scanning. Its
original snprintf argument no longer reads the buffer, and a privileged
output with an unknown size does not trigger the whole-stack read fallback.
A variable-offset key and parent-frame value retain the intended assertion.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260921023843.411943-10-memxor@gmail.com
|
|
check_kfunc_args() rejects a NULL or possibly-NULL register passed to
a non-nullable pointer argument up front. Helpers only do so inside
check_reg_type() for PTR_TO_BTF_ID arguments, leaving other pointer
kinds to fail indirectly through compatible_reg_types[].
Give both paths the same policy and factor it into
check_func_arg_nullability(). Gate it on arg_type_is_scalar() rather
than on the BTF shape of the kfunc parameter. This keeps a zero passed
to a size argument from being interpreted as a NULL pointer.
Taking nullability from the argument classification also avoids an
is_kfunc_arg_nullable() lookup for every kfunc argument on every
verification.
Keep release-argument nullability separate from ownership checking.
A possibly-NULL release argument must be rejected even if it is
otherwise nullable, while the ownership check must still permit a
literal NULL for bpf_kptr_xchg().
Use call-neutral structured diagnostics and retain the expected BTF
type when it is available for a kfunc argument. Resolve that type lazily
from the call metadata only when reporting an error. Helpers now report
NULL-ness rather than a register-type mismatch for non-BTF-ID pointer
arguments and literal NULL passed to a non-nullable pointer argument.
Update the affected selftest expectations.
Signed-off-by: Amery Hung <ameryhung@gmail.com>
Link: https://lore.kernel.org/r/20260911220415.1396439-16-ameryhung@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
Add test cases for clear_stack_for_all_offs and dst_is_local_fp
handling of multi-offset and ARG_IMPRECISE stack pointers:
- st_imm_join_with_multi_off: BPF_ST through multi-offset dst should
join at_stack with none instead of overwriting both candidate slots.
- st_imm_join_with_imprecise_off: BPF_ST through offset-imprecise dst
should join at_stack with none instead of clearing all slots.
- st_imm_join_with_single_off: a canary checking that BPF_ST with a
known offset overwrites slot instead of joining.
- imprecise_dst_spill_join: BPF_STX through ARG_IMPRECISE dst should
be recognized as a local spill and join at_stack with the written
value.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20260413-stacklive-fixes-v2-2-398e126e5cf3@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
Add a bunch of new tests to verify the static stack
liveness analysis.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20260410-patch-set-v4-13-5d4eecb343db@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
The verifier cleans all dead registers and stack slots in the current
state. Adjust expected output in tests or insert dummy stack/register
reads. Also update verifier_live_stack tests to adhere to new logging
scheme.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20260410-patch-set-v4-11-5d4eecb343db@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
A new test is added: caller_stack_write_tail_call tests that the live
stack is correctly tracked for a tail call.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Martin Teichmann <martin.teichmann@xfel.eu>
Link: https://lore.kernel.org/r/20251119160355.1160932-5-martin.teichmann@xfel.eu
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
- simple propagation of read/write marks;
- joining read/write marks from conditional branches;
- avoid must_write marks in when same instruction accesses different
stack offsets on different execution paths;
- avoid must_write marks in case same instruction accesses stack
and non-stack pointers on different execution paths;
- read/write marks propagation to outer stack frame;
- independent read marks for different callchains ending with the same
function;
- bpf_calls_callback() dependent logic in
liveness.c:bpf_stack_slot_alive().
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20250918-callchain-sensitive-liveness-v3-12-c3cd27bacc60@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
