[RFC PATCH v3 bpf-next 0/5] 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, the code handling subprogs can
 in various places be made simpler, more explicit, and more efficient (i.e.
 better asymptotic complexity).  This also lays the ground for possible
 future work in which an extension of the check_subprogs() code to cover
 basic blocks could replace check_cfg(), which currently largely duplicates
 the insn-walking part.

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.
* Subprog numbers and corresponding subprog_info index are now 0-based;
  subprog 0 is the main()-function of the program, starting at insn 0.
* 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 #5 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.

Testing done on this version:
* test_verifier
* test_progs (mostly)
* test_kmod.sh
* tested whether processed-insn numbers (hence pruning) change.
  (Couldn't test with programs containing pseudo-calls (e.g.
  test_xdp_noinline.o), because iproute2 rejects them in its bpf lib.)
  I tested with some Cilium object files, and found that in some cases
  the numbers *do* change as compared to bpf-next.
  - bpf_lxc_opt_-DDROP_ALL.o   26713 -> 17753
  - bpf_lxc_opt_-DUNKNOWN.o    36604 -> 23324
  - bpf_netdev.o               10003 -> 9984
  I'm not yet sure why this is, especially as these object files do not
  contain pseudo-calls.
  One possibility I see: in BPF_MOV64_REG handling, we copy the register
  state, which includes the parent pointer.  But that shouldn't matter,
  because we just read-marked the src reg (via check_reg_arg), and we
  write-mark the dst reg immediately after.  Same goes for other places
  we copy reg states around (e.g. stack reads and writes).
  So I don't quite see how this can affect pruning; but _something_ did.

Changes from v2->v3:
* Added RFC tags back since bpf-next is closed right now.
* Split up first patch into three parts to avoid doing too many things at
  once.
* Restore check_subprogs() as a separate pass rather than doing the work
  on-the-fly in do_check().
* Removed changes in jit_subprogs() handling which were there to support
  non-contiguous subprogs, since that's no longer needed.

Changes from v1->v2:
* No longer allows non-contiguous subprogs.
* No longer allows LD_ABS|IND and pseudo-calls in the same prog.

Edward Cree (5):
  bpf/verifier: store subprog info in struct bpf_subprog_info
  bpf/verifier: rewrite subprog boundary detection
  bpf/verifier: update selftests
  bpf/verifier: use call graph to efficiently check max stack depth
  bpf/verifier: per-register parent pointers

 include/linux/bpf_verifier.h                |  21 +-
 kernel/bpf/verifier.c                       | 617 ++++++++++++++--------------
 tools/testing/selftests/bpf/test_verifier.c |  51 ++-
 3 files changed, 354 insertions(+), 335 deletions(-)