作者簡介：尹忠凱，Linux內(nèi)核愛好者，閱碼場用戶。現(xiàn)就職于北京地平線信息技術(shù)有限公司，任系統(tǒng)軟件工程師。

物理內(nèi)存分配設(shè)計(jì)有兩個(gè)重要的評(píng)價(jià)維度。一方面，物理內(nèi)存分配器要追求更高的內(nèi)存資源利用率，即盡可能減少資源浪費(fèi)。另一方面，物理內(nèi)存分配器要追求更好的性能，主要是盡可能降低分配延遲和節(jié)約CPU資源。

內(nèi)存碎片

內(nèi)存碎片指的是無法被利用的內(nèi)存，進(jìn)一步又可以分為外部碎片和內(nèi)部碎片。

外部碎片

圖1 外部碎片

如圖1所示，假設(shè)系統(tǒng)中共有25MB內(nèi)存，系統(tǒng)經(jīng)過長期的運(yùn)行后，使用了19MB內(nèi)存(帶顏色的部分)，假如此時(shí)想申請3MB內(nèi)存，總的空閑內(nèi)存是滿足要求的，但每一塊單獨(dú)的空閑內(nèi)存都不滿足要求。此時(shí)這些無法被使用的內(nèi)存稱為外部碎片。

內(nèi)部碎片

為了解決外部碎片問題，一種比較簡的方式就是將物理內(nèi)存以固定大小劃分成若干塊，每次用一個(gè)塊或者多個(gè)塊來滿足一次內(nèi)存請求。

圖2 內(nèi)部碎片

如圖2所示，還是這25MB內(nèi)存，這次以3MB大小固定塊來分配內(nèi)存，申請6MB內(nèi)存就分配兩個(gè)固定塊，申請3MB內(nèi)存分配一個(gè)固定塊，申請1MB內(nèi)存，也分配一個(gè)固定塊。可以看到此時(shí)外部碎片的問題是解決了，但是又引入了新的問題即只申請1MB內(nèi)存，卻分配了3MB內(nèi)存，多出的2MB內(nèi)存即為內(nèi)部碎片。

下面會(huì)介紹linux系統(tǒng)中的頁分配器和塊分配器，頁分配器用來解決外部碎片問題，而塊分配器用來解決內(nèi)部碎片問題，通過這兩個(gè)分配器，可以有效減少內(nèi)存碎片的產(chǎn)生，從而提高內(nèi)存資源的利用率。

物理內(nèi)存組織

在介紹頁分配器和塊分配器之前，先來了解下現(xiàn)代計(jì)算的物理內(nèi)存是如何組織的，因?yàn)橛行└拍钤诤竺鏁?huì)用到。

SMP架構(gòu)

圖3 SMP架構(gòu)

SMP架構(gòu)就是對稱多處理器，所有的CPU必須通過相同的內(nèi)存總線訪問相同的內(nèi)存資源。所以所有CPU訪問內(nèi)存等資源的速度是一樣的，即對稱。這種架構(gòu)的缺點(diǎn)是，CPU數(shù)量增加，內(nèi)存訪問沖突將迅速增加，最終會(huì)造成CPU資源的浪費(fèi)，使 CPU性能的有效性大大降低。

NUMA架構(gòu)

圖4 NUMA架構(gòu)

NUMA架構(gòu)將CPU劃分到多個(gè)Node中，每個(gè)node有自己獨(dú)立的內(nèi)存空間。各個(gè)node之間通過高速互聯(lián)通訊。CPU訪問不同類型節(jié)點(diǎn)內(nèi)存的速度是不相同的，訪問本地節(jié)點(diǎn)的速度最快，訪問遠(yuǎn)端節(jié)點(diǎn)的速度最慢，即訪問速度與節(jié)點(diǎn)的距離有關(guān)，距離越遠(yuǎn)訪問速度越慢，即非一致。這種架構(gòu)的缺點(diǎn)是，本node的內(nèi)存不足時(shí)，需要垮節(jié)點(diǎn)訪問內(nèi)存，節(jié)點(diǎn)間的訪問速度慢。

三級(jí)結(jié)構(gòu)

內(nèi)存管理子系統(tǒng)使用節(jié)點(diǎn)(node)、區(qū)域(zone)、和頁(page)三級(jí)結(jié)構(gòu)描述物理內(nèi)存。

