Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 1 | Fighting regressions with git bisect |
| 2 | ==================================== |
| 3 | :Author: Christian Couder |
| 4 | :Email: chriscool@tuxfamily.org |
| 5 | :Date: 2009/11/08 |
| 6 | |
| 7 | Abstract |
| 8 | -------- |
| 9 | |
| 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. |
| 17 | |
| 18 | |
| 19 | Introduction to "git bisect" |
| 20 | ---------------------------- |
| 21 | |
| 22 | Git is a Distributed Version Control system (DVCS) created by Linus |
| 23 | Torvalds and maintained by Junio Hamano. |
| 24 | |
| 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. |
| 30 | |
| 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. |
| 37 | |
| 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. |
| 45 | |
| 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. |
| 48 | |
| 49 | |
| 50 | Fighting regressions overview |
| 51 | ----------------------------- |
| 52 | |
| 53 | Regressions: a big problem |
| 54 | ~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 55 | |
| 56 | Regressions are a big problem in the software industry. But it's |
| 57 | difficult to put some real numbers behind that claim. |
| 58 | |
| 59 | There are some numbers about bugs in general, like a NIST study in |
| 60 | 2002 <<1>> that said: |
| 61 | |
| 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 | _____________ |
| 79 | |
| 80 | And then: |
| 81 | |
| 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 | _____________ |
| 88 | |
| 89 | Eventually the conclusion started with: |
| 90 | |
| 91 | _____________ |
| 92 | The path to higher software quality is significantly improved software |
| 93 | testing. |
| 94 | _____________ |
| 95 | |
| 96 | There are other estimates saying that 80% of the cost related to |
| 97 | software is about maintenance <<2>>. |
| 98 | |
| 99 | Though, according to Wikipedia <<3>>: |
| 100 | |
| 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 | _____________ |
| 109 | |
| 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. |
| 113 | |
| 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. |
| 121 | |
Thomas Ackermann | f745acb | 2014-11-03 21:37:07 +0100 | [diff] [blame] | 122 | One such software is the Linux kernel. And if we look at the Linux |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 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. |
| 128 | |
| 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. |
| 134 | |
Thomas Ackermann | f745acb | 2014-11-03 21:37:07 +0100 | [diff] [blame] | 135 | And then this is what Ingo Molnar (a well known Linux kernel |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 136 | developer) says about his use of git bisect: |
| 137 | |
| 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 | _____________ |
| 144 | |
| 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. |
| 149 | |
| 150 | Other tools to fight regressions |
| 151 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 152 | |
| 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". |
| 156 | |
| 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 |
Elijah Newren | 031fd4b | 2019-11-05 17:07:20 +0000 | [diff] [blame] | 161 | combinatorial explosion. |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 162 | |
| 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: |
| 167 | |
| 168 | ------------- |
| 169 | N * M * T tests |
| 170 | ------------- |
| 171 | |
| 172 | where N, M and T are all growing with the size your software. |
| 173 | |
| 174 | So very soon it will not be possible to completely test everything. |
| 175 | |
| 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. |
| 182 | |
| 183 | "git bisect" overview |
| 184 | --------------------- |
| 185 | |
| 186 | Starting a bisection |
| 187 | ~~~~~~~~~~~~~~~~~~~~ |
| 188 | |
| 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: |
| 194 | |
| 195 | ------------- |
| 196 | $ git bisect start [BAD [GOOD...]] |
| 197 | ------------- |
| 198 | |
| 199 | or they can be set using: |
| 200 | |
| 201 | ------------- |
| 202 | $ git bisect bad [COMMIT] |
| 203 | ------------- |
| 204 | |
| 205 | and: |
| 206 | |
| 207 | ------------- |
| 208 | $ git bisect good [COMMIT...] |
| 209 | ------------- |
| 210 | |
| 211 | where BAD, GOOD and COMMIT are all names that can be resolved to a |
| 212 | commit. |
| 213 | |
| 214 | Then "git bisect" will checkout a commit of its choosing and ask the |
| 215 | user to test it, like this: |
| 216 | |
| 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 | ------------- |
| 222 | |
| 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 |
Thomas Ackermann | 2de9b71 | 2013-01-21 20:17:53 +0100 | [diff] [blame] | 227 | better ways to find this commit with Git than using "git bisect" (for |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 228 | example "git blame" or "git log -S<string>"). |
| 229 | |
| 230 | Driving a bisection manually |
| 231 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 232 | |
| 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. |
| 236 | |
| 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: |
| 241 | |
| 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 | ------------- |
| 247 | |
| 248 | And after a few more steps like that, "git bisect" will eventually |
| 249 | find a first bad commit: |
| 250 | |
| 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 |
| 257 | |
| 258 | Linux 2.6.26-rc1 |
| 259 | |
Thomas Ackermann | 9fa9728 | 2012-10-16 19:21:57 +0200 | [diff] [blame] | 260 | :100644 100644 5cf82581... 4492984e... M Makefile |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 261 | ------------- |
| 262 | |
| 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: |
| 265 | |
| 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 |
| 271 | |
| 272 | Linux 2.6.26-rc1 |
| 273 | |
| 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 |
| 286 | |
| 287 | # *DOCUMENTATION* |
| 288 | ------------- |
| 289 | |
| 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: |
| 292 | |
| 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 | ------------- |
| 299 | |
| 300 | Driving a bisection automatically |
| 301 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 302 | |
| 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: |
| 307 | |
| 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 |
| 312 | $ |
| 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 |
| 321 | ... |
| 322 | ... |
| 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 |
| 331 | |
| 332 | Linux 2.6.26-rc1 |
| 333 | |
Thomas Ackermann | 9fa9728 | 2012-10-16 19:21:57 +0200 | [diff] [blame] | 334 | :100644 100644 5cf82581... 4492984e... M Makefile |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 335 | bisect run success |
| 336 | ------------- |
| 337 | |
| 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". |
| 345 | |
| 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. |
| 350 | |
| 351 | It can also be useful in scripts passed to "git bisect run" to "exit |
| 352 | 255" if some very abnormal situation is detected. |
| 353 | |
| 354 | Avoiding untestable commits |
| 355 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 356 | |
| 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. |
| 362 | |
| 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.) |
| 366 | |
| 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" |
Tom Russello | 47d81b5 | 2016-06-08 00:35:07 +0200 | [diff] [blame] | 369 | if the `DISPLAY` environment variable is not set) to help you find a |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 370 | better bisection point. |
| 371 | |
| 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. |
| 376 | |
| 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: |
| 379 | |
| 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 | ------------- |
| 389 | |
| 390 | Saving a log and replaying it |
| 391 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 392 | |
| 393 | If you want to show other people your bisection process, you can get a |
| 394 | log using for example: |
| 395 | |
| 396 | ------------- |
| 397 | $ git bisect log > bisect_log.txt |
| 398 | ------------- |
| 399 | |
| 400 | And it is possible to replay it using: |
| 401 | |
| 402 | ------------- |
| 403 | $ git bisect replay bisect_log.txt |
| 404 | ------------- |
| 405 | |
| 406 | |
| 407 | "git bisect" details |
| 408 | -------------------- |
| 409 | |
| 410 | Bisection algorithm |
| 411 | ~~~~~~~~~~~~~~~~~~~ |
| 412 | |
| 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. |
| 417 | |
| 418 | So the algorithm used by "git bisect" to find the best bisection |
| 419 | commit when there are no skipped commits is the following: |
| 420 | |
| 421 | 1) keep only the commits that: |
| 422 | |
| 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). |
| 425 | |
| 426 | This means that we get rid of the uninteresting commits in the DAG. |
| 427 | |
| 428 | For example if we start with a graph like this: |
| 429 | |
| 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 |
| 438 | |
| 439 | -> time goes this way -> |
| 440 | ------------- |
| 441 | |
| 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: |
| 445 | |
| 446 | ------------- |
| 447 | W-W-W |
| 448 | \ |
| 449 | W-W-B |
| 450 | / |
| 451 | W---W |
| 452 | ------------- |
| 453 | |
| 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. |
| 457 | |
Thomas Ackermann | 2de9b71 | 2013-01-21 20:17:53 +0100 | [diff] [blame] | 458 | Note for Git users, that it is equivalent as keeping only the commit |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 459 | given by: |
| 460 | |
| 461 | ------------- |
| 462 | git rev-list BAD --not GOOD1 GOOD2... |
| 463 | ------------- |
| 464 | |
| 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: |
| 468 | |
| 469 | ------------- |
| 470 | G-W-W-W-B |
| 471 | / |
| 472 | Z-Z |
| 473 | ------------- |
| 474 | |
| 475 | 2) starting from the "good" ends of the graph, associate to each |
Jean-Noël Avila | df49a80 | 2020-10-08 22:23:54 +0200 | [diff] [blame] | 476 | commit the number of ancestors it has plus one |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 477 | |
| 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: |
| 480 | |
| 481 | ------------- |
| 482 | A-B-C |
| 483 | \ |
| 484 | F-G-H |
| 485 | / |
| 486 | D---E |
| 487 | ------------- |
| 488 | |
| 489 | this will give: |
| 490 | |
| 491 | ------------- |
| 492 | 1 2 3 |
| 493 | A-B-C |
| 494 | \6 7 8 |
| 495 | F-G-H |
| 496 | 1 2/ |
| 497 | D---E |
| 498 | ------------- |
| 499 | |
| 500 | 3) associate to each commit: min(X, N - X) |
| 501 | |
| 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. |
| 504 | |
| 505 | In the above example we have N = 8, so this will give: |
| 506 | |
| 507 | ------------- |
| 508 | 1 2 3 |
| 509 | A-B-C |
| 510 | \2 1 0 |
| 511 | F-G-H |
| 512 | 1 2/ |
| 513 | D---E |
| 514 | ------------- |
| 515 | |
| 516 | 4) the best bisection point is the commit with the highest associated |
Jean-Noël Avila | df49a80 | 2020-10-08 22:23:54 +0200 | [diff] [blame] | 517 | number |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 518 | |
| 519 | So in the above example the best bisection point is commit C. |
| 520 | |
| 521 | 5) note that some shortcuts are implemented to speed up the algorithm |
| 522 | |
| 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. |
| 528 | |
| 529 | Bisection algorithm debugging |
| 530 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 531 | |
| 532 | For any commit graph, you can see the number associated with each |
| 533 | commit using "git rev-list --bisect-all". |
| 534 | |
| 535 | For example, for the above graph, a command like: |
| 536 | |
| 537 | ------------- |
| 538 | $ git rev-list --bisect-all BAD --not GOOD1 GOOD2 |
| 539 | ------------- |
| 540 | |
| 541 | would output something like: |
| 542 | |
| 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 | ------------- |
| 553 | |
| 554 | Bisection algorithm discussed |
| 555 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 556 | |
| 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". |
| 561 | |
| 562 | This means that the best bisection commits are the commits where the |
| 563 | following function is maximum: |
| 564 | |
| 565 | ------------- |
| 566 | f(X) = min(information_if_good(X), information_if_bad(X)) |
| 567 | ------------- |
| 568 | |
| 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. |
| 571 | |
| 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). |
| 580 | |
| 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 |
Jean-Noël Avila | df49a80 | 2020-10-08 22:23:54 +0200 | [diff] [blame] | 583 | the information we get in terms of number of commit we can remove |
| 584 | from the graph.. |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 585 | |
| 586 | And let's take a commit X in the graph. |
| 587 | |
| 588 | If X is found to be "good", then we know that its ancestors are all |
| 589 | "good", so we want to say that: |
| 590 | |
| 591 | ------------- |
| 592 | information_if_good(X) = number_of_ancestors(X) (TRUE) |
| 593 | ------------- |
| 594 | |
| 595 | And this is true because at step 1) b) we remove the ancestors of the |
| 596 | "good" commits. |
| 597 | |
| 598 | If X is found to be "bad", then we know that its descendants are all |
| 599 | "bad", so we want to say that: |
| 600 | |
| 601 | ------------- |
| 602 | information_if_bad(X) = number_of_descendants(X) (WRONG) |
| 603 | ------------- |
| 604 | |
| 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. |
| 612 | |
| 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: |
| 616 | |
| 617 | ------------- |
| 618 | information_if_bad(X) = N - number_of_ancestors(X) (TRUE) |
| 619 | ------------- |
| 620 | |
| 621 | where N is the number of commits in the (cleaned up) graph. |
| 622 | |
| 623 | So in the end this means that to find the best bisection commits we |
| 624 | should maximize the function: |
| 625 | |
| 626 | ------------- |
| 627 | f(X) = min(number_of_ancestors(X), N - number_of_ancestors(X)) |
| 628 | ------------- |
| 629 | |
| 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). |
| 632 | |
| 633 | Let's take the following graph as an example: |
| 634 | |
| 635 | ------------- |
Andreas Heiduk | 39a3682 | 2018-10-22 22:45:42 +0200 | [diff] [blame] | 636 | G-H-I-J |
| 637 | / \ |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 638 | A-B-C-D-E-F O |
Andreas Heiduk | 39a3682 | 2018-10-22 22:45:42 +0200 | [diff] [blame] | 639 | \ / |
| 640 | K-L-M-N |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 641 | ------------- |
| 642 | |
| 643 | If we compute the following non optimal function on it: |
| 644 | |
| 645 | ------------- |
| 646 | g(X) = min(number_of_ancestors(X), number_of_descendants(X)) |
| 647 | ------------- |
| 648 | |
| 649 | we get: |
| 650 | |
| 651 | ------------- |
Andreas Heiduk | 39a3682 | 2018-10-22 22:45:42 +0200 | [diff] [blame] | 652 | 4 3 2 1 |
| 653 | G-H-I-J |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 654 | 1 2 3 4 5 6/ \0 |
| 655 | A-B-C-D-E-F O |
Andreas Heiduk | 39a3682 | 2018-10-22 22:45:42 +0200 | [diff] [blame] | 656 | \ / |
| 657 | K-L-M-N |
| 658 | 4 3 2 1 |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 659 | ------------- |
| 660 | |
| 661 | but with the algorithm used by git bisect we get: |
| 662 | |
| 663 | ------------- |
Andreas Heiduk | 39a3682 | 2018-10-22 22:45:42 +0200 | [diff] [blame] | 664 | 7 7 6 5 |
| 665 | G-H-I-J |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 666 | 1 2 3 4 5 6/ \0 |
| 667 | A-B-C-D-E-F O |
Andreas Heiduk | 39a3682 | 2018-10-22 22:45:42 +0200 | [diff] [blame] | 668 | \ / |
| 669 | K-L-M-N |
| 670 | 7 7 6 5 |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 671 | ------------- |
| 672 | |
| 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). |
| 678 | |
| 679 | So the current algorithm seems to be the best possible given what we |
| 680 | initially supposed. |
| 681 | |
| 682 | Skip algorithm |
| 683 | ~~~~~~~~~~~~~~ |
| 684 | |
| 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: |
| 688 | |
| 689 | 6) sort the commit by decreasing associated value |
| 690 | |
| 691 | 7) if the first commit has not been skipped, we can return it and stop |
Jean-Noël Avila | df49a80 | 2020-10-08 22:23:54 +0200 | [diff] [blame] | 692 | here |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 693 | |
| 694 | 8) otherwise filter out all the skipped commits in the sorted list |
| 695 | |
| 696 | 9) use a pseudo random number generator (PRNG) to generate a random |
Jean-Noël Avila | df49a80 | 2020-10-08 22:23:54 +0200 | [diff] [blame] | 697 | number between 0 and 1 |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 698 | |
| 699 | 10) multiply this random number with its square root to bias it toward |
Jean-Noël Avila | df49a80 | 2020-10-08 22:23:54 +0200 | [diff] [blame] | 700 | 0 |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 701 | |
| 702 | 11) multiply the result by the number of commits in the filtered list |
Jean-Noël Avila | df49a80 | 2020-10-08 22:23:54 +0200 | [diff] [blame] | 703 | to get an index into this list |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 704 | |
| 705 | 12) return the commit at the computed index |
| 706 | |
| 707 | Skip algorithm discussed |
| 708 | ~~~~~~~~~~~~~~~~~~~~~~~~ |
| 709 | |
| 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 |
Thomas Ackermann | 2de9b71 | 2013-01-21 20:17:53 +0100 | [diff] [blame] | 713 | developed in Git version 1.5.4 (released on February 1st 2008) until |
| 714 | Git version 1.6.4 (released July 29th 2009). |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 715 | |
| 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. |
| 721 | |
| 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. |
| 725 | |
| 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. |
| 729 | |
| 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). |
| 733 | |
| 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. |
| 736 | |
| 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. |
| 741 | |
| 742 | So using a PRNG with a bias to favor commits away from the good and |
| 743 | bad commits looked like a good choice. |
| 744 | |
| 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. |
| 751 | |
| 752 | Checking merge bases |
| 753 | ~~~~~~~~~~~~~~~~~~~~ |
| 754 | |
| 755 | There is another tweak in the bisection algorithm that has not been |
| 756 | described in the "bisection algorithm" above. |
| 757 | |
| 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". |
| 761 | |
| 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. |
| 769 | |
| 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: |
| 772 | |
| 773 | ------------- |
| 774 | A-B-C-D-E-F-G <--main |
| 775 | \ |
Andreas Heiduk | 39a3682 | 2018-10-22 22:45:42 +0200 | [diff] [blame] | 776 | H-I-J <--dev |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 777 | ------------- |
| 778 | |
| 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. |
| 781 | |
| 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. |
| 785 | |
| 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. |
| 789 | |
| 790 | So we would be left with only: |
| 791 | |
| 792 | ------------- |
| 793 | H-I-J |
| 794 | ------------- |
| 795 | |
| 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"? |
| 798 | |
| 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! |
| 801 | |
Ralf Wildenhues | 6a5d0b0 | 2010-01-31 14:24:39 +0100 | [diff] [blame] | 802 | And yes it can happen in practice that people working on one branch |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 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. |
| 807 | |
| 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: |
| 813 | |
| 814 | ------------- |
| 815 | $ git bisect start dev main |
| 816 | ------------- |
| 817 | |
| 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. |
| 823 | |
| 824 | If it happens that one merge base is bad, then the bisection process |
| 825 | is stopped with a message like: |
| 826 | |
| 827 | ------------- |
| 828 | The merge base BBBBBB is bad. |
| 829 | This means the bug has been fixed between BBBBBB and [GGGGGG,...]. |
| 830 | ------------- |
| 831 | |
| 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. |
| 834 | |
| 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: |
| 838 | |
| 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 | ------------- |
| 844 | |
| 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. |
| 848 | |
| 849 | So if there is no bad merge base, the bisection process continues as |
| 850 | usual after this step. |
| 851 | |
| 852 | Best bisecting practices |
| 853 | ------------------------ |
| 854 | |
| 855 | Using test suites and git bisect together |
| 856 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 857 | |
| 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. |
| 863 | |
| 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: |
| 868 | |
| 869 | ------------- |
| 870 | c * N * T + b * M * log2(M) tests |
| 871 | ------------- |
| 872 | |
| 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). |
| 875 | |
Jonathan Nieder | 4fccc04 | 2010-08-20 05:40:31 -0500 | [diff] [blame] | 876 | So of course it's much better as it's O(N * T) vs O(N * T * M) if |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 877 | you would test everything after each commit. |
| 878 | |
| 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. |
| 883 | |
| 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. |
| 890 | |
| 891 | So if you know how to create test cases and how to bisect, you will be |
| 892 | subject to a virtuous circle: |
| 893 | |
| 894 | more tests => easier to create tests => easier to bisect => more tests |
| 895 | |
| 896 | So test suites and "git bisect" are complementary tools that are very |
| 897 | powerful and efficient when used together. |
| 898 | |
| 899 | Bisecting build failures |
| 900 | ~~~~~~~~~~~~~~~~~~~~~~~~ |
| 901 | |
| 902 | You can very easily automatically bisect broken builds using something |
| 903 | like: |
| 904 | |
| 905 | ------------- |
| 906 | $ git bisect start BAD GOOD |
| 907 | $ git bisect run make |
| 908 | ------------- |
| 909 | |
| 910 | Passing sh -c "some commands" to "git bisect run" |
| 911 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 912 | |
| 913 | For example: |
| 914 | |
| 915 | ------------- |
| 916 | $ git bisect run sh -c "make || exit 125; ./my_app | grep 'good output'" |
| 917 | ------------- |
| 918 | |
| 919 | On the other hand if you do this often, then it can be worth having |
| 920 | scripts to avoid too much typing. |
| 921 | |
| 922 | Finding performance regressions |
| 923 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 924 | |
| 925 | Here is an example script that comes slightly modified from a real |
| 926 | world script used by Junio Hamano <<4>>. |
| 927 | |
| 928 | This script can be passed to "git bisect run" to find the commit that |
| 929 | introduced a performance regression: |
| 930 | |
| 931 | ------------- |
| 932 | #!/bin/sh |
| 933 | |
| 934 | # Build errors are not what I am interested in. |
| 935 | make my_app || exit 255 |
| 936 | |
| 937 | # We are checking if it stops in a reasonable amount of time, so |
| 938 | # let it run in the background... |
| 939 | |
| 940 | ./my_app >log 2>&1 & |
| 941 | |
| 942 | # ... and grab its process ID. |
| 943 | pid=$! |
| 944 | |
| 945 | # ... and then wait for sufficiently long. |
| 946 | sleep $NORMAL_TIME |
| 947 | |
| 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 |
| 958 | fi |
| 959 | ------------- |
| 960 | |
| 961 | Following general best practices |
| 962 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 963 | |
| 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. |
| 967 | |
| 968 | It is also a good idea when using any VCS to have only one small |
| 969 | logical change in each commit. |
| 970 | |
| 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 |
Ville Skyttä | 6b677a2 | 2010-07-20 00:17:17 +0300 | [diff] [blame] | 974 | only reviewed by the committer. |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 975 | |
| 976 | Another good idea is to have good commit messages. They can be very |
| 977 | helpful to understand why some changes were made. |
| 978 | |
| 979 | These general best practices are very helpful if you bisect often. |
| 980 | |
| 981 | Avoiding bug prone merges |
| 982 | ~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 983 | |
| 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. |
| 988 | |
| 989 | For example one branch can change the semantic of a function while the |
| 990 | other branch add more calls to the same function. |
| 991 | |
| 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. |
| 998 | |
| 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. |
| 1004 | |
| 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. |
| 1007 | |
| 1008 | And testing can be done more often in special integration branches |
| 1009 | like linux-next for the linux kernel. |
| 1010 | |
| 1011 | Adapting your work-flow |
| 1012 | ~~~~~~~~~~~~~~~~~~~~~~~ |
| 1013 | |
| 1014 | A special work-flow to process regressions can give great results. |
| 1015 | |
| 1016 | Here is an example of a work-flow used by Andreas Ericsson: |
| 1017 | |
| 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) |
| 1022 | |
| 1023 | And here is what Andreas said about this work-flow <<5>>: |
| 1024 | |
| 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 |
Thomas Ackermann | 2de9b71 | 2013-01-21 20:17:53 +0100 | [diff] [blame] | 1028 | which just measures wall-clock time). Since we moved to Git, we've |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 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 |
Thomas Ackermann | 2de9b71 | 2013-01-21 20:17:53 +0100 | [diff] [blame] | 1031 | bugs (we're quite proud of how lazy we are to let Git find the bugs |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 1032 | for us). Each new release results in ~40% fewer bugs (almost certainly |
| 1033 | due to how we now feel about writing tests). |
| 1034 | _____________ |
| 1035 | |
| 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. |
| 1039 | |
| 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. |
| 1044 | |
| 1045 | So a good work-flow should be designed around the above points. That |
| 1046 | is making bisecting easier, more useful and standard. |
| 1047 | |
| 1048 | Involving QA people and if possible end users |
| 1049 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 1050 | |
| 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). |
| 1055 | |
| 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. |
| 1059 | |
| 1060 | For example David Miller wrote <<6>>: |
| 1061 | |
| 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 | _____________ |
| 1069 | |
| 1070 | This means that it is often "cheaper" if QA people or end users can do |
| 1071 | it. |
| 1072 | |
| 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. |
| 1079 | |
| 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. |
| 1083 | |
| 1084 | Using complex scripts |
| 1085 | ~~~~~~~~~~~~~~~~~~~~~ |
| 1086 | |
| 1087 | In some cases like for kernel development it can be worth developing |
| 1088 | complex scripts to be able to fully automate bisecting. |
| 1089 | |
| 1090 | Here is what Ingo Molnar says about that <<7>>: |
| 1091 | |
| 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 | _____________ |
| 1102 | |
| 1103 | Combining test suites, git bisect and other systems together |
| 1104 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 1105 | |
Ville Skyttä | 928f0ab | 2018-06-22 09:50:37 +0300 | [diff] [blame] | 1106 | We have seen that test suites and git bisect are very powerful when |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 1107 | used together. It can be even more powerful if you can combine them |
| 1108 | with other systems. |
| 1109 | |
| 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. |
| 1116 | |
| 1117 | |
| 1118 | The future of bisecting |
| 1119 | ----------------------- |
| 1120 | |
| 1121 | "git replace" |
| 1122 | ~~~~~~~~~~~~~ |
| 1123 | |
| 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. |
| 1128 | |
| 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). |
| 1134 | |
| 1135 | For example: |
| 1136 | |
| 1137 | ------------- |
| 1138 | ...-Y-BBC-X1-X2-X3-X4-X5-X6-BFC-Z-... |
| 1139 | ------------- |
| 1140 | |
| 1141 | where we know that Y is good and BFC is bad, and where BBC and X1 to |
| 1142 | X6 are untestable. |
| 1143 | |
| 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. |
| 1150 | |
| 1151 | For example: |
| 1152 | |
| 1153 | ------------- |
| 1154 | (BBC+BFC)-X1'-X2'-X3'-X4'-X5'-X6'-Z' |
| 1155 | / |
| 1156 | ...-Y-BBC-X1-X2-X3-X4-X5-X6-BFC-Z-... |
| 1157 | ------------- |
| 1158 | |
| 1159 | where commits quoted with ' have been rebased. |
| 1160 | |
| 1161 | You can easily create such a branch with Git using interactive rebase. |
| 1162 | |
| 1163 | For example using: |
| 1164 | |
| 1165 | ------------- |
| 1166 | $ git rebase -i Y Z |
| 1167 | ------------- |
| 1168 | |
| 1169 | and then moving BFC after BBC and squashing it. |
| 1170 | |
| 1171 | After that you can start bisecting as usual in the new branch and you |
| 1172 | should eventually find the first bad commit. |
| 1173 | |
| 1174 | For example: |
| 1175 | |
| 1176 | ------------- |
| 1177 | $ git bisect start Z' Y |
| 1178 | ------------- |
| 1179 | |
| 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. |
| 1189 | |
| 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.) |
| 1194 | |
| 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. |
| 1202 | |
| 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. |
| 1207 | |
| 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. |
| 1211 | |
| 1212 | With the example above that would give: |
| 1213 | |
| 1214 | ------------- |
| 1215 | (BBC+BFC)-X1'-X2'-X3'-X4'-X5'-X6'-Z'-... |
| 1216 | / |
| 1217 | ...-Y-BBC-X1-X2-X3-X4-X5-X6-BFC-Z |
| 1218 | ------------- |
| 1219 | |
| 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. |
| 1225 | |
| 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. |
| 1230 | |
Thomas Ackermann | 2de9b71 | 2013-01-21 20:17:53 +0100 | [diff] [blame] | 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. |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 1234 | |
| 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. |
| 1241 | |
| 1242 | Bisecting sporadic bugs |
| 1243 | ~~~~~~~~~~~~~~~~~~~~~~~ |
| 1244 | |
| 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. |
| 1248 | |
| 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. |
| 1252 | |
| 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. |
| 1261 | |
| 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>>: |
| 1265 | |
| 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 | _____________ |
| 1273 | |
| 1274 | But BBChop is independent of any VCS and it would be easier for Git |
| 1275 | users to have something integrated in Git. |
| 1276 | |
| 1277 | Conclusion |
| 1278 | ---------- |
| 1279 | |
| 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. |
| 1285 | |
| 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: |
| 1292 | |
| 1293 | _____________ |
| 1294 | a _lot_. |
| 1295 | |
| 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. |
| 1300 | |
| 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'. |
| 1303 | |
| 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. |
| 1308 | |
| 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. |
| 1314 | |
| 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. |
| 1318 | |
| 1319 | So git bisect is unconditional goodness - and feel free to quote that |
| 1320 | ;-) |
| 1321 | _____________ |
| 1322 | |
Ondřej Bílka | 17b83d7 | 2013-07-22 23:02:23 +0200 | [diff] [blame] | 1323 | Acknowledgments |
John Keeping | be510e0 | 2015-09-25 13:59:35 +0100 | [diff] [blame] | 1324 | --------------- |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 1325 | |
| 1326 | Many thanks to Junio Hamano for his help in reviewing this paper, for |
Thomas Ackermann | 2de9b71 | 2013-01-21 20:17:53 +0100 | [diff] [blame] | 1327 | reviewing the patches I sent to the Git mailing list, for discussing |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 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. |
| 1330 | |
| 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. |
| 1335 | |
| 1336 | Many thanks to Linus Torvalds for inventing, developing and |
| 1337 | evangelizing "git bisect", Git and Linux. |
| 1338 | |
| 1339 | Many thanks to the many other great people who helped one way or |
Thomas Ackermann | 2de9b71 | 2013-01-21 20:17:53 +0100 | [diff] [blame] | 1340 | another when I worked on Git, especially to Andreas Ericsson, Johannes |
Christian Couder | 69a9cd3 | 2009-11-08 16:09:47 +0100 | [diff] [blame] | 1341 | Schindelin, H. Peter Anvin, Daniel Barkalow, Bill Lear, John Hawley, |
| 1342 | Shawn O. Pierce, Jeff King, Sam Vilain, Jon Seymour. |
| 1343 | |
| 1344 | Many thanks to the Linux-Kongress program committee for choosing the |
| 1345 | author to given a talk and for publishing this paper. |
| 1346 | |
| 1347 | References |
| 1348 | ---------- |
| 1349 | |
Andrei Rybak | f5156f1 | 2023-01-10 10:32:51 +0100 | [diff] [blame] | 1350 | - [[[1]]] https://web.archive.org/web/20091206032101/http://www.nist.gov/public_affairs/releases/n02-10.htm['Software Errors Cost U.S. Economy $59.5 Billion Annually'. Nist News Release.] See also https://www.nist.gov/system/files/documents/director/planning/report02-3.pdf['The Economic Impacts of Inadequate Infratructure for Software Testing'. Nist Planning Report 02-3], Executive Summary and Chapter 8. |
Andrei Rybak | 18ecb23 | 2023-01-10 10:32:50 +0100 | [diff] [blame] | 1351 | - [[[2]]] https://www.oracle.com/java/technologies/javase/codeconventions-introduction.html['Code Conventions for the Java Programming Language: 1. Introduction'. Sun Microsystems.] |
Jeff King | e52a53d | 2017-04-20 16:32:33 -0400 | [diff] [blame] | 1352 | - [[[3]]] https://en.wikipedia.org/wiki/Software_maintenance['Software maintenance'. Wikipedia.] |
Jeff King | 3eae30e | 2019-11-27 07:54:04 -0500 | [diff] [blame] | 1353 | - [[[4]]] https://lore.kernel.org/git/7vps5xsbwp.fsf_-_@assigned-by-dhcp.cox.net/[Junio C Hamano. 'Automated bisect success story'.] |
Jeff King | e52a53d | 2017-04-20 16:32:33 -0400 | [diff] [blame] | 1354 | - [[[5]]] https://lwn.net/Articles/317154/[Christian Couder. 'Fully automated bisecting with "git bisect run"'. LWN.net.] |
| 1355 | - [[[6]]] https://lwn.net/Articles/277872/[Jonathan Corbet. 'Bisection divides users and developers'. LWN.net.] |
Denton Liu | dcee037 | 2019-12-02 11:26:18 -0800 | [diff] [blame] | 1356 | - [[[7]]] https://lore.kernel.org/lkml/20071207113734.GA14598@elte.hu/[Ingo Molnar. 'Re: BUG 2.6.23-rc3 can't see sd partitions on Alpha'. Linux-kernel mailing list.] |
Jeff King | e52a53d | 2017-04-20 16:32:33 -0400 | [diff] [blame] | 1357 | - [[[8]]] https://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]]] https://github.com/Ealdwulf/bbchop[Ealdwulf. 'bbchop'. GitHub.] |