Linux內(nèi)存管理之頁面回收

請求調(diào)頁機(jī)制，只要用戶態(tài)進(jìn)程繼續(xù)執(zhí)行，他們就能獲得頁框，然而，請求調(diào)頁沒有辦法強(qiáng)制進(jìn)程釋放不再使用的頁框。因此，遲早所有空閑內(nèi)存將被分配給進(jìn)程和高速緩存，Linux內(nèi)核的頁面回收算法（PFRA）采取從用戶進(jìn)程和內(nèi)核高速緩存“竊取”頁框的辦法不從伙伴系統(tǒng)的空閑塊列表。

實(shí)際上，在用完所有空閑內(nèi)存之前，就必須執(zhí)行頁框回收算法。否則，內(nèi)核很可能陷入一種內(nèi)存請求的僵局中，并導(dǎo)致系統(tǒng)崩潰。也就是說，要釋放一個(gè)頁框，內(nèi)核就必須把頁框的數(shù)據(jù)寫入磁盤；但是，為了完成這一操作，內(nèi)核卻要請求另一個(gè)頁框（例如，為I/O數(shù)據(jù)傳送分配緩沖區(qū)首部）。因?yàn)椴淮嬖诳臻e頁框，因此，不可能釋放頁框。

頁框算法的目標(biāo)之一就是保存最少的空閑頁框并使內(nèi)核可以安全地從“內(nèi)存緊缺”的情形中恢復(fù)過來。

選擇目標(biāo)頁

PFRA的目標(biāo)就是獲得頁框并使之空閑。PFRA按照頁框所含內(nèi)容，以不同的方式處理頁框。我們將他們區(qū)分成：不可回收頁、可交換頁、可同步頁和可丟棄頁：

進(jìn)行頁面回收的時(shí)機(jī)

Linux 操作系統(tǒng)使用如下這兩種機(jī)制檢查系統(tǒng)內(nèi)存的使用情況，從而確定可用的內(nèi)存是否太少從而需要進(jìn)行頁面回收。

周期性的檢查：這是由后臺(tái)運(yùn)行的守護(hù)進(jìn)程 kswapd 完成的。該進(jìn)程定期檢查當(dāng)前系統(tǒng)的內(nèi)存使用情況，當(dāng)發(fā)現(xiàn)系統(tǒng)內(nèi)空閑的物理頁面數(shù)目少于特定的閾值時(shí)，該進(jìn)程就會(huì)發(fā)起頁面回收的操作。

“內(nèi)存嚴(yán)重不足”事件的觸發(fā)：在某些情況下，比如，操作系統(tǒng)忽然需要通過伙伴系統(tǒng)為用戶進(jìn)程分配一大塊內(nèi)存，或者需要?jiǎng)?chuàng)建一個(gè)很大的緩沖區(qū)，而當(dāng)時(shí)系統(tǒng)中的內(nèi)存沒有辦法提供足夠多的物理內(nèi)存以滿足這種內(nèi)存請求，這時(shí)候，操作系統(tǒng)就必須盡快進(jìn)行頁面回收操作，以便釋放出一些內(nèi)存空間從而滿足上述的內(nèi)存請求。這種頁面回收方式也被稱作“直接頁面回收”。

睡眠回收，在進(jìn)入suspend-to-disk狀態(tài)時(shí)，內(nèi)核必須釋放內(nèi)存。

?

如果操作系統(tǒng)在進(jìn)行了內(nèi)存回收操作之后仍然無法回收到足夠多的頁面以滿足上述內(nèi)存要求，那么操作系統(tǒng)只有最后一個(gè)選擇，那就是使用 OOM( out of memory )killer，它從系統(tǒng)中挑選一個(gè)最合適的進(jìn)程殺死它，并釋放該進(jìn)程所占用的所有頁面。

上面介紹的內(nèi)存回收機(jī)制主要依賴于三個(gè)字段：pages_min，pages_low 以及 pages_high。每個(gè)內(nèi)存區(qū)域（ zone ）都在其區(qū)域描述符中定義了這樣三個(gè)字段，這三個(gè)字段的具體含義如下表 所示。

字段含義

PFRA設(shè)計(jì)

設(shè)計(jì)總則

首先釋放“無害”頁，即必須線回收沒有被任何進(jìn)程使用的磁盤與內(nèi)存高速緩存中的頁；

將用戶態(tài)進(jìn)程和所有頁定為可回首頁，F(xiàn)PRA必須能夠竊得人任何用戶態(tài)進(jìn)程頁，包括匿名頁。這樣，睡眠較長時(shí)間的進(jìn)程將逐漸失去所有頁；

同時(shí)取消引用一個(gè)共享頁的所有頁表項(xiàng)的映射，就可以回收該共享頁；

