git-bisect failed me again

git-bisect failed me again

[Andrew Morton]

Trying to find a recently-merged box-killer in Len's tree:

bix:/usr/src/git26> cat .git/branches/git-acpi 
git+ssh://master.kernel.org/pub/scm/linux/kernel/git/lenb/linux-acpi-2.6.git#test

git-checkout git-acpi
git-bisect reset
git-bisect start
git-bisect good ff2fc3e9e3edb918b6c6b288485c6cb267bc865e
git-bisect bad 9011bff4bdc0fef1f9a782d7415c306ee61826c9

And it led me to

bix:/usr/src/git26> git-bisect good
9011bff4bdc0fef1f9a782d7415c306ee61826c9 is first bad commit
diff-tree 9011bff4bdc0fef1f9a782d7415c306ee61826c9 (from 7e1f19e50371e1d148226b64c8edc77fec47fa5b)
Author: Len Brown <len.brown@intel.com>
Date:   Thu May 11 00:28:12 2006 -0400

    ACPI: delete newly added debugging macros in processor_perflib.c
    

which isn't a buggy patch.

bix:/usr/src/git26> cat .git/BISECT_LOG
git-bisect start
# good: [ff2fc3e9e3edb918b6c6b288485c6cb267bc865e] ACPI: EC acpi-ecdt-uid-hack
git-bisect good ff2fc3e9e3edb918b6c6b288485c6cb267bc865e
# bad: [9011bff4bdc0fef1f9a782d7415c306ee61826c9] ACPI: delete newly added debugging macros in processor_perflib.c
git-bisect bad 9011bff4bdc0fef1f9a782d7415c306ee61826c9
# good: [c52851b60cc0aaaf974ff0e49989fb698220447d] P-state software coordination for speedstep-centrino
git-bisect good c52851b60cc0aaaf974ff0e49989fb698220447d
# good: [7e1f19e50371e1d148226b64c8edc77fec47fa5b] ACPI: UP build fix for bugzilla-5737
git-bisect good 7e1f19e50371e1d148226b64c8edc77fec47fa5b


A had a second go - fed it the very first and last commit IDs in that tree.
 Same result.

bix:/usr/src/git26> git-bisect good
9011bff4bdc0fef1f9a782d7415c306ee61826c9 is first bad commit
diff-tree 9011bff4bdc0fef1f9a782d7415c306ee61826c9 (from 7e1f19e50371e1d148226b64c8edc77fec47fa5b)
Author: Len Brown <len.brown@intel.com>
Date:   Thu May 11 00:28:12 2006 -0400

    ACPI: delete newly added debugging macros in processor_perflib.c
    
    Signed-off-by: Len Brown <len.brown@intel.com>

:040000 040000 f7a3b4cfdb128fb6a777b2e30a83c63edd70f46a 2ca1c42aaae65df9052d60d274aaec3116e30c2d M      drivers
bix:/usr/src/git26> cat .git/BISECT_LOG       
git-bisect start
# good: [74951d613e758f9709d6f2173107be68f18f77f4] ACPI: Remove debugging macros from drivers/acpi/thermal.c
git-bisect good 74951d613e758f9709d6f2173107be68f18f77f4
# bad: [9011bff4bdc0fef1f9a782d7415c306ee61826c9] ACPI: delete newly added debugging macros in processor_perflib.c
git-bisect bad 9011bff4bdc0fef1f9a782d7415c306ee61826c9
# good: [c52851b60cc0aaaf974ff0e49989fb698220447d] P-state software coordination for speedstep-centrino
git-bisect good c52851b60cc0aaaf974ff0e49989fb698220447d
# good: [7e1f19e50371e1d148226b64c8edc77fec47fa5b] ACPI: UP build fix for bugzilla-5737
git-bisect good 7e1f19e50371e1d148226b64c8edc77fec47fa5b


What did I do wrong this time?

Thanks.

Re: git-bisect failed me again

[Linus Torvalds]

On Fri, 12 May 2006, Andrew Morton wrote:
> 
> Trying to find a recently-merged box-killer in Len's tree:
> 
> bix:/usr/src/git26> cat .git/branches/git-acpi 
> git+ssh://master.kernel.org/pub/scm/linux/kernel/git/lenb/linux-acpi-2.6.git#test
> 
> git-checkout git-acpi

Just for others: if you already have a Linux repo, this is the perfect 
time to do

	git clone --reference <old-linux-repo>
		git://git.kernel.org/pub/scm/linux/kernel/git/lenb/linux-acpi-2.6

