1、為什么要使用反向映射

物理內存的分頁機制，一個PTE（Page Table Entry）對應一個物理頁，但一個物理頁可以由多個PTE與之相對應，當該頁要被回收時，Linux2.4的做法是遍歷每個進程的所有PTE判斷該PTE是否與該頁建立了映射，如果建立則取消該映射，最后無PTE與該相關聯后才回收該頁。該方法顯而易見效率極低，因為其為了查找某個頁的關聯PTE遍歷了所有的PTE，我們不禁想：如果把每個頁關聯的PTE保存在頁結構里面，每次只需要訪問那些與之相關聯的PTE不很方便嗎？確實，2.4之后確實采用過此方法，為每個頁結構（Page）維護一個鏈表，這樣確實節省了時間，但此鏈表所占用的空間及維護此鏈表的代價很大，在2.6中棄之不用，但反向映射機制的思想不過如此，所以還是有參考價值的，

2.6內核新引入的反向映射

反向映射是2.6內核中新引入的一個機制，主要是為了加速頁面置換的時候的效率，由于內核中的頁面是不區分進程的，多個進程很有可能會共享一個頁面，內核只管每個頁面必須和一個或者多個pte對應，反過來，每一個present位為1的pte必須和一個頁面相對應，這個反過來的對應是個一一映射關系，但是前面的卻不然，也就是說頁面到pte的映射卻不是一一映射的關系，而在一個頁面將要被換出物理內存的時候必須實時更新與之相關的各個pte，由此得出的問題就是必須掃描所有的進程的所有的pte，只要找到pte所對應的頁面是將要被換出的頁面就更新之，這樣效率未免太低下，為什么呢？因為頁面被換出本應該只涉及頁面和與該頁面相關的實體，如果為了找到這些所謂的相關實體而消耗大量的時間和空間資源，那么這必然是一個瓶頸，并且這個缺陷是一定可以彌補的，為什么可以彌補呢？因為我們需要做的僅僅是記錄下和此頁面相關的實體就可以了，而不是通過遍歷尋找的方式，這樣可以濾去很多無關的查找，必然的一種可能是浪費了空間來存儲額外的信息，帶來的優惠就是節省了大量的時間，這就是反向映射的設計初衷，那么反向映射是怎么實現的呢？最簡單的實現就是在page數據結構中擴展一個字段，實際上是一個鏈表，里面鏈接所有指向這個page的pte，換出該頁面的時候遍歷這個鏈表就會得到所有的需要更新的pte，這也是2.6的早期版本中使用的方式：

struct page {
...//別的字段就此略過

union {
struct pte_chain *chain;

pte_addr_t direct;

} pte; //這個聯合式新增的

...

};

struct pte_chain {
unsigned long next_and_idx;

pte_addr_t ptes[NRPTE]; //一切為了效率，采用了緩存對齊的方式可以最小化緩存缺失

} ____cacheline_aligned;

我已經不能用除了藝術之外的其他詞匯來形容以下這個函數了，當然linux內核不管藝術不藝術，最終美麗的代碼終成泡影，換來的是高效，linux就是這樣，下面的page_add_rmap函數好在巧妙的使用了pte_chain結構：

struct pte_chain * page_add_rmap(struct page *page, pte_t *ptep, struct pte_chain *pte_chain)

