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.

Reply via email to