From: Maxim Mikityanskiy <maxtram95@gmail.com>
To: Eduard Zingerman <eddyz87@gmail.com>,
Alexei Starovoitov <ast@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Andrii Nakryiko <andrii@kernel.org>,
Shung-Hsi Yu <shung-hsi.yu@suse.com>
Cc: John Fastabend <john.fastabend@gmail.com>,
Martin KaFai Lau <martin.lau@linux.dev>,
Song Liu <song@kernel.org>,
Yonghong Song <yonghong.song@linux.dev>,
KP Singh <kpsingh@kernel.org>,
Stanislav Fomichev <sdf@google.com>, Hao Luo <haoluo@google.com>,
Jiri Olsa <jolsa@kernel.org>, Mykola Lysenko <mykolal@fb.com>,
Shuah Khan <shuah@kernel.org>,
"David S. Miller" <davem@davemloft.net>,
Jakub Kicinski <kuba@kernel.org>,
Jesper Dangaard Brouer <hawk@kernel.org>,
bpf@vger.kernel.org, linux-kselftest@vger.kernel.org,
netdev@vger.kernel.org, Maxim Mikityanskiy <maxim@isovalent.com>
Subject: [PATCH bpf-next v2 00/15] Improvements for tracking scalars in the BPF verifier
Date: Mon, 8 Jan 2024 22:51:54 +0200 [thread overview]
Message-ID: <20240108205209.838365-1-maxtram95@gmail.com> (raw)
From: Maxim Mikityanskiy <maxim@isovalent.com>
The goal of this series is to extend the verifier's capabilities of
tracking scalars when they are spilled to stack, especially when the
spill or fill is narrowing. It also contains a fix by Eduard for
infinite loop detection and a state pruning optimization by Eduard that
compensates for a verification complexity regression introduced by
tracking unbounded scalars. These improvements reduce the surface of
false rejections that I saw while working on Cilium codebase.
Patch 1 (Maxim): Fix for an existing test, it will matter later in the
series.
Patches 2-3 (Eduard): Fixes for false rejections in infinite loop
detection that happen in the selftests when my patches are applied.
Patches 4-5 (Maxim): Fix the inconsistency of find_equal_scalars that
was possible if 32-bit spills were made.
Patches 6-11 (Maxim): Support the case when boundary checks are first
performed after the register was spilled to the stack.
Patches 12-13 (Maxim): Support narrowing fills.
Patches 14-15 (Eduard): Optimization for state pruning in stacksafe() to
mitigate the verification complexity regression.
veristat -e file,prog,states -f '!states_diff<50' -f '!states_pct<10' -f '!states_a<10' -f '!states_b<10' -C ...
* Without patch 14:
File Program States (A) States (B) States (DIFF)
-------------------- ------------ ---------- ---------- ----------------
bpf_xdp.o tail_lb_ipv6 3877 2936 -941 (-24.27%)
pyperf180.bpf.o on_event 8422 10456 +2034 (+24.15%)
pyperf600.bpf.o on_event 22259 37319 +15060 (+67.66%)
pyperf600_iter.bpf.o on_event 400 540 +140 (+35.00%)
strobemeta.bpf.o on_event 4702 13435 +8733 (+185.73%)
* With patch 14:
File Program States (A) States (B) States (DIFF)
-------------------- ------------ ---------- ---------- --------------
bpf_xdp.o tail_lb_ipv6 3877 2937 -940 (-24.25%)
pyperf600_iter.bpf.o on_event 400 500 +100 (+25.00%)
v2 changes:
Fixed comments in patch 1, moved endianness checks to header files in
patch 12 where possible, added Eduard's ACKs.
Eduard Zingerman (4):
bpf: make infinite loop detection in is_state_visited() exact
selftests/bpf: check if imprecise stack spills confuse infinite loop
detection
bpf: Optimize state pruning for spilled scalars
selftests/bpf: states pruning checks for scalar vs STACK_{MISC,ZERO}
Maxim Mikityanskiy (11):
selftests/bpf: Fix the u64_offset_to_skb_data test
bpf: Make bpf_for_each_spilled_reg consider narrow spills
selftests/bpf: Add a test case for 32-bit spill tracking
bpf: Add the assign_scalar_id_before_mov function
bpf: Add the get_reg_width function
bpf: Assign ID to scalars on spill
selftests/bpf: Test assigning ID to scalars on spill
bpf: Track spilled unbounded scalars
selftests/bpf: Test tracking spilled unbounded scalars
bpf: Preserve boundaries and track scalars on narrowing fill
selftests/bpf: Add test cases for narrowing fill
include/linux/bpf_verifier.h | 4 +-
include/linux/filter.h | 12 +
kernel/bpf/verifier.c | 155 ++++-
.../bpf/progs/verifier_direct_packet_access.c | 2 +-
.../selftests/bpf/progs/verifier_loops1.c | 24 +
.../selftests/bpf/progs/verifier_spill_fill.c | 533 +++++++++++++++++-
.../testing/selftests/bpf/verifier/precise.c | 6 +-
7 files changed, 685 insertions(+), 51 deletions(-)
--
2.43.0
next reply other threads:[~2024-01-08 20:52 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-01-08 20:51 Maxim Mikityanskiy [this message]
2024-01-08 20:51 ` [PATCH bpf-next v2 01/15] selftests/bpf: Fix the u64_offset_to_skb_data test Maxim Mikityanskiy
2024-01-08 20:51 ` [PATCH bpf-next v2 02/15] bpf: make infinite loop detection in is_state_visited() exact Maxim Mikityanskiy
2024-01-08 20:51 ` [PATCH bpf-next v2 03/15] selftests/bpf: check if imprecise stack spills confuse infinite loop detection Maxim Mikityanskiy
2024-01-08 20:51 ` [PATCH bpf-next v2 04/15] bpf: Make bpf_for_each_spilled_reg consider narrow spills Maxim Mikityanskiy
2024-01-08 20:51 ` [PATCH bpf-next v2 05/15] selftests/bpf: Add a test case for 32-bit spill tracking Maxim Mikityanskiy
2024-01-08 20:52 ` [PATCH bpf-next v2 06/15] bpf: Add the assign_scalar_id_before_mov function Maxim Mikityanskiy
2024-01-08 20:52 ` [PATCH bpf-next v2 07/15] bpf: Add the get_reg_width function Maxim Mikityanskiy
2024-01-08 20:52 ` [PATCH bpf-next v2 08/15] bpf: Assign ID to scalars on spill Maxim Mikityanskiy
2024-01-08 20:52 ` [PATCH bpf-next v2 09/15] selftests/bpf: Test assigning " Maxim Mikityanskiy
2024-01-09 23:34 ` Andrii Nakryiko
2024-01-08 20:52 ` [PATCH bpf-next v2 10/15] bpf: Track spilled unbounded scalars Maxim Mikityanskiy
2024-01-12 19:10 ` Alexei Starovoitov
2024-01-12 20:44 ` Maxim Mikityanskiy
2024-01-12 20:50 ` Alexei Starovoitov
2024-01-08 20:52 ` [PATCH bpf-next v2 11/15] selftests/bpf: Test tracking " Maxim Mikityanskiy
2024-01-08 20:52 ` [PATCH bpf-next v2 12/15] bpf: Preserve boundaries and track scalars on narrowing fill Maxim Mikityanskiy
2024-01-09 23:51 ` Andrii Nakryiko
2024-01-08 20:52 ` [PATCH bpf-next v2 13/15] selftests/bpf: Add test cases for " Maxim Mikityanskiy
2024-01-09 23:55 ` Andrii Nakryiko
2024-01-08 20:52 ` [PATCH bpf-next v2 14/15] bpf: Optimize state pruning for spilled scalars Maxim Mikityanskiy
2024-01-10 0:22 ` Andrii Nakryiko
2024-01-10 21:04 ` Eduard Zingerman
2024-01-10 21:52 ` Andrii Nakryiko
2024-01-08 20:52 ` [PATCH bpf-next v2 15/15] selftests/bpf: states pruning checks for scalar vs STACK_{MISC,ZERO} Maxim Mikityanskiy
2024-01-10 0:27 ` Andrii Nakryiko
2024-01-10 20:27 ` Eduard Zingerman
2024-01-12 3:00 ` [PATCH bpf-next v2 00/15] Improvements for tracking scalars in the BPF verifier patchwork-bot+netdevbpf
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=20240108205209.838365-1-maxtram95@gmail.com \
--to=maxtram95@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=davem@davemloft.net \
--cc=eddyz87@gmail.com \
--cc=haoluo@google.com \
--cc=hawk@kernel.org \
--cc=john.fastabend@gmail.com \
--cc=jolsa@kernel.org \
--cc=kpsingh@kernel.org \
--cc=kuba@kernel.org \
--cc=linux-kselftest@vger.kernel.org \
--cc=martin.lau@linux.dev \
--cc=maxim@isovalent.com \
--cc=mykolal@fb.com \
--cc=netdev@vger.kernel.org \
--cc=sdf@google.com \
--cc=shuah@kernel.org \
--cc=shung-hsi.yu@suse.com \
--cc=song@kernel.org \
--cc=yonghong.song@linux.dev \
/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).