Article about "git bisect run" on LWN

Hi,

For information, an article from me, 'Fully automated bisecting with "git 
bisect run"' has been published in today's edition of LWN on the 
development page:

http://lwn.net/Articles/317154/

Thank you guys,
Christian.

On Thursday, February 5, 2009 at 07:47:49 (+0100) Christian Couder writes:

Hi,

For information, an article from me, 'Fully automated bisecting with "git 
bisect run"' has been published in today's edition of LWN on the 
development page:

http://lwn.net/Articles/317154/

Wow, very nice Christian.  Thank you for including me in the article
and for sending me this notice --- very thoughtful of you.


Bill

* Christian Couder [off-list ref] wrote:

Hi,

For information, an article from me, 'Fully automated bisecting with "git 
bisect run"' has been published in today's edition of LWN on the 
development page:

http://lwn.net/Articles/317154/

Nice article!

In terms of possible future enhancements of git bisect, here's a couple of 
random ideas that would help my auto-bisection efforts:

 - Feature: support "Bisection Redundancy"

   This feature helps developers realize if a bug is sporadic. This happens 
   quite often in the kernel space: a bug looks deterministic, but down the 
   line it becomes sporadic. Sometimes a boot crash only occurs with a 75% 
   probability - and if one is unlucky it can cause a _lot_ of wasted 
   bisection time. The wrong commit gets blamed and the wrong set of 
   developers start scratching their heads. It's a reoccuring theme on lkml.

   What git could do here is to allow testers to inject a bit of extra 
   "redundancy" automatically, and use the redundant test-points to detect 
   conflicts in good/bad constraints.

   It would work like this:

      git bisect start --redundancy=33%

   It would mean that for every third bisection points, Git would
   _not_ chose the ideal (estimated) 'middle point' from the set of "unknown 
   quality" changes that are still outstanding - but would intentionally 
   "weer outside" and select one commit from the _known_ set of commits.

   If such a redundant re-test of the known-good or known-bad set yields a 
   nonsensical result then Git aborts the bisection with a "logic
   inconsistency detected" kind of message - and people could at this point
   realize the non-determinism of the test.

   ( Git can do this when a "redundant" test point is marked as 'bad' - 
     despite an earlier bisection already categorizing that test point as 
     'good' - or if it's the other way around. Git will only continue with 
     the bisection if the test point has the expected quality. )

   This essentially means an automated re-test - but it's much better than 
   just a repeated bisection - i've often met non-deterministic bugs that 
   yield the _exact same_ nonsensical commit even on repeat bisections. That 
   happens when a timing bug depends on the exact kernel layout, or a 
   miscompilation or linker bug depends on the exact kernel layout, etc.

   It's also faster than a re-done bisection: 33% more testpoints is better 
   than twice as many test-points. Also, auto-bisection can deal with 
   redundancy just fine - it does not really matter whether i have to wait 
   20 or 30 minutes for a test result since there's no manual intervention 
   needed - but it _very_ much matters whether i can trust the validity of 
   the bisection result.

- Feature: better "git bisect next" support.

  Sometimes a commit wont build. In that case we have "git bisect next", but 
  last i checked that only jumps a single commit - and build breakages 
  often have a large scope - full trees that got merged upstream, etc. Most 
  of the time those build breakages are uninteresting and the build-broken 
  window does not contain the bad commit.

  So it would be nice to have a "git bisect next --left=20%" type of 
  feature. This would jump 20% commits to the "left" from the bisection 
  point, towards the 'known bad' set of commits, but still within the 
  bisection window.

  Similarly, "git bisect next --right=20%" would jump towards the known-good 
  edge of the bisection window (but still within the bisection window).

  Currently when i hit a build error during auto-bisection, it aborts and i 
  have to intervene manually. But with a bigger jump distance i could use
  git-bisect-next reliably in scripts too.

  Likewise, users too hit build breakages often, and find it hard to get out 
  of the window of breakage. With the high-order tree structure of the 
  kernel repository that is rather non-intuitive to do as well, and often 
  people make mistakes and test the wrong commit.

