好久沒有更新了。。。

主要內容：

• 緩存簡介
• 頁高速緩存
• 頁回寫

1. 緩存簡介

在編程中，緩存是很常見也很有效的一種提高程序性能的機制。

linux內核也不例外，為了提高I/O性能，也引入了緩存機制，即將一部分磁盤上的數據緩存到內存中。

1.1 原理

之所以通過緩存能提高I/O性能是基于以下2個重要的原理：

1. CPU訪問內存的速度遠遠大于訪問磁盤的速度（訪問速度差距不是一般的大，差好幾個數量級）
2. 數據一旦被訪問，就有可能在短期內再次被訪問（臨時局部原理）

1.2 策略

緩存的創建和讀取沒什么好說的，無非就是檢查緩存是否存在要創建或者要讀取的內容。

但是寫緩存和緩存回收就需要好好考慮了，這里面涉及到「緩存內容」和「磁盤內容」同步的問題。

1.2.1 「寫緩存」常見的有3種策略

• 不緩存(nowrite) :: 也就是不緩存寫操作，當對緩存中的數據進行寫操作時，直接寫入磁盤，同時使此數據的緩存失效
• 寫透緩存(write-through) :: 寫數據時同時更新磁盤和緩存
• 回寫(copy-write or write-behind) :: 寫數據時直接寫到緩存，由另外的進程(回寫進程)在合適的時候將數據同步到磁盤

3種策略的優缺點如下：

1.2.2 「緩存回收」的策略

• 最近最少使用(LRU) :: 每個緩存數據都有個時間戳，保存最近被訪問的時間。回收緩存時首先回收時間戳較舊的數據。
• 雙鏈策略(LRU/2) :: 基于LRU的改善策略。具體參見下面的補充說明

補充說明(雙鏈策略):

雙鏈策略其實就是 LRU(Least Recently Used) 算法的改進版。

它通過2個鏈表(活躍鏈表和非活躍鏈表)來模擬LRU的過程，目的是為了提高頁面回收的性能。

頁面回收動作發生時，從非活躍鏈表的尾部開始回收頁面。

雙鏈策略的關鍵就是頁面如何在2個鏈表之間移動的。

雙鏈策略中，每個頁面都有2個標志位，分別為

PG_active - 標志頁面是否活躍，也就是表示此頁面是否要移動到活躍鏈表

PG_referenced - 表示頁面是否被進程訪問到

頁面移動的流程如下：

1. 當頁面第一次被被訪問時，PG_active 置為1，加入到活動鏈表
2. 當頁面再次被訪問時，PG_referenced 置為1，此時如果頁面在非活動鏈表，則將其移動到活動鏈表，并將PG_active置為1，PG_referenced 置為0
3. 系統中 daemon 會定時掃描活動鏈表，定時將頁面的 PG_referenced 位置為0
4. 系統中 daemon 定時檢查頁面的 PG_referenced，如果 PG_referenced=0，那么將此頁面的 PG_active 置為0，同時將頁面移動到非活動鏈表

參考：Linux 2.6 中的頁面回收與反向映射

2. 頁高速緩存

故名思義，頁高速緩存中緩存的最小單元就是內存頁。

但是此內存頁對應的數據不僅僅是文件系統的數據，可以是任何基于頁的對象，包括各種類型的文件和內存映射。

2.1 簡介

頁高速緩存緩存的是具體的物理頁面，與前面章節中提到的虛擬內存空間(vm_area_struct)不同，假設有進程創建了多個 vm_area_struct 都指向同一個文件，

那么這個 vm_area_struct 對應的 頁高速緩存只有一份。

也就是磁盤上的文件緩存到內存后，它的虛擬內存地址可以有多個，但是物理內存地址卻只能有一個。

為了有效提高I/O性能，頁高速緩存要需要滿足以下條件：

1. 能夠快速檢索需要的內存頁是否存在
2. 能夠快速定位 臟頁面(也就是被寫過，但還沒有同步到磁盤上的數據)
3. 頁高速緩存被并發訪問時，盡量減少并發鎖帶來的性能損失

下面通過分析內核中的相應的結構體，來了解內核是如何提高 I/O性能的。

2.2 實現

實現頁高速緩存的最重要的結構體要算是 address_space ，在 <linux/fs.h> 中

struct address_space {
    struct inode        *host;        /* 擁有此 address_space 的inode對象 */
    struct radix_tree_root    page_tree;    /* 包含全部頁面的 radix 樹 */
    spinlock_t        tree_lock;    /* 保護 radix 樹的自旋鎖 */
    unsigned int        i_mmap_writable;/* VM_SHARED 計數 */
    struct prio_tree_root    i_mmap;        /* 私有映射鏈表的樹 */
    struct list_head    i_mmap_nonlinear;/* VM_NONLINEAR 鏈表 */
    spinlock_t        i_mmap_lock;    /* 保護 i_map 的自旋鎖 */
    unsigned int        truncate_count;    /* 截斷計數 */
    unsigned long        nrpages;    /* 總頁數 */
    pgoff_t            writeback_index;/* 回寫的起始偏移 */
    const struct address_space_operations *a_ops;    /* address_space 的操作表 */
    unsigned long        flags;        /* gfp_mask 掩碼與錯誤標識 */
    struct backing_dev_info *backing_dev_info; /* 預讀信息 */
    spinlock_t        private_lock;    /* 私有 address_space 自旋鎖 */
    struct list_head    private_list;    /* 私有 address_space 鏈表 */
    struct address_space    *assoc_mapping;    /* 緩沖 */
    struct mutex        unmap_mutex;    /* 保護未映射頁的 mutux 鎖 */
} __attribute__((aligned(sizeof(long))));

