ucore作業系統學習筆記(二) ucore lab2物理記憶體管理分析
一、lab2物理記憶體管理介紹
作業系統的一個主要職責是管理硬體資源，並嚮應用程式提供具有良好抽象的介面來使用這些資源。
而記憶體作為重要的電腦硬體資源，也必然需要被作業系統統一的管理。最初沒有作業系統的情況下，不同的程式通常直接編寫物理地址相關的指令。在多道並發程式的運行環境下，這會造成不同程式間由於物理地址的訪問衝突，造成數據的相互覆蓋，進而出錯、崩潰。
現代的作業系統在管理記憶體時，希望達到兩個基本目標：地址保護和地址獨立。
地址保護指的是一個程式不能隨意的訪問另一個程式的空間，而地址獨立指的是程式指令給出的記憶體定址命令是與最終的物理地址無關的。在實現這兩個目標後，便能夠為多道並發程式運行時的物理記憶體訪問的隔離提供支援。每個程式在編譯、鏈接後產生的最終機器程式碼都可以使用完整的地址空間(虛擬地址)，而不需要考慮其它的程式的存在。ucore通過兩個連續的實驗迭代，lab2和lab3分別實現了物理記憶體管理和虛擬記憶體管理(利用磁碟快取非工作集記憶體，擴展邏輯上的記憶體空間)。
ucore的每個實驗都是建立在前一個實驗迭代的基礎上的，要想更好的理解lab2，最好先理解之前lab1中的內容（lab1學習筆記）。
lab2在lab1平坦模型段機制的基礎上，開啟了80386的分頁機制，並建立了內核頁表；同時通過硬體中斷探測出了當前記憶體硬體的布局，並以此為依據根據可用的記憶體建立了一個物理記憶體管理框架，通過指定某種分配演算法，負責處理所有的物理記憶體頁分配與釋放的請求。
lab2的程式碼結構和執行流程與lab1差別不大，其主要新增了以下功能：
1. bootmain.S中的物理記憶體探測
2. 在新增的entry.S內核入口程式中開啟了80386頁機制
3. kern_init內核總控函數中通過pmm_init函數進行整個物理記憶體管理器的構建初始化
二、lab2實驗細節分析
2.1 物理記憶體布局探測
為了進行物理記憶體的管理，作業系統必須先探測出當前硬體環境下記憶體的布局，了解具體哪些物理記憶體空間是可用的。
ucore在實驗中是通過e820這一BIOS中斷來探測記憶體布局的，由於BIOS中斷必須在80386的實模式下才能正常工作，因此是在bootloader引導進入保護模式前進行的，程式碼位於/boot/bootasm,S中。在引導的彙編程式碼中收集到的數據，通過C中定義的e820map結構體進行映射。
e820map結構：
struct e820map { int nr_map; struct { uint64_t addr; uint64_t size; uint32_t type; } __attribute__((packed)) map[E820MAX]; };
bootasm.S記憶體布局探測：
# 在實模式下，通過BIOS的e820中斷探測當前記憶體的硬體資訊 probe_memory: # 0x8000處開始存放探測出的記憶體布局結構(e820map) movl $0, 0x8000 xorl %ebx, %ebx # 0x8004處開始存放e820map中的map欄位，存放每一個entry movw $0x8004, %di start_probe: # 在eax、ecx、edx中設置int 15h中斷參數 movl $0xE820, %eax movl $20, %ecx movl $SMAP, %edx int $0x15 # 如果eflags的CF位為0，說明探測成功，跳轉至cont段執行 jnc cont # e820h中斷失敗，直接結束探測 movw $12345, 0x8000 jmp finish_probe cont: # 設置存放下一個探測出的記憶體布局entry的地址(因為e820map中的entry數組每一項是8+8+4=20位元組的) addw $20, %di # e820map中的nr_map自增1 incl 0x8000 # 0與中斷響應後的ebx比較(如果是第一次調用或記憶體區域掃描完畢，則ebx為0。 如果不是，則ebx存放上次調用之後的計數值) cmpl $0, %ebx # 是否還存在新的記憶體段需要探測 jnz start_probe finish_probe: # 結束探測
2.2 啟用分頁機制
ucore在lab2中開啟了80386的分頁機制，實現了基於平坦段模型的段頁式記憶體管理，為後續虛擬記憶體的實現做好了準備。
如果對80386分頁機制原理不太熟悉的話，可以參考一下我之前的部落格：80386分頁機制與虛擬記憶體。
虛擬地址的概念
需要注意的是，在80386分頁機制工作原理的許多資料中，開啟了頁機制後由指令(段選擇子+段內偏移)所構成的地址被稱為邏輯地址；而邏輯地址通過GDT或LDT等段錶轉換之後得到的地址被稱為線性地址；如果開啟了頁機制，得到線性地址後還需要查找頁表來得到最終的物理地址。
整個的轉換過程大致為：邏輯地址->線性地址->物理地址。但虛擬地址這一概念並沒有得到統一，在實驗指導書中，虛擬地址指的是程式指令給出的邏輯地址，而在有的資料中，則將線性地址稱作虛擬地址。查閱有關資料時一定要注意虛擬地址這一概念在上下文中的確切含義，避免產生混淆。
ucore開啟分頁機制的細節
lab2以及往後的實驗中，在ucore的虛擬空間設計中，開啟了頁機制後的內核是位於高位地址空間的，而低位記憶體空間則讓出來交給用戶應用程式使用。
ucore內核被bootloader指定載入的物理地址基址相對lab1而言是不變的。但在開啟分頁機制的前後，CPU翻譯邏輯地址的方式也立即發生了變化。開啟分頁機制前，內核程式的指令指針是指向低位記憶體的，而開啟了頁機制後，我們希望能夠正確、無損的令內核的指令指針指向高位地址空間，但保證其最終訪問的物理地址不變，依然能夠正確的執行。在實驗指導書中有專門的一節提到：系統執行中地址映射的三個階段。
在這裡補充一下第二個階段開啟分頁模式時的細節：在開啟頁機制的瞬間是如何巧妙的保證後續指令正確訪問的。
根據git倉庫上的提交記錄，發現ucore開啟分頁機制的實現細節在2018年初進行了很大的改動。網上許多發表較早的ucore學習部落格其內容部分已經過時，在參考時需要注意。(實驗指導書的該節標題也有錯誤：應該是系統執行中地址映射的三個階段，而不是之前的四個階段了)。
entry.S
#include <mmu.h> #include <memlayout.h> #define REALLOC(x) (x - KERNBASE) .text .globl kern_entry kern_entry: # REALLOC是因為內核在構建時被設置在了高位(kernel.ld中設置了內核起始虛地址0xC0100000,使得虛地址整體增加了KERNBASE) # 因此需要REALLOC來對內核全局變數進行重定位，在開啟分頁模式前保證程式訪問的物理地址的正確性 # load pa of boot pgdir # 此時還沒有開啟頁機制，__boot_pgdir(entry.S中的符號)需要通過REALLOC轉換成正確的物理地址 movl $REALLOC(__boot_pgdir), %eax # 設置eax的值到頁表基址暫存器cr3中 movl %eax, %cr3 # enable paging 開啟頁模式 movl %cr0, %eax # 通過or運算，修改cr0中的值 orl $(CR0_PE | CR0_PG | CR0_AM | CR0_WP | CR0_NE | CR0_TS | CR0_EM | CR0_MP), %eax andl $~(CR0_TS | CR0_EM), %eax # 將cr0修改完成後的值，重新送至cr0中(此時第0位PE位已經為1，頁機制已經開啟，當前頁表地址為剛剛構造的__boot_pgdir) movl %eax, %cr0 # update eip # now, eip = 0x1..... next是處於高位地址空間的 leal next, %eax # set eip = KERNBASE + 0x1..... # 通過jmp至next處，使得內核的指令指針指向了高位。但由於巧妙的設計了高位映射的內核頁表，使得依然能準確訪問之前低位虛空間下的所有內容 jmp *%eax next: # unmap va 0 ~ 4M, it is temporary mapping xorl %eax, %eax # 將__boot_pgdir的第一個頁目錄項清零，取消0~4M虛地址的映射 movl %eax, __boot_pgdir # 設置C的內核棧 # set ebp, esp movl $0x0, %ebp # the kernel stack region is from bootstack -- bootstacktop, # the kernel stack size is KSTACKSIZE (8KB)defined in memlayout.h movl $bootstacktop, %esp # now kernel stack is ready , call the first C function # 調用init.c中的kern_init總控函數 call kern_init # should never get here # 自旋死循環(如果內核實現正確，kern_init函數將永遠不會返回並執行至此。因為作業系統內核本身就是通過自旋循環常駐記憶體的) spin: jmp spin .data .align PGSIZE .globl bootstack bootstack: .space KSTACKSIZE .globl bootstacktop bootstacktop: # kernel builtin pgdir # an initial page directory (Page Directory Table, PDT) # These page directory table and page table can be reused! .section .data.pgdir .align PGSIZE __boot_pgdir: .globl __boot_pgdir # map va 0 ~ 4M to pa 0 ~ 4M (temporary) # 80386的每一個一級頁表項能夠映射4MB連續的虛擬記憶體至物理記憶體的關係 # 第一個有效頁表項，當訪問0~4M虛擬記憶體時，虛擬地址的高10位為0，即找到該一級頁表項(頁目錄項)，進而可以找到二級頁表__boot_pt1 # 進而可以進行虛擬地址的0~4M -> 物理地址 0~4M的等價映射 .long REALLOC(__boot_pt1) + (PTE_P | PTE_U | PTE_W) # space用於將指定範圍大小內的空間全部設置為0(等價於P位為0，即不存在的、無效的頁表項) # KERNBASE/一個物理頁的大小(PGSHIFT 4KB即偏移12位)/一個二級頁表內的頁表項(2^10個) * 4(一個頁表項32位，即4byte) # 偏移的距離 - (. - __boot_pgdir) 是為了對齊 .space (KERNBASE >> PGSHIFT >> 10 << 2) - (. - __boot_pgdir) # pad to PDE of KERNBASE # map va KERNBASE + (0 ~ 4M) to pa 0 ~ 4M # 第二個有效頁表項，前面通過.space偏移跳過特定的距離，當虛擬地址為KERNBASE~KERNBASE+4M時，能夠查找到該項 # 其對應的二級頁表同樣是__boot_pt1，而其中映射的物理地址為按照下標順序排列的0~4M， # 因此其最終的效果便能將KERNBASE~KERNBASE+4M的虛擬記憶體空間映射至物理記憶體空間的0~4M .long REALLOC(__boot_pt1) + (PTE_P | PTE_U | PTE_W) .space PGSIZE - (. - __boot_pgdir) # pad to PGSIZE .set i, 0 # __boot_pt1是一個存在1024個32位long數據的數組，當將其作為頁表時其中每一項都代表著一個物理地址映射項 # i為下標，每個頁表項的內容為i*1024作為映射的物理頁面基址並加上一些低位的屬性位(PTE_P代表存在，PTE_W代表可寫) __boot_pt1: .rept 1024 .long i * PGSIZE + (PTE_P | PTE_W) .set i, i + 1 .endr
頁表映射關係圖：
2.3 ucore是如何實現物理記憶體管理功能的
開啟了分頁機制後，下面介紹lab2中的重點：ucore是如何實現物理記憶體管理功能的。初始化物理記憶體管理器的入口位於總控函數的pmm_init函數。
pmm_init函數：
//pmm_init - setup a pmm to manage physical memory, build PDT&PT to setup paging mechanism // - check the correctness of pmm & paging mechanism, print PDT&PT void pmm_init(void) { // We've already enabled paging // 此時已經開啟了頁機制，由於boot_pgdir是內核頁表地址的虛擬地址。通過PADDR宏轉化為boot_cr3物理地址，供後續使用 boot_cr3 = PADDR(boot_pgdir); //We need to alloc/free the physical memory (granularity is 4KB or other size). //So a framework of physical memory manager (struct pmm_manager)is defined in pmm.h //First we should init a physical memory manager(pmm) based on the framework. //Then pmm can alloc/free the physical memory. //Now the first_fit/best_fit/worst_fit/buddy_system pmm are available. // 初始化物理記憶體管理器 init_pmm_manager(); // detect physical memory space, reserve already used memory, // then use pmm->init_memmap to create free page list // 探測物理記憶體空間，初始化可用的物理記憶體 page_init(); //use pmm->check to verify the correctness of the alloc/free function in a pmm check_alloc_page(); check_pgdir(); static_assert(KERNBASE % PTSIZE == 0 && KERNTOP % PTSIZE == 0); // recursively insert boot_pgdir in itself // to form a virtual page table at virtual address VPT // 將當前內核頁表的物理地址設置進對應的頁目錄項中(內核頁表的自映射) boot_pgdir[PDX(VPT)] = PADDR(boot_pgdir) | PTE_P | PTE_W; // map all physical memory to linear memory with base linear addr KERNBASE // linear_addr KERNBASE ~ KERNBASE + KMEMSIZE = phy_addr 0 ~ KMEMSIZE // 將內核所佔用的物理記憶體，進行頁表<->物理頁的映射 // 令處於高位虛擬記憶體空間的內核，正確的映射到低位的物理記憶體空間 // (映射關係(虛實映射): 內核起始虛擬地址(KERNBASE)~內核截止虛擬地址(KERNBASE+KMEMSIZE) = 內核起始物理地址(0)~內核截止物理地址(KMEMSIZE)) boot_map_segment(boot_pgdir, KERNBASE, KMEMSIZE, 0, PTE_W); // Since we are using bootloader's GDT, // we should reload gdt (second time, the last time) to get user segments and the TSS // map virtual_addr 0 ~ 4G = linear_addr 0 ~ 4G // then set kernel stack (ss:esp) in TSS, setup TSS in gdt, load TSS // 重新設置GDT gdt_init(); //now the basic virtual memory map(see memalyout.h) is established. //check the correctness of the basic virtual memory map. check_boot_pgdir(); print_pgdir(); }
物理記憶體管理器pmm_manager初始化
pmm_init在得到了內核頁目錄表的物理地址後(boot_cr3)，便通過init_pmm_manager函數初始化了物理記憶體管理器框架。該框架(全局變數pmm_manager)是一個被抽象出來的，用於表達物理記憶體管理行為的函數指針集合，內核啟動時會對這一函數指針集合進行賦值。
有了這一層函數指針集合的抽象層後，調用方就可以與提供服務的邏輯解耦了，在不修改任何調用方邏輯的情況下，簡單的修改函數指針集合的實現便能進行不同物理記憶體管理器的替換。如果熟悉面向對象概念的話，就會發現這和介面interface的概念類似，ucore物理記憶體管理器框架就是以面向對象的思維，面向介面開發的，通過函數指針集合的方式實現多態這一特性。
C語言作為一門較低級的語言，其底層的函數指針功能就是C++/JAVA等面向對象語言中虛函數表的基礎，只是C語言本身設計上並不支援語言級的面向對象編程，而必須由開發者手工的編寫類似的模板程式碼，自己實現面向對象語言中由編譯器自動實現的邏輯。
init_pmm_manager函數：
//init_pmm_manager - initialize a pmm_manager instance static void init_pmm_manager(void) { // pmm_manager默認指向default_pmm_manager 使用第一次適配演算法 pmm_manager = &default_pmm_manager; cprintf("memory management: %s\n", pmm_manager->name); pmm_manager->init(); }
pmm_manager定義：
// pmm_manager is a physical memory management class. A special pmm manager - XXX_pmm_manager // only needs to implement the methods in pmm_manager class, then XXX_pmm_manager can be used // by ucore to manage the total physical memory space. struct pmm_manager { const char *name; // XXX_pmm_manager's name // 管理器的名稱 void (*init)(void); // initialize internal description&management data structure // (free block list, number of free block) of XXX_pmm_manager // 初始化管理器 void (*init_memmap)(struct Page *base, size_t n); // setup description&management data structcure according to // the initial free physical memory space // 設置可管理的記憶體,初始化可分配的物理記憶體空間 struct Page *(*alloc_pages)(size_t n); // allocate >=n pages, depend on the allocation algorithm // 分配>=N個連續物理頁,返回分配塊首地址指針 void (*free_pages)(struct Page *base, size_t n); // free >=n pages with "base" addr of Page descriptor structures(memlayout.h) // 釋放包括自Base基址在內的，起始的>=N個連續物理記憶體頁 size_t (*nr_free_pages)(void); // return the number of free pages // 返回全局的空閑物理頁數量 void (*check)(void); // check the correctness of XXX_pmm_manager };
通過探測出的記憶體布局設置空閑物理映射空間
ucore使用一個通用的Page結構，來映射每個被管理的物理頁面。
其中調用的init_memmap函數，會通過pmm_manage框架的init_memmap，由指定的演算法來初始化其內部結構。在ucore lab2的參考答案中，默認使用的是default_pmm_manager，其使用的是效率雖然不高，但簡單、易理解的第一次適配演算法(first fit)。關於default_pmm_manager的細節，會在下面再展開介紹。
Page結構
/* * * struct Page - Page descriptor structures. Each Page describes one * physical page. In kern/mm/pmm.h, you can find lots of useful functions * that convert Page to other data types, such as phyical address. * */ struct Page { // 當前物理頁被虛擬頁面引用的次數(共享記憶體時，影響物理頁面的回收) int ref; // page frame's reference counter // 標誌位集合(目前只用到了第0和第1個bit位) bit 0表示是否被保留（可否用於物理記憶體分配: 0未保留，1被保留）;bit 1表示對於可分配的物理頁，當前是否是已被分配的 uint32_t flags; // array of flags that describe the status of the page frame // 在不同分配演算法中意義不同(first fit演算法中表示當前空閑塊中總共所包含的空閑頁個數 ，只有位於空閑塊頭部的Page結構才擁有該屬性，否則為0) unsigned int property; // the num of free block, used in first fit pm manager // 空閑鏈表free_area_t的鏈表節點引用 list_entry_t page_link; // free list link };
通過page_init函數可以利用之前在bootasm.S中探測到的e820map布局結構，初始化空閑物理記憶體空間。
page_init函數：
/* pmm_init - initialize the physical memory management */ static void page_init(void) { // 通過e820map結構體指針，關聯上在bootasm.S中通過e820中斷探測出的硬體記憶體布局 // 之所以加上KERNBASE是因為指針定址時使用的是線性虛擬地址。按照最終的虛實地址關係(0x8000 + KERNBASE)虛擬地址 = 0x8000 物理地址 struct e820map *memmap = (struct e820map *)(0x8000 + KERNBASE); uint64_t maxpa = 0; cprintf("e820map:\n"); int i; // 遍歷memmap中的每一項(共nr_map項) for (i = 0; i < memmap->nr_map; i ++) { // 獲取到每一個布局entry的起始地址、截止地址 uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size; cprintf(" memory: %08llx, [%08llx, %08llx], type = %d.\n", memmap->map[i].size, begin, end - 1, memmap->map[i].type); // 如果是E820_ARM類型的記憶體空間塊 if (memmap->map[i].type == E820_ARM) { if (maxpa < end && begin < KMEMSIZE) { // 最大可用的物理記憶體地址 = 當前項的end截止地址 maxpa = end; } } } // 迭代每一項完畢後，發現maxpa超過了定義約束的最大可用物理記憶體空間 if (maxpa > KMEMSIZE) { // maxpa = 定義約束的最大可用物理記憶體空間 maxpa = KMEMSIZE; } // 此處定義的全局end數組指針，正好是ucore kernel載入後定義的第二個全局變數(kern_init處第一行定義的) // 其上的高位記憶體空間並沒有被使用,因此以end為起點，存放用於管理物理記憶體頁面的數據結構 extern char end[]; // 需要管理的物理頁數 = 最大物理地址/物理頁大小 npage = maxpa / PGSIZE; // pages指針指向->可用於分配的，物理記憶體頁面Page數組起始地址 // 因此其恰好位於內核空間之上(通過ROUNDUP PGSIZE取整，保證其位於一個新的物理頁中) pages = (struct Page *)ROUNDUP((void *)end, PGSIZE); for (i = 0; i < npage; i ++) { // 遍歷每一個可用的物理頁，默認標記為被保留無法使用 SetPageReserved(pages + i); } // 計算出存放物理記憶體頁面管理的Page數組所佔用的截止地址 // freemem = pages(管理數據的起始地址) + (Page結構體的大小 * 需要管理的頁面數量) uintptr_t freemem = PADDR((uintptr_t)pages + sizeof(struct Page) * npage); // freemem之上的高位物理空間都是可以用於分配的free空閑記憶體 for (i = 0; i < memmap->nr_map; i ++) { // 遍歷探測出的記憶體布局memmap uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size; if (memmap->map[i].type == E820_ARM) { if (begin < freemem) { // 限制空閑地址的最小值 begin = freemem; } if (end > KMEMSIZE) { // 限制空閑地址的最大值 end = KMEMSIZE; } if (begin < end) { // begin起始地址以PGSIZE為單位，向高位取整 begin = ROUNDUP(begin, PGSIZE); // end截止地址以PGSIZE為單位，向低位取整 end = ROUNDDOWN(end, PGSIZE); if (begin < end) { // 進行空閑記憶體塊的映射，將其納入物理記憶體管理器中管理，用於後續的物理記憶體分配 // 這裡的begin、end都是探測出來的物理地址 // 第一個參數：起始Page結構的虛擬地址base = pa2page(begin) // 第二個參數：空閑頁的個數 = (end - begin) / PGSIZE init_memmap(pa2page(begin), (end - begin) / PGSIZE); } } } } }
初始化完畢後ucore物理記憶體布局示意圖：
其中page_init中的end指向了BSS段結束處，freemem指向空閑記憶體空間的起始地址。pages(內核頁表)位於”管理空閑空間的區域”這一記憶體塊中。實際可用於分配/釋放的空閑物理頁位於記憶體空間起始地址~實際物理記憶體空間結束地址之間。
對虛擬地址進行映射/解除映射
ucore的lab2中有兩個練習：
1. 通過一個線性地址來得到對應的二級頁表項(pmm.c中的get_pte函數)。得到這個二級頁表項地址後，便可以建立起虛擬地址與物理地址的映射關係。
2. 解除釋放一個二級頁表項與實際物理記憶體的映射關係(pmm.c中的page_remove_pte函數)。
需要注意的是，開啟了頁機制後，所有程式指令都是以邏輯地址(虛擬地址)的形式工作的，像指針、數組訪問時等都必須是虛擬地址才能正確的工作(例如使用KADDR宏進行轉換)。而頁表/頁目錄表中的存放的物理頁面基址映射都是物理地址。
get_pte函數：
//get_pte - get pte and return the kernel virtual address of this pte for la // - if the PT contains this pte didn't exist, alloc a page for PT // 通過線性地址(linear address)得到一個頁表項(二級頁表項)(Page Table Entry)，並返回該頁表項結構的內核虛擬地址 // 如果應該包含該線性地址對應頁表項的那個頁表不存在，則分配一個物理頁用於存放這個新創建的頁表(Page Table) // parameter: 參數 // pgdir: the kernel virtual base address of PDT 頁目錄表(一級頁表)的起始內核虛擬地址 // la: the linear address need to map 需要被映射關聯的線性虛擬地址 // create: a logical value to decide if alloc a page for PT 一個布爾變數決定對應頁表項所屬的頁表不存在時，是否將頁表創建 // return vaule: the kernel virtual address of this pte 返回值: la參數對應的二級頁表項結構的內核虛擬地址 pte_t * get_pte(pde_t *pgdir, uintptr_t la, bool create) { /* LAB2 EXERCISE 2: YOUR CODE * * If you need to visit a physical address, please use KADDR() * please read pmm.h for useful macros * * Maybe you want help comment, BELOW comments can help you finish the code * * Some Useful MACROs and DEFINEs, you can use them in below implementation. * MACROs or Functions: * PDX(la) = the index of page directory entry of VIRTUAL ADDRESS la. * KADDR(pa) : takes a physical address and returns the corresponding kernel virtual address. * set_page_ref(page,1) : means the page be referenced by one time * page2pa(page): get the physical address of memory which this (struct Page *) page manages * struct Page * alloc_page() : allocation a page * memset(void *s, char c, size_t n) : sets the first n bytes of the memory area pointed by s * to the specified value c. * DEFINEs: * PTE_P 0x001 // page table/directory entry flags bit : Present * PTE_W 0x002 // page table/directory entry flags bit : Writeable * PTE_U 0x004 // page table/directory entry flags bit : User can access */ #if 0 pde_t *pdep = NULL; // (1) find page directory entry if (0) { // (2) check if entry is not present // (3) check if creating is needed, then alloc page for page table // CAUTION: this page is used for page table, not for common data page // (4) set page reference uintptr_t pa = 0; // (5) get linear address of page // (6) clear page content using memset // (7) set page directory entry's permission } return NULL; // (8) return page table entry #endif // PDX(la) 根據la的高10位獲得對應的頁目錄項(一級頁表中的某一項)索引(頁目錄項) // &pgdir[PDX(la)] 根據一級頁表項索引從一級頁表中找到對應的頁目錄項指針 pde_t *pdep = &pgdir[PDX(la)]; // 判斷當前頁目錄項的Present存在位是否為1(對應的二級頁表是否存在) if (!(*pdep & PTE_P)) { // 對應的二級頁表不存在 // *page指向的是這個新創建的二級頁表基地址 struct Page *page; if (!create || (page = alloc_page()) == NULL) { // 如果create參數為false或是alloc_page分配物理記憶體失敗 return NULL; } // 二級頁表所對應的物理頁 引用數為1 set_page_ref(page, 1); // 獲得page變數的物理地址 uintptr_t pa = page2pa(page); // 將整個page所在的物理頁格式胡，全部填滿0 memset(KADDR(pa), 0, PGSIZE); // la對應的一級頁目錄項進行賦值，使其指向新創建的二級頁表(頁表中的數據被MMU直接處理，為了映射效率存放的都是物理地址) // 或PTE_U/PTE_W/PET_P 標識當前頁目錄項是用戶級別的、可寫的、已存在的 *pdep = pa | PTE_U | PTE_W | PTE_P; } // 要想通過C語言中的數組來訪問對應數據，需要的是數組基址(虛擬地址),而*pdep中頁目錄表項中存放了對應二級頁表的一個物理地址 // PDE_ADDR將*pdep的低12位抹零對齊(指向二級頁表的起始基地址)，再通過KADDR轉為內核虛擬地址，進行數組訪問 // PTX(la)獲得la線性地址的中間10位部分，即二級頁表中對應頁表項的索引下標。這樣便能得到la對應的二級頁表項了 return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)]; }
page_remove_pte函數：
//page_remove_pte - free an Page sturct which is related linear address la // - and clean(invalidate) pte which is related linear address la //note: PT is changed, so the TLB need to be invalidate static inline void page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) { /* LAB2 EXERCISE 3: YOUR CODE * * Please check if ptep is valid, and tlb must be manually updated if mapping is updated * * Maybe you want help comment, BELOW comments can help you finish the code * * Some Useful MACROs and DEFINEs, you can use them in below implementation. * MACROs or Functions: * struct Page *page pte2page(*ptep): get the according page from the value of a ptep * free_page : free a page * page_ref_dec(page) : decrease page->ref. NOTICE: ff page->ref == 0 , then this page should be free. * tlb_invalidate(pde_t *pgdir, uintptr_t la) : Invalidate a TLB entry, but only if the page tables being * edited are the ones currently in use by the processor. * DEFINEs: * PTE_P 0x001 // page table/directory entry flags bit : Present */ #if 0 if (0) { //(1) check if page directory is present struct Page *page = NULL; //(2) find corresponding page to pte //(3) decrease page reference //(4) and free this page when page reference reachs 0 //(5) clear second page table entry //(6) flush tlb } #endif if (*ptep & PTE_P) { // 如果對應的二級頁表項存在 // 獲得*ptep對應的Page結構 struct Page *page = pte2page(*ptep); // 關聯的page引用數自減1 if (page_ref_dec(page) == 0) { // 如果自減1後，引用數為0，需要free釋放掉該物理頁 free_page(page); } // 清空當前二級頁表項(整體設置為0) *ptep = 0; // 由於頁表項發生了改變，需要TLB快表 tlb_invalidate(pgdir, la); } }
default_pmm.c 第一次適配分配演算法分析
ucore提供了pmm_manager框架，可以支援靈活的切換多種物理記憶體分配演算法。而為了實驗的簡單性，ucore的參考答案提供了相對好理解的first fit第一次適配演算法作為例子，來展示ucore是的物理記憶體管理功能時如何工作的。
在ucore的第一次適配分配演算法中，是通過一個雙向鏈表結構來連接各個連續空閑塊的，即定義在default_pmm.c中的free_area_t變數。free_area_t結構十分簡單，一個整數nr_free記錄著全局保存著多少空閑物理頁，另一個list_entry_t類型的變數free_list，作為整個空閑鏈表的頭結點。
free_area_t結構：
/* free_area_t - maintains a doubly linked list to record free (unused) pages */ typedef struct { list_entry_t free_list; // the list header unsigned int nr_free; // # of free pages in this free list } free_area_t;
list_entry_t結構：
struct list_entry { struct list_entry *prev, *next; }; typedef struct list_entry list_entry_t;
回顧一下Page結構的定義，其中包含了一個屬性page_link，就可以用於掛載到free_area_t空閑鏈表中。
ucore通用雙向鏈表介紹
如果對數據結構中的雙向鏈表知識有一定了解的話，可能會對ucore中雙向鏈表的實現感到疑惑。
一般來說，雙向鏈表結構的節點除了前驅和後繼節點的指針/引用之外，還存在一個用於包裹業務數據的data屬性，而ucore中的鏈表節點list_entry卻沒有這個data數據屬性。這是因為ucore中的雙向鏈表結構在設計之初是希望能夠通用的：不但能將Page結構鏈接起來，還能鏈接其它任意的數據。而C語言中並沒有c++或是java中的泛型功能，只能定義為某一特定類型的data屬性，如果data域與鏈表的節點定義在一起的話，就沒法做到足夠通用。
ucore參考了linux中的做法，反其道而行：不再是雙向鏈表的節點包裹數據，而是由數據本身保存鏈表節點引用。這樣設計的最大好處就是鏈表可以通用，能夠鏈接各種類型的數據結構到一起；但與此同時也帶來了一些問題，比如其降低了程式碼的可讀性，編譯器也沒法確保鏈表中的數據都是合理的類型。
le2page宏的原理
在對傳統的雙向鏈表遍歷時，由於是鏈表節點本身包裹了data，因此可以直接訪問到節點關聯的data數據。而在ucore的雙向鏈表實現中，由於鏈表節點本身沒有保存data數據，而是反被data數據包裹，因此需要一些比較巧妙(tricky)的方法來實現對節點所屬結構的訪問。
在空閑鏈表這一實現中，是由Page結構包裹著鏈表節點page_link。ucore提供了le2page宏，通過le2page可以由page_link反向得到節點所屬的Page結構。
在ucore中，就有通過struct Page *p = le2page(le, page_link)這樣的邏輯，其中le是鏈表節點的指針。
// convert list entry to page #define le2page(le, member) \ to_struct((le), struct Page, member) /* * * to_struct - get the struct from a ptr * @ptr: a struct pointer of member * @type: the type of the struct this is embedded in * @member: the name of the member within the struct * */ #define to_struct(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member))) /* Return the offset of 'member' relative to the beginning of a struct type 返回member到結構起始地址的相對偏移*/ #define offsetof(type, member) \ ((size_t)(&((type *)0)->member))
可以看到le2page宏是依賴to_struct這一通用宏來實現的。在le2page中，其傳遞給to_struct宏的三個參數分別是鏈表的指針ptr，type為Page結構體本身的定義，member為page_link。
C語言中，結構體中數據結構的最終在虛擬記憶體空間中是按照屬性的順序，從低位到高位排列的，而page_link的指針地址必然高於Page結構的基地址，且兩者之間的差值可以通過結構體中的定義得到。在to_struct中，通過ptr(即page_link的指針地址)減去offset(type,member)(即page_link到Struct Page結構的相對偏移)，便能夠得到page_link節點所屬Page結構的首地址。最後通過type *，將其強制轉換為對應的Page指針。
offsetof宏巧妙的構造了一個位於起始地址0的type類型指針，並通過&獲得其member屬性的地址。由於其結構指針的初始地址為0，則最後得到的就是member欄位相對於type結構基址的相對偏移量了。
這是C語言中通過結構體中某一屬性地址訪問其所屬結構體的一種巧妙實現。
le2page宏對於C語言的初學者來說確實不是很好理解，連注釋中都指出這一做法有些tricky，但在理解其原理之後，未來實驗中更多依賴to_struct宏的地方就不會再被困擾了。
le2page原理圖：
default_pmm.c 第一次適配分配演算法中的分配與釋放功能的分析
default_pmm.c中完整的實現了pmm_manager所指定的函數介面，限於篇幅，這裡只重點介紹其分配與釋放物理記憶體頁的功能。
分配物理記憶體頁的功能由default_alloc_pages函數完成；釋放物理記憶體頁的功能由default_free_pages函數完成。
default_alloc_pages函數：
/** * 接受一個合法的正整數參數n，為其分配N個物理頁面大小的連續物理記憶體空間. * 並以Page指針的形式，返回最低位物理頁(最前面的)。 * * 如果分配時發生錯誤或者剩餘空閑空間不足，則返回NULL代表分配失敗 * */ static struct Page * default_alloc_pages(size_t n) {
assert(n > 0); if (n > nr_free) { return NULL; } struct Page *page = NULL; list_entry_t *le = &free_list; // TODO: optimize (next-fit) // 遍歷空閑鏈表 while ((le = list_next(le)) != &free_list) { // 將le節點轉換為關聯的Page結構 struct Page *p = le2page(le, page_link); if (p->property >= n) { // 發現一個滿足要求的，空閑頁數大於等於N的空閑塊 page = p; break; } } // 如果page != null代表找到了，分配成功。反之則分配物理記憶體失敗 if (page != NULL) { if (page->property > n) { // 如果空閑塊的大小不是正合適(page->property != n) // 按照指針偏移，找到按序後面第N個Page結構p struct Page *p = page + n; // p其空閑塊個數 = 當前找到的空閑塊數量 - n p->property = page->property - n; SetPageProperty(p); // 按對應的物理地址順序，將p加入到空閑鏈表中對應的位置 list_add_after(&(page->page_link), &(p->page_link)); } // 在將當前page從空間鏈表中移除 list_del(&(page->page_link)); // 閑鏈表整體空閑頁數量自減n nr_free -= n; // 清楚page的property(因為非空閑塊的頭Page的property都為0) ClearPageProperty(page); } return page; }
default_free_pages函數：
/** * 釋放掉自base起始的連續n個物理頁,n必須為正整數 * */ static void default_free_pages(struct Page *base, size_t n) { assert(n > 0); struct Page *p = base; // 遍歷這N個連續的Page頁，將其相關屬性設置為空閑 for (; p != base + n; p ++) { assert(!PageReserved(p) && !PageProperty(p)); p->flags = 0; set_page_ref(p, 0); } // 由於被釋放了N個空閑物理頁，base頭Page的property設置為n base->property = n; SetPageProperty(base); // 下面進行空閑鏈表相關操作 list_entry_t *le = list_next(&free_list); // 迭代空閑鏈表中的每一個節點 while (le != &free_list) { // 獲得節點對應的Page結構 p = le2page(le, page_link); le = list_next(le); // TODO: optimize if (base + base->property == p) { // 如果當前base釋放了N個物理頁後，尾部正好能和Page p連上，則進行兩個空閑塊的合併 base->property += p->property; ClearPageProperty(p); list_del(&(p->page_link)); } else if (p + p->property == base) { // 如果當前Page p能和base頭連上，則進行兩個空閑塊的合併 p->property += base->property; ClearPageProperty(base); base = p; list_del(&(p->page_link)); } } // 空閑鏈表整體空閑頁數量自增n nr_free += n; le = list_next(&free_list); // 迭代空閑鏈表中的每一個節點 while (le != &free_list) { // 轉為Page結構 p = le2page(le, page_link); if (base + base->property <= p) { // 進行空閑鏈表結構的校驗，不能存在交叉覆蓋的地方 assert(base + base->property != p); break; } le = list_next(le); } // 將base加入到空閑鏈表之中 list_add_before(le, &(base->page_link)); }
三、總結
從ucore lab2的實驗pmm_manager框架的實現中使得我進一步的意識到面向對象，或者說是面向介面/協議編程並不是面向對象語言的專屬。面向對象這一概念更多的是一種通過抽象、聚合進行模組化，降低系統複雜度的一種思想。在ucore中就用C語言以面向對象的方式，解耦了具體的物理記憶體分配策略與使用物理記憶體管理邏輯的解耦，而在《電腦程式的構造與解釋》SICP一書中，便是用lisp這一被公認為是函數式編程範式的語言實現了一個面向對象的系統。面向對象與函數式這兩種編程範式並不是水火不容的，而都是作為一種控制系統整體複雜度的抽象手段之一。
仔細觀察pmm_manager框架的設計，可以明顯感到C的多態實現不如支援面向對象編程的語言優雅，需要額外編寫許多模板程式碼，且無法得到編譯器更多的支援。這樣一種類似設計模式的繁瑣實現方式，在某種程度上來說也體現了C語言本身表達能力不足的缺陷，也是後來C++出現的一個主要原因。
通過ucore的實驗，令我們能從源碼層面實現不同物理記憶體的分配演算法(挑戰練習中要求實現更複雜的夥伴系統、slab分配器)，使得作業系統書籍、原理課上講解的相關理論不再枯燥，而是變得栩栩如生了，
這篇部落格的完整程式碼注釋在我的github上：//github.com/1399852153/ucore_os_lab (fork自官方倉庫)中的lab2_answer。
希望我的部落格能幫助到對作業系統、ucore os感興趣的人。存在許多不足之處，還請多多指教。
