0%

【OS】mit6.828 Lab2

停了好久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=0limit=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.hpmap.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_walkpage_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_walkpage_lookup是作为辅助函数使用的,page_insertpage_remove在内存初始化结束后的内存管理中使用,而boot_map_region在后续的内存初始化中使用。

Exercise 4Exercise 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