msysGit-based Git for Windows 1.x was superseded by Git for Windows 2.x
[git/mingw/4msysgit.git] / Documentation / git-bisect-lk2009.txt
blobafeb86c6cd4ed695fd47019c016657fab217ac82
1 Fighting regressions with git bisect
2 ====================================
3 :Author: Christian Couder
4 :Email: chriscool@tuxfamily.org
5 :Date: 2009/11/08
7 Abstract
8 --------
10 "git bisect" enables software users and developers to easily find the
11 commit that introduced a regression. We show why it is important to
12 have good tools to fight regressions. We describe how "git bisect"
13 works from the outside and the algorithms it uses inside. Then we
14 explain how to take advantage of "git bisect" to improve current
15 practices. And we discuss how "git bisect" could improve in the
16 future.
19 Introduction to "git bisect"
20 ----------------------------
22 Git is a Distributed Version Control system (DVCS) created by Linus
23 Torvalds and maintained by Junio Hamano.
25 In Git like in many other Version Control Systems (VCS), the different
26 states of the data that is managed by the system are called
27 commits. And, as VCS are mostly used to manage software source code,
28 sometimes "interesting" changes of behavior in the software are
29 introduced in some commits.
31 In fact people are specially interested in commits that introduce a
32 "bad" behavior, called a bug or a regression. They are interested in
33 these commits because a commit (hopefully) contains a very small set
34 of source code changes. And it's much easier to understand and
35 properly fix a problem when you only need to check a very small set of
36 changes, than when you don't know where look in the first place.
38 So to help people find commits that introduce a "bad" behavior, the
39 "git bisect" set of commands was invented. And it follows of course
40 that in "git bisect" parlance, commits where the "interesting
41 behavior" is present are called "bad" commits, while other commits are
42 called "good" commits. And a commit that introduce the behavior we are
43 interested in is called a "first bad commit". Note that there could be
44 more than one "first bad commit" in the commit space we are searching.
46 So "git bisect" is designed to help find a "first bad commit". And to
47 be as efficient as possible, it tries to perform a binary search.
50 Fighting regressions overview
51 -----------------------------
53 Regressions: a big problem
54 ~~~~~~~~~~~~~~~~~~~~~~~~~~
56 Regressions are a big problem in the software industry. But it's
57 difficult to put some real numbers behind that claim.
59 There are some numbers about bugs in general, like a NIST study in
60 2002 <<1>> that said:
62 _____________
63 Software bugs, or errors, are so prevalent and so detrimental that
64 they cost the U.S. economy an estimated $59.5 billion annually, or
65 about 0.6 percent of the gross domestic product, according to a newly
66 released study commissioned by the Department of Commerce's National
67 Institute of Standards and Technology (NIST). At the national level,
68 over half of the costs are borne by software users and the remainder
69 by software developers/vendors.  The study also found that, although
70 all errors cannot be removed, more than a third of these costs, or an
71 estimated $22.2 billion, could be eliminated by an improved testing
72 infrastructure that enables earlier and more effective identification
73 and removal of software defects. These are the savings associated with
74 finding an increased percentage (but not 100 percent) of errors closer
75 to the development stages in which they are introduced. Currently,
76 over half of all errors are not found until "downstream" in the
77 development process or during post-sale software use.
78 _____________
80 And then:
82 _____________
83 Software developers already spend approximately 80 percent of
84 development costs on identifying and correcting defects, and yet few
85 products of any type other than software are shipped with such high
86 levels of errors.
87 _____________
89 Eventually the conclusion started with:
91 _____________
92 The path to higher software quality is significantly improved software
93 testing.
94 _____________
96 There are other estimates saying that 80% of the cost related to
97 software is about maintenance <<2>>.
99 Though, according to Wikipedia <<3>>:
101 _____________
102 A common perception of maintenance is that it is merely fixing
103 bugs. However, studies and surveys over the years have indicated that
104 the majority, over 80%, of the maintenance effort is used for
105 non-corrective actions (Pigosky 1997). This perception is perpetuated
106 by users submitting problem reports that in reality are functionality
107 enhancements to the system.
108 _____________
110 But we can guess that improving on existing software is very costly
111 because you have to watch out for regressions. At least this would
112 make the above studies consistent among themselves.
114 Of course some kind of software is developed, then used during some
115 time without being improved on much, and then finally thrown away. In
116 this case, of course, regressions may not be a big problem. But on the
117 other hand, there is a lot of big software that is continually
118 developed and maintained during years or even tens of years by a lot
119 of people. And as there are often many people who depend (sometimes
120 critically) on such software, regressions are a really big problem.
122 One such software is the linux kernel. And if we look at the linux
123 kernel, we can see that a lot of time and effort is spent to fight
124 regressions. The release cycle start with a 2 weeks long merge
125 window. Then the first release candidate (rc) version is tagged. And
126 after that about 7 or 8 more rc versions will appear with around one
127 week between each of them, before the final release.
129 The time between the first rc release and the final release is
130 supposed to be used to test rc versions and fight bugs and especially
131 regressions. And this time is more than 80% of the release cycle
132 time. But this is not the end of the fight yet, as of course it
133 continues after the release.
135 And then this is what Ingo Molnar (a well known linux kernel
136 developer) says about his use of git bisect:
138 _____________
139 I most actively use it during the merge window (when a lot of trees
140 get merged upstream and when the influx of bugs is the highest) - and
141 yes, there have been cases that i used it multiple times a day. My
142 average is roughly once a day.
143 _____________
145 So regressions are fought all the time by developers, and indeed it is
146 well known that bugs should be fixed as soon as possible, so as soon
147 as they are found. That's why it is interesting to have good tools for
148 this purpose.
150 Other tools to fight regressions
151 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
153 So what are the tools used to fight regressions? They are nearly the
154 same as those used to fight regular bugs. The only specific tools are
155 test suites and tools similar as "git bisect".
157 Test suites are very nice. But when they are used alone, they are
158 supposed to be used so that all the tests are checked after each
159 commit. This means that they are not very efficient, because many
160 tests are run for no interesting result, and they suffer from
161 combinational explosion.
163 In fact the problem is that big software often has many different
164 configuration options and that each test case should pass for each
165 configuration after each commit. So if you have for each release: N
166 configurations, M commits and T test cases, you should perform:
168 -------------
169 N * M * T tests
170 -------------
172 where N, M and T are all growing with the size your software.
174 So very soon it will not be possible to completely test everything.
176 And if some bugs slip through your test suite, then you can add a test
177 to your test suite. But if you want to use your new improved test
178 suite to find where the bug slipped in, then you will either have to
179 emulate a bisection process or you will perhaps bluntly test each
180 commit backward starting from the "bad" commit you have which may be
181 very wasteful.
183 "git bisect" overview
184 ---------------------
186 Starting a bisection
187 ~~~~~~~~~~~~~~~~~~~~
189 The first "git bisect" subcommand to use is "git bisect start" to
190 start the search. Then bounds must be set to limit the commit
191 space. This is done usually by giving one "bad" and at least one
192 "good" commit. They can be passed in the initial call to "git bisect
193 start" like this:
195 -------------
196 $ git bisect start [BAD [GOOD...]]
197 -------------
199 or they can be set using:
201 -------------
202 $ git bisect bad [COMMIT]
203 -------------
205 and:
207 -------------
208 $ git bisect good [COMMIT...]
209 -------------
211 where BAD, GOOD and COMMIT are all names that can be resolved to a
212 commit.
214 Then "git bisect" will checkout a commit of its choosing and ask the
215 user to test it, like this:
217 -------------
218 $ git bisect start v2.6.27 v2.6.25
219 Bisecting: 10928 revisions left to test after this (roughly 14 steps)
220 [2ec65f8b89ea003c27ff7723525a2ee335a2b393] x86: clean up using max_low_pfn on 32-bit
221 -------------
223 Note that the example that we will use is really a toy example, we
224 will be looking for the first commit that has a version like
225 "2.6.26-something", that is the commit that has a "SUBLEVEL = 26" line
226 in the top level Makefile. This is a toy example because there are
227 better ways to find this commit with Git than using "git bisect" (for
228 example "git blame" or "git log -S<string>").
230 Driving a bisection manually
231 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
233 At this point there are basically 2 ways to drive the search. It can
234 be driven manually by the user or it can be driven automatically by a
235 script or a command.
237 If the user is driving it, then at each step of the search, the user
238 will have to test the current commit and say if it is "good" or "bad"
239 using the "git bisect good" or "git bisect bad" commands respectively
240 that have been described above. For example:
242 -------------
243 $ git bisect bad
244 Bisecting: 5480 revisions left to test after this (roughly 13 steps)
245 [66c0b394f08fd89236515c1c84485ea712a157be] KVM: kill file->f_count abuse in kvm
246 -------------
248 And after a few more steps like that, "git bisect" will eventually
249 find a first bad commit:
251 -------------
252 $ git bisect bad
253 2ddcca36c8bcfa251724fe342c8327451988be0d is the first bad commit
254 commit 2ddcca36c8bcfa251724fe342c8327451988be0d
255 Author: Linus Torvalds <torvalds@linux-foundation.org>
256 Date:   Sat May 3 11:59:44 2008 -0700
258     Linux 2.6.26-rc1
260 :100644 100644 5cf82581... 4492984e... M      Makefile
261 -------------
263 At this point we can see what the commit does, check it out (if it's
264 not already checked out) or tinker with it, for example:
266 -------------
267 $ git show HEAD
268 commit 2ddcca36c8bcfa251724fe342c8327451988be0d
269 Author: Linus Torvalds <torvalds@linux-foundation.org>
270 Date:   Sat May 3 11:59:44 2008 -0700
272     Linux 2.6.26-rc1
274 diff --git a/Makefile b/Makefile
275 index 5cf8258..4492984 100644
276 --- a/Makefile
277 +++ b/Makefile
278 @@ -1,7 +1,7 @@
279  VERSION = 2
280  PATCHLEVEL = 6
281 -SUBLEVEL = 25
282 -EXTRAVERSION =
283 +SUBLEVEL = 26
284 +EXTRAVERSION = -rc1
285  NAME = Funky Weasel is Jiggy wit it
287  # *DOCUMENTATION*
288 -------------
290 And when we are finished we can use "git bisect reset" to go back to
291 the branch we were in before we started bisecting:
293 -------------
294 $ git bisect reset
295 Checking out files: 100% (21549/21549), done.
296 Previous HEAD position was 2ddcca3... Linux 2.6.26-rc1
297 Switched to branch 'master'
298 -------------
300 Driving a bisection automatically
301 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
303 The other way to drive the bisection process is to tell "git bisect"
304 to launch a script or command at each bisection step to know if the
305 current commit is "good" or "bad". To do that, we use the "git bisect
306 run" command. For example:
308 -------------
309 $ git bisect start v2.6.27 v2.6.25
310 Bisecting: 10928 revisions left to test after this (roughly 14 steps)
311 [2ec65f8b89ea003c27ff7723525a2ee335a2b393] x86: clean up using max_low_pfn on 32-bit
313 $ git bisect run grep '^SUBLEVEL = 25' Makefile
314 running grep ^SUBLEVEL = 25 Makefile
315 Bisecting: 5480 revisions left to test after this (roughly 13 steps)
316 [66c0b394f08fd89236515c1c84485ea712a157be] KVM: kill file->f_count abuse in kvm
317 running grep ^SUBLEVEL = 25 Makefile
318 SUBLEVEL = 25
319 Bisecting: 2740 revisions left to test after this (roughly 12 steps)
320 [671294719628f1671faefd4882764886f8ad08cb] V4L/DVB(7879): Adding cx18 Support for mxl5005s
323 running grep ^SUBLEVEL = 25 Makefile
324 Bisecting: 0 revisions left to test after this (roughly 0 steps)
325 [2ddcca36c8bcfa251724fe342c8327451988be0d] Linux 2.6.26-rc1
326 running grep ^SUBLEVEL = 25 Makefile
327 2ddcca36c8bcfa251724fe342c8327451988be0d is the first bad commit
328 commit 2ddcca36c8bcfa251724fe342c8327451988be0d
329 Author: Linus Torvalds <torvalds@linux-foundation.org>
330 Date:   Sat May 3 11:59:44 2008 -0700
332     Linux 2.6.26-rc1
334 :100644 100644 5cf82581... 4492984e... M      Makefile
335 bisect run success
336 -------------
338 In this example, we passed "grep '^SUBLEVEL = 25' Makefile" as
339 parameter to "git bisect run". This means that at each step, the grep
340 command we passed will be launched. And if it exits with code 0 (that
341 means success) then git bisect will mark the current state as
342 "good". If it exits with code 1 (or any code between 1 and 127
343 included, except the special code 125), then the current state will be
344 marked as "bad".
346 Exit code between 128 and 255 are special to "git bisect run". They
347 make it stop immediately the bisection process. This is useful for
348 example if the command passed takes too long to complete, because you
349 can kill it with a signal and it will stop the bisection process.
351 It can also be useful in scripts passed to "git bisect run" to "exit
352 255" if some very abnormal situation is detected.
354 Avoiding untestable commits
355 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
357 Sometimes it happens that the current state cannot be tested, for
358 example if it does not compile because there was a bug preventing it
359 at that time. This is what the special exit code 125 is for. It tells
360 "git bisect run" that the current commit should be marked as
361 untestable and that another one should be chosen and checked out.
363 If the bisection process is driven manually, you can use "git bisect
364 skip" to do the same thing. (In fact the special exit code 125 makes
365 "git bisect run" use "git bisect skip" in the background.)
367 Or if you want more control, you can inspect the current state using
368 for example "git bisect visualize". It will launch gitk (or "git log"
369 if the DISPLAY environment variable is not set) to help you find a
370 better bisection point.
372 Either way, if you have a string of untestable commits, it might
373 happen that the regression you are looking for has been introduced by
374 one of these untestable commits. In this case it's not possible to
375 tell for sure which commit introduced the regression.
377 So if you used "git bisect skip" (or the run script exited with
378 special code 125) you could get a result like this:
380 -------------
381 There are only 'skip'ped commits left to test.
382 The first bad commit could be any of:
383 15722f2fa328eaba97022898a305ffc8172db6b1
384 78e86cf3e850bd755bb71831f42e200626fbd1e0
385 e15b73ad3db9b48d7d1ade32f8cd23a751fe0ace
386 070eab2303024706f2924822bfec8b9847e4ac1b
387 We cannot bisect more!
388 -------------
390 Saving a log and replaying it
391 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
393 If you want to show other people your bisection process, you can get a
394 log using for example:
396 -------------
397 $ git bisect log > bisect_log.txt
398 -------------
400 And it is possible to replay it using:
402 -------------
403 $ git bisect replay bisect_log.txt
404 -------------
407 "git bisect" details
408 --------------------
410 Bisection algorithm
411 ~~~~~~~~~~~~~~~~~~~
413 As the Git commits form a directed acyclic graph (DAG), finding the
414 best bisection commit to test at each step is not so simple. Anyway
415 Linus found and implemented a "truly stupid" algorithm, later improved
416 by Junio Hamano, that works quite well.
418 So the algorithm used by "git bisect" to find the best bisection
419 commit when there are no skipped commits is the following:
421 1) keep only the commits that:
423 a) are ancestor of the "bad" commit (including the "bad" commit itself),
424 b) are not ancestor of a "good" commit (excluding the "good" commits).
426 This means that we get rid of the uninteresting commits in the DAG.
428 For example if we start with a graph like this:
430 -------------
431 G-Y-G-W-W-W-X-X-X-X
432            \ /
433             W-W-B
434            /
435 Y---G-W---W
436  \ /   \
437 Y-Y     X-X-X-X
439 -> time goes this way ->
440 -------------
442 where B is the "bad" commit, "G" are "good" commits and W, X, and Y
443 are other commits, we will get the following graph after this first
444 step:
446 -------------
447 W-W-W
448      \
449       W-W-B
450      /
451 W---W
452 -------------
454 So only the W and B commits will be kept. Because commits X and Y will
455 have been removed by rules a) and b) respectively, and because commits
456 G are removed by rule b) too.
458 Note for Git users, that it is equivalent as keeping only the commit
459 given by:
461 -------------
462 git rev-list BAD --not GOOD1 GOOD2...
463 -------------
465 Also note that we don't require the commits that are kept to be
466 descendants of a "good" commit. So in the following example, commits W
467 and Z will be kept:
469 -------------
470 G-W-W-W-B
471    /
473 -------------
475 2) starting from the "good" ends of the graph, associate to each
476 commit the number of ancestors it has plus one
478 For example with the following graph where H is the "bad" commit and A
479 and D are some parents of some "good" commits:
481 -------------
482 A-B-C
483      \
484       F-G-H
485      /
486 D---E
487 -------------
489 this will give:
491 -------------
492 1 2 3
493 A-B-C
494      \6 7 8
495       F-G-H
496 1   2/
497 D---E
498 -------------
500 3) associate to each commit: min(X, N - X)
502 where X is the value associated to the commit in step 2) and N is the
503 total number of commits in the graph.
505 In the above example we have N = 8, so this will give:
507 -------------
508 1 2 3
509 A-B-C
510      \2 1 0
511       F-G-H
512 1   2/
513 D---E
514 -------------
516 4) the best bisection point is the commit with the highest associated
517 number
519 So in the above example the best bisection point is commit C.
521 5) note that some shortcuts are implemented to speed up the algorithm
523 As we know N from the beginning, we know that min(X, N - X) can't be
524 greater than N/2. So during steps 2) and 3), if we would associate N/2
525 to a commit, then we know this is the best bisection point. So in this
526 case we can just stop processing any other commit and return the
527 current commit.
529 Bisection algorithm debugging
530 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
532 For any commit graph, you can see the number associated with each
533 commit using "git rev-list --bisect-all".
535 For example, for the above graph, a command like:
537 -------------
538 $ git rev-list --bisect-all BAD --not GOOD1 GOOD2
539 -------------
541 would output something like:
543 -------------
544 e15b73ad3db9b48d7d1ade32f8cd23a751fe0ace (dist=3)
545 15722f2fa328eaba97022898a305ffc8172db6b1 (dist=2)
546 78e86cf3e850bd755bb71831f42e200626fbd1e0 (dist=2)
547 a1939d9a142de972094af4dde9a544e577ddef0e (dist=2)
548 070eab2303024706f2924822bfec8b9847e4ac1b (dist=1)
549 a3864d4f32a3bf5ed177ddef598490a08760b70d (dist=1)
550 a41baa717dd74f1180abf55e9341bc7a0bb9d556 (dist=1)
551 9e622a6dad403b71c40979743bb9d5be17b16bd6 (dist=0)
552 -------------
554 Bisection algorithm discussed
555 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
557 First let's define "best bisection point". We will say that a commit X
558 is a best bisection point or a best bisection commit if knowing its
559 state ("good" or "bad") gives as much information as possible whether
560 the state of the commit happens to be "good" or "bad".
562 This means that the best bisection commits are the commits where the
563 following function is maximum:
565 -------------
566 f(X) = min(information_if_good(X), information_if_bad(X))
567 -------------
569 where information_if_good(X) is the information we get if X is good
570 and information_if_bad(X) is the information we get if X is bad.
572 Now we will suppose that there is only one "first bad commit". This
573 means that all its descendants are "bad" and all the other commits are
574 "good". And we will suppose that all commits have an equal probability
575 of being good or bad, or of being the first bad commit, so knowing the
576 state of c commits gives always the same amount of information
577 wherever these c commits are on the graph and whatever c is. (So we
578 suppose that these commits being for example on a branch or near a
579 good or a bad commit does not give more or less information).
581 Let's also suppose that we have a cleaned up graph like one after step
582 1) in the bisection algorithm above. This means that we can measure
583 the information we get in terms of number of commit we can remove from
584 the graph..
586 And let's take a commit X in the graph.
588 If X is found to be "good", then we know that its ancestors are all
589 "good", so we want to say that:
591 -------------
592 information_if_good(X) = number_of_ancestors(X)  (TRUE)
593 -------------
595 And this is true because at step 1) b) we remove the ancestors of the
596 "good" commits.
598 If X is found to be "bad", then we know that its descendants are all
599 "bad", so we want to say that:
601 -------------
602 information_if_bad(X) = number_of_descendants(X)  (WRONG)
603 -------------
605 But this is wrong because at step 1) a) we keep only the ancestors of
606 the bad commit. So we get more information when a commit is marked as
607 "bad", because we also know that the ancestors of the previous "bad"
608 commit that are not ancestors of the new "bad" commit are not the
609 first bad commit. We don't know if they are good or bad, but we know
610 that they are not the first bad commit because they are not ancestor
611 of the new "bad" commit.
613 So when a commit is marked as "bad" we know we can remove all the
614 commits in the graph except those that are ancestors of the new "bad"
615 commit. This means that:
617 -------------
618 information_if_bad(X) = N - number_of_ancestors(X)  (TRUE)
619 -------------
621 where N is the number of commits in the (cleaned up) graph.
623 So in the end this means that to find the best bisection commits we
624 should maximize the function:
626 -------------
627 f(X) = min(number_of_ancestors(X), N - number_of_ancestors(X))
628 -------------
630 And this is nice because at step 2) we compute number_of_ancestors(X)
631 and so at step 3) we compute f(X).
633 Let's take the following graph as an example:
635 -------------
636             G-H-I-J
637            /       \
638 A-B-C-D-E-F         O
639            \       /
640             K-L-M-N
641 -------------
643 If we compute the following non optimal function on it:
645 -------------
646 g(X) = min(number_of_ancestors(X), number_of_descendants(X))
647 -------------
649 we get:
651 -------------
652             4 3 2 1
653             G-H-I-J
654 1 2 3 4 5 6/       \0
655 A-B-C-D-E-F         O
656            \       /
657             K-L-M-N
658             4 3 2 1
659 -------------
661 but with the algorithm used by git bisect we get:
663 -------------
664             7 7 6 5
665             G-H-I-J
666 1 2 3 4 5 6/       \0
667 A-B-C-D-E-F         O
668            \       /
669             K-L-M-N
670             7 7 6 5
671 -------------
673 So we chose G, H, K or L as the best bisection point, which is better
674 than F. Because if for example L is bad, then we will know not only
675 that L, M and N are bad but also that G, H, I and J are not the first
676 bad commit (since we suppose that there is only one first bad commit
677 and it must be an ancestor of L).
679 So the current algorithm seems to be the best possible given what we
680 initially supposed.
682 Skip algorithm
683 ~~~~~~~~~~~~~~
685 When some commits have been skipped (using "git bisect skip"), then
686 the bisection algorithm is the same for step 1) to 3). But then we use
687 roughly the following steps:
689 6) sort the commit by decreasing associated value
691 7) if the first commit has not been skipped, we can return it and stop
692 here
694 8) otherwise filter out all the skipped commits in the sorted list
696 9) use a pseudo random number generator (PRNG) to generate a random
697 number between 0 and 1
699 10) multiply this random number with its square root to bias it toward
702 11) multiply the result by the number of commits in the filtered list
703 to get an index into this list
705 12) return the commit at the computed index
707 Skip algorithm discussed
708 ~~~~~~~~~~~~~~~~~~~~~~~~
710 After step 7) (in the skip algorithm), we could check if the second
711 commit has been skipped and return it if it is not the case. And in
712 fact that was the algorithm we used from when "git bisect skip" was
713 developed in Git version 1.5.4 (released on February 1st 2008) until
714 Git version 1.6.4 (released July 29th 2009).
716 But Ingo Molnar and H. Peter Anvin (another well known linux kernel
717 developer) both complained that sometimes the best bisection points
718 all happened to be in an area where all the commits are
719 untestable. And in this case the user was asked to test many
720 untestable commits, which could be very inefficient.
722 Indeed untestable commits are often untestable because a breakage was
723 introduced at one time, and that breakage was fixed only after many
724 other commits were introduced.
726 This breakage is of course most of the time unrelated to the breakage
727 we are trying to locate in the commit graph. But it prevents us to
728 know if the interesting "bad behavior" is present or not.
730 So it is a fact that commits near an untestable commit have a high
731 probability of being untestable themselves. And the best bisection
732 commits are often found together too (due to the bisection algorithm).
734 This is why it is a bad idea to just chose the next best unskipped
735 bisection commit when the first one has been skipped.
737 We found that most commits on the graph may give quite a lot of
738 information when they are tested. And the commits that will not on
739 average give a lot of information are the one near the good and bad
740 commits.
742 So using a PRNG with a bias to favor commits away from the good and
743 bad commits looked like a good choice.
745 One obvious improvement to this algorithm would be to look for a
746 commit that has an associated value near the one of the best bisection
747 commit, and that is on another branch, before using the PRNG. Because
748 if such a commit exists, then it is not very likely to be untestable
749 too, so it will probably give more information than a nearly randomly
750 chosen one.
752 Checking merge bases
753 ~~~~~~~~~~~~~~~~~~~~
755 There is another tweak in the bisection algorithm that has not been
756 described in the "bisection algorithm" above.
758 We supposed in the previous examples that the "good" commits were
759 ancestors of the "bad" commit. But this is not a requirement of "git
760 bisect".
762 Of course the "bad" commit cannot be an ancestor of a "good" commit,
763 because the ancestors of the good commits are supposed to be
764 "good". And all the "good" commits must be related to the bad commit.
765 They cannot be on a branch that has no link with the branch of the
766 "bad" commit. But it is possible for a good commit to be related to a
767 bad commit and yet not be neither one of its ancestor nor one of its
768 descendants.
770 For example, there can be a "main" branch, and a "dev" branch that was
771 forked of the main branch at a commit named "D" like this:
773 -------------
774 A-B-C-D-E-F-G  <--main
775        \
776         H-I-J  <--dev
777 -------------
779 The commit "D" is called a "merge base" for branch "main" and "dev"
780 because it's the best common ancestor for these branches for a merge.
782 Now let's suppose that commit J is bad and commit G is good and that
783 we apply the bisection algorithm like it has been previously
784 described.
786 As described in step 1) b) of the bisection algorithm, we remove all
787 the ancestors of the good commits because they are supposed to be good
788 too.
790 So we would be left with only:
792 -------------
793 H-I-J
794 -------------
796 But what happens if the first bad commit is "B" and if it has been
797 fixed in the "main" branch by commit "F"?
799 The result of such a bisection would be that we would find that H is
800 the first bad commit, when in fact it's B. So that would be wrong!
802 And yes it can happen in practice that people working on one branch
803 are not aware that people working on another branch fixed a bug! It
804 could also happen that F fixed more than one bug or that it is a
805 revert of some big development effort that was not ready to be
806 released.
808 In fact development teams often maintain both a development branch and
809 a maintenance branch, and it would be quite easy for them if "git
810 bisect" just worked when they want to bisect a regression on the
811 development branch that is not on the maintenance branch. They should
812 be able to start bisecting using:
814 -------------
815 $ git bisect start dev main
816 -------------
818 To enable that additional nice feature, when a bisection is started
819 and when some good commits are not ancestors of the bad commit, we
820 first compute the merge bases between the bad and the good commits and
821 we chose these merge bases as the first commits that will be checked
822 out and tested.
824 If it happens that one merge base is bad, then the bisection process
825 is stopped with a message like:
827 -------------
828 The merge base BBBBBB is bad.
829 This means the bug has been fixed between BBBBBB and [GGGGGG,...].
830 -------------
832 where BBBBBB is the sha1 hash of the bad merge base and [GGGGGG,...]
833 is a comma separated list of the sha1 of the good commits.
835 If some of the merge bases are skipped, then the bisection process
836 continues, but the following message is printed for each skipped merge
837 base:
839 -------------
840 Warning: the merge base between BBBBBB and [GGGGGG,...] must be skipped.
841 So we cannot be sure the first bad commit is between MMMMMM and BBBBBB.
842 We continue anyway.
843 -------------
845 where BBBBBB is the sha1 hash of the bad commit, MMMMMM is the sha1
846 hash of the merge base that is skipped and [GGGGGG,...]  is a comma
847 separated list of the sha1 of the good commits.
849 So if there is no bad merge base, the bisection process continues as
850 usual after this step.
852 Best bisecting practices
853 ------------------------
855 Using test suites and git bisect together
856 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
858 If you both have a test suite and use git bisect, then it becomes less
859 important to check that all tests pass after each commit. Though of
860 course it is probably a good idea to have some checks to avoid
861 breaking too many things because it could make bisecting other bugs
862 more difficult.
864 You can focus your efforts to check at a few points (for example rc
865 and beta releases) that all the T test cases pass for all the N
866 configurations. And when some tests don't pass you can use "git
867 bisect" (or better "git bisect run"). So you should perform roughly:
869 -------------
870 c * N * T + b * M * log2(M) tests
871 -------------
873 where c is the number of rounds of test (so a small constant) and b is
874 the ratio of bug per commit (hopefully a small constant too).
876 So of course it's much better as it's O(N * T) vs O(N * T * M) if
877 you would test everything after each commit.
879 This means that test suites are good to prevent some bugs from being
880 committed and they are also quite good to tell you that you have some
881 bugs. But they are not so good to tell you where some bugs have been
882 introduced. To tell you that efficiently, git bisect is needed.
884 The other nice thing with test suites, is that when you have one, you
885 already know how to test for bad behavior. So you can use this
886 knowledge to create a new test case for "git bisect" when it appears
887 that there is a regression. So it will be easier to bisect the bug and
888 fix it. And then you can add the test case you just created to your
889 test suite.
891 So if you know how to create test cases and how to bisect, you will be
892 subject to a virtuous circle:
894 more tests => easier to create tests => easier to bisect => more tests
896 So test suites and "git bisect" are complementary tools that are very
897 powerful and efficient when used together.
899 Bisecting build failures
900 ~~~~~~~~~~~~~~~~~~~~~~~~
902 You can very easily automatically bisect broken builds using something
903 like:
905 -------------
906 $ git bisect start BAD GOOD
907 $ git bisect run make
908 -------------
910 Passing sh -c "some commands" to "git bisect run"
911 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
913 For example:
915 -------------
916 $ git bisect run sh -c "make || exit 125; ./my_app | grep 'good output'"
917 -------------
919 On the other hand if you do this often, then it can be worth having
920 scripts to avoid too much typing.
922 Finding performance regressions
923 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
925 Here is an example script that comes slightly modified from a real
926 world script used by Junio Hamano <<4>>.
928 This script can be passed to "git bisect run" to find the commit that
929 introduced a performance regression:
931 -------------
932 #!/bin/sh
934 # Build errors are not what I am interested in.
935 make my_app || exit 255
937 # We are checking if it stops in a reasonable amount of time, so
938 # let it run in the background...
940 ./my_app >log 2>&1 &
942 # ... and grab its process ID.
943 pid=$!
945 # ... and then wait for sufficiently long.
946 sleep $NORMAL_TIME
948 # ... and then see if the process is still there.
949 if kill -0 $pid
950 then
951         # It is still running -- that is bad.
952         kill $pid; sleep 1; kill $pid;
953         exit 1
954 else
955         # It has already finished (the $pid process was no more),
956         # and we are happy.
957         exit 0
959 -------------
961 Following general best practices
962 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
964 It is obviously a good idea not to have commits with changes that
965 knowingly break things, even if some other commits later fix the
966 breakage.
968 It is also a good idea when using any VCS to have only one small
969 logical change in each commit.
971 The smaller the changes in your commit, the most effective "git
972 bisect" will be. And you will probably need "git bisect" less in the
973 first place, as small changes are easier to review even if they are
974 only reviewed by the committer.
976 Another good idea is to have good commit messages. They can be very
977 helpful to understand why some changes were made.
979 These general best practices are very helpful if you bisect often.
981 Avoiding bug prone merges
982 ~~~~~~~~~~~~~~~~~~~~~~~~~
984 First merges by themselves can introduce some regressions even when
985 the merge needs no source code conflict resolution. This is because a
986 semantic change can happen in one branch while the other branch is not
987 aware of it.
989 For example one branch can change the semantic of a function while the
990 other branch add more calls to the same function.
992 This is made much worse if many files have to be fixed to resolve
993 conflicts. That's why such merges are called "evil merges". They can
994 make regressions very difficult to track down. It can even be
995 misleading to know the first bad commit if it happens to be such a
996 merge, because people might think that the bug comes from bad conflict
997 resolution when it comes from a semantic change in one branch.
999 Anyway "git rebase" can be used to linearize history. This can be used
1000 either to avoid merging in the first place. Or it can be used to
1001 bisect on a linear history instead of the non linear one, as this
1002 should give more information in case of a semantic change in one
1003 branch.
1005 Merges can be also made simpler by using smaller branches or by using
1006 many topic branches instead of only long version related branches.
1008 And testing can be done more often in special integration branches
1009 like linux-next for the linux kernel.
1011 Adapting your work-flow
1012 ~~~~~~~~~~~~~~~~~~~~~~~
1014 A special work-flow to process regressions can give great results.
1016 Here is an example of a work-flow used by Andreas Ericsson:
1018 * write, in the test suite, a test script that exposes the regression
1019 * use "git bisect run" to find the commit that introduced it
1020 * fix the bug that is often made obvious by the previous step
1021 * commit both the fix and the test script (and if needed more tests)
1023 And here is what Andreas said about this work-flow <<5>>:
1025 _____________
1026 To give some hard figures, we used to have an average report-to-fix
1027 cycle of 142.6 hours (according to our somewhat weird bug-tracker
1028 which just measures wall-clock time). Since we moved to Git, we've
1029 lowered that to 16.2 hours. Primarily because we can stay on top of
1030 the bug fixing now, and because everyone's jockeying to get to fix
1031 bugs (we're quite proud of how lazy we are to let Git find the bugs
1032 for us). Each new release results in ~40% fewer bugs (almost certainly
1033 due to how we now feel about writing tests).
1034 _____________
1036 Clearly this work-flow uses the virtuous circle between test suites
1037 and "git bisect". In fact it makes it the standard procedure to deal
1038 with regression.
1040 In other messages Andreas says that they also use the "best practices"
1041 described above: small logical commits, topic branches, no evil
1042 merge,... These practices all improve the bisectability of the commit
1043 graph, by making it easier and more useful to bisect.
1045 So a good work-flow should be designed around the above points. That
1046 is making bisecting easier, more useful and standard.
1048 Involving QA people and if possible end users
1049 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1051 One nice about "git bisect" is that it is not only a developer
1052 tool. It can effectively be used by QA people or even end users (if
1053 they have access to the source code or if they can get access to all
1054 the builds).
1056 There was a discussion at one point on the linux kernel mailing list
1057 of whether it was ok to always ask end user to bisect, and very good
1058 points were made to support the point of view that it is ok.
1060 For example David Miller wrote <<6>>:
1062 _____________
1063 What people don't get is that this is a situation where the "end node
1064 principle" applies. When you have limited resources (here: developers)
1065 you don't push the bulk of the burden upon them. Instead you push
1066 things out to the resource you have a lot of, the end nodes (here:
1067 users), so that the situation actually scales.
1068 _____________
1070 This means that it is often "cheaper" if QA people or end users can do
1073 What is interesting too is that end users that are reporting bugs (or
1074 QA people that reproduced a bug) have access to the environment where
1075 the bug happens. So they can often more easily reproduce a
1076 regression. And if they can bisect, then more information will be
1077 extracted from the environment where the bug happens, which means that
1078 it will be easier to understand and then fix the bug.
1080 For open source projects it can be a good way to get more useful
1081 contributions from end users, and to introduce them to QA and
1082 development activities.
1084 Using complex scripts
1085 ~~~~~~~~~~~~~~~~~~~~~
1087 In some cases like for kernel development it can be worth developing
1088 complex scripts to be able to fully automate bisecting.
1090 Here is what Ingo Molnar says about that <<7>>:
1092 _____________
1093 i have a fully automated bootup-hang bisection script. It is based on
1094 "git-bisect run". I run the script, it builds and boots kernels fully
1095 automatically, and when the bootup fails (the script notices that via
1096 the serial log, which it continuously watches - or via a timeout, if
1097 the system does not come up within 10 minutes it's a "bad" kernel),
1098 the script raises my attention via a beep and i power cycle the test
1099 box. (yeah, i should make use of a managed power outlet to 100%
1100 automate it)
1101 _____________
1103 Combining test suites, git bisect and other systems together
1104 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1106 We have seen that test suites an git bisect are very powerful when
1107 used together. It can be even more powerful if you can combine them
1108 with other systems.
1110 For example some test suites could be run automatically at night with
1111 some unusual (or even random) configurations. And if a regression is
1112 found by a test suite, then "git bisect" can be automatically
1113 launched, and its result can be emailed to the author of the first bad
1114 commit found by "git bisect", and perhaps other people too. And a new
1115 entry in the bug tracking system could be automatically created too.
1118 The future of bisecting
1119 -----------------------
1121 "git replace"
1122 ~~~~~~~~~~~~~
1124 We saw earlier that "git bisect skip" is now using a PRNG to try to
1125 avoid areas in the commit graph where commits are untestable. The
1126 problem is that sometimes the first bad commit will be in an
1127 untestable area.
1129 To simplify the discussion we will suppose that the untestable area is
1130 a simple string of commits and that it was created by a breakage
1131 introduced by one commit (let's call it BBC for bisect breaking
1132 commit) and later fixed by another one (let's call it BFC for bisect
1133 fixing commit).
1135 For example:
1137 -------------
1138 ...-Y-BBC-X1-X2-X3-X4-X5-X6-BFC-Z-...
1139 -------------
1141 where we know that Y is good and BFC is bad, and where BBC and X1 to
1142 X6 are untestable.
1144 In this case if you are bisecting manually, what you can do is create
1145 a special branch that starts just before the BBC. The first commit in
1146 this branch should be the BBC with the BFC squashed into it. And the
1147 other commits in the branch should be the commits between BBC and BFC
1148 rebased on the first commit of the branch and then the commit after
1149 BFC also rebased on.
1151 For example:
1153 -------------
1154       (BBC+BFC)-X1'-X2'-X3'-X4'-X5'-X6'-Z'
1155      /
1156 ...-Y-BBC-X1-X2-X3-X4-X5-X6-BFC-Z-...
1157 -------------
1159 where commits quoted with ' have been rebased.
1161 You can easily create such a branch with Git using interactive rebase.
1163 For example using:
1165 -------------
1166 $ git rebase -i Y Z
1167 -------------
1169 and then moving BFC after BBC and squashing it.
1171 After that you can start bisecting as usual in the new branch and you
1172 should eventually find the first bad commit.
1174 For example:
1176 -------------
1177 $ git bisect start Z' Y
1178 -------------
1180 If you are using "git bisect run", you can use the same manual fix up
1181 as above, and then start another "git bisect run" in the special
1182 branch. Or as the "git bisect" man page says, the script passed to
1183 "git bisect run" can apply a patch before it compiles and test the
1184 software <<8>>. The patch should turn a current untestable commits
1185 into a testable one. So the testing will result in "good" or "bad" and
1186 "git bisect" will be able to find the first bad commit. And the script
1187 should not forget to remove the patch once the testing is done before
1188 exiting from the script.
1190 (Note that instead of a patch you can use "git cherry-pick BFC" to
1191 apply the fix, and in this case you should use "git reset --hard
1192 HEAD^" to revert the cherry-pick after testing and before returning
1193 from the script.)
1195 But the above ways to work around untestable areas are a little bit
1196 clunky. Using special branches is nice because these branches can be
1197 shared by developers like usual branches, but the risk is that people
1198 will get many such branches. And it disrupts the normal "git bisect"
1199 work-flow. So, if you want to use "git bisect run" completely
1200 automatically, you have to add special code in your script to restart
1201 bisection in the special branches.
1203 Anyway one can notice in the above special branch example that the Z'
1204 and Z commits should point to the same source code state (the same
1205 "tree" in git parlance). That's because Z' result from applying the
1206 same changes as Z just in a slightly different order.
1208 So if we could just "replace" Z by Z' when we bisect, then we would
1209 not need to add anything to a script. It would just work for anyone in
1210 the project sharing the special branches and the replacements.
1212 With the example above that would give:
1214 -------------
1215       (BBC+BFC)-X1'-X2'-X3'-X4'-X5'-X6'-Z'-...
1216      /
1217 ...-Y-BBC-X1-X2-X3-X4-X5-X6-BFC-Z
1218 -------------
1220 That's why the "git replace" command was created. Technically it
1221 stores replacements "refs" in the "refs/replace/" hierarchy. These
1222 "refs" are like branches (that are stored in "refs/heads/") or tags
1223 (that are stored in "refs/tags"), and that means that they can
1224 automatically be shared like branches or tags among developers.
1226 "git replace" is a very powerful mechanism. It can be used to fix
1227 commits in already released history, for example to change the commit
1228 message or the author. And it can also be used instead of git "grafts"
1229 to link a repository with another old repository.
1231 In fact it's this last feature that "sold" it to the Git community, so
1232 it is now in the "master" branch of Git's Git repository and it should
1233 be released in Git 1.6.5 in October or November 2009.
1235 One problem with "git replace" is that currently it stores all the
1236 replacements refs in "refs/replace/", but it would be perhaps better
1237 if the replacement refs that are useful only for bisecting would be in
1238 "refs/replace/bisect/". This way the replacement refs could be used
1239 only for bisecting, while other refs directly in "refs/replace/" would
1240 be used nearly all the time.
1242 Bisecting sporadic bugs
1243 ~~~~~~~~~~~~~~~~~~~~~~~
1245 Another possible improvement to "git bisect" would be to optionally
1246 add some redundancy to the tests performed so that it would be more
1247 reliable when tracking sporadic bugs.
1249 This has been requested by some kernel developers because some bugs
1250 called sporadic bugs do not appear in all the kernel builds because
1251 they are very dependent on the compiler output.
1253 The idea is that every 3 test for example, "git bisect" could ask the
1254 user to test a commit that has already been found to be "good" or
1255 "bad" (because one of its descendants or one of its ancestors has been
1256 found to be "good" or "bad" respectively). If it happens that a commit
1257 has been previously incorrectly classified then the bisection can be
1258 aborted early, hopefully before too many mistakes have been made. Then
1259 the user will have to look at what happened and then restart the
1260 bisection using a fixed bisect log.
1262 There is already a project called BBChop created by Ealdwulf Wuffinga
1263 on Github that does something like that using Bayesian Search Theory
1264 <<9>>:
1266 _____________
1267 BBChop is like 'git bisect' (or equivalent), but works when your bug
1268 is intermittent. That is, it works in the presence of false negatives
1269 (when a version happens to work this time even though it contains the
1270 bug). It assumes that there are no false positives (in principle, the
1271 same approach would work, but adding it may be non-trivial).
1272 _____________
1274 But BBChop is independent of any VCS and it would be easier for Git
1275 users to have something integrated in Git.
1277 Conclusion
1278 ----------
1280 We have seen that regressions are an important problem, and that "git
1281 bisect" has nice features that complement very well practices and
1282 other tools, especially test suites, that are generally used to fight
1283 regressions. But it might be needed to change some work-flows and
1284 (bad) habits to get the most out of it.
1286 Some improvements to the algorithms inside "git bisect" are possible
1287 and some new features could help in some cases, but overall "git
1288 bisect" works already very well, is used a lot, and is already very
1289 useful. To back up that last claim, let's give the final word to Ingo
1290 Molnar when he was asked by the author how much time does he think
1291 "git bisect" saves him when he uses it:
1293 _____________
1294 a _lot_.
1296 About ten years ago did i do my first 'bisection' of a Linux patch
1297 queue. That was prior the Git (and even prior the BitKeeper) days. I
1298 literally days spent sorting out patches, creating what in essence
1299 were standalone commits that i guessed to be related to that bug.
1301 It was a tool of absolute last resort. I'd rather spend days looking
1302 at printk output than do a manual 'patch bisection'.
1304 With Git bisect it's a breeze: in the best case i can get a ~15 step
1305 kernel bisection done in 20-30 minutes, in an automated way. Even with
1306 manual help or when bisecting multiple, overlapping bugs, it's rarely
1307 more than an hour.
1309 In fact it's invaluable because there are bugs i would never even
1310 _try_ to debug if it wasn't for git bisect. In the past there were bug
1311 patterns that were immediately hopeless for me to debug - at best i
1312 could send the crash/bug signature to lkml and hope that someone else
1313 can think of something.
1315 And even if a bisection fails today it tells us something valuable
1316 about the bug: that it's non-deterministic - timing or kernel image
1317 layout dependent.
1319 So git bisect is unconditional goodness - and feel free to quote that
1321 _____________
1323 Acknowledgments
1324 ----------------
1326 Many thanks to Junio Hamano for his help in reviewing this paper, for
1327 reviewing the patches I sent to the Git mailing list, for discussing
1328 some ideas and helping me improve them, for improving "git bisect" a
1329 lot and for his awesome work in maintaining and developing Git.
1331 Many thanks to Ingo Molnar for giving me very useful information that
1332 appears in this paper, for commenting on this paper, for his
1333 suggestions to improve "git bisect" and for evangelizing "git bisect"
1334 on the linux kernel mailing lists.
1336 Many thanks to Linus Torvalds for inventing, developing and
1337 evangelizing "git bisect", Git and Linux.
1339 Many thanks to the many other great people who helped one way or
1340 another when I worked on Git, especially to Andreas Ericsson, Johannes
1341 Schindelin, H. Peter Anvin, Daniel Barkalow, Bill Lear, John Hawley,
1342 Shawn O. Pierce, Jeff King, Sam Vilain, Jon Seymour.
1344 Many thanks to the Linux-Kongress program committee for choosing the
1345 author to given a talk and for publishing this paper.
1347 References
1348 ----------
1350 - [[[1]]] http://www.nist.gov/public_affairs/releases/n02-10.htm['Software Errors Cost U.S. Economy $59.5 Billion Annually'. Nist News Release.]
1351 - [[[2]]] http://java.sun.com/docs/codeconv/html/CodeConventions.doc.html#16712['Code Conventions for the Java Programming Language'. Sun Microsystems.]
1352 - [[[3]]] http://en.wikipedia.org/wiki/Software_maintenance['Software maintenance'. Wikipedia.]
1353 - [[[4]]] http://article.gmane.org/gmane.comp.version-control.git/45195/[Junio C Hamano. 'Automated bisect success story'. Gmane.]
1354 - [[[5]]] http://lwn.net/Articles/317154/[Christian Couder. 'Fully automated bisecting with "git bisect run"'. LWN.net.]
1355 - [[[6]]] http://lwn.net/Articles/277872/[Jonathan Corbet. 'Bisection divides users and developers'. LWN.net.]
1356 - [[[7]]] http://article.gmane.org/gmane.linux.scsi/36652/[Ingo Molnar. 'Re: BUG 2.6.23-rc3 can't see sd partitions on Alpha'. Gmane.]
1357 - [[[8]]] http://www.kernel.org/pub/software/scm/git/docs/git-bisect.html[Junio C Hamano and the git-list. 'git-bisect(1) Manual Page'. Linux Kernel Archives.]
1358 - [[[9]]] http://github.com/Ealdwulf/bbchop[Ealdwulf. 'bbchop'. GitHub.]