多年以來,Linux 內核使用一種稱為 SLAB 的內核對象緩衝區分配器。但是,隨著系統規模的不斷增大,SLAB 逐漸暴露出自身的諸多不足。SLUB 是 Linux 內核 2.6.22 版本中引入的一種新型分配器,它具有設計簡單、代碼精簡、額外內存佔用率小、擴展性高,性能優秀、方便調試等特點。本文先介紹 SLAB 分配器的基本原理,然後分析其不足之處並詳細介紹 SLUB 的設計思想,最後介紹 SLUB 介面 API 函數及對象分配/釋放函數的具體實現。
內核對象緩衝區管理
Linux 內核在運行過程中,常常會需要經常使用一些內核的數據結構(對象)。例如,當進程的某個線程第一次打開一個文件的時候,內核需要為該文件分配一個稱為 file 的數據結構;當該文件被最終關閉的時候,內核必須釋放此文件所關聯的 file 數據結構。這些小塊存儲空間並不只在某個內核函數的內部使用,否則就可以使用當前線程的內核棧空間。同時,這些小塊存儲空間又是動態變化的,不可能像物理內存頁面管理使用的 page 結構那樣,有多大內存就有多少個 page 結構,形成一個靜態長度的隊列。而且由於內核無法預測運行中各種不同的內核對象對緩衝區的需求,因此不適合為每一種可能用到的對象建立一個“緩衝池”,因為那樣的話很可能出現有些緩衝池已經耗盡而有些緩衝池中卻又大量空閑緩衝區的現象。因此,內核只能採取更全局性的方法。
我們可以看出,內核對象的管理與用戶進程中的堆管理比較相似,核心問題均是:如何高效地管理內存空間,使得可以快速地進行對象的分配和回收並減少內存碎片。但是內核不能簡單地採用用戶進程的基於堆的內存分配演算法,這是因為內核對其對象的使用具有以下特殊性:
如何有效地管理緩衝區空間,長期以來都是一個熱門的研究課題。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 種狀態,動態地處於緩衝區相應的隊列中:
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 分配器逐漸暴露出自身的嚴重不足:
為了解決以上 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 列出了它的欄位(省略了統計和調試相關的欄位)。
類型 | 名稱 | 描述 |
unsigned long | flags | 描述緩衝區屬性的一組標誌 |
int | size | 分配給對象的內存大小(可能大於對象的實際大小) |
int | objsize | 對象的實際大小 |
int | offset | 存放空閑對象指針的位移 |
int | order | 表示一個 slab 需要 2^order 個物理頁框 |
kmem_cache_node | local_node | 創建緩衝區的節點的 slab 信息 |
int | objects | 一個 slab 中的對象總個數 |
gfp_t | allocflags | 創建一個 slab 時使用的一組額外標誌 |
int | refcount | 緩衝區計數器。當用戶請求創建新的緩衝區時,SLUB 分配器重用已創建的相似大小的緩衝區,從而減少緩衝區的個數。 |
void (*)(…) | ctor | 創建 slab 時用於初始化每個對象的構造函數 |
int | inuse | 元數據的位移 |
int | align | 對齊 |
const char * | name | 緩衝區名字 |
struct list_head | list | 包含所有緩衝區描述結構的雙向循環隊列,隊列頭為 slab_caches |
int | remote_node_defrag_ratio | 該值越小,越傾向從本節點中分配對象 |
struct kmem_cache_node * [] | node | 為每個節點創建的 slab 信息的數據結構(創建緩衝區的節點除外,使用 local_node 欄位) |
struct kmem_cache_cpu * [] | cpu_slab | 為每個處理器創建的 slab 信息的數據結構 |
我們可以看到,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 列出它的欄位(省略了統計相關的欄位)。
類型 | 名稱 | 描述 |
void ** | freelist | 空閑對象隊列的指針,即第一個空閑對象的指針 |
struct page * | page | slab 的第一個物理頁框描述符 |
int | node | 處理器所在 NUMA 節點號,值 -1 用於調試 |
unsigned int | offset | 用於存放下一個空閑對象指針的位移,以字(word)為單位 |
unsigned int | objsize | 對象實際大小,與 kmem_cache 結構 objsize 欄位一致 |
在 SLUB 中,沒有單獨的 Empty slab 隊列。每個 NUMA 節點使用 kmem_cache_node 結構維護一個處於 Partial 狀態的 slab 隊列。表 3 列出它的欄位(省略了調試相關的欄位)。
類型 | 名稱 | 描述 |
spinlock_t | list_lock | 保護 nr_partial 和 partial 欄位的自旋鎖 |
unsigned long | nr_partial | 本節點 Partial slab 的數目 |
atomic_long_t | nr_slabs | 本節點 slab 的總數 |
struct list_head | partial | Partial slab 的雙向循環隊列 |
創建處理器活動 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_create | 創建新的緩衝區。 |
kmem_cache_destroy | 銷毀緩衝區。因為存在重用緩衝區的情況,只有當 kmem_cache 結構的 refcount 欄位為 0時才真正銷毀。 |
kmem_cache_alloc | 從處理器本地的活動 slab 中分配對象。 |
kmem_cache_alloc_node | 如果指定的 NUMA 節點與本處理器所在節點不一致,則先從指定節點上獲取 slab,替換處理器活動 slab,然後分配對象。 |
kmem_cache_free | 釋放對象。如果對象屬於某 Partial slab 且釋放操作使這個 slab轉變成Empty 狀態,則釋放該 slab。 |
kmem_ptr_validate | 檢查給定對象的指針是否合法。 |
kmem_cache_size | 返回對象實際大小。 |
kmem_cache_shrink | 檢查各個節點的 Partial 隊列,回收實際處於 Empty 狀態的 slab,並將剩餘的 slab 按已分配對象的數目排序。 |
kmalloc | 從通用緩衝區中分配一個對象。 |
kmalloc_node | 從通用緩衝區中分配一個屬於指定 NUMA 節點的對象。 |
kfree | 釋放一個通用對象。 |
ksize | 返回分配給對象的內存大小(可能大於對象的實際大小) |
下面介紹 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) } |
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; } |
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); } |
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; } |
總結
SLUB 是 Linux Kernel 2.6.22 版本引入的一種新的內核對象緩衝區分配器,它具有設計簡單、代碼精簡、額外內存佔用率小、擴展性高,性能優秀、方便調試等特點。測試表明,SLUB 相對 SLAB 的性能提升大約在 5-10%,可以預見在不久的將來,SLUB 分配器一定能徹底取代 SLAB。
(責任編輯:A6)
[火星人 ] Linux SLUB 分配器詳解已經有659次圍觀