{
pte_addr_t pte_paddr = ptep_to_paddr(ptep); //得到pte的地址

struct pte_chain *cur_pte_chain;

if (!pfn_valid(page_to_pfn(page)) || PageReserved(page))

return pte_chain;

pte_chain_lock(page);

if (page->pte.direct == 0) { //新分配的頁面肯定只有自己擁有pte指向，新分配的page的pte.direct肯定為0

page->pte.direct = pte_paddr; //下一次該page的pte.direct字段就不為0了

SetPageDirect(page); //設置Direct標志

inc_page_state(nr_mapped);

goto out; //第一次分配的頁面不需要什么反向映射，直接返回，實際上第一次分配這個page時，待這個函數返回后，pte_chain將會被釋放掉，因為它沒有用

}

if (PageDirect(page)) { //如果第二次該page被引用，那么就需要反向映射了，第二次引用該頁面時一共有兩個pte引用之，第一個就是該頁面剛剛被分配時的page->pte.direc，第二個就是當前調用的pte_paddr

ClearPageDirect(page); //清楚掉Direct標志，表明它開始使用反向映射了

pte_chain->ptes[NRPTE-1] = page->pte.direct; //從后向前設置

pte_chain->ptes[NRPTE-2] = pte_paddr;

pte_chain->next_and_idx = pte_chain_encode(NULL, NRPTE-2);

page->pte.direct = 0; //這里設置為0豈不是下次又要到上面的if (page->pte.direct == 0)里面去了，哈哈，注意page的pte是個聯合體而不是結構體

page->pte.chain = pte_chain; //這個設置將使得下次上面的if (page->pte.direct == 0)通不過！

pte_chain = NULL; /* We consumed it */

goto out;

}

cur_pte_chain = page->pte.chain; //如果該page第三次被引用，那么就要從這里開始了

if (cur_pte_chain->ptes[0]) { //已經到了第一個，說明一個pte_chain已經滿了，因為各個pte是從pte_chain的后面向前面推進的

pte_chain->next_and_idx = pte_chain_encode(cur_pte_chain, NRPTE - 1);

page->pte.chain = pte_chain; //下次將使用新的pte_chain

pte_chain->ptes[NRPTE-1] = pte_paddr;

pte_chain = NULL; //將pte_chain設置為NULL，目的是在外面不被釋放，因為我們已經使用了

goto out;

}

cur_pte_chain->ptes[pte_chain_idx(cur_pte_chain) - 1] = pte_paddr;

cur_pte_chain->next_and_idx--; //向前推進

out:

pte_chain_unlock(page);

return pte_chain; //如果沒有使用參數傳進來的pte_chain，那么返回它，調用者負責釋放它，只要返回一個非NULL的pte_chain就說明傳進來的pte_chain沒有被使用，外面的調用這需要釋放之，這是本著誰申請誰釋放這一基本的編程原則來的

}

上面的函數其實一點也不復雜，只要仔細閱讀一定可以理解的，看完了上面的add，那么這個函數所做的一切在什么地方使用呢？答案當然是在unmap的時候，那么看一下try_to_unmap吧：

int try_to_unmap(struct page * page)

{
struct pte_chain *pc, *next_pc, *start;

int ret = SWAP_SUCCESS;

int victim_i = -1;

...

if (PageDirect(page)) { //如果是第一個頁面，那么說明只有一個引用，更新之即可

ret = try_to_unmap_one(page, page->pte.direct);

if (ret == SWAP_SUCCESS) {
page->pte.direct = 0;

ClearPageDirect(page);

}

goto out;

}

start = page->pte.chain; //否則就需要遍歷pte.chain了

for (pc = start; pc; pc = next_pc) { //遍歷所有的pte_chain

int i;

next_pc = pte_chain_next(pc);

if (next_pc)

prefetch(next_pc);

for (i = pte_chain_idx(pc); i < NRPTE; i++) { //遍歷一個pte_chain數組的ptes

pte_addr_t pte_paddr = pc->ptes[i]; //這樣就找到了一個pte

...

switch (try_to_unmap_one(page, pte_paddr)) {
...//結果碼處理

}

}

}

...

}

