Upgrade to Pro — share decks privately, control downloads, hide ads and more …

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

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

@nullpo_head
kernel/vm探検隊 東京18
https://kernelvm.connpass.com/event/355100/

ハードウェアメモリモデル(Sequential Consistency, TSO, Multicopy atomic weak models, Non-Multicopy atomic weak models)とC++ソフトウェアメモリーモデルの話をしました

Avatar for Takaya Saeki

Takaya Saeki

August 09, 2025
Tweet

More Decks by Takaya Saeki

Other Decks in Technology

Transcript

  1. • メモリモデルについてTSO, Weak, そしてC++ソフトウェアメモリーモデルを解説した • が、思いっきり誤りがあった Special Thanks: @yamasa さん(本当に)

    • 誤りがまた見つかると思うので今度は https://fuel.edby.coffee/posts/kvm-mm-teisei に随時訂正をあげます(予定) • 前回のスライドは単純に非公開にしたので今回は訂正先へのリンクを書いた 2 前回の内容を訂正しつつパワーアップし て話します
  2. 6 杞 憂 杞 国 有 下 人 憂 二

    天 地 崩 墜 、 身 亡 一 レ 所 レ 寄 、 廃 二 寝 食 一 者 上 。 又 有 下 憂 二 彼 之 所 一 レ 憂 者 上
  3. 8 杞(き)の国に、天が落 ち地が崩れて身の置き所 がなくなるのではないか と心配し、夜も寝られず、 食物もろくに食べられな い者がいた。 今週のことわざ(三省堂辞書 編集部)2008/1/28より引用 杞

    憂 杞 国 有 下 人 憂 二 天 地 崩 墜 、 身 亡 一 レ 所 レ 寄 、 廃 二 寝 食 一 者 上 。 又 有 下 憂 二 彼 之 所 一 レ 憂 者 上 天が落ちてきたらどうしよう?
  4. 杞(き)の国に、天が落 ち地が崩れて身の置き所 がなくなるのではないか と心配し、夜も寝られず、 食物もろくに食べられな い者がいた。 今週のことわざ(三省堂辞書 編集部)2008/1/28より引用 杞 憂

    杞 国 有 下 人 憂 二 天 地 崩 墜 、 身 亡 一 レ 所 レ 寄 、 廃 二 寝 食 一 者 上 。 又 有 下 憂 二 彼 之 所 一 レ 憂 者 上 9 天が落ちてきたらどうしよう? そんなことを心配する 必要はないのだ
  5. Core 1 Core 2 Ry = load(y) Store(x,1) Rx =

    load(x) Store(y,1) Ry: ??? Rx: ??? ← Code Order Initially x: 0, y: 0
  6. Core 1 Core 2 Ry = load(y) Store(x,1) Rx =

    load(x) Store(y,1) Ry: 1 Rx: 0 Initially x: 0, y: 0 ← Execution Order Execution Pattern 1
  7. Core 1 Core 2 Ry = load(y) Store(x,1) Rx =

    load(x) Store(y,1) Ry: 1 Rx: 1 ← Execution Order Initially x: 0, y: 0 Execution Pattern 2
  8. Core 1 Core 2 Ry = load(y) Store(x,1) Rx =

    load(x) Store(y,1) Ry: 1 Rx: 1 ← Execution Order Initially x: 0, y: 0 Execution Pattern 3
  9. Core 1 Core 2 Ry = load(y) Store(x,1) Rx =

    load(x) Store(y,1) Ry: 0 Rx: 1 ← Execution Order Initially x: 0, y: 0 Execution Pattern 4
  10. Core 1 Core 2 Ry = load(y) Store(x,1) Rx =

    load(x) Store(y,1) Ry: 1 Rx: 1 ← Execution Order Initially x: 0, y: 0 Execution Pattern 5
  11. Core 1 Core 2 Ry = load(y) Store(x,1) Rx =

    load(x) Store(y,1) Ry: 1 Rx: 1 ← Execution Order Initially x: 0, y: 0 Execution Pattern 6 Ry: 0, Rx: 0は 起こらない Sequential Consistency リオーダーのないモデル
  12. • CPUは「実行結果を変えない限り」 なんでも最適化をやる • 古典的なのがwrite-backキャッシュ • マルチコアだと 「実行結果を変えない限り」 が成り立たなくなりうる 23

    CPUの最適化がSCを壊す Core 1 Store(x,1) // cached Ry: 0 ← Execution Order Ry = load(y) (xのキャッシュが任意のタイミ ングでメモリに反映される) 一旦write buffer にキャッシュだ けすれば、書き 込み完了を待た なくていいしあ とでキャッシュ から読める
  13. 24 マルチコアで実行結果が変わる最適化 Core 1 Core 2 Store(x,1) // cached Rx

    = load(x) Store(y,1) Ry: ? Rx: ? ← Execution Order Ry = load(y) (x の キ ャ ッ シ ュ が メモリに反映される) (y の キ ャ ッ シ ュ が メモリに反映される) これが実行結果 を変えてしまう
  14. 25 マルチコアで実行結果が変わる最適化 Core 1 Core 2 Store(x,1) // cached Rx

    = load(x) Store(y,1) Ry: 0 Rx: 0 ← Execution Order Ry = load(y) (x の キ ャ ッ シ ュ が メモリに反映される) (y の キ ャ ッ シ ュ が メモリに反映される)
  15. 29 最初の例 • Store -> load の順だから、x86 / armの両方でリオーダーが許されるというモデリングが可能 ペア

    TSO (x86) Weak (arm) load -> load No Yes store -> store No Yes load -> store No Yes store -> load Yes Yes
  16. インテルが「Intra-Processor Forwarding」や 「Store-buffer Forwarding」と呼ぶ挙動 この例でも rxとryは0になりうる • Store(x,1)がRy=load(y)より遅くリオー ダーされるのはいいね? •

    でもならRx=load(x)も0なのでは?? • Ry = load(y)がrx=load(x)を追い越さ ないと無理でしょ? • TSOではload->loadの入れ替わりは 起こらないはず 31 ストアバッファバイパス Core 1 Core 2 Ry: 0 Rx: 0 Store(x,1) Rx = load(x) Store(y,1) ← Execution Order Ry = load(y) Ry = load(y) // 1 Rx = load(x) // 1??
  17. インテルが「Intra-Processor Forwarding」や 「Store-buffer Forwarding」と呼ぶ挙動 この例でも rxとryは0になりうる • Store(x,1)がRy=load(y)より遅くリオー ダーされるのはいいね? •

    でもならRx=load(x)も0なのでは?? • Ry = load(y)がr1=load(x)を追い越さ ないと無理でしょ? • TSOではload->loadの入れ替わりは 起こらないはず 「r1 = load(x)もstore(x, 1)をグローバルメモリ オーダーでは追い越しているが、その際ストア バッファからプログラム順で先行するストア命 令の値が転送されてくる」と定 義する。 32 ストアバッファバイパス
  18. 34 弱いメモリモデル(arm v8, RISC-V) ペア TSO (x86) Weak load ->

    load No* Yes store -> store No Yes load -> store No Yes store -> load Yes Yes
  19. • コア1がS1で行ったx <-1 を観測するまでコア2はL1でループを行う • その後、コア2はS2で y <- 1を実行 •

    コア3がこのS2の結果をL2で x<-1を読んだ • L3がL2を追い越さないようにフェンスしつつxの値を読む!!当然1だよね? 42 因果律の崩壊 0が読まれ うる!
  20. • 命令のリオーダーを制約するフェンスや順序保証付きメモリ命令、 もしくはほかのコアへメモリをフラッシュする命令をつかって適切に制御しよう 44 適切にフェンス/アトミック命令を使おう リオーダー ペア Sequential Consistency TSO

    (x86, RISC-V ztso) MCA 弱いモデ ル (RISC-V, armv8) Non-MCA 弱い モデル (armv7, POWER) load -> load No No*バイパスルールに注意 Yes Yes store -> store No No Yes Yes load -> store No No Yes Yes store -> load No Yes Yes Yes 書き込み伝搬 タイミング差 No No No Yes
  21. • “atomic”型の操作にメモリモデルを指定させるAPIでオーダリングとアトミック性の両方を制御 1. seq_cst 2. relaxed 3. acquire 4. release

    5. acq_rel (for atomic read-write) 6. consume (非推奨忘れていい) 50 C++メモリモデル atomic_bool.store(true, std::memory_order::seq_cst)
  22. “synchronize” : スレッドAがrelease storeで書き込んだ値を別のスレッドBがacquire loadで読み込んだ時 このペアはスレッドをまたがってhappens before関係を作る ざっくり • スレッドAがrelease

    storeで入れた値を、別のスレッドBがacquire loadで読みこんだら、ス レッドBのacquire以降のメモリ操作はすべてrelease以前のスレッドAのメモリ操作の結果を読 み込める 54 Acquire load & release store スレッドA たくさんのメモリ操作 x.store(1, release) スレッドB x.load(acquire) // 1 たくさんのメモリ操作 … Happens-before
  23. 55 C++のメモリオ ー ダ ー だって?あれは単に COHERENCE-BEFORE と HAPPENS-BEFORE の

    ニつの半順序が互いに無矛盾であるようなメモリ 操作集合だよ。何か問題でも? (こんな格言はない)
  24. • スレッドAがrelease storeで入れた値を、別のスレッドBがacquire loadで読みこんだ ら、スレッドBのacquire以降のメモリ操作はすべてrelease以前のスレッドAのメモリ 操作の結果を読み込める • store -> storeおよびload

    -> storeはリオーダーされない => 末尾のstore以前のメモリ操作は終わっている load -> storeおよび load -> loadもリオーダーされない => 先頭のloadを追い越すメモリ命令はない =>なのでacquire / releaseの制限を満たす 他のアーキテクチャでは、TSO相当のフェンスや、専用の命令を使うことになる 57 acquire, releaseは x86(TSO)だと普通のload/storeで良い スレッドA … Store(x, 1) スレッドB Load(x) // 1 …
  25. • Release / acquireが持つ保証はすべて保証する • seq_cst store & seq_cst load

    • seq_cst store & acquire load • release store & seq_cst load がhappens-before* • くわえて、全スレッド間でseq_cstのアトミック操作すべての読み書きの順序がつけれることを 保証する(グローバルメモリオーダーみたいなノリ) • POWER上でさえも! • コンパイラはいっぱいフェンスをいれることになる 60 Seq_cst
  26. • Release / acquireが持つ保証はすべて保証する • seq_cst store & seq_cst load

    • seq_cst store & acquire load • release store & seq_cst load がhappens-before* • くわえて、全スレッド間でseq_cstのアトミック操作すべての読み書きの順序がつけれることを 保証する(グローバルメモリオーダーみたいなノリ) • POWER上でさえも! • コンパイラはいっぱいフェンスをいれることになる 61 Seq_cst
  27. • C++ 11 から17でseq_cstの全順序がPOWER上で矛盾することが報告 -> C++20で修正 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0668r5.html (strongly happens before)が導入された理由

    • C++20で今度はx86上で起こるストアバッファバイパスによりseq_cstの全順序が壊れることが報 告 -> いまだ修正されず https://cplusplus.github.io/LWG/issue3941 上の修正でついでのcoherence order関係を導入したのが原因 C++委員会にすらC++メモリモデルは難しい (全部仕様上の重箱の隅ケースだから実用上は気にしないでね 63 しかし、バベルの塔は今日も崩壊する…
  28. • https://research.swtch.com/hwmm Hardware Memory Models, Russ Cox • ある程度短いが詳細なのでいちばんおすすめ •

    “A Primer on Memory Consistency and Cache Coherence“ • 詳細な教科書だが、Non-MCAなアーキテクチャとC++への言及がない • https://docs.kernel.org/core-api/wrappers/memory-barriers.html Linux kerenlのメモリモデルて • C++ほど抽象的ではないモデルで、具体例をもとに説明してくれる • 最近はもっとフォーマルなメモリモデルも生えたらしいけど読んでいない • Rust atomics and lock • いいらしい • C++ spec 65 参考文献