Re: [心得] X86 架構下的 Memory Model
看板C_and_CPP (C/C++)作者sarafciel (Cattuz)時間3年前 (2021/07/20 01:32)推噓20(20推 0噓 17→)留言37則, 18人參與討論串2/3 (看更多)
※ 引述《Instance (呆呆華)》之銘言：
: 大多時間在家有點無聊，花了點時間研究以前一知半解的東西。
: 不過要強調的是，這篇文章只針對 X86。
: std::atomic 有六種 Memory Order 選項：
: memory_order_relaxed,
: memory_order_consume,
: memory_order_acquire,
: memory_order_release,
: memory_order_acq_rel,
: memory_order_seq_cst
: 這六種模式在 X86 底下幾乎沒什麼差別的，
: 用最弱的 memory_order_relaxed 就可以了，
: 因為 X86 是屬於 Strong Memory Model 的架構。
: Load-Load, Store-Store, Load-Store 情況下是安全的。
純看文章敘述而不去找reference是一件有點危險的事情
關於x86_64架構不管是amd還是intel都有留蠻大量的說明文件和手冊在網路上:
Intel® 64 Architecture Memory Ordering White Paper
https://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf
AMD64 Architecture Programmer’s Manual Volume 2:(請看7.2章)
https://www.amd.com/system/files/TechDocs/24593.pdf
: Store-Load 情況下表示，
: A 執行緒儲存某一變數，
: 其他執行緒必須同步讀到最新的數值，
: 這時就必須用到原子操作。
從這邊開始就錯了
原子操作的目的是為了解決指令的執行粒度過小的問題
以簡單的i++來說，一般在組語層級會變成read-modify-write三道指令執行
當多個core要同時執行i++的時候，有可能core A還在modify階段
core B就做read，但此時i的值還沒有存入core A的計算結果
導致最後core A跟core B在write的時候，有一方的運算是沒有反映在i的值上面
要解決這個問題，就得確保core A或core B在讀取前，
有一方的操作已經完整反映在i上面
所以read-modify-write必須變成一組不可分割的操作
這就是原子操作的由來跟目的，當有某個core在看某個被分享的共同變數x時
要不其它core對這個x什麼都還沒做，要嘛其它core已經把它的計算結果存入x了
所以原PO這邊你在談的東西，並不是atomic
它的專有名詞叫做memory barrier，
在解決的主要是亂序執行跟相依性不可見衍生的問題
因為x86_64設計特性的緣故，atomic本身自帶memory barrier的作用
但這不代表atomic就是memory barrier
就好像折凳可以當武器用，但終究折凳本來誕生的目的是給人坐的
: 如果要理解原子操作的話，
: 最簡單的方法是從硬體角度來思考。
: 現代的 CPU 有 L1, L2, L3 Cache，
: 如果你的電腦有多個核心，
: 當資料放在 L1, L2 Cache 時，
: 並不保證所有核心對某一變數的值是一致的。
well,這裡開始的東西就很複雜了XD
這一段敘述其實是對的，但也不對
L1 L2 cache確實因為是core各自獨有的
連帶會產生存在cache裡的值有同步性問題要解決
但cpu的designer其實並沒有擺爛把這個問題丟給compiler跟programmer去煩惱
原因也很簡單，如果某個共同變數x
會因為compiler跟programmer的不注意就讓core A跟B裡面的值不一樣
那這個共同變數在硬體提供的抽象上是根本失敗的
所以cache跟cache之間，其實是有一個機制在保護共同變數這個抽象的
它的名字叫做cache coherence protocol (快取一致性協議)
上面的AMD64 Architecture Programmer’s Manual Vol.2在7.3章就是這個部份了
它也告訴你amd用的是MOESI這個cache coherence protocol
但是當代的CPU為了得到更好的效能，在CCP這個部分有做一些投機的設計加速
進而導致了快取一致性在某些特定的場合下，
core A對好幾個共同變數的更改順序在core B的視野裡會跟core A不同
這個部分要講細節就必須非常的細節，所以我直接丟reference:
Memory Barriers: a Hardware View for Software Hackers
http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.06.07c.pdf
務必精讀，我找不到比這篇講得更細膩的paper了(逃)
回到memory barrier這件事上，我直接拿裡面的舉例來講:
1 void foo(void)
2 {
3 a = 1;
4 b = 1;
5 }
6
7 void bar(void)
8 {
9 while (b == 0) continue;
10 assert(a == 1);
11 }
文章內在講的是因為store buffer的影響跟共同變數在MESI裡的state不同，
導致執行bar的core看到的a跟b賦值順序有可能是反過來的
但這段code最本質的問題其實是相依性不可見。
foo裡面a跟b的賦值在純粹的context上面你是觀察不出有什麼相依性的
但是在bar裡面a跟b卻有了時序上的相關，
a的assert過不過會被b維持在0這個state有多久某種程度的決定
而相依性不可見這件事，
會直接導致亂序執行(Out of Order Execution，以下簡稱OOE)的假設失靈
CPU因為pipeline設計的緣故，兩條沒有相依性的指令儘管執行結果跟順序無關
但有些場合透過設計指令的執行順序可以減少pipeline的stall
所以執行速度是跟執行順序有關的
(如果看不懂這邊在講什麼，請去找計組跟計結的課本來翻，
pipeline是要在大學花好幾節課講的東西，我不可能在這邊講完它的內容orz)
這也導致了在不違背相依性的前提下，CPU跟compiler都會試著去做一定程度的OOE
所以上述的這段程式碼不是只有在store buffer的影響下會出錯
CPU跟compiler的OOE都有可能導致a=1和b=1的順序調換，
因為這兩行code在foo的視野裡面，你根本看不到有任何相依性，他們看起來是可以換的
所以你必須提供一個機制，讓唯一有機會觀察到相依性的角色－也就是programmer
手動的去告訴CPU跟compiler，在某個時間點你不可以做OOE
不但不能做OOE，還要把之前的讀寫結果明確的在每個core上同步
這個機制就叫memory barrier
要打個比方的話，就像你一直覺得坐你隔壁的同事是正直有為的好青年
直到他確診之前你都不知道他愛去萬華阿公店，這個就是相依性不可見
所以那個有機會觀察到相依性的人，也就是指揮中心做了PCR檢測以後
因為讓你們在外面繼續人與人的連結(OOE)很危險
所以會把跟你同事接觸過的人(包括你)關14天(設memory barrier)
而本質上你有沒有染疫這件事情當下是一個不確定的狀態
於是大家一起關14天，等到所有人的狀態都確定以後再做下一步的決策
: 而進行原子操作的動作之後，
: 變數的值會同步到所有核心的 Cache。
: 原子操作的方法有很多種：
: 1. std::atomic<int> x;
: 2. std::atomic_thread_fence(std::memory_order_relaxed);
: 3. asm volatile("mfence" ::: "memory"); // 組合語言
: 4. asm volatile("lock; addl $0,0(%%rsp)" ::: "memory", "cc"); // 好像是更快的組合
: 語言，我不是很了解
again，x86_64指令集的文獻跟說明其實很多
其中之一就是intel那個4000多頁的說明手冊:
https://tinyurl.com/6dsna7db
LOCK—Assert LOCK# Signal Prefix 在3-592 Vol. 2A
主要是說明LOCK是一個前綴，用來描述下一條指令必須要有atomic的性質
MFENCE—Memory Fence 在4-22 Vol. 2B
這個就是組語層級的total order的memory barrier了
mfence主要是針對cpu的OOE，
compiler的OOE則是由括號裡面的那個"memory"來關掉
Vol. 3A的8.1章開始就是講atomic跟memory ordering相關的部分，
其中的8.2.2節有提到:
‧ Locked instructions have a total order.
所以lock是帶有memory barrier效果的
而且lock還很神奇的比原生的mfence來的快
所以linux kernel裡就直接拿lock接一條廢指令來當作它的mfence
: 5. InterlockedExchange(); // Win API
InterlockExchange就真的是atomic operation了
而不是memory barrier
: 效果都是將變數的值同步到所有核心，
: 這樣才能保證多執行緒環境下此變數的全局可見，
: Win API 或許效能會稍差一點吧。
: 參考文章：
: C++11中的內存模型上篇 - 內存模型基礎
: https://tinyurl.com/f36rsus9
: C++11中的內存模型下篇 - C++11支持的幾種內存模型
: https://tinyurl.com/95e33cf5
: X86/GCC memory fence的一些見解
: https://zhuanlan.zhihu.com/p/41872203
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.37.122 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1626715947.A.35F.html
推
07/20 03:12,
3年前
, 1F
07/20 03:12, 1F
→
07/20 03:12,
3年前
, 2F
07/20 03:12, 2F
→
07/20 03:12,
3年前
, 3F
07/20 03:12, 3F
→
07/20 03:12,
3年前
, 4F
07/20 03:12, 4F
→
07/20 03:12,
3年前
, 5F
07/20 03:12, 5F
memory barrier是人去寫code加出來的啊
我怎麼可能知道什麼情況會有memory barrier產生XD
這個問題就好像你去問什麼情況CPU會產生加法運算一樣
我能給你最精確的回答也只有"請去看編出來的組語"而已
→
07/20 03:12,
3年前
, 6F
07/20 03:12, 6F
→
07/20 03:12,
3年前
, 7F
07/20 03:12, 7F
→
07/20 03:12,
3年前
, 8F
07/20 03:12, 8F
→
07/20 03:12,
3年前
, 9F
07/20 03:12, 9F
你如果是想問OS系統提供的多緒API有沒有memory barrier
基本上應該是100%會有，或者是他會用其他的方式保證正確性
姑且不論OS本身就要處理很多同步性問題，你會踩到的雷他們應該都踩到過
像autoresetevent這種本身就帶有時序性的機制，
微軟會讓OOE越過時序性的抽象的話早就被公開處刑了
推
07/20 14:36,
3年前
, 10F
07/20 14:36, 10F
推
07/20 16:59,
3年前
, 11F
07/20 16:59, 11F
推
07/21 07:24,
3年前
, 12F
07/21 07:24, 12F
推
07/21 12:10,
3年前
, 13F
07/21 12:10, 13F
推
07/21 12:43,
3年前
, 14F
07/21 12:43, 14F
推
07/21 12:48,
3年前
, 15F
07/21 12:48, 15F
推
07/21 13:37,
3年前
, 16F
07/21 13:37, 16F
推
07/21 16:47,
3年前
, 17F
07/21 16:47, 17F
推
07/21 23:16,
3年前
, 18F
07/21 23:16, 18F
→
07/21 23:16,
3年前
, 19F
07/21 23:16, 19F
→
07/21 23:16,
3年前
, 20F
07/21 23:16, 20F
→
07/21 23:16,
3年前
, 21F
07/21 23:16, 21F
→
07/21 23:16,
3年前
, 22F
07/21 23:16, 22F
你沒有加不代表替你寫thread API的人沒有在你呼叫的函式裡加啊XDD
而且以這個case來說，可能是連加memory barrier都不用
OOE是一個幾道 了不起十幾道指令之間發生的事件
可以說他是微觀尺度的事件
連帶的用來處理OOE的memory barrier也是微觀尺度的事件
thread因為是要被scheduling的單位 他需要在OS裡面做控管
你勢必是要用system call進kernel mode建資料結構，
還要去跟kernel要塞thread stack的分頁
然後還要等scheduler找個良辰吉時
去把這個建好的thread做context switch丟到core上面去跑
這中間能花掉的時間一定比你那個store寫值多個幾百倍
你根本不需要去擔心thread建好的時候那個值還沒進cache
那你既然可以確定thread建好的時候那個值早就在cache裡了
剩下來的就只是他會怎麼被傳遞到thread那個core上面而已
一樣的，這邊硬體會自己跑快取一致性協議，以MESI的情況來講，
就是有值的那個core裡的cache line會從Modify State進Share State
然後把值丟給你新建好的這個thread所在的core cache
最後該cache line也設成Share State，結束
你會有這樣的問題其實是出因於你對OS不了解，
然後可能對CPU的一些設計特性也不夠認識，當然這兩門都是念不完的學問啦
我知道多執行緒的東西寫久了Programmer都會變成懷疑論者
包含我自己都是，就算上面洋洋灑灑的寫了一大堆，
我都還是會怕說有些地方自己本身的理解是錯的
說穿了沒人真的有辦法看到CPU每秒10^9量級的運算是怎麼做的
如果要用眼見為憑當標準來檢驗的話，現在講的東西多多少少都有信仰的成分在
但沒有辦法真的眼見為憑，你總是可以退一步用設計的抽象做推論的
這也是為什麼應該去學OS跟CA的知識，包含這些說明手冊、教科書或著是談設計的paper
至少會讓你在判斷的時候有所本，心裡就會比較踏實
※ 編輯: sarafciel (123.193.37.122 臺灣), 07/22/2021 02:44:37
推
07/22 16:09,
3年前
, 23F
07/22 16:09, 23F
推
08/05 14:01, , 24F
08/05 14:01, 24F
推
08/05 14:59, , 25F
08/05 14:59, 25F
推
08/05 15:06, , 26F
08/05 15:06, 26F
→
08/05 15:06, , 27F
08/05 15:06, 27F
推
08/07 23:09, , 28F
08/07 23:09, 28F
推
08/09 09:02, , 29F
08/09 09:02, 29F
→
08/09 09:03, , 30F
08/09 09:03, 30F
推
08/10 00:16, , 31F
08/10 00:16, 31F
推
08/10 19:50, , 32F
08/10 19:50, 32F
→
08/10 19:51, , 33F
08/10 19:51, 33F
→
08/10 20:06, , 34F
08/10 20:06, 34F
→
08/10 20:08, , 35F
08/10 20:08, 35F
推
08/17 21:32, , 36F
08/17 21:32, 36F
推
08/20 00:55, , 37F
08/20 00:55, 37F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
