作者 Ivan Chien
始于 2020/03/12
分类：OS
Tags: [ OS ]
6.828 Lab2 的笔记和实验报告

6.828 Lab 2 Memory Management 报告

正文

前言

在这个 lab 里, 我们将要为我们的操作系统加上内存管理(memory management)的代码.
内存管理有两个组件:
第一个是内核的物理内存分配器(physical memory allocator for kernel), 这个分配器以 4096 bytes 为字节操作, 也就是页(pages)宽. 我们的任务维护记录释放的物理页和分配的物理页, 以及进程之间的页共享数目的数据结构. 然后我们还需要编写分配释放内存的流程.
第二个是虚拟内存(virtual memory), 将 kernel 和用户程序使用的物理内存地址映射到虚拟地址. The x86 hardware’s memory management unit(MMU) 指令使用内存时时进行映射, 此时会用到一些页表(a set of page tables). 我们的任务是按照要求修改 JOS 去完成 MMU 页表的部署.

Getting started

先要把 lab2 的分支拉一下, 然后把 lab1 的 commit 合过来.

$ git pull
Already up-to-date.
$ git checkout -b lab2 origin/lab2
Branch lab2 set up to track remote branch lab2 from origin.
Switched to a new branch 'lab2'
$ git merge lab1
Merge made by the 'recursive' strategy.
 kern/console.c |  2 +-
 kern/kdebug.c  |  8 ++++++--
 kern/monitor.c | 22 +++++++++++++++++++++-
 lib/printfmt.c |  7 +++----
 4 files changed, 31 insertions(+), 8 deletions(-)

最后在 git branch 确认一下分支, 这样就算是做完了.

lab2 新加入了 5 个源文件:

inc/memlayout.h: 描述虚拟地址空间的布局.
kern/pmap.h: 上面这两个文件定义了 PageInfo 数据结构, 我们要使用它去跟踪空闲的物理内存页.
kern/kclock.h:
kern/kclock.c: 操作 PC 的电池供电时钟(battery-backed clock)和 CMOS RAM 硬件, 这里面有 BIOS 记录的物理内存量和其他的一些东西.
kern/pmap.c: 读取设备硬件, 计算物理内存量. 但是这段代码是需要我们自己写的, 应该就是最后的大作业了.

Lab Requirements

完成所有常规 Exercise 和至少一个 Challenge. 为 lab 结尾的 questions 写上简明的回答.

Part 1: Physical Page Management

JOS 使用 page granularity(页粒度)来管理物理内存, 以便它能使用 MMU 去映射和保护每一个 allocated 内存块.
给我们的任务是完成物理页分配器的代码. 它会跟踪一个 struct PageInfo 对象的链表中的空闲页(对应到物理页). 我们需要在完成虚拟内存实现的剩余部分之前完成物理页分配器.
完成 Exercise 1.
说真的, 好难, 真的好难.

Part 2: Virtual Memory

先要了解 x86 保护模式的内存管理结构. 见 Exercise 2.
虽然 Exercise 2 我们没有完成, 但是最起码知道了两个最基本的 x86 的内存管理框架: 段翻译和页翻译.

Virtual, Linear and Physical Addresses

在 x86 术语中, 虚拟地址由一个段选择器和一个段中存储的 offset 组成; 线性地址是经过段翻译但是没有经过页翻译的地址; 物理地址是经过了段翻译再经过页翻译(在 Exercise 2 中我们看到了, 这个步骤其实是可选的)得到的地址, 最终从硬件总线到达 RAM.

所谓的 offset, 或者说是 offset, 是一个 C 指针. 在 boot/boot.S 我们装载了可以通过设定段的基址(们)为 0 和最高上限为 0xffffffff 来高效地停用段翻译. 所以会影响到 selector 不起作用然后线性地址总是等于虚拟内存的 offset. 在 lab3 中我们会更多地去干涉分段行为(segmentation)来部署权力级别(privilege levels, 在 Exercise 2 中出现了, 但是我没提[摊手]), 但对于内存翻译, 我们在整个 JOS labs 中可以忽略分段, 然后仅仅专注于页翻译.
我觉得我已经在代替 Google Translation 人工进行机翻了.

