okkyの銀河制圧奇譚

2013年9月29日

クラウド時代の core の解析法

クラウド・コンピューティングというと次の2つを主眼とした技術になります。

リソースを共有、適切に分散することで、ハードウェア購入・維持費を下げよう
瞬間的に大量の計算機リソースを借りる事で、必要になる計算機能力がバースト的に増大する場合に備えよう

しかし、現在の仮想化技術には、複数の物理マシンを仮想的に1台のマシンに編み上げる方法は存在しません。この事は次の単純な事実をもたらします：

物理的に保持しているマシンの台数より

仮想的に保持しているマシンの台数のほうが多い

一方で、ハードウェアをいくら仮想化しようが、その上で動作するアプリケーションの数は減りません。使うアプリケーションの種類は減りませんし、分散コンピューティングとかですと、複数のマシンで同じソフトウェアを動作させて協調分散して仕事をさせるのですから、むしろプロセス数とかは増えます。

それどころか協調分散システムでは、どこかのプログラムがヘコッとコケるのは当たり前になっているので、

こけても

即座に

別のプロセスや

別の仮想マシンを

立ち上げればええやん

という発想がまかり通っています。つまりソフトウェアの品質は低くなっている。

仮想マシンの台数は増え、ソフトウェアの動作プロセス数も増え、なおかつ品質が悪くなると何が起こるか…

システムの面倒を見る側が

見なくちゃいけない core ファイルの数が

爆発的に増大する

コアファイルを見て、適切なプログラマに

これはテメーの間違いだ!!

直しやがれ

と押し付ける交通整理役の人が大変になるってことです。

先日も、とあるシステムのコアの数を調べたら 6000 を超えてまして…総量を計算したら 3Tbyteを越えてまして…ちょっとどうしようかと思案中。

こういう作業を全部手作業だけで1つ1つ処理していくのは大変すぎます。少なくとも 深さ優先(１つづつコアを分析していく) でやったのでは死んでしまいます。ここは 幅優先(表面を撫でるように簡単なチェックをして、共通な物同士をまとめ、不要なものを破棄しながら分析する) 戦略が必要です。

というわけで、私が普段使っているやり方を少しここに書いてみようと思います。

対象は基本的に Linux になりますが、BSD などの Unix 系 OS なら、ある程度は共通していると思います。

デバッガは gdb を前提とします。多分他のデバッガでもできるんでしょうが、バッチ処理的に実施する上では gdb は便利なので。

最後に。ソースコードが無いと仮定します。
あなたの仕事はこけているコアファイルを適切なプログラマのもとに送り届けることだとします。しかもあなたは開発部隊に所属していないので、ソースコードは読めない。
そんな条件下での分析と、プログラマが出鱈目八百を答えてきた時に反論できる程度の知識を予め引きずり出す事が主な仕事とします。

まぁ、実行バイナリがあって、コアファイルがあるんだから、じっくりと時間を掛けて、本気で分析すればそりゃ問題点は判るでしょうが、どうせ直せませんからね。

コアファイルの命名規則を調べる

unix 系 OS では伝統的に、デフォルトのコアファイル名は core です。
厳密に言うと、そのプログラムにとっての「カレントディレクトリ」に core というファイル名で作られます。

すぐ判ることですが、cron で動かしたとか、daemon であるとかのプロセスのカレントディレクトリ…それももうすでにコケて core ファイルを吐いた後のプロセスのカレントディレクトリを探すのは容易なことではありません。
また、同じディレクトリで core というファイルをどんどん上書きされるのも困りますし、逆に色んなディレクトリに core ファイルを撒き散らかされるのも運用上ありがたいことではありません。
だいたい、「core」だけじゃ、何の core ファイルなんだか判らないし。

という訳で、最近の unix 系 OS は何らかの方法で、coreファイル名を指定する方法があります。ファイル名を指定する方法があるという事は、上手に使えば core ファイルを保存する絶対パスを指定できる、と言うことです。これがちゃんと設定してあれば、core　ファイルがファイルシステム中に撒き散らされる、なんてことはありません。

Linuxの場合、2.6 か 2.4.21以降であれば、
/proc/sys/kernel/core_pattern
というファイルに、パス名パターンを指定することで core ファイル名を指定できます。これは
/etc/sysctl.conf
か、そんな感じのファイル名/ディレクトリ名の下にある設定ファイルで設定できます。ココらへんは distribution/version 依存なので、各自調べて下さい。

ちなみに私の見ているシステムでは
/var/cores/%e.%p.%t.%s
になっていました。これを解釈すると：

全てのコアファイルは /var/cores/ ディレクトリ下にあります
ファイル名の最初は %e　つまり「プログラムファイルの名前」をパス名無しで…になります
. で分けた後、%p つまりプロセスIDが続きます。
これは同時刻に同じプログラムが連続してこけた場合でも区別できるようにするための工夫ですね
. を挟んで、次が %t …つまり epoch time が来ます。これはこの core ファイルが作られた(作る要因が発生した)時刻を、1970年1月1日 00:00:00 (UTC) からの時刻で表したものになります
. を挟んで、最後に %s …つまりこの core file の発生要因となったシグナル番号が来ます。

見ての通り、このファイル名をちゃんと設定するだけで、色々と面倒がスキップできることが判ります。特に最後の %s はとても有効です。

もし、この辺りを自由にできる権限があるならば、是非多くの情報がファイル名だけからでも判るように設定することを強くおすすめします。

命名規則に従って、コアファイルの表面的な情報を調べ、分類する

さて、以下の議論では /proc/sys/kernel/core_pattern が /var/cores/%e.%p.%t.%s であると仮定します。

ここで役に立ちそうなのは %t と %s です。%e は最初から human readable ですし、%p は単なる番号なので readable もへったくれもありません。

そこで %t と %s をもっと human readable にしてあげましょう。なお、以下の説明では
「もっと簡単な方法がある」
「もっと判りやすい方法がある」
どちらも受け付けません ( w )。

簡単な方から。

%s は番号⇒文字列変換配列があればよいでしょう。bash は配列が使えますので、それを使うと便利。LinuxのSIGNALのマニュアルページに書いてある表の真ん中を元に作ったのがこれです。

declare -a SIGNAL_NAME
SIGNAL_NAME[1]='SIGHUP'
SIGNAL_NAME[2]='SIGINT'
SIGNAL_NAME[3]='SIGQUIT'
SIGNAL_NAME[4]='SIGILL'
SIGNAL_NAME[5]='SIGTRAP'
SIGNAL_NAME[6]='SIGABRT'
SIGNAL_NAME[7]='SIGBUS'
SIGNAL_NAME[8]='SIGFPE'
SIGNAL_NAME[9]='SIGKILL'
SIGNAL_NAME[10]='SIGUSR1'
SIGNAL_NAME[11]='SIGSEGV'
SIGNAL_NAME[12]='SIGUSR2'
SIGNAL_NAME[13]='SIGPIPE'
SIGNAL_NAME[14]='SIGALRM'
SIGNAL_NAME[15]='SIGTERM'
SIGNAL_NAME[16]='SIGSTKFLT'
SIGNAL_NAME[17]='SIGCHLD'
SIGNAL_NAME[18]='SIGCONT'
SIGNAL_NAME[19]='SIGSTOP'
SIGNAL_NAME[20]='SIGTSTP'
SIGNAL_NAME[21]='SIGTTIN'
SIGNAL_NAME[22]='SIGTTOU'
SIGNAL_NAME[23]='SIGURG'
SIGNAL_NAME[24]='SIGXCPU'
SIGNAL_NAME[25]='SIGXFSZ'
SIGNAL_NAME[26]='SIGVTALRM'
SIGNAL_NAME[27]='SIGPROF'
SIGNAL_NAME[28]='SIGWINCH'
SIGNAL_NAME[29]='SIGIO'
SIGNAL_NAME[30]='SIGPWR'
SIGNAL_NAME[31]='SIGSYS'
signum=$( echo $filename | sed -r -e 's%.+\.[[:digit:]]+\.[[:digit:]]+\.([[:digit:]]+)$%\1%g' )
signame=${SIGNAL_NAME[$signum]}

