From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751657AbdF1UiX (ORCPT ); Wed, 28 Jun 2017 16:38:23 -0400 Received: from www62.your-server.de ([213.133.104.62]:43007 "EHLO www62.your-server.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751505AbdF1UiO (ORCPT ); Wed, 28 Jun 2017 16:38:14 -0400 Message-ID: <595413AA.40502@iogearbox.net> Date: Wed, 28 Jun 2017 22:38:02 +0200 From: Daniel Borkmann User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0 MIME-Version: 1.0 To: Edward Cree , davem@davemloft.net, Alexei Starovoitov , Alexei Starovoitov CC: netdev@vger.kernel.org, linux-kernel@vger.kernel.org, iovisor-dev Subject: Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier References: <5953B436.6030506@iogearbox.net> <788035e1-1974-b48e-3008-d294194a8b05@solarflare.com> In-Reply-To: <788035e1-1974-b48e-3008-d294194a8b05@solarflare.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Authenticated-Sender: daniel@iogearbox.net Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 06/28/2017 04:11 PM, Edward Cree wrote: > On 28/06/17 14:50, Daniel Borkmann wrote: >> Hi Edward, >> >> Did you also have a chance in the meantime to look at reducing complexity >> along with your unification? I did run the cilium test suite with your >> latest set from here and current # worst case processed insns that >> verifier has to go through for cilium progs increases from ~53k we have >> right now to ~76k. I'm a bit worried that this quickly gets us close to >> the upper ~98k max limit starting to reject programs again. Alternative >> is to bump the complexity limit again in near future once run into it, >> but preferably there's a way to optimize it along with the rewrite? Do >> you see any possibilities worth exploring? > The trouble, I think, is that as we're now tracking more information about > each register value, we're less able to prune branches. But often that > information is not actually being used in reaching the exit state. So it Agree. > seems like the way to tackle this would be to track what information is > used — or at least, which registers are read from (including e.g. writing > through them or passing them to helper calls) — in reaching a safe state. > Then only registers which are used are required to match for pruning. > But that tracking would presumably have to propagate backwards through the > verifier stack, and I'm not sure how easily that could be done. Someone > (was it you?) was talking about replacing the current DAG walking and > pruning with some kind of basic-block thing, which would help with this. > Summary: I think it could be done, but I haven't looked into the details > of implementation yet; if it's not actually breaking your programs (yet), > maybe leave it for a followup patch series? Could we adapt the limit to 128k perhaps as part of this set given we know that we're tracking more meta data here anyway? Then we could potentially avoid going via -stable later on, biggest pain point is usually tracking differences in LLVM code generation (e.g. differences in optimizations) along with verifier changes to make sure that programs still keep loading on older kernels with e.g. newer LLVM; one of the issues is that pruning can be quite fragile. E.g. worst case adding a simple var in a branch that LLVM assigns a stack slot that was otherwise not used throughout the prog can cause a significant increase of verifier work (run into this multiple times in the past and is a bit of a pain to track down actually). If we could keep some buffer in BPF_COMPLEXITY_LIMIT_INSNS at least when we know that more work is needed anyway from that point onward, that would be good. From mboxrd@z Thu Jan 1 00:00:00 1970 From: Daniel Borkmann via iovisor-dev Subject: Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Date: Wed, 28 Jun 2017 22:38:02 +0200 Message-ID: <595413AA.40502@iogearbox.net> References: <5953B436.6030506@iogearbox.net> <788035e1-1974-b48e-3008-d294194a8b05@solarflare.com> Reply-To: Daniel Borkmann Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8"; Format="flowed" Content-Transfer-Encoding: base64 Cc: netdev-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, iovisor-dev , linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org To: Edward Cree , davem-fT/PcQaiUtIeIZ0/mPfg9Q@public.gmane.org, Alexei Starovoitov , Alexei Starovoitov Return-path: In-Reply-To: <788035e1-1974-b48e-3008-d294194a8b05-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: iovisor-dev-bounces-9jONkmmOlFHEE9lA1F8Ukti2O/JbrIOy@public.gmane.org Errors-To: iovisor-dev-bounces-9jONkmmOlFHEE9lA1F8Ukti2O/JbrIOy@public.gmane.org List-Id: netdev.vger.kernel.org T24gMDYvMjgvMjAxNyAwNDoxMSBQTSwgRWR3YXJkIENyZWUgd3JvdGU6Cj4gT24gMjgvMDYvMTcg MTQ6NTAsIERhbmllbCBCb3JrbWFubiB3cm90ZToKPj4gSGkgRWR3YXJkLAo+Pgo+PiBEaWQgeW91 IGFsc28gaGF2ZSBhIGNoYW5jZSBpbiB0aGUgbWVhbnRpbWUgdG8gbG9vayBhdCByZWR1Y2luZyBj b21wbGV4aXR5Cj4+IGFsb25nIHdpdGggeW91ciB1bmlmaWNhdGlvbj8gSSBkaWQgcnVuIHRoZSBj aWxpdW0gdGVzdCBzdWl0ZSB3aXRoIHlvdXIKPj4gbGF0ZXN0IHNldCBmcm9tIGhlcmUgYW5kIGN1 cnJlbnQgIyB3b3JzdCBjYXNlIHByb2Nlc3NlZCBpbnNucyB0aGF0Cj4+IHZlcmlmaWVyIGhhcyB0 byBnbyB0aHJvdWdoIGZvciBjaWxpdW0gcHJvZ3MgaW5jcmVhc2VzIGZyb20gfjUzayB3ZSBoYXZl Cj4+IHJpZ2h0IG5vdyB0byB+NzZrLiBJJ20gYSBiaXQgd29ycmllZCB0aGF0IHRoaXMgcXVpY2ts eSBnZXRzIHVzIGNsb3NlIHRvCj4+IHRoZSB1cHBlciB+OThrIG1heCBsaW1pdCBzdGFydGluZyB0 byByZWplY3QgcHJvZ3JhbXMgYWdhaW4uIEFsdGVybmF0aXZlCj4+IGlzIHRvIGJ1bXAgdGhlIGNv bXBsZXhpdHkgbGltaXQgYWdhaW4gaW4gbmVhciBmdXR1cmUgb25jZSBydW4gaW50byBpdCwKPj4g YnV0IHByZWZlcmFibHkgdGhlcmUncyBhIHdheSB0byBvcHRpbWl6ZSBpdCBhbG9uZyB3aXRoIHRo ZSByZXdyaXRlPyBEbwo+PiB5b3Ugc2VlIGFueSBwb3NzaWJpbGl0aWVzIHdvcnRoIGV4cGxvcmlu Zz8KPiBUaGUgdHJvdWJsZSwgSSB0aGluaywgaXMgdGhhdCBhcyB3ZSdyZSBub3cgdHJhY2tpbmcg bW9yZSBpbmZvcm1hdGlvbiBhYm91dAo+ICAgZWFjaCByZWdpc3RlciB2YWx1ZSwgd2UncmUgbGVz cyBhYmxlIHRvIHBydW5lIGJyYW5jaGVzLiAgQnV0IG9mdGVuIHRoYXQKPiAgIGluZm9ybWF0aW9u IGlzIG5vdCBhY3R1YWxseSBiZWluZyB1c2VkIGluIHJlYWNoaW5nIHRoZSBleGl0IHN0YXRlLiAg U28gaXQKCkFncmVlLgoKPiAgIHNlZW1zIGxpa2UgdGhlIHdheSB0byB0YWNrbGUgdGhpcyB3b3Vs ZCBiZSB0byB0cmFjayB3aGF0IGluZm9ybWF0aW9uIGlzCj4gICB1c2VkIOKAlCBvciBhdCBsZWFz dCwgd2hpY2ggcmVnaXN0ZXJzIGFyZSByZWFkIGZyb20gKGluY2x1ZGluZyBlLmcuIHdyaXRpbmcK PiAgIHRocm91Z2ggdGhlbSBvciBwYXNzaW5nIHRoZW0gdG8gaGVscGVyIGNhbGxzKSDigJQgaW4g cmVhY2hpbmcgYSBzYWZlIHN0YXRlLgo+ICAgVGhlbiBvbmx5IHJlZ2lzdGVycyB3aGljaCBhcmUg dXNlZCBhcmUgcmVxdWlyZWQgdG8gbWF0Y2ggZm9yIHBydW5pbmcuCj4gQnV0IHRoYXQgdHJhY2tp bmcgd291bGQgcHJlc3VtYWJseSBoYXZlIHRvIHByb3BhZ2F0ZSBiYWNrd2FyZHMgdGhyb3VnaCB0 aGUKPiAgIHZlcmlmaWVyIHN0YWNrLCBhbmQgSSdtIG5vdCBzdXJlIGhvdyBlYXNpbHkgdGhhdCBj b3VsZCBiZSBkb25lLiAgU29tZW9uZQo+ICAgKHdhcyBpdCB5b3U/KSB3YXMgdGFsa2luZyBhYm91 dCByZXBsYWNpbmcgdGhlIGN1cnJlbnQgREFHIHdhbGtpbmcgYW5kCj4gICBwcnVuaW5nIHdpdGgg c29tZSBraW5kIG9mIGJhc2ljLWJsb2NrIHRoaW5nLCB3aGljaCB3b3VsZCBoZWxwIHdpdGggdGhp cy4KPiBTdW1tYXJ5OiBJIHRoaW5rIGl0IGNvdWxkIGJlIGRvbmUsIGJ1dCBJIGhhdmVuJ3QgbG9v a2VkIGludG8gdGhlIGRldGFpbHMKPiAgIG9mIGltcGxlbWVudGF0aW9uIHlldDsgaWYgaXQncyBu b3QgYWN0dWFsbHkgYnJlYWtpbmcgeW91ciBwcm9ncmFtcyAoeWV0KSwKPiAgIG1heWJlIGxlYXZl IGl0IGZvciBhIGZvbGxvd3VwIHBhdGNoIHNlcmllcz8KCkNvdWxkIHdlIGFkYXB0IHRoZSBsaW1p dCB0byAxMjhrIHBlcmhhcHMgYXMgcGFydCBvZiB0aGlzIHNldApnaXZlbiB3ZSBrbm93IHRoYXQg d2UncmUgdHJhY2tpbmcgbW9yZSBtZXRhIGRhdGEgaGVyZSBhbnl3YXk/ClRoZW4gd2UgY291bGQg cG90ZW50aWFsbHkgYXZvaWQgZ29pbmcgdmlhIC1zdGFibGUgbGF0ZXIgb24sCmJpZ2dlc3QgcGFp biBwb2ludCBpcyB1c3VhbGx5IHRyYWNraW5nIGRpZmZlcmVuY2VzIGluIExMVk0KY29kZSBnZW5l cmF0aW9uIChlLmcuIGRpZmZlcmVuY2VzIGluIG9wdGltaXphdGlvbnMpIGFsb25nIHdpdGgKdmVy aWZpZXIgY2hhbmdlcyB0byBtYWtlIHN1cmUgdGhhdCBwcm9ncmFtcyBzdGlsbCBrZWVwIGxvYWRp bmcKb24gb2xkZXIga2VybmVscyB3aXRoIGUuZy4gbmV3ZXIgTExWTTsgb25lIG9mIHRoZSBpc3N1 ZXMgaXMgdGhhdApwcnVuaW5nIGNhbiBiZSBxdWl0ZSBmcmFnaWxlLiBFLmcuIHdvcnN0IGNhc2Ug YWRkaW5nIGEgc2ltcGxlCnZhciBpbiBhIGJyYW5jaCB0aGF0IExMVk0gYXNzaWducyBhIHN0YWNr IHNsb3QgdGhhdCB3YXMgb3RoZXJ3aXNlCm5vdCB1c2VkIHRocm91Z2hvdXQgdGhlIHByb2cgY2Fu IGNhdXNlIGEgc2lnbmlmaWNhbnQgaW5jcmVhc2Ugb2YKdmVyaWZpZXIgd29yayAocnVuIGludG8g dGhpcyBtdWx0aXBsZSB0aW1lcyBpbiB0aGUgcGFzdCBhbmQKaXMgYSBiaXQgb2YgYSBwYWluIHRv IHRyYWNrIGRvd24gYWN0dWFsbHkpLiBJZiB3ZSBjb3VsZCBrZWVwCnNvbWUgYnVmZmVyIGluIEJQ Rl9DT01QTEVYSVRZX0xJTUlUX0lOU05TIGF0IGxlYXN0IHdoZW4gd2Uga25vdwp0aGF0IG1vcmUg d29yayBpcyBuZWVkZWQgYW55d2F5IGZyb20gdGhhdCBwb2ludCBvbndhcmQsIHRoYXQKd291bGQg YmUgZ29vZC4KX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18K aW92aXNvci1kZXYgbWFpbGluZyBsaXN0Cmlvdmlzb3ItZGV2QGxpc3RzLmlvdmlzb3Iub3JnCmh0 dHBzOi8vbGlzdHMuaW92aXNvci5vcmcvbWFpbG1hbi9saXN0aW5mby9pb3Zpc29yLWRldgo=