在《linux內存管理淺析》中提到內核管理自己使用的內存時，使用了SLAB對象池。SLAB確實是比較復雜，所以一直以來都沒有深入看一看。
不過現在，linux內核中，SLAB已經被它的簡化版--SLUB所代替。最近抽時間看了一下SLUB的代碼，略記一些自己的理解。
盡管SLUB是在內核里面實現的，用戶態的對象池其實也可以借鑒這樣的做法。

SLUB的總體思想還是跟SLAB類似，對象池里面的內存都是以“大塊”為單位來進行分配與回收的。然后每個“大塊”又按對象的大小被分割成“小塊”，使用者對于對象的分配與回收都是以“小塊”為單位來進行的。

SLUB的結構如下圖：

另外，kmem_cache還有以下一些參數（后面會解釋到）：
int size;???????? /* 每個對象占用的空間 */
int objsize;????? /* 對象的大小 */
int offset;?????? /* 對象所占用的空間中，存放next指針的偏移 */
int refcount;???? /* 引用計數 */
int inuse;??????? /* 對象除next指針外所占用的大小 */
int align;??????? /* 對齊字節數 */
void (*ctor)(void *); /* 構造函數 */
unsigned long min_partial; /* kmem_cache_node中保存的最小page數 */
struct kmem_cache_order_objects oo; /* 首選的page分配策略（分配多少個連續頁面，能劃分成多少個對象） */
struct kmem_cache_order_objects min; /* 次選的page分配策略 */
（另外還有一些成員，或支持了一些選項、或支持了DEBUG、或是為周期性的內存回收服務。這里就不列舉了。）

?

大體結構

kmem_cache是對象池管理器，每一個kmem_cache管理一種類型的對象。所有的管理器通過雙向鏈表由表頭slab_caches串連起來。
這一點跟之前的SLAB是一樣的。

kmem_cache的內存管理工作是通過成員kmem_cache_node來完成的。在NUMA環境下（非均質存儲結構），一個kmem_cache維護了一組kmem_cache_node，分別對應每一個內存節點。kmem_cache_node只負責管理對應內存節點下的內存。（如果不是 NUMA環境，那么kmem_cache_node只有一個。）

而實際的內存還是靠page結構來管理的，kmem_cache_node通過partial指針串連起一組page（nr_partial代表鏈表長度），它們就代表了對象池里面的內存。page結構不僅代表了內存，結構里面還有一些union變量用來記錄其對應內存的對象分配情況（僅當page被加入到SLUB分配器后有效，其他情況下這些變量有另外的解釋）。
原先的SLAB則要復雜一些，SLAB里面的page僅僅是管理內存，不維護“對象”的概念。而是由額外的SLAB控制結構（slab）來管理對象，并通過slab結構的一些指針數組來劃定對象的邊界。

前面說過，對象池里面的內存是以“大塊”為單位來進行分配與回收的，page就是這樣的大塊。page內部被劃分成若干個小塊，每一塊用于容納一個對象。這些對象是以鏈表的形式來存儲的，page->freelist就是鏈表頭，只有未被分配的對象才會放在鏈表中。對象的next指針存放在其偏移量為kmem_cache->offset的位置。（見上面的圖）
而在SLAB中，“大塊”則是提供控制信息的slab結構。page結構只表示內存，它僅是slab所引用的資源。

每一個page并不只代表一個頁面，而是2^order個連續的頁面，這里的order值是由kmem_cache里面的oo或min來確定的。分配頁面時，首先嘗試使用oo里面的order值，分配較合適大小的連續頁面（這個值是在kmem_cache創建的時候計算出來的，使用這個值時需要分配一定的連續頁面，以使得內存分割成“小塊”后剩余的邊角廢料較少）。如果分配不成功（運行時間長了，內存碎片多了，分配大量連續頁面就不容易了），則使用min里面的order值，分配滿足對象大小的最少量的連續頁面（這個值也是創建kmem_cache時計算出來的）。

