1. 前言

限于作者能力水平，本文可能存在謬誤，因此而給讀者帶來(lái)的損失，作者不做任何承諾。

2. 背景

本文所有分析基于 ARMv7 架構(gòu) 和 Linux 4.14 內(nèi)核。

3. Cache 硬件基礎(chǔ)

3.1 什么是 Cache ？

Cache 是一塊高速內(nèi)存，由于 CPU 和 主存(通常是DDR等) 速度之間存在數(shù)量級(jí)的差異，于是在 CPU 和 主存 之間，加入速度更快、造價(jià)更高、容量更小 的內(nèi)存，也即 Cache，以緩解 CPU 和 主存 之間速度差異造成的性能損失：CPU 可以先將數(shù)據(jù)從主存加載到高速內(nèi)存(即Cache)，然后 CPU 大多數(shù)時(shí)候和高速Cache交互，在必要的時(shí)候從主存加載數(shù)據(jù)到Cache，或者將Cache中的數(shù)據(jù)刷入到主存。

3.2 Cache 工作原理

Cache 之所以能提高程序的速度，首先自然是因?yàn)樗鄬?duì)于主存更高的讀寫(xiě)速度。但同時(shí)由于 Cache 的容量有限，不可能緩存所有程序和數(shù)據(jù)，此時(shí) Cache 利用了程序執(zhí)行的 空間局部性(Spatial locality) 和 時(shí)間局部性(Temporal locality) 原理，來(lái)提高程序的性能。
空間局部性(Spatial locality) 是指緊鄰當(dāng)前位置訪問(wèn)的指令和數(shù)據(jù)，接下來(lái)本訪問(wèn)的可能性很大。
時(shí)間局部性(Temporal locality) 是指最近訪問(wèn)的指令和數(shù)據(jù)，在接下來(lái)短時(shí)間內(nèi)被訪問(wèn)的可能性很大。

3.3 Cache 層級(jí)架構(gòu)

下圖是一個(gè)典型的 ARMv7 架構(gòu)下，Cache 在內(nèi)存層級(jí)架構(gòu)中的位置，其它硬件架構(gòu)下的類(lèi)似，讀者可查找相關(guān)資料。

上面是典型的 哈佛總線 架構(gòu)下 Cache 層級(jí)組織。上圖中 第1級(jí) Cache(L1 cache) 的 數(shù)據(jù)cache(Data cache) 和 指令cache(Instruction cache) 是獨(dú)立的，第2級(jí)cache(L2 cache)，指令和數(shù)據(jù)使用同一cache空間，L2 cache 通過(guò) 總線(Bus) 和 主存空間(Main memory)進(jìn)行交互。
上圖只給出了一個(gè) CPU 核情況下的 cache 組織，對(duì)于多核情形下，ARMv8 架構(gòu)下典型的 cache 組織如下圖：

上圖中：

. 每個(gè) CPU Core ，有自身獨(dú)立的 L1 Cache( ARM架構(gòu)下，L1的指令和數(shù)據(jù)cache是獨(dú)立的，途中未有體現(xiàn))；
. 每個(gè) Cluster 有自己獨(dú)立的 L2 Cache，同一 Cluster 內(nèi)的所有 CPU Core，共享一個(gè) L2 Cache，；
. 所有 Cluster 內(nèi)的 CPU Core，共享同一個(gè) L3 Cache。

3.4 內(nèi)存架構(gòu)中各級(jí)訪問(wèn)速度概覽

從 3.3 小節(jié)中，我們了解到了包括 Cache 在內(nèi)的典型存儲(chǔ)架構(gòu)。下面通過(guò)一張圖，讓我們對(duì)存儲(chǔ)架構(gòu)中各級(jí)存儲(chǔ)的訪問(wèn)速度有個(gè)大概了解：

3.5 Cache 分類(lèi)

按照 處理器 取指操作 和 數(shù)據(jù)讀寫(xiě)操作，是否使用獨(dú)立的 指令 Cache 和 數(shù)據(jù) Cache ，可以將 Cache 分為 統(tǒng)一型 Cache(Unified Cache) 和 分離型 Cache(Separate cache) 。統(tǒng)一型 Cache(Unified Cache) 指令 和 數(shù)據(jù) 使用相同的 Cache； 分離型 Cache(Separate cache) 指令 和 數(shù)據(jù) 使用各自獨(dú)立的 Cache 。統(tǒng)一型 Cache(Unified Cache) 是 馮.諾伊曼架構(gòu)(Neumann architecture) 使用的模型； 分離型 Cache(Separate cache) 是 哈佛架構(gòu)(Harvard architecture) 使用的模型。
ARM 架構(gòu)下 Cache，使用 哈佛架構(gòu)(Harvard architecture) 的 分離型 Cache(Separate cache) 。

3.6 Cache 的 查找 和 組織方式

下圖給出了 ARMv7 架構(gòu)下的 Cache 組織形式：

上圖中涉及多個(gè) Cache 相關(guān)的術(shù)語(yǔ)，將在 3.5.1 小節(jié)中一一加以說(shuō)明。

3.6.1 Cache 組織相關(guān)術(shù)語(yǔ)

先介紹下 Cache 相關(guān)術(shù)語(yǔ) Way 和 Line ：

Way: 中文通常翻譯為 路，將 Cache 按容量平均分成 N 份，每一份稱(chēng)為一路(Way)，N 份就是 N 路(Way)。如一個(gè) 32KB 的 Cache ，分為4份，每份 32KB / 4 = 8KB ，每 8KB 為一路，總共有 4 路。
Line: Cache 行(Line)，Cache的每一路(Way)，包含多個(gè) Cache 行(Line)，每個(gè) Cache 行(Line)包含 多個(gè)Word 或 多個(gè)字節(jié)，所有的 Cache 行(Line)的長(zhǎng)度都是一樣的，常見(jiàn)的有 32 或 64 字節(jié)等。如一個(gè) 32KB Cache 分為 4 路，則每路為 8KB，如果 Cache 行的長(zhǎng)度為 64 字節(jié)，則每 8KB 大小的一路 Cache，將包含 8KB / 64 = 128 個(gè) Cache 行。由于所有 Cache 路 具有相同的容量，那自然所有的 Cache 路 都包含相同的 Cache 行 數(shù)目。Cache 行也是 和 主存 進(jìn)行交互的最小單位，即 每次從 主存 加載 到 Cache ，或者 將 Cache 數(shù)據(jù)刷回到 主存，都是以 Cache 行 為單位進(jìn)行的。

需要有一種方法，建立 主存地址塊 和 Cache 行 之間的映射關(guān)系，硬件通過(guò) 主存地址塊首地址，來(lái)建立 主存地址塊 和 Cache 行 之間的映射，如下圖(ARM32 架構(gòu)示例)：

上圖將 主存地址塊首地址，劃分為 Tag，Index，Offset 三部分。其中：

Tag: 用來(lái) 匹配 或者說(shuō) 標(biāo)記 一個(gè) Cache 行。每個(gè) Cache 行有額外的空間(圖中 Tag RAM)，用來(lái)存儲(chǔ)映射的主存內(nèi)存塊的首地址的 Tag ，這個(gè)額外 Tag 空間，不包含在 Cache 行的存儲(chǔ)空間(圖中 Data RAM)之內(nèi)。
Index: 每路 Cache 包含多個(gè) Cache 行，這些 Cache 行通過(guò) 主存地址的 Index 部分進(jìn)行索引。
Offset: 每個(gè) Cache 行包含 多個(gè)Word 或 多個(gè)字節(jié)。這些 Cache 行中的 Word 或 字節(jié)，通過(guò) Offset 進(jìn)行定位。

到此已經(jīng)基本介紹完了 3.5 開(kāi)頭部分圖片包含的、Cache 組織相關(guān)的術(shù)語(yǔ)，只剩下一個(gè) Set 的術(shù)語(yǔ)了，來(lái)看一下：

Set: 所有 Cache 路中，(對(duì)應(yīng)主存地址的) Index 相同的所有 Cache 行，稱(chēng)為 一組(Set)。組(Set)的數(shù)目對(duì)應(yīng)每路中 Cache 行的數(shù)目。如一個(gè) 32KB 的 Cache，分為 4 路，Cache 行大小為 64 字節(jié)，則每路 Cache 有 128 個(gè) Cache 行，也即有 128 組(Set)。

3.6.2 Cache 查找

3.6.2.1 Cache 查找過(guò)程概述

Cache 查找，是指根據(jù)數(shù)據(jù)的虛擬地址(VA：Virtual Address)和物理地址(PA：Physical Address)，定位到 數(shù)據(jù)對(duì)應(yīng) Cache 行(Line)內(nèi)的Word或字節(jié)偏移位置的過(guò)程。如果查找成功，則表示 Cache 命中(Cache Hit)，否則為 Cache 未命中(Cache Miss) 。
Cache 查找過(guò)程將數(shù)據(jù)地址分為如下圖的3部分進(jìn)行：

