Binary searching with the help of quilt

Suppose that we have a quilt series of patches with the following contents of the series file:

01-kmemleak-base.patch
02-kmemleak-doc.patch
03-kmemleak-hooks.patch
04-kmemleak-modules.patch
05-kmemleak-i386.patch
06-kmemleak-arm.patch
07-kmemleak-false-positives.patch
08-kmemleak-keep-init.patch
09-kmemleak-test.patch
10-kmemleak-maintainers.patch
#11-new-locking.patch
#12-new-locking-fix.patch
13-vt-memleak-fix.patch
14-new-locking-fix.patch
15-fix-for-possible-leak-in-delayacctc.patch

and we cannot build the kernel after applying all of the above patches. To find the patch that causes the problem to appear, we can carry out a binary search.

Of course, having only 13 patches to check, we can use the 'quilt patches <file_name>' command to identify patches modifying the file which fails to compile, so that we can revert them and test the kernel without them, but if the tested patchset is huge, it usually is not a good idea to revert random patches from the middle of it.

Suppose that we have applied all of the patches from the series:

$ quilt push -a
Applying patch patches/01-kmemleak-base.patch
patching file include/linux/kernel.h
[..]
patching file kernel/delayacct.c
Now at patch patches/15-fix-for-possible-leak-in-delayacctc.patch

and it turns out that something is wrong, because we cannot compile the kernel any more. First, we obtain the number of applied patches:

$ quilt applied | wc -l
13

and we revert one half of them:

$ quilt pop 6
Removing patch patches/15-fix-for-possible-leak-in-delayacctc.patch
Restoring include/linux/delayacct.h
[..]
Restoring lib/Kconfig.debug
Now at patch patches/07-kmemleak-false-positives.patch

Then, the number of patches to revert or apply in the next step is 3 (we must remember this number, so it is best to write it down somewhere). We test the kernel and find that the problem is still appearing, so we revert 3 patches:

$ quilt pop 3
[...]
Now at patch patches/04-kmemleak-modules.patch

and note that the number of patches to check in the next step is 1.

Next, we test the kernel again and find that the problem has disappeared. We thus apply one patch:

$ quilt push
[...]
Now at patch patches/05-kmemleak-i386.patch

and note that the number of patches to check in the next step will depend on the result of the subsequent kernel test. Namely, if we test the kernel and the problem reappears, we will know that 05-kmemleak-i386.patch is the source of it, since none of the ''earlier'' patches has caused it to be present. Otherwise, we will need to apply one patch more

$ quilt push
[...]
Now at patch patches/06-kmemleak-arm.patch

and if the problem reappears, we will know that this patch is ''guilty''. Otherwise, the next patch, which is 07-kmemleak-false-positives.patch, will have to be the offending one, since the problem is not present with all of the patches ''below'' it applied.

Some more useful hints about using quilt for binary searching can be found in the Andrew Morton's article How to perform bisection searches on -mm trees (http://www.zip.com.au/~akpm/linux/patches/stuff/bisecting-mm-trees.txt). In particular, you can learn from it that if the -mm tree contains a series of patches similar to the following one:

patch-blah.patch
patch-blah-blah.patch
patch-blah-blah-fix1.patch
patch-blah-blah-fix2.patch
patch-blah-blah-fix3.patch

you should treat them as a single patch. That is, you should always revert them all or apply them all at once.

A practical example of binary searching with the help of quilt is shown in the movie available at http://www.youtube.com/watch?v=LS_hTnBDIYk .