本文內(nèi)容主要是對(duì)“Memory Barriers: a Hardware View for Software Hackers” 這篇論文的總結(jié)。
背景
在 Linux 內(nèi)核和 SPDK 代碼中經(jīng)常見到 memory barrier 的使用融求，線上也遇到過因未正確使用 memory barrier 導(dǎo)致的故障务傲，自己在嘗試?yán)斫?memory barrier 過程中也走了些彎路杏糙，寫此文用以記錄。
memory barrier 并不解決同步互斥問題，而是解決 “order” 問題吴攒，即在一個(gè) CPU 上對(duì)不同數(shù)據(jù)的先后改動(dòng)，在另一個(gè) CPU 上觀察到的結(jié)果中砂蔽，兩個(gè)數(shù)據(jù)的先后變動(dòng)順序不能改變洼怔。通常只有高性能編程才會(huì)涉及，比如內(nèi)核和 SPDK左驾，普通編程場景使用的“鎖”也能解決 order 問題镣隶，但和 memory barrier比起來性能開銷太大极谊。
編譯器優(yōu)化、CPU 亂序機(jī)制也會(huì)導(dǎo)致 order 問題安岂，但本文討論范圍并不包括這兩個(gè)因素轻猖，僅討論 cache 原生帶來的 order 問題。當(dāng)然 memory barrier 解決的 order 問題既包括 cache 原生帶來的嗜闻，也包括編譯器和 CPU 亂序帶來的蜕依。
細(xì)節(jié)
一、cache 及問題由來
CPU 速度遠(yuǎn)高于 memory琉雳，為了提升效率引入了 Cache样眠。
二、緩存一致性協(xié)議
本來在沒有 Cache 的情況下可以依靠內(nèi)存總線確保數(shù)據(jù)在不同 CPU 上的一致性翠肘，但引入 Cache 后則出現(xiàn)了數(shù)據(jù)一致性問題：即同一時(shí)刻不同 CPU 看到的數(shù)據(jù)可能不一致檐束。為解決這個(gè)問題引入了cache-coherence protocol，即給每個(gè) cache 數(shù)據(jù)增加狀態(tài)信息束倍，CPU 之間通過發(fā)消息來驅(qū)動(dòng)狀態(tài)變更被丧，某個(gè)讀寫請求只有在Cache 處于特定狀態(tài)下才能執(zhí)行。
以一個(gè) 4 狀態(tài)的一致性協(xié)議舉例绪妹。MESI state：分別代表 Modified甥桂，Exclusive，Shared邮旷，Invalid 四種狀態(tài)黄选。當(dāng) CPU0 需要讀某個(gè)數(shù)據(jù)時(shí)，如果數(shù)據(jù)在 cache 中且是Shared 狀態(tài)婶肩，則可以直接讀取 cache 中的數(shù)據(jù)办陷；如果是 Invalid 狀態(tài)，則需要發(fā)送一個(gè) read 消息到其他 CPU律歼，假設(shè) CPU1 占有該數(shù)據(jù)民镜，且處于 Modified 狀態(tài)，說明數(shù)據(jù)有修改险毁，需要先刷回主存制圈，再將狀態(tài)轉(zhuǎn)為 shared，并回一個(gè) ACK 消息畔况，最終相關(guān)的 CPU 都進(jìn)入 shared 狀態(tài)鲸鹦，CPU0 可以確認(rèn)讀取到的數(shù)據(jù)為最新數(shù)據(jù)。
三问窃、優(yōu)化
1. store buffer
一致性協(xié)議雖然解決了一致性問題亥鬓，但顯然通過消息傳遞機(jī)制仍會(huì)有性能損失。比如 CPU0 要對(duì)變量 a 賦值域庇，需要先將 CPU1 的 cache invalidate嵌戈，在 CPU1 返回 ACK 前只能等待覆积。
為解決等待帶來的性能問題，在 CPU 和 Cache 之間又加了一層 buffer熟呛，在對(duì)端回應(yīng)前可以先寫入 buffer宽档，而不是阻塞等待。
// 加入 store buffer 后庵朝，對(duì) a 的賦值直接寫入 store buffer吗冤，不再阻塞后續(xù)對(duì) b 的操作
a = 1;
b = 1;
2. write barrier
但隨之而來的問題是數(shù)據(jù)的順序依賴問題。比如這段代碼：
// 初始 a==0, b==0九府，a 在 CPU1 cache 中椎瘟，b 在 CPU0 cache 中
// cpu0 執(zhí)行
void func1() {
a = 1;
b = 1;
}
// cpu1 執(zhí)行
void func2() {
while(b==0) continue;
assert(a==1);
}
CPU0 會(huì)先向 CPU1 發(fā)送 Invalidate 請求CPU1 放棄 a 的 cache，但在收到 ACK 前可以先將改動(dòng)寫入自己的 buffer侄旬，然后繼續(xù)修改 b 并寫入 cache（因?yàn)楠?dú)占 b肺蔚，所以不用寫到 buffer）。CPU1 得到 b 的新值后儡羔，開始通過一致性協(xié)議讀取 a宣羊，此時(shí) a 在 CPU0 的 cache 中，值為 0汰蜘，因此 CPU1 得到的值也為 0仇冯。
造成這個(gè)問題的原因是數(shù)據(jù)間有依賴，且因 store buffer 的引入族操， 后寫的數(shù)據(jù)已經(jīng)在 cache 中苛坚，但先寫的數(shù)據(jù)還沒刷到 cache。解決這個(gè)問題有兩種辦法：
- 當(dāng) buffer 非空時(shí)坪创，所有后續(xù)寫入均寫入 buffer炕婶。這樣就能避免其他 CPU 通過 cache 先獲得后修改的數(shù)據(jù)姐赡。
- 在執(zhí)行賦值前將 buffer 刷回 cache莱预。這樣雖然也要等待，但只有連續(xù)寫入才會(huì)有等待涡尘，而其他場景則仍有store buffer 的優(yōu)化效果上炎。
系統(tǒng)層面則提供了 smp_wmb() 調(diào)用便监，效果就是下刷當(dāng)前 store buffer。修改后的正確代碼如下：
void func1() {
a = 1;
smp_wmb();
b = 1;
}
// cpu1 執(zhí)行
void func2() {
while(b==0) continue;
assert(a==1);
}
3. read barrier
現(xiàn)在重新考慮下引入 store buffer 的初衷：等待 invalidate 返回時(shí)間太長危喉。既然這樣，也可以從加快 invalidate 返回入手州疾。
為加快對(duì) invalidate 消息的處理辜限，引入了 Invalidate queue，作用就是當(dāng) cpu 收到 invalidate 消息后严蓖，先放到隊(duì)列薄嫡，立刻返回一個(gè) ACK氧急，CPU 后續(xù)再逐個(gè)處理隊(duì)列中的消息。
但這個(gè)改動(dòng)對(duì)下面的代碼將帶來錯(cuò)誤：
void func1() {
a = 1;
smp_wmb();
b = 1;
}
// cpu1 執(zhí)行
void func2() {
while(b==0) continue;
assert(a==1);
}
原因是由于 invalidate queue 的引入毫深，CPU1 對(duì) a 的 invalidate 可能滯后于對(duì) b 的加載吩坝，如果執(zhí)行 assert 時(shí)仍未完成對(duì) a 的 invalidate，則會(huì)認(rèn)為命中 cache哑蔫，而此時(shí) CPU1 中關(guān)于a 的 cache 是舊值钉寝。
解決辦法便是引入 read barrier，系統(tǒng)接口為smp_rmb()闸迷，正確代碼如下：
void func1() {
a = 1;
smp_wmb();
b = 1;
}
// cpu1 執(zhí)行
void func2() {
while(b==0) continue;
smp_rmb();
assert(a==1);
}
read barrier 起作用的方式便是強(qiáng)制等待處理完 invalidate queue嵌纲。
4. 其他
上述的smp_wmb()和smp_rmb()還有一個(gè)合并版本：smp_mb()，即同時(shí)保證 read order 和 write order腥沽。除了這個(gè)最常見的接口疹瘦，每個(gè)系統(tǒng)還有其他版本的優(yōu)化，具體可以參考內(nèi)核文檔巡球，此處不展開言沐。
總結(jié)
關(guān)于 memory barrier 的產(chǎn)生以及整個(gè)過程解決的問題描述如下：
參考資料
- LKMM : 內(nèi)核代碼中的文檔，非常貼心地按照難易程度進(jìn)行了劃分酣栈。當(dāng)然讀起來也會(huì)比較吃力险胰。
- Memory Barriers: a Hardware View for Software Hackers。強(qiáng)烈推薦的一篇論文矿筝，難度比內(nèi)核文檔低起便，看完后再去看內(nèi)核文檔阻力會(huì)小很多。
