Linux Cache管理之radix_tree

    檔案 Cache 是檔案資料在記憶體中的副本，因此檔案 Cache 管理與記憶體管理系統和檔案系統都相關：一方面檔案 Cache 作為物理記憶體的一部分，需要參與物理記憶體的分配回收過程，另一方面檔案 Cache 中的資料來源於儲存裝置上的檔案，需要透過檔案系統與儲存裝置進行讀寫互動。從作業系統的角度考慮，檔案 Cache 可以看做是記憶體管理系統與檔案系統之間的聯絡紐帶。因此，檔案 Cache 管理是作業系統的一個重要組成部分，它的效能直接影響著檔案系統和記憶體管理系統的效能。 
    圖1描述了 Linux 作業系統中檔案 Cache 管理與記憶體管理以及檔案系統的關係示意圖。從圖中可以看到，在 Linux 中，具體檔案系統，如 ext2/ext3、jfs、ntfs 等，負責在檔案 Cache和儲存裝置之間交換資料，位於具體檔案系統之上的虛擬檔案系統VFS負責在應用程式和檔案 Cache 之間透過 read/write 等介面交換資料，而記憶體管理系統負責檔案 Cache 的分配和回收，同時虛擬記憶體管理系統(VMM)則允許應用程式和檔案 Cache 之間透過 memory map的方式交換資料。可見，在 Linux 系統中，檔案 Cache 是記憶體管理系統、檔案系統以及應用程式之間的一個聯絡樞紐。

    在 Linux 的實現中，檔案 Cache 分為兩個層面，一是 Page Cache，另一個 Buffer Cache，每一個 Page Cache 包含若干 Buffer Cache。記憶體管理系統和 VFS 只與 Page Cache 互動，記憶體管理系統負責維護每項 Page Cache 的分配和回收，同時在使用 memory map 方式訪問時負責建立對映；VFS 負責 Page Cache 與使用者空間的資料交換。而具體檔案系統則一般只與 Buffer Cache 互動，它們負責在外圍儲存裝置和 Buffer Cache 之間交換資料。Page Cache、Buffer Cache、檔案以及磁碟之間的關係如圖 2 所示，Page 結構和 buffer_head 資料結構的關係如圖 3 所示。在上述兩個圖中，假定了 Page 的大小是 4K，磁碟塊的大小是 1K。本文所講述的，主要是指對 Page Cache 的管理。 
    在 Linux 核心中，檔案的每個資料塊最多隻能對應一個 Page Cache 項，它透過兩個資料結構來管理這些 Cache 項，一個是 radix tree，另一個是雙向連結串列。Radix tree 是一種搜尋樹，Linux 核心利用這個資料結構來透過檔案內偏移快速定位 Cache 項，圖 4 是 radix tree的一個示意圖，該 radix tree 的分叉為4(22)，樹高為4，用來快速定位8位檔案內偏移。Linux(2.6.7) 核心中的分叉為 64(26)，樹高為 6(64位系統)或者 11(32位系統)，用來快速定位 32 位或者 64 位偏移，radix tree 中的每一個葉子節點指向檔案內相應偏移所對應的Cache項。 
    另一個資料結構是雙向連結串列，Linux核心為每一片物理記憶體區域(zone)維護active_list和inactive_list兩個雙向連結串列，這兩個list主要用來實現物理記憶體的回收。這兩個連結串列上除了檔案Cache之外，還包括其它匿名(Anonymous)記憶體，如行程堆疊等。

address_space，inode，基樹以及頁描述符之間的關係 
1、每個adrres_space物件對應一顆搜尋樹。他們之間的聯絡是透過address_space物件中的page_tree欄位指向該address_space物件對應的基樹。 
2、一個inode節點對應一個address_space物件，其中inode節點物件的i_mapping和i_data欄位指向相應的 address_space物件，而address_space物件的host欄位指向對應的inode節點物件。 
3、）一般情況下一個inode節點物件對應的檔案或者是塊裝置都會包含多個頁面的內容，所以一個inode物件對應多個page描述符。同一個檔案擁有的所有page描述符都可以在該檔案對應的基樹中找到。

它們之間的關係如下圖：