Chapter 17
Troubleshooting with Bisection
During development, it often happens that an error that was not present in earlier versions suddenly appears in functionality that has already been successfully tested. A promising strategy for debugging is to search for the commit in which the error can be observed for the first time. Since when working with Git you typically produce small commits, you can analyze the changes and find the cause quickly.
Git supports searching for faulty commits with bisection.
Bisection is based on a binary search. Starting from a known good commit and a known faulty commit, this commit history is “halved” and the “middle” commit is activated in the workspace. The active commit can then be examined for the error. Depending on whether or not the error is found in the active commit, the remaining of the history in which the error must be hiding is again “halved” and a new “middle” commit is selected. In the end, you will normally find the commit in which the error first appears.
This workflow shows
Overview
Figure 17.1 shows a commit history with a commit that is error free and another commit that is known to be faulty. A commit history does not need to be linear. However, there must be a path from the faulty commit to the error-free commit through parent relationships between the two commits.
When a bisection process is started, Git selects a suitable commit in the middle of the history. This commit can then be tested either manually or with a script and marked as “good” or “bad.” Next, the bisection task picks another commit and examines and marks it. This process is repeated until it finds a commit with the error whose direct predecessor is error-free.
Requirements
Reproducible error detection: The fault must be proven consistent, i.e., it is possible clearly to identify one version as correct or incorrect. An automated error detection, using a test case or script, must be able to detect the error.
The error detection must not be expensive: The error detection must be fast and not costly. With bisection multiple fault detections are required depending on the number of commits examined. If the time required or the cost is too great, an analytic search for the cause of the error will be more efficient.
Workflow “Troubleshooting with bisection”
During development, an error occurs, which was not present in previous versions. Bisection locates the commit that has introduced the error in the commit history.
Figure 17.1: Workflow overview
Process and Implementation
For the following operations, we have a small sample project that implements various mathematical functions. Among other things, it calculates the factorial of a number and returns a list of all factorials of 1 to 5.
> java FactorialMain
Factorial of 1 = 1 Factorial of 2 = 1 Factorial of 3 = 2 Factorial of 4 = 6 Factorial of 5 = 24
Manual Troubleshooting with Bisection
The first process describes the basic procedure of bisection, in which the test is carried out manually because of an error.
Step 1: Define the error indicator
Typically, an error will be caught by a developer, tester or user.
The first step is to analytically understand the error situation and find an indicator of the error.
The following points are examples of error indicators:
In our example, the factorial of 3 can be seen as an indicator that there is an error.
In many cases, this analysis alone already leads to finding the cause and bisection is no longer necessary.
Step 2: Find the error-free and faulty commit s
The bisection process requires an error-free commit and an erroneous commit. A good candidate for a flawless commit is the last release or the last milestone.
If you find out that the potential candidate for an error-free commit also contains the error, you should go further back in history.
Finding an erroneous commit should not be hard because the error was already reported. However, if more flawed commits are found when searching for flawless commits, it makes sense to select the oldest known erroneous commit.
Below is the log output from our example that shows the commit history.
> git log --oneline
202d25d modulo finished e36fead multiply finished 918ed2f sub finished ebe741d add finished 87ac59e ComputeFactorial finished 39cbdc0 init
Analysis shows that commit 87ac59e ComputerFactorial finished is error free and commit 202d25d modulo finished is incorrect.
Step 3: Troubleshoot with bisection
Now that the error has been confined to an area in the commit history, the actual search for the error can start with bisection.
You start bisection with the bisect start command. You must specify the faulty commit as the first parameter and the error-free commit as the second parameter.
> git bisect start 202d25d 87ac59e
Bisecting: 1 revision left to test after this (roughly 1 step) [918ed2f29a44e468d690fb770aab1ad2dbae1a5a] sub finished
The bisect start command marks the first commit as the bad commit and the second commit as the good one. Subsequently, the commit located between the two commits (in this case, commit 918ed2f sub finished) is activated.
Now the workspace contains files from a commit that we are not yet sure is faulty or faultless. Thanks to the error indicator found, the version status can now be tested.
> java FactorialMain
Factorial of 1 = 1 Factorial of 2 = 1 Factorial of 3 = 2 Factorial of 4 = 6 Factorial of 5 = 24
The result from running FactorialMain in the workspace shows that the error is still there, which means the current commit is faulty.
We can now mark the current commit with one of the following commands.
In our example, the error is still present and we mark the commit as “bad.”
> git bisect bad
Bisecting: 0 revisions left to test after this (roughly 0 steps) [ebe741de3366a3fc08fbedfdfa408517dd172ca3] add finished
In response Git reports that now commit ebe741d add finished is activated. In addition, Git reports that this is the last commit that must be tested.
The re-testing of our FactorialComputer shows that this commit is error-free, and the commit will be marked as “good.”
> git bisect good
commit 918ed2f29a44e468d690fb770aab1ad2dbae1a5a Author: Rene Preissel <[email protected]> Date: Fri Jun 24 08:04:43 2011 +0200 sub finished :040000 040000 0e5bfb07e859072a564eaca073461e4a12a0ed61 329e7f864bac874c69be4531452c753cf56be794 M src
Git now tells us that the commit 918ed2f sub finished is the first commit where the error occurs. Now you can analyze the changes in the commit using Git commands (for example, git show 918ed2f).
Finally, it was found in our example that the factorial was calculated only up to n-1.
Note that before troubleshooting begins, the workspace must be set to the HEAD of the current branch again. This will be described in the next step.
Step 4: Stop or cancel bisection
After a successful root cause analysis with bisection or after deciding a bisection operation should be canceled, the workspace must be reset to the normal version of development with the bisect reset command .
> git bisect reset
Previous HEAD position was ebe741d... add finished Switched to branch 'master'
Automated Troubleshooting with Bisection
In the previous sequence, the test was to determine whether or not a commit contains a bug and was carried out manually. If the confined area of the history is very long or the test is manually very expensive, then you can also automate the test with a script and let bisection do its job.
Step 1: Define the error indicator
The error indicator is defined the same way as the manual troubleshooting with bisection. It is only necessary to ensure that the indicator can be checked automatically with a script.
Step 2: Prepare a test script
To automate troubleshooting with bisection, you have to provide a shell script that can detect the error indicator automatically. The shell script must return a different exit code depending whether or not the error is present.
Our calculator application was written in Java. As an example, we show how debugging can be automated using bisection in this environment. In other development environments, the individual scripts need to be adjusted accordingly.
Automatic verification of the actual fault is performed by a JUnit test (JUnit can be downloaded from http://www.junit.org). It simply checks if the factorial of 3 is really 6. If the result is false, then the test will fail.
public class FactorialBisectTest { @Test public void testFactorial() { long result = Computer.factorial(3); Assert.assertEquals(6, result); } }
Warning. It is important to implement this test in a new file. This file should not be versioned in Git. In a bisection process different commits are activated in the workspace one after the other. If the test file is under Git control, this file would no longer be present when an old commit is activated. On the other hand, non-versioned files will leave the change in the workspace.
The automated bisection process requires a shell script. This shell script must first compile our Java source files and then start the test.Ant is used as the build system in our example. In the Computer project, there is a build file named build.xml that can perform a clean build (ant clean compile). To run the bisection testing, another build file, named bisect-build.xml, is also provided that contains only one target to start the test. Note that this file should not be versioned with Git.
<target name="test"> <junit> <classpath refid="build.classpath" /> <test name="FakultaetsBisectTest" haltonerror="true" haltonfailure="true"/> </junit> </target>
To access the various Ant targets, there is a shell script called bisect-test.sh. This script is also not versioned with Git.
#!/bin/bash ant clean compile if [ $? -ne 0 ];then exit 125; fi ant -f bisect-build.xml if [ $? -ne 0 ];then exit 1; else exit 0; fi
This script calls the various build targets on and checks the exit code of Ant. On failure Ant returns an exit code other than 0. This needs to be converted to the desired code from the bisection process.
Step 3: Find an error-free and a defective commits
The search for a fault-free and a faulty commits is no different from the manual process. However, you can also use the JUnit test to check for the error. As an example, we select commit 87ac59e FactorialCompute finished and verify that it is error-free.
> git checkout 87ac59e > ant -f bisect-build.xml
Buildfile: bisect-build.xml test: BUILD SUCCESSFUL Total time: 0 seconds
Warning. After the process, do not forget to set the master branch back as the active branch.
> git checkout master
Step 4: Automated troubleshooting with bisection
With automated troubleshooting, bisection is also started with the bisect start command as the first bisection process. Also, the faulty commit is passed as the first parameter and the error-free commit as the second parameter.
> git bisect start 202d25d 87ac59e
Bisecting: 1 revision left to test after this (Roughly 1 step) [918ed2f29a44e468d690fb770aab1ad2dbae1a5a] sub finished
Then the bisect run command is used to execute the bisect-test.sh shell script.
> git bisect run ./bisect-test.sh
The following output is truncated, showing only the last lines of the bisect run command. It is good to see that the command finds 918ed2f sub finished as the first erroneous commit.
.. Buildfile: bisect-build.xml test: BUILD SUCCESSFUL Total time: 0 seconds 918ed2f29a44e468d690fb770aab1ad2dbae1a5a is the first bad commit commit 918ed2f29a44e468d690fb770aab1ad2dbae1a5a Author: Rene Preissel <[email protected]> Date: Fri Jun 24 08:04:43 2011 +0200 sub finished :040000 040000 0e5bfb07e859072a564eaca073461e4a12a0ed61 329e7f864bac874c69be4531452c753cf56be794 M src bisect run success
Step 5: Complete the bisection operation
After the successful troubleshooting, the bisection process must end the procedure with a bisect reset command.
> git bisect reset
Previous HEAD position was ebe741d... add finished Switched to branch 'master'
Why Not the Alternatives?
Why Not Use merge to Add the Test Scripts in Old Commits?
The procedure described takes advantage of the fact that Git leaves unversioned files in the workspace when a new commit is activated. This makes it possible to execute the “new” test scripts in old commits.
An alternative solution will be to incorporate the test scripts into a new branch (see the bisect-test branch in Figure 17.2).
In the bisection shell script, a merge of the bisect-test branch with the commit currently selected by bisection is now performed before each test run. The option --no-commit is used to prevent a permanent commit.
After the test has been performed, the changes resulting from the merge are reset using the reset command.
This sequence and an example script can be found in the online documentation of the bisect command in the Example section.
The solution that uses the bisect-test branch can be useful not only when a test case and new test scripts have been added. It can also be useful when existing code for the test must be adapted, for example because a review needs to access data not visible in the old commits.
However, the process that uses unversioned files that we described is sufficient and easier to implement in most cases.
Figure 17.2: Using the bisect-test branch
18.117.74.231