Linux SLUB 分配器詳解

多年以來，Linux 內核使用一種稱為 SLAB 的內核對象緩衝區分配器。但是，隨著系統規模的不斷增大，SLAB 逐漸暴露出自身的諸多不足。SLUB 是 Linux 內核 2.6.22 版本中引入的一種新型分配器，它具有設計簡單、代碼精簡、額外內存佔用率小、擴展性高，性能優秀、方便調試等特點。本文先介紹 SLAB 分配器的基本原理，然後分析其不足之處並詳細介紹 SLUB 的設計思想，最後介紹 SLUB 介面 API 函數及對象分配/釋放函數的具體實現。

內核對象緩衝區管理

Linux 內核在運行過程中，常常會需要經常使用一些內核的數據結構（對象）。例如，當進程的某個線程第一次打開一個文件的時候，內核需要為該文件分配一個稱為 file 的數據結構；當該文件被最終關閉的時候，內核必須釋放此文件所關聯的 file 數據結構。這些小塊存儲空間並不只在某個內核函數的內部使用，否則就可以使用當前線程的內核棧空間。同時，這些小塊存儲空間又是動態變化的，不可能像物理內存頁面管理使用的 page 結構那樣，有多大內存就有多少個 page 結構，形成一個靜態長度的隊列。而且由於內核無法預測運行中各種不同的內核對象對緩衝區的需求，因此不適合為每一種可能用到的對象建立一個“緩衝池”，因為那樣的話很可能出現有些緩衝池已經耗盡而有些緩衝池中卻又大量空閑緩衝區的現象。因此，內核只能採取更全局性的方法。

我們可以看出，內核對象的管理與用戶進程中的堆管理比較相似，核心問題均是：如何高效地管理內存空間，使得可以快速地進行對象的分配和回收並減少內存碎片。但是內核不能簡單地採用用戶進程的基於堆的內存分配演算法，這是因為內核對其對象的使用具有以下特殊性：

1. 內核使用的對象種類繁多，應該採用一種統一的高效管理方法。
2. 內核對某些對象（如 task_struct）的使用是非常頻繁的，所以用戶進程堆管理常用的基於搜索的分配演算法比如First-Fit（在堆中搜索到的第一個滿足請求的內存塊）和 Best-Fit（使用堆中滿足請求的最合適的內存塊）並不直接適用，而應該採用某種緩衝區的機制。
3. 內核對象中相當一部分成員需要某些特殊的初始化（例如隊列頭部）而並非簡單地清成全 0。如果能充分重用已被釋放的對象使得下次分配時無需初始化，那麼可以提高內核的運行效率。
4. 分配器對內核對象緩衝區的組織和管理必須充分考慮對硬體高速緩存的影響。
5. 隨著共享內存的多處理器系統的普及，多處理器同時分配某種類型對象的現象時常發生，因此分配器應該盡量避免處理器間同步的開銷，應採用某種 Lock-Free 的演算法。

如何有效地管理緩衝區空間，長期以來都是一個熱門的研究課題。90 年代初期，在 Solaris 2.4 操作系統中，採用了一種稱為“slab”（原意是大塊的混凝土）的緩衝區分配和管理方法，在相當程度上滿足了內核的特殊需求。

SLAB 分配器介紹

多年以來，Linux 內核使用一種稱為 SLAB 的內核對象緩衝區分配器。SLAB 分配器源於 Solaris 2.4 的分配演算法，工作於物理內存頁框分配器之上，管理特定大小對象的緩存，進行快速而高效的內存分配。

SLAB 分配器為每種使用的內核對象建立單獨的緩衝區。Linux 內核已經採用了夥伴系統（Buddy System）管理物理內存頁框，因此 SLAB 分配器直接工作於夥伴系統之上。每種緩衝區由多個 slab 組成，每個 slab就是一組連續的物理內存頁框，被劃分成了固定數目的對象。根據對象大小的不同，預設情況下一個 slab 最多可以由 1024 個物理內存頁框構成。出於對齊等其它方面的要求，slab 中分配給對象的內存可能大於用戶要求的對象實際大小，這會造成一定的內存浪費。

由於內核對象在使用前和釋放后可能需要做某些特殊處理，緩衝區擁有自己的“構造函數（constructor）”和“析構函數（destructor）”，類似於C++ 等面向對象編程語言中的概念（不過最新版本的 SLAB 分配器取消了析構函數）。創建新 slab 時內核調用構造函數初始化每個對象，釋放 slab 時則調用析構函數。這就是內核數據結構被稱為對象的原因。

