プロフィール

kosaki

Author:kosaki
連絡先はコチラ

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

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

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


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

シーケンスロック その5 volatileがダメな理由 このエントリーをはてなブックマークに追加

どもども。またまた間隔があいてしまいましたがシーケンスロックな話しの続きです。
前回の記事で坩堝さんから面白い指摘をうけたので今回は予定を変更してvolatileの話をしたいと思います。


retをvolatileにするだけではうまくいかないんですよね?
どういう風になるんだろ.




なるほど、たしかに世のC言語の参考書を見るとvolatileはある種の最適化を妨げる効果を持つと
されています。
これだけ見ると、volatileとつけるだけすべての最適化が無効になってうまく動きそうですね。
しかし、その理屈は微妙におかしいのである


多くの人が「ある種の」という言葉を拡大解釈しているがvolatileは本来スレッド同期に使えるようなシロモノではないのである。

つづきは、続きを読むからご覧ください。


あと、お願い。
今回の話は前提知識がいろいろとあるので、末尾のご参考にあげたURLを読んでから
読んでいただけるとうれしいっす。



そのりくつはおかしい
その理屈はおかしい! ランキング



でわ。ぢっけん!

↓ ソース case1.c

extern int hogehoge;
extern int tmp;
extern int bar(int);

typedef struct {
unsigned sequence;
} seqlock_t;


foo(seqlock_t* lock)
{
volatile unsigned seq;

do{
volatile unsigned ret = lock->sequence;
seq = ret;

tmp = hogehoge;

}while( (seq & 1) | (lock->sequence ^ seq) );

bar(tmp); // tmpを参照しておかないと最適化で消されちゃうので適当に。

}


指摘されたのはretだけだったが、ここではseqもvolatile指定しているのに注意。
こいつをgcc -S でコンパイル

; 以降のコメントは僕が挿入したもの。
これでx86のアセンブラが読めない人も大体なにをやっているのかわかると思う。
%eaxとか%edxとかってのはレジスタね。念のため。

↓ 生成された case1.asm

.file "case1.c"
.text
.p2align 2,,3
.globl foo
.type foo, @function
foo:
pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $20, %esp
movl 8(%ebp), %eax ; %eax = lock
movl hogehoge, %ebx ; %ebx = hogehoge
movl (%eax), %ecx ; %ecx = lock->sequence
.p2align 2,,3
.L2:
movl %ecx, -12(%ebp) ; ret = %ecx;
movl -12(%ebp), %eax ; %eax = ret;
movl %eax, -8(%ebp) ; seq = %eax
movl -8(%ebp), %edx ; %edx = seq
movl -8(%ebp), %eax ; %eax = seq
andl $1, %edx ; %edx = 1 & %edx
xorl %ecx, %eax ; %eax = %ecx ^ %eax
orl %eax, %edx ; %edx = %eax | %edx
jne .L2 ; if( %edx != 0 ) goto L2
subl $12, %esp
pushl %ebx
movl %ebx, tmp
call bar
movl -4(%ebp), %ebx
leave
ret
.size foo, .-foo
.section .note.GNU-stack,"",@progbits
.ident "GCC: (GNU) 3.4.4 20050721 (Red Hat 3.4.4-2)"


はい、見事に動かないプログラムが出来ましたね。
retへのstoreは最適化の影響を免れてループ内に残っていますが、肝心のlock->sequenceのloadと
hogehogeのloadが両方ともループ外に追い出されてしまいました。

なお悪いことに、hogehogeの読み出しにいたってはロック取るよりも前に移動しちゃってます。
ループの中とか外とか以前の問題ですね。


ここで詐欺だ。コンパイラがバグってるぞ!と思う人もいるかもしれません。
でもそうではないのです。

これから、色んな人がvilatileやら最適化やらスレッドやら同期やらという単語で想像する動作と
実際にvolatileがそれを行うかについて、一つ一つ説明していきましょう。
ただし、C言語の規格上はvolatileについて処理系独立は意味は存在しないので、これはあくまで
私の経験上の「普通」なので、世の中は広いので反論あるかもしれない。

