Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call simplifications

[Edward Cree <ecree@solarflare.com>]

On 05/04/18 06:28, Alexei Starovoitov wrote:
> 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.
As I think I already said, I'm working on a next version of the patch that
 does just that.

> 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.
... IF it's possible at all, which I'm still doubtful about.

> This sounds like arbitrary assumptions what this new approach would do.
> Instead of rejecting it outright try to solve this very hard problem.
I'm not rejecting it outright; I'm just saying, be prepared for the possibility
 that it can't be solved, and try to leave a line of retreat / have a plan B in
 the case that it proves to be subject to a no-free-lunch theorem.  Because my
 intuition is that an entropy argument may require all algos to have the same
 superexponential worst-case running time as 'explore all paths' does.

> 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.
I think the next version of the patch series (coming real soon now) answers at
 least most of your objections (and indeed the above debate isn't relevant to it).