bpf_loop inlining

Hi Everyone,

This is the next iteration of the patch. It includes changes suggested by Song, Joanne and Alexei. Please find updated intro message and change log below.

This patch implements inlining of calls to bpf_loop helper function when bpf_loop's callback is statically known. E.g. the rewrite does the following transformation during BPF program processing:

  bpf_loop(10, foo, NULL, 0);

->

  for (int i = 0; i < 10; ++i)
    foo(i, NULL);

The transformation leads to measurable latency change for simple loops. Measurements using benchs/run_bench_bpf_loop.sh inside QEMU / KVM on i7-4710HQ CPU show a drop in latency from 14 ns/op to 2 ns/op.

The change is split in five parts:

* Update to test_verifier.c to specify expected and unexpected instruction sequences. This allows to check BPF program rewrites applied by e.g. do_mix_fixups function.

* Update to test_verifier.c to specify BTF function infos and types per test case. This is necessary for tests that load sub-program addresses to a variable because of the checks applied by check_ld_imm function.

* The update to verifier.c that tracks state of the parameters for each bpf_loop call in a program and decides whether it could be replaced by a loop.

* A set of test cases for test_verifier that use capabilities added by the first two patches to verify instructions produced by inlining logic.

* Two test cases for test_prog to check that possible corner cases behave as expected.

Additional details are available in commit messages for each patch.

Changes since v7:
- Call to mark_chain_precision is added in loop_flag_is_zero to avoid potential issues with state pruning and precision tracking.
- flags non-zero test_verifier test case is updated to have two execution paths reaching bpf_loop call, one with flags = 0, another with flags = 1. Potentially this test case should be able to show that call to mark_chain_precision is necessary in loop_flag_is_zero but not at the moment. Please refer to discussion for [PATCH bpf-next v7 3/5] for additional details.
- stack_depth_extra computation is updated to guarantee that R6, R7 and R8 offsets are always aligned on 8 byte boundary.
- stack locations for loop vars test_verifier test case updated to show that R6, R7, R8 offsets are indeed aligned when function stack depth is not a multiple of 8.
- I removed Song Liu's ACK from commit message for [PATCH bpf-next v8 4/5] because I updated the patch. (Please let me know if I had to keep the ACK tag).

Changes since v6:
- Return value of the optimize_bpf_loop function is no longer ignored. This is necessary to properly propagate -ENOMEM error.

Changes since v5:
- Added function loop_flag_is_zero to skip a few checks in update_loop_inline_state when loop instruction is not fit for inline.

Changes since v4:
- Added missing static modifier for update_loop_inline_state and inline_bpf_loop functions.
- update_loop_inline_state updated for better readability.
- Fields initialized and fit_for_inline of struct bpf_loop_inline_state are changed back from bool to bitfields.
- Acks from Song Liu added to comments for patches 1/5, 2/5, 4/5, 5/5.

Changes since v3:
- Function adjust_stack_depth_for_loop_inlining is replaced by function optimize_bpf_loop. Function optimize_bpf_loop is responsible for both stack depth adjustment and call instruction replacement.
- Changes in do_misc_fixups are reverted.
- Changes in adjust_subprog_starts_after_remove are reverted and function adjust_loop_inline_subprogno is removed. This is possible because call to optimize_bpf_loop is placed before the dead code removal in opt_remove_dead_code (in contrast to the position of do_misc_fixups where inlining was done in v3).
- Field bpf_insn_aux_data.loop_inline_state is now a part of anonymous union at the start of the bpf_insn_aux_data.
- Data structure bpf_loop_inline_state is simplified to use single flag field fit_for_inline instead of separate fields flags_is_zero & callback_is_constant.
- Macro definition BPF_MAX_LOOPS is moved from include/linux/bpf_verifier.h to include/linux/bpf.h to avoid include of include/linux/bpf_verifier.h in bpf_iter.c.
- inline_bpf_loop changed back to use array initialization and hard coded offsets as in v2.
- Style / formatting updates.

Changes since v2:
- fix for stack_check test case in test_progs-no_alu32, all tests are passing now;
- v2 3/3 patch is split in three parts:
- kernel changes
- test_verifier changes
- test_prog changes
- updated inline_bpf_loop in verifier.c to calculate each offset used in instructions to avoid "magic" numbers;
- removed newline handling logic in fail_log branch of do_single_test in test_verifier.c to simplify the patch set;
- styling fixes suggested in review for v2 of this patch set.

Changes since v1:
- allow to use SKIP_INSNS in instruction pattern specification in test_verifier tests;
- fix for a bug in spill offset assignement for loop vars when bpf_loop is located in a non-main function.

Eduard Zingerman (5):
selftests/bpf: specify expected instructions in test_verifier tests selftests/bpf: allow BTF specs and func infos in test_verifier tests
bpf: Inline calls to bpf_loop when callback is known selftests/bpf: BPF test_verifier selftests for bpf_loop inlining selftests/bpf: BPF test_prog selftests for bpf_loop inlining

 include/linux/bpf.h                           |   3 +
 include/linux/bpf_verifier.h                  |  12 +
 kernel/bpf/bpf_iter.c                         |   9 +-
 kernel/bpf/verifier.c                         | 180 +++++++++-
 .../selftests/bpf/prog_tests/bpf_loop.c       |  62 ++++
 tools/testing/selftests/bpf/prog_tests/btf.c  |   1 -
 tools/testing/selftests/bpf/progs/bpf_loop.c  | 114 ++++++
 tools/testing/selftests/bpf/test_btf.h        |   2 +
 tools/testing/selftests/bpf/test_verifier.c   | 328 +++++++++++++++++-
 .../selftests/bpf/verifier/bpf_loop_inline.c  | 252 ++++++++++++++
 10 files changed, 936 insertions(+), 27 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/bpf_loop_inline.c

2.25.1