Linux buddyy系統(tǒng)是linux kernel比較穩(wěn)定的一個(gè)模塊，但是并不是說(shuō)它沒(méi)有缺陷，Linux內(nèi)存管理系統(tǒng)自誕生之日，就一直存在物理內(nèi)存碎片化的問(wèn)題：在系統(tǒng)啟動(dòng)并且運(yùn)行很長(zhǎng)一段時(shí)間后，極端情況下，盡管總的可用物理page數(shù)目很高，但是空閑的連續(xù)物理內(nèi)存可能并不大，這就造成申請(qǐng)大塊連續(xù)物理內(nèi)存分配時(shí)失敗。尤其是當(dāng)分配操作帶有ATOMAIC標(biāo)記時(shí)，系統(tǒng)連回收內(nèi)存的機(jī)會(huì)都沒(méi)有。

避免碎片

很長(zhǎng)時(shí)間以來(lái)，物理內(nèi)存的碎片化一直是Linux操作系統(tǒng)的弱點(diǎn)之一，盡管已經(jīng)有人提出了很多解決方法，但是沒(méi)有哪個(gè)方法能夠徹底的解決，memory buddy分配就是解決方法之一。 我們知道磁盤(pán)文件也有碎片化問(wèn)題，但是磁盤(pán)文件的碎片化只會(huì)減慢系統(tǒng)的讀寫(xiě)速度，并不會(huì)導(dǎo)致功能性錯(cuò)誤，而且我們還可以在不影響磁盤(pán)功能的前提的下，進(jìn)行磁盤(pán)碎片整理。而物理內(nèi)存碎片則截然不同，物理內(nèi)存和操作系統(tǒng)結(jié)合的太過(guò)于緊密，以至于我們很難在運(yùn)行時(shí)，進(jìn)行物理內(nèi)存的搬移（這一點(diǎn)上，磁盤(pán)碎片要容易的多；實(shí)際上mel gorman已經(jīng)提交了內(nèi)存緊縮的patch，只是還沒(méi)有被主線(xiàn)內(nèi)核接收）。 因此解決的方向主要放在預(yù)防碎片上。

在2.6.24內(nèi)核開(kāi)發(fā)期間，防止碎片的內(nèi)核功能加入了主線(xiàn)內(nèi)核。在了解反碎片的基本原理前，先對(duì)內(nèi)存頁(yè)面做個(gè)歸類(lèi)：

1. 不可移動(dòng)頁(yè)面 unmoveable：在內(nèi)存中位置必須固定，無(wú)法移動(dòng)到其他地方，核心內(nèi)核分配的大部分頁(yè)面都屬于這一類(lèi)。

2. 可回收頁(yè)面 reclaimable：不能直接移動(dòng)，但是可以回收，因?yàn)檫€可以從某些源重建頁(yè)面，比如映射文件的數(shù)據(jù)屬于這種類(lèi)別，kswapd會(huì)按照一定的規(guī)則，周期性的回收這類(lèi)頁(yè)面。

3. 可移動(dòng)頁(yè)面 movable：可以隨意的移動(dòng)。屬于用戶(hù)空間應(yīng)用程序的頁(yè)屬于此類(lèi)頁(yè)面，它們是通過(guò)頁(yè)表映射的，因此我們只需要更新頁(yè)表項(xiàng)，并把數(shù)據(jù)復(fù)制到新位置就可以了，當(dāng)然要注意，一個(gè)頁(yè)面可能被多個(gè)進(jìn)程共享，對(duì)應(yīng)著多個(gè)頁(yè)表項(xiàng)。

防止碎片的方法就是把這三類(lèi)page放在不同的鏈表上，避免不同類(lèi)型頁(yè)面相互干擾?？紤]這樣的情形，一個(gè)不可移動(dòng)的頁(yè)面位于可移動(dòng)頁(yè)面中間，那么我們移動(dòng)或者回收這些頁(yè)面后，這個(gè)不可移動(dòng)的頁(yè)面阻礙著我們獲得更大的連續(xù)物理空閑空間。

（圖片來(lái)源：https://images2015.cnblogs.com/blog/758933/201703/758933-20170301165125907-1024080699.png）

