# Arm Programmer's Guide VIII - Caches 學習筆記
<h1>1. 前言</h1>
此筆記為學習 [ARM® Cortex™-A Series Programmer's Guide
Version: 4.0 中第八章 Caches ](https://developer.arm.com/documentation/den0013/d/Caches) 的心得筆記。主旨在解釋 Armv7 Aarch32 下的快取 (Cache) 相關行為跟設計。
<h1>2. 概述</h1>
由於現今的處理器速度皆遠大於其外部記憶體設備，頻繁的使用外部記憶體設備將使效能大幅降低。如果處理器內本身能有個空間來儲存一些常用到的資料，這樣就能減少外部記憶體的使用、進而增加效能，而這個空間就是快取 (Cache)。理論上這個空間越大越好，但這將會帶來過度複雜且昂貴的處理器設計，在實務上是不切實際的，所以快取的大小相對於主記憶體空間來說都還是很小的，而重點是該怎麼最佳化地利用此有限但快速的空間。
由於快取的大小是小於主記憶體的，它儲存資料 (指令位置、要讀的資料、要寫的資料) 的同時也必須將該資料的記憶體位置也一起紀錄。當 CPU 要讀寫某個記憶體位置的資料時，他會先在快取中確認該資料是否存在，如果存在，就直接使用快取中的資料，減少外部主記憶體的存取，進而提升效能。
另外一個在核心跟 Cache 很像的東西是寫緩衝 (Write Buffer)，它位於 Cache 和主記憶體之間。不論是 CPU 要直接對主記憶體做寫操作，或是 Cache 被 Clean 要將資料寫回主記憶體，他們都會將資料先寫進 Write Buffer 中，寫入後就當作寫操作完成，可以繼續進行它們的下一步動作，而 Write Buffer 中的資料會再以非同步的方法慢慢的寫進主記憶體。這樣做的目的一樣是為了不被較慢的 Core 外部操作給拖慢效能。
<h2>2.1 為什麼 Cache 可以提升效能?</h2>
由前面的描述可以了解，在資料第一次被存取的時候，因為他一定不存在於 Cache 中，所以它的存取會是和沒有 Cache 的情況下一樣慢的 (甚至更慢，因為還要將資料放進 Cache 中)，只有當系統再次存取該資料時，效能上才能受益於 Cache。**而 Cache 這樣的策略能有效的帶來效能提升，其實是因為程式在存取資料的位置上有其時空地域性 (the properties of temporal and spatial locality)，而非完全隨機的。** 也就是說，在空間上，程式偏向頻繁使用相鄰或附近的資料；在時間上，程式偏向使用最近使用過的資料。舉例來說，迴圈會重複的使用相同位置的資料或函式、Stack 中的資料都是在 Top 位置前後做讀寫。
<h2>2.2 Cache 的缺點 </h2>
最大的缺點就是每個指令的執行時間會變得不確定。因為無法預期該指令本身或是所需的資料是否在 Cache 中，如果有的話可以馬上取得、如果沒有的話要先將它搬至 Cache 中、如果沒有而且 Cache 是滿的話，還要先判斷 Cache 中要將誰清除等等。這些不確定性在很要求實時 (real-time) 的系統中會是個問題。
另一個缺點就是系統和開發者需要花額外的心力在一致性 (coherency) 問題上。由於資料有可能還在 Cache 中、還沒被更新進主記憶體裡，這時如果有其他能存取主記憶體的元件 (也就是所謂的 Agent) -- 像是 DMA 或是其他核心 -- 去主記憶體讀取該位置，那麼它就會得到舊的資料，這就是一致性問題。
<h1>3. 記憶體階級 (Memory Hierachy)</h1>
一個系統會有許多階層的記憶體，他們越靠近核心就會越快但是空間越小、離核心越遠就會越慢但是可用的空間會越大。在嵌入式系統中，通常可以簡單地根據他們是在核心內 (或至少在同個 Package 中) 還是核心外來做區分。而 Cache 可以存在在任何一個階層之中，用來消除上下層之間速度差異造成的效能下降。
L1 快取 (Level 1 Cache) 是 SRAM 製成且通常直接和核心相連或是核心的一部分，它的大小通常是 16KB 或者是 32KB，因為這是核心在速度 1GHz 下，能夠在 1 個 cycle 內完成存取的最大大小。所以過大的 Cache 其實也有可能帶來反效果、反而降低效能，像是:
1. Cache 大小越大，核心需要花費越多的時間去查找 (Cache look-Up)。
2. 當需要同步各 Cache 之間的資訊時，會需要花費更多的時間。
3. Cache 做 Invlaid 或是 Clean 也都會需要花更多時間。
L2 快取 (Leve 2 Cache) 較大，通常為 256KB、512KB 或者 1MB，它一定是 Unified Cache，它也可以是核心的一部分，或者是獨立於核心和其他記憶體階層間的模塊 (Block)。L2 快取不只能夠在多核之間共享，它甚至可以跟其他的 Agent (像是 GPU) 共享。
(下圖顯示一個 L1 為 Harvard Cache -- 會在下一章提到 -- 且 L2 為獨立於核心之外的模塊的記憶體階級示意圖。)
在多核心的系統中，可能每個核心都有自己的 L1 Cache，這就會需要一個同步機制來同步所有核心的 L1 Cache ，否則就會問題。
<h1>4. Cache 架構</h1>
<h2>4.1 Harvard / von Neumann </h2>
Harvard 架構將 Cache 拆成 D-Cache (Data Cache) 和 I-Cache (Instruction Cache) 兩個獨立部分。
優點:
1. 提供更高的效率，資料和指令的存取可以同時進行。
2. 不會因為 Data 或 Instruction Cache 的大量使用排擠另一個 Cache 的空間。
缺點:
1. 硬體設計更複雜、成本更高。
2. 兩 Cache 之間需要注意資料一致性的問題。
von Neumann 架構則是使用單一 Cache 同時負責 Data 和 Instruction，它的優缺點剛好和 Harvard 相反。
<h2>4.2 資料結構</h2>
如果資料是以一個 Byte 或一個 Word 為最小單位的方式儲存會非常沒有效率，所以 Cache 最小的存取單位稱作 Line，它是由多個 word 組成:
而 Index 是用來指定第幾條 Line 用的:
Set Associative Cache 會將 Cache 平分成多個 Way (通常是 2 或 4 個):
不同 Way 中相同 Index 的 Line 又組成 Set:
因前面提到過的， Cache 的大小必定是遠小於主記憶體，所以存取資料的同時，也需要將該資料在記憶體中的位置一併紀錄。又因 Cache 是用 Line 來一次存取一段連續的記憶體資訊，所以只需要在每條 Line 紀錄該連續記憶體的起始位置就好，這資訊稱為 Tag:
Tag 會是由記憶體位置最高位的幾個位元組成。舉例來說，假設上圖的 Cache 表示為一個 Line Size 為 4 word、每個 word 為 4 Bytes、每個 way 有四條 Line 的 Cache，那麼記憶體的最高 26 位 (BIT[31:6]) 就會是 Tag。(BIT[5:4] 指定是哪一條 Line；BIT[3:2] 指定是 Line 中的哪一個 Word；BIT[1:0] 指定是 Word 中的哪一個 Byte):
雖然 Tag 會需要 Cache 花費空間來儲存，但是由於它不屬於資料，所以它並不會被計算進 Cache 的大小。也就是說，當提到 32KB Cache 時，這 32KB 並不包含儲存 Tag 的空間。
最後還需要一些位元用來表示 Cache 內資料的狀態
1. Valid bit 用來表示某一條 Line 是否含有能用的資料 (也就是說該 Tag 是否是真的)。
3. Data Cache 中還會有 Dirty bit 用來表示 Cache 中的資料和主記憶體中的資料是否一致。
<h2>4.3 Direct Mapped Caches</h2>
Cache 有很多種實作方法，Direct Mapped Cache 算是最簡單的一種。所有的主記憶體資料都會被映射到指定的 Cache 位置。方法為從頭開始一對一的映射，當到達 Cache 的末端後，就從 Cache 的開頭重新開始映射。由於主記憶體空間大於 Cache 很多，所以必定會有多個主記憶體資料映射到同一個 Cache 位置。
一樣假設現有一 Cache 其 Line Size 為 4 word、每個 word 為 4 Bytes、每個 way 有四條 Line，那麼 Direct Mapped 的映射方法示意圖如下:
記憶體位置一樣會被切成以下幾個區域:
所以在 Core 查找 Cache 的時候，他會先從 Address 的 BIT[5:4] 取得 Line Index，然後去 Cache 中檢查該 Line 的 Tag 和 Address 的 BIT[31:6] 是否吻合。若吻合而且 Valid Bit 顯示資料是 valid 的，那麼就確定在 Cache 中找到該資料所在的 Line (A hit)， Core 接下來會利用 Address 的 BIT[3:2] 來在 Line 找到正確的 Word ，在用 BIT[1:0] 來在該 Word 中找到的正確 Byte；若該 Line 是 valid 但是 Tag 不吻合 (A miss)，那表示該 Line 存的是其他 Address 的資料，這時就需要去主記憶體中將現在要存取的資料讀出來取代現在 Line 上的資料，並更新 Tag。
Directed Mapped 最大的缺點就是容易遇到一種叫做鞭打 (Thrashing) 的問題。先來看看下面的程式若跑在上面範例的 Cache 會發生什麼事:
```clike=
void example()
{
int* result = (int*)0x00;
int* data1 = (int*)0x40;
int* data2 = (int*)0x80;
int i;
for(i = 0; i < 16; i++)
result[i] = data1[i] + data2[i];
}
```
由於 result, data1 和 data2 的起始位置都是對應到 Cache 的 Index 0 (他們 Address 的 BIT[5:4] 都是 b00)，所以當迴圈第一圈執行 result[0] = data1[0] + data2[0] 時:
1. 讀取 data1[0] 時會發現 Cache 的 Line Index 0 沒有資料 (Invalid)，所以把 data1[0] 以及其相鄰的資料 (Addr 0x40~0x4F) 存進 Line Index 0 中 (Tag -- Address 的 BIT[31:6] -- 為 0x1)。
2. 讀取 data2[0] 時會發現 Cache 的 Line Index 雖然有資料 (Valid)，但是它的 Tag 不對 (data2[0] 的記憶體位置 BIT[31:6] 為 0x2)，所以會拿 data2[0] 及其相鄰的資料 (Addr 0x80~0x8F) 取代 Line Index 0。
3. 將資料寫進 result[0] 會遇到和 2 一樣的情況，Cache Index 0 會需要再次被替換成 result[0] 以及和它相鄰的資料 (Addr 0x00~0xF)。(會不會替換 Cache 其實會根據 Allocation Policy -- 這個會在後面說明 -- 決定，但前述況的確有可能會發生，我們這邊也假設它會發生。)
4. 前面同樣的事情會隨著迴圈不斷重複執行而不斷發生，Cache 的 Line index 0 也會被不斷地覆寫、不斷地被「鞭打」。
<h2>4.4 Set Asscociative Caches</h2>
這個是 Arm 核心主要採用的 Cache 架構，它的優點如下:
1. 能夠大幅降低上面提到的 Thrashing 鞭打問題。
2. 提供更好的效能。
3. 提供每個指令更穩定的執行時間。
缺點則是:
1. 更複雜的硬體設計。
2. 稍微較高的電量消耗。
它會將 Cache 等分成多個 Way，每一個 Way 都有自己的 Line Index，並且 Address 中的 Line Index N 不再用來指定第 N 條 Line，而是會用來指定第 N 個 Set (也就是所有 Way 中的第 N 條 Line)。下圖顯示的是 Set Asscociative Cache 映射到主記憶體的示意圖，像 Address 0x0 的資料有可能放在 Way0 的 Line0 中，也有可能放在 Way1 的 Line0 中 (但不可能兩者都放)。
當要在 Cache 中查找指定地址資料是否存在時，需要先從 Address 中取出 Index 已得知資料可能所在的 Set，然後在該 Set 中確認所有 Line 的 Tag 來確認是否 hit。
可想而知，Associativity 越多 (也就是 Way 越多)，Thrashing 的機率就越小，效率就越高。一般來說，L1 Cache 只要超過 4-way Asscociativity 效能增加就會變得很有限，所以 8-way、16-way 等更多 way 的 Asscociativity 在 L2 中更為有用。
<h1>5. Cache Controller</h1>
Cache controller 就是用來控制 Cache 的硬體，他負責在 Cache 中查找資料 (Cache look-up)、填寫或覆寫 Cache 中的 Line，以及當 Cache miss 時，將指令往下繼續傳遞給下一層 Cache 或者主記憶體。
值得一提的是，為了更大程度的優化效能，當有整個 Line 需要被重寫 (執行 Linefill) 時，為了讓核心不需要等待整條 Line 的操作完成，Cache Controller 通常會先將核心關心的資料 (Critical word) 傳給核心，讓核心可以取得所需資訊並繼續執行，然後 Cache Controller 再將 Line 裡面的其他資料覆寫在背地裡慢慢完成。
<h1>6. Virtual/Physical Tags and Indexes</h1>
前面章節有提到核心是會根據所需存取資料的記憶體位置來定位 Cache 中的 Line，並會將記憶體位置最高的幾個位元當成 Tag 一併存進 Line 中。但這邊提到的記憶體位置是虛擬 (Virtual) 記憶體位置還是實體 (Physical) 記憶體位置也是存在學問的。
<h2>6.1 VIVT (Virtual Indexed, Virtual Tagged)</h2>
不論 Index 還是 Tag 都是用 Virtual Address 來取得。
優點:
1. 核心在做 Cache look up 的時候不需要先對 Address 做 V2P (Virtual to Physical)的轉換。
缺點:
1. 若 V2P 的映射表 (Translation Table) 需要更換，那就需要再更換前將整個 Cache 的內容更新進主記憶體中 (clean)，並將整個 Cache 標為 Invalid。這在需要頻繁切換工作的系統上會是一個很大的效能開銷。
<h2>6.2 VIPT (Virtual Indexed, Phyical Tagged)</h2>
Index 從 Virutal Address 來，但是 Tag 是從 Physical Address 來。
優點:
1. 就算 Translation Table 更換了，也不需要動 Cache，因為它是用 Physical Address 來紀錄 Tag。
2. 來自 Virtal Address 的 Index 也可以讓核心在不用做 V2P 就可以知道該去哪一個 Set 尋找目標資料。
缺點:
1. 如果 Translation Table 的 Page 大小沒有和 Cache 的大小配合好，導致 Tag 的位元數跟會做 V2P 的最高記憶體位元數不一致的話，就有可能出問題。請看下面範例:
【Cache 資訊】
Size: 32 KB
Asscociativity: 4-Way
Line Size: 8 Word (32 Byte)
一個 Word 是 4 Byte，所以 BIT[1:0] 用來指定 Byte。
每條 Line 有 8 個 Word，所以 BIT[4:2] 用來指定 Word。
32 KB / 4 / 32 = 256，所以每個 way 有 256 條 Line。
256 為 2^8，所以 BIT[12:5] 用來指定 Index。
剩下的 BIT[31:13] 則是 Tag。
【Translation Table 資訊】
Page Size: 4 KB (通常需要 L2 Translation Table)
2^32 / 2^12 = 2^20，所以 BIT[31:12] 會被用來做 V2P 的轉換。
Address 的結構如下:
現在假設有兩個 Virtual Address Va = 0x00000000 和 Vb = 0x00002000:
然後 Va 的 BIT[31:12] 被 MMU 翻譯成 Px 0，其中 Px 為一個 19 位元數字；Vb 的 BIT[31:12] 則是被 MMU 翻譯成 Px 1。
那麼根據上圖和 VIPT 的策略，Va 和 Vb Virtual Address 的 BIT[12:0] 都是 0，所以他們的 Index、Line 甚至最後的 Byte Offset 都會一樣、都會是 0；Va 和 Vb 他們被翻成 Physicall Address 後的 BIT[31:13] 也都是 Px，所以他們的 Tag 也會是一樣，但事實上很明顯這是兩個不同記憶體位置的資料，在 Cache 上定位到同樣的位置同樣的 Tag 是有問題的。而**出問題原因其實就是紅框的長度和 Tag 的長度不一致造成的**。
其中一種解法就是要求軟體建立的 Translation Table 配合 Cache 的 Tag 長度，這樣的方法也被稱為 "Page Coloring"。另一種解法就是採用 PIPT。
<h2>6.3 PIPT (Physical Indexed, Physical Tagged)</h2>
無論是 Index 還是 Tag 都是來自 Physical Address。
優點:
1. 能夠完全避免 Page Coloring 的問題。
2. 切換 Translation Table 也不需要動 Cache。
缺點:
1. 更複雜的硬體設計讓核心能夠支援先做 V2P 再取 Index 和 Tag。
<h1>7. Cache Policies</h1>
<h2>7.1 Allocation Policy</h2>
Allocation Policy 指的是當 Cache Miss 的時候，是否需要將新的資料做 Linefill 填進 Cache 中:
1. Read Allocate Policy: 只有在讀取 Miss 的時候會去將該資料更新 (Allocate) 到 Cache 中。如果寫 Miss 則直接忽略當前階級的 Cache，往下一層移動。
2. Wite Allocate Policy: 無論讀或寫 Miss 都將該資料更新進 Cache 中 (所以其實稱其為 Write-Read Allocate Policy 更為洽當)。常常和 Write-bakc -- 稍後會提到 -- 搭配使用。
有時候 Linefill 會占用核心非常多的時間，所以核心在硬體上有對其做優化。舉例來說，在呼叫 memcpy() 或是 memset() 這類函式時，常常會執行非常大量且連續的 Linefill，而且這些資料常常馬上就會被覆蓋或者短時間內不會再被用到，在覆寫他們之前將他們更新進 Cache 是沒有意義的，所以核心會將它優化成不更新進 Cache 、直接在主記憶體中做更新。(而這也表示 Allocation Policy 對核心來說其實並不是硬性的規定。)
<h2>7.2 Replacement Policy</h2>
Replacement Policy 是指在 Set Asscociative Cache 中，如果一個 Set 的所有 Line 都有資料了，但是還是發生 Cache Miss，需要將新資料覆寫其中一條 Line 時，該選擇哪條 Line 的策略。
其中，被選中的 Line 稱為受害者 (Victim)，如果 Victim 是 Dirty 的，那它在被覆寫之前需要先將它的資訊更新回主記憶體中，這個動作稱為回收 (Eviction)。
1. Round-robin 或 Cyclic (輪替法):
有一個受害者計數器 (Victim Counter) 在 Set 裡面循環依序選擇下一個受害者。這種方式很好預測，但是在特定的情況下，會有非常差的效能。
2. LRU (Least Recently Used):
將最後一個被使用的 Line 選為 Victim。因為需要維護每個 Line 的計數器或時間戳記，所以硬體成本上較高，實際上較少核心支援。
3. Pseudo-random (偽隨機法):
使用一種接近隨機的計算方法去決定下一個 Victim 是哪一條 Line。常常是使用 LFSR (Linear Feedback Shigt Register) 來產生「類似」隨機的數字。這種方法通常比完全隨機更具可重複性和硬體友善性，但仍可以避免固定模式導致的性能問題。再加上對硬體要求沒有 LRU 來的高，導致這是較常被採用的 Replacement Policy。
<h2>7.3 Write Policy</h2>
Write Policy 是指 Write 指令在 Cache 中 Hit 時的行為:
1. Write-through: 同時對 Cache 和主記憶體做資料的寫入。它的效率通常會比 Write-back 差，但是會有較少的一致性問題。
2. Write-back: 只對 Cache 做寫入。這樣會造成 Cache 裡的資料較新，主記憶體中的資料較舊 (stale)，所以該 Cache Line 的 Dirty bit 會被舉起來標記這件事。如果未來這條 Line 要被 Evicted，Cache 就知道要先將資料更新回主記憶體中。Write-back 因為不需要等較慢的外部記憶體操作，它的效能是比較好的，但如果有其他人 (Agent) 可以存取主記憶體資料，那麼將要注意如何避免其他人取得過時的資料。
<h1>8. Write and Fetch Buffers</h1>
Write buffer 通常是核心硬體的一部分 (但也可以不是)，它從核心那裡取得寫指令的細節，包含寫的內容、位置等等後，核心就可以當作寫指令完成了，並繼續接下來的動作。而與此同時，Write Buffer 會在不影響核心的情況下完成實際將資料寫進主記憶體的工作。這樣的效能提升前提是 Write Buffer 沒有被填滿的情況，所以如何避免 Write Buffer 滿也是提升效能的一個關鍵。
有的 Write Buffer 支援多個寫指令的合併 (write merging 或 write combining)。舉例來說，它能將多個對相鄰位置的寫指令，合併成一個包含整個相鄰區域的寫指令，藉此來降低外部記憶體的使用以提升效能。
但某些時候你反而會希望寫指令不要被合併或者不要被 Buffered，你需要等待該指令確實地寫進主記憶體中，舉例來說，當你在對 Memory-Mapped 的周邊設備記憶體位置做操作的時候。這時你可以透過設定該記憶體區段的 Memory Type 來達到此目的。更多細節請看 [Arm Programmer's Guide X - Memory Ordering 學習筆記的 2. Memory Type](https://hackmd.io/@uMqav-XESBCsrtZEx_Jpug/Arm_Programmer_Guide_Memory_Ordering_Studying_Note#2-Memory-Type)。
Fetch Buffer 則是在讀取指令的時候核心會預先讀取未來的指令並存放其中，以提升執行速度。這可能會造成實際實行順序和程式呼叫順序不一致，進而造成其他問題。一樣更多細節請看 [Arm Programmer's Guide X - Memory Ordering 學習筆記](https://hackmd.io/@uMqav-XESBCsrtZEx_Jpug/Arm_Programmer_Guide_Memory_Ordering_Studying_Note)。
<h1>9. Cache performance and hit rate</h1>
Cache Hit Rate 指的是一個記憶體存取要求能在 Cache 中 hit 的機率。很直觀地，Cache Hit Rate 越高，系統的效能就越好。而以下方法可以幫助提高 Cache Hit Rate:
1. 將頻繁使用的資料放在相鄰的位置。這樣第一個資料被使用後，其他的常用資料也會一起被 Linefill 進 Cache。實際做法可以是將常用的資料放進一個陣列中。而像是 Link List 裡的這種不相鄰的資料就比較沒有辦法受益於 Cache (not Cache-friendly)。
2. 較小的 Code Size 對於 Cache 來說是比較有益的，因為 Code Size 越小，Cache 可以存放整體 Code 的比例就越高，效能也就越好。甚至假設 Code Size 比 Cache 還小的話，就可以整包 Code 放進 Instruction Cache 中，執行過程的每個指令都會是 Cache Hit。
<h1>10. Invalidating and cleaning cache memory</h1>
無效化 (Invalidation): 無效化基本上就是把資料從 Data Line 中移除，但它不是真的將資料刪掉，而是將 Valid Bit 設定成 Invalid 的值。對於一條 Dirty 的 Line 來說，你直接將它無效化基本上是錯誤的，因為這樣 Cache 中的較新資料將會遺失。另外，如果其他 Agent 修改了主記憶體中的資料，那麼該資料在 Cache 中的備份就應該要被無效化。
掃除 (Cleaning): Clean 是指將該 Dirty Line 的內容更新進主記憶體中，並且將 Dirty Bit 清除。這通常只有在 Write-back Policy 才用的到，Write-through 用不到。
除了上述的例子之外，MMU 相關的改動之後也常常需要做 Invaludation 和 Clean:
1. 改變記憶體的存取權限: 舉例來說，將核心對某個記憶體區段的寫權限移除，那麼在那之前應該先將 Cache 中對於該記憶體區段的 Dirty Line 做 Clean 的動作。
2. 改變 Cache Policies: 舉例來說，將 Write-back 改成 Write-through 前，須也需要對 Dirty Line 做 Clean 的動作。
3. Translation Table 改變: 若 Tag 是用 Virtual Address 的話，那麼因 Translation Table 改變使 Tag 的意義 (對應的 Physical Address) 跟著改變，需要將整個 Cache 在改變前做 Clean、改變後做 Invalid。
還有修改或複製程式碼的操作也會需要用到 Invalid 和 Clean。假設核心修改了記憶體中的某一段程式碼，而且是採用 Write-Back，那麼它勢必要在更新完 Data Cache 後執行 Clean 來將實際的改動寫進主記憶體中，這樣未來 Instruction Cache 才不會讀到舊的程式碼。除此之外，如果該段程式碼在被修改之前就已經被 Instruction Cache 讀取過了，那 Instruction Cache 也應該將原本的備份 Invalide 掉。(這邊提到的其實就是要維持 PoU 的概念。PoU 會在稍後的章節提到。)
大部分時候 Invalid 前都應該要先做 Clean，除了:
1. 這個 Cache 不可能有 Dirty Line，像是 Harvard Instruction Cache (他只負責讀取指令，不會去寫)。又或者是 Write-Through Policy 下的 Data Cache。
2. 如果這些 Dirty 資料馬上就會被覆寫掉，那麼就也可以不用在乎他們遺失了。
協處理器 CP15 的 [SCTLR (System Control Register)](https://developer.arm.com/documentation/den0013/d/ARM-Processor-Modes-and-Registers/Registers/System-control-register--SCTLR-?lang=en) 用來控制 Cache 的 Clean 和 Invalid，且**只有在特權 (Privileged) 模式下才能執行**。這邊有一個 Invalid Cache 的範例 (關於 Clean 的範例會在後面一章提到):
```c=
;-----------------------------------------------
; 1.MMU, L1$ disable ($ 就是 Cache 的意思)
;-----------------------------------------------
MRC p15, 0, r1, c1, c0, 0 ; Read System Control Register (SCTLR)
BIC r1, r1, #1 ; mmu off
BIC r1, r1, #(1 << 12) ; i-cache off
BIC r1, r1, #(1 << 2) ; d-cache & L2-$ off
MCR p15, 0, r1, c1, c0, 0 ; Write System Control Register (SCTLR)
;-----------------------------------------------
; 2. invalidate: L1$, TLB, branch predictor
;-----------------------------------------------
MOV r0, #0
MCR p15, 0, r0, c7, c5, 0 ; Invalidate Instruction Cache
MCR p15, 0, r0, c7, c5, 6 ; Invalidate branch prediction array
MCR p15, 0, r0, c8, c7, 0 ; Invalidate entire Unified Main TLB
ISB ; instr sync barrier
;-----------------------------------------------
; 2.a. Enable I cache + branch prediction
;-----------------------------------------------
MRC p15, 0, r0, c1, c0, 0 ; System control register
ORR r0, r0, #1 << 12 ; Instruction cache enable
ORR r0, r0, #1 << 11 ; Program flow prediction
MCR p15, 0, r0, c1, c0, 0 ; System control register
```
<h1>11. PoC and PoU</h1>
<h2>11.1 PoC (Point of Coherency)</h2>
PoC 代表的是系統中的一個記憶體層級，該層級對於所有使用者 (Agent) 來說，讀到的資料都是一致的。通常來說，PoC 指的就是主記憶體。
PoC 是在 CP15 的 CLIDR (Cache Level ID Register) 中設定:
其中 BIT[26:24] 為 LoC (Level of Coherence) 就是用來顯示 PoC 等級的。如果值為 N 就表示若要將資料同步進 PoC，需要對 Level N 以下的 Cache 做 Clean。如果值為 0 就表示整個系統都是 Write-through 的，到處都是 PoC、不存在主記憶體和 Cache 資料不一致的問題。
(更多 LoC 的資訊可以參考 [Cortex-A53 Technical Reference Manual](https://developer.arm.com/documentation/ddi0500/j/System-Control/AArch64-register-descriptions/Cache-Level-ID-Register?lang=en) 中的說明)
而 CLIDR 的 CTypeN 則表示 LN-Cache 的類別:
| Ctype<n> | Meaning |
| -------- | ------------------------------------- |
| 0b000 | No cache. |
| 0b001 | Instruction cache only. |
| 0b010 | Data cache only. |
| 0b011 | Separate instruction and data caches. |
| 0b100 | Unified cache. |
更多 CLIDR 資訊請參考: [CLIDR, Cache Level ID Register](https://developer.arm.com/documentation/ddi0601/2024-12/AArch32-Registers/CLIDR--Cache-Level-ID-Register?lang=en)。
<h2>11.2 PoU (Point of Unification)</h2>
PoU 代表的則是一個記憶體層級，該層級對於 Instruction Cache 和 Data Cache 來說，讀到的資料都是一致的。舉例來說，Harvard Cache 中的 L2 Unified Cache 就是兩個 L1 Cache 的 PoU。如果沒有 L2 Cache，那主記憶體就是 L1 兩個 Cache 的 PoU。
<h2>11.3 PoC 同步範例</h2>
以下方法顯示要如何 Clean 指定 Cache 中的指定 Set:
1. 透過選取 CP15 的 CCSELR (Cache Size Selection Register) BIT[3:1] 來指定要做 Clean 的 Cache 等級:
BIT[0] 為 Instruction not Data BIT，如果是 1 就是指定 Instruction Cache；反之則指定 Data 或 Unified Cache。
更多 CCSELR 資訊請參考: [CSSELR, Cache Size Selection Register](https://developer.arm.com/documentation/ddi0601/2024-12/AArch32-Registers/CSSELR--Cache-Size-Selection-Register?lang=en)。
2. 步驟一之後，讀取 CP15 的 CCSIDR (Current Cache Size ID Register) 就可以取步驟一指定的 Cache 的資訊:
更多 CCSIDR 資訊請參考: [CCSIDR, Current Cache Size ID Register](https://developer.arm.com/documentation/ddi0601/2024-12/AArch32-Registers/CCSIDR--Current-Cache-Size-ID-Register?lang=en)。
3. 這時再將要做 Clean 的 Way 和 Set 透過指定格式填入 CP15 的 DCCSW (Data or unified Cache line Clean by Set/Way) 中，就可以將該 Set 做 Clean。
更多 DCCSW 資訊請參考: [DC CSW, Data or unified Cache line Clean by Set/Way](https://developer.arm.com/documentation/ddi0601/2024-12/AArch64-Instructions/DC-CSW--Data-or-unified-Cache-line-Clean-by-Set-Way?lang=en)。
了解上面的方法後，下面範例示範如何將所有的資料 (L1 ~ L3 Cache) 同步進 PoC:
```c=
/*********************************************************/
/* STEP1 */
/* 取得 PoC 的是在 Cache Level 多少，如果是 0 就直接跳至完成 */
/*********************************************************/
MRC p15, 1, R0, c0, c0, 1 // Read CLIDR into R0
ANDS R3, R0, #0x07000000
MOV R3, R3, LSR #23 // Cache level value (naturally aligned)
BEQ Finished
/************************************************************/
/* STEP2 */
/* Loop1 會用 R10 來依序選取 L1 到 PoC Level 間的所有 Cache */
/* Level，且若該 Cache Level 沒有 Cache 或只有 I-Cache 則跳過。*/
/************************************************************/
MOV R10, #0
Loop1
ADD R2, R10, R10, LSR #1 // Work out 3 x cache level
MOV R1, R0, LSR R2 // bottom 3 bits are the Cache type for this level
AND R1, R1, #7 // get those 3 bits alone
CMP R1, #2
BLT Skip // no cache or only instruction cache at this level
MCR p15, 2, R10, c0, c0, 0 // write CSSELR from R10
ISB // ISB to sync the change to the CCSIDR
/************************************************************/
/* STEP3 */
/* 讀取該 Cache Level 的資訊: Line、Way 和 Set 的大小。 */
/************************************************************/
MRC p15, 1, R1, c0, c0, 0 // read current CCSIDR to R1
AND R2, R1, #7 // extract the line length field
ADD R2, R2, #4 // add 4 for the line length offset (log2 16 bytes)
LDR R4, =0x3FF
ANDS R4, R4, R1, LSR #3 // R4 is the max number on the way size (right aligned)
CLZ R5, R4 // R5 is the bit position of the way size increment
MOV R9, R4 // R9 working copy of the max way size (right aligned)
/************************************************************/
/* STEP4 */
/* Loop2 和 Loop3 分別使用 Set 和 Way Index 來去遍歷該 Level */
/* Cache 的 Line，並對其做 Clean。 */
/************************************************************/
Loop2
LDR R7, =0x00007FFF
ANDS R7, R7, R1, LSR #13 // R7 is the max num of the index size (right aligned)
Loop3
ORR R11, R10, R9, LSL R5 // factor in the way number and cache number into R11
ORR R11, R11, R7, LSL R2 // factor in the index number
MCR p15, 0, R11, c7, c10, 2 // DCCSW, clean by set/way
SUBS R7, R7, #1 // decrement the index
BGE Loop3
SUBS R9, R9, #1 // decrement the way number
BGE Loop2
Skip
ADD R10, R10, #2 // increment the cache number
CMP R3, R10
BGT Loop1
DSB
Finished
```
<h1>12. Parity and ECC in caches</h1>
由於硬體電器上的不穩定，記憶體裝置上的位元有可能會發生翻轉 (Bit Flip )的情況，也就是應該要是 0 但是變成 1 或者相反。而有許多方法 (Parity) 能夠偵測到這樣子的問題，最簡單的就是增加一個 Bit (稱為 ECC, Error-Correcting Code 錯誤校正碼) 來紀錄資料裡面的是 1 的位元數量是偶數還是奇數，這樣如果發生一個或奇數個 Bit Flip 的話，實際的值為 1 的位元數量就會和 ECC 上所記錄的不一樣，以此來偵測出 Bit Flip 的發生。除上述之外也存在其他方法可以偵測更大範圍的 Bit Flip，甚至可以在一定程度的出錯範圍內修正錯誤 (當然這要求更大尺寸的 ECC，且修正將花費許多 Cycle 的時間)。
Arm 的 Cache 不論在 Read 或 Write、Data 還是 Tag Ram 也有支援 Parity 和 ECC 的功能，但是由於在 L1-Cache 實作此功能會大幅增加硬體設計的複雜度，所以大部分只有位於核心之外的 L2 Cache 才有支援 ECC (但少數像 Cortex-A15 還是有支援核心內的 Cache ECC)。如果 Cache 發生一個 Ecc 錯誤，那麼核心就會發出 Prefetch 或是 Data Abort 的 Exception。
---
上一篇: [Arm Programmer's Guide VII - Introducing NEON 學習筆記](https://hackmd.io/@uMqav-XESBCsrtZEx_Jpug/Arm_Programmer_Guide_Introducing_NEON_Study_note)
下一篇: [Arm Programmer's Guide IX - The Memory Management Unit 學習筆記](https://hackmd.io/@uMqav-XESBCsrtZEx_Jpug/Arm_Programmer_Guide_Memory_Management_Unit_Studying_Note)
Sign in with Wallet
Connect another wallet