在 lab 1 的 part 3 中, 我们装载了一个简单的页表在 0xf0100000 的位置. 这个页表仅映射了 4 MB 的内存. 在 lab 2 中我们要亲手在虚拟地址空间布局中部署, 将这 4 MB 扩展到从物理内存最起始的 256 MB 映射到虚拟地址的 0xf0000000, 还有其他一些虚拟内存区域.
进入 Exercise 3.

代码在 CPU 执行的同时, 我们就处于保护模式了(也就是 boot/boot.S 最开始要做的事), 在此之后就没法直接使用线性地址和物理地址了(这就是 qemu 显示物理地址部分为 read-only 的原因?). 所有的内存引用都被翻译作虚拟地址且由 MMU 转换, 就像 C 指针一样.

接着我们稍微总结一下原文中提到的一些信息:

C type	Address type
`T*`	Virtual
`uintptr_t`	Virtual
`physaddr_t`	Physical

uintptr_t 和 physaddr_t 都是 uint32_t, 所以不需要进行类型转换.
uintptr_t 和 physaddr_t 都是整数类型, 所以不能进行解引用.
JOS 允许解引用 uintptr_t 除非先将它转换为一个指针类型.

解答 Question 1.
JOS 内核有时需要去读取或者修改只知道物理地址的内存区域, 这时候需要使用KADDR(pa)将物理地址转换为虚拟地址. 这个操作其实就是将物理地址加上 0xf0000000. 相反的情况也有, 这时使用PADDR(pa)将虚拟地址转换为物理地址.

Reference Counting

在之后的 lab 里这经常将相同的物理页同时映射在多个虚拟地址上, 这时候就需要用到 struct PageInfo 的 pp_ref 域来进行引用计数, 当计数量为 0 时这个页才可以被释放.

Page Table Management

见 Exercise 4.

Part 3. Kernel Address Space

JOS kernel 将线性地址空间分割成了两个部分, 用户环境控制低地址的部分, kernel 控制高地址的部分. 其分界线在 inc/memlayout.h 中定义作 ULIM, 为 kernel 保留大约 256 MB 的虚拟地址空间. 这也就是在 lab 1 中将 kernel 放在一个高地址的原因了: 给用户提供足够的空间.

inc/memlayout.h:

/*
 * 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.
 */

我们可以看到, 在 ULIM 下面就是页表空间. ULIM 以上的, 拿 0x100000000 减去 0xef800000 等于 0x10800000, 其中靠近 ULIM 的 4 MB(PTSIZE)是内核的区域, 再往上的就是 0xf0000000~0x100000000 的 256 MB 空间.

Permissions and Fault Isolation

x86 页表使用了权限位来控制用户的可访问性, 这个我们在 Exercise 4 里也着实看到了. 其中的 PTE_W 就是用来控制 kernel 写权限的, PTE_U 是用来控制用户权限的.
用户环境对于 ULIM 以升的内存没有权限, 但是 kernel 可以对这内存进行读写. 对于范围 [UTOP,ULIM), 用户环境和 kernel 应有相同的权限, 这个我们在 inc/memlayout.h 里也看到了. 然后 UTOP 以降的地址就是专门给用户环境使用的了, 不再多提了.

Initializing the Kernel Address Space

在 Exercise 5 实现刚才提到的东西.

Address Space Layout Alternatives

我们在 JOS 中使用的内存布局只是一种实现, 其他的操作系统也可以将低地址区域保留给操作系统, 高地址区域给用户环境. 不过, 因为要考虑到一个 x86 向后兼容性模式, 叫做 virtual 8086 mode, 处理器硬件中写死了会使用线性地址空间的底部空间, 于是内核即使有映射那个部分也无法使用.

Question

Question 1