補充說明：

1. inode - 如果 address_space 是由不帶inode的文件系統中的文件映射的話，此字段為 null
2. page_tree - 這個樹結構很重要，它保證了頁高速緩存中數據能被快速檢索到，臟頁面能夠快速定位。
3. i_mmap - 根據 vm_area_struct，能夠快速的找到關聯的緩存文件(即 address_space)，前面提到過， address_space 和 vm_area_struct 是 一對多的關系。
4. 其他字段主要是提供各種鎖和輔助功能

此外，對于這里出現的一種新的數據結構 radix 樹，進行簡要的說明。

radix樹通過long型的位操作來查詢各個節點， 存儲效率高，并且可以快速查詢。

linux中 radix樹相關的內容參見： include/linux/radix-tree.h 和 lib/radix-tree.c

下面根據我自己的理解，簡單的說明一下radix樹結構及原理。

2.2.1 首先是 radix樹節點的定義

/* 源碼參照 lib/radix-tree.c */
struct radix_tree_node {
    unsigned int    height;        /* radix樹的高度 */
    unsigned int    count;      /* 當前節點的子節點數目 */
    struct rcu_head    rcu_head;   /* RCU 回調函數鏈表 */
    void        *slots[RADIX_TREE_MAP_SIZE]; /* 節點中的slot數組 */
    unsigned long    tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; /* slot標簽 */
};

弄清楚 radix_tree_node 中各個字段的含義，也就差不多知道 radix樹是怎么一回事了。

• height   表示的整個 radix樹的高度（即葉子節點到樹根的高度）， 不是當前節點到樹根的高度
• count    這個比較好理解，表示當前節點的子節點個數，葉子節點的 count=0
• rcu_head RCU發生時觸發的回調函數鏈表
• slots    每個slot對應一個子節點（葉子節點）
• tags     標記子節點是否 dirty 或者 wirteback

2.2.2 每個葉子節點指向文件內相應偏移所對應的緩存頁

比如下圖表示 0x000000 至 0x11111111 的偏移范圍，樹的高度為4 （圖是網上找的，不是自己畫的）

2.2.3 radix tree 的葉子節點都對應一個二進制的整數，不是字符串，所以進行比較的時候非常快

其實葉子節點的值就是地址空間的值(一般是long型)

3. 頁回寫

由于目前linux內核中對于「寫緩存」采用的是第3種策略，所以回寫的時機就顯得非常重要，回寫太頻繁影響性能，回寫太少容易造成數據丟失。

3.1 簡介

linux 頁高速緩存中的回寫是由內核中的一個線程(flusher 線程)來完成的，flusher 線程在以下3種情況發生時，觸發回寫操作。

1. 當空閑內存低于一個閥值時

    空閑內存不足時，需要釋放一部分緩存，由于只有不臟的頁面才能被釋放，所以要把臟頁面都回寫到磁盤，使其變成干凈的頁面。

2. 當臟頁在內存中駐留時間超過一個閥值時

   確保臟頁面不會無限期的駐留在內存中，從而減少了數據丟失的風險。

3. 當用戶進程調用 sync() 和 fsync() 系統調用時

   給用戶提供一種強制回寫的方法，應對回寫要求嚴格的場景。

頁回寫中涉及的一些閥值可以在 /proc/sys/vm 中找到

下表中列出的是與 pdflush(flusher 線程的一種實現) 相關的一些閥值

3.2 實現

flusher線程的實現方法隨著內核的發展也在不斷的變化著。下面介紹幾種在內核發展中出現的比較典型的實現方法。

1. 膝上型計算機模式

這種模式的意圖是將硬盤轉動的機械行為最小化，允許硬盤盡可能長時間的停滯，以此延長電池供電時間。

該模式通過 /proc/sys/vm/laptop_mode 文件來設置。(0 - 關閉該模式  1 - 開啟該模式)

2. bdflush 和 kupdated (2.6版本前 flusher 線程的實現方法)

bdflush 內核線程在后臺運行，系統中只有一個 bdflush 線程，當內存消耗到特定閥值以下時，bdflush 線程被喚醒

kupdated 周期性的運行，寫回臟頁。

bdflush 存在的問題：

整個系統僅僅只有一個 bdflush 線程，當系統回寫任務較重時，bdflush 線程可能會阻塞在某個磁盤的I/O上，

導致其他磁盤的I/O回寫操作不能及時執行。

3. pdflush (2.6版本引入)

pdflush 線程數目是動態的，取決于系統的I/O負載。它是面向系統中所有磁盤的全局任務的。

pdflush 存在的問題：

pdflush的數目是動態的，一定程度上緩解了 bdflush 的問題。但是由于 pdflush 是面向所有磁盤的，

所以有可能出現多個 pdflush 線程全部阻塞在某個擁塞的磁盤上，同樣導致其他磁盤的I/O回寫不能及時執行。

4. flusher線程 (2.6.32版本后引入)

flusher線程改善了上面出現的問題：

首先，flusher 線程的數目不是唯一的，這就避免了 bdflush 線程的問題

其次，flusher 線程不是面向所有磁盤的，而是每個 flusher 線程對應一個磁盤，這就避免了 pdflush 線程的問題