From mboxrd@z Thu Jan  1 00:00:00 1970
From: Edward Cree <ecree@solarflare.com>
Subject: Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call
 simplifications
Date: Thu, 5 Apr 2018 17:29:40 +0100
Message-ID: <9ed026cd-cf98-f7fc-e7d6-26117b620204@solarflare.com>
References: <d13f6b60-3632-3e4d-111a-2edb4198b473@solarflare.com>
 <20180403010802.jkqffxw4m75oioj7@ast-mbp>
 <2ff89131-c6ea-5ddf-156c-c6f6e455fbdd@netronome.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
Cc: Daniel Borkmann <daniel@iogearbox.net>, <netdev@vger.kernel.org>
To: Jiong Wang <jiong.wang@netronome.com>,
        Alexei Starovoitov <alexei.starovoitov@gmail.com>
Return-path: <netdev-owner@vger.kernel.org>
Received: from dispatch1-us1.ppe-hosted.com ([148.163.129.52]:49604 "EHLO
        dispatch1-us1.ppe-hosted.com" rhost-flags-OK-OK-OK-OK)
        by vger.kernel.org with ESMTP id S1751353AbeDEQ3p (ORCPT
        <rfc822;netdev@vger.kernel.org>); Thu, 5 Apr 2018 12:29:45 -0400
In-Reply-To: <2ff89131-c6ea-5ddf-156c-c6f6e455fbdd@netronome.com>
Content-Language: en-GB
Sender: netdev-owner@vger.kernel.org
List-ID: <netdev.vger.kernel.org>

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