多核心Linux的slab系統(tǒng)的內(nèi)核優(yōu)化方面

作為這個(gè)系列的第一篇，我先來描述一下slab系統(tǒng)。因?yàn)榻┨煊泻屯?，朋友討論過這個(gè)主題，而且覺得這個(gè)主題還算比較典型，所以就作為第一篇了。其實(shí)按照操作系統(tǒng)理論來講，進(jìn)程管理應(yīng)該更加重要些，按照我自己的興趣來講，IO管理以及TCP/IP協(xié)議棧會(huì)更加有分量，關(guān)于這些內(nèi)容，我會(huì)陸續(xù)給出。

Linux內(nèi)核的slab來自一種很簡單的思想，即事先準(zhǔn)備好一些會(huì)頻繁分配，釋放的數(shù)據(jù)結(jié)構(gòu)。然而標(biāo)準(zhǔn)的slab實(shí)現(xiàn)太復(fù)雜且維護(hù)開銷巨大，因此便分化出了更加小巧的slub，因此本文討論的就是slub，后面所有提到slab的地方，指的都是slub。另外又由于本文主要描述內(nèi)核優(yōu)化方面的內(nèi)容，并不是基本原理介紹，因此想了解slab細(xì)節(jié)以及代碼實(shí)現(xiàn)的請自行百度或者看源碼。

單CPU上單純的slab

下圖給出了單CPU上slab在分配和釋放對象時(shí)的情景序列：

可以看出，非常之簡單，而且完全達(dá)到了slab設(shè)計(jì)之初的目標(biāo)。

擴(kuò)展到多核心CPU

現(xiàn)在我們簡單的將上面的模型擴(kuò)展到多核心CPU，同樣差不多的分配序列如下圖所示：

我們看到，在只有單一slab的時(shí)候，如果多個(gè)CPU同時(shí)分配對象，沖突是不可避免的，解決沖突的幾乎是唯一的辦法就是加鎖排隊(duì)，然而這將大大增加延遲，我們看到，申請單一對象的整個(gè)時(shí)延從T0開始，到T4結(jié)束，這太久了。

多CPU無鎖化并行化操作的直接思路-復(fù)制給每個(gè)CPU一套相同的數(shù)據(jù)結(jié)構(gòu)。

不二法門就是增加“每CPU變量”。對于slab而言，可以擴(kuò)展成下面的樣子：

如果以為這么簡單就結(jié)束了，那這就太沒有意義了。

問題

首先，我們來看一個(gè)簡單的問題，如果單獨(dú)的某個(gè)CPU的slab緩存沒有對象可分配了，但是其它CPU的slab緩存仍有大量空閑對象的情況，如下圖所示：

這是可能的，因?yàn)閷为?dú)一種slab的需求是和該CPU上執(zhí)行的進(jìn)程/線程緊密相關(guān)的，比如如果CPU0只處理網(wǎng)絡(luò)，那么它就會(huì)對skb等數(shù)據(jù)結(jié)構(gòu)有大量的需求，對于上圖最后引出的問題，如果我們選擇從伙伴系統(tǒng)中分配一個(gè)新的page(或者pages，取決于對象大小以及slab cache的order)，那么久而久之就會(huì)造成slab在CPU間分布的不均衡，更可能會(huì)因此吃掉大量的物理內(nèi)存，這都是不希望看到的。

在繼續(xù)之前，首先要明確的是，我們需要在CPU間均衡slab，并且這些必須靠slab內(nèi)部的機(jī)制自行完成，這個(gè)和進(jìn)程在CPU間負(fù)載均衡是完全不同的，對進(jìn)程而言，擁有一個(gè)核心調(diào)度機(jī)制，比如基于時(shí)間片，或者虛擬時(shí)鐘的步進(jìn)速率等，但是對于slab，完全取決于使用者自身，只要對象仍然在使用，就不能剝奪使用者繼續(xù)使用的權(quán)利，除非使用者自己釋放。因此slab的負(fù)載均衡必須設(shè)計(jì)成合作型的，而不是搶占式的。

