簡介

之前在看volatile 可見性的時(shí)候，經(jīng)常會看到內(nèi)存屏障，但是對于其基本原理似懂非懂，也對于內(nèi)存屏障是如何保障多個(gè)CPU之間的數(shù)據(jù)可見性保持好奇，網(wǎng)上的博客基本上只是停留于表面，導(dǎo)致我產(chǎn)生了幾個(gè)誤區(qū)：
1. CPU之間內(nèi)存數(shù)據(jù)可見性問題是由于cpu cache沒及時(shí)同步數(shù)據(jù)導(dǎo)致的。
2. 內(nèi)存屏障為啥能通過防止指令重排序，就能讓cpu cache及時(shí)同步數(shù)據(jù)？
不過最近發(fā)現(xiàn)這只是表面現(xiàn)象！所以今天寫一下這篇文章來徹底介紹一下內(nèi)存屏障

CPU cache

雖然內(nèi)存可見性問題不是直接由cpu cache導(dǎo)致的，還是與cpu cache是有密切聯(lián)系的，所以我們先來簡單介紹一下cpu cache。
在我之前的文章中有提到內(nèi)核對于小塊內(nèi)存是通過slab來管理的，slab將內(nèi)存劃分為小塊，每一塊為2的一個(gè)指數(shù)級，而這個(gè)內(nèi)存塊是與cpu cacheline一一對應(yīng)的，cacheline的大小在一個(gè)16字節(jié)到256字節(jié)的范圍，通過一些緩存失效機(jī)制來進(jìn)行替換，比如FIFO，LRU之類的。

cpu cache

內(nèi)核其實(shí)是有機(jī)制保證CPU之間數(shù)據(jù)一致性的，我們稱這種緩存一致性協(xié)議為MESI 狀態(tài)機(jī)。
MESI是一個(gè)比較啰嗦的機(jī)制，其主要作用就是通過四種狀態(tài)之間的切換來保證同一數(shù)據(jù)在不同CPU中的一致性，這和內(nèi)存屏障其實(shí)關(guān)系不大，所以我下面只做簡單介紹，如果有興趣詳細(xì)了解的，見文章最后的參考資料。
M即"modify"，表示一個(gè)CPU line獨(dú)占當(dāng)前變量數(shù)據(jù)，且該變量未同步回memory，所以更新該變量時(shí)需要同步回內(nèi)存，或轉(zhuǎn)發(fā)給其他cpu。
E即"exclusive"，它和modify的唯一區(qū)別是，已經(jīng)同步回memory，因而可以直接操作該line(讀寫)，而不需要和其他cpu或者memory進(jìn)行其他交互。
S即"share"，表示該line至少被一個(gè)cpu共享著，如果需要操作該line需要通知其他也共享該line的cpu。
I即"invalid"，表示空line或者無效line。

MESI state diagram

Read response: 返回?cái)?shù)據(jù)
Invalidate: 將一個(gè)指定cache line物理地址標(biāo)記為無效，所有相關(guān)CPU都要刪除對應(yīng)的cache line
Invalidate response: 收到invalidate消息的cpu要返回確認(rèn)。
Read Invalidate: 原子性的發(fā)送 Read + Invalidate
Writeback: 將指定cache line中的數(shù)據(jù)寫回memory
CPU通過MESI中一套嚴(yán)密的事務(wù)操作來保障操作同一變量，在各個(gè)CPU中都是一致的。這里狀態(tài)切換，特別繁雜，就不一一介紹了，就舉一個(gè)簡單列子來說明一下兩個(gè)CPU中是如何保障操作同一變量的一致性吧：
有如下三條指令

1 a=1;
2 b=a+1;
3 assert(b == 2);

其中a存在cpu1的cache中，b存在cpu0的cache中，現(xiàn)在在cpu0中執(zhí)行上述指令：
那么操作過程為：

1. cpu 0 發(fā)現(xiàn)a不在緩存中，且自己需要read-modify-write，所以就會發(fā)起一個(gè)Read Invalidate message，cpu1將a對應(yīng)的cpu line置為無效，并返回ack。
2. cpu 0 等待 Invalidate ACK，直至收到ACK后，才執(zhí)行后續(xù)指令
3. b就在cpu 0的cache line中，所以直接操作讓b = 2；
4. 指令3assert成功。
5. 如果cpu1上的進(jìn)程如果讀a的話，會向cpu0發(fā)送read請求

如果按照上面的邏輯走的話，即使沒有mb(memory barrier)，也不會有任何問題。但是有經(jīng)驗(yàn)的同學(xué)會發(fā)現(xiàn)在步驟2中，必須要等待CPU1返回ACK后才能執(zhí)行后續(xù)的指令，非常低效，因此CPU 引入了store buffer的機(jī)制，來提高CPU性能。

Unnecessary Stall

store buffer

在上述的例子中，可以發(fā)現(xiàn)CPU 0 其實(shí)并不依賴其他CPU中a的值，所以完全可以不用等待ack也能保障CPU 0中指令的執(zhí)行正確性，通過把a(bǔ)的值存入store buffer就可以接著跑后續(xù)的指令了，性能大大提升。
但是這種有些特殊場景卻無法涵蓋，比如上述指令中對于變量a，Read Invalidate調(diào)用會將CPU 0 的cache line置為0(從CPU1讀過來的)，而store buffer中的值為1，如果CPU只拿cache line中的值的話，會有一致性問題，所以store buffer還需要與store forwarding機(jī)制一起合作。也就是如果store buffer中有值，就從store buffer中拿。

Store Forwarding

memory barrier

引入了store buffer 及 store forwarding 后看上去解決了cpu cache一致性問題，且性能大大提升，但是這僅僅保證了當(dāng)前CPU的指令正確性。我們來看另外一個(gè)例子：

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 }