Assuming that the following JOS kernel code is correct, what type should variable x have, uintptr_t or physaddr_t?
	mystery_t x;
	char* value = return_a_pointer();
	*value = 10;
	x = (mystery_t) value;

这里我猜测是uintptr_t, 因为前文提到过在进入保护模式之后无法修改物理地址? 类似的代码稍后应该能在 Exercise 4 中看到. 事实证明这是对的.

Question 2

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:

问页目录里有什么, 这其实没啥好说的, inc/memlayout.h 里说的已经很清楚了.

Question 3

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?

如果用户程序能够读写内核, 后果将不堪设想好吧.
特殊机制? 权限位的设置.

Question 4

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

最大支持的物理内存量, 不知道, 不会.

Question 5

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?

Question 6

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?

在 lab 1 的 Exercise 6 中, 我们可以看到:

(gdb) b *0x7d6b
Breakpoint 1 at 0x7d6b
(gdb) c
Continuing.
The target architecture is assumed to be i386
=> 0x7d6b:	call   *0x10018

boot/main.c:60:

((void (*)(void)) (ELFHDR->e_entry))();

检查过了, 确实是这里跳转的.

Exercise

Exercise 1

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

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.

按先后次序实现这些函数.
boot_alloc():

// This simple physical memory allocator is used only while JOS is setting
// up its virtual memory system.  page_alloc() is the real allocator.
//
// 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.
//
// If we're out of memory, boot_alloc should panic.
// This function may ONLY be used during initialization,
// before the page_free_list list has been set up.
static void *
boot_alloc(uint32_t n)
{
	static char *nextfree;	// virtual address of next byte of free memory
	char *result;

	// Initialize nextfree if this is the first time.
	// '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.
	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.

	// 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) {
		char *new_nextfree = ROUNDUP((char *) nextfree + n, PGSIZE);
		// If alloc failed
		if (new_nextfree < nextfree)
			panic("Alloc failed.");
		// If we're out of memory, boot_alloc should panic.
        // 这里的 `PADDR` 参考了孟佬的文章
		if (PADDR(new_nextfree) > 0x40000000)
			panic("Out of memory.");
		result = nextfree;
		nextfree = new_nextfree;
		return (void *) result;
	}
	// If n==0, returns the address of the next free page without allocating
	// anything.
	else if (n == 0) {
		return (void *) nextfree;
	}

	return NULL;
}

部分代码参考了孟佬的文章$^1$.
mem_init():

// Set up a two-level page table:
//    kern_pgdir is its linear (virtual) address of the root
//
// This function only sets up the kernel part of the address space
// (ie. addresses >= UTOP).  The user part of the address space
// will be set up later.
//
// From UTOP to ULIM, the user is allowed to read but not write.
// Above ULIM the user cannot read or write.
void
mem_init(void)
{
	uint32_t cr0;
	size_t n;

	// Find out how much memory the machine has (npages & npages_basemem).
	i386_detect_memory();

	// Remove this line when you're ready to test this function.
    // 完成了这里注释掉
	// panic("mem_init: This function is not finished\n");

	//////////////////////////////////////////////////////////////////////
	// 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:
    // npages 是一个全局变量, 由 `i386_detect_memory()` 确定. 
	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_page_free_list(1);
	check_page_alloc();
	check_page();

	//////////////////////////////////////////////////////////////////////
	// 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:

	//////////////////////////////////////////////////////////////////////
	// 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:

	//////////////////////////////////////////////////////////////////////
	// 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:

	// Check that the initial page directory has been set up correctly.
	check_kern_pgdir();

	// Switch from the minimal entry page directory to the full kern_pgdir
	// page table we just created.	Our instruction pointer should be
	// somewhere between KERNBASE and KERNBASE+4MB right now, which is
	// mapped the same way by both page tables.
	//
	// If the machine reboots at this point, you've probably set up your
	// kern_pgdir wrong.
	lcr3(PADDR(kern_pgdir));

	check_page_free_list(0);

	// entry.S set the really important flags in cr0 (including enabling
	// paging).  Here we configure the rest of the flags that we care about.
	cr0 = rcr0();
	cr0 |= CR0_PE|CR0_PG|CR0_AM|CR0_WP|CR0_NE|CR0_MP;
	cr0 &= ~(CR0_TS|CR0_EM);
	lcr0(cr0);

	// Some more checks, only possible after kern_pgdir is installed.
	check_page_installed_pgdir();
}

