MIT6.828 | Lab 2: Memory Management - Part 2: Virtual Memory

1
2
3
4

	mystery_t x;
	char* value = return_a_pointer();
	*value = 10;
	x = (mystery_t) value;

1
2
3
4
5

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

 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
45
46
47
48
49
50

// 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.
//
// The relevant page table page might not exist yet.
// If this is true, and create == false, then pgdir_walk returns NULL.
// Otherwise, pgdir_walk allocates a new page table page with page_alloc.
//    - If the allocation fails, pgdir_walk returns NULL.
//    - Otherwise, the new page's reference count is incremented,
//	the page is cleared,
//	and pgdir_walk returns a pointer into the new page table page.
//
// Hint 1: you can turn a PageInfo * into the physical address of the
// page it refers to with page2pa() from kern/pmap.h.
//
// Hint 2: the x86 MMU checks permission bits in both the page directory
// and the page table, so it's safe to leave permissions in the page
// directory more permissive than strictly necessary.
//
// Hint 3: look at inc/mmu.h for useful macros that manipulate page
// table and page directory entries.
//
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
	// PDX: page directory index from linear address
	uint32_t pd_idx = PDX(va);
	// PTE_P: Present bit
	if (~(pgdir[pd_idx] & PTE_P)) {
		// The relevant page table page is not exist
		if (~create) {
			return NULL;
		}
		// Allocates a new page table page
		struct PageInfo *pg = page_alloc(ALLOC_ZERO);
		if (!pg) return NULL; // the allocation fails
		// Clear the new page
		// page2kva: physical -> virtual address
		memset(page2kva(pg), 0, PGSIZE);
		// Update the reference counting manually
		pg->pp_ref++;
		// page2pa(pg) | PTE_P | PTE_U | PTE_W;	
		pgdir[pd_idx] = page2pa(pg) | PTE_P | PTE_U | PTE_W;
	}
	// PTX: page table index from linear address
	uint32_t pt_idx = PTX(va);
	// KADDR: physical address -> virtual address
	pte_t *p = KADDR(PTE_ADDR(pgdir[pd_idx])) + pt_idx;
	return p;
}

 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

//
// 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.
//
// This function is only intended to set up the ``static'' mappings
// above UTOP. As such, it should *not* change the pp_ref field on the
// mapped pages.
//
// Hint: the TA solution uses pgdir_walk
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
	// Fill this function in
	pte_t *pt;
	uint32_t offset = 0;
	while (offset < size) {
		// Pointer to the page table entry (PTE) for linear address 'va'
		pt = pgdir_walk(pgdir, (void *)va, 1);
		// Use permission bits perm|PTE_P for the entries.
		*pt = pa | perm | PTE_P;
		// va and pa are both page-aligned
		pa += PGSIZE;
		va += PGSIZE;
		// Size is a multiple of PGSIZE
		offset += PGSIZE;
	}
}

 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

//
// 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.
//
// Return NULL if there is no page mapped at va.
//
// Hint: the TA solution uses pgdir_walk and pa2page.
//
struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
	// Fill this function in
	// Address to the page table entry (PTE) for linear address 'va'
	pte_t *pte = pgdir_walk(pgdir, va, 0);
	// used by page_remove
	if (pte_store != 0) {
		// Store in it the address of the pte for this page
		*pte_store = pte;
	}
	// check if there is any page mapped at va
	if (pte != NULL && (*pte & PTE_P)) {
		// PTE_ADDR: address in page table or page directory entry
		return pa2page(PTE_ADDR(*pte));
	}
	return NULL;
}

 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

//
// Unmaps the physical page at virtual address 'va'.
// If there is no physical page at that address, silently does nothing.
//
// Details:
//   - The ref count on the physical page should decrement.
//   - The physical page should be freed if the refcount reaches 0.
//   - The pg table entry corresponding to 'va' should be set to 0.
//     (if such a PTE exists)
//   - The TLB must be invalidated if you remove an entry from
//     the page table.
//
// Hint: The TA solution is implemented using page_lookup,
// 	tlb_invalidate, and page_decref.
//
void
page_remove(pde_t *pgdir, void *va)
{
	// Fill this function in
	pte_t *pte;
	// the page mapped at virtual address 'va'
	struct PageInfo *page = page_lookup(pgdir, va, &pte);
	if (page) {
		// decrese the ref and auto free physical page if ref == 0
		page_decref(page);
		// set the pg table entry corresponding to 'va' to 0
		*pte = 0;
		// Invalidate a TLB entry
		tlb_invalidate(pgdir, va);
	}
}

 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
45
46
47
48
49
50
51
52
53
54
55
56

//
// 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'.
//
// Requirements
//   - If there is already a page mapped at 'va', it should be page_remove()d.
//   - If necessary, on demand, a page table should be allocated and inserted
//     into 'pgdir'.
//   - pp->pp_ref should be incremented if the insertion succeeds.
//   - The TLB must be invalidated if a page was formerly present at 'va'.
//
// Corner-case hint: Make sure to consider what happens when the same
// pp is re-inserted at the same virtual address in the same pgdir.
// However, try not to distinguish this case in your code, as this
// frequently leads to subtle bugs; there's an elegant way to handle
// everything in one code path.
//
// RETURNS:
//   0 on success
//   -E_NO_MEM, if page table couldn't be allocated
//
// Hint: The TA solution is implemented using pgdir_walk, page_remove,
// and page2pa.
//
int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
	// Fill this function in
	// Address of the page table entry (PTE) for linear address 'va'
	// create on demond, a page table should be allocated and inserted into 'pgdir'.
	pte_t *pte = pgdir_walk(pgdir, va, 1);	
	if (!pte) {	// page table couldn't be allocated
		return -E_NO_MEM;
	}
	if (*pte & PTE_P) {	// the *pte is validate
		// PTE_ADDR: Address in page table or page directory entry
		// page2pa: physical -> virtual
		if (PTE_ADDR(*pte) == page2pa(pp)) {
			// The TLB must be invalidated if a page was formerly present at 'va'
			tlb_invalidate(pgdir, va);
			// do not use page_decref(), as physical may be free
			pp->pp_ref--;	
		} else {
			// already a page mapped at 'va', it should be page_remove()
			page_remove(pgdir, va);
		}
	}
	*pte = page2pa(pp) | perm | PTE_P;
	// pp->pp_ref should be incremented if the insertion succeeds.
	pp->pp_ref++;
	// The permissions (the low 12 bits) of the page table entry should be set to 'perm|PTE_P'.
	// PDX: page directory index from linear address
	*pte = page2pa(pp) | perm | PTE_P;
	return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

qemu-system-i386 -nographic -drive file=obj/kern/kernel.img,index=0,media=disk,format=raw -serial mon:stdio -gdb 
tcp::26000 -D qemu.log
6828 decimal is  octal! 
Physical memory: 131072K available, base = 640K, extended = 130432K
boot_alloc memory at <f011a000>
Next free memory at <f011b000>
boot_alloc memory at <f011b000>
Next free memory at <f015b000> 
kern end page:347
check_page_free_list() succeeded!
check_page_alloc() succeeded! 
check_page() succeeded!
check_kern_pgdir() succeeded! 
check_page_free_list() succeeded! 
check_page_installed_pgdir() succeeded!
Welcome to the JOS kernel monitor!
Type 'help' for a list of commands.
K>