針對(duì)頁(yè)面的分類(lèi)，我們引入了movable zone，事實(shí)上movable zone是虛擬zone，是在運(yùn)行時(shí)逐漸建立的。當(dāng)然內(nèi)核的確可以建立真實(shí)的內(nèi)存zone。

我們知道大部分buddy分配失敗，發(fā)生在申請(qǐng)unremovable頁(yè)面時(shí)。這樣分類(lèi)還有一個(gè)潛在的好處，為unremovable保留的頁(yè)面，被reclaimable和movable分配的優(yōu)先級(jí)低（參見(jiàn)fallbacks），因此客觀上減少了buddy分配unremovable頁(yè)面的幾率。

數(shù)據(jù)結(jié)構(gòu)

kernel引入了一些宏來(lái)表示不同的遷移類(lèi)型：

#define MIGRATE_UNMOVABLE 0#define MIGRATE_RECLAIMABLE 0#define MIGRATE_MOVALBE 0#define MIGRATE_RESERVE 0#define MIGRATE_ISOLATE 0#define MIGRATE_TYPES 0

類(lèi)型MIGRATE_UNMOVABLE, MIGRATE_RECLAIMABLE和MIGRATE_MOVALBE就是我們上面介紹的三種頁(yè)面類(lèi)型。如果向特定類(lèi)型頁(yè)面分配請(qǐng)求失敗，緊急情況下可以從MIGRATE_RESERVE分配內(nèi)存。

當(dāng)制定類(lèi)型的空閑列表無(wú)法滿(mǎn)足分配時(shí)，可以按照一定規(guī)則從其他類(lèi)型空閑鏈表分配，這個(gè)次序用下面數(shù)據(jù)描述

static int fallbacks[MIRGRATE_TYPES][MIGRATE_TYPES-1] = { [MIGRATE_UNMOVABLE] = {MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE}, [MIGRATE_RECLAIMABLE] = {MIRGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE}, [MIGRATE_MOVABLE] = {MIRGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE}, [MIGRATE_RESERVE] = {MIGRATE_RESERVE, MIGRATE_RESERVE, MIGRATE_RESERVE},}

和zone_list功能類(lèi)似，當(dāng)內(nèi)核想要分配不可移動(dòng)頁(yè)面，如果該鏈表為空，則優(yōu)先選擇從RECLAIMABLE鏈表分配，然后是MOVABLE，最后使用RESERVE鏈表。

實(shí)際上，這種方法并不能解決我們的問(wèn)題，因?yàn)橛脩?hù)空間頁(yè)面映射以及內(nèi)核申請(qǐng)RECLAIMABLE頁(yè)面的需求可能是無(wú)止境的，當(dāng)MOVABLE和RECLAIMABLE鏈表無(wú)法滿(mǎn)足分配時(shí)，根據(jù)fallbacks會(huì)占用MIGRATE_UNMOVABLE鏈表，這就導(dǎo)致后面UNMOVABLE分配可能失敗。

So，我們可以修改fallbacks如下

static int fallbacks[MIRGRATE_TYPES][MIGRATE_TYPES-1] = { [MIGRATE_UNMOVABLE] = {MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE}, [MIGRATE_RECLAIMABLE] = {MIRGRATE_MOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE}, [MIGRATE_MOVABLE] = {MIRGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE}, [MIGRATE_RESERVE] = {MIGRATE_RESERVE, MIGRATE_RESERVE, MIGRATE_RESERVE},}

禁止MOVABLE或者RECLAIMABLE失敗后嘗試從UNMOVABLE鏈表分配頁(yè)面，這樣可以保持UNMOVABLE不受非關(guān)鍵頁(yè)面分配的干擾。

注意：即便可移動(dòng)分組特性已經(jīng)編譯到內(nèi)核中，但是只有當(dāng)系統(tǒng)中有足夠內(nèi)存可以分配給多個(gè)類(lèi)型的鏈表時(shí)，該特性才有意義。這個(gè)足夠的含義由pageblock_order和pageblock_nr_pages來(lái)定義。當(dāng)可用內(nèi)存過(guò)少的時(shí)候，引入頁(yè)面遷移沒(méi)有任何好處，相反會(huì)增加系統(tǒng)負(fù)擔(dān)。系統(tǒng)會(huì)在 build_all_zonelist中進(jìn)行檢查，如果沒(méi)有足夠內(nèi)存，則關(guān)閉該特性。