page_init():

// --------------------------------------------------------------
// Tracking of physical pages.
// The 'pages' array has one 'struct PageInfo' entry per physical page.
// Pages are reference counted, and free pages are kept on a linked list.
// --------------------------------------------------------------

//
// Initialize page structure and memory free list.
// After this is done, NEVER use boot_alloc again.  ONLY use the page
// allocator functions below to allocate and deallocate physical
// memory via the page_free_list.
//
void
page_init(void)
{
	// The example code here marks all physical pages as free.
	// However this is not truly the case.  What memory is free?
	//  1) 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...)
	//  2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
	//     is free.
	//  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
	//     never be allocated.
	//  4) 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?
	//
	// Change the code to reflect this.
	// NB: DO NOT actually touch the physical memory corresponding to
	// free pages!
	/*
	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;
	};
	*/

	size_t i;
	size_t size;

	// 1) Mark physical page 0 as in use.
	pages[0].pp_ref = 1;

	// 2) The rest of base memory. 
	// [PGSIZE, npages_basemem * PGSIZE)
	for (i = 1; i < npages_basemem; i++) {
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}

	// 3) The IO hole.
	// [IOPHYSMEM, EXTPHYSMEM)
	for (; i < EXTPHYSMEM / PGSIZE; i++) {
		pages[i].pp_ref = 1;
	}

	// 4) Extended memory.
	// [EXTPHYSMEM, ...)
	size_t first_free_page_idx = PADDR(boot_alloc(0)) / PGSIZE;
	for (; i < first_free_page_idx; i++) {
		pages[i].pp_ref = 1;
	}

	for (; i < npages; i++) {
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}
}

部分参考了网友完成的 6.828 JOS 代码$^2$.
page_alloc():

struct PageInfo *
page_alloc(int alloc_flags)
{
	// Fill this function in
	struct PageInfo *alloc_page;
	if (page_free_list == NULL) {
		return NULL;
	}
	alloc_page = page_free_list;
	page_free_list = alloc_page->pp_link;
	alloc_page->pp_link = NULL;

	if (alloc_flags & ALLOC_ZERO) {
		memset(page2kva(alloc_page), 0, PGSIZE);
	}
	return alloc_page;
}

page2kva() 函数可以将 page 的地址转换为 kernel virtual address. 这段是我蠢了, 没看其他的人的文章真的没想到.
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.
	if (pp->pp_ref != 0) {
		panic("pp->pp_ref is nonzero.");
		return ;
	}
	if (pp->pp_link != NULL) {
		panic("pp->pp_link is not NULL.");
		return ;
	}
	pp->pp_link = page_free_list;
	page_free_list = pp;
}

这五个函数写起来其实不是很难, 只是用到了一些宏呀函数呀全局变量呀不是特别熟悉, 参考了一些资料后完成后再来看代码着实是非常简单, 所谓的链表数据结构也就只是最简单的 push 和 pop 操作.
中间出了一些没有转换成物理地址的问题, 都用 assert(0) 断点(至今还是不习惯用 gdb 调试)处理好了.
注意, 这里只需要过 check_page_free_list() 和 check_page_alloc() 就行了, check_page() 暂时过不了.

Exercise 2

Exercise 2. Look at chapters 5 and 6 of the Intel 80386 Reference Manual, if you haven’t done so already. Read the sections about page translation and page-based protection closely (5.2 and 6.4). We recommend that you also skim the sections about segmentation; while JOS uses the paging hardware for virtual memory and protection, segment translation and segment-based protection cannot be disabled on the x86, so you will need a basic understanding of it.

读文档.

Chapter 5

