Page Frame Reclamation in Linux kernel

Page Replacement Policy

Linux 核心 當中也有使用到 LRU-based algorithm ，但他不是嚴格定義的 LRU 因為它維護的 LRU lists 並非嚴格的 LRU order 。 LRU lists 在 Linux 核心 當中分為兩種， active_list 和 inactive_list ， active_list 當中包含了 working set 的行程，而 inactive_set 包含了被回收的行程。這此描述的 Page Replacement Policy 適用於所有行程，不管是 active_list 或 inactive_list 當中行程的 page 都可以被回收，而非只有 faulting process 的 page 才會被回收。

這裡維護的兩個 lists 十分類似於 LRU 2Q ， page 被建立後會先被放在一個 FIFO queue 稱為 A1 ，如果他們被使用到 (referenced) ，則把他移動到 LRU managed list 稱為 Am 。事實上在 Linux 核心 當中的 Am 比起 LRU algorithm 更像是使用 Clock algorithm ，大小和 active_list 相同，如果 page 移動到此 list 的最尾端，則檢查 referenced flag ，如果該 flag 已被設定，則會把該 page 移動到 list 最前端並檢查下一個 page ，如果 flag 被清除則把該 page 移動到 inactive_list 。

理論上的 LRU algorithm 跟 Linux 核心 當中使用的演算法不同的主要原因是因為每個行程的記憶體空間大小不是固定的，不遵守 inclusion property ，所以在 lists 當中 page 的位置其實是由 list 大小決定的，而非最近存取的時間。

原文中有以下這段話

As a final nail in the stack algorithm coffin, the lists are almost ignored when paging out from processes as pageout decisions are related to their location in the virtual address space of the process rather than the location within the page lists.

stack algorithm 在 Operating Systems: Advanced Concepts 當中有提及，此處是說 page 是否被替換掉的決定並非由 page 在 lists 當中的位置決定，而是行程的 virtual address space 。

Page Cache

Page Cache 是以下四種類型的 page 的集合

• page that were faulted in as a result of reading a memory mapped file
• blocks read from a block device or filesystem are packed into speical pages called buffer pages
• anonymous pages exist in a special aspect of the page cache when slots are allocated in the backing storage for page-out.
• pages belonging to shared memory regions are treated in a similar fashion to anonymous pages. The only difference is that shared pages are added to the swap cache and space reserved in backing storage immediately after the first write to the page.

設計此種 cache 的理由是為了減少非必要的 disk reads 。從 disk 當中讀取的 pages 都會被存在 page hash table 。

Linux kernel code section

/include/linux/lru_cache.h
/lib/lru_cache.c

Explanation

閱讀 /include/linux/lru_cache.h 的註解，當我們想要 "cool down" 某個正在 active set 當中的記憶體區域時，我們使用 LRU policy ，然後才能 "heat" 之前沒用到的區域。實際上它只會追蹤在 active set 當中的物件。
使用到的情境有以下幾種

• 從 local 複製資料到 disk
• Recovery after replication node failure ，則進行 crash recovery ，但我們不知道哪些區塊有被成功複製哪些沒有，但我們又不想全部重新複製，所以我們需要利用 "write intent log" ，實作方式可以利用 on-disk bitmap 。
• Recovery after replication link failure ，此情況下我們需要把全部被改變的 block 都 resync ，追蹤這些區塊狀態的方式可以利用 "dirty bitmap" 來實作。

Write intent log information

有三種實作方法

• Chunk dirtying
  把 on-disk "dirty bitmap" 拿來重新使用，當作 "write-intent" bitmap 。為了減少改動 write-intent log 的頻率，我們可以一次對 on-disk bitmap 的 chuncks 進行 dirty 的操作，同時保持 in-memory "dirty" bitmap as clean as possible ，只有當 "hot" area "cools down" 時才把資料寫入 on-disk bitmap 。
• Explicit write intent bitmap
  在原本的 fine grained dirty bitmap 以外再另外用一個 bitmap 來當作 write-intent log 用途。
• Activity log
  從一個空集合開始，寫下變為 "hot" 的 region number 或那些已經 "cool down" 的區域。利用ring buffer 紀錄 active set 的變化，我們利用 round-robin 的方式，不只紀錄實際變更的行為，也紀錄沒有變更的成員，利用固定數量的 slots (可以利用 index 儲存) 並且每個 index 代表對應的區域號碼。
  每個 transaction 我們都會把 label 變化記錄下來 (index: -old_label, +new_label) ，並且紀錄 (index, label) pair 。若 ring buffer 夠大則每次 crash recovery 時我們都能精準地將整個 active set 重建。是否足夠大則由 active objects 的最大值還有紀錄 (index: current_label) 的 sliding window 的大小來決定。

目前每次單一的 label change 就需要一個 activity log transaction ，這樣跟 dirty chunks of bitmap 的實作方法比起來沒有好多少。未來會嘗試支援 multiple changes per transaction ，如此一來可以將數次對 bitmap 的改變整合成一次對 activity log ring buffer 的 transaction 。