< 2.6.17 な Linux に存在する flock の double free バグ

Linux Kernel 2.6.17(正しくは 2.6.16.x で入ったのかもしれないが…) で新しく入った修正の一つに、flock(2) システムコール起因でカーネルがメモリをダブルバインドする、というものがある。

これを修正するパッチ自体は、2つ。
http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=993dfa8776308dcfd311cf77a3bbed4aa11e9868
http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=9cedc194a7735e5d74ad26d3825247dc65a4d98e
最初のパッチが問題の本質を直して、2つ目のパッチはその修正の際に、異常系処理が甘くてエラーが還らなくなっていたのを直した、というものだ。

あぁ、あれね、と判っている人はこのバグが高負荷時に結構酷い確率で頻発することも知っているでしょう。
RHEL4U4でもまだ直っていないので、是非 RedHat にギャーギャー言ってください。
^*1

当然、ここでは「で? それはどういうバグなの?」という質問してくれる、ヨイ子のみんなのためにある。つーてもいきなり答はタイトルに書いてありますが。


*1) morikawaさん、情報ありがとうございます _o_。

つーかこれは修正し忘れですね。大昔、これを書き始めた時の情報を更新し忘れてました。

---

なぜコレをここに書くのかと言うと、理由は2つ。

1つ目は Linux Kernel の内部構造が double free に弱い(コレ自体はしょうがない)ため、類似のバグがあると、このバグを踏んだかなり後になってから いきなり kernel がぶっ倒れる、という事が多々あるからだ。この症状から真の原因を直接求めるのははっきり言って不可能に近い。が、なぜ不可能なのかをよく判っていない人に説明するのもかなり困難だ。なのでここに書いておけば、再びそういう目にあったときもここを見れば判る。

2つ目は、このバグがタイミング依存性の高い、かなりいやらしい構造をしたバグだから、だ。同期系のプログラムはかなり丁寧に動作を追わないと、いつ足元を掬われるか判らない。そのためには、いろいろな「実在したバグのケース」を記録しておくのが一番だ。というか、ややこしすぎて厳密に覚えていないと意味がないのに、すぐ忘れるからここに書くわけ。

---

とりあえず、パッチは上記にあるが、ソースコードはこんな感じだ。

2.6.16: http://lxr.linux.no/linux+v2.6.16/fs/locks.c の flock_lock_file()
2.6.17: http://lxr.linux.no/linux+v2.6.17/fs/locks.c の flock_lock_file()

で、この flock_lock_file() を呼び出しているのは sys_flock() 関数… flock() システムコールの入り口だ:
2.6.16: http://lxr.linux.no/linux+v2.6.16/fs/locks.c#L1495
2.6.17: http://lxr.linux.no/linux+v2.6.17/fs/locks.c#L1535

sys_flock() の中で flock_lock_file_wait() という関数が呼ばれている:
     http://lxr.linux.no/linux+v2.6.17/fs/locks.c#L1569

flock_lock_file_wait() はここだ：
     http://lxr.linux.no/linux+v2.6.17/fs/locks.c#L1496
で、flock_lock_file_wait() の中のここで flock_lock_file() が呼ばれている:
     http://lxr.linux.no/linux+v2.6.17/fs/locks.c#L1501

これが、全体の流れだ。

で、メインの処理は flock_lock_file() が受け持っている。

まず、flock_lock_file() の中で kernel 全体を lock している。つーてもシングルプロセッサの場合は何もしていなくて、SMPの場合だけ、lock が必要な場所で lock をかけている。これが lock_kernel() と unlock_kernel()。もし、kernel_lock がすでに取られていたら、SMPの場合はこのロックが解除されるのを待つことになる。

先に 2.6.17 …つまりバグが修正された後のコードを見て欲しい。lock_kernel() が呼ばれているのはここだ:
        http://lxr.linux.no/linux+v2.6.17/fs/locks.c#L739
