MIT 6.828 lab2

前言

这个lab主要是写内存管理相关的代码。实现操作系统必须满足三个要求multiplexing, isolation, and interaction 。翻译成中文就是复用,隔离和相互作用。这三个条件其实主要靠抽象完成。复用 比如IO读写,都对文件描述符进行处理,而不管底下是网络读写还是磁盘读写等。隔离抽象地址空间,每个进程拥有一个自己的地址空间,相互并不影响。相互作用也需要抽象的控制,防止一些恶意的软件。

lab2关注点在于如何实现地址空间。jos通过实现分页管理来实现。操作系统中所有程序接触的地址都是虚拟地址,然后硬件上真正需要的则是物理地址,所以中间则是使用MMU(memory management unit)来把虚拟地址翻译为物理地址。

连续的内存分配

早期操作系统都是直接操作物理地址,很明显,这样做有着致命的缺点。比如用户程序可以直接访问kernel地址,导致系统崩溃,多个用户程序程序直接相互影响。即使设立了保护机制,也就是通过一些flag来辨别是否可以访问,但还是会有问题。就是当两个进程同时载入内存时,会进行地址偏移,跳转到指令并不会是程序中原先的指令,此时需要进行重定位,就是扫描一遍程序,给程序中涉及到的地址加上偏移量。但是这种方法效率是很低的。需要为每个需要执行的程序进行扫描判定计算。

地址空间

所以这里我们提出了地址空间的概念。重点还是抽象。我门让每个进程处于独立的进程空间中。比如虽然两个进程都指向同一个虚拟地址,但是实际所指的物理地址是不同的。

基地寄存器和界限寄存器

其实就是动态重定位。把重定位的时间推迟了,之前的重定位一般发生在加载时,而现在推迟到访问内存时,并且减少了扫描查找的时间。通过两个寄存器来保存进程的起始地址和进程使用空间的长度。当程序访问内存时,自动加上偏移量,如果超出界限,则产生错误。但这种方法还是不够快,需要进行计算,比较可以进行的很快,但计算不行。进行动态重定位之后地址称为线性地址

非连续的内存分配

之前的内存分配,都是连续的,但是其实这种分法的内存利用效率很低。会产生很多的内碎片外碎片,当你找不到足够大内存块时,还需要对内存进行整理。然后就有人提出了不连续的内存分配。把内存切开,分块保存。那么这时候,切多大的块又是一个问题。进而产生了两种方法分段分页

分段

分段的概念就是说,我们把进程的地址空间分成堆、栈、符号表、代码段等等。分成几个比较大的块,这几个块在物理内存中是可以不连续的。每个进程都有段表段表是由操作系统建立的。虚拟地址分成两块,段号偏移量,通过段号索引段表得到基址再加上偏移量,则为物理地址。段是可以动态生长的。

虚拟内存

虽然上述的基地寄存器界限寄存器可以建立独立地址空间的抽象。但是依然有问题。现在软件越做越大,早就无法装下所有的进程了。当整个进程无法全部装入进程的时候,提出了一种更加灵活的方式,虚拟内存。主要思想是把进程的地址空间切成块,这些块无需全部都装到内存里,而是把一部分必要的装到内存中,而另外一些不是那么重要的装到硬盘中,直到进程需要的时候才调出来使用,大大节省内存空间。其实也是一种抽象,把磁盘的容量抽象成内存。我们用分页来实现虚拟内存

分页

分页意味当把进程切块的时候切的比分段要小,每一块则称为。好现在我们有两个空间。虚拟地址空间以及物理地址空间。我们需要在这中间搭建一个桥梁,把虚拟地址翻译成物理地址,即MMUMMU则是通过页表来索引得到地址的。

虚拟地址空间会比物理地址大的多,因为很多页并未分配到物理内存中,而是存在磁盘中,当需要那一页时才会调出来,替换最近使用次数最少的那一页。就好像Cache一样。可以把内存抽象成磁盘的一层Cache,以为读内存的速度比读硬盘的速度快的多。

页表

