From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jiong Wang Subject: Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call simplifications Date: Thu, 5 Apr 2018 16:50:03 +0100 Message-ID: <2ff89131-c6ea-5ddf-156c-c6f6e455fbdd@netronome.com> References: <20180403010802.jkqffxw4m75oioj7@ast-mbp> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Cc: Daniel Borkmann , netdev@vger.kernel.org To: Alexei Starovoitov , Edward Cree Return-path: Received: from mail-wm0-f54.google.com ([74.125.82.54]:34121 "EHLO mail-wm0-f54.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751696AbeDEPuJ (ORCPT ); Thu, 5 Apr 2018 11:50:09 -0400 Received: by mail-wm0-f54.google.com with SMTP id w2so3886991wmw.1 for ; Thu, 05 Apr 2018 08:50:09 -0700 (PDT) In-Reply-To: <20180403010802.jkqffxw4m75oioj7@ast-mbp> Content-Language: en-GB Sender: netdev-owner@vger.kernel.org List-ID: 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