[bpf-next,v1,00/10] bpf: copy_verifier_state() should copy 'loop_entry' field

Message

Eduard Zingerman Feb. 15, 2025, 11:03 a.m. UTC

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/[e-mail]/

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(-)