圖5 物理內(nèi)存三級(jí)結(jié)構(gòu)

如圖5所示，在linux中使用三級(jí)結(jié)構(gòu)來描述物理內(nèi)存。

節(jié)點(diǎn)(node)：每個(gè)節(jié)點(diǎn)用一個(gè)struct pglist_data結(jié)構(gòu)體來表示，每個(gè)節(jié)點(diǎn)內(nèi)的內(nèi)存會(huì)劃分成不同的區(qū)域

區(qū)域(zone)：每個(gè)區(qū)域用一個(gè)struct zone結(jié)構(gòu)體來表示，每個(gè)區(qū)域又會(huì)劃分成不同的頁

頁(page)：每個(gè)頁用一個(gè)struct page結(jié)構(gòu)體來表示，頁是伙伴算法分配的最小單位(比如：4K，16K，64K)。

頁分配器(buddy)

伙伴算法

伙伴算法的基本思想是將物理內(nèi)存劃分成連續(xù)的塊，以塊作為基本單位進(jìn)行分配。不同的塊大小可以不同，但每個(gè)塊都由一個(gè)或多個(gè)連續(xù)的物理頁組成，物理頁的數(shù)量必須是2的n次冪(0 <= n < 預(yù)設(shè)的最大值)。

內(nèi)存分配過程

圖6 伙伴系統(tǒng)的空閑鏈表數(shù)組

如圖6所示伙伴算法一般使用空閑鏈表數(shù)組來實(shí)現(xiàn)，假如我們要申請一塊7K大小的內(nèi)存。

首先7K / 4K = 1，也就arr[1]這一個(gè)空閑鏈表上申請空閑塊，結(jié)果發(fā)現(xiàn)鏈表為空。

然后發(fā)現(xiàn)下一級(jí)空閑鏈表arr[2]不為空，從arr[2]的鏈表頭取出一個(gè)16K的空閑塊，并分裂成2個(gè)8K的空閑塊。

最后將分裂的2個(gè)8K空閑塊，一個(gè)返回給申請者，另一個(gè)放到arr[1]的空閑鏈表中。

申請完畢，就是這么簡單。

伙伴算法特點(diǎn)

查找空閑鏈表的過程十分簡單，比如頁大小來4K，如果申請7K內(nèi)存的話，直接7K / 4K = 1計(jì)算一下就可以找到空閑鏈表位置。

確定一個(gè)塊的伙伴塊十分簡單，比如arr[0]空閑鏈表塊A(0 ~ 4K)和塊B(4K ~ 8K)互為伙伴塊，塊A物理地址為0x0，塊B物理地址為0x1000，可以看出只有12位不同，同時(shí)塊大小也是2^12；再比如arr[1]空閑鏈表塊A(16K ~ 24K)和塊B(24K ~ 32K)互為伙伴塊，塊A物理地址為0x4000，塊B物理地址0x6000，可以看出只有13位不同，同時(shí)塊大小也是2^13(很神奇)。

由于伙伴算法的這種特點(diǎn)，在塊的分裂與合并的計(jì)算都很高效，有效的管理了物理內(nèi)存，很好的緩解了外部碎片的問題。

分區(qū)的伙伴算法

前面介紹了Linux使用三級(jí)結(jié)構(gòu)來描述物理內(nèi)存，Linux伙伴算法是基于區(qū)域(zone)這一級(jí)來實(shí)現(xiàn)。

/*include/linuxmmzone.h*/
#ifndefCONFIG_FORCE_MAX_ZONEORDER
#defineMAX_ORDER11
#else
#defineMAX_ORDERCONFIG_FORCE_MAX_ZONEORDER
#endif
structfree_area{
structlist_headfree_list[MIGRATE_TYPES];
unsignedlongnr_free;
};
structzone{
...
/*freeareasofdifferentsizes*/
structfree_areafree_area[MAX_ORDER];
....
} ____cacheline_internodealigned_in_smp;

