歡迎光臨
每天分享高質量文章

Linux Cache管理之radix_tree

Linux Cache管理之radix_tree

檔案Cache的地位和作用▼

    檔案 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 是記憶體管理系統、檔案系統以及應用程式之間的一個聯繫樞紐。

檔案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)記憶體,如行程堆棧等。

mmap▼

內核中radix_tree結構▼

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描述符都可以在該檔案對應的基樹中找到。

它們之間的關係如下圖:

    page cache是VFS的一部分,buffer cache是塊設備驅動的一部分,或者說page cache是面向用戶IO的cache,buffer cache是面向塊設備IO的cache,page cache按照檔案的邏輯頁進行緩衝,buffer cache按照檔案的物理塊進行緩衝。

本文轉自:

https://blog.csdn.net/lsgqjh/article/details/76592495

    赞(0)

    分享創造快樂