kmem_cache_node通過partial指針串連的一組page，這些page必須是沒被占滿的（一個page被劃分成page->objects個對象大小的空間，這些空間中有page->inuse個已經被使用。如果page->objects==page->inuse，則page為full）。如果一個page為full，則它會被從鏈表中移除。而如果page是free的（page->inuse==0），一般情況下它也會被釋放，除非這里的nr_partial（鏈表長度）小于kmem_cache里面的min_partial。（既然是池，就應該有一定的存量，min_partial就代表最低存量。這個值也是在創建kmem_cache時計算出來的，對象的size較大時，會得到較大的min_partial值。因為較大的size值在分配page時會需要更多連續頁面，而分配連續頁面不如單個的頁面容易，所以應該多緩存一些。）
而原先的SLAB則有三個鏈表，分別維護“full”、“partial”、“free”的slab。“free”和“partial”在SLUB里面合而為一，成了前面的partial鏈表。而“full”的page就不維護了。其實也不需要維護，因為page已經full了，不能再滿足對象的分配，只能響應對象的回收。而在對象回收時，通過對象的地址就能得到對應的page結構（page結構的地址是與內存地址相對應的，見《linux內存管理淺析》）。維護full的page可以便于查看分配器的狀態，所以在DEBUG模式下，kmem_cache_node里面還是會提供一個full鏈表。

分配與釋放

對象的分配與釋放并不是直接在kmem_cache_node上面操作的，而是在kmem_cache_cpu上。一個kmem_cache維護了一組kmem_cache_cpu，分別對應系統中的每一個CPU。kmem_cache_cpu相當于為每一個CPU提供了一個分配緩存，以避免CPU總是去kmem_cache_node上面做操作，而產生競爭。并且kmem_cache_cpu能讓被它緩存的對象固定在一個CPU上，從而提高CPU的cache命中率。kmem_cache_cpu只提供了一個page的緩存。

原先的SLAB是為每個CPU提供了一個array_cache結構來緩存對象。對象在array_cache結構中的組織形式跟它在slab中的組織形式是不一樣的，這也就增加了復雜性。而SLUB則都是通過page結構來組織對象的，組織形式都一樣。

進行對象分配的時候，首先嘗試在kmem_cache_cpu上去分配。如果分配不成功，再去kmem_cache_node上move一個page到kmem_cache_cpu上面來。分配不成功的原因有兩個：kmem_cache_cpu上的page已經full了、或者現在需要分配的node跟kmem_cache_cpu上緩存page對應的node不相同。對于page已full的情況，page被從kmem_cache_cpu上移除掉（或者DEBUG模式下，被移動到對應kmem_cache_node的full鏈表上）；而如果是node不匹配的情況，則kmem_cache_cpu上緩存page會先被move回到其對應kmem_cache_node的partial鏈表上（再進一步，如果page是free的，且partial鏈表的長度已經不小于min_partial了，則page被釋放）。
反過來，釋放對象的時候，通過對象的地址能找到它所對應的page的地址，將對象放歸該page即可。但是里面也有一些特殊邏輯，如果page正被kmem_cache_cpu緩存，就沒有什么需要額外處理的了；否則，在將對象放歸page時，需要對page加鎖（因為其他CPU也可能正在該page上分配或釋放對象）。另外，如果對象在回收之前該page是full的，則對象釋放后該page就成partial的了，它還應該被添加到對應的kmem_cache_node的partial鏈表中。而如果對象回收之后該page成了free的，則它應該被釋放掉。
對象的釋放還有一個細節，既然對象會放回到對應的page上去，那如果這個page正在被其他的CPU?cache呢（其他CPU的kmem_cache_cpu正指使用這個page）？其實沒關系，kmem_cache_cpu和page各自有一個freelist指針，當page被一個CPU cache時，page的freelist上的所有對象全部移動到kmem_cache_cpu的freelist上面去（其實就是一個指針賦值），page的freelist變成NULL。而釋放的時候是釋放到page的freelist上去。兩個freelist互不影響。但是這個地方貌似有個問題，如果一個被cache的page的freelist由于對象的釋放而變成非NULL，那么這個page就可能再被cache到其他CPU的kmem_cache_cpu上面去，于是多個kmem_cache_cpu可能cache同一個page。這將導致一個CPU內部的緩存可能cache到其他CPU上的對象（因為CPU緩存跟對象并不是對齊的），從而一個CPU上的對象寫操作可能引起另一個CPU的緩存失效。

