為什么需要cache

如果CPU需要將一個變量（假設地址是A）加1，一般分為以下3個步驟：

CPU 從主存中讀取地址A的數據到內部通用寄存器 x0（ARM64架構的通用寄存器之一）

通用寄存器 x0 加1

CPU 將通用寄存器 x0 的值寫入主存

我們將這個過程可以表示如下：

其實現實中，CPU通用寄存器的速度和主存之間存在著太大的差異。兩者之間的速度大致如下關系：

CPU register的速度一般小于1ns，主存的速度一般是65ns左右。速度差異近百倍。在硬件上，我們將cache放置在CPU和主存之間，作為主存數據的緩存。當CPU試圖從主存中load/store數據的時候， CPU會首先從cache中查找對應地址的數據是否緩存在cache 中。如果其數據緩存在cache中，直接從cache中拿到數據并返回給CPU。當存在cache的時候，以上程序如何運行的例子的流程將會變成如下：

CPU和主存之間直接數據傳輸的方式轉變成CPU和cache之間直接數據傳輸。cache負責和主存之間數據傳輸。

多級cache存儲結構

前面提到的cache，稱之為L1 cache（第一級cache）。我們在L1 cache 后面連接L2 cache，在L2 cache 和主存之間連接L3 cache。等級越高，速度越慢，容量越大。但是速度相比較主存而言，依然很快。不同等級cache速度之間關系如下：

經過3級cache的緩沖，各級cache和主存之間的速度最萌差也逐級減小。在一個真實的系統上，各級cache之間硬件上是如何關聯的呢？我們看下Cortex-A53架構上各級cache之間的硬件抽象框圖如下：

在Cortex-A53架構上，L1 cache分為單獨的instruction cache（ICache）和data cache（DCache）。L1 cache是CPU私有的，每個CPU都有一個L1 cache。一個cluster 內的所有CPU共享一個L2 cache，L2 cache不區分指令和數據，都可以緩存。所有cluster之間共享L3 cache。L3 cache通過總線和主存相連。

多級cache之間的配合工作

首先引入兩個名詞概念，命中和缺失。CPU要訪問的數據在cache中有緩存，稱為“命中” (hit)，反之則稱為“缺失” (miss)。多級cache之間是如何配合工作的呢？我們假設現在考慮的系統只有兩級cache。

inclusive cache(某一地址的數據可能存在多級緩存中) 當CPU試圖從某地址load數據時，首先從L1 cache中查詢是否命中，如果命中則把數據返回給CPU 如果L1 cache缺失，則繼續從L2 cache中查找。當L2 cache命中時，數據會返回給L1 cache以及CPU 如果L2 cache也缺失，很不幸，我們需要從主存中load數據，將數據返回給L2 cache、L1 cache及CPU

exclusive cache 這種cache保證某一地址的數據緩存只會存在于多級cache其中一級

直接映射緩存(Direct mapped cache)

我們繼續引入一些cache相關的名詞。cache的大小稱之為cahe size，代表cache可以緩存最大數據的大小。我們將cache平均分成相等的很多塊，每一個塊大小稱之為cache line，其大小是cache line size。例如一個64 Bytes大小的cache。如果我們將64 Bytes平均分成64塊，那么cache line就是1字節，總共64行cache line。如果我們將64 Bytes平均分成8塊，那么cache line就是8字節，總共8行cache line。現在的硬件設計中，一般cache line的大小是4-128 Byts。

這里有一點需要注意，cache line是cache和主存之間數據傳輸的最小單位。什么意思呢？當CPU試圖load一個字節數據的時候，如果cache缺失，那么cache控制器會從主存中一次性的load cache line大小的數據到cache中。例如，cache line大小是8字節。CPU即使讀取一個byte，在cache缺失后，cache會從主存中load 8字節填充整個cache line。

我們假設下面的講解都是針對64 Bytes大小的cache，并且cache line大小是8字節。我們可以類似把這塊cache想想成一個數組，數組總共8個元素，每個元素大小是8字節。就像下圖這樣。

現在我們考慮一個問題，CPU從0x0654地址讀取一個字節，cache控制器是如何判斷數據是否在cache中命中呢？cache大小相對于主存來說，可謂是小巫見大巫。所以cache肯定是只能緩存主存中極小一部分數據。我們如何根據地址在有限大小的cache中查找數據呢？現在硬件采取的做法是對地址進行散列（可以理解成地址取模操作）。我們接下來看看是如何做到的？