开头一张图告诉我们, logical address(分割成 selector 和 offset, 这个我们在 NASM 手册里已经提到过了)先进行 segment translation, 这里需要判断一个 paging 标记是否开启, 如果开启那么翻译出来的直接就是 physical address; 如果关闭, 则翻译成 linear address, 再通过 page translation 翻译成 physical address.

5.1 Segment Translation

实现这个翻译过程, 处理器会使用下面的数据结构:

Descriptors (描述符)
Descriptor tables (描述符表, 姑且认定为链表)
Selectors (选择器)
Segment Registers (段寄存器)

5.1.1 Descriptors

段描述符为处理器提供了从逻辑地址到线性地址的映射数据, 描述符由编译器/链接起/加载器/操作系统创建, 并非应用程序程序员. 段描述符有两个格式, 比较复杂就不讨论了, 但两个格式都是占 32 位.

5.1.2 Descriptor Tables

段描述符必被存储在下面两个表中其中一个:

The global descriptor table (GDT)
A local descriptor table (LDT)

描述符表是非常简易的由 8 字节 entry(其中包含描述符)为单位的内存数组. 表的空间是可变的, 最大可以容纳 8192 个描述符. GDT 的第一个 entry 不被处理器使用.

处理器提供了 GDTR 和 LDTR 两个寄存器存储两表的基址(线性地址空间的)和段上限. LGDT, SGDT, LLDT, SLDT 四个指令分别用来控制 GDT 和 LDT 的 load 和 set.

5.1.3 Selectors

逻辑地址选择器通过指定描述符表和在表中建立索引来标识描述符. 选择器可作为一个指针域对应用程序可见, 但是其值通常被链接器或链接加载器赋予. 一个 selector 占 16 个位.

5.1.4 Segment Registers

80386 在段寄存器中存储来自描述符的信息, 使用寄存器从而避免参考描述表时每次都要访问内存.
每一个段寄存器都有可视和不可视的部分. 在 lab1 中我们就有从叔的文章中盗了一些资料, 段寄存器除了 CS 和 SS 外, 还有 DS, ES, FS, GS 的额外段寄存器. 这 6 个寄存器会被看作是 16 位寄存器, 但其实它们的后面还有很大一个区域(看图例至少比 16 位大两倍)是由处理器控制而不可见的.
读取这些寄存器的指令分为两类:

直接(direct)读取指令: 如 MOV, POP, LDS, LSS, LGS, LFS.
间接(implied)读取指令: 如 far CALL 和 JMP.

不管是哪种, 它们都会使用 16 位选择器去读入寄存器的可视部分. 处理器自动从描述符表中获取基址, 上限, 类型和其他信息并将他们加载到段寄存器的可视部分.

5.2 Page Translation

地址翻译的第二阶段, 将线性地址翻译成物理地址. 这个阶段需要实现面向页的虚拟内存系统和页级保护等基本功能.
页翻译的步骤是可选的, 这样看 CR0 的 PG bit 是否被置位. 参考 lab1 的 Exercise 7.

5.2.1 Page Frame

页帧是 4kB 物理内存连续地址单位. 页的起始地址受限(我们在之前的代码中也见到过了), 并且定长.

5.2.2 Linear Address

由 DIR, PAGE 和 OFFSET 三个域组成. 寻址机制是一个二级索引方式. 先使用 DIR 作为索引套出一个页目录, 再使用 PAGE 作为索引套出单个页表, 最后再 offset.

5.2.3 Page Tables

页表是一个简易的 32 位页说明符(specifier)数组. 页表本身就是页, 意思就是它有 4KiB 的内存, 意思就是可以保存大概 1k 的 32 位项目.
页表同样是用二级索引. 上层索引是一个页目录, 这个目录可以索引到一个 1k 页表. 下层索引是 1k 页表, 可以所引导一个 1k 页. 所有的页表被一个页目录寻址, 所以总共可以寻址 1m($2^{20}$) 个页. 因为一个页包含 4kB, 所以页目录表总共占物理内存的 $2^32$ 个字节*(指80386).

