git bisect and the merge from hell

git bisect and the merge from hell

[Luck, Tony]

Sometime between -rc1 and -rc2 the ia64 kernel picked up a bug
that prevents booting a UP kernel on my workstation (I recycled
the serial cable to hook up a new machine, so I don't have the
OOPS).

So I thought I'd use git bisect to narrow it down.  A few iterations
in it picked the merge from hell, and two iterations after that it
appears to have wandered into the weeds and picked something from
before -rc1.

 $ git describe 3c5c363826e435cf4d54d917202567e5b57cae5f
 v2.6.15-g3c5c3638

Is this normal?

A couple of iterations down (with git bisect saying that we were into
the home stretch with only 5 commits to go) I ran into build problems,
so I haven't yet got to the bottom of the problem).

Here's the BISECT_LOG:
git-bisect start
# bad: [826eeb53a6f264842200d3311d69107d2eb25f5e] Linux v2.6.16-rc2
git-bisect bad 826eeb53a6f264842200d3311d69107d2eb25f5e
# good: [2664b25051f7ab96b22b199aa2f5ef6a949a4296] Linux v2.6.16-rc1
git-bisect good 2664b25051f7ab96b22b199aa2f5ef6a949a4296
# good: [10379a25fee8ddc8698d2f6c54ccedd4664c2941] Merge master.kernel.org:/pub/scm/linux/kernel/git/davej/agpgart
git-bisect good 10379a25fee8ddc8698d2f6c54ccedd4664c2941
# good: [9a2dba4b4912b493070cbc170629fdbf440b01d7] slab: rename ac_data to cpu_cache_get
git-bisect good 9a2dba4b4912b493070cbc170629fdbf440b01d7
# good: [9ad11ab48b1ad618bf47076e9e579f267f5306c2] compat: fix compat_sys_openat and friends
git-bisect good 9ad11ab48b1ad618bf47076e9e579f267f5306c2
# good: [1494a92f4c2b1d5abdaa1f823dd19f797bb137de] [ALSA] hda-codec - Fix typos in alc882 model table
git-bisect good 1494a92f4c2b1d5abdaa1f823dd19f797bb137de
# bad: [9fdb62af92c741addbea15545f214a6e89460865] [ACPI] merge 3549 4320 4485 4588 4980 5483 5651 acpica asus fops pnpacpi branches into release
git-bisect bad 9fdb62af92c741addbea15545f214a6e89460865
# bad: [3c5c363826e435cf4d54d917202567e5b57cae5f] [ACPI] delete message "**** SET: Misaligned resource pointer:"
git-bisect bad 3c5c363826e435cf4d54d917202567e5b57cae5f
# bad: [c51a4de85de720670f2fbc592a6f8040af72ad87] [ACPI] ACPICA 20051117
git-bisect bad c51a4de85de720670f2fbc592a6f8040af72ad87

Git version is 1.1.4

-Tony

Re: git bisect and the merge from hell

[Junio C Hamano]

"Luck, Tony" <tony.luck@intel.com> writes:

> Sometime between -rc1 and -rc2 the ia64 kernel picked up a bug
> that prevents booting a UP kernel on my workstation (I recycled
> the serial cable to hook up a new machine, so I don't have the
> OOPS).
>
> So I thought I'd use git bisect to narrow it down.  A few iterations
> in it picked the merge from hell, and two iterations after that it
> appears to have wandered into the weeds and picked something from
> before -rc1.
>
>  $ git describe 3c5c363826e435cf4d54d917202567e5b57cae5f
>  v2.6.15-g3c5c3638
>
> Is this normal?

I haven't looked at your ancestry graph yet (I am at work
writing this message during my lunch break), but if one of the
branches merged between rc1 and rc2 were forked from the
mainline at a commit before rc1, that is an expected behaviour.
Suppose:

       .o---o---o--- ... ---o---o.
      /                           \
     /                             \
 ---o---o---*---o--- ... ---o---o---*---o---o---*
            rc1                     octopus     rc2

And you said "rc1 was OK but rc2 is BAD".  Now, the bug may well
be somewhere between rc1 and Len's octopus on the lower
development track.  But the problem may have been introduced by
some of the commits on the upper development track that bypassed
rc1.  They are not descendant of rc1, and describe would say
they come after v2.6.15.

The side branch merged during that timeperiod that forked before
rc1 may not be the one merged by Len's octopus but may be merged
by some other merge, but the story is the same.

Re: git bisect and the merge from hell

[Linus Torvalds]

On Fri, 3 Feb 2006, Luck, Tony wrote:
>
> Sometime between -rc1 and -rc2 the ia64 kernel picked up a bug
> that prevents booting a UP kernel on my workstation (I recycled
> the serial cable to hook up a new machine, so I don't have the
> OOPS).
> 
> So I thought I'd use git bisect to narrow it down.  A few iterations
> in it picked the merge from hell, and two iterations after that it
> appears to have wandered into the weeds and picked something from
> before -rc1.
>
>  $ git describe 3c5c363826e435cf4d54d917202567e5b57cae5f
>  v2.6.15-g3c5c3638
> 
> Is this normal?

