Message-ID: <20180405052820.eurpes52ilhofbg3@ast-mbp.dhcp.thefacebook.com>
Date:   Wed, 4 Apr 2018 22:28:22 -0700
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Edward Cree <ecree@...arflare.com>
Cc:     Daniel Borkmann <daniel@...earbox.net>, netdev@...r.kernel.org
Subject: Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call
 simplifications

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.

> > Even if we don't see the solution today we have to work towards it.
> I guess I'm just not confident "towards" is the direction you think it is.
> 
> > Compiler designers could have combined multiple of such passes into
> > fewer ones, but it's not done, because it increases complexity and
> > causes tough bugs where pass is partially complete.
> I'm not trying to combine together multiple 'for bb in prog/for insn in bb'-
>  type passes.  The combining I was doing was more on 'for all possible
>  execution paths'-type passes, because it's those that explode combinatorially.
> Happily I think we can go a long way towards getting rid of them; but while I
>  think we can get down to only having 1, I don't think we can reach 0.

we have to. That's the point. 'explore all possible paths' must be removed.
New code should not be relying on that in a way that it's difficult to remove
later. subprog boundaries is a typical example where doing it as
part of 'explore all paths' is harmful long term. Regardless of extra
O(num_of_subrogs) complexity it brings short term.

> > The prime example where more than 4k instructions and loops are mandatory
> > is user space stack analysis inside the program. Like walking python stack
> > requires non-trival pointer chasing. With 'pragma unroll' the stack depth
> > limit today is ~18. That's not really usable. Looping through 100 python
> > frames would require about 16k bpf assembler instructions.
> But this would be solved by having support for bounded loops, and I think I've
>  successfully shown that this is not inherently incompatible with a do_check()
>  style walk.

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.

> > Hence do_check approach must go. The rough idea is to compute per basic
> > block a set of INs (registers and stack) that basic block needs
> > to see to be safe and corresponding set of OUTs.
> > Then propagate this knowledge across cfg edges.
> > Once we have such set per bpf function, it will essentially answer the question
> > 'what arguments this function needs to see to be safe and what it returns'
> > To make bpf libraries scale we'd need to keep such information
> > around after the verification, so dynamic linking and indirect calls
> > are fast to verify.
> > It's very high level obviously. There are many gotchas to resolve.
> I agree that if we can do this it'll be ideal.  But that's a big 'if'; my
>  example code was intended to demonstrate that the "set of INs bb/func needs to
>  see to be safe" can be an arbitrarily complicated disjunction, and that instead
>  of a combinatorially exploding number of paths to walk (the do_check() approach)
>  you now have combinatorially exploding IN-constraints to propagate backwards.

This sounds like arbitrary assumptions what this new approach would do.
Instead of rejecting it outright try to solve this very hard problem.

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.

Powered by blists - more mailing lists