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

Jiong Wang
2018-04-10T12:54:22Z

On 06/04/2018 18:11, Edward Cree wrote:
> 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).

IMHO, the subprog number might be much smaller than insn number, so just
keeping sorted subprog information in env->subprog_info and do bsearch
looks reasonable to me.

While the new added "subprogno" field is only used round find_subprog, so
I feel it is a little bit heavy to allocate a delicated field that wouldn't
be used broadly for each instruction.

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

I was thinking to remove the insn-walk duplication in the other way by
center them in the DFS insn-walk in check_cfg, as we can't remove that one
before we migrate to other loop detection method. This approach is
questionable though.

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

Ack above changes which center all subprog related info into
env->subprog_info and the new addition of callee field.