如果linux和微軟一樣，那么代碼就到此為止了，事實證明這樣已經很不錯了，是的，代碼優美，效率又高，一切都不錯，但是linux開發中沒有最好只有更好，所有的物理內存都有page結構與之對應，每個page結構中保存一個pte聯合實在不是什么明智之舉，畢竟很多page根本就不需要pte反向映射，比如內核使用的page以及很多只有一個進程使用的匿名頁面，那么就必須想一個辦法，一個懶惰的辦法將這個反向映射的相關信息保存到一個用戶空間使用的結構體之內，就是說只有在使用反向映射的實體中才保存反向映射信息，否則不保存，這樣算法的時間復雜度不變，同時可以節省更多的空間，這樣一來2.6后來的內核中就廢棄了以上的優雅方式，使用了一種更加高效的方法，將反向映射信息保存到vm_area_struct結構中，因為只有用戶空間的頁面才會有反向映射，而vm_area_struct是只有用戶空間進程才有的數據結構

void page_add_anon_rmap(struct page *page, struct vm_area_struct *vma, unsigned long address)

{
struct anon_vma *anon_vma = vma->anon_vma; //這個anon_vma是一定要有的，如果在fork的時候有兩個vma公用了一個page，那么page顯然影響了兩個pte，這兩個pte可以通過這兩個vma得到

pgoff_t index;

anon_vma = (void *) anon_vma + PAGE_MAPPING_ANON;

index = (address - vma->vm_start) >> PAGE_SHIFT;

index += vma->vm_pgoff;

index >>= PAGE_CACHE_SHIFT - PAGE_SHIFT;

if (atomic_inc_and_test(&page->_mapcount)) {
page->index = index;

page->mapping = (struct address_space *) anon_vma; //2.6的稍微后期的版本中巧妙使用page的mapping字段存儲了反向映射的信息，當然光有page的字段不行，必須要有有個地方將pte鏈接在一起才行，這個結構就是上面的anon_vma，這個anon_vma是vma中多出來的字段，可能浪費了一些空間，但是說實話vma中頁面在物理內存的數量與page的數量相比還是要少啊，因此相比前一個解決方案還是節省了空間。

inc_page_state(nr_mapped);

}

}

2.6后期的方案利用了mapping的低位沒有用的特征從而使用了這些位，利用了一切可以利用的空間，并且這個方案將匿名反向映射和文件緩存反向映射分離，在文件反向映射中使用優先級樹高效處理，相比前一個早期的版本性能提高了不少。2.6的后期版本中的反向映射解決方案的資料是比較多的，我就不多說了，但是早期的反向映射的資料比較少，因此本文就分析了代碼。本文主要想表達的意思就是linux的后期版本的性能基本都比以前的高，不管它的代碼的可讀性有多糟糕，其實閱讀linux代碼和理解代碼的關鍵就是理解作者的設計思想，最好的辦法就是看changelog，只要理解了changelog就可以理解作者的意圖，讀懂了代碼才可以修改代碼，才可以添加自己的邏輯，開發自己的內核。

2、Linux2.6中是如何實現反向映射

（以下代碼均來自內核版本2.6.11.）

2.1 與RM（Reverse Mapping）相關的結構

page, address_space, vm_area_struct, mm_struct, anon_vma.

以下均顯示部分成員：

struct page{
    　　struct address_space *mapping;  /* address_space類型，為對齊需要，其值為4的位數，所以最低兩位無用，為充分利用資源，所以此處利用此最低位。
                                         * 最低位為1表示該頁為匿名頁，并且它指向anon_vma對象。
                                         * 最低為0表映射頁，此時mapping指向文件節點地址空間。
                                         */
    atomic_t _mapcount;      /* 取值-1時表示沒有指向該頁框的引用，
                             取值0時表示該頁框不可共享
                             取值大于0時表示該頁框可共享表示有幾個PTE引用
                          */
　　pgoff_t index;
};

?

struct mm_struct {
    pgd_t * pgd;
}

?

truct vm_area_struct {
    struct list_head anon_vma_node;    /* Serialized by anon_vma->lock */
    struct anon_vma *anon_vma;    /* Serialized by page_table_lock */
}    

?

struct anon_vma {
    spinlock_t lock;    /* Serialize access to vma list */
    struct list_head head;    /* List of private "related" vmas */
};