$filename という変数に元のファイル名が入っているとします。フォーマットは最初に指定した通り。で、最後の数値の部分を取り出して、そいつで SIGNAL_NAME 配列を引っ張ると $signame にSIGNAL名が入ります。

%t はもう少し面倒と言うべきか簡単というべきか…

epoch=$( echo $filename | sed -r -e 's%.+\.[[:digit:]]+\.([[:digit:]]+)\.[[:digit:]]+$%\1%g' ) gendate=$(echo $epoch | gawk '{x = strftime("%F-%H-%M-%S",$0); print x}' )

$epoch 変数に %t の部分を取り出すのは、sed による強引な書き換えで実装しています。で、gawk の strftime() を使って、無理やり年-月-日-時-分-秒に置き換えます。これを $gendate 変数に入れておきます。

ここまできたら、後は簡単。

newname=$(echo $filename | sed -r -e "s%^(.+\.[[:digit:]]+\.)[[:digit:]]+\.[[:digit:]]+\$%\1$gendate.$signame%g")

これでファイル名を作り出し、必要に応じて新しいファイル名の置き場所のディレクトリ部分とかを書き換えたら

ln $filename $newname

これで、$newname で、$filename の中身を参照できるようになりました。ハードリンクにしておけば、ディスクを消費する量も少なく、元のファイル名を壊すこともなく、新しい名前でコアファイルを参照することができます。

そうやって出来上がったファイル名がこんな感じ…

# ls
httpd.worker.811.2013-08-18-02-41-24.SIGSEGV
js.10354.2013-07-27-16-03-37.SIGSEGV
js.10536.2013-07-17-20-28-30.SIGSEGV
js.1081.2013-07-23-20-08-01.SIGSEGV
js.10878.2013-06-25-16-39-17.SIGSEGV
js.11114.2013-06-24-18-30-48.SIGSEGV
js.11476.2013-07-12-19-13-40.SIGSEGV
js.11863.2013-06-01-17-29-44.SIGSEGV
js.11950.2013-08-05-19-22-43.SIGSEGV
js.12204.2013-07-26-17-21-56.SIGSEGV
　　　　　　　　　　　　　：
mauiss.6915.2013-06-06-04-30-52.SIGABRT
mauiss.719.2013-08-05-06-15-14.SIGABRT
mauiss.794.2013-05-11-15-17-30.SIGABRT
mauiss.9527.2013-06-08-10-05-47.SIGABRT
mauiss.9578.2013-05-11-19-39-35.SIGABRT
mauiss.9914.2013-07-05-11-00-33.SIGABRT
mds_10401.20200.2013-06-01-22-28-45.SIGABRT
mongrel_rails.16093.2012-09-17-18-34-17.SIGABRT
mongrel_rails.16528.2013-02-14-21-05-59.SIGABRT

これだけでもいくつかのことが判ります。

mauiss, mds_10401, mongrel_rails の3種類はやたらと SIGABRT で死んでいる。

SIGABRT はそもそもプログラマが assert() 構文で
「こんなことになったら終わりや…コア吐いて死によし」
と組み込んでおいた、まさにその条件にヒットしたので core 吐いて死んだ、と言うことです。これらはまさにソースコードの assert() 文の中身を見ない限り、何が悪いのか判らない、と言う事。これらに関して深堀りはするだけ無駄です。
つーても一応この次の一手分まで実行しておきますが。
http.worker と js というプログラムは SIGSEGVで死んでいるので、多分 bad pointer 系の何かだろう。

ということは、stack の状態を調べて、同じ call tree を辿って、同じ場所でコケてる場合は、同じような理由で死んでいる可能性が高いってことです。
PID邪魔かも…

いつのコアファイルなのかを知る上で、PID順に並んでいるのはとてつもなく邪魔である事がよく判ります。PIDを切り出して、一番最後に回せばよかったよ…

まぁ、とりあえず反省点は見つけたので、めでたく次の一手へと進みます。

どんなコアファイルでも最初に調べるべき内容を吐き出させる

さて次は。

いよいよgdbにコアファイルを分析させるのですが。

当たり前ですが、コアファイルの分析には、そのコアファイルを吐いたプログラムの実行ファイルが必要になります。いまどきのOSですとそのような実行ファイルは動作するのに動的ライブラリを必要としますが、動的ライブラリのバージョンもぴったり一致している必要があります。

コアファイルは、正確には「stackとheap」のメモリイメージをファイルに吐き出したものです。ですので、実行ファイルとかロードした動的ライブラリのイメージは含まれていません(a.out形式ならあり得たかもしれませんが)。こいつらを適切にメモリ上に展開してやらないと、

「0x00238d93fc で SIGSEGVを起こしました」
「そんな所に実行プログラムあらへんわ」

とか

