最近在極客星球群里討論內(nèi)存缺頁(yè)中斷問(wèn)題，討論到了MMU和TLB原理相關(guān)的：

今天就分享一篇TLB的好文章，希望大家夯實(shí)基本功，讓我們一起深入理解計(jì)算機(jī)系統(tǒng)。

TLB是translation lookaside buffer的簡(jiǎn)稱。首先，我們知道MMU的作用是把虛擬地址轉(zhuǎn)換成物理地址。

MMU工作原理

虛擬地址和物理地址的映射關(guān)系存儲(chǔ)在頁(yè)表中，而現(xiàn)在頁(yè)表又是分級(jí)的。64位系統(tǒng)一般都是3~5級(jí)。常見(jiàn)的配置是4級(jí)頁(yè)表，就以4級(jí)頁(yè)表為例說(shuō)明。分別是PGD、PUD、PMD、PTE四級(jí)頁(yè)表。在硬件上會(huì)有一個(gè)叫做頁(yè)表基地址寄存器，它存儲(chǔ)PGD頁(yè)表的首地址。

Linux分頁(yè)機(jī)制

MMU就是根據(jù)頁(yè)表基地址寄存器從PGD頁(yè)表一路查到PTE，最終找到物理地址(PTE頁(yè)表中存儲(chǔ)物理地址)。這就像在地圖上顯示你的家在哪一樣，我為了找到你家的地址，先確定你是中國(guó)，再確定你是某個(gè)省，繼續(xù)往下某個(gè)市，最后找到你家是一樣的原理。一級(jí)一級(jí)找下去。這個(gè)過(guò)程你也看到了，非常繁瑣。如果第一次查到你家的具體位置，我如果記下來(lái)你的姓名和你家的地址。下次查找時(shí)，是不是只需要跟我說(shuō)你的姓名是什么，我就直接能夠告訴你地址，而不需要一級(jí)一級(jí)查找。四級(jí)頁(yè)表查找過(guò)程需要四次內(nèi)存訪問(wèn)。延時(shí)可想而知，非常影響性能。頁(yè)表查找過(guò)程的示例如下圖所示。以后有機(jī)會(huì)詳細(xì)展開(kāi)，這里了解下即可。

page table walk

TLB的本質(zhì)是什么

TLB其實(shí)就是一塊高速緩存。數(shù)據(jù)cache緩存地址(虛擬地址或者物理地址)和數(shù)據(jù)。TLB緩存虛擬地址和其映射的物理地址。TLB根據(jù)虛擬地址查找cache，它沒(méi)得選，只能根據(jù)虛擬地址查找。所以TLB是一個(gè)虛擬高速緩存。硬件存在TLB后，虛擬地址到物理地址的轉(zhuǎn)換過(guò)程發(fā)生了變化。虛擬地址首先發(fā)往TLB確認(rèn)是否命中cache，如果cache hit直接可以得到物理地址。否則，一級(jí)一級(jí)查找頁(yè)表獲取物理地址。并將虛擬地址和物理地址的映射關(guān)系緩存到TLB中。既然TLB是虛擬高速緩存（VIVT），是否存在別名和歧義問(wèn)題呢？如果存在，軟件和硬件是如何配合解決這些問(wèn)題呢？

TLB的特殊

虛擬地址映射物理地址的最小單位是4KB。所以TLB其實(shí)不需要存儲(chǔ)虛擬地址和物理地址的低12位(因?yàn)榈?2位是一樣的，根本沒(méi)必要存儲(chǔ))。另外，我們?nèi)绻衏ache，肯定是一次性從cache中拿出整個(gè)數(shù)據(jù)。所以虛擬地址不需要offset域。index域是否需要呢？這取決于cache的組織形式。如果是全相連高速緩存。那么就不需要index。如果使用多路組相連高速緩存，依然需要index。下圖就是一個(gè)四路組相連TLB的例子?，F(xiàn)如今64位CPU尋址范圍并沒(méi)有擴(kuò)大到64位。64位地址空間很大，現(xiàn)如今還用不到那么大。因此硬件為了設(shè)計(jì)簡(jiǎn)單或者解決成本，實(shí)際虛擬地址位數(shù)只使用了一部分。這里以48位地址總線為了例說(shuō)明。

TLB的別名問(wèn)題

我先來(lái)思考第一個(gè)問(wèn)題，別名是否存在。我們知道PIPT的數(shù)據(jù)cache不存在別名問(wèn)題。物理地址是唯一的，一個(gè)物理地址一定對(duì)應(yīng)一個(gè)數(shù)據(jù)。但是不同的物理地址可能存儲(chǔ)相同的數(shù)據(jù)。也就是說(shuō)，物理地址對(duì)應(yīng)數(shù)據(jù)是一對(duì)一關(guān)系，反過(guò)來(lái)是多對(duì)一關(guān)系。由于TLB的特殊性，存儲(chǔ)的是虛擬地址和物理地址的對(duì)應(yīng)關(guān)系。因此，對(duì)于單個(gè)進(jìn)程來(lái)說(shuō)，同一時(shí)間一個(gè)虛擬地址對(duì)應(yīng)一個(gè)物理地址，一個(gè)物理地址可以被多個(gè)虛擬地址映射。將PIPT數(shù)據(jù)cache類比TLB，我們可以知道TLB不存在別名問(wèn)題。而VIVT Cache存在別名問(wèn)題，原因是VA需要轉(zhuǎn)換成PA，PA里面才存儲(chǔ)著數(shù)據(jù)。中間多經(jīng)傳一手，所以引入了些問(wèn)題。

