Cache的結(jié)構(gòu)設(shè)計(VIVT-PIPT-VIPT)

發(fā)現(xiàn)一篇講cache特別好的文章，在看uboot代碼時看到cache的開關(guān)總是和mmu有一些聯(lián)系，直到看到這篇文章，明白了其中的一些聯(lián)系。文中深入的對cache的工作機制進行分析，首先明確在CPU是如何使用Cache的，Cache和主存到底是如何通過虛擬地址和物理地址進行映射的，映射的過程中是否存在問題等等。沒有特殊說明，Cache中的數(shù)據(jù)包括指令和被指令操作的數(shù)據(jù)。

1、Cache的工作方式

從處理器的角度分析一下Cache在PE工作中的作用。處理器工作的時候，訪問主存使用的是虛擬地址的編碼方式。前文中也已經(jīng)講過，cache中的數(shù)據(jù)其實就是主存中數(shù)據(jù)的副本。主存中的數(shù)據(jù)編碼方式是以字節(jié)為單位，而Cache中的數(shù)據(jù)編址是以Cache Line(一般為64字節(jié))為單位，這樣Cache和內(nèi)存中的數(shù)據(jù)進行映射就需要一個過程，又因為作為數(shù)據(jù)的訪問者CPU使用虛擬地址進行數(shù)據(jù)的訪問，那么自然這個過程的參與者就變成了PE、MMU、Cache、主存，如何通過虛擬地址進行串聯(lián)的過程，這里通過一個經(jīng)典的Cache架構(gòu)加以說明，如下圖所示。

對上面這個架構(gòu)做一下拆解，其實就是一個尋找TAG、Index、Offset之旅：

• S-1 任何時候，CPU在訪問主存的時候永遠(yuǎn)是使用虛擬地址的。內(nèi)存管理是個很復(fù)雜的課題，后續(xù)單獨進行討論。而支持通過虛擬地址方式訪問是現(xiàn)代處理器的基本能力?？梢赃@么理解虛擬地址給軟件用的，物理地址是給硬件用的，虛擬地址和物理地址之間有一個映射的關(guān)系，不過這個映射是以頁或者塊為單位的，最少小映射顆粒度是4k空間。
• 處理器在訪問存儲器時，會把虛擬地址同時傳遞給 TLB (S-2)和Cache高速緩存(S-6)。TLB (Translation Lookaside Buffer)是一個用于存儲虛擬地址到物理地址轉(zhuǎn)換的小緩存，處理器先使用有效頁幀號(Effective Page Number， EPN)在 TLB 中查找最終的實際頁幀號(Real Page Number， RPN)。假設(shè)發(fā)生 TLB 命中(TLB hit)(S-3)，就會很快獲得合適的 RPN ，并得到相應(yīng)的物理地址(Physical Address ， PA)。到這里簡單回顧下尋址一個cache line的3要素：TAG、Index、Offset。既然，我們已經(jīng)鎖定了物理地址，那么至少TAG到這里我們是可以確定了的。
• 同時，處理器通過高速緩存編碼地址的索引(index )域可以很快找到相應(yīng)的高速緩存行對應(yīng)的組Set(S-3)。但是這里的高速緩存行的數(shù)據(jù)不一定是處理器所需要的，因此有必要進行一些檢查，將高速緩存行中存放的標(biāo)記域TAG和通過MMU 轉(zhuǎn)換得到的物理地址的標(biāo)記域進行比較。如果相同并且狀態(tài)位匹配，就會發(fā)生高速緩存命中(cache hit)(S-8)，處理器通過字節(jié)選擇與對齊(byte select and align)部件，就可以獲取所需要的數(shù)據(jù)。這個過程就是把S-6過來的Index分發(fā)給所有的Way的Set然后比較TAG，再比較TAG的有效位，如果都匹配說明數(shù)據(jù)在cache且有效。就可以把cache line上的數(shù)據(jù)整體取出來了。
• 此時通過TAG和Index已經(jīng)取出了Cache Line的數(shù)據(jù)，但是CPU其實想要的也許就是其中的幾個字節(jié)的數(shù)據(jù)，那么就通過S-9傳過來的Offset做更精細(xì)化的自己尋址就可以了。到這里，就順利地給CPU返回它想要的數(shù)據(jù)了。

例外的情況:

• 如果發(fā)生高速緩存未命中(cache miss)，處理器需要用物理地址進一步訪問主存儲器來獲得最終數(shù)據(jù)，數(shù)據(jù)也會填充到相應(yīng)的高速緩存行中。也就是經(jīng)過TAG和Index進行比較判斷出，想要的數(shù)據(jù)沒有在Cache中，因為此時系統(tǒng)已經(jīng)了主存數(shù)據(jù)所在的物理地址，直接按照既定的替換策略，將數(shù)據(jù)經(jīng)過L3-Cache->L2-Cache->L1 Cache(S-7)加載到Cache，然后重復(fù)過程上述(3)(4)也達(dá)到了CPU的目的。
• 如果其間發(fā)生 TLB 未命中(TLB miss)(S-4)，將會帶來一系列嚴(yán)重的系統(tǒng)懲罰，處理器需要查詢頁表。那么此時，MMU就要做虛擬地址和物理地址映射，其實就是到頁表中找到對應(yīng)分配好的頁中數(shù)據(jù)的物理地址(之前沒有分配的話，說明想要的數(shù)據(jù)主存中也有沒有就要拋出異常先將數(shù)據(jù)從系統(tǒng)外部加載到主存)，然后將這個物理地址和數(shù)據(jù)經(jīng)過S-5和(5)中的過程，然后就讓CPU得到它想要的數(shù)據(jù)。

