[PATCH 6.6.y 00/17] bpf: backport of iterator and callback handling fixes

[Eduard Zingerman <eddyz87@gmail.com>]

This is a backport of two upstream patch-sets:
1. "exact states comparison for iterator convergence checks"
   https://lore.kernel.org/all/20231024000917.12153-1-eddyz87@gmail.com/
2. "verify callbacks as if they are called unknown number of times"
   https://lore.kernel.org/all/20231121020701.26440-1-eddyz87@gmail.com/
  
Both patch-sets fix BPF verifier logic related to handling loops:
for bpf iterators, and for helper functions that accept callback
functions.

The backport of (2) was requested as a response to bug report by
Mateusz Gienieczko <mat.gienieczko@tum.de>.
The (1) is a dependency of (2).

The patch-set was tested by running BPF verifier selftests on my local
qemu-based setup.

Most of the commits could be cherry-picked but three required merging:

| Action | Upstream commit                                                                                 |
|--------+-------------------------------------------------------------------------------------------------|
| pick   | 3c4e420cb653 ("bpf: move explored_state() closer to the beginning of verifier.c ")              |
| pick   | 4c97259abc9b ("bpf: extract same_callsites() as utility function ")                             |
| merge  | 2793a8b015f7 ("bpf: exact states comparison for iterator convergence checks ")                  |
| pick   | 389ede06c297 ("selftests/bpf: tests with delayed read/precision makrs in loop body ")           |
| pick   | 2a0992829ea3 ("bpf: correct loop detection for iterators convergence ")                         |
| pick   | 64870feebecb ("selftests/bpf: test if state loops are detected in a tricky case ")              |
| pick   | b4d8239534fd ("bpf: print full verifier states on infinite loop detection ")                    |
| drop   | dedd6c894110 ("Merge branch 'exact-states-comparison-for-iterator-convergence-checks' ")        |
|--------+-------------------------------------------------------------------------------------------------|
| pick   | 977bc146d4eb ("selftests/bpf: track tcp payload offset as scalar in xdp_synproxy ")             |
| pick   | 87eb0152bcc1 ("selftests/bpf: track string payload offset as scalar in strobemeta ")            |
| pick   | 683b96f9606a ("bpf: extract __check_reg_arg() utility function ")                               |
| pick   | 58124a98cb8e ("bpf: extract setup_func_entry() utility function ")                              |
| merge  | ab5cfac139ab ("bpf: verify callbacks as if they are called unknown number of times ")           |
| pick   | 958465e217db ("selftests/bpf: tests for iterating callbacks ")                                  |
| pick   | cafe2c21508a ("bpf: widening for callback iterators ")                                          |
| pick   | 9f3330aa644d ("selftests/bpf: test widening for iterating callbacks ")                          |
| merge  | bb124da69c47 ("bpf: keep track of max number of bpf_loop callback iterations ")                 |
| pick   | 57e2a52deeb1 ("selftests/bpf: check if max number of bpf_loop iterations is tracked ")          |
| drop   | acb12c859ac7 ("Merge branch 'verify-callbacks-as-if-they-are-called-unknown-number-of-times' ") |

Note:
I don't know how deal with merge commits, so I just dropped those.
These commits are empty but contain cover letters for both series,
so it might be useful to pick those (how?).

Eduard Zingerman (17):
  bpf: move explored_state() closer to the beginning of verifier.c
  bpf: extract same_callsites() as utility function
  bpf: exact states comparison for iterator convergence checks
  selftests/bpf: tests with delayed read/precision makrs in loop body
  bpf: correct loop detection for iterators convergence
  selftests/bpf: test if state loops are detected in a tricky case
  bpf: print full verifier states on infinite loop detection
  selftests/bpf: track tcp payload offset as scalar in xdp_synproxy
  selftests/bpf: track string payload offset as scalar in strobemeta
  bpf: extract __check_reg_arg() utility function
  bpf: extract setup_func_entry() utility function
  bpf: verify callbacks as if they are called unknown number of times
  selftests/bpf: tests for iterating callbacks
  bpf: widening for callback iterators
  selftests/bpf: test widening for iterating callbacks
  bpf: keep track of max number of bpf_loop callback iterations
  selftests/bpf: check if max number of bpf_loop iterations is tracked

 include/linux/bpf_verifier.h                  |  32 +
 kernel/bpf/verifier.c                         | 875 ++++++++++++++----
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 tools/testing/selftests/bpf/progs/cb_refs.c   |   1 +
 tools/testing/selftests/bpf/progs/iters.c     | 695 ++++++++++++++
 .../testing/selftests/bpf/progs/strobemeta.h  |  78 +-
 .../bpf/progs/verifier_iterating_callbacks.c  | 242 +++++
 .../bpf/progs/verifier_subprog_precision.c    |  86 +-
 .../selftests/bpf/progs/xdp_synproxy_kern.c   |  84 +-
 9 files changed, 1830 insertions(+), 265 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c

-- 
2.43.0