首先通過(guò)數(shù)據(jù)地址的 Index 部分，定位到 Cache 組(Set)，如 3.6 節(jié)開(kāi)始部分圖中所示 Set；然后比較 Cache 組(Set) 中的每個(gè) Cache 行(Line) 的 Tag 和 數(shù)據(jù)地址的 Tag 部分，如果 Tag 相等，則表示 Cache 命中(Cache Hit)，否則 Cache 未命中(Cache Miss) 。在 Cache 命中后，已經(jīng)定位到了 Cache 行，數(shù)據(jù)地址的 Offset 部分，最后用來(lái)定位數(shù)據(jù)在 Cache 行中的偏移位置。
下圖是一個(gè) 32KB，4 路(Way) 組相聯(lián) Cache 查找實(shí)現(xiàn)示例：

3.6.2.2 Cache 查找硬件實(shí)現(xiàn)

在 3.6.2.1 小節(jié)對(duì) Cache 查找過(guò)程的描述中，沒(méi)有具體交代 數(shù)據(jù)地址 是指的 虛擬地址(VA) 還是 物理地址(PA)。查找使用的 Tag，Index，Offset 可能來(lái)自于被 Cache 緩存數(shù)據(jù)的 虛擬地址(VA) 或 物理地址(PA)，常見(jiàn)的硬件實(shí)現(xiàn)有 VIVT，VIPT，PIPT：

o `VIVT(Virtually Indexed Virtually Tagged)``Tag` 來(lái)自于數(shù)據(jù)的虛擬地址(VA)，`Index` 來(lái)自于數(shù)據(jù)的虛擬地址(VA)，`Offset` 來(lái)自于數(shù)據(jù)的虛擬地址。o `VIPT(Virtually Indexed PhysicallyTagged)``Tag` 來(lái)自于數(shù)據(jù)的物理地址(PA)，`Index` 來(lái)自于數(shù)據(jù)的虛擬地址(VA)，`Offset` 來(lái)自于數(shù)據(jù)的虛擬地址(VA)。o `PIPT(Physically Indexed PhysicallyTagged)``Tag` 來(lái)自于數(shù)據(jù)的物理地址(PA)，`Index` 來(lái)自于數(shù)據(jù)的虛擬地址(PA)，`Offset` 來(lái)自于數(shù)據(jù)的虛擬地址(PA)。

3.6.3 Cache 的各種組織形式

本小節(jié)描述 Cache 的各種組織形式，以及它們各自的優(yōu)缺點(diǎn)。

3.6.3.1 直接映射(Direct Mapped)

直接映射 Cache(Direct Mapped Cache)，是指主存的每個(gè)位置，唯一映射到一個(gè) Cache 行。由于 Cache 的容量遠(yuǎn)小于主存的容量，所以會(huì)存在多個(gè)主存位置映射到同一 Cache 行的情形。 映射示例如下圖：

上圖中，Cache 只有1路(Way)，同時(shí)沒(méi)有分組(Set)，或者也可以認(rèn)為是只有1路1組的情形；Cache 行大小為 16 字節(jié)，Cache 總大小為 16x4 = 64 字節(jié)，總共 64/16 = 4 個(gè) Cache 行。Cache 行的分配如下：

o 主存地址塊 0x00000000, 0x00000040, 0x00000080, ... 映射到 Cache 的第 1 行
o 主存地址塊 0x00000010, 0x00000050, 0x00000090, ... 映射到 Cache 的第 2 行
o 主存地址塊 0x00000020, 0x00000060, 0x000000A0, ... 映射到 Cache 的第 3 行
o 主存地址塊 0x00000030, 0x00000070, 0x000000B0, ... 映射到 Cache 的第 4 行

假設(shè)使用 VIVT 查找實(shí)現(xiàn)，則 數(shù)據(jù)虛擬地址(VA) 的 劃分如下：

                          VA31                            6 5     4 3        0            --------------------------------------------------
|              Tag              | Index |  Offset  |--------------------------------------------------
VA[31:8]: Tag
VA[5:4] : Index
VA[3:0] : Offset

直接映射 Cache(Direct Mapped Cache) 的優(yōu)點(diǎn)點(diǎn)在于硬件實(shí)現(xiàn)簡(jiǎn)單、成本低；缺點(diǎn)在于容易造成 Cache 顛簸(thrashing)：前一數(shù)據(jù)剛被加載到某一 Cache 行，緊接著使用的數(shù)據(jù)又要使用相同的 Cache 行，這就使得前一數(shù)據(jù)剛加載到 Cache 行、立馬又被換出這個(gè) Cache 行，這樣就無(wú)法利用 Cache 帶來(lái)的速度優(yōu)勢(shì)。下面用一個(gè)例子代碼來(lái)說(shuō)明造成 Cache 顛簸的情形：

void add_array(int *data1, int *data2, int *result, int size)
{int i;for (i = 0; i < size; i++)result[i] = data1[i] + data2[i];
}

假設(shè)示例代碼中的 result，data1，data2 分別位于地址 0x00, 0x040, 0x80 ，并以前面圖 Figure 8-4所示進(jìn)行映射，那計(jì)算語(yǔ)句 result[i] = data1[i] + data2[i]; 會(huì)造成 3 次 cache 加載，因?yàn)?result[i]，data1[i]，data2[i] 映射到了同一 Cache 行，這種情形就是 Cache 顛簸。
在現(xiàn)代計(jì)算機(jī)上，沒(méi)再見(jiàn)過(guò)使用 直接映射 Cache(Direct Mapped Cache) 。

3.6.3.2 多路組相聯(lián)(N-Way Set-Associative)

多路組相聯(lián) Cache(N-Way Set-Associative Cache)，是指 將 Cache 按容量平均分成 N 份，稱(chēng)為 N 路(N-Way)；同時(shí)每路(Way) Cache 中，Index 相同的 Cache 行(Line) 形成一組(Set)，組(Set)的數(shù)目為一路(Way) Cache 包含的 Cache 行(Line)數(shù)。來(lái)看一個(gè)例子，有一 Cache，其容量為 128 字節(jié)，分為兩路，每路容量則為 128/2 = 64 字節(jié)，Cache 行的大小為 16 字節(jié)，所以每路 Cache 包含 64/16 = 4 個(gè) Cache 行，也即 Cache 組數(shù)為 4 組。這是一個(gè) 兩路組相聯(lián)的 Cache 。看一下圖示：

多路組相聯(lián) Cache(N-Way Set-Associative Cache)，是現(xiàn)代 Cache 實(shí)現(xiàn)的主流方式。

3.6.3.3 全相聯(lián)(Fully Associative)

全相聯(lián) Cache(Fully Associative Cache)，可以認(rèn)為是 多路組相聯(lián)(N-Way Set-Associative) 的一種特殊情形：任意的主存數(shù)據(jù)在 Cache 所有行都可進(jìn)行映射。這和 直接映射 Cache(Direct Mapped Cache) 的情形剛好相反，是 Cache 映射的另一種極端情況。
在實(shí)際應(yīng)用當(dāng)中，大于4路的組相聯(lián) L1 Cache，對(duì)性能提升很小；8路 或 16路 的組相聯(lián)，對(duì)于容量更大的 L2 Cache 會(huì)更有用。

3.6.4 Cache 查找相關(guān)問(wèn)題和解決方案

在不同的 Cache 查找策略下，在某些情形會(huì)引入 Cache 歧義 和 Cache 別名 問(wèn)題，下面將一一加以說(shuō)明。在正式開(kāi)始之前，首先要明晰的是：所有的討論都是基于對(duì)同一 Cache 的訪問(wèn)。 如對(duì)于多個(gè)不同 VA 映射到同一 PA 的情形，不同 VA 加載 PA 的數(shù)據(jù)到不同 CPU core 的 L1 Cache ，這就不是 Cache 別名問(wèn)題；只有同一 PA 數(shù)據(jù)加載到同一 Cache 的不同 Cache 行，這才是 Cache 別名。

3.6.4.1 Cache 歧義

一個(gè) 虛擬地址(VA)，可能映射到兩個(gè)不同的 物理地址(PA1,PA2)，典型的如進(jìn)程切換，如果當(dāng)前被調(diào)度出去的 進(jìn)程1 將 VA 映射到 PA1 ，同時(shí) Cache 緩存了 PA1 的數(shù)據(jù)在 Cache 行1；然后進(jìn)行進(jìn)程切換(假定不進(jìn)行 Cache Clean/Invalidate 操作)，切換到目標(biāo) 進(jìn)程2，目標(biāo) 進(jìn)程2 的 頁(yè)表(進(jìn)程切換會(huì)伴隨頁(yè)表切換)將 VA 映射到 PA2，接下來(lái) 進(jìn)程2 訪問(wèn) VA 映射的 PA2 數(shù)據(jù)，如果使用 VIVT(Virtually Indexed Virtually Tagged) Cache 查找方式，由于 進(jìn)程1 訪問(wèn) VA 時(shí) 將 PA1 數(shù)據(jù)加載到了 Cache 行1，所以 進(jìn)程2 用同一 VA 訪問(wèn) PA2 會(huì)命中 PA1 的數(shù)據(jù)，但是事實(shí)上，進(jìn)程2 應(yīng)該去訪問(wèn) PA2 的數(shù)據(jù)，這種情形，就是 Cache 歧義。
只有 VIVT 會(huì)引入 Cache 歧義，而 VIPT 和 PIPT 都不會(huì)引入 Cache 歧義，感興趣的讀者可以自行推導(dǎo)一下。

3.6.4.2 Cache 別名

