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).
