?

There are only two hard things in Computer Science: cache invalidation and naming things.

-- Phil Karlton

全文目錄

CACHE基礎(chǔ)

CACHE的組織

????? TAG,INDEX

????? VIVT,VIPT,PIPT

????? Cache別名問題

CACHE一致性

????? icache、dcache同步

????? 多CPU核cache同步

????? CPU與設(shè)備cache同步

意識到CACHE的編程

????? perf中的cache統(tǒng)計

????? cache的false sharing

????? cache miss與低IPC關(guān)系

CACHE基礎(chǔ)

對cache的掌握，對于Linux工程師（其他的非Linux工程師也一樣）寫出高效能代碼，以及優(yōu)化Linux系統(tǒng)的性能是至關(guān)重要的。簡單來說，cache快，內(nèi)存慢，硬盤更慢。在一個典型的現(xiàn)代CPU中比較接近改進(jìn)的哈佛結(jié)構(gòu)，cache的排布大概是這樣的：

L1速度>? L2速度> L3速度> RAM

L1容量<? L2容量< L3容量< RAM

現(xiàn)代CPU，通常L1 cache的指令和數(shù)據(jù)是分離的。這樣可以實(shí)現(xiàn)2條高速公路并行訪問，CPU可以同時load指令和數(shù)據(jù)。當(dāng)然，cache也不一定是一個core獨(dú)享，現(xiàn)代很多CPU的典型分布是這樣的，比如多個core共享一個L3。比如這臺的Linux里面運(yùn)行l(wèi)stopo命令：

人們也常常稱呼L2cache為MLC（MiddleLevel Cache）,L3cache為LLC（Last LevelCache）。這些Cache究竟有多塊呢？我們來看看Intel的數(shù)據(jù)，具體配置：Intel i7-4770 (Haswell), 3.4 GHz (Turbo Boostoff), 22 nm. RAM: 32 GB (PC3-12800 cl11 cr2)

訪問延遲：

數(shù)據(jù)來源：https://www.7-cpu.com/cpu/Haswell.html

由此我們可以知道，我們應(yīng)該盡可能追求cache的命中率高，以避免延遲，最好是低級cache的命中率越高越好。

CACHE的組織

現(xiàn)代的cache基本按照這個模式來組織：SET、WAY、TAG、INDEX，這幾個概念是理解Cache的關(guān)鍵。隨便打開一個數(shù)據(jù)手冊，就可以看到這樣的字眼：

翻譯成中文就是4路（way）組（set）相聯(lián)，VIPT表現(xiàn)為(behave as)PIPT --這尼瑪什么鬼？，cacheline的長度是64字節(jié)。

下面我們來想象一個16KB大小的cache，假設(shè)是4路組相聯(lián)，cacheline的長度是64字節(jié)。Cacheline的概念比較簡單，cache的整個替換是以行為單位的，一行64個字節(jié)里面讀了任何一個字節(jié)，其實(shí)整個64字節(jié)就進(jìn)入了cache。

比如下面兩段程序，前者的計算量是后者的8倍：

但是它的執(zhí)行時間，則遠(yuǎn)遠(yuǎn)不到后者的8倍：

16KB的cache是4way的話，每個set包括4*64B，則整個cache分為16KB/64B/4 = 64set，也即2的6次方。當(dāng)CPU從cache里面讀數(shù)據(jù)的時候，它會用地址位的BIT6-BIT11來尋址set，BIT0-BIT5是cacheline內(nèi)的offset。

比如CPU訪問地址

0 000000 XXXXXX

或者

1 000000 XXXXXX

或者

YYYY 000000 XXXXXX

由于它們紅色的6位都相同，所以他們?nèi)慷紩业降?個set的cacheline。第0個set里面有4個way，之后硬件會用地址的高位如0,1，YYYY作為tag，去檢索這4個way的tag是否與地址的高位相同，而且cacheline是否有效，如果tag匹配且cacheline有效，則cache命中。

