《MIT JOS Lab2: Memory Management》实验报告
目录
目录
0 准备文件
和实验一类似，注意git的冲突处理，此处不再赘述。
1 物理页管理
The operating system must keep track of which parts of physical RAM are free and which are currently in use. JOS manages the PC's physical memory with page granularity so that it can use the MMU to map and protect each piece of allocated memory.
You'll now write the physical page allocator. It keeps track of which pages are free with a linked list of struct Page objects, each corresponding to a physical page. You need to write the physical page allocator before you can write the rest of the virtual memory implementation, because your page table management code will need to allocate physical memory in which to store page tables.
这个实验主要是为了让读者了解内核RAM如何分配和释放内存，首先要手动写一个物理页面分配器（physical page allocator），这个分配器用来维护一个数据结构，该数据结构记录了物理内存空闲页面的链表。
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.操作系统必需跟踪哪些物理 RAM 是空闲的，哪些正在使用。这个 exercise 主要编写物理页面分配器。它利用一个 PageInfo 结构体组成的链表记录哪些页面空闲，每个结构体对应一个物理页。因为页表的实现需要分配物理内存来存储页表，在虚拟内存的实现之前，我们需要先编写物理页面分配器。
1.1 boot_alloc( )函数
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) {
return nextfree;
}
result = nextfree;
nextfree += ROUNDUP(n, PGSIZE);
return result;
}要写出这个函数需要搞懂几个概念，n是什么，end是什么，ROUNDUP宏是什么，nextfree是什么：
首先，n是分配n个byte，意思就是现在要分配n个byte，占用n个byte。
第二，end是指向内核的 bss 段的末尾的一个指针。
进入 $ROOT/obj/kern 目录，键入objdump -h kernel，查看文件结构可以发现，bss已经位于内核最终，所以，end是向内核的 bss 段的末尾的一个指针，也就是第一个未使用的虚拟内存地址。
第三，ROUNDUP宏。
进入 $ROOT/inc 目录下的 types.h 可以看到ROUNDUP的原定义。
// Round up to the nearest multiple of n
#define ROUNDUP(a, n) \
({ \
uint32_t __n = (uint32_t) (n); \
(typeof(a)) (ROUNDDOWN((uint32_t) (a) + __n - 1, __n)); \
})
定义为：用多个大小为n的页面聚集最近的a个Byte。（Round up to the nearest multiple of n）
最后，nextfree 是下一个空闲地址的虚拟地址。
函数开头写到：
if (!nextfree) {
extern char end[];
nextfree = ROUNDUP((char *) end, PGSIZE);
}如果 nextfree 是第一次被使用，那么初始化这个变量，如果不是第一次被使用，那么就找到下一个空闲地址的虚拟地址。找到下一个空闲地址的虚拟地址的方法是 用 PGSIZE 为大小的页面聚集 以end地址处的内容 个byte。
PGSIZE是一个物理页面的大小 4KB=4096B，定义在 inc/mmu.h 中，其中还有一个后面要用的重要常量PTSIZE，为一个页表对应实际物理内存的大小 1024*4KB=4MB
那么接下来的情况应该是 nextfree 不是第一次被使用：
if (n == 0) {
return nextfree;
}
result = nextfree;
nextfree += ROUNDUP(n, PGSIZE);
return result;1）如果分配的n是0的话，那么就意味着不用分配了，直接把nextfree的指针输出即可。
2）如果分配的n不是0，那么就意味着有分配内容，就要 用 PGSIZE 为大小的页面聚集 n 个byte。那么下一个空闲页面（nextfree）就是 从当前开始算起加上 分配的页面之后的页面序号。
1.2 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:
pages = (struct PageInfo *) boot_alloc(npages*sizeof(struct PageInfo));
memset(pages, 0, npages*sizeof(struct PageInfo));
//////////////////////////////////////////////////////////////////////
// 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();
}这个函数不怎么好理解，得一行行硬看：
首先，这个函数用到了刚才提到的数据结构 PageInfo ，就要先看了解到PageInfo的具体定义是什么：
1.2.1 函数中用到的 PageInfo 结构
进入 $ROOT/inc/memlayout.h 中可以看到PageInfo的定义：
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;
};这个 PageInfo 中包括了两个变量：
pp_link：指向下一个空闲的页。
pp_ref：这是指向该页的指针数量。在启动时间时，Pages没有合法的指针，即指针为NULL。
1.2.2 初始化分配首页
// create initial page directory.
kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
memset(kern_pgdir, 0, PGSIZE);文段头部写到，kern_pgdir 是虚拟地址的首部，那么在 kern_pgdir 作为页表头部的指针进行首页的分配。
1.2.3 分配npages大小的数组
分配数组大小为 npages，数据单元是 PageInfo，那么所占用空间就是 ： npages*sizeof(struct PageInfo)
将分配完的数据指针放入pages变量中，可以模仿1.2.2 中初始化分配首页的步骤来写下面的代码：
// 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:
pages = (struct PageInfo *) boot_alloc(npages*sizeof(struct PageInfo));
memset(pages, 0, npages*sizeof(struct PageInfo)); only up to the call to check_page_free_list(1)，所以我就不往下分析了先。
1.3 page_init()函数
// 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...)
pages[i].pp_ref = 1;
// 2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
// is free.
for (i = 0; i < npages_basemem; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
// 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!
size_t i;
for (i = 0; i < npages; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
}初始化页表结构和空闲页的链表。
这个函数中已经写好的代码片段是假设所有的物理页面都为空的情况，当然这在实际中是不可能的。
所以要初始化空闲页的链表的话就要明确哪些内存是空闲的。
步骤如下：
1）给0页面标记为正在使用的状态。
2）剩下的基础内存是空闲的。
3）IO洞 不能被分配。
4）扩展内存有些被用，有些空闲。
看完了这四句话整个人都不好了，第一句第二句还知道什么意思，剩下的是什么意思呢？
1.3.1 给初始页面标记为正在使用状态
// 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...)
pages[i].pp_ref = 1;刚开始的时候如果被占用的页面所拥有的指针数量是1，那么模仿下面已存在的代码可以得到以上的这段代码，将指针数量标记为1即可。
1.3.2 剩下的基础内存是空闲的
什么叫基础内存，大概意思就是在头上有一部分空着的吧。所以直接复制下面的那段代码稍作修改就可以了。
// 2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
// is free.
for (i = 0; i < npages_basemem; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}1.3.3 IO洞 不能被分配
IO洞是个什么意思？
上一篇： [操作系统实验lab2]实验报告
下一篇： 软件测试 实验一