5.2.4 Page-Table Entries

Page Frame Address, 因为页有 4k 的边界, 所以这个地址的低 12 位总是 0. 在不同的场合 page frame address 可以表示不同的含义.
Present Bit, 指示页表项是否可以被进行 address translation. P=1 指可以.
Accessed and Dirty Bits, 这些为提供每一级页表的页使用情况的数据.
Read/Write and User/Supervisor Bits, 不在 address translation 中使用, 用于页级保护.

5.2.5 Page Translation Cache

为保证地址翻译的极高效, 处理器会将最近使用的页表数据存进芯片缓存(on-chip cache)中, 使用到的相关寄存器是 CR3.

5.3 Combining Segment and Page Translation

跳过.

Chapter 6 Protection

6.1 Why Protection?

保护功能可以帮助 80386 检测和识别 bugs. 80386 支持可能由成百上千模块组成的复杂应用程序, 这其中定少不了一些冲突. 80386 的机制会按照保护标准符合性(conformance to protection criteria)验证内存访问和指令执行.
一定要注意, 这些机质会因系统设计目的而被使用或者忽略.

6.2 Overview of 80386 Protection Mechanisms

80386 的保护分为五类:

Type checking 类型检查
Limit checking 范围检查
Restriction of addressable domain 可寻址域限制
Restriction of procedure entry points 函数入口点限制
Restriction of instruction set 指令集限制

6.3 Segment-Level Protection

上面那 5 个保护跟这一级都有关. 保护检测会在一个段描述符的选择器被读取进段寄存器同时进行每一个段访问时被 CPU 自动执行. 段寄存器持有当前可寻址段的保护参数. 原话:

Protection checks are performed automatically by the CPU when the selector of a segment descriptor is loaded into a segment register and with every segment access. Segment registers hold the protection parameters of the currently addressable segments.

我自己都不知道我翻译了个啥.

后面的不看了, 我不想活了. 所以这个 Exercise 没有完成.

Exercise 3

Exercise 3. While GDB can only access QEMU’s memory by virtual address, it’s often useful to be able to inspect physical memory while setting up virtual memory. Review the QEMU monitor commands from the lab tools guide, especially the xp command, which lets you inspect physical memory. To access the QEMU monitor, press Ctrl-a c in the terminal (the same binding returns to the serial console).

Use the xp command in the QEMU monitor and the x command in GDB to inspect memory at corresponding physical and virtual addresses and make sure you see the same data.

Our patched version of QEMU provides an info pg command that may also prove useful: it shows a compact but detailed representation of the current page tables, including all mapped memory ranges, permissions, and flags. Stock QEMU also provides an info mem command that shows an overview of which ranges of virtual addresses are mapped and with what permissions.

字很多但是没啥内容. 我们使用快捷键调出 qemu 的命令行看一下指令的输出结果.

第一个, 我们开 gdb, 断点打在 kernel 的入口.

(gdb) x/8x 0xf0100000
0xf0100000 <_start+4026531828>:	0x1badb002	0x00000000	0xe4524ffe	0x7205c766
0xf0100010 <entry+4>:	0x34000004	0x2000b812	0x220f0011	0xc0200fd8
(gdb) x/8x 0x00100000
0x100000:	0x1badb002	0x00000000	0xe4524ffe	0x7205c766
0x100010:	0x34000004	0x2000b812	0x220f0011	0xc0200fd8

还是很熟悉的数据, 我们看下 qemu 那边:

(qemu) xp 0xf0100000
00000000f0100000: 0x00000000
(qemu) xp 0x00100000
0000000000100000: 0x1badb002

但是 qemu 这边看不到, 我也不知道是为啥.

第二个, 因为我们的 qemu 使用 apt 装的, 所以没有 828 patch 的指令, 就使用 info mem 看下好了.

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