在kmem_cache被創建的時候，SLUB會根據各種各樣的信息，計算出對象池的合理布局（見上面的圖）。objsize是對象本身的大小；這個大小經過對齊處理以后就成了inuse；緊貼inuse的后面可能會存放對象的next指針（由offset來標記），從而將對象實際占用的大小擴大到size。
其實，這里的offset并不總是指向inuse后面的位置（否則offset就可以用inuse來代替了）。offset有兩種可能的取值，一是 inuse、一是0。這里的offset指定了next指針的位置，而next是為了將對象串連在空閑鏈表中。那么，需要用到next指針的時候，對象必定是空閑的，對象里面的空間是未被使用的。于是正好，對象里的第一個字長的空間就拿來當next指針好了，此時offset就是0。但是在一些特殊情況下，對象里面的空間不能被復用作next指針，比如對象提供了構造函數ctor，那么對象的空間是被構造過的。此時，offset就等于inuse，next指針只好存放在對象的空間之后。

關于kmem_cache_cpu

前面在講對象分配與釋放的時候，著重講的是過程。下面再細細分析一下kmem_cache_cpu的作用。

如果沒有kmem_cache_cpu，那么分配對象的過程就應該是：
1、從對應的kmem_cache_node的partial鏈表里面選擇一個page；
2、從選中的page的freelist鏈表里面選擇一個對象；
這就是最基本的分配過程。

但是這個過程有個不好的地方，kmem_cache_node的partial鏈表是全局的、page的freelist鏈表也是全局的：
1、第一步訪問partial鏈表的時候，需要上鎖；
2、第二步訪問page->freelist鏈表的時候，也需要上鎖；
3、對象可能剛在CPU1上被釋放，又馬上被CPU2分配走。不利于CPU cache；

引入kmem_cache_cpu就是對這一問題的優化。每個CPU各自對應一個kmem_cache_cpu實例，用于緩存第一步中選中的那個page。這樣一來，第一步就不需要上鎖了；而page中的對象在一段時間內也將趨于在同一個CPU上使用，有利于CPU cache。
而kmem_cache_cpu中的freelist則是為了避免第二步的上鎖。

假設沒有kmem_cache_cpu->freelist，而page->freelist初始時有1、2、3、4，四個對象?？紤]如下事件序列：
1、page被CPU1所cache，然后1、2被分配；
2、由于在CPU1上請求的node id與該page不匹配，page被放回kmem_cache_node的partial鏈表，那么此時page->freelist還剩3和4兩個對象；
3、page又被CPU2所cache（page在上一步已經被放回partial鏈表了）。
此時，page->freelist就有可能被CPU1和CPU2兩個CPU所訪問，當對象1或2被釋放時（這兩個對象已經分配給了CPU1），CPU1會訪問page->freelist；而顯然CPU2分配對象時也要會訪問page->freelist。

所以為了避免上鎖，kmem_cache_cpu要維護自己的freelist，把page->freelist下的對象都接管過來。
這樣一來，CPU1就只跟page->freelist打交道，CPU2跟kmem_cache_cpu的freelist打交道，就不需要上鎖了。

?

關于page同時被多CPU使用

前面還提到，從屬于同一個page的對象可能cache到不同CPU上，從而可能對CPU的緩存造成一定的影響。不過這似乎也是沒辦法的事情。

首先，初始狀態下，page加入到slub之后，從屬于該page的對象都是空閑的，都存在于page->freelist中；
然后，這個page可能被某個CPU的kmem_cache_cpu所cache，假設是CPU-0，那么這個kmem_cache_cpu將得到屬于該page的所有對象。 page->freelist將為空；
接下來，這個page下的一部分對象可能在CPU-0上被分配出去；
再接著，可能由于NUMA的node不匹配，這個page從CPU-0的kmem_cache_cpu上面脫離下來。這時page->freelist將保存著那些未被分配出去的對象（而其他的對象已經在CPU-0上被分配出去了）；

