いかにして命令の入れ替わりについて心配するのをやめ、メモリモデルを愛するようになったか

kernel/vm探検隊 17回 @nullpo_head

Transcript

1. いかにして命令の入れ替わり について心配するのをやめ、 メモリモデルを 愛するようになったか @nullpo_head kernel/vm探検隊17 1
2. @nullpo_head (Takaya Saeki) 仮想化周りとかOSとかよくやってます 過去の発表とか • カーネル空間ですべてのプロセスを動かすには • WebAssemblyのWeb以外のことぜんぶ話す • Unikernelと和解せよ
3. 3 一瞬宣伝 • オライリーから名著Binary Hacksの続編だします！ • @nullpo_headも著者の一人です • ELFの話、セキュリティの話、 OSの話、VMの話、コンテナの 話、浮動小数点の話など もりだくさん
4. 本題 4
5. 杞国有下人憂二天地崩墜、身亡一レ所レ寄、廃 二寝食一者上。又有下憂二彼之所一レ憂者上。 杞（き）の国に、天が落ち地が崩れて身の置き 所がなくなるのではないかと心配し、夜も寝ら れず、食物もろくに食べられない者がいた。 ― 無用の心配をする。とりこし苦労 今週のことわざ（三省堂辞書編集部）2008/1/28よ り引用 杞憂 5
6. 杞国有下人憂二天地崩墜、身亡一レ所レ寄、廃 二寝食一者上。又有下憂二彼之所一レ憂者上。 杞（き）の国に、天が落ち地が崩れて身の置き 所がなくなるのではないかと心配し、夜も寝ら れず、食物もろくに食べられない者がいた。 ― 無用の心配をする。とりこし苦労 今週のことわざ（三省堂辞書編集部）2008/1/28よ り引用 杞憂 6 天が落ちてきたらどうしよう？
7. 杞国有下人憂二天地崩墜、身亡一レ所レ寄、廃 二寝食一者上。又有下憂二彼之所一レ憂者上。 杞（き）の国に、天が落ち地が崩れて身の置き 所がなくなるのではないかと心配し、夜も寝ら れず、食物もろくに食べられない者がいた。 ― 無用の心配をする。とりこし苦労 今週のことわざ（三省堂辞書編集部）2008/1/28よ り引用 杞憂 7 天が落ちてきたらどうしよう？ そんなことを心配する 必要はないのだ
8. 天が落ちてきたらどうしよ う？ ありえないようなことを心配 する、とりこし苦労をすると いう意味になった 杞憂 8
9. • プログラムは書いた順に上から実行される • マルチスレッドプログラムではどちらの スレッドが先に動くかはタイミングにより不定 9 プログラマにとっての天地 適当なコード片
10. 10 プログラムが書いた順番では 実行されなくなったらどうし よう 杞憂？
11. 11 プログラムが書いた順番では 実行されなくなったらどうし よう これが 杞憂？ 適当なコード片
12. 12 プログラムが書いた順番では 実行されなくなったらどうし よう これが こうとか 杞憂？ 適当なコード片
13. 13 プログラムが書いた順番では 実行されなくなったらどうし よう これが こうとか 杞憂？ 適当なコード片 それについては心配してくれ
14. • マルチコアプロセッサでは観測可能なメモリ命令の入れ替わりが起こる • 今日はメモリモデルの話をします • なぜ急に？→苦労したからみんながこれで苦労してないとは信じたくない… • Kernel/VMの人で「メモリモデル」を聞いたことがないという人はいなさそうだが、 苦労していないかというとそうではないのでは？と疑っている 14 メモリ命令の入れ替わり
15. ゴール：C++のレベルで、何のメモリモデルを選べばいいかわかる • C++メモリモデルなどから難しいイメージがある • しかしCPUのレベルに落とすと原則は簡単に理解できる！ • ハードウェアメモリモデル → ソフトウェアメモリモデルの順番で入って完全制覇や！ • ところでキャッシュコヒーレンシは仮定します 15 ゴール
16. クイズ 16 このプログラムでありうる(Ry, Rx)は？ 1. (1, 0), (0, 1), (1,1) だけ 2. x86では (1, 0), (0, 1), (1,1) 、 armでは加えて (0,0)も 3. x86/armともに (1, 0), (0, 1), (1,1), (0,0) すべて
17. クイズ 17 このプログラムでありうる(Ry, Rx)は？ 1. (1, 0), (0, 1), (1,1) だけ 2. x86では (1, 0), (0, 1), (1,1) 、 armでは加えて (0,0)も 3. x86/armともに (1, 0), (0, 1), (1,1), (0,0) すべて
18. 正解: 3 x86, armとも右の実行順による (0,0)がありうる 18
19. マルチコア環境で動く プログラムは 突然順番がひっくり返ったりする 杞憂ではない！！ 19 プログラムが書いた順番 では実行されなくなったら どうしよう
20. なぜメモリ命令が入れ替わるのか 20
21. • CPUは「実行結果を変えない限り」 なんでも最適化をやる • 古典的なのがwrite-backキャッシュ • マルチコアだと 「実行結果を変えない限り」 が成り立たなくなりうる • Out-of-orderも含むがそれに限らない 21 CPUの最適化 Execution Order のキャッシュが任意のタイ ミングでメモリに反映される 一旦write buffer にキャッシュだ けすれば、書き 込み完了を待た なくていいしあ とでキャッシュ から読める
22. 22 マルチコアで実行結果が変わる最適化 Execution Order の キ ャ ッ シ ュ が メモリに反映される の キ ャ ッ シ ュ が メモリに反映される
23. 23 マルチコアで実行結果が変わる最適化 Execution Order の キ ャ ッ シ ュ が メモリに反映される の キ ャ ッ シ ュ が メモリに反映される
24. 24 マルチコアで実行結果が変わる最適化 Execution Order の キ ャ ッ シ ュ が メモリに反映される の キ ャ ッ シ ュ が メモリに反映される
25. 25 マルチコアで実行結果が変わる最適化 Execution Order の キ ャ ッ シ ュ が メモリに反映される の キ ャ ッ シ ュ が メモリに反映される
26. 26 マルチコアで実行結果が変わる最適化 Execution Order の キ ャ ッ シ ュ が メモリに反映される の キ ャ ッ シ ュ が メモリに反映される
27. ハードウェアメモリモデル 27
28. 原因はさまざま • ライトバッファキャッシュ • Out-of-order実行 • … 28 マルチコア環境では 最適化が観測結果を変える
29. マルチコアの恩恵のために観測結果を変える最適化は禁止/もしくはキャンセル可能にするぞ！ • ライトバッファキャッシュ禁止 • Out-of-order実行の複雑化 => つらすぎ 29 最適化あきらめる？
30. • 観測可能な（=プログラムの実行結果が変わるような）入れ替わりは共有メモリで起こる • 最適化をあきらめるのではなく、抽象化してメモリ命令の入れ替わりとしてモデル化する • 入れ替わりの原因は実装依存だが、Out-of-orderが直接関係するとは限らないことに注意 • 「いつ命令が入れ替わるだろう？」と心配するのではなく、対策をとれるようにする 30 メモリモデルが来る
31. • 最適化をあきらめるのではなく、抽象化してメモリ命令の入れ替わりとしてモデル化する • 入れ替わりの原因は実装依存だが、Out-of-orderが直接関係するとは限らないことに注意 • ハードウェアメモリモデルはシンプル • ざっくりいって、次の表で、「どの後続の命令が前の命令を追い越しうるか」を定義する 31 ハードウェアメモリモデル ペア 追い越す? load -> load ??? store -> store ??? load -> store ??? store -> load ???
32. • シングルコアでも結果が壊れるような追い越しは起きない • 同じアドレスへのメモリ命令は追い越さない • 結果を使用する先のメモリ命令は追い越さない (分岐は依存ではないので注意） 32 メモリ命令の追い越し 追い越しうる 追い越さない 追い越しうる 追い越さない
33. Execution Order
34. Execution Order loadが追い越したとモデル化する
35. • Sequential Consistency (逐次実行、理想の世界) • TSO (x86) • Weak (arm) • なおrisc-vはTSO実装もweak実装もある 35 主要な3つのハードウェアメモリモデル ペア Sequential Consistency TSO (x86) Weak (arm) load -> load No No Yes store -> store No No Yes load -> store No No Yes store -> load No Yes Yes
36. 36 最初の例 • Store -> load の順だから、x86 / armの両方で追い越しが起こる ペア TSO (x86) Weak (arm) load -> load No Yes store -> store No Yes load -> store No Yes store -> load Yes Yes
37. Store-> load -> store-> store -> load • Loadは前二つのstoreの片方、または両方追い越しうる • しかし先頭のstoreは追い越さない • そのためにはload->loadの追い越しが必要だから 37 複数命令の追い越しの考え方 pair TSO load -> load No store -> store No load -> store No store -> load Yes
38. 38 ハードウェアメモリモデルは 詳細を横に置けば割とそれだけ！！
39. 入れ替わりますとだけ言われても困る しかしまぁ 39
40. メモリ命令を制御しろ！ 40
41. • X86のmfenceやarmのdmbなど • 本来のメモリモデルなら許されている場所の追い越しを禁止すると考えていい • 局所的にWeak -> TSO -> SC の昇格を行える • 細かい命令はリファレンスを参照してね (lock, xchg, CPUID, .. も追い越し禁止をするよ) 41 メモリバリア命令 – フェンス mov [x] <- 1 mfence mov rax <- [y] ペア SC TSO (s86) load -> load No No store -> store No No load -> store No No store -> load No Yes mfence
42. • C++メモリモデルを効率的に実装するために追加された メモリ追い越しを制御するための命令 • あとで話します 42 Store-release / load-acquire 命令
43. ソフトウェアメモリモデル 43
44. 基本的にはハードウェアメモリモデルと同じ しかし二つのコンセプトの追加がある 1. コンパイル時リオーダリング 2. Atomic性 44 ソフトウェアメモリモデル
45. • コンパイラも自由に命令を並べ替えてコンパイルすることがある • X86 (TSO)のCPUであろうと、もとのプログラムからはload->loadの入れ替えさえ起こる 45 コンパイル時追い越し void func(int *p1) { int *p2 = heavy_calc(p1); int i1 = *p2; int i2 = *p1; func: reg_for_i2 <- load(reg_for_p1) call heavy_calc(reg_for_p1) reg_for_p2 <- reg_for_return reg_for_i1 <- load(reg_for_p2)
46. • コンパイラは32bitメモリアクセスを1バイトx4回してもよい • Atomicアクセスを明示する必要がある 46 Atomic性
47. • “atomic”型の操作にメモリモデルを指定させるAPIで追い越しとアトミック性の両方を制御 1. seq_cst 2. relaxed 3. acquire 4. release 5. acq_rel (for atomic read-write) 6. consume (非推奨忘れていい) • informalには結局のところ、他のatomic/non-atomic変数との間の追い越しの有無で理解していい • なお、追い越しの結果、複数スレッドが同時にnon atomic変数に読み書きするようなコードは非合法 47 C++メモリモデル atomic_bool.store(true, std::memory_order::seq_cst)
48. • ハードウェアメモリモデルのSequential Consistencyに対応 • non-atomicな変数を含め、 先にあるすべてのメモリアクセスを追い越さない 後続のすべてのメモリアクセスに対して、seq_cstを追い越しさせない 48 Seq cst ペア 追い越す？ seq_cst load/store -> any variable No any variable -> seq_cst load/store No
49. • ハードウェアメモリモデルのWeakに対応 • すべての追い越しを許す • 他のseq_cstやacquire,releaseに邪魔されない限り 49 releaxed ペア 追い越す？ 下行以外の relaxed/non-atomic load/store relaxed/non-atomic load/store Yes seq_cst load/store relaxed load/store No relaxed load/store → release store No acquire load → relaxed load/store No
50. • C++ではこれを使いこないしたいわけです！ • 一旦formalなC++のセマンティクスをみてみよう An atomic operation A that performs a release operation on an atomic object M synchronizes with an atomic operation B that performs an acquire operation on M 10 50 acquire, release ＿人人人人人人人人人人人＿ ＞ なかなか意味不明！ ＜ ￣Y^Y^Y^Y^Y^Y^Y^Y^Y ^
51. An atomic operation A that performs a release operation on an atomic object M synchronizes with an atomic operation B that performs an acquire operation on M 10 “synchronizes”： ざっくり、 • あるスレッドのatomic変数への書き込みで、 同じatomic変数への読み込みで別のスレッドが入れた値を観測したら、 • 読み込み以降のメモリ操作はすべて書き込み以前のメモリ操作の結果を観測できる • 逆にそれ以外は保証しない まだ難しい • ちなみに基本的にペアで使うが、そろわなくても害はない 51 acquire, release
52. 52 CPUのrelease/acquire命令を見よう！
53. • 理解のためにCPU命令の話に戻りましょう • CPU命令はシンプル • 先にネタバレすると、フェンスやロックなしにおおよそTSOに相当する命令 • なのでこれはarm/risc-vにしかない 53 Acquire-release / load-store 命令
54. load命令に、メモリリオーダリングの制御がくっついたもの • ld.aq (正確には `.aq`部分) は、後続するメモリ命令が ld.aq を追い越すのを禁止する • しかし、ld.aq自体は先の命令を追い越していい それだけ！ 54 ld.aq - RISC-V weak memory
55. store命令に、メモリリオーダリングの制御がくっついたもの • sd.rl (正確には `.rl`部分) は、それ以前の命令を追い越さない • しかし、sd.rl以降の命令がsd.rlやそれ以前の命令を 追い越すのは邪魔しない • なのでsdの前にフェンス命令を置く場合より弱い 55 sd.rl - RISC-V weak memory
56. • 組み合わせると、sd.rl -> ld.aqの追い越しは許されることが特徴 56 お互いの追い越しは許される 追い越しうる 追い越さない
57. すべてのメモリ命令をacquire/releaseで行ったとすると表の通りTSOと一致 • TSOによるメモリ操作を必要な箇所だけで効率的に行う命令といえる 57 TSOとrelease/acquireの関係 pair TSO load -> load No store -> store No load -> store No store -> load Yes pair 追い越す？ ld.aq -> ld.aq No sd.rl -> sd.rl No ld.aq -> sd.rl No sd.rl -> ld.aq Yes
58. • いかにもload acquire / store releaseという 名前をしているがSequential Consistency • v8.3から入ったLDAPRは真にload acquire 58 こぼれ話: armv8 の LDAR / STLR
59. 59 C++ の release / acquire に戻る
60. An atomic operation A that performs a release operation on an atomic object M synchronizes with an atomic operation B that performs an acquire operation on M 10 “synchronizes”： • acquire loadで、release storeで別のスレッドが入れた値を観測したら、acquire以降 のメモリ操作はすべてrelease以前のメモリ操作の結果を観測できる → sd.rlは以前のメモリ命令を追い越さないことでこれを実装 • 逆にそれ以外は保証しない → releaseより後のメモリ操作はreleaseを追い越しているかもしれないし、 acquire側は先のメモリ命令を追い越しているかもしれない 60 acquire, release
61. • informalには、結局以下の表の追い越しが起こるということ 61 acquire, release ペア 追い越す？ Any atomic/non-atomic load/store → release store No acquire load → any atomic/non-atomic load/store No release store / relaxed or non-atomic load/store → acquire load / relaxed or non-atomic load/store Yes release store → seq_cst load/store No seq_cst load/store → acquire load No
62. • seq_cst, acquire/release, relaxedは、だいたいSC, TSO, Weakに対応して追い越し関係を制御する • 許可された追い越しが起きても、non-atomic変数に複数スレッドが 同時に読み書きしないようモデルを選択する ⇒ synchronizeの結果non-atomic変数のアクセス順序がきまるようにする 62 C++メモリモデルまとめ ペア 追い越す？ seq_cst load/store → any atomic/non-atomic variable No any atomic/non-atomic variable → seq_cst load/store No any atomic/non-atomic load/store → release store No acquire load → any atomic/non-atomic load/store No release store / relaxed or non-atomic load/store → acquire load / relaxed or non-atomic load/store Yes
63. メモリモデルを通して命令の追い越しを理解し、必要なバリアやmemory_order::*を使おう まとめ 63 ペア Sequential Consistency TSO (x86) Weak (arm) load -> load No No Yes store -> store No No Yes load -> store No No Yes store -> load No Yes Yes ペア 追い越す？ seq_cst load/store → any atomic/non-atomic variable No any atomic/non-atomic variable → seq_cst load/store No any atomic/non-atomic load/store → release store No acquire load → any atomic/non-atomic load/store No release store / relaxed or non-atomic load/store → acquire load / relaxed or non-atomic load/store Yes