That commit _is_ in between v2.6.16-rc1 and -r2:

  [torvalds@g5 linux]$ git-rev-list v2.6.16-rc1..v2.6.16-rc2 | grep 3c5c363826e435
  3c5c363826e435cf4d54d917202567e5b57cae5f

but it came through a merge, so the history isn't linear. That commit does 
not actually ever reach 2.6.16-rc1 in its history.

Use "git bisect visualize" to see what "git bisect" is doing. It's doing 
everything right so far..

> A couple of iterations down (with git bisect saying that we were into
> the home stretch with only 5 commits to go) I ran into build problems,
> so I haven't yet got to the bottom of the problem).

Ok. That's a different issue. 

When you hit a problem where "git bisect" will pick a place that doesn't 
compile (usually for some stupid reason that you're not at all 
interested in chasing down), what you should do is

	git bisect visualize

to see what commits are interesting.

Then, pick one of the interesting ones "at random" (it helps if it's not 
close to any of the known-uninteresting points), and do

	git reset --hard <picked-sha1>

and try that instead (and compile that, and just continue with your 
bisection: mark it good or bad depending on whether it works).

Basically, what you're doing is to override the choice of place to test 
that "git bisect" chose automatically for you. It still works, but 
obviously the point is probably not as "half-way" any more, so it makes 
the narrowing down of the bad commit slightly less efficient.

> Here's the BISECT_LOG:

Ok, you've done great progress. You only have 11 revisions left to test 
(the last message would have been "5 revisions left to test after this", 
but that means that _after_ you've verified the picked point, you'd have 
had just five versions left.

"git bisect visualize" really makes it very obvious what to try next, I 
think. Which exact commit you try next probably depends on what the 
compile error was. I'd try

	git reset --hard 3d5271f9883cba7b54762bc4fe027d4172f06db7

(which is after the "pull release into acpica branch" commit).

		Linus

RE: git bisect and the merge from hell

[Luck, Tony]

> "git bisect visualize" really makes it very obvious what to try next, I 
> think. Which exact commit you try next probably depends on what the 
> compile error was. I'd try
>
>	git reset --hard 3d5271f9883cba7b54762bc4fe027d4172f06db7
>
> (which is after the "pull release into acpica branch" commit).

Yup, that got the bisection moving again.  I finished up at:

$ git bisect bad
96db255c8f014ae3497507104e8df809785a619f is first bad commit
diff-tree 96db255c8f014ae3497507104e8df809785a619f (from 0897831bb54eb36fd9e2a22da7f0f64be1b20d09)
Author: Bob Moore <robert.moore@intel.com>
Date:   Wed Nov 2 00:00:00 2005 -0500

    [ACPI] ACPICA 20051102

So Len's mega-octopus merge wasn't a problem at all, but this is still
all his fault :-)  I'll go beat on him.

Thanks for the tip.

-Tony

RE: git bisect and the merge from hell

[Linus Torvalds]

On Fri, 3 Feb 2006, Luck, Tony wrote:
> 
> So Len's mega-octopus merge wasn't a problem at all, but this is still
> all his fault :-)  I'll go beat on him.

Note that this _can_ be a problem with huge octopus merges.

If some bug only appears as a result of the interaction of two branches, 
doing a 12-way merge will make it harder to debug. Doing a "git bisect" 
will (correctly) pinpoint the merge as being the problem, but after that 
you're on your own as to how to debug it.

So _if_ it had been a merge error, there's two issues with that:

 - debugging merges is usually a bit less straightforward than debugging a 
   single well-defined changeset anyway.

 - especially an octopus-merge will cause "git-bisect" to be less 
   efficient, since it cannot be bisected, so if the bug is in the merge 
   itself, it will ask you to test _every_ _single_ top-of-branch before 
   the merge.

(Normally, testing 12 kernels would zoom in on a bug from 10.000 feet, and 
you'd have bisected a massive four-thousand commits. So having to test 12 
branch heads just to pinpoint a _single_ commit is "unusually expensive" 
by any standard for git bisection).

Anyway, had it been a merge bug, you should then have done:

 - check if it's simply a mis-merge. Do "git-diff-tree --cc" to see if 
   there were any conflicts, and check them out more closely to see 
   if maybe they were incorrectly fixed up.

   Normally, an octopus merge will never have any actual _manual_ 
   conflicts (the standard git tools shouldn't allow it), but there can 
   still be several branches that touch the same area and that could have 
   merged strangely.

If that doesn't get you anywhere, you'll literally have to go to the next 
step:

 - re-do the merges one by one, until the bug appears, or, if it's not 
   there once you've re-done them all, check what the differences are 
   (there _should_ be none, but see above on doing mis-merging) with the 
   final octopus one.

Anyway, for "normal" bugs (like this one apparently is), git-bisect 
shouldn't ever pinpoint a merge, since the bug hopefully was introduced 
somewhere _during_ the branch development, and not when it was merged 
back. Hopefully.

Anyway. The message you should take home from this is that "git bisect" 
handles merges perfectly well, and that at worst it might be less 
efficient and harder to debug - especially for octopus merges - but that 
both of those problems are likely (a) rare and (b) not insurmountable.

		Linus