mit6.828 Lab2

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 2.8k 阅读时长 ≈ 10 分钟

停了好久 Orz。。。本来 Lab2 在半个月前就完成了，结果 Part2 的某个地方出了问题，查了半天还没查出来错在哪里 QAQ。前两天趁着假期又重写了一遍，终于过了检查。另外考虑把实验报告都换成中文。

Lab2 的主要任务是完成 JOS 的基本内存管理。内存管理分为两个部分，一是对于物理内存的管理，二是虚拟内存到物理内存的映射。

Part1: Physical Page Management

为什么说是物理页管理呢？因为在 JOS 中，对物理内存是以 “页” 这个粒度进行管理的。操作系统要想做到对物理内存的管理和使用，就要了解每一块物理内存的使用情况：内存是否可用？如果不可用，那么它现在被映射了几次？JOS 通过如下结构体追踪每一块物理内存（每一个物理页）的使用情况

1
2
3
4
5
6
7
8
9
10
11
struct PageInfo {
	// Next page on the free list.
	struct PageInfo *pp_link;

	// pp_ref is the count of pointers (usually in page table entries)
	// to this page, for pages allocated using page_alloc.
	// Pages allocated at boot time using pmap.c's
	// boot_alloc do not have valid reference count fields.

	uint16_t pp_ref;
};

如果一个物理页是可用的，那么它会在 free list 中的某个位置，这个结构是通过 PageInfo.pp_link 维系的；而如果一个物理页不是可用的，那么它的 pp_link==NULL，且 pp_ref 非零。

当 JOS 需要分配物理页时，会从 free list 的头部取出空闲的物理页；而当 JOS 发现一个正在使用的物理页的 pp_ref 归零后，代表此时没有虚拟页映射到该物理页，即物理页状态变为空闲。JOS 会将其回收至 free list 中。

Exercise 1

1
2
3
4
5
6
完成与物理页管理相关的如下函数：
boot_alloc()
mem_init() (完成到 check_page_free_list(1) 处)
page_init()
page_alloc()
page_free()

P.S. 这些函数的注释都详细至极，对函数的完整功能、使用场景给出了清晰详细的描述，部分函数甚至给出了实现方面的 Hint 以及易错点。因此，写代码前阅读相关注释非常重要！

考虑到阅读体验和重点突出，我会酌情删除部分注释。

boot_alloc()

这玩意是个丐版的 page_alloc。说它丐版是因为由它分配的物理页 OS 并不能进行追踪管理，因此这些物理页必须被用于固定且特殊的用途（创建内核 page directory（不会翻译）以及所有可用物理页的结构体 PageInfo），这一点在函数的注释中也有说明：

This simple physical memory allocator is used only while JOS is setting up its virtual memory system. page_alloc() is the real allocator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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[];
		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;
	if (ROUNDUP((uint32_t)(nextfree + n), PGSIZE) < KERNBASE + npages * PGSIZE)
		nextfree = ROUNDUP((char *)(nextfree + n), PGSIZE);
	else 
		panic("mem_init: Out of memory!\n");
	return (void *)result;
}

mem_init()

这个函数是 Lab2 的真正主角，其他所有函数都在为它服务，从而完成 OS 启动时的内存初始化。让我们简单地看看它干了些什么事情（好像注释都说的很清楚了哈，我们需要做的只是添加两行代码）。

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
41
42
43
44
void
mem_init(void)
{
	uint32_t cr0;
	size_t n;

	// Find out how much memory the machine has (npages & npages_basemem).
	i386_detect_memory();

	//////////////////////////////////////////////////////////////////////
	// 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;

	//////////////////////////////////////////////////////////////////////
	// 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);

	//////////////////////////////////////////////////////////////////////
	// Now that we've allocated the initial kernel data structures, we set
	// up the list of free physical pages. Once we've done so, all further
	// memory management will go through the page_* functions. In
	// particular, we can now map memory using boot_map_region
	// or page_insert
	page_init();

	// Check correctness of implemented functions 
    // Part 2 content...
}

page_init()