所以地址YYYYYY000000XXXXXX全部都是找第0個set，YYYYYY000001XXXXXX全部都是找第1個set，YYYYYY111111XXXXXX全部都是找第63個set。每個set中的4個way，都有可能命中。

中間紅色的位就是INDEX，前面YYYY這些位就是TAG。具體的實(shí)現(xiàn)可以是用虛擬地址或者物理地址的相應(yīng)位做TAG或者INDEX。如果用虛擬地址做TAG，我們叫VT；如果用物理地址做TAG，我們叫PT；如果用虛擬地址做INDEX，我們叫VI；如果用物理地址做TAG，我們叫PT。工程中碰到的cache可能有這么些組合：

VIVT、VIPT、PIPT。

VIVT的硬件實(shí)現(xiàn)開銷最低，但是軟件維護(hù)成本高；PIPT的硬件實(shí)現(xiàn)開銷最高，但是軟件維護(hù)成本最低；VIPT介于二者之間，但是有些硬件是VIPT，但是behave as PIPT，這樣對軟件而言，維護(hù)成本與PIPT一樣。

在VIVT的情況下，CPU發(fā)出的虛擬地址，不需要經(jīng)過MMU的轉(zhuǎn)化，直接就可以去查cache。

而在VIPT和PIPT的場景下，都涉及到虛擬地址轉(zhuǎn)換為物理地址后，再去比對cache的過程。VIPT如下：

PIPT如下：

從圖上看起來，VIVT的硬件實(shí)現(xiàn)效率很高，不需要經(jīng)過MMU就可以去查cache了。不過，對軟件來說，這是個災(zāi)難。因為VIVT有嚴(yán)重的歧義和別名問題。

歧義：一個虛擬地址先后指向兩個（或者多個）物理地址

別名：兩個（或者多個）虛擬地址同時指向一個物理地址

這里我們重點(diǎn)看別名問題。比如2個虛擬地址對應(yīng)同一個物理地址，基于VIVT的邏輯，無論是INDEX還是TAG，2個虛擬地址都是可能不一樣的(盡管他們的物理地址一樣，但是物理地址在cache比對中完全不摻和)，這樣它們完全可能在2個cacheline同時命中。

由于2個虛擬地址指向1個物理地址，這樣CPU寫過第一個虛擬地址后，寫入cacheline1。CPU讀第2個虛擬地址，讀到的是過時的cacheline2，這樣就出現(xiàn)了不一致。所以，為了避免這種情況，軟件必須寫完虛擬地址1后，對虛擬地址1對應(yīng)的cache執(zhí)行clean，對虛擬地址2對應(yīng)的cache執(zhí)行invalidate。

而PIPT完全沒有這樣的問題，因為無論多少虛擬地址對應(yīng)一個物理地址，由于物理地址一樣，我們是基于物理地址去尋找和比對cache的，所以不可能出現(xiàn)這種別名問題。

那么VIPT有沒有可能出現(xiàn)別名呢？答案是有可能，也有可能不能。如果VI恰好對于PI，就不可能，這個時候，VIPT對軟件而言就是PIPT了：

VI=PI

PT=PT

那么什么時候VI會等于PI呢？這個時候我們來回憶下虛擬地址往物理地址的轉(zhuǎn)換過程，它是以頁為單位的。假設(shè)一頁是4K，那么地址的低12位虛擬地址和物理地址是完全一樣的。回憶我們前面的地址：

YYYYY000000XXXXXX

其中紅色的000000是INDEX。在我們的例子中，紅色的6位和后面的XXXXXX（cache內(nèi)部偏移）加起來正好12位，所以這個000000經(jīng)過虛實(shí)轉(zhuǎn)換后，其實(shí)還是000000的，這個時候VI=PI，VIPT沒有別名問題。