只回收“未用”頁，使用LRU算法。Linux使用每個(gè)頁表項(xiàng)中的訪問標(biāo)志位，在頁被訪問時(shí)，該標(biāo)志位由銀獎(jiǎng)自動(dòng)置位；而且，頁年齡由頁描述符在鏈表（兩個(gè)不同的鏈表之一）中的位置來表示。

因此，頁框回收算法是集中啟發(fā)式方法的混合：

謹(jǐn)慎選擇檢查高速緩存的順序；

基于頁年齡的變化排序；

區(qū)別對待不同狀態(tài)的頁；

反向映射

PFRA的目標(biāo)之一是能釋放共享頁框。為達(dá)到這個(gè)目地。Linux內(nèi)核能夠快速定為指向同一頁框的所有頁表項(xiàng)。這個(gè)過程就叫做反向映射。Linux 操作系統(tǒng)為物理頁面建立一個(gè)鏈表，用于指向引用了該物理頁面的所有頁表項(xiàng)。

基本思想如下圖：

?
?

Linux采用“面向?qū)ο蟮姆聪蛴成洹奔夹g(shù)。實(shí)際上，對任何可回收的用戶態(tài)頁，內(nèi)核保留系統(tǒng)中該頁所在所有現(xiàn)行區(qū)（“對象”）的反向鏈接，每個(gè)線性區(qū)描述符（ vm_area_struct 結(jié)構(gòu)）存放一個(gè)指針指向一個(gè)內(nèi)存描述符（ mm_struct 結(jié)構(gòu)），而該內(nèi)存描述符又包含一個(gè)指針指向一個(gè)頁全局目錄（PGD）。因此，這些反向鏈接使得PFRA能夠檢索引用某頁的所有頁表項(xiàng)。因?yàn)榫€性區(qū)描述符比頁描述符少，所以更新共享頁的反向鏈接就比較省時(shí)間。下面是具體的實(shí)現(xiàn)：

基于對象的反向映射的實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)

首先，PFRA必須要確定待回收頁是共享的還是非共享的，以及是映射頁或是匿名頁。為做到這一點(diǎn)，內(nèi)核要查看頁描述符的兩個(gè)字段：_mapcount和mapping。_mapcount字段存放引用頁框的頁表項(xiàng)數(shù)目，確定其是否共享；mapping字段用于確定頁是映射的或是匿名的：為空表示該頁屬于交換高速緩存；非空，且最低位是1，表示該頁為匿名頁，同時(shí)mapping字段中存放的是指向anon_vma描述符的指針；如果mapping字段非空，且最低位是0，表示該頁為映射頁；同時(shí)mapping字段指向?qū)?yīng)文件的address_space對象。

struct page   
{   
     atomic_t _mapcount;          
                  
     union {   
        ……  
        struct {   
        ……        
         struct address_space *mapping;       
        };   
        ……  
 };   

Linux的address_space對象在RAMA中是對其的，所以其起始地址是4的倍數(shù)。因此其mapping字段的最低位可以用作一個(gè)標(biāo)志位來表示該字段的指針是指向address_space對象還是anon_vma描述符。PageAnon檢查mapping最低位。

/*檢查頁是否為匿名頁，低位為1時(shí)為匿名頁*/  
static inline int PageAnon(struct page *page)  
{  
    return ((unsigned long)page->mapping & PAGE_MAPPING_ANON) != 0;  
}  

匿名頁面和文件映射頁面分別采用了不同的底層數(shù)據(jù)結(jié)構(gòu)去存放與頁面相關(guān)的虛擬內(nèi)存區(qū)域。對于匿名頁面來說，與該頁面相關(guān)的虛擬內(nèi)存區(qū)域存放在結(jié)構(gòu) anon_vma 中定義的雙向鏈表中。結(jié)構(gòu) anon_vma 定義很簡單，如下所示：

struct anon_vma   
{   
     spinlock_t lock;     
     struct list_head head;       
};  
 

匿名頁的面向?qū)ο蠓聪蛴成淙缦聢D：

?
?

可以通過頁面的mapping找到anon_vma然后找到映射該頁面的所有線性區(qū)域（vm_area_struct結(jié)構(gòu)）。

而對于基于文件映射的頁面來說，與匿名頁面不同的是，與該頁面相關(guān)的虛擬內(nèi)存區(qū)域的存放是利用了優(yōu)先級搜索樹這種數(shù)據(jù)結(jié)構(gòu)的。這是因?yàn)閷τ谀涿撁鎭碚f，頁面雖然可以是共享的，但是一般情況下，共享匿名頁面的使用者的數(shù)目不會(huì)很多；而對于基于文件映射的頁面來說，共享頁面的使用者的數(shù)目可能會(huì)非常多，使用優(yōu)先級搜索樹這種結(jié)構(gòu)可以更加快速地定位那些引用了該頁面的虛擬內(nèi)存區(qū)域。操作系統(tǒng)會(huì)為每一個(gè)文件都建立一個(gè)優(yōu)先級搜索樹，其根節(jié)點(diǎn)可以通過結(jié)構(gòu) address_space 中的 i_mmap 字段獲取。

