-3-4 Lab 2: Memory Management | Part 1: Physical Page Management

一、寻址方式的变化

实模式：CS*4 + ip = 物理地址

保护模式 ：以 Segmentation Mechanism 的方式来寻址，addr = selector+ ip

之后在保护模式寻址的基础上引入 paging （也就是说，通过 addr = selector+ ip 得到的地址是虚拟地址，仍然需要通过 map 映射成为实际的物理地址），这样能够更好的解决内存碎片的问题。

在这个实验中通过 bootmain 开启 PG 后所有的地址都是虚拟地址了。

paging 的寻址方式如下图所示，虚拟地址和物理地址的偏移量是一致的，差的是虚拟页面到物理页面的转换。

具体在程序中的实现

page directory 和 page table 里面存放的是什么地址？

都是物理地址，page directory 存放的是 page table 的物理地址，page table 存放的是映射的物理地址。

猜测 xv6 使用的是二级页表。果真如此：This two-level

structure allows a page table to omit entire page table pages in the common case in which large ranges of virtual addresses have no mappings.

有一篇文章讲得非常详细：Page Directory Table

二、程序能够使用的地址空间从 KERNBASE 到 4g 都是可以使用的。

inc/memlayout.c 当中描述内存空间分配的部分。

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.

分页要做些什么事情？

1、划分分页后的地址空间

kern/pmap.h

inc/memlayout.c 定义了 PageInfo 结构，

这里是用链表来记录内存的分配情况吗？

kclock.h 和 kclock.c 用来读取 NVRAM（非易失性随机访问存储器，断电之后所存储的数据不丢失的随机访问存储器）。

/* See COPYRIGHT for copyright information. */#ifndef JOS_KERN_KCLOCK_H#define JOS_KERN_KCLOCK_H#ifndef JOS_KERNEL# error "This is a JOS kernel header; user programs should not #include it"#endif#defineIO_RTC0x070/* RTC port */#defineMC_NVRAM_START0xe/* start of NVRAM: offset 14 */#defineMC_NVRAM_SIZE50/* 50 bytes of NVRAM *//* NVRAM bytes 7 & 8: base memory size */#define NVRAM_BASELO(MC_NVRAM_START + 7)/* low byte; RTC off. 0x15 */#define NVRAM_BASEHI(MC_NVRAM_START + 8)/* high byte; RTC off. 0x16 *//* NVRAM bytes 9 & 10: extended memory size (between 1MB and 16MB) */#define NVRAM_EXTLO(MC_NVRAM_START + 9)/* low byte; RTC off. 0x17 */#define NVRAM_EXTHI(MC_NVRAM_START + 10)/* high byte; RTC off. 0x18 *//* NVRAM bytes 38 and 39: extended memory size (between 16MB and 4G) */#define NVRAM_EXT16LO(MC_NVRAM_START + 38)/* low byte; RTC off. 0x34 */#define NVRAM_EXT16HI(MC_NVRAM_START + 39)/* high byte; RTC off. 0x35 */unsigned mc146818_read(unsigned reg);void mc146818_write(unsigned reg, unsigned datum);#endif// !JOS_KERN_KCLOCK_H

1、boot_alloc ()

n 是请求分配的物理内存大小。

这个函数并不真正的分配内存，真正分配内存的是 page_alloc() 。

n > 0 这个函数是返回可用的虚拟地址。

n == 0 这个函数返回第一个可用的未分配的虚拟地址。

// 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.// Note that when this function is called, we are still using entry_pgdir,// which only maps the first 4MB of physical memory.static void *boot_alloc(uint32_t n){static char *nextfree;// virtual address of next byte of free memorychar *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.//分配的内存地址的起始位置result = nextfree;//roundup()根据分配的大小按照 PGSIZE 的取整，得到的nextfree 指向分配完成后下一个空闲的地址空间nextfree = ROUNDUP(result + n, PGSIZE);if((uint32_t)nextfree - KERNBASE > (npages*PGSIZE))panic("Out of memory!\n");//返回分配的空间的起始位置//在没有分配过空间的时候，返回的是内核栈后的第一个空白地址return result;}