實(shí)現(xiàn)方法也很簡單，就是在struct zone結(jié)構(gòu)體中定義了一個(gè)struct free_area結(jié)構(gòu)體數(shù)據(jù)，這個(gè)數(shù)組也就是我們前面提到了空閑鏈表數(shù)組。可以看到MAX_ORDER默認(rèn)值為11，也就是說最大的塊為為2^10 * 4K(4K頁大小) = 4M，假如申請內(nèi)存大小超過4M，會(huì)申請成功嗎？。

/#cat/proc/buddyinfo
Node0,zoneDMA1423142533207
/ #

如上為使用qemu模擬的環(huán)境，可以看出2^10的大小塊有207個(gè)，2^9的大小塊為3個(gè)……

可移動(dòng)性分組

到前一小節(jié)為止，伙伴系統(tǒng)的主要內(nèi)容已經(jīng)介紹完了，但是Linux針對內(nèi)存碎片問題還有很多優(yōu)化，本小節(jié)會(huì)介紹下可移動(dòng)性分組的實(shí)現(xiàn)原理。

圖7 內(nèi)存碎片整理

如圖7所示，假如系統(tǒng)運(yùn)行一段時(shí)間后，被使用的內(nèi)存為紫色部分，空閑的為淡藍(lán)色部分，此時(shí)可使用的連續(xù)的物理內(nèi)存只有8K；如果經(jīng)過內(nèi)存碎片整理，把使用的內(nèi)存都放到一起，那么可使的連續(xù)的物理內(nèi)存就有16K了。伙伴算法只會(huì)保證在內(nèi)存申請的時(shí)候盡量避免內(nèi)存碎片的產(chǎn)生，但是內(nèi)存碎片不可避免的還是會(huì)產(chǎn)生，這時(shí)就需要在運(yùn)行時(shí)對內(nèi)存碎片進(jìn)行整理，從而獲取更大的連續(xù)內(nèi)存。

如圖7所示是對編號(hào)5的內(nèi)存塊進(jìn)行了遷移，假如編號(hào)5的內(nèi)存塊不能移動(dòng)，中間的內(nèi)存碎片就得不到整理，這種情況咱辦呢？

針對前面提到的問題，Linux將物理內(nèi)存進(jìn)行了劃分，分為不可移動(dòng)頁，可移動(dòng)頁，可回收頁。

不可移動(dòng)頁：位置必須固定，不能移動(dòng)，直接映射到內(nèi)核虛擬地址空間的頁屬于這一類。

可移動(dòng)頁：使用頁表映射的頁屬于這一類，可以移動(dòng)到其他位置，然后修改頁表映射。

可回收頁：不能移動(dòng)，但可以回收，需要數(shù)據(jù)的時(shí)候，可以重新從數(shù)據(jù)源獲取。后備存儲(chǔ)設(shè)備支持的頁屬于這一類。

/*include/linuxmmzone.h*/
enummigratetype{
MIGRATE_UNMOVABLE,
MIGRATE_MOVABLE,
MIGRATE_RECLAIMABLE,
MIGRATE_PCPTYPES,/*thenumberoftypesonthepcplists*/
MIGRATE_HIGHATOMIC=MIGRATE_PCPTYPES,
#ifdefCONFIG_CMA
MIGRATE_CMA,
#endif
#ifdefCONFIG_MEMORY_ISOLATION
MIGRATE_ISOLATE,/*can'tallocatefromhere*/
#endif
MIGRATE_TYPES
};
structfree_area{
structlist_headfree_list[MIGRATE_TYPES];
unsignedlongnr_free;
};
structzone{
...
/*freeareasofdifferentsizes*/
structfree_areafree_area[MAX_ORDER];
....
} ____cacheline_internodealigned_in_smp;

繼續(xù)看struct free_area結(jié)構(gòu)體，里面定義了一個(gè)數(shù)組鏈表，數(shù)組索引為當(dāng)前塊的遷移類型。所以在申請內(nèi)存的時(shí)候，可以通過flag來告訴系統(tǒng)，要申請什么類型的內(nèi)存，系統(tǒng)會(huì)將相同類型的內(nèi)存放在一起，從而解決上面的提到的問題。這里的思路也是在內(nèi)存申請時(shí)，盡量減少內(nèi)存碎片的產(chǎn)生。

假如申請內(nèi)存大小超過4M，會(huì)申請成功嗎？

