Lab2: Memory Management
前置芝士：
Intel 80386 Reference Manual
第五章内存管理和第六章保护机制是在做本次lab前需要详细了解的。
Part 1: Physical Page Management
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()
check_page_free_list() and check_page_alloc() test your physical page allocator. You should boot JOS and see whether check_page_alloc() reports success. Fix your code so that it passes. You may find it helpful to add your own assert()s to verify that your assumptions are correct.
在kern/pmap.c中我们可以找到mem_init函数。这个函数被i386_init调用，用来完成内存管理的初始化。首先来看我们需要完成的第一个功能，实现boot_alloc。
在mem_init中，首先调用了一个函数i386_detect_memory来查看机器的内存情况。然后通过调用boot_alloc来创建了一个页目录表。
……
// create initial page directory.
kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
memset(kern_pgdir, 0, PGSIZE);
……
boot_alloc要实现的功能也很简单：
// If n>0, allocates enough pages of contiguous physical memory to hold 'n'
// bytes. Doesn't initialize the memory. Returns a kernel virtual address.
//
// If n==0, returns the address of the next free page without allocating
// anything.
在提供的代码中已经找到了内存中下一个空闲的位置，且地址也已经对齐。我们只需要更新返回值result并找到分配好需要的空间后内存中下一个空闲的地址，并将地址对齐。
result = nextfree;
if (n > 0) {
nextfree = ROUNDUP(nextfree + n, PGSIZE);
}
return result;
接下来继续去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.
分配容纳npages个struct PageInfo的空间，将首地址存储在pages中并初始化所有数据为0。
直接调用刚才实现的boot_alloc：
pages = (struct PageInfo *)boot_alloc(npages * sizeof(struct PageInfo));
memset(pages, 0, npages * sizeof(struct PageInfo));
struct PageInfo是一个描述页的结构，它的定义在memlayout.h中：
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;
};
pp_link指向下一个空闲页，pp_ref说明当前结构对应物理页存在多少引用，当引用为0时，就说明该页空闲。
接下来实现page_init。需要完成的功能有以下几点：
- Mark physical page 0 as in use. This way we preserve the real-mode IDT and BIOS structures in case we ever need them. (Currently we don't, but...)
- The rest of base memory, [PGSIZE, npages_basemem * PGSIZE) is free.
- Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must never be allocated.
- Then extended memory [EXTPHYSMEM, ...). Some of it is in use, some is free. Where is the kernel in physical memory? Which pages are already in use for page tables and other data structures?
首先将物理页0标记为正在使用很简单，直接将pp_ref设置为1，pp_link设置为NULL即可。
接下来是空闲的npages_basemem页，我们将pp_ref设置为1，并让下一个页表项的pp_link指向自己。接下来是IO hole，我们需要知道这里占用了多少页，从lab1我们知道，IO hole指的是从0x000A0000~0x00100000这段地址空间，除以每页的大小即可知道占用的页数。在memlayout.h中也有对应描述：
// At IOPHYSMEM (640K) there is a 384K hole for I/O. From the kernel,
// IOPHYSMEM can be addressed at KERNBASE + IOPHYSMEM. The hole ends
// at physical address EXTPHYSMEM.
#define IOPHYSMEM 0x0A0000
#define EXTPHYSMEM 0x100000
接下来是extended memory，这部分内存有一些是正在使用的，我们需要计算出已经使用了多少，然后初始化剩下的内存对应的页表项。
在boot_alloc中我们可以看到这么一段话：
// 'end' is a magic symbol automatically generated by the linker,
// which points to the end of the kernel's bss segment:
// the first virtual address that the linker did *not* assign
// to any kernel code or global variables.
end指向内核bss段的末尾，是第一个没有被连接器分配给任何内核代码和全局变量的虚拟地址。我们在之前已经调用过一次boot_alloc，为页目录分配内存，已经更新了nextfree。此时我们再次调用该函数，但分配0字节，返回地址应该就是第一个可供分配的地址。
pages[0].pp_ref = 1;
pages[0].pp_link = page_free_list = NULL;
int num_ioalloc = (EXTPHYSMEM - IOPHYSMEM)/PGSIZE;
int num_extalloc = (PADDR(boot_alloc(0)) - EXTPHYSMEM)/PGSIZE;
size_t i;
for (i = 1; i < npages; i++) {
if (i < npages_basemem || i >= npages_basemem + num_extalloc + num_ioalloc){
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
else {
pages[i].pp_ref = 1;
pages[i].pp_link = NULL;
}
page_alloc和page_free根据注释应该能很快写出来：
struct PageInfo *
page_alloc(int alloc_flags)
{
// Fill this function in
struct PageInfo *result = page_free_list;
if(result != NULL) {
page_free_list = (struct PageInfo *)(result->pp_link);
result->pp_link = NULL;
if(alloc_flags & ALLOC_ZERO) memset(page2kva(result), 0, PGSIZE);
}
return result;
}
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_ref != 0 || pp->pp_link != NULL) {
panic("page_free failed\n");
}
else {
pp->pp_link = page_free_list;
page_free_list = pp;
}
}
完成后应该能看见这样的信息（当然之后就panic了）：
……
Physical memory: 131072K available, base = 640K, extended = 130432K
check_page_free_list() succeeded!
check_page_alloc() succeeded!
……
Part 2: Virtual Memory
page translation:
实现以下函数：
pgdir_walk()
boot_map_region()
page_lookup()
page_remove()
page_insert()
pgdir_walk:
// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
// a pointer to the page table entry (PTE) for linear address 'va'.
// This requires walking the two-level page table structure.
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
// Fill this function in
pde_t *result = NULL;
pde_t* pde = pgdir + PDX(va);
if (!(*pde & PTE_P)) {
if (create) {
struct PageInfo *pp = page_alloc(1);
if (pp) {
pp->pp_ref++;
*pde = (page2pa(pp)) | PTE_P | PTE_U | PTE_W;
result = (pte_t *)KADDR(PTE_ADDR(*pde)) + PTX(va);
}
}
}
else result = (pte_t *)KADDR(PTE_ADDR(*pde)) + PTX(va);
return result;
}
给定指向页目录起始的指针pgdir，返回一个与虚拟地址va对应的PTE项的指针。首先根据页目录中的偏移量DIR(PDX(va))找到对应的PDE，如果该项无效则根据create决定是否创建对应的PDE。找到PDE后，根据PDE中页表的基址和页表中的偏移量PAGE(PTX(va))找到对应的PTE，然后返回对应的指针。
boot_map_region：
// Map [va, va+size) of virtual address space to physical [pa, pa+size)
// in the page table rooted at pgdir. Size is a multiple of PGSIZE, and
// va and pa are both page-aligned.
// Use permission bits perm|PTE_P for the entries.
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
// Fill this function in
uint32_t i = 0;
for (i = 0; i < size; i += PGSIZE) {
pte_t *pte = pgdir_walk(pgdir, (void *)va, 1);
*pte = pa | perm | PTE_P;
va += PGSIZE;
pa += PGSIZE;
}
}
将虚拟地址空间[va, va + size)映射到物理地址空间[pa, pa + size)。直接调用pgdir_walk然后更新*pte即可。
page_lookup：
// Return the page mapped at virtual address 'va'.
// If pte_store is not zero, then we store in it the address
// of the pte for this page. This is used by page_remove and
// can be used to verify page permissions for syscall arguments,
// but should not be used by most callers.
struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
// Fill this function in
struct PageInfo *result = NULL;
pte_t *pte = pgdir_walk(pgdir, va, 0);
if (pte != NULL && (*pte) & PTE_P) {
result = pa2page(PTE_ADDR(*pte));
if (pte_store != NULL) *pte_store = pte;
}
return result;
}
返回虚拟地址va对应的PageInfo指针，先根据虚拟地址找到对应的PTE，然后判断该PTE是否有效。用PTE中该页的物理地址作为参数调用pa2page找到对应的PageInfo指针。
page_remove:
// Unmaps the physical page at virtual address 'va'.
// If there is no physical page at that address, silently does nothing.
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 != NULL) {
page_decref(pp);
*pte_store = 0;
tlb_invalidate(pgdir, va);
}
}
解除一个地址映射。先找到对应的pp，更新一下值即可，将缓存中该项的内容标记为无效。
page_insert：
// Map the physical page 'pp' at virtual address 'va'.
// The permissions (the low 12 bits) of the page table entry
// should be set to 'perm|PTE_P'.
int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
// Fill this function in
pte_t *pte = pgdir_walk(pgdir, va, 1);
if(pte != NULL) {
pp->pp_ref += 1;
if((*pte) & PTE_P) page_remove(pgdir, va);
*pte = page2pa(pp) | perm | PTE_P;
pgdir[PDX(va)] |= perm;
return 0;
}
return -E_NO_MEM;
}
将pp对应的物理页映射到虚拟地址va上。先找到该虚拟地址对应的PTE项。然后检测该PTE是否有效，如果有效说明该虚拟地址已经被映射到一个物理页上了，先删去该映射关系，再补充我们想要的映射。注意pp->pp_ref需要在page_remove调用之前增加。如果目前存在的映射关系就是我们想要的，且该物理页只存在这一个引用，那remove操作会将该物理页放入空闲列表中，然后我们又增加引用数，这会导致一些错误。
Part 3: Kernel Address Space
* Virtual memory map: Permissions
* kernel/user
*
* 4 Gig --------> +------------------------------+
* | | RW/--
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* : . :
* : . :
* : . :
* |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
* | | RW/--
* | Remapped Physical Memory | RW/--
* | | RW/--
* KERNBASE, ----> +------------------------------+ 0xf0000000 --+
* KSTACKTOP | CPU0's Kernel Stack | RW/-- KSTKSIZE |
* | - - - - - - - - - - - - - - -| |
* | Invalid Memory (*) | --/-- KSTKGAP |
* +------------------------------+ |
* | CPU1's Kernel Stack | RW/-- KSTKSIZE |
* | - - - - - - - - - - - - - - -| PTSIZE
* | Invalid Memory (*) | --/-- KSTKGAP |
* +------------------------------+ |
* : . : |
* : . : |
* MMIOLIM ------> +------------------------------+ 0xefc00000 --+
* | Memory-mapped I/O | RW/-- PTSIZE
* ULIM, MMIOBASE --> +------------------------------+ 0xef800000
* | Cur. Page Table (User R-) | R-/R- PTSIZE
* UVPT ----> +------------------------------+ 0xef400000
* | RO PAGES | R-/R- PTSIZE
* UPAGES ----> +------------------------------+ 0xef000000
* | RO ENVS | R-/R- PTSIZE
* UTOP,UENVS ------> +------------------------------+ 0xeec00000
* UXSTACKTOP -/ | User Exception Stack | RW/RW PGSIZE
* +------------------------------+ 0xeebff000
* | Empty Memory (*) | --/-- PGSIZE
* USTACKTOP ---> +------------------------------+ 0xeebfe000
* | Normal User Stack | RW/RW PGSIZE
* +------------------------------+ 0xeebfd000
* | |
* | |
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* . .
* . .
* . .
* |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
* | Program Data & Heap |
* UTEXT --------> +------------------------------+ 0x00800000
* PFTEMP -------> | Empty Memory (*) | PTSIZE
* | |
* UTEMP --------> +------------------------------+ 0x00400000 --+
* | Empty Memory (*) | |
* | - - - - - - - - - - - - - - -| |
* | User STAB Data (optional) | PTSIZE
* USTABDATA ----> +------------------------------+ 0x00200000 |
* | Empty Memory (*) | |
* 0 ------------> +------------------------------+ --+
*
* (*) Note: The kernel ensures that "Invalid Memory" is *never* mapped.
* "Empty Memory" is normally unmapped, but user programs may map pages
* there if desired. JOS user programs map pages temporarily at UTEMP.
实现三个区域的映射，直接调用刚刚实现的boot_map_region即可。
// 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
// boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
// 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, ~0 - KERNBASE, 0, PTE_W);
最后：
……
running JOS: (1.0s)
Physical page allocator: OK
Page management: OK
Kernel page directory: OK
Page management 2: OK
Score: 70/70