自電子計(jì)算機(jī)誕生以來(lái)，內(nèi)存性能一直是行業(yè)關(guān)心的重點(diǎn)。內(nèi)存也隨著摩爾定律，在大小和速度上一直增長(zhǎng)?，F(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 鏈表來(lái)管理全部用戶使用的內(nèi)存，用一組鏈表串聯(lián)起一個(gè)個(gè)的內(nèi)存頁(yè)，并且使用lru lock來(lái)保護(hù)鏈表的完整性。

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

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

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

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

尋找解決方案

通過(guò)仔細(xì)的觀察發(fā)現(xiàn)， 內(nèi)核在2008年引進(jìn)內(nèi)存組-memcg以來(lái)， 系統(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 高？

原來(lái)， 內(nèi)核在引入per memcg lru lists后，并沒(méi)有使用per memcg lru lock， 還在使用舊的全局lru lock 來(lái)管理全部memcg lru lists. 這造成了本來(lái)可以自治的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。鎖競(jìng)爭(zhēng)限制在每個(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用作頁(yè)是否在lru list存在的指示器， 可以避免查表才能知道頁(yè)是否在list中。那么lru lock保護(hù)它也說(shuō)的通。

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

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

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

2.pagecache xa_lock和memcg->move_lock,

xa_lock并沒(méi)有需要lru lock保護(hù)的場(chǎng)景，這個(gè)保護(hù)也是多余。相反，lru lock放到xa_lock 之下， 符合x(chóng)a_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ù)取訪問(wèn)，造成異常。用memory barrier 方式可以避免這個(gè)預(yù)取， 所以可以在page idle中撤掉lru lock.

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

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

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

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

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

最終解決

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

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

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

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

swap in 的頁(yè)是先加入lru, 然后charge to memcg, 這樣造成頁(yè)在加入lru 時(shí)，并不知道自己會(huì)在那個(gè)memcg上， 我們也拿不到正確的per memcg lru_lock, 所以上面場(chǎng)景中左側(cè)CPU 即使提前檢查PageLRU 也找不到正確的lru lock 來(lái)阻止右面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來(lái)做page isolation的互斥條件， 用isolation來(lái)保護(hù)頁(yè)在memcg間的移動(dòng)， 讓lru lock只完成它的最基本任務(wù)， 保護(hù)lru list完整性。至此方案主體完成。lru lock的保護(hù)對(duì)象也由6個(gè)減小到一個(gè)。編碼實(shí)現(xiàn)就很容易了。

測(cè)試結(jié)果

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

Upstream過(guò)程

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

對(duì)比google的補(bǔ)丁， 我們的實(shí)現(xiàn)共同點(diǎn)都是使用relock來(lái)確保page->memcg線性化， 其他實(shí)現(xiàn)細(xì)節(jié)則不盡相同。測(cè)試表明我們的patch性能更好一點(diǎn)。于是我基于自己的補(bǔ)丁繼續(xù)修改并和Johannes討論方案改進(jìn)。這也導(dǎo)致了以后每一版都有g(shù)oogle同學(xué)的反對(duì)：我們的測(cè)試發(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ǔ)丁毫無(wú)關(guān)聯(lián)， 并且在和Johannes的持續(xù)討論中，解決方案的核心：page->memcg的線性化已經(jīng)進(jìn)化了幾個(gè)版本了， 從relock 到 lock_page_memcg, 再到TestClearPageLRU. 和google的補(bǔ)丁是路線上的不同。

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

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

后來(lái)memcg charge的問(wèn)題解決后， 就可以用lru bit來(lái)保證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ò)過(guò)合適的內(nèi)核upstream 窗口。但是也增強(qiáng)了社區(qū)的信心。

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

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

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

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

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

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

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

后記

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

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

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

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

責(zé)任編輯：haq