这个函数只是简单的划分以下要分配的地址，像分配的页初始化、在内核中记录啥的都没有做。（也做不了，因为还没有页表咋记录）

第一次调用返回内存栈的后的地址，这个地址用于存放页表记录页的分配情况。

2.mem_init（）

UVPT 是什么？

#if JOS_USER/** The page directory entry corresponding to the virtual address range* [UVPT, UVPT + PTSIZE) points to the page directory itself. Thus, the page* directory is treated as a page table as well as a page directory.** One result of treating the page directory as a page table is that all PTEs* can be accessed through a "virtual page table" at virtual address UVPT (to* which uvpt is set in lib/entry.S). The PTE for page number N is stored in* uvpt[N]. (It's worth drawing a diagram of this!)** A second consequence is that the contents of the current page directory* will always be available at virtual address (UVPT + (UVPT >> PGSHIFT)), to* which uvpd is set in lib/entry.S.*/extern volatile pte_t uvpt[];// VA of "virtual page table"extern volatile pde_t uvpd[];// VA of current page directory#endif

lib/entry.S

在 lab 2 的exercise 1 当中只实现了为页表数组分配空间并初始化

voidmem_init(void){uint32_t cr0;size_t n;// Find out how much memory the machine has (npages & npages_basemem).i386_detect_memory();//npages是剩余物理内存的页数，每页的大小是PGSIZE。因此一共能分配的空间大小为(npages*PGSIZE)//npages_basemem 不晓得这个是什么？// Remove this line when you're ready to test this function.// panic("mem_init: This function is not finished\n");//猜测这句话和perror 类似，输出错误号并终止程序。//// 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 Rkern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;//这一条指令就是再为页目录表添加第一个页目录表项。通过查看memlayout.h文件，我们可以看到，UVPT的定义是一段虚拟地址的起始地址，0xef400000，从这个虚拟地址开始，存放的就是这个操作系统的页表kern_pgdir，所以我们必须把它和页表kern_pgdir的物理地址映射起来，PADDR(kern_pgdir)就是在计算kern_pgdir所对应的真实物理地址。//其实不太明白这个是什么？//// 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://存放页面信息的数组的大小size_t sizes = sizeof(struct PageInfo) * npages;//为这个数组分配空间pages = (struct PageInfo*)boot_alloc(sizes); //初始化该空间memset(pages, 0, sizes);//意思大概是：每个页的信息都存放在一个叫做 PageInfo 的数据结构当中，所有页面的 PageInfo 汇集形成了一个数组。分配页表首先需要为这个数组分配空间。//

3.page_init()

这个函数有两个功能：

初始化页面的数组（程序不可用的标记为已经用过了）并且将程序可用的数组加入 free_page_list 当中。

voidpage_init(void){// LAB 4:// Change your code to mark the physical page at MPENTRY_PADDR// as in use// 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!//1.mark page 0 as in use// 这样我们就可以保留实模式IDT和BIOS结构，以备不时之需。pages[0].pp_ref = 1;pages[0].pp_link = NULL;size_t i;size_t kernel_end_page = PADDR(boot_alloc(0)) / PGSIZE;size_t mpentry = MPENTRY_PADDR / PGSIZE;for (i = 1; i < npages; i++) {if (i >= npages_basemem && i < kernel_end_page) {//extend mem 程序不可用pages[i].pp_ref = 1;pages[i].pp_link = NULL;} else if (i == mpentry) {//估计是 I/O 那一块儿，程序不可用pages[i].pp_ref = 1;pages[i].pp_link = NULL;} else {//其他的地方程序可用pages[i].pp_ref = 0;//所以后面这两步操作我没有看懂//指向上一个可以用的空间pages[i].pp_link = page_free_list;//将 page_free_list 指向当前的空间。//感觉 page_free_list 就起到一个 temp 的作用，不是不存储所有的空闲页。//不是的，是空间页表从 index 大的空闲页指向index小的空闲页，然后 page_free_list 保存的是空闲页的 index 最大的页面。作为空闲页表的headpage_free_list = &pages[i];}}}//没有看懂上面的代码//有些不明白内核已经占有的空间是否也要按照页来划分？是否也需要记录到页表当中？//看了一下图，应该是分了的。具体功能分区再由内核自己决定。//因此这些被内核占有的内存应该在页表数组中标记为不可用//对于不可用的页面标记成已经用过了，但是如何判断留给 I/O 操作的地址只有一个？

下面是其他我认为比较好的实现

// 1.mark page 0 as in use// 这样我们就可以保留实模式IDT和BIOS结构，以备不时之需。pages[0].pp_ref = 1;// 2.size_t i;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.[IOPHYSMEM, EXTPHYSMEM)// mark I/O holefor (;i<EXTPHYSMEM/PGSIZE;i++) {pages[i].pp_ref = 1;}// 4. Extended memory // 还要注意哪些内存已经被内核、页表使用了！// first需要向上取整对齐。同时此时已经工作在虚拟地址模式（entry.S对内存进行了映射）下，// 需要求得first的物理地址physaddr_t first_free_addr = PADDR(boot_alloc(0));size_t first_free_page = first_free_addr/PGSIZE;for(;i<first_free_page;i++) {pages[i].pp_ref = 1;}// mark other pages as freefor(;i<npages;i++) {pages[i].pp_ref = 0;pages[i].pp_link = page_free_list;page_free_list = &pages[i];}

总的来说这个函数具体干了两件事情。

1.初始化 pages 数组。内核的空间，留给 I/O 设备的空间都是程序不可以用的。其他都是可以用的。

2.将空闲的页面从index 小 到 index 大加入 page_free_list 当中。最后 page_free_list 作为空闲页页表的开头开始从 index 大向 index 小来分配内存。

3、page_alloc()

真正的分配内存空间的内容。

1.从 page_list_free 当中取出一个可用的页面

2.更新 page_list_free 信息

3.根据具体的申请来决定是否需要初始化页为0.

//// Allocates a physical page. If (alloc_flags & ALLOC_ZERO), fills the entire// returned physical page with '\0' bytes. Does NOT increment the reference// count of the page - the caller must do these if necessary (either explicitly// or via page_insert).//// Be sure to set the pp_link field of the allocated page to NULL so// page_free can check for double-free bugs.//// Returns NULL if out of free memory.//// Hint: use page2kva and memsetstruct PageInfo *page_alloc(int alloc_flags){// Fill this function in//如果没有空闲的页面，说明内存超出了范围，提示错误，就不分配了if (page_free_list == NULL) {cprintf("page_alloc: out of free memory\n");return NULL;}//获取空闲列表当中的第一个struct PageInfo *addr = page_free_list;//空闲列表的指针移动到下一个空闲的位置page_free_list = page_free_list->pp_link;addr->pp_link = NULL;//如果空闲页面分配过了，就不能再指向空闲页面了//page2kva 返回值 KernelBase + 物理页号<<PGSHIFT, 虚拟地址//如果传递的 alloc_flags 当中有 ALLOC_ZERO 说明分配内存的时候指定了要将内存初始化为0.if (alloc_flags & ALLOC_ZERO) {memset(page2kva(addr), 0, PGSIZE);}return addr;//返回分配后的地址。}

4、page_free()

这个函数实现两个功能

1）检查页表是否还在使用。是就报错

2）归还页面。（无需清零什么的，因为申请 使用的时候会清零）

//// Return a page to the free list.// (This function should only be called when pp->pp_ref reaches 0.)//voidpage_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: can not free the memory");return;}pp->pp_link = page_free_list;page_free_list = pp;}

第一次测试的结果

如何测试？

先使用 make clean 删除之前的编译结果，

之后再使用 make 重新编译

再使用 make qemu 来查看运行的结果。

修改了 page_init ()后再来一次，勉强算是成功的。