這時，從屬于該page的一部分對象正在CPU-0上被使用著，另一部分對象存在于page->freelist中。
那么，現在就有兩個選擇：
1、不將這個page放回partial list，阻止其他CPU使用這個page；
2、將這個page放回partial list，允許其他CPU使用這個page；

對于第一種做法，可以避免屬于同一個page的對象被cache到不同CPU。但是這個page必須等到CPU-0再次cache它以后才能被繼續使用；或者等待CPU-0所使用的從屬于這個page的對象全都被釋放，然后這個page才能被放回partial list或者直接被釋放掉。
這樣一來，一個page盡管擁有空閑的對象，卻可能在一定時間內處于不可用狀態（極端情況是永遠不可用）。這樣實現的系統似乎不太可控……

而現在的slub選擇了第二種做法，將page放回partial list，于是page馬上就能被其他CPU使用起來。那么，由此引發的從屬于同一個page的對象被cache到不同CPU的問題，也就是沒辦法的事情……

?

vs slab

相比SLAB，SLUB還有一個比較有意思的特性。當創建新的對象池時，如果發現原先已經創建的某個kmem_cache的size剛好等于或略大于新的size，則新的kmem_cache不會被創建，而是復用這個大小差不多kmem_cache。所以kmem_cache里面還維護了一個refcount（引用計數），表示它被復用的次數。

另外，SLUB也去掉了SLAB中很有意思的一個特性，Coloring（著色）。
什么是著色呢？一個內存“大塊”，在按對象大小劃分成“小塊”的時候，可能并不是那么剛好，還會空余一些邊邊角角。著色就是利用這些邊邊角角來做文章，使得“小塊”的起始地址并不總是等于“大塊”內的0地址，而是在0地址與空余大小之間浮動。這樣就使得同一種類型的各個對象，其地址的低幾位存在更多的變化。
為什么要這樣做呢？這是考慮到了CPU的cache。在學習操作系統原理的時候我們都聽說過，為提高CPU對內存的訪存效率，CPU提供了cache。于是就有了從內存到cache之間的映射。當CPU指令要求訪問一個內存地址的時候，CPU會先看看這個地址是否已經被緩存了。
內存到cache的映射是怎么實現的呢？或者說CPU怎么知道某個內存地址有沒有被緩存呢？
一種極端的設計是“全相連映射”，任何內存地址都可以映射到任何的cache位置上。那么CPU拿到一個地址時，它可能被緩存的cache位置就太多了，需要維護一個龐大的映射關系表，并且花費大量的查詢時間，才能確定一個地址是否被緩存。這是不太可取的。
于是，cache的映射總是會有這樣的限制，一個內存地址只可以被映射到某些個cache位置上。而一般情況下，內存地址的低幾位又決定了內存被cache的位置（如：cache_location = address % cache_size）。
好了，回到SLAB的著色，著色可以使同一類型的對象其低幾位地址相同的概率減小，從而使得這些對象在cache中映射沖突的概率降低。
這有什么用呢？其實同一種類型的很多對象被放在一起使用的情況是很多的，比如數組、鏈表、vector、等等情況。當我們在遍歷這些對象集合的時候，如果每一個對象都能被CPU緩存住，那么這段遍歷代碼的處理效率勢必會得到提升。這就是著色的意義所在。
SLUB把著色給去掉了，是因為對內存使用更加摳門了，盡可能的把邊邊角角減少到最小，也就干脆不要著色了。還有就是，既然kmem_cache可以被size差不多的多種對象所復用，復用得越多，著色也就越沒意義了。

轉載于:https://www.cnblogs.com/wangfengju/archive/2013/05/11/6173088.html

總結

以上是生活随笔為你收集整理的linux slub分配器浅析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。