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/

> 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/

> * Christian Couder <chriscool@tuxfamily.org> 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.

> On Thu, 5 Feb 2009, Ingo Molnar wrote:
>
>> * Christian Couder <chriscool@tuxfamily.org> 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.
>
> 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

> 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)

> * Christian Couder <chriscool@tuxfamily.org> 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.

>   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.

> Le jeudi 5 février 2009, Ingo Molnar a écrit :
>
> > - 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

> 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

> On Sat, Feb 7, 2009 at 3:41 PM, Christian Couder
>
> <chriscool@tuxfamily.org> 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

> On Sat, Feb 7, 2009 at 3:41 PM, Christian Couder
> <chriscool@tuxfamily.org> 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

> David Symonds <dsymonds@gmail.com> writes:
> 
> > On Sat, Feb 7, 2009 at 3:41 PM, Christian Couder
> > <chriscool@tuxfamily.org> 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
> 
> Don't cat a file into grep, please.

> * Junio C Hamano <gitster@pobox.com> wrote:
> 
> > David Symonds <dsymonds@gmail.com> writes:
> > 
> > > On Sat, Feb 7, 2009 at 3:41 PM, Christian Couder
> > > <chriscool@tuxfamily.org> 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
> > 
> > Don't cat a file into grep, please.
> 
> I do it all the time not because i dont know about grep's ability
> to take a file parameter, but because this way it's just a
> special-case of command piping and i can inject other commands as
> i extend/edit the command line interactively, etc.

> On Tue, Feb 10, 2009 at 12:15 AM, Johannes Schindelin
>
> <Johannes.Schindelin@gmx.de> wrote:
> > I think Junio meant using '< $file' type redirection, to avoid an
> > unnecessary fork().  (Good habit, avoiding fork()s...)
>
> Yes, I usually pass filenames to grep; this time I was
> copy-and-pasting parts of the original script. But my point still
> remains: it seems it would be cleaner to do this kind of
> always-good-filtering in the test script rather than make git-bisect
> more complex.

> 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/

> 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!

> On Thu, 5 Feb 2009 07:47:49 +0100
> Christian Couder <chriscool@tuxfamily.org> 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!