111qqz的小窝

老年咸鱼冲锋!

【施工完毕】MIT 6.828 lab 2: Memory Management

2019年2月24:完成了除了”Challenge”以外的全部练习和问题. 总共花费15个小时.

2019年2月26:完成”Challenge 2″(应该是最简单的一个orz,只花了不到一个小时)

Part 1: Physical Page Management

操作系统必须时刻追踪哪些物理内存在使用,哪些物理内存没有在使用。

一个问题是,

Ex 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要求写一个physical page allocator。我们先看第一个函数boot_alloc()

 

这个函数只有在JOS初始化虚拟内存之前会被调用一次。

通过查看 mem_init 函数可以知道,boot_alloc 是用来初始化页目录(page directory)

为什么我们需要一个单独的page allocator呢?原因是:

kernel启动时需要将物理地址映射到虚拟地址,而我们需要一个page table来记录这种映射关系。但是创建一个page table涉及到为page table所在的page分配空间…而为一个page分配空间需要在将物理地址映射到虚拟地址以后。。

解决办法是,使用一个单独的page allocator,在一个固定的位置allocate memory. 然后在这部分去做初始化的工作。

参考xv6-book:

There is a bootstrap problem: all of physical memory must be mapped in order
for the allocator to initialize the free list, but creating a page table with those mappings
involves allocating page-table pages. xv6 solves this problem by using a separate page
allocator during entry, which allocates memory just after the end of the kernel’s data
segment. This allocator does not support freeing and is limited by the 4 MB mapping
in the entrypgdir, but that is sufficient to allocate the first kernel page table.

这个函数有两个难点,第一个是,如何才能”allocate memory”? 说到”allocate memory”总是想到malloc…但是现在我们什么都没有…

然而实际上很简单(虽然我卡了好一会。。。),我们只要计算出第一个虚拟地址就好了。根据注释, magic symbol ‘end’位于没有被任何kernel code或全局变量占用的虚拟地址的起始位置。

第二个是,如何确定何时空间不够? 我们观察函数i386_detect_memory

发现这个函数的作用是得到剩余的物理内存。其中basemem就是0-640k之间的memory,extmem是1M以后的memory.

npages是剩余物理内存的页数,每页的大小是PGSIZE。因此一共能分配的空间大小为(npages*PGSIZE)

而虚拟地址的base为KERNBASE(定义在inc/memlayout.h中),因此最大能访问的虚拟地址为KERNBASE+(npages*PGSIZE)

最后的实现为:

接下来的部分就相对简单了。首先是mem_init,初始化PageInfo,由于是在page_init之前,不能使用page_alloc,因此这部分allocate也是由boot_alloc完成的。这也是唯二的由boot_alloc来分配内存的部分。代码如下:

接下来是page_init.这部分主要是判断哪些page是free的,哪些不是,参考注释,主要是[EXTPHYSMEM,…)这部分。 我们知道,对于EXTPHYSMEM之上的内存空间,首先kernel占用的空间,kernel之后是分配给kern_pgdir的空间,再然后是分配给PageInfo的空间。这之后的空间,应该都是可用的。因此代码如下:

再然后是page_alloc函数。其实就是取一个链表头的操作。

再之后的page_free. 相对应的,就是在链表头插入一个节点的操作。

到现在,练习1就算完成了。怎么知道我们的实现是对的呢,启动JOS,断言应该挂在page_insert处,并且make grade显示Physical page allocator: OK  就应该是没问题了。

 

Part 2: Virtual Memory

首先明确一下virtual address,liner address, physical address

简单来说,virtual address就是应用程序使用的地址,包括指针之类的值.

liner address 是virtual address经过segment translation 得到的.

Physical addresses 是 linear addresses 经过paging得到的.

具体来说:

Virtual addresses are used by an application program. They consist of a 16-bit selector and a 32-bit offset. In the flat memory model, the selectors are preloaded into segment registers CS, DS, SS, and ES, which all refer to the same linear address. They need not be considered by the application. Addresses are simply 32-bit near pointers.

Linear addresses are calculated from virtual addresses by segment translation. The base of the segment referred to by the selector is added to the virtual offset, giving a 32-bit linear address. Under RTTarget-32, virtual offsets are equal to linear addresses since the base of all code and data segments is 0.

Physical addresses are calculated from linear addresses through paging. The linear address is used as an index into the Page Table where the CPU locates the corresponding physical address. If paging is not enabled, linear addresses are always equal to physical addresses. Under RTTarget-32, linear addresses are equal to physical addresses except for remapped RAM regions

放几张重要的图:

详细情况可以参考Intel 80386 Reference Programmer’s Manual Chapter 5 Memory Management  建议通读,非常短,却又把最重要的内容都讲清楚了.

练习3和question 1都比较水,不说了.

接下来说练习4

ex4 In the file kern/pmap.c, you must implement code for the following functions.

check_page(), called from  mem_init(), tests your page table management routines. You should make sure it reports success before proceeding.

比较重要的是mmu.h文件,里面有很多有用的宏.

