每個程序員都應該了解的“虛擬內存”知識

        英文原文：Memory part 3: Virtual Memory

編輯注：本文是 Ulrich Drepper 的“每個程序員應該了解的內存方面的知識”文章的第三部分；這一部分談論了虛擬內存，特別是 TLB 性能。沒有閱讀第 1 部分和第 2 部分的人可能現在就想讀一讀了。和往常一樣，請將排字錯誤報告之類發送到 lwn@lwn.net，而不要發送到這里的評論。

        4 虛擬內存

        處理器的虛擬內存子系統為每個進程實現了虛擬地址空間。這讓每個進程認為它在系統中是獨立的。虛擬內存的優點列表別的地方描述的非常詳細，所以這里就不重復了。本節集中在虛擬內存的實際的實現細節，和相關的成本。

        虛擬地址空間是由 CPU 的內存管理單元(MMU)實現的。OS 必須填充頁表數據結構，但大多數 CPU 自己做了剩下的工作。這事實上是一個相當復雜的機制；最好的理解它的方法是引入數據結構來描述虛擬地址空間。

        由 MMU 進行地址翻譯的輸入地址是虛擬地址。通常對它的值很少有限制 — 假設還有一點的話。 虛擬地址在 32 位系統中是 32 位的數值，在 64 位系統中是 64 位的數值。在一些系統，例如 x86 和 x86-64，使用的地址實際上包含了另一個層次的間接尋址：這些結構使用分段，這些分段只是簡單的給每個邏輯地址加上位移。我們可以忽略這一部分的地址 產生，它不重要，不是程序員非常關心的內存處理性能方面的東西。{x86 的分段限制是與性能相關的，但那是另一回事了}

        4. 1 最簡單的地址轉換

        有趣的地方在于由虛擬地址到物理地址的轉換。MMU 可以在逐頁的基礎上重新映射地址。就像地址緩存排列的時候，虛擬地址被分割為不同的部分。這些部分被用來做多個表的索引，而這些表是被用來創建最終物理地址用的。最簡單的模型是只有一級表。

Figure 4.1: 1-Level Address Translation

        圖 4.1 顯示了虛擬地址的不同部分是如何使用的。高字節部分是用來選擇一個頁目錄的條目；那個目錄中的每個地址可以被 OS 分別設置。頁目錄條目決定了物理內存頁的地址；頁面中可以有不止一個條目指向同樣的物理地址。完整的內存物理地址是由頁目錄獲得的頁地址和虛擬地址低字節 部分合并起來決定的。頁目錄條目還包含一些附加的頁面信息，如訪問權限。

        頁目錄的數據結構存儲在內存中。OS 必須分配連續的物理內存，并將這個地址范圍的基地址存入一個特殊的寄存器。然后虛擬地址的適當的位被用來作為頁目錄的索引，這個頁目錄事實上是目錄條目的列表。

        作為一個具體的例子，這是 x86 機器 4MB 分頁設計。虛擬地址的位移部分是 22 位大小，足以定位一個 4M 頁內的每一個字節。虛擬地址中剩下的 10 位指定頁目錄中 1024 個條目的一個。每個條目包括一個 10 位的 4M 頁內的基地址，它與位移結合起來形成了一個完整的 32 位地址。

        4. 2 多級頁表

        4MB 的頁不是規范，它們會浪費很多內存，因為 OS 需要執行的許多操作需要內存頁的隊列。對于 4kB 的頁（32 位機器的規范，甚至通常是 64 位機器的規范），虛擬地址的位移部分只有 12 位大小。這留下了 20 位作為頁目錄的指針。具有2²⁰個條目的表是不實際的。即使每個條目只要 4 比特，這個表也要 4MB 大小。由于每個進程可能具有其唯一的頁目錄，因為這些頁目錄許多系統中物理內存被綁定起來。

        解決辦法是用多級頁表。然后這些就能表示一個稀疏的大的頁目錄，目錄中一些實際不用的區域不需要分配內存。因此這種表示更緊湊，使它可能為內存中的很多進程使用頁表而并不太影響性能。.

        今天最復雜的頁表結構由四級構成。圖 4.2 顯示了這樣一個實現的原理圖。

