bpf: fix precision backtracking instruction iteration

The first patch in this patchset was already backported before, as commit ecc2aeeaa08a, to address CVE-2023-52920 [1]. That backport was however later reverted in commit 199f04528737 because it reduced the efficiency of the BPF verifier, to the point that it rejected some previously-accepted programs.

This patchset backports commit 41f6f64e6999 ("bpf: support non-r10 register spill/fill to/from stack in precision tracking") again, but this time with the subsequent commits that improved the efficiency of the verifier. In addition, the last two commits fix and test a regression that was later found in commit 41f6f64e6999.

It took us a while with Shung-Hsi to come back to this because we felt we didn't have enough test coverage to backport this. That changed with the stable BPF CI Shung-Hsi built for v6.6, which successfully validated this patchset [2]. In addition, I tested the impact of this patchset on the verifier's efficiency with Cilium's BPF programs [3]:
it significantly improves, reducing the number of instructions the verifier has to analyze by up to 87% in some cases!

1: https://lore.kernel.org/linux-cve-announce/2024110518-CVE-2023-52920-17f6@gregkh/
2: https://github.com/pchaigno/stable-bpf-ci/actions/runs/25671397661/job/75357317078
3: https://pchaigno.github.io/test-verifier-complexity.html

Andrii Nakryiko (10):
bpf: support non-r10 register spill/fill to/from stack in precision
tracking
selftests/bpf: add stack access precision test
bpf: preserve STACK_ZERO slots on partial reg spills selftests/bpf: validate STACK_ZERO is preserved on subreg spill
bpf: preserve constant zero when doing partial register restore selftests/bpf: validate zero preservation for sub-slot loads
bpf: track aligned STACK_ZERO cases as imprecise spilled registers selftests/bpf: validate precision logic in
partial_stack_load_preserves_zeros
bpf: handle fake register spill to stack with BPF_ST_MEM instruction selftests/bpf: validate fake register spill/fill precision
backtracking logic

 include/linux/bpf_verifier.h                  |  31 +-
 kernel/bpf/verifier.c                         | 233 +++++++++------
 .../selftests/bpf/progs/verifier_spill_fill.c | 281 ++++++++++++++++++
 .../bpf/progs/verifier_subprog_precision.c    |  87 +++++-
 .../testing/selftests/bpf/verifier/precise.c  |  38 ++-
 5 files changed, 557 insertions(+), 113 deletions(-)

2.43.0