Jserv's blog

探索 Linux Memory Model (上)

以下翻譯 IBM 軟體工程師 Vikram Shukla 的文章 [Explore the Linux memory model]，重要的技術術語我保留不翻譯，行文也稍調整，翻譯也主要是閱讀時的筆記，或許不甚流暢。

標題： 探索 Linux Memory Model
原作： Vikram Shukla (vikshukl@in.ibm.com), Software Engineer, IBM
繁體中文翻譯： 黃敬群 (Jim Huang / jserv)
最後更新日期： 24 Jan 2006

理解 Linux Kernel 中的 memory model 是揭開 Linux 複雜設計與實做層層布幕的第一步，本文將給予關於 Linux memory model 的入門等級介紹。

Linux 採用 monolithic 途徑以規範基本操作，或用以實做作業系統服務的系統呼叫的集合，這些包含了執行於 supervisor 模式中若干模組的 process management、cocurrency，以及 memory management。[譯注：相對於 Linux kernel 的 monolithic 途徑，就是 1990 年代相當熱門的 microkernel 設計，以第二代 microkenel 設計的代表 L4 來說，in-kernel 的系統呼叫不過 12 個 (傳統的 kernel 則有兩百以上之譜)，上述的模組則獨立存在，以 Fast IPC 作溝通] 並且。雖然 Linux 基於硬體相容性考量，維護了 segment control unit model [譯注：這是 Intel 80386 保護模式的術語，文後的參考書籍《Understanding the Linux Kernel, Third Edition]》在這個主題有相當清楚的闡述]，不過在最小層次來說，仍採用這個模式。與 memory management 相關的主要議題有：

• VMM (Virtual Memory Management) - 對應用程式記憶體需求與實體記憶體的邏輯上分層機制
• Physical memory management
• Kernel virtual memory management / kernel memory allocator - 用以提供記憶體需求與配置的元件，這些需求可能是來自 kernel 或從 user 端。
• Virtual address space management
• Swapping 與 caching

本文將協助讀者從 memory management 的角度，來理解 Linux kernel 內部的以下行為：

• segment control unit model - 通論以及 Linux 的行為
• paging model - 通論以及 Linux 的行為
• memory zone 的實際細節

本文無法詳細探討 Linux kernel 管理記憶體的細節，但文後關於 memory model 與其定址處理的概念將對理解細節有很大的助益，並且儘管本文著重於 x86 硬體架構，不過同樣的概念可以推廣到其他硬體架構。[譯注：IBM developerWorks 其他文章有探討 Linux 在 PowerPC 硬體架構的議題，很值得參考]

x86 記憶體架構
x86 分成以下三種記憶體定址方式：

• logical address - 顧名思義，這段 adress 與實體記憶體是邏輯上的關聯 (直接或間接)，通常用在一個 controller [譯注：包含 Linux Device Driver] 要求資訊時
• linear address (或 flat address space [譯注：在 Intel Developer Manual 中後者較常見]) - 以 0 作起點的記憶體區段，後繼的 byte 計數則遞增，如 0, 1, 2, 3, ... 等，直到記憶體區段的終點，這是絕多數非 x86 架構的硬體採用的設計 [譯注：特別是 ARM 與 MIPS 這類的 RISC]。Intel 採用的配置方式則迥異於前，透過 64 kb 長度的 segment 切割記憶體， 伴隨 segment register 指向特定 segment base address，用以表示目前使用中的 segment。在 Intel 32 位元的硬體架構 [譯注：也就是 IA32]，可視為 flat address space，但使用了 segment
• physical address - 實體記憶體 bus 所表示的記憶體範圍 [譯注：特別是在硬體 Block diagram 可見區域]，與前述的 logical address 相較，physical address 的差異在於 memory management unit，該單元是轉換 logical address 到 physical address

x86 CPU 使用兩個單元來作 logical address 到 physical address 的轉換，分別是 segmented unit 與 paging unit，示意圖如下：

接下來，將探討 segment control unit model。

Segment control unit model 通論
segmentation model 背後的基本想法是以一組 segment 來作記憶體管理，每個 segment 都有專屬的 address space。每個 segment 由以下兩個部份組成：

• base address - 內含特定實體記憶體位址的 address
• length value - 指定該 segment 的長度