Figure 4.2: 4-Level Address Translation

        在這個例子中，虛擬地址被至少分為五個部分。其中四個部分是不同的目錄的索引。被引用的第 4 級目錄使用 CPU 中一個特殊目的的寄存器。第 4 級到第 2 級目錄的內容是對次低一級目錄的引用。如果一個目錄條目標識為空，顯然就是不需要指向任何低一級的目錄。這樣頁表樹就能稀疏和緊湊。正如圖 4.1，第 1 級目錄的條目是一部分物理地址，加上像訪問權限的輔助數據。

        為了決定相對于虛擬地址的物理地址，處理器先決定最高級目錄的地址。這個地址一般保存在一個寄存器。然后 CPU 取出虛擬地址中相對于這個目錄的索引部分，并用那個索引選擇合適的條目。這個條目是下一級目錄的地址，它由虛擬地址的下一部分索引。處理器繼續直到它到達 第 1 級目錄，那里那個目錄條目的值就是物理地址的高字節部分。物理地址在加上虛擬地址中的頁面位移之后就完整了。這個過程稱為頁面樹遍歷。一些處理器（像 x86 和 x86-64）在硬件中執行這個操作，其他的需要 OS 的協助。

        系統中運行的每個進程可能需要自己的頁表樹。有部分共享樹的可能，但是這相當例外。因此如果頁表樹需要的內存盡可能小的話將對性能與可擴展性有 利。理想的情況是將使用的內存緊靠著放在虛擬地址空間；但實際使用的物理地址不影響。一個小程序可能只需要第2，3，4 級的一個目錄和少許第 1 級目錄就能應付過去。在一個采用 4kB 頁面和每個目錄 512 條目的 x86-64 機器上，這允許用 4 級目錄對 2MB 定位（每一級一個）。1GB 連續的內存可以被第 2 到第 4 級的一個目錄和第 1 級的 512 個目錄定位。

        但是，假設所有內存可以被連續分配是太簡單了。由于復雜的原因，大多數情況下，一個進程的棧與堆的區域是被分配在地址空間中非常相反的兩端。這樣使得任一個區域可以根據需要盡可能的增長。這意味著最有可能需要兩個第 2 級目錄和相應的更多的低一級的目錄。

        但即使這也不常常匹配現在的實際。由于安全的原因，一個可運行的（代碼，數據，堆，棧，動態共享對象，aka 共享庫）不同的部分被映射到隨機的地址[未選中的]。隨機化延伸到不同部分的相對位置；那意味著一個進程使用的不同的內存范圍，遍布于虛擬地址空間。通過 對隨機的地址位數采用一些限定，范圍可以被限制，但在大多數情況下，這當然不會讓一個進程只用一到兩個第 2 和第 3 級目錄運行。

        如果性能真的遠比安全重要，隨機化可以被關閉。OS 然后通常是在虛擬內存中至少連續的裝載所有的動態共享對象(DSO)。

        4. 3 優化頁表訪問

        頁表的所有數據結構都保存在主存中；在那里 OS 建造和更新這些表。當一個進程創建或者一個頁表變化，CPU 將被通知。頁表被用來解決每個虛擬地址到物理地址的轉換，用上面描述的頁表遍歷方式。更多有關于此：至少每一級有一個目錄被用于處理虛擬地址的過程。這需 要至多四次內存訪問（對一個運行中的進程的單次訪問來說），這很慢。有可能像普通數據一樣處理這些目錄表條目，并將他們緩存在 L1d,L2 等等，但這仍然非常慢。

        從虛擬內存的早期階段開始，CPU 的設計者采用了一種不同的優化。簡單的計算顯示，只有將目錄表條目保存在 L1d 和更高級的緩存，才會導致可怕的性能問題。每個絕對地址的計算，都需要相對于頁表深度的大量的 L1d 訪問。這些訪問不能并行，因為它們依賴于前面查詢的結果。在一個四級頁表的機器上，這種單線性將至少至少需要 12 次循環。再加上 L1d 的非命中的可能性，結果是指令流水線沒有什么能隱藏的。額外的 L1d 訪問也消耗了珍貴的緩存帶寬。

        所以，替代于只是緩存目錄表條目，物理頁地址的完整的計算結果被緩存了。因為同樣的原因，代碼和數據緩存也工作起來，這樣的地址計算結果的緩存 是高效的。由于虛擬地址的頁面位移部分在物理頁地址的計算中不起任何作用，只有虛擬地址的剩余部分被用作緩存的標簽。根據頁面大小這意味著成百上千的指令 或數據對象共享同一個標簽，因此也共享同一個物理地址前綴。

        保存計算數值的緩存叫做旁路轉換緩存(TLB)。因為它必須非常的快，通常這是一個小的緩存。現代 CPU 像其它緩存一樣，提供了多級 TLB 緩存；越高級的緩存越大越慢。小號的 L1 級 TLB 通常被用來做全相聯映像緩存，采用 LRU 回收策略。最近這種緩存大小變大了，而且在處理器中變得集相聯。其結果之一就是，當一個新的條目必須被添加的時候，可能不是最久的條目被回收于替換了。

        正如上面提到的，用來訪問 TLB 的標簽是虛擬地址的一個部分。如果標簽在緩存中有匹配，最終的物理地址將被計算出來，通過將來自虛擬地址的頁面位移地址加到緩存值的方式。這是一個非常快 的過程；也必須這樣，因為每條使用絕對地址的指令都需要物理地址，還有在一些情況下，因為使用物理地址作為關鍵字的 L2 查找。如果 TLB 查詢未命中，處理器就必須執行一次頁表遍歷；這可能代價非常大。

        通過軟件或硬件預取代碼或數據，會在地址位于另一頁面時，暗中預取 TLB 的條目。硬件預取不可能允許這樣，因為硬件會初始化非法的頁面表遍歷。因此程序員不能依賴硬件預取機制來預取 TLB 條目。它必須使用預取指令明確的完成。就像數據和指令緩存，TLB 可以表現為多個等級。正如數據緩存，TLB 通常表現為兩種形式：指令 TLB (ITLB)和數據 TLB (DTLB)。高級的 TLB 像 L2TLB 通常是統一的，就像其他的緩存情形一樣。

        4. 3.1 使用 TLB 的注意事項

        TLB 是以處理器為核心的全局資源。所有運行于處理器的線程與進程使用同一個 TLB。由于虛擬到物理地址的轉換依賴于安裝的是哪一種頁表樹，如果頁表變化了，CPU 不能盲目的重復使用緩存的條目。每個進程有一個不同的頁表樹（不算在同一個進程中的線程），內核與內存管理器 VMM (管理程序)也一樣，如果存在的話。也有可能一個進程的地址空間布局發生變化。有兩種解決這個問題的辦法：

• 當頁表樹變化時 TLB 刷新。
• TLB 條目的標簽附加擴展并唯一標識其涉及的頁表樹

        第一種情況，只要執行一個上下文切換 TLB 就被刷新。因為大多數 OS 中，從一個線程/進程到另一個的切換需要執行一些核心代碼，TLB 刷新被限制進入或離開核心地址空間。在虛擬化的系統中，當內核必須調用內存管理器 VMM 和返回的時候，這也會發生。如果內核和/或內存管理器沒有使用虛擬地址，或者當進程或內核調用系統/內存管理器時，能重復使用同一個虛擬地址，TLB 必須被刷新。當離開內核或內存管理器時，處理器繼續執行一個不同的進程或內核。

        刷新 TLB 高效但昂貴。例如，當執行一個系統調用，觸及的內核代碼可能僅限于幾千條指令，或許少許新頁面（或一個大的頁面，像某些結構的 Linux 的就是這樣）。這個工作將替換觸及頁面的所有 TLB 條目。對 Intel 帶 128ITLB 和 256DTLB 條目的 Core2 架構，完全的刷新意味著多于 100 和 200 條目（分別的）將被不必要的刷新。當系統調用返回同一個進程，所有那些被刷新的 TLB 條目可能被再次用到，但它們沒有了。內核或內存管理器常用的代碼也一樣。每條進入內核的條目上，TLB 必須擦去再裝，即使內核與內存管理器的頁表通常不會改變。因此理論上說，TLB 條目可以被保持一個很長時間。這也解釋了為什么現在處理器中的 TLB 緩存都不大：程序很有可能不會執行時間長到裝滿所有這些條目。

        當然事實逃脫不了 CPU 的結構。對緩存刷新優化的一個可能的方法是單獨的使 TLB 條目失效。例如，如果內核代碼與數據落于一個特定的地址范圍，只有落入這個地址范圍的頁面必須被清除出 TLB。這只需要比較標簽，因此不是很昂貴。在部分地址空間改變的場合，例如對去除內存頁的一次調用，這個方法也是有用的，

        更好的解決方法是為 TLB 訪問擴展標簽。如果除了虛擬地址的一部分之外，一個唯一的對應每個頁表樹的標識（如一個進程的地址空間）被添加，TLB 將根本不需要完全刷新。內核，內存管理程序，和獨立的進程都可以有唯一的標識。這種場景唯一的問題在于，TLB 標簽可以獲得的位數異常有限，但是地址空間的位數卻不是。這意味著一些標識的再利用是有必要的。這種情況發生時 TLB 必須部分刷新（如果可能的話）。所有帶有再利用標識的條目必須被刷新，但是希望這是一個非常小的集合。

        當多個進程運行在系統中時，這種擴展的 TLB 標簽具有一般優勢。如果每個可運行進程對內存的使用（因此 TLB 條目的使用）做限制，進程最近使用的 TLB 條目，當其再次列入計劃時，有很大機會仍然在 TLB。但還有兩個額外的優勢：