上面应该是物理内存的 0x000000~0x400000 的区域, 映射到虚拟地址的 0xf0000000~0xf0400000 16 MB 的区域. 注意物理地址的首 16 MB 区域只有读权限, 而虚拟内存的对应区域有写权限.

按叔的文章$^3$的说法, 使用手册里给的快捷键无法打开 qemu monitor. 我在 Google 搜索 qemu xp 指令的问题时, 看到了另外一位大佬的文章$^4$里有相关联的解决方案:

qemu-system-i386 -hda obj/kern/kernel.img -monitor stdio -gdb tcp::26000 -D qemu.log

不过我没有出现这个问题.

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()
check_page(), called from mem_init(), tests your page table management routines. You should make sure it reports success before proceeding.

强调, 这题只需要过 check_page()!!, 又被坑了一次!

稍微总结一下, 首先, pde_t 和 pte_t 分别表示 Page Directory Entry 和 Page Table Entry.
比如 pgdir_walk() 函数, 这个函数的目的是利用 va 线性地址为 pgdir 这样一个页目录进行索引. 线性地址的结构早在 Exercise 2 中就出现过, 但是因为这篇文章里没有放出那张图片, 当时觉得可能不是什么很重要的东西, 就没想到这里就用到了. 线性地址的高 10 位是 Page Directory Index, 较高 10 位是 Page Table Index, 于是理所当然, 我们的寻址应该是类似 pgdir[PDX(va)][PTX(va)] 这样的, 进行一些细则的分解, 就变成了 *(*(pgdir + PDX(va)) + PTX(va)). 根据 Exercise 2 中说的, 其实不管是目录还是页表, 这中间的每一层都是一个页. 在 pgdir_walk() 中, 我们首先使用了 PTE_P flag 去判断了 pde 引用的目录是否存在, 如果存在则直接将其转换为 PTE 的地址, 最后返回 PTE 的首地址加上一个 offset(这里就是 PTX(va)), 完成这个二级索引; 如果不存在, 中间加上一个创建这一个目录的过程, 创建一个 PageInfo 其实也就是创建了一个新的页, 然后使用 page2pa() 将页信息对象转换为其对应的物理地址. 注意, PDE 里存的都是 PTE 的 kernel 虚拟地址.
再就是 page_lookup(), 返回页在 va 处映射的虚拟地址. 首先使用 pgdir_walk() 经过一次二级寻址找到 PTE 的地址, 而后再检查 PTE 引用的内容.
page_remove() 和 page_insert() 的功能更像是 STL 智能指针的工作, 进行解除引用和引用(这里叫解除映射和映射). 大致的功能不用多说了, insert 就是普通的插入, 如果原位置已经被占用了, 就先将原来的页映射解除掉; remove 就是解除一次引用, 如果页不再被引用, 就使用 page_free() 将其释放掉, 当然这个部分已经被 page_decref() 托管了.

下面是四处拼凑来的代码:

pgdir_walk():

pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
	if (pgdir == NULL) {
		return NULL;
	}

	// A linear address 'la' has a three-part structure as follows:
	//
	// +--------10------+-------10-------+---------12----------+
	// | Page Directory |   Page Table   | Offset within Page  |
	// |      Index     |      Index     |                     |
	// +----------------+----------------+---------------------+
	//  \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/
	//  \---------- PGNUM(la) ----------/
	//
	// The PDX, PTX, PGOFF, and PGNUM macros decompose linear addresses as shown.
	// To construct a linear address la from PDX(la), PTX(la), and PGOFF(la),
	// use PGADDR(PDX(la), PTX(la), PGOFF(la)).
	pde_t *pde = pgdir + PDX(va);
	pte_t *pte;

	if (*pde & PTE_P) {
		pte = (pte_t*)KADDR(PTE_ADDR(*pde));
	}
	else {
		if (create) {
			// If (alloc_flags & ALLOC_ZERO), fills the entire returned physical page with '\0' bytes.
			// ALLOC_ZERO == 1 << 0;
			// 这里参数填写 ALLOC_ZERO, 是为了使用 memset 对页进行填充
			struct PageInfo* page_info = page_alloc(ALLOC_ZERO);
			if (page_info == NULL) {
				return NULL;
			}
			// 引用计数增加
			// 注意我们在编写 page_alloc() 函数的时候, 上面有注释提示我们
			// 不要增加引用计数的
			page_info->pp_ref++;
			*pde = page2pa(page_info) | PTE_P | PTE_W | PTE_U;
			pte = (pte_t*)KADDR(PTE_ADDR(*pde));
		} else {
			// create == false, 则作不创建直接返回 NULL
			return NULL;
		}
	}
	return pte + PTX(va);
}

