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(-) >
