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

[Jiong Wang <jiong.wang@netronome.com>]

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.