環(huán)境
Ubuntu 20.04 64 位系統(tǒng)
Lab的地址:點(diǎn)擊這里去Lab2
準(zhǔn)備工作
因?yàn)樵贚ab1當(dāng)中代碼我寫了很多注釋在里面派昧，并且還有修改了一些代碼。所以我重新clone一份lab1疆偿。然后執(zhí)行下面的命令就行:
git checkout -b lab2 origin/lab2
git merge lab1
這樣一來應(yīng)該就看到lab2新的一些文件出現(xiàn)了碗淌。接下來直接開始做lab2吧隅肥，雖然mit6.828要求學(xué)生做至少一個(gè)challenge,但是覺challenge都挺難的弄砍。我就沒做。
Part1
這次不像Lab1一樣對(duì)lab介紹的非常仔細(xì)裸准。一上來就直接說把下面幾個(gè)函數(shù)補(bǔ)充完整還是有被嚇到梅尤。不過認(rèn)真看代碼里面的注釋還是能知道實(shí)現(xiàn)的函數(shù)時(shí)干嘛的柜思。在正式開始寫代碼之前，先看一下實(shí)際上內(nèi)存的結(jié)構(gòu):
在8086的時(shí)候巷燥，尋址范圍時(shí)0-1MB赡盘。所以在32bit機(jī)器里面我們將大于1MB的內(nèi)存叫extended memory》龋看具體的硬件亡脑，在32bit機(jī)器中extended memory最大可以到4GB。上面這幅圖對(duì)page_init()的實(shí)現(xiàn)很重要邀跃。待會(huì)可以重新回來看霉咨。
另外一個(gè)很重要的結(jié)構(gòu)就是PageInfo,每一個(gè)頁(yè)都有自己對(duì)應(yīng)的一個(gè)PageInfo。他有兩個(gè)變量
struct PageInfo {
struct PageInfo* pp_link;
uint16_t pp_ref;
}
這個(gè)結(jié)構(gòu)其實(shí)有點(diǎn)像鏈表的node拍屑，鏈表的node有一個(gè)變量next途戒，這里的pp_link就是和next的作用差不多。因?yàn)橄到y(tǒng)當(dāng)中所有科用的頁(yè)我們使用一個(gè)鏈表來管理僵驰。暫時(shí)不了解也沒關(guān)系喷斋，看接下來的代碼實(shí)現(xiàn)應(yīng)該可以理解的。
第一題 實(shí)現(xiàn)boot_alloc()
注釋里說了他不是真正的physical memory alloctor蒜茴。此時(shí)我們還沒有初始化將所有的可用內(nèi)存用鏈表串起來星爪。因?yàn)槲覀冊(cè)趀ntry.S里面已經(jīng)開啟了paging，對(duì)照一下上圖粉私，有些地址是不能使用的顽腾，比如IO hole。所以他不是真正的allocator,只是在這里臨時(shí)用一下诺核。page_alloc()才是真正的內(nèi)存分配函數(shù)抄肖。
先上答案在解釋久信。
static void * boot_alloc(uint32_t n)
{
static char *nextfree; // virtual address of next byte of free memory
char *result;
// Initialize nextfree if this is the first time.
// 'end' is a magic symbol automatically generated by the linker,
// which points to the end of the kernel's bss segment:
// the first virtual address that the linker did *not* assign
// to any kernel code or global variables.
if (!nextfree) {
extern char end[];
nextfree = ROUNDUP((char *) end, PGSIZE);
}
// 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.
result = nextfree;
nextfree = ROUNDUP(nextfree+n,PGSIZE); //n決定了是直接返回可用的地址還是分配后再返回。
if((uint32_t) nextfree - KERNBASE > (npages*PGSIZE)) {
panic("next free memory address is out of memory");
}
//返回當(dāng)前空閑的地址
return result;
}
那個(gè)if判斷是初始化了nextfree漓摩，這里一個(gè)比較取巧的寫法就是end points to end of bss segment裙士。然后第一次運(yùn)行boot_alloc的時(shí)候條件成立，nextfree指向內(nèi)核代碼尾端4kb對(duì)齊的第一個(gè)字節(jié)管毙。后面的內(nèi)存都是空的腿椎，可以隨便使用。要求完成的代碼按照注釋應(yīng)該可以理解夭咬，不再過多解釋酥诽。注意，如果申請(qǐng)的內(nèi)存大于物理內(nèi)存大小皱埠，應(yīng)該panic，所以要加一個(gè)判斷咖驮。哦對(duì)了,npages是系統(tǒng)所有的頁(yè)的數(shù)量边器，在i386_detect_memory中計(jì)算好的。所以系統(tǒng)可用的內(nèi)存大小:npages*PGSIZE托修。
第二題 補(bǔ)充mem_init()中的代碼
現(xiàn)在我們分配內(nèi)存的函數(shù)已經(jīng)實(shí)現(xiàn)了忘巧，接下來就是存放pages這個(gè)數(shù)組。所以思路很簡(jiǎn)單睦刃，只要計(jì)算出所有的PageInfo一共需要多少內(nèi)存(一個(gè)page對(duì)應(yīng)一個(gè)PageInfo)砚嘴，然后把boot_alloc()的返回的地址賦值給pages就好
pages = (struct PageInfo*) boot_alloc(npages * sizeof (struct PageInfo));
memset(pages,0, npages* sizeof (struct PageInfo));
第三題 補(bǔ)充page_init() 的代碼
這題的關(guān)鍵就是看一下上面的圖，還有就是注釋里面的內(nèi)容涩拙。前面說過,用鏈表來管理所有空閑的頁(yè)际长，指針page_free_list就是鏈表的表頭。指針的內(nèi)容是某個(gè)PageInfo的地址兴泥。下圖幫助理解:
畫的很難看工育，不過大概意思應(yīng)該是明確了。page_free_list將所有的空閑PageInfo串起來搓彻。PageInfo中如绸，1表示被用，0表示空閑旭贬。關(guān)于鏈表的插入怔接，我們的代碼實(shí)現(xiàn)的使用頭插法。
EXPTHSNEN這個(gè)就是IO hole頂部的地址0x10000稀轨。在extended memory當(dāng)中扼脐，有一部分內(nèi)存已經(jīng)被內(nèi)核使用了，那么我們?nèi)绾沃纼?nèi)核使用了到哪里了靶端？答案就是用boot_alloc(0)谎势，當(dāng)參數(shù)為0的時(shí)候boot_alloc會(huì)返回當(dāng)前的空閑地址凛膏。0x10000(IO hole的頂部) 到 boot_alloc(0)這一塊都被內(nèi)存使用了。另外脏榆，因?yàn)槲覀儸F(xiàn)在已經(jīng)開啟了paging猖毫，現(xiàn)在都是地址都是虛擬地址，所以還需要將boot_alloc(0)得到的虛擬地址用PADRR（）轉(zhuǎn)為物理地址须喂。本題的代碼實(shí)現(xiàn)如下吁断，注意結(jié)合注釋來理解:
void page_init(void)
{
pages[0].pp_ref = 1;
// IO hole之前的內(nèi)存都是free的
size_t i ;
for ( i = 1; i < npages_basemem; i++) {
pages[i].pp_ref = 0;
//這里設(shè)想一下鏈表的頭插法就理解了！
pages[i].pp_link = page_free_list;
//&pages[i]并不是真正的空閑頁(yè)的地址坞生，這是Pages這個(gè)數(shù)組中的元素的地址
//page2pa這個(gè)函數(shù)才是得到真正的地址的仔役。
page_free_list = &pages[i];
}
//IO hole
for(; i < EXTPHYSMEM/PGSIZE; i++) {
pages[i].pp_ref = 1;
}
//Kernel占據(jù)了從0x0010_0000 - 0x0fff_ffff，這一部分是kernel的
//所以第一個(gè)空閑的頁(yè)就緊跟在內(nèi)核之后是己，所以 end of IO hole ~ first free page 就是內(nèi)核占據(jù)的內(nèi)存
///PADDR是將虛擬地址轉(zhuǎn)為實(shí)際的物理地址
physaddr_t first_free_addr = PADDR(boot_alloc(0));
size_t first_free_page = first_free_addr/PGSIZE;
for(; i < first_free_page; i++) {
pages[i].pp_ref = 1;
}
//內(nèi)核之后的所有內(nèi)存都是free的
for(; i < npages; i++ ) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
}
第四題 實(shí)現(xiàn)page_alloc()
在上一題我們已經(jīng)將所有空閑的頁(yè)表的PageInfo用page_free_list串起來又兵。所以新分配一個(gè)頁(yè)只需要從pagr_free_list空閑的第一個(gè)取出即可。注釋里面還要我們?nèi)ネ瓿?code>if(alloc & ALLOC_ZERO)條件成立卒废，將對(duì)應(yīng)頁(yè)內(nèi)的內(nèi)容都改為0沛厨。Hint:使用page2kva（）這個(gè)函數(shù)來獲得對(duì)應(yīng)頁(yè)的虛擬地址，用memset()來設(shè)置內(nèi)存的值摔认。還有一點(diǎn)就是注釋里說了不要增加pp_ref逆皮，讓caller去做這件事。注釋說的還是比較清楚的参袱。直接給代碼實(shí)現(xiàn)电谣；
struct PageInfo * page_alloc(int alloc_flags)
{
// Fill this function in
if( page_free_list == NULL) {
return NULL;
}
struct PageInfo* next = page_free_list;
page_free_list = page_free_list->pp_link;
next->pp_link = NULL;
if(alloc_flags & ALLOC_ZERO) {
/*
static inline void*
page2kva(struct PageInfo *pp)
{
return KADDR(page2pa(pp));
}
*/
//獲得下一個(gè)可用的地址的虛擬地址，然后設(shè)置一個(gè)PGSIZE大小的都為0
void* va = page2kva(next);
memset(va,'\0',PGSIZE);
}
//新分配的頁(yè)在pages
return next;
}
第五題 實(shí)現(xiàn)page free
這題就比較簡(jiǎn)單了抹蚀。如果前面都理解了剿牺，free一個(gè)page只需要將它放回到page_free_list當(dāng)中就行，還是使用我們熟悉的頭插法就行环壤。如果pp_ref > 0或者pp_link != null說明這個(gè)PageInfo要么是還在被使用牢贸，要么就是本來就在page_free_list當(dāng)中(因?yàn)橹挥性趐age_free_list中pp_link才會(huì)不為NULL)。被使用的是時(shí)候顯然不能放回到page_free_list當(dāng)中镐捧。如果本來就在page_free_list中潜索，就沒意義了還會(huì)出錯(cuò)。代碼實(shí)現(xiàn)如下:
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 > 0 || pp->pp_link) {
panic("This page is still inused or already in page free list, fail to free it ");
}
//頭插法
pp->pp_link = page_free_list;
page_free_list = pp;
}
所有的工作完成后懂酱，make一下竹习，然后在make qemu。正確了就會(huì)看到sucessed列牺。我下面的截圖是lab1,lab2,lab3都做完的結(jié)果整陌。實(shí)際上的應(yīng)該是輸出check_page_free_list() succeeded! 和check_page_alloc() succeeded ! 即可
