投機性缺頁異常處理

背景

大家都知道避免缺頁異常帶來的性能損耗最好的辦法是避免産生缺頁（我說了一句廢話。。。）。但實際上使用者态程式根本做不到這一點，而對于一個多線程程式而言這個問題尤其嚴重，是以核心就需要想盡辦法将缺頁異常處理帶來的額外開銷降到最低。于是乎最近一個八年老坑Speculative page-fault handling終于可能要到被考慮合并進主線的階段了。

Linux核心使用mmapsem來串行化對描述程序位址空間的資料結構的通路，而缺頁異常的處理也需要通路mmapsem。是以多線程程式在通路記憶體方面的能力是嚴重受到擷取mmapsem讀/寫信号量的能力制約的。而由于線程數很多所産生的缺頁異常就更加容易發生資源争用。為了解決這個問題，核心研發人員提出了Speculative page-fault handling，它的基本思路是當我們對程序的virtual memory areas (VMA) 進行通路的時候不持有mmapsem，進而實作無鎖讀通路。

Speculative page-fault handling的patch，第一次出現是在2009年（八年了，核心研發的效率啊！），之後斷斷續續地，多個核心開發者又對它進行了讨論和改進，但相關工作一直沒有被merge進主線。Laurent Dufour最近重新開機了這些工作，fix了這些patch的bug，添加上了自己的改進并重新送出到了郵件清單。之後大家就開始在linux-kernel的郵件清單上對這份工作展開了活躍的讨論。一個令人激動的事實是，在Dufour的性能測試報告中，當我們啟用了Speculative page-fault handling後，讀取一個2TB的資料庫會得到20%的速度提升。

如上所述，mmapsem是多線程程式一個顯著的資源争用點。而我們關注的缺頁處理也需要通路程序的VMA結構。VMA結構描述了程序的記憶體布局，是以要求缺頁處理時需要持有mmapsem。即使隻要求讀鎖（我們讨論的缺頁處理即為這種情況），我們也會頻繁通路mmapsem，進而導緻緩存颠簸（cache-line bouncing）以及性能下降。Speculative page-fault handling背後的思想是，通過避免在缺頁異常進行中使用mmapsem，無鎖周遊VMA，進而提高記憶體通路的性能。但是我們不得不說，設計和使用mmap_sem就是為了解決一些不好解決的同步問題，現在不持有鎖了，這些問題就得想其他的辦法了。

問題和解法

第一個問題是：假如不持有mmapsem，當我們處理缺頁異常的時候，如果對應的VMA描述中的區域發生了變化怎麼辦？應對這個問題的政策是，盡可能把與VMA狀态無關的工作都先做掉，然後在直接改變程序位址空間之前，再檢查一下VMA是否發生了改變。舉例來說，當我們從磁盤讀資料到記憶體的時候，我們可以先配置設定一個記憶體頁，将資料讀取出來，這些階段都是不需要mmapsem的，而當我們把這個頁加入到程序位址空間的時候我們需要一個一緻的VMA，是以這個時候是需要拿mmap_sem的。

對于這個問題的解決，核心有一直都有一個機制叫seqlock。是以這套patch把seqlock添加到了VMA結構中，在所有改變VMA的地方都遞增sequence count。Speculative fault-handling代碼便可以在工作之前記錄sequence number，并且在工作結束後檢查sequence number有沒有改變。如果sequence number改變了，我們可以知道VMA也改變了，投機進行的工作就當做白做了。這種情況就是失敗的投機嘗試，此時隻能繞過Speculative fault-handling，并按照老辦法重試處理缺頁異常。

第二個問題要更棘手一些，沒有持有mmap_sem，在處理缺頁異常的時候，一個VMA可能會完全消失。這種情況可以使用Read-Copy-Update(RCU)來避免，使用RCU，可以保證在處理缺頁異常的時候，VMA結構是存在的。當然因為缺頁異常處理過程中的很多操作都可能會睡眠，是以我們要使用SRCU（RCU的一種可睡眠的變體）來串行化VMA的更新。

進行Speculative fault-handling時，核心會先無鎖地周遊頁表，同時持有一個細粒度的頁表鎖。然後調用srcureadlock()以便進行VMA查找。最後檢查VMA的write-sequence count。未來遵守核心的鎖使用順序，我們需要先放棄頁表鎖，然後使用VMA來找到發生故障的位址所在的頁。一旦頁找到了，VMA需要重新驗證一次，進行頁表周遊、擷取頁表鎖，并檢查VMA的sequence number是否沒有改變。如果沒有改變，那麼頁被安裝到頁表裡，頁表鎖也被釋放。

speculative page-fault handling的另一個難題與Translation lookaside buffer(TLB)的失效有關。很多行為，例如unmapping一個記憶體區域，都會導緻TLB的失效。失效TLB的過程是發送處理期間中斷(IPI)來告訴每個CPU失效它自己的TLB。unmap的調用路徑可能會在鎖住特定的頁表項期間進行TLB失效操作。此時，Speculative-fault-handling可能在關中斷的情況下嘗試擷取頁表鎖，如果這種嘗試的頁表項被鎖在unmap的路徑上，處理器會在關中斷的情況下自旋，是以永遠收不到TLB失效的IPI，這将導緻死鎖。這是比mmap_sem競争更壞的情況。了解清楚這個問題後，解決辦法也顯而易見：在speculative路徑使用trylock操作擷取鎖，如果擷取鎖失敗，則立即fall back到傳統page fault處理流程上。

曆史

第一套speculative page fault相關的patch由Hiroyuki Kamezawa在2009年釋出，接下來Peter Zijlstra組織了核心社群的讨論并開發了他自己的實作，他使用了RCU來完成無鎖讀VMA。不過Peter的實作也有一些問題，是以沒能被合并進主幹。到了2014年，由于很多之前導緻他的patch不能工作的問題都已經解決了，是以Peter Zijlstra重新開機了這個想法。然而，讨論再次無疾而終。今年6月，Dufourt在最新核心移植了PeterZ的patch，同時也添加了自己的一些patch，然後重新發送到了郵件清單。不過Dufour提到，他的patch集裡仍然存在TLB失效的問題。

抛開前面兩個廢棄掉的Speculative page fault的實作不說，這套patch目前的進展已經非常不錯了，是以也許社群可以認真考慮一下合并進核心主線的事情。Dufour的測試中關于資料庫讀取性能的提高也引起核心其他開發者，如Michal Hocko的注意，Hocko追問Dufour是否在别的benchmark，例如kernbench或其他的高度多線程的測試負載上測試過這套patch的收益。作為回應，今年8月8日Dufour給出了很多不同benchmark的測試結果，顯示了針對不同的測試，結果也有差異（有的提升顯著，有的基本沒有提升）。

到此為止，這套patch的主要問題已經都解決了。鑒于speculative page-fault handling對于部分測試負荷有着顯著的性能提升，在這份工作最初的想法浮出水面八年後，我們有理由相信這份工作有望在不遠的未來被合并。希望更多的應用能夠最終收益。