自電子計(jì)算機(jī)誕生以來，內(nèi)存性能一直是行業(yè)關(guān)心的重點(diǎn)。內(nèi)存也隨著摩爾定律，在大小和速度上一直增長。現(xiàn)在的阿里云服務(wù)器動(dòng)輒單機(jī)接近TB的內(nèi)存大小，加上數(shù)以百記的CPU數(shù)量也著實(shí)考驗(yàn)操作系統(tǒng)的資源管理能力。

作為世間最流行的操作系統(tǒng)Linux， 內(nèi)核使用LRU, Last Recent Used 鏈表來管理全部用戶使用的內(nèi)存，用一組鏈表串聯(lián)起一個(gè)個(gè)的內(nèi)存頁，并且使用lru lock來保護(hù)鏈表的完整性。

所有應(yīng)用程序常用操作都會(huì)涉及到LRU鏈表操作，例如，新分配一個(gè)頁，需要掛在inactive lru 鏈上， 2次訪問同一個(gè)文件地址， 會(huì)導(dǎo)致這個(gè)頁從inactive 鏈表升級(jí)到active 鏈表， 如果內(nèi)存緊張， 頁需要從active 鏈表降級(jí)到inactive 鏈表， 內(nèi)存有壓力時(shí)，頁被回收導(dǎo)致被從inactive lru鏈表移除。不單大量的用戶內(nèi)存使用創(chuàng)建，回收關(guān)系到這個(gè)鏈表， 內(nèi)核在內(nèi)存大頁拆分，頁移動(dòng)，memcg 移動(dòng)，swapin/swapout, 都要把頁移進(jìn)移出lru 鏈表。

可以簡單計(jì)算一下x86服務(wù)器上的鏈表大小：x86最常用的是4k內(nèi)存頁， 4GB 內(nèi)存會(huì)分成1M個(gè)頁, 如果按常用服務(wù)器256GB頁來算， 會(huì)有超過6千萬個(gè)頁掛在內(nèi)核lru 鏈表中。超大超長的內(nèi)存鏈表和頻繁的lru 操作造成了2個(gè)著名的內(nèi)核內(nèi)存鎖競爭， zone lock, 和 lru lock. 這2個(gè)問題也多次在阿里內(nèi)部造成麻煩， 系統(tǒng)很忙， 但是業(yè)務(wù)應(yīng)用并沒得到多少cpu時(shí)間， 大部分cpu都花在sys上了。一個(gè)簡單2次讀文件的benchmark可以顯示這個(gè)問題， 它可以造成70%的cpu時(shí)間花費(fèi)在LRU lock上。

作為一個(gè)知名內(nèi)核性能瓶頸， 社區(qū)也多次嘗試以各種方法解決這個(gè)問題， 例如，使用更多的 LRU list， 或者LRU contention 探測。

但是都因?yàn)楦鞣N原因被linux 內(nèi)核拒絕。

尋找解決方案

通過仔細(xì)的觀察發(fā)現(xiàn)， 內(nèi)核在2008年引進(jìn)內(nèi)存組-memcg以來， 系統(tǒng)單一的lru lists已經(jīng)分成了每個(gè)內(nèi)存組一個(gè)lru list， 由每個(gè)內(nèi)存組單獨(dú)管理自己的lru lists。那么按道理lru lock的contention應(yīng)該有所減小啊？為什么還是經(jīng)常在內(nèi)部服務(wù)器觀察到lru lock hot引起的sys 高？

原來， 內(nèi)核在引入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拆分到每一個(gè)memcg中， 不是可以理所當(dāng)然的享受到了memcg獨(dú)立的好處了嗎？這樣每個(gè)memcg 都不會(huì)需要等待其他memcg 釋放lru lock。鎖競爭限制在每個(gè)memcg 內(nèi)部了。

要完成lru lock 拆分，首先要知道lru lock 保護(hù)了多少對(duì)象， 通常情況中， page lru lock需要保護(hù)lru list完整性， 這個(gè)是必須的。與lru list相關(guān)的還有page flags中的lru bit，這個(gè)lru bit用作頁是否在lru list存在的指示器， 可以避免查表才能知道頁是否在list中。那么lru lock保護(hù)它也說的通。

