<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>
版权：本文版权归作者和博客园共有
转载：欢迎转载，但未经作者同意，必须保留此段声明；必须在文章中给出原文连接；否则必究法律责任