寒假在家终于有时间继续处理上学期没有做完的Labs，虽然效率偏低但总不是完全没有进展。
Lab2 - Memory Management主要包括了操作系统的内存管理，具体来说可以分为两部分。第一部分需要编写内核的物理内存分配器（Physical memory allocator），这会允许内核分配和释放内存。第二部分需要修改JOS的代码去实现一个虚拟内存，将虚拟地址映射到物理内存中。
2018年2月23日，完成了实验并写完了报告。

根据实验官网的提示，依次切换到分支lab2并且合并分支lab1，在合并的过程中，没有发生冲突。

user% git checkout -b lab2 origin/lab2
user% git merge lab1

实验二包括如下的新文件：

• inc/memlayout.h 描述了虚拟地址空间的结构
• kern/pmap.c 需要修改、添加代码以完成实验
• kern/pmap.h 定义了PageInfo结构 用来管理物理页状态
• kern/kclock.h
• kern/kclock.c 操作电池供电的时钟以及CMOS RAM硬件

第一部分 Physical Page Management - 物理页管理

操作系统必须追踪物理内存以得知哪些内存是空闲的，以及哪些内存是正在被使用的。JOS使用页粒度管理PC的物理内存以便利用MMU映射和保护每一片被分配的内存。

实验的第一部分需要完成一个物理页面分配器，该分配器维护了一个struct PageInfo的链表来追踪空闲的物理页面（也就是空闲链表），空闲链表已经在CSAPP中有所了解，这里不再赘述。

具体来说，需要完成kern/pmap.c中实现以下的函数：

• boot_alloc()
• mem_init() （完成直到check_page_free_list(1)为止）
• page_init()
• page_alloc()
• page_free()

完成后可以启动JOS去观察check_page_free_list()以及check_page_alloc()函数是否成功以检查编写的分配器的正确性。

第一部分的物理页面分配器总体来说难度不大，因为编写的分配器不像CSAPP中的malloc()一样，需要处理空闲内存的合并以及拆分，分配器只需要以物理页面为固定的粒度管理所有的内存即可。

在实际的Linux系统中，内核使用Buddy System快速地管理内存。

练习1的代码如下，仅供参考:

// In boot_alloc():
// 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.
if (n == 0) {
    // return the address of next free page
    return nextfree;
} else if (n > 0) {
    // round up size to a multiple of PGSIZE
    size_t size = ROUNDUP(n, PGSIZE);
    char * addr = nextfree;
    // update address of next free page(still multiple of PGSIZE)
    nextfree += size;
    // nextfree is a kernel virtual address, out out memory when it exceeds 4 MB
	if (nextfree >= (char *)KADDR(0x400000)) {
        panic("out of memory when booting!");
    }
    // return address
    return addr;
}

// In mem_init():
//////////////////////////////////////////////////////////////////////
// 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:
// get size of pages
uint32_t pages_size = sizeof(struct PageInfo) * npages;
// use boot_alloc to allocate memory
pages = (struct PageInfo *) boot_alloc(pages_size);
// initialization
memset(pages, 0, pages_size);

// In page_init():
size_t i;

// initialize from page 1 to page npages_basemem - 1
// set pp_ref to 0, set pp_link to last page_free_list
// and then update page_free_list
for(i = 1 ; i < npages_basemem ; i++) {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
}

// calculate next free page and initialize corresponding pages entry
// convert from kernel virtual address to physical address
size_t next_free_page = PADDR(boot_alloc(0)) / PGSIZE;
pages[next_free_page].pp_link = &pages[npages_basemem - 1];
page_free_list = &pages[next_free_page];

// initialize remaining pages entry
for (i = next_free_page + 1 ; i < npages ; i++) {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
}

// In page_alloc():
struct PageInfo *
page_alloc(int alloc_flags)
{
	// get first element in free list
	struct PageInfo * page_ptr = page_free_list;
	if (page_ptr != NULL) {
		// NOT out of memory
		// update free list
		page_free_list = page_free_list->pp_link;
		// get kernal virtual address from given page
		char * addr = page2kva(page_ptr);
		// set pp_link to NULL to allow double-free bugs check
		page_ptr->pp_link = NULL;
		// ALLOC_ZERO set, use memset to initialze physical page
		if (alloc_flags & ALLOC_ZERO) {
			memset(addr, 0, PGSIZE);
		}

// return page
		return page_ptr;
	}

return NULL;
}