- Feature: detect "redundant" and "inconsistent" test points

  This is a variation of the redunant testing theme, but from a different 
  angle: often newbies when they bisect the kernel weer outside of the 
  bisection window without realizing it. It would be nice if Git printed a 
  friendly notifier that:

     git bisect good 12341234
     info: bisection point 12341234 was already in the 'good' range

  Or, if the redunant test point is conflicting, print:

     git bisect good 12341234
     fatal: bisection point 12341234 was already in the 'bad' range!

  And give an error return as well, so that scripts can abort.

  Currently Git seems to be very forgiving and accepts all bisection points 
  that we feed it, without checking them for consistency. (this might have 
  changed in current development versions, i dont know.)

- User friendliness: give an estimation about how many steps are remaining

  Right now git prints this when a bisection session begins:

     aldebaran:~/tip> git bisect start
     aldebaran:~/tip> git bisect bad linus
     aldebaran:~/tip> git bisect good v2.6.28
     Bisecting: 5449 revisions left to test after this
     [e0b685d39a0404e7f87fb7b7808c3b37a115fe11] Updated contact info for CREDITS file

  It would be nice if Git estimated the expected number of bisection points. 
  Something like this would be helpful:

     aldebaran:~/tip> git bisect good v2.6.28
     Bisecting: 5449 revisions left to test after this
                About ~16 test steps left [approximated]
     [e0b685d39a0404e7f87fb7b7808c3b37a115fe11] Updated contact info for CREDITS file

  The real number of test points might be higher than this, if the tree 
  layout is unlucky, or it might be less than this if the user manually 
  narrows the bisection window to a suspected set of commits - but that's 
  OK - most kernel testers use the default variant and the message is clear 
  enough that it's only an estimation.

	Ingo

On Thu, 5 Feb 2009 07:47:49 +0100
Christian Couder [off-list ref] wrote:

For information, an article from me, 'Fully automated bisecting with
"git bisect run"' has been published in today's edition of LWN on the 
development page:

http://lwn.net/Articles/317154/

For those of you lacking an LWN subscription, please follow this link
instead:

	http://lwn.net/SubscriberLink/317154/c49a5d1a14050820/

Thanks to Christian for doing this article for us!

jon

Le jeudi 5 février 2009, Jonathan Corbet a écrit :

On Thu, 5 Feb 2009 07:47:49 +0100

For those of you lacking an LWN subscription, please follow this link
instead:

	http://lwn.net/SubscriberLink/317154/c49a5d1a14050820/

Thanks to Christian for doing this article for us!

Thank you Jon for publishing this article and for the subscriber link.
And thank you Jake for your help in writing this article.

Best regards,
Christian.

On Thu, 5 Feb 2009, Ingo Molnar wrote:

* Christian Couder [off-list ref] wrote:

quoted

Hi,

For information, an article from me, 'Fully automated bisecting with "git
bisect run"' has been published in today's edition of LWN on the
development page:

http://lwn.net/Articles/317154/

Nice article!

In terms of possible future enhancements of git bisect, here's a couple of
random ideas that would help my auto-bisection efforts:

- Feature: support "Bisection Redundancy"

  This feature helps developers realize if a bug is sporadic. This happens
  quite often in the kernel space: a bug looks deterministic, but down the
  line it becomes sporadic. Sometimes a boot crash only occurs with a 75%
  probability - and if one is unlucky it can cause a _lot_ of wasted
  bisection time. The wrong commit gets blamed and the wrong set of
  developers start scratching their heads. It's a reoccuring theme on lkml.

  What git could do here is to allow testers to inject a bit of extra
  "redundancy" automatically, and use the redundant test-points to detect
  conflicts in good/bad constraints.

  It would work like this:

     git bisect start --redundancy=33%

  It would mean that for every third bisection points, Git would
  _not_ chose the ideal (estimated) 'middle point' from the set of "unknown
  quality" changes that are still outstanding - but would intentionally
  "weer outside" and select one commit from the _known_ set of commits.

  If such a redundant re-test of the known-good or known-bad set yields a
  nonsensical result then Git aborts the bisection with a "logic
  inconsistency detected" kind of message - and people could at this point
  realize the non-determinism of the test.

  ( Git can do this when a "redundant" test point is marked as 'bad' -
    despite an earlier bisection already categorizing that test point as
    'good' - or if it's the other way around. Git will only continue with
    the bisection if the test point has the expected quality. )

  This essentially means an automated re-test - but it's much better than
  just a repeated bisection - i've often met non-deterministic bugs that
  yield the _exact same_ nonsensical commit even on repeat bisections. That
  happens when a timing bug depends on the exact kernel layout, or a
  miscompilation or linker bug depends on the exact kernel layout, etc.

  It's also faster than a re-done bisection: 33% more testpoints is better
  than twice as many test-points. Also, auto-bisection can deal with
  redundancy just fine - it does not really matter whether i have to wait
  20 or 30 minutes for a test result since there's no manual intervention
  needed - but it _very_ much matters whether i can trust the validity of
  the bisection result.

