linux-kernel - Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <BANLkTikDafbCnsXPoidnMBAE0qtd9aC4oQ@mail.gmail.com>
Date:	Fri, 13 May 2011 12:13:23 -0400
From:	Andrew Lutomirski <luto@....edu>
To:	Linus Torvalds <torvalds@...ux-foundation.org>
Cc:	Christian Couder <christian.couder@...il.com>,
	linux-kernel@...r.kernel.org, netdev@...r.kernel.org,
	git@...r.kernel.org, Shuang He <shuang.he@...el.com>
Subject: Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard
 right after logging in)

On Fri, May 13, 2011 at 12:11 PM, Linus Torvalds
<torvalds@...ux-foundation.org> wrote:
> On Fri, May 13, 2011 at 7:56 AM, Andrew Lutomirski <luto@....edu> wrote:
>>
>> So what I really want is a fancy version of git bisect that makes no
>> assumptions about the relationship of good and bad commits in the
>> graph and just finds me a commit that is bad but for which all parents
>> are good or vice versa.
>
> Ehh. That's the "non-fancy" way of testing, I'm afraid: if you cannot
> make assumption about the relationship between good and bad commits,
> then you have to test _every_ commit.
>
> So yes, bisection has its problems. But they really do come from the
> fact that it's very efficient. When you have (on average) about ten
> thousand commits between releases, you have to make assumptions about
> the relationships. But once you do that, the efficiency also results
> in a certain fragility.
>
> Think of it as a compression method: it generates the smallest
> possible set of test points for you. But it's a "lossy" compression -
> you don't test everything. And it's extreme: it boils down 10k commit
> events to about 13 bisection events. If anything goes wrong (like the
> bug not being entirely repeatable, or the bug comes and goes), it will
> give the wrong answer.
>
> The good news is that _usually_ it works really well. And when the
> choice is between "works really well for 10k commits but can have
> problems" and "you need to test all 10k commits", the "can have
> problems" part turns out to be a pretty small downside ;)

In conclusion, I found the problem.  It's a clusterfuck and I think
there's no way that any bisection tool under any sane assumptions
could have found it.  Patch coming in a couple seconds b/c I think it
needs to go in to 2.6.39.

--Andy

>
>                                Linus
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/