From: Jakub Kicinski <jakub.kicinski@netronome•com>
To: Alexei Starovoitov <ast@kernel•org>
Cc: <davem@davemloft•net>, <daniel@iogearbox•net>, <jannh@google•com>,
<netdev@vger•kernel.org>, <bpf@vger•kernel.org>,
<kernel-team@fb•com>
Subject: Re: [PATCH bpf-next 2/7] bpf: improve verification speed by droping states
Date: Fri, 29 Mar 2019 20:12:39 -0700 [thread overview]
Message-ID: <20190329201239.7736739e@cakuba.netronome.com> (raw)
In-Reply-To: <20190330001612.2354959-3-ast@kernel.org>
On Fri, 29 Mar 2019 17:16:07 -0700, Alexei Starovoitov wrote:
> Branch instructions, branch targets and calls in a bpf program are
> the places where the verifier remembers states that led to successful
> verification of the program.
> These states are used to prune brute force program analysis.
> For unprivileged programs there is a limit of 64 states per such
> 'branching' instructions (maximum length is tracked by max_states_per_insn
> counter introduced in the previous patch).
> Simply reducing this threshold to 32 or lower increases insn_processed
> metric to the point that small valid programs get rejected.
> For root programs there is no limit and cilium programs can have
> max_states_per_insn to be 100 or higher.
> Walking 100+ states multiplied by number of 'branching' insns during
> verification consumes significant amount of cpu time.
> Turned out simple LRU-like mechanism can be used to remove states
> that unlikely will be helpful in future search pruning.
> This patch introduces hit_cnt and miss_cnt counters:
> hit_cnt - this many times this state successfully pruned the search
> miss_cnt - this many times this state was not equivalent to other states
> (and that other states were added to state list)
>
> The heuristic introduced in this patch is:
> if (sl->miss_cnt > sl->hit_cnt * 3 + 3)
> /* drop this state from future considerations */
>
> Higher numbers increase max_states_per_insn (allow more states to be
> considered for pruning) and slow verification speed, but do not meaningfully
> reduce insn_processed metric.
> Lower numbers drop too many states and insn_processed increases too much.
> Many different formulas were considered.
> This one is simple and works well enough in practice.
> (the analysis was done on selftests/progs/* and on cilium programs)
>
> The end result is this heuristic improves verification speed by 10 times.
> Large synthetic programs that used to take a second more now take
> 1/10 of a second.
> In cases where max_states_per_insn used to be 100 or more, now it's ~10.
>
> There is a slight increase in insn_processed for cilium progs:
> before after
> bpf_lb-DLB_L3.o 1831 1838
> bpf_lb-DLB_L4.o 3029 3218
> bpf_lb-DUNKNOWN.o 1064 1064
> bpf_lxc-DDROP_ALL.o 26309 26935
> bpf_lxc-DUNKNOWN.o 33517 34439
> bpf_netdev.o 9713 9721
> bpf_overlay.o 6184 6184
> bpf_lcx_jit.o 37335 39389
> And 2-3 times improvement in the verification speed.
>
> Signed-off-by: Alexei Starovoitov <ast@kernel•org>
Reviewed-by: Jakub Kicinski <jakub.kicinski@netronome•com>
> @@ -6182,8 +6185,35 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
> return err;
> return 1;
> }
> - sl = sl->next;
> states_cnt++;
> + sl->miss_cnt++;
> + /* heuristic to determine whether this state is beneficial
> + * to keep checking from state equivalence point of view.
> + * Higher numbers increase max_states_per_insn and verification time,
> + * but do not meaningfully decrease insn_processed.
> + */
> + if (sl->miss_cnt > sl->hit_cnt * 3 + 3) {
> + /* the state is unlikely to be useful. Remove it to
> + * speed up verification
> + */
> + *pprev = sl->next;
> + if (sl->state.frame[0]->regs[0].live & REG_LIVE_DONE) {
> + free_verifier_state(&sl->state, false);
> + kfree(sl);
> + env->peak_states--;
nit: is peak_states always equal to number of states when verifier
exits?
> + } else {
> + /* cannot free this state, since parentage chain may
> + * walk it later. Add it for free_list instead to
> + * be freed at the end of verification
> + */
> + sl->next = env->free_list;
> + env->free_list = sl;
> + }
> + sl = *pprev;
> + continue;
> + }
> + pprev = &sl->next;
> + sl = *pprev;
> }
>
> if (env->max_states_per_insn < states_cnt)
next prev parent reply other threads:[~2019-03-30 3:12 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-03-30 0:16 [PATCH bpf-next 0/7] bpf: improve verifier scalability Alexei Starovoitov
2019-03-30 0:16 ` [PATCH bpf-next 1/7] bpf: add verifier stats and log_level bit 2 Alexei Starovoitov
2019-03-30 0:16 ` [PATCH bpf-next 2/7] bpf: improve verification speed by droping states Alexei Starovoitov
2019-03-30 3:12 ` Jakub Kicinski [this message]
2019-03-30 3:29 ` Alexei Starovoitov
2019-03-30 0:16 ` [PATCH bpf-next 3/7] bpf: improve verification speed by not remarking live_read Alexei Starovoitov
2019-03-30 3:12 ` Jakub Kicinski
2019-04-01 15:38 ` Edward Cree
2019-03-30 0:16 ` [PATCH bpf-next 4/7] bpf: increase complexity limit and maximum program size Alexei Starovoitov
2019-03-30 0:16 ` [PATCH bpf-next 5/7] bpf: increase verifier log limit Alexei Starovoitov
2019-03-30 3:16 ` Jakub Kicinski
2019-03-30 0:16 ` [PATCH bpf-next 6/7] libbpf: teach libbpf about log_level bit 2 Alexei Starovoitov
2019-03-30 0:16 ` [PATCH bpf-next 7/7] selftests/bpf: add few verifier scale tests Alexei Starovoitov
2019-04-01 14:17 ` Daniel Borkmann
2019-04-01 16:35 ` Daniel Borkmann
2019-04-02 2:08 ` Alexei Starovoitov
2019-04-02 14:13 ` Daniel Borkmann
2019-04-02 18:12 ` Alexei Starovoitov
2019-03-30 3:18 ` [PATCH bpf-next 0/7] bpf: improve verifier scalability Jakub Kicinski
2019-03-30 3:35 ` 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=20190329201239.7736739e@cakuba.netronome.com \
--to=jakub.kicinski@netronome$(echo .)com \
--cc=ast@kernel$(echo .)org \
--cc=bpf@vger$(echo .)kernel.org \
--cc=daniel@iogearbox$(echo .)net \
--cc=davem@davemloft$(echo .)net \
--cc=jannh@google$(echo .)com \
--cc=kernel-team@fb$(echo .)com \
--cc=netdev@vger$(echo .)kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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