Caffeinated 6.828：實驗 2：記憶體管理 | Linux 中國

簡介

在本實驗中，你將為你的作業系統寫記憶體管理方面的程式碼。記憶體管理由兩部分組成。

第一部分是內核的物理記憶體分配器，核心透過它來分配記憶體，以及在不需要時釋放所分配的記憶體。分配器以頁page為單位分配記憶體，每個頁的大小為 4096 位元組。你的任務是去維護那個資料結構，它負責記錄物理頁的分配和釋放，以及每個分配的頁有多少行程共享它。本實驗中你將要寫出分配和釋放記憶體頁的全套程式碼。

第二個部分是虛擬記憶體的管理，它負責由內核和使用者軟體使用的虛擬記憶體地址到物理記憶體地址之間的對映。當使用記憶體時，x86 架構的硬體是由記憶體管理單元（MMU）負責執行對映操作來查閱一組頁表。接下來你將要修改 JOS，以根據我們提供的特定指令去設定 MMU 的頁表。

預備知識

在本實驗及後面的實驗中，你將逐步構建你的核心。我們將會為你提供一些附加的資源。使用 Git 去獲取這些資源、提交自實驗 1[1] 以來的改變（如有需要的話）、獲取課程倉庫的最新版本、以及在我們的實驗 2 （origin/lab2）的基礎上建立一個稱為 lab2 的本地分支：

1. athena% cd ~/6.828/lab
2. athena% add git
3. athena% git pull
4. Already up-to-date.
5. athena% git checkout -b lab2 origin/lab2
6. Branch lab2 set up to track remote branch refs/remotes/origin/lab2.
7. Switched to a new branch "lab2"
8. athena%

上面的 git checkout -b 命令其實做了兩件事情：首先它建立了一個本地分支 lab2，它跟蹤給我們提供課程內容的遠端分支 origin/lab2 ，第二件事情是，它改變你的 lab 目錄的內容以反映 lab2 分支上儲存的檔案的變化。Git 允許你在已存在的兩個分支之間使用 git checkout *branch-name* 命令去切換，但是在你切換到另一個分支之前，你應該去提交那個分支上你做的任何有意義的變更。

現在，你需要將你在 lab1 分支中的改變合併到 lab2 分支中，命令如下：

1. athena% git merge lab1
2. Merge made by recursive.
3. kern/kdebug.c  |   11 +++++++++--
4. kern/monitor.c |   19 +++++++++++++++++++
5. lib/printfmt.c |    7 +++----
6. 3 files changed, 31 insertions(+), 6 deletions(-)
7. athena%

在一些案例中，Git 或許並不知道如何將你的更改與新的實驗任務合併（例如，你在第二個實驗任務中變更了一些程式碼的修改）。在那種情況下，你使用 git 命令去合併，它會告訴你哪個檔案發生了衝突，你必須首先去解決衝突（透過編輯衝突的檔案），然後使用 git commit -a 去重新提交檔案。

實驗 2 包含如下的新原始碼，後面你將逐個瞭解它們：

memlayout.h 描述虛擬地址空間的佈局，這個虛擬地址空間是透過修改 pmap.c、memlayout.h 和 pmap.h 所定義的 PageInfo 資料結構來實現的，這個資料結構用於跟蹤物理記憶體頁面是否被釋放。kclock.c 和 kclock.h 維護 PC 上基於電池的時鐘和 CMOS RAM 硬體，在此，BIOS 中記錄了 PC 上安裝的物理記憶體數量，以及其它的一些資訊。在 pmap.c 中的程式碼需要去讀取這個裝置硬體，以算出在這個裝置上安裝了多少物理記憶體，但這部分程式碼已經為你完成了：你不需要知道 CMOS 硬體工作原理的細節。

特別需要註意的是 memlayout.h 和 pmap.h，因為本實驗需要你去使用和理解的大部分內容都包含在這兩個檔案中。你或許還需要去看看 inc/mmu.h 這個檔案，因為它也包含了本實驗中用到的許多定義。

開始本實驗之前，記得去新增 exokernel 以獲取 QEMU 的 6.828 版本。

實驗過程

在你準備進行實驗和寫程式碼之前，先新增你的 answers-lab2.txt 檔案到 Git 倉庫，提交你的改變然後去執行 make handin。

1. athena% git add answers-lab2.txt
2. athena% git commit -am "my answer to lab2"
3. [lab2 a823de9] my answer to lab2 4 files changed, 87 insertions(+), 10 deletions(-)
4. athena% make handin

正如前面所說的，我們將使用一個評級程式來分級你的解決方案，你可以在 lab 目錄下執行 make grade，使用評級程式來測試你的核心。為了完成你的實驗，你可以改變任何你需要的核心原始碼和頭檔案。但毫無疑問的是，你不能以任何形式去改變或破壞評級程式碼。

