selftests/bpf: add a verifier scale test with unknown bounded loop
Subsystems (3)
PATCH v2 1/1 selftests/bpf: add a verifier scale test with unknown bounded loop
The original bcc pull request
https://github.com/iovisor/bcc/pull/3270
exposed a verifier failure with Clang 12/13 while Clang 4 works fine. Further investigation exposed two issues.
Issue 1: LLVM may generate code which uses less refined
value. The issue is fixed in llvm patch
https://reviews.llvm.org/D97479
Issue 2: Spills with initial value 0 are marked as precise
which makes later state pruning less effective. This is my rough initial analysis and further investigation is needed to find how to improve verifier pruning in such cases.
With the above llvm patch, for the new loop6.c test, which has smaller loop bound compared to original test, I got
$ test_progs -s -n 10/16
...
stack depth 64
processed 390735 insns (limit 1000000) max_states_per_insn 87
total_states 8658 peak_states 964 mark_read 6
#10/16 loop6.o:OKUse the original loop bound, i.e., commenting out "#define WORKAROUND", I got
$ test_progs -s -n 10/16
...
BPF program is too large. Processed 1000001 insn
stack depth 64
processed 1000001 insns (limit 1000000) max_states_per_insn 91
total_states 23176 peak_states 5069 mark_read 6
...
#10/16 loop6.o:FAILThe purpose of this patch is to provide a regression test for the above llvm fix and also provide a test case for further analyzing the verifier pruning issue.
--- tools/testing/selftests/bpf/README.rst | 39 ++++++++ .../bpf/prog_tests/bpf_verif_scale.c | 1 + tools/testing/selftests/bpf/progs/loop6.c | 99 +++++++++++++++++++ 3 files changed, 139 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/loop6.c
Changelog:
v1 -> v2:
- use BPF_KPROBE macro to simplify code.
tools/testing/selftests/bpf/README.rst +39 -0
@@ -111,6 +111,45 @@ available in 10.0.1. The patch is available in llvm 11.0.0 trunk. __ https://reviews.llvm.org/D78466 +bpf_verif_scale/loop6.o test failure with Clang 12 +================================================== + +With Clang 12, the following bpf_verif_scale test failed: + * ``bpf_verif_scale/loop6.o`` + +The verifier output looks like + +.. code-block:: c + + R1 type=ctx expected=fp + The sequence of 8193 jumps is too complex. + +The reason is compiler generating the following code + +.. code-block:: c + + ; for (i = 0; (i < VIRTIO_MAX_SGS) && (i < num); i++) { + 14: 16 05 40 00 00 00 00 00 if w5 == 0 goto +64 <LBB0_6> + 15: bc 51 00 00 00 00 00 00 w1 = w5 + 16: 04 01 00 00 ff ff ff ff w1 += -1 + 17: 67 05 00 00 20 00 00 00 r5 <<= 32 + 18: 77 05 00 00 20 00 00 00 r5 >>= 32 + 19: a6 01 01 00 05 00 00 00 if w1 < 5 goto +1 <LBB0_4> + 20: b7 05 00 00 06 00 00 00 r5 = 6 + 00000000000000a8 <LBB0_4>: + 21: b7 02 00 00 00 00 00 00 r2 = 0 + 22: b7 01 00 00 00 00 00 00 r1 = 0 + ; for (i = 0; (i < VIRTIO_MAX_SGS) && (i < num); i++) { + 23: 7b 1a e0 ff 00 00 00 00 *(u64 *)(r10 - 32) = r1 + 24: 7b 5a c0 ff 00 00 00 00 *(u64 *)(r10 - 64) = r5 + +Note that insn #15 has w1 = w5 and w1 is refined later but +r5(w5) is eventually saved on stack at insn #24 for later use. +This cause later verifier failure. The bug has been `fixed`__ in +Clang 13. + +__ https://reviews.llvm.org/D97479 + BPF CO-RE-based tests and Clang version =======================================
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +1 -0
@@ -76,6 +76,7 @@ void test_bpf_verif_scale(void) { "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT }, { "loop4.o", BPF_PROG_TYPE_SCHED_CLS }, { "loop5.o", BPF_PROG_TYPE_SCHED_CLS }, + { "loop6.o", BPF_PROG_TYPE_KPROBE },/* partial unroll. 19k insn in a loop. * Total program size 20.8k insn.
tools/testing/selftests/bpf/progs/loop6.c new file +99 -0
99 lines not on this page · raw message
Signature · 1 line
2.24.1
This patch was applied to bpf/bpf-next.git (refs/heads/master):
Hello:
This patch was applied to bpf/bpf-next.git (refs/heads/master):
Quoted 13 lines · On Fri, 26 Feb 2021 14:38:10 -0800 you wrote:
The original bcc pull request
https://github.com/iovisor/bcc/pull/3270
exposed a verifier failure with Clang 12/13 while Clang 4 works fine. Further investigation exposed two issues.
Issue 1: LLVM may generate code which uses less refined
value. The issue is fixed in llvm patch
https://reviews.llvm.org/D97479
Issue 2: Spills with initial value 0 are marked as precise
which makes later state pruning less effective. This is my rough initial analysis and further investigation is needed to find how to improve verifier pruning in such cases.
Quoted 1 line
[...]
Here is the summary with links:
- [bpf-next,v2] selftests/bpf: add a verifier scale test with unknown bounded loop
https://git.kernel.org/bpf/bpf-next/c/86a35af628e5
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html