From: Alexei Starovoitov <ast@kernel.org>
To: <davem@davemloft.net>
Cc: <daniel@iogearbox.net>, <andriin@fb.com>,
<netdev@vger.kernel.org>, <bpf@vger.kernel.org>,
<kernel-team@fb.com>
Subject: [PATCH v2 bpf-next 0/9] bpf: bounded loops and other features
Date: Fri, 14 Jun 2019 00:25:48 -0700 [thread overview]
Message-ID: <20190614072557.196239-1-ast@kernel.org> (raw)
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 | 739 ++++++++++++++++--
.../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, 2289 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-14 7:26 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-06-14 7:25 Alexei Starovoitov [this message]
2019-06-14 7:25 ` [PATCH v2 bpf-next 1/9] bpf: track spill/fill of constants Alexei Starovoitov
2019-06-14 16:29 ` Andrii Nakryiko
2019-06-14 7:25 ` [PATCH v2 bpf-next 2/9] selftests/bpf: fix tests due to const spill/fill Alexei Starovoitov
2019-06-14 7:25 ` [PATCH v2 bpf-next 3/9] bpf: extend is_branch_taken to registers Alexei Starovoitov
2019-06-14 16:38 ` Andrii Nakryiko
2019-06-14 7:25 ` [PATCH v2 bpf-next 4/9] bpf: introduce bounded loops Alexei Starovoitov
2019-06-14 7:25 ` [PATCH v2 bpf-next 5/9] bpf: fix callees pruning callers Alexei Starovoitov
2019-06-14 7:25 ` [PATCH v2 bpf-next 6/9] selftests/bpf: fix tests Alexei Starovoitov
2019-06-14 7:25 ` [PATCH v2 bpf-next 7/9] selftests/bpf: add basic verifier tests for loops Alexei Starovoitov
2019-06-14 7:25 ` [PATCH v2 bpf-next 8/9] selftests/bpf: add realistic loop tests Alexei Starovoitov
2019-06-14 16:49 ` Andrii Nakryiko
2019-06-14 7:25 ` [PATCH v2 bpf-next 9/9] bpf: precise scalar_value tracking Alexei Starovoitov
2019-06-14 21:45 ` Andrii Nakryiko
2019-06-15 19:00 ` Alexei Starovoitov
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=20190614072557.196239-1-ast@kernel.org \
--to=ast@kernel.org \
--cc=andriin@fb.com \
--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).