好了?，F(xiàn)在我們知道，從伙伴系統(tǒng)重新分配一個(gè)page(s)并不是一個(gè)好主意，它應(yīng)該是最終的決定，在執(zhí)行它之前，首先要試一下別的路線。

現(xiàn)在，我們引出第二個(gè)問題，如下圖所示：

誰也不能保證分配slab對象的CPU和釋放slab對象的CPU是同一個(gè)CPU，誰也不能保證一個(gè)CPU在一個(gè)slab對象的生命周期內(nèi)沒有分配新的page(s)，這期間的復(fù)雜操作誰也沒有規(guī)定。這些問題該怎么解決呢？事實(shí)上，理解了這些問題是怎么解決的，一個(gè)slab框架就徹底理解了。

問題的解決-分層slab cache

無級(jí)變速總是讓人向往。

如果一個(gè)CPU的slab緩存滿了，直接去搶同級(jí)別的別的CPU的slab緩存被認(rèn)為是一種魯莽且不道義的做法。那么為何不設(shè)置另外一個(gè)slab緩存，獲取它里面的對象不像直接獲取CPU的slab緩存那么簡單且直接，但是難度卻又不大，只是稍微增加一點(diǎn)消耗，這不是很好嗎？事實(shí)上，CPU的L1，L2，L3 cache不就是這個(gè)方案設(shè)計(jì)的嗎？這事實(shí)上已經(jīng)成為cache設(shè)計(jì)的不二法門。這個(gè)設(shè)計(jì)思想同樣作用于slab，就是Linux內(nèi)核的slub實(shí)現(xiàn)。

現(xiàn)在可以給出概念和解釋了。

Linux kernel slab cache：一個(gè)分為3層的對象cache模型。

Level 1 slab cache：一個(gè)空閑對象鏈表，每個(gè)CPU一個(gè)的獨(dú)享cache，分配釋放對象無需加鎖。

Level 2 slab cache：一個(gè)空閑對象鏈表，每個(gè)CPU一個(gè)的共享page(s) cache，分配釋放對象時(shí)僅需要鎖住該page(s)，與Level 1 slab cache互斥，不互相包容。

Level 3 slab cache：一個(gè)page(s)鏈表，每個(gè)NUMA NODE的所有CPU共享的cache，單位為page(s)，獲取后被提升到對應(yīng)CPU的Level 1 slab cache，同時(shí)該page(s)作為Level 2的共享page(s)存在。

共享page(s)：該page(s)被一個(gè)或者多個(gè)CPU占有，每一個(gè)CPU在該page(s)上都可以擁有互相不充圖的空閑對象鏈表，該page(s)擁有一個(gè)唯一的Level 2 slab cache空閑鏈表，該鏈表與上述一個(gè)或多個(gè)Level 1 slab cache空閑鏈表亦不沖突，多個(gè)CPU獲取該Level 2 slab cache時(shí)必須爭搶，獲取后可以將該鏈表提升成自己的Level 1 slab cache。

該slab cache的圖示如下：

其行為如下圖所示：

2個(gè)場景

對于常規(guī)的對象分配過程，下圖展示了其細(xì)節(jié)：

事實(shí)上，對于多個(gè)CPU共享一個(gè)page(s)的情況，還可以有另一種玩法，如下圖所示：

伙伴系統(tǒng)

前面我們簡短的體會(huì)了Linux內(nèi)核的slab設(shè)計(jì),不宜過長,太長了不易理解.但是最后,如果Level 3也沒有獲取page(s)，那么最終會(huì)落到終極的伙伴系統(tǒng)。

伙伴系統(tǒng)是為了防內(nèi)存分配碎片化的，所以它盡可能地做兩件事：

1).盡量分配盡可能大的內(nèi)存

2).盡量合并連續(xù)的小塊內(nèi)存成一塊大內(nèi)存

我們可以通過下面的圖解來理解上面的原則：

注意，本文是關(guān)于優(yōu)化的，不是伙伴系統(tǒng)的科普，所以我假設(shè)大家已經(jīng)理解了伙伴系統(tǒng)。

