位址轉譯與 TLB (Address Translation & TLB)

Overview Table

頁層級保護:PTE 權限位 (p.849)

位址轉譯硬體每次都要讀 PTE,因此在 PTE 加上權限位 (permission bits) 就能以頁為單位控管存取:

• SUP:是否須在 kernel (supervisor) mode 才能存取;user mode 只能存取 SUP=0 的頁。
• READ / WRITE:控制讀/寫權限。
• 違反權限 → CPU 觸發 general protection fault → kernel 例外處理器送 SIGSEGV 給行程;shell 回報為 "segmentation fault"。

9.6 位址轉譯基礎 (p.849-851)

符號整理(Figure 9.11)

形式化定義:位址轉譯是 $N$ 元素 VAS 到 $M$ 元素 PAS 的映射

$\text{MAP}(A)=A^{\prime }$ 若虛擬位址 $A$ 的資料在實體位址 $A^{\prime }$;$\text{MAP}(A)=\mathrm{\varnothing }$ 若不在實體記憶體。

硬體轉譯流程(Figure 9.12)

• PTBR (page table base register):CPU 控制暫存器,指向目前行程的 page table。
• $n$-bit VA = $(n-p)$-bit VPN + $p$-bit VPO;VPN 當作 page table 的索引(VPN 0 → PTE 0...)。
• PA = PTE 中的 PPN 串接 VPO;因虛實頁同為 $P$ bytes,PPO 恆等於 VPO(不需轉譯)。

              n-1        p p-1      0
  VA:        [    VPN     |   VPO   ]
                  |            |
   PTBR ──> Page  v            |
            Table[VPN] ─> PTE  |
                  | (valid=1)  |  valid=0 → page fault
                  v            v
  PA:        [    PPN     |   PPO   ]
              m-1        p p-1      0

Page hit 流程(純硬體,Figure 9.13a)

1. Processor 產生 VA 送給 MMU。
2. MMU 產生 PTEA(PTE address)向 cache/main memory 請求。
3. Cache/memory 回傳 PTE 給 MMU。
4. MMU 組出 PA 送給 cache/memory。
5. Cache/memory 回傳資料字給 processor。

Page fault 流程(硬體 + OS,Figure 9.13b)

1-3. 同上。4. PTE 的 valid bit = 0 → MMU 觸發例外,控制權轉給 kernel 的 page fault handler。5. Handler 選出 victim page;若已被修改(dirty)則先寫回磁碟(page out)。6. Handler 將新頁 page in,並更新記憶體中的 PTE。7. Handler 返回原行程,重新執行 faulting instruction;這次變成 page hit。

Page hit:                          Page fault:
CPU ──VA──> MMU ──PTEA──> Mem      CPU ──VA──> MMU ──PTEA──> Mem
            MMU <──PTE─── Mem                  MMU <──PTE──── Mem (valid=0)
            MMU ──PA────> Mem                  MMU ──Exception──> Fault handler
CPU <─Data───────────────Mem                  handler: victim page ──> Disk
                                              handler: new page  <── Disk
                                              return & restart instruction

9.6.1 Cache 與 VM 的整合 (p.853)

• 多數系統選擇 physical addressing 的 SRAM cache:轉譯發生在 cache lookup 之前。
• 好處:多個行程可同時在 cache 中有 block、可共享同一虛擬頁的 block;cache 不必處理保護問題(權限已在轉譯時檢查)。
• PTE 和一般資料一樣可以被 cache(MMU 的 PTEA 請求會先查 L1)。

9.6.2 用 TLB 加速位址轉譯 (p.853-855)

每次 CPU 產生 VA,MMU 都要讀一次 PTE——最壞情況多一次記憶體存取(數十至數百 cycle);即使 PTE 在 L1 也要數個 cycle。解法:在 MMU 內放一個小型 PTE cache,即 TLB (translation lookaside buffer)。

• TLB 是小型、virtually addressed 的 cache,每行存一個 PTE,通常高關聯度 (high associativity)。
• 若 TLB 有 $T=2^t$ 個 set:TLBI = VPN 的最低 t 位,TLBT = VPN 其餘高位。

     n-1          p+t p+t-1    p p-1      0
VA: [  TLBT (tag)   | TLBI(idx) |   VPO   ]
     └────────── VPN ──────────┘

TLB hit(Figure 9.16a,常見情形):

1. CPU 產生 VA → 2-3. MMU 從 TLB 取得 PTE → 4. MMU 組 PA 送 cache/memory → 5. 回傳資料。
   全部步驟都在晶片內的 MMU 完成,因此很快。

TLB miss(Figure 9.16b):MMU 必須向 L1 cache/memory 發 PTEA 取 PTE,新取得的 PTE 存入 TLB(可能覆蓋既有 entry),再組 PA 完成存取。

9.6.3 多層 Page Table (p.855-857)

單層表的問題:32-bit 位址空間、4 KB 頁、4-byte PTE → page table 大小 = $2^{32}/2^{12}\times 4\text{B}=4\text{MB}$,且須常駐記憶體;64-bit 空間更不可行。

兩層範例(32-bit、4KB 頁、4B PTE,Figure 9.17):

• Level 1 每個 PTE 負責 4 MB chunk(= 1,024 個連續頁);1,024 個 L1 PTE 即涵蓋 4 GB。
• 若 chunk i 內全部頁未配置 → L1 PTE i 為 null,對應的 level 2 表根本不必存在。
• 若至少一頁已配置 → L1 PTE i 指向一個 level 2 page table 的基底;L2 PTE 才對映 4-KB 頁。
• 每個 L1/L2 表 = 1,024 × 4 B = 4 KB,恰為一頁大小。

省記憶體的兩個機制:

1. null L1 PTE → 子表不存在(典型程式的 4 GB 空間大多未配置)。
2. 只有 level 1 表須常駐;level 2 表可由 VM 系統按需建立、換入換出。

k 層一般化(Figure 9.18):VA 切成 k 個 VPN + 一個 VPO;VPN i 索引第 i 層表;第 j 層($1\le j\le k-1$)PTE 指向第 j+1 層表基底;第 k 層 PTE 才含 PPN(或磁碟區塊位址);PPO = VPO 不變。

VA: [ VPN 1 | VPN 2 | ... | VPN k |  VPO ]
       |       |             |       |
       v       v             v       |
  L1 PT ──> L2 PT ──> ... ──> Lk PT  |
  (PTBR/CR3)              PTE→ PPN   |
                               v     v
PA:              [    PPN    |  PPO  ]

9.6.4 End-to-End 轉譯範例 (p.857-860)

假設:byte-addressable、1-byte 存取、$n=14$、$m=12$、$P=64$($p=6$);TLB 4-way、16 entries(→ 4 sets);L1 d-cache 為 physically addressed、direct-mapped、4-byte block、16 sets。

推導欄位寬度:

• VPO = PPO = $p$ = 6 bits;VPN = $14-6$ = 8 bits;PPN = $12-6$ = 6 bits。
• TLB:4 sets → TLBI = VPN 低 2 位,TLBT = VPN 高 6 位。
• Cache:block 4 B → CO = 2 bits;16 sets → CI = 4 bits;CT = $12-4-2$ = 6 bits。

VA (14 bits): [ TLBT(6) | TLBI(2) |  VPO(6) ]
              └────── VPN(8) ─────┘
PA (12 bits): [  CT(6)  |  CI(4)  |  CO(2)  ]
              └ PPN(6) ┘└──── PPO(6) ─────┘

手算流程(VA = 0x03D4,Figure 9.20 快照):

其他可能路徑 (p.860):TLB miss → 到 page table 取 PTE;PTE invalid → page fault,kernel 換頁後重跑指令;PTE valid 但 cache miss → 到 main memory 取 block。

9.7 個案研究:Intel Core i7 / Linux (p.861-865)

記憶體系統概觀(Figure 9.21)

• 支援 48-bit (256 TB) 虛擬位址空間、52-bit (4 PB) 實體位址空間(另有 32-bit 相容模式)。
• 頁大小開機時可設 4 KB 或 4 MB;Linux 用 4 KB。

TLB 為 virtually addressed;各 cache 為 physically addressed。核心間以 QuickPath 點對點連結通訊。

Core i7 位址轉譯(Figure 9.22, 9.25)

