From: Alexei Starovoitov <ast@kernel.org>
To: <davem@davemloft.net>
Cc: <daniel@iogearbox.net>, <netdev@vger.kernel.org>,
<bpf@vger.kernel.org>, <kernel-team@fb.com>
Subject: [PATCH v3 bpf-next 0/9] bpf: bounded loops and other features
Date: Sat, 15 Jun 2019 12:12:16 -0700 [thread overview]
Message-ID: <20190615191225.2409862-1-ast@kernel.org> (raw)
v2->v3: fixed issues in backtracking pointed out by Andrii.
The next step is to add a lot more tests for backtracking.
v1->v2: addressed Andrii's feedback.
this patch set introduces verifier support for bounded loops and
adds several other improvements.
Ideally they would be introduced one at a time,
but to support bounded loop the verifier needs to 'step back'
in the patch 1. That patch introduces tracking of spill/fill
of constants through the stack. Though it's a useful feature
it hurts cilium tests.
Patch 3 introduces another feature by extending is_branch_taken
logic to 'if rX op rY' conditions. This feature is also
necessary to support bounded loops.
Then patch 4 adds support for the loops while adding
key heuristics with jmp_processed.
Introduction of parentage chain of verifier states in patch 4
allows patch 9 to add backtracking of precise scalar registers
which finally resolves degradation from patch 1.
The end result is much faster verifier for existing programs
and new support for loops.
See patch 8 for many kinds of loops that are now validated.
Patch 9 is the most tricky one and could be rewritten with
a different algorithm in the future.
Alexei Starovoitov (9):
bpf: track spill/fill of constants
selftests/bpf: fix tests due to const spill/fill
bpf: extend is_branch_taken to registers
bpf: introduce bounded loops
bpf: fix callees pruning callers
selftests/bpf: fix tests
selftests/bpf: add basic verifier tests for loops
selftests/bpf: add realistic loop tests
bpf: precise scalar_value tracking
include/linux/bpf_verifier.h | 69 +-
kernel/bpf/verifier.c | 767 ++++++++++++++++--
.../bpf/prog_tests/bpf_verif_scale.c | 67 +-
tools/testing/selftests/bpf/progs/loop1.c | 28 +
tools/testing/selftests/bpf/progs/loop2.c | 28 +
tools/testing/selftests/bpf/progs/loop3.c | 22 +
tools/testing/selftests/bpf/progs/pyperf.h | 6 +-
tools/testing/selftests/bpf/progs/pyperf600.c | 9 +
.../selftests/bpf/progs/pyperf600_nounroll.c | 8 +
.../testing/selftests/bpf/progs/strobemeta.c | 10 +
.../testing/selftests/bpf/progs/strobemeta.h | 528 ++++++++++++
.../bpf/progs/strobemeta_nounroll1.c | 9 +
.../bpf/progs/strobemeta_nounroll2.c | 9 +
.../selftests/bpf/progs/test_seg6_loop.c | 261 ++++++
.../selftests/bpf/progs/test_sysctl_loop1.c | 71 ++
.../selftests/bpf/progs/test_sysctl_loop2.c | 72 ++
.../selftests/bpf/progs/test_xdp_loop.c | 231 ++++++
tools/testing/selftests/bpf/test_verifier.c | 11 +-
tools/testing/selftests/bpf/verifier/calls.c | 22 +-
tools/testing/selftests/bpf/verifier/cfg.c | 11 +-
.../bpf/verifier/direct_packet_access.c | 3 +-
.../bpf/verifier/helper_access_var_len.c | 28 +-
tools/testing/selftests/bpf/verifier/loops1.c | 161 ++++
23 files changed, 2317 insertions(+), 114 deletions(-)
create mode 100644 tools/testing/selftests/bpf/progs/loop1.c
create mode 100644 tools/testing/selftests/bpf/progs/loop2.c
create mode 100644 tools/testing/selftests/bpf/progs/loop3.c
create mode 100644 tools/testing/selftests/bpf/progs/pyperf600.c
create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_nounroll.c
create mode 100644 tools/testing/selftests/bpf/progs/strobemeta.c
create mode 100644 tools/testing/selftests/bpf/progs/strobemeta.h
create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_nounroll1.c
create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_nounroll2.c
create mode 100644 tools/testing/selftests/bpf/progs/test_seg6_loop.c
create mode 100644 tools/testing/selftests/bpf/progs/test_sysctl_loop1.c
create mode 100644 tools/testing/selftests/bpf/progs/test_sysctl_loop2.c
create mode 100644 tools/testing/selftests/bpf/progs/test_xdp_loop.c
create mode 100644 tools/testing/selftests/bpf/verifier/loops1.c
--
2.20.0
next reply other threads:[~2019-06-15 19:12 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-06-15 19:12 Alexei Starovoitov [this message]
2019-06-15 19:12 ` [PATCH v3 bpf-next 1/9] bpf: track spill/fill of constants Alexei Starovoitov
2019-06-20 0:24 ` John Fastabend
2019-06-20 3:35 ` Alexei Starovoitov
2019-06-20 5:04 ` John Fastabend
2019-06-20 15:37 ` Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 2/9] selftests/bpf: fix tests due to const spill/fill Alexei Starovoitov
2019-06-20 5:40 ` John Fastabend
2019-06-15 19:12 ` [PATCH v3 bpf-next 3/9] bpf: extend is_branch_taken to registers Alexei Starovoitov
2019-06-20 6:01 ` John Fastabend
2019-06-15 19:12 ` [PATCH v3 bpf-next 4/9] bpf: introduce bounded loops Alexei Starovoitov
2019-06-20 9:59 ` [bpf] 9fe4f05d33: kernel_selftests.bpf.test_verifier.fail kernel test robot
2019-06-15 19:12 ` [PATCH v3 bpf-next 5/9] bpf: fix callees pruning callers Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 6/9] selftests/bpf: fix tests Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 7/9] selftests/bpf: add basic verifier tests for loops Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 8/9] selftests/bpf: add realistic loop tests Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 9/9] bpf: precise scalar_value tracking Alexei Starovoitov
2019-06-17 17:20 ` Andrii Nakryiko
2019-06-17 16:39 ` [PATCH v3 bpf-next 0/9] bpf: bounded loops and other features Andrii Nakryiko
2019-06-17 18:57 ` Alexei Starovoitov
2019-06-17 19:06 ` Andrii Nakryiko
2019-06-18 14:05 ` Paul Chaignon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190615191225.2409862-1-ast@kernel.org \
--to=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=davem@davemloft.net \
--cc=kernel-team@fb.com \
--cc=netdev@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).