[RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications

Edward Cree
2018-04-06T17:12:13Z

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