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: <BANLkTimE2GkkhcFZtNrYZASWp0LDhUx=GQ@mail.gmail.com>
Date:	Fri, 13 May 2011 09:11:31 -0700
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Andrew Lutomirski <luto@....edu>
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 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 ;)

                                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/