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

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

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

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

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

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

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

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

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

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

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

• Linux 內核將物理內存劃分為?內存管理區(qū)?進行管理，內存管理區(qū)使用結構體?zone_struct?表示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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