boot_map_region():

static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
	for (size_t i = 0; i < size; i += PGSIZE, va += PGSIZE, pa += PGSIZE) {
		pte_t* pte = pgdir_walk(pgdir, (void*)va, 1);
		if (pte == NULL)
			panic("pgdir_walk failed in boot_map_region");
		*pte = pa | perm | PTE_P;
	}
}

page_lookup():

struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
	// 查找 pte, 如果没找到不进行创建
	pte_t* pte = pgdir_walk(pgdir, va, 0);

	if (pte == NULL) {
		return NULL;
	}
	if (pte_store != NULL) {
		*pte_store = pte;	
	}
	if (*pte & PTE_P) {
		return pa2page(PTE_ADDR(*pte));
	}
	return NULL;
}

page_remove():

void
page_remove(pde_t *pgdir, void *va)
{
	pte_t* pte;
	struct PageInfo* page_info = page_lookup(pgdir, va, &pte);

	if (pte == NULL) {
		return ;
	}
	if (page_info == NULL) {
		return ;
	}
	page_decref(page_info);

	
	// page_info->pp_ref--;
	// if (page_info->pp_ref == 0) {
	// 	page_free(page_info);
	// }
	
	tlb_invalidate(pgdir, va);
	*pte = 0;
}

page_insert:

int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
	pte_t* pte = pgdir_walk(pgdir, va, 1);
	if (pte == NULL)
		return -E_NO_MEM;

	pp->pp_ref++;

	if (*pte & PTE_P)
		page_remove(pgdir, va);

	*pte = page2pa(pp) | perm | PTE_P;
	return 0;
}

Exercise 5

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

Your code should now pass the check_kern_pgdir() and check_page_installed_pgdir() checks.

In kern/pmap.c:186:

	//////////////////////////////////////////////////////////////////////
	// 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, ROUNDUP(npages * sizeof(struct PageInfo), PGSIZE), 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:
	// 
	// KSTKSIZE 是 kernel 栈的大小, 别搞错了
	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:
	// 区域是 [KERNBASE, 0xffffffff], 权限是 PTE_W
	boot_map_region(kern_pgdir, KERNBASE, 0xffffffff-KERNBASE, 0, PTE_W);

	// Check that the initial page directory has been set up correctly.
	check_kern_pgdir();

做到 Exercise 5 我才知道这个 lab 到底要干嘛. 前面的函数的实现, 全是为最后一个部分准备的.

Challenge!

极难警告!
因为麻烦了就不做了, 其实是懒.

总结

中间因为有点事耽误了一个多星期, 加上自己偷了点懒.
个人觉得这个实验比实验 1 要难, 自己也是很多东西都没搞懂, 最后的 questions 也没有都答上来. 不过大体上对虚拟内存, 页表, 内存管理的知识有了一些宏观的认识. Challenge 看着头疼没做了.

$ ./grade-lab2
running JOS: (1.4s) 
  Physical page allocator: OK 
  Page management: OK 
  Kernel page directory: OK 
  Page management 2: OK 
Score: 70/70

引用

https://zhuanlan.zhihu.com/p/41871340
https://github.com/SmallPond/MIT6.828_OS/blob/master/lab/kern/pmap.c
https://github.com/Spdwal/LearningLanuages/blob/master/OperatingSystem/Lab2.md
https://xinqiu.me/2016/12/09/MIT-6.828-2

⇦ ⇨