struct address_space {   
  ……  
 struct prio_tree_root   i_mmap;          
……  
 }   

Linux中使用 (radix,size,heap) 來表示優(yōu)先級搜索樹中的節(jié)點(diǎn)。其中，radix 表示內(nèi)存區(qū)域的起始位置，heap 表示內(nèi)存區(qū)域的結(jié)束位置，size 與內(nèi)存區(qū)域的大小成正比。在優(yōu)先級搜索樹中，父節(jié)點(diǎn)的 heap 值一定不會(huì)小于子節(jié)點(diǎn)的 heap 值。在樹中進(jìn)行查找時(shí)，根據(jù)節(jié)點(diǎn)的 radix 值進(jìn)行。程序可以根據(jù) size 值區(qū)分那些具有相同 radix 值的節(jié)點(diǎn)。

在用于表示虛擬內(nèi)存區(qū)域的結(jié)構(gòu) vm_area_struct 中，與上邊介紹的雙向鏈表和優(yōu)先級搜索樹相關(guān)的字段如下所示：

struct vm_area_struct {   
 struct mm_struct * vm_mm;    
……  
 union {   
     struct {   
         struct list_head list;   
         void *parent;    
         struct vm_area_struct *head;   
     } vm_set;   
  
     struct raw_prio_tree_node prio_tree_node;   
 } shared;   
  
  
 struct list_head anon_vma_node;      
 struct anon_vma *anon_vma;       
};   

與匿名頁面的雙向鏈表相關(guān)的字段是 anon_vma_node 和 anon_vma。union shared 則與文件映射頁面使用的優(yōu)先級搜索樹相關(guān)。字段 anon_vma 指向 anon_vma 表；字段 anon_vma_node 將映射該頁面的所有虛擬內(nèi)存區(qū)域鏈接起來；union shared 中的 prio_tree_node 結(jié)構(gòu)用于表示優(yōu)先級搜索樹的一個(gè)節(jié)點(diǎn)；在某些情況下，比如不同的進(jìn)程的內(nèi)存區(qū)域可能映射到了同一個(gè)文件的相同部分，也就是說這些內(nèi)存區(qū)域具有相同的（radix,size,heap）值，這個(gè)時(shí)候 Linux 就會(huì)在樹上相應(yīng)的節(jié)點(diǎn)（樹上原來那個(gè)具有相同（radix,size,heap） 值的內(nèi)存區(qū)域）上接一個(gè)雙向鏈表用來存放這些內(nèi)存區(qū)域，這個(gè)鏈表用 vm_set.list 來表示；樹上那個(gè)節(jié)點(diǎn)指向的鏈表中的第一個(gè)節(jié)點(diǎn)是表頭，用 vm_set.head 表示；vm_set.parent 用于表示是否是樹結(jié)點(diǎn)。下邊給出一個(gè)小圖示簡單說明一下 vm_set.list 和 vm_set.head。

vm_set.list 和 vm_set.head

?

通過結(jié)構(gòu) vm_area_struct 中的 vm_mm 字段可以找到對應(yīng)的 mm_struct 結(jié)構(gòu)，在該結(jié)構(gòu)中找到頁全局目錄，從而定位所有相關(guān)的頁表項(xiàng)。

反向映射實(shí)現(xiàn)

在進(jìn)行頁面回收的時(shí)候，Linux的 shrink_page_list() 函數(shù)中調(diào)用 try_to_unmap() 函數(shù)去更新所有引用了回收頁面的頁表項(xiàng)。其代碼流程如下所示：

實(shí)現(xiàn)函數(shù) try_to_unmap() 的關(guān)鍵代碼流程圖

?

函數(shù) try_to_unmap() 分別調(diào)用了兩個(gè)函數(shù) try_to_unmap_anon() 和 try_to_unmap_file()，其目的都是檢查并確定都有哪些頁表項(xiàng)引用了同一個(gè)物理頁面，但是，由于匿名頁面和文件映射頁面分別采用了不同的數(shù)據(jù)結(jié)構(gòu)，所以二者采用了不同的方法。

函數(shù) try_to_unmap_anon() 用于匿名頁面，該函數(shù)掃描相應(yīng)的 anon_vma 表中包含的所有內(nèi)存區(qū)域，并對這些內(nèi)存區(qū)域分別調(diào)用 try_to_unmap_one() 函數(shù)。

函數(shù) try_to_unmap_file() 用于文件映射頁面，該函數(shù)會(huì)在優(yōu)先級搜索樹中進(jìn)行搜索，并為每一個(gè)搜索到的內(nèi)存區(qū)域調(diào)用 try_to_unmap_one() 函數(shù)。

