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

• how to use bisection to find faulty commits efficiently, and
• how to automate troubleshooting with bisection.

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:

• An action or a function call raises an exception, the program is canceled or an error message is displayed.
• A function returns an erroneous result for certain entries.
• A test case fails.

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.

• bisect good: The error was not observed; the commit is error-free.
• bisect bad: The error was observed; the commit is faulty.
• bisect skip: The current commit cannot be tested. Typically, it is because it does not compile or missing files. Bisection will activate another commit to test.

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.

• Exit code 0: The error was not found. Bisection should mark the commit as “good.”
• Exit codes 1-124, 126, 127: The error was found. Bisection should mark the commit as “bad.”
• Exit code 125: The test could not be performed because the application does not work. Typically, this version is not compilable. Bisection should skip the commit.

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.

• If the build fails, then exit code 125 is returned.
• If the test is successful, exit code 0 is returned.
• If the test fails, the exit code of 1 is returned.

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