第 1 部分：物理頁面管理

作業系統必須跟蹤物理記憶體頁是否使用的狀態。JOS 以“頁”為最小粒度來管理 PC 的物理記憶體，以便於它使用 MMU 去對映和保護每個已分配的記憶體片段。

現在，你將要寫記憶體的物理頁分配器的程式碼。它將使用 struct PageInfo 物件的連結串列來保持對物理頁的狀態跟蹤，每個物件都對應到一個物理記憶體頁。在你能夠編寫剩下的虛擬記憶體實現程式碼之前，你需要先編寫物理記憶體頁面分配器，因為你的頁表管理程式碼將需要去分配物理記憶體來儲存頁表。

練習 1

在檔案 kern/pmap.c 中，你需要去實現以下函式的程式碼（或許要按給定的順序來實現）。

◈ boot_alloc()

◈ mem_init()（只要能夠呼叫 check_page_free_list() 即可）

◈ page_init()

◈ page_alloc()

◈ page_free()

check_page_free_list() 和 check_page_alloc() 可以測試你的物理記憶體頁分配器。你將需要引導 JOS 然後去看一下 check_page_alloc() 是否報告成功即可。如果沒有報告成功，修複你的程式碼直到成功為止。你可以新增你自己的 assert() 以幫助你去驗證是否符合你的預期。

本實驗以及所有的 6.828 實驗中，將要求你做一些檢測工作，以便於你搞清楚它們是否按你的預期來工作。這個任務不需要詳細描述你新增到 JOS 中的程式碼的細節。查詢 JOS 原始碼中你需要去修改的那部分的註釋；這些註釋中經常包含有技術規範和提示資訊。你也可能需要去查閱 JOS 和 Intel 的技術手冊、以及你的 6.004 或 6.033 課程筆記的相關部分。

第 2 部分：虛擬記憶體

在你開始動手之前，需要先熟悉 x86 記憶體管理架構的保護樣式：即分段和頁面轉換。

練習 2

如果你對 x86 的保護樣式還不熟悉，可以檢視 Intel 80386 參考手冊[2]的第 5 章和第 6 章。閱讀這些章節（5.2 和 6.4）中關於頁面轉換和基於頁面的保護。我們建議你也去瞭解關於段的章節；在虛擬記憶體和保護樣式中，JOS 使用了分頁、段轉換、以及在 x86 上不能禁用的基於段的保護，因此你需要去理解這些基礎知識。

虛擬地址、線性地址和物理地址

在 x86 的專用術語中，一個虛擬地址virtual address是由一個段選擇器和在段中的偏移量組成。一個線性地址linear address是在頁面轉換之前、段轉換之後得到的一個地址。一個物理地址physical address是段和頁面轉換之後得到的最終地址，它最終將進入你的物理記憶體中的硬體匯流排。

一個 C 指標是虛擬地址的“偏移量”部分。在 boot/boot.S 中我們安裝了一個全域性描述符表Global Descriptor Table（GDT），它透過設定所有的段基址為 0，並且限製為 0xffffffff來有效地禁用段轉換。因此“段選擇器”並不會生效，而線性地址總是等於虛擬地址的偏移量。在實驗 3 中，為了設定許可權級別，我們將與段有更多的互動。但是對於記憶體轉換，我們將在整個 JOS 實驗中忽略段，只專註於頁轉換。

回顧實驗 1[1] 中的第 3 部分，我們安裝了一個簡單的頁表，這樣核心就可以在 0xf0100000連結的地址上執行，儘管它實際上是載入在 0x00100000 處的 ROM BIOS 的物理記憶體上。這個頁表僅映射了 4MB 的記憶體。在實驗中，你將要為 JOS 去設定虛擬記憶體佈局，我們將從虛擬地址 0xf0000000 處開始擴充套件它，以對映物理記憶體的前 256MB，並對映許多其它區域的虛擬記憶體。

練習 3

雖然 GDB 能夠透過虛擬地址訪問 QEMU 的記憶體，它經常用於在配置虛擬記憶體期間檢查物理記憶體。在實驗工具指南中複習 QEMU 的監視器命令[3]，尤其是 xp 命令，它可以讓你去檢查物理記憶體。要訪問 QEMU 監視器，可以在終端中按 Ctrl-a c（相同的系結傳回到序列控制檯）。

使用 QEMU 監視器的 xp 命令和 GDB 的 x 命令去檢查相應的物理記憶體和虛擬記憶體，以確保你看到的是相同的資料。

我們的打過補丁的 QEMU 版本提供一個非常有用的 info pg 命令：它可以展示當前頁表的一個具體描述，包括所有已對映的記憶體範圍、許可權、以及標誌。原本的 QEMU 也提供一個 info mem 命令用於去展示一個概要資訊，這個資訊包含了已對映的虛擬記憶體範圍和使用了什麼許可權。