多個(gè)不同的虛擬地址 (VA1,VA2,…) ，如果映射到同一個(gè) 物理地址 PA (如不同進(jìn)程間的共享內(nèi)存)，可能導(dǎo)致 同一 PA 地址的數(shù)據(jù)，被加載到多個(gè)不同 Cache 行的情形，就是所謂的 Cache 別名。Cache 別名 會(huì)導(dǎo)致 Cache 浪費(fèi)，以及潛在的數(shù)據(jù)不一致性。
各種 Cache 查找方式，除了 PIPT 外，VIVT 和 VIPT 在不同的情形下，都可能引發(fā) Cache 別名問(wèn)題。本小節(jié)接下來(lái)的討論，都假定兩個(gè)不同的虛擬地址 VA1,VA2，映射到了同一物理地址 PA 。
第一類(lèi) Cache 別名問(wèn)題是由 VIVT 下 Cache Index 的不唯一性 引發(fā)的 。假設(shè)有一個(gè) 8KB 的 直接映射(Direct Mapped) 的 Cache，那么 Cache 查找的 Index + Offset 兩部分需要 13-bit；同時(shí)假定內(nèi)存系統(tǒng)采用 4KB 大小的頁(yè)面，那么頁(yè)面內(nèi)偏移需要 12-bit 。當(dāng) VA1,VA2 映射到同一 PA 時(shí)，則一定有 VA1[11:0]==VA2[11:0] (即 頁(yè)面內(nèi)偏移位置相同) ，但 VA1[12]==VA2[12] 則不一定成立；如果 VA1[12] != VA2[12]，則意味著 VA1 和 VA2 的 Index 值不同 (VA[12]是Index的一位)，所以 VA1 和 VA2 會(huì)占據(jù)兩個(gè)不同的 Cache 行。
第二類(lèi) Cache 別名問(wèn)題是由 VIVT 下 Cache Tag 的不唯一性 引發(fā)的。假設(shè)有一個(gè) 8KB 兩路組相聯(lián) 的 Cache ，Cache 查找的 Index + Offset 兩部分需要 12-bit。當(dāng) VA1,VA2 映射到同一 PA 時(shí)，則一定有 VA1[11:0]==VA2[11:0] (即 頁(yè)面內(nèi)偏移位置相同) ，也即 VA1,VA2 Cache 查找的 Index 是相等的，這意味著 VA1,VA2 的 Cache 行位于同一組(Set)，但同時(shí)由于 VA1 != VA2，所以 VA1 和 VA2 的 Cache Tag 值不相等，這樣 VA1,VA2 映射的 PA 數(shù)據(jù)，會(huì)被加載同一 Cache 組中的不同路(Way) 的 Cache 行中，也就導(dǎo)致了 Cache 別名。
第三類(lèi) Cache 別名問(wèn)題是由 VIPT 下 Cache Index 的不唯一性 引發(fā)的。假設(shè)有一個(gè) 32KB 4路組相聯(lián) 的 Cache，那么 Cache 查找的 Index + Offset 兩部分需要 13-bit；同時(shí)假定內(nèi)存系統(tǒng)采用 4KB 大小的頁(yè)面，那么頁(yè)面內(nèi)偏移需要 12-bit 。當(dāng) VA1,VA2 映射到同一 PA 時(shí)，則一定有 VA1[11:0]==VA2[11:0] (即 頁(yè)面內(nèi)偏移位置相同) ，但 VA1[12]==VA2[12] 則不一定成立；如果 VA1[12] != VA2[12]，則意味著 VA1 和 VA2 的 Index 值不同 (VA[12]是Index的一位)，這樣 VA1,VA2 映射的 PA 數(shù)據(jù)，會(huì)被加載到 Cache 的不同 Cache 行中，也就是 Cache 別名。

3.6.4.3 Cache 歧義 和 別名 的解決方案

Cache 歧義 問(wèn)題，可以通過(guò) Cache Clean/Invalidate 操作避免。Cache Clean/Invalidate 操作的含義在后續(xù)章節(jié) 3.10 中進(jìn)行解釋。只有 VIVT 下才會(huì)發(fā)生 Cache 歧義，Cache Clean/Invalidate 的解決方式很低效，但好在現(xiàn)在沒(méi)有實(shí)現(xiàn)再用 VIVT 。
Cache 別名 問(wèn)題，我們只關(guān)注 VIPT 查找方式(VIVT 棄用，PIPT 不存在該問(wèn)題)。同時(shí)，本小節(jié)的后續(xù)討論，都是基于多個(gè)不同 VA 映射到 同一個(gè) PA 的前提下進(jìn)行的，這也是產(chǎn)生 Cache 別名問(wèn)題的必要條件。從 3.6.4.2 了解到，VIPT 下的別名問(wèn)題，是由于 Cache Index 的不唯一性 引起的，我們可以通過(guò) 將 Index + Offset 占用虛擬地址的位數(shù)，限定為 小于等于 虛擬地址頁(yè)面偏移所占用的位數(shù) 來(lái)避免。為什么？Cache 別名的根因，是多個(gè)不同 VA 映射到了同一 PA ，導(dǎo)致 Cache Index 可能的不同 引發(fā)的。如果我們消除那些 Cache Index 不同的情形，自然也就消除了 VIPT 的 Cache 別名問(wèn)題。那么哪些情形可能會(huì)導(dǎo)致不同 VA 的 Cache Index 不同？對(duì)比一下 虛擬地址 VA 的 Cache 映射 和 頁(yè)面映射：

 31                          S+1 S                0            --------------------------------------------------
|              Tag              | Index +  Offset  |  VA 的 Cache 映射--------------------------------------------------31                          P+1 P                0            --------------------------------------------------
|              頁(yè)表索引          |    Page Offset   |  VA 的 頁(yè)面映射--------------------------------------------------

看出點(diǎn)什么沒(méi)有？如果上圖中 S <= P ，在多個(gè) VA 映射到同一 PA 的前提下，則必定會(huì)有 VA[S:0]==VA[P:0] 成立，這意味著這些不同 VA 的 Cache Index 值相同；如果 S > P ，即劃分為 Cache Index + Offset 的比特?cái)?shù)，比用來(lái)作為頁(yè)面內(nèi)偏移 Page Offset 的比特?cái)?shù)要多，就有可能出現(xiàn)同一 PA 的不同 VA 的 Cache Index 不同的情形。因?yàn)椴煌?VA 映射到同一 PA ，只能保證 Cache 映射中 和 頁(yè)面映射 的 Page Offset 對(duì)應(yīng)部分的值是相同的。所以，消除 VIPT 的 Cache 別名，只需要保證上圖中的 S <= P 成立即可。也可以換成另一個(gè)說(shuō)法，要消除 VIPT 的 Cache 別名，只需要保證 Cache 路的容量 <= 內(nèi)存映射頁(yè)面容量 即可，因?yàn)樵?Cache 映射中的 Index + Offset 部分，就是描述的一路 Cache 的尋址范圍(Cache 路的容量 = 2 ^ S+1)；而 內(nèi)存頁(yè)面映射中的 Page Offset 部分就是尋址的一個(gè)頁(yè)面(內(nèi)存映射頁(yè)面容量 = 2 ^ P+1)。Cache 別名，本質(zhì)是因?yàn)?Cache 的映射方式 和 內(nèi)存頁(yè)面映射方式 的不一致造成的。

3.7 Cache 策略

3.7.1 Cache 分配策略

Cache 分配策略，是指在什么情形下分配 Cache 行。有 讀分配 和 寫(xiě)分配 兩種分配策略，下面一一加以說(shuō)明。

3.7.1.1 讀分配策略(read allocate)

當(dāng)且僅當(dāng)讀操作引發(fā) Cache Miss 時(shí)，才會(huì)分配 Cache 行。寫(xiě)操作 Cache Miss ，只會(huì)將 Cache 行數(shù)據(jù)寫(xiě)入到內(nèi)存架構(gòu)的下一級(jí)存儲(chǔ)(L2 Cache 或 主存)。

3.7.1.2 寫(xiě)分配策略(write allocate)

更準(zhǔn)確來(lái)說(shuō)，寫(xiě)分配策略(write allocate) 應(yīng)該叫 讀寫(xiě)分配策略(read-write allocate)。讀和寫(xiě)引發(fā)的 Cache Miss，都會(huì)分配 Cache 行。
寫(xiě)分配策略(write allocate) 通常搭配 Cache 寫(xiě)策略 write-back 一起使用。

3.7.2 Cache 替換策略

Cache Index 選擇 Cache 組(Set)；而 Cache 替換策略，用來(lái)決定選擇 Cache 組中的哪一個(gè) Cache 行(Line)。如果被替換的 Cache 當(dāng)前包含合法的(Valid)、臟(Dirty)數(shù)據(jù)，則在替換 Cache 行之前，必須先將 Cache 行的數(shù)據(jù)寫(xiě)回到主存。
Cache 替換策略 有 Round-robin，Pseudo-random，Last Recently Used(LRU) 三種，下面一一加以說(shuō)明。

3.7.2.1 Round-robin

輪流替換每路中的 Cache 行。在 Index 選定某個(gè) Cache 組后，依次替換組中各路的 Cache 行。如第1次替換某組第1路的 Cache 行，第2次替換某組第1路的 Cache 行，… 依次類(lèi)推，替換到某組的最后一路的 Cache 行后，將回卷到該組的第一路。

