深入理解Linux內核——記憶體管理（1）

提要：系列文章主要參考MIT 6.828課程以及兩本書籍《深入理解Linux內核》 《深入Linux內核架構》對Linux內核內容進行總結。

記憶體管理的實現覆蓋了多個領域：

1. 記憶體中的物理記憶體頁的管理
2. 分配戴愛記憶體的伙伴系統
3. 分配較小記憶體的slab、slub、slob分配器
4. 分配非連續記憶體塊的vmalloc分配器
5. 進程的地址空間

傳統的記憶體管理主要包括段式存儲、頁式存儲、段頁式存儲，這裡我們會以這部分開始，逐步介紹Linux內核中的記憶體管理，而要學習記憶體管理，首先需要瞭解記憶體定址。所以本節內容主要講解記憶體定址的相關知識，並介紹Linux內核中的段、頁式存儲。

記憶體地址

在編程過程中，難免需要通過記憶體地址來訪問記憶體中的某些內容，那麼這個過程中地址是如何映射到對應的物理單元的呢？解決這一問題首先要區分三種不同的地址：

1. 邏輯地址：邏輯地址是包含在機器語言指令中用來指定一個操作數或者一條指令的地址。每一個邏輯地址都由一個段和一個偏移量組成，偏移量指明瞭從段開始的地方到實際地址之間的距離。（這在分段結構中表現的極為明顯）。
2. 線性地址：線性地址是一個32位的無符號數，可以用來表示高達4GB的地址。線性地址通常使用十六進位數字表示，值的範圍從0x00000000到0xffffffff（常用於頁式存儲）。
3. 物理地址：用於記憶體晶元級記憶體單元定址。它們與微處理器的地址引腳發送到記憶體匯流排上的電信號相對應。物理地址由32位或36位無符號整數表示。

記憶體控制單元(MMU)通過分段單元（硬體設備）將邏輯地址轉化為線性地址。使用分頁單元（硬體設備）把線性地址轉化為物理地址：

               --------                     -------
|邏輯地址| --> |分段單元| --> |線性地址| --> |分頁單元| --> |物理地址|
               --------                     -------

從格式上簡單區別邏輯地址與線性地址，邏輯地址包含了兩部分：段和偏移量（註意這兩者是分開的），而線性地址知識一個32位無符號數，雖然後期也會根據地址的位數再次進行劃分（詳見分頁部分），但終歸只是一個線性的無符號數。

段式存儲

硬體將邏輯地址轉化為線性地址主要由分段單元完成該任務。邏輯地址由兩部分組成：

1. 段標識符：該欄位是一個16位長的欄位，稱為段選擇符，負責從眾多段中選擇出正確的段,因為段信息會存儲在一張段描述符表中，因此需要通過段選擇符從段描述符表中索引找到正確的段描述符。
2. 指定段內相對地址的偏移量：32位長的欄位（因為一個段可能很長，因此偏移量要足夠大）

段選擇符格式如下：

        15        3     2 1 0
          --------  ----  ---
段選擇符 |  index  |  TL | RPL|
          --------  ----  ---

對於每個欄位的含義，後續在詳細講解通過段選擇符尋找對應段時會對每個欄位給出解釋。

段選擇符被存放在段寄存器中，這使得可以方便快速地找到段選擇符，段寄存器主要包括6個，分別為cs，ss，ds，es，fs，gs。其中有3個具有專門的用途：

其他3個段寄存器作一般用途，可以指向任意的數據段。

註意：cs寄存器還有一個很重要的功能：它含有一個兩位的欄位，用以指明CPU的當前特權級(GPL)。值為0代表最高優先順序，而值為3代表最低優先順序。Linux只用0級和3級，分別稱為內核態和用戶態。

段描述符

剛纔提到過，每個段由一個8位元組的段描述符表示，它描述了段的特征。段描述符放在全局描述符表（GDT）或者局部描述符表裡（LDT）中（前面提到過）。通常只定義一個GDT，而每個進程除了存放在GDT中的段之外如果還需要創建附加段，就會創建自己的LDT。GDT在主存中的地址和大小存放在gdtr控制寄存器中，當前正被使用的LDT地址和大小存放在ldtr寄存器中。如下給出一個全局段描述符例子：

在段描述符表中通常會使用如下幾種段描述符（簡單瞭解各個段的作用即下麵第一個表就好，具體欄位的名稱可以用到再回來查）：

段描述符格式如下：

段描述符中各個欄位含義如下：

快速訪問段描述符

在本節主要介紹分段單元將邏輯地址轉化為線性地址的過程。我們知道邏輯地址主要包括：16位的段選擇符和32位的段偏移量，段選擇符存放在段寄存器中。段選擇符格式如下：

        15        3     2 1 0
          --------  ----  ---
段選擇符 |  index  |  TL | RPL|
          --------  ----  ---

