ucore Lab2 實驗筆記

ucore Lab2

lab 2 直接執行make qemu-nox會顯示 assert 失敗:

kernel panic at kern/mm/default_pmm.c:277:
    assertion failed: (p0 = alloc_page()) == p2 - 1

1 連續物理記憶體管理

1.1 page 概覽

對物理記憶體的管理,為了節省空間,也是為了配合接下來的虛擬記憶體管理,通常以某個比 byte 大一些的單位進行管理,我們稱這一單位記憶體為一"頁(page)",通常是 4KB.待 pages 初始化完畢後,物理記憶體示意圖如下:

其中綠色代表可以分配的記憶體,紅色代表不可被分配的記憶體.註意,ucore規定物理記憶體可用範圍最大不超過KERNSIZE.函數page_init的主要作用就是初始化pages也就是所有page的所有信息.

註意,pages以全局指針的形式存在,因為最開始無法知道 page 的數量,所以無法寫成數量確定的數組.此數量必須儘快確認,否則後期無法管理.

如何確定 page 的數量npage呢?

1.1 探測物理記憶體佈局,獲取 pages 大小

npages可由最大物理記憶體邊界/PGSIZE 得出.

而最大物理記憶體邊界可以藉助 BIOS 可以探測並計算出來,參考探測系統物理記憶體佈局和實現物理記憶體探測.可以獲取到最大可用物理記憶體邊界maxpa, 但maxpa 最終必須<=KMEMSIZE.

於是確認了npage和pages:

npage = maxpa / PGSIZE;
pages = (struct Page *)ROUNDUP((void *)end, PGSIZE);// 從end向上取整頁

1.2 確定每個 page 的狀態

每個page 的狀態即其四個欄位:

struct Page {
    int ref;                // 虛存引用計數, 實際上是被頁表項引用的數量.每有一個頁表項指向此 page,ref 就+1
    uint32_t flags;         // 當前頁狀態位.解釋見下
    unsigned int property;  // (對於 first fit)用於可用區域記憶體的第一個 page,記錄其之後有多少個 page 是 free 的
    list_entry_t page_link; // 上/下一個空閑 page
};

對於狀態的解釋 : 在當前階段,此欄位理解為是否可用.通過SetPageReserved來標記其為保留(即不可用)的.

註意使用free_list作為雙良鏈表的表頭,應使用相關函數維護好關係.

參考以頁為單位管理物理記憶體

練習 1 重寫記憶體管理函數

參考 嚴蔚敏老師的 數據結構(C 語言版) 8.2 節 "首次擬合法".

first fit 演算法要求空閑 block 按起始地址有序排列.

default 系列的記憶體管理函數,註釋已經描述的非常清楚了,這裡再描述下演算法原理.

first-fit 的分配演算法, 核心步驟如下:

1. 找到 property > n 的節點 base_page
2. 從 base_page 步進 n 個 page 找到 p
3. 設置 p 的 property,值為 property - n
4. 把 p 作為新節點直接加入鏈表
5. 刪除 base_page

釋放的情況比較多,釋放page後有四種情況:

1. 空閑塊與其之前的空閑塊相鄰,與之後的空閑塊不相鄰
2. 空閑塊與其之前的空閑塊相鄰,與之後的空閑塊相鄰
3. 空閑塊與其之前的空閑塊不相鄰,與之後的空閑塊不相鄰
4. 空閑塊與其之前的空閑塊相鄰,與之後的空閑塊也相鄰

練習 2 實現尋找虛擬地址對應的頁表項

完成函數:

pte_t *
get_pte(pde_t *pgdir, uintptr_t la, bool create) {

此函數的作用是向上提供一個幾乎透明的操作,返回指定 linear address 對應的 page table entry.註意寫這個函數時有坑,此函數並非要初始化對應的頁表項,而是單純的獲取其地址! 初始化頁表項的在boot_map_segment中進行.

1. 得到 page dir 的 index: PDX(la),於是對應的 pde 是 pgdir[PDX(la)].

2. 考察 pde 具體的結構:

高 20 位是 page table 地址.

pgdir[PSX(la)]& ~0xFFF即可得到 page table 的物理地址.

在取值之前,首先要判斷存在位PTE_P.

1. 如果存在,說明之前已經初始化過了 pd,只需計算la對應的頁表項即可.
2. 如果不存在,說明當前 page directory entry 除了 PTE_P 外都是空的!更別說頁表了,肯定也是不存在.此時需要新申請一塊物理記憶體,作為新的頁表.但如果 create=0 的話就直接返回 NULL 就行了.

當前的頁目錄是__boot_pgdir,而我們之前只初始化了虛擬地址的[0,4M)和KERNBASE + [0 ~ 4M)的頁表,而未初始化其他部分.其他部分是 0.新申請page作為頁表之後,只是把頁表的(物理)基址寫到 pd 項中而已.此函數可能更新pd,但不會更新pt.

pte_t *
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
    // 1. 由線性地址取page directory 中對應的條目
    pde_t *pdep = &pgdir[PDX(la)];
    // 2.1 若存在位為 0,則需要判斷 create 選項.
    if (!(*pdep & PTE_P)) {
        struct Page *page;
        // 2.1.1 若 create=0 則返回 NULL
        if (!create)
            return NULL;
        // 2.1.2 若 create=1 則分配一塊物理記憶體,作為新的頁表
        if (page = alloc_page() == NULL) {
            return NULL;
        }
        // 2.1.3 設置此 page 的引用計數
        set_page_ref(page, 1);
        // 2.1.4 修改 page directory 項的標誌位,把新頁表地址寫入此項.
        uintptr_t pa = page2pa(page);
        memset(KADDR(pa), 0, PGSIZE);
        *pdep = pa | PTE_U | PTE_W | PTE_P;
    }
    // 2.2 若存在位不為 0,則返回頁表項地址.
    //      1. 對 *pdep 取高 20 位得到頁表(物理)基址
    //      2. 用KADDR將頁表物理基址換算為內核虛擬地址
    //      2. 從頁表虛擬基址取 PTX(la) 個偏移量得到頁表項,返回它的地址.
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];
}

練習3 釋放某虛地址所在的頁並取消對應二級頁表項的映射

編寫函數:

// 釋放給定頁表ptep關聯的page
// 去使能地址 la 對應的 tlb.
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep)

用到函數:page_ref_dec, 即減少引用.

    // 排除頁表不存在的情況
    if (*ptep & PTE_P) {
        struct Page *page = pte2page(*ptep);
        if (page_ref_dec(page) == 0) {
            free_page(page);
        }
        *ptep = 0;
        tlb_invalidate(pgdir, la);
    }