# 五、
来源：[JOS学习笔记（五）](http://blog.csdn.net/roger__wong/article/details/8656339)
> 神说、内存之间要有映射、将地址空间分为虚实。
> 神就造出两级页表、将变换前的地址、变换后的地址分开了．事就这样成了。
> 有晚上、有早晨、是第二日。
来到了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 !