兩條代碼路徑最終匯合到 try_to_unmap_one() 函數(shù)中，更新引用特定物理頁面的所有頁表項(xiàng)的操作都是在這個(gè)函數(shù)中實(shí)現(xiàn)的。

代碼如下，對關(guān)鍵部分做了注釋：

static int try_to_unmap_anon(struct page *page, enum ttu_flags flags)  
{  
    struct anon_vma *anon_vma;  
    struct vm_area_struct *vma;  
    unsigned int mlocked = 0;  
    int ret = SWAP_AGAIN;  
    int unlock = TTU_ACTION(flags) == TTU_MUNLOCK;  
  
    if (MLOCK_PAGES && unlikely(unlock))  
        ret = SWAP_SUCCESS; /* default for try_to_munlock() */  
    /*如果該頁面為匿名映射，返回該頁面對應(yīng)的匿名結(jié)構(gòu)*/  
    anon_vma = page_lock_anon_vma(page);  
    if (!anon_vma)  
        return ret;  
    /*這里可以看出，vma的anon_vma_node字段鏈接到 
    anon_vma的head字段*/  
    /*掃描線性區(qū)描述符的anon_vma鏈表*/  
    list_for_each_entry(vma, &anon_vma->head, anon_vma_node) {  
        if (MLOCK_PAGES && unlikely(unlock)) {  
            if (!((vma->vm_flags & VM_LOCKED) &&  
                  page_mapped_in_vma(page, vma)))  
                continue;  /* must visit all unlocked vmas */  
            ret = SWAP_MLOCK;  /* saw at least one mlocked vma */  
        } else {  
            /*對anon_vma鏈表中的每一個(gè)vma線性區(qū)描述符 
            調(diào)用該函數(shù)*/  
            ret = try_to_unmap_one(page, vma, flags);  
            if (ret == SWAP_FAIL || !page_mapped(page))  
                break;  
        }  
        if (ret == SWAP_MLOCK) {  
            mlocked = try_to_mlock_page(page, vma);  
            if (mlocked)  
                break;  /* stop if actually mlocked page */  
        }  
    }  
  
    page_unlock_anon_vma(anon_vma);  
  
    if (mlocked)  
        ret = SWAP_MLOCK;   /* actually mlocked the page */  
    else if (ret == SWAP_MLOCK)  
        ret = SWAP_AGAIN;   /* saw VM_LOCKED vma */  
  
    return ret;  
｝  
/* 
 * Subfunctions of try_to_unmap: try_to_unmap_one called 
 * repeatedly from either try_to_unmap_anon or try_to_unmap_file. 
 */  
 /** 
    *page是一個(gè)指向目標(biāo)頁描述符的指針； 
    *vma是指向線性區(qū)描述符的指針 
    */  
static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma,  
                enum ttu_flags flags)  
{  
    struct mm_struct *mm = vma->vm_mm;  
    unsigned long address;  
    pte_t *pte;  
    pte_t pteval;  
    spinlock_t *ptl;  
    int ret = SWAP_AGAIN;  
    /*計(jì)算出待回收頁的線性地址*/  
    address = vma_address(page, vma);  
    if (address == -EFAULT)  
        goto out;  
    /*獲取線性地址對應(yīng)的頁表項(xiàng)地址*/  
    pte = page_check_address(page, mm, address, &ptl, 0);  
    if (!pte)  
        goto out;  
  
    /* 
     * 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 (!(flags & TTU_IGNORE_MLOCK)) {  
        if (vma->vm_flags & VM_LOCKED) {  
            ret = SWAP_MLOCK;  
            goto out_unmap;  
        }  
    }  
    if (!(flags & TTU_IGNORE_ACCESS)) {  
        if (ptep_clear_flush_young_notify(vma, address, pte)) {  
            ret = SWAP_FAIL;  
            goto out_unmap;  
        }  
    }  
  
    /* Nuke the page table entry. */  
    flush_cache_page(vma, address, page_to_pfn(page));  
    /*更新頁表項(xiàng)并沖刷相應(yīng)的TLB*/  
    pteval = ptep_clear_flush_notify(vma, address, pte);  
  
    /* Move the dirty bit to the physical page now the pte is gone. */  
    if (pte_dirty(pteval))/*如果是臟頁面，置位PG_dirty*/  
        set_page_dirty(page);  
  
    /* Update high watermark before we lower rss */  
    /*更新mm的hiwater_rss*/  
    update_hiwater_rss(mm);  
  