由于要把所有函数都实现完成才能跑通…所以比之前的练习稍微困难了一点…

首先是pgdir_walk函数的实现. 实现的时候有几个地方需要考虑.

第一个是根据注释”The relevant page table page might not exist yet.”

那么如何判断一个page是否存在?答案是使用present bit, (*pgdir_entry & PTE_P)为True则表示一个page存在.

第二个是create一个page的时候,需要两部分. page frame address和各种权限位.  page_alloc返回的是PageInfo* ,可以用page2pa得到对应的物理地址.

权限位的设置可以参考6.4 Page-Level Protection  或者下图

然后第三点,返回的是一个pointer,必须是VA,需要做相应的转换.

 

接下里是boot_map_region.  由于各种参数已经保证了对齐PGSIZE…所以也没什么cornor case.

唯一值得强调的是,map一个VA到PA的含义,其实就是将VA对应的page entry的page frame address设置为PA.

 

接下来是page_lookup,作用是从va得到映射到该位置的page的信息.

一开始少判断了一种情况,就是忘记检查返回的*entry,导致一个assert(!page_alloc(0)); 一直过不去…调了蛮久orz

 

下来是page_remove.

接下来是page_insert.

被坑的一个点是…错误码是带负号的…滑稽

然后我的实现中用了page_lookup…其实不用也完全可以…但是觉得使用page_lookup检查某一个va是否有page存在的逻辑更加合理…

 

Part 3: Kernel Address Space

JOS把地址空间整体分为两部分,用户环境和kernel. 这条分界线在ULIM. 具体可以参考memlayout.h中的图.

JOS会把物理地址[0x00000000 ,0x0fffffff] 的256MB空间映射到虚拟空间[0xf0000000 ,0xffffffff ]

做这个地址映射原因之一是”One reason JOS remaps all of physical memory starting from physical address 0 at virtual address 0xf0000000 is to help the kernel read and write memory for which it knows just the physical address”

 

接下来看练习5,要求初始化kernel address space.

Ex 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.

根据注释实现即可,没有什么难度(虽然因为写错个常数调了半天2333

接下来来填表格,可以部分参考上面的layout图.

  1. 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:
    Entry Base Virtual Address Points to (logically):
    1023 0xff000000 Page table for top 4MB of phys memory
    1022 0xfc000000 Page table for top *  of phys memory
    . ? ?
    . ? ?
    . ? ?
    960 0xf0000000 kernel
    959 0xefc00000 cpu0’s kernel stack(0xefff8000),cpu1’s kernel stack(0xeffe8000)
    956
    0xef000000
     npages of PageInfo(0xef000000)
    952
    0xee000000
     bootstack
    . ? ?
    2 0x00800000
    Program Data & Heap
    1 0x00400000
    Empty Memory
    0 0x00000000
    Empty Memory

接下来回答几个问题:

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?

对于JOS来说,主要就是”page-level protection”在起作用. 具体来说,就是PTE_W还有PTE_U两个bit.

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

最大能支持256MB.因为KERNBASE到4GB之间只有这么大的空间.

如果需要支持更大的物理内存,至少需要先将KERNBASE设置为一个较低的值.

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?

让我们来看看我们为了管理内存,我们都做了什么.

首先是一个page dir,大小为一个PGSIZE个字节,也就是4KB

然后是npages个PageInfo,大小为0x40000个字节,也就是256KB

然后是将物理地址的256MB映射到KERNBASE以上的地址,对应于page table [960,1024)共64个page table.每个page table需要PGSIZE个字节,所以一共是64*4096 byte,也就是256KB

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?

jmp    *%eax 之后EIP才在KERNBASE地址以上运行. 开了paging却还可以在地地址执行的原因是VA[0,4MB)也被映射到了PA[0,4MB)

这是必要的,原因参见Lab1 “Operating system kernels often like to be linked and run at very high virtual address, such as 0xf0100000, in order to leave the lower part of the processor’s virtual address space for user programs to use.”

 

那么到现在为止,挑战以外的题目就全部完成了.

 

Challenge! Extend the JOS kernel monitor with commands to:

  • Display in a useful and easy-to-read format all of the physical page mappings (or lack thereof) that apply to a particular range of virtual/linear addresses in the currently active address space. For example, you might enter 'showmappings 0x3000 0x5000' to display the physical page mappings and corresponding permission bits that apply to the pages at virtual addresses 0x3000, 0x4000, and 0x5000.
  • Explicitly set, clear, or change the permissions of any mapping in the current address space.
  • Dump the contents of a range of memory given either a virtual or physical address range. Be sure the dump code behaves correctly when the range extends across page boundaries!
  • Do anything else that you think might be useful later for debugging the kernel. (There’s a good chance it will be!)

迫于太菜了。。。选了这个可能是最简单的题目。。。实现也很无脑。。。就是模拟

 

 

 

 

 

 

 

有道词典

We have placed …

详细X

我们已经把内核和用户环境在同一地址空间。为什么将用户程序不能读或写内核的内存?具体机制保护内核内存?

说点什么

您将是第一位评论人!

提醒
wpDiscuz