3.7.2.2 Pseudo-random

在 Index 選定某個(gè) Cache 組后，隨機(jī)選擇一路 Cache 的 Cache 行替換。

3.7.2.3 Last Recently Used(LRU)

在 Index 選定某個(gè) Cache 組后，替換組中最近最少使用的 Cache 行替換。

3.7.2.4 替換策略總結(jié)

大多數(shù) ARM 處理同時(shí)支持 Round-robin 和 Pseudo-random 兩種替換策略，Cortex-A15 支持 LRU 替換策略。
Round-robin 在某些情形下，會(huì)導(dǎo)致很差的性能，通常來(lái)講，Pseudo-random 會(huì)是更好的選擇。

3.7.3 Cache 寫(xiě)策略

Cache 寫(xiě)策略，是指當(dāng)寫(xiě)操作 Cache 命中時(shí)，所作出的數(shù)據(jù)更新策略：同步更新 Cache 和 主存(Write-through)，或 僅更新 Cache(Write-back)。

3.7.3.1 透寫(xiě)(Write-through)

數(shù)據(jù)同時(shí)寫(xiě)入到 Cache 和 主存。這意味著，Cache 和 主存 的數(shù)據(jù)保持一致。

3.7.3.2 回寫(xiě)(Write-back)

數(shù)據(jù)僅回寫(xiě)到 Cache，不回寫(xiě)到 主存。很顯然，Cache 和 主存 的數(shù)據(jù)會(huì)不一致。

3.8 Cache 和 主存之間寫(xiě)緩沖: Write buffer

為了加快 Cache 回寫(xiě)數(shù)據(jù)到主存的速度，在 Cache 和 主存之間，加入了 Write buffer，其大小通常是幾個(gè) Cache 行。這樣在將 Cache 數(shù)據(jù)回寫(xiě)到主存時(shí)，CPU 只需要給 Write buffer 提供一些信息(如數(shù)據(jù)地址，大小等)，發(fā)起回寫(xiě)請(qǐng)求后，就不需要等待回寫(xiě)操作完成，可以繼續(xù)執(zhí)行后續(xù)工作；而后 Write buffer 會(huì)在某個(gè)時(shí)間點(diǎn)完成回寫(xiě)操作。
有的 Write buffer 實(shí)現(xiàn)，還支持多個(gè)回寫(xiě)請(qǐng)求的合并，即 write merging，又叫做 write combining。write merging 將多個(gè)回寫(xiě)操作合并成單個(gè)操作，這樣可以減少和主存間交互，提高性能。但 write merging 并不總是可行的，譬如與外設(shè)的數(shù)據(jù)交互，可能需要即時(shí)完成。
有回寫(xiě)的 Write buffer，自然也有為提高效率的預(yù)取緩沖，如用來(lái) 指令 prefetch buffer 等。

3.9 Cache 維護(hù)操作

3.9.1 Cache invalidate

Cache invalidate 是指清除一個(gè)或多個(gè) Cache 行的 Valid 位，Cache 行的數(shù)據(jù)將丟失。如果被清除的 Cache 行包含合法數(shù)據(jù)，通常應(yīng)該先將數(shù)據(jù)刷回主存，然后再執(zhí)行清除操作。當(dāng)然如果不關(guān)心這些數(shù)據(jù)自然就沒(méi)所謂了。
在復(fù)位后，所有的 Cache 行都處于被 Invalidate 了的狀態(tài)。

3.9.2 Cache clean

Cache clean 是指將包含臟(Dirty)數(shù)據(jù)的Cache行回寫(xiě)到主存，并清除 Cache 行的 Valid 位。

3.9.3 Cache flush

通常沒(méi)有對(duì) Cache flush 給出正式定義，通常所說(shuō)的 Cache flush 是指 Cache invalidate + Cache clean。

3.9.4 Cache lockdown

Cache 隨著代碼和數(shù)據(jù)的運(yùn)行，會(huì)被分配到不同位置的代碼和數(shù)據(jù)，這導(dǎo)致 Cache 對(duì)性能的提升呈現(xiàn)抖動(dòng)(不穩(wěn)定)?？梢酝ㄟ^(guò)鎖定(lockdown)一些關(guān)鍵代碼和數(shù)據(jù)的 Cache 行，這些被鎖定的 Cache 行，后續(xù)不再參加重新分配，這使得這些映射到被鎖定 Cache 行的代碼和數(shù)據(jù)穩(wěn)定，呈現(xiàn)出穩(wěn)定的性能提升。
ARM架構(gòu)支持 Format A，Format B，Format C，Format D 4種格式的 Cache 鎖定機(jī)制，更多相關(guān)細(xì)節(jié)，可參考 ARM 官方手冊(cè)，本文不做更多展開(kāi)。

3.9.5 Cache 操作的目標(biāo)或范圍

Cache 操作可按 Cache 組(Set)、Cache 路(Way)、虛擬地址 實(shí)施。

3.10 Cache 性能 和 命中率

要利用 Cache 提高性能，說(shuō)到底是利用程序執(zhí)行的時(shí)空局限性，盡力的提高 Cache 命中率。一直在說(shuō) Cache 命中率，到底什么是 Cache 命中率？Cache 命中率 是指在一定時(shí)間內(nèi)，Cache 命中的次數(shù)，通常表示為一個(gè)百分比。
對(duì)于提高 Cache 命中率(也即提高 Cache 性能)，有一些通用性的規(guī)則和建議：

. 將近期訪問(wèn)的數(shù)據(jù)和代碼，盡量讓它們?cè)诘刂房臻g上相鄰
. 更小的數(shù)據(jù)和更小的代碼
. 盡量將熱點(diǎn)代碼和數(shù)據(jù)組織到相鄰位置
. 避免cache行的偽共享：把沒(méi)有依賴(lài)關(guān)系的數(shù)據(jù)，放到不同的 Cache 行，避免寫(xiě)數(shù)據(jù)時(shí)無(wú)謂的Cache同步操作
. 保持?jǐn)?shù)據(jù)對(duì)齊到 cache 行

3.11 內(nèi)存的 Cache 屬性

ARM架構(gòu)下，將內(nèi)存分為如下三種類(lèi)型：

Normal: 如果標(biāo)記為共享類(lèi)型(Shareable)，則可被多個(gè)CPU核訪問(wèn)，數(shù)據(jù)可被Cache緩存(Cacheable)；如果標(biāo)記為非共享類(lèi)型(Non-shareable)，則只能被指定的某個(gè)CPU和訪問(wèn)，數(shù)據(jù)可被Cache緩存。
Device: 數(shù)據(jù)不能被 Cache 緩存。數(shù)據(jù)的訪問(wèn)遵循編程順序。
Strongly-ordered: 數(shù)據(jù)不能被 Cache 緩存。數(shù)據(jù)的訪問(wèn)遵循編程順序。

我們僅關(guān)注和 Cache 相關(guān)部分，只有 Normal 類(lèi)型的內(nèi)存，是可被 Cache 緩存。這些相關(guān)細(xì)節(jié)，可以在后面的章節(jié) 4. 里看到。

3.12 Cache 一致性

即使跳過(guò) Cache 歧義 和 別名 的坑，Cache 帶來(lái)的也不只是性能的提升，同樣也帶來(lái)了其它麻煩。當(dāng)多個(gè)不同的 CPU 核訪問(wèn)相同的主存位置，會(huì)將數(shù)據(jù)加載到 CPU 核各自的緩存中，如果其中一個(gè) CPU 核更新了緩存(假設(shè)寫(xiě)策略使用 write-back)，那另一個(gè) CPU 核可能看不到最新的數(shù)據(jù)版本，這就是 Cache 一致性問(wèn)題。當(dāng)然，不僅不同 CPU 核之間對(duì)數(shù)據(jù)的訪問(wèn)存在一致性問(wèn)題，CPU 和 外設(shè)之間的協(xié)同數(shù)據(jù)訪問(wèn)，也存在一致性問(wèn)題。
本文不打算對(duì) Cache 一致性 做更多展開(kāi)，未來(lái)可能會(huì)單獨(dú)寫(xiě)一篇關(guān)于 ARM Cache 一致性 MESI 協(xié)議 的學(xué)習(xí)文章。

3.13 Cache 和 存儲(chǔ)模型

(待續(xù))

3.14 地址翻譯 Cache: TLB

3.14.1 什么是 TLB ?

TLB 是 Translation Lookaside Buffer 的縮寫(xiě)，是 MMU(Memory Management Unit) 在執(zhí)行地址翻譯過(guò)程中，緩存最近地址翻譯數(shù)據(jù)的一塊 Cache。在需要進(jìn)行地址翻譯時(shí)，首先從 TLB 緩存查找，如果命中則直接使用 TLB 緩存結(jié)果，不必再執(zhí)行整個(gè)地址翻譯過(guò)程。

TLB 緩存包含多條 地址翻譯數(shù)據(jù) 的緩存，每條 TLB 緩存的結(jié)構(gòu)大體如下：

3.14.2 TLB 維護(hù)操作

TLB 支持 使能(Enable)、使無(wú)效(Invalidate) 等操作。系統(tǒng)復(fù)位時(shí)，所有的 TLB 表項(xiàng)處于禁用狀態(tài)，此時(shí)要使用 TLB ，需要先對(duì) TLB 表項(xiàng)進(jìn)行 Invalidate 操作，然后再使能。

3.14.3 TLB 刷新

在進(jìn)程切換時(shí)，會(huì)伴隨著頁(yè)表的切換，此時(shí) TLB 中緩存著舊進(jìn)程的虛擬地址翻譯數(shù)據(jù)，如果不進(jìn)行清理，新進(jìn)程會(huì)在相同虛擬地址下命中這些翻譯數(shù)據(jù)，從而訪問(wèn)錯(cuò)誤的物理地址。為了避免這種問(wèn)題，在進(jìn)程切換時(shí)需要刷新整個(gè) TLB，這很低效，事實(shí)上，我們只需要清理那些進(jìn)程特定的 TLB 表項(xiàng)，那些全局共享的地址空間對(duì)應(yīng)的 TLB 表項(xiàng)，完全沒(méi)必要進(jìn)行清理。鑒于此，引入了 ASID(Address Space ID) 和 頁(yè)表項(xiàng)的 nG(not Global) 比特位。對(duì)于每個(gè)進(jìn)程，系統(tǒng)為其分配一個(gè)唯一的 ASID，同時(shí)將特定于進(jìn)程頁(yè)表項(xiàng)的 nG 比特位設(shè)為1，標(biāo)識(shí)該頁(yè)表項(xiàng)是特定于特定進(jìn)程的；同時(shí)對(duì)于這些特定于進(jìn)程的 TLB 表項(xiàng)，同樣也用進(jìn)程 ASID 和 nG 進(jìn)行標(biāo)記。這樣在進(jìn)行 TLB 查找時(shí)，通過(guò) ASID 和 nG 區(qū)分是不是進(jìn)程特定的表項(xiàng)，提高效率；切換進(jìn)程時(shí)，也可以只清理那些不屬于新進(jìn)程的、非全局(nG=0) TLB 表項(xiàng)。當(dāng)然，要有位置記錄當(dāng)前進(jìn)程的 ASID，ARM 設(shè)計(jì)有用于記錄當(dāng)前進(jìn)程 ASID 的寄存器。
ARM 架構(gòu)下，ASID 用 8-bit 或 16-bit 進(jìn)行標(biāo)識(shí)，所以能分配的 ASID 是有限的，如果當(dāng)前可分配的 ASID 消耗完了，那需要刷掉 TLB 中所有進(jìn)程特定的表項(xiàng)，重新來(lái)過(guò)。

4. Linux 下的 Cache

Cache 的實(shí)現(xiàn)，和具體的硬件架構(gòu)和硬件設(shè)計(jì)緊密相關(guān)，因此 Linux 下 Cache 相關(guān)代碼也隨著具體硬件實(shí)現(xiàn)而不同。本文僅就 ARMv7 架構(gòu)下 Cortex A7 相關(guān)代碼進(jìn)行分析。

4.1 Cache 初始化

在內(nèi)核啟動(dòng)階段，會(huì)進(jìn)行 Cache 相關(guān)的初始化。先來(lái)看一下內(nèi)核中 Cortex A7 處理器的配置數(shù)據(jù)：

/* arch/arm/mm/proc-v7.S *//** ARM Ltd. Cortex A7 processor.*/.type __v7_ca7mp_proc_info, #object 
__v7_ca7mp_proc_info:.long 0x410fc070 /* proc_info_list::cpu_val */.long 0xff0ffff0 /* proc_info_list::cpu_mask */__v7_proc __v7_ca7mp_proc_info, __v7_ca7mp_setup.size __v7_ca7mp_proc_info, . - __v7_ca7mp_proc_info

匯編代碼 .type __v7_ca7mp_proc_info, #object 定義了一個(gè) struct proc_info_list 結(jié)構(gòu)體數(shù)據(jù)，struct proc_info_list 的定義如下：

/* arch/arm/include/asm/procinfo.h */struct proc_info_list {unsigned int  cpu_val; /* 處理器 ID (寄存器)值 */unsigned int  cpu_mask; /* 處理器 ID 掩碼 */unsigned long  __cpu_mm_mmu_flags; /* used by head.S */ /* MMU 相關(guān)配置，包括 Cache 配置 */unsigned long  __cpu_io_mmu_flags; /* used by head.S */unsigned long  __cpu_flush;  /* used by head.S */ // __v7_ca7mp_setup()const char  *arch_name;const char  *elf_name;unsigned int  elf_hwcap;const char  *cpu_name;struct processor *proc; // &v7_processor_functionsstruct cpu_tlb_fns *tlb; // &v7wbi_tlb_fnsstruct cpu_user_fns *user; // &v6_user_fns struct cpu_cache_fns *cache; // &v7_cache_fns
};

這里只重點(diǎn)關(guān)注結(jié)構(gòu)體成員 __cpu_mm_mmu_flags 中 Cache 相關(guān)的設(shè)置。前面的匯編代碼中，__v7_proc 是一個(gè)匯編宏，定義了結(jié)構(gòu)體 struct proc_info_list 中除 cpu_val，cpu_mask 外的其它成員的值：

/* arch/arm/mm/proc-v7.S */.section ".rodata"string cpu_arch_name, "armv7"string cpu_elf_name, "v7".section ".proc.info.init", #alloc /* 將所有定義的 struct proc_info_list 鏈接到 .proc.info.init 輸出段中 *//** Standard v7 proc info content*/
.macro __v7_proc name, initfunc, mm_mmuflags = 0, io_mmuflags = 0, hwcaps = 0, proc_fns = v7_processor_functionsALT_SMP(.long PMD_TYPE_SECT | PMD_SECT_AP_WRITE | PMD_SECT_AP_READ | \PMD_SECT_AF | PMD_FLAGS_SMP | \mm_mmuflags) /* unsigned long  __cpu_mm_mmu_flags; */.long PMD_TYPE_SECT | PMD_SECT_AP_WRITE | \PMD_SECT_AP_READ | PMD_SECT_AF | \io_mmuflags /* unsigned long  __cpu_io_mmu_flags; */initfn \initfunc, \name /* unsigned long  __cpu_flush; ==> __v7_ca7mp_setup */.long cpu_arch_name /* const char  *arch_name; ==> "armv7" */.long cpu_elf_name /* const char  *elf_name; ==> "v7" */.long HWCAP_SWP | HWCAP_HALF | HWCAP_THUMB | HWCAP_FAST_MULT | \HWCAP_EDSP | HWCAP_TLS | \hwcaps /* unsigned int  elf_hwcap; */.long cpu_v7_name /* const char  *cpu_name; ==> "ARMv7 Processor" */.long \proc_fns /* struct processor *proc; ==> v7_processor_functions */.long v7wbi_tlb_fns /* struct cpu_tlb_fns *tlb; ==> v7wbi_tlb_fns */.long v6_user_fns /* struct cpu_user_fns *user; ==> v6_user_fns */.long v7_cache_fns /* struct cpu_cache_fns *cache; ==> v7_cache_fns */
.endmstring cpu_v7_name, "ARMv7 Processor".../* * 處理器操作接口定義：* struct processor v7_processor_functions = {* 	._data_abort = v7_early_abort,* 	._prefetch_abort = v7_pabort,* 	._proc_init = cpu_v7_proc_init,* 	.check_bugs = cpu_v7_bugs_init,* 	._proc_fin = cpu_v7_proc_fin,* 	.reset = cpu_v7_reset,* 	._do_idle = cpu_v7_do_idle,* 	.dcache_clean_area = cpu_v7_dcache_clean_area,* 	.switch_mm = cpu_v7_switch_mm,* 	.set_pte_ext = cpu_v7_set_pte_ext,* 	.suspend_size = cpu_v7_suspend_size,* 	.do_suspend = cpu_v7_do_suspend,* 	.do_resume = cpu_v7_do_resume,* };* struct processor 結(jié)構(gòu)體 定義在文件 arch/arm/include/asm/proc-fns.h 中。*/@ define struct processor (see <asm/proc-fns.h> and proc-macros.S)define_processor_functions v7, dabort=v7_early_abort, pabort=v7_pabort, suspend=1, bugs=cpu_v7_bugs_init

/* arch/arm/mm/tlb-v7.S *//** TLB 操作接口 定義：* struct cpu_tlb_fns v7wbi_tlb_fns = {* 	.flush_user_range = v7wbi_flush_user_tlb_range,* 	.flush_kern_range = v7wbi_flush_kern_tlb_range,* 	.tlb_flags = v7wbi_tlb_flags_smp,* };* struct cpu_tlb_fns 結(jié)構(gòu)體 定義在文件 arch/arm/include/asm/tlbflush.h 中。*//* define struct cpu_tlb_fns (see <asm/tlbflush.h> and proc-macros.S) */define_tlb_functions v7wbi, v7wbi_tlb_flags_up, flags_smp=v7wbi_tlb_flags_smp

/* arch/arm/mm/copypage-v6.c */struct cpu_user_fns v6_user_fns __initdata = {.cpu_clear_user_highpage = v6_clear_user_highpage_nonaliasing,.cpu_copy_user_highpage = v6_copy_user_highpage_nonaliasing,
};

/* arch/arm/mm/cache-v7.S *//* * 處理器 Cache (L1 Cache) 操作接口定義: * struct cpu_cache_fns v7_cache_fns = {*	.flush_icache_all = v7_flush_icache_all,*	.flush_kern_all = v7_flush_kern_cache_all,*	.flush_kern_louis = v7_flush_kern_cache_louis,*	.flush_user_all = v7_flush_user_cache_all,*	.flush_user_range = v7_flush_user_cache_range,*	.coherent_kern_range = v7_coherent_kern_range,*	.coherent_user_range = v7_coherent_user_range,*	.flush_kern_dcache_area = v7_flush_kern_dcache_area,*	.dma_map_area = v7_dma_map_area,*	.dma_unmap_area = v7_dma_unmap_area,*	.dma_flush_range = v7_dma_flush_range,* };* struct cpu_cache_fns 結(jié)構(gòu)體 定義在文件 arch/arm/include/asm/cacheflush.h 中。*/
@ define struct cpu_cache_fns (see <asm/cacheflush.h> and proc-macros.S)
define_cache_functions v7

上面已經(jīng)給出了所有 Cache 相關(guān)接口的定義，接下來(lái)看 Cache 的初始化過(guò)程。進(jìn)入內(nèi)核時(shí)，系統(tǒng)先將 L1 Cache 置于無(wú)效狀態(tài)：

/* 內(nèi)核入口 */__HEAD
ENTRY(stext)...mrc p15, 0, r9, c0, c0  @ get processor idbl __lookup_processor_type  @ r5=procinfo r9=cpuidmovs r10, r5    @ invalid processor (r5=0)? /* r10: 處理器信息指針 (struct proc_info_list *) */...bl __create_page_tables // 內(nèi)核初始頁(yè)表建立，以及頁(yè)表相關(guān) Cache 屬性配置.../* 處理器初始化，包括 Invalidate 所有 L1 Cache */ldr r12, [r10, #PROCINFO_INITFUNC]add r12, r12, r10ret r12 /* CPU 初始化: __v7_ca7mp_setup */....
ENDPROC(stext)__create_page_tables: // 內(nèi)核初始頁(yè)表建立，以及頁(yè)表相關(guān) Cache 屬性配置ldr r7, [r10, #PROCINFO_MM_MMUFLAGS] @ mm_mmuflags (struct proc_info_list::__cpu_mm_mmu_flags, Cache 配置)...1: 	orr r3, r7, r5, lsl #SECTION_SHIFT @ flags + kernel base (配置頁(yè)表項(xiàng)屬性，包括 Cache 屬性 (PMD_FLAGS_SMP))str r3, [r4, r5, lsl #PMD_ORDER] @ identity mappingcmp r5, r6addlo r5, r5, #1   @ next sectionblo 1b

/* arch/arm/mm/proc-v7.S */__v7_ca7mp_setup:.../* arch/arm/mm/cache-v7.S: v7_invalidate_l1() */bl      v7_invalidate_l1 /* 使 L1 Cache 所有 Set/Way 中的 Cache 行無(wú)效 (Invalidate) */...b __v7_setup_cont...__v7_setup_cont:.../* 使 L1 指令 Cache 無(wú)效 */mcr p15, 0, r10, c7, c5, 0  @ I+BTB cache invalidate
#ifdef CONFIG_MMU/* 使所有 TLB 無(wú)效 */mcr p15, 0, r10, c8, c7, 0  @ invalidate I + D TLBs/* 配置頁(yè)表基地址到 TTBRx 寄存器 */v7_ttb_setup r10, r4, r5, r8, r3 @ TTBCR, TTBRx setup/* 內(nèi)存區(qū)域的 類(lèi)型 和 屬性 寄存器配置 (包括 是否可以加載到 Cache，Cache 的分配、寫(xiě)策略) */ldr r3, =PRRR   @ PRRRldr r6, =NMRR   @ NMRRmcr p15, 0, r3, c10, c2, 0  @ write PRRRmcr p15, 0, r6, c10, c2, 1  @ write NMRR
#endifdsb     @ Complete invalidations/* 設(shè)置 Cache 替換策略，I & D Cache 使能 比特位 (后續(xù)在 __turn_mmu_on 中寫(xiě)入到 SCTLR 寄存器，使配置生效) */adr r3, v7_crval /* ARMv7 的 SCTLR 配置(包括 Cache 配置) */ldmia r3, {r3, r6}mrc p15, 0, r0, c1, c0, 0  @ read control register (r0 = SCTLR)bic r0, r0, r3   @ clear bits themorr r0, r0, r6   @ set them/* 返回到 head.S: stext 中 1: b __enable_mmu 處 */ret lr    @ return to head.S:__ret

/* arch/arm/kernel/head.S */__enable_mmu:...b __turn_mmu_on__turn_mmu_on:...mcr p15, 0, r0, c1, c0, 0 /* 啟用 當(dāng)前 CPU 的 MMU，以及 Cache 等其它配置 (r0 的值在前面 __v7_setup_cont 中設(shè)置) */.../** BOOT CPU: 返回到 __mmap_switched 處* 非 BOOT CPU: 返回到 __secondary_switched 處** BOOT CPU: TTBR0 = TTBR1 = swapper_pg_dir* 非 BOOT CPU: TTBR0 = idmap_pgd(用于等同映射代碼), TTBR1 = swapper_pg_dir ???*/ret r3

/* arch/arm/kernel/head-common.S */__mmap_switched:adr r3, __mmap_switched_data /* r3 = __mmap_switched_data 虛擬地址 */.../** r4 = &processor_id (arch/arm/kernel/setup.c)* r5 = &__machine_arch_type (arch/arm/kernel/setup.c)* r6 = &__atags_pointer (arch/arm/kernel/setup.c)* r7 = &cr_alignment (arch/arm/kernel/entry-armv.S)* sp = 當(dāng)前 CPU 的 swapper 進(jìn)程內(nèi)核棧指針*/ARM( ldmia r3, {r4, r5, r6, r7, sp})/* processor_id = 處理器 ID */str r9, [r4]   @ Save processor ID/* __machine_arch_type = machine no */str r1, [r5]   @ Save machine type/* __atags_pointer = DTB 物理地址 */str r2, [r6]   @ Save atags pointercmp r7, #0/* cr_alignment = CP15 控制寄存器 SCTLR 的當(dāng)前配置值 */strne r0, [r7]   @ Save control register valuesb start_kernel /* 跳轉(zhuǎn)到 start_kernel() 執(zhí)行 */

進(jìn)入start_kernel() 后，按上面定義的 struct proc_info_list::__cpu_mm_mmu_flags 里，Cache 相關(guān)的配置進(jìn)行 Cache 初始化：

start_kernel()setup_arch(&command_line)setup_processor()

/* arch/arm/kernel/setup.c */static void __init setup_processor(void)
{unsigned int midr = read_cpuid_id(); /* 讀取 CPU ID *//* 找到預(yù)定義的、和 CPU ID 匹配的處理器對(duì)象(struct proc_info_list) */struct proc_info_list *list = lookup_processor(midr); /* arch/arm/mm/proc-v7.S: &__v7_ca7mp_proc_info */...
#ifdef MULTI_TLBcpu_tlb = *list->tlb; /* 設(shè)置 TLB 操作接口 */
#endif...
#ifdef MULTI_CACHEcpu_cache = *list->cache; /* 設(shè)置 cache 操作接口 */
#endifpr_info("CPU: %s [%08x] revision %d (ARMv%s), cr=%08lx\n",list->cpu_name, midr, midr & 15,proc_arch[cpu_architecture()], get_cr());...#ifdef CONFIG_MMU/** 設(shè)置 cache 讀寫(xiě)、分配 策略到 @cachepolicy:* 按 CPU 的 MMU 配置 (list->__cpu_mm_mmu_flags), 從策略表 cache_policies[] * 中，找到匹配 (list->__cpu_mm_mmu_flags) 的 cache 策略，設(shè)定為默認(rèn)的 cache 策略： * (write back, write through, non-cachable, bufferable, ...)* 設(shè)置到 @cachepolicy 。 */init_default_cache_policy(list->__cpu_mm_mmu_flags);
#endif.../* 設(shè)置 cache 查找策略到 @cacheid */cacheid_init();...
}

/* arch/arm/mm/mmu.c *//* ARM32 架構(gòu)支持的 cache 讀寫(xiě)、分配 策略 */
static struct cachepolicy cache_policies[] __initdata = {{.policy		= "uncached",.cr_mask	= CR_W|CR_C,.pmd		= PMD_SECT_UNCACHED,.pte		= L_PTE_MT_UNCACHED,.pte_s2		= s2_policy(L_PTE_S2_MT_UNCACHED),}, {.policy		= "buffered",.cr_mask	= CR_C,.pmd		= PMD_SECT_BUFFERED,.pte		= L_PTE_MT_BUFFERABLE,.pte_s2		= s2_policy(L_PTE_S2_MT_UNCACHED),}, {.policy		= "writethrough",.cr_mask	= 0,.pmd		= PMD_SECT_WT,.pte		= L_PTE_MT_WRITETHROUGH,.pte_s2		= s2_policy(L_PTE_S2_MT_WRITETHROUGH),}, {.policy		= "writeback",.cr_mask	= 0,.pmd		= PMD_SECT_WB,.pte		= L_PTE_MT_WRITEBACK,.pte_s2		= s2_policy(L_PTE_S2_MT_WRITEBACK),}, {.policy		= "writealloc",.cr_mask	= 0,.pmd		= PMD_SECT_WBWA,.pte		= L_PTE_MT_WRITEALLOC,.pte_s2		= s2_policy(L_PTE_S2_MT_WRITEBACK),}
};.../* 設(shè)置 cache 讀寫(xiě)、分配 策略到 @cachepolicy */
void __init init_default_cache_policy(unsigned long pmd)
{int i;initial_pmd_value = pmd;pmd &= PMD_SECT_CACHE_MASK;for (i = 0; i < ARRAY_SIZE(cache_policies); i++)if (cache_policies[i].pmd == pmd) {cachepolicy = i;break;}if (i == ARRAY_SIZE(cache_policies))pr_err("ERROR: could not find cache policy\n");
}

/* 設(shè)置 cache 查找策略到 @cacheid */
static void __init cacheid_init(void)
{unsigned int arch = cpu_architecture();if (arch >= CPU_ARCH_ARMv6) { /* Armv6, Armv7 架構(gòu) */unsigned int cachetype = read_cpuid_cachetype();if ((arch == CPU_ARCH_ARMv7M) && !(cachetype & 0xf000f)) { /* Cortex-M 系列、不支持 cache 的 CPU */cacheid = 0;}  else if ((cachetype & (7 << 29)) == 4 << 29) { /* Armv7 架構(gòu) *//* ARMv7 register format */arch = CPU_ARCH_ARMv7;cacheid = CACHEID_VIPT_NONALIASING;switch (cachetype & (3 << 14)) {case (1 << 14):cacheid |= CACHEID_ASID_TAGGED;break;case (3 << 14):cacheid |= CACHEID_PIPT;break;}}  else { /* Armv6 架構(gòu) */arch = CPU_ARCH_ARMv6;if (cachetype & (1 << 23))cacheid = CACHEID_VIPT_ALIASING;elsecacheid = CACHEID_VIPT_NONALIASING;}} else { /* Armv6 之前的架構(gòu)，使用 VIVT cache 查找策略 */cacheid = CACHEID_VIVT;}pr_info("CPU: %s data cache, %s instruction cache\n",cache_is_vivt() ? "VIVT" :cache_is_vipt_aliasing() ? "VIPT aliasing" :cache_is_vipt_nonaliasing() ? "PIPT / VIPT nonaliasing" : "unknown",cache_is_vivt() ? "VIVT" :icache_is_vivt_asid_tagged() ? "VIVT ASID tagged" :icache_is_vipt_aliasing() ? "VIPT aliasing" :icache_is_pipt() ? "PIPT" :cache_is_vipt_nonaliasing() ? "VIPT nonaliasing" : "unknown");
}

4.2 Cache 代碼文件組織

按 Cache 層級(jí)結(jié)構(gòu)，簡(jiǎn)單說(shuō)明下各級(jí) Cache 功能相關(guān)實(shí)現(xiàn)代碼文件。

L1 Cache:arch/arm/include/asm/glue-cache.h
arch/arm/include/asm/cacheflush.h
arch/arm/mm/cache-v7.S
arch/arm/mm/flush.c

L2 Cache:arch/arm/mm/cache-l2*.c

TLB:arch/arm/include/asm/tlbflush.h
arch/arm/kernel/smp_tlb.c
arch/arm/mm/tlb-v7.S

4.3 Cache 操作接口 和 范例

// arch/arm/include/asm/cacheflush.h/** Select the calling method*/
#ifdef MULTI_CACHEextern struct cpu_cache_fns cpu_cache;#define __cpuc_flush_icache_all		cpu_cache.flush_icache_all
#define __cpuc_flush_kern_all		cpu_cache.flush_kern_all
#define __cpuc_flush_kern_louis		cpu_cache.flush_kern_louis
#define __cpuc_flush_user_all		cpu_cache.flush_user_all
#define __cpuc_flush_user_range		cpu_cache.flush_user_range
#define __cpuc_coherent_kern_range	cpu_cache.coherent_kern_range
#define __cpuc_coherent_user_range	cpu_cache.coherent_user_range
#define __cpuc_flush_dcache_area	cpu_cache.flush_kern_dcache_area#define dmac_flush_range		cpu_cache.dma_flush_range#else
...
#endif.../** Flush caches up to Level of Unification Inner Shareable*/
#define flush_cache_louis()		__cpuc_flush_kern_louis()#define flush_cache_all()		__cpuc_flush_kern_all()static inline void
vivt_flush_cache_range(struct vm_area_struct *vma, unsigned long start, unsigned long end)
{...
}static inline void
vivt_flush_cache_page(struct vm_area_struct *vma, unsigned long user_addr, unsigned long pfn)
{...
}#ifndef CONFIG_CPU_CACHE_VIPT
#define flush_cache_mm(mm) \vivt_flush_cache_mm(mm)
#define flush_cache_range(vma,start,end) \vivt_flush_cache_range(vma,start,end)
#define flush_cache_page(vma,addr,pfn) \vivt_flush_cache_page(vma,addr,pfn)
#else
...
#endif#define flush_cache_user_range(s,e)	__cpuc_coherent_user_range(s,e)#define flush_icache_range(s,e)		__cpuc_coherent_kern_range(s,e)#define clean_dcache_area(start,size)	cpu_dcache_clean_area(start, size)

使用 Cache 接口可能存在不同的形式，有的是通過(guò)架構(gòu) cacheflush.h 提供的接口、間接調(diào)用架構(gòu)底層實(shí)現(xiàn)進(jìn)行 Cache 操作，有的是直接調(diào)用架構(gòu)實(shí)現(xiàn)的底層接口，這里各給出一個(gè)示例：

// 使用 cacheflush.h 提供的接口remap_pfn_range()...flush_cache_range()...

// 直接使用架構(gòu)底層接口dma_sync_single_for_cpu()arm_dma_sync_single_for_cpu()__dma_page_dev_to_cpu()if (dir != DMA_TO_DEVICE) { // DMA: 數(shù)據(jù)方向?yàn)?從 設(shè)備 到 CPUouter_inv_range(paddr, paddr + size) // 將內(nèi)存區(qū)間對(duì)應(yīng)的 L2 cache line 級(jí) cache 置為無(wú)效 (Invalidate)dma_cache_maint_page(page, off, size, dir, dmac_unmap_area)v7_dma_unmap_area() // 將內(nèi)存區(qū)間對(duì)應(yīng)的 L1 cache line 置為無(wú)效(Invalidate)}

接下來(lái)看 TLB 的操作接口 和 范例：

// arch/arm/include/asm/tlbflush.h...#ifndef CONFIG_SMP
...
#else
extern void flush_tlb_all(void);
extern void flush_tlb_mm(struct mm_struct *mm);
extern void flush_tlb_page(struct vm_area_struct *vma, unsigned long uaddr);
extern void flush_tlb_kernel_page(unsigned long kaddr);
extern void flush_tlb_range(struct vm_area_struct *vma, unsigned long start, unsigned long end);
extern void flush_tlb_kernel_range(unsigned long start, unsigned long end);
extern void flush_bp_all(void);
#endif...

進(jìn)程切換時(shí)，會(huì)進(jìn)行 TLB 操作：

/* kernel/sched/core.c */schedule()__schedule(false)rq = context_switch(rq, prev, next, &rf); /* 進(jìn)程上下文切換 */struct mm_struct *mm, *oldmm;...mm = next->mm;oldmm = prev->active_mm;...if (!mm) {next->active_mm = oldmm;mmgrab(oldmm);enter_lazy_tlb(oldmm, next);} elseswitch_mm_irqs_off(oldmm, mm, next); /* 進(jìn)程地址空間切換 */...