そこはご理解のうえ、書き文章を読んでいただきたい。
(つまり調べもせずに適当かいてるってことね。眉に唾つけて読んでね)


1.レジスタ変数とはならないことの保障する

C言語の世界では普通に int var1; などと宣言しただけだとその変数がメモリにとられるか
レジスタに置かれるかは分からない。
ただし、どこかで addr = &var1; のようにアドレスをとるとメモリに置かれる変数であることが
保障されます。

volatile int var1; と宣言することは、アドレスをとらなくてもメモリ上に変数が
取られることを保障します。

こういう実装にするよって、自動変数をvolatileにしたときにsetjmp/longjmpで復帰できなきゃだめ。
という規格要請が満足できるわけです。

volatileの説明でよく見かける、HWサポートのための修飾子という説明だけだと、自動変数はHWレジスタでは
ありえんからvolatileを無視するコンパイラとかわらわら出てきそうですが、setjmp/longjmpは
標準Cライブラリだからして、なかなか非サポートとはいえない。
かつsetjmpなんかあんまり使わないので、こって巧妙な最適化をしてもしょうがない。ってわけで
結構通用する常識だったりします。


2.load命令、store命令の発行回数の保存

これは説明いる?
for(i=0;i<3;i++){
*pHWDevice = 3;
}
とかやったときに代入をループの外に追い出したりすると、メモリへのstoreの回数が変わるでひょ。
それは禁止。
つまり、周りの変数がvolatileでない以上、式が展開されたり移動したりくっついたりするのは
避けられない。
でも、その結果によってメモリアクセスの回数が変わっちゃダメよん。
ハードウェアにアクセスするときに結果が変わるから。

ってのがコンパイラ製作者には求められておりますです。


3.メモリ引数命令を使うことは保障されない

CPUによっては、算術演算にメモリ引数をとる形式とレジスタ引数の両方をサポートしているものがある
(x86とかね)

たとえば
i++
をコンパイルした結果として

a) メモリオペラント
	inc [iのアドレス]


b) レジスタオペラント
	movl [iのアドレス], $eax
inc $eax
movl $eax, [iのアドレス]


の2通りの形式が考えられるが、volatileをつけたからといってa)の形式は強制されない。
むしろgccとかだと普通はb)

なんでかというと、たとえばRISCだとa)がそもそも存在しないから考えるだけ無意味だし
x86だとa)のようなコードを吐いてもどうせCPUが内部的にμop命令に変換するときに
b)形式になってしまうので意味がないから

これは勘違いしている人がたまにいる


特にa)のデメリットも思いつかないけれども、ま、メンドクサイんだろうね。
volatileなければb)のほうが、別のload/store命令とくっつけて最適化できる可能性があるので
常にb)にしとけや。と


4.volatile変数の代入、インクリメントはatomicな操作になるとは限らない

3とちょっとかぶっているが、UNIXな世界ではsig_atomic_tという、もう紛らわしい事この上ない
typedefが定義されている。
こやつは普通は typedef int sig_atomic_t; となっている。所詮、ただのint
なんにもatomic操作を保障してくれるものではない。

x86風にいうと

lock inc [mem]


のような、アトミック命令を生成してくれたりはしないってことね。

で、intだと何が保障できるかというと普通のRISCで考えると32bitデータが32bitアラインされた所に
おかれているとき、

movl reg mem 
movl mem reg


の2つがatomicであることが保障されるってことね。
これ重要。

キャッシュだのメモリだのっては、64 or 128 or 256 bit単位での read/write が
出来るだけのデバイスだから、アドレスが中途半端なところにあると
2回のread やら write やらを発行する必要が出てきて atomic じゃなくなる。

で、Cのコンパイラはめんどいからvolatileとかそういうのに関係なく
32bit integerは32bit alignされるようにデフォルトで配置している。

メデタシメデタシ


	struct {
char c;
volatile sig_atomic_t sig_atomic;
} __attribute__ ((packed))

とかするとめでたくなくなるけど、packed は標準外なので分かってる人だけお使いくださいってことで一つ・・




6.CPUのキャッシュをバイパスしてメモリに書き出したりはしない