在 CPU 上執行的程式碼，一旦處於保護樣式（這是在 boot/boot.S 中所做的第一件事情）中，是沒有辦法去直接使用一個線性地址或物理地址的。所有的記憶體取用都被解釋為虛擬地址，然後由 MMU 來轉換，這意味著在 C 語言中的指標都是虛擬地址。

例如在物理記憶體分配器中，JOS 記憶體經常需要在不反向取用的情況下，去維護作為地址的一個很難懂的值或一個整數。有時它們是虛擬地址，而有時是物理地址。為便於在程式碼中證明，JOS 源檔案中將它們區分為兩種：型別 uintptr_t 表示一個難懂的虛擬地址，而型別 physaddr_trepresents 表示物理地址。這些型別其實不過是 32 位整數（uint32_t）的同義詞，因此編譯器不會阻止你將一個型別的資料指派為另一個型別！因為它們都是整數（而不是指標）型別，如果你想去反向取用它們，編譯器將報錯。

JOS 內核能夠透過將它轉換為指標型別的方式來反向取用一個 uintptr_t 型別。相反，核心不能反向取用一個物理地址，因為這是由 MMU 來轉換所有的記憶體取用。如果你轉換一個 physaddr_t 為一個指標型別，並反向取用它，你或許能夠載入和儲存最終結果地址（硬體將它解釋為一個虛擬地址），但你並不會取得你想要的記憶體位置。

總結如下：

問題：

1. 假設下麵的 JOS 核心程式碼是正確的，那麼變數 x 應該是什麼型別？uintptr_t 還是 physaddr_t ？

JOS 內核有時需要去讀取或修改它只知道其物理地址的記憶體。例如，新增一個對映到頁表，可以要求分配物理記憶體去儲存一個頁目錄，然後去初始化它們。然而，核心也和其它的軟體一樣，並不能跳過虛擬地址轉換，核心並不能直接載入和儲存物理地址。一個原因是 JOS 將重對映從虛擬地址 0xf0000000 處的物理地址 0 開始的所有的物理地址，以幫助核心去讀取和寫入它知道物理地址的記憶體。為轉換一個物理地址為一個內核能夠真正進行讀寫操作的虛擬地址，核心必須新增 0xf0000000 到物理地址以找到在重對映區域中相應的虛擬地址。你應該使用 KADDR(pa)去做那個新增操作。

JOS 內核有時也需要能夠透過給定的核心資料結構中儲存的虛擬地址找到記憶體中的物理地址。核心全域性變數和透過 boot_alloc() 分配的記憶體是在核心所載入的區域中，從 0xf0000000處開始的這個所有物理記憶體對映的區域。因此，要轉換這些區域中一個虛擬地址為物理地址時，內核能夠只是簡單地減去 0xf0000000 即可得到物理地址。你應該使用 PADDR(va) 去做那個減法操作。

取用計數

在以後的實驗中，你將會經常遇到多個虛擬地址（或多個環境下的地址空間中）同時對映到相同的物理頁面上。你將在 struct PageInfo 資料結構中的 pp_ref 欄位來記錄一個每個物理頁面的取用計數器。如果一個物理頁面的這個計數器為 0，表示這個頁面已經被釋放，因為它不再被使用了。一般情況下，這個計數器應該等於所有頁表中物理頁面出現在 UTOP 之下的次數（UTOP 之上的對映大都是在引導時由核心設定的，並且它從不會被釋放，因此不需要取用計數器）。我們也使用它去跟蹤放到頁目錄頁的指標數量，反過來就是，頁目錄到頁表頁的取用數量。

使用 page_alloc 時要註意。它傳回的頁面取用計數總是為 0，因此，一旦對傳回頁做了一些操作（比如將它插入到頁表），pp_ref 就應該增加。有時這需要透過其它函式（比如，page_instert）來處理，而有時這個函式是直接呼叫 page_alloc 來做的。

頁表管理

現在，你將寫一套管理頁表的程式碼：去插入和刪除線性地址到物理地址的對映表，並且在需要的時候去建立頁表。

練習 4

在檔案 kern/pmap.c 中，你必須去實現下列函式的程式碼。

◈ pgdir_walk()

◈ bootmapregion()

◈ page_lookup()

◈ page_remove()

◈ page_insert()

check_page()，呼叫自 mem_init()，測試你的頁表管理函式。在進行下一步流程之前你應該確保它成功執行。

第 3 部分：核心地址空間

JOS 分割處理器的 32 位線性地址空間為兩部分：使用者環境（行程），（我們將在實驗 3 中開始載入和執行），它將控制其上的佈局和低位部分的內容；而核心總是維護對高位部分的完全控制。分割線的定義是在 inc/memlayout.h 中透過符號 ULIM 來劃分的，它為內核保留了大約 256MB 的虛擬地址空間。這就解釋了為什麼我們要在實驗 1 中給核心這樣的一個高位連結地址的原因：如是不這樣做的話，內核的虛擬地址空間將沒有足夠的空間去同時對映到下麵的使用者空間中。