2.2 進程地址空間

?

?

每個進程有個進程描述符task_struct，其中有mm域指向該進程的內存描述符mm_struct。

每個進程都擁有一個內存描述符，其中有PGD域，指向該進程地址空間的全局頁目錄；mmap域指向第一個內存區域描述符vm_area_strut1。

進程通過內存區域描述符vm_area_struct管理內存區域，每個內存區域描述符都有vm_start和vm_end域指向該內存區域的在虛擬內存中的起始位置；vm_mm域指向該進程的內存描述符；每個vm_area_struct都有一個anon_vma域指向該進程的anon_vma；

每個進程都有一個anon_vma，是用于鏈接所有vm_area_struct的頭結點，通過vm_area_struct的anon_vma_node構成雙循環鏈表。

　最終形成了上圖。

?

現在假設我們要回收一個頁，我們要做的是訪問所有與該頁相關聯的PTE并修改之取消二者之間的關聯。與之相關聯的函數為：try_to_unmap。

2.3 try_to_unmap

2.3.1 try_to_unmap函數及PageOn宏 分析

int try_to_unmap(struct page *page)
{
    int ret;

    BUG_ON(PageReserved(page));
    BUG_ON(!PageLocked(page));

    /*判斷是不是匿名頁，若是的話執行try_to_unmap_anon函數，否則的話執行try_to_unmap_file函數*/
    if (PageAnon(page))         // PageAnon函數分析在下面
        ret = try_to_unmap_anon(page);
    else
        ret = try_to_unmap_file(page);

    if (!page_mapped(page))
        ret = SWAP_SUCCESS;
    return ret;
}

static inline int PageAnon(struct page *page)
{
    return ((unsigned long)page->mapping & PAGE_MAPPING_ANON) != 0;
    /* #define PAGE_MAPPING_ANON    1  此函數非常easy，就是判斷page的mapping成員的末位是不是1，是的話返回1，不是的話返回0*/

}

2.3.2 try_to_unmap_anon函數及page_lock_anon_vma函數及list_for_each_entry宏 分析

還沒開始看文件系統一節，所以try_to_unmap_file沒看懂，所以此處只分析 try_to_unmap_anon函數，等看完vfs后再來補充吧。

static int try_to_unmap_anon(struct page *page)
{
    struct anon_vma *anon_vma;
    struct vm_area_struct *vma;
    int ret = SWAP_AGAIN;

    anon_vma = page_lock_anon_vma(page); /* 獲取該匿名頁的anon_vma結構
                                          * page_lock_anon_vma函數分析在下面。
                                          */
    if (!anon_vma)
        return ret;

    list_for_each_entry(vma, &anon_vma->head, anon_vma_node) { /* 循環遍歷
                                                                * list_for_each_entry分析在下面
                                                                * anon_vma就是上圖中anon_vma的指針，anon_vma->head得到其head成員（是list_head）類型，
                                                                * 其next值便對應上圖中vm_area_struct1中的anon_vma_node中的head。
                                                                * vma 是vm_area_struct類型的指針，anon_vma_node為typeof(*vma)即vm_area_struct中的成員。
                                                                * 到此便可以開始雙鏈表循環
                                                                */
        ret = try_to_unmap_one(page, vma);      // 不管是調用try_to_unmap_anon還是try_to_unmap_file最終還是回到try_to_unmap_one上
        if (ret == SWAP_FAIL || !page_mapped(page))
            break;
    }
    spin_unlock(&anon_vma->lock);
    return ret;
}

static struct anon_vma *page_lock_anon_vma(struct page *page)
{
    struct anon_vma *anon_vma = NULL;
    unsigned long anon_mapping;

