Lab2
0. 任務介紹
你将編寫一個記憶體管理代碼。主要分為兩大部分。分别對實體記憶體和虛拟記憶體的管理。
- 對于實體記憶體，每次配置設定記憶體配置設定器會為你配置設定4096bytes。也稱為一個頁（在大部分作業系統中一個頁的大小都是4B）你需要維護一個資料結構來記錄哪個實體頁是空閑的哪個實體頁是已被占用的。以及有多少程序共享已配置設定的頁。并且你需要編寫程式來進行記憶體的配置設定和回收
- 對于虛拟記憶體，它将核心和使用者軟體使用的虛拟位址映射到實體記憶體中的位址。 x86硬體的記憶體管理單元（MMU）在指令使用記憶體時執行映射，查閱一組頁面表。 您将根據我們提供的規範設定MMU的頁面表。
1. Part1: Physical Page Management
作業系統必須跟蹤哪部分實體記憶體是被使用的以及哪部分實體記憶體是空閑的。你需要在切入到虛拟記憶體之前完成這一操作，因為當使用虛拟記憶體的時候我們需要頁表來進行管理，而你需要為頁表配置設定實體記憶體。
下面的圖來自于[https://blog.csdn.net/qq_40871466/article/details/103922416]
你需要實作
kern/pmap.c
的下列函數
boot_alloc()
mem_init() (only up to the call to `check_page_free_list(1)`)
page_init()
page_alloc()
page_free()
check_page_free_list()
and
check_page_alloc()
test your physical page allocator. You should boot JOS and see whether
check_page_alloc()
reports success. Fix your code so that it passes.
1.1 實作boot_alloc
在lab1我們知道了pc的啟動過程。這裡是在核心執行的init.c中先調用了
mem_init
。
根據我的調試輸出(printf)我發現
.bss的位址是 0xf01156a0
這個位址在虛拟位址0xf0000000之上。我們知道核心的虛拟位址是在0xf0000000為起點的。随後是核心的代碼段+資料段然後就是
.bss
是以這裡bss大于核心虛拟位址起始位置是合理的.
boot_alloc
就是在
.bss
之上配置設定制定大小為n的區域。注意這裡都是在虛拟記憶體位址下進行的操作
- 如果n為0則直接範圍
nextfree
- 如果不為0則為他配置設定記憶體。其實就是把nextfree的位址往後移動 (n * PGSIZE)。不過我們要傳回這段位址的起始位址。就相當于一個page數組的起始位址
static void *
boot_alloc(uint32_t n)
{
static char *nextfree; // virtual address of next byte of free memory
char *result;
if (!nextfree) {
extern char end[];
cprintf("end is %08x\n",end);
nextfree = ROUNDUP((char *) end, PGSIZE);
}
cprintf("nextfree is %08x\n",nextfree);
// Allocate a chunk large enough to hold 'n' bytes, then update
// nextfree. Make sure nextfree is kept aligned
// to a multiple of PGSIZE.
//
// LAB 2: Your code here.
if (n == 0) {
return nextfree;
}
//allocate
result = nextfree;
nextfree = ROUNDUP((char *)(nextfree + n), PGSIZE);
return result;
}
1.2 實作 mem_init
mem_init
在mem_init中我們會調用兩次boot_alloc。第一次為了建立頁目錄。第二次則為了建立所有的實體頁表。分别為它們配置設定記憶體然後memset成0。
// create initial page directory.
kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
memset(kern_pgdir, 0, PGSIZE);
//////////////////////////////////////////////////////////////////////
// Recursively insert PD in itself as a page table, to form
// a virtual page table at virtual address UVPT.
// (For now, you don't have understand the greater purpose of the
// following line.)
// Permissions: kernel R, user R
kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;
cprintf("Page nubmer %d\n",npages);
//////////////////////////////////////////////////////////////////////
// Allocate an array of npages 'struct PageInfo's and store it in 'pages'.
// The kernel uses this array to keep track of physical pages: for
// each physical page, there is a corresponding struct PageInfo in this
// array. 'npages' is the number of physical pages in memory. Use memset
// to initialize all fields of each struct PageInfo to 0.
// Your code goes here:
// all 32768 number pages
pages = (struct PageInfo *) boot_alloc(sizeof(struct PageInfo) * npages);
memset(pages, 0, sizeof(struct PageInfo) * npages);
1.3 實作 page_alloc
page_alloc
這裡給了我們示例代碼。不過這裡把所有的pages都初始化了成了0和可用。這顯然是不合理的
-
根據下圖和實驗中給的提示。base_memory(也就是 1mb + extended_memoy)這一段 。的low memory是可以被配置設定成use的
但是注意最下面的一個page不可以(實驗中有提到儲存實模式的一些資訊)
-
第二就是extended memory裡會存有核心的資訊。我們要找到核心的結束位置，然後給剩餘部分進行初始化
這裡就可以簡單利用boot_alloc(0)。因為這個會傳回核心的結束位置對應的虛拟位址。
但是我們要找的是這個虛拟位址定于的實體位址在哪個page中。也就是要找到它在pages數組中的标号。
這裡實驗給我們提供了一個宏定義
page2kva
即可獲得它對應的實體位址。然後除頁表大小就可以獲得對應的标号
好了代碼已經呼之欲出了
cprintf("npages_basemem is %d\n",npages_basemem); cprintf("pages addr is %0x8 \n", pages); size_t i; //all low memeory is free expect 0 page for (i = 1; i < npages_basemem; i++) { cprintf("pages addr is %0x8 \n", pages[i]); pages[i].pp_ref = 0; pages[i].pp_link = page_free_list; page_free_list = &pages[i]; } i = PADDR(boot_alloc(0)) / PGSIZE; for (; i < npages; i++) { pages[i].pp_ref = 0; pages[i].pp_link = page_free_list; page_free_list = &pages[i]; } }1.4 實作
這個就比較簡單了。隻需要簡單的把要釋放的頁加入到page_free
free_page_list
中就好。
根據實驗中給出的提示，可以很容易的寫出來
void page_free(struct PageInfo *pp) { // Fill this function in // Hint: You may want to panic if pp->pp_ref is nonzero or // pp->pp_link is not NULL. if (pp->pp_ref || pp->pp_link) { panic("no shoule page free"); } //head insert pp -> pp_link = page_free_list; page_free_list = pp; }
2. Part2: Virtual Memory
跳過中間的一些廢話，直接開始exercise4。這裡要求我們編寫代碼來管理頁面表。要插入和删除linear-to-physical(其實就是虛拟位址和實體位址之間的mappings，并按需配置設定頁。
這個是JOS所用的32位虛拟位址的分布
下面就是虛拟位址的翻譯過程。這個學過os的應該非常熟悉了吧。這裡的
page_dir
和
page_table
其實就是一個二級頁表。的多級索引非常簡單。
整體過程就是我們先通過CR3寄存器找到
PAGE_DIR
所在的位置，然後通過虛拟位址的前10位在PAGE_DIR中擷取到下一級頁表，也就是
PAGE_TABLE
的位址。随後通過虛拟位址的12-21這10位去找到對應的PAGE_FRAME的位址。從裡面擷取到ppa的位址結合OFFSET就可以得到最終的實體位址了。
好了搞清楚大概邏輯之後，下面開始完成第二部分的代碼
2.1 pgdir_walk
這個代碼是後面四個代碼的基礎，是以一定要小心認真，這裡的意思就是說給你pgdir的位址。和虛拟位址va你要傳回一個指向pte的指針。pte就是頁表條目在最後一層頁表對應位置處。
- 首先我們通過幾個宏定義把虛拟位址分解
- 如果page_dir對應的PTE_P也就是有效位為0的話則表明相關的頁表條目并不存在
- 如果不存在的話需要通過create标記來判斷是否需要建立對應的頁
- 這裡根據提示我們需要把新建立頁的實體位址存儲在對應的page_dir位置處
- 然後就是在page_table中找到對應的PTE傳回
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
// Fill this function in
uintptr_t dir = PDX(va); //表示對應的page_dir索引
uintptr_t page = PTX(va); // 表示對應的page_table索引
uintptr_t offset = PGOFF(va); // 表示在page中對應的頁内偏移
pde_t dir_entry = pgdir[dir]; // 首先要判斷這個虛拟位址是否有映射
if (!(dir_entry & PTE_P)) {
if (create) {
// allocate
struct PageInfo *newPage = page_alloc(ALLOC_ZERO);
if (newPage == NULL) {
// allocation failed
return NULL;
}
newPage->pp_ref++;
pgdir[dir] = (pde_t)page2pa(newPage)|PTE_P|PTE_U|PTE_W;
} else {
return NULL;
}
}
//
pte_t *ptab = (pte_t *)KADDR(PTE_ADDR(pgdir[dir]));
return &ptab[page];
}
2.2 boot_map_region
這個函數的實作就比較簡單了。要求是把虛拟位址[va, va+size)映射到實體位址[pa, pa+size]，使用權限位為perm|PTE_P，隻是在UTOP上方做靜态映射，是以不能修改pp_ref字段.
基本上就是通過上面實作的
pgdir_walk
函數找到給定虛拟位址對應的pte。然後修改pte條目即可
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
// Fill this function in
uintptr_t start = 0;
for ( ; start < size; start += PGSIZE, va += PGSIZE, pa += PGSIZE) {
pte_t *pte = pgdir_walk(pgdir,(void *) va, 1);
*pte = pa | perm | PTE_P;
}
}
2.3 Page_lookup
傳回一個虛拟位址va映射的頁面。如果pte_store不是0，那麼将對應的頁表項位址存到pte_store的位址裡（用于結果傳回）。如果沒有頁面映射在va那麼傳回NULL。提示：使用pgdir_walk和pa2page
struct PageInfo *
pgee_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
// Fill this function in
pte_t *pte = pgdir_walk(pgdir,(void *) va, 0);
if (!pte) {
return NULL;
}
if (*pte && !(*pte & PTE_P)) {
return NULL;
}
if (pte_store) {
*pte_store = pte;
}
struct PageInfo* page = pa2page(PTE_ADDR(*pte));
return page;
}
基本上通過給的提示就可以實作這個函數
2.4 Page_remove
也是通過提示。移除給定的va對應的映射。
- 如果給定的va在頁表中沒有對應映射則直接傳回。
- 否則把對應的pte清0,然後調用
tlb_invalidate
page_decref
void
page_remove(pde_t *pgdir, void *va)
{
// Fill this function in
pte_t * pte;
struct PageInfo *page = page_lookup(pgdir,va,&pte);
if (!page) {
return;
}
*pte = 0;
tlb_invalidate(pgdir,va);
page_decref(page);
}
2.5 Page_insert
把實體頁pp映射在虛拟位址va，頁表項權限設定為perm|PTE_P。
- 如果已經有一個頁面在va，它應該先調用page_remove()删除
- 如有必要，應按需配置設定頁表并将其插入“ pgdir”。插入成功pp->ref應該自增。如果以前有頁面位于“ va”，則TLB必須無效。
- 提示：使用pgdir_walk,page_remove和page2pa。
- 根據提示我們需要配置設定頁表并将其插入pgdir。這不是就是前面實作的pgir_walk把crate設定成1的功能。
- 同樣如果以前有頁面位于va。則讓他的tlb無效。。這裡聽起來很麻煩，但實際上隻需要調用page_remove原來va對應的映射移除即可。而且page_remove已經實作了讓tlb無效的操作。
int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
// Fill this function in
pte_t *pte = pgdir_walk(pgdir,(void *) va, 1);
if (!pte) {
return -E_NO_MEM;
}
pp->pp_ref++;
if (*pte & PTE_P) {
page_remove(pgdir,va);
}
*pte = page2pa(pp) | perm | PTE_P;
return 0;
}
3. Part3 : Kernel Address Space
第三部分需要我們補齊
mem_init
函數
隻要跟随提示來完成對于核心部分的一些映射。按照下面這樣做就好了
boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U);
boot_map_region(kern_pgdir, KSTACKTOP - KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);
boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W);
3.1 Question
補充完第三部分的代碼之後，我們來看一下第三部分的問題
- What entries (rows) in the page directory have been filled in at this point? What addresses do they map and where do they point? In other words, fill out this table as much as possible:
Entry Base Virtual Address Points to (logically): 1023 0xff000000 Page table for top 4MB of phys memory 1022 ? ? 959 0xefc00000 cpu0's kernel stack(0xefff8000),cpu1's kernel stack(0xeffe8000) 956 0xef000000 npages of PageInfo(0xef000000) 952 0xee000000 bootstack 2 0x00800000 Program Data & Heap 1 0x00400000 Empty 0x00000000 [see next question] 這個地方要參考一下
memlayout.h
就可以寫出了
其實主要搞清楚幾個重要的就可以了
比如0xef000000表示UPAGES
oxefc00000表示核心棧等等
- We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel's memory? What specific mechanisms protect the kernel memory?
通過把頁表項中的 Supervisor/User位置0，那麼使用者态的代碼就不能通路記憶體中的這個頁。
- What is the maximum amount of physical memory that this operating system can support? Why?
這個作業系統利用一個大小為4MB的空間也就是UPAGES這一段。來存放所有的頁的PageInfo結構體資訊，每個結構體的大小為8B，是以一共可以存放512K個PageInfo結構體，是以一共可以出現512K個實體頁，每個實體頁大小為4KB，自然總的實體記憶體占2GB。
- How much space overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this overhead broken down?
這個問題是說如果我們現在的實體頁達到最大，那麼管理這些記憶體所需要的額外空間開銷有多少
首先我們所有的pageinfo需要4mb。然後需要存放頁目錄表。一共1024個每一個需要4B是以一共4kb
還有存放目前的頁表。頁表是1024 * 4kb = 4mb
是以一共需要4MB + 4MB + 4KB = 8MB + 4KB
- Revisit the page table setup in
kern/entry.S
kern/entrypgdir.c
- 是通過下面的代碼來跳轉到kernbase之上的虛拟位址的
mov $relocated, %eax
jmp *%eax
-
是因為我們把[0,4mb]和[KernalBASE,KERNALBASR + 4MB]這段的虛拟位址都映射到了0-4MB的實體位址上，是以無論EIP在高位還是在低位都可以運作。必須這樣做的原因是，如果隻映射高位位址。在我們剛開啟分頁模式之後就會crash。
因為剛開始我們通路的還是地位位址。是通過jump來跳轉到高位》
4. Part4 : Challenge
//TODO