From mboxrd@z Thu Jan  1 00:00:00 1970
From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Subject: Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call
 simplifications
Date: Thu, 5 Apr 2018 18:20:15 -0700
Message-ID: <20180406012013.pcvoz2qqlgoxu7lh@ast-mbp.dhcp.thefacebook.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=us-ascii
Cc: Edward Cree <ecree@solarflare.com>,
        Daniel Borkmann <daniel@iogearbox.net>, netdev@vger.kernel.org
To: Jiong Wang <jiong.wang@netronome.com>
Return-path: <netdev-owner@vger.kernel.org>
Received: from mail-pl0-f65.google.com ([209.85.160.65]:37187 "EHLO
        mail-pl0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
        with ESMTP id S1751312AbeDFBUR (ORCPT
        <rfc822;netdev@vger.kernel.org>); Thu, 5 Apr 2018 21:20:17 -0400
Received: by mail-pl0-f65.google.com with SMTP id v5-v6so19674482plo.4
        for <netdev@vger.kernel.org>; Thu, 05 Apr 2018 18:20:17 -0700 (PDT)
Content-Disposition: inline
In-Reply-To: <2ff89131-c6ea-5ddf-156c-c6f6e455fbdd@netronome.com>
Sender: netdev-owner@vger.kernel.org
List-ID: <netdev.vger.kernel.org>

On Thu, Apr 05, 2018 at 04:50:03PM +0100, 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.
> 
> 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 don't think that will work.
Functions are independent from CFG.
With bpf libraries we will have disjoint functions sitting in the kernel
and check_cfg would need to be done separately from function boundaries.