內核使用 kmem_cache 數據結構管理緩衝區。由於 kmem_cache 自身也是一種內核對象，所以需要一個專門的緩衝區。所有緩衝區的 kmem_cache 控制結構被組織成以 cache_chain 為隊列頭的一個雙向循環隊列，同時 cache_cache 全局變數指向kmem_cache 對象緩衝區的 kmem_cache 對象。每個 slab 都需要一個類型為 struct slab 的描述符數據結構管理其狀態，同時還需要一個 kmem_bufctl_t（被定義為無符號整數）的結構數組來管理空閑對象。如果對象不超過 1/8 個物理內存頁框的大小，那麼這些 slab 管理結構直接存放在 slab 的內部，位於分配給 slab 的第一個物理內存頁框的起始位置；否則的話，存放在 slab 外部，位於由 kmalloc 分配的通用對象緩衝區中。

slab 中的對象有 2 種狀態：已分配或空閑。為了有效地管理 slab，根據已分配對象的數目，slab 可以有 3 種狀態，動態地處於緩衝區相應的隊列中：

1. Full 隊列，此時該 slab 中沒有空閑對象。
2. Partial 隊列，此時該 slab 中既有已分配的對象，也有空閑對象。
3. Empty 隊列，此時該 slab 中全是空閑對象。

NUMA（Non Uniform Memory Access） 系統中，每個節點都會擁有這 3 種 slab 隊列，struct kmem_list3結構用於維護相關隊列。SLAB 分配器優先從 Partial 隊列里的 slab 中分配對象。當 slab 的最後一個已分配對象被釋放時，該 slab 從 Partial 隊列轉移到 Empty 隊列；當 slab 的最後一個空閑對象被分配時，該 slab 從Partial 隊列轉移到Full 隊列里。緩衝區中空閑對象總數不足時，則分配更多的 slab；但是如果空閑對象比較富餘，Empty 隊列的部分 slab 將被定期回收。

為了充分利用硬體高速緩存，SLAB 分配器允許對象在一級硬體高速緩存中對齊（創建緩衝區時，設置 SLAB_HWCACHE_ALIGN 標誌）；同時使用著色（color）策略，使得同一緩衝區內不同 slab 中相同編號的對象的地址相互錯開，避免它們被放入同一物理高速緩存行而造成頻繁換入/換出的性能損失。

為了支持多處理器同時分配對象，緩衝區為每個處理器維護一個本地緩存。處理器直接從本地緩存中分配對象，從而避免了鎖的使用；當本地緩存為空時，從 slab 中批量分配對象到本地緩存。

SLUB 分配器的設計原理

SLAB 分配器多年以來一直位於 Linux 內核的內存管理部分的核心地帶，內核黑客們一般不願意主動去更改它的代碼，因為它實在是非常複雜，而且在大多數情況下，它的工作完成的相當不錯。但是，隨著大規模多處理器系統和 NUMA系統的廣泛應用，SLAB 分配器逐漸暴露出自身的嚴重不足：

1. 較多複雜的隊列管理。在 SLAB 分配器中存在眾多的隊列，例如針對處理器的本地對象緩存隊列，slab 中空閑對象隊列，每個 slab 處於一個特定狀態的隊列中，甚至緩衝區控制結構也處於一個隊列之中。有效地管理這些不同的隊列是一件費力且複雜的工作。
2. slab 管理數據和隊列的存儲開銷比較大。每個 slab 需要一個 struct slab 數據結構和一個管理所有空閑對象的 kmem_bufctl_t（4 位元組的無符號整數）的數組。當對象體積較少時，kmem_bufctl_t 數組將造成較大的開銷（比如對象大小為32位元組時，將浪費 1/8 的空間）。為了使得對象在硬體高速緩存中對齊和使用著色策略，還必須浪費額外的內存。同時，緩衝區針對節點和處理器的隊列也會浪費不少內存。測試表明在一個 1000 節點/處理器的大規模 NUMA 系統中，數 GB 內存被用來維護隊列和對象的引用。
3. 緩衝區內存回收比較複雜。
4. 對 NUMA 的支持非常複雜。SLAB 對 NUMA 的支持基於物理頁框分配器，無法細粒度地使用對象，因此不能保證處理器級緩存的對象來自同一節點。
5. 冗餘的 Partial 隊列。SLAB 分配器針對每個節點都有一個 Partial 隊列，隨著時間流逝，將有大量的 Partial slab 產生，不利於內存的合理使用。
6. 性能調優比較困難。針對每個 slab 可以調整的參數比較複雜，而且分配處理器本地緩存時，不得不使用自旋鎖。
7. 調試功能比較難於使用。

