內存管理學習筆記分享

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

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

內存碎片

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

外部碎片

圖1 外部碎片

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

內部碎片

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

圖2 內部碎片

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

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

物理內存組織

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

SMP架構

圖3 SMP架構

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

NUMA架構

圖4 NUMA架構

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

三級結構

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

圖5 物理內存三級結構

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

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

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

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

頁分配器(buddy)

伙伴算法

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

內存分配過程

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

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

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

然后發(fā)現(xiàn)下一級空閑鏈表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(很神奇)。

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

分區(qū)的伙伴算法

前面介紹了Linux使用三級結構來描述物理內存，Linux伙伴算法是基于區(qū)域(zone)這一級來實現(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;

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

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

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

可移動性分組

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

圖7 內存碎片整理

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

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

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

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

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

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

/*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結構體，里面定義了一個數(shù)組鏈表，數(shù)組索引為當前塊的遷移類型。所以在申請內存的時候，可以通過flag來告訴系統(tǒng)，要申請什么類型的內存，系統(tǒng)會將相同類型的內存放在一起，從而解決上面的提到的問題。這里的思路也是在內存申請時，盡量減少內存碎片的產生。

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

#這里申請16M大小物理內存，可能看到內存申請不成功，系統(tǒng)報了一個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)最小的分配單位是一個物理頁，但是大多數(shù)情況下，內核需要分配的內存大小通常是幾十個字節(jié)或者幾百個字節(jié)，遠遠小于一個物理頁的大小。如果僅僅使用伙伴系統(tǒng)進行內存分配，會出現(xiàn)嚴重的內部碎片問題，從而導致資源利用率降低。

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

SLAB發(fā)展

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

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

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

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

基本原理

圖8 slab空閑鏈表

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

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

系統(tǒng)初始化

在系統(tǒng)初始化時，會初始化一批常用大小的slab結構體，其對應全局變量kmalloc_caches，使用類似kmalloc()這種接口時，會根據(jù)申請內存大小直接找到對應的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);

自己初始化

除了系統(tǒng)自帶的slab結構，當然也可以使用自己創(chuàng)建的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分配器還做了很多優(yōu)化，比如per cpu支持，numa構架的支持，這里面有很多細節(jié)，可以研究研究源碼。本小節(jié)從實際需求出發(fā)，比如我們有如下需求：

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

圖9 object內存結構

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

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

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

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

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

track：該區(qū)域用來記錄內存申請或者釋放相關的信息，比如申請或釋放的堆棧，申請或釋放的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占用率。

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

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

其它

實驗環(huán)境

kernel version：v5.12

qemu version：v6.0.0

審核編輯：湯梓紅