這裡我們需要瞭解3個欄位的含義：

由於一個段描述符是8個位元組長，因此它在GDT或LDT內的相對地址是由段選擇符的最高13位的值乘以8得到的（8=2^3,13+3=16）。例如如果GDT在0x00020000（這個值保存在gdtr寄存器中），切由段選擇符所指定的索引號為2，那麼相應的段描述符地址為0x00020000+(2*8)即0x00020010。

邏輯地址轉換為線性地址流程如下圖：

1. 先檢查段選擇符的TI欄位，以確定段描述符保存在哪一個描述符表（GDT、LDT）中。
2. 從段選擇符的index欄位計算段描述符的地址，index欄位值乘以8（一個段描述符大小），這個結果與gdtr或ldtr寄存器中的內容相加
3. 把邏輯地址的偏移量與段描述符的Base欄位的值相加就得到了線性地址。

操作系統課本中的介紹通常如下，可以與之進行對比：

註意：GDT的第一項總是設置為0。這就確保空段選擇符的邏輯地址會被認為是無效的，因此引起一個處理器異常。能夠保存在GDT中的段描述符的最大數目是8191，即2^13-1。

最後，由於整個地址轉換過程中，前兩個過程，即訪問GDT、LDT中段描述符的過程是比較耗時的，為了加速該過程，80x86處理器提供了一種附加的非編程的寄存器供6個可編程的段寄存器使用。每個非編程寄存器含有8個位元組的段描述符。通過這個非編程寄存器，達到瞭如下功能：每當一個段描述符被裝入段寄存器時，相應的段描述符就由記憶體裝入到對應的非編程CPU寄存器中，從那時起，針對那個段的邏輯地址轉換就可以不訪問主存中的GDT或LDT，只有在段寄存器內容改變時，才有必要訪問GDT或LDT。

Linux中的分段

Linux以非常有限的方式使用分段，分段可以給一個進程分配不同的線性地址空間，而分頁可以把同一線性地址空間映射到不同的物理空間，與分段相比，Linux更喜歡使用分頁方式，因為：

1. 當所有進程使用相同的段寄存器時，記憶體管理變得更簡單，也就是說他們能共用同樣的一組線性地址。
2. Linux設計目標之一時可以把它移植到絕大多數的處理器平臺上。然而，RISC體繫結構對分段的支持很有限。

2.6版的Linux只有在80x86結構下才需要使用分段。

運行在用戶態的所有Linux進程都使用一對相同的段來對指令和數據定址。這兩個段就是所謂的用戶代碼段和用戶數據段。類似的運行在內核態的所有Linux進程都使用一對相同的段對指令和數據定址，他們分別是內核代碼段和內核數據段。下表顯示了這四個重要段的段描述符欄位的值。

上面4個段，G標誌都設置為1，即limit以4096為單位。與段相關的線性地址從0開始，達到2^32-1的定址限長，這意味著在用戶態或內核態下的所有進程可以使用相同的邏輯地址。

所有段都從0x00000000開始，表示Linux下邏輯地址和線性地址是一致的，即邏輯地址的偏移量欄位的值與相應的線性地址的值總是一致的。

那如何區分這4個段呢？

如前所述，CPU的當前特權級（CPL）反映了進程是在用戶態還是內核態，並由存放在cs寄存器中的段選擇符的RPL欄位指定。只要當前特權級被改變，一些段寄存器必須相應地更新。例如，當CPL=3時（用戶態），ds寄存器必須含有用戶數據段的段選擇符，而當CPL=0時，ds寄存器必須含有內核數據段的段選擇符。

頁式存儲

分頁單元（paging unit）把線性地址轉換成物理地址。其中的一個關鍵任務是把所請求的訪問類型與線性地址的訪問許可權項比較，如果這次記憶體訪問是無效的，就產生一個缺頁異常。

為了效率起見，線性地址被分成以固定長度為單位的組，稱為頁（page）。頁內部連續的線性地址被映射到連續的物理地址中。這樣，內核可以指定一個頁的物理地址和其存儲許可權，而不用指定頁所包含的全部線性地址的存取許可權。

分頁單元把所有的RAM分成固定長度的頁框（有時叫做物理頁）。每一個頁框包含一個頁（page），也就是說一個頁框的長度與一個頁的長度一致。頁框是主存的一部分，因此也是一個存儲區域。

把線性地址映射到物理地址的數據結構稱為頁表。頁表存放在主存中，併在啟動分頁單元之前必須由內核對頁表進行適當的初始化。

從80386開始，所有的80x86處理器都支持分頁，它通過設置cr0寄存器的PG標誌啟用。當PG=0時，線性地址就被解釋成物理地址。

常規分頁

從80386起，Intel處理器的分頁單元處理4KB的頁。

