大家好，我是小林。

今天上午在群里有位讀者面試時(shí)，被問到這么一個(gè)問題：

快表其實(shí)是 TLB，是 CPU 封裝在芯片里的一個(gè)東西：

為什么要有 TLB ？

現(xiàn)在的內(nèi)存分頁都是多級頁表的，這樣虛擬地址到物理地址的轉(zhuǎn)換就多了幾道轉(zhuǎn)換的工序，這顯然就降低了這倆地址轉(zhuǎn)換的速度，也就是帶來了時(shí)間上的開銷。

所以，TLB 是專門存放程序最常訪問的頁表項(xiàng)的 Cache，有了 TLB 后，那么 CPU 在尋址時(shí)，會(huì)先查 TLB，如果沒找到，才會(huì)繼續(xù)查常規(guī)的頁表。

每個(gè)進(jìn)程的虛擬地址范圍都是一樣的，那不同進(jìn)程對應(yīng)相同的虛擬地址，在 TLB 是如何區(qū)分的呢?

正文

TLB是translation lookaside buffer的簡稱。首先，我們知道MMU的作用是把虛擬地址轉(zhuǎn)換成物理地址。虛擬地址和物理地址的映射關(guān)系存儲(chǔ)在頁表中，而現(xiàn)在頁表又是分級的。64位系統(tǒng)一般都是3~5級。

常見的配置是4級頁表，就以4級頁表為例說明。分別是PGD、PUD、PMD、PTE四級頁表。在硬件上會(huì)有一個(gè)叫做頁表基地址寄存器，它存儲(chǔ)PGD頁表的首地址。MMU就是根據(jù)頁表基地址寄存器從PGD頁表一路查到PTE，最終找到物理地址(PTE頁表中存儲(chǔ)物理地址)。

這就像在地圖上顯示你的家在哪一樣，我為了找到你家的地址，先確定你是中國，再確定你是某個(gè)省，繼續(xù)往下某個(gè)市，最后找到你家是一樣的原理。一級一級找下去。這個(gè)過程你也看到了，非常繁瑣。

如果第一次查到你家的具體位置，我如果記下來你的姓名和你家的地址。下次查找時(shí)，是不是只需要跟我說你的姓名是什么，我就直接能夠告訴你地址，而不需要一級一級查找。四級頁表查找過程需要四次內(nèi)存訪問。延時(shí)可想而知，非常影響性能。

頁表查找過程的示例如下圖所示。以后有機(jī)會(huì)詳細(xì)展開，這里了解下即可。

page table walk

TLB的本質(zhì)是什么

TLB其實(shí)就是一塊高速緩存。數(shù)據(jù)cache緩存地址(虛擬地址或者物理地址)和數(shù)據(jù)。TLB緩存虛擬地址和其映射的物理地址。

TLB根據(jù)虛擬地址查找cache，它沒得選，只能根據(jù)虛擬地址查找。所以TLB是一個(gè)虛擬高速緩存。硬件存在TLB后，虛擬地址到物理地址的轉(zhuǎn)換過程發(fā)生了變化。

虛擬地址首先發(fā)往TLB確認(rèn)是否命中cache，如果cache hit直接可以得到物理地址。否則，一級一級查找頁表獲取物理地址。

并將虛擬地址和物理地址的映射關(guān)系緩存到TLB中。既然TLB是虛擬高速緩存(VIVT)，是否存在別名和歧義問題呢?如果存在，軟件和硬件是如何配合解決這些問題呢?

TLB的特殊

虛擬地址映射物理地址的最小單位是4KB。所以TLB其實(shí)不需要存儲(chǔ)虛擬地址和物理地址的低12位(因?yàn)榈?2位是一樣的，根本沒必要存儲(chǔ))。

另外，我們?nèi)绻衏ache，肯定是一次性從cache中拿出整個(gè)數(shù)據(jù)。所以虛擬地址不需要offset域。index域是否需要呢?這取決于cache的組織形式。

