[PATCH bpf-next 00/17] BPF open-coded iterators

[Andrii Nakryiko <andrii@kernel.org>]

Add support for open-coded (aka inline) iterators in BPF world. This is a next
evolution of gradually allowing more powerful and less restrictive looping and
iteration capabilities to BPF programs.

We set up a framework for implementing all kinds of iterators (e.g., cgroup,
task, file, etc, iterators), but this patch set only implements numbers
iterator, which is used to implement ergonomic bpf_for() for-like construct
(see patch #15). We also add bpf_for_each(), which is a generic foreach-like
construct that will work with any kind of open-coded iterator implementation,
as long as we stick with bpf_iter_<type>_{new,next,destroy}() naming pattern.

Patches #1 through #12 are various preparatory patches, first eitht of them
are from preliminaries patch set ([0]) which haven't landed yet, so I just
merged them together to let CI do end-to-end testing of everything properly.
Few new patches further adds some necessary functionality in verifier (like
fixed-size read-only memory access for `int *`-returning kfuncs).

The meat of verifier-side logic is in lucky patch #13. Patch #14 implements
numbers iterator. I kept them separate to have clean reference for how to
integrate new iterator types. And it makes verifier core logic changes
abstracted from any particularities of numbers iterator. Patch #15 adds
bpf_for(), bpf_for_each(), and bpf_repeat() macros to bpf_misc.h, and also
adds yet another pyperf test variant, now with bpf_for() loop. Patch #16 is
verification tests, based on numbers iterator (as the only available right
now). Patch #17 actually tests runtime behavior of numbers iterator.

Most of the relevant details are in corresponding commit messages or code
comments.

  [0] https://patchwork.kernel.org/project/netdevbpf/list/?series=725996&state=*

Cc: Tejun Heo <tj@kernel.org>

Andrii Nakryiko (17):
  bpf: improve stack slot state printing
  bpf: improve regsafe() checks for PTR_TO_{MEM,BUF,TP_BUFFER}
  selftests/bpf: enhance align selftest's expected log matching
  bpf: honor env->test_state_freq flag in is_state_visited()
  selftests/bpf: adjust log_fixup's buffer size for proper truncation
  bpf: clean up visit_insn()'s instruction processing
  bpf: fix visit_insn()'s detection of BPF_FUNC_timer_set_callback
    helper
  bpf: ensure that r0 is marked scratched after any function call
  bpf: move kfunc_call_arg_meta higher in the file
  bpf: mark PTR_TO_MEM as non-null register type
  bpf: generalize dynptr_get_spi to be usable for iters
  bpf: add support for fixed-size memory pointer returns for kfuncs
  bpf: add support for open-coded iterator loops
  bpf: implement number iterator
  selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros
  selftests/bpf: add iterators tests
  selftests/bpf: add number iterator tests

 include/linux/bpf.h                           |  19 +-
 include/linux/bpf_verifier.h                  |  22 +-
 include/uapi/linux/bpf.h                      |   6 +
 kernel/bpf/bpf_iter.c                         |  71 ++
 kernel/bpf/helpers.c                          |   3 +
 kernel/bpf/verifier.c                         | 851 ++++++++++++++++--
 tools/include/uapi/linux/bpf.h                |   6 +
 .../testing/selftests/bpf/prog_tests/align.c  |  18 +-
 .../bpf/prog_tests/bpf_verif_scale.c          |   6 +
 .../testing/selftests/bpf/prog_tests/iters.c  |  62 ++
 .../selftests/bpf/prog_tests/log_fixup.c      |   2 +-
 .../bpf/prog_tests/uprobe_autoattach.c        |   1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  |  77 ++
 tools/testing/selftests/bpf/progs/iters.c     | 720 +++++++++++++++
 .../selftests/bpf/progs/iters_looping.c       | 163 ++++
 tools/testing/selftests/bpf/progs/iters_num.c | 242 +++++
 .../selftests/bpf/progs/iters_state_safety.c  | 455 ++++++++++
 tools/testing/selftests/bpf/progs/lsm.c       |   4 +-
 tools/testing/selftests/bpf/progs/pyperf.h    |  14 +-
 .../selftests/bpf/progs/pyperf600_iter.c      |   7 +
 .../selftests/bpf/progs/pyperf600_nounroll.c  |   3 -
 21 files changed, 2641 insertions(+), 111 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/iters.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters_looping.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters_num.c
 create mode 100644 tools/testing/selftests/bpf/progs/iters_state_safety.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c

-- 
2.30.2