但是lru lock 看起來還有一些奇怪的保護(hù)對(duì)象，承擔(dān)了一些不屬于它的任務(wù)：

1.PageMlock bit，保護(hù) munlock_vma 和split_huge_page 沖突，

其實(shí)， 上述2個(gè)函數(shù)在調(diào)用鏈中都需要 page lock， 所以沖突可以完全由page lock來保證互斥。這里lru lock使用屬于多余。

2.pagecache xa_lock和memcg->move_lock,

xa_lock并沒有需要lru lock保護(hù)的場景，這個(gè)保護(hù)也是多余。相反，lru lock放到xa_lock 之下， 符合xa_lock/lock_page_memcg, 的使用次序。反而可以優(yōu)化 lru lock 和 memcg move_lock的關(guān)系。

3.lru bit in page_idle_get_page, 用在這里是因?yàn)閾?dān)心 page_set_anon_rmap中， mapping 被提前預(yù)取訪問，造成異常。用memory barrier 方式可以避免這個(gè)預(yù)取， 所以可以在page idle中撤掉lru lock.

+ WRITE_ONCE(page->mapping, (struct address_space *) anon_vma);

經(jīng)過這樣的修改， lru lock 可以在memory lock 調(diào)用層次中降級(jí)到最底層。

這時(shí)， lru lock已經(jīng)非常簡化，可以用per memcg lru lock來替換全局的lru lock了嗎？還不行，使用per memcg lru lock 有一個(gè)根本問題，使用者要保證 page所屬的memcg不變，但是頁在生命周期中是可能轉(zhuǎn)換memcg的，比如頁在memcg之間migration，導(dǎo)致 lru_lock隨著memcg變化, 拿到的lru lock是錯(cuò)誤的，好消息是memcg 變化也需要先拿到lru lock鎖，這樣我們可以獲得lru lock之后檢查這個(gè)是不是正確的鎖：

如果不是， 由反復(fù)的relock 來保證鎖的正確性。bingo! 完美解決！

由此， 這個(gè)feature曲折的upstream 之路開始了。。。

最終解決

這個(gè)patchset 2019年發(fā)出到社區(qū)之后， google的 Hugh Dickins 提出， 他和facebook的Konstantin Khlebnikov 同學(xué)已經(jīng)在2011發(fā)布了非常類似的patchset，當(dāng)時(shí)沒有進(jìn)主線。不過google內(nèi)部生產(chǎn)環(huán)境中一直在使用。所以現(xiàn)在Hugh Dickins發(fā)出來他的upstream版本。關(guān)鍵路徑和我的版本是一樣的

2個(gè)相似patchset的PK, 引起了memcg 維護(hù)者Johannes 的注意， Johannes發(fā)現(xiàn)在compaction的時(shí)候， relock并不能保護(hù)某些特定場景：

所以他建議，也許增加原子的lru bit操作作為 lru_lock 的前提也許可以保護(hù)這個(gè)場景。Hugh Dickins 則不認(rèn)為這樣會(huì)有效，并且堅(jiān)持他patchset已經(jīng)在google內(nèi)部用了9年了。一直安全穩(wěn)定。。。

Johannes的建議的本質(zhì)是使用lru bit代替lru lock做page isolation互斥，但是問題的難點(diǎn)在其他地方， 比如在通常的一個(gè)swap in 的場景中：

swap in 的頁是先加入lru, 然后charge to memcg, 這樣造成頁在加入lru 時(shí)，并不知道自己會(huì)在那個(gè)memcg上， 我們也拿不到正確的per memcg lru_lock, 所以上面場景中左側(cè)CPU 即使提前檢查PageLRU 也找不到正確的lru lock 來阻止右面cpu的操作, 然并卵。

正確的解決方案， 就是上面第9步移動(dòng)到第7步前面， 在加入lru前charge to memcg. 并且在取得lru lock之前檢查lru bit是否存在, 這樣才可以保證我們可以拿到的是正確的memcg 的lru lock。由此提前清除/檢查lru bit的方法才會(huì)有效。這個(gè)memcg charge的上升， 在和Johannes討論后， Johannes在5.8 完成了代碼實(shí)現(xiàn)并且和入主線。

