隨筆檔案

上一篇從 Bootloader 開始到內核載入使用的都是平坦內存，即所有地址對應實際的物理地址。現代操作系統都使用分頁來管理內存，分頁可以讓每個進程都有完整的虛擬地址空間，進程間的虛擬地址空間相互隔離以提供頁層級的保護。另外分頁可以讓物理內存少于虛擬地址空間，同時可以使用磁盤存儲暫時未使用的內存頁，提供更多的「內存」。

分頁通過 CPU 的 MMU(Memory Management Unit) 完成，MMU 通過當前的分頁表完成虛擬地址到物理地址的轉換。在 x86 下 MMU 通過兩級分頁表（也可以開啟三級）完成地址轉換，這兩級分別是頁目錄(Page Directory)和頁表(Page Table)。在 x86 下，由 cr3 寄存器存儲頁目錄的地址（物理地址），頁目錄和頁表都包含 1024 項，每項 4 字節，因此頁目錄和頁表大小為 4KB ，按照 4KB 一頁的話，剛好占用一頁。

MMU 將虛擬地址轉換成物理地址的方式是，取虛擬地址的 22~31bits 表示頁目錄的下標，獲得頁目錄項定位到頁表，再取 12~21bits 表示頁表的下標，獲得頁表項定位到頁，最后取 0~11bits 表示頁偏移。頁目錄項和頁表項的下標分別用 10bits 表示，剛好最大 1024 項，頁內偏移用 12bits 表示，剛好 4KB。

頁目錄項結構如下：

其中 S 表示頁大小是 4KB 還是 4MB，P 表示頁表是否在內存中，如果在內存中，那么 12～31 bits 存儲了 4KB 對齊的頁表地址（同樣是物理地址），其它 bit 的含義請參考這里。

頁表項結構如下：

同樣的，P 表示此頁是否在內存中，如果在內存中，12~31 bits 存儲了頁的地址。

我們知道了頁目錄和頁表的結構，準備好頁目錄和頁表，就可以開啟分頁了，開啟分頁只需把頁目錄地址放到 cr3 寄存器中，并把 cr0 的最高 bit 置 1。通過頁目錄項，我們可以發現頁表不需要都存在內存當中，當訪問一個虛擬地址，它對應的頁表或者頁不存在內存中時會觸發 Page Fault 異常，我們可以在異常處理函數中完成頁表或者頁的分配，理論上開啟分頁只需要準備好頁目錄。

準備好頁目錄頁表，設置 cr3 和 cr0，開啟了分頁之后，內核的所有地址都變成了虛擬地址，所有的地址都要通過 MMU 映射到物理地址再訪問內存。這一變化是需要小心注意的，開啟分頁前，訪問的所有地址是物理地址，開啟分頁之后，所有的地址都變成了虛擬地址，因此，如果分頁由內核來完成，那么內核就需要考慮到前后的變化，即有一部分代碼運行在物理地址下，其它代碼都運行在虛擬地址下；如果分頁由 Bootloader 完成，那么 Bootloader 需要注意這個變化，并正確跳轉到內核，讓內核完整運行在虛擬地址下。

上一篇我把內核展開到從 0x100000 開始的物理內存中，編譯鏈接內核的時候也把代碼段的地址指定到 0x100000 的地址。開啟分頁之后，內核一般運行在高地址（比如 Linux 內核地址從 0x80000000 開始，Windows 從 0xC0000000 開始），而內核同樣是展開到從 0x100000 開始的物理內存中。我選擇把內核的虛擬地址鏈接到從 0xC0100000 開始，并把這個虛擬地址映射到 0x100000 的物理地址，開啟分頁之前運行的代碼，凡是涉及到地址的操作，我都會把虛擬地址調整為物理地址再操作，開啟分頁之后，所有虛擬地址就可以正常運行了。

操作系統采用分頁方式管理內存，因此物理內存的管理也需按照頁的方式管理，在 Page Fault 異常觸發時，在異常處理函數中分配新的物理頁并把它映射到分頁表中。這里牽涉到空閑物理內存頁的分配和釋放，我們很容易想到一種直觀的方法，把所有空閑內存頁用鏈表串聯起來，分配釋放一頁只需對鏈表進行操作。這種方式管理對進程的物理頁分配簡單有效，但是對內核本身使用的內存分配釋放會導致內存利用率不高，因為這種方式管理的最大連續內存是一頁，而內核中經常會分配大對象，連續多頁的物理內存有更好的利用率。Linux 采用 Buddy memory allocation 方式管理物理內存，使用 Slab/Slub 管理內核對象的分配釋放。

我的實現也采用 Buddy 方式管理物理內存，把空閑內存頁用多層級的 Buddy 方式管理，分別是 order 0 ~ order 10，表示 2^order 頁連續內存頁塊，即 order 0 管理單頁的空閑內存塊，order 10 管理連續 1024 頁的空閑內存塊。分配內存時，算出最佳的 order，在相應的 order 層級里分配一塊內存塊，如果當前 order 中沒有可用的空閑內存塊，就向 order + 1 層級中借一塊，并把借來的空閑內存塊平分成 2 塊 order 層級的空閑內存塊，其中一塊當作分配結果返回，另一塊放入到 order 層級中待以后分配使用。當第 order 塊的內存使用完釋放時，把這塊釋放的內存塊放入 order 層級時，判斷與它相連的同樣大小的內存塊是否在 order 層級中，如果存在，把它和它的 Buddy 合并成一個 order + 1 的內存塊放入到 order + 1的層級中。

在內存管理初始化之前，內核沒有動態內存分配能力，因此很多時候我們需要使用靜態全局變量。內存管理器初始化時，可能會使用到動態內存分配，這就出現雞與蛋的問題，為了解決這個問題，通常會實現一個簡單的 Boot Allocator 用在內存管理器初始化之前分配動態內存。我的實現是從內核展開的末尾位置開始建立一個只分配不釋放的 Boot Allocator，等到內存管理器初始化完成之后，Boot Allocator 的使命便完成了。

另外還有一個問題，我們管理物理內存，需要知道安裝了多少物理內存，因此我們要探測安裝了多少物理內存，這里介紹了幾種探測方法，我使用的是 BIOS 的 INT 0x15, EAX = 0xE820 函數，它由 Bootloader 調用完成，最后通過參數把它傳遞給操作系統內核。