    rcu_read_lock();
    anon_mapping = (unsigned long) page->mapping;
    if (!(anon_mapping & PAGE_MAPPING_ANON))
        goto out;
    if (!page_mapped(page))
        goto out;
    // 前面已經提到，mapping最低位為1時表匿名頁，此時mapping是指向anon_vma指針，故此處-1后強制轉化為struct anon_vma指針類型，并返回該值。
    anon_vma = (struct anon_vma *) (anon_mapping - PAGE_MAPPING_ANON);
    spin_lock(&anon_vma->lock);
out:
    rcu_read_unlock();
    return anon_vma;
}

/* 參數含義：
 * head是list_head指針，無非此處需要的第一個list_head是head->next
 * pos是個指向包含list_head的結構體的指針，可以用typeof(*pos)解引用來得到此結構體
 * member 是list_head在typeof(*pos)中的名稱
 * 這樣pos = list_entry((head)->next, typeof(*pos), member)第一次便初始化pos為指向包含head->next指向的那個結構體的指針。
 * 之后便是雙循環鏈表遍歷了
 */
#define list_for_each_entry(pos, head, member)                \
    for (pos = list_entry((head)->next, typeof(*pos), member);    \ // list_entry分析在下面
         prefetch(pos->member.next), &pos->member != (head);     \
         pos = list_entry(pos->member.next, typeof(*pos), member))

/* list_entry函數其實非常簡單，其各參數的意義：
 * ptr 指向list_head類型的指針
 * type 包含list_head類型的結構體
 * member list_head在type中的名稱
 * 返回值：包含ptr指向的list_head的類型為type的指針，即由list_head指針得到包含此list_head結構體的指針，實現也很簡單，ptr減去member在type中的偏移即可
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
#define container_of(ptr, type, member) ({            \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

2.3.3 try_to_unmap_one函數及vma_address函數及pdg_offset宏 分析

?

?

Linux采用三級頁表：

PGD：頂級頁表，由pgd_t項組成的數組，其中第一項指向一個二級頁表。

PMD：二級頁表，由pmd_t項組成的數組，其中第一項指向一個三級頁表（兩級處理器沒有物理的PMD）。

PTE：是一個頁對齊的數組，第一項稱為一個頁表項，由pte_t類型表示。一個pte_t包含了數據頁的物理地址。

static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma)
{
    struct mm_struct *mm = vma->vm_mm;
    unsigned long address;
    pgd_t *pgd;
    pud_t *pud;
    pmd_t *pmd;
    pte_t *pte;
    pte_t pteval;
    int ret = SWAP_AGAIN;

    if (!mm->rss)
        goto out;
    address = vma_address(page, vma); /* 通過頁和vma得到線性地址
                                       * vm_address函數解析在下面
                                       */
    if (address == -EFAULT)
        goto out;

    /*
     * We need the page_table_lock to protect us from page faults,
     * munmap, fork, etc...
     */
    spin_lock(&mm->page_table_lock); // 頁表鎖

    pgd = pgd_offset(mm, address); /* 獲得pdg
                                    * pdg_offset通過內存描述符和線性地址得到pgd
                                    * 該函數解析在下面
                                    */
    if (!pgd_present(*pgd))        
        goto out_unlock;

    pud = pud_offset(pgd, address); /* 獲得pud
                                       i386上應該是0吧？
                                     */
    if (!pud_present(*pud))
        goto out_unlock;

    pmd = pmd_offset(pud, address); /* 獲得pmd */
    if (!pmd_present(*pmd))
        goto out_unlock;

    pte = pte_offset_map(pmd, address); /* 獲得pte */
    if (!pte_present(*pte))
        goto out_unmap;

    /* 有了pgd pmd pte 后我們便達到我們目的了 ===> 查找與頁相關聯系的頁表項，找到后便可以進行修改了(如果是要換出該頁的話則應該解除映射pte_unmap()函數)
     * 但修改之前還要做些判斷和處理
     */
    
    // 
    if (page_to_pfn(page) != pte_pfn(*pte))
        goto out_unmap;

    /*
     * If the page is mlock()d, we cannot swap it out.
     * If it's recently referenced (perhaps page_referenced
     * skipped over this mm) then we should reactivate it.
     */
    if ((vma->vm_flags & (VM_LOCKED|VM_RESERVED)) ||
            ptep_clear_flush_young(vma, address, pte)) {
        ret = SWAP_FAIL;
        goto out_unmap;
    }

    /*
     * Don't pull an anonymous page out from under get_user_pages.
     * GUP carefully breaks COW and raises page count (while holding
     * page_table_lock, as we have here) to make sure that the page
     * cannot be freed.  If we unmap that page here, a user write
     * access to the virtual address will bring back the page, but
     * its raised count will (ironically) be taken to mean it's not
     * an exclusive swap page, do_wp_page will replace it by a copy
     * page, and the user never get to see the data GUP was holding
     * the original page for.
     *
     * This test is also useful for when swapoff (unuse_process) has
     * to drop page lock: its reference to the page stops existing
     * ptes from being unmapped, so swapoff can make progress.
     */
    if (PageSwapCache(page) &&
        page_count(page) != page_mapcount(page) + 2) {
        ret = SWAP_FAIL;
        goto out_unmap;
    }

    /* Nuke the page table entry. */
    flush_cache_page(vma, address);
    pteval = ptep_clear_flush(vma, address, pte);

    /* Move the dirty bit to the physical page now the pte is gone. */
    if (pte_dirty(pteval))
        set_page_dirty(page);

    if (PageAnon(page)) {
        swp_entry_t entry = { .val = page->private };
        /*
         * Store the swap location in the pte.
         * See handle_pte_fault() ...
         */
        BUG_ON(!PageSwapCache(page));
        swap_duplicate(entry);
        if (list_empty(&mm->mmlist)) {
            spin_lock(&mmlist_lock);
            list_add(&mm->mmlist, &init_mm.mmlist);
            spin_unlock(&mmlist_lock);
        }
        set_pte(pte, swp_entry_to_pte(entry));
        BUG_ON(pte_file(*pte));
        mm->anon_rss--;
    }

    mm->rss--;
    acct_update_integrals();
    page_remove_rmap(page);
    page_cache_release(page);

