一篇搞懂linux內(nèi)核內(nèi)存管理學(xué)習(xí)之（物理內(nèi)存管理-伙伴系統(tǒng)）
linux使用伙伴系統(tǒng)來管理物理內(nèi)存頁。
一、伙伴系統(tǒng)原理
1. 伙伴關(guān)系
定義：由一個(gè)母實(shí)體分成的兩個(gè)各方面屬性一致的兩個(gè)子實(shí)體，這兩個(gè)子實(shí)體就處于伙伴關(guān)系。在操作系統(tǒng)分配內(nèi)存的過程中，一個(gè)內(nèi)存塊常常被分成兩個(gè)大小相等的內(nèi)存塊，這兩個(gè)大小相等的內(nèi)存塊就處于伙伴關(guān)系。它滿足 3 個(gè)條件 ：
兩個(gè)塊具有相同大小記為 2^K
它們的物理地址是連續(xù)的
從同一個(gè)大塊中拆分出來
2. 伙伴算法的實(shí)現(xiàn)原理
為了便于頁面的維護(hù)，將多個(gè)頁面組成內(nèi)存塊，每個(gè)內(nèi)存塊都有 2 的方冪個(gè)頁，方冪的指數(shù)被稱為階 order。order相同的內(nèi)存塊被組織到一個(gè)空閑鏈表中?；锇橄到y(tǒng)基于2的方冪來申請釋放內(nèi)存頁。
當(dāng)申請內(nèi)存頁時(shí)，伙伴系統(tǒng)首先檢查與申請大小相同的內(nèi)存塊鏈表中，檢看是否有空閑頁，如果有就將其分配出去，并將其從鏈表中刪除，否則就檢查上一級，即大小為申請大小的2倍的內(nèi)存塊空閑鏈表，如果該鏈表有空閑內(nèi)存，就將其分配出去，同時(shí)將剩余的一部分（即未分配出去的一半）加入到下一級空閑鏈表中；如果這一級仍沒有空閑內(nèi)存；就檢查它的上一級，依次類推，直到分配成功或者徹底失敗，在成功時(shí)還要按照伙伴系統(tǒng)的要求，將未分配的內(nèi)存塊進(jìn)行劃分并加入到相應(yīng)的空閑內(nèi)存塊鏈表
在釋放內(nèi)存頁時(shí)，會(huì)檢查其伙伴是否也是空閑的，如果是就將它和它的伙伴合并為更大的空閑內(nèi)存塊，該檢查會(huì)遞歸進(jìn)行，直到發(fā)現(xiàn)伙伴正在被使用或者已經(jīng)合并成了最大的內(nèi)存塊。
二、linux中的伙伴系統(tǒng)相關(guān)的結(jié)構(gòu)
系統(tǒng)中的每個(gè)物理內(nèi)存頁（頁幀）都對應(yīng)一個(gè)struct page數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都包含了多個(gè)zone，每個(gè)zone都有struct zone表示，其中保存了用于伙伴系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)。zone中的
struct free_area ? ? ?free_area[MAX_ORDER];
用于管理該zone的伙伴系統(tǒng)信息?；锇橄到y(tǒng)將基于這些信息管理該zone的物理內(nèi)存。該數(shù)組中每個(gè)數(shù)組項(xiàng)用于管理一個(gè)空閑內(nèi)存頁塊鏈表，同一個(gè)鏈表中的內(nèi)存頁塊的大小相同，并且大小為2的數(shù)組下標(biāo)次方頁。MAX_ORDER定義了支持的最大的內(nèi)存頁塊大小。
struct free_area的定義如下
nr_free:其中nr_free表示內(nèi)存頁塊的數(shù)目，對于0階的表示以1頁為單位計(jì)算，對于1階的以2頁為單位計(jì)算，n階的以2的n次方為單位計(jì)算。
free_list:用于將具有該大小的內(nèi)存頁塊連接起來。由于內(nèi)存頁塊表示的是連續(xù)的物理頁，因而對于加入到鏈表中的每個(gè)內(nèi)存頁塊來說，只需要將內(nèi)存頁塊中的第一個(gè)頁加入該鏈表即可。因此這些鏈表連接的是每個(gè)內(nèi)存頁塊中第一個(gè)內(nèi)存頁，使用了struct page中的struct list_head成員lru。free_list數(shù)組元素的每一個(gè)對應(yīng)一種屬性的類型，可用于不同的目地，但是它們的大小和組織方式相同。
因此在伙伴系統(tǒng)看來，一個(gè)zone中的內(nèi)存組織方式如下圖所示：
基于伙伴系統(tǒng)的內(nèi)存管理方式專注于內(nèi)存節(jié)點(diǎn)的某個(gè)內(nèi)存域的管理，但是系統(tǒng)中的所有zone都會(huì)通過備用列表連接起來。伙伴系統(tǒng)和內(nèi)存域/節(jié)點(diǎn)的關(guān)系如下圖所示：
系統(tǒng)中伙伴系統(tǒng)的當(dāng)前信息可以通過/proc/buddyinfo查看：
這是我的PC上的信息，這些信息描述了每個(gè)zone中對應(yīng)于每個(gè)階的空閑內(nèi)存頁塊的數(shù)目，從左到右階數(shù)依次升高。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ? ? ?
三、避免碎片
1.碎片概念
伙伴系統(tǒng)也存在一些問題，在系統(tǒng)長時(shí)間運(yùn)行后，物理內(nèi)存會(huì)出現(xiàn)很多碎片，如圖所示：
這是雖然可用內(nèi)存頁還有很多，但是最大的連續(xù)物理內(nèi)存也只有一頁，這對于用戶程序不成問題，因?yàn)橛脩舫绦蛲ㄟ^頁表映射，應(yīng)用程序看到的總是連續(xù)的虛擬內(nèi)存。但是對于內(nèi)核來說就不行了，因?yàn)閮?nèi)核有時(shí)候需要使用連續(xù)的物理內(nèi)存。
2.linux解決方案
碎片問題也存在于文件系統(tǒng)，文件系統(tǒng)中的碎片可以通過工具來解決，即分析文件系統(tǒng)，然后重新組織文件的位置，但是這種方不適用于內(nèi)核，因?yàn)橛行┪锢眄摃r(shí)不能隨意移動(dòng)。內(nèi)核采用的方法是反碎片（anti-fragmentation）。為此內(nèi)核根據(jù)頁的可移動(dòng)性將其劃分為3種不同的類型：
不可移動(dòng)的頁：在內(nèi)存中有固定位置，不能移動(dòng)。分配給核心內(nèi)核的頁大多是此種類型
可回收的頁：不能移動(dòng)，但是可以刪除，其內(nèi)容可以從某些源重新生成。
可移動(dòng)的頁：可以隨意移動(dòng)。屬于用戶進(jìn)程的頁屬于這種類型，因?yàn)樗鼈兪峭ㄟ^頁表映射的，因而在移動(dòng)后只需要更新用戶進(jìn)程頁表即可。
頁的可移動(dòng)性取決于它屬于上述三類中的哪一類，內(nèi)核將頁面按照不同的可移動(dòng)性進(jìn)行分組，通過這種技術(shù)，雖然在不可移動(dòng)頁中仍可能出現(xiàn)碎片，但是由于具有不同可移動(dòng)性的頁不會(huì)進(jìn)入同一個(gè)組，因而其它兩個(gè)類型的內(nèi)存塊就可以獲得較好的“對抗碎片”的特性。
需要注意的是按照可移動(dòng)性對內(nèi)存頁進(jìn)行分組時(shí)在運(yùn)行中進(jìn)行的，而不是在一開始就設(shè)置好的。
3.數(shù)據(jù)結(jié)構(gòu)
內(nèi)核定義了MIGRATE_TYPES中遷移類型，其定義如下：
其中前三種分別對應(yīng)于三種可移動(dòng)性，其它幾種的含義：
MIGRATE_pcpTYPES：是per_cpu_pageset，即用來表示每CPU頁框高速緩存的數(shù)據(jù)結(jié)構(gòu)中的鏈表的遷移類型數(shù)目
MIGRATE_RESERVE：是在前三種的列表中都沒用可滿足分配的內(nèi)存塊時(shí)，就可以從MIGRATE_RESERVE分配
MIGRATE_ISOLATE：用于跨越NUMA節(jié)點(diǎn)移動(dòng)物理內(nèi)存頁，在大型系統(tǒng)上，它有益于將物理內(nèi)存頁移動(dòng)到接近于是用該頁最頻繁地CPU
每種類型都對應(yīng)free_list中的一個(gè)數(shù)組項(xiàng)。
類似于從zone中的分配，如果無法從指定的遷移類型分配到頁，則會(huì)按照fallbacks指定的次序從備用遷移類型中嘗試分配，它定義在page_alloc.c中。
雖然該特性總是編譯進(jìn)去的，但是該特性只有在系統(tǒng)中有足夠的內(nèi)存可以分配到每種遷移類型對應(yīng)的鏈表時(shí)才有意義，也就是說每個(gè)可以遷移性鏈表都要有“適量”的內(nèi)存，內(nèi)核需要對“適量”的判斷是基于兩個(gè)宏的：
pageblock_order：內(nèi)核認(rèn)為夠大的一個(gè)分配的階。
pageblock_nr_pages：內(nèi)核認(rèn)為啟用該特性時(shí)每個(gè)遷移鏈表需要具有的最少的內(nèi)存頁數(shù)。它的定義是基于pageblock_order的。
基于這個(gè)“適量”的概念內(nèi)核會(huì)在build_all_zonelists中判斷是否要啟用該特性。page_group_by_mobility_disabled表示是否啟用了該特性。
內(nèi)核定義了兩個(gè)標(biāo)志：__GFP_MOVABLE和 __GFP_RECLAIMABLE分別用來表示可移動(dòng)遷移類型和可回收遷移類型，如果沒有設(shè)置這兩個(gè)標(biāo)志，則表示是不可移動(dòng)的。如果頁面遷移特性被禁止了，則所有的頁都是不可移動(dòng)頁。
struct zone中包含了一個(gè)字段pageblock_flags，它用于跟蹤包含pageblock_nr_pages個(gè)頁的內(nèi)存區(qū)的屬性。在初始化期間，內(nèi)核自動(dòng)保證對每個(gè)遷移類型，在pageblock_flags中都分配了足夠存儲(chǔ)NR_PAGEBLOCK_BITS個(gè)比特的空間。
set_pageblock_migratetype用于設(shè)置一個(gè)以指定的頁為起始地址的內(nèi)存區(qū)的遷移類型。
頁的遷移類型是預(yù)先分配好的，對應(yīng)的比特位總是可用，在頁釋放時(shí)，必須將其返還給正確的鏈表。get_pageblock_migratetype可用于從struct page中獲取頁的遷移類型。
通過/proc/pagetypeinfo可以獲取系統(tǒng)當(dāng)前的信息。
在內(nèi)存初始化期間memmap_init_zone會(huì)將所有的內(nèi)存頁都初始化為可移動(dòng)的。該函數(shù)在paging_init中會(huì)最終被調(diào)到（會(huì)經(jīng)過一些中間函數(shù)，其中就有free_area_init_node）。
4.虛擬可移動(dòng)內(nèi)存
內(nèi)核還提供了一種機(jī)制來解決碎片問題，即使用虛擬內(nèi)存域ZONE_MOVABLE。其思想是：可用內(nèi)存劃分為兩個(gè)部分，一部分用于可移動(dòng)分配，一部分用于不可移動(dòng)分配。這樣就防止了不可移動(dòng)頁向可移動(dòng)內(nèi)存區(qū)域引入碎片。
該機(jī)制需要管理員來配置兩部分內(nèi)存的大小。
kernel參數(shù)kernelcore用于指定用于不可移動(dòng)分配的內(nèi)存數(shù)量，如果指定了該參數(shù)，其值會(huì)保存在required_kernelcore會(huì)基于它來計(jì)算。
kernel參數(shù)movablecore用于指定用于可移動(dòng)分配的內(nèi)存數(shù)量，如果指定了該參數(shù)，則其值會(huì)被保存在required_movablecore中，同時(shí)會(huì)基于它來計(jì)算required_kernelcore，代碼如下（函數(shù)find_zone_movable_pfns_for_nodes）：
如果計(jì)算出來的required_kernelcore為0，則該機(jī)制將無效。
該zone是一個(gè)虛擬zone，它不和任何物理內(nèi)存相關(guān)聯(lián)，該域中的內(nèi)存可能來自高端內(nèi)存或者普通內(nèi)存。用于不可移動(dòng)分配的內(nèi)存會(huì)被均勻的分布到系統(tǒng)的各個(gè)內(nèi)存節(jié)點(diǎn)中；同時(shí)用于可移動(dòng)分配的內(nèi)存只會(huì)取自最高內(nèi)存域的內(nèi)存，zone_movable_pfn記錄了取自各個(gè)節(jié)點(diǎn)的用于可移動(dòng)分配的內(nèi)存的起始地址。
四、初始化內(nèi)存域和節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
在內(nèi)存管理的初始化中，架構(gòu)相關(guān)的代碼要完成系統(tǒng)中可用內(nèi)存的檢測，并要將相關(guān)信息提交給架構(gòu)無關(guān)的代碼。架構(gòu)無關(guān)的代碼free_area_init_nodes負(fù)責(zé)完成管理數(shù)據(jù)結(jié)構(gòu)的創(chuàng)建。該函數(shù)需要一個(gè)參數(shù)max_zone_pfn，它由架構(gòu)相關(guān)的代碼提供，其中保存了每個(gè)內(nèi)存域的最大可用頁幀號。內(nèi)核定義了兩個(gè)數(shù)組：
這兩個(gè)數(shù)組在free_area_init_nodes用于保存來自max_zone_pfn的信息，并將它轉(zhuǎn)變成[low，high]的形式。
然后內(nèi)核開始調(diào)用find_zone_movable_pfns_for_nodes對ZONE_MOVABLE域進(jìn)行初始化。
然后內(nèi)核開始為每一個(gè)節(jié)點(diǎn)調(diào)用free_area_init_node，這個(gè)函數(shù)將完成：
調(diào)用calculate_node_totalpages計(jì)算節(jié)點(diǎn)中頁的總數(shù)
調(diào)用alloc_node_mem_map負(fù)責(zé)初始化struct pglist_data中的node_mem_map，為它分配的內(nèi)存將用于存儲(chǔ)本節(jié)點(diǎn)的所有物理內(nèi)存的struct page結(jié)構(gòu)。這片內(nèi)存將對其到伙伴系統(tǒng)的最大分配階上。而且如果當(dāng)前節(jié)點(diǎn)是第0個(gè)節(jié)點(diǎn)，則該指針信息還將保存在全局變量mem_map中。
調(diào)用free_area_init_core完成初始化進(jìn)一步的初始化
free_area_init_core將完成內(nèi)存域數(shù)據(jù)結(jié)構(gòu)的初始化，在這個(gè)函數(shù)中
nr_kernel_pages記錄直接映射的頁面數(shù)目，而nr_all_pages則記錄了包括高端內(nèi)存中頁數(shù)在內(nèi)的頁數(shù)
會(huì)調(diào)用zone_pcp_init初始化該內(nèi)存域的每CPU緩存
會(huì)調(diào)用init_currently_empty_zone初始化該zone的wait_table，free_area列表
調(diào)用memmap_init初始化zone的頁，所有頁都被初始化為可移動(dòng)的
五、分配器API
伙伴系統(tǒng)只能分配2的整數(shù)冪個(gè)頁。因此申請時(shí)，需要指定請求分配的階。
有很多分配和釋放頁的API，都定義在gfp.h中。最簡單的是alloc_page(gfp_mask)用來申請一個(gè)頁， free_page(addr)用來釋放一個(gè)頁。
這里更值得關(guān)注的獲取頁面時(shí)的參數(shù)gfp_mask，所有獲取頁面的API都需要指定該參數(shù)。它用來影響分配器的行為，其中有是分配器提供的標(biāo)志，標(biāo)志有兩種：
zone修飾符：用于告訴分配器從哪個(gè)zone分配內(nèi)存
行為修飾符：告訴分配器應(yīng)該如何進(jìn)行分配
其中zone修飾符定義為
這些定義都一目了然，需要指出的是如果同時(shí)指定了__GFP_MOVABLE和__GFP_HIGHMEM，則會(huì)從虛擬的ZONE_MOVABLE分配。
更詳細(xì)的可以參考gfp.h，其中包含了所有的標(biāo)志及其含義。
1.分配頁
__alloc_pages會(huì)完成最終的內(nèi)存分配，它是伙伴系統(tǒng)的核心代碼（但是在內(nèi)核代碼中，這種命名方式的函數(shù)都是需要小心調(diào)用的，一般都是給實(shí)現(xiàn)該功能的代碼自己調(diào)用，不作為API提供出去的，因而它的包裝器才是對外提供的API，也就是alloc_pages_node）。
1.1選擇頁
選擇頁中最重要的函數(shù)是get_page_from_freelist，它負(fù)責(zé)通過標(biāo)志和分配階來判斷分配是否可以進(jìn)行，如果可以就進(jìn)行實(shí)際的分配。該函數(shù)還會(huì)調(diào)用zone_watermark_ok根據(jù)指定的標(biāo)識判斷是否可以從給定的zone中進(jìn)行分配。該函數(shù)需要struct zonelist的指針指向備用zone，當(dāng)當(dāng)前zone不能滿足分配需求時(shí)就依次遍歷該列表嘗試進(jìn)行分配。整體的分配流程是：
調(diào)用get_page_from_freelist嘗試進(jìn)行分配，如果成功就返回分配到的頁，否則
喚醒kswapd，然后再次調(diào)用get_page_from_freelist嘗試進(jìn)行分配，如果成功就返回分配的頁，否則
如果分配的標(biāo)志允許不檢查閾值進(jìn)行分配，則以ALLOC_NO_WATERMARKS為標(biāo)志再次調(diào)用get_page_from_freelist嘗試分配，如果成功則返回分配的頁；如果不允許不檢查閾值或者仍然失敗，則
如果不允許等待，就分配失敗，否則
如果支持壓縮，則嘗試先對內(nèi)存進(jìn)行一次壓縮，然后再調(diào)用get_page_from_freelist，如果成功就返回，否則
進(jìn)行內(nèi)存回收，然后再調(diào)用get_page_from_freelist，如果成功就返回，否則
根據(jù)回收內(nèi)存并嘗試分配的結(jié)果以及分配標(biāo)志，可能會(huì)調(diào)用OOM殺死一個(gè)進(jìn)程然后再嘗試分配，也可能不執(zhí)行OOM這一步的操作，如果執(zhí)行了，則在失敗后可能就徹底失敗，也可能重新回到第2步，也可能繼續(xù)下一步
回到第2步中調(diào)用get_page_from_freelist的地方或者再嘗試一次先壓縮后分配，如果走了先壓縮再分配這一步，這就是最后一次嘗試了，要么成功要么失敗，不會(huì)再繼續(xù)嘗試了
1.2移出所選擇的頁
在函數(shù)get_page_from_freelist中，會(huì)首先在zonelist中找到一個(gè)具有足夠的空閑頁的zone，然后會(huì)調(diào)用buffered_rmqueue進(jìn)行處理，在分配成功時(shí)，該函數(shù)會(huì)把所分配的內(nèi)存頁從zone的free_list中移出，并且保證剩余的空閑內(nèi)存頁滿足伙伴系統(tǒng)的要求，該函數(shù)還會(huì)把內(nèi)存頁的遷移類型存放在page的private域中。
該函數(shù)的步驟如圖所示：
編輯切換為居中
可以看出buffered_rmqueue的工作過程為：
如果申請的是單頁，會(huì)做特殊處理，內(nèi)核會(huì)利用每CPU的緩存加速這個(gè)過程。并且在必要的時(shí)候會(huì)首先填充每CPU的緩存。函數(shù)rmqueue_bulk用于從伙伴系統(tǒng)獲取內(nèi)存頁，并添加到指定的鏈表，它會(huì)調(diào)用函數(shù)__rmqueue。
如果是分配多個(gè)頁，則會(huì)首先調(diào)用__rmqueue從內(nèi)存域的伙伴系統(tǒng)中選擇合適的內(nèi)存塊，這一步可能失敗，因?yàn)殡m然內(nèi)存域中有足夠數(shù)目的空閑頁，但是頁不一定是連續(xù)的，如果是這樣這一步就會(huì)返回NULL。在這一步中如果需要還會(huì)將大的內(nèi)存塊分解成小的內(nèi)存塊來進(jìn)行分配，即按照伙伴系統(tǒng)的要求進(jìn)行分配。
無論是分配單頁還是多個(gè)頁，如果分配成功，在返回分配的頁之前都要調(diào)用prep_new_page，如果這一步的處理不成功就會(huì)重新進(jìn)行分配（跳轉(zhuǎn)到函數(shù)buffered_rmqueue的開始），否則返回分配的頁。
函數(shù)__rmqueue的執(zhí)行過程：
首先調(diào)用__rmqueue_smallest嘗試根據(jù)指定的zone，分配的階，遷移類型進(jìn)行分配，該函數(shù)根據(jù)指定的信息進(jìn)行查找，在找到一個(gè)可用的空閑內(nèi)存頁塊后會(huì)將該內(nèi)存頁塊從空閑內(nèi)存頁塊鏈表中刪除，并且會(huì)調(diào)用expand使得剩余的內(nèi)存頁塊滿足伙伴系統(tǒng)的要求。如果在這一步成功就返回，否則執(zhí)行下一步
調(diào)用__rmqueue_fallback嘗試從備用zone分配。該函數(shù)用于根據(jù)前一類型的備用列表嘗試從其它備用列表分配，但是需要注意的是這里會(huì)首先嘗試最大的分配階，依次降低分配的階，直到指定的分配的階，采用這個(gè)策略是為了避免碎片—如果要用其它遷移類型的內(nèi)存，就拿一塊大的過來，而不是在其它遷移類型的小區(qū)域中到處引入碎片。同時(shí)如果從其它遷移類型的空閑內(nèi)存頁塊分配到的是一個(gè)較大的階，則整塊內(nèi)存頁塊的遷移類型可能會(huì)發(fā)生改變，從原來的類型改變?yōu)樯暾埛峙鋾r(shí)所請求的類型（即遷移類型發(fā)生了改變）。分配成功時(shí)的動(dòng)作和__rmqueue_smallest類似，移出內(nèi)存頁，調(diào)用expand。
函數(shù)prep_new_page的操作
對頁進(jìn)行檢查，以確保頁確實(shí)是可用的，否則就返回一個(gè)非0值導(dǎo)致分配失敗
設(shè)置頁的標(biāo)記以及引用計(jì)數(shù)等等。
如果設(shè)置而來__GFP_COMP標(biāo)志，則調(diào)用prep_compound_page將頁組織成復(fù)合頁（hugetlb會(huì)用到這個(gè)）。
復(fù)合頁的結(jié)構(gòu)如圖所示：
復(fù)合頁具有如下特性：
復(fù)合頁中第一個(gè)頁稱為首頁，其它所擁有頁都稱為尾頁
組成復(fù)合頁的所有的private域都指向首頁
第一個(gè)尾頁的lru的next域指向釋放復(fù)合頁的函數(shù)指針
第一個(gè)尾頁的lru的prev域用于指向復(fù)合頁所對應(yīng)的分配的階，即多少個(gè)頁
2.釋放頁
__free_pages是釋放頁的核心函數(shù)，伙伴系統(tǒng)提供出去的API都是它的包裝器。其流程：
減小頁的引用計(jì)數(shù)，如果計(jì)數(shù)不為0則直接返回，否則
如果釋放的是單頁，則調(diào)用free_hot_cold_page，否則
調(diào)用__free_pages_ok
free_hot_cold_page會(huì)把頁返還給每-CPU緩存而不是直接返回給伙伴系統(tǒng)，因?yàn)槿绻看味挤颠€給伙伴系統(tǒng)，那么將會(huì)出現(xiàn)每次的分配和釋放都需要伙伴系統(tǒng)進(jìn)行分割和合并的情況，這將極大的降低分配的效率。因而這里采用的是一種“惰性合并”，單頁會(huì)首先返還給每-CPU緩存，當(dāng)每-CPU緩存的頁面數(shù)大于一個(gè)閾值時(shí)（pcp->high），則一次將pcp->patch個(gè)頁返還給伙伴系統(tǒng)。free_pcppages_bulk在free_hot_cold_page中用于將內(nèi)存頁返還給伙伴系統(tǒng)，它會(huì)調(diào)用函數(shù)__free_one_page。
函數(shù)__free_pages_ok最終頁會(huì)調(diào)到__free_one_page來釋放頁，__free_one_page會(huì)將頁面釋放返還給伙伴系統(tǒng)，同時(shí)在必要時(shí)進(jìn)行遞歸合并。
在__free_one_page進(jìn)行合并時(shí)，需要找到釋放的page的伙伴的頁幀號，這是通過__find_buddy_index來完成的，其代碼非常簡單：
根據(jù)異或的規(guī)則，這個(gè)結(jié)果剛好可以得到鄰居的頁幀號。因?yàn)楦鶕?jù)linux的管理策略以及伙伴系統(tǒng)的定義，伙伴系統(tǒng)中每個(gè)內(nèi)存頁塊的第一個(gè)頁幀號用來標(biāo)志該頁，因此對于order階的兩個(gè)伙伴，它們只有1<<order這個(gè)比特位是不同的，這樣，只需要將該比特與取反即可，而根據(jù)異或的定義，一個(gè)比特和0異或還是本身，一個(gè)比特和1異或剛好可以取反。因此就得到了這個(gè)算式。
如果可以合并還需要取得合并后的頁幀號，這個(gè)更簡單，只需要讓兩個(gè)伙伴的頁幀號相與即可。
__free_one_page調(diào)用page_is_buddy來對伙伴進(jìn)行判斷，以決定是否可以合并。
六、不連續(xù)內(nèi)存頁的分配
內(nèi)核總是嘗試使用物理上連續(xù)的內(nèi)存區(qū)域，但是在分配內(nèi)存時(shí)，可能無法找到大片的物理上連續(xù)的內(nèi)存區(qū)域，這時(shí)候就需要使用不連續(xù)的內(nèi)存，內(nèi)核分配了其虛擬地址空間的一部分（vmalloc區(qū)）用于管理不連續(xù)內(nèi)存頁的分配。
每個(gè)vmalloc分配的子區(qū)域都自包含的，在內(nèi)核的虛擬地址空間中vmalloc子區(qū)域之間都通過一個(gè)內(nèi)存頁隔離開來，這個(gè)間隔用來防止不正確的訪問。
1. 用vmalloc分配內(nèi)存
vmalloc用來分配在虛擬地址空間連續(xù)，但是在物理地址空間不一定連續(xù)的內(nèi)存區(qū)域。它只需要一個(gè)以字節(jié)為單位的長度參數(shù)。為了節(jié)省寶貴的較低端的內(nèi)存區(qū)域，vmalloc會(huì)使用高端內(nèi)存進(jìn)行分配。
內(nèi)核使用struct vm_struct來管理vmalloc分配的每個(gè)子區(qū)域，其定義如下：
每個(gè)vmalloc子區(qū)域都對應(yīng)一個(gè)該結(jié)構(gòu)的實(shí)例。
next：指向下一個(gè)vmalloc子區(qū)域 addr：vmalloc子區(qū)域在內(nèi)核虛擬地址空間的起始地址 size：vmalloc子區(qū)域的長度 flags：與該區(qū)域相關(guān)標(biāo)志 pages：指針，指向映射到虛擬地址空間的物理內(nèi)存頁的struct page實(shí)例 nr_pages：映射的物理頁面數(shù)目 phys_addr：僅當(dāng)用ioremap映射了由物理地址描述的內(nèi)存頁時(shí)才需要改域，它保存物理地址 caller：申請者
2. 創(chuàng)建vmalloc子區(qū)域
所有的vmalloc子區(qū)域都被連接保存在vmlist中，該鏈表按照addr排序，順序是從小到大。當(dāng)創(chuàng)建一個(gè)新的子區(qū)域時(shí)需要，需要找到一個(gè)合適的位置。查找合適的位置采用的是首次適用算法，即從vmalloc區(qū)域找到第一個(gè)可以滿足需求的區(qū)域，查找這樣的區(qū)域是通過函數(shù)__get_vm_area_node完成的。其分配過程以下幾步：
調(diào)用__get_vm_area_node找到合適的區(qū)域
調(diào)用__vmalloc_area_node分配物理內(nèi)存頁
調(diào)用map_vm_area將物理內(nèi)存頁映射到內(nèi)核的讀你地址空間
將新的子區(qū)域插入vmlist鏈表
在從伙伴系統(tǒng)分配物理內(nèi)存頁時(shí)使用了標(biāo)志：GFP_KERNEL | __GFP_HIGHMEM
還有其它的方式來建立虛擬地址空間的連續(xù)映射：
vmalloc_32：與vmallo工作方式相同，但是確保所使用的物理地址總可以用32位指針尋址
vmap：將一組物理頁面映射到連續(xù)的虛擬地址空間
ioremap：特定于處理器的分配函數(shù)，用于將取自物理地址空間而、由系統(tǒng)總線用于I/O操作的一個(gè)內(nèi)存塊，映射到內(nèi)核的虛擬地址空間
3. 釋放內(nèi)存
vfree用于釋放vmalloc和vmalloc_32分配的內(nèi)存空間，vunmap用于釋放由vmap和ioremap分配的空間（iounmap會(huì)調(diào)到vunmap）。最終都會(huì)歸結(jié)到函數(shù)__vunmap。
__vunmap的執(zhí)行過程：
調(diào)用remove_vm_area從vmlist中找到一個(gè)子區(qū)域，然后將其從子區(qū)域刪除，再解除物理頁面的映射
如果設(shè)置了deallocate_pages，則將物理頁面歸還給伙伴系統(tǒng)
釋放管理虛擬內(nèi)存的數(shù)據(jù)結(jié)構(gòu)struct vm_struct
七、內(nèi)核映射
高端內(nèi)存可通過vmalloc機(jī)制映射到內(nèi)核的虛擬地址空間，但是高端內(nèi)存往內(nèi)核虛擬地址空間的映射并不依賴于vmalloc，而vmalloc是用于管理不連續(xù)內(nèi)存的，它也并不依賴于高端內(nèi)存。
1.持久內(nèi)核映射
如果想要將高端內(nèi)存長期映射到內(nèi)核中，則必須使用kmap函數(shù)。該函數(shù)需要一個(gè)page指針用于指向需要映射的頁面。如果沒有啟用高端內(nèi)存，則該函數(shù)直接返回頁的地址，因?yàn)樗许撁娑伎梢灾苯佑成?。如果啟用了高端?nèi)存，則：
如果不是高端內(nèi)存的頁面，則直接返回頁面地址，否則
調(diào)用kmap_high進(jìn)行處理
1.1使用的數(shù)據(jù)結(jié)構(gòu)
vmalloc區(qū)域后的持久映射區(qū)域用于建立持久映射。pkmap_count是一個(gè)有LAST_PKMAP個(gè)元素的數(shù)組，每個(gè)元素對應(yīng)一個(gè)持久映射。每個(gè)元素的值是被映射頁的一個(gè)使用計(jì)數(shù)器：
0：相關(guān)的頁么有被使用
1：該位置關(guān)聯(lián)的頁已經(jīng)映射，但是由于CPU的TLB沒有刷新而不能使用
大于1的其它值：表示該頁的引用計(jì)數(shù)，n表示有n-1處在使用該頁
數(shù)據(jù)結(jié)構(gòu)
用于建立物理頁和其在虛擬地址空間位置之間的關(guān)系。
page：指向全局?jǐn)?shù)據(jù)結(jié)構(gòu)mem_map數(shù)組中的page實(shí)例的指針
virtual：該頁在虛擬地址空間中分配的位置
所有的持久映射保存在一個(gè)散列表page_address_htable中，并用鏈表處理沖突，page_slot是散列函數(shù)。
函數(shù)page_address用于根據(jù)page實(shí)例獲取器對應(yīng)的虛擬地址。其處理過程：
如果不是高端內(nèi)存直接根據(jù)page獲得虛擬地址（利用__va(paddr)），否則
在散列表中查找該page對應(yīng)的struct page_address_map實(shí)例，獲取其虛擬地址
1.2創(chuàng)建映射
函數(shù)kmap_high完成映射的實(shí)際創(chuàng)建，其工作過程：
調(diào)用page_address獲取對應(yīng)的虛擬地址
如果沒有獲取到，則調(diào)用map_new_virtual獲取虛擬地址
pkmap_count數(shù)組中對應(yīng)于該虛擬地址的元素的引用計(jì)數(shù)加1
新映射的創(chuàng)建在map_new_virtual中完成，其工作過程：
執(zhí)行一個(gè)無限循環(huán)：
更新last_pkmap_nr為last_pkmap_nr+1
同時(shí)如果last_pkmap_nr為0，調(diào)用flush_all_zero_pkmaps，flush CPU高速緩存
檢查pkmap_count數(shù)組中索引last_pkmap_nr對應(yīng)的元素的引用計(jì)數(shù)是否為0，如果是0就退出循環(huán)，否則
將自己加入到一個(gè)等待隊(duì)列
調(diào)度其它任務(wù)
被喚醒時(shí)會(huì)首先檢查是否有其它任務(wù)已經(jīng)完成了新映射的創(chuàng)建，如果是就直接返回
回到循環(huán)頭部重新執(zhí)行
獲取與該索引對應(yīng)的虛擬地址
修改內(nèi)核頁表，將該頁映射到獲取到的虛擬地址
更新該索引對應(yīng)的pkmap_count元素的引用計(jì)數(shù)為1
調(diào)用set_page_address將新的映射加入到page_address_htable中
flush_all_zero_pkmaps的工作過程：
調(diào)用flush_cache_kmaps執(zhí)行高速緩存flush動(dòng)作
遍歷pkmap_count中的元素，如果某個(gè)元素的值為1就將其減小為0，并刪除相關(guān)映射同時(shí)設(shè)置需要刷新標(biāo)記
如果需要刷新，則調(diào)用flush_tlb_kernel_range刷新指定的區(qū)域?qū)?yīng)的tlb。
1.3解除映射
kunmap用于解除kmap創(chuàng)建的映射，如果不是高端內(nèi)存，什么都不做，否則kunmap_high將完成實(shí)際的工作。kunmap_high的工作很簡單，將對應(yīng)的pkmap_count中的元素的引用計(jì)數(shù)的值減1，如果新值為1，則看是否有任務(wù)在pkmap_map_wait上等待，如果有就喚醒它。根據(jù)該機(jī)制的涉及原理，該函數(shù)不能將引用計(jì)數(shù)減小到小于1，否則就是一個(gè)BUG。
2.臨時(shí)內(nèi)核映射
kmap不能用于無法休眠的上線文，如果要在不可休眠的上下文調(diào)用，則需要調(diào)用kmap_atomic。它是原子的，特定于架構(gòu)的。同樣的只有是高端內(nèi)存時(shí)才會(huì)做實(shí)際的映射。
kmap_atomic使用了固定映射機(jī)制。在固定映射區(qū)域，系統(tǒng)中每個(gè)CPU都有一個(gè)對應(yīng)的“窗口”，每個(gè)窗口對應(yīng)于KM_TYPE_NR中不同的類型都有一項(xiàng)。這個(gè)映射的核心代碼如下（取自powerpc）：
固定映射區(qū)域?yàn)橛糜趉map_atomic預(yù)留內(nèi)存區(qū)的代碼如下：