我們原先假設(shè)的cache是：16KB大小的cache，假設(shè)是4路組相聯(lián)，cacheline的長度是64字節(jié)，這樣我們正好需要紅色的6位來作為INDEX。但是如果我們把cache的大小增加為32KB，這樣我們需要 ?32KB/4/64B=128=2^7，也即7位來做INDEX。

YYYY0000000XXXXXX

這樣VI就可能不等于PI了，因為紅色的最高位超過了2^12的范圍，完全可能出現(xiàn)如下2個虛擬地址，指向同一個物理地址：

這樣就出現(xiàn)了別名問題，我們在工程里，可能可以通過一些辦法避免這種別名問題，比如軟件在建立虛實(shí)轉(zhuǎn)換的時候，把虛實(shí)轉(zhuǎn)換往2^13而不是2^12對齊，讓物理地址的低13位而不是低12位與物理地址相同，這樣強(qiáng)行繞開別名問題，下圖中，2個虛擬地址指向了同一個物理地址，但是它們的INDEX是相同的，這樣VI=PI，就繞開了別名問題。這通常是PAGE COLOURING技術(shù)中的一種技巧。

如果這種PAGE COLOURING的限制對軟件仍然不可接受，而我們又想享受VIPT的INDEX不需要經(jīng)過MMU虛實(shí)轉(zhuǎn)換的快捷？有沒有什么硬件技術(shù)來解決VIPT別名問題呢？確實(shí)是存在的，現(xiàn)代CPU很多都是把L1 CACHE做成VIPT，但是表現(xiàn)地（behave as）像PIPT。這是怎么做到的呢？

這要求VIPT的cache，硬件上具備alias detection的能力。比如，硬件知道YYYY0000000XXXXXX既有可能出現(xiàn)在第0000000，又可能出現(xiàn)在1000000這2個set，然后硬件自動去比對這2個set里面是否出現(xiàn)映射到相同物理地址的cacheline，并從硬件上解決好別名同步，那么軟件就完全不用操心了。

下面我們記住一個簡單的規(guī)則：

對于VIPT，如果cache的size除以WAY數(shù)，小于等于1個page的大小，則天然VI=PI，無別名問題；

對于VIPT，如果cache的size除以WAY數(shù)，大于1個page的大小，則天然VI≠PI，有別名問題；這個時候又分成2種情況:

• 硬件不具備alias detection能力，軟件需要pagecolouring；

• 硬件具備alias detection能力，軟件把cache當(dāng)成PIPT用。

比如cache大小64KB，4WAY，PAGE SIZE是4K，顯然有別名問題；這個時候，如果cache改為16WAY，或者PAGE SIZE改為16K，不再有別名問題。為什么？感覺小學(xué)數(shù)學(xué)知識也能算得清????

CACHE的一致性

Cache的一致性有這么幾個層面

1.?????一個CPU的icache和dcache的同步問題

2.?????多個CPU各自的cache同步問題

3.?????CPU與設(shè)備（其實(shí)也可能是個異構(gòu)處理器，不過在Linux運(yùn)行的CPU眼里，都是設(shè)備，都是DMA）的cache同步問題

先看一下ICACHE和DCACHE同步問題。由于程序的運(yùn)行而言，指令流的都流過icache，而指令中涉及到的數(shù)據(jù)流經(jīng)過dcache。所以對于自修改的代碼（Self-Modifying Code）而言，比如我們修改了內(nèi)存p這個位置的代碼（典型多見于JIT compiler），這個時候我們是通過store的方式去寫的p，所以新的指令會進(jìn)入dcache。但是我們接下來去執(zhí)行p位置的指令的時候，icache里面可能命中的是修改之前的指令。

所以這個時候軟件需要把dcache的東西clean出去，然后讓icache invalidate，這個開銷顯然還是比較大的。

但是，比如ARM64的N1處理器，它支持硬件的icache同步，詳見文檔：The Arm Neoverse N1 Platform: Building Blocks for the Next-Gen Cloud-to-Edge Infrastructure SoC

特別注意畫紅色的幾行。軟件維護(hù)的成本實(shí)際很高，還涉及到icache的invalidation向所有核廣播的動作。