    if (PageHWPoison(page) && !(flags & TTU_IGNORE_HWPOISON)) {  
        if (PageAnon(page))  
            dec_mm_counter(mm, anon_rss);  
        else  
            dec_mm_counter(mm, file_rss);  
        set_pte_at(mm, address, pte,  
                swp_entry_to_pte(make_hwpoison_entry(page)));  
    } else if (PageAnon(page)) {/*如果是匿名頁*/  
        swp_entry_t entry = { .val = page_private(page) };  
  
        if (PageSwapCache(page)) {  
            /* 
             * Store the swap location in the pte. 
             * See handle_pte_fault() ... 
             */  
             /*保存換出位置*/  
            swap_duplicate(entry);  
            if (list_empty(&mm->mmlist)) {  
                spin_lock(&mmlist_lock);  
                if (list_empty(&mm->mmlist))  
                    /*添加到init_mm的相應(yīng)鏈表，從這里可以 
                    看出mm->mmlist為交換用的鏈表*/  
                    list_add(&mm->mmlist, &init_mm.mmlist);  
                spin_unlock(&mmlist_lock);  
            }  
            dec_mm_counter(mm, anon_rss);  
        } else if (PAGE_MIGRATION) {  
            /* 
             * Store the pfn of the page in a special migration 
             * pte. do_swap_page() will wait until the migration 
             * pte is removed and then restart fault handling. 
             */  
            BUG_ON(TTU_ACTION(flags) != TTU_MIGRATION);  
            entry = make_migration_entry(page, pte_write(pteval));  
        }  
        set_pte_at(mm, address, pte, swp_entry_to_pte(entry));  
        BUG_ON(pte_file(*pte));  
    } else if (PAGE_MIGRATION && (TTU_ACTION(flags) == TTU_MIGRATION)) {  
        /* Establish migration entry for a file page */  
        swp_entry_t entry;  
        entry = make_migration_entry(page, pte_write(pteval));  
        set_pte_at(mm, address, pte, swp_entry_to_pte(entry));  
    } else  
        dec_mm_counter(mm, file_rss);  
  
    /*斷開頁表項(xiàng)和物理頁面的關(guān)系*/  
    page_remove_rmap(page);  
    /*釋放所分配的緩存*/  
    page_cache_release(page);  
  
out_unmap:  
    pte_unmap_unlock(pte, ptl);  
out:  
    return ret;  
}  

對于給定的物理頁面來說，該函數(shù)會(huì)根據(jù)計(jì)算出來的線性地址找到對應(yīng)的頁表項(xiàng)地址，并更新頁表項(xiàng)。對于匿名頁面來說，換出的位置必須要被保存下來，以便于該頁面下次被訪問的時(shí)候可以被換進(jìn)來。并非所有的頁面都是可以被回收的，比如被 mlock() 函數(shù)設(shè)置過的內(nèi)存頁，或者最近剛被訪問過的頁面，等等，都是不可以被回收的。一旦遇上這樣的頁面，該函數(shù)會(huì)直接跳出執(zhí)行并返回錯(cuò)誤代碼。如果涉及到頁緩存中的數(shù)據(jù)，需要設(shè)置頁緩存中的數(shù)據(jù)無效，必要的時(shí)候還要置位頁面標(biāo)識符以進(jìn)行數(shù)據(jù)回寫。該函數(shù)還會(huì)更新相應(yīng)的一些頁面使用計(jì)數(shù)器，比如前邊提到的 _mapcount 字段，還會(huì)相應(yīng)地更新進(jìn)程擁有的物理頁面數(shù)目等。

PFRA具體實(shí)現(xiàn)

LRU 鏈表

在 Linux 中，操作系統(tǒng)對 LRU 的實(shí)現(xiàn)主要是基于一對雙向鏈表：active 鏈表和 inactive 鏈表，這兩個(gè)鏈表是 Linux 操作系統(tǒng)進(jìn)行頁面回收所依賴的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，每個(gè)內(nèi)存區(qū)域都存在一對這樣的鏈表。顧名思義，那些經(jīng)常被訪問的處于活躍狀態(tài)的頁面會(huì)被放在 active 鏈表上，而那些雖然可能關(guān)聯(lián)到一個(gè)或者多個(gè)進(jìn)程，但是并不經(jīng)常使用的頁面則會(huì)被放到 inactive 鏈表上。頁面會(huì)在這兩個(gè)雙向鏈表中移動(dòng)，操作系統(tǒng)會(huì)根據(jù)頁面的活躍程度來判斷應(yīng)該把頁面放到哪個(gè)鏈表上。頁面可能會(huì)從 active 鏈表上被轉(zhuǎn)移到 inactive 鏈表上，也可能從 inactive 鏈表上被轉(zhuǎn)移到 active 鏈表上，但是，這種轉(zhuǎn)移并不是每次頁面訪問都會(huì)發(fā)生，頁面的這種轉(zhuǎn)移發(fā)生的間隔有可能比較長。那些最近最少使用的頁面會(huì)被逐個(gè)放到 inactive 鏈表的尾部。進(jìn)行頁面回收的時(shí)候，Linux 操作系統(tǒng)會(huì)從 inactive 鏈表的尾部開始進(jìn)行回收。