鑒于slab緩存對象大多數(shù)都是不超過1個(gè)頁面的小結(jié)構(gòu)(不僅僅slab系統(tǒng)，超過1個(gè)頁面的內(nèi)存需求相比1個(gè)頁面的內(nèi)存需求，很少)，因此會(huì)有大量的針對1個(gè)頁面的內(nèi)存分配需求。從伙伴系統(tǒng)的分配原理可知，如果持續(xù)大量分配單一頁面，會(huì)有大量的order大于0的頁面分裂成單一頁面，在單核心CPU上，這不是問題，但是在多核心CPU上，由于每一個(gè)CPU都會(huì)進(jìn)行此類分配，而伙伴系統(tǒng)的分裂，合并操作會(huì)涉及大量的鏈表操作，這個(gè)鎖開銷是巨大的，因此需要優(yōu)化！

Linux內(nèi)核對伙伴系統(tǒng)針對單一頁面的分配需求采取的批量分配“每CPU單一頁面緩存”的方式！

每一個(gè)CPU擁有一個(gè)單一頁面緩存池，需要單一頁面的時(shí)候，可以無需加鎖從當(dāng)前CPU對應(yīng)的頁面池中獲取頁面。而當(dāng)池中頁面不足時(shí)，系統(tǒng)會(huì)批量從伙伴系統(tǒng)中拉取一堆頁面到池中，反過來，在單一頁面釋放的時(shí)候，會(huì)擇優(yōu)將其釋放到每CPU的單一頁面緩存中。

為了維持“每CPU單一頁面緩存”中頁面的數(shù)量不會(huì)太多或太少(太多會(huì)影響伙伴系統(tǒng)，太少會(huì)影響CPU的需求)，系統(tǒng)保持了兩個(gè)值，當(dāng)緩存頁面數(shù)量低于low值的時(shí)候，便從伙伴系統(tǒng)中批量獲取頁面到池中，而當(dāng)緩存頁面數(shù)量大于high的時(shí)候，便會(huì)釋放一些頁面到伙伴系統(tǒng)中。

小結(jié)

多CPU操作系統(tǒng)內(nèi)核中，關(guān)鍵的開銷就是鎖的開銷。我認(rèn)為這是一開始的設(shè)計(jì)導(dǎo)致的，因?yàn)橐婚_始，多核CPU并沒有出現(xiàn)，單核CPU上的共享保護(hù)幾乎都是可以用“禁中斷”，“禁搶占”來簡單實(shí)現(xiàn)的，到了多核時(shí)代，操作系統(tǒng)同樣簡單平移到了新的平臺(tái)，因此同步操作是在單核的基礎(chǔ)上后來添加的。簡單來講，目前的主流操作系統(tǒng)都是在單核年代創(chuàng)造出來的，因此它們都是順應(yīng)單核環(huán)境的，對于多核環(huán)境，可能它們一開始的設(shè)計(jì)就有問題。

不管怎么說，優(yōu)化操作的不二法門就是禁止或者盡量減少鎖的操作。隨之而來的思路就是為共享的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)創(chuàng)建"每CPU的緩存“，而這類緩存分為兩種類型：

1).數(shù)據(jù)通路緩存。

比如路由表之類的數(shù)據(jù)結(jié)構(gòu)，你可以用RCU鎖來保護(hù)，當(dāng)然如果為每一個(gè)CPU都創(chuàng)建一個(gè)本地路由表緩存，也是不錯(cuò)的，現(xiàn)在的問題是何時(shí)更新它們，因?yàn)樗械木彺娑际瞧郊?jí)的，因此一種批量同步的機(jī)制是必須的。

2).管理機(jī)制緩存。

比如slab對象緩存這類，其生命周期完全取決于使用者，因此不存在同步問題，然而卻存在管理問題。采用分級(jí)cache的思想是好的，這個(gè)非常類似于CPU的L1/L2/L3緩存，采用這種平滑的開銷逐漸增大，容量逐漸增大的機(jī)制，并配合以設(shè)計(jì)良好的換入/換出等算法，效果是非常明顯的。