在新的代碼基礎(chǔ)上， 增加了lru bit的原子操作TestClearPageLRU， 把lru bit移出了lru lock的保護(hù)，相反用這個(gè)bit來做page isolation的互斥條件， 用isolation來保護(hù)頁在memcg間的移動(dòng)， 讓lru lock只完成它的最基本任務(wù)， 保護(hù)lru list完整性。至此方案主體完成。lru lock的保護(hù)對(duì)象也由6個(gè)減小到一個(gè)。編碼實(shí)現(xiàn)就很容易了。

測試結(jié)果

方案完成后， 上面提到的file readtwice 測試中，多個(gè)memcg的情況下，lru lock 競爭造成的sys 從70% 下降了一半，throughput 提高到260%。（80個(gè)cpu的神龍機(jī)器）

Upstream過程

經(jīng)過漫長4輪的逐行review, 目前這個(gè)feature 已經(jīng)進(jìn)入了 linus的 5.11 https://github.com/torvalds/linux

第一版patch 發(fā)到了社區(qū)后， google的skakeel butt立刻提出， google曾經(jīng)在2011發(fā)過一樣的patchset來解決 per memcg lru lock 問題。所以，skakeel 要求我們停止自己開發(fā)， 基于google的版本來解決這個(gè)問題。然后我才發(fā)現(xiàn)真的2011年 google Hugh Dickins 和 Facebook Konstantin Khlebnikov 就大約同時(shí)提出類似的patchset。， 但是當(dāng)時(shí)引起的關(guān)注比較少，也缺乏benchmark來展示補(bǔ)丁的效果， 所以很快被社區(qū)遺忘了。不過google內(nèi)部則一直在維護(hù)這組補(bǔ)丁，隨他們內(nèi)核版本升級(jí)。

對(duì)比google的補(bǔ)丁， 我們的實(shí)現(xiàn)共同點(diǎn)都是使用relock來確保page->memcg線性化， 其他實(shí)現(xiàn)細(xì)節(jié)則不盡相同。測試表明我們的patch性能更好一點(diǎn)。于是我基于自己的補(bǔ)丁繼續(xù)修改并和Johannes討論方案改進(jìn)。這也導(dǎo)致了以后每一版都有g(shù)oogle同學(xué)的反對(duì)：我們的測試發(fā)現(xiàn)你的patchset 有bug, 請(qǐng)參考google可以工作的版本。并在linux-next上發(fā)現(xiàn)一個(gè)小bug時(shí)達(dá)到頂峰：https://lkml.org/lkml/2020/3/6/627 google同學(xué)批評(píng)我們抄他們的補(bǔ)丁還抄出一堆bug.

其實(shí)這些補(bǔ)丁和Hugh Dickins的補(bǔ)丁毫無關(guān)聯(lián)， 并且在和Johannes的持續(xù)討論中，解決方案的核心：page->memcg的線性化已經(jīng)進(jìn)化了幾個(gè)版本了， 從relock 到 lock_page_memcg, 再到TestClearPageLRU. 和google的補(bǔ)丁是路線上的不同。

面對(duì)這樣的無端指責(zé)，memcg 維護(hù)者 Johannes 看不下去， 出來說了一些公道話：我和Alex同學(xué)都在嘗試和你不同的方案來解決上次提出的compacion沖突問題，而且我記得你當(dāng)時(shí)是覺得這個(gè)沖突你無能為力的：

之后google同學(xué)分享了他們的測試程序，然后在這個(gè)話題上沉默了一段時(shí)間。

后來memcg charge的問題解決后， 就可以用lru bit來保證page->memcg互斥了。v17 coding很快完成后。intel 的Alexander Duyck， 花了5個(gè)星期， 逐行逐字的review整個(gè)patchset, 并其基于補(bǔ)丁的改進(jìn)， 提出了一些后續(xù)優(yōu)化補(bǔ)丁。5個(gè)星期的review, 足以讓一個(gè)feature 錯(cuò)過合適的內(nèi)核upstream 窗口。但是也增強(qiáng)了社區(qū)的信心。

