• 内核分配物理内存时，是以内存页作为分配单位的。但有时候内核需要分配一些物理内存地址连续的内存页，所以，Linux内核使用了 伙伴系统分配算法 来管理系统中的物理内存页.

• 什么是 伙伴系统分配算法？下面将会进行详细的介绍。

什么是伙伴系统分配算法

• 在 Linux 内核中，要分配内存页可以使用 alloc_pages() 函数来完成。而 alloc_pages() 函数最后会调用 rmqueue() 函数来分配内存页, rmqueue() 函数原型如下:

• 参数 zone 是内存管理区, 而 order 是要分配 2order 个内存页. 由于 rmqueue() 函数使用了伙伴系统算法, 所以下面先来介绍一下伙伴系统算法的原理.

• 伙伴系统算法 的核心是 伙伴，那什么是伙伴呢？在 Linux 内核中，把两个物理地址相邻的内存页当作成伙伴。

• 因为，Linux 是以页面号来管理内存页的。所以，就是说两个相邻页面号的页面是伙伴关系。但是并不是所有相邻页面号的页面都是伙伴关系, 例如 0 号和 1 号页面是伙伴关系，但是 1 号和 2 号就不是了。为什么呢? 这是因为如果把 1 号页面和 2 号页面当成伙伴关系，那么 0 号页面就没有伙伴从而变成孤岛了。

• 那么给定一个 i 号内存页，怎么找到他的伙伴内存页呢？通过观察我们可以发现，如果页面号是复数的，那么他的伙伴内存页要加 1。

• 如果页面号是单数的，那么他的伙伴内存页要减 1。所以，对于给定一个页面号为 i 的内存页，他的伙伴内存页号可以使用以下的代码获得：

• 那么知道一个内存页的伙伴页面有什么用呢？答案是为了合并为更大的内存页，例如把两个单位为1的伙伴内存页合并成为一个单位为2的内存页(这时应该称为内存块)，把两个单位为2的伙伴内存块合并为单位为4的内存块，以此类推。

• 所以，使用伙伴系统算法只能分配 2order (order为0,1,2,3...)个页面。那么order是不是无限大呢？当然不是，在Linux内核中，order的最大值是 10。也就是说在内核中，最大能够申请到一个 29 个页面的内存块。

• Linux 内核将物理内存划分为 内存管理区 进行管理，内存管理区使用结构体 zone_struct 表示。

• 而在内存管理区数据结构中有个名为 free_area 类型为 free_area_t 的字段，他的作用就是用来管理内存管理区内的空闲物理内存页. 定义如下：

• free_area 是伙伴系统算法的核心，可以看到 free_area 有10个元素。每个元素都是一个类型为 free_area_t 的结构体，free_area_t 结构的 free_list 字段用于连接有相同页面个数的内存块。map 字段是一个位图，用于记录伙伴内存块的使用情况。

• Linux内核使用 free_area[i] 管理 2i 个内存页面大小的内存块列表，例如 free_area[0] 就是管理1个内存页面大小的内存块(20等于1)；而 free_area[1] 则管理2个内存页面大小的内存块(21等于2)。如下图所示：

• 【文章福利】小编推荐自己的Linux内核技术交流群:【891587639】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！前100名进群领取，额外赠送一份价值699的内核资料包（含视频教程、电子书、实战项目及代码)   

• 管理物理内存页的 struct page 结构中有个 list 的字段，内核就是通过这个字段把有着相同个数页面的内存块连成一个链表的：

• 前面我们说过，在 free_area_t 结构中有个名为 map 的字段，map 字段是一个位图，每个位记录着一对伙伴内存块的使用情况。举个例子，如果一对伙伴内存块中的某一个内存块在使用，那么对应的位就为 1，如果两个伙伴内存块都是空闲或者使用，那么对应的位就为 0。如下图：

• 使用位图来标识伙伴内存块使用情况的原因是: 当释放内存块时, 如果对应的位是1的话, 那么说明另外一个伙伴内存块是空闲状态的, 所以释放当前内存块可以跟其伙伴内存块合并成一个更大的内存块了.

伙伴系统分配算法实现

• 我们来看看内核在初始化内存管理区时怎么初始化空闲内存块链表的，代码如下：

• 上面的代码首先为每个管理不同大小空闲内存块的 free_area_t 结构初始化其 free_list 字段，然后根据其管理内存块的大小来计算需要多少个位来记录伙伴内存块的关系，并保存到 map 字段中。

说明一下，这里计算位图的大小时为每个内存块申请了一个位。但事实上每个位记录的是一对伙伴内存块的关系，所以需要除以 2。而现在明显浪费了一半的内存，在后面的 Linux 版本中改进了这个问题。

• 现在再回头看看物理内存分配 rmqueue() 函数的实现:

• 申请内存块时，首先会在大小一致的空闲链表中申请，如果大小一致的空闲链表没有空闲的内存块，那么只能向空间更大的空闲内存块链表中申请。

• 如果申请到的内存块比要申请的大小大，那么需要调用 expand() 函数来把内存块分裂成指定大小的内存块。

• 大内存块分裂为小内存块的过程也很简单，举个例子：

• 如果我们要申请 order 为 2 的内存块(也就是大小为 4 个内存页的内存块)，但是 order 为 2 的空闲链表没有空闲的内存，那么只能向 order 为 3 的空闲内存块链表中申请。如果 order 为 3 的空闲链表有空闲内存块，那么就从 order 为 3 的链表中申请一块空闲内存块。并且把此内存块分裂为2块 order 为 2 的内存块，一块添加到 order 为 2 的空闲链表中，另外一块分配给用户。如果 order 为 3 的空闲链表也没有空闲内存块，那么只能向 order 为 4 的空闲链表中申请，如此类推。

• expand() 函数的源码如下：

• 可以对照上面的思路来分析 expand() 函数。

• 我们接着来分析内存块的释放，内存块的释放是通过 free_pages() 函数来实现的。而 free_pages() 函数最终会调用 __free_pages_ok() 函数，__free_pages_ok() 函数代码如下：

• 释放过程和分配过程是一对互逆的过程，释放内存块时首先看看伙伴内存块的状态。如果伙伴内存块是空闲状态，那么就与伙伴内存块合并为更大的内存块，并且一直尝试合并为更大的内存块。

• 直到伙伴内存块不是空闲状态或者达到内存块的最大限制(order为9)停止合并过程，根据上面代码的注释可以慢慢理解。