• 內(nèi)核分配物理內(nèi)存時(shí)，是以內(nèi)存頁(yè)作為分配單位的。但有時(shí)候內(nèi)核需要分配一些物理內(nèi)存地址連續(xù)的內(nèi)存頁(yè)，所以，Linux內(nèi)核使用了?伙伴系統(tǒng)分配算法?來(lái)管理系統(tǒng)中的物理內(nèi)存頁(yè).

• 什么是?伙伴系統(tǒng)分配算法？下面將會(huì)進(jìn)行詳細(xì)的介紹。

什么是伙伴系統(tǒng)分配算法

• 在 Linux 內(nèi)核中，要分配內(nèi)存頁(yè)可以使用?alloc_pages()?函數(shù)來(lái)完成。而?alloc_pages()?函數(shù)最后會(huì)調(diào)用?rmqueue()?函數(shù)來(lái)分配內(nèi)存頁(yè),?rmqueue()?函數(shù)原型如下:

• 參數(shù)?zone?是內(nèi)存管理區(qū), 而?order?是要分配 2order 個(gè)內(nèi)存頁(yè). 由于?rmqueue()?函數(shù)使用了伙伴系統(tǒng)算法, 所以下面先來(lái)介紹一下伙伴系統(tǒng)算法的原理.

• 伙伴系統(tǒng)算法?的核心是?伙伴，那什么是伙伴呢？在 Linux 內(nèi)核中，把兩個(gè)物理地址相鄰的內(nèi)存頁(yè)當(dāng)作成伙伴。

• 因?yàn)?，Linux 是以頁(yè)面號(hào)來(lái)管理內(nèi)存頁(yè)的。所以，就是說(shuō)兩個(gè)相鄰頁(yè)面號(hào)的頁(yè)面是伙伴關(guān)系。但是并不是所有相鄰頁(yè)面號(hào)的頁(yè)面都是伙伴關(guān)系, 例如 0 號(hào)和 1 號(hào)頁(yè)面是伙伴關(guān)系，但是 1 號(hào)和 2 號(hào)就不是了。為什么呢? 這是因?yàn)槿绻?1 號(hào)頁(yè)面和 2 號(hào)頁(yè)面當(dāng)成伙伴關(guān)系，那么 0 號(hào)頁(yè)面就沒(méi)有伙伴從而變成孤島了。

• 那么給定一個(gè)?i?號(hào)內(nèi)存頁(yè)，怎么找到他的伙伴內(nèi)存頁(yè)呢？通過(guò)觀察我們可以發(fā)現(xiàn)，如果頁(yè)面號(hào)是復(fù)數(shù)的，那么他的伙伴內(nèi)存頁(yè)要加 1。

• 如果頁(yè)面號(hào)是單數(shù)的，那么他的伙伴內(nèi)存頁(yè)要減 1。所以，對(duì)于給定一個(gè)頁(yè)面號(hào)為?i?的內(nèi)存頁(yè)，他的伙伴內(nèi)存頁(yè)號(hào)可以使用以下的代碼獲得：

• 那么知道一個(gè)內(nèi)存頁(yè)的伙伴頁(yè)面有什么用呢？答案是為了合并為更大的內(nèi)存頁(yè)，例如把兩個(gè)單位為1的伙伴內(nèi)存頁(yè)合并成為一個(gè)單位為2的內(nèi)存頁(yè)(這時(shí)應(yīng)該稱(chēng)為內(nèi)存塊)，把兩個(gè)單位為2的伙伴內(nèi)存塊合并為單位為4的內(nèi)存塊，以此類(lèi)推。

• 所以，使用伙伴系統(tǒng)算法只能分配 2order (order為0,1,2,3...)個(gè)頁(yè)面。那么order是不是無(wú)限大呢？當(dāng)然不是，在Linux內(nèi)核中，order的最大值是?10。也就是說(shuō)在內(nèi)核中，最大能夠申請(qǐng)到一個(gè) 29 個(gè)頁(yè)面的內(nèi)存塊。

• Linux 內(nèi)核將物理內(nèi)存劃分為?內(nèi)存管理區(qū)?進(jìn)行管理，內(nèi)存管理區(qū)使用結(jié)構(gòu)體?zone_struct?表示。

• 而在內(nèi)存管理區(qū)數(shù)據(jù)結(jié)構(gòu)中有個(gè)名為?free_area?類(lèi)型為?free_area_t?的字段，他的作用就是用來(lái)管理內(nèi)存管理區(qū)內(nèi)的空閑物理內(nèi)存頁(yè). 定義如下：

• free_area?是伙伴系統(tǒng)算法的核心，可以看到?free_area?有10個(gè)元素。每個(gè)元素都是一個(gè)類(lèi)型為?free_area_t?的結(jié)構(gòu)體，free_area_t?結(jié)構(gòu)的?free_list?字段用于連接有相同頁(yè)面?zhèn)€數(shù)的內(nèi)存塊。map?字段是一個(gè)位圖，用于記錄伙伴內(nèi)存塊的使用情況。

• Linux內(nèi)核使用?free_area[i]?管理 2i 個(gè)內(nèi)存頁(yè)面大小的內(nèi)存塊列表，例如?free_area[0]?就是管理1個(gè)內(nèi)存頁(yè)面大小的內(nèi)存塊(20等于1)；而?free_area[1]?則管理2個(gè)內(nèi)存頁(yè)面大小的內(nèi)存塊(21等于2)。如下圖所示：