「0x00238d93fc で SIGSEGVを起こしました」
「そこにあるのは～　おぉ malloc() やな(古いライブラリでは free でした）」

とか、間違った解析になりかねません。ですので、コア解析でベストなのは、実行環境そのもので実施する事なのですが…それが無理なら、せめて同じインストールセットの環境を整える必要があります。

判ると思いますが、これが実運用環境をなかなか変更するべきではない本当の理由です。逆にこの手の分析をしないのなら、どんどんバージョンアップをするべきなのですよ!! それなのに日本人が運用すると、意味もなくゴネるばかりでブツブツブツブツ…はっ、閑話休題、閑話休題。

とにかく、実行ファイルとかライブラリが全部あって、それもコアファイルを作った環境と全く同じ環境が作れるとしましょう。

現実問題として core file からこれらの環境を推測するのは多分不可能ではないとは思うのですが、1つ1つやってたらたまったものではないので、今回はパスします。

さて、実行ファイルの名前は、コアファイルの先頭にあります。先の例なら mauiss とか js とか言うやつですよね。こいつを見つけ出します。同じ名前のものは、基本的に同じ場所にあると考えてよいでしょう。

which httpd.worker
which mauiss
which js

とかやればきっと出てくる。出てこない場合は泣きながら探す。もし沢山コアファイルがあるなら、きっとその涙はダイヤモンド。1つしか無かったらすねて諦めて寝るのとどっちが効率が良いか、一考の余地がありますが。

実行ファイルが見つかって、コアファイルもある、となればあとは gdb にお任せ…とはまいりません。「何をするのか」を教えてあげなくちゃいけない。

幸い、gdb には「バッチモード」というのがあります。事前に何をして欲しいかを指定しておけば、OK…なのですが、このgdbのバッチ、2つ問題があります。

分岐もループも書けない
厳密に言うと「私は知らない」だけで、もしかするとあるのかもしれませんが、取得した情報をもとに条件分岐するとか、繰り返しループを書くとか、そういう方法が、無いのか、私が無知すぎるだけなのか…
とにかくきれいな方法が提供されていません。
途中でエラーを起こすとそこから先を実行してくれない。
例えば SIGSEGV で倒れた理由が NULL pointer を実行アドレスとした call 命令の結果だったとしましょう。stack の frame 0 はこの null pointer を実行するためのアドレスになっています。

ここで「frame0の Instruction Pointer が指している辺りを disassemble して」とお願いすると、通常モードなら gdb は
No function contains specific address.
とか何とか言ってエラーになった後、プロンプトを出すのですが、バッチモードの場合は、そのまま gdb を終了してしまうのです。

な・ん・の・た・め・の・バッチモードなのやら。

ですので、gdb のバッチコマンドは、なるべく失敗しそうな命令を別々のバッチファイルにして、それらをシェルなどで駆動する…あるいは gdb に対するフロントエンドを作ってやって、それを使ってコマンドをくべてやる必要があるのです。

(以下、未完)

う

2013年8月18日

神保町小学館ビルに行ってみました。

やっぱりほら、流行りモノは押さえないと ( w )

アルバムビューアーで見る場合はこちら

こんな感じに結構良い天気でした。

小学館ビル前その一。
実は奥側の半分だけしか見えない。

小学館ビル前その二。
微妙な人だかり。かつ皆携帯カメラで撮影しているので、滞在時間はムダに長い(私は Q10 で撮影しているのでもっと長い…)。

建物の中その一。
これはいろいろ補正した後ですが、ガラスへの映り込みは激しいですな。まだ立入禁止状態なので、ガラス越しとはいえ中がそれなりに見えます。

建物の中その二。

ブヒョー
神保町の交差点に戻ってきました。
やはりぶっ飛んで天気が良かった、という話。

2013年7月29日

100Mbps と 1Gbps と 10Gbps と…

序

世の中素晴らしいもので、ついこの間まで Lan で100Mbps 回線を使えれば速い方だったのに、今じゃ1Gbpsは当たり前、お金持ちな方は 10Gbps なんて速度の回線を使ってたりします。

Wanだって負けていませんで、1Mbps がやっとこだったのに100Mbpsなら個人でも、企業なら1Gbps位出ないと…てなもんです。

素晴らしい

素晴らしい…んですが。皆さんなんか忘れちゃいませんかね?? えぇ、通信ってのはbpsだけで決まるもんじゃないんですよ。

ほら、「光速の壁」って奴があるじゃありませんか…。どんなに転送ビットレートが速くなっても、ある1ビットが目的地に到達するのには絶対越えられない最短時間ってのがあるはずですよね？えぇ、だからLatencyとか、TCP/IPだとRound Trip Time(RTT)は改善しないはずで、なのに回線上は沢山ビットが飛び回れるって事は…

送るべきデータも、予め沢山用意しないといけないって事です。

どうも最近、あちこちのお客さんがこの問題に直面しています。今まで気にしなくても良かった事が、通信速度が速くなる事で徐々にそうは行かなくなってきている…。下手をしなくても、古い機械/OSじゃ対応できない事態になってきている…。そういうことが判っていない人がどツボにハマり始めている…。

というわけで、ちょっとその辺の話を書いてみようかと。

以下の説明の一部は間違っている/嘘を含んでいます。例えば通信では octet という単位を使うものであって byte じゃねー、とか。ヘッダサイズ0ってなんだよーとか。

ちゃんとした説明は、真面目な本とか、この辺:

に任せる事にします。この章の説明はあくまでも今回の議題を理屈的に判ればそれで十分、という精度で書いていくことにします。

TCP Window

例えば今読んでいるこの blog とか、Youtube の動画をダウンロードしているとか、インターネット上で情報をやり取りする多くの場合、我々は TCP/IP という通信プロトコルを利用しています。例外はNTPとか実時間動画配信とか…そういう「今すぐ　でないと　情報に価値が無くなる場合」ぐらいなものでしょう。

TCP/IP は IP … Internet Protocol を使ってバイト列を送るプロトコルの一種でして、最も重要なのはバイト「列」を送る、という所です。つまり

A, B, C, D...

のようにバイト列が存在したら、
「Aが見えてからでなくてはBが見えるようにならない」
「Bが見える前にCは見えない」
ようするに A の後に B が来て、その後に C が来る…という順序保証された状態を保証してくれる、と言うことです。

このバイト列の順序保証は送信・受信を実際に行うマシンのメモリ容量よりも大きなバイト列に対しても保証されます。つまり、全部のデータを送って、正しい順番に並べ直して、それから「こんなんでました～」と表示する訳にはいかない、ということ。

一方、IP はパケット通信です。データは塊(パケット)に分割され、パケット単位で送信されます。パケットがネットワーク回線のどこをどう通るのか、本当に受信側に届くのか、誰も何も保証してくれません。

なるべく頑張る　(best effort)

以上の事は誰も言ってくれない。

いや、仮に運良く到達するとしても。パケットは送った順序通りに届くことは保証されない。もちろん LAN…近距離であれば到達するためのコースが１通りしか無いのでほぼ順序通りに到着するでしょうが、長距離になると複数の経路が考えられて、時々の都合で経路が変化し、後から送ったはずのパケットが先に到着する…なんてことも考えられる。

こんな性質の IP を使って TCP の順序保証をどのように実装するか?

順序を保証する部分は「パケットに番号を振れば良い」というのはすぐわかると思います。実際番号は「パケット」ではなく

通信を開始してから頭から何バイト目のデータを送っているのか

を表すシークエンス番号というものを使いますが、そんなのは些細な部分。

失われた…届かないパケットは？

受け取った側はシークエンス番号の何番までは「全部連続して届きましたよ」ということを送信側に教えることができます。その先のパケットは、そもそも送り側が送っていないのか、送ったけど届いていないだけなのか、受け取った側には見分けはつきませんが。だって届いていませんからね。
送信側は、どの部分をいつ送ったのか、いつ届いたと教えてもらったのか、という履歴を元に、本来ならいつぐらいに届くはずなのかを推測します。

「あれ？もう届くはずなのに、届いたって言わないなぁ…もう一度送ってみるか」

本来届いたって教えてもらえるはずの時間が過ぎても届いたといってもらえない場合、同じデータを再度送ります(再送)。再送を使って届かないデータを何度も送ることで、到着する確率を上げます。

でも。

もし、送信側が 1024kbyte のデータを持っていて、受信側のメモリが 1kbyte しか無かったら? 送信側が勝手気ままに 1024kbyte 分を送っても 1023kbyte 分はほぼ確実に再送対象になっちゃいますよね? だって受信側は 1kbyte しかメモリがないので、シークエンス番号を見て、最初の 1kbyte の外にあるデータは捨ててしまいます。

TCPの順序保証機能を実装するためには、最初の 1kbyte 以外の部分を受け取るゆとりはないからです。

最初の1kbyteの部分を順番通りのバイト列に戻して、アプリケーションとかにそのバイト列を渡してから、次の1kbyteのことが考えられるようになる。
そこに 1024kbyte 分のパケットを送りつけられても、最初の 1kbyte 分以外は全部棄てるしかありませんよね?

そこで、TCPには TCP Window という考えがあります。ようするに送信側、受信側で
「オラーこんだけ一気に送れるだよ？」
「オラーこんだけしか受け取れねーだよ？」
というサイズを教えあうのです。で、小さい方を TCP Window とする。

送信側は、受信側が「受け取ったー」と言ってきたシークエンス番号(通信を開始して以来、先頭から何バイト目かを表す番号)にこの TCP Window の大きさを足した分までの範囲だけを送ることにする。
受信側が送ってきたシークエンス番号よりも前の部分はもう受信側も受け取ったので送り直す必要はない。
シークエンス番号にTCP Windowの大きさを足した分を超えた先の部分のデータは、受信側は受け取れない可能性があるので、あえて送らない。

こうして送らなくてはいけない全データ、ではなくデータのごく一部に集中することで、少ないリソースで再送機能を実装して、確実に順序保証ができる形でデータをやり取りするわけです。

このTCP Window の「大きさ」のことを TCP Window size と言います。

Round Trip Time

パケットをA地点からB地点まで運ぶのにどれぐらいかかるでしょう…??
え？そんなの簡単？？予め2つ時計を用意しておいて、一定時刻にAからパケットを送ってBで受け取った時刻を記録すればいい??

いえ、それは簡単ではありません。A,B両地点の時計を完璧に同期させるのは不可能です。光の速度で数msecかかるということは時計だって同期させると数msecの誤差が出るということ。

ましてやパケットはどのような経路を通って伝わるのか分かりませんし、本当の本当にA<->B地点間の通信ケーブルの長さが何メートルなのかも判りません…。

だから別の手を使います。

A地点からB地点へとパケットを飛ばします。B地点ではそれを受けたら「受け取ったー」というACKを返すようにします。で、パケットを送ってからACKがかえってくるまでにかかる時間を計測するのです。これなら時計は一種類ですし距離は2倍に伸びますから、計測しやすく誤差も出にくい。
この「行って・来い」一周(Round Trip)にかかる時間のことを Round Trip Time(RTT)と言います。

TCPの場合、受信側はパケットを受信し、なおかつそれが今まで受信してきた部分の続きの場合、「ここまで受信したよ」というシーケンス番号を返してくれます。これを ACK と言います。traceroute などはこのデータパケットを送ってから ACK パケットが返ってくるまでの時間を計測して RTT を算出します。

類似の方法に ICMP echo と ICMP echo reply パケットを使う方法もあります。これは ping が使う方法ですね。

ここでは TCP/ACK の方で RTT を測る、としましょう。

TCP Window size が同じサイズで通信速度が違うと何が起こる?

この章では TCP Window size が同じサイズだと仮定しましょう。　RFC793(RFC793和訳) の時代に戻って 65,535　byte と仮定します。

先出の通り、TCP Window size は「受信側が受け取ったとしたシーケンス番号以降、TCP Window size までのデータを送信して良い」サイズです。

65,535byte は 1byte = 8bit なので　524,280bit です。本当はこれはペイロードなので TCP header とか IP header とか色々くっつくのですが、面倒なのでそれらのサイズは全部 0 だとして、代わりに諸々計算する時にどんどん「切り上げ」することにしましょう。

100Mbps

100Mbps の世界では 524280bit を送信するのに 5.2428msec かかります。つまり、5.2428msec …大雑把に 6msec ですか…以内に ACK が帰ってこないと、送信側はこれ以降のデータを送れなくなります。

6msecの RTT というのは…大雑把に言うと東京・大阪間を直結した場合がそれぐらいです。
Google 先生によると光の速さは 299,792,458m/sec で、東京・大阪間の距離がだいたい 515km だそうですので、片道

515*1000/299,792,458(sec) = 1.7178(msec)

往復で3.5mseecぐらい。電気信号でLANの中を走り回ったり、信号を変換したり、1packet のデータ分をビットに変換したりしてると、だいたい 6msec のRTTは妥当だ、と言うことになります。

東京・名古屋だと 5msec ぐらい。東京・仙台間や、大阪広島間も同じぐらいの距離なので直結線であれば時間も同じぐらいです。

なので、100Mbpsの回線を東京・大阪間でフルパワーで使えると仮定するなら、古い TCP の実装でも Window Size を最大にすれば、全力で通信できる、ということができます。

しかし仙台・大阪間のように、明らかに6msec以上かかる距離になると、通信は間欠泉のように「データを送れないタイミング」ができてしまう。

例えば仙台・大阪間が10msecかかるとします。最初の6msecかけてTCP Windowに格納されていたデータが全部送られるわけですが、最初のパケットに対する ACK はまだ返って来ません。結果、6msec経ったポイントからしばらく沈黙が発生します…最初のパケットに対するACKが返ってくる4msec後までは。

4msecしてACKが返ってくると、受信が確認された分だけ TCP Window に空きができますから、その分だけ新しいデータを相手に送れるようになります。その間にもACKが次々と返って来ますので、TCP Window に空きができ、その分データが送れるようになります。
データが送れるようになればその分また新しいパケットを送るようになるわけで…その状態が6msec続きます。で、またACK待ちになり…

つまり　6msec データを送っては 4msec 沈黙、6msec データを送っては 4msec 沈黙、を繰り返すようになるのです。

ただし、このような状態は WAN …中でも日本を半分近く縦断するような WAN 通信でない限り起こりません。LANと呼べるレベルならほとんど心配は無いはずです。逆に言うと海外との通信に於いてはほぼ確実にこれは起こってしまいます。

1Gbps

1Gbps の世界では 524280bit を送信するのに 0.52428msec かかります。つまり、大雑把に 0.6msec ですか…以内に ACK が帰ってこないと、送信側はこれ以降のデータを送れなくなります。

RTTが0.6msecかかるには、ちょっと大きめの工場の端から端までぐらいの規模の LAN が必要でしょう。同じビル程度であれば 0.15msec とか 0.2msec 程度になります。

つまり、1Gbpsの世界で WAN を貼ろうとすると、　RFC793(RFC793和訳) の世界だと 100Mbps で海外と通信しようとした時に生じる問題が、となり町との通信でも発生する、と言うことです。

もちろん、東京・大阪間などひどい状態に…なにしろ　RTT 自体は変わらないのです。6msec中最初の0.6msec でデータを送り終わり、5.4msec 沈黙を守った後、また0.6msecデータを送り…を繰り返すことになります。
つまり実質 100Mbps でしか通信できない…。原因はもちろん、TCP Windowサイズの小ささと RTT の大きさが通信幅にマッチしていないことにあります。

10Gbps

10Gbps の世界では 524280bit を送信するのに 0.052428msec かかります。つまり、大雑把に 0.06msec ですか…以内に ACK が帰ってこないと、送信側はこれ以降のデータを送れなくなります。

これは正直、スイッチを一台挟んで隣のラック上のマシンと通信してもクリアするのは難しい。Fibre で直結すれば 7kmぐらいまではどうにかなるでしょうが…

このレベルになると、ケーブル上をデータが流れていくのにかかる時間よりも、スイッチやルーターで信号処理をしたり、リダイレクションを掛けたりするのにかかる時間の方が長くなります。

新しい問題は何もありません
全ては新しい問題です

これでお分かりいただけたでしょう。

10Gbpsの世界では隣同士のマシンで起こる事象は、100Mbpsの時代には長距離通信において起こっていた現象でしかありません。別に新しい問題ではないのです。新しい問題ではないのですが…

同時にほとんどの人が意識したこともなく、意識することもなかった問題が噴出する、ということでもあります。ほとんどの人が気にして来なかった、太古から存在する問題が襲ってくる。

解決策は簡単です。TCP Window size を大きくしてやればいいのです。RTTが大きいといっても人間が感知できるほどの大きさではありません。通信格闘ゲームでもやってれば別ですが。なので TCP Window size の default 値を大きくすれば…いい…ん…で…す…が……

実はこれが容易なこっちゃありません。

あぁ、もちろん、64bit 環境においてはアホのように簡単な問題です。問題はこれが「2000年1桁台」初期の頃のマシンや、その頃以前のソフトウェア…特にOSと混ざった場合…32bit CPU とかその程度の環境で発症します。

話を応用性が効くようにするために 10Gbps で東京・大阪間を通信する場合を考えましょう。

RTTは相変わらず 6msec です。常時通信し続けるのに必要な TCP Window size は 60Mbit …大雑把に 8Mbyte 弱です。最近の TCP には Scaling Factor という機能があって、16bit の変数を 2ⁿ倍しろ、とすることができます。この n　を 0 から 14 まで指定することができるので Window size は (1024-16)Mbyte = 1008Mbyte まで指定することができます。

しかし。プログラムからすればこれから開始する TCP session が「どれぐらい遠く」としゃべるためのものなのか、知るすべはありません。というかプログラムを動かしている「持ち主」だって知らない。インターネットの通信は、サーバがどこにあるのかが「シームレス」だというのも特徴の一つですから。

と言うことは、仮に最長が東京・大阪間で、それ以外はLANの中に収まるとしても、TCP Window size は「全ての session に対して」8Mbyte 用意しなくちゃいけない、と言う事。例えば私が今これを書いている Windows7 マシンは、netstat で ESTABLISHED 状態のセッションを数えただけで18個あります。全部に 8Mbyte を与えると 144Mbyte * 送受信それぞれ = 288Mbyte 、kernel の作業領域から持っていかれることになります。

私が仕事で面倒を見ているマシンになると、常時なんだかんだで 800session ぐらい貼り続けていますから、12800Mbyte = 12.5Gbyte 必要なわけで…

32bit の Linux Kernel の場合、Kernel 自身が動作できるメモリの大きさは 892Mbyte ぐらいです。この内　288Mbyte を通信で消費されただけでも動作への影響は著しくでかい。12.5Gbyte 頂戴なんて言われたら絶対無理。

ましてやこれは東京・大阪間の 6msec の RTT の場合です。世界中を股にかけるとなると 300msec ぐらいは RTT があり得る。このさらに 50倍…600Gbyte…

昔の 1Gbyte ぐらいまでしかメモリが搭載できないマシンに、Windows2003 とか RHEL5 とか載っけて、無理やり動かしているマシンなんて疾うの昔にまともに動けるような状態じゃない、と言うことです。
64bit CPU に 64bit CPU 用OSを用意して、クライアントマシンでも　16Gbyte …サーバなら 1Tbyte ぐらいは搭載しないと、まともな通信なんかできなくなりつつあるってことです。

もちろん、世界中を股にかけた通信なんて、まだ 10Gbps 出ません。100Mbps だって出るかどうか。でも 1/100 にしても 6Gbyte は当たり前の世界なんですよ。

判りますか? HWだけ新しくして、ふっるい distribution …例えば RHEL 5 とか…を使って
「TCO下げてます」
なんて大間違いなんですよ。全然 TCO 下がってないんです。単純に不便になってるだけ。しかも通信していない理由なんか統計情報からは全然判りませんから、問題があるようには見えないかもしれませんが、それは問題を発見するための物差しが間違っているだけなんです。

また、新しく回線を敷設する場合は、通信速度だけではなく、RTT も確認するべきです。もし、本来直結線で 6msec の RTT の回線が 12msec かかるようなサービスがあったら…そりゃ値段を叩いて安くさせるべきです。だってその分メモリを浪費して、サーバの動作効率が落ちるんですから。IO cache とかどれぐらいヒット率が下がってどれぐらい無駄に計算時間が浪費されると思ってるんですか…

RTTは短い場合はルーティング候補がほとんどありませんのでいいのですが、RTTが不必要に長い場合、複数のルーティングの中から適宜選んでいる…という場合があり得ます。この場合、性能を出し続けるためには 一番長いRTT にパラメータを合わせなくちゃいけません。たとえば、60%が 13msec、20% が 20msec、10% が 25msec、5%が 30msec、残り 5% が 40msec 以上…と言われたなら、例えば
「合計95%までの確率で通信速度が全力であることを保持したい」
ならばRTTの短い方95%の中で最も長い RTT … 30msec で値を決めなくちゃいけません。

え？ TCP Window size を RTT に合わせて長くしなおせばいいんじゃないかって?? 今の所、RWINなどは、最初に Window Size を大きく negociation しておいて、実際には少ししか使わない、と言う方法で Window size の調整をしています。
そうではなく TCP Window sizeを最初は小さく、後で option か何かで大きく同意し直す、という方法は、RFCを書く所から始めなくてはいけないレベルの話です。仮に今日、RFCを書いたとしても実装が普及してあなたが使えるようになるのは 10年後ぐらいの話ですよ…。

結論

ようするにこういうことです。

TCP Window size こそが真の通信速度の律速条件となる世界がやってきた。
昔WANで気にしなくちゃいけないことは、今やLANでも気にしなくちゃいけない。
古いOSや、32bit HW だともう速い速度にはついていけない。いい加減諦めて買い換えろ。特に Windows を 2003 とか XP とか使ってる奴ら、大概にしろっ!!

2012年6月17日

MECEと「7±2」と「その他禁止!」の話

世の中、分析を行う上で使う価値のある「考え方のツール」というのはいくつもあります。MECEもそのひとつ。網羅性を尽くしたい時によく使われますね。あまりにも広まっているので、珍しくもなんともないのですが…

珍しくない割には、ちゃんと使いこなしている人が余りいません。
いや、言い過ぎですね。今の会社で、私の周りには、あまりいません。

で、何故なのかなぁ、と調べていくと…うむ。これは酷い。お前ら何考えてるんだ、という事が浮かび上がりました。それが「7±2」と「その他禁止!」のルールを知らない、と言う事。

いや、「7±2」は聞いたことがある、と言う人も多いんですよ? 多いんですが…覚えているだけという感じ。意味無いじゃん。

というわけで、今回は私が知っている「MECEを使う上での注意事項」を2つ紹介しようと思います。

まずは MECE についてのおさらいから。

MECEは「Mutually Exclusive and Collectively Exhaustive」の略です。見ての通り実際には2つの条件「Mutually Exclusive」と「Collectively Exhaustive」を両方満たせ、と言っています。

Mutually Exclusive というのは「相互に排他的な項目」…もっと簡単に「ダブリ無し」とか「無駄なし」と言い換えられています。

「Aが成り立つ場合と、Bが成り立つ場合と、Cが成り立つ場合と…」

と列挙していった時に、それぞれが互いに重なり合っていると場合分けが大変になるので、なるべく

「Aが成り立つなら、BやCは成り立たない」

ように条件を決めてやろう、というわけです。

Collectively Exhaustive は「完全な全体集合」ということです。「漏れなし」と言い換えられています。
後から「考慮対象外」が出てきて困ったことになってしまうことがないように、最初から「これで全部」であることを考慮する。特に分類項目なんかを考える時に重要なルールです。

MECEはどういうときに使うかというと…まぁ、「条件分け」と「各条件に当てはまる事象として何が言えるか/既知の情報として何があるか」を分類して、考慮漏れ・配慮漏れを見つけたり、まだ誰も攻略していないブルーオーシャンを見つけたりするのに使います。

例えば客に何かレポートを送らなくちゃいけない場合、「言わなくちゃいけないことは何か？」を考える時に、最初に MECE で条件分けをして、それぞれの箱のなかに何が入るかを並べていき、穴がないことを確認する、なんていう風に使う事が多いです、最近は。

「それで全部考え尽くしたよね?」
と議論とか考察の最後に確認しなくちゃいけない場合は、最初から MECE を考慮しておくと非常に便利です。

MECE …ちゃんと使いこなすと便利だというのは、誰でも直感的に判ると思うんですが…実はこいつには制約事項があります。

その一つ目が「7±2」。

もっと簡単に言いましょう。

書け!!

えぇ、この単純な条件をロクに実施しない奴がほとんどなんですよ。

MECEは「ME」の条件が「分類数を減らす」事に寄与し、「CE」の条件が「網羅性」に寄与します。別の言い方をすると、MECEを使った場合の真の価値は「CE」の方にある。CE の条件を満たす時に ME の条件を満たしていないと無限地獄に陥るから、MEの条件が付与されているのに過ぎません。

一方で。「7±2」の条件は「人間が一度に把握できる概念数の上限」を示しています。チャンク、と呼ばれていますが、ようするに「一塊にできる」概念を持ってきた時に、人間は 5～9個しか「塊」を覚えていられないのです。

更に言うなら。

MEの条件だけなら、9個に近い所まで人間は覚えられます。これは、「互いに排他である」事を理解するには、一度に2つの「塊」だけを比較すれば良いため、記憶にあまり大きな負荷がかからないから。

しかし、CEの条件の場合、人間が覚えられる塊は5個に近い処にまで落ちていきます。「全体網羅性」は「全部の塊を一気に把握しないと判らない」ため、CEの確認は記憶に非常に大きな負荷がかかる作業になります。

このため、全てを記憶だけに頼っていると(すでに何度も使っていて慣れている分類パターンならばともかく、新規の分類パターンの場合)、MEの条件は満たしているがCEの条件を満たしていない分類法を使ってしまったり、全条件パターンについて網羅的に調べきれずに失念してしまう物が出てきたりと、ミスが続発します。

えぇ、

MECEは書いてなんぼ

なんでございますよ、奥様。

MECEは記憶力だけで
使うもんじゃない

んでございますよ、お嬢様。

なのに、ノートに書かない、そこらへんの紙にすらろくに書かない、ホワイトボードも何も使わない奴らがゴロゴロゴロゴロ…挙句に、穴だらけの考察を持ってきて
「これでどうですかねぇ」
とか、寝言は寝て言えと。

そもそもお前ら、俺がノートを6冊以上消費しているのに、まだ半分使ってないとか、なにやっとんのかと(ただし、私はノートの紙の片面しか基本的に使わないようにしているので、私が6冊使う間に3冊しか使ってなくてもそれはOK。2冊しか使ってない、とか言うのはありえなくはない状態)。
そんなに「何も書いてない」状態自体、MECEを使いこなせていない証拠だろうが。

えぇ、実際。私はほとんどの考察をノートに書いていまして。というか書かないとダメで。覚えていられませんで。というか私の記憶力は 5±2ぐらいしかないんじゃないかという嫌な予感が、特に英語を叩きこまれた辺りからずーっとしているんですが(多分、無茶な環境変化を食らったせいで記憶制御ユニットが一部壊れたんじゃないかと…)。

…
閑話休題。

とにかく。MECEを使いこなしたければ「書け」。これがポイント。そして殆どの人が「実行に移していない」ポイントの1つ目でもあり、その度に穴だらけの考察が出来上がる理由でもあります。

具体的に「どう」書くか、は人それぞれです。
私は表を作って埋めていくタイプが好きです。人によってはマインドマップで書くのが好きだという人もいます(これでMEの条件を満たしていると判る理由が私にはわからない)。何がどこにあるんだかよく判らない具合に列挙するだけ、と言う人も居ます(これでもちゃんとMECEの条件を満たす辺りがすごい)。
まぁ、やり方はいろいろです。そこをとやかくいうつもりは全くありません。重要なのは「覚えきれないに決まってるんだから、記憶力に頼るな」と言う事。

さて、MECE を使いこなす上での2つ目の制約条件。それが「その他禁止!」です。

例えば…人間を次のように分類する場合を考えてみましょう。

女性
オカマ
その他

女性とオカマは排他です。オカマの性別は(一応)男性ですから。オカマは男性全体ではありませんが、男性の部分集合です。また、「その他」は「女性でもオカマでもない」ものを表すので、この3つは Mutually Exclusive なのは間違いありません。

「その他」は「それまで列挙してきた条件を満たさないもの全て」という意味なので、Collectively Exhaustive でもあります。女性でもオカマでもない人間は全て「その他」に分類できます。どこにも属さない人間は発生しません。

つまり「女性」「オカマ」「その他」と言う分類は、確かに MECE を満たしているのです。しかし…この分類、役に立つでしょうか??

実は殆どの場合、役に立ちません。それは分類の精度がバラバラだから…ではなく、「CE」の条件を満たしているのが『その他』という単語に起因しているからです。実はこの分類、「その他」に何が当てはまるのか、理解できている保証がありません。そのような保証がなくてもMECEの条件を満たしてしまう、それが『その他』という単語の恐ろしいところなのです。

実際、この条件から「その他」にはどのような人が割り当てられるか、想像できるでしょうか? ノーマルな男性? あぁ、それは確かに「一部」そうでしょうね。その他には? 「フタナリ」…んー、女性とオカマの定義によっては若干ブレますが、それもアリでしょう。他には?…

そう。これ、いつまででも「他には？」って聞いていられるんです。そういう曖昧模糊としたラベリングでは、「そこに対応するものを思いつけ」と言われてもいつまでも終わらない。逆に「これはどこに分類されるんだ?」となった時に「その他」がどれぐらいの大きさになるのかも予測がつかない。もし、大半が「その他」に入ってしまったら、多分その分類は意味を成さないでしょう。

ところが、この「その他」もこれがまた、失敗した考察にはよく出てくる。そして「その他」が実は重要な要素を持っているはずなのに、完全に失念されていたりする。

なので「その他禁止!」となるわけです。意味もわかってないものを使うな、と。でないと、何のために MECE を使って考えているのか、わからなくなりますからね。

というわけで、MECEを使う上での条件「7±2」と「その他禁止!」というお話でした。

どっと払い(なんでや)

2012年4月9日

I just couldn't stand it....

いやー、アメリカに出張になった時からず――っと我慢してたんだけど。Easterで大半のお店が閉まってる中、ToysRusで見つけちゃったら…我慢できなかった。

まぁ、なんか後ろから全力で背中を突き飛ばしてくれた人もいたみたいだけれど…$200だったので買ってしまいましたよ、あぁ…

とりあえず、日本語の Web Page も読めたし、なかなか面白い。
同時に、「お急ぎ配送サービス」とかが1ヶ月無料…とかのサービスも付いてきていて、あぁ、こりゃアメリカ合衆国だけにするわけだわさ、と納得。つーか、本の虫な人とか、Amazonのヘビーユーザーなら、これは安い買い物だろう。

2012年2月10日

Sudo format string vulnerability

前置き

Sudo format string vulnerability ( CVE-2012-0809 ) というバグが、sudo コマンドには存在する。CVEが出ていることからも判るように、結構深刻なバグで、セキュリティ・ホールとしての性質を伴う。sudoのページによれば

運が良くても sudo はクラッシュし、

運が悪いと攻撃者に root 権限を掌握される問題が含まれているかもしれない

との事だ。

で、このバグ、何がどうなっているのかについては、『てきとうなメモ: [Linux][Security] sudo-1.8のバグ』が詳しい。とても詳しいので、そちらだけ見ておけばいいやと思っていたのだが、何箇所かから、

お前も書け

という圧力を食らったので、書くことにする。ただし、新しい情報がなにかあるって言うわけじゃない。

影響範囲

このバグは sudo の 1.8.0 で導入され 1.8.3-p2 で修正されました。なので、影響は 1.8.0 - 1.8.3-p1 と言うことになります。

で、商用 Linux distribution の中で、影響があるのはなさそうです。
Free distribution の中も含めると、Fedora16, OpenSuSE 12.1, Rawhide の3つが影響を受けているようです。
(http://rpm.pbone.net/index.php3 でどのdistributionがどのrpmを使っているのか、分かります)

ただし、それ以外のOSでも sudo は使っているはずです。それらが安全かどうかは判りません。一応、sudo のページには対応している各種OS用の置き換えバイナリは用意されているようです。

という訳で、ほぼ影響はない、と言うことなので、以下は笑い話として。他人の失敗は蜜の味 (^w^)。

攻撃方法

攻撃方法は次のとおりです。

ln -s /sbin/sudo /tmp/%s
のようにして、sudu コマンドを「%s」というファイル名にすり替える
/tmp/%s を実行する

%s は printf() 系処理が format 文として利用しているものであれば、大抵のもので問題が生じるようです。どれでどのような症状が出るのかは、CPUなどにある程度依存します。

こうすると、argv[0] 文字列の中に %s という文字列が含まれるようになります。

技術的概略

このバグは、すごく簡単に言うと printf() 系関数を2段階かけた事に起因したバグです。printf() 系関数を多段に使うことは、セキュリティを考慮したコーディングとしては非常にまずいもので、

絶対やるな

と言っても構わないぐらい、危険な行為です。

修正後も2度使っていますが、まぁ、これならしょうがないかな、という所にまで治っています。

実はもう一つ、例外処理が足りていない、と言う問題もあります。sudoだから発生する確率はあまり高くありませんが…仮想メモリシステムを使い切った状態だと危険ですね。

詳細

sudo-1.8.3-p1 の ./src/sudo.c の最後に次のような関数があります。デバッグログを出力するためのコードですが、ここに悪さの元が含まれています:

void
sudo_debug(int level, const char *fmt, ...)
{
    va_list ap;
    char *fmt2;

    if (level > debug_level)
 return;

    /* Backet fmt with program name and a newline to make it a single write */
    easprintf(&fmt2, "%s: %s\n", getprogname(), fmt);
    va_start(ap, fmt);
    vfprintf(stderr, fmt2, ap);
    va_end(ap);
    efree(fmt2);
}

通常、argv[0] は "sudo" という文字列へのポインタです。で、getprogname() は argv[0]を返すようになっています。
そこで、
fmt = "%s"
　　fmtの次の引数 = "hello"
のような場合について考えてみましょう。

    easprintf(&fmt2, "%s: %s\n", getprogname(), fmt);

この行を通った段階で fmt2 は

    fmt2 = "sudo: %s\n";

になります。で、その後：


    vfprintf(stderr, fmt2, ap);

という行を通ると、stderr には


    "sudo: hello\n";

という文字列が送りつけられることになります。
何も問題はありませんよね??

では、攻撃方法にあるように sudo コマンドに対してリンクを貼って './%s' という名前で起動したらどうなるでしょう?

argv[0] = "./%s"

になります。


    easprintf(&fmt2, "%s: %s\n", getprogname(), fmt);

この行を通った段階で fmt2 は

    fmt2 = "./%s: %s\n";

になります。で、その後：


    vfprintf(stderr, fmt2, ap);

という行を通ると、stderr にはまず、第1引数である "hello" が出るので:


    "./hello:

…おや、困りました。後半の %s のための文字列へのポインタが引数として渡されていません。しかも vfprintf() はそんな事を知りません。しょうがないので、stack 上にある値をポインタと解釈してしまいます。

運がよいと、「Segmentation Violation」が発生します。で sudo はクラッシュします。あぁ、core を吐かないように設定しているといいんですが…。運が悪いと、coreファイルを持っていかれますが、そこには /etc/shadow の値が書いてあるかもしれません。

まぁ、意図的にやっている奴らは

確実に core 取得できるように

設定してから実行するよね。

はっはっはっ

まぁ、運良く大した情報が保存されていない core ファイルが出来上がることを祈るしかありませんな。

ちなみに。"%s" は上記のとおりですが、"%n" という楽しい引数がございましてな…これ、引数で渡したアドレスにそこまで書いた文字数を「書きこむ」んですわ… はっはっは　…

判ったと思いますが、万が一これらのバージョンを使っていたら

血の涙を流してでも upgrade しろ!!

対策

1.8.3-p2 はこう変更されました。

void
sudo_debug(int level, const char *fmt, ...)
{
    va_list ap;
    char *buf;

    if (level > debug_level)
 return;

    /* Bracket fmt with program name and a newline to make it a single write */
    va_start(ap, fmt);
    evasprintf(&buf, fmt, ap);
    va_end(ap);
    fprintf(stderr, "%s: %s\n", getprogname(), buf);
    efree(buf);
}

えぇ、見ての通り printf は相変わらず2度使われています。

ただ、1度目は与えられたフォーマットと引数から、とりあえず buf という文字列を作るために、2度目はargv[0] と buf を fprintf() で出力するために使われます。

fmt は sudo のプログラム内で指定するフォーマット文ですし、fprintf() で使われるフォーマット文もプログラム内で指定するフォーマット文ですので、取り敢えず引数に %s などの危険な記号が含まれていても安全、とは言えるでしょう。

ただね。このコード、 buf == NULL だった場合を考慮していないんですわ。一応、glibc の場合 NULL を渡されると "(null)" という文字列を出しますけどね、これは必須ではない。たとえばSolarisは core dump するそうです。

環境によっては fprintf() の例外処理の定義が甘い所につけ込んだコードになる危険性は残されています。

2011年12月29日

sched_clock() overflow after 208.5 days in Linux Kernel

えーっと、久しぶりに Linux Kernel にダメダメなバグが発見されて、よりにもよってうちの製品も影響を受けたので、ここに詳細を書くことにした。

つーか。新しい Kernel を使うなら皆で使おうよ。なんだよその「1つだけ」影響を受けて残りは「影響も受けないぐらい古い」ってのは…

概要
大雑把に 208.5日連続運転した Linux Kernel が突如として reboot する。

実機でなおかつ Time Stamp Counter を内包している必要があるので、Pentium4以降のプロセッサ(が、それはようするに今ある Intel 系CPU全部)か、その互換CPUである必要がある。32bit モード、64bit モードの区別はない。
逆に VMware や Xen など、仮想マシン上で動いている kernel に影響はない。これはそもそもバグを内包したルーチンを、仮想マシンで動いていると検出した Linux Kernel は使わなくなるからだ。

一切の予防的挙動は取られていないので、file systemなども含めて、non-volatile メディアに対する影響は甚大かつ破壊的。回避策はパッチの当たった Kernel をインストールしてrebootするか、200日以内に計画的に reboot する事のみ。

影響範囲
Linux Kernel 2.6.28 で導入されたパッチにバグがあり、3.1.5 で修正された。この間にリリースされた distribution は多分全部影響を受ける。

なお、具体的には
2.6系列:  2.6.32.50でfix
3.0系列:   3.0.13でfix
3.1系列:   3.1.5でfix
らしい。

商用 distribution で影響を受けているもの。

まずは SuSE11 SP1。fix パッチはこうなっている:
http://kernel.opensuse.org/cgit/kernel-source/commit/?id=413af9e6f17a1a1519cae0bfd1c1fe4409bb42a3

RHEL6も 2.6.32 base らいいのでこれも影響を受ける。
(2012/02/14追記: RHEL6 は kernel-2.6.32-220.4.2.el6 で修正が入ったらしい。http://rhn.redhat.com/errata/RHBA-2012-0124.html
ただし、ひどい事に「2012年１月２４日に登録され、fix ができたのは2012-02-13という事になっている。３ヶ月近く何をしていたのか…)

~~多分Fedoraとかも影響をうけるはずだが、マシンを上げていないので判らない(何その手抜き)。~~
Fedora マシンを上げたら
「3.1.1→3.16 に kernel を更新」
という update が出ていた。 Fedora16使いは速攻で上げることをお勧めする。
また、Fedora15使いは速攻で Fedora16 にして、update を最新に持っていくことをおすすめする。

3.1.5のバグ修正後のコードはこう:
http://lxr.linux.no/linux+v3.1.5/arch/x86/include/asm/timer.h#L58
(LXRとか、こうやってソースコード丸ごと指定できるからありがたい)

なお、VMware とかの仮想環境では、このバグっているルーチンはそもそも利用されない。なのでこれは実機上で動かしている Linux Kernel でのみ、発生する。なので、VMで実験を…とかは一切効かない。

技術的詳細
最近の Intel processor やその互換CPUには Time Stamp Counter (TSC) という 64bit レジスタがある。

こいつは Intel の場合だと CPU 駆動クロックでカウントアップしていて、1tick ごとに+1していく。例えば 2GHz のCPUの場合、1秒で2Gづつ増えていくのだ。

また、AMDの場合だとCPUに投入されるクロックで 1tickごとに+1していく。大抵の場合は 800MHz なので1秒で800Mづつ増える。

判ると思うが、ほぼ nano 秒オーダーの時計として使えるので、リアルタイム制御をしたい場合、TSCはとてもありがたい。しかし、最近の電力消費量制御機構は、CPU駆動クロック周波数を変更してしまう。すると TSC の値は何がなんだか判らなくなる…
そこで、Linux Kernel 内部には cycles_2_ns() という関数があって、TSCの値をナノ秒に修正してくれる事になっている。

しかし、不幸はここに内包されていた

すごく簡単に言うと、TSCの値を必要な Scale Factor 倍すれば　nano sec になる。しかし、TSCの値は nano sec に近い。当然 Scale Factor は 1.0 に近い、微妙な浮動小数点になってしまう。

そうだ! Scale Factor を分数で表そう!!

SC/1024 で表現して、

SCを整数にしておけば、

SCを掛け算した後、

右に10bit シフトすれば済むよっ!!!

…この段階で何か嫌な予感がしなかったんだろうか、こいつらは…

とにかく、元の式は、TSCの値を 64bit 変数に代入し、それに 32bit のSC ( コード上は per_cpu() という関数の戻り値) を掛けて、10bit 右にシフトする、というものになった。

さて。ちょっとここで視点を変えてほしい。
「TSCに SC を掛けて、その後 1024 で割ると nano sec になる」
って事は、

TSCにSCを掛けると

大雑把に pico sec の精度の数字ができる

って事だ。

2¹⁰ = 1024 ≒ 1000 = 10³

なので、メートル法の縮尺単位が1つ変化する度に10bit消費される。
(ここは試験に出ます)

すると、pico sec レベルでの数字を扱うと、1秒を扱うには 40bit 必要、ということだ。しかるに、この値は 64bit の変数に代入されいてる。って事は「1秒以上」の表現には 24bit しか有効桁数がないって事だ。

2²⁴ / ( 24 * 60 * 60 ) = 194.180741日

実際には、1024の方が若干大きいので、その端数が載る。具体的には 64bit変数を最後に 10bit 右にシフトするので、有効桁数は 54bitになる。これが nano sec で表された時刻なのだから、

2⁵⁴ / ( 24 * 60 * 60 * 1000 * 1000 * 1000 )

= 208.499983日

めでたく、今回 overflow を起こした日数そのものが出てくる。64bitは、無限にでかいに等しい桁数ではないのだ。

かくして、cycles_2_ns() は、208.5日経つと、桁あふれを起こして 0 に近い値を出力する。sched_clock() はこの値を利用しているため、ここもぶち飛ぶ。

スケジューラーはここの値に強く依存しているので、突如として 54bit の数字が 0 になると、カーネルのあちこちがぶっ飛んでしまい、reboot に至る。

感想

497日問題の反省

全く活かされておらずっっ!!!

------

あれから2年…どうやら新しい 208.5日問題が発見されたらしい…

http://hisayosh.github.io/posts/2013/12/208days-problem/

「新208.5日問題 - Systems with Intel® Xeon® Processor E5 hung after upgrade of Red Hat Enterprise Linux 6」

今回は私なんぞよりよほどわかりやすく説明してくれる人が現れた。お陰でリンクを貼るだけで済む。ありがたや、ありがたや… (-人-)

今度のは CPU のバグとペアになっていて、reboot すると freeze する、という実に悪質な…実運用に入っているサーバのメンテナンスとかで再起動しようとしたら freeze した…なんて事、その場に立ち会ったら心臓がショックで止まりかねないだろう…。

2011年12月11日

lunar eclipse

On year 2011, Dec. 10th around 21:30 - 00:00, we had Lunar Eclipse here at Japan.

Here's some of the photos I took.

Camera: RICOH CX1
Mode: ... ah .. I kept on changing it in the dark. So I'm not sure.

And .. Battery run out ..... gosh ...

2011年11月24日

ホームゲート

都営大江戸線の青山一丁目駅。

ホームゲートが設置されているのに、まだ稼動していない。

ゲートは全開でその先にレールが見えている。

実運用が始まるとこんな光景はもう見られない。珍しいので撮影。

2011年9月23日

< 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 全体がクラッシュする、という状態に陥るのです。

2011年9月16日

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 ...

2011年6月11日

リサイクルループに着目しよう

節電が叫ばれている。一般家庭も企業も15%ぐらいは節電して欲しいそうだ。

で、老人が「ペカペカ光るもの」は「電気を食うに違いない」とボケを垂れ流している。が、正直、それではたいして節電にならない。本当に電気を食うものってそんな所にはないからだ。

というか、「ペカペカと光る」とか「キンキンに冷える」とか、そういう擬音付きキーワードな代物は、別に昨日今日目の敵にされたわけじゃない。なのでアチラコチラに工夫がしてあって、実はかなり電力を食わないようになっているのだ。だからそんな所を今更攻めたって、たいして節電になどならぬ。

じゃぁ、どこにエネルギーは消費されているか?

エコロジーだともてはやされたもの。CO2削減にはこれ、ともてはやされたものにこそエネルギー消費は隠れている。

というわけでリサイクルを槍玉にあげてみよう。

リサイクルって言うのは「モノ」の形状を変えて、同じ物体をなんども変形させながら使い回しする、っていうのが基本発想だ。ペットボトルを粉砕して溶かしてもう一度ペットボトルにするとか。紙をパルプに戻して漂白してまた紙にするとか。「モノ」を無駄に破棄しない、と言う意味では素晴らしい。

でもちょっとまってくれ。そもそも、その「モノ」は何のために消費されているのだ? 我々は「ペットボトルを買いたい」わけじゃない。我々は「紙が欲しい」わけじゃない。

ペットボトルなら、その中にあるジュースが欲しいのだ。紙が欲しいのではなく、紙に印刷されている情報が欲しいのだったり、紙に包まれている中身が欲しかったりするのだ。まさに輸送のためのケースがペットボトルであり、紙なわけだ。だからこそリサイクル出来るぐらい損傷少なくペットボトルや紙を回収できる。

しかし、リサイクル・ループはエネルギー的に見れば決してただじゃない。輸送にはガソリンが、加工には電気が使われているはずだ。

じゃぁ、ペットボトルを使わない、紙を使わないで目的を達することは出来ないだろうか?

非炭酸系の飲み物をペットボトルから紙容器に切り替えるとか。

新聞を紙から電子版に変えるとか。

本来の目的からすれば別に欲しいわけじゃないモノを使わないようにする事で、リサイクル・ループを流れるモノの絶対量を減らす。しかも「本来の目的」は別にセーブしなくてよい事になる。

今回の節電は、目先の電力消費量を変えるのではなく、リサイクル・ループを流れる物流を減らしつつ、無駄にモノを廃棄しない、という形を取らないと苦しいと思う。目先のペカペカしたものを排除するような発想では、長期的に見ると必要なエネルギーが減らないままだ。

登録: 投稿 (Atom)