為了解決以上 SLAB 分配器的不足之處，內核開發人員 Christoph Lameter 在 Linux 內核 2.6.22 版本中引入一種新的解決方案：SLUB 分配器。SLUB 分配器特點是簡化設計理念，同時保留 SLAB 分配器的基本思想：每個緩衝區由多個小的 slab 組成，每個 slab 包含固定數目的對象。SLUB 分配器簡化了kmem_cache，slab 等相關的管理數據結構，摒棄了SLAB 分配器中眾多的隊列概念，並針對多處理器、NUMA 系統進行優化，從而提高了性能和可擴展性並降低了內存的浪費。為了保證內核其它模塊能夠無縫遷移到 SLUB 分配器，SLUB 還保留了原有 SLAB 分配器所有的介面 API 函數。

本文所列的數據結構和源代碼均摘自 Linux 內核 2.6.25 版本。

每個內核對象緩衝區都是由 kmem_cache 類型的數據結構來描述的，表 1 列出了它的欄位（省略了統計和調試相關的欄位）。

我們可以看到，SLUB 分配器的 kmem_cache 結構相對 SLAB 而言簡化了不少，而且沒有了隊列的相關欄位。值得注意的是 SLUB 分配器具有緩衝區合併的功能：當內核執行緒請求創建新的緩衝區 C2 時，SLUB 分配器會先搜索已創建的緩衝區，如果發現某緩衝區 C1 的對象大小略大於 C2，則重用 C1。測試表明，這項功能減少了大約 50% 的緩衝區數目，從而減少了 slab 碎片並提高了內存利用率。

在 SLUB 分配器中，一個 slab 就是一組連續的物理內存頁框，被劃分成了固定數目的對象。slab 沒有額外的空閑對象隊列（這與 SLAB 不同），而是重用了空閑對象自身的空間。slab 也沒有額外的描述結構，因為 SLUB 分配器在代表物理頁框的 page 結構中加入 freelist，inuse 和 slab 的 union 欄位，分別代表第一個空閑對象的指針，已分配對象的數目和緩衝區 kmem_cache 結構的指針，所以 slab 的第一個物理頁框的 page 結構就可以描述自己。

每個處理器都有一個本地的活動 slab，由 kmem_cache_cpu 結構描述。表 2 列出它的欄位（省略了統計相關的欄位）。

在 SLUB 中，沒有單獨的 Empty slab 隊列。每個 NUMA 節點使用 kmem_cache_node 結構維護一個處於 Partial 狀態的 slab 隊列。表 3 列出它的欄位（省略了調試相關的欄位）。

創建處理器活動 slab時，第一個空閑對象的指針被複制到 kmem_cache_cpu 結構的 freelist 欄位中。雖然對象分配和釋放的操作只針對處理器本地的活動 slab，但是在某些特殊的情況下會為當前處理器創建新的活動 slab 並把原先未用完的活動 slab 加到 NUMA 節點 的Partial 隊列中（例如，在處理器 A 上運行的某內核執行緒申請對象，但是 A 的活動 slab 中已經沒有空閑對象，因此必須創建新的 slab。但是創建 slab 的操作可能導致睡眠，所以當創建操作完成後該執行緒可能被調度到處理器 B 上，這將停止使用 B 原有的活動 slab，並將其加入 B 所在節點的 Partial 隊列中）。相較 SLAB 而言，處於Partial 狀態的 slab 的數目比較少，因此合理有效地利用了內存。當本地 slab 沒有空閑對象時，SLUB 分配器優先從處理器所在節點的 Partial 隊列中分配一個 slab 作為新的本地活動 slab，其次從其它節點中分配 slab。

內核執行緒申請對象時，直接從所在處理器的kmem_cache_cpu 結構的 freelist 欄位獲得第一個空閑對象的地址，然後更新 freelist 欄位，使其指向下一個空閑對象。釋放對象時，如果對象屬於所在處理器的活動 slab 中，直接將其添加到空閑對象隊列的隊首，並更新 freelist 欄位；否則的話，對象一定屬於某 Partial slab 中。如果釋放操作使得該 Partial slab 轉變成 Empty 狀態，則釋放該 slab。可見 SLUB 分配器不需要複雜的緩衝區內存回收機制。

SLUB 的調試代碼總是可用，一旦激活“slab_debug”選項，用戶就可以很方便地選擇單個或一組指定的緩衝區進行動態調試。

