From mboxrd@z Thu Jan 1 00:00:00 1970 From: Edward Cree Subject: Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call simplifications Date: Thu, 5 Apr 2018 09:49:40 +0100 Message-ID: <0c879399-ec66-938f-b49e-58dffb6a705e@solarflare.com> References: <20180403010802.jkqffxw4m75oioj7@ast-mbp> <554dc916-2eed-dabc-1776-eca6d8bf019b@solarflare.com> <20180403233718.rrzh6ds67hraxhax@ast-mbp> <3484e40e-57a7-e7c6-520d-b9ca795616e2@solarflare.com> <20180405052820.eurpes52ilhofbg3@ast-mbp.dhcp.thefacebook.com> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit Cc: Daniel Borkmann , To: Alexei Starovoitov Return-path: Received: from dispatch1-us1.ppe-hosted.com ([148.163.129.52]:57474 "EHLO dispatch1-us1.ppe-hosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751097AbeDEItq (ORCPT ); Thu, 5 Apr 2018 04:49:46 -0400 In-Reply-To: <20180405052820.eurpes52ilhofbg3@ast-mbp.dhcp.thefacebook.com> Content-Language: en-GB Sender: netdev-owner@vger.kernel.org List-ID: On 05/04/18 06:28, Alexei Starovoitov wrote: > On Thu, Apr 05, 2018 at 12:58:46AM +0100, Edward Cree wrote: >> On 04/04/18 00:37, Alexei Starovoitov wrote: >>> hmm. that doesn't fail for me and any other bots didn't complain. >>> Are you sure you're running the latest kernel and tests? >> Ah, test_progs isn't actually rebuilding because __NR_bpf is undeclared; >>  something must be going wrong with header files. >> Never mind. >> >>> hmm. what's wrong with bsearch? It's trivial and fast. >> bsearch is O(log n), and the sort() call on the subprog_starts (which happens >>  every time add_subprog() is called) is O(n log n). >> Whereas reading aux->subprogno is O(1). >> As far as I'm concerned, that's a sign that the latter data structure is the >>  appropriate one. > only if it can be done as separate _first_ pass before cfg. As I think I already said, I'm working on a next version of the patch that  does just that. > No. It's worse. Your proposed approach to bounded loops completely > relying on 'explore all paths' whereas John's does not. > Can 'explore all paths' work with 1M bpf insns? No. > Whereas an approach that builds dom graph, detects natural loops > and loop invariants - can. ... IF it's possible at all, which I'm still doubtful about. > This sounds like arbitrary assumptions what this new approach would do. > Instead of rejecting it outright try to solve this very hard problem. I'm not rejecting it outright; I'm just saying, be prepared for the possibility  that it can't be solved, and try to leave a line of retreat / have a plan B in  the case that it proves to be subject to a no-free-lunch theorem.  Because my  intuition is that an entropy argument may require all algos to have the same  superexponential worst-case running time as 'explore all paths' does. > Before this discussion gets carried away too far let's get back to this patch set. > Having seen all arguments I still think that only patch 3 is worth pursuing further. I think the next version of the patch series (coming real soon now) answers at  least most of your objections (and indeed the above debate isn't relevant to it).