208.5日問題

• 突然の再起動によるデータの喪失

Linux Kernel 2.6.28で導入された __cycles_2_ns() パッチに不具合があった。

Pentium 4以降には、Time Slice Stamp Counterと呼ばれる64ビットのカウンターが搭載されている。このカウンターはクロック単位でカウントアップされる。1GHzであれば、秒間1G増えることになる。つまり、概ねナノ秒単位のカウンターとして使用できる。

ただし省電力制御のためCPUクロックは随時変化するため、Linuxカーネルはcycles_2_ns()という関数を用意し、TSCの値をナノ秒単位に換算する機構を用意した。

しかしながら、そのお粗末な計算方法に問題があり、約208.5日経過していると計算中に数値がオーバーフローしてしまい、変換関数は異常な値を返すため、結果システムがクラッシュする。

__cycles_2_ns()関数を修正した。修正は「sched, x86: Avoid unnecessary overflow in sched_clock」と題されている。

 static inline unsigned long long __cycles_2_ns(unsigned long long cyc)
 {
+    unsigned long long quot;
+    unsigned long long rem;
     int cpu = smp_processor_id();
     unsigned long long ns = per_cpu(cyc2ns_offset, cpu);
-    ns += cyc * per_cpu(cyc2ns, cpu) >> CYC2NS_SCALE_FACTOR;
+    quot = (cyc >> CYC2NS_SCALE_FACTOR);
+    rem = cyc & ((1ULL << CYC2NS_SCALE_FACTOR) - 1);
+    ns += quot * per_cpu(cyc2ns, cpu) +
+        ((rem * per_cpu(cyc2ns, cpu)) >> CYC2NS_SCALE_FACTOR);
     return ns;
 }

TSCは概ねナノ秒単位のカウンターである。1GHzちょうどで動作するならTSCは1ナノ秒単位でカウントアップしていることになる。更に言えば、2GHzちょうどなら0.5ナノ秒単位となる。

得られた値をscale factor倍すればナノ秒単位であり、クロックに合わせてscale factorを定義すればよいのだが、TSCは元々ほぼナノ秒単位なので、これをナノ秒単位にするとなると逆に難しい。何しろほぼナノ秒なのであるから、普通に考えればscale factorは1前後の値の小数となり、この1前後の値での浮動小数点演算が必要となってしまうからである。

そこで誰かが考えた方法は、1000倍にして計算したあと、10ビットの右シフトで1/1024するという手法であった。これなら、若干の誤差は生じるものの、浮動小数点演算も、大きな数の除算も不要で、全てが簡単な演算で済む。(この時点で嫌な予感がしたなら、エンジニアとしての素質あり)

具体的には、64ビットのTSC値に、32ビットのcyc2ns_scale(これはper_cpu()関数の返却値)を掛け、これを10ビット右シフトして64ビット変数に求めるという方法である。

さて、1/1024すればナノ秒が求まるということは、その直前はピコ秒オーダーの値となっていることになる。ピコ秒のオーダーで時間を扱うとなると、1秒を扱うのに40ビットが必要となる。となると、秒以上の値を扱う余裕は24ビットしかないことになる。

有効ビット長24ビットを秒単位で表現したときに表現できる時間は次のとおり。

2²⁴ / ( 24 × 60 × 60 ) = 194.18074日

実際には、10ビットシフトして消すため、有効ビット長54ビットのナノ秒単位であるので、表現可能な時間は次のようになる。

2⁵⁴ / ( 24 × 60 × 60 × 1000 × 1000 × 1000 ) = 208.499983日

つまりこの方法では、約208.5日経つと演算が途中でオーバーフローしてしまい、__cycles_2_ns()はいきなり0に近い値を返すことになる。かくして、カーネル内の様々な処理のスケジュールが狂い、カーネルパニックが発生してリブートしてしまったのである。