內核函數常常需要臨時分配一塊任意大小的物理地址連續的內存空間，如果請求不頻繁的話，則沒有必要創建單獨的緩衝區。Linux 內核為這種請求準備了一組特定大小的通用對象緩衝區。調用 kmalloc 函數就可以得到符合請求大小的內存空間，調用 kfree 則釋放該內存空間。kmalloc 工作於 SLUB 分配器之上。內核初始化時，創建一組共 13 個通用對象的緩衝區。kmalloc_caches 數組存放了這些緩衝區的 kmem_cache 數據結構。由於 kmem_cache 數據結構是通過 kmalloc 來分配的，故而只能用靜態分配的 kmem_cache 結構數組來描述通用對象的緩衝區。其中 kmalloc_caches[0] 代表的緩衝區專門分配 kmem_cache_node 結構。kmalloc_caches[1] 緩衝區對象大小為64，kmalloc_caches[2] 緩衝區對象大小為192，其餘第 i（3-12）號緩衝區對象大小為 2^i。如果請求分配超過物理頁面大小的對象，直接調用頁框分配器。為了滿足老式 ISA 設備的需要，內核還使用 DMA 內存創建了 13 個通用對象的緩衝區，用 kmalloc_caches_dma 數組存放相應的 kmem_cache 結構。

SLUB 分配器的實現

為了保證內核其它模塊能夠無縫遷移到 SLUB 分配器，SLUB保留了原有 SLAB 分配器所有的介面 API 函數。表 4 列出主要的 API 函數：

下面介紹 kmem_cache_alloc，kmem_cache_alloc_node 和 kmem_cache_free 三個函數的實現細節。kmem_cache_alloc 和 kmem_cache_alloc_node 函數都是直接調用 slab_alloc 函數，只是 kmem_cache_alloc 傳入的 node 參數為 -1；kmem_cache_free 則調用 slab_free 函數。

                  static __always_inline void *slab_alloc(struct kmem_cache *s,          gfp_t gfpflags, int node, void *addr)  {      void **object;      struct kmem_cache_cpu *c;      unsigned long flags;        local_irq_save(flags);      c = get_cpu_slab(s, smp_processor_id());                         (a)      if (unlikely(!c->freelist || !node_match(c, node)))          object = __slab_alloc(s, gfpflags, node, addr, c);         (b)      else {          object = c->freelist;                                            (c)          c->freelist = object[c->offset];          stat(c, ALLOC_FASTPATH);      }      local_irq_restore(flags);        if (unlikely((gfpflags & __GFP_ZERO) && object))          memset(object, 0, c->objsize);        return object;                                                         (d)  }  

1. 獲取本處理器的 kmem_cache_cpu 數據結構。
2. 假如當前活動 slab 沒有空閑對象，或本處理器所在節點與指定節點不一致，則調用 __slab_alloc 函數。
3. 獲得第一個空閑對象的指針，然後更新指針使其指向下一個空閑對象。
4. 返回對象地址。

                  static void *__slab_alloc(struct kmem_cache *s,          gfp_t gfpflags, int node, void *addr, struct kmem_cache_cpu *c)  {      void **object;      struct page *new;        gfpflags &= ~__GFP_ZERO;        if (!c->page)                                                          (a)          goto new_slab;        slab_lock(c->page);      if (unlikely(!node_match(c, node)))                                (b)          goto another_slab;        stat(c, ALLOC_REFILL);    load_freelist:      object = c->page->freelist;      if (unlikely(!object))                                                (c)          goto another_slab;      if (unlikely(SlabDebug(c->page)))          goto debug;        c->freelist = object[c->offset];                                    (d)      c->page->inuse = s->objects;      c->page->freelist = NULL;      c->node = page_to_nid(c->page);  unlock_out:      slab_unlock(c->page);      stat(c, ALLOC_SLOWPATH);      return object;    another_slab:      deactivate_slab(s, c);                                                (e)    new_slab:      new = get_partial(s, gfpflags, node);                              (f)      if (new) {          c->page = new;          stat(c, ALLOC_FROM_PARTIAL);          goto load_freelist;      }        if (gfpflags & __GFP_WAIT)                                           (g)          local_irq_enable();        new = new_slab(s, gfpflags, node);                                 (h)        if (gfpflags & __GFP_WAIT)          local_irq_disable();        if (new) {          c = get_cpu_slab(s, smp_processor_id());          stat(c, ALLOC_SLAB);          if (c->page)              flush_slab(s, c);          slab_lock(new);          SetSlabFrozen(new);          c->page = new;          goto load_freelist;      }      if (!(gfpflags & __GFP_NORETRY) &&                  (s->flags & __PAGE_ALLOC_FALLBACK)) {          if (gfpflags & __GFP_WAIT)              local_irq_enable();          object = kmalloc_large(s->objsize, gfpflags);                (i)          if (gfpflags & __GFP_WAIT)              local_irq_disable();          return object;      }      return NULL;  debug:      if (!alloc_debug_processing(s, c->page, object, addr))          goto another_slab;        c->page->inuse++;      c->page->freelist = object[c->offset];      c->node = -1;      goto unlock_out;  }  