接下來的一個問題就是多個核之間的cache同步。下面是一個簡化版的處理器，CPU_A和B共享了一個L3，CPU_C和CPU_D共享了一個L3。實(shí)際的硬件架構(gòu)由于涉及到NUMA，會比這個更加復(fù)雜，但是這個圖反映層級關(guān)系是足夠了。

比如CPU_A讀了一個地址p的變量？CPU_B、C、D又讀，難道B,C,D又必須從RAM里面經(jīng)過L3,L2,L1再讀一遍嗎？這個顯然是沒有必要的，在硬件上，cache的snooping控制單元，可以協(xié)助直接把CPU_A的p地址cache拷貝到CPU_B、C和D的cache。

這樣A-B-C-D都得到了相同的p地址的棕色小球。

假設(shè)CPU B這個時候，把棕色小球?qū)懗杉t色，而其他CPU里面還是棕色，這樣就會不一致了：

這個時候怎么辦？這里面顯然需要一個協(xié)議，典型的多核cache同步協(xié)議有MESI和MOESI。MOESI相對MESI有些細(xì)微的差異，不影響對全局的理解。下面我們重點(diǎn)看MESI協(xié)議。

MESI協(xié)議定義了4種狀態(tài)：

M（Modified）: 當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)已被修改而且與內(nèi)存中的數(shù)據(jù)不一致，數(shù)據(jù)只在當(dāng)前cache里存在；類似RAM里面是棕色球，B里面是紅色球（CACHE與RAM不一致），A、C、D都沒有球。

E（Exclusive）：當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)與內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)只在當(dāng)前cache里存在；類似RAM里面是棕色球，B里面是棕色球（RAM和CACHE一致），A、C、D都沒有球。

S（Shared）：當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)與內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)在多個cache里存在。類似如下圖，在CPU A-B-C里面cache的棕色球都與RAM一致。

I（Invalid）：?? 當(dāng)前cache無效。前面三幅圖里面cache沒有球的那些都是屬于這個情況。

然后它有個狀態(tài)機(jī)

這個狀態(tài)機(jī)比較難記，死記硬背是記不住的，也沒必要記，它講的cache原先的狀態(tài)，經(jīng)過一個硬件在本cache或者其他cache的讀寫操作后，各個cache的狀態(tài)會如何變遷。所以，硬件上不僅僅是監(jiān)控本CPU的cache讀寫行為，還會監(jiān)控其他CPU的。只需要記住一點(diǎn)：這個狀態(tài)機(jī)是為了保證多核之間cache的一致性，比如一個干凈的數(shù)據(jù)，可以在多個CPU的cache share，這個沒有一致性問題；但是，假設(shè)其中一個CPU寫過了，比如A-B-C本來是這樣：

然后B被寫過了：

這樣A、C的cache實(shí)際是過時的數(shù)據(jù)，這是不允許的。這個時候，硬件會自動把A、C的cache invalidate掉，不需要軟件的干預(yù)，A、C其實(shí)變地相當(dāng)于不命中這個球了：

這個時候，你可能會繼續(xù)問，如果C要讀這個球呢？它目前的狀態(tài)在B里面是modified的，而且與RAM不一致，這個時候，硬件會把紅球clean，然后B、C、RAM變地一致，B、C的狀態(tài)都變化為S（Shared）：

這一系列的動作雖然由硬件完成，但是對軟件而言不是免費(fèi)的，因為它耗費(fèi)了時間。如果編程的時候不注意，引起了硬件的大量cache同步行為，則程序的效率可能會急劇下降。

為了讓大家直觀感受到這個cache同步的開銷，下面我們寫一個程序，這個程序有2個線程，一個寫變量，一個讀變量：

這個程序里，x和y都是cacheline對齊的，這個程序的thread1的寫，會不停地與thread2的讀，進(jìn)行cache同步。

它的執(zhí)行時間為：

