From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jiong Wang Subject: Re: [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Date: Tue, 10 Apr 2018 13:54:18 +0100 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Cc: netdev@vger.kernel.org To: Edward Cree , Alexei Starovoitov , Daniel Borkmann Return-path: Received: from mail-wm0-f45.google.com ([74.125.82.45]:39903 "EHLO mail-wm0-f45.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752940AbeDJMyW (ORCPT ); Tue, 10 Apr 2018 08:54:22 -0400 Received: by mail-wm0-f45.google.com with SMTP id f125so23134293wme.4 for ; Tue, 10 Apr 2018 05:54:22 -0700 (PDT) In-Reply-To: Content-Language: en-GB Sender: netdev-owner@vger.kernel.org List-ID: On 06/04/2018 18:11, Edward Cree wrote: > By storing subprog boundaries as a subprogno mark on each insn, rather than > a start (and implicit end) for each subprog, the code handling subprogs can > in various places be made simpler, more explicit, and more efficient (i.e. > better asymptotic complexity). IMHO, the subprog number might be much smaller than insn number, so just keeping sorted subprog information in env->subprog_info and do bsearch looks reasonable to me. While the new added "subprogno" field is only used round find_subprog, so I feel it is a little bit heavy to allocate a delicated field that wouldn't be used broadly for each instruction. > This also lays the ground for possible > future work in which an extension of the check_subprogs() code to cover > basic blocks could replace check_cfg(), which currently largely duplicates > the insn-walking part. I was thinking to remove the insn-walk duplication in the other way by center them in the DFS insn-walk in check_cfg, as we can't remove that one before we migrate to other loop detection method. This approach is questionable though. > Some other changes were also included to support this: > * Per-subprog info is stored in env->subprog_info, an array of structs, > rather than several arrays with a common index. > * Subprog numbers and corresponding subprog_info index are now 0-based; > subprog 0 is the main()-function of the program, starting at insn 0. > * Call graph is now stored in the new bpf_subprog_info struct; used here > for check_max_stack_depth() but may have other uses too. Ack above changes which center all subprog related info into env->subprog_info and the new addition of callee field.