/*mm/page_alloc.c*/
struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid, nodemask_t *nodemask)
{
...
    /*
     * There are several places where we assume that the order value is sane
     * so bail out early if the request is out of bound.
     */
    if (unlikely(order >= MAX_ORDER)) {
        WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
        return NULL;
}
...
    return page;
}
EXPORT_SYMBOL(__alloc_pages_nodemask);

如上代碼10 ~ 13行，當(dāng)申請內(nèi)存大小超過系統(tǒng)最大塊時(shí)，內(nèi)存申請會(huì)失敗的。但如果就想申請大塊內(nèi)存，比如像圖像數(shù)據(jù)這種就需要大塊內(nèi)存，怎么辦呢？可以使用保留內(nèi)存的方式。

#這里申請16M大小物理內(nèi)存，可能看到內(nèi)存申請不成功，系統(tǒng)報(bào)了一個(gè)warning
/ # insmod /app/cdev-test.ko
[   11.895824] cdev_test: loading out-of-tree module taints kernel.
[   11.921420] [cdev_test_init:151]devno = 0x0e600000
[   11.921561] <__alloc_pages_nodemask: 4984>order = 12
[   11.922725] ------------[ cut here ]------------
[   11.923045] WARNING: CPU: 2 PID: 47 at mm/page_alloc.c:4985 __alloc_pages_nodemask+0x8c/0x268
[   11.923509] Modules linked in: cdev_test(O+)
[   11.924604] CPU: 2 PID: 47 Comm: insmod Tainted: G           O      5.12.0-00008-g48ca89975eb3-dirty #14
[   11.925044] Hardware name: linux,dummy-virt (DT)
[   11.925521] pstate: 40000005 (nZcv daif -PAN -UAO -TCO BTYPE=--)
[   11.925885] pc : __alloc_pages_nodemask+0x8c/0x268
[   11.926191] lr : __alloc_pages_nodemask+0x68/0x268
[   11.926467] sp : ffff800010223a50
[   11.926677] x29: ffff800010223a50 x28: ffff6a86485ff8d0
[   11.927121] x27: ffff6a86485ff880 x26: 0000000000000001
[   11.927477] x25: ffff6a86485ff8d0 x24: ffff6a8648521bc0
[   11.927835] x23: 0000000000000000 x22: ffffdafc7ac98000
[   11.928186] x21: 000000000000000c x20: 000000000000000c
[   11.928540] x19: 0000000000040cc0 x18: 000000000000000a
[   11.928892] x17: 0000000000000000 x16: ffffdafc7a8e840c
[   11.929246] x15: 00000000000e0fd9 x14: 000000000000008c
[   11.929606] x13: ffff800010223720 x12: 00000000ffffffea
[   11.929962] x11: ffffdafc7af65410 x10: ffffdafc7aca5468
[   11.930312] x9 : ffff800010223718 x8 : ffff800010223720
[   11.930732] x7 : ffffdafc7b025450 x6 : 00000000ffff7fff
[   11.931082] x5 : 00000000002bffa8 x4 : 0000000000000000
[   11.931440] x3 : 0000000000000000 x2 : 7aafd30192e33000
[   11.931791] x1 : 0000000000000000 x0 : 0000000000000028
[   11.932244] Call trace:
[   11.932464]  __alloc_pages_nodemask+0x8c/0x268
[   11.932727]  alloc_pages_current+0xc4/0xc8
[   11.932964]  kmalloc_order+0x34/0xa4
[   11.933190]  cdev_test_init+0x48/0x1000 [cdev_test]
[   11.934498]  do_one_initcall+0x74/0x184
[   11.934726]  do_init_module+0x54/0x1f4
[   11.934956]  load_module+0x1870/0x1f24
[   11.935184]  __do_sys_init_module+0x154/0x184
[   11.935421]  __arm64_sys_init_module+0x14/0x1c
[   11.935666]  do_el0_svc+0x100/0x144
[   11.935885]  el0_svc+0x10/0x18
[   11.936090]  el0_sync_handler+0x64/0x12c
[   11.936314]  el0_sync+0x13c/0x140
[   11.936632] ---[ end trace 206fd1429c29dfb5 ]---
[   11.937737] kmalloc failed
insmod: can't insert '/app/cdev-test.ko': Operation not permitted

塊分配器(slab)