用于描述內(nèi)存區(qū)域的 struct zone() 中關(guān)于這兩個(gè)鏈表以及相關(guān)的關(guān)鍵字段的定義如下所示：

struct zone {   
   ……  
 spinlock_t             lru_lock;     
 struct list_head    active_list;   
 struct list_head    inactive_list;   
 unsigned long       nr_active;   
 unsigned long       nr_inactive;   
   ……  
  
}   

各字段含義如下所示：

lru_lock：active_list 和 inactive_list 使用的自旋鎖。

active_list：管理內(nèi)存區(qū)域中處于活躍狀態(tài)的頁面。

inactive_list：管理內(nèi)存區(qū)域中處于不活躍狀態(tài)的頁面。

nr_active：active_list 鏈表上的頁面數(shù)目。

nr_inactive：inactive_list 鏈表上的頁面數(shù)目。

如何在兩個(gè)LRU 鏈表之間移動(dòng)頁面

Linux 引入了兩個(gè)頁面標(biāo)志符 PG_active 和 PG_referenced 用于標(biāo)識頁面的活躍程度，從而決定如何在兩個(gè)鏈表之間移動(dòng)頁面。PG_active 用于表示頁面當(dāng)前是否是活躍的，如果該位被置位，則表示該頁面是活躍的。PG_referenced 用于表示頁面最近是否被訪問過，每次頁面被訪問，該位都會(huì)被置位。Linux 必須同時(shí)使用這兩個(gè)標(biāo)志符來判斷頁面的活躍程度，假如只是用一個(gè)標(biāo)志符，在頁面被訪問時(shí)，置位該標(biāo)志符，之后該頁面一直處于活躍狀態(tài)，如果操作系統(tǒng)不清除該標(biāo)志位，那么即使之后很長一段時(shí)間內(nèi)該頁面都沒有或很少被訪問過，該頁面也還是處于活躍狀態(tài)。為了能夠有效清除該標(biāo)志位，需要有定時(shí)器的支持以便于在超時(shí)時(shí)間之后該標(biāo)志位可以自動(dòng)被清除。然而，很多 Linux 支持的體系結(jié)構(gòu)并不能提供這樣的硬件支持，所以 Linux 中使用兩個(gè)標(biāo)志符來判斷頁面的活躍程度。

Linux 2.6 中這兩個(gè)標(biāo)志符密切合作，其核心思想如下所示：

如果頁面被認(rèn)為是活躍的，則將該頁的 PG_active 置位；否則，不置位。

當(dāng)頁面被訪問時(shí)，檢查該頁的 PG_referenced 位，若未被置位，則置位之；若發(fā)現(xiàn)該頁的 PG_referenced 已經(jīng)被置位了，則意味著該頁經(jīng)常被訪問，這時(shí)，若該頁在 inactive 鏈表上，則置位其 PG_active 位，將其移動(dòng)到 active 鏈表上去，并清除其 PG_referenced 位的設(shè)置；如果頁面的 PG_referenced 位被置位了一段時(shí)間后，該頁面沒有被再次訪問，那么 Linux 操作系統(tǒng)會(huì)清除該頁面的 PG_referenced 位，因?yàn)檫@意味著這個(gè)頁面最近這段時(shí)間都沒有被訪問。

PG_referenced 位同樣也可以用于頁面從 active 鏈表移動(dòng)到 inactive 鏈表。對于某個(gè)在 active 鏈表上的頁面來說，其 PG_active 位被置位，如果 PG_referenced 位未被置位，給定一段時(shí)間之后，該頁面如果還是沒有被訪問，那么該頁面會(huì)被清除其 PG_active 位，挪到 inactive 鏈表上去。

Linux 中實(shí)現(xiàn)在 LRU 鏈表之間移動(dòng)頁面的關(guān)鍵函數(shù)如下所示（本文涉及的源代碼均是基于 Linux 2.6.18.1 版本的）：

mark_page_accessed()：當(dāng)一個(gè)頁面被訪問時(shí)，則調(diào)用該函數(shù)相應(yīng)地修改 PG_active 和 PG_referenced。

page_referenced()：當(dāng)操作系統(tǒng)進(jìn)行頁面回收時(shí)，每掃描到一個(gè)頁面，就會(huì)調(diào)用該函數(shù)設(shè)置頁面的 PG_referenced 位。如果一個(gè)頁面的 PG_referenced 位被置位，但是在一定時(shí)間內(nèi)該頁面沒有被再次訪問，那么該頁面的 PG_referenced 位會(huì)被清除。

activate_page()：該函數(shù)將頁面放到 active 鏈表上去。

shrink_active_list()：該函數(shù)將頁面移動(dòng)到 inactive 鏈表上去。

LRU 緩存

