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