<code>Read the fucking source code!</code> --By 魯迅
<code>A picture is worth a thousand words.</code> --By 高爾基
說明：
Kernel版本：4.14
ARM64處理器，Contex-A53，雙核
使用工具：Source Insight 3.5， Visio
本文将分析<code>Buddy System</code>。
<code>Buddy System</code>夥伴系統，是通過将實體記憶體劃分為頁面來進行管理的系統，支援連續的實體頁面配置設定和釋放。此外，使用與碎片相關的算法來確定最大的連續頁面。
先通過一個例子大體介紹一下原理吧：
空閑的實體頁框按大小分組成<code>0~MAX_ORDER</code>個連結清單，每個連結清單存放頁框的大小為2的n次幂，其中n在<code>0 ~ MAX_ORDER-1</code>中取值。
假設請求配置設定<code>2^8 = 256</code>個頁框塊：
檢查<code>n = 8</code>的連結清單，檢查是否有空閑塊，找到了則直接傳回；
沒有找到滿足需求的，則查找<code>n = 9</code>的連結清單，找到<code>512大小</code>空閑塊，拆分成兩個<code>256大小</code>塊，将其中一個<code>256大小</code>塊傳回，另一個<code>256大小</code>塊添加到<code>n = 8</code>的連結清單中；
在<code>n = 9</code>的連結清單中沒有找到合适的塊，則查找<code>n = 10</code>的連結清單，找到1024大小空閑塊，将其拆分成<code>512 + 256 + 256</code>大小的塊，傳回需要擷取的<code>256大小</code>的塊，将剩下的<code>512大小</code>塊插入<code>n = 9</code>連結清單中，剩下的<code>256大小</code>塊插入<code>n = 8</code>的連結清單中；
合并過程是上述流程的逆過程，試圖将大小相等的<code>Buddy塊</code>進行合并成單獨的塊，并且會疊代合并下去，嘗試合并成更大的塊。合并需要滿足要求：
兩個<code>Buddy塊</code>大小一緻；
它們的實體位址連續；
第一個<code>Buddy塊</code>的起始位址為 <code>(2 x N x 4K)</code>的整數倍，其中<code>4K</code>為頁面大小，<code>N</code>為<code>Buddy塊</code>的大小；
<code>struct page</code>結構中，與<code>Buddy System</code>相關的字段有：
<code>_mapcount</code>： 用于标記<code>page</code>是否處在<code>Buddy System</code>中，設定成<code>-1</code>或<code>PAGE_BUDDY_MAPCOUNT_VALUE(-128)</code>；
<code>private</code>： 一個<code>2^k</code>次幂的空閑塊的第一個頁描述符中，<code>private</code>字段存放了塊的<code>order</code>值，也就是<code>k</code>值；
<code>index</code>： 存放<code>MIGRATE</code>類型；
<code>_refcount</code>： 使用者使用計數值，沒有使用者使用為0，有使用的話則增加；
合并時如下圖所示：
Buddy頁面配置設定的流程如下圖所示：
從上圖中可以看出，在頁面進行配置設定的時候，有以下四個步驟：
如果申請的是<code>order = 0</code>的頁面，直接選擇從<code>pcp</code>中進行配置設定，并直接退出；
<code>order > 0</code>時，如果配置設定标志中設定了<code>ALLOC_HARDER</code>，則從<code>free_list[MIGRATE_HIGHATOMIC]</code>的連結清單中進行頁面配置設定，配置設定成功則傳回；
前兩個條件都不滿足，則在正常的<code>free_list[MIGRATE_*]</code>中進行配置設定，配置設定成功則直接則傳回；
如果3中配置設定失敗了，則查找<code>後備類型fallbacks[MIGRATE_TYPES][4]</code>，并将查找到的頁面移動到所需的<code>MIGRATE</code>類型中，移動成功後，重新嘗試配置設定；
如下圖：
上述配置設定的過程，前3個步驟都會調用到<code>__rmqueue_smallest</code>，第4步調用<code>__rmqueue_fallback</code>，将從這兩個函數來分析。
<code>__rmqueue_smallest</code>的源代碼比較簡單，貼上來看看吧：
從代碼中可以看出：
從申請的<code>order</code>大小開始查找目标<code>MIGRATE</code>類型連結清單中頁表，如果沒有找到，則從更大的<code>order</code>中查找，直到<code>MAX_ORDER</code>；
查找到頁表之後，從對應的連結清單中删除掉，并調用<code>expand</code>函數進行處理；
<code>expand</code>函數的處理邏輯就跟本文概述中講的例子一樣，當在大的<code>order</code>連結清單中申請到了記憶體後，剩餘部分會插入到其他的<code>order</code>連結清單中，來一張圖就清晰了：
當上述過程沒有配置設定到記憶體時，便會開始從後備遷移類型中進行配置設定。
其中，定義了一個全局的<code>二維fallbacks</code>的數組，并根據該數組進行查找，代碼如下：
<code>__rmqueue_fallback</code>完成的主要工作就是從後備<code>fallbacks</code>中找到一個遷移類型頁面塊，将其移動到目标類型中，并重新進行配置設定。
下圖将示例整個流程：
頁面釋放是申請的逆過程，相對來說要簡單不少，先看一下函數調用圖吧：
當<code>order = 0</code>時，會使用<code>Per-CPU Page Frame</code>來釋放，其中：
<code>MIGRATE_UNMOVABLE, MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE</code>三個按原來的類型釋放；
<code>MIGRATE_CMA, MIGRATE_HIGHATOMIC</code>類型釋放到<code>MIGRATE_UNMOVABLE</code>類型中；
<code>MIGRATE_ISOLATE</code>類型釋放到Buddy系統中；
此外，在PCP釋放的過程中，發生溢出時，會調用<code>free_pcppages_bulk()</code>來傳回給Buddy系統。來一張圖就清晰了：
在整個釋放過程中，核心函數為<code>__free_one_page</code>，該函數的核心邏輯部分如下所示：
<code>__find_buddy_pfn</code>： 根據釋放頁面的<code>pfn</code>計算對應的<code>buddy_pfn</code>，比如<code>pfn = 0x1000, order = 3</code>，則<code>buddy_pfn = 0x1008</code>，<code>pfn = 0x1008, order = 3</code>，則<code>buddy_pfn = 0x1000</code>；
<code>page_is_buddy</code>：将<code>page</code>和<code>buddy</code>進行配對處理，判斷是否能配對；
進行combine之後，再将pfn指向合并後的開始位置，繼續往上一階進行合并處理；
按照慣例，再來張圖檔吧：
不得不說，還有很多細節沒有去扣，一旦沉淪，将難以自拔，待續吧。
作者：LoyenWang
出處：https://www.cnblogs.com/LoyenWang/
公衆号：<b>LoyenWang</b>
版權：本文版權歸作者和部落格園共有
轉載：歡迎轉載，但未經作者同意，必須保留此段聲明；必須在文章中給出原文連接配接；否則必究法律責任