MIT6.828 | Lab 2: Memory Management - Part 1: Physical Page Management

Part 1: Physical Page Management

操作系统必须跟踪物理RAM的哪些部分是空闲的以及哪些是当前正在使用的。 JOS使用 page granularity 管理PC的物理内存以使用MMU映射和保护每个分配的内存。

Part1 目的是编写物理页面分配器,它通过 struct PageInfo 对象的链接列表跟踪哪些页面是空闲的(与xv6不同,它们没有嵌入到自由页面中),每个对应一个物理页面。 在编写剩余的虚拟内存实现之前,您需要编写物理页分配器,因为页表管理代码需要分配用于存储页表的物理内存。

Exercise 1. In the file kern/pmap.c, you must implement code for the following functions (probably in the order given).

`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. You may find it helpful to add your own assert()s to verify that your assumptions are correct.

boot_alloc()

上面的代码默认分配了 bss 片段,并将 nextfree 指向末尾,这里只需要再分配 n byte 即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
	// 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.
	 * ***************************************************************/
	cprintf("\n>>>Function <%s> called.<<<\n", __FUNCTION__);
	if (n != 0) {
		cprintf("boot_alloc memory at <%x>\n", nextfree);
		char *next = nextfree;
		// keep aligned to a mutiple of PGSIZE
		nextfree = ROUNDUP((char *) (nextfree+n), PGSIZE);
		cprintf("Next free memory at <%x>\n", nextfree);
		return next;
	}
	return nextfree;

mem_init()

根据注释,注释掉这行,保证后面可以正常执行

1
2
3
    // Remove this line when you're ready to test this function.
    // panic("mem_init: This function is not finished\n");

这里需要实现为 page 分配内存,根据提示调用 boot_alloc 保留空间并使用 memset 初始化即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
	//////////////////////////////////////////////////////////////////////
	// 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:
	pages = (struct PageInfo *)boot_alloc(sizeof(struct PageInfo) * npages);
	memset(pages, 0, sizeof(struct PageInfo) * npages);

page_init()

这里需要完成 page 的初始化,第一句说明了给出的代码使所有的物理页视为空闲状态,而实际上部分页表是需要保留的。

结合之前所学及注释,第一个 page 需要保留 (所以第一个for循环从1开始),之后直到第 npages_basemempage 都设置为 free

之后需要计算保留部分的末尾,可以简单地调用 boot_alloc(0) 得到(参考 boot_alloc中的magic end),并将此后的所有 page 设置为 free 即可。

设置 free 本质就是将这个 page 加入 page_free_list 链表中,(这里的实现是加到头节点)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
	// The example code here marks all physical pages as free.
	// However this is not truly the case.  What memory is free?
	//  1) Mark physical page 0 as in use.
	//     This way we preserve the real-mode IDT and BIOS structures
	//     in case we ever need them.  (Currently we don't, but...)
	//  2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
	//     is free.
	//  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
	//     never be allocated.
	//  4) Then extended memory [EXTPHYSMEM, ...).
	//     Some of it is in use, some is free. Where is the kernel
	//     in physical memory?  Which pages are already in use for
	//     page tables and other data structures?
	//
	// Change the code to reflect this.
	// NB: DO NOT actually touch the physical memory corresponding to
	// free pages!
	cprintf("\n>>> Function <%s> called <<<\n", __FUNCTION__);
	size_t i;
	for (i = 1; i < npages_basemem; i++) {
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;	 
		page_free_list = &pages[i];
	}
	char *nextfree = boot_alloc(0);
	size_t kern_end_page = PGNUM(PADDR(nextfree));
	cprintf("kern end page:%d\n", kern_end_page);
	// char *nextfree = (char *)(page_free_list + 1);  //boot_alloc(0);
    // size_t kern_end_page = PGNUM(PADDR(nextfree));
    // cprintf("kern end pages:%d\n", kern_end_page);
	for (i = kern_end_page; i < npages; i++) {
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}

page_alloc()

第三步已经了解到, 设置 free 本质就是将这个 page 加入 page_free_list 链表中,(这里的实现是加到头节点),因此分配当然就是删除了。

这里的判断根据注释就可以写出来,需要注意的是: memset 的第一个参数需要的是物理地址,而我们此时的是虚拟内存的地址,因此需要 使用page2kva() 将其映射到物理内存中

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
struct PageInfo *
page_alloc(int alloc_flags)
{
	if (page_free_list) {
	// has free memory
		struct PageInfo *ret = page_free_list;
		page_free_list = page_free_list->pp_link;
		ret->pp_link = NULL;
		if (alloc_flags & ALLOC_ZERO) 
			memset(page2kva(ret), 0, PGSIZE);
			// page2kna() takes physical address and returns virtual address
		return ret;
	} else {
	// out of free memory
		return NULL;	
	}
}

page_free()

简单的指针使用,将其添加到链表即可,这里的 Hint 内判断的 NULL 需要与 page_alloc 搭配食用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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 != NULL)
		_panic(__FILE__, 0, "page_free called with invalid PageInfo %x", pp);
	pp->pp_link = page_free_list;
	page_free_list = pp;
}

之后便可以编译测试了,结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
$ make qemu-nox 
+ cc kern/pmap.c 
+ ld obj/kern/kernel 
ld: warning: section `.bss' type changed to PROGBITS 
+ mk obj/kern/kernel.img 
*** 
*** Use Ctrl-a x to exit qemu 
*** 
qemu-system-i386 -nographic -drive file=obj/kern/kernel.img,index=0,media=disk,format=raw -serial mon:stdio -gdb 
tcp::26000 -D qemu.log
6828 decimal is  octal! 
Physical memory: 131072K available, base = 640K, extended = 130432K

>>>Function <boot_alloc> called.<<<
boot_alloc memory at <f0117000> 
Next free memory at <f0118000>

>>>Function <boot_alloc> called.<<<
boot_alloc memory at <f0118000> 
Next free memory at <f0158000>

>>> Function <page_init> called <<<

>>>Function <boot_alloc> called.<<< 
nextfree = 0xf0158000kern end page:344

>>> Function <check_page_free_list> called <<< 

>>>Function <boot_alloc> called.<<< 
check_page_free_list() succeeded!

>>> Function <check_page_alloc> called <<<
check_page_alloc() succeeded! 

>>> Function <check_page> called <<<
kernel panic at kern/pmap.c:726: assertion failed: page_insert(kern_pgdir, pp1, 0x0, PTE_W) < 0 
Welcome to the JOS kernel monitor!
Type 'help' for a list of commands. 
K> QEMU: Terminated 

可以看到 check_page_free_list()check_page_alloc() 函数均测试通过。