內存管理學習筆記

作者簡介：尹忠凱，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 中使用三級結構來描述物理內存。

頁分配器 (buddy)

夥伴算法

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

內存分配過程

圖 6 夥伴系統的空閒鏈表數組

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

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

夥伴算法特點

分區的夥伴算法

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

/* include/linuxmmzone.h */
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};
struct zone {
...
    /* free areas of different sizes */
    struct free_area    free_area[MAX_ORDER];
    ....
} ____cacheline_internodealigned_in_smp;

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

/ # cat /proc/buddyinfo
Node 0, zone      DMA      1      4      2      3      1      4      2      5      3      3    207
/ #

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

可移動性分組

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

圖 7 內存碎片整理

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

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

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

/* include/linuxmmzone.h */
enum migratetype {
    MIGRATE_UNMOVABLE,
    MIGRATE_MOVABLE,
    MIGRATE_RECLAIMABLE,
    MIGRATE_PCPTYPES,   /* the number of types on the pcp lists */
    MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
    MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    MIGRATE_ISOLATE,    /* can't allocate from here */
#endif
    MIGRATE_TYPES
};
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};
struct zone {
...
    /* free areas of different sizes */
    struct free_area    free_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 內存結構。

/* linux/poison.h */
#define SLUB_RED_INACTIVE   0xbb
#define SLUB_RED_ACTIVE     0xcc
/* linux/poison.h */
/* ...and for poisoning */
#define POISON_INUSE    0x5a    /* for use-uninitialised poisoning */
#define POISON_FREE 0x6b    /* for use-after-free poisoning */
#define POISON_END  0xa5    /* end-byte of poisoning */
/* 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 */
};

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

總結

其它

實驗環境

參考

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/oVLdy6pKsZc-RWRAgSkozw

猜你喜歡