// In page_free():
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.

//check pp_ref and pp_link
	if (pp->pp_ref != 0) {
		panic("page's reference count is non-zero!");
	}
	if (pp->pp_link != NULL) {
		panic("double free error when free page!");
	}

// return page to free list
	pp->pp_link = page_free_list;
	page_free_list = pp;
}

然后启动JOS，在终端观察到如下输出：

Physical memory: 131072K available, base = 640K, extended = 130432K
check_page_free_list() succeeded!
check_page_alloc() succeeded!

证明内存分配器工作正常。

第二部分 Virtual Memory - 虚拟内存

练习2：阅读Intel 80386 Reference Manual的第五章和第六章。主要阅读页翻译和页保护机制的部分。同时，也要对x86的分段机制有所了解。

虚拟地址、线性地址和物理地址

在x86中，虚拟地址由段选择子和段内偏移组成，通过段翻译机制，得到线性地址。线性地址经过页翻译机制，得到物理地址。物理地址就是实际的内存位置。

在实验1中，已经将线性地址0-4M映射到了虚拟地址0-4M和KERNBASE-KERNBASE+4M。在本实验中，要将物理内存的低256M映射到从KERNBASE开始的虚拟地址。此外，还要映射其他几个虚拟地址空间。（KERNBASE为0xf0000000）

练习3：在QEMU监视器中使用xp命令检查物理内存0x00100000处的字，在gdb中使用x命令检查虚拟内存0xf0100000处的字，观察结果：

(qemu) xp 0x00100000
0000000000100000: 0x1badb002
(gdb) x/x 0xf0100000
0xf0100000 <_start+4026531828>: 0x1badb002

可以得出，物理地址0x00100000和虚拟地址0xf0100000上具有相同的数据。

info pg和info mem的输出如下：

(qemu) info pg
VPN range     Entry         Flags        Physical page
[00000-003ff]  PDE[000]     ----A----P
  [00000-00000]  PTE[000]     --------WP 00000
  [00001-0009f]  PTE[001-09f] ---DA---WP 00001-0009f
  [000a0-000b7]  PTE[0a0-0b7] --------WP 000a0-000b7
  [000b8-000b8]  PTE[0b8]     ---DA---WP 000b8
  [000b9-000ff]  PTE[0b9-0ff] --------WP 000b9-000ff
  [00100-00103]  PTE[100-103] ----A---WP 00100-00103
  [00104-00119]  PTE[104-119] --------WP 00104-00119
  [0011a-0011a]  PTE[11a]     ---DA---WP 0011a
  [0011b-0011c]  PTE[11b-11c] --------WP 0011b-0011c
  [0011d-003ff]  PTE[11d-3ff] ---DA---WP 0011d-003ff
[f0000-f03ff]  PDE[3c0]     ----A---WP
  [f0000-f0000]  PTE[000]     --------WP 00000
  [f0001-f009f]  PTE[001-09f] ---DA---WP 00001-0009f
  [f00a0-f00b7]  PTE[0a0-0b7] --------WP 000a0-000b7
  [f00b8-f00b8]  PTE[0b8]     ---DA---WP 000b8
  [f00b9-f00ff]  PTE[0b9-0ff] --------WP 000b9-000ff
  [f0100-f0103]  PTE[100-103] ----A---WP 00100-00103
  [f0104-f0119]  PTE[104-119] --------WP 00104-00119
  [f011a-f011a]  PTE[11a]     ---DA---WP 0011a
  [f011b-f011c]  PTE[11b-11c] --------WP 0011b-0011c
  [f011d-f03ff]  PTE[11d-3ff] ---DA---WP 0011d-003ff

(qemu) info mem
  0000000000000000-0000000000400000 0000000000400000 -r-
  00000000f0000000-00000000f0400000 0000000000400000 -rw

在JOS内核中，uintptr_t代表虚拟地址，physaddr_t代表物理地址，它们都只是uint32_t的别名。因此，不能直接对其（int类型）解引用，需要先将其转换成指针类型。
对物理地址的解引用是错误的，因为MMU会将其当做虚拟地址，你将无法得到正确的内存内容。

问题1：
x的类型应当为uintptr_t，因为对其进行了解引用操作，所以x应当为虚拟地址。

