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

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

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

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

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

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

• 因為，Linux 是以頁面號來管理內(nèi)存頁的。所以，就是說兩個相鄰頁面號的頁面是伙伴關系。但是并不是所有相鄰頁面號的頁面都是伙伴關系, 例如 0 號和 1 號頁面是伙伴關系，但是 1 號和 2 號就不是了。為什么呢? 這是因為如果把 1 號頁面和 2 號頁面當成伙伴關系，那么 0 號頁面就沒有伙伴從而變成孤島了。

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

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

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

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

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

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

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

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

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

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

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

• 使用位圖來標識伙伴內(nèi)存塊使用情況的原因是: 當釋放內(nèi)存塊時, 如果對應的位是1的話, 那么說明另外一個伙伴內(nèi)存塊是空閑狀態(tài)的, 所以釋放當前內(nèi)存塊可以跟其伙伴內(nèi)存塊合并成一個更大的內(nèi)存塊了.

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

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

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

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

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

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

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

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

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

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

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

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

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

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