Re: [PATCH bpf-next v4 09/14] bpf: simplify liveness to use (callsite, depth) keyed func_instances

[Paul Chaignon <paul.chaignon@gmail.com>]

On Fri, Apr 10, 2026 at 01:56:00PM -0700, Eduard Zingerman wrote:
> Rework func_instance identification and remove the dynamic liveness
> API, completing the transition to fully static stack liveness analysis.
> 
> Replace callchain-based func_instance keys with (callsite, depth)
> pairs. The full callchain (all ancestor callsites) is no longer part
> of the hash key; only the immediate callsite and the call depth
> matter. This does not lose precision in practice and simplifies the
> data structure significantly: struct callchain is removed entirely,
> func_instance stores just callsite, depth.
> 
> Drop must_write_acc propagation. Previously, must_write marks were
> accumulated across successors and propagated to the caller via
> propagate_to_outer_instance(). Instead, callee entry liveness
> (live_before at subprog start) is pulled directly back to the
> caller's callsite in analyze_subprog() after each callee returns.
> 
> Since (callsite, depth) instances are shared across different call
> chains that invoke the same subprog at the same depth, must_write
> marks from one call may be stale for another. To handle this,
> analyze_subprog() records into a fresh_instance() when the instance
> was already visited (must_write_initialized), then merge_instances()
> combines the results: may_read is unioned, must_write is intersected.
> This ensures only slots written on ALL paths through all call sites
> are marked as guaranteed writes.
> This replaces commit_stack_write_marks() logic.
> 
> Skip recursive descent into callees that receive no FP-derived
> arguments (has_fp_args() check). This is needed because global
> subprogram calls can push depth beyond MAX_CALL_FRAMES (max depth
> is 64 for global calls but only 8 frames are accommodated for FP
> passing). It also handles the case where a callback subprog cannot be
> determined by argument tracking: such callbacks will be processed by
> analyze_subprog() at depth 0 independently.
> 
> Update lookup_instance() (used by is_live_before queries) to search
> for the func_instance with maximal depth at the corresponding
> callsite, walking depth downward from frameno to 0. This accounts for
> the fact that instance depth no longer corresponds 1:1 to
> bpf_verifier_state->curframe, since skipped non-FP calls create gaps.
> 
> Remove the dynamic public liveness API from verifier.c:
>   - bpf_mark_stack_{read,write}(), bpf_reset/commit_stack_write_marks()
>   - bpf_update_live_stack(), bpf_reset_live_stack_callchain()
>   - All call sites in check_stack_{read,write}_fixed_off(),
>     check_stack_range_initialized(), mark_stack_slot_obj_read(),
>     mark/unmark_stack_slots_{dynptr,iter,irq_flag}()
>   - The per-instruction write mark accumulation in do_check()
>   - The bpf_update_live_stack() call in prepare_func_exit()
> 
> mark_stack_read() and mark_stack_write() become static functions in
> liveness.c, called only from the static analysis pass. The
> func_instance->updated and must_write_dropped flags are removed.
> Remove spis_single_slot(), spis_one_bit() helpers from bpf_verifier.h
> as they are no longer used.
> 
> Signed-off-by: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>

I tested this series with Cilium's complexity test suite [1]. We have a
lot of different configuration and some producing larger programs than
covered in the cover letter.

Overall, the impact is quite good. It reduces the number of processed
instructions by more than 60k instructions for some of our largest
programs. It also increases the number of processed instructions by up
to 20k in fewer other cases, but I think it's manageable because they
are not the largest programs so we have some room. The mean diff over
all programs is a reduction of a few thousands processed instructions.

For good measure, I also ran this patchset through a subset of Cilium's
CI. All looks good.

For the whole series, but probably only needs to be applied for this
patch:

Tested-by: Paul Chaignon <paul.chaignon@gmail.com>

1: https://pchaigno.github.io/test-verifier-complexity.html

[...]