在CPU 0中執(zhí)行foo，CPU 1中執(zhí)行bar，a在CPU 1的緩存中， b 在CPU 0的緩存中，執(zhí)行序列如下：

1. CPU0 執(zhí)行 a=1，將a的值存入store buffer，發(fā)現(xiàn)a不在緩存中，所以向發(fā)送Read Invalidate message。
2. CPU1 執(zhí)行while (b == 0) continue;，b不在CPU1cache中，發(fā)送Read message。
3. CPU0 執(zhí)行 b=1，b owned by itself，所以直接更新。
4. CPU0 接收到b的read請求后，將更新過后的值發(fā)給CPU1。
5. CPU1 將b的值更新到自己的緩存
6. CPU1 執(zhí)行while (b == 0) continue;中b的值變?yōu)?，可以跳出該循環(huán)了。
7. CPU1 執(zhí)行assert(a == 1);，此時(shí)CPU1中的a值可能尚未被置為無效，所以直接從cache中拿出來其，值為0，導(dǎo)致assert failed。
   從上可以看出，如果Read Invalidate message未被執(zhí)行完時(shí)，會讓兩個(gè)CPU中對于同一值出現(xiàn)不一致的情況。按正常邏輯來說b已經(jīng)更新為1了，a不可能還是0。
   單從硬件方面來說，目前沒有很好的機(jī)制來解決這一類問題，所以就引入了memory barrier 指令來防止CPU cache中的這種store buffer帶來的不一致性問題。但是mb相比于原始的unnecessary stall機(jī)制還是有優(yōu)化的，就是當(dāng)遇到memory barrier 指令時(shí)，將store buffer中的已有的所有變量做標(biāo)記，后續(xù)的write操作，必須要等buffer中所有被標(biāo)記數(shù)據(jù)清空后，才將未做標(biāo)記的數(shù)據(jù)更新到cache。我們將上述例子改寫如下：

1 void foo(void) 
2{
3 a=1;
4 smp_mb();
5 b=1;
6 }
7
8 void bar(void)
9{
10 while (b == 0) continue;
11 assert(a == 1);
12 }

那么CPU0執(zhí)行完a=1后，將其寫入store buffer，執(zhí)行到smp_mb后將store buffer中的所有變量標(biāo)記，執(zhí)行到b=1時(shí)，寫入store buffer后不做標(biāo)記，且不寫回cache line，在收到CPU1的請求后將b的cache line 標(biāo)記為shared，當(dāng)CPU0收到CPU1對于a的Invalidate ACK后，將a更新回cache line并將其置為modified，且清除store buffer中a的值，所以CPU0中store buffer沒有被標(biāo)記的數(shù)據(jù)了，剩余的b就可以更新會cache了，此時(shí)其是share狀態(tài)所以其更新會向其share CPU發(fā)送Invalidate message，CPU1接收到message后重新Read，將b置一繼續(xù)后面的邏輯，這樣assert就是沒問題的了。

Store Sequence Capacity

有了上續(xù)機(jī)制后，可以通過mb來禁止指令讀取亂序后，解決了數(shù)據(jù)CPU間的一致性問題，但是又帶了另外一個(gè)問題，store buffer的容量是很小的，如果等待的Invalidate指令遲遲不返回，那么store buffer就會被填滿，而無法繼續(xù)執(zhí)行后續(xù)指令。
所以就需要一些機(jī)制來加速Invalidate message的執(zhí)行，便引入了Invalidate Queue，這是因?yàn)镮nvalidate message執(zhí)行慢的主要原因是需要確保對應(yīng)的cache line確實(shí)是無效的，但是這個(gè)驗(yàn)證工作有時(shí)候會因?yàn)镃PU過忙而推遲。所以有了Invalidate Queue后可以不做有效性驗(yàn)證，直接ACK，后續(xù)有空了再驗(yàn)證清除對應(yīng)的cache line，這樣就不會stalling 其他 CPU了。但這又產(chǎn)生了另外一個(gè)問題，要確保當(dāng)前CPU中讀取某一個(gè)值時(shí)，其是否在Invalidate Queue中，否則就會讀到無效的數(shù)據(jù)。比如上述例子中的a如果只存在CPU1的Invalidate Queue中，卻未被真正的清除，那么bar還是assert 失敗(a == 0)的，具體過程可以自己推到。

Invalidate Queues and Memory Barriers

所以我們需要另外一種機(jī)制確保讀某一個(gè)值時(shí)，其不能存在于Invalidate Queues中，所以硬件開發(fā)者又提供了一種方式來解決該問題，這種機(jī)制還是基于mb 指令，但是這次帶來了一個(gè)新的限制，當(dāng)遇到mb時(shí)將Invalidate Queues中的所有變量做標(biāo)記，后續(xù)有讀指令時(shí)，必須要等所有被標(biāo)記的Invalidate Queues的數(shù)據(jù)被處理完后才能繼續(xù)執(zhí)行。因此我們可以將上述代碼修改如下：

1 void foo(void) 
2{
3 a=1;
4 smp_mb();
5 b=1;
6}
7
8 void bar(void) 
9{
10 while (b == 0) continue;
11 smp_mb();
12 assert(a == 1);
13 }

至此就可以保障變量a在CPU0 和 CPU1中的完全一致可見性了。

后記

由此可見，CPU之間的變量可見性不是直接由于CPU cache，也不是由于指令亂序，而是由于CPU Cache-Coherence Protocols性能優(yōu)化中store buffer帶來的數(shù)據(jù)不一致性問題帶來的的cache不一致性問題，而內(nèi)存屏障也不是用來禁止指令亂序，而是解決由于數(shù)據(jù)只更新到了store buffer卻沒有更新回cache以及Invalidate不同步問題。

參考資料
whymb