上面這個過程，大家先關(guān)注總結(jié)2個點：

• TAG 在這里是是通過物理地址算出來的。
• Index是通過虛擬地址算出來的。
• 通過虛擬Index和物理TAG的形式我們尋址到了Cache Line。這就是緩存實際的組織形式之一VIPT，實際上Cache還有其他的組織形式，一個CPU中不同level的cache可以支持不同的組織形式。本文下面的章節(jié)，就來介紹Cache的類型。

2、Cache類型

這里結(jié)合一款具體的ARM處理器架構(gòu)來介紹一下Cache的分類，如下圖所示。

通過Cortex-A710的block圖，可以清晰看到，ARM設(shè)計了兩級Cache結(jié)構(gòu)，其中L1層還對Cache做了細(xì)分(指令和數(shù)據(jù)分離)。下面看一下這兩級Cache的具體特征，如下圖所示。

Cortex-A710的Cache的Feature可以簡單總結(jié)一下:

• Cache Size 為 32KB、64KB、256KB、512KB；
• Cache Line length都為64bytes；
• 都是組多路組關(guān)聯(lián)的方式(4 or 8 ways set associative)；
• Index和Tag的類型分別是VIPT和PIPT；
• 替換策略為LRU 或者 動態(tài)地調(diào)整替換策略。

Cache的詳細(xì)結(jié)構(gòu)

Feature中的前三點在前面的文章已經(jīng)充分討論過了，替換的策略后續(xù)討論一下，這里會重點討論一下Index和Tag的類型，借此也討論清楚Cache的結(jié)構(gòu)。前面講述VIPT類型的Cache的工作流程，這里們看到ARM-Core中的cache還有另外一種組織形式PIPT，要討論講清楚這兩種Cache類型，還是要結(jié)合的具體結(jié)構(gòu)，如下圖所示。

這是ARM手冊中一個比較經(jīng)典的例子(手冊中的例子貌似有點錯誤，這里也希望大家一起思考指正)，64KB-L1 data cache，分成4路，采用組關(guān)聯(lián)的方式，每行的cache line的長度或者size為64字節(jié)。

• 高速緩存的總大小為 64KB ，并且是 4 路的，所以每一路的大小為 16KB(way_size = 64KB/ 4 = 16KB) 。
• 高速緩存行的大小為 64 字節(jié)，所以每一路包含的高速緩存行數(shù)量如下num_cache_line = 16KB/64B = 256。

Offset

這里offset為地址編碼的Bit[0:5]總計6位，其中Bit[2:5]共計4位可以用來尋址0~15共計16個字，Bit[0:1]可以對字中的字節(jié)進行尋址，最終實現(xiàn)的效果就是可以實現(xiàn)Cache Line中的64字節(jié)尋址。

Index

Bit[6:13] 共8位用于在索引域中選擇每一路上的高速緩存行，也就是Index可以實現(xiàn)在一路cache中進行256行的尋址。因為cache采用的是組關(guān)聯(lián)的方式，也就是說這里Index可以實現(xiàn)這4路256組的尋址。

TAG

Bit[14:43]共30位用作標(biāo)記域。

V & D

當(dāng)通過主存的地址編碼確認(rèn)了Offset、Index、TAG之后就可以在cache中鎖定了CPU想要的數(shù)據(jù)了，但是此時還不是勝利的時候，還需要檢查數(shù)據(jù)所在的Cache Line的兩個標(biāo)志位：V，D。這兩個標(biāo)志位的作用，我們直接引用手冊的描述：

• Valid bits to indicate whether the line exists in the cache, that is whether the tag is valid. Valid bits can also be state bits for the MESI state if the cache is coherent across multiple cores.
• Dirty data bits to indicate whether the data in the cache line is not coherent with external memory.

上圖雖然詳細(xì)的描述了cache的結(jié)構(gòu)，但是還是有一個點沒有表達(dá)清楚，就是CPU使用的虛擬地址采用什么樣的方式和cache中的TAG、Index做映射，比如例子中使用的是VIPT(使用虛擬地址的索引域和物理地址的標(biāo)記域)的方式，下面繼續(xù)討論其他的方式。不同的映射方式對應(yīng)的CPU-Core內(nèi)部硬件電路(CPU的架構(gòu))也是不同的。以ARM為例，從早期到現(xiàn)在共使用了三種映射技術(shù)：虛擬高速緩存(VIVT)、物理標(biāo)記的虛擬高速緩存(VIPT)、物理高速緩存(PIPT)。

VIVT

VIVT(Virtual Index Virtual Tag) 使?虛擬地址的索引域和虛擬地址的標(biāo)記域，相當(dāng)于虛擬?速緩存，早期的處理器采用的就是這種方式。這種方式就是把PE傳遞過來的虛擬地址直接切成三段分別代表TAG、Index、Offset(如下圖)，然后對Cache進行尋址，命中則直接返回數(shù)據(jù)，失敗則需要將虛擬地址轉(zhuǎn)換成物理地址，然后尋址主存儲器然后將數(shù)據(jù)加載到Cache再返回給PE。

一個VA的地址可以映射任意的物理地址，VIVT的cache不需要經(jīng)過譯碼，直接被拆分成TAG(V)和Index(V)，以頁為4K為例，無論怎么切分就是上述三種場景，這樣設(shè)計的好處是架構(gòu)簡單，會引入兩個問題：歧義和別名。

（1）歧義(ambiguity)

當(dāng)不同的數(shù)據(jù)在高速緩存中有相同的index、tag