Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932105AbdHUUYo (ORCPT ); Mon, 21 Aug 2017 16:24:44 -0400 Received: from dispatch1-us1.ppe-hosted.com ([67.231.154.164]:58014 "EHLO dispatch1-us1.ppe-hosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754248AbdHUUYm (ORCPT ); Mon, 21 Aug 2017 16:24:42 -0400 Subject: Re: [PATCH v3 net-next] bpf/verifier: track liveness for pruning To: Alexei Starovoitov , , Alexei Starovoitov , Daniel Borkmann References: <89ff34f7-84ee-0e0a-3766-5b4d046189bf@fb.com> CC: , , iovisor-dev From: Edward Cree Message-ID: Date: Mon, 21 Aug 2017 21:24:24 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.1.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-Originating-IP: [10.17.20.45] X-ClientProxiedBy: ocex03.SolarFlarecom.com (10.20.40.36) To ukex01.SolarFlarecom.com (10.17.10.4) X-TM-AS-Product-Ver: SMEX-11.0.0.1191-8.100.1062-23272.003 X-TM-AS-Result: No--4.166500-0.000000-31 X-TM-AS-User-Approved-Sender: Yes X-TM-AS-User-Blocked-Sender: No X-MDID: 1503347081-f+-x0OP63dhr Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1264 Lines: 25 On 18/08/17 15:16, Edward Cree wrote: > On 18/08/17 04:21, Alexei Starovoitov wrote: >> It seems you're trying to sort-of do per-fake-basic block liveness >> analysis, but our state_list_marks are not correct if we go with >> canonical basic block definition, since we mark the jump insn and >> not insn after the branch and not every basic block boundary is >> properly detected. > I think the reason this works is that jump insns can't do writes. > [snip] > the sl->state will never have any write marks and it'll all just work. > But I should really test that! I tested this, and found that, no, sl->state can have write marks, and the algorithm will get the wrong answer in that case. So I've got a patch to make the first iteration ignore write marks, as part of a series which I will post shortly. When I do so, please re-do your tests with adding state_list_marks in strange and exciting places; it should work wherever you put them. Like you say, it "magically doesn't depend on proper basic block boundaries", and that's because really pruning is just a kind of checkpointing that just happens to be most effective when done just after a jump (pop_stack). Can I have a SOB for your "grr" test program, so I can include it in the series? -Ed