Lv的杂货铺

我们都是阴沟里的虫子，但总还是得有人仰望星空

0%

Lab 2: Memory management

发表于 更新于
MIT 6.828 Lab2

Part 1: Physical Page Management

该部分要求完成一个简单的物理页分配器，它通过维持一个链表持续追踪每一个可用的物理页。

值得注意的是，在init.c的i386_init函数中，首先声明了extern char edata[], end[]，其中edata和end是定义在链接脚本kernel.ld中的，分别代表了内核的ELF文件的.data段和.bss段的地址。而它们之间的部分就是.bss段，在被装载到内存后，其相应部分应当全部置0，也就是i386_init函数前两句所做的事情。在内核镜像.bss段之后便无内容了，所以，在pmap.c的boot_alloc函数的开头，将nextfree初始化为end之后的第一个4k对齐的地址，就是实际的内存中，空闲的地址的起点。

Exercise 1

exercise 1要求补全代码，除此之外基本上没有说明，需要自己阅读相关代码来明白程序的含义。

首先是boot_alloc()。该函数用于分配一些连续的物理页，需要的空间大小由参数给出。注意到，函数中一个重要的变量是static char *nextfree，它指向下一个可用的页。它在内核被装载到内存中的时候被初始化为0（static），然后在这个函数首次运行的时候被初始化为虚拟内存空间中紧接着内核之后的那个空闲地址（当然，它是4k对齐的）。同时，由于它是static类型的，每次函数运行之后，它的值被更新，然后在下次被调用，再次被更新，以此类推…

函数要求分配一些物理页，乍一看这个“分配”无从下手，因为现在既没有页表也没有什么别的帮助函数，但是回想一下，在lab1中，我们知道在进入内核入口点的时候已经加载了一个临时的页目录表entry_pgdir，它将0xf0000000 ~ 0xf0400000之间的地址直接映射到物理地址0x00000000 ~ 0x00400000，而现在next_free指向虚拟地址空间中内核后面的空闲地址，那么它指向的内容也会被直接映射到物理地址中（只要没超过0xf0400000）。那么，这个“分配”就只要返回一个虚拟地址就行了，映射的事情是不必管的。

boot_alloc()的注释中已经说明了，参数代表期望分配的字节数，但既然分配的粒度是以“页”为单位，那么就需要向上取整了，而如果空间不够了则要panic，当然这个“空间不够”也是指的是0xf0000000 ~ 0xf0400000之间的空闲页面被用尽了。另外，参数为0代表返回next_free的内容，不做分配。因此，函数需要补全的代码即为：

1
2
3
4
5
6
7
8
9
10
11
12
13
	// LAB 2: Your code here.
if(n==0)
	return nextfree;
	
result = nextfree;
uint32_t require = n / PGSIZE + (n % PGSIZE == 0 ? 0:1);
nextfree += require * PGSIZE;
if((uint32_t)nextfree >= 0xf0400000)
{
	panic("boot_alloc: Out of memory!\n");
}

return result;

接下来是mem_init()，要求只需要完成到调用check_page_free_list(1)之前到部分即可。

在mem_init()中，首先，调用i386_detect_memory()来探测物理内存的大小，然后才能着手建立页表。使用boot_alloc()分配了一个物理页给kern_pgdir来做页目录表，并把这个页初始化为0，接着插入一个表项:kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P，这个操作的意义在于，它提供了一个很方便的访问页表条目的方式：试想一下，如果想要访问第 n 个页的PTE，直观的做法是，查kern_pgdir，找到这个页的对应的页表的条目，这时问题就出现了，因为kern_pgdir中的条目保存的是物理地址，而现在虚拟内存建立起来以后，直接在程序中使用这个物理地址是不行的，而如果把上面这个表项插入后，就变得非常方便了。此时，使用((pte_t*)UVPT)[n] ，得到的正是第 n 个页的PTE。这在后面会很有用，因为，以后如果要判断用户程序对某个地址的内存访问是否合法的话，不仅要看相应的页的PDE的权限位是否满足，还要看PTE的权限位是否满足。只有二者同时满足了，访问才是合法的。

然后，就到了要求完成代码到地方，要求是分配一个含npages个元素的struct PageInfo数组pages，用于创建一个与每一个物理页的一一对应，初始化为0.这个还是很简单的，代码如下

1
2
3
4
// Your code goes here:

pages = (struct PageInfo*)boot_alloc(npages * sizeof(struct PageInfo));
memset(pages, 0, npages * sizeof(struct PageInfo));

