LWN：允許其他CPU來(lái)清空此CPU的page list！
關(guān)注了就能看到更多這么棒的文章哦～
Remote per-CPU page list draining
By Jonathan Corbet
February 15, 2022
DeepL assisted translation
https://lwn.net/Articles/884448/
有時(shí)，一組內(nèi)核 patch 會(huì)有一個(gè)令人眼前一亮、非常吸引眼球的標(biāo)題。不過(guò)大多數(shù)時(shí)候在郵件列表中的 patch 標(biāo)題都是類似 "remote per-cpu lists drain support" 這樣的。對(duì)許多人來(lái)說(shuō)這組 patch 就跟這個(gè)標(biāo)題本身一樣看起來(lái)很枯燥。但是，那些對(duì)這方面感興趣的人——許多 LWN 的讀者都是這樣的—— Nicolas Saenz Julienne 的這組短小的 patch 給了我們一些啟示，告訴開(kāi)發(fā)者們?nèi)绾慰梢宰寖?nèi)核的 page 分配器盡可能快以及盡可能地強(qiáng)大。
Per-CPU page lists
page allocator 這個(gè)名字很直白地說(shuō)明了它是負(fù)責(zé)以整個(gè) page 為單位來(lái)管理系統(tǒng)的內(nèi)存的。它跟通常用來(lái)處理更小塊的內(nèi)存的 slab allocator 是有區(qū)別的。內(nèi)存的分配和釋放動(dòng)作在內(nèi)核中頻繁發(fā)生，使得 page allocator 成為許多性能敏感的關(guān)鍵路徑（hot path）的一環(huán)。例如，來(lái)一個(gè)系統(tǒng)調(diào)用或者設(shè)備中斷之后，就可能多次引發(fā)對(duì) page allocator 的調(diào)用，因此代碼需要能飛快執(zhí)行完畢。有時(shí)候，內(nèi)存管理代碼會(huì)被認(rèn)為是限制了內(nèi)核其他部分性能的瓶頸，盡管人們已經(jīng)做了很多努力來(lái)優(yōu)化它。
抽象地來(lái)說(shuō)，page allocator 是基于 "buddy allocator" 的，它以 2 的冪次數(shù)量的連續(xù) page 為單位來(lái)進(jìn)行內(nèi)存處理。整體來(lái)說(shuō)，buddy allocator 專注于盡可能將相鄰的 page 合并成更大的連續(xù)內(nèi)存塊。但是，在面對(duì)當(dāng)代系統(tǒng)的需求中的新特點(diǎn)時(shí)，這種抽象就開(kāi)始出現(xiàn)問(wèn)題了，因?yàn)槟呐卢F(xiàn)在一個(gè)手機(jī)里面也可能有許多的 CPU。而維護(hù)一個(gè)全局的 buddy structure 就意味著會(huì)有大量的對(duì)這個(gè)數(shù)據(jù)的并發(fā)訪問(wèn)操作。這反過(guò)來(lái)又意味著會(huì)引入 locking （互斥鎖）機(jī)制以及導(dǎo)致 cache miss，這兩種情況都會(huì)破壞系統(tǒng)的性能。
要想緩解這些因?yàn)椴l(fā)訪問(wèn)（concurrent access）這些共享數(shù)據(jù)而產(chǎn)生的性能問(wèn)題，最好方法之一就是避免對(duì)共享數(shù)據(jù)的進(jìn)行并發(fā)訪問(wèn)。只要每個(gè) CPU 能夠在自己的私有領(lǐng)域中獨(dú)立工作，不與其他 CPU 爭(zhēng)奪，那么性能就會(huì)得到改善。page allocator 就跟內(nèi)核中許多其他部分一樣，通過(guò)針對(duì)每個(gè) CPU 都維護(hù)一個(gè)獨(dú)立的空閑 page 列表（per-CPU list of free pages）來(lái)實(shí)現(xiàn)這一點(diǎn)。
具體來(lái)說(shuō)，內(nèi)存管理子系統(tǒng)會(huì)在用于描述內(nèi)存管理區(qū)的 zone structure 中存放一個(gè) per-CPU 的空閑 page 列表。雖然實(shí)際情況（必定）會(huì)更復(fù)雜一些，但這個(gè)結(jié)構(gòu)確實(shí)可以被簡(jiǎn)化為是一個(gè)簡(jiǎn)單的 page 列表數(shù)組，系統(tǒng)中每個(gè) CPU 都有一個(gè)列表。每當(dāng)某個(gè) CPU 需要分配一個(gè) page 時(shí)，它首先會(huì)在其 per-CPU 的列表中尋找，如果找到了一個(gè)可以使用的 page，那么就從中取出來(lái)用。當(dāng)該 CPU 釋放了一個(gè) page 的時(shí)候，它就會(huì)把這個(gè) page 放回到 per-CPU 的列表中。通過(guò)這種方式，page allocator 中的許多操作都可以在不需要對(duì)全局?jǐn)?shù)據(jù)結(jié)構(gòu)進(jìn)行寫入的情況下就能完成，這樣就大大地加快了速度。并且在 CPU 上可以更高概率地使用本地仍然在 cache 中的 page，也有助于性能。
當(dāng)然，這只有在 per-CPU 的列表中有所需數(shù)量的 page 時(shí)才能起效。如果某個(gè) CPU 需要分配一個(gè) page，但此時(shí)它的 per-CPU 列表是空的，那么就必須采取較慢的方式來(lái)從全局的 free list 中獲取到內(nèi)存，在這個(gè)過(guò)程中就可能會(huì)與其他 CPU 競(jìng)爭(zhēng)。相反，如果 per-CPU 的列表變得太長(zhǎng)了，那么它就可能會(huì)占用原本可以用在其他地方的內(nèi)存，這里最好把其中一部分 page 交還給全局分配器。不過(guò)很多時(shí)候，每個(gè) CPU 都可以直接用自己的 free page 列表就能完成工作，大家都很高興。
不過(guò)，當(dāng)系統(tǒng)整體在面臨內(nèi)存壓力時(shí)，就會(huì)出現(xiàn)一種情況。如果內(nèi)存管理子系統(tǒng)在所有可能的地方都去尋找可用的 page 的時(shí)候，它很快就會(huì)來(lái)盯上這個(gè) per-CPU 的 list，尋找其中閑置的、可供使用的內(nèi)存。不幸的是，這里不可以直接去搶過(guò)來(lái)使用，因?yàn)?per-CPU 的列表只有在每個(gè) CPU 都能確保是自己獨(dú)占訪問(wèn)這個(gè) list 時(shí)才能發(fā)揮作用。如果有其他的 CPU 插手進(jìn)來(lái)的話，整個(gè)系統(tǒng)就會(huì)完全亂套了。
那么，當(dāng)系統(tǒng)需要奪取 per-CPU 列表中的空閑 page 時(shí)，應(yīng)該怎么做呢？當(dāng)前的做法是，內(nèi)核要求每個(gè) CPU 從自己的 list 中釋放（drain）這些 page。這個(gè)動(dòng)作是由一個(gè)特殊的、per-CPU 的 workqueue 來(lái)完成的，這個(gè) workqueue 中會(huì)有多個(gè) callback 在排隊(duì)來(lái)釋放 page。等這個(gè) CPU 開(kāi)始 schedule 調(diào)度的時(shí)候，此 workqueue 就會(huì)立即運(yùn)行，通常這個(gè)過(guò)程會(huì)很快。
不過(guò)這個(gè)解決方案并不完美。最起碼它會(huì)導(dǎo)致每個(gè)目標(biāo) CPU 發(fā)生一次上下文切換來(lái)運(yùn)行 drain 操作的 callback 函數(shù)。但是，如果有一個(gè)目標(biāo) CPU 是運(yùn)行在 tickless 模式下的，或者如果它正在運(yùn)行一個(gè)高優(yōu)先級(jí)的實(shí)時(shí)任務(wù)，那么 workqueue 可能在很長(zhǎng)一段時(shí)間內(nèi)根本就不會(huì)有機(jī)會(huì)運(yùn)行。因此，該 CPU 上的所有 free page 都會(huì)被鎖在其本地列表中，搞不好大多數(shù) free page 都會(huì)堆在這里了。
Draining the lists remotely
這個(gè) patch 就是為了緩解這個(gè)問(wèn)題的，有了它，就可以遠(yuǎn)程（即從別的 CPU 上進(jìn)行）地從這個(gè)目標(biāo) CPU 的本地列表中獲取到 page。上一次的嘗試是增加了 spinlock 來(lái)控制對(duì) per-CPU list 的訪問(wèn)，這本質(zhì)上是打破了 per-CPU 的特性，因此那個(gè)解決方案雖然是有效的，但它所增加的開(kāi)銷正是我們創(chuàng)建出 per-CPU 列表所想避免的。因此這些 patch 并沒(méi)有進(jìn)入內(nèi)核。
目前這組 patch 的做法不同，它采用了內(nèi)核社區(qū)最喜歡的處理擴(kuò)展性問(wèn)題（scalability problem）的工具之一：read-copy-update（RCU）。這反過(guò)來(lái)又利用了計(jì)算機(jī)科學(xué)的最原始的一個(gè)技巧：添加一層間接抽象（a layer of indirection）。使用這組 patch 之后，每個(gè) CPU 現(xiàn)在有兩組存放空閑 page 的列表了，其中一組 list 是在任何時(shí)候都使用的，而另一組則被預(yù)留下來(lái)（是個(gè)空 list）。在 zone structure 里面添加了一個(gè)新的指針，指向當(dāng)前正在使用的是哪組 list；每當(dāng)一個(gè) CPU 需要訪問(wèn)其本地的 list 時(shí)，它必須使用這個(gè)指針來(lái)取到。
當(dāng)需要搶奪一個(gè) CPU 的 free page 時(shí)，搶奪者所在的 CPU 將使用一個(gè)原子操作的比較和交換動(dòng)作（atomic compare-and-swap operation）來(lái)把目標(biāo) CPU 的指針切換到第二組（空的）列表上。不過(guò)，哪怕是切換動(dòng)作完成之后，目標(biāo) CPU 仍可能在繼續(xù)使用前一組列表，所以搶奪者的 CPU 必須等到 RCU 的 grace period 完成之后才可以去正式訪問(wèn)原來(lái)的列表。由于這是個(gè) per-CPU data structure，在 RCU 的 grace period 期限到了之后，目標(biāo) CPU 就不能再持有對(duì)舊列表的引用了。屆時(shí)就完全可以對(duì)舊列表進(jìn)行提取和清空了。與此同時(shí)，目標(biāo) CPU 會(huì)仍然正常地進(jìn)行工作，盡管它沒(méi)有了任何一個(gè)本地空閑 page，但它也沒(méi)有被人打斷過(guò)。
這種方法也不是完全沒(méi)有性能損失的，它在內(nèi)存分配的 hot path 中增加了一個(gè)額外的指針解析動(dòng)作（pointer dereference），會(huì)增加一些開(kāi)銷。各種基準(zhǔn)測(cè)試結(jié)果看起來(lái)在大多數(shù)情況下沒(méi)有什么區(qū)別，而在一些情況下會(huì)有 1-3% 的性能損失。patch 的說(shuō)明郵件中認(rèn)為這種開(kāi)銷是可以接受的。
目前還不清楚其他的內(nèi)存管理開(kāi)發(fā)者是否會(huì)同意這個(gè)結(jié)論。內(nèi)核開(kāi)發(fā)者會(huì)為了 1% 的性能提升而努力工作很長(zhǎng)時(shí)間，他們可能不會(huì)愿意為了一部分使用場(chǎng)景特有的好處而放棄這么多的性能。不過(guò)無(wú)論如何這里所要解決的問(wèn)題是真實(shí)存在，而且尚不清楚是否還有更好的解決方案。無(wú)論這組 patch 的標(biāo)題是否讓讀者們喜歡與激動(dòng)，這個(gè) remote per-CPU list draining 的改動(dòng)很可能會(huì)是未來(lái)的內(nèi)核里的一部分。
全文完
LWN 文章遵循 CC BY-SA 4.0 許可協(xié)議。
長(zhǎng)按下面二維碼關(guān)注，關(guān)注 LWN 深度文章以及開(kāi)源社區(qū)的各種新近言論～