前邊提到，頁面根據(jù)其活躍程度會(huì)在 active 鏈表和 inactive 鏈表之間來回移動(dòng)，如果要將某個(gè)頁面插入到這兩個(gè)鏈表中去，必須要通過自旋鎖以保證對鏈表的并發(fā)訪問操作不會(huì)出錯(cuò)。為了降低鎖的競爭，Linux 提供了一種特殊的緩存：LRU 緩存，用以批量地向 LRU 鏈表中快速地添加頁面。有了 LRU 緩存之后，新頁不會(huì)被馬上添加到相應(yīng)的鏈表上去，而是先被放到一個(gè)緩沖區(qū)中去，當(dāng)該緩沖區(qū)緩存了足夠多的頁面之后，緩沖區(qū)中的頁面才會(huì)被一次性地全部添加到相應(yīng)的 LRU 鏈表中去。Linux 采用這種方法降低了鎖的競爭，極大地提升了系統(tǒng)的性能。

LRU 緩存用到了 pagevec 結(jié)構(gòu)，如下所示 :

struct pagevec {   
     unsigned long nr;   
     unsigned long cold;   
     struct page *pages[PAGEVEC_SIZE];   
 };  

pagevec 這個(gè)結(jié)構(gòu)就是用來管理 LRU 緩存中的這些頁面的。該結(jié)構(gòu)定義了一個(gè)數(shù)組，這個(gè)數(shù)組中的項(xiàng)是指向 page 結(jié)構(gòu)的指針。一個(gè) pagevec 結(jié)構(gòu)最多可以存在 14 個(gè)這樣的項(xiàng)（PAGEVEC_SIZE 的默認(rèn)值是 14）。當(dāng)一個(gè) pagevec 的結(jié)構(gòu)滿了，那么該 pagevec 中的所有頁面會(huì)一次性地被移動(dòng)到相應(yīng)的 LRU 鏈表上去。

用來實(shí)現(xiàn) LRU 緩存的兩個(gè)關(guān)鍵函數(shù)是 lru_cache_add() 和 lru_cache_add_active()。前者用于延遲將頁面添加到 inactive 鏈表上去，后者用于延遲將頁面添加到 active 鏈表上去。這兩個(gè)函數(shù)都會(huì)將要移動(dòng)的頁面先放到頁向量 pagevec 中，當(dāng) pagevec 滿了（已經(jīng)裝了 14 個(gè)頁面的描述符指針），pagevec 結(jié)構(gòu)中的所有頁面才會(huì)被一次性地移動(dòng)到相應(yīng)的鏈表上去。

下圖概括總結(jié)了上文介紹的如何在兩個(gè)鏈表之間移動(dòng)頁面，以及 LRU 緩存在其中起到的作用：

頁面在 LRU 鏈表之間移動(dòng)示意圖

?

其中，1 表示函數(shù) mark_page_accessed()，2 表示函數(shù) page_referenced()，3 表示函數(shù) activate_page()，4 表示函數(shù) shrink_active_list()。

PFRA具體實(shí)現(xiàn)

PFRA必須處理多種屬于用戶態(tài)進(jìn)程、磁盤高速緩存和內(nèi)存高速緩存的頁，而且必須遵照幾條試探法準(zhǔn)則。PFRA的大部分函數(shù)如下：

?

如上圖在分配VFS緩沖區(qū)或緩沖區(qū)首部時(shí)，內(nèi)核調(diào)用free_more_memory();而當(dāng)從伙伴系統(tǒng)分配一個(gè)或多個(gè)頁框時(shí)，調(diào)用try_to_free_pages()。

頁面回收關(guān)鍵代碼流程圖

?

?

上文提到 Linux 中頁面回收主要是通過兩種方式觸發(fā)的，一種是由“內(nèi)存嚴(yán)重不足”事件觸發(fā)的；一種是由后臺(tái)進(jìn)程 kswapd 觸發(fā)的，該進(jìn)程周期性地運(yùn)行，一旦檢測到內(nèi)存不足，就會(huì)觸發(fā)頁面回收操作。對于第一種情況，系統(tǒng)會(huì)調(diào)用函數(shù) try_to_free_pages() 去檢查當(dāng)前內(nèi)存區(qū)域中的頁面，回收那些最不常用的頁面。對于第二種情況，函數(shù) balance_pgdat() 是入口函數(shù)。

當(dāng) NUMA 上的某個(gè)節(jié)點(diǎn)的低內(nèi)存區(qū)域調(diào)用函數(shù) try_to_free_pages() 的時(shí)候，該函數(shù)會(huì)反復(fù)調(diào)用 shrink_zones() 以及 shrink_slab() 釋放一定數(shù)目的頁面，默認(rèn)值是 32 個(gè)頁面。如果在特定的循環(huán)次數(shù)內(nèi)沒有能夠成功釋放 32 個(gè)頁面，那么頁面回收會(huì)調(diào)用 OOM killer 選擇并殺死一個(gè)進(jìn)程，然后釋放它占用的所有頁面。函數(shù) shrink_zones() 會(huì)對內(nèi)存區(qū)域列表中的所有區(qū)域分別調(diào)用 shrink_zone() 函數(shù)，后者是從內(nèi)存回收最近最少使用頁面的入口函數(shù)。

