Binary searching with the help of git-bisect

Since binary searching for buggy patches is a very important debugging technique, as far as the Linux kernel is concerned, and git is the primary versioning control system used by the kernel developers, the git package contains a tool that automates binary searching, called git-bisect. It is powerful and easy to use, so it can be recommended to inexperienced kernel testers.

To explain how to use git-bisect, we suppose that there is a problem in the 2.6.18-rc5 kernel and we do not know which commit has introduced it. We know, however, that it is not present in the 2.6.18-rc4 kernel.

We start the bisection by running

$ git-bisect start

and mark the current kernel version as the first known bad one:

$ git-bisect bad

Next, we use gitk to get the commit identifier associated with the 2.6.18-rc4 version of the kernel, which is 9f737633e6ee54fc174282d49b2559bd2208391d, and mark this version as the last known good one:

$ git-bisect good 9f737633e6ee54fc174282d49b2559bd2208391d

Now, git-bisect will select a commit, more or less equally distant from the two corresponding to the first known bad and the last known good kernel versions, that we should test:

Bisecting: 202 revisions left to test after this
[c5ab964debe92d0ec7af330f350a3433c1b5b61e] spectrum_cs: Fix firmware
uploading errors

(using 'git-bisect visualize' we can see the current status of the bisection in gitk). Then, we need to compile, install and test the kernel.

Suppose that we have done it and the problem is still appearing, so we mark the current kernel version (ie. the one corresponding to the commit previously selected by git-bisect) as the first known bad one and git-bisect selects the next commit to test:

$ git-bisect bad
Bisecting: 101 revisions left to test after this
[1d7ea7324ae7a59f8e17e4ba76a2707c1e6f24d2] fuse: fix error case in
fuse_readpages

We compile the kernel, install and test it. Suppose that this time the problem is not present, so we mark the current kernel version, corresponding to the last commit selected by git-bisect, as the last known good one and let git-bisect select another commit:

git-bisect good
Bisecting: 55 revisions left to test after this
[a4657141091c2f975fa35ac1ad28fffdd756091e]
Merge gregkh@master.kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6

Next, we compile, install and test the kernel, and so on, until we get a message similar to the following one:

$ git-bisect good
1d7ea7324ae7a59f8e17e4ba76a2707c1e6f24d2 is first bad commit
commit 1d7ea7324ae7a59f8e17e4ba76a2707c1e6f24d2
Author: Jan Kowalski <a@b>
Date:   Sun Aug 13 23:24:27 2006 -0700

    [PATCH] fuse: fix error case in fuse_readpages

    Don't let fuse_readpages leave the @pages list not empty when exiting
    on error.
[...]

which contains the identifier of the commit that, most probably, has introduced the bug.

Still, we need to make sure that the bug has really been introduced by this particular commit. For this purpose we return to the initial kernel version:

$ git-bisect reset

and try to revert the commit that we have identified as the source of the problem with the help of git-bisect:

$ git-revert 1d7ea7324ae7a59f8e17e4ba76a2707c1e6f24d2

If we are lucky, the commit will be reverted cleanly and we will be able to test the kernel without it to make sure that it is buggy. Otherwise, there are some commits that depend on this one and in fact we should revert them all for the final testing.

Although the binary searching in the above example is pretty straightforward, generally it can be more complicated. For example, we may be unable to test the commit selected by git-bisect, because some more commits must be applied so that we can build the kernel. In that case we need to tell git-bisect where to continue and 'git-reset --hard' can be used for this purpose.

Suppose, for instance, that you have:

$ git-bisect start
$ git-bisect bad 5ecd3100e695228ac5e0ce0e325e252c0f11806f
$ git-bisect good f285e3d329ce68cc355fadf4ab2c8f34d7f264cb
Bisecting: 41 revisions left to test after this
[c1a13ff57ab1ce52a0aae9984594dbfcfbaf68c0] Merge branch
'upstream-linus' of
master.kernel.org:/pub/scm/linux/kernel/git/jgarzik/netdev-2.6

but you cannot compile the kernel version corresponding to the selected commit. Then, you can use 'git-reset --hard' to manually select the next commit for git-bisect:

$ git-reset --hard c4d36a822e7c51cd6ffcf9133854d5e32489d269
HEAD is now at c4d36a8... Pull osi-now into release branch

Now, after running 'git-bisect visualize' you will see that the commits 5ecd3100e695... and f285e3d329ce... are still marked as ''bad'' and ''good'', respectively, but the commit c4d36a822e7c51cd6ffcf9133854d5e32489d269 that you have selected is marked as ''bisect'' instead of c1a13ff57ab1ce52a0aae9984594dbfcfbaf68c0.

It is also possible that a new version of the kernel appears on the kernel.org server while you are carrying out a bisection search. In that case you may suspect that the bug under investigation has been fixed in the new kernel version, but nevertheless you may want to continue the bisection if it turns out not to be the case. Then, you can run

$ cp .git/BISECT_LOG ../bisect.replay
$ git-bisect reset

and use git-pull, as usual, to get the new kernel version (see Section 4.1). After testing it, if the bug is still present, you can do:

$ git-bisect replay ../bisect.replay

to return to the point at which you have ''suspended'' the binary search.

To summarize, the most often used commands related to binary searching with the help of git-bisect are:

• git-bisect start - starts a new binary search
• git-bisect reset - goes back to the initial kernel version and finishes the bisection
• git-bisect good <commit> - marks the commit given by <commit>, or the current commit, as corresponding to the last known good kernel version
• git-bisect bad <commit> - marks the commit given by <commit>, or the current commit, as corresponding to the first known bad kernel version
• git-bisect visualize - uses gitk to show changes between the last known good and the first known bad kernel versions

Additionally,

• git-bisect replay - may be used to return to the point at which the bisection has been ''suspended'' in order to test a new version of the kernel
• git-reset --hard - can be used to select the next commit for git-bisect manually

For more information about git-bisect see its manual page ('man git-bisect') that contains more detailed description of it. You can also refer to the git documentation available on the Web (eg. at http://www.kernel.org/pub/software/scm/git/docs).

A practical example of binary searching with the help of git-bisect is shown in the movie available at http://www.youtube.com/watch?v=R7_LY-ceFbE