• 【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書(shū)籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。?！前100名進(jìn)群領(lǐng)取，額外贈(zèng)送一份價(jià)值699的內(nèi)核資料包（含視頻教程、電子書(shū)、實(shí)戰(zhàn)項(xiàng)目及代碼)? ?

• 管理物理內(nèi)存頁(yè)的?struct page?結(jié)構(gòu)中有個(gè)?list?的字段，內(nèi)核就是通過(guò)這個(gè)字段把有著相同個(gè)數(shù)頁(yè)面的內(nèi)存塊連成一個(gè)鏈表的：

• 前面我們說(shuō)過(guò)，在?free_area_t?結(jié)構(gòu)中有個(gè)名為?map?的字段，map?字段是一個(gè)位圖，每個(gè)位記錄著一對(duì)伙伴內(nèi)存塊的使用情況。舉個(gè)例子，如果一對(duì)伙伴內(nèi)存塊中的某一個(gè)內(nèi)存塊在使用，那么對(duì)應(yīng)的位就為 1，如果兩個(gè)伙伴內(nèi)存塊都是空閑或者使用，那么對(duì)應(yīng)的位就為 0。如下圖：

• 使用位圖來(lái)標(biāo)識(shí)伙伴內(nèi)存塊使用情況的原因是: 當(dāng)釋放內(nèi)存塊時(shí), 如果對(duì)應(yīng)的位是1的話, 那么說(shuō)明另外一個(gè)伙伴內(nèi)存塊是空閑狀態(tài)的, 所以釋放當(dāng)前內(nèi)存塊可以跟其伙伴內(nèi)存塊合并成一個(gè)更大的內(nèi)存塊了.

伙伴系統(tǒng)分配算法實(shí)現(xiàn)

• 我們來(lái)看看內(nèi)核在初始化內(nèi)存管理區(qū)時(shí)怎么初始化空閑內(nèi)存塊鏈表的，代碼如下：

• 上面的代碼首先為每個(gè)管理不同大小空閑內(nèi)存塊的?free_area_t?結(jié)構(gòu)初始化其?free_list?字段，然后根據(jù)其管理內(nèi)存塊的大小來(lái)計(jì)算需要多少個(gè)位來(lái)記錄伙伴內(nèi)存塊的關(guān)系，并保存到?map?字段中。

說(shuō)明一下，這里計(jì)算位圖的大小時(shí)為每個(gè)內(nèi)存塊申請(qǐng)了一個(gè)位。但事實(shí)上每個(gè)位記錄的是一對(duì)伙伴內(nèi)存塊的關(guān)系，所以需要除以 2。而現(xiàn)在明顯浪費(fèi)了一半的內(nèi)存，在后面的 Linux 版本中改進(jìn)了這個(gè)問(wèn)題。

• 現(xiàn)在再回頭看看物理內(nèi)存分配?rmqueue()?函數(shù)的實(shí)現(xiàn):

• 申請(qǐng)內(nèi)存塊時(shí)，首先會(huì)在大小一致的空閑鏈表中申請(qǐng)，如果大小一致的空閑鏈表沒(méi)有空閑的內(nèi)存塊，那么只能向空間更大的空閑內(nèi)存塊鏈表中申請(qǐng)。

• 如果申請(qǐng)到的內(nèi)存塊比要申請(qǐng)的大小大，那么需要調(diào)用?expand()?函數(shù)來(lái)把內(nèi)存塊分裂成指定大小的內(nèi)存塊。

• 大內(nèi)存塊分裂為小內(nèi)存塊的過(guò)程也很簡(jiǎn)單，舉個(gè)例子：

• 如果我們要申請(qǐng) order 為 2 的內(nèi)存塊(也就是大小為 4 個(gè)內(nèi)存頁(yè)的內(nèi)存塊)，但是 order 為 2 的空閑鏈表沒(méi)有空閑的內(nèi)存，那么只能向 order 為 3 的空閑內(nèi)存塊鏈表中申請(qǐng)。如果 order 為 3 的空閑鏈表有空閑內(nèi)存塊，那么就從 order 為 3 的鏈表中申請(qǐng)一塊空閑內(nèi)存塊。并且把此內(nèi)存塊分裂為2塊 order 為 2 的內(nèi)存塊，一塊添加到 order 為 2 的空閑鏈表中，另外一塊分配給用戶。如果 order 為 3 的空閑鏈表也沒(méi)有空閑內(nèi)存塊，那么只能向 order 為 4 的空閑鏈表中申請(qǐng)，如此類(lèi)推。

• expand()?函數(shù)的源碼如下：

• 可以對(duì)照上面的思路來(lái)分析?expand()?函數(shù)。

• 我們接著來(lái)分析內(nèi)存塊的釋放，內(nèi)存塊的釋放是通過(guò)?free_pages()?函數(shù)來(lái)實(shí)現(xiàn)的。而?free_pages()?函數(shù)最終會(huì)調(diào)用?__free_pages_ok()?函數(shù)，__free_pages_ok()?函數(shù)代碼如下：

• 釋放過(guò)程和分配過(guò)程是一對(duì)互逆的過(guò)程，釋放內(nèi)存塊時(shí)首先看看伙伴內(nèi)存塊的狀態(tài)。如果伙伴內(nèi)存塊是空閑狀態(tài)，那么就與伙伴內(nèi)存塊合并為更大的內(nèi)存塊，并且一直嘗試合并為更大的內(nèi)存塊。

• 直到伙伴內(nèi)存塊不是空閑狀態(tài)或者達(dá)到內(nèi)存塊的最大限制(order為9)停止合并過(guò)程，根據(jù)上面代碼的注釋可以慢慢理解。