隨筆檔案

上一篇從 Bootloader 開始到內(nèi)核載入使用的都是平坦內(nèi)存，即所有地址對(duì)應(yīng)實(shí)際的物理地址。現(xiàn)代操作系統(tǒng)都使用分頁(yè)來(lái)管理內(nèi)存，分頁(yè)可以讓每個(gè)進(jìn)程都有完整的虛擬地址空間，進(jìn)程間的虛擬地址空間相互隔離以提供頁(yè)層級(jí)的保護(hù)。另外分頁(yè)可以讓物理內(nèi)存少于虛擬地址空間，同時(shí)可以使用磁盤存儲(chǔ)暫時(shí)未使用的內(nèi)存頁(yè)，提供更多的「內(nèi)存」。

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

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

頁(yè)目錄項(xiàng)結(jié)構(gòu)如下：

其中 S 表示頁(yè)大小是 4KB 還是 4MB，P 表示頁(yè)表是否在內(nèi)存中，如果在內(nèi)存中，那么 12～31 bits 存儲(chǔ)了 4KB 對(duì)齊的頁(yè)表地址（同樣是物理地址），其它 bit 的含義請(qǐng)參考這里。

頁(yè)表項(xiàng)結(jié)構(gòu)如下：

同樣的，P 表示此頁(yè)是否在內(nèi)存中，如果在內(nèi)存中，12~31 bits 存儲(chǔ)了頁(yè)的地址。

我們知道了頁(yè)目錄和頁(yè)表的結(jié)構(gòu)，準(zhǔn)備好頁(yè)目錄和頁(yè)表，就可以開啟分頁(yè)了，開啟分頁(yè)只需把頁(yè)目錄地址放到 cr3 寄存器中，并把 cr0 的最高 bit 置 1。通過頁(yè)目錄項(xiàng)，我們可以發(fā)現(xiàn)頁(yè)表不需要都存在內(nèi)存當(dāng)中，當(dāng)訪問一個(gè)虛擬地址，它對(duì)應(yīng)的頁(yè)表或者頁(yè)不存在內(nèi)存中時(shí)會(huì)觸發(fā) Page Fault 異常，我們可以在異常處理函數(shù)中完成頁(yè)表或者頁(yè)的分配，理論上開啟分頁(yè)只需要準(zhǔn)備好頁(yè)目錄。

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

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

操作系統(tǒng)采用分頁(yè)方式管理內(nèi)存，因此物理內(nèi)存的管理也需按照頁(yè)的方式管理，在 Page Fault 異常觸發(fā)時(shí)，在異常處理函數(shù)中分配新的物理頁(yè)并把它映射到分頁(yè)表中。這里牽涉到空閑物理內(nèi)存頁(yè)的分配和釋放，我們很容易想到一種直觀的方法，把所有空閑內(nèi)存頁(yè)用鏈表串聯(lián)起來(lái)，分配釋放一頁(yè)只需對(duì)鏈表進(jìn)行操作。這種方式管理對(duì)進(jìn)程的物理頁(yè)分配簡(jiǎn)單有效，但是對(duì)內(nèi)核本身使用的內(nèi)存分配釋放會(huì)導(dǎo)致內(nèi)存利用率不高，因?yàn)檫@種方式管理的最大連續(xù)內(nèi)存是一頁(yè)，而內(nèi)核中經(jīng)常會(huì)分配大對(duì)象，連續(xù)多頁(yè)的物理內(nèi)存有更好的利用率。Linux 采用 Buddy memory allocation 方式管理物理內(nèi)存，使用 Slab/Slub 管理內(nèi)核對(duì)象的分配釋放。

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

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

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