1. 特殊的地址空間，像內核和內存管理器使用的那些，經常僅僅進入一小段時間；之后控制經常返回初始化此次調用的地址空間。沒有標簽，就有兩次 TLB 刷新操作。有標簽，調用地址空間緩存的轉換地址將被保存，而且由于內核與內存管理器地址空間根本不會經常改變 TLB 條目，系統調用之前的地址轉換等等可以仍然使用。
2. 當同一個進程的兩個線程之間切換時，TLB 刷新根本就不需要。雖然沒有擴展 TLB 標簽時，進入內核的條目會破壞第一個線程的 TLB 的條目。

        有些處理器在一些時候實現了這些擴展標簽。AMD 給帕西菲卡（Pacifica）虛擬化擴展引入了一個 1 位的擴展標簽。在虛擬化的上下文中，這個 1 位的地址空間 ID（ASID）被用來從客戶域區別出內存管理程序的地址空間。這使得 OS 能夠避免在每次進入內存管理程序的時候（例如為了處理一個頁面錯誤）刷新客戶的 TLB 條目，或者當控制回到客戶時刷新內存管理程序的 TLB 條目。這個架構未來會允許使用更多的位。其它主流處理器很可能會隨之適應并支持這個功能。

        4. 3.2 影響 TLB 性能

        有一些因素會影響 TLB 性能。第一個是頁面的大小。顯然頁面越大，裝進去的指令或數據對象就越多。所以較大的頁面大小減少了所需的地址轉換總次數，即需要更少的 TLB 緩存條目。大多數架構允許使用多個不同的頁面尺寸；一些尺寸可以并存使用。例如，x86/x86-64 處理器有一個普通的 4kB 的頁面尺寸，但它們也可以分別用 4MB 和 2MB 頁面。IA-64 和 PowerPC 允許如 64kB 的尺寸作為基本的頁面尺寸。

        然而，大頁面尺寸的使用也隨之帶來了一些問題。用作大頁面的內存范圍必須是在物理內存中連續的。如果物理內存管理的單元大小升至虛擬內存頁面的 大小，浪費的內存數量將會增長。各種內存操作（如加載可執行文件）需要頁面邊界對齊。這意味著平均每次映射浪費了物理內存中頁面大小的一半。這種浪費很容 易累加；因此它給物理內存分配的合理單元大小劃定了一個上限。

        在 x86-64 結構中增加單元大小到 2MB 來適應大頁面當然是不實際的。這是一個太大的尺寸。但這轉而意味著每個大頁面必須由許多小一些的頁面組成。這些小頁面必須在物理內存中連續。以 4kB 單元頁面大小分配 2MB 連續的物理內存具有挑戰性。它需要找到有 512 個連續頁面的空閑區域。在系統運行一段時間并且物理內存開始碎片化以后，這可能極為困難（或者不可能）

        因此在 Linux 中有必要在系統啟動的時候，用特別的 Huge TLBfs 文件系統，預分配這些大頁面。一個固定數目的物理頁面被保留，以單獨用作大的虛擬頁面。這使可能不會經常用到的資源捆綁留下來。它也是一個有限的池；增大 它一般意味著要重啟系統。盡管如此，大頁面是進入某些局面的方法，在這些局面中性能具有保險性，資源豐富，而且麻煩的安裝不會成為大的妨礙。數據庫服務器 就是一個例子。

        增大最小的虛擬頁面大小（正如選擇大頁面的相反面）也有它的問題。內存映射操作（例如加載應用）必須確認這些頁面大小。不可能有更小的映射。對 大多數架構來說，一個可執行程序的各個部分位置有一個固定的關系。如果頁面大小增加到超過了可執行程序或 DSO (Dynamic Shared Object)創建時考慮的大小，加載操作將無法執行。腦海里記得這個限制很重要。圖 4.3 顯示了一個 ELF 二進制的對齊需求是如何決定的。它編碼在 ELF 程序頭部。

