5

神说、内存之间要有映射、将地址空间分为虚实。

神就造出两级页表、将变换前的地址、变换后的地址分开了．事就这样成了。

有晚上、有早晨、是第二日。

来到了lab2，内存管理，该实验分为两部分，第一部分为物理内存管理，第二部分为虚拟内存管理，本篇先描述lab1。

做本章实验一定头脑中要时刻清晰的记住两个内存分布图：物理内存分布图以及虚拟内存分布图。

物理内存的分布在前面的笔记中有介绍，这里拷贝过来：

+------------------+  <- 0xFFFFFFFF (4GB)
|      32-bit      |
|  memory mapped   |
|     devices      |
|                  |
/\/\/\/\/\/\/\/\/\/\

/\/\/\/\/\/\/\/\/\/\
|                  |
|      Unused      |
|                  |
+------------------+  <- depends on amount of RAM
|                  |
|                  |
| Extended Memory  |
|------------------|
|       kernnel    |
+------------------+  <- 0x00100000 (1MB)
|     BIOS ROM     |
+------------------+  <- 0x000F0000 (960KB)
|  16-bit devices, |
|  expansion ROMs  |
+------------------+  <- 0x000C0000 (768KB)
|   VGA Display    |
+------------------+  <- 0x000A0000 (640KB)
|                  |
|    Low Memory    |
|------------------|  <-0x00010000 (elf herader here!)
|------------------|  <-0x00007c00   (boot loader here!)
|  bootmain stack  |
+------------------+  <- 0x00000000

虚拟内存分布参见memlayout.h文件，这里也拷贝过来：

好，记住这两个图然后开始做实验。

1、实验内容

实验内容很简单，只是让你完成下列几个函数

boot_alloc()
mem_init() 
page_init()
page_alloc()
page_free()

mem_init()会调用你写的函数，然后再调用check_page_free_list和check_page_alloc两个函数来判断你完成的函数的逻辑对不对，基本上通过验证就没问题了。

2、原理。

JOS使用Page数据结构来管理内存，一个Page代表一个PGSIZE（4K）大小的物理页面，Page数据结构的定义在memlayout.h中，共有两个域，第一个域是pp_link，指向下一个空闲Page结构的指针，第二个域是一个short整形，代表当前此物理页面的引用次数，若为0则是没有被引用也就是空闲页面。

其次使用free_page_list维护一个空闲物理内存的链表，free_page_list本身就是一个Page指针，然后通过Page结构体里面的pp_link域构成空闲链表。

再次一个Page代表4K，在pmap.c中的i386_memory_detect函数中检测内存后，使用总物理内存/4k得到所需要的Page数量，赋值给npages，换句话说npages代表所需Page结构体的数量。

最后所有Page在内存（物理内存）中的存放是连续的，存放于pages处，可以通过数组的形式访问各个Page，而pages紧接于end[]符号之上，end符号是编译器导出符号，其值约为kernel的bss段在内存（虚拟内存）中的地址+bss段的段长，对应物理和虚拟内存布局也就是在kernel向上的紧接着的高地址部分连续分布着pages数组。

除此之外JOS提供page2pa,pa2page等函数可以进行Page数据结构的指针向物理地址的转换，或反转换等。

3、具体函数实现

首先被调用的是boot_alloc()，它要在什么都没做好的情况下开辟出n字节的空闲空间，并返回其首地址。

做法很简单，end符号向上均为未使用空间，只要返回这些空间就行。

首先将end符号向上和4K字节对齐（JOS已经帮我们完成），然后将这个地址（也就是nextfree）加上你要分配的空间并依然4K字节对齐，接着返回原先的nextfree即可。

char* result;  
result=nextfree;  
nextfree+=ROUNDUP(n,PGSIZE);  
return result;

然后完成mem_init()中的部分代码，可以看到mem_init()中首先检查可用内存大小，然后调用boot_alloc()分配了一个页面给kern_pgdir，这个在part2中会用，现在没啥用。

接下来需要我们给pages分配空间。通过以上原理分析，很容易得出代码：

pages=(struct Page*)boot_alloc(npages*sizeof(struct Page);

接着完成page_init()。

在page_init()里系统首先给我们初始化了pages数组以及page_free_list，可以看到这个page_free_list指向了所有的Page结构，换句话说此时认为所有的页面都是空闲可分配的，这当然是不对的，所以就要从中把一些我们已经用的内存页面从中剔除出去，这包括0地址向上的第一个页面（包括IDT等），IO hole（0xA0000--0x100000，包括vga display ,bios等），kernel地址之上的部分（kernel本身+kern_pgdir+pages）。巧合的是，IO hole，和kernel之上部分是连续的地址，因为kernel就加载在0x100000处，所以其实只需要剔除两块地址，第一块是0地址开始的第一个页面，第二块就是io hole开始的向上的一组连续的页面。

分析一下page_free_list的代码逻辑，不难发现这个链表是从pages数组的末尾开始从高地址指向低地址，所以我们先计算出要剔除的Page的地址，然后通过指针操作剔除即可。

首先剔除第一个页面，只需让第二个页面（下标为1）的pp_link域指向空，因为原本其指向的是第一个页面，而第一个页面的pp_link域指向空，也等价与pages[1].pp_link=pages[0].pp_link

其次剔除一组连续页面，使用pgstart和pgend代表这组连续地址空间的首尾所在的Page结构（所谓首是低地址，所谓尾是高地址）。

首地址也就是IOPHYSMEM所在地址，注意IOPHYSMEM已经是物理地址了，所以只需要使用pa2page得到Page结构即可。

pgend是较高位的地址，首先将end符号地址转化成物理地址(-KERNBASE)，然后再加上刚才分配的kern_pgdir（一个PGSIZE）和pages数组所占用的空间即可。当然更严谨点应该4K字节对齐的，不过不对其也能落在正确的4K范围内，不影响程序正确性。

其次注意到pgstart和pgend这两个Page也是要剔除的，所以需要找到pgend的上一个Page，和pgstart的下一个Page，这两个Page应该是空闲的。因为所有Page的组织是按数组进行组织，所以只需要进行+1和-1的地址操作即可。

接着改变pp_link域，跳过中间的区域即可。

接下来是很简单的page_alloc()。

代码逻辑很简单，从page_free_list头剔除一个Page，然后改变page_free_list使其为其pp_link即可。

接着是Page_free，直接上图：

至此part1结束：

一点感想：

在用户态编程反而觉得内存的分配是理所当然的，然而在OS内核中写相关代码时，产生的一种很奇妙的感觉就是这个过程是由程序员自己掌控的，并且分配的结果会反而影响后面的代码逻辑。

What an amazing experience !