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

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

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.

This won't make the existing DFS complexer as it only does information
collection as a side job during traversal. These collected information
then could be used to build any other information to be consumed later,
for example subprog, basic blocks etc.

For the redundant insn traversal issue during subprog detection, the
Like how we mark STATE_LIST_MARK in DFS, we could just call add_subprog
for BPF_PSEUDO_CALL insn during DFS.

i.e we change the code logic of check_cfg into:

check_cfg
{
   * DFS traversal:
     - detect back-edge.
     - collect STATE_LIST_MARK.
     - collect subprog destination.

   * check all insns are reachable.
   * check_subprogs (insn traversal removed).
}

I prototyped a patch for above change, the change looks to me is easier to
review. There are 8 regressions on selftests however after this change due
to check_subprogs moved after some checks in DFS that some errors detected
before the expected errors, need to be cleaned up.

Does this direction sound good?

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