$ time ./a.out real 0m3.614s user 0m7.021s sys??0m0.004s

它在2個CPU上的userspace共運(yùn)行了7.021秒，累計這個程序從開始到結(jié)束的對應(yīng)真實(shí)世界的時間是3.614秒（就是從命令開始到命令結(jié)束的時間）。

如果我們把程序改一句話，把thread2里面的c = x改為c = y，這樣2個線程在2個CPU運(yùn)行的時候，讀寫的是不同的cacheline，就沒有這個硬件的cache同步開銷了：

它的運(yùn)行時間：

$ time ./b.out real 0m1.820s user 0m3.606s sys??0m0.008s

現(xiàn)在只需要1.8秒，幾乎減小了一半。

感覺前面那個a.out，雙核的幫助甚至都不大。如果我們改為單核跑呢？

$ time taskset -c 0 ./a.out real 0m3.299s user 0m3.297s sys??0m0.000s

它單核跑，居然只需要3.299秒跑完，而雙核跑，需要3.614s跑完。單核跑完這個程序，甚至比雙核還快，有沒有驚掉下巴？！！！因為單核里面沒有cache同步的開銷。

下一個cache同步的重大問題，就是設(shè)備與CPU之間。如果設(shè)備感知不到CPU的cache的話（下圖中的紅色數(shù)據(jù)流向不經(jīng)過cache），這樣，做DMA前后，CPU就需要進(jìn)行相關(guān)的cacheclean和invalidate的動作，軟件的開銷會比較大。

這些軟件的動作，若我們在Linux編程的時候，使用的是streaming DMA APIs的話，都會被類似這樣的API自動搞定：

dma_map_single() dma_unmap_single() dma_sync_single_for_cpu() dma_sync_single_for_device() dma_sync_sg_for_cpu() dma_sync_sg_for_device()

如果是使用的dma_alloc_coherent() API呢，則設(shè)備和CPU之間的buffer是cache一致的，不需要每次DMA進(jìn)行同步。對于不支持硬件cache一致性的設(shè)備而言，很可能dma_alloc_coherent()會把CPU對那段DMA buffer的訪問設(shè)置為uncachable的。

這些API把底層的硬件差異封裝掉了，如果硬件不支持CPU和設(shè)備的cache同步的話，延時還是比較大的。那么，對于底層硬件而言，更好的實(shí)現(xiàn)方式，應(yīng)該仍然是硬件幫我們來搞定。比如我們需要修改總線協(xié)議，延伸紅線的觸角：

當(dāng)設(shè)備訪問RAM的時候，可以去snoop CPU的cache：

• 如果做內(nèi)存到外設(shè)的DMA，則直接從CPU的cache取modified的數(shù)據(jù)；

• 如果做外設(shè)到內(nèi)存的DMA，則直接把CPU的cache invalidate掉。

這樣，就實(shí)現(xiàn)硬件意義上的cache同步。當(dāng)然，硬件的cache同步，還有一些其他方法，原理上是類似的。注意，這種同步仍然不是免費(fèi)的，它仍然會消耗bus cycles的。實(shí)際上，cache的同步開銷還與距離相關(guān)，可以說距離越遠(yuǎn)，同步開銷越大，比如下圖中A、B的同步開銷比A、C小。

對于一個NUMA服務(wù)器而言，跨NUMA的cache同步開銷顯然是要比NUMA內(nèi)的同步開銷大。

意識到CACHE的編程

通過上一節(jié)的代碼，讀者應(yīng)該意識到了cache的問題不處理好，程序的運(yùn)行性能會急劇下降。所以意識到cache的編程，對程序員是至關(guān)重要的。

#推薦閱讀：

? ??專輯|Linux文章匯總

? ??專輯|程序人生

? ??專輯|C語言

嵌入式Linux

微信掃描二維碼，關(guān)注我的公眾號?

總結(jié)

以上是生活随笔為你收集整理的深入理解cache对写好代码至关重要的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。