when you gave this the title of redundnancy and described the problem I 
assumed that you would then propose running the test multiple times (so 
"git bisect run X --redundancy 5" would run each test 5 times, it would 
pass IFF it passed the test all 5 times. that would seem to be a better 
match for the name, as well as being a better test

David Lang

On Thu, 5 Feb 2009, Jonathan Corbet wrote:

On Thu, 5 Feb 2009 07:47:49 +0100
Christian Couder [off-list ref] wrote:

quoted

For information, an article from me, 'Fully automated bisecting with
"git bisect run"' has been published in today's edition of LWN on the
development page:

http://lwn.net/Articles/317154/

For those of you lacking an LWN subscription, please follow this link
instead:

	http://lwn.net/SubscriberLink/317154/c49a5d1a14050820/

Thanks to Christian for doing this article for us!

and since Jon was too professional to put in a plug himself, I'll do it 
for him ;-)

if you aren't a subscriber, consider subscribing (the 'starving-hacker' 
level is only $2.50USD/month)

David Lang

* david@lang.hm [off-list ref] wrote:

On Thu, 5 Feb 2009, Ingo Molnar wrote:

quoted

* Christian Couder [off-list ref] wrote:

quoted

Hi,

For information, an article from me, 'Fully automated bisecting with "git
bisect run"' has been published in today's edition of LWN on the
development page:

http://lwn.net/Articles/317154/

Nice article!

In terms of possible future enhancements of git bisect, here's a couple of
random ideas that would help my auto-bisection efforts:

- Feature: support "Bisection Redundancy"

  This feature helps developers realize if a bug is sporadic. This happens
  quite often in the kernel space: a bug looks deterministic, but down the
  line it becomes sporadic. Sometimes a boot crash only occurs with a 75%
  probability - and if one is unlucky it can cause a _lot_ of wasted
  bisection time. The wrong commit gets blamed and the wrong set of
  developers start scratching their heads. It's a reoccuring theme on lkml.

  What git could do here is to allow testers to inject a bit of extra
  "redundancy" automatically, and use the redundant test-points to detect
  conflicts in good/bad constraints.

  It would work like this:

     git bisect start --redundancy=33%

  It would mean that for every third bisection points, Git would
  _not_ chose the ideal (estimated) 'middle point' from the set of "unknown
  quality" changes that are still outstanding - but would intentionally
  "weer outside" and select one commit from the _known_ set of commits.

  If such a redundant re-test of the known-good or known-bad set yields a
  nonsensical result then Git aborts the bisection with a "logic
  inconsistency detected" kind of message - and people could at this point
  realize the non-determinism of the test.

  ( Git can do this when a "redundant" test point is marked as 'bad' -
    despite an earlier bisection already categorizing that test point as
    'good' - or if it's the other way around. Git will only continue with
    the bisection if the test point has the expected quality. )

  This essentially means an automated re-test - but it's much better than
  just a repeated bisection - i've often met non-deterministic bugs that
  yield the _exact same_ nonsensical commit even on repeat bisections. That
  happens when a timing bug depends on the exact kernel layout, or a
  miscompilation or linker bug depends on the exact kernel layout, etc.

  It's also faster than a re-done bisection: 33% more testpoints is better
  than twice as many test-points. Also, auto-bisection can deal with
  redundancy just fine - it does not really matter whether i have to wait
  20 or 30 minutes for a test result since there's no manual intervention
  needed - but it _very_ much matters whether i can trust the validity of
  the bisection result.

