プロフィール

kosaki

Author:kosaki
連絡先はコチラ

ブログ検索
最近の記事
最近のコメント
最近のトラックバック
リンク
カテゴリー
月別アーカイブ
RSSフィード
FC2ブログランキング

スポンサーサイト このエントリーをはてなブックマークに追加

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


スポンサー広告 | 【--------(--) --:--:--】 | Trackback(-) | Comments(-)

シーケンスロック その4(コンパイラの野望を打ち砕け!) このエントリーをはてなブックマークに追加

引きだけで終わってしまった前回のつづきです。
最近2件つづけて「トイレ スピンロック」というキーワードでうちのサイトにやってきた人がいました。
どうやらLinuxでロック=トイレという常識は予想以上に広まっているようです。

赤レンジャーも負けてはいられません(マテ


どうみても加藤です
野望を打ちくだ・・・ってアンタどこの加藤ですか!? ランキング!





さて、今回からいよいよ rmb(), wmb() の謎に迫っていくわけであるが、そもそも、なぜにこげなモノが必要なのだろう? Why?


それは、プログラムは人間が書いた順番では動かないからである。

プログラムは決して思ったとおりには動かない――― 書いたとおりには動くけど。 
-- 詠み人不明


という古の格言を無視するような発言であるが、これは一面において事実である。
なぜなら、コンパイラには最適化、CPUにはアウトオブオーダ実行というものがあるからだ。

これが普段問題にならないのは、ソースコードに書いた順番に実行したときと異なる結果になるような最適化は許されていないからである(あたりまえだ)

ところがここで両者ともに重大な仮定をおいている。
それはシングルプロセッサで実行した時しか同一の結果を保証しない。というものである。

これにはもちろん理由がある。積極的な理由と消極的な理由の2つあるんだけど

まず、消極的な理由として、マルチプロセッサ環境では相方プロセッサの動作としてありとあらゆる可能性が考えられるので、それを考え出したら実質すべての最適化は適用不可能である。

次に積極的な理由として、少なくともユーザーランドのアプリケーションに限っていえば、
・複数プロセスが同時に動いても(プロセス毎にメモリ空間が異なるので)まったく困らない
・マルチスレッドプログラムはそもそも、たとえシングルプロセッサだとしても
複数のスレッドから触る変数にアクセスするときは、Mutexなりなんなりの排他制御しとるはずや。
だからそれ系のロック関数(の実装者)さえ頑張ればアプリの書き換えはいらん。

え、libcとカーネルの実装者はどうするって?
あいつらはキチガイやからどんだけ大変でもなんとかするよ。

というわけである。

そういう訳でわれわれキチガ・・もといカーネルハッカーはコンパイラがどういうコードを吐くのか。とか吐いたコードがどのようなメモリモデルで動くのか。とかそういうものと無縁ではいられないのである。

そういうわけで、しばらくコンパイラとCPUの最適化と戦う話をします。


まず、簡単なほうから。という事でコンパイラの話をします

コンパイラには最適化オプションというものがあり、kernelのビルドでは当然のようにONされます。
あたりまえです。だれも遅いカーネルなんて使いたくありません。

んが、しかし、さきほど説明したようにコヤツはシングルプロセッサを仮定するノータリンです。

たとえば
    do {
seq = read_seqbegin(&lock);
tmp = hogehoge;
} while (read_seqretry(&lock, seq));


というコードがあったとします。read_seqbegin(), read_seqretry()はinline関数なので
コンパイラには以下のように見えます。

    do {
unsigned ret = lock.sequence;
smp_rmb();
seq = ret;

tmp = hogehoge;

smp_rmb();
} while ( (seq & 1) | (lock.sequence ^ seq) );


ここで、smp_rmb(), smp_wmb()がなかったとしたら。つまり

#define smp_rmb()
#define smp_wmb()


こんな定義になっていたとしたらどうなるでしょうか。


コンパイラはこう考える(かもしれない)

ふむふむ、まず一時変数のretはいらんな。

    do {
seq = lock.sequence;
tmp = hogehoge;
} while ( (seq & 1) | (lock.sequence ^ seq) );



おお、sl->sequenceはこのループ中に変わることはないではないか。
てことは、ループの脱出条件のXORは常に0だな。

    do {
seq = lock.sequence;
tmp = hogehoge;
} while ( (seq & 1) | (0) );


おお、seqはループ中に変更されないから、seqの初期化はループの外に出してしまえるぞ。
てか、それを言ったらtmpもそーじゃん。
うしし

結果こうなりました。

	seq = lock.sequence;
tmp = hogehoge;

do {
} while ( (seq & 1) | (0) );


・・・・なにかがおかしいですね。


これはコンパイラから見て、「この辺でいつのまにかメモリが書きかえられちゃうかもしれないよ」と教えてくれるヒントがコードのドコにもないのが原因。

だから教えてあげればいい。これはGCCだと以下のように書く。

 asm volatile ("" ::: "memory") 


なんと、asm文の癖に機種非依存コード。
asm文を乱用している気もしなくもない。

もちろん、ここでついでにasm文にアセンブラ入れてもOK.
前回みたようにrmb(), wmb() の正体がまさにそんな感じ
#define rmb() asm volatile ("lfence" ::: "memory")
#define wmb() asm volatile ("sfence" ::: "memory")


さて、
#define smp_rmb() asm volatile ("" ::: "memory")
#define smp_wmb() asm volatile ("" ::: "memory")


となっていたら、先ほどの結果はどうなるでしょう。


まず、インライン展開まではまったくおなじ

    do {
unsigned ret = lock.sequence;
smp_rmb();
seq = ret;

tmp = hogehoge;

smp_rmb();
} while ( (seq & 1) | (lock.sequence ^ seq) );


    do {
unsigned ret = lock.sequence;
asm volatile ("" ::: "memory")
seq = ret;

tmp = hogehoge;

asm volatile ("" ::: "memory")
} while ( (seq & 1) | (lock.sequence ^ seq) );


おお、sl->sequenceはこのループ中に変わることはないではないか。
てことは、ループの脱出条件のXORは常に0だな。

むー、ループ中で lock.sequenceは変わる可能性があるな。
whileの条件式は定数式にならないぞ

おお、seqはループ中に変更されないから、seqの初期化はループの外に出してしまえるぞ。
てか、それを言ったらtmpもそーじゃん。

lock.sequenceもhogehogeもループ中に変わる可能性があるからseqもtmpもループの外に出せないぞ。
ループの外、というだけでなくループ内でもasm("":::"memory") の外側の
lock.sequenceを読み出してるあたりとは交換できない。
これは、まんま書かれたとおりにコンパイルするしかないねぇ・・トホホ

これでやっと思い通りのコードを吐いてくれました。やれやれ。

今回はコードをもりもり文中に差し入れたのでやたら長いのですが、そんなに難しいことは書いてない・・・はず。
次回は(やっと)CPUのお話に移りたいとおもいます。ではでは




関連記事
linux | 【2006-03-19(Sun) 23:49:33】 | Trackback:(0) | Comments:(3)
コメント

retをvolatileにするだけではうまくいかないんですよね?
どういう風になるんだろ.
2006-03-21 火 16:24:33 | URL | 坩堝 #- [ 編集]
このコメントは管理人のみ閲覧できます
2007-09-01 土 16:20:02 | | # [ 編集]
このコメントは管理人のみ閲覧できます
2007-10-08 月 09:04:05 | | # [ 編集]
  1. 無料アクセス解析
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。