From mboxrd@z Thu Jan 1 00:00:00 1970 From: Edward Cree Subject: Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call simplifications Date: Thu, 29 Mar 2018 23:50:05 +0100 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Cc: To: Alexei Starovoitov , Daniel Borkmann Return-path: Received: from dispatch1-us1.ppe-hosted.com ([148.163.129.52]:34170 "EHLO dispatch1-us1.ppe-hosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750735AbeC2Wuf (ORCPT ); Thu, 29 Mar 2018 18:50:35 -0400 In-Reply-To: Content-Language: en-GB Sender: netdev-owner@vger.kernel.org List-ID: On 29/03/18 23:44, Edward Cree wrote: > By storing subprog boundaries as a subprogno mark on each insn, rather than > a start (and implicit end) for each subprog, we collect a number of gains: > * More efficient determination of which subprog contains a given insn, and > thus of find_subprog (which subprog begins at a given insn). > * Number of verifier "full recursive walk" passes is reduced, since most of > the work is done in the main insn walk (do_check()). Leftover work in > other passes is mostly linear scans (O(insn_cnt)) or, in the case of > check_max_stack_depth(), a topological sort (O(subprog_cnt)). > > Some other changes were also included to support this: > * Per-subprog info is stored in env->subprog_info, an array of structs, > rather than several arrays with a common index. > * Call graph is now stored in the new bpf_subprog_info struct; used here > for check_max_stack_depth() but may have other uses too. > > Along with this, patch #3 puts parent pointers (used by liveness analysis) > in the registers instead of the func_state or verifier_state, so that we > don't need skip_callee() machinery. This also does the right thing for > stack slots, so they don't need their own special handling for liveness > marking either. Whoops, forgot to add: Changes from v1: * No longer allows non-contiguous subprogs. * No longer allows LD_ABS|IND and pseudo-calls in the same prog. > Edward Cree (3): > bpf/verifier: validate func_calls by marking at do_check() time > bpf/verifier: update selftests > bpf/verifier: per-register parent pointers > > include/linux/bpf_verifier.h | 32 +- > kernel/bpf/verifier.c | 631 +++++++++++++--------------- > tools/testing/selftests/bpf/test_verifier.c | 51 ++- > 3 files changed, 344 insertions(+), 370 deletions(-) >