[v5,bpf-next,0/8] BPF open-coded iterators

Message

Andrii Nakryiko March 8, 2023, 6:41 p.m. UTC

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 patches #4-#5). 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 (which we now enforce on the kernel side).

Patch #1 is preparatory refactoring for easier way to check for special kfunc
calls. Patch #2 is adding iterator kfunc registration and validation logic,
which is mostly independent from the rest of open-coded iterator logic, so is
separated out for easier reviewing.

The meat of verifier-side logic is in patch #3. Patch #4 implements numbers
iterator. I kept them separate to have clean reference for how to integrate
new iterator types (now even simpler to do than in v1 of this patch set).
Patch #5 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 #6 is verification tests, based on numbers iterator (as the only
available right now). Patch #7 actually tests runtime behavior of numbers
iterator.

Finally, with changes in v2, it's possible and trivial to implement custom
iterators completely in kernel modules, which we showcase and test by adding
a simple iterator returning same number a given number of times to
bpf_testmod. Patch #8 is where all this happens and is tested.

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

v4->v5:
  - fixing missed inner for() in is_iter_reg_valid_uninit, and fixed return
    false (kernel test robot);
  - typo fixes and comment/commit description improvements throughout the
    patch set;
v3->v4:
  - remove unused variable from is_iter_reg_valid_init (kernel test robot);
v2->v3:
  - remove special kfunc leftovers for bpf_iter_num_{new,next,destroy};
  - add iters/testmod_seq* to DENYLIST.s390x, it doesn't support kfuncs in
    modules yet (CI);
v1->v2:
  - rebased on latest, dropping previously landed preparatory patches;
  - each iterator type now have its own `struct bpf_iter_<type>` which allows
    each iterator implementation to use exactly as much stack space as
    necessary, allowing to avoid runtime allocations (Alexei);
  - reworked how iterator kfuncs are defined, no verifier changes are required
    when adding new iterator type;
  - added bpf_testmod-based iterator implementation;
  - address the rest of feedback, comments, commit message adjustment, etc.

Cc: Tejun Heo <[e-mail]>

Andrii Nakryiko (8):
  bpf: factor out fetching basic kfunc metadata
  bpf: add iterator kfuncs registration and validation logic
  bpf: add support for open-coded iterator loops
  bpf: implement numbers iterator
  selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros
  selftests/bpf: add iterators tests
  selftests/bpf: add number iterator tests
  selftests/bpf: implement and test custom testmod_seq iterator

 include/linux/bpf.h                           |   8 +-
 include/linux/bpf_verifier.h                  |  25 +
 include/linux/btf.h                           |   4 +
 include/uapi/linux/bpf.h                      |   8 +
 kernel/bpf/bpf_iter.c                         |  70 ++
 kernel/bpf/btf.c                              | 112 ++-
 kernel/bpf/helpers.c                          |   3 +
 kernel/bpf/verifier.c                         | 687 ++++++++++++++++-
 tools/include/uapi/linux/bpf.h                |   8 +
 tools/testing/selftests/bpf/DENYLIST.s390x    |   1 +
 .../selftests/bpf/bpf_testmod/bpf_testmod.c   |  42 +-
 .../selftests/bpf/bpf_testmod/bpf_testmod.h   |   6 +
 .../bpf/prog_tests/bpf_verif_scale.c          |   6 +
 .../testing/selftests/bpf/prog_tests/iters.c  | 106 +++
 .../bpf/prog_tests/uprobe_autoattach.c        |   1 -
 tools/testing/selftests/bpf/progs/bpf_misc.h  | 100 +++
 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  | 426 +++++++++++
 .../selftests/bpf/progs/iters_testmod_seq.c   |  79 ++
 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 -
 25 files changed, 2790 insertions(+), 55 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/iters_testmod_seq.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c

Comments

[e-mail] March 9, 2023, 12:30 a.m. UTC | #1

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <[e-mail]>:

On Wed, 8 Mar 2023 10:41:13 -0800 you wrote:
> 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 patches #4-#5). 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 (which we now enforce on the kernel side).
> 
> [...]

Here is the summary with links:
  - [v5,bpf-next,1/8] bpf: factor out fetching basic kfunc metadata
    https://git.kernel.org/bpf/bpf-next/c/07236eab7a31
  - [v5,bpf-next,2/8] bpf: add iterator kfuncs registration and validation logic
    https://git.kernel.org/bpf/bpf-next/c/215bf4962f6c
  - [v5,bpf-next,3/8] bpf: add support for open-coded iterator loops
    https://git.kernel.org/bpf/bpf-next/c/06accc8779c1
  - [v5,bpf-next,4/8] bpf: implement numbers iterator
    https://git.kernel.org/bpf/bpf-next/c/6018e1f407cc
  - [v5,bpf-next,5/8] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros
    https://git.kernel.org/bpf/bpf-next/c/8c2b5e90505e
  - [v5,bpf-next,6/8] selftests/bpf: add iterators tests
    https://git.kernel.org/bpf/bpf-next/c/57400dcce6c2
  - [v5,bpf-next,7/8] selftests/bpf: add number iterator tests
    https://git.kernel.org/bpf/bpf-next/c/f59b14609265
  - [v5,bpf-next,8/8] selftests/bpf: implement and test custom testmod_seq iterator
    https://git.kernel.org/bpf/bpf-next/c/7e86a8c4ac8d

You are awesome, thank you!