• 四層 page table;每個行程有私有的階層。行程執行時已配置頁的 page table 全部常駐記憶體(架構上允許換出)。
• CR3 控制暫存器存 level 1 表的實體位址;CR3 是行程 context 的一部分,context switch 時還原。
• 36-bit VPN 切成 4 個 9-bit 欄位,各為該層表的 offset;VPO = 12 bits(4 KB 頁)。
• L1 d-cache 端:PA 切成 CT(40)| CI(6)| CO(6)。

VA(48): [ VPN1(9) | VPN2(9) | VPN3(9) | VPN4(9) | VPO(12) ]
             |         |         |         |        |
CR3 ──> L1 PT ──> L2 PT ──> L3 PT ──> L4 PT        |
     (page global (page upper (page middle (page    |
      directory)   directory)  directory)  table)  |
       512 GB/項    1 GB/項     2 MB/項    4 KB/項  |
                                        PTE → PPN(40)
                                             v      v
PA(52):                            [ PPN(40) | PPO(12) ]

PTE 格式(Figure 9.23, 9.24)

Level 1-3 PTE(每項指向一個 4 KB 子表)與 Level 4 PTE(指向 4 KB 實體頁)欄位:

• P = 0 時,其餘位元可供 OS 使用(例如存放頁在磁碟上的位置)。
• A/D 位由 MMU 硬體設定、由 kernel 以特殊 kernel-mode 指令清除——這是 kernel page fault handler 實作替換策略與寫回判斷的依據。

9.7.2 Linux 虛擬記憶體系統 (p.864-867)

Kernel virtual memory

每個行程的位址空間 = 使用者部分(code、data、heap、shared library、stack)+ user stack 之上的 kernel virtual memory:

• 所有行程共享的區域:kernel 的 code 與全域資料結構;此外 Linux 把一段連續虛擬頁直接映到全部 DRAM 的連續實體頁,讓 kernel 能方便存取任意實體位置(如存取 page table、對映到特定實體位址的裝置做 memory-mapped I/O)。
• 各行程不同的區域:該行程的 page tables、kernel 在此行程 context 執行時用的 kernel stack、記錄位址空間組織的資料結構。

Areas(Figure 9.27)

Linux 把虛擬記憶體組織成 area(又稱 segment) 的集合:一段已配置的連續虛擬記憶體,其頁彼此相關(code、data、heap、shared library、stack 各是一個 area)。

• 每個存在的虛擬頁都屬於某個 area;不屬於任何 area 的頁不存在、不可被參照,也不耗任何 kernel/記憶體/磁碟資源 → 位址空間可以有 gap。

task_struct        mm_struct         vm_area_struct 串列
+--------+        +--------+        +----------+
|  mm ---+------->| pgd ---+--CR3   | vm_end   |    對應一個 area
|  ...   |        | mmap --+------->| vm_start |    (shared libs / data
+--------+        +--------+        | vm_prot  |     / text ...)
                                    | vm_flags |
                                    | vm_next -+--> 下一個 area struct
                                    +----------+

• 行程執行時,kernel 把 pgd 存入 CR3。

Linux Page Fault 處理(Figure 9.28, p.868-869)

MMU 轉譯位址 A 觸發 page fault 後,kernel handler 依序判斷:

page fault on VA = A
  |
  |-- (1) A 落在某個 area 內嗎?(比對各 vm_start/vm_end)
  |        否 --> segmentation fault,終止行程
  |
  |-- (2) 存取方式合法嗎?(寫唯讀頁?user mode 讀 kernel 記憶體?)
  |        否 --> protection exception,終止行程
  |
  '-- (3) 合法位址 + 合法操作 => 正常 page fault:
          選 victim -> dirty 則換出 -> 換入新頁 -> 更新 page table
          -> handler 返回,CPU 重跑 faulting instruction(這次正常轉譯)

Exam/Test Patterns

Related Notes

• 09-Virtual-Memory/01-Address-Spaces-and-VM-Caching
• 09-Virtual-Memory/02-VM-Management-and-Protection
• 09-Virtual-Memory/04-Memory-Mapping
• 06-Memory-Hierarchy/03-Cache-Memories
• 08-Exceptional-Control-Flow/01-Exceptions
• 03-Machine-Level-Programs/06-Buffer-Overflow-and-Pointer-Safety