（重大內(nèi)核的feature 的merge窗口是這樣的：大的feature 在進(jìn)入linus tree之前， 要在linux-next tree 待一段時(shí)間， 主要的社區(qū)測試如Intel LKP, google syzbot 等等也會(huì)在著重測試Linux-next。所以為了保證足夠的測試時(shí)間， 進(jìn)入下個(gè)版本重要feature 必須在當(dāng)前版本的rc4之前進(jìn)入linux-next。而當(dāng)前版本-rc1通常bug比較多， 所以最佳rebase 版本是 rc2, 錯(cuò)過最佳merge 窗口 rc2-rc4. 意味著需要在等2個(gè)月到下一個(gè)窗口。并且還要適應(yīng)新的內(nèi)核版本的相關(guān)修改。）

基于5.9-rc2的 v18 版本完成后， google hugh dickins同學(xué)強(qiáng)勢歸來，主動(dòng)申請(qǐng)測試和review，根據(jù)他的意見v18 做了很多刪減和合并，甚至推翻了一些Alexander Duyck要求的修改。patch 數(shù)量從32個(gè)壓縮到20個(gè)。Hugh Dickin 逐行review 了整整4個(gè)星期。也完美錯(cuò)過了5.10和入窗口。之后v19, Johannes 同學(xué)終于回來開始review. Johannes比較快，一個(gè)星期就完成了review。現(xiàn)在v20, 幾乎每個(gè)patch 都有了2個(gè)reviewed-by: Hugh/Johannes.

然而， 這次不像以前, 以前 patchset 沒有人關(guān)心， 這次大家的review興趣很大，來了就停不住， SUSE的 Vlastimil Babka 同學(xué)又過來開始review， 并且提出了一些coding style 和代碼解釋要求。不過被強(qiáng)勢的Hugh Dickins 駁回：

Hugh 的影響力還是很大的， Vlastimil 和其他潛在的reivewer都閉上了嘴。代碼終于進(jìn)了基于5.10-rc 的 linux-next。不過這個(gè)駁回也引起一個(gè)在5.11提交窗口的麻煩， memory總維護(hù)者 Andrew Morthon突然發(fā)現(xiàn)Vlastimil Babka 表示過一些異議。所以他問我：是不是輿論還不一致， 還有曾經(jīng)推給你一個(gè)bug， 你解決了嗎？

I assume the consensus on this series is 'not yet"?

Hugh再次出來護(hù)場：我現(xiàn)在覺得patchset 足夠好了， 足夠多人review過足夠多的版本了， 已經(jīng)在linux-next 安全運(yùn)行一個(gè)多月了，沒有任何功能和性能回退， Vlastimil也已經(jīng)沒有意見了。至于那個(gè)bug， Alex有足夠的證據(jù)表明和這個(gè)補(bǔ)丁無關(guān)。。。

最終這個(gè)patchset享受到了Andrew 向 Linus單獨(dú)推送的待遇。進(jìn)了5.11。

后記

在 Linux 上游做事情，有很多成就感，也可以保證自己需要的feature，一直在線， 免去了內(nèi)核升級(jí)維護(hù)之苦。但也會(huì)面臨荊棘和險(xiǎn)阻， 各種內(nèi)部不關(guān)心的場景都要照顧到， 不能影響其他任何人的feature。所以相比coding, 大量的社區(qū)討論大概是coding的3～5倍時(shí)間，主要是反復(fù)的代碼解釋和修改.

在整個(gè)upstreaming的過程中特別值得一提的是一些google的同學(xué)態(tài)度轉(zhuǎn)變， 從一開始的反對(duì)，到最后加入我們。從google方面來說， google在內(nèi)存方面有很多優(yōu)化都依賴于per memcg lru lock. 這個(gè)代碼加入內(nèi)核也解除了他們9年來的代碼維護(hù)痛苦。

原文標(biāo)題：memcg lru lock 血淚史

文章出處：【微信公眾號(hào)：Linuxer】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq