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 passes is reduced, since most of the work is done in the main insn walk (do_check()). * Subprogs no longer have to be contiguous; so long as they don't overlap and there are no unreachable insns, verifier is happy. (This does require a small amount of care at jit_subprogs() time to fix up jump offsets, so we could instead disallow this if people prefer.)
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. * LD_ABS and LD_IND were previously disallowed in programs that also contain subprog calls. Now they are only disallowed in callees, i.e. main() can always use them even if it also uses subprog calls. AFAICT this is safe (main()'s r1 arg is still known to be ctx, so prologue can do its stuff). But again it can be disallowed if necessary. Most tests in test_verifier pass (a few had to be changed to expect different failure messages), but there are a couple I wasn't quite sure what to do with - see comment on patch #2. Edward Cree (2): bpf/verifier: validate func_calls by marking at do_check() time bpf/verifier: update selftests include/linux/bpf_verifier.h | 24 +- kernel/bpf/verifier.c | 425 +++++++++++++++------------- tools/testing/selftests/bpf/test_verifier.c | 46 +-- 3 files changed, 271 insertions(+), 224 deletions(-)