如果是全相連高速緩存。那么就不需要index。如果使用多路組相連高速緩存，依然需要index。下圖就是一個(gè)四路組相連TLB的例子。

現(xiàn)如今64位CPU尋址范圍并沒有擴(kuò)大到64位。64位地址空間很大，現(xiàn)如今還用不到那么大。因此硬件為了設(shè)計(jì)簡單或者解決成本，實(shí)際虛擬地址位數(shù)只使用了一部分。這里以48位地址總線為了例說明。

TLB的別名問題

我先來思考第一個(gè)問題，別名是否存在。我們知道PIPT的數(shù)據(jù)cache不存在別名問題。物理地址是唯一的，一個(gè)物理地址一定對應(yīng)一個(gè)數(shù)據(jù)。

但是不同的物理地址可能存儲(chǔ)相同的數(shù)據(jù)。也就是說，物理地址對應(yīng)數(shù)據(jù)是一對一關(guān)系，反過來是多對一關(guān)系。由于TLB的特殊性，存儲(chǔ)的是虛擬地址和物理地址的對應(yīng)關(guān)系。

因此，對于單個(gè)進(jìn)程來說，同一時(shí)間一個(gè)虛擬地址對應(yīng)一個(gè)物理地址，一個(gè)物理地址可以被多個(gè)虛擬地址映射。將PIPT數(shù)據(jù)cache類比TLB，我們可以知道TLB不存在別名問題。

而VIVT Cache存在別名問題，原因是VA需要轉(zhuǎn)換成PA，PA里面才存儲(chǔ)著數(shù)據(jù)。中間多經(jīng)傳一手，所以引入了些問題。

TLB的歧義問題

我們知道不同的進(jìn)程之間看到的虛擬地址范圍是一樣的，所以多個(gè)進(jìn)程下，不同進(jìn)程的相同的虛擬地址可以映射不同的物理地址。這就會(huì)造成歧義問題。

例如，進(jìn)程A將地址0x2000映射物理地址0x4000。進(jìn)程B將地址0x2000映射物理地址0x5000。當(dāng)進(jìn)程A執(zhí)行的時(shí)候?qū)?x2000對應(yīng)0x4000的映射關(guān)系緩存到TLB中。當(dāng)切換B進(jìn)程的時(shí)候，B進(jìn)程訪問0x2000的數(shù)據(jù)，會(huì)由于命中TLB從物理地址0x4000取數(shù)據(jù)。這就造成了歧義。

如何消除這種歧義？我們可以借鑒VIVT數(shù)據(jù)cache的處理方式，在進(jìn)程切換時(shí)將整個(gè)TLB無效。切換后的進(jìn)程都不會(huì)命中TLB，但是會(huì)導(dǎo)致性能損失。

如何盡可能的避免flush TLB

首先需要說明的是，這里的flush理解成使無效的意思。我們知道進(jìn)程切換的時(shí)候，為了避免歧義，我們需要主動(dòng)flush整個(gè)TLB。如果我們能夠區(qū)分不同的進(jìn)程的TLB表項(xiàng)就可以避免flush TLB。

我們知道Linux如何區(qū)分不同的進(jìn)程？每個(gè)進(jìn)程擁有一個(gè)獨(dú)一無二的進(jìn)程ID。如果TLB在判斷是否命中的時(shí)候，除了比較tag以外，再額外比較進(jìn)程ID該多好呢!這樣就可以區(qū)分不同進(jìn)程的TLB表項(xiàng)。進(jìn)程A和B雖然虛擬地址一樣，但是進(jìn)程ID不一樣，自然就不會(huì)發(fā)生進(jìn)程B命中進(jìn)程A的TLB表項(xiàng)。

所以，TLB添加一項(xiàng)ASID(Address Space ID)的匹配。ASID就類似進(jìn)程ID一樣，用來區(qū)分不同進(jìn)程的TLB表項(xiàng)。這樣在進(jìn)程切換的時(shí)候就不需要flush TLB。但是仍然需要軟件管理和分配ASID。