有些时候，内核必须要处理物理地址，这也是要把0-4M映射到KERNBASE-KERNBASE+4M的理由。
为了能使内核读写物理地址，必须要加上KERNBASE，可以通过宏KADDR(pa)实现。
同理，有时候需要能通过虚拟地址找到物理地址，需要减去KERNBASE，可以通过宏PADDR(va)实现。

在未来的实验中很可能将同样的物理页映射到多个虚拟地址，你需要在struct PageInfo的pp_ref域中保持物理页被引用的次数，当引用计数归0，页面不再被使用，可以被释放。
总的来说，引用计数应当等于物理页面在UTOP之下出现的次数（UTOP之上的物理页面大多在启动时被内核分配并且永远不应当被释放，所以不需要对其进行引用计数）。
引用计数也会被用来追踪指向页目录页的指针数，以及页目录对页表页的引用数。

在使用page_alloc()时应当小心，返回页的pp_ref应当很快被递增，如被别的函数如(page_insert())递增，在某些情况下，调用page_insert()的函数必须手动增加引用计数。

需要编写管理页表的例程：插入和删除线性地址到物理地址的映射，当需要时创建页表等。

在练习4中遇到的问题总结如下：

• pgdir_walk在设置页表项时应当使用物理地址，在返回指针时应当返回虚拟地址。这是因为此时实际的二级页表还未被设置应用，且0-4M被映射为只读，而KERNBASE-KERNBASE+4M被映射为可读可写。需要使用给出的宏而不要自己加减
• 将PTE_P笔误成PTE_G
• 在page_insert中提前将引用计数pp_ref自增就可以避免边界情况的错误
• pgdir_walk中对于页目录的设置可以更宽松，否则可能会对之后的实验产生影响

练习4的代码如下，仅供参考：

// In pgdir_walk():
pte_t *pgdir_walk(pde_t *pgdir, const void *va, int create) {
    // get page directory index and page directory entry
    size_t pgdir_index = PDX(va);
    pde_t  pgdir_entry = pgdir[pgdir_index];
    // get page table index
    size_t pgtable_index = PTX(va);
    if ((pgdir_entry & PTE_P) == 1) {
        // page table page exists
        // get address of page table
        pte_t *pgtable = KADDR(PTE_ADDR(pgdir_entry));
        return (pte_t *)(pgtable + pgtable_index);
    } else {
        // page table page doesn't exist
        if (create == false) {
            // create flag is false, returns NULL
            return NULL;
        } else {
            // allocate a new page table page
            struct PageInfo *page = page_alloc(ALLOC_ZERO);
            if (page == NULL) {
                // allocation fails
                return NULL;
            } else {
                // increase physical page's reference count
                page->pp_ref++;
                // get physical address of physical page
                physaddr_t page_pa = page2pa(page);
                // insert page table into page directory
                pgdir[pgdir_index] = page_pa | PTE_W | PTE_U | PTE_P;
                // NB: returns KERNEL VIRTUAL ADDRESS here, for 0-4M is NOT
                // writable
                return (pte_t *)page2kva(page) + pgtable_index;
            }
        }
    }
    return NULL;
}

// In boot_map_region():
static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size,
                            physaddr_t pa, int perm) {
    // round up size
    size = ROUNDUP(size, PGSIZE);
    // get the number of pages to be mapped
    size_t page_num = PGNUM(size);

size_t i;
    for (i = 0; i < page_num; i++) {
        // iterate through to get each pte_t * through pgdir_walk given virtual
        // address
        pte_t *pgtable_entry_ptr =
            pgdir_walk(pgdir, (char *)(va + i * PGSIZE), true);
        // set pte_t according to physical address and permission flags
        *pgtable_entry_ptr = (pa + i * PGSIZE) | perm | PTE_P;
    }
}

// In page_lookup():
struct PageInfo *page_lookup(pde_t *pgdir, void *va, pte_t **pte_store) {
    // Fill this function in
    pte_t *pgtable_entry_ptr = pgdir_walk(pgdir, va, false);
    if (pgtable_entry_ptr && ((*pgtable_entry_ptr) & PTE_P) == 1) {
        if (pte_store != NULL) {
            // pte_store not zero, store the address of pte of the page in it
            *pte_store = pgtable_entry_ptr;
        }
        // converts from pa to page and returns
        physaddr_t pa = PTE_ADDR(*pgtable_entry_ptr);
        return pa2page(pa);
    } else {
        // no page mapped at va
        return NULL;
    }
    return NULL;
}