when you gave this the title of redundnancy and described the problem I  
assumed that you would then propose running the test multiple times (so  
"git bisect run X --redundancy 5" would run each test 5 times, it would  
pass IFF it passed the test all 5 times. that would seem to be a better  
match for the name, as well as being a better test

Yeah, but using 100%, 200%, 300%, etc. redundancy is a bit wasteful and not 
granular enough for my purposes.

Here's the math:

A typical kernel bisection takes 15 test steps. 30% of redundancy means that 
it takes only 30% longer, but for that we get +5 tests. Five extra test 
points are usually enough to establish whether a test method shows sporadic 
tendencies or not, with an ~90% confidence factor.

Repeating the test 5 times would bring a 15-steps kernel bisection from 30 
minutes [it's about 60 seconds to build a kernel, 60 seconds to boot it] to 
about 2.5 hours - that's very long. The confidence factor only goes from 
~90% to 99% - that extra 9% is not worth the cost.

The idea would be to insert 30% redunancy into my bisections automatically - 
so that i could trust _all_ bisections more - not just the ones i suspect to 
be non-deterministic. Hence the suggestion to enable lower levels of 
redundancy like 30%. (but even 10% or 20% might be enough to weed out the 
most obvious cases)

	Ingo

* Ingo Molnar [off-list ref] wrote:

The idea would be to insert 30% redunancy into my bisections automatically 
- so that i could trust _all_ bisections more - not just the ones i 
suspect to be non-deterministic. Hence the suggestion to enable lower 
levels of redundancy like 30%. (but even 10% or 20% might be enough to 
weed out the most obvious cases)

the other advantage of redundancy that i forgot to mention:

- Sometimes the non-determinism is inserted by a _human_. It happened not
  once that i accidentally mis-judged a testpoint, and the bisection ran
  afoul. Only 4-5 steps later do i suspect that something is wrong: that i 
  get an unlikely series of good,good,good,good,good or bad,bad,bad,bad,bad 
  testpoint qualities.

So for manual bisection, redundancy can be a big time-saver. If i mess up a 
bisection point then say 50% redundancy can still point out my stupidity 
with a high likelyhood.

In fact if Git sees an unlikely series of same-quality bisection points, it 
could artificially insert a test to around the last-different test point, to 
test the theory of a messed up bisection.

	Ingo

Le jeudi 5 février 2009, Ingo Molnar a écrit :

* Christian Couder [off-list ref] wrote:

quoted

Hi,

For information, an article from me, 'Fully automated bisecting with
"git bisect run"' has been published in today's edition of LWN on the
development page:

http://lwn.net/Articles/317154/

Nice article!

In terms of possible future enhancements of git bisect, here's a couple
of random ideas that would help my auto-bisection efforts:

 - Feature: support "Bisection Redundancy"

   This feature helps developers realize if a bug is sporadic. This
happens quite often in the kernel space: a bug looks deterministic, but
down the line it becomes sporadic. Sometimes a boot crash only occurs
with a 75% probability - and if one is unlucky it can cause a _lot_ of
wasted bisection time. The wrong commit gets blamed and the wrong set of
developers start scratching their heads. It's a reoccuring theme on lkml.

   What git could do here is to allow testers to inject a bit of extra
   "redundancy" automatically, and use the redundant test-points to
detect conflicts in good/bad constraints.

   It would work like this:

      git bisect start --redundancy=33%

   It would mean that for every third bisection points, Git would
   _not_ chose the ideal (estimated) 'middle point' from the set of
"unknown quality" changes that are still outstanding - but would
intentionally "weer outside" and select one commit from the _known_ set
of commits.

   If such a redundant re-test of the known-good or known-bad set yields
a nonsensical result then Git aborts the bisection with a "logic
inconsistency detected" kind of message - and people could at this point
realize the non-determinism of the test.

   ( Git can do this when a "redundant" test point is marked as 'bad' -
     despite an earlier bisection already categorizing that test point as
     'good' - or if it's the other way around. Git will only continue
with the bisection if the test point has the expected quality. )

   This essentially means an automated re-test - but it's much better
than just a repeated bisection - i've often met non-deterministic bugs
that yield the _exact same_ nonsensical commit even on repeat bisections.
That happens when a timing bug depends on the exact kernel layout, or a
miscompilation or linker bug depends on the exact kernel layout, etc.

   It's also faster than a re-done bisection: 33% more testpoints is
better than twice as many test-points. Also, auto-bisection can deal with
redundancy just fine - it does not really matter whether i have to wait
20 or 30 minutes for a test result since there's no manual intervention
needed - but it _very_ much matters whether i can trust the validity of
the bisection result.

I see. With the current code it seems difficult to have a "weer outside" 
algorithm, but if the "git bisect skip" code is ported (from shell 
in "git-bisect.sh") to C in "builtin-rev-list.c", that might be doable. And 
anyway moving the bisect skip code to C is needed for other improvements.

- Feature: better "git bisect next" support.

You probably mean "git bisect skip" here.

  Sometimes a commit wont build. In that case we have "git bisect next",
but last i checked that only jumps a single commit - and build breakages 
often have a large scope - full trees that got merged upstream, etc. Most
of the time those build breakages are uninteresting and the build-broken
window does not contain the bad commit.

  So it would be nice to have a "git bisect next --left=20%" type of
  feature. This would jump 20% commits to the "left" from the bisection
  point, towards the 'known bad' set of commits, but still within the
  bisection window.

  Similarly, "git bisect next --right=20%" would jump towards the
known-good edge of the bisection window (but still within the bisection
window).

In the following thread, H. Peter Anvin suggested an algorithm to deal with 
this kind of problem:

http://thread.gmane.org/gmane.comp.version-control.git/98164/

And I suggested a simpler one, that might be implemented without having to 
port "git bisect skip" code to C first, but I did not work on it yet.

  Currently when i hit a build error during auto-bisection, it aborts and
i have to intervene manually. But with a bigger jump distance i could use
git-bisect-next reliably in scripts too.

  Likewise, users too hit build breakages often, and find it hard to get
out of the window of breakage. With the high-order tree structure of the
kernel repository that is rather non-intuitive to do as well, and often
people make mistakes and test the wrong commit.

I am working slowly on "git replace" these days and, if everything goes 
well, it should make it possible to use "replace" refs when bisecting, so 
that people could bisect on commit trees where many breakages have been 
removed. And as refs can be shared, this means that users and developers 
should be able to easily share these improved trees.

Another way to work around breakages could be to have a list of commits and 
ranges of commits that should always be skipped and always pass them 
to "git bisect skip" before using "git bisect run". Something like that 
perhaps:

$ git bisect start <bad> <good>
$ git bisect skip $(cat always_skipped.txt)
$ git bisect run ./my_test_script.sh

But I agree that it would also be a good thing to have an improved "git 
bisect skip" that could jump out of breakage windows.

- Feature: detect "redundant" and "inconsistent" test points

  This is a variation of the redunant testing theme, but from a different
  angle: often newbies when they bisect the kernel weer outside of the
  bisection window without realizing it. It would be nice if Git printed
a friendly notifier that:

     git bisect good 12341234
     info: bisection point 12341234 was already in the 'good' range

I agree that it would be nice. And it might be easy to implement.

  Or, if the redunant test point is conflicting, print:

     git bisect good 12341234
     fatal: bisection point 12341234 was already in the 'bad' range!

  And give an error return as well, so that scripts can abort.

  Currently Git seems to be very forgiving and accepts all bisection
points that we feed it, without checking them for consistency. (this
might have changed in current development versions, i dont know.)

I don't think conflicting test points are accepted. An error should be 
reported (with exit code 1), like this:

$ git bisect start HEAD~5 HEAD
Some good revs are not ancestor of the bad rev.
git bisect cannot work properly in this case.
Maybe you mistake good and bad revs?

- User friendliness: give an estimation about how many steps are
remaining

  Right now git prints this when a bisection session begins:

     aldebaran:~/tip> git bisect start
     aldebaran:~/tip> git bisect bad linus
     aldebaran:~/tip> git bisect good v2.6.28
     Bisecting: 5449 revisions left to test after this
     [e0b685d39a0404e7f87fb7b7808c3b37a115fe11] Updated contact info for
CREDITS file

  It would be nice if Git estimated the expected number of bisection
points. Something like this would be helpful:

     aldebaran:~/tip> git bisect good v2.6.28
     Bisecting: 5449 revisions left to test after this
                About ~16 test steps left [approximated]
     [e0b685d39a0404e7f87fb7b7808c3b37a115fe11] Updated contact info for
CREDITS file

  The real number of test points might be higher than this, if the tree
  layout is unlucky, or it might be less than this if the user manually
  narrows the bisection window to a suspected set of commits - but that's
  OK - most kernel testers use the default variant and the message is
clear enough that it's only an estimation.

I will have a look at that. It might be easy to do.

Thanks,
Christian.

Le vendredi 6 février 2009, Christian Couder a écrit :

Le jeudi 5 février 2009, Ingo Molnar a écrit :

quoted

- Feature: better "git bisect next" support.

You probably mean "git bisect skip" here.

quoted

  Sometimes a commit wont build. In that case we have "git bisect
next", but last i checked that only jumps a single commit - and build
breakages often have a large scope - full trees that got merged
upstream, etc. Most of the time those build breakages are uninteresting
and the build-broken window does not contain the bad commit.

  So it would be nice to have a "git bisect next --left=20%" type of
  feature. This would jump 20% commits to the "left" from the bisection
  point, towards the 'known bad' set of commits, but still within the
  bisection window.

  Similarly, "git bisect next --right=20%" would jump towards the
known-good edge of the bisection window (but still within the bisection
window).

In the following thread, H. Peter Anvin suggested an algorithm to deal
with this kind of problem:

http://thread.gmane.org/gmane.comp.version-control.git/98164/

And I suggested a simpler one, that might be implemented without having
to port "git bisect skip" code to C first, but I did not work on it yet.

quoted

  Currently when i hit a build error during auto-bisection, it aborts
and i have to intervene manually. But with a bigger jump distance i
could use git-bisect-next reliably in scripts too.

  Likewise, users too hit build breakages often, and find it hard to
get out of the window of breakage. With the high-order tree structure
of the kernel repository that is rather non-intuitive to do as well,
and often people make mistakes and test the wrong commit.

I am working slowly on "git replace" these days and, if everything goes
well, it should make it possible to use "replace" refs when bisecting, so
that people could bisect on commit trees where many breakages have been
removed. And as refs can be shared, this means that users and developers
should be able to easily share these improved trees.

Another way to work around breakages could be to have a list of commits
and ranges of commits that should always be skipped and always pass them
to "git bisect skip" before using "git bisect run". Something like that
perhaps:

$ git bisect start <bad> <good>
$ git bisect skip $(cat always_skipped.txt)
$ git bisect run ./my_test_script.sh

It might be useful to have a list of always good commits too, and use it 
like this:

$ git bisect start <bad> <good> $(cat always_good.txt)
$ git bisect skip $(cat always_skipped.txt)
$ git bisect run ./my_test_script.sh

or you may want to use grafts in your bisection repository. See the 
following thread about bisection breakage in the btrfs history:

http://thread.gmane.org/gmane.comp.version-control.git/105186/

Regards,
Christian.

On Sat, Feb 7, 2009 at 3:41 PM, Christian Couder
[off-list ref] wrote:

It might be useful to have a list of always good commits too, and use it
like this:

$ git bisect start <bad> <good> $(cat always_good.txt)
$ git bisect skip $(cat always_skipped.txt)
$ git bisect run ./my_test_script.sh

Your test script could just do this at its start instead:

  if cat always_good.txt | grep $(rev-parse HEAD); then
    exit 0
  elif cat always_skipped.txt | grep $(rev-parse HEAD); then
    exit 125
  fi


Dave.

Le samedi 7 février 2009, David Symonds a écrit :

On Sat, Feb 7, 2009 at 3:41 PM, Christian Couder

[off-list ref] wrote:

quoted

It might be useful to have a list of always good commits too, and use
it like this:

$ git bisect start <bad> <good> $(cat always_good.txt)
$ git bisect skip $(cat always_skipped.txt)
$ git bisect run ./my_test_script.sh

Your test script could just do this at its start instead:

  if cat always_good.txt | grep $(rev-parse HEAD); then
    exit 0

This won't work, because when you give one good rev, you say that all the 
ancestors of this rev are good (not just that the rev you give is good).

  elif cat always_skipped.txt | grep $(rev-parse HEAD); then
    exit 125
  fi

If you have a range like v1..v2 in "always_skipped.txt" this won't work.
And anyway it may be less efficient because it may perform many useless 
checkouts.

Regards,
Christian.