TLB的歧義問(wèn)題

我們知道不同的進(jìn)程之間看到的虛擬地址范圍是一樣的，所以多個(gè)進(jìn)程下，不同進(jìn)程的相同的虛擬地址可以映射不同的物理地址。這就會(huì)造成歧義問(wèn)題。例如，進(jìn)程A將地址0x2000映射物理地址0x4000。進(jìn)程B將地址0x2000映射物理地址0x5000。當(dāng)進(jìn)程A執(zhí)行的時(shí)候?qū)?x2000對(duì)應(yīng)0x4000的映射關(guān)系緩存到TLB中。當(dāng)切換B進(jìn)程的時(shí)候，B進(jìn)程訪問(wèn)0x2000的數(shù)據(jù)，會(huì)由于命中TLB從物理地址0x4000取數(shù)據(jù)。這就造成了歧義。如何消除這種歧義，我們可以借鑒VIVT數(shù)據(jù)cache的處理方式，在進(jìn)程切換時(shí)將整個(gè)TLB無(wú)效。切換后的進(jìn)程都不會(huì)命中TLB，但是會(huì)導(dǎo)致性能損失。

如何盡可能的避免flush TLB

首先需要說(shuō)明的是，這里的flush理解成使無(wú)效的意思。我們知道進(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ú)一無(wú)二的進(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一樣，用來(lái)區(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說(shuō)明。所以我們不可能將進(jìn)程ID和ASID一一對(duì)應(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。然而事實(shí)并非如此，因此管理ASID上需要軟硬結(jié)合。Linux kernel為了管理每個(gè)進(jìn)程會(huì)有個(gè)task_struct結(jié)構(gòu)體，我們可以把分配給當(dāng)前進(jìn)程的ASID存儲(chǔ)在這里。頁(yè)表基地址寄存器有空閑位也可以用來(lái)存儲(chǔ)ASID。當(dāng)進(jìn)程切換時(shí)，可以將頁(yè)表基地址和ASID(可以從task_struct獲得)共同存儲(chǔ)在頁(yè)表基地址寄存器中。當(dāng)查找TLB時(shí)，硬件可以對(duì)比tag以及ASID是否相等(對(duì)比頁(yè)表基地址寄存器存儲(chǔ)的ASID和TLB表項(xiàng)存儲(chǔ)的ASID)。如果都相等，代表TLB hit。否則TLB miss。當(dāng)TLB miss時(shí)，需要多級(jí)遍歷頁(yè)表，查找物理地址。然后緩存到TLB中，同時(shí)緩存當(dāng)前的ASID。

多個(gè)進(jìn)程共享

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

我們針對(duì)內(nèi)核空間這種全局共享的映射關(guān)系稱之為global映射。針對(duì)每個(gè)進(jìn)程的映射稱之為non-global映射。所以，我們?cè)谧詈笠患?jí)頁(yè)表中引入一個(gè)bit(non-global (nG) bit)代表是不是global映射。當(dāng)虛擬地址映射物理地址關(guān)系緩存到TLB時(shí)，將nG bit也存儲(chǔ)下來(lái)。當(dāng)判斷是否命中TLB時(shí)，當(dāng)比較tag相等時(shí)，再判斷是不是global映射，如果是的話，直接判斷TLB hit，無(wú)需比較ASID。當(dāng)不是global映射時(shí)，最后比較ASID判斷是否TLB hit。

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

我們?cè)賮?lái)最后的總結(jié)，什么時(shí)候應(yīng)該flush TLB。

當(dāng)ASID分配完的時(shí)候，需要flush全部TLB，ASID的管理可以使用bitmap管理，flush TLB后clear整個(gè)bitmap。

當(dāng)我們建立頁(yè)表映射的時(shí)候，就需要flush虛擬地址對(duì)應(yīng)的TLB表項(xiàng)。

第一印象可能是修改頁(yè)表映射的時(shí)候才需要flush TLB，但是實(shí)際情況是只要建立映射就需要flush TLB。原因是，建立映射時(shí)你并不知道之前是否存在映射，例如，建立虛擬地址A到物理地址B的映射，我們并不知道之前是否存在虛擬地址A到物理地址C的映射情況，所以就統(tǒng)一在建立映射關(guān)系的時(shí)候flush TLB。

審核編輯 ：李倩