我們一共有8行cache line，cache line大小是8 Bytes。所以我們可以利用地址低3 bits（如上圖地址藍色部分）用來尋址8 bytes中某一字節，我們稱這部分bit組合為offset。同理，8行cache line，為了覆蓋所有行。我們需要3 bits（如上圖地址黃色部分）查找某一行，這部分地址部分稱之為index。現在我們知道，如果兩個不同的地址，其地址的bit3-bit5如果完全一樣的話，那么這兩個地址經過硬件散列之后都會找到同一個cache line。所以，當我們找到cache line之后，只代表我們訪問的地址對應的數據可能存在這個cache line中，但是也有可能是其他地址對應的數據。所以，我們又引入tag array區域，tag array和data array一一對應。每一個cache line都對應唯一一個tag，tag中保存的是整個地址位寬去除index和offset使用的bit剩余部分（如上圖地址綠色部分）。tag、index和offset三者組合就可以唯一確定一個地址了。因此，當我們根據地址中index位找到cache line后，取出當前cache line對應的tag，然后和地址中的tag進行比較，如果相等，這說明cache命中。如果不相等，說明當前cache line存儲的是其他地址的數據，這就是cache缺失。

我們可以從圖中看到tag旁邊還有一個valid bit，這個bit用來表示cache line中數據是否有效（例如：1代表有效；0代表無效）。當系統剛啟動時，cache中的數據都應該是無效的，因為還沒有緩存任何數據。cache控制器可以根據valid bit確認當前cache line數據是否有效。所以，上述比較tag確認cache line是否命中之前還會檢查valid bit是否有效。只有在有效的情況下，比較tag才有意義。如果無效，直接判定cache缺失。

上面的例子中，cache size是64 Bytes并且cache line size是8 bytes。offset、index和tag分別使用3 bits、3 bits和42 bits（假設地址寬度是48 bits）。我們現在再看一個例子：512 Bytes cache size，64 Bytes cache line size。根據之前的地址劃分方法，offset、index和tag分別使用6 bits、3 bits和39 bits。如下圖所示。

直接映射緩存的優缺點

直接映射緩存在硬件設計上會更加簡單，因此成本上也會較低。根據直接映射緩存的工作方式，我們可以畫出主存地址0x00-0x88地址對應的cache分布圖。

我們可以看到，地址0x00-0x3f地址處對應的數據可以覆蓋整個cache。0x40-0x7f地址的數據也同樣是覆蓋整個cache。我們現在思考一個問題，如果一個程序試圖依次訪問地址0x00、0x40、0x80，cache中的數據會發生什么呢？首先我們應該明白0x00、0x40、0x80地址中index部分是一樣的。因此，這3個地址對應的cache line是同一個。所以，當我們訪問0x00地址時，cache會缺失，然后數據會從主存中加載到cache中第0行cache line。當我們訪問0x40地址時，依然索引到cache中第0行cache line，由于此時cache line中存儲的是地址0x00地址對應的數據，所以此時依然會cache缺失。然后從主存中加載0x40地址數據到第一行cache line中。同理，繼續訪問0x80地址，依然會cache缺失。這就相當于每次訪問數據都要從主存中讀取，所以cache的存在并沒有對性能有什么提升。訪問0x40地址時，就會把0x00地址緩存的數據替換。這種現象叫做cache顛簸（cache thrashing）。針對這個問題，我們引入多路組相連緩存。我們首先研究下最簡單的兩路組相連緩存的工作原理。

兩路組相連緩存(Two-way set associative cache)

我們依然假設64 Bytes cache size，cache line size是8 Bytes。什么是路（way）的概念。我們將cache平均分成多份，每一份就是一路。因此，兩路組相連緩存就是將cache平均分成2份，每份32 Bytes。如下圖所示。

cache被分成2路，每路包含4行cache line。我們將所有索引一樣的cache line組合在一起稱之為組。例如，上圖中一個組有兩個cache line，總共4個組。我們依然假設從地址0x0654地址讀取一個字節數據。由于cache line size是8 Bytes，因此offset需要3 bits，這和之前直接映射緩存一樣。不一樣的地方是index，在兩路組相連緩存中，index只需要2 bits，因為一路只有4行cache line。上面的例子根據index找到第2行cache line（從0開始計算），第2行對應2個cache line，分別對應way 0和way 1。因此index也可以稱作set index（組索引）。先根據index找到set，然后將組內的所有cache line對應的tag取出來和地址中的tag部分對比，如果其中一個相等就意味著命中。

因此，兩路組相連緩存較直接映射緩存最大的差異就是：第一個地址對應的數據可以對應2個cache line，而直接映射緩存一個地址只對應一個cache line。那么這究竟有什么好處呢？