以 segment 劃分的 address 也包含兩個部份： segment selector 與 offset into segment。前者描述了欲使用的 segment，而欲使用的 segment 也內含 base address 與 length value，而後者針對真實的記憶體存取，指定了自 base address 的 offset (偏移量)。對映到實體記憶體，真實的記憶體就是 offset 與 base address 值的和 (sum)，倘若 offset 值超過了 segment 的長度，系統會產生 protection violation。以扼要的文字描述：

Segmented Unit 表示為 -> Segment: Offset model 也可以表示為 -> Segment Identifier: Offset

每個 segment 是個 16-bit 的欄位，稱為 segment identifier 或 segment selector，x86 硬體有一些可程式化的 register，稱為 segment register，可保存這些 segment seletor。這些 register 是： cs (code segment)、ds (data segment)，以及 ss (stack segment)。每個 segment identifier 識別以 64-bit (8 bytes) segment descriptor 表示的 segment，這些 segment descriptor 儲存於一個 GDT (Global Descriptor Table)，也可能儲存於 LDT (Local Descriptor Table) 中，示意圖如下：


每次 segment seletor 載入到 segment register 時，對應的 segment descriptor 會自記憶體載入到非可程式化的 CPU register。每個 segment descriptor 是 8-bytes 的長度，並在記憶體中以單一 segment 表示，儲存於 LDT 或 GDT 中。The segment descriptor entry contains both a pointer to the first byte in the associated segment represented by the Base field and a 20-bit value (the Limit field) which represents the size of the segment in memory. [譯注：抓不到感覺，保留原文，直接參考下面的圖可以協助理解]

其他欄位包含了特殊的屬性，像是 privilege level 與 segment type (cs 或 ds)，segment type 是以 4-bit 表示的 Type 欄位。

因為我們使用非可程式化的 register，當 logical address 到 linear address 轉換進行時，GDT 或 LDT 不會受到影響，這可加速記憶體轉換的速度。

segment selector 包含以下項目：

• 13-bit index - 識別在 GDT 或 LDT 中對應的 segment descriptor entry
• TI (Table Indicator) flag - 如果 TI flag = 0 表示 segment descriptor 在 GDT，而若是 1，表示 segment descriptor 在 LDT 中
• RPL (request privilege level) - 定義當對應 segment selector 載入於 segment register 時，目前 CPU 的 privilege level

既然 segment descriptor 的長度是 8 bytes，其在 GDT 或 LDT 的相對 address 可由 segment selector 最前面 13 bits 與 8 的乘積獲得。比方說，如果 GDT 儲存於 address 0x0002000，且 segment selector 的 Index 值為 2，那麼，對應的 segment descriptor 為 (2*8) + 0x0002000 。可儲存於 GDT 的 segment descriptor 的總和為 (2^13 - 1)，也就是 8191 。下圖表示了從 logical address 取得 linear address 的過程：

以上就是 Segment control unit model 的一般性介紹 [譯注：看到這裡，想必一定開始頭暈了，建議閱讀《Understanding the Linux Kernel, Third Edition]》前三章，書中有更詳盡的圖表與描述]，那 Linux 有什麼特別之處呢？

Segment control unit in Linux
在 Linux 中，前述的模式有了小量的修改。作者已經注意到 Linux 以較為侷限的方式，使用 segmentation model：在 Linux 中，所有 segment register 指向相同範圍的 segment address，換言之，每個 segment register 使用同一組的 linear address，這讓 Linux 得以使用有限數量的 segment descriptor，因此，所有 descriptor 可保持於 GDT。這個模式的優點有兩項：

• 在所有 process 使用相同的 segment register 值 (當分享相同組的 linear address)，Memory management 可更簡單
• 達到多數硬體架構可支援的可攜性，有些 RISC 處理器也支援這種侷限的 segmentation [譯注：像是 Sun Sparc]

下圖展示 Linux 的修改模式，由此可見 segment register 指向一組相同的 address：


Segment descriptors
Linux 使用以下 segment descriptor：

• kernel code segment
• kernel data segment
• user code segment
• user data segment
• TSS segment
• 預設 LDT segment

讓我們進一步探討。

在 GDT 中的 kernel code segment descriptor 有以下數值：

• Base = 0x00000000
• Limit = 0xffffffff (2^32 -1) = 4GB
• G (granularity flag) = 1 表示 pages 中的 segment size
• S = 1 表示正常的 code / data segment
• Type = 0xa 表示可被讀取與執行的 code segment
• DPL value = 0 表示 kernel mode