那么具体是如何翻译的?用页表(page table)的方式来索引。有点像Hash table。可以把页表看成一个大的数组。每个进程都有一个页表页表的每一项叫做页表项( page table entries)页表项包含20位physical page number (PPN) 和剩下12个标志位来用作权限控制。下面是具体翻译的过程

  1. 得到虚拟地址
  2. 截取虚拟地址的前20位作为索引
  3. 通过索引从页表中获取页表项
  4. 页表项的前20位(PPN)加上虚拟地址的后12位(offset),则得到完整的物理地址。

实际情况中,我们不可能只用一个表来存储所有的地址。因为页表中的大部分页表项都用不到,因为还未分配。所以采用多级页表的方式来存储。具体看下图,主要方式和上面相同,只不过多加了一层罢了。这样的话,如果页目录中某一项未分配的话,则不需要后面的页表了,大大节省空间。

以上就是分页实现方式。分页十分简洁明了的实现了操作系统的需求。比如说两个虚拟地址可以指向同一个物理地址,这就是复用和交互。还可以通过标志位来阻止进程访问别的进程,这就是隔离

lab2

前面是lab2所需的所有知识,当然我梳理的不是很细。非常具体的东西,大家还是看书为好。

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()

boot_alloc()在物理内存上为页目录以及页表的数据结构分配数据,只在mem_init()调用。真正的页面分配是用page_alloc()的。boot_alloc()是从kernel装载的结束位置开始分配的。代码如下。

1
2
3
4
5
6
7
8
result = nextfree;
if(n > 0){
if (PADDR(nextfree) + n > (npages + 1) * PGSIZE) {
panic("out of memory\n");
}
nextfree = ROUNDUP((char *)nextfree + n, PGSIZE);
}
return result;

写这个lab这个之前一定要弄清楚原理,不要什么都不懂就开始写了,这样只会无从下手。其实要写的代码都不难。

mem_init() 望名知意,初始化内存。第一部分主要是分配页目录,以及追踪页表的数据结构。

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

page_init() 按照注释的要求初始化pagespage_free_list,这里比较要注意的是,这个链表是反向的。pp_link指向的是前一个page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void page_init(void) {
size_t i, io_page_i, ext_page_i, free_top;
for (i = 0; i < npages; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
pages[0].pp_link = NULL;
pages[1].pp_link = NULL;
io_page_i = PGNUM(IOPHYSMEM);
ext_page_i = PGNUM(EXTPHYSMEM);
free_top = PGNUM(PADDR(boot_alloc(0)));
pages[ext_page_i].pp_link = pages[io_page_i].pp_link;
for(i = io_page_i;i < ext_page_i;i++)
pages[i].pp_link = NULL;
pages[free_top].pp_link = pages[ext_page_i].pp_link;
for (i = ext_page_i; i < free_top; i++)
pages[i].pp_link = NULL;
}

page_alloc() 分配页,这个也很简单。都是链表的基础操作。照着注释做就行了。

1
2
3
4
5
6
7
8
9
10
11
12
struct PageInfo * page_alloc(int alloc_flags) {
struct PageInfo *p = page_free_list;
if(p){
page_free_list = p->pp_link;
p->pp_link = NULL;
if(alloc_flags & ALLOC_ZERO){
memset(page2kva(p), 0, PGSIZE);
}
}
else return NULL;
return p;
}

page_free() 释放页,把它添加回free_list中。

1
2
3
4
5
6
7
void page_free(struct PageInfo *pp) {
if(pp->pp_ref != 0 || pp->pp_link!=NULL){
panic("pp->pp_ref is nonzero or pp->pp_link is not NULL\n");
}
pp->pp_link = page_free_list;
page_free_list = pp;
}

Exercise 4

Exercise 4. In the file kern/pmap.c, you must implement code for the following functions.

pgdir_walk()
boot_map_region()
page_lookup()
page_remove()
page_insert()

pgdir_walk 是个关键函数。这里需要你实现虚拟地址翻译到物理地址的过程,先从页目录中拿到页表的地址,然后再根据页表的索引获得页表项。这里是返回指向页表项的地址。注意这里返回的要是虚拟地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pte_t * pgdir_walk(pde_t *pgdir, const void *va, int create) {
int pdr_i = PDX(va);
pde_t *pde = &pgdir[pdr_i];
pte_t *pgt;
if(!(*pde & PTE_P)){
if(!create)
return NULL;
struct PageInfo *page = page_alloc(ALLOC_ZERO);
if(page == NULL) return NULL;
*pde = page2pa(page) | PTE_P | PTE_U | PTE_W;
page->pp_ref ++;
}
pgt = KADDR(PTE_ADDR(*pde));
return &pgt[PTX(va)];
}

boot_map_region这个函数无非就是映射的过程了,并设置权限。

1
2
3
4
5
6
7
8
9
static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm) {
int i;
for(i = 0; i < (size / PGSIZE); i++, va += PGSIZE, pa+=PGSIZE){
pte_t* pte = pgdir_walk(pgdir,(const void *) va, 1);
if(pte!=NULL){
*pte = pa|perm|PTE_P;
}
}
}