$ eu-readelf -l /bin/ls
Program Headers:
  Type   Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
...
  LOAD   0x000000 0x0000000000400000 0x0000000000400000 0x0132ac 0x0132ac R E 0x200000
  LOAD   0x0132b0 0x00000000006132b0 0x00000000006132b0 0x001a71 0x001a71 RW 0x200000
...

        在這個例子中，一個 x86-64 二進制，它的值為0×200000 = 2,097,152 = 2MB，符合處理器支持的最大頁面尺寸。

        使用較大內存尺寸有第二個影響：頁表樹的級數減少了。由于虛擬地址相對于頁面位移的部分增加了，需要用來在頁目錄中使用的位，就沒有剩下許多了。這意味著當一個 TLB 未命中時，需要做的工作數量減少了。

        超出使用大頁面大小，它有可能減少移動數據時需要同時使用的 TLB 條目數目，減少到數頁。這與一些上面我們談論的緩存使用的優化機制類似。只有現在對齊需求是巨大的。考慮到 TLB 條目數目如此小，這可能是一個重要的優化。

        4. 4 虛擬化的影響

        OS 映像的虛擬化將變得越來越流行；這意味著另一個層次的內存處理被加入了想象。進程（基本的隔間）或者 OS 容器的虛擬化，因為只涉及一個 OS 而沒有落入此分類。類似 Xen 或 KVM 的技術使 OS 映像能夠獨立運行 — 有或者沒有處理器的協助。這些情形下，有一個單獨的軟件直接控制物理內存的訪問。

 圖 4.4: Xen 虛擬化模型

        對 Xen 來說（見圖 4.4），Xen VMM (Xen 內存管理程序)就是那個軟件。但是，VMM 沒有自己實現許多硬件的控制，不像其他早先的系統（包括 Xen VMM 的第一個版本）的 VMM，內存以外的硬件和處理器由享有特權的 Dom0 域控制。現在，這基本上與沒有特權的 DomU 內核一樣，就內存處理方面而言，它們沒有什么不同。這里重要的是，VMM 自己分發物理內存給 Dom0 和 DomU 內核，然后就像他們是直接運行在一個處理器上一樣，實現通常的內存處理

        為了實現完成虛擬化所需的各個域之間的分隔，Dom0 和 DomU 內核中的內存處理不具有無限制的物理內存訪問權限。VMM 不是通過分發獨立的物理頁并讓客戶 OS 處理地址的方式來分發內存；這不能提供對錯誤或欺詐客戶域的防范。替代的，VMM 為每一個客戶域創建它自己的頁表樹，并且用這些數據結構分發內存。好處是對頁表樹管理信息的訪問能得到控制。如果代碼沒有合適的特權，它不能做任何事。 在虛擬化的 Xen 支持中，這種訪問控制已被開發，不管使用的是參數的或硬件的（又名全）虛擬化。客戶域以意圖上與參數的和硬件的虛擬化極為相似的方法，給每個進程創建它們 的頁表樹。每當客戶 OS 修改了 VMM 調用的頁表，VMM 就會用客戶域中更新的信息去更新自己的影子頁表。這些是實際由硬件使用的頁表。顯然這個過程非常昂貴：每次對頁表樹的修改都需要 VMM 的一次調用。而沒有虛擬化時內存映射的改變也不便宜，它們現在變得甚至更昂貴。 考慮到從客戶 OS 的變化到 VMM 以及返回，其本身已經相當昂貴，額外的代價可能真的很大。這就是為什么處理器開始具有避免創建影子頁表的額外功能。這樣很好不僅是因為速度的問題，而且它 減少了 VMM 消耗的內存。Intel 有擴展頁表(EPTs)，AMD 稱之為嵌套頁表(NPTs)。基本上兩種技術都具有客戶 OS 的頁表，來產生虛擬的物理地址。然后通過每個域一個 EPT/NPT 樹的方式，這些地址會被進一步轉換為真實的物理地址。這使得可以用幾乎非虛擬化情境的速度進行內存處理，因為大多數用來內存處理的 VMM 條目被移走了。它也減少了 VMM 使用的內存，因為現在一個域（相對于進程）只有一個頁表樹需要維護。 額外的地址轉換步驟的結果也存儲于 TLB。那意味著 TLB 不存儲虛擬物理地址，而替代以完整的查詢結果。已經解釋過 AMD 的帕西菲卡擴展為了避免 TLB 刷新而給每個條目引入 ASID。ASID 的位數在最初版本的處理器擴展中是一位；這正好足夠區分 VMM 和客戶 OS。Intel 有服務同一個目的的虛擬處理器 ID (VPIDs)，它們只有更多位。但對每個客戶域 VPID 是固定的，因此它不能標記單獨的進程，也不能避免 TLB 在那個級別刷新。

        對虛擬 OS，每個地址空間的修改需要的工作量是一個問題。但是還有另一個內在的基于 VMM 虛擬化的問題：沒有什么辦法處理兩層的內存。但內存處理很難（特別是考慮到像 NUMA 一樣的復雜性，見第 5 部分）。Xen 方法使用一個單獨的 VMM，這使最佳的（或最好的）處理變得困難，因為所有內存管理實現的復雜性，包括像發現內存范圍之類“瑣碎的”事情，必須被復制于 VMM。OS 有完全成熟的與最佳的實現；人們確實想避免復制它們。