在 mem_init() 中，我们已经为所有物理页创建了 PageInfo，接下来 page_init() 的任务就是初始化这些结构体，把应该放入 page_free_list 的页放进去，剩下的特殊用途保留页、使用 boot_alloc() 分配的页则跳过初始化。跳过初始化的页不受 page_alloc() 的管理，因为它们不会进入 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
void
page_init(void)
{
	// NB: DO NOT actually touch the physical memory corresponding to
	// free pages!

	// Set all physical page reference to 0
	size_t i;
	for (i = 0; i < npages; i++)
		pages[i].pp_ref = 0;
	// Mark physical page [1, npages_basemen - 1] as free
	for (i = 1; i < npages_basemem; i++) {
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}
	// Detect and mark free pages in extended memory
	// We assume that 'nextfree' in boot_alloc function is above EXTPHYSMEM
	// Well, still check it out first...
	if (PADDR(boot_alloc(0)) < EXTPHYSMEM)
		panic("page init error!\n");
	for (i = PTX(PADDR(boot_alloc(0))); i < npages; i++) {
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}
}

page_alloc()

真正的页分配器出现了。在收到页分配的请求后，它负责从 page_free_list 头部取出一个空闲页并将这个页返回给调用者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct PageInfo *
page_alloc(int alloc_flags)
{
	// Fill this function in
	if (page_free_list == NULL)
		return NULL;

	struct PageInfo *alloc_page = page_free_list;
	page_free_list = page_free_list->pp_link;
	alloc_page->pp_link = NULL;

	if(alloc_flags & ALLOC_ZERO)
		memset(page2kva(alloc_page), 0, PGSIZE);
	return alloc_page;
}

page_free()

操作系统对物理页进行管理，不仅负责物理页的分配，也要在没有人使用物理页时将其进行回收，重新放回 page_free_list 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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_link != NULL)
		panic("pp->pp_link is not NULL!\n");
	if(pp->pp_ref != 0)
		panic("pp->pp_ref is not 0!\n");

	pp->pp_link = page_free_list;
	page_free_list = pp;
}

总的来说，Exercise 1 没什么难度，照着注释就能顺利写下来。最终的结果是运行 make qemu 后得到

1
2
3
check_page_free_list() succeeded!
check_page_alloc() succeeded!
check_page() succeeded!

Part2: Virtual Memory

x86 在保护模式下的内存映射分为两个部分：segmentation translation 和 page translation（不会翻译 orz），具体过程放一张神图，我就不再赘述了

目前在 JOS 中，由于 boot.S 的设置，所有 segment 的 base=0，limit=0xffffffff，相当于分了个寂寞简化了 segmentation translation，使得 virtual address 在实际上等同于 logical address。因此在这部分实验中我们只需完成 page translation。

Exercise 2 是 Intel Reference Manual 的阅读，Exercise 3 是使用 GDB 检查虚拟地址和对应物理地址的一致性，这里不再进行描述。

Exercise 4

1
2
3
4
5
6
完成以下函数：
pgdir_walk()
boot_map_region()
page_lookup()
page_remove()
page_insert()

完成这部分实验时需要注意或者说需要小心的一点是对于地址的操纵。有时为了方便对地址值的直接操作，地址会被放入 uint32_t 中，而有时会被放入 uint32_t * 中，涉及到二者转换的地方容易发生错误。

mmu.h 和 pmap.h 中提供了很多有用的宏和函数，这在完成接下来的实验中是必要的。

此外，涉及到虚拟地址到物理地址的映射、页表项权限分配的问题，可以查阅 memlayout.h 中的 Virtual memory map 获得帮助。

pgdir_walk()

这个函数的名字非常形象，给定一个 page directory，给定一个 virtual address，要求返回 virtual address 对应的 page table entry（我们应当意识到我们操纵的是一个二级页表）。

这里需要注意的是页表项的权限分配。一是不要随意分配 PTE_W 权限，二是创建页表后不要忘记对 page directory entry 进行相应的权限分配（不然会给以后埋雷）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
	// Fill this function in
	pte_t *pgdir_e = pgdir + PDX(va), *pte = NULL;
	pte_t pt_exist = *pgdir_e & PTE_P;

	if (pt_exist) {
		pte = (pte_t *)KADDR(PTE_ADDR(*pgdir_e)) + PTX(va);
	} else if (create) {
		struct PageInfo *pt = page_alloc(ALLOC_ZERO);
		if (pt) {
			int perm = PTE_P;
			if (PDX(va) >= PDX(KERNBASE))
				perm |= PTE_W;
			*pgdir_e = page2pa(pt) | perm;
			pt->pp_ref += 1;
			pte = (pte_t *)page2kva(pt) + PTX(va);
		}
	}
	return pte;
}

boot_map_region()