page_lookup 查找虚拟地址所对应的页

1
2
3
4
5
6
7
8
9
10
struct PageInfo * page_lookup(pde_t *pgdir, void *va, pte_t **pte_store) {
pte_t *pte = pgdir_walk(pgdir, va, 0);
if(pte == NULL)
return NULL;
else{
if(pte_store!=NULL)
*pte_store = pte;
return pa2page(PTE_ADDR(*pte));
}
}

page_remove 删除对页的分配。TLB页表之上又加了一层cache,所以这里也要删除记录

1
2
3
4
5
6
7
8
9
void page_remove(pde_t *pgdir, void *va) {
pte_t *pte;
struct PageInfo *pp = page_lookup(pgdir, va, &pte);
if(pp!=NULL){
page_decref(pp);
*pte = 0;
tlb_invalidate(pgdir, va);
}
}

page_insert分配页,若页表中已有数据,则需要删除。

1
2
3
4
5
6
7
8
9
10
11
12
int page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm) {
pte_t *pte = pgdir_walk(pgdir, va, 1);
if(pte){
pp->pp_ref ++;
if(PTE_ADDR(*pte))
page_remove(pgdir, va);
*pte = page2pa(pp) | perm |PTE_P;
tlb_invalidate(pgdir, va);
return 0;
}
return -E_NO_MEM;
}

Exercise 5

不保证答案的正确性,纯粹是自己的理解

Fill in the missing code in mem_init() after the call to check_page().

这个比较简单,按照注释说的来就行。用之前的boot_map_region来建立虚拟地址到物理地址的映射。

1
2
3
boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U);
boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);
boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W);

What entries (rows) in the page directory have been filled in at this point? What addresses do they map and where do they point? In other words, fill out this table as much as possible:

Entry Base Virtual Address Points to (logically):
1023 0xFFC00000 phys memory
. ? ?
960 0xF0000000 phys memory
959 0xEFC00000 Kernel Stack
958 0xEF800000 Memory-mapped I/O
957 0xEF400000 page table
956 0xEF000000 page structures
. ? ?
0 0x00000000 [see next question]

We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel’s memory? What specific mechanisms protect the kernel memory?

页目录项以及页表项,都有保留相应的标志位来确定此地址的权限。

What is the maximum amount of physical memory that this operating system can support? Why?

每个PageInfo 对应一个物理页也就是2^12(4096)字节。根据上面的映射,我们把所有pages放到到UPAGES之上,大小为PTSIZE。那么最大的可以支持的物理内存为(PTSIZE/sizeof(PageInfo))*4096

How much space overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this overhead broken down?

页目录4M,页表4M,PageInfo 4M ,总共12M。注意这里虽然页目录PageInfo都不到4M,但操作系统还是预留了这么多。

Revisit the page table setup in kern/entry.S and kern/entrypgdir.c. Immediately after we turn on paging, EIP is still a low number (a little over 1MB). At what point do we transition to running at an EIP above KERNBASE? What makes it possible for us to continue executing at a low EIP between when we enable paging and when we begin running at an EIP above KERNBASE? Why is this transition necessary?

1
2
mov $relocated, %eax
jmp *%eax

我汇编不熟。不太明白为什么要这么做。至于为什么能继续在低地址执行,是因为有映射到低地址。

为何是必须的?我也没弄清楚。照网上的答案是说,kernel需要获得更多的空间。

Reference

《现代操作系统》
清华大学操作系统课