何度も書いていますが、volatileはコンパイラの最適化にのみ影響を及ぼすものなので
CPUが勝手にメモリアクセスをキャッシュしちまうのは防ぎようがありません。
別途CPU(&OS)依存の方法で制御する必要があります。

ページテーブルの属性だったり、特殊なディスクリプタを設定したり、あるレジスタに書き込んだり、
特殊な命令があったり、ってのが多いのかな?

その全部がサポートされていたりCPUもあるみたいですが(x86だ。こんちくしょー)
組み込みだと、アドレス決めうちでxxx番地以上はuncachedねー。みたいなのも結構ある。


7.メモリへの書き込みをstrong orderでの書き込みを保障したりはしない

6と同じ。
CPU依存の方法でuncached なメモリだよーん。と指定すればstrong orderで書き込まれます。
strong orderってのは、ようするのアウトオブオーダー実行しない。って事。


8.すくなくとも、関数コールするまえにメモリに書き戻すことが保障される

3の補足。

b) レジスタオペラント
	movl [iのアドレス], $eax
inc $eax
movl $eax, [iのアドレス]


の最後のstoreが最大どこまで延期されるか、であるが、実質的には次の関数callまでが
限度だと考えていいと思う。

なぜなら、
・longjmpしたときに、volatileな変数は復帰しないといけない。
・でも、レジスタになってる変数は復帰できない

という制約から。

レジスタも復帰できるレジスタスタックアーキ(SPARCとIA64)だとまた違うテクも
考えれそうだが詳しく知らない。


9.volatile変数への読み書きはいかなるmemory barrierも張らない

ここ超重要。
でも、この連載でアウトオブオーダの解説がまだ終わってないから書けない。
残念。無念。

別途書きます。


まとめ

メモリマップされたハードウェアレジスタへのアクセスとスレッド同期とでは用件が大きく異なる。

H/Wレジスタアクセス
・load / store の回数を勝手に削減しないでくれ
・(タイミングずれるから)storeをあんまり遅延しないでくれ

スレッド同期
・ロック変数への書き込みが終わったときには、それ以前のコードがすべて実行が終わっていることを保障してくれ
・ロック変数への書き込みの次の命令を実行するよりも前に、他のCPUからもロック変数の書き込みが可視になっていることを保障してくれ


要するに、スレッド同期は前後の順番が重要で、ハードウェアレジスタアクセスはそれはどうでもいい。
だから、volatile は基本的には使い物にならない。

だが、タチの悪いことに標準規格で signal/setjmp というコーナーケースで最適化を封じ込める為に
volatileを悪用することを認めてしまったので、さらに混乱が増えた。


参考:
「組み込み」ならではの基礎知識 http://www.kumikomi.net/article/explanation/2003/10kumi/13.html
法大奥山研究室:C言語:17.2. volatile: http://okuyama.mt.tama.hosei.ac.jp/unix/C/slide88-1.html
Javaの理論と実戦: Javaメモリ・モデルを修正する http://www-06.ibm.com/jp/developerworks/java/040416/j_j-jtp02244.html

関連記事
linux | 【2006-04-06(Thu) 11:06:13】 | Trackback:(0) | Comments:(3)
コメント
このコメントは管理人のみ閲覧できます
2007-09-01 土 17:43:10 | | # [ 編集]
>肝心のlock->sequenceのloadとhogehogeのloadが両方ともループ外に追い出されてしまいました。

ループ外に追い出されたのは、volatileが付いてないからですよね。

volatile extern int hogehoge;

typedef struct {
volatile unsigned sequence;
} seqlock_t;
という修正を追加すれば、期待通りに動くのではないですか?
2007-10-30 火 04:04:35 | URL | otn #UwJ9cKX2 [ 編集]

otnさん>
ちょうど最近、LKMLでvolatile議論があったので適当な要約ページで議論を追ってみるといいと思いますが、結論からいうとNGっすわ
要約するとSMPでまともに動かしたかったらvolatileは忘れろ。と
2007-10-30 火 06:55:43 | URL | kosaki #- [ 編集]
  1. 無料アクセス解析
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。