你可以在 inc/memlayout.h 中找到一個圖表，它有助於你去理解 JOS 記憶體佈局，這在本實驗和後面的實驗中都會用到。

許可權和故障隔離

由於內核和使用者的記憶體都存在於它們各自環境的地址空間中，因此我們需要在 x86 的頁表中使用許可權位去允許使用者程式碼只能訪問使用者所屬地址空間的部分。否則，使用者程式碼中的 bug 可能會覆寫核心資料，導致系統崩潰或者發生各種莫名其妙的的故障；使用者程式碼也可能會偷窺其它環境的私有資料。

對於 ULIM 以上部分的記憶體，使用者環境沒有任何許可權，只有核心才可以讀取和寫入這部分記憶體。對於 [UTOP,ULIM] 地址範圍，內核和使用者都有相同的許可權：它們可以讀取但不能寫入這個地址範圍。這個地址範圍是用於向用戶環境暴露某些只讀的核心資料結構。最後，低於 UTOP 的地址空間是為使用者環境所使用的；使用者環境將為訪問這些核心設定許可權。

初始化核心地址空間

現在，你將去配置 UTOP 以上的地址空間：核心部分的地址空間。inc/memlayout.h 中展示了你將要使用的佈局。我將使用函式去寫相關的線性地址到物理地址的對映配置。

練習 5

完成呼叫 check_page() 之後在 mem_init() 中缺失的程式碼。

現在，你的程式碼應該透過了 check_kern_pgdir() 和 check_page_installed_pgdir() 的檢查。

問題：

1、在這個時刻，頁目錄中的條目（行）是什麼？它們對映的址址是什麼？以及它們對映到哪裡了？換句話說就是，盡可能多地填寫這個表：

< 如顯示不全，請左右滑動 >

條目	虛擬地址基址	指向（邏輯上）：
1023	?	物理記憶體頂部 4MB 的頁表
1022	?	?
.	?	?
.	?	?
.	?	?
2	0x00800000	?
1	0x00400000	?
0	0x00000000	[參見下一問題]

2、(來自課程 3) 我們將內核和使用者環境放在相同的地址空間中。為什麼使用者程式不能去讀取和寫入內核的記憶體？有什麼特殊機制保護核心記憶體？

3、這個作業系統能夠支援的最大的物理記憶體數量是多少？為什麼？

4、如果我們真的擁有最大數量的物理記憶體，有多少空間的開銷用於管理記憶體？這個開銷可以減少嗎？

5、複習在 kern/entry.S 和 kern/entrypgdir.c 中的頁表設定。一旦我們開啟分頁，EIP 仍是一個很小的數字（稍大於 1MB）。在什麼情況下，我們轉而去執行在 KERNBASE 之上的一個 EIP？當我們啟用分頁並開始在 KERNBASE 之上執行一個 EIP 時，是什麼讓我們能夠一個很低的 EIP 上持續執行？為什麼這種轉變是必需的？

地址空間佈局的其它選擇

在 JOS 中我們使用的地址空間佈局並不是我們唯一的選擇。一個作業系統可以在低位的線性地址上對映核心，而為使用者行程保留線性地址的高位部分。然而，x86 核心一般並不採用這種方法，因為 x86 向後相容樣式之一（被稱為“虛擬 8086 樣式”）“不可改變地”在處理器使用線性地址空間的最下麵部分，所以，如果核心被對映到這裡是根本無法使用的。

雖然很困難，但是設計這樣的內核是有這種可能的，即：不為處理器自身保留任何固定的線性地址或虛擬地址空間，而有效地允許使用者級行程不受限制地使用整個 4GB 的虛擬地址空間 —— 同時還要在這些行程之間充分保護內核以及不同的行程之間相互受保護！

將內核的記憶體分配系統進行概括類推，以支援二次冪為單位的各種頁大小，從 4KB 到一些你選擇的合理的最大值。你務必要有一些方法，將較大的分配單位按需分割為一些較小的單位，以及在需要時，將多個較小的分配單位合併為一個較大的分配單位。想一想在這樣的一個系統中可能會出現些什麼樣的問題。

這個實驗做完了。確保你透過了所有的等級測試，並記得在 answers-lab2.txt 中寫下你對上述問題的答案。提交你的改變（包括新增 answers-lab2.txt 檔案），併在 lab 目錄下輸入 make handin 去提交你的實驗。

via: https://sipb.mit.edu/iap/6.828/lab/lab2/

作者：Mit[4] 譯者：qhwdw 校對：wxy

本文由 LCTT 原創編譯，Linux中國 榮譽推出