伙伴系統(tǒng)最小的分配單位是一個(gè)物理頁，但是大多數(shù)情況下，內(nèi)核需要分配的內(nèi)存大小通常是幾十個(gè)字節(jié)或者幾百個(gè)字節(jié)，遠(yuǎn)遠(yuǎn)小于一個(gè)物理頁的大小。如果僅僅使用伙伴系統(tǒng)進(jìn)行內(nèi)存分配，會(huì)出現(xiàn)嚴(yán)重的內(nèi)部碎片問題，從而導(dǎo)致資源利用率降低。

塊分配器(slab)就是用來解決這個(gè)問題的，slab分配器做的事情是把伙伴系統(tǒng)分配的大塊內(nèi)存進(jìn)一步細(xì)分成小塊內(nèi)存進(jìn)行管理。一方面由于操作系統(tǒng)頻繁分配的對象大小相對固定，另一方面為了避免外部碎片問題。其實(shí)現(xiàn)也比較簡單，一般slab分配器只分配固定大小的內(nèi)存塊，大小通常是2^n個(gè)字節(jié)(一般來說，3 <= n < 12，4K大小頁)。

SLAB發(fā)展

20世紀(jì)90年代，Jeff Bonwick最先在Solaris 2.4操作系統(tǒng)內(nèi)核中設(shè)計(jì)并實(shí)現(xiàn)了SLAB分配器。之后，該分配器廣泛地被Linux、FreeBSD等操作系統(tǒng)使用并得以發(fā)展。21世紀(jì)，操作系統(tǒng)開發(fā)人員逐漸發(fā)現(xiàn)SLAB分配器存在一些問題，比如維護(hù)了太多了隊(duì)列、實(shí)現(xiàn)日趨復(fù)雜、存儲(chǔ)開銷也由于復(fù)雜的設(shè)計(jì)而增大等。于是，開發(fā)人員在SLAB的分配器的基礎(chǔ)上設(shè)計(jì)了SLUB分配器。

SLUB分配器極大簡化了SLAB分配器的設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)，在降低復(fù)雜度的同時(shí)依然能夠提供與原來相當(dāng)甚至更好的性能，同時(shí)也繼承了SLAB分配器的接口。

此外，SLAB分配器家族中還有一種最簡單的分配器稱為SLOB分配器，它的出現(xiàn)主要為了滿足內(nèi)存資源稀缺的場景（比如嵌入式設(shè)備）的需求，它具有最小的存儲(chǔ)開銷，但在碎片問題的處理方面比不上其他兩種分配器。

SLAB、SLUB、SLOB三種分配器往往被統(tǒng)稱為SLAB分配器。

基本原理

圖8 slab空閑鏈表

slab分配器實(shí)現(xiàn)也很簡單，如圖8所示，Linux通過鏈表來維護(hù)不同大小的slab結(jié)構(gòu)(struct kmem_cache結(jié)構(gòu)體)， 每個(gè)slab結(jié)構(gòu)中都會(huì)記錄內(nèi)存塊的信息，并將大的內(nèi)存塊劃分內(nèi)多個(gè)小的內(nèi)存塊備用。當(dāng)有內(nèi)存申請時(shí)，首先會(huì)找到合適大小的slab結(jié)構(gòu)，然后從小的內(nèi)存塊中返回一個(gè)給申請者就可以了(看就是這么簡單)。用鏈表來維護(hù)slab結(jié)構(gòu)，難道申請內(nèi)存的時(shí)候需要遍歷一次鏈表？當(dāng)然不會(huì)！

struct kmem_cache結(jié)構(gòu)體一般有兩種初始化方式。

系統(tǒng)初始化

在系統(tǒng)初始化時(shí)，會(huì)初始化一批常用大小的slab結(jié)構(gòu)體，其對應(yīng)全局變量kmalloc_caches，使用類似kmalloc()這種接口時(shí)，會(huì)根據(jù)申請內(nèi)存大小直接找到對應(yīng)的slab結(jié)構(gòu)。

/*mm/slab_common.c*/
struct kmem_cache *kmalloc_caches[NR_KMALLOC_TYPES][KMALLOC_SHIFT_HIGH + 1] =
{ /* initialization for https://bugs.llvm.org/show_bug.cgi?id=42570 */ };
EXPORT_SYMBOL(kmalloc_caches);

