Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call simplifications

[Edward Cree <ecree@solarflare.com>]

On 05/04/18 16:50, Jiong Wang wrote:
> On 03/04/2018 02:08, Alexei Starovoitov wrote:
>> Combining subprog pass with do_check is going into opposite direction
>> of this long term work. Divide and conquer. Combining more things into
>> do_check is the opposite of this programming principle.
>
> Agree. And for the redundant insn traversal issue in check_subprogs that
> Edward trying to fix, I am thinking we could do it by utilizing the
> existing DFS traversal in check_cfg.
>
> The current DFS probably could be improved into an generic instruction
> information collection pass.
<snip>
> And if we want to build basic-block later, we could just call a new add_bb
> (similar as add_subprog) for jump targets etc. (some of those places are
> actually STATE_LIST_MARK_JMPTARGET if we separate STATE_LIST_MARK as
> STATE_LIST_MARK_JMPTARGET and STATE_LIST_MARK_HEURISTIC).
>
> Regards,
> Jiong
>
This is broadly similar to my medium-term plan, except that I would use
 the Kahn's-algorithm style tsort rather than the depth-first tsort
 algorithm used by current check_cfg.
* chop up prog into functions and bbs, incidentally placing S_L_Ms
* create control flow graph similar to my function call graph
* tsort it to detect loops, similar to how my check_max_stack_depth()
  implementation detects recursion.

-Ed