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

避免碎片

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

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

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

2. 可回收頁面 reclaimable：不能直接移動，但是可以回收，因為還可以從某些源重建頁面，比如映射文件的數(shù)據(jù)屬于這種類別，kswapd會按照一定的規(guī)則，周期性的回收這類頁面。

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

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

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

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

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

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

kernel引入了一些宏來表示不同的遷移類型：

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

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

當(dāng)制定類型的空閑列表無法滿足分配時，可以按照一定規(guī)則從其他類型空閑鏈表分配，這個次序用下面數(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功能類似，當(dāng)內(nèi)核想要分配不可移動頁面，如果該鏈表為空，則優(yōu)先選擇從RECLAIMABLE鏈表分配，然后是MOVABLE，最后使用RESERVE鏈表。

實際上，這種方法并不能解決我們的問題，因為用戶空間頁面映射以及內(nèi)核申請RECLAIMABLE頁面的需求可能是無止境的，當(dāng)MOVABLE和RECLAIMABLE鏈表無法滿足分配時，根據(jù)fallbacks會占用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鏈表分配頁面，這樣可以保持UNMOVABLE不受非關(guān)鍵頁面分配的干擾。

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

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

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)存分配時，如果沒有預(yù)定遷移類型的內(nèi)存區(qū)。那么會嘗試從MOVABLE鏈表上獲取盡可能大的內(nèi)存區(qū)，并轉(zhuǎn)換到相應(yīng)的列表，由于獲取的內(nèi)存區(qū)長度是最大的，因此不會向可移動內(nèi)存區(qū)引入碎片。這種做法使得不同類型的頁面從不同的頁面范圍內(nèi)分配，從而使得不同類型的內(nèi)存分配比避免干擾。

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

Virtual Movable Zone

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

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

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

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

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

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

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

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

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

ZONE_MOVABLE 使用者

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

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

結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

lowmem_reserve

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

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