在內(nèi)存子系統(tǒng)初始化期間，memmap_init_zone負(fù)責(zé)處理內(nèi)存域的page實(shí)列，所有的頁(yè)最初都標(biāo)記為可移動(dòng)的！

mm/page_alloc.cvoid __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone, unsigned long start_pfn, enum memmap_context context){ strcut page *page; unsigned long end_pfn = start_pfn+size; unsigned long pfn; for (pfn = start_pfn; pfn < end_pfn; pfn++) {? ? ? ? ... ? ? ? ?if ((pfn & (pageblock_nr_pages - 1))) ? ? ? ? ? ?set_pageblock_migratetype(page, MIGRATE_MOVABLE);? ? ? ...}

在進(jìn)行內(nèi)存分配時(shí)，如果沒(méi)有預(yù)定遷移類(lèi)型的內(nèi)存區(qū)。那么會(huì)嘗試從MOVABLE鏈表上獲取盡可能大的內(nèi)存區(qū)，并轉(zhuǎn)換到相應(yīng)的列表，由于獲取的內(nèi)存區(qū)長(zhǎng)度是最大的，因此不會(huì)向可移動(dòng)內(nèi)存區(qū)引入碎片。這種做法使得不同類(lèi)型的頁(yè)面從不同的頁(yè)面范圍內(nèi)分配，從而使得不同類(lèi)型的內(nèi)存分配比避免干擾。

內(nèi)存分配器如何知道分配申請(qǐng)是哪種遷移類(lèi)型呢，這需要所有內(nèi)存申請(qǐng)?zhí)峁┫鄳?yīng)的分配標(biāo)記，如果需要分配可移動(dòng)的內(nèi)存頁(yè)，那么使用__GFP_MOVABLE，如果申請(qǐng)可回收的則使用__GFP_RECLAIMABLE。如果這些標(biāo)記都沒(méi)有設(shè)置，則認(rèn)為是UNMOVABLE的。

Virtual Movable Zone

這種方法是提前分配一個(gè)稱(chēng)為ZONE_MOVABLE的內(nèi)存zone，ZONE_MOVABLE內(nèi)核特性必須由管理員顯示激活。其基本思想是：把物理內(nèi)存劃分為兩個(gè)內(nèi)存zone，一個(gè)用于可移動(dòng)分配，另外一個(gè)用于不可移動(dòng)分配。這樣不可移動(dòng)內(nèi)存域不會(huì)干擾可移動(dòng)內(nèi)存域引入碎片，而可移動(dòng)內(nèi)存域因此很容易滿(mǎn)足分配。

當(dāng)然，如何劃分這兩個(gè)內(nèi)存域，對(duì)系統(tǒng)管理員是個(gè)挑戰(zhàn)。

和系統(tǒng)中的其他內(nèi)存域不同，ZONE_MOVABLE是一個(gè)虛擬的內(nèi)存域，它的內(nèi)存取自高端內(nèi)存域或者普通內(nèi)存域。ZONE_MOVABLE內(nèi)存有兩種提取方式：

1. 用于可移動(dòng)分配的內(nèi)存平均分布到所有的內(nèi)存節(jié)點(diǎn)上。

2. 只使用來(lái)自最高內(nèi)存域的內(nèi)存，在內(nèi)存較多的32位系統(tǒng)上，這通常是ZONE_HIGHMEM。注意這也和ZONE_MOVABLE的使用者吻合，因?yàn)橹挥杏脩?hù)頁(yè)面映射才算是MOVA LE的內(nèi)存頁(yè)，而用戶(hù)頁(yè)面映射優(yōu)先使用的也是HIGHMEM。

因此對(duì)于ZONE_MOVABLE我們可以使用如下策略：

1. 使能高端內(nèi)存

2. ZONE_MOVABLE從HIGHMEM提取內(nèi)存

3. 系統(tǒng)管理員估算ZONE_MOVABLE的大小，較小的ZONE_MOVABLE使得非movable ZONE有更多地物理內(nèi)存。

ZONE_MOVABLE 使用者