對于定期頁面檢查并進(jìn)行回收的入口函數(shù) balance_pgdat() 來說，它主要調(diào)用的函數(shù)是 shrink_zone() 和 shrink_slab()。從上圖中我們也可以看出，進(jìn)行頁面回收的兩條代碼路徑最終匯合到函數(shù) shrink_zone() 和函數(shù) shrink_slab() 上。

函數(shù) shrink_zone()

其中，shrink_zone() 函數(shù)是 Linux 操作系統(tǒng)實(shí)現(xiàn)頁面回收的最核心的函數(shù)之一，它實(shí)現(xiàn)了對一個(gè)內(nèi)存區(qū)域的頁面進(jìn)行回收的功能，該函數(shù)主要做了兩件事情：

將某些頁面從 active 鏈表移到 inactive 鏈表，這是由函數(shù) shrink_active_list() 實(shí)現(xiàn)的。

從 inactive 鏈表中選定一定數(shù)目的頁面，將其放到一個(gè)臨時(shí)鏈表中，這由函數(shù) shrink_inactive_list() 完成。該函數(shù)最終會(huì)調(diào)用 shrink_page_list() 去回收這些頁面。

函數(shù) shrink_page_list() 返回的是回收成功的頁面數(shù)目。概括來說，對于可進(jìn)行回收的頁面，該函數(shù)主要做了這樣幾件事情，其代碼流程圖如下所示：

函數(shù) shrink_page_list() 實(shí)現(xiàn)的關(guān)鍵功能

?

?

對于匿名頁面來說，在回收此類頁面時(shí)，需要將其數(shù)據(jù)寫入到交換區(qū)。如果尚未為該頁面分配交換區(qū)槽位，則先分配一個(gè)槽位，并將該頁面添加到交換緩存。同時(shí)，將相關(guān)的 page 實(shí)例加入到交換區(qū)，這樣，對該頁面的處理就可以跟其他已經(jīng)建立映射的頁面一樣；

如果該頁面已經(jīng)被映射到一個(gè)或者多個(gè)進(jìn)程的頁表項(xiàng)中，那么必須找到所有引用該頁面的進(jìn)程，并更新頁表中與這些進(jìn)程相關(guān)的所有頁表項(xiàng)。在這里，Linux 2.6 操作系統(tǒng)會(huì)利用反向映射機(jī)制去檢查哪些頁表項(xiàng)引用了該頁面，關(guān)于反向映射的內(nèi)容在后邊會(huì)有介紹；

如果該頁面中的數(shù)據(jù)是臟的，那么數(shù)據(jù)必須要被回寫；

釋放頁緩存中的干凈頁面。

函數(shù) shrink_slab()

函數(shù) shrink_slab() 是用來回收磁盤緩存所占用的頁面的。Linux 操作系統(tǒng)并不清楚這類頁面是如何使用的，所以如果希望操作系統(tǒng)回收磁盤緩存所占用的頁面，那么必須要向操作系統(tǒng)內(nèi)核注冊 shrinker 函數(shù)，shrinker 函數(shù)會(huì)在內(nèi)存較少的時(shí)候主動(dòng)釋放一些該磁盤緩存占用的空間。函數(shù) shrink_slab() 會(huì)遍歷 shrinker 鏈表，從而對所有注冊了 shrinker 函數(shù)的磁盤緩存進(jìn)行處理。

從實(shí)現(xiàn)上來看，shrinker 函數(shù)和 slab 分配器并沒有固定的聯(lián)系，只是當(dāng)前主要是 slab 緩存使用 shrinker 函數(shù)最多。

注冊 shrinker 是通過函數(shù) set_shrinker() 實(shí)現(xiàn)的，解除 shrinker 注冊是通過函數(shù) remove_shrinker() 實(shí)現(xiàn)的。當(dāng)前，Linux 操作系統(tǒng)中主要的 shrinker 函數(shù)有如下幾種：

shrink_dcache_memory()：該 shrinker 函數(shù)負(fù)責(zé) dentry 緩存。

shrink_icache_memory()：該 shrinker 函數(shù)負(fù)責(zé) inode 緩存。

mb_cache_shrink_fn()：該 shrinker 函數(shù)負(fù)責(zé)用于文件系統(tǒng)元數(shù)據(jù)的緩存。

具體的源代碼實(shí)現(xiàn)細(xì)節(jié)有時(shí)間再做分析。后面將談?wù)摻粨Q。

　　審核編輯：湯梓紅