至此，mem_init()需要补全的代码就没有了，接下来是page_init()，其功能是初始化上面创建的pages数组。struct PageInfo包含两个字段:pp_link和pp_ref。pp_link字段在当前页处于page_free_list链表中的时候才有效，它指向了下一个空闲页对应的struct PageInfo；pp_ref表明当前物理页被多少个虚拟页指向（回想一下，在虚拟内存中，可能出现多个虚拟地址对应了同一个物理页）。显然，只有在物理页对应的pp_ref为0的时候，它才是一个可用的空闲页。

函数要求将物理页0标记为使用状态，用于保留BIOS和实模式中断描述符表以及一些其他东西，然后将之后的到IO hole之间的页标记为空闲页，IO hole中的页将永远不能被使用，因此标记为使用。剩下的物理页中，将内核、kern_pgdir和pages所占的页面标记为使用，将剩下的所有其他页面标记为空闲，代码如下

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
size_t i;

pages[0].pp_ref=1;
// base memory
for (i = 1; i < npages_basemem; i++) {
	pages[i].pp_ref = 0;
	pages[i].pp_link = page_free_list;
	page_free_list = &pages[i];
}

// IO hole
for(;i < EXTPHYSMEM/PGSIZE; i++)
{
	pages[i].pp_ref = 1;
}
	
// kern & kern_pgdir & pages
for(;i < ((uint32_t)boot_alloc(0)&0x0ffffff)/PGSIZE; i++)
	pages[i].pp_ref = 1;

for(;i < npages; i++)
{
	pages[i].pp_ref = 0;
	pages[i].pp_link = page_free_list;
	page_free_list = &pages[i];
}

在上面的代码中，通过pp_link字段，所有空闲页对应的struct PageInfo被组织成了一个链表，头为page_free_list。page_free_list初始值为0，因为它是一个static类型的变量。值得一提的是，上面所提到的所有的非空闲页面不能被释放（释放掉了将麻烦了！）、被加入page_free_list，所以，这些页对应的pp_link字段事实上是无意义的，所以不必初始化。

接下来是page_alloc()，它的功能是分配一个物理页，返回这个页对应的struct PageInfo，从原理上来看非常简单，只需要从page_free_list拿出来一个并返回就行若page_free_list为空，代表没有空余页了，分配失败返回NULL。代码如下

1
2
3
4
5
6
7
8
9
10
11
    // Fill this function in
if(page_free_list == NULL)
	return NULL;
struct PageInfo* tmp = page_free_list;
page_free_list = page_free_list->pp_link;
tmp->pp_link = NULL;
if(alloc_flags & ALLOC_ZERO)
{
	memset((void*)page2kva(tmp), 0, PGSIZE);
}
return tmp;

最后是page_free()，它将一个页加入page_free_list。只有当当前页的pp_ref为0且pp_link为空的时候才能释放，代码如下

1
2
3
4
5
if(pp->pp_ref != 0 || pp->pp_link != NULL)
	panic("page_free error!\n");

pp->pp_link = page_free_list;
page_free_list = pp;

Part 2: Virtual Memory

Exercise 4

这一部分要求补全几个函数。

首先是pgdir_walk()。给定一个虚拟地址，该函数返回一个指向这个虚拟地址对应的页表表项的指针.如果这个地址对应的页表还没有被创建，那么首先分配一个页作为页表，把页表的物理地址加上一些权限控制字段，填入页目录表中对应的位置。另外，分配页的时候可能因为内存不足分配失败，此时返回空指针。同时，分配页成功后，这个页对应的pp_ref也应当增加1.

值得一提的是，返回的虚拟地址对应的页表表项的指针需要是一个虚拟地址，尽管乍一看应当是物理地址。返回的指针是被page_insert()、page_lookup()等函数使用的，用于朝那个“地方”写入值的（*ptr = XXXXX）。我们只需要保证向页目录表、页表中写入的内容是物理地址，而这个指针只是提供了“写”的途径。虽然完全可以返回物理地址，只要在后续的函数中将每个用到这个指针的地方先通过宏KADDR()转成虚拟地址，不过这完全是在自找麻烦…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    // Fill this function in
if(!pgdir[PDX(va)])
{
	if(create == false)
		return NULL;
	else
	{
		struct PageInfo* alloc = page_alloc(1);
		if(alloc == NULL)
			return NULL;

		pgdir[PDX(va)] = (uint32_t)page2pa(alloc)| PTE_U | PTE_P | PTE_W;
		alloc->pp_ref++;
		pte_t* tmp = &((pte_t *)page2pa(alloc))[PTX(va)];
		
		return KADDR((uint32_t)tmp);
	}
}
else
{
	return KADDR((uint32_t)(&((pte_t *)PTE_ADDR(pgdir[PDX(va)]))[PTX(va)]));
}