兩路組相連緩存優缺點

兩路組相連緩存的硬件成本相對于直接映射緩存更高。因為其每次比較tag的時候需要比較多個cache line對應的tag（某些硬件可能還會做并行比較，增加比較速度，這就增加了硬件設計復雜度）。為什么我們還需要兩路組相連緩存呢？因為其可以有助于降低cache顛簸可能性。那么是如何降低的呢？根據兩路組相連緩存的工作方式，我們可以畫出主存地址0x00-0x4f地址對應的cache分布圖。

我們依然考慮直接映射緩存一節的問題“如果一個程序試圖依次訪問地址0x00、0x40、0x80，cache中的數據會發生什么呢？”。現在0x00地址的數據可以被加載到way 1，0x40可以被加載到way 0。這樣是不是就在一定程度上避免了直接映射緩存的尷尬境地呢？在兩路組相連緩存的情況下，0x00和0x40地址的數據都緩存在cache中。試想一下，如果我們是4路組相連緩存，后面繼續訪問0x80，也可能被被緩存。

因此，當cache size一定的情況下，組相連緩存對性能的提升最差情況下也和直接映射緩存一樣，在大部分情況下組相連緩存效果比直接映射緩存好。同時，其降低了cache顛簸的頻率。從某種程度上來說，直接映射緩存是組相連緩存的一種特殊情況，每個組只有一個cache line而已。因此，直接映射緩存也可以稱作單路組相連緩存。

全相連緩存(Full associative cache)

既然組相連緩存那么好，如果所有的cache line都在一個組內。豈不是性能更好。是的，這種緩存就是全相連緩存。我們依然以64 Byts大小cache為例說明。

由于所有的cache line都在一個組內，因此地址中不需要set index部分。因為，只有一個組讓你選擇，間接來說就是你沒得選。我們根據地址中的tag部分和所有的cache line對應的tag進行比較（硬件上可能并行比較也可能串行比較）。哪個tag比較相等，就意味著命中某個cache line。因此，在全相連緩存中，任意地址的數據可以緩存在任意的cache line中。所以，這可以最大程度的降低cache顛簸的頻率。但是硬件成本上也是更高。

Cache分配策略(Cache allocation policy)

cache的分配策略是指我們什么情況下應該為數據分配cache line。cache分配策略分為讀和寫兩種情況。

讀分配(read allocation) 當CPU讀數據時，發生cache缺失，這種情況下都會分配一個cache line緩存從主存讀取的數據。默認情況下，cache都支持讀分配。

寫分配(write allocation) 當CPU寫數據發生cache缺失時，才會考慮寫分配策略。當我們不支持寫分配的情況下，寫指令只會更新主存數據，然后就結束了。當支持寫分配的時候，我們首先從主存中加載數據到cache line中（相當于先做個讀分配動作），然后會更新cache line中的數據。

Cache更新策略(Cache update policy)

cache更新策略是指當發生cache命中時，寫操作應該如何更新數據。cache更新策略分成兩種：寫直通和回寫。

寫直通(write through) 當CPU執行store指令并在cache命中時，我們更新cache中的數據并且更新主存中的數據。cache和主存的數據始終保持一致。

寫回(write back) 當CPU執行store指令并在cache命中時，我們只更新cache中的數據。并且每個cache line中會有一個bit位記錄數據是否被修改過，稱之為dirty bit（翻翻前面的圖片，cache line旁邊有一個D就是dirty bit）。我們會將dirty bit置位。主存中的數據只會在cache line被替換或者顯示的clean操作時更新。因此，主存中的數據可能是未修改的數據，而修改的數據躺在cache中。cache和主存的數據可能不一致。

同時思考個問題，為什么cache line大小是cache控制器和主存之間數據傳輸的最小單位呢？這也是因為每個cache line只有一個dirty bit。這一個dirty bit代表著整個cache line是否被修改的狀態。

Cache組織方式

但是，我們一直避開了一個關鍵問題。我們都知道cache控制器根據地址查找判斷是否命中，這里的地址究竟是虛擬地址(virtual address，VA)還是物理地址(physical address，PA)？

虛擬高速緩存(VIVT)

我們首先介紹的是虛擬高速緩存，這種cache硬件設計簡單。在cache誕生之初，大部分的處理器都使用這種方式。虛擬高速緩存以虛擬地址作為查找對象。如下圖所示。

