[PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call simplifications

[Edward Cree <ecree@solarflare.com>]

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