1. 如果沒有本地活動 slab，轉到 (f) 步驟獲取 slab 。
2. 如果本處理器所在節點與指定節點不一致，轉到 (e) 步驟。
3. 檢查處理器活動 slab 沒有空閑對象，轉到 (e) 步驟。
4. 此時活動 slab 尚有空閑對象，將 slab 的空閑對象隊列指針複製到 kmem_cache_cpu 結構的 freelist 欄位，把 slab 的空閑對象隊列指針設置為空，從此以後只從 kmem_cache_cpu 結構的 freelist 欄位獲得空閑對象隊列信息。
5. 取消當前活動 slab，將其加入到所在 NUMA 節點的 Partial 隊列中。
6. 優先從指定 NUMA 節點上獲得一個 Partial slab。
7. 加入 gfpflags 標誌置有 __GFP_WAIT，開啟中斷，故後續創建 slab 操作可以睡眠。
8. 創建一個 slab，並初始化所有對象。
9. 如果內存不足，無法創建 slab，調用 kmalloc_large（實際調用物理頁框分配器）分配對象。

                  static __always_inline void slab_free(struct kmem_cache *s,              struct page *page, void *x, void *addr)  {      void **object = (void *)x;      struct kmem_cache_cpu *c;      unsigned long flags;        local_irq_save(flags);      c = get_cpu_slab(s, smp_processor_id());      debug_check_no_locks_freed(object, c->objsize);      if (likely(page == c->page && c->node >= 0)) {                   (a)          object[c->offset] = c->freelist;          c->freelist = object;          stat(c, FREE_FASTPATH);      } else          __slab_free(s, page, x, addr, c->offset);                     (b)        local_irq_restore(flags);  }  

1. 如果對象屬於處理器當前活動的 slab，或處理器所在 NUMA 節點號不為 -1（調試使用的值），將對象放回空閑對象隊列。
2. 否則調用 __slab_free 函數。

                  static void __slab_free(struct kmem_cache *s, struct page *page,                  void *x, void *addr, unsigned int offset)  {      void *prior;      void **object = (void *)x;      struct kmem_cache_cpu *c;        c = get_cpu_slab(s, raw_smp_processor_id());      stat(c, FREE_SLOWPATH);      slab_lock(page);        if (unlikely(SlabDebug(page)))          goto debug;    checks_ok:      prior = object[offset] = page->freelist;                          (a)      page->freelist = object;      page->inuse--;        if (unlikely(SlabFrozen(page))) {          stat(c, FREE_FROZEN);          goto out_unlock;      }        if (unlikely(!page->inuse))                                          (b)          goto slab_empty;        if (unlikely(!prior)) {                                               (c)          add_partial(get_node(s, page_to_nid(page)), page, 1);          stat(c, FREE_ADD_PARTIAL);      }    out_unlock:      slab_unlock(page);      return;    slab_empty:      if (prior) {                                                            (d)          remove_partial(s, page);          stat(c, FREE_REMOVE_PARTIAL);      }      slab_unlock(page);      stat(c, FREE_SLAB);      discard_slab(s, page);      return;    debug:      if (!free_debug_processing(s, page, x, addr))          goto out_unlock;      goto checks_ok;  }  

1. 執行本函數表明對象所屬 slab 並不是某個活動 slab。保存空閑對象隊列的指針，將對象放回此隊列，最後把已分配對象數目減一。
2. 如果已分配對象數為 0，說明 slab 處於 Empty 狀態，轉到 (d) 步驟。
3. 如果原空閑對象隊列的指針為空，說明 slab 原來的狀態為 Full，那麼現在的狀態應該是 Partial，將該 slab 加到所在節點的 Partial 隊列中。
4. 如果 slab 狀態轉為 Empty，且先前位於節點的 Partial 隊列中，則將其剔出並釋放所佔內存空間。

總結

SLUB 是 Linux Kernel 2.6.22 版本引入的一種新的內核對象緩衝區分配器，它具有設計簡單、代碼精簡、額外內存佔用率小、擴展性高，性能優秀、方便調試等特點。測試表明，SLUB 相對 SLAB 的性能提升大約在 5-10%，可以預見在不久的將來，SLUB 分配器一定能徹底取代 SLAB。

（責任編輯：A6）