虛擬地址直接送到cache控制器，如果cache hit。直接從cache中返回數據給CPU。如果cache miss，則把虛擬地址發往MMU，經過MMU轉換成物理地址，根據物理地址從主存(main memory)讀取數據。但是，正是使用了虛擬地址作為tag，所以引入很多軟件使用上的問題。操作系統在管理高速緩存正確工作的過程中，主要會面臨兩個問題。歧義(ambiguity)和別名(alias)。為了保證系統的正確工作，操作系統負責避免出現歧義和別名。

歧義(ambiguity)

歧義是指不同的數據在cache中具有相同的tag和index。cache控制器判斷是否命中cache的依據就是tag和index，因此這種情況下，cache控制器根本沒辦法區分不同的數據。這就產生了歧義。什么情況下發生歧義呢？我們知道不同的物理地址存儲不同的數據，只要相同的虛擬地址映射不同的物理地址就會出現歧義。操作系統如何避免歧義的發生呢？當我們切換進程的時候，可以選擇flush所有的cache。flush cache操作有兩種：- 使主存儲器有效。針對write back高速緩存，首先應該使主存儲器有效，保證已經修改數據的cacheline寫回主存儲器，避免修改的數據丟失。- 使高速緩存無效。保證切換后的進程不會錯誤的命中上一個進程的緩存數據

因此，切換后的進程剛開始執行的時候，將會由于大量的cache miss導致性能損失。所以，VIVT高速緩存明顯的缺點之一就是經常需要flush cache以保證歧義不會發生，最終導致性能的損失。VIVT高速緩存除了面對歧義問題外，還面臨另一個問題：別名(alias)。

別名(alias)

當不同的虛擬地址映射相同的物理地址，而這些虛擬地址的index不同，此時就發生了別名現象(多個虛擬地址被稱為別名)。通俗點來說就是指同一個物理地址的數據被加載到不同的cacheline中就會出現別名現象。

針對共享數據所在頁的映射方式采用nocache映射。例如上面的例子中，0x2000和0x4000映射物理地址0x8000的時候都采用nocache的方式，這樣不通過cache的訪問，肯定可以避免這種問題。但是這樣就損失了cache帶來的性能好處。這種方法既適用于不同進程共享數據，也適用于同一個進程共享數據。如果是不同進程之間共享數據，還可以在進程切換時主動flush cache(使主存儲器有效和使高速緩存無效)的方式避免別名現象。但是，如果是同一個進程共享數據該怎么辦？除了nocache映射之外，還可以有另一種解決方案。這種方法只針對直接映射高速緩存，并且使用了寫分配機制有效。在建立共享數據映射時，保證每次分配的虛擬地址都索引到相同的cacheline。這種方式，后面還會重點說。

物理高速緩存(PIPT)

基于對VIVT高速緩存的認識，我們知道VIVT高速緩存存在歧義和名別兩大問題。主要問題原因是：tag取自虛擬地址導致歧義，index取自虛擬地址導致別名。所以，如果想讓操作系統少操心，最簡單的方法是tag和index都取自物理地址。物理的地址tag部分是獨一無二的，因此肯定不會導致歧義。而針對同一個物理地址，index也是唯一的，因此加載到cache中也是唯一的cacheline，所以也不會存在別名。我們稱這種cache為物理高速緩存，簡稱PIPT(Physically Indexed Physically Tagged)。PIPT工作原理如下圖所示。

CPU發出的虛擬地址經過MMU轉換成物理地址，物理地址發往cache控制器查找確認是否命中cache。雖然PIPT方式在軟件層面基本不需要維護，但是硬件設計上比VIVT復雜很多。因此硬件成本也更高。同時，由于虛擬地址每次都要翻譯成物理地址，因此在查找性能上沒有VIVT方式簡潔高效，畢竟PIPT方式需要等待虛擬地址轉換物理地址完成后才能去查找cache。順便提一下，為了加快MMU翻譯虛擬地址的速度，硬件上也會加入一塊cache，作用是緩存虛擬地址和物理地址的映射關系，這塊cache稱之為TLB(Translation Lookaside Buffer)。當MMU需要轉換虛擬地址時，首先從TLB中查找，如果cache hit，則直接返回物理地址。如果cache miss則需要MMU查找頁表。這樣就加快了虛擬地址轉換物理地址的速度。如果系統采用的PIPT的cache，那么軟件層面基本不需要任何的維護就可以避免歧義和別名問題。這是PIPT最大的優點。現在的CPU很多都是采用PIPT高速緩存設計。在Linux內核中，可以看到針對PIPT高速緩存的管理函數都是空函數，無需任何的管理。

物理標記的虛擬高速緩存(VIPT)

