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.