to get that linux-acpi-2.6 repository.

And for Junio: good job on that "--reference" flag. I used to do a local 
clone and then force an update, this was much better.

> git-bisect reset
> git-bisect start
> git-bisect good ff2fc3e9e3edb918b6c6b288485c6cb267bc865e
> git-bisect bad 9011bff4bdc0fef1f9a782d7415c306ee61826c9
> 
> And it led me to
> 
> bix:/usr/src/git26> git-bisect good
> 9011bff4bdc0fef1f9a782d7415c306ee61826c9 is first bad commit
> 
> which isn't a buggy patch.

Well, to see what's up, do "git bisect visualize". That tends to not only 
help bisect things (for when you want to pick a different bisection 
point), it's also a wonderfully visual tool to what the f*%& happens when 
something goes wrong.

Anyway, when I replay your log:

> bix:/usr/src/git26> cat .git/BISECT_LOG
> git-bisect start
> # good: [ff2fc3e9e3edb918b6c6b288485c6cb267bc865e] ACPI: EC acpi-ecdt-uid-hack
> git-bisect good ff2fc3e9e3edb918b6c6b288485c6cb267bc865e
> # bad: [9011bff4bdc0fef1f9a782d7415c306ee61826c9] ACPI: delete newly added debugging macros in processor_perflib.c
> git-bisect bad 9011bff4bdc0fef1f9a782d7415c306ee61826c9
> # good: [c52851b60cc0aaaf974ff0e49989fb698220447d] P-state software coordination for speedstep-centrino
> git-bisect good c52851b60cc0aaaf974ff0e49989fb698220447d
> # good: [7e1f19e50371e1d148226b64c8edc77fec47fa5b] ACPI: UP build fix for bugzilla-5737
> git-bisect good 7e1f19e50371e1d148226b64c8edc77fec47fa5b

I definitely get the same "9011bff4bdc0fef1f9a782d7415c306ee61826c9 is 
first bad commit" result, and going along visually at every point makes it 
very very obvious that git-bisect is right.

(In fact, the _most_ visually obvious way to do it is to do this:

	git bisect reset
	git bisect start
	git bisect good ff2fc3e9e3edb918b6c6b288485c6cb267bc865e
	git bisect bad 9011bff4bdc0fef1f9a782d7415c306ee61826c9
	git bisect visualize &
	git bisect good c52851b60cc0aaaf974ff0e49989fb698220447d
	.. go into the "file" menu, and select "re-read references" ..
	git-bisect good 7e1f19e50371e1d148226b64c8edc77fec47fa5b
	.. do "re-read references" again ..

and you'll see exactly what "git bisect" is doing).

You claimed that the previous commit (7e1f19..) was good, and that 
9011bff.. itself was bad). So if that was true, then it really _was_ that 
9011bff.. commit that caused it.

> What did I do wrong this time?

