一 背景
自電子計算機誕生以來，記憶體性能一直是行業關心的重點。 記憶體也随着摩爾定律，在大小和速度上一直增長。 現在的阿裡雲伺服器動辄單機接近TB的記憶體大小，加上數以百記的CPU數量也着實考驗作業系統的資源管理能力。
作為世間最流行的作業系統Linux， 核心使用LRU, Last Recent Used 連結清單來管理全部使用者使用的記憶體，用一組連結清單串聯起一個個的記憶體頁，并且使用lru lock來保護連結清單的完整性。
但是都因為各種原因被linux 核心拒絕。
二 尋找解決方案
通過仔細的觀察發現， 核心在2008年引進記憶體組-memcg以來， 系統單一的lru lists已經分成了每個記憶體組一個lru list， 由每個記憶體組單獨管理自己的lru lists。 那麼按道理lru lock的contention應該有所減小啊？ 為什麼還是經常在内部伺服器觀察到lru lock hot引起的sys 高？
原來， 核心在引入per memcg lru lists後，并沒有使用per memcg lru lock， 還在使用舊的全局lru lock 來管理全部memcg lru lists. 這造成了本來可以自治的memcg A， 卻要等待memcg B 釋放使用的lru lock。然後A拿起的lru lock又造成 memcg C的等待。。。
那麼把全局lru lock拆分到每一個memcg中， 不是可以理所當然的享受到了memcg獨立的好處了嗎？ 這樣每個memcg 都不會需要等待其他memcg 釋放lru lock。 鎖競争限制在每個memcg 内部了。
要完成lru lock 拆分，首先要知道lru lock 保護了多少對象， 通常情況中， page lru lock需要保護lru list完整性， 這個是必須的。 與lru list相關的還有page flags中的lru bit，這個lru bit用作頁是否在lru list存在的訓示器， 可以避免查表才能知道頁是否在list中。 那麼lru lock保護它也說的通。
但是lru lock 看起來還有一些奇怪的保護對象，承擔了一些不屬于它的任務：
1， PageMlock bit，保護 munlock_vma 和split_huge_page 沖突，
其實， 上述2個函數在調用鍊中都需要 page lock， 是以沖突可以完全由page lock來保證互斥。這裡lru lock使用屬于多餘。
2， pagecache xa_lock和memcg->move_lock,
xa_lock并沒有需要lru lock保護的場景，這個保護也是多餘。 相反，lru lock放到xa_lock 之下， 符合xa_lock/lock_page_memcg, 的使用次序。 反而可以優化 lru lock 和 memcg move_lock的關系。
3， lru bit in page_idle_get_page, 用在這裡是因為擔心 page_set_anon_rmap中， mapping 被提前預取通路，造成異常。 用memory barrier 方式可以避免這個預取， 是以可以在page idle中撤掉lru lock.
+ WRITE_ONCE(page->mapping, (struct address_space *) anon_vma); 經過這樣的修改， lru lock 可以在memory lock 調用層次中降級到最底層。
這時， lru lock已經非常簡化，可以用per memcg lru lock來替換全局的lru lock了嗎？ 還不行，使用per memcg lru lock 有一個根本問題，使用者要保證 page所屬的memcg不變，但是頁在生命周期中是可能轉換memcg的，比如頁在memcg之間migration，導緻 lru_lock随着memcg變化, 拿到的lru lock是錯誤的，好消息是memcg 變化也需要先拿到lru lock鎖，這樣我們可以獲得lru lock之後檢查這個是不是正确的鎖：
如果不是， 由反複的relock 來保證鎖的正确性。 bingo! 完美解決！
由此， 這個feature曲折的upstream 之路開始了。。。
三 最終解決
這個patchset 2019年發出到社群之後， google的 Hugh Dickins 提出， 他和facebook的Konstantin Khlebnikov 同學已經在2011釋出了非常類似的patchset，當時沒有進主線。不過google内部生産環境中一直在使用。是以現在Hugh Dickins發出來他的upstream版本。關鍵路徑和我的版本是一樣的 ?
2個相似patchset的PK, 引起了memcg 維護者Johannes 的注意， Johannes發現在compaction的時候， relock并不能保護某些特定場景：
是以他建議，也許增加原子的lru bit操作作為 lru_lock 的前提也許可以保護這個場景。 Hugh Dickins 則不認為這樣會有效，并且堅持他patchset已經在google内部用了9年了。 一直安全穩定。。。
Johannes的建議的本質是使用lru bit代替lru lock做page isolation互斥，但是問題的難點在其他地方， 比如在通常的一個swap in 的場景中：
swap in 的頁是先加入lru, 然後charge to memcg, 這樣造成頁在加入lru 時，并不知道自己會在那個memcg上， 我們也拿不到正确的per memcg lru_lock, 是以上面場景中左側CPU 即使提前檢查PageLRU 也找不到正确的lru lock 來阻止右面cpu的操作, 然并卵。
正确的解決方案， 就是上面第9步移動到第7步前面， 在加入lru前charge to memcg. 并且在取得lru lock之前檢查lru bit是否存在, 這樣才可以保證我們可以拿到的是正确的memcg 的lru lock。由此提前清除/檢查lru bit的方法才會有效。這個memcg charge的上升， 在和Johannes讨論後， Johannes在5.8 完成了代碼實作并且和入主線。
在新的代碼基礎上， 增加了lru bit的原子操作TestClearPageLRU， 把lru bit移出了lru lock的保護，相反用這個bit來做page isolation的互斥條件， 用isolation來保護頁在memcg間的移動， 讓lru lock隻完成它的最基本任務， 保護lru list完整性。至此方案主體完成。 lru lock的保護對象也由6個減小到一個。編碼實作就很容易了。
四 測試結果
方案完成後， 上面提到的file readtwice 測試中，多個memcg的情況下，lru lock 競争造成的sys 從70% 下降了一半，throughput 提高到260%。（80個cpu的神龍機器）
五 Upstream過程
經過漫長4輪的逐行review, 目前這個feature 已經進入了 linus的 5.11
https://github.com/torvalds/linux第一版patch 發到了社群後， google的skakeel butt立刻提出， google曾經在2011發過一樣的patchset來解決 per memcg lru lock 問題。 是以，skakeel 要求我們停止自己開發， 基于google的版本來解決這個問題。然後我才發現真的2011年 google Hugh Dickins 和 Facebook Konstantin Khlebnikov 就大約同時提出類似的patchset。， 但是當時引起的關注比較少，也缺乏benchmark來展示更新檔的效果， 是以很快被社群遺忘了。 不過google内部則一直在維護這組更新檔，随他們核心版本更新。
對比google的更新檔， 我們的實作共同點都是使用relock來確定page->memcg線性化， 其他實作細節則不盡相同。 測試表明我們的patch性能更好一點。 于是我基于自己的更新檔繼續修改并和Johannes讨論方案改進。 這也導緻了以後每一版都有google同學的反對：我們的測試發現你的patchset 有bug, 請參考google可以工作的版本。 并在linux-next上發現一個小bug時達到頂峰：
https://lkml.org/lkml/2020/3/6/627google同學批評我們抄他們的更新檔還抄出一堆bug.
其實這些更新檔和Hugh Dickins的更新檔毫無關聯， 并且在和Johannes的持續讨論中，解決方案的核心：page->memcg的線性化已經進化了幾個版本了， 從relock 到 lock_page_memcg, 再到TestClearPageLRU. 和google的更新檔是路線上的不同。
面對這樣的無端指責，memcg 維護者 Johannes 看不下去， 出來說了一些公道話：我和Alex同學都在嘗試和你不同的方案來解決上次提出的compacion沖突問題，而且我記得你當時是覺得這個沖突你無能為力的：
之後google同學分享了他們的測試程式，然後在這個話題上沉默了一段時間。
後來memcg charge的問題解決後， 就可以用lru bit來保證page->memcg互斥了。 v17 coding很快完成後。 intel 的Alexander Duyck， 花了5個星期， 逐行逐字的review整個patchset, 并其基于更新檔的改進， 提出了一些後續優化更新檔。5個星期的review, 足以讓一個feature 錯過合适的核心upstream 視窗。但是也增強了社群的信心。
（重大核心的feature 的merge視窗是這樣的： 大的feature 在進入linus tree之前， 要在linux-next tree 待一段時間， 主要的社群測試如Intel LKP, google syzbot 等等也會在着重測試Linux-next。 是以為了保證足夠的測試時間， 進入下個版本重要feature 必須在目前版本的rc4之前進入linux-next。 而目前版本-rc1通常bug比較多， 是以最佳rebase 版本是 rc2, 錯過最佳merge 視窗 rc2-rc4. 意味着需要在等2個月到下一個視窗。并且還要适應新的核心版本的相關修改。）
基于5.9-rc2的 v18 版本完成後， google hugh dickins同學強勢歸來，主動申請測試和review，根據他的意見v18 做了很多删減和合并，甚至推翻了一些Alexander Duyck要求的修改。patch 數量從32個壓縮到20個。Hugh Dickin 逐行review 了整整4個星期。 也完美錯過了5.10和入視窗。 之後v19, Johannes 同學終于回來開始review. Johannes比較快，一個星期就完成了review。 現在v20, 幾乎每個patch 都有了2個reviewed-by: Hugh/Johannes.
然而， 這次不像以前, 以前 patchset 沒有人關心， 這次大家的review興趣很大，來了就停不住， SUSE的 Vlastimil Babka 同學又過來開始review， 并且提出了一些coding style 和代碼解釋要求。不過被強勢的Hugh Dickins 駁回：
Hugh 的影響力還是很大的， Vlastimil 和其他潛在的reivewer都閉上了嘴。代碼終于進了基于5.10-rc 的 linux-next。 不過這個駁回也引起一個在5.11送出視窗的麻煩， memory總維護者 Andrew Morthon突然發現Vlastimil Babka 表示過一些異議。 是以他問我： 是不是輿論還不一緻， 還有曾經推給你一個bug， 你解決了嗎？
I assume the consensus on this series is 'not yet"? Hugh再次出來護場： 我現在覺得patchset 足夠好了， 足夠多人review過足夠多的版本了， 已經在linux-next 安全運作一個多月了，沒有任何功能和性能回退， Vlastimil也已經沒有意見了。 至于那個bug， Alex有足夠的證據表明和這個更新檔無關。。。
最終這個patchset享受到了Andrew 向 Linus單獨推送的待遇。 進了5.11.
六 後記
從 anolis os 開始，國人要持續投入作業系統研發。在 Linux 上遊做事情，有很多成就感，也可以保證自己需要的feature，一直線上， 免去了核心更新維護之苦。 但也會面臨荊棘和險阻， 各種内部不關心的場景都要照顧到， 不能影響其他任何人的feature。 是以相比coding, 大量的社群讨論大概是coding的3～5倍時間，主要是反複的代碼解釋和修改.
在整個upstreaming的過程中特别值得一提的是一些google的同學态度轉變， 從一開始的反對，到最後加入我們。從google方面來說， google在記憶體方面有很多優化都依賴于per memcg lru lock. 這個代碼加入核心也解除了他們9年來的代碼維護痛苦。
在社群溝通上google Hugh Dickins同學幫了很多忙！Intel 的 LKP 測試系統也持續提供測試支援，特别感謝