為了提升cache查找性能，我們不想等到虛擬地址轉換物理地址完成后才能查找cache。因此，我們可以使用虛擬地址對應的index位查找cache，與此同時(硬件上同時進行)將虛擬地址發到MMU轉換成物理地址。當MMU轉換完成，同時cache控制器也查找完成，此時比較cacheline對應的tag和物理地址tag域，以此判斷是否命中cache。我們稱這種高速緩存為VIPT(Virtually Indexed Physically Tagged)。

VIPT以物理地址部分位作為tag，因此我們不會存在歧義問題。但是，采用虛擬地址作為index，所以可能依然存在別名問題。是否存在別名問題，需要考慮cache的結構，我們需要分情況考慮。

VIPT Cache為什么不存在歧義

在這里重點介紹下為什么VIPT Cache不存在歧義。假設以32位CPU為例，頁表映射最小單位是4KB。我們假設虛擬地址<12:4>位(這是一個有別名問題的VIPT Cache)作為index，于此同時將虛擬地址<31:12>發送到MMU轉換得到物理地址的<31:12>，這里我們把<31:12>作為tag，并不是<31:13>。這地方很關鍵，也就是說VIPT的tag取決于物理頁大小的剩余位數，而不是去掉index和offset的剩余位數。物理tag是惟一的，所以不存在歧義。

VIPT Cache什么情況不存在別名

我們知道VIPT的優點是查找cache和MMU轉換虛擬地址同時進行，所以性能上有所提升。歧義問題雖然不存在了，但是別名問題依舊可能存在，那么什么情況下別名問題不會存在呢？Linux系統中映射最小的單位是頁，一頁大小是4KB。那么意味著虛擬地址和其映射的物理地址的位<11...0>是一樣的。針對直接映射高速緩存，如果cache的size小于等于4KB，是否就意味著無論使用虛擬地址還是物理地址的低位查找cache結果都是一樣呢？是的，因為虛擬地址和物理地址對應的index是一樣的。這種情況，VIPT實際上相當于PIPT，軟件維護上和PIPT一樣。如果示例是一個四路組相連高速緩存呢？只要滿足一路的cache的大小小于等于4KB，那么也不會出現別名問題。

VIPT Cache的別名問題

假設系統使用的是直接映射高速緩存，cache大小是8KB，cacheline大小是256字節。這種情況下的VIPT就存在別名問題。因為index來自虛擬地址位<12...8>，虛擬地址和物理地址的位<11...8>是一樣的，但是bit12卻不一定相等。假設虛擬地址0x0000和虛擬地址0x1000都映射相同的物理地址0x4000。那么程序讀取0x0000時，系統將會從物理地址0x4000的數據加載到第0x00行cacheline。然后程序讀取0x1000數據，再次把物理地址0x4000的數據加載到第0x10行cacheline。這不，別名出現了。相同物理地址的數據被加載到不同cacheline中。

如何解決VIPT Cache別名問題

我們接著上面的例子說明。首先出現問題的場景是共享映射，也就是多個虛擬地址映射同一個物理地址才可能出現問題。我們需要想辦法避免相同的物理地址數據加載到不同的cacheline中。如何做到呢？那我們就避免上個例子中0x1000映射0x4000的情況發生。我們可以將虛擬地址0x2000映射到物理地址0x4000，而不是用虛擬地址0x1000。0x2000對應第0x00行cacheline，這樣就避免了別名現象出現。因此，在建立共享映射的時候，返回的虛擬地址都是按照cache大小對齊的地址，這樣就沒問題了。如果是多路組相連高速緩存的話，返回的虛擬地址必須是滿足一路cache大小對齊。在Linux的實現中，就是通過這種方法解決別名問題。

不存在的PIVT高速緩存

按照排列組合來說，應該還存在一種PIVT方式的高速緩存。因為PIVT沒有任何優點，卻包含以上的所有缺點。你想想，PIVT方式首先要通過MMU轉換成物理地址，然后才能根據物理地址index域查找cache。這在速度上沒有任何優勢，而且還存在歧義和別名問題。請忘記它吧。不，應該不算是忘記，因為它從來就沒出現過。

總結

VIVT Cache問題太多，軟件維護成本過高，是最難管理的高速緩存。所以現在基本只存在歷史的文章中。現在我們基本看不到硬件還在使用這種方式的cache。現在使用的方式是PIPT或者VIPT。如果多路組相連高速緩存的一路的大小小于等于4KB，一般硬件采用VIPT方式，因為這樣相當于PIPT，豈不美哉。當然，如果一路大小大于4KB，一般采用PIPT方式，也不排除VIPT方式，這就需要操作系統多操點心了。

編輯：黃飛