[PATCH bpf-next v6 0/6] Improve stack depth verification stats output

Some improvements for more clarity in the stack depth verification
statistics output. See commit logs for details.

For example, ./test_progs -t subprogs/subprogs_alone loads prog4,
which has a main program, two static subprograms, and two independently
verified global subprograms. A sample run produces:

  verification time 1765 usec
  stack depth max 48
  subprog 0 (prog4) main insns_own 29 insns_total 51 stack 8
  subprog 1 (get_task_tgid) global insns_own 9 insns_total 9 stack 8
  subprog 2 (sub4) static insns_own 15 insns_total 22 stack 8
  subprog 3 (sub3) static insns_own 7 insns_total 7 stack 0
  subprog 4 (sub1) global insns_own 10 insns_total 10 stack 8
  processed 70 insns (limit 1000000) max_states_per_insn 0 total_states 7 peak_states 7 mark_read 0

The insns_own counts account for every processed instruction exactly once:

  29 + 9 + 15 + 7 + 10 = 70

The main program and global subprograms are independent exploration roots,
so their insns_total counts also account for the full processed budget:

  51 + 9 + 10 = 70

Static subprogram totals provide a nested, top-down breakdown inside their
root. In this example:

  sub4: 22 = 15 own + 7 in sub3
  prog4: 51 = 29 own + 22 in sub4

The global subprogram bodies are accounted in their own root totals rather
than being included in prog4 or the static callees which call them.

Asynchronous callback work is propagated through every scheduling subprogram
in a nested callback chain. Running:

  ./test_progs -t verifier_subprog_insn_stats/stats_async_nested -v

produces the following stats:

  stack depth max 0
  subprog 0 (stats_async_nested) main insns_own 9 insns_total 23 stack 0
  subprog 1 (stats_async_nested_leaf) static insns_own 2 insns_total 2 stack 0
  subprog 2 (stats_async_outer) static insns_own 6 insns_total 8 stack 0
  subprog 3 (stats_async_nested_schedule) static insns_own 6 insns_total 14 stack 0
  processed 23 insns

Here, 9 + 2 + 6 + 6 = 23. The nested callback work is propagated
bottom-up through both scheduling subprograms:

  stats_async_outer: 8 = 6 own + 2 in stats_async_nested_leaf
  stats_async_nested_schedule: 14 = 6 own + 8 in stats_async_outer
  stats_async_nested: 23 = 9 own + 14 in stats_async_nested_schedule

Changelog:
----------
v5 -> v6
v5: https://lore.kernel.org/bpf/[email protected]

 * Track own and inclusive instruction counts for main, global, and static
   subprograms. (Andrii, Eduard)
 * Keep instruction subtotals path-local across verifier state copies.
 * Propagate async callback budget through nested scheduling chains. (Andrii)
 * Split per-subprogram instruction accounting into a preparatory patch.
 * Add deterministic selftests with exact own, total, and processed counts.

v4 -> v5
v4: https://lore.kernel.org/bpf/[email protected]

 * Change the format to combine instruction counts and stack depths into
   per-program records. (Andrii)
 * Adjust veristat for the new format while retaining support for the legacy format.
 * Explain why the legacy stack parsing buffer is zero-initialized. (BPF CI Bot)

v3 -> v4
v3: https://lore.kernel.org/bpf/[email protected]

 * Read names from subprog_info directly to avoid an out-of-bounds access
   when func_info validation fails. (BPF CI Bot)

v2 -> v3
v2: https://lore.kernel.org/bpf/[email protected]

 * Reuse subprog_name() to fetch subprogram names. (BPF CI Bot)

v1 -> v2
v1: https://lore.kernel.org/bpf/[email protected]

 * Use multi-line format. (Eduard)
 * Adjust veristat to work with old and new format.
 * Adjust selftest log_level without new option. (Eduard)

Kumar Kartikeya Dwivedi (6):
  bpf: Track verifier instruction stats for each subprogram
  bpf: Propagate async callback instructions to scheduling subprograms
  bpf: Show more useful info in stack depth stats
  selftests/bpf: Adjust veristat stack depth parsing
  selftests/bpf: Test stack depth stats without BTF subprog names
  selftests/bpf: Test subprogram instruction statistics

 include/linux/bpf_verifier.h                  |   7 +-
 kernel/bpf/verifier.c                         |  88 +++++--
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../bpf/progs/verifier_basic_stack.c          |   8 +-
 .../bpf/progs/verifier_bpf_fastcall.c         |  38 ++-
 .../bpf/progs/verifier_global_subprogs.c      |   6 +-
 .../bpf/progs/verifier_private_stack.c        |  22 +-
 .../bpf/progs/verifier_subprog_insn_stats.c   | 225 ++++++++++++++++++
 .../selftests/bpf/progs/verifier_var_off.c    |   8 +-
 tools/testing/selftests/bpf/test_verifier.c   |   2 +-
 tools/testing/selftests/bpf/verifier/calls.c  |  12 +-
 tools/testing/selftests/bpf/veristat.c        |  16 +-
 12 files changed, 395 insertions(+), 39 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_subprog_insn_stats.c


base-commit: 6655c409707ec8ce9ce0850ffe4fe02331fd4d9c
-- 
2.53.0