6

接下来做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即可。

基本到此这部分实验就结束了，运行后能通过：