深入理解 TLB 原理

原文:https://zhuanlan.zhihu.com/p/108425561

更新:極客重生

最近在極客星球羣裏討論內存缺頁中斷問題,討論到了 MMU 和 TLB 原理相關的:

今天就分享一篇 TLB 的好文章,希望大家夯實基本功,讓我們一起深入理解計算機系統。

TLB 是 translation lookaside buffer 的簡稱。首先,我們知道 MMU 的作用是把虛擬地址轉換成物理地址。

MMU 工作原理

虛擬地址和物理地址的映射關係存儲在頁表中,而現在頁表又是分級的。64 位系統一般都是 3~5 級。常見的配置是 4 級頁表,就以 4 級頁表爲例說明。分別是 PGD、PUD、PMD、PTE 四級頁表。在硬件上會有一個叫做頁表基地址寄存器,它存儲 PGD 頁表的首地址。

Linux 分頁機制

MMU 就是根據頁表基地址寄存器從 PGD 頁表一路查到 PTE,最終找到物理地址 (PTE 頁表中存儲物理地址)。這就像在地圖上顯示你的家在哪一樣,我爲了找到你家的地址,先確定你是中國,再確定你是某個省,繼續往下某個市,最後找到你家是一樣的原理。一級一級找下去。這個過程你也看到了,非常繁瑣。如果第一次查到你家的具體位置,我如果記下來你的姓名和你家的地址。下次查找時,是不是隻需要跟我說你的姓名是什麼,我就直接能夠告訴你地址,而不需要一級一級查找。四級頁表查找過程需要四次內存訪問。延時可想而知,非常影響性能。頁表查找過程的示例如下圖所示。以後有機會詳細展開,這裏瞭解下即可。

page table walk

TLB 的本質是什麼

TLB 其實就是一塊高速緩存。數據 cache 緩存地址 (虛擬地址或者物理地址) 和數據。TLB 緩存虛擬地址和其映射的物理地址。TLB 根據虛擬地址查找 cache,它沒得選,只能根據虛擬地址查找。所以 TLB 是一個虛擬高速緩存。硬件存在 TLB 後,虛擬地址到物理地址的轉換過程發生了變化。虛擬地址首先發往 TLB 確認是否命中 cache,如果 cache hit 直接可以得到物理地址。否則,一級一級查找頁表獲取物理地址。並將虛擬地址和物理地址的映射關係緩存到 TLB 中。既然 TLB 是虛擬高速緩存(VIVT),是否存在別名和歧義問題呢?如果存在,軟件和硬件是如何配合解決這些問題呢?

TLB 的特殊

虛擬地址映射物理地址的最小單位是 4KB。所以 TLB 其實不需要存儲虛擬地址和物理地址的低 12 位 (因爲低 12 位是一樣的,根本沒必要存儲)。另外,我們如果命中 cache,肯定是一次性從 cache 中拿出整個數據。所以虛擬地址不需要 offset 域。index 域是否需要呢?這取決於 cache 的組織形式。如果是全相連高速緩存。那麼就不需要 index。如果使用多路組相連高速緩存,依然需要 index。下圖就是一個四路組相連 TLB 的例子。現如今 64 位 CPU 尋址範圍並沒有擴大到 64 位。64 位地址空間很大,現如今還用不到那麼大。因此硬件爲了設計簡單或者解決成本,實際虛擬地址位數只使用了一部分。這裏以 48 位地址總線爲了例說明。

TLB 的別名問題

我先來思考第一個問題,別名是否存在。我們知道 PIPT 的數據 cache 不存在別名問題。物理地址是唯一的,一個物理地址一定對應一個數據。但是不同的物理地址可能存儲相同的數據。也就是說,物理地址對應數據是一對一關係,反過來是多對一關係。由於 TLB 的特殊性,存儲的是虛擬地址和物理地址的對應關係。因此,對於單個進程來說,同一時間一個虛擬地址對應一個物理地址,一個物理地址可以被多個虛擬地址映射。將 PIPT 數據 cache 類比 TLB,我們可以知道 TLB 不存在別名問題。而 VIVT Cache 存在別名問題,原因是 VA 需要轉換成 PA,PA 裏面才存儲着數據。中間多經傳一手,所以引入了些問題。

TLB 的歧義問題