32位的線性地址被分為3個域（線性地址是根據位數劃分的，是隱式劃分的功能）：

• Directory(目錄):最高10位。
• Table(頁表)：中間10位。
• Offset(偏移量)：最低12位。

線性地址轉換為物理地址時，需要依賴兩張表：頁目錄表和頁表。轉換過程如下圖：

每個活動進程必須有一個分配給它的頁目錄，正在使用的頁目錄的物理地址存放在控制寄存器cr3中。線性地址內的Directory欄位決定頁目錄表中的目錄項，而目錄項指向適當的頁表。地址的Table欄位依次又決定頁表中的表項，而表項含有頁所在頁框的物理地址。Offset欄位決定頁框內的相對位置，由於它是12位長，故每一頁含有4096位元組的數據。

頁目錄項表和頁表中的每項具有相同的結構（可以先暫時跳過，碰到使用的欄位可以再回來看），每項欄位如下：

這裡再簡單強調一個問題，為何要使用多級頁表：

常規分頁的加速策略

當今的微處理器時鐘頻率接近幾個GHz，而動態RAM（DRAM）晶元的存取時間是時鐘周期的數百倍。這意味著，當從RAM中取操作數或向RAM中存放結果這樣的指令執行時，CPU可能等待很長時間。

硬體高速緩存

為了縮小CPU和RAM之間的速度不匹配，引入了硬體高速緩存記憶體（hardware cache memory）。硬體高速緩存基於著名的局部性原理（locality principle），它表明由於程式的迴圈結構及相關數組可以組織成線性數組，最近最常用的相鄰地址在最近的將來又被用到的可能性極大。80x86體繫結構中引入了一個叫行（line）的新單位。行由幾十個連續的位元組組成，它們以脈衝突發模式（burst mode）在慢速DRAM和快速的用來實現告訴緩存的片上靜態RAM（SRAM）之間傳送，用來實現高速緩存。

高速緩存再被細分為行的子集。在一種極端的情況下，高速緩存可以是直接映射的(direct mapped),這時主存中的一個行總是存放在高速緩存中完全相同的位置。在另一種極端情況下，高速緩存是充分關聯的(fully associative)，這意味著主存中的任意一個行可以存放在高速緩存中的任意位置。但是大多數高速緩存在某種程度上是N-路組關聯的(N-way set associative)，意味著主存中的任意一個行可以存放在高速緩存N行中的任意一行中。例如，記憶體中的一個行可以存放到一個2路組關聯高速緩存兩個不同的行中。

如下圖，硬體高速緩存由兩部分組成：

1. 硬體高速緩存記憶體：負責存放真正的行
2. 高速緩存控制器：存放一個表項數組，每個表項對應高速緩存記憶體中的一個行。每個表項有一個標簽(tag)和描述高速緩存行狀態的幾個標誌(flag)。這個標簽由一些位組成,這些位讓高速緩存控制器能夠辨別由這個行當前所映射的記憶體單元。這種記憶體物理地址通常分為3組:最高幾位對應標簽，中間幾位對應高速緩存控制器的子集索引，最低幾位對應行內的偏移量。

這裡引用鏈接中的一部分描述，對記憶體物理地址進行描述（否則後續的高速緩存訪問過程可能比較難以看懂）：

訪問cache時，訪問地址可分為3個部分：偏移量Offset、索引Index和標簽Tag。

• Offset是塊內地址，在地址的低幾位，因為cache塊一般比較大，如每個cache塊32位元組或64位元組。以32個位元組為例，讀cache時把32個位元組即256位作為一組一起都讀出來，用Offset在32位元組中選擇本次訪問所需的字或雙字等；
• Index用來索引cache，訪問時用Index作為訪問cache的地址。
• 地址的高位是訪問cache的Tag，由於cache的大小有限，每個cache行可能對應記憶體中的若幹個存儲塊，cache中的每一行都要用tag來標識當前存的是哪個存儲塊，訪問時用地址的Tag跟cache存的tag進行比較，如果相等就給出命中信號hit。

瞭解了上面的內容，原書中的高速緩存訪問過程就可以很容易看懂了：

1. 當訪問一個RAM存儲單元時,CPU從物理地址中提取出子集的索引號並把子集中所有行的標簽與物理地址的高幾位相比較。
2. 如果發現某一個行的標簽與這個物理地址的高位相同，則CPU命中一個高速緩存(cache hit);否則,高速緩存沒有命中(cache miss)。

最後給出了查找到高速緩存中具體內容後的一些後操作：

1. 當命中一個高速緩存時，高速緩存控制器進行不同的操作，具體取決於存儲類型。