You did nothing wrong, unless your _testing_ was wrong, and one of your 
"git bisect good" entries should have been bad, or the other way around 
(you booted into the wrong kernel, so you thought something was ok when it 
wasn't).

Why are you so sure that git bisect gave the wrong answer? This is ACPI, 
after all. For all we know, subtle cache-effects could break it.

"git bisect" sadly won't help with bugs that show up due to some other 
subtle interaction..

Anyway, my first guess would be that you might have marked something good 
or bad that wasn't. How sure are you about that initial "git bisect bad" 
you did?

		Linus

Re: git-bisect failed me again

[Andrew Morton]

Linus Torvalds <torvalds@osdl.org> wrote:
>
> (In fact, the _most_ visually obvious way to do it is to do this:
> 
>  	git bisect reset
>  	git bisect start
>  	git bisect good ff2fc3e9e3edb918b6c6b288485c6cb267bc865e
>  	git bisect bad 9011bff4bdc0fef1f9a782d7415c306ee61826c9
>  	git bisect visualize &
>  	git bisect good c52851b60cc0aaaf974ff0e49989fb698220447d
>  	.. go into the "file" menu, and select "re-read references" ..
>  	git-bisect good 7e1f19e50371e1d148226b64c8edc77fec47fa5b
>  	.. do "re-read references" again ..
> 
>  and you'll see exactly what "git bisect" is doing).
> 
>  You claimed that the previous commit (7e1f19..) was good, and that 
>  9011bff.. itself was bad). So if that was true, then it really _was_ that 
>  9011bff.. commit that caused it.
> 
>  > What did I do wrong this time?
> 
>  You did nothing wrong, unless your _testing_ was wrong, and one of your 
>  "git bisect good" entries should have been bad, or the other way around 
>  (you booted into the wrong kernel, so you thought something was ok when it 
>  wasn't).
> 
>  Why are you so sure that git bisect gave the wrong answer? This is ACPI, 
>  after all. For all we know, subtle cache-effects could break it.
> 
>  "git bisect" sadly won't help with bugs that show up due to some other 
>  subtle interaction..
> 
>  Anyway, my first guess would be that you might have marked something good 
>  or bad that wasn't. How sure are you about that initial "git bisect bad" 
>  you did?

Am pretty confident.


bix:/usr/src/25> grep '^commit ' patches/git-acpi.patch 
commit 9011bff4bdc0fef1f9a782d7415c306ee61826c9		<- This was my `bad'
commit 5d882e684aafea30c508d86d235327d94e1d38ae
commit 14394600cdfe0c952ce662a32a68c5c5524d32ac
commit da95181baf3cf6a2bd81c0c8af1d4c6790703e4f
commit b128440ed11d108c375772b7fe9ad46d2ac07084		<- This was the bug
commit 61ce94e1f8b16b1694475adba9bf2e07fac02020
commit a48142ea89e02ed0aba0a481ead1e9302e1a4160
commit d5c11d3ba31d6ead24f27de648dc2dcfde5092e3
commit f6a08bf2cb06ee3d5be749cf20685b677619bc8e
commit 2cb7f1704275905b7548eee299c554bcdc5cf357
commit 2ce2b16467f0d43d0f8933eb4821b2369b31888c
commit 8ec0cbd9386a40a3afffad78334f4403b256dc4b
commit ba8acc597cff47fcbbd7b9f0d73a59e784852d8b
commit 7e9e8344848d80c9b6e1b9eaf32dd498b48ca5bb
commit d2606159ffdf8e435f6a7714f8e8910672b944d5
commit 8fb1d47b74e2bad912f74783048b433a1e313799
commit f7c0fce6da5cb68b8b0e203df4ff8ef9b3265105
commit 61e295946a248e43cf244cb24097e284d1d00e35
commit a32283362a7a8e7cff608fe25299a59925daea4d
commit 4cd5611ca16348b3805ddcf89b97fe670e76faaa
commit 529758bad4b0f9a8eec56fcc5cad342e9680ea36
commit 91afb9e683426ff238aab159e60f6d6e792e7488
commit 9f102deee398ea4dfcee3b2108dc00bc59ea877b
commit e85eb9a47f19a26b636b58106e309f8db6b2415d
commit 4597ac50598b85a09417df531849b80ce2e8e44b
commit 74951d613e758f9709d6f2173107be68f18f77f4
commit e6f1f3c54974a30c65ea0b699809d12f0aa04272
commit c12ea918ee175ceb3a258cd81f1c43e897d0c0bc
commit eefa27a93a0490902f33837ac86dbcf344b3aa29
commit ff2fc3e9e3edb918b6c6b288485c6cb267bc865e
commit df42baa0d8e54df18dd9366dd7c93d6be7d5d063
commit 200739c179c63d21804e9e8e2ced265243831579
commit 5e15b92d07fb11490c886c5dd7567f523ea43e2d
commit 9224a867c497053842dc595e594ca6d32112221f
commit 459c7266d7a5c1730169258217e25fdd1b7ca854
commit 1a36561607abf1405b56a41aac2fd163429cd1f8
commit e4513a57ef719d3d6d1cee0ca4d9f4016aa452bb
commit 578b333bfe8eb1360207a08a53c321822a8f40f3
commit 9d9f749b316ac21cb59ad3e595cbce469b409e1a
commit cd090eedd85256829f762677d0752a846c1b88b9
commit 81507ea9cfa64e9851b53e0fefebfa776eda9ecb
commit 1c6e7d0aeecac38e66b1bb63e3eff07b2a1c2f2c
commit b5f2490b6e3317059e87ba40d4f659d1c30afc1f
commit 1acfb7f2b0d460ee86bdb25ad0679070ec8a5f0d
commit 7e1f19e50371e1d148226b64c8edc77fec47fa5b
commit 1300124f69cafc54331bc06e968a8dd67863f989
commit ec7381d6bfd3e7b8d2880dd5e9d03b131b0603f6
commit 8313524a0d466f451a62709aaedf988d8257b21c
commit ea936b78f46cbe089a4ac363e1682dee7d427096
commit 52fc0b026e99b5d5d585095148d997d5634bbc25
commit 46358614ed5b031797522f1020e989c959a8d8a6
commit 6665bda76461308868bd1e52caf627f4cb29ed32
commit fdc136ccd3332938e989439c025c363f8479f3e6
commit a1f9e65e2085e0a87f28a4d5a8ae43b32c087f24
commit 1fee94034917aa711fcbd4ebf4c36f7ebd9fa7d6
commit 0eacee585a89ce5827b572a73a024931506bef48
commit 9cfda2c94df61c9f859b474abe774c65a4464d0a
commit d52bb94d56676acd9bdac8e097257a87b4b1b2e1
commit c52851b60cc0aaaf974ff0e49989fb698220447d
commit 09b4d1ee881c8593bfad2a42f838d85070365c3e
commit 3b2d99429e3386b6e2ac949fc72486509c8bbe36
commit ffd642e748c867a7339b57225b8bf8b9a0dcd9c5      <- This was my `good'
commit f9ea7fd8be9827791f407ca1191ff70ec25eb2d9
commit b60e49b2383db0334bef1f0d9cdad9bec2336050
commit 1ca218d3bd6acca0922a349cb76e3244d27ebfba

and git-bisect claimed that 9011bff4bdc0fef1f9a782d7415c306ee61826c9
introduced the bug.  

Re: git-bisect failed me again

[Linus Torvalds]

On Fri, 12 May 2006, Andrew Morton wrote:
>
> Linus Torvalds <torvalds@osdl.org> wrote:
> > 
> >  Anyway, my first guess would be that you might have marked something good 
> >  or bad that wasn't. How sure are you about that initial "git bisect bad" 
> >  you did?
> 
> Am pretty confident.

And I'm pretty damn sure it ain't.

Andrew, git is _not_ linear. You can't just list the commits, take the 
last and the first, and say "the last must be bad, the first must be 
good". Which seems to be what you did.

> 
> 
> bix:/usr/src/25> grep '^commit ' patches/git-acpi.patch 
> commit 9011bff4bdc0fef1f9a782d7415c306ee61826c9		<- This was my `bad'
> commit 5d882e684aafea30c508d86d235327d94e1d38ae
> commit 14394600cdfe0c952ce662a32a68c5c5524d32ac
> commit da95181baf3cf6a2bd81c0c8af1d4c6790703e4f
> commit b128440ed11d108c375772b7fe9ad46d2ac07084		<- This was the bug

That "b128440e.." commit wasn't even among the collection of commits that 
you tested with "git bisect" in the first place. 

You've apparently created a "list of commits" that doesn't include any 
merges, and then you decided that the "most recent of those commits was 
obviously bad".

WHICH IS NOT TRUE.

You never actually even TESTED that 9011bff commit, did you? In fact, I'm 
100% sure you didn't. You just said "it's bad", without any confidence 
what-so-ever except that it happened to be first on your list.

Right?

The fact is, it seems that the way you generated the list of commits was 
basically:

 - pick every commit that is not a merge and doesn't exist in linus tree.

   (ie you basically did the equivalent of "git-rev-list --no-merges 
   linus..acpi", although it's possible that you used "git whatchanged" or 
   something else that will not show merges because they don't generate 
   diffs)

And then you believed that you had a linear series of commits, and that 
the most recent commit must thus be the buggy one.

But git isn't linear. Never has been. The fact that commits get (roughtly) 
sorted by date (modified by their ancestry relationships either subtly or 
grossly depending on whether --topo-sort is off or on) does not make 
anything linear.

The commit you mark as "this was the bug" is on a totally different 
development branch from the one you marked "bad". That development branch 
was merged with the branch that your "bad" commit came from with commit 
7378614.. (which is not on your list at all):

	"Pull bugzilla-5737 into test branch"

but there are actually a few other merges there too (and ACPI-only commits 
that aren't reachable from your "top" bad commit).

> and git-bisect claimed that 9011bff4bdc0fef1f9a782d7415c306ee61826c9
> introduced the bug.  

Hell no. Git bisect did no such thing at all. YOU DID.

Go back and look at what your sequence of instructions was (from your 
original email):

 ->> Trying to find a recently-merged box-killer in Len's tree:
 ->> 
 ->> bix:/usr/src/git26> cat .git/branches/git-acpi 
 ->> git+ssh://master.kernel.org/pub/scm/linux/kernel/git/lenb/linux-acpi-2.6.git#test
 ->> 
 ->> git-checkout git-acpi
 ->> git-bisect reset
 ->> git-bisect start
 ->> git-bisect good ff2fc3e9e3edb918b6c6b288485c6cb267bc865e
 ->> git-bisect bad 9011bff4bdc0fef1f9a782d7415c306ee61826c9
 ->> 
 ->> And it led me to

and notice how YOU claimed that "9011bff4.." was bad at the very
beginning of the "git bisect" run.  Not "git bisect". YOU. You started off 
by claiming that 9011bff4 was bad, apparently without having ever even 
tested it.

The way "git bisect" works is that if you give it garbage information, it 
_will_ give you a garbage result. That's pretty much guaranteed. But if 
you actually give it tested and correct information, it will very 
efficiently zero in on what the problem really was.

And the whole _point_ about "git bisect" is that the git history isn't 
linear. If it was linear, you wouldn't need a tool to bisect it at all: 
you'd just pick the middle entry from the history list, and use it. It 
would be so trivial to bisect by hand, that using a tool is just 
unnecessary.

So really, take a look at "git bisect visualize". In this case, you should 
have noticed that you had a list of 50+ commits, but when you did

	git bisect good ff2fc3e
	git bisect bad 9011bff
	git bisect visualize

you had cut your list of commits down to just six (none of which was the 
bug).

This is why I integrated "gitk" immediately when it became available. It's 
really important to see the non-linear history, because if you don't 
visualize it (either mentally or with a tool like "gitk"), you'll never 
understand what is going on. 

		Linus

Re: git-bisect failed me again

[Linus Torvalds]

On Fri, 12 May 2006, Linus Torvalds wrote:
> 
> But git isn't linear. Never has been. The fact that commits get (roughtly) 
> sorted by date (modified by their ancestry relationships either subtly or 
> grossly depending on whether --topo-sort is off or on) does not make 
> anything linear.

Note that totally independently of sort order (whether "topo-order" or the 
normal cheaper "order by date, but at least one chain of parenthood always 
first"), you _will_ get the situation that a commit that was shown "last" 
in a linear list is actually merged long before.

The simplest case is this:

		merge
		 |  \
		 A   \
		 |    \
		 B     \
		 |      X
		 C      |
		 |	Y
		 D	|
		 |      Z
		..	..

where the "main branch" is the A-B-C-D.. line of history, and the merge 
brings in another "X-Y-Z" line of history.

Now, the A-B-C branch may have gotten a lot more recent love and 
attention, and when you linearize it, since the normal ordering tends to 
show it in a date-like order, you may get a list of commits like

		merge
		A
		B
		C
		D
		..
		X
		Y
		Z
		..


which makes you think that "A" is much more recent than "X". That may be 
actually be _true_, but:

 - 'X' actually _showed_up_ in the mainline much later than A. So, if you 
   track another persons tree like this, X as a commit may be 2 weeks old, 
   but it might not have been in the tree you tracked yesterday, because 
   it hadn't been _merged_ until today.

   So in a very real sense, from your standpoint, 'X' may be the 'recent' 
   one, because you hadn't seen it before, but you _had_ seen 'A' 
   yesterday.

 - Equally importantly, 'A' very much is _not_ a descendant of 'X' (ie, 
   'X' is _not_ reachable from 'A'). So even though 'A' is in a time-sense 
   much more recent than 'X', you can't say "it's the most recent commit, 
   so if there's a bug in any of the series, the bug must have been 
   visible at point 'A'".

This is why it's wrong to look at _any_ linearized list of commits and 
imply any ordering what-so-ever. There simply is no list ordering that 
guarantees anything at all, because even with "topo-sort", the only thing 
we guarantee is that commits that are directly related to each other will 
always sort the child before its parents. So even there, you can't 
actually say that one commit "dominates" another commit unless you end up 
looking at the parenthood chain (and merges are really important).

[ Strictly speaking, there is exactly _one_ thing you can say from just 
  seeing a list of commits: _if_ that list includes all types of commits 
  (ie notably merges and empty changes) _and_ if that list was generated 
  with just one "top" commit, then the first commit on the list will 
  dominate all other commits. But that's literally the only real ordering 
  you can ever know from just a list.

  So looking at the first commit in a list is actually valid, but only if 
  you included all the merges and only if the list was generated by a git 
  command, and not sorted by any other criteria ]

			Linus