自己初始化

除了系統(tǒng)自帶的slab結(jié)構(gòu)，當(dāng)然也可以使用自己創(chuàng)建的slab結(jié)構(gòu)，常用接口如下，相信大家基于都使用過，就不多介紹了

/*linux/slab.h*/
struct kmem_cache *kmem_cache_create(const char *name, unsigned int size, unsigned int align,
        slab_flags_t flags, void (*ctor)(void *));
void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags);
void kmem_cache_free(struct kmem_cache *s, void *x);
void kmem_cache_destroy(struct kmem_cache *s);

調(diào)試slab分配器

Linux對slab分配器還做了很多優(yōu)化，比如per cpu支持，numa構(gòu)架的支持，這里面有很多細(xì)節(jié)，可以研究研究源碼。本小節(jié)從實(shí)際需求出發(fā)，比如我們有如下需求：

kmalloc/kfree時(shí)間戳
kmalloc/kfree堆棧信息
內(nèi)存重復(fù)釋放
申請內(nèi)存模塊id
訪問釋放后的內(nèi)存

圖9 object內(nèi)存結(jié)構(gòu)

前一小節(jié)介紹了，slab分配器會(huì)將大塊內(nèi)存劃分成多個(gè)小塊內(nèi)存，每一個(gè)小塊內(nèi)存對應(yīng)一個(gè)object結(jié)構(gòu)(如圖9)，對于上面的需求，基本思路就是給每個(gè)object多分配一些內(nèi)存，用來存儲(chǔ)與該內(nèi)存塊相關(guān)的額外信息。下面分析下object內(nèi)存結(jié)構(gòu)。

red_left_pad：該區(qū)域會(huì)填充兩個(gè)值0xbb或0xcc，分別表示該內(nèi)存塊是否被使用，這個(gè)區(qū)域就可以用來做一些內(nèi)存檢查。

/*linux/poison.h*/
#defineSLUB_RED_INACTIVE0xbb
#define SLUB_RED_ACTIVE     0xcc

object_ptr：該區(qū)域是真正給申請都使用的內(nèi)存區(qū)域，如果開啟毒化功能的話，該區(qū)域會(huì)填充0x5a、0x6b、0xa5，從伙伴系統(tǒng)申請大塊內(nèi)存后，會(huì)填充成0x5a，劃分成小塊后會(huì)填充0x6b，而該區(qū)域最后一個(gè)字節(jié)填充0xa5，這個(gè)區(qū)域也可以用來做一些內(nèi)存檢查。

/*linux/poison.h*/
/*...andforpoisoning*/
#definePOISON_INUSE0x5a/*foruse-uninitialisedpoisoning*/
#definePOISON_FREE0x6b/*foruse-after-freepoisoning*/
#define POISON_END  0xa5    /* end-byte of poisoning */

track：該區(qū)域用來記錄內(nèi)存申請或者釋放相關(guān)的信息，比如申請或釋放的堆棧，申請或釋放的cpu/pid/時(shí)間等信息。

/*mm/slub.c*/


/*
 * Tracking user of a slab.
 */
#define TRACK_ADDRS_COUNT 16
struct track {
    unsigned long addr; /* Called from address */
#ifdef CONFIG_STACKTRACE
    unsigned long addrs[TRACK_ADDRS_COUNT]; /* Called from address */
#endif
    int cpu;        /* Was running on cpu */
    int pid;        /* Pid context */
    unsigned long when; /* When did the operation occur */
};

所以當(dāng)進(jìn)行內(nèi)存的申請與釋放時(shí)，只需要把這些額外的信息記錄下來就可以了。

總結(jié)

內(nèi)存分配設(shè)計(jì)的兩個(gè)維度，提高內(nèi)存的利用率，減少內(nèi)存分配時(shí)的延時(shí)與CPU占用率。

頁分配器用來解決外部碎片問題，塊分配器用來解決內(nèi)部碎片問題，從而提高內(nèi)存的利用率。

頁分配器與塊分配器的算法簡單、高效。

其它

實(shí)驗(yàn)環(huán)境

kernel version：v5.12

qemu version：v6.0.0

審核編輯：湯梓紅