圖 4.5: KVM 虛擬化模型

        這就是為什么對 VMM/Dom0 模型的分析是這么有吸引力的一個選擇。圖 4.5 顯示了 KVM 的 Linux 內核擴展如何嘗試解決這個問題的。并沒有直接運行在硬件之上且管理所有客戶的單獨的 VMM，替代的，一個普通的 Linux 內核接管了這個功能。這意味著 Linux 內核中完整且復雜的內存管理功能，被用來管理系統的內存。客戶域運行于普通的用戶級進程，創建者稱其為“客戶模式”。虛擬化的功能，參數的或全虛擬化的， 被另一個用戶級進程 KVM VMM 控制。這也就是另一個進程用特別的內核實現的 KVM 設備，去恰巧控制一個客戶域。

        這個模型相較 Xen 獨立的 VMM 模型好處在于，即使客戶 OS 使用時，仍然有兩個內存處理程序在工作，只需要在 Linux 內核里有一個實現。不需要像 Xen VMM 那樣從另一段代碼復制同樣的功能。這帶來更少的工作，更少的 bug，或許還有更少的兩個內存處理程序接觸產生的摩擦，因為一個 Linux 客戶的內存處理程序與運行于裸硬件之上的 Linux 內核的外部內存處理程序，做出了相同的假設。

        總的來說，程序員必須清醒認識到，采用虛擬化時，內存操作的代價比沒有虛擬化要高很多。任何減少這個工作的優化，將在虛擬化環境付出更多。隨著時間的過去，處理器的設計者將通過像 EPT 和 NPT 技術越來越減少這個差距，但它永遠都不會完全消失。