memcg lru lock 血泪史

背景

自电子计算机诞生以来，内存性能一直是行业关心的重点。内存也随着摩尔定律，在大小和速度上一直增长。现在的阿里云服务器动辄单机接近TB的内存大小，加上数以百记的CPU数量也着实考验操作系统的资源管理能力。

 作为世间最流行的操作系统Linux， 内核使用LRU, Last Recent Used 链表来管理全部用户使用的内存，用一组链表串联起一个个的内存页，并且使用lru lock来保护链表的完整性。

所有应用程序常用操作都会涉及到LRU链表操作，例如，新分配一个页，需要挂在inactive lru 链上， 2次访问同一个文件地址， 会导致这个页从inactive 链表升级到active 链表， 如果内存紧张， 页需要从active 链表降级到inactive 链表， 内存有压力时，页被回收导致被从inactive lru链表移除。不单大量的用户内存使用创建，回收关系到这个链表， 内核在内存大页拆分，页移动，memcg 移动，swapin/swapout, 都要把页移进移出lru 链表。

可以简单计算一下x86服务器上的链表大小：x86最常用的是4k内存页， 4GB 内存会分成1M个页, 如果按常用服务器256GB页来算， 会有超过6千万个页挂在内核lru 链表中。超大超长的内存链表和频繁的lru 操作造成了2个著名的内核内存锁竞争， zone lock, 和 lru lock. 这2个问题也多次在阿里内部造成麻烦， 系统很忙， 但是业务应用并没得到多少cpu时间， 大部分cpu都花在sys上了。一个简单2次读文件的benchmark可以显示这个问题， 它可以造成70%的cpu时间花费在LRU lock上。https://git.kernel.org/pub/scm/linux/kernel/git/wfg/vm-scalability.git/tree/case-lru-file-readtwice 

作为一个知名内核性能瓶颈， 社区也多次尝试以各种方法解决这个问题， 例如，使用更多的 LRU list， 或者LRU contention 探测（https://lwn.net/Articles/753058/）。

但是都因为各种原因被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/627 google同学批评我们抄他们的补丁还抄出一堆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。

 后记

在 Linux 上游做事情，有很多成就感，也可以保证自己需要的feature，一直在线， 免去了内核升级维护之苦。但也会面临荆棘和险阻， 各种内部不关心的场景都要照顾到， 不能影响其他任何人的feature。所以相比coding, 大量的社区讨论大概是coding的3～5倍时间，主要是反复的代码解释和修改.

在整个upstreaming的过程中特别值得一提的是一些google的同学态度转变， 从一开始的反对，到最后加入我们。从google方面来说， google在内存方面有很多优化都依赖于per memcg lru lock. 这个代码加入内核也解除了他们9年来的代码维护痛苦。 

在社区沟通上google Hugh Dickins同学帮了很多忙！Intel 的 LKP 测试系统也持续提供测试支持，特别感谢！

欢迎您扫码进群交流：

往期精彩回顾：