/* arch/arm/include/asm/mmu_context.h */static inline void
switch_mm(struct mm_struct *prev, struct mm_struct *next,struct task_struct *tsk)
{
#ifdef CONFIG_MMUunsigned int cpu = smp_processor_id();if (cache_ops_need_broadcast() &&!cpumask_empty(mm_cpumask(next)) &&!cpumask_test_cpu(cpu, mm_cpumask(next)))__flush_icache_all();if (!cpumask_test_and_set_cpu(cpu, mm_cpumask(next)) || prev != next) {check_and_switch_context(next, tsk);if (cache_is_vivt())cpumask_clear_cpu(cpu, mm_cpumask(prev));}
#endif
}/* arch/arm/mm/context.c */
void check_and_switch_context(struct mm_struct *mm, struct task_struct *tsk)
{unsigned long flags;unsigned int cpu = smp_processor_id();u64 asid;/** We cannot update the pgd and the ASID atomicly with classic* MMU, so switch exclusively to global mappings to avoid* speculative page table walking with the wrong TTBR.*/cpu_set_reserved_ttbr0();asid = atomic64_read(&mm->context.id);if (!((asid ^ atomic64_read(&asid_generation)) >> ASID_BITS)&& atomic64_xchg(&per_cpu(active_asids, cpu), asid))goto switch_mm_fastpath;// 分配新的 ASIDraw_spin_lock_irqsave(&cpu_asid_lock, flags);/* Check that our ASID belongs to the current generation. */asid = atomic64_read(&mm->context.id);if ((asid ^ atomic64_read(&asid_generation)) >> ASID_BITS) {asid = new_context(mm, cpu);...asid = find_next_zero_bit(asid_map, NUM_USER_ASIDS, cur_idx);if (asid == NUM_USER_ASIDS) { // ASID 耗光了，重新分配generation = atomic64_add_return(ASID_FIRST_VERSION,&asid_generation);flush_context(cpu);.../* Queue a TLB invalidate and flush the I-cache if necessary. */cpumask_setall(&tlb_flush_pending); // 需要 flush TLB...asid = find_next_zero_bit(asid_map, NUM_USER_ASIDS, 1);}...__set_bit(asid, asid_map);cur_idx = asid;cpumask_clear(mm_cpumask(mm));return asid | generation;atomic64_set(&mm->context.id, asid);}// 刷 TLBif (cpumask_test_and_clear_cpu(cpu, &tlb_flush_pending)) {local_flush_bp_all();local_flush_tlb_all();}// 設(shè)置當(dāng)前 CPU ASID 相關(guān)數(shù)據(jù)atomic64_set(&per_cpu(active_asids, cpu), asid);cpumask_set_cpu(cpu, mm_cpumask(mm));raw_spin_unlock_irqrestore(&cpu_asid_lock, flags);switch_mm_fastpath:cpu_switch_mm(mm->pgd, mm); // 進(jìn)程地址空間(mm_struct)切換
}

5. Cache 調(diào)試方法

5.1 使用 Cache 調(diào)試工具

Linux 的 perf 工具可以用來(lái)查看 Cache Miss 的信息，進(jìn)而用來(lái)調(diào)試 Cache 相關(guān)問(wèn)題：

$ sudo perf list cache # 查詢(xún) perf 支持的 cache 事件List of pre-defined events (to be used in -e):L1-dcache-load-misses                              [Hardware cache event]L1-dcache-loads                                    [Hardware cache event]L1-dcache-stores                                   [Hardware cache event]L1-icache-load-misses                              [Hardware cache event]branch-load-misses                                 [Hardware cache event]branch-loads                                       [Hardware cache event]dTLB-load-misses                                   [Hardware cache event]dTLB-loads                                         [Hardware cache event]dTLB-store-misses                                  [Hardware cache event]dTLB-stores                                        [Hardware cache event]iTLB-load-misses                                   [Hardware cache event]iTLB-loads                                         [Hardware cache event]# perf 記錄 cache 事件數(shù)據(jù)
perf stat -e L1-dcache-load-misses
perf record -e L1-dcache-load-misses

注意，這些 Cache 事件查詢(xún)都需要硬件底層架構(gòu)提供支持。

5.2 查詢(xún) Cache 信息

$ lscpu
...
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
...// 查看 /sys/devices/system/cpu/cpuN/cache 目錄
$ ls /sys/devices/system/cpu/cpu0/cache/ -l
total 0
drwxr-xr-x 3 root root    0 9月  17 14:19 index0
drwxr-xr-x 3 root root    0 9月  17 14:19 index1
drwxr-xr-x 3 root root    0 9月  17 14:19 index2
drwxr-xr-x 3 root root    0 9月  17 14:19 index3
drwxr-xr-x 2 root root    0 9月  17 14:20 power
-rw-r--r-- 1 root root 4096 9月  17 14:20 uevent
$ ls -l /sys/devices/system/cpu/cpu0/cache/index0/
total 0
-r--r--r-- 1 root root 4096 9月  17 14:22 coherency_line_size
-r--r--r-- 1 root root 4096 9月  17 14:22 id
-r--r--r-- 1 root root 4096 9月  17 14:19 level
-r--r--r-- 1 root root 4096 9月  17 14:22 number_of_sets
-r--r--r-- 1 root root 4096 9月  17 14:22 physical_line_partition
drwxr-xr-x 2 root root    0 9月  17 14:22 power
-r--r--r-- 1 root root 4096 9月  17 14:22 shared_cpu_list
-r--r--r-- 1 root root 4096 9月  17 14:19 shared_cpu_map
-r--r--r-- 1 root root 4096 9月  17 14:19 size
-r--r--r-- 1 root root 4096 9月  17 14:19 type
-rw-r--r-- 1 root root 4096 9月  17 14:22 uevent
-r--r--r-- 1 root root 4096 9月  17 14:22 ways_of_associativity
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 
64
$ cat /sys/devices/system/cpu/cpu0/cache/index0/level 
1
$ cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets 
64
$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K
$ cat /sys/devices/system/cpu/cpu0/cache/index0/type
Data
$ cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity 
8

$ getconf -a | grep CACHE
LEVEL1_ICACHE_SIZE                 32768
LEVEL1_ICACHE_ASSOC                8
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  262144
LEVEL2_CACHE_ASSOC                 4
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  3145728
LEVEL3_CACHE_ASSOC                 12
LEVEL3_CACHE_LINESIZE              64
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
LEVEL4_CACHE_LINESIZE              0

還可以通過(guò)函數(shù) sysconf(_SC_LEVEL1_DCACHE_LINESIZE) 查詢(xún) dCache 行大小，不過(guò)這個(gè)方法似乎有些場(chǎng)合下不奏效。

6. Cache 性能優(yōu)化案例

6.1 熱點(diǎn)代碼 iCache & dCache Miss

頻繁被調(diào)用的代碼，可以通過(guò) LLVM 對(duì) 內(nèi)核 和 應(yīng)用代碼 進(jìn)行 二進(jìn)制重排，將熱點(diǎn)集中在局部，可以提高 iCache 命中率，還可以減少應(yīng)用 page 換入換出。

6.2 Cache 偽共享(False Sharing)優(yōu)化

// false_sharing-1.c#include <stdio.h>
#include <pthread.h>#define N_LOOP 1000000000// thread1_data 和 thread1_data 共享一個(gè) L1 數(shù)據(jù) Cache 行
struct
{int thread1_data;int thread2_data;
} data;void *thread1_entry(void *args)
{int i;for (i = 0; i < N_LOOP; i++)data.thread1_data = 1;
}void *thread2_entry(void *args)
{int i;for (i = 0; i < N_LOOP; i++)data.thread2_data = 2;
}int main(int argc, char *argv[])
{pthread_t t1, t2;pthread_create(&t1, NULL, thread1_entry, NULL);pthread_create(&t2, NULL, thread2_entry, NULL);pthread_join(t1, NULL);pthread_join(t2, NULL);return 0;
}

修改上面代碼結(jié)構(gòu)體的定義，將數(shù)據(jù) thread1_data 和 thread2_data 隔離到兩個(gè)不同的 L1 數(shù)據(jù) Cache 行：

// false_sharing-2.c...// 通過(guò)在 thread1_data 和 thread1_data 中間插入 pad[] ，使得
// thread1_data 和 thread1_data 位于兩個(gè)獨(dú)立 L1 數(shù)據(jù) Cache 行
struct
{int thread1_data;char pad[64];int thread2_data;
} data;...

編譯測(cè)試 false_sharing-1.c 和 false_sharing-2.c ：

$ gcc -o false_sharing-1 -pthread false_sharing-1.c
$ gcc -o false_sharing-2 -pthread false_sharing-2.c
$ time ./false_sharing-1real	0m4.125s
user	0m8.236s
sys	0m0.004s
$ time ./false_sharing-2real	0m2.288s
user	0m4.554s
sys	0m0.004s

可以分別多運(yùn)行幾次，以避免偶發(fā)因素導(dǎo)致的錯(cuò)誤結(jié)論。從多次測(cè)試結(jié)果看，很明顯 false_sharing-2.c 的性能優(yōu)于 false_sharing-1.c 。注意，代碼中的 N_LOOP 數(shù)值應(yīng)該盡可能的大，以使得 thread 1, 2 有機(jī)會(huì)運(yùn)行于不同的 CPU 核上，同時(shí)，足夠多的訪存次數(shù)，才能夠看的到性能的差異。產(chǎn)生性能差異的原因在于，在 false_sharing-1.c 中，當(dāng) thread 1,2 運(yùn)行不同 CPU 核上時(shí)，thread1_data 和 thread2_data 會(huì)同時(shí)位于不同 CPU 核各自的 Cache 行內(nèi)，當(dāng)某一個(gè)改變了 CPU 改變了 thread1_data 或 thread2_data 時(shí)，需要做兩個(gè) CPU Cache 數(shù)據(jù)之間的同步；而 在 false_sharing-1.c 中，由于 thread1_data 和thread2_data 位于不同的 Cache 行，所以改變 thread1_data 或 thread2_data 無(wú)需做 Cache 數(shù)據(jù)同步，因而減少開(kāi)銷(xiāo)，挺高了性能。

7. 參考資料

ARM Architecture Reference Manual.pdf
DDI0406C_d_armv7ar_arm.pdf
DDI0464D_cortex_a7_mpcore_r0p3_trm.pdf
DDI0464F_cortex_a7_mpcore_r0p5_trm.pdf
https://blog.csdn.net/kakaBack/article/details/126537156
https://zhuanlan.zhihu.com/p/577138649
https://www.freesion.com/article/9682678000/