This patch set fixes a bug in copy_verifier_state() where the
loop_entry field was not copied. This omission led to incorrect
loop_entry fields remaining in env->cur_state, causing incorrect
decisions about loop entry assignments in update_loop_entry().
An example of an unsafe program accepted by the verifier due to this
bug can be found in patch #2. This bug can also cause an infinite loop
in the verifier, see patch #5.
Structure of the patch set:
- Patch #1 fixes the bug but has a significant negative impact on
verification performance for sched_ext programs.
- Patch #3 mitigates the verification performance impact of patch #1
by avoiding clean_live_states() for states whose loop_entry is still
being verified. This reduces the number of processed instructions
for sched_ext programs by 28–92% in some cases.
- Patches #5-6 simplify {get,update}_loop_entry() logic (and are not
strictly necessary).
- Patches #7–10 mitigate the memory overhead introduced by patch #1
when a program with iterator-based loop hits the 1M instruction
limit. This is achieved by freeing states in env->free_list when
their branches and used_as_loop_entry counts reach zero.
Note: for env->peak_states computation in patch #10,
I think this should also include env->stack_size.
Patches #1-4 were previously sent as a part of [1].
[1] https://lore.kernel.org/bpf/20250122120442.3536298-1-eddyz87@xxxxxxxxx/
Eduard Zingerman (10):
bpf: copy_verifier_state() should copy 'loop_entry' field
selftests/bpf: test correct loop_entry update in copy_verifier_state
bpf: don't do clean_live_states when state->loop_entry->branches > 0
selftests/bpf: check states pruning for deeply nested iterator
bpf: detect infinite loop in get_loop_entry()
bpf: make state->dfs_depth < state->loop_entry->dfs_depth an invariant
bpf: do not update state->loop_entry in get_loop_entry()
bpf: use list_head to track explored states and free list
bpf: free verifier states when they are no longer referenced
bpf: fix env->peak_states computation
include/linux/bpf_verifier.h | 25 ++-
kernel/bpf/verifier.c | 229 +++++++++++++---------
tools/testing/selftests/bpf/progs/iters.c | 139 +++++++++++++
3 files changed, 296 insertions(+), 97 deletions(-)
--
2.48.1
