Page Cache與Page回寫詳述

綜述

Page cache是通過將磁碟中的資料快取到記憶體中，從而減少磁碟I/O操作，從而提高效能。此外，還要確保在page cache中的資料更改時能夠被同步到磁碟上，後者被稱為page回寫（page writeback）。一個inode對應一個page cache物件，一個page cache物件包含多個物理page。

對磁碟的資料進行快取從而提高效能主要是基於兩個因素：第一，磁碟存取的速度比記憶體慢好幾個數量級（毫秒和納秒的差距）。第二是被存取過的資料，有很大概率會被再次存取。

Page Cache

Page cache由記憶體中的物理page組成，其內容對應磁碟上的block。page cache的大小是動態變化的，可以擴大，也可以在記憶體不足時縮小。cache快取的儲存裝置被稱為後備儲存（backing store），注意我們在block I/O中提到的：一個page通常包含多個block，這些block不一定是連續的。

讀Cache

當核心發起一個讀請求時（例如進程發起read()請求），首先會檢查請求的資料是否快取到了page cache中，如果有，那麼直接從記憶體中讀取，不需要存取磁碟，這被稱為cache命中（cache hit）。

如果cache中沒有請求的資料，即cache未命中（cache miss），就必須從磁碟中讀取資料。然後核心將讀取的資料快取到cache中，這樣後續的讀請求就可以命中cache了。page可以只快取一個檔案部分的內容，不需要把整個檔案都快取進來。

寫Cache

當核心發起一個寫請求時（例如進程發起write()請求），同樣是直接往cache中寫入，後備儲存中的內容不會直接更新。核心會將被寫入的page標記為dirty，並將其加入dirty list中。核心會周期性地將dirty list中的page寫回到磁碟上，從而使磁碟上的資料和記憶體中快取的資料一致。

Cache回收

Page cache的另一個重要工作是釋放page，從而釋放記憶體空間。cache回收的任務是選擇合適的page釋放，並且如果page是dirty的，需要將page寫回到磁碟中再釋放。理想的做法是釋放距離下次存取時間最久的page，但是很明顯，這是不現實的。下面先介紹LRU演算法，然後介紹基於LRU改進的Two-List策略，後者是Linux使用的策略。

LRU演算法

LRU（least rencently used)演算法是選擇最近一次存取時間最靠前的page，即乾掉最近沒被光顧過的page。原始LRU演算法存在的問題是，有些檔案只會被存取一次，但是按照LRU的演算法，即使這些檔案以後再也不會被存取了，但是如果它們是剛剛被存取的，就不會被選中。

Two-List策略

Two-List策略維護了兩個list，active list 和 inactive list。在active list上的page被認為是hot的，不能釋放。只有inactive list上的page可以被釋放的。首次快取的資料的page會被加入到inactive list中，已經在inactive list中的page如果再次被存取，就會移入active list中。兩個連結串列都使用了偽LRU演算法維護，新的page從尾部加入，移除時從頭部移除，就像佇列一樣。如果active list中page的數量遠大於inactive list，那麼active list頭部的頁面會被移入inactive list中，從而位置兩個表的平衡。

Page Cache在Linux中的具體實現

address_space結構

核心使用address_space結構來表示一個page cache，address_space這個名字起得很糟糕，叫page_ache_entity可能更合適。下面是address_space的定義

struct address_space {
    struct inode            *host;              /* owning inode */
    struct radix_tree_root  page_tree;          /* radix tree of all pages */
    spinlock_t              tree_lock;          /* page_tree lock */
    unsigned int            i_mmap_writable;    /* VM_SHARED ma count */
    struct prio_tree_root   i_mmap;             /* list of all mappings */
    struct list_head        i_mmap_nonlinear;   /* VM_NONLINEAR ma list */
    spinlock_t              i_mmap_lock;        /* i_mmap lock */
    atomic_t                truncate_count;     /* truncate re count */
    unsigned long           nrpages;            /* total number of pages */
    pgoff_t                 writeback_index;    /* writeback start offset */
    struct address_space_operations *a_ops;     /* operations table */
    unsigned                long flags;         /* gfp_mask and error flags */
    struct backing_dev_info *backing_dev_info;  /* read-ahead information */
    spinlock_t              private_lock;       /* private lock */
    struct list_head        private_list;       /* private list */
    struct address_space    *assoc_mapping;     /* associated buffers */
};

