From: John Fastabend <john.fastabend@gmail.com>
To: Alexei Starovoitov <ast@kernel.org>, davem@davemloft.net
Cc: daniel@iogearbox.net, netdev@vger.kernel.org,
bpf@vger.kernel.org, kernel-team@fb.com
Subject: RE: [PATCH v3 bpf-next 1/9] bpf: track spill/fill of constants
Date: Wed, 19 Jun 2019 17:24:32 -0700 [thread overview]
Message-ID: <5d0ad24027106_8822adea29a05b47c@john-XPS-13-9370.notmuch> (raw)
In-Reply-To: <20190615191225.2409862-2-ast@kernel.org>
Alexei Starovoitov wrote:
> Compilers often spill induction variables into the stack,
> hence it is necessary for the verifier to track scalar values
> of the registers through stack slots.
>
> Also few bpf programs were incorrectly rejected in the past,
> since the verifier was not able to track such constants while
> they were used to compute offsets into packet headers.
>
> Tracking constants through the stack significantly decreases
> the chances of state pruning, since two different constants
> are considered to be different by state equivalency.
> End result that cilium tests suffer serious degradation in the number
> of states processed and corresponding verification time increase.
>
> before after
> bpf_lb-DLB_L3.o 1838 6441
> bpf_lb-DLB_L4.o 3218 5908
> bpf_lb-DUNKNOWN.o 1064 1064
> bpf_lxc-DDROP_ALL.o 26935 93790
> bpf_lxc-DUNKNOWN.o 34439 123886
> bpf_netdev.o 9721 31413
> bpf_overlay.o 6184 18561
> bpf_lxc_jit.o 39389 359445
>
> After further debugging turned out that cillium progs are
> getting hurt by clang due to the same constant tracking issue.
> Newer clang generates better code by spilling less to the stack.
> Instead it keeps more constants in the registers which
> hurts state pruning since the verifier already tracks constants
> in the registers:
> old clang new clang
> (no spill/fill tracking introduced by this patch)
> bpf_lb-DLB_L3.o 1838 1923
> bpf_lb-DLB_L4.o 3218 3077
> bpf_lb-DUNKNOWN.o 1064 1062
> bpf_lxc-DDROP_ALL.o 26935 166729
> bpf_lxc-DUNKNOWN.o 34439 174607
^^^^^^^^^^^^^^
Any idea what happened here? Going from 34439 -> 174607 on the new clang?
> bpf_netdev.o 9721 8407
> bpf_overlay.o 6184 5420
> bpf_lcx_jit.o 39389 39389
>
> The final table is depressing:
> old clang old clang new clang new clang
> const spill/fill const spill/fill
> bpf_lb-DLB_L3.o 1838 6441 1923 8128
> bpf_lb-DLB_L4.o 3218 5908 3077 6707
> bpf_lb-DUNKNOWN.o 1064 1064 1062 1062
> bpf_lxc-DDROP_ALL.o 26935 93790 166729 380712
> bpf_lxc-DUNKNOWN.o 34439 123886 174607 440652
> bpf_netdev.o 9721 31413 8407 31904
> bpf_overlay.o 6184 18561 5420 23569
> bpf_lxc_jit.o 39389 359445 39389 359445
>
> Tracking constants in the registers hurts state pruning already.
> Adding tracking of constants through stack hurts pruning even more.
> The later patch address this general constant tracking issue
> with coarse/precise logic.
>
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> Acked-by: Andrii Nakryiko <andriin@fb.com>
> ---
> kernel/bpf/verifier.c | 90 +++++++++++++++++++++++++++++++------------
> 1 file changed, 65 insertions(+), 25 deletions(-)
I know these are already in bpf-next sorry it took me awhile to get
time to review, but looks good to me. Thanks! We had something similar
in the earlier loop test branch from last year.
next prev parent reply other threads:[~2019-06-20 0:24 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-06-15 19:12 [PATCH v3 bpf-next 0/9] bpf: bounded loops and other features Alexei Starovoitov
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 [this message]
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=5d0ad24027106_8822adea29a05b47c@john-XPS-13-9370.notmuch \
--to=john.fastabend@gmail.com \
--cc=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).