作者簡介：尹忠凱，Linux內核愛好者，閱碼場用戶。現就職于北京地平線信息技術有限公司，任系統軟件工程師。

物理內存分配設計有兩個重要的評價維度。一方面，物理內存分配器要追求更高的內存資源利用率，即盡可能減少資源浪費。另一方面，物理內存分配器要追求更好的性能，主要是盡可能降低分配延遲和節約CPU資源。

內存碎片

內存碎片指的是無法被利用的內存，進一步又可以分為外部碎片和內部碎片。

外部碎片

圖1 外部碎片

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

內部碎片

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

圖2 內部碎片

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

下面會介紹linux系統中的頁分配器和塊分配器，頁分配器用來解決外部碎片問題，而塊分配器用來解決內部碎片問題，通過這兩個分配器，可以有效減少內存碎片的產生，從而提高內存資源的利用率。

物理內存組織

在介紹頁分配器和塊分配器之前，先來了解下現代計算的物理內存是如何組織的，因為有些概念在后面會用到。

SMP架構

圖3 SMP架構

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

NUMA架構

圖4 NUMA架構

NUMA架構將CPU劃分到多個Node中，每個node有自己獨立的內存空間。各個node之間通過高速互聯通訊。CPU訪問不同類型節點內存的速度是不相同的，訪問本地節點的速度最快，訪問遠端節點的速度最慢，即訪問速度與節點的距離有關，距離越遠訪問速度越慢，即非一致。這種架構的缺點是，本node的內存不足時，需要垮節點訪問內存，節點間的訪問速度慢。

三級結構

內存管理子系統使用節點(node)、區域(zone)、和頁(page)三級結構描述物理內存。

圖5 物理內存三級結構

如圖5所示，在linux中使用三級結構來描述物理內存。

節點(node)：每個節點用一個struct pglist_data結構體來表示，每個節點內的內存會劃分成不同的區域

區域(zone)：每個區域用一個struct zone結構體來表示，每個區域又會劃分成不同的頁

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

頁分配器(buddy)

伙伴算法

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

內存分配過程

圖6 伙伴系統的空閑鏈表數組

如圖6所示伙伴算法一般使用空閑鏈表數組來實現，假如我們要申請一塊7K大小的內存。

首先7K / 4K = 1，也就arr[1]這一個空閑鏈表上申請空閑塊，結果發現鏈表為空。

然后發現下一級空閑鏈表arr[2]不為空，從arr[2]的鏈表頭取出一個16K的空閑塊，并分裂成2個8K的空閑塊。

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

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

伙伴算法特點

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

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

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

分區的伙伴算法

前面介紹了Linux使用三級結構來描述物理內存，Linux伙伴算法是基于區域(zone)這一級來實現。

/*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;

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

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

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

可移動性分組

到前一小節為止，伙伴系統的主要內容已經介紹完了，但是Linux針對內存碎片問題還有很多優化，本小節會介紹下可移動性分組的實現原理。

圖7 內存碎片整理

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

如圖7所示是對編號5的內存塊進行了遷移，假如編號5的內存塊不能移動，中間的內存碎片就得不到整理，這種情況咱辦呢？

針對前面提到的問題，Linux將物理內存進行了劃分，分為不可移動頁，可移動頁，可回收頁。

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

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

可回收頁：不能移動，但可以回收，需要數據的時候，可以重新從數據源獲取。后備存儲設備支持的頁屬于這一類。

/*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;

繼續看struct free_area結構體，里面定義了一個數組鏈表，數組索引為當前塊的遷移類型。所以在申請內存的時候，可以通過flag來告訴系統，要申請什么類型的內存，系統會將相同類型的內存放在一起，從而解決上面的提到的問題。這里的思路也是在內存申請時，盡量減少內存碎片的產生。

假如申請內存大小超過4M，會申請成功嗎？

/*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行，當申請內存大小超過系統最大塊時，內存申請會失敗的。但如果就想申請大塊內存，比如像圖像數據這種就需要大塊內存，怎么辦呢？可以使用保留內存的方式。

#這里申請16M大小物理內存，可能看到內存申請不成功，系統報了一個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)

伙伴系統最小的分配單位是一個物理頁，但是大多數情況下，內核需要分配的內存大小通常是幾十個字節或者幾百個字節，遠遠小于一個物理頁的大小。如果僅僅使用伙伴系統進行內存分配，會出現嚴重的內部碎片問題，從而導致資源利用率降低。

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

SLAB發展

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

SLUB分配器極大簡化了SLAB分配器的設計和數據結構，在降低復雜度的同時依然能夠提供與原來相當甚至更好的性能，同時也繼承了SLAB分配器的接口。

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

SLAB、SLUB、SLOB三種分配器往往被統稱為SLAB分配器。

基本原理

圖8 slab空閑鏈表

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

struct kmem_cache結構體一般有兩種初始化方式。

系統初始化

在系統初始化時，會初始化一批常用大小的slab結構體，其對應全局變量kmalloc_caches，使用類似kmalloc()這種接口時，會根據申請內存大小直接找到對應的slab結構。

/*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);

自己初始化

除了系統自帶的slab結構，當然也可以使用自己創建的slab結構，常用接口如下，相信大家基于都使用過，就不多介紹了

/*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);

調試slab分配器

Linux對slab分配器還做了很多優化，比如per cpu支持，numa構架的支持，這里面有很多細節，可以研究研究源碼。本小節從實際需求出發，比如我們有如下需求：

kmalloc/kfree時間戳
kmalloc/kfree堆棧信息
內存重復釋放
申請內存模塊id
訪問釋放后的內存

圖9 object內存結構

前一小節介紹了，slab分配器會將大塊內存劃分成多個小塊內存，每一個小塊內存對應一個object結構(如圖9)，對于上面的需求，基本思路就是給每個object多分配一些內存，用來存儲與該內存塊相關的額外信息。下面分析下object內存結構。

red_left_pad：該區域會填充兩個值0xbb或0xcc，分別表示該內存塊是否被使用，這個區域就可以用來做一些內存檢查。

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

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

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

track：該區域用來記錄內存申請或者釋放相關的信息，比如申請或釋放的堆棧，申請或釋放的cpu/pid/時間等信息。

/*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 */
};

所以當進行內存的申請與釋放時，只需要把這些額外的信息記錄下來就可以了。

總結

內存分配設計的兩個維度，提高內存的利用率，減少內存分配時的延時與CPU占用率。

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

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

其它

實驗環境

kernel version：v5.12

qemu version：v6.0.0

審核編輯：湯梓紅