與此 segment 相關的 linear address 為 4 GB，S = 1 與 type = 0xa 參考該 code segment，seletor 位於 cs register 中。在 Linux kernel 中，可透過 _KERNEL_CS macro 來存取對應的 segment selector。

對 kernel code segment 來說，kernel data segment descriptor 有相似的數值，除了 file Type 被設定為 2，這表示了該 segment 為 data segment，並且 selector 儲存 ds register。在 Linux kernel 中，可透過 _KERNEL_DS macro 來存取對應的 segment selector。

user code segment 為所有的執行於 user mode 的 process 所分享，在 GDT 中對應的 segment descriptor 有以下的數值：

• Base = 0x00000000
• Limit = 0xffffffff
• G = 1
• S = 1
• Type = 0xa 表示可被讀取與執行的 code segment
• DPL = 3 表示 user mode

在 Linux kernel 中，可透過 _USER_CS macro 以存取該 segment selector。在 user data segment descriptor 中，唯一有更動的欄位是 Type，更動為 2，表示為可被讀取與寫入的 data segment，在 Linux kernel 中，可透過 _USER_DS macro 以存取該 segment selector。

除了上述的 segment descriptors，GDT 對於每個建立的 process 還有兩個 segment descriptors： TSS 與 LDT segments。

每個 TSS segment descriptor 指向不同的 process，TSS 保留每個 CPU 硬體的 context information [譯注：最少包含 register 與狀態值]，以便於 context switch 的過程中使用。舉例來說，從 User mode 切換到 Kernel mode 時，x86 CPU 會從 TSS 取得 kernel mode stack 的 address。

每個 process 有其獨立的、對應該 process (decriptor)，並且儲存於 GDT 中的 TSS descriptor，該 descriptor 有以下數值：

• Base = &tss (對應 process descriptor 的 TSS field 的 address，例如 &tss_struct) - 定義於 Linux kernel 的 schedule.h 檔案中
• Limit = 0xeb (TSS segment 長度為 236 bytes)
• Type = 9 或 11
• DPL = 0. user mode 不會存取 TSS，所以 G flag 是清除的

所有的 process 分享預設的 LDT segment，一般情況下，LDT segment 包含了空的 segment descriptor。預設的 LDT segment descriptor 儲存於 GDT 中，Linux 所產生的 LDT 有 24 bytes，預設情況下，以下三個 entries 總是有效的 (present)：

LDT[0] = null
LDT[1] = user code segment
LDT[2] = user data/stack segment descriptor

Calculating TASKS
為了要計算 GDT 中最大的 permission entries，知悉 NR_TASKS (用以決定 Linux 對於同時執行的 process 數量，在 kernel source 中預設為 512，允許最多 256 對單一 instance 的連線數量) 是必要的。允許在 GDT 中的 entries 總和可用以下計算式決定：

GDT 的 entries 數量 = 12 + 2 * NR_TASKS
在文章前面已經提過，x86 硬體中，GDT 可有的 entries 數量 = 2^13 -1 = 8192

[譯注： NR_TASKS 這個 macro definition 首次出現於 Linux 的「參考對象」Minix 中，在 Linux kernel 改版時，曾經從 sched.h 移到 tasks.h]
8192 segment descriptor 之外，Linux 使用六個 segment descriptors, 另外四個用以 APM 功能 (advanced power management features)，還有四個在 GDT 中的保留未使用，因此，在 GDT 中可能的數量為8192 - 14 = 8180 。

在任何時間，在 GDT 中不可能有超過 8180 個 entries，因此：

2 * NR_TASKS = 8180
NR_TASKS = 8180/2 = 4090

為什麼要 2 * NR_TASKS 呢？因為對每個建立的 process 來說，不只有 TSS descriptor (用以維護 context-switch 的 context) 會被載入，而且 LDT descriptor 也會被載入。

在 x86 的數量限制過去在 2.2 kernel 是個議題，不過自從 2.4 kernel 開始，這個問題消除了，部份是因為 context switching (這讓使用 TSS 成為必然) 與硬體關聯的抽離，並且引入 process switching 所致。

接下來，我們來探討 paging model。
(待續...)
由 jserv 發表於 January 28, 2006 08:30 PM