因?yàn)閆ONE_MOVABLE的使用者是帶有GFP_MOVABLE和GFP_HIGHMEM標(biāo)記的內(nèi)核分配（主要是應(yīng)用程序的頁(yè)面映射）。

void *vmalloc(unsigned long size){ return __vmalloc_node_flags(size, -1, GFP_KERNEL | __GFP_HIGHMEM);}

結(jié)論

ZONE_MOVABLE和頁(yè)面分類(lèi)方法相比，好處是很明顯的：固定UNMOVABLE zone的大?。?yè)面分類(lèi)鏈表是動(dòng)態(tài)生成的），UNMOVABLE zone供內(nèi)核關(guān)鍵分配函數(shù)使用。系統(tǒng)頻繁申請(qǐng)的MOVABLE分配，不會(huì)導(dǎo)致unmovable zone的碎片化。但是缺點(diǎn)仍然很明顯，即RECLAIMABLE分配還是使用unmovable zone，頻繁的分配回收仍然使得unmovable zone碎片化。

所以看起來(lái)，ZONE_MOVABLE方法只是緩解了物理內(nèi)存碎片化，但是并沒(méi)有完全解決。

對(duì)于某些特定的驅(qū)動(dòng)，我們可以通過(guò)以下方式減少分配失敗的可能性。

1. 減少分配所需的連續(xù)頁(yè)面數(shù)目。

2. 如果內(nèi)存申請(qǐng)操作對(duì)系統(tǒng)來(lái)說(shuō)是關(guān)鍵操作（比如framebuffer，網(wǎng)絡(luò)傳輸buffer），不允許分配失敗，但是又無(wú)法做到1，那么可以考慮使用預(yù)分配的策略。

對(duì)于某些特定的項(xiàng)目，可以通過(guò)如下方法減少DMA內(nèi)存分配失敗的可能性。

1. 禁止帶有GFP_HIGHMEM標(biāo)記的內(nèi)存分配在HIGHMEM zone 分配失敗后，進(jìn)入DMA zone尋找合適的頁(yè)面。

2. 禁止對(duì)Normal zone分配失敗，進(jìn)入DMA zone尋找合適頁(yè)面

HIGHMEM的使用者主要是應(yīng)用程序的頁(yè)面映射和內(nèi)核vmalloc分配，這兩種操作都不需要連續(xù)物理頁(yè)面，HIGHMEM zone并不關(guān)心物理內(nèi)存碎片化，而且這兩種操作映射的頁(yè)面本身就是reclaimable，實(shí)在沒(méi)有必要再去占用Normal和DMA zone的物理頁(yè)面。

尤其在Android系統(tǒng)上，Android退出應(yīng)用操作只是把應(yīng)用退到后臺(tái)，并沒(méi)有釋放內(nèi)存，當(dāng)運(yùn)行時(shí)間較長(zhǎng)，啟動(dòng)多個(gè)應(yīng)用后，這些應(yīng)用占滿(mǎn)HIGHMEM zone后，就會(huì)去占用Normal zone和Highmem zone的內(nèi)存。在這里我們切斷zone_list，就是防止貪得無(wú)厭的Android應(yīng)用和Vmalloc占據(jù)Normal和DMA zone。

此外，linux kernel本身對(duì)待cache（此cache不是物理cache，而是指buffer cache, inode cache, dentry cache）也是有求必應(yīng)的，Normal zone分配完，就使用DMA zone，直到把DMA zone占完為止。因此我們實(shí)在是有必要禁止cache這種貪得無(wú)厭的東西進(jìn)入DMA zone。

這種截?cái)嗟淖龇m然背離了linux盡量使用系統(tǒng)內(nèi)存的做法，但是卻保證了三個(gè)內(nèi)存區(qū) DMA zone, Normal zone, Highmem zone互不干擾。

lowmem_reserve

上面提到了切斷HIGHMEM zone分配失敗回退到Normal zone和DMA zone，以及切斷Normal zone失敗回退到DMA zone。具體做法是配置lowmem_reserve

通過(guò)配置lowmem_reserve的為1，使得本內(nèi)存zone針對(duì)高端分配保留盡可能多的空間，來(lái)減少fallback分配，這里用減少而不是禁止是因?yàn)閘owmem_reserve算法在某些內(nèi)存配置下，無(wú)法完全禁止fallback。