Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754367AbdHUVTV (ORCPT ); Mon, 21 Aug 2017 17:19:21 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:56935 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754198AbdHUVTS (ORCPT ); Mon, 21 Aug 2017 17:19:18 -0400 Subject: Re: [PATCH v3 net-next] bpf/verifier: track liveness for pruning To: Edward Cree , , Alexei Starovoitov , Daniel Borkmann References: <89ff34f7-84ee-0e0a-3766-5b4d046189bf@fb.com> CC: , , iovisor-dev From: Alexei Starovoitov Message-ID: Date: Mon, 21 Aug 2017 14:18:45 -0700 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 7bit X-Originating-IP: [2620:10d:c090:200::6:8186] X-ClientProxiedBy: DM5PR19CA0028.namprd19.prod.outlook.com (2603:10b6:3:9a::14) To CO1PR15MB0967.namprd15.prod.outlook.com (2a01:111:e400:7b64::25) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: a0374f32-e393-4658-52b8-08d4e8da3812 X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:(300000500095)(300135000095)(300000501095)(300135300095)(22001)(300000502095)(300135100095)(2017030254152)(300000503095)(300135400095)(201703131423075)(201703031133081)(201702281549075)(300000504095)(300135200095)(300000505095)(300135600095)(300000506095)(300135500095);SRVR:CO1PR15MB0967; X-Microsoft-Exchange-Diagnostics: 1;CO1PR15MB0967;3:E2NHN2crTUMjLm6mOMpq4ORfpyOZFX4OarHjzRDKGKHmgfPBt56ziZ3i+Sn8aRUV4jlTjqgZyiftIkx3ZqUAd1GBt+w/U2RkDomzJOq+4NcFd35isVJLTYVbAfW0EKyM9SamGk8C3rfF5iy+Ny8E5N0i05VMhLpiGp9xbbOOvGrSM6PK8YCXMO9O/QR+M1reAmYTSgbP9qo5ir/W/v/dQ8sWkzvAjYmXdYOJ6NtHRf/u2XffLZf0hW2QBHdLzXQP;25:TaTEEZd7m4hlXw/uMlVzQZ9nyIOz/GUIeoowgjACSKzy1Tx4xnyHxnHlWfVEME0FKPIMkdEcT6gFvIGWffTpBdDd/s9QJXECuxsbjCrbJZ4o/2YAFyhYFtYvWKg/RUAFPWpqBagfDUM/SPO+VNEE1D/3fjJxdCF6SGlqCJmpJsDyafDUQs4XdIOB4gFCGGgpd1isNsLLwiMsxwVKXJqobSBsLm+fKQz2BJuif1Jl0ct9KYZONVqODMHrmL7upvaL/ZihN8swAepr7RYePQ7JkatN/h7wWKxveqg37e6gyKcfG8NZykLr9yjwMEy5XjuTaLAcURQsYc7gyG2Lq7FZIw==;31:ZKSmkPWc48vzmHs38yVlz73rsTPPEPIDjgqN7fHTyVh2Wa0yvWeR6C3kgj3BX6I+b8fUbJmtG8Kw6NLvpKI0WeMzRmQVoE0QY3/9k4mAS1MIvcAyOS5xCZ707CSFF6jOcmY386kh6QvTnNrjape+SwfDIyIcfXnAs49Uf8EZhjvQjsEWTHs1fhv2MmaTerz90FpWXvqGAZlc7rmqHDt60AeNmF96xDRB542jTkyC5sQ= X-MS-TrafficTypeDiagnostic: CO1PR15MB0967: X-Microsoft-Exchange-Diagnostics: 1;CO1PR15MB0967;20:AZSp5/rt/AHjLVLT+UgmJTP+BgFo96mX6MyPunYZF7JbLyZSvrWIncbm7HO9KfjE4z5ohHh9nIFXqevTPFa2f9msh9v/U6+Ki0vjKoR5ST2ssURywguCZEiqlihJ+zbDlrPsdeWvc9UIdxQ4h6Tw9uxgwZLVGRliMU0itaQEwzMHWrdMpW19rtJVDAOgp4o4q0Kv1/XzzRBU03O9ecbcFZWsLF3ymQXlAVMR8j2fhtIYsMbRTT9yNReTjVIQZOIjIv1d7IvFKpz2nb2J4iqCeWCzru8sppp8lmCMKcGn1ZN3YKwg8gQME+pnEgVpZvgVP4paE3JOvIRyJg0x3d9UPBJqxvxEmipmuIlIoKo6mFam74rQm/BXrAXtxZynch4T9m+Ma5eNgiyOy/uKk+5PCfJK7vAaqfnjGlEaws9tsiMGBgtKwgHmDkcMzx8bcw2hGKGz8IE/5UGO5t/AKvgXwCBvdsoBE2/uiToQPPw5x0/cyynIPpvh9pxEfxEHUc9C;4:qyrbNFQDIn01FhRs9RGdLJESb6FIeABzJr+f8oX6Kf58wpWuh7q7iK6fgflrFhuEfHReuUud5KfpEaOCaama/iY6KYti7L1z/V46nL7RH08g4Ye8QrtBGe/YUs9VZQNsaresb9WTPrqNAaaMGZZS95giNk7EMTrxM/Nn3i6Ud2NwPAa0mXM9M0HhU8kcsyvsl3vSpoPdWKzIr9pjaT4xud7xyLFSsz/ZQ8HLEMe3IRg14xZ5ZjO+HFjodYT0oTwH X-Exchange-Antispam-Report-Test: UriScan:; X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6040450)(601004)(2401047)(8121501046)(5005006)(93006095)(93001095)(100000703101)(100105400095)(10201501046)(3002001)(6041248)(20161123560025)(20161123555025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123558100)(20161123562025)(20161123564025)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095);SRVR:CO1PR15MB0967;BCL:0;PCL:0;RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095);SRVR:CO1PR15MB0967; X-Forefront-PRVS: 040655413E X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(7370300001)(4630300001)(6009001)(24454002)(377454003)(189002)(199003)(1706002)(50986999)(54356999)(25786009)(83506001)(76176999)(86362001)(6116002)(8676002)(189998001)(81166006)(4326008)(31686004)(2906002)(53936002)(42186005)(81156014)(106356001)(7736002)(31696002)(33646002)(230700001)(101416001)(105586002)(36756003)(305945005)(229853002)(47776003)(2950100002)(65956001)(97736004)(65806001)(23676002)(93886005)(5660300001)(6486002)(4001350100001)(7350300001)(64126003)(6246003)(53546010)(68736007)(6666003)(65826007)(478600001)(50466002)(42262002);DIR:OUT;SFP:1102;SCL:1;SRVR:CO1PR15MB0967;H:[IPv6:2620:10d:c082:1055:1980:fe71:b585:9fe0];FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtDTzFQUjE1TUIwOTY3OzIzOllGVGc2T2R4cVB4NXk1bFRLMksyWmJOUXJY?= =?utf-8?B?U3d4eHVPcWlqeGtQN1dOcjcyaTNUb0ZSSUJIVHdDdXRJRjVndUR3SFRsa2lK?= =?utf-8?B?aHFsZzgxZXNTaEhNaldrUXNrQittbEFNN1pKSS9RYWovaVAwbERUcGZYMGIw?= =?utf-8?B?MGZ3VnRYTVF4Z0ZTYW5sRDdCRndOdnVrZVpBMEpYY0FXODNDK0ZUR0Y1VWs3?= =?utf-8?B?NW5DQ3pGajRZRmFOREREMU91a0lXY0pjbmhlNW5qdGN6VWtmRHFwdTdxK0hy?= =?utf-8?B?RkJvM05SRTRDTUl5T3dqZURvekpTOUhDc0Q2dXlzK1ZYTUkwZ3VZZzcxRHI2?= =?utf-8?B?b1JzRVFGZFFKM0dMYytVUTRSVU04U0lsWjk0QW95VEZrTEVMaGNBcUxHYk9k?= =?utf-8?B?RlJKazJGc2NYYUpXb0JXODFtRlp4SUZ4S1BIWnZZRHZCVTAvYithRVVmWnov?= =?utf-8?B?M1oxSHBxTkEyUUJvY2tEbEJuTXVnU1BqanFkMU9ERUE2a1A1b2E2NTZjL2Ro?= =?utf-8?B?MExCYmhUd1lFcWtXaHhxZFNjdU9LQ0NpWEk2MWY1Q29VdkJsZnZSYXRDNzgr?= =?utf-8?B?NlJ5aUl2ck9Cb2VkL1QrQ0pUbnA0YWZJVm1zY3NNQTA1STM2ZXlKV1JTUFNk?= =?utf-8?B?ZENxYlR5UzB1Zkc3Qm9nbTEvQnVubGJCWXcvbzEyQUdTN0d5aE9va1lyVlYx?= =?utf-8?B?YnNSTlFhRCtETXpDMkx1czh0cWI3ZHNBTDF5TGpqZEpHRzcvM1U0RCs0cEZq?= =?utf-8?B?eTVNUXpvaWtRNmdEelRoOXN1U1U0bkhsdDFKRmtnQzluNzJJWDJMaVgwN3Z0?= =?utf-8?B?ZWtrdHViMi9jbjVzbXRRbjA4aGV1WFpGR2t6a0VmWDhJVm5ncndxUkpQcm1O?= =?utf-8?B?YWRXMjk1M21GVDZFY0xUcmk2OVRkMFFrY2JiWUZMQ1lSaUxOREVpbnhFdEdq?= =?utf-8?B?cm42WXNnR3V3dXI3eDFweUp5WFo3ZXR0NkQ0Tk1sVSt4VVJ3NktCdlg3bGxx?= =?utf-8?B?VnJZMmROeFBNMlBkZ05lVWJWbGVCaEVPZkxqWTIvdlltSS8zUWVnN1Q2YTAy?= =?utf-8?B?eDF5NzZlV3pDc0kzV3MwK2RMUTZjQ21ITW1sTmRiNVhndmVQTXRuMHIrQWI2?= =?utf-8?B?ZjNpTldNcjl0MTlKajJoVW12SVNkWVp2dEFhZTc3bU1vWTh5SWsxL3dsNWNZ?= =?utf-8?B?NWdCWS9VaW9EdVRFZ2ZMckE3cDBJOEYwd2FYY1Q0UGJJanRFSHVZZ1Z2d3Iv?= =?utf-8?B?bHhYTGJldGlPZVdORHg4T3h4LzU4eGdaSTNKZTNxZFRFUjQydzN2bXhyZ1pZ?= =?utf-8?B?YWN5ZUU0WkFWZ0tEM0J1YXN4ZERDYU1wMjRVWEdxS1lEbGpFNUpUd3VOSUxI?= =?utf-8?B?TWVhY0hlNFptRytpQmxTQ2RGRGJaNFFIVlVjSmJjUWM3Yks2V1Bhbk1pRUFP?= =?utf-8?B?MFlPSVpkS25kZGVLZ3d5TDVGbkVqZlVGU0ZtdWdOZzZQNnU1eUhtRFB2SjB6?= =?utf-8?B?TFdEdW5pYmhBSTFOR3JZWnJRcVMyUDdwcGVEYUJTQ3BpRHZ5cEtHcEp2T1Qv?= =?utf-8?B?V05QdTdIOUNLU1BoNTdCTzA3a2NSaU10T3FRbnFleFVJQlhaVjBGR2NkUkt1?= =?utf-8?B?NGRhT3VCWUp2TFlhYlhrd3EwQ3RCRzM2ZFdMVUhlN2pGdXNIZU1KdzZObnln?= =?utf-8?B?c0w2cWl4RC9qZzJFbWQ2TTU1NDJwNko0WGQyZ0NMVkxCa01FUkM2bE9RSmVR?= =?utf-8?Q?//hPU4IaLEe0PovDkDKsW2KFHQvl+cdXSwbKg=3D?= X-Microsoft-Exchange-Diagnostics: 1;CO1PR15MB0967;6:bQIl67RpWj4f4HOQmLbWzORRbip0eNmofASaTY+ZJW2qWm1iaj9pXBAF+1VmqziJrrXYP6JY/FR5fhbrkU+0EvAoATBWo5qP3BS4PH0U/vHFERiJdTFHjSPPT72G7WyWhYb3vHIontPVrMCW3POs4ph8wFnK6a362b+AS1qLD4r80f980woFXRuWXrj6xvpE+5IOfir7eXsCAuAdK7oy5eJMkO5wdh529BrtRVlj7kGp72XB/b4dwA8iEqG6AH2Ch1KNCSmLQHVFRPnlg3X8QVMNi4qhD2FHw4BptBDpOI6WWFfWFXcfXLXBgtYWdLyrtdP90LHZhlmj/GMmTtCSwA==;5:DUMxl12hZmPn+TXeYeXlZATiaQOqpttTcKRxSIY12+UOwfrhwAuDp6pSbFr3hZETH7MksjYoO/DPRYso0wrD+vLWJVuaqm75EQ5lxgUkrwdeMseon+28PCNLiBOWGV/fDeQLDQIhbNv8t5wSHyO6hA==;24:OqWPGUmS30URcFF0AB77aeHy1AtB1SKdagS/GjeWlw3EUgYnvdlkrHpuVzXVvAxpBUqXBfCs2SLERSFDYbhppJodfT4W3WWX3Gqa6itHhuU=;7:r+TSCtj/rRR6hKYeXuPUykqBfwzd0PvjWLvTQxOD90/JRBB3GjIlJpi/i7F8IpLQ8eT76CPyTEhOt0MU60AVFzZGcgkbd7Nr6zv3AfwZ7YXKApL9FPWXLS2fLx/AwxAgpWV5x+Gh//btWW+6nxa4gkAb6GQpkkPc98+sKL3+69Wkyonaxl/pmx/PIPuUHt38dDZ+fzR1Kbku8/RlJ05vDN8OdkoqI+NIe4e/20NNbUY= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1;CO1PR15MB0967;20:qIQsBEgboBdxWleTbWuIJ+xYdWTynL12gX6qyNEiuT+go6VaVRQGpl/IHlPpDUXHeAZOHsyGU8X98KB8h3cPlcEGcR0kGtWbaVf75S5MucmeplcvDzy2dRXIFYYnz70/iTonsYp5sbJACk/NocNIrQ1sq3vt5nw8uYOlm8UEOqA= X-MS-Exchange-CrossTenant-OriginalArrivalTime: 21 Aug 2017 21:18:49.5134 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: CO1PR15MB0967 X-OriginatorOrg: fb.com X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2017-08-21_14:,, signatures=0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1393 Lines: 26 On 8/21/17 1:24 PM, Edward Cree wrote: > 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? yes. of course. just give the test some reasonable name :)