一方、unlock_kernel() が呼ばれているのはここ:
        http://lxr.linux.no/linux+v2.6.17/fs/locks.c#L788

ようするに入り口の所すぐで kernel_lock を取得し、この関数から出ていくまで一度も解放しない。これが正しいやり方だ。この間のどこかで kernel_lock を解放してしまうと、仮にそのあとすぐ kernel_lock を再取得したとしても、その間に別CPUが処理に入り込んでくる危険性がある。

で、一方で 2.6.16 は
2.6.17と同様、関数の入り口でkernel_lock を取得している。
         http://lxr.linux.no/linux+v2.6.16/fs/locks.c#L722
で、関数の出口で kernel_lock を解放している:
         http://lxr.linux.no/linux+v2.6.16/fs/locks.c#L768

が、その途中で一度 kernel_lock を解放し:
        http://lxr.linux.no/linux+v2.6.16/fs/locks.c#L737
再度取得し直している。
        http://lxr.linux.no/linux+v2.6.16/fs/locks.c#L749

問題は、この L737 出の開放の後、L749 での再ロックまでの間に、別のCPUが flock_lock_file() 関数に入ってくる危険性がある、ということだ。最初の git パッチ にはこうある:

sys_flock() currently has a race which can result in a double free in the
multi-thread case.

Thread 1 Thread 2

sys_flock(file, LOCK_EX)
sys_flock(file, LOCK_UN)

If Thread 2 removes the lock from inode->i_lock before Thread 1 tests for
list_empty(&lock->fl_link) at the end of sys_flock, then both threads will
end up calling locks_free_lock for the same lock.

ちょっと見辛いし判りづらいな：

SMP環境において

Thread1: sys_flock(file, LOCK_EX)
Thread2: sys_flock(file, LOCK_UN)

がほぼ同時に呼ばれたとする。ただし、最初に kernel_lock を取得したのは Thread1 の方だ。で、Thread1 が最初の unlock_kernel() を呼んだ。

この瞬間に Thread2 は kernel_lock を取得できる。で、ここ:
        http://lxr.linux.no/linux+v2.6.16/fs/locks.c#L734
この場所で、inode->i_lock を解放する。

で、ここを通り抜けた後、Thread2 が unlock_kernel() を呼ぶと、Thread1 が flock_lock_file() の後半部を通り抜け、flock_lock_file_wait() へと戻り、そこから sys_flock() へと帰る。

問題は、Thread1 が sys_flock() へと帰った後。ここ:
http://lxr.linux.no/linux+v2.6.16/fs/locks.c#L1532
で、lock_free_lock() を呼んでしまうことだ。結果として、同じロックを2重解放してしまう。

lock_free_lock() のコードはここだ:
2.6.16:    http://lxr.linux.no/linux+v2.6.16/fs/locks.c#L157
2.6.17:    http://lxr.linux.no/linux+v2.6.17/fs/locks.c#L169

ここで問題なのはただ1点、kmem_cache_free() を呼び出すところだ。これを同じ構造体に対して行なってしまう。結果として、2重解放が行われる。

---

二重解放されたメモリは、やがて再利用される。二箇所の、全然関係ない所で。

それぞれを利用している kernel thread や、ルーチンはまさか他の人も同じ部分を利用している人がいるなんて考えてコーディングされていない。というか、それを疑ったら何もできなくなっちゃう。

で、ある日。自分が昔設定した値に従って処理を実行しようとしたのに、実はその値は別の人が別の目的で書いた値で…結果としてそのせいで、kernel 全体がクラッシュする、という状態に陥るのです。

Brave to stay

This brave Mantis has been on "outside" of the window of 29th Floor elevator hall since noon.

I shoot this photo on my way back to home, 17:48, and (s)he was still there!

Hanging upside down on the glass must be tremendously tough job. And since (s)he have a wing to fly, it's not hard for h(im|er) to give up and fly a little bit aside for better environment. What a brave.

...

Well ... it might simply be that this insect was stupid as to stay though ... staying on tough situation for nothing ...