Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753923AbdHUSg5 (ORCPT ); Mon, 21 Aug 2017 14:36:57 -0400 Received: from dispatch1-us1.ppe-hosted.com ([67.231.154.164]:46479 "EHLO dispatch1-us1.ppe-hosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753596AbdHUSg4 (ORCPT ); Mon, 21 Aug 2017 14:36:56 -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> <5d4e12aa-6861-a176-a8cf-a766bbca0a7a@fb.com> CC: , , iovisor-dev From: Edward Cree Message-ID: Date: Mon, 21 Aug 2017 19:36:44 +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: <5d4e12aa-6861-a176-a8cf-a766bbca0a7a@fb.com> 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--8.312100-0.000000-31 X-TM-AS-User-Approved-Sender: Yes X-TM-AS-User-Blocked-Sender: No X-MDID: 1503340614-A2zAuAXNJTpG Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1925 Lines: 42 On 19/08/17 00:37, Alexei Starovoitov wrote: > that '14: safe' above is not correct. > > Disabling liveness as: > @@ -3282,7 +3288,7 @@ static bool regsafe(struct bpf_reg_state *rold, > struct bpf_reg_state *rcur, > bool varlen_map_access, struct idpair *idmap) > { > - if (!(rold->live & REG_LIVE_READ)) > + if (0 && !(rold->live & REG_LIVE_READ)) > > makes the test work properly and proper verifier output is: > from 9 to 11: R0=map_value(id=0,off=0,ks=8,vs=48,imm=0) R1=inv(id=0,smax_value=10) R2=inv11 R10=fp0 > 11: (64) (u32) r1 <<= (u32) 2 > 12: (0f) r0 += r1 > 13: (05) goto pc+0 > 14: (7a) *(u64 *)(r0 +0) = 4 > > R0=map_value(id=0,off=0,ks=8,vs=48,umax_value=17179869180,var_off=(0x0; 0x3fffffffc)) R1=inv(id=0,umax_value=17179869180,var_off=(0x0; 0x3fffffffc)) R2=inv11 R10=fp0 > R0 unbounded memory access, make sure to bounds check any array access into a map > > I don't yet understand the underlying reason. R0 should have been > marked as LIVE_READ by ST_MEM... > Please help debug it further. > Having added a bunch of debugging, I found out that indeed R0 _had_ been marked as LIVE_READ. The problem was that env->varlen_map_value_access wasn't set, because the access was at a constant offset (imm=0), but then when we compare register states we just say "oh yeah, it's a map_value, we don't need to look at the var_off". This probably results from my unifying PTR_TO_MAP_VALUE with PTR_TO_MAP_VALUE_ADJ; before that the old and new R0 would have different reg->type so wouldn't match. I'm tempted to just rip out env->varlen_map_value_access and always check the whole thing, because honestly I don't know what it was meant to do originally or how it can ever do any useful pruning. While drastic, it does cause your test case to pass. I'm not quite sure why your test passed when you disabled liveness, though; that I can't explain. -Ed