其中 host域指向對應的inode物件，host有可能為NULL，這意味著這個address_space不是和一個檔案關聯，而是和swap area相關，swap是Linux中將匿名記憶體（比如進程的堆、棧等，沒有一個檔案作為back store）置換到swap area（比如swap分割區）從而釋放實體記憶體的一種機制。page_tree儲存了該page cache中所有的page，使用基數樹(radix Tree)來儲存。i_mmap是儲存了所有對映到當前page cache（物理的）的虛擬記憶體區域（VMA）。nrpages是當前address_space中page的數量。

address_space操作函數

address_space中的a_ops域指向操作函數表（struct address_space_operations），每個後備儲存都要實現這個函數表，比如ext3檔案系統在fs/ext3/inode.c中實現了這個函數表。

核心使用函數表中的函數管理page cache，其中最重要的兩個函數是readpage() 和writepage()

readpage()函數

readpage()首先會呼叫find_get_page(mapping, index)在page cache中尋找請求的資料，mapping是要尋找的page cache物件，即address_space物件，index是要讀取的資料在檔案中的偏移量。如果請求的資料不在該page cache中，那麼核心就會建立一個新的page加入page cache中，並將要請求的磁碟資料快取到該page中，同時將page返回給呼叫者。

writepage() 函數

對於檔案對映（host指向一個inode物件），page每次修改後都會呼叫SetPageDirty（page）將page標識為dirty。（個人理解swap對映的page不需要dirty，是因為不需要考慮斷電丟失資料的問題，因為記憶體的資料斷電時預設就是會失去的）核心首先在指定的address_space尋找目標page，如果沒有，就分配一個page並加入到page cache中，然後核心發起一個寫請求將資料從使用者空間拷入核心空間，最後將資料寫入磁碟中。（對從使用者空間拷貝到核心空間不是很理解，後期會重點學習Linux讀、寫檔案的詳細過程然後寫一篇詳細的blog介紹）

Buffer Cache

在Block I/O的文章中提到用於表示記憶體到磁碟對映的buffer_head結構，每個buffer-block對映都有一個buffer_head結構，buffer_head中的b_assoc_map指向了address_space。在Linux2.4中，buffer cache和 page cache之間是獨立的，前者使用老版本的buffer_head進行儲存，這導致了一個磁碟block可能在兩個cache中同時存在，造成了記憶體的浪費。2.6核心中將兩者合併到了一起，使buffer_head只儲存buffer-block的對映資訊，不再儲存block的內容。這樣保證一個磁碟block在記憶體中只會有一個副本，減少了記憶體浪費。

Flusher執行緒群（Flusher Threads）

Page cache推遲了檔案寫入後備儲存的時間，但是dirty page最終還是要被寫回磁碟的。

核心在下面三種情況下會進行會將dirty page寫回磁碟：

• 使用者進程呼叫sync() 和 fsync()系統呼叫
• 空閒記憶體低於特定的閾值（threshold）
• Dirty資料在記憶體中駐留的時間超過一個特定的閾值

執行緒群的特點是讓一個執行緒負責一個儲存裝置（比如一個磁碟驅動器），多少個儲存裝置就用多少個執行緒。這樣可以避免阻塞或者競爭的情況，提高效率。當空閒記憶體低於閾值時，核心就會呼叫wakeup_flusher_threads()來喚醒一個或者多個flusher執行緒，將資料寫回磁碟。為了避免dirty資料在記憶體中駐留過長時間（避免在系統崩潰時丟失過多資料），核心會定期喚醒一個flusher執行緒，將駐留時間過長的dirty資料寫回磁碟。