该函数负责把一整段连续的虚拟地址映射到一整段连续的物理地址上，是通过 pgdir_walk 实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
	// Fill this function in
	size_t page_num = size / PGSIZE;
	pte_t *pte = NULL;
	for (size_t i = 0; i < page_num; i++) {
		pte = pgdir_walk(pgdir, (void *)(va + i * PGSIZE), true);
		if (pte) {
			*pte = (pa + i * PGSIZE) | perm | PTE_P;
		}
	}
}

page_lookup()

给定一个 page directory，给定一个 virtual address，如果 virtual address 映射到了某个 physical address，那么将它返回。该函数同样用 pgdir_walk 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
	// Fill this function in
	pte_t *pte = pgdir_walk(pgdir, va, false);
	if (pte == NULL || ((*pte & PTE_P) == 0))
		return NULL;

	struct PageInfo *pp = pa2page(PTE_ADDR(*pte));
	if (pte_store) 
		*pte_store = pte;
	return pp;
}

page_remove()

给定一个 page directory，给定一个 virtual address，如果 virtual address 映射到了某个 physical address，那么就取消这个映射。

1
2
3
4
5
6
7
8
9
10
11
12
void
page_remove(pde_t *pgdir, void *va)
{
	// Fill this function in
	pte_t *pte_store = NULL;
	struct PageInfo *pp = page_lookup(pgdir, va, &pte_store);
	if (pp) {
		*pte_store = 0;
		tlb_invalidate(pgdir, va);
		page_decref(pp);
	}
}

page_insert()

给定一个 page directory，给定一个 virtual address，给定一个 physical address，添加映射。这个函数通过 pgdir_walk 和 page_remove 实现。

需要注意这样一种情况：virtual address 已经映射到了一个 physical address，那么再次映射到相同的 physical address 时如何处理？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
	// Fill this function in
	pte_t *pte = pgdir_walk(pgdir, va, true);
	if (pte == NULL) 
		return -E_NO_MEM;
	
	pp->pp_ref += 1;
	page_remove(pgdir, va);
	*pte = PTE_ADDR(page2pa(pp)) | perm | PTE_P;
	pgdir[PDX(va)] = pgdir[PDX(va)] | perm;		// update perm
	return 0;
}

这几个函数中，pgdir_walk、page_lookup 是作为辅助函数使用的，page_insert、page_remove 在内存初始化结束后的内存管理中使用，而 boot_map_region 在后续的内存初始化中使用。

Exercise 4 较 Exercise 1 难度有所提升，需要注意的细节更多。最终的结果是运行 make qemu 后得到

1
check_kern_pgdir() succeeded!

Part 3: Kernel Address Space

在 memlayout.h 中可以发现虚拟内存被划分为两部分：用户地址空间和内核地址空间，用户无权访问内核地址空间。

  • UTOP 以下属于用户地址空间，用户拥有对这部分内存的读写权限。

  • [UTOP, ULIM) 间是两个地址空间的缓冲区，二者均只有对这一段地址的读权限。这一段地址的目的为向用户暴露必要的内核数据结构。

  • ULIM 以上完全属于内核地址空间，用户对这部分内存没有任何权限。

Exercise 5

1
完成mem_init()的剩下部分，以完成对 UTOP 上地址空间的设置
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
//////////////////////////////////////////////////////////////////////
// Map 'pages' read-only by the user at linear address UPAGES
// Permissions:
//    - the new image at UPAGES -- kernel R, user R
//      (ie. perm = PTE_U | PTE_P)
//    - pages itself -- kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U);

//////////////////////////////////////////////////////////////////////
// Use the physical memory that 'bootstack' refers to as the kernel
// stack.  The kernel stack grows down from virtual address KSTACKTOP.
// We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP)
// to be the kernel stack, but break this into two pieces:
//     * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
//     * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if
//       the kernel overflows its stack, it will fault rather than
//       overwrite memory.  Known as a "guard page".
//     Permissions: kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);

//////////////////////////////////////////////////////////////////////
// Map all of physical memory at KERNBASE.
// Ie.  the VA range [KERNBASE, 2^32) should map to
//      the PA range [0, 2^32 - KERNBASE)
// We might not have 2^32 - KERNBASE bytes of physical memory, but
// we just set up the mapping anyway.
// Permissions: kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W);

运行 make qemu 后得到

1
2
check_page_free_list() succeeded!
check_page_installed_pgdir() succeeded!

Question 和 Challenge 先鸽了，过几天再补上：P