然后是boot_map_region()。给出一段物理地址和一段虚拟地址，它在这些地址间建立建立起映射。原理上讲还是非常简单的，只需要修改这些虚拟地址对应的页表项就行了。无需关心对应的页表是否建立起来，pgdir_walk()的实现保证了它返回的指针指向的页表项是有效的。因为是在一段连续的地址间建立映射，所以用一个循环就能完成。

1
2
3
4
5
6
7
8
	// Fill this function in
size_t pgnum = size / PGSIZE;
for(size_t i=0; i<pgnum; i++)
{
	*pgdir_walk(pgdir, (const void*)va,1) = pa | PTE_P | perm;
	pa += PGSIZE;
	va += PGSIZE;
}

然后是page_lookup()。给出一个虚拟地址，它查找页表返回虚拟地址对应的物理地址对应的struct PageInfo；如果这个虚拟地址未与任何物理地址建立映射，返回NULL（有两种情况：第一种情况是虚拟地址对应的页表还未建立，第二种情况是虚拟地址对应的页表建立起来了，但是对应的页表项还未建立）；如果函数的参数pte_t **pte_store不是一个空指针，它将对应的页表项的地址放入指针指向的地址中。

1
2
3
4
5
6
7
8
	// Fill this function in
pte_t * tmp = pgdir_walk(pgdir, va, 0);
if(!tmp || *tmp == 0)
	return NULL;
if(pte_store)
	*pte_store = tmp;
	
return pa2page(*tmp);

接着是page_remove()。它用于取消一个虚拟页与物理页之间的映射。如果参数给出的虚拟地址还未与物理地址建立映射，什么都不做，否则，清空对应的页表项，然后把TLB中的缓存清除，然后将物理页解除引用。代码如下

1
2
3
4
5
6
7
8
9
pte_t* pte_store;

struct PageInfo* tmp = page_lookup(pgdir, va, &pte_store);
if(tmp != NULL)
{
	*pte_store = 0;
	tlb_invalidate(pgdir, va);
	page_decref(tmp);
}

最后是page_insert()。给出一个物理页和虚拟地址，它将物理页插入虚拟地址对应的页表中。在这个过程中，如果虚拟地址对应的页表没有建立，而建立页表时因为物理内存不足而失败，返回一个错误代码，否则，首先查看页表项是否之前已经映射了一个其他的物理页，如果是，则先把这个物理页给移除，然后修改对应的页表项。

注意到函数注释中的提示，考虑相同的物理页被重复插入同一个虚拟地址的情况，提示中还说了不要尝试采用分支进行进行判断，否则将产生一些微妙的bug。考虑一下，如果发现页表项之前已经映射了一个物理页，那么我们需要将这个物理页使用page_remove()移除，而page_remove()会把pp_ref减1，如果减到了0，就调用page_free()释放掉，在上面的特殊情况中，如果按照正常的流程，那么这个物理页会因为page_remove()时pp_ref减到了0而首先被释放掉，然后被插入相同的页表项，显然会导致错误。那么调换一下顺序就行了。显然在插入页表项后，无论什么页，它对应的pp_ref都需要加1，那么我们就先把pp_ref加1，然后把之前的物理页移除，这时插入相同物理页的时候它的pp_ref会从2减到1，就不会被释放了。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Fill this function in
pte_t* tmp = pgdir_walk(pgdir, va, 1);
if(tmp)
{
	pp->pp_ref++;
	if(*tmp)
	{
		page_remove(pgdir, va);
		tlb_invalidate(pgdir, va);
	}
	*tmp = page2pa(pp) | perm | PTE_P;
	return 0;
	}
else
{
	return -E_NO_MEM;
}

Part 3: Kernel Address Space

Exercise 5

这部分要求补充mem_init()中调用check_page()之后的缺失部分。这部分要做的内容比较少，大体上来说就是将pages映射到虚拟地址UPAGES，将符号bootstack对应的物理页映射到虚拟地址空间中的内核栈部分[KSTACKTOP-PTSIZE, KSTACKTOP)，最后建立所有物理地址到虚拟地址空间KERNBASE之后的所有部分之间的映射。需要注意加上合适的保护字段。三个需要填代码的部分一共只有三行代码。

1
2
3
boot_map_region(kern_pgdir, UPAGES, npages * sizeof(struct PageInfo), PADDR(pages), PTE_U | PTE_P);
boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_P | PTE_W);
boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_P | PTE_W);

至此，lab2基本上就算完成了（除了challenge problem，不过这个不算在评分中）。使用make grade检查一下正确性

img

lab的完整代码在我的GitHub中可以找到

（完）