我們知道不同的進程之間看到的虛擬地址範圍是一樣的,所以多個進程下,不同進程的相同的虛擬地址可以映射不同的物理地址。這就會造成歧義問題。例如,進程 A 將地址 0x2000 映射物理地址 0x4000。進程 B 將地址 0x2000 映射物理地址 0x5000。當進程 A 執行的時候將 0x2000 對應 0x4000 的映射關係緩存到 TLB 中。當切換 B 進程的時候,B 進程訪問 0x2000 的數據,會由於命中 TLB 從物理地址 0x4000 取數據。這就造成了歧義。如何消除這種歧義,我們可以借鑑 VIVT 數據 cache 的處理方式,在進程切換時將整個 TLB 無效。切換後的進程都不會命中 TLB,但是會導致性能損失。

如何儘可能的避免 flush TLB

首先需要說明的是,這裏的 flush 理解成使無效的意思。我們知道進程切換的時候,爲了避免歧義,我們需要主動 flush 整個 TLB。如果我們能夠區分不同的進程的 TLB 表項就可以避免 flush TLB。

我們知道 Linux 如何區分不同的進程?每個進程擁有一個獨一無二的進程 ID。如果 TLB 在判斷是否命中的時候,除了比較 tag 以外,再額外比較進程 ID 該多好呢!這樣就可以區分不同進程的 TLB 表項。進程 A 和 B 雖然虛擬地址一樣,但是進程 ID 不一樣,自然就不會發生進程 B 命中進程 A 的 TLB 表項。所以,TLB 添加一項 ASID(Address Space ID) 的匹配。ASID 就類似進程 ID 一樣,用來區分不同進程的 TLB 表項。這樣在進程切換的時候就不需要 flush TLB。但是仍然需要軟件管理和分配 ASID。

如何管理 ASID

ASID 和進程 ID 肯定是不一樣的,別混淆二者。進程 ID 取值範圍很大。但是 ASID 一般是 8 或 16 bit。所以只能區分 256 或 65536 個進程。我們的例子就以 8 位 ASID 說明。所以我們不可能將進程 ID 和 ASID 一一對應,我們必須爲每個進程分配一個 ASID,進程 ID 和每個進程的 ASID 一般是不相等的。每創建一個新進程,就爲之分配一個新的 ASID。當 ASID 分配完後,flush 所有 TLB,重新分配 ASID。

所以,如果想完全避免 flush TLB 的話,理想情況下,運行的進程數目必須小於等於 256。然而事實並非如此,因此管理 ASID 上需要軟硬結合。Linux kernel 爲了管理每個進程會有個 task_struct 結構體,我們可以把分配給當前進程的 ASID 存儲在這裏。頁表基地址寄存器有空閒位也可以用來存儲 ASID。當進程切換時,可以將頁表基地址和 ASID(可以從 task_struct 獲得) 共同存儲在頁表基地址寄存器中。當查找 TLB 時,硬件可以對比 tag 以及 ASID 是否相等 (對比頁表基地址寄存器存儲的 ASID 和 TLB 表項存儲的 ASID)。如果都相等,代表 TLB hit。否則 TLB miss。當 TLB miss 時,需要多級遍歷頁表,查找物理地址。然後緩存到 TLB 中,同時緩存當前的 ASID。

多個進程共享

我們知道內核空間和用戶空間是分開的,並且內核空間是所有進程共享。既然內核空間是共享的,進程 A 切換進程 B 的時候,如果進程 B 訪問的地址位於內核空間,完全可以使用進程 A 緩存的 TLB。但是現在由於 ASID 不一樣,導致 TLB miss。

我們針對內核空間這種全局共享的映射關係稱之爲 global 映射。針對每個進程的映射稱之爲 non-global 映射。所以,我們在最後一級頁表中引入一個 bit(non-global (nG) bit) 代表是不是 global 映射。當虛擬地址映射物理地址關係緩存到 TLB 時,將 nG bit 也存儲下來。當判斷是否命中 TLB 時,當比較 tag 相等時,再判斷是不是 global 映射,如果是的話,直接判斷 TLB hit,無需比較 ASID。當不是 global 映射時,最後比較 ASID 判斷是否 TLB hit。

什麼時候應該 flush TLB

我們再來最後的總結,什麼時候應該 flush TLB。

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/KSf4GT3vI4ABHp9jvTqa2A