Caffeinated 6.828：實驗 2：內存管理

簡介

在本實驗中，你將為你的操作系統寫內存管理方面的代碼。內存管理由兩部分組成。

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

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

預備知識

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

athena% cd ~/6.828/lab
athena% add git
athena% git pull
Already up-to-date.
athena% git checkout -b lab2 origin/lab2
Branch lab2 set up to track remote branch refs/remotes/origin/lab2.
Switched to a new branch "lab2"
athena%

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

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

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

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

實驗 2 包含如下的新源代碼，後面你將逐個了解它們：

inc/memlayout.h
kern/pmap.c
kern/pmap.h
kern/kclock.h
kern/kclock.c

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。

athena% git add answers-lab2.txt
athena% git commit -am "my answer to lab2"
[lab2 a823de9] my answer to lab2 4 files changed, 87 insertions(+), 10 deletions(-)
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 參考手冊的第 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 中的第 3 部分，我們安裝了一個簡單的頁表，這樣內核就可以在 0xf0100000 鏈接的地址上運行，儘管它實際上是載入在 0x00100000 處的 ROM BIOS 的物理內存上。這個頁表僅映射了 4MB 的內存。在實驗中，你將要為 JOS 去設置虛擬內存布局，我們將從虛擬地址 0xf0000000 處開始擴展它，以映射物理內存的前 256MB，並映射許多其它區域的虛擬內存。

練習 3

雖然 GDB 能夠通過虛擬地址訪問 QEMU 的內存，它經常用於在配置虛擬內存期間檢查物理內存。在實驗工具指南中複習 QEMU 的監視器命令，尤其是 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 為一個指針類型，並反向引用它，你或許能夠載入和存儲最終結果地址（硬體將它解釋為一個虛擬地址），但你並不會取得你想要的內存位置。

總結如下：

C 類型	地址類型
`T*`	虛擬
`uintptr_t`	虛擬
`physaddr_t`	物理

問題：

假設下面的 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 上持續運行？為什麼這種轉變是必需的？

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

地址空間布局的其它選擇

在 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 譯者：qhwdw 校對：wxy

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

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive