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 

Reply via email to