// In page_remove():
void page_remove(pde_t *pgdir, void *va) {
    // Fill this function in
    pte_t *pgtable_entry_ptr = NULL;
    // use page_lookup to get struct PageInfo
    struct PageInfo *page = page_lookup(pgdir, va, &pgtable_entry_ptr);
    if (page && pgtable_entry_ptr) {
        // if page mapped at va
        // decrease and try to free page
        page_decref(page);
        // set page table entry to 0
        *pgtable_entry_ptr = 0;
        // invalidate tlb
        tlb_invalidate(pgdir, va);
    }
}

// In page_insert():
int page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm) {
    // Fill this function in
    // try to get pointer to page table entry, created if needed
    pte_t *pgtable_entry_ptr = pgdir_walk(pgdir, va, true);
    if (!pgtable_entry_ptr) {
        // page table cannot be allocated
        return -E_NO_MEM;
    }

// increase reference ahead of insertion to process CORNER CASE
    pp->pp_ref++;

if (((*pgtable_entry_ptr) & PTE_P) != 0) {
        // exists page mapped at va
        // remove page and invalidate tlb
        page_remove(pgdir, va);
    }

// get physical address of page
    physaddr_t pa = page2pa(pp);
    // insert page into page table
    *pgtable_entry_ptr = pa | perm | PTE_P;

// update permission flags of corresponding page directory
    pgdir[PDX(va)] = pgdir[PDX(va)] | perm;

return 0;
}

第三部分 Kernel Address Space - 内核地址空间

JOS将32位的地址空间划为了两部分——用户环境（在Lab3中加载和运行）将控制低地址空间、而内核总是完全地控制高地址空间，由ULIM显式地划分地址空间。内核将占据约256M的地址空间。

尽管内核和用户内存位于同一地址空间，仍需要在x86的页表中使用权限位去保证用户代码仅能访问低地址空间。否则用户代码可能会覆写内核数据，导致故障。此外，用户代码还可能能从窃取其他用户、内核的私有数据。
在JOS中，用户环境将不具有ULIM以上任何内存的权限；只有内核可以读写这些内存。对于[UTOP, ULIM)，内核和用户都仅能读而不能写，该段内存主要用于向用户暴露某些内核的只读数据结构；最后，UTOP以下的地址空间由用户环境使用，由用户环境自行设置这些内存的权限。

练习5的代码如下，仅供参考：

//////////////////////////////////////////////////////////////////////
// Now we set up virtual memory

//////////////////////////////////////////////////////////////////////
// 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, pages_size, PADDR(pages), PTE_U | PTE_P);

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

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

Enrty Base Virtual Address Points to (logically) 1023 0xFFC00000 Physical Memory … ………. … 960 0xF0000000 First 4 MB on Physical Memory 959 0xEFC00000 Kernel Stack 957 0xEF400000 Kernel Page Directory 956 0xEF000000 Pages

问题3：
页保护机制实现了这一点，用户将不能访问未设置PTE_U的页（对于页目录和页表皆是如此）。

问题4：
注意到pages最多只有4MB，而一个struct PageInfo为8字节（对齐），所以实际上最多只有512K个项，总大小为2GB。

问题5：
使用了页表来管理虚拟内存，页表完整地映射了4GB的地址空间。使用pages追踪物理页面的情况，由于最初只映射了4MB，使得内存被限制在了2GB。

问题6：
执行转换的代码在entry.S中，和32位保护模式时相似：

mov	$relocated, %eax
jmp	*%eax

实际的跳转是通过一次jmp实现的，得以继续执行的原因是引导时不仅将0-4M映射到了KERNBASE-KERNBASE+4M的读写，同时也映射到了0-4M的只读。不这么做的话将出现无法处理的SIGTRAP信号而导致系统Triple Fault。
不通过转换就无法在高地址执行内核代码，将内核映射在高地址主要是为了完整地映射内核的约256M空间。

最终执行make grade，评分脚本的输出如下：

running JOS:
$ make qemu-nox-gdb
(1.3s)
  Physical page allocator: OK
  Page management: OK
  Kernel page directory: OK
  Page management 2: OK
Score: 70/70

至此，实验二结束。

第二个实验主要关注于操作系统的内存管理的基本概念，使用的也是简单的分配器，但是完整地描述了操作系统从引导直至内核初始化完毕是如何一步步设置页表，管理内存的。

由于已经在CSAPP（CMU 15213）中接触过相关的内存概念，本实验难度并不是很大。