# 六、
来源：[JOS学习笔记（六）](http://blog.csdn.net/roger__wong/article/details/8661558)
接下来做part2，先上一张开启分页后的地址变换图：（完整的图在 http://pdos.csail.mit.edu/6.828/2011/lec/x86_translation_and_registers.pdf ）
然后再放一张具体的地址变换的图：
好当我们把这两张图也牢记于心的时候就可以开始实验的part2了。
## 1、实验要求
完成以下几个函数：
```
pgdir_walk()
boot_map_region()
page_lookup()
page_remove()
page_insert()
```
然后通过mem_init()里面的check_page函数就算过关了。
虽然要求比较简单，但实现起来可真不容易。
## 2、原理
### （1）地址变换
首先从硬件机制说起，当cpu拿到一个地址并根据这个地址访问主存时，在x86体系架构下要经过至少两级的地址变换，第一级成为段式地址变换而第二级成为页式地址变换。（为什么？主要是从安全、兼容老的os、考虑现代os等原因）
最原始的地址叫做虚拟地址，根据规定，将前16位作为段选择子，后32位作为偏移。根据段选择子查找gdt/ldt，查到的内容替加上偏移，此时的地址就变成了线性地址。
线性地址前10位被称作页目录入口（page directory entry也就是pde），其含义为该地址在页目录中的索引，中间10位为页表入口（page table entry，也就是pte），代表在页表中的索引，最后12位是偏移。
当一个线性地址进入页式地址变换机制时，首先cpu从cr3寄存器里得到页目录（page directory）在主存中的地址，然后根据这个地址加上pde得到该地址在页目录中对应的项。无论是页目录的项还是页表的项均是32位，前20位为地址，后12位为标志位。当获取了相应的页目录项之后，根据前20位地址得到页表所在地址，加上偏移pte得到页表项，取出前20位加上线性地址本身的后12位组成物理地址，整个变换过程结束。这也就是以上两个图所描述的功能。
值得注意的是，这个过程完全是由硬件实现，在这个部分的实验中要做的是初始化并维护页目录与页表，当页目录与页表维护好了，然后使cr3装载新的页目录，一切就交由硬件去处理地址变换了。
这里还有两个点需要说下：
1、为什么是20位就能表示页表所在地址？因为页表的分配以页为单位，换句话分配的过程是分配一个页面，而这个页面所有内容都用来当做页表，而页正好是4k，所以页表地址必定是4k对齐。
2、一个页表项对应一页（也就是4K内容），因为其后面有12位的偏移。一个页表有1024个页表项，因为一个页表大小为4K，一个页表项为32位（4B）。一个页目录项对应一个页表，对应4K\*1024=4M空间的映射。一个页目录有1024个页目录项，对应4M\*1024=4G地址的映射，正好是32位地址空间。
3、一个理发师只为不自己理发的人理发，当然我们在这里不套路罗素悖论。段页地址变换只为虚拟地址进行地址变换，而不为它本身的地址进行变换。换句话说变换过程中所出现的任何地址都是物理地址，在编写代码的时候尤其要注意这一点。
### （2）JOS的相关部分
之前的日志里已经说过，JOS的机制中，虽然使用段式地址变换，但和没使用完全一样，因为只定义了一个段，其长度为4G，换句话说，经过段式地址变换后的内容和之前完全一样，虚拟地址和线性地址完全一样。
在part2中也就是mem_init()执行环境里，JOS已经开启了页式地址变换，但变换的比较粗糙，只是简单的把0--4M物理地址分别映射到了0--4M物理地址和0xf0000000开始的4M 地址处，之前也已经详细说过这个问题。但同时也感谢一下这种“粗糙”的变换方式，让我们在编程填充页表和页目录的时候方便了许多。（为什么？因为要往里填充物理地址，存在一个把当前符号地址转化成物理地址的过程，因为变换的粗糙，所以这个过程相对简单）。
值得注意的是，在代码里我们的所有地址均为虚拟地址，不同通过任何方法直接得到某个符号实际存在于物理内存中的地址，只有通过算才能得到我们需要的物理地址。
## 3、实现
### （1）基本数据类型与函数说明
+ pde_t 代表一个页目录项
+ pte_t 代表一个页表项
+ pgdir_walk() 用于查找某个虚拟地址是否有页表项，如果没有也可以通过此函数创建，值得注意的是，有页表项并不代表已经被映射。
+ boot_map_region() 映射一个虚拟地址区间到一个物理地址区间，貌似在本部分没用到。
+ page_insert() 将一个虚拟地址映射到一个Page数据结构，也就是映射到某个物理地址。
+ page_lookup() 查找一个虚拟地址对应的Page数据结构，若没有映射返回空。
+ page_remove() 解除某个虚拟地址的映射。
### （2）具体实现
```
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
cprintf("pgdir_walk\r\n");
// Fill this function in
pte_t* result=NULL;
if(pgdir[PDX(va)]==(pte_t)NULL)
{
if(create==0)
{
return NULL;
}
else
{
struct Page* page=page_alloc(1);
if(page==NULL)
{
return NULL;
}
page->pp_ref++;
pgdir[PDX(va)]=page2pa(page)|PTE_P|PTE_W|PTE_U;
result=page2kva(page);
}
}
else
{
//cprintf("%u ",PGNUM(PTE_ADDR(pgdir[PDX(va)])));
result=page2kva(pa2page(PTE_ADDR(pgdir[PDX(va)])));
}
return &result[PTX(va)];
}
```
思路：
首先明确一点，返回地址是虚拟地址，要不然没有任何意义（在程序中拿到物理地址也没法用）。
查找页目录表，根据宏PDX取得页目录项（相关宏定义在mmu.h中），如果不为空，取出该项内容的前20位（PTE_ADDR宏），这是物理地址，通过此物理地址查找对应的Page结构（pa2page宏），然后获得此Page的虚拟地址（page2kva宏）。
此时的地址为页表的虚拟地址，根据偏移得到页目录项，在返回此页目录项地址。
如果前20位不为空，检查create，如果为0，返回null。否则新分配一个Page作为页表，然后自增Page 的引用，让该页目录项的前20位为页表物理地址（page2pa得到物理地址），并设置一些权限符号（不加通不过最后的检测函数），在通过此页表的虚拟地址得到相应页表项的虚拟地址并返回。
boot_map_region暂时略过，等到用的时候再说。
```
struct Page *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
cprintf("page_lookup\r\n");
// Fill this function in
pte_t* pte=pgdir_walk(pgdir,va,0);
if(pte==NULL)
{
return NULL;
}
if(pte_store!=0)
{
*pte_store=pte;
}
if(pte[0] !=(pte_t)NULL)
{
//cprintf("%x \r\n",pte[PTX(va)]);
return pa2page(PTE_ADDR(pte[0]));
}
else
{
return NULL;
}
}
```
首先使用pgdir_walk查找pte，如果为空则说明没有映射，返回NULL。
否则根据pte_store是否为0，先把此pte的地址存到pte_store里。
接着看这个页表项是否为0（更正确的写法应该是pte[0] & PTE_U，也就是查找PTE_U这一位是否为0，但貌似我这么写也没出错），如果为0，说明地址没有被映射（有页表项不代表被映射），返回NULL。
否则返回这个页表项的前20位所组成的物理地址所对应的Page结构。
```
void
page_remove(pde_t *pgdir, void *va)
{
cprintf("page_remove\r\n");
pte_t* pte=0;
struct Page* page=page_lookup(pgdir,va,&pte);
if(page!=NULL)
{
page_decref(page);
}
pte[0]=0;
tlb_invalidate(pgdir,va);
}
```
这个函数逻辑很简单，首先查找此va对应的物理页面，如果此页面不为空，说明va已经映射到了物理页面，减少这个物理页面的引用次数（次数为0就释放这个页面了，相关逻辑封装在了page_decref中），然后置相应的页表项为0，并通知tlb失效。tlb是个高速缓存，用来缓存查找记录增加查找速度。
```
int
page_insert(pde_t *pgdir, struct Page *pp, void *va, int perm)
{
cprintf("page_insert\r\n");
// Fill this function in
pte_t* pte;
struct Page* pg=page_lookup(pgdir,va,NULL);
if(pg==pp)
{
pte=pgdir_walk(pgdir,va,1);
pte[0]=page2pa(pp)|perm|PTE_P;
return 0;
}
else if(pg!=NULL )
{
page_remove(pgdir,va);
}
pte=pgdir_walk(pgdir,va,1);
if(pte==NULL)
{
return -E_NO_MEM;
}
pte[0]=page2pa(pp)|perm|PTE_P;
pp->pp_ref++;
return 0;
}
```
首先查找该va是否已经映射到了某个物理页面，如果映射到了，则解除映射。
使用pgdir_walk查询该地址的pte（若不存在则建立，第三个参数传入1），如果pte为空，说明没有额外的空间分配页表，因此返回-E_NO_MEM。
否则将该pte的内容填充成相应物理页面的物理地址，增加这个物理页面的引用次数。
存在一个问题，若此时的va已经映射到了物理页面，而这个页面恰好又是函数传入的pp，则这段代码不能正常的工作。
假设这个物理页面恰好是pp，则会调用page_remove尝试释放这个pp，又假设这个pp的引用次数正好又是1，则这个pp就会被释放掉，进入空闲页面的链表中。
但问题是这个pp不是空闲页面，虽然之后又为其建立了映射，但将Page结构从空闲链表中取出来的逻辑仅仅包含在page_alloc函数中，因此我们又不能简单的将其取出来，这要就会导致一个非空闲的页面（其引用是1）却出现在了空闲页面的链表中。
虽然实验中再三要求不使用特例的方式进行实现，但我实在找不到更美的方式（把remove逻辑或者page_alloc部分逻辑拿出来在这个函数里重新实现一次诸如此类的方法），所以我还是用了特例进行实现，若发现引用了同一个页面，就直接改pte即可。
基本到此这部分实验就结束了，运行后能通过：