• 對於讀操作，控制器從高速緩存行中選取數據並送到CPU寄存器；不需要訪問RAM而節約了CPU時間。因此高速緩存系統起到了其應有的作用。
• 對於寫操作，控制器可能採用以下兩個基本策略之一，分別稱之為通寫和回寫。
  • 在通寫中，控制器總是既寫RAM也寫高速緩存行，為了提高寫操作的效率關閉高速緩存。
  • 回寫方式只更新高速緩存行，不改變RAM的內容，提供了更快的功效。當然，回寫結束後，RAM最終必須被更新。只有當CPU執行一條要求刷新高速緩存表項的指令時，或者當一個FLUSH硬體信號產生時（通常在高速緩存不命中之後），高速緩存控制器才把高速緩存行寫回到RAM中。

2. 當高速緩存沒有命中時，高速緩存行被寫回到記憶體中，如果有必要的話，吧正確的行從RAM中取出放到高速緩存的表項中。

頁目錄項表和頁表中的每項具有相同的結構 中PCD和PWT兩個標誌用於控制上述操作：

• PCD（Page Cache Disabit）標誌指明當訪問包含在這個頁框中的數據時，高速緩存功能必須被啟用還是禁用。
• PWT（page Write-Through）標誌指明當把數據寫到頁框時，必須使用的策略是回寫策略還是通寫策略。

最後給出一個鏈接，較為詳細的介紹了硬體高速緩存，如果感興趣可以繼續瞭解。

轉換後援緩衝器（TLB）

註意：這個TLB不是Thread Local Buffer。

除了通用硬體高速緩存之外，80x86處理器還包含了另一個稱為轉換後援緩衝器或TLB（Translation Lookaside Buffer）的高速緩存用於加快線性地址的轉換。當一個線性地址被第一個使用時，通過慢速訪問RAM中的頁表計算出相應的物理地址。同時物理地址被存放在一個TLB表項（TLB entry）中，以便以後對同一個線性地址的引用可以快速地得到轉換。

在多處理器系統中，每個CPU都有自己的TLB，這叫做該CPU的本地TLB。與硬體高速緩存相反，TLB中的對應項不必同步，這是因為運行在現有CPU上的進程可以使同一線性地址與不同的物理地址發生聯繫。

當CPU的cr3控制寄存器被修改時，硬體自動使本地TLB中的所有項都無效，這是因為新的一組頁表被啟用而TLB指向的是舊數據。

64位系統中的分頁

通過上面我們可以看到32位系統使用兩級分頁就可以滿足需求，那64位系統呢？

首先假設一個大小為4KB的標準頁。因為1KB覆蓋2^{10個地址的範圍，4KB覆蓋2}12個地址，所以offset欄位是12位。這樣線性地址就剩下52位分配給Table和Directory欄位。如果我們現在決定僅僅使用64位中的48位來定址(這個限制仍然使我們自在地擁有256TB的定址空間!)，剩下的48-12=36位將被分配給Table和Directory欄位。如果我們現在決定為兩個欄位各預留18位,那麼每個進程的頁目錄和頁表都含有2^18個項,即超過256000個項，而一頁無法放下如此多的頁目錄項和頁表項。

因此,所有64位處理器的硬體分頁系統都使用了額外的分頁級別。使用的級別數量取決於處理器的類型。下表總結出了一些Linux支持64位平臺使用的硬體分頁系統的主要特征：

Linux本身提供了一種通用的分頁系統，它適用於絕大多數所支持的硬體分頁系統。

Linux的分頁

Linux採用了一種同時適用於32位和64位系統的普通分頁模型。到2.6.10版本，Linux採用三級分頁的模型。從2.6.11版本開始，採用了四級分頁模型，分為4種頁表如下：

• 頁全局目錄（Page Global Directory）
• 頁上級目錄（Page Upper Directory）
• 頁中間目錄（Page Middle Directory）
• 頁表（Page Table）

結構如下圖：

頁全局目錄包含若幹頁上級目錄的地址，頁上級目錄又依次包含若幹頁中間目錄的地址，而頁中間目錄又包含若幹頁表地址。因此線性地址被分成五個部分。上圖沒有顯示位數，因為每一部分的大小與具體的電腦體繫結構有關。

對於沒有啟用物理地址擴展的32位系統，兩級頁表已經足夠了。Linux通過使“頁上級目錄”位和“頁中間目錄”位全為0，從根本上取消了頁上集目錄和頁中間目錄欄位。不過，頁上級目錄和頁中間目錄在指針序列中的位置被保留，以便同樣的代碼在32位系統和64位系統下都能使用。內核為頁上集目錄和頁中間目錄保留了一個位置，這是通過把它們的頁目錄項數設置為1，並把這兩個目錄項映射到全局目錄一個適當的目錄而實現的。

總結

本篇文章主要講解記憶體地址轉換的主要內容，並對Linux內核對段式存儲和頁式存儲進行了簡單的瞭解，下一篇文章將開始進行真正記憶體管理相關的內容。