CSE506: Linux Page Cache

Page Cache
Page cache 的主要功能是當作files on disk的快取.  每個on disk file都有一個相對映的page cache (a radix tree), 存取file的最小單位是4K page size, 每當從disk存取後就會被存在page cache裡面.
當要讀取檔案時, find_get_page()會要求輸入inode跟index, index為此file address space裡面的offset. Linux kernel會根據此index去搜尋radix tree來獲取相對映的phyiscal page. 若此page不存在於page cache, 則必須要從disk 裡面重新讀出來.

Recap: Memory用途
1. Process virtual memory, 2. File, 3. I/O mapping, and 4. device buffer.


Note:
- Address space有很多種
1. Virtual address space: 4G,  anonymous, (VM area struct, vma)
2. physical address space: depends on the size of your physical memory, and
3. file address space: offset from the head of the file
- 每個inode有自己的page cache
- 當file size超過4G時, file address space就無法用32 bits address space來表示, 此時就需要64bits or concatenation of registers.

Radix tree
對Process來說, linux使用page table來管理virtual to physical mapping. 對file來說, linux使用radix tree.  (特性: virtual address一定是0-4G, 但file size可大可小).
"In order to perform page cache lookup efficiently, Linux 2.6 makes use of a large set of search trees, one for each address_space object. "
Radix tree利用file address的prefix來找到對應的page.  Page cache是由一個radix tree來儲存, 每個node含有64個leaves, 最後指向physical page.
- Branching factor: 64
- TRIE: prefix tree. Rather than storing the entire key in the node, traversal of parent builds a prefix, node just stores suffix.
- height:1 , size = 64 * 4K  = 256K, height:2, 64*64*4K = 16M

Positioning:
一個file address的前12 bit (4K)會先被拿掉, 之後每六個bit代表一個radix tree level的index.

from ref1:

Buffer heads (BH) 15.2
(Mapping pages to disk blocks)
需要buffer head的原因是因為disk每個單位是512byte (sector), 而OS的單位是4K byte. 因此每個page中都含有8個buffer cache. Linux kernel利用buffer_head來做housekeeping. 當寫入範圍小於一個sector時,此page cache會被mark dirty, 但update only the BH in the disk, not the whole page containing 8 buffer.
from ref2:

Example: write() system call for first 5 bytes
1. Look up first page in radix tree
2. Modify page, mark dirty
3. Only mark first buffer head dirty

Raw device caching:
Disk 也可以有自己radix tree + address space!

Page cache v.s Page table
相對於Process address space (4K), page cache 是用來cache on disk file. 而4K的virtual address 是利用page table (10bits for page directory, 10bits for page table, and 12 bits for offset.)

如下圖, page cache處理的是從address space region到backing store 的cache (左半部), 而page table處理的是virtual address space mapping到physical page frame.

review page table from ref3:

Linux represents portions of a process with a vm_area_struct, or vma. 利用red-black tree來管理mapping.  from ref4

Reference:
1. Understanding the Linux Kernel, Chapter 15
2. http://www.ibm.com/developerworks/cn/linux/l-cache/index.html
3. Professional Linux Kernel architecture
4. CSE506 slide, Don Porter