out_unmap:
    pte_unmap(pte);
out_unlock:
    spin_unlock(&mm->page_table_lock);
out:
    return ret;
}
         


static inline unsigned long
vma_address(struct page *page, struct vm_area_struct *vma)
{
    pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT); /* PAGE_CACHE_SHIFT - PAGE_SHIFT值為0，其實就是把page->index賦給pgoff
                                                                     * 至于為什么要這樣右移一下，我也不清楚
                                                                     */
    unsigned long address;
    address = vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT); /* page->index是頁的偏移
                                                                        * vma->vm_pgoff是內存區域首地址的偏移，都是以頁為單位
                                                                        * 相減后再vm_start || address >= vma->vm_end)) { /* 得到的地址應該在vm->vm_start和vm_end之間，否則報錯 */
        /* page should be within any vma from prio_tree_next */
        BUG_ON(!PageAnon(page));
        return -EFAULT;
    }
    return address;
}

#define PGDIR_SHIFT    22          // 在i386機子上線性地址0-11位表PTE，12-21表PMD，22-31位表PGD，即線性地址右移22位的結果為其在全局頁目錄的偏移
#define PTRS_PER_PGD    1024    // 因PGD共10位，所以其最多可以有2^10=1024個全局描述符項

#define pgd_index(address) (((address) >> PGDIR_SHIFT) & (PTRS_PER_PGD-1)) // 得到線性地址address在全局頁目錄里面的偏移
#define pgd_offset(mm, address) ((mm)->pgd+pgd_index(address))             // 再加上全局描述符基地址（存儲在內存描述符mm_struct中的pdg域）后便得到其在全局描述符中的具體位置便得到頁在內存區域的中的偏移>便得到頁在內存區域中的地址>

?

?