如何管理ASID

ASID和進(jìn)程ID肯定是不一樣的，別混淆二者。進(jìn)程ID取值范圍很大。但是ASID一般是8或16 bit。所以只能區(qū)分256或65536個(gè)進(jìn)程。

我們的例子就以8位ASID說明。所以我們不可能將進(jìn)程ID和ASID一一對應(yīng)，我們必須為每個(gè)進(jìn)程分配一個(gè)ASID，進(jìn)程ID和每個(gè)進(jìn)程的ASID一般是不相等的。每創(chuàng)建一個(gè)新進(jìn)程，就為之分配一個(gè)新的ASID。當(dāng)ASID分配完后，flush所有TLB，重新分配ASID。所以，如果想完全避免flush TLB的話，理想情況下，運(yùn)行的進(jìn)程數(shù)目必須小于等于256。

管理ASID上需要軟硬結(jié)合。Linux kernel為了管理每個(gè)進(jìn)程會(huì)有個(gè)task_struct結(jié)構(gòu)體，我們可以把分配給當(dāng)前進(jìn)程的ASID存儲(chǔ)在這里。頁表基地址寄存器有空閑位也可以用來存儲(chǔ)ASID。

當(dāng)進(jìn)程切換時(shí)，可以將頁表基地址和ASID(可以從task_struct獲得)共同存儲(chǔ)在頁表基地址寄存器中。當(dāng)查找TLB時(shí)，硬件可以對比tag以及ASID是否相等(對比頁表基地址寄存器存儲(chǔ)的ASID和TLB表項(xiàng)存儲(chǔ)的ASID)。如果都相等，代表TLB hit。否則TLB miss。當(dāng)TLB miss時(shí)，需要多級遍歷頁表，查找物理地址。然后緩存到TLB中，同時(shí)緩存當(dāng)前的ASID。

更上一層樓

我們知道內(nèi)核空間和用戶空間是分開的，并且內(nèi)核空間是所有進(jìn)程共享。

既然內(nèi)核空間是共享的，進(jìn)程A切換進(jìn)程B的時(shí)候，如果進(jìn)程B訪問的地址位于內(nèi)核空間，完全可以使用進(jìn)程A緩存的TLB。但是現(xiàn)在由于ASID不一樣，導(dǎo)致TLB miss。

我們針對內(nèi)核空間這種全局共享的映射關(guān)系稱之為global映射。針對每個(gè)進(jìn)程的映射稱之為non-global映射。所以，我們在最后一級頁表中引入一個(gè)bit(non-global (nG) bit)代表是不是global映射。

當(dāng)虛擬地址映射物理地址關(guān)系緩存到TLB時(shí)，將nG bit也存儲(chǔ)下來。當(dāng)判斷是否命中TLB時(shí)，當(dāng)比較tag相等時(shí)，再判斷是不是global映射，如果是的話，直接判斷TLB hit，無需比較ASID。當(dāng)不是global映射時(shí)，最后比較ASID判斷是否TLB hit。

什么時(shí)候應(yīng)該flush TLB

我們再來最后的總結(jié)，什么時(shí)候應(yīng)該flush TLB。

• 當(dāng)ASID分配完的時(shí)候，需要flush全部TLB。ASID的管理可以使用bitmap管理，flush TLB后clear整個(gè)bitmap。
• 當(dāng)我們建立頁表映射的時(shí)候，就需要flush虛擬地址對應(yīng)的TLB表項(xiàng)。第一印象可能是修改頁表映射的時(shí)候才需要flush TLB，但是實(shí)際情況是只要建立映射就需要flush TLB。原因是，建立映射時(shí)你并不知道之前是否存在映射。例如，建立虛擬地址A到物理地址B的映射，我們并不知道之前是否存在虛擬地址A到物理地址C的映射情況。所以就統(tǒng)一在建立映射關(guān)系的時(shí)候flush TLB。