カーネルにおけるリグレッションの特定

例えば、2.6.17では問題ないのに、2.6.18だとなぜか問題が発生するとする。linux kernel は git というソースコード管理システムによって、全ての変更が管理されているので、その機能を利用して問題を発生させたパッチを特定する事ができる。

基本的な考え方は、コミットしたパッチを問題を発生させた組と、発生しない組にわけていって、問題を絞り込む。2分検索だ。

例えば、1000個分の変更がコミットされていたとする。これを問題が発生しない状況から一個一個順ぐりにあてていき、問題が発生したら、最後にあてたパッチが原因だということがわかる。この順ぐりにあてていく場合、最悪1000回試行錯誤しなくてはいけない。

2分検索の場合、まづ、500個分あてた状態で(gitで簡単にそのような状況をつくれる)試験をし、仮に問題が発生しなければ、残りの500個に問題があるので、さらに、その半分250個をあて(最初から見ると750個のところ)試験をする。仮に問題が発生したとしたら、最初の500個分のなかに問題を発生させるパッチがあるので、さらにその半分の地点の250個分をあてた時点で試験をする。その結果によって、さらに問題を絞りこむ。

git bisectというコマンドがそれを簡単にやってくれる。手始めにOKのバージョンとNGのバージョンを設定し、その後、テストを繰り返し、テスト結果にしたがって、もし、問題が発生したら(bad)、OKであれば(good)。
git bisect bad
ないし
git bisect good
として問題をしぼりこむ。

以下実例。

# git bisect start
# git bisect good v2.6.17
# git bisect bad v2.6.18
Bisecting: 3399 revisions left to test after this
[2a2ed2db353d949c06b6ef8b6913f65b39111eab] Merge git://git.kernel.org/pub/scm/linux/kernel/git/sam/kbuild
# git bisect bad
Bisecting: 1699 revisions left to test after this
[8d3c138b77f195ca0eee6fb639ae73f5ea9edb6b] page migration: Update documentation
# git bisect good
Bisecting: 849 revisions left to test after this
[88ca8ed0b7f2f04a055ff3c389f398ba3ad3d27d] V4L/DVB (4048): Add support for the Texas Instruments TLV320AIC23B audio codec
... （中略）
# git bisect good
Bisecting: 3 revisions left to test after this
[c22ce143d15eb288543fe9873e1c5ac1c01b69a1] x86: cache pollution aware __copy_from_user_ll()
# git bisect bad
Bisecting: 1 revisions left to test after this
[f2c780c1fdbe5008c902c2d7e37242ac5e60f0b9] Au1550/1200: add missing PSC #define's, make OSS driver use the proper ones
# git bisect good
Bisecting: 0 revisions left to test after this
[7dbdf43cfa635ddc3701cc8d1eab07597cd731c0] mips: fix number of mremap arguments
# git bisect good
c22ce143d15eb288543fe9873e1c5ac1c01b69a1 is first bad commit
commit c22ce143d15eb288543fe9873e1c5ac1c01b69a1
Author: Hiro Yoshioka 

Date:   Fri Jun 23 02:04:16 2006 -0700

    [PATCH] x86: cache pollution aware __copy_from_user_ll()

    Use the x86 cache-bypassing copy instructions for copy_from_user().

...
    Signed-off-by: Hiro Yoshioka 

    Signed-off-by: Andrew Morton 

    Signed-off-by: Linus Torvalds 


:040000 040000 73b282577d95f4b69f046f715ac6a5a4694ba758 a2b88cac24b674c0519352c3f74a122ed6e46e7a M      arch
:040000 040000 e15615138743db3d63ba41ca2c0cf00854e601eb e1d7a032e27ab3cb0bbe6df743d1ae644bd8a999 M      include
:040000 040000 8361e3dcee117b08ccce5ccc9d451d84b07edfad 847b80b43154037f25781dda0e059df7e94c1ff8 M      mm

ふんぎゃーー。わたしのパッチで何か問題があるらしい。
という感じになる。

今回このブログを書くきっかけは、下記のスレッドにある問題。2.6.18にしたらなぜかファイルがcorruptionした。
http://marc.info/?t=119116762100001&r=1&w=2

上記のようにbisectしてみたら、どうもcache pollution aware patchがなにやらやっているらしい。
http://marc.info/?l=linux-kernel&m=119135926624999&w=2

gitのログでわたしのメールアドレスが明記されているので、メールをCCされてしまって気がついた。

それにしても3399もあるコミットからいとも簡単に問題となるパッチを特定しちゃうんだからgitというツールはすごい。

さらに言うとLinusは何千もあるパッチのうち、当該パッチはmovntiを利用していて、キャッシュをバイパスしてデータをストアしているということを正確に理解している。

http://marc.info/?l=linux-kernel&m=119144213218621&w=2
http://marc.info/?l=linux-kernel&m=119146929402139&w=2

Linusってやっぱり神だよ。

git bisectのマニュアル
http://www.kernel.org/pub/software/scm/git/docs/git-bisect.html

Git を使ってソース・コードを管理する
http://www-06.ibm.com/jp/developerworks/linux/060809/j_l-git.shtml

Real-life kernel debugging scenario
http://kernel.org/pub/software/scm/git/docs/v1.3.3/howto/isolate-bugs-with-bisect.txt

Bisection searches/みたのブログ
http://blog.miraclelinux.com/mita/2006/06/bisection_searc.html

Comments

[投稿： sakaia]

やはり、binary searchでのRegression用のコマンドがgitにはあるのですね。
素朴な疑問ですが、カーネルを入れ替えるには、再起動が必須と思いますが、どのような処理で自動化しているのでしょう？
Xenで使われている。mercurialには、知る限りまだないです。あえて言えば、hg annotateあたりが、便利だったりします。(ソースコードの1行ごとに変更を行った版数(Change Set)が表示されます）

[投稿： hyoshiok]

sakaiaさん、コメントありがとうございます。

カーネルを入れ換えるには当然再起動が必要です。今回の例では省いていますが、カーネルビルド、再起動、テスト実行、結果の確認のステップが必須です。これは手作業でやることを想定しています。一回の試行に1時間かかるとすると12回の試行なので、12時間、一日半ほどかかりますね。

[投稿： sakaia]

やはりそうですか？
OSなどでの自動化は、まだ、夢ですね。
それにしても、Linuxは2.6.23にしても6700近いパッチを管理しているとは驚きです。
Xenと比較しても7倍ぐらいのパッチの数です。