认识Linux物理内存管理系统--Buddy System

Agenda

1.       Linux 如何管理物理内存

2.       什么是Buddy System

3.       如何从Buddy System中分配内存

4.       如何释放页到Buddy System

5.       冷热页

6.       关于fall-back zone lists

1.       Linux如何管理物理内存

         为了有效的管理物理内存（分配、回收），Linux将整个物理内存划分为若干个页，对每一个页，都有相关的数据结构来记录该页的状态和使用信息。在Linux中，每个页的大小是4KB. 对于一个512MB的物理内存一共有（512*1024*1024）/（4*1024）个页。对于每一个页，在Linux中都有一个struct page数据结构来记录该物理页的使用情况。所有页的struct page结构组成一个连续的数组存放在物理内存的某个地方。某页在物理内存中的物理地址除以4KB,就得到该页是第几个物理页索引，然后索引就可以查询struct page数组得到该页的具体信息。

图1. Memory Page

         除了使用struct page来记录某个4KB物理页的状态和使用信息外，Linux还将整个物理内存根据物理地址划分为不同的区域（zone）。zone的划分是与体系结构相关的，对于X86，ZONE可以划分为DMA区[0，16MB]、NORMAL区[16MB，min(memory length, 896MB)]和HIGHMEM区[min(memory length,896MB)，memory length]。对于ARM，ZONE划分为NORMAL区和HIGHMEM区。其中NORMAL区对应线性映射的物理内存，HIGHMEM区对应非线性映射的物理内存。其地址范围是：NORMAL[0,min(768MB，memory Length)] HIGHMEM[min(memory length,896MB)，memory length]。

图2. Memory Zone

2.       什么是Buddy System?

         Buddy System是Linux Kernel 进行物理内存页管理的一个子系统。在Buddy System中，管理的一个基本单位是block，每一个block有若干个连续的物理页组成，物理页的个数为2ⁿ，这个n在buddy system中被称为order。相同order的block，挂载一条双向链表上。当某个block空闲时，只要发现对应的伙伴也是空闲的，就和伙伴组成一个页数为2^（n+1）的block，挂载在order为(n+1)的双向链表上，换句话说一个页数为2ⁿ的block，是由两个页数为2^（n-1）的伙伴block组成的。因此，一个block的伙伴肯定是和这个block在物理地址上是连续的。在Linux中，order的默认的取值范围是[0,10]。

图3. Buddy Organize

在buddy system中，存入一个页会进行一次伙伴整合的迭代操作，直到不能再合并为止。那么，如何查找某个block的伙伴呢？在Linux中，一个block的伙伴信息记录在该block的第一个物理页的struct page上。也就是说，假若一个页在伙伴系统中，page->private的值为n,则后面连续的2ⁿ-1个页面就在buddy system中。一个页面在buddy System中，就代表了该页是空闲的，可以被分配。查找一个页数为2ⁿ的block的伙伴计算方法是buddy_index=page_index^(1<<n)，buddy_index 表示伙伴块首页的页索引，page_index是该block首页的页索引，n代表order。

3.       从buddy System中分配页

buddy System用来管理空闲的物理内存，接受进程的内存页申请。Linux提供给用户进程申请内存的接口函数中包含两个参数：一个是GFP_***，另一个是order。前者表示分配标志信息，从标志中可以知道进程要从哪个zone中申请物理内存，并在内存紧缺的情况下指导内存何时回收内存；后者表示需要分配2^order个连续的物理页。

buddy system根据参数order，在要求的zone中查找对应的链表。若该order的双向链表非空，则把该双向链表上的第一个block从buddy system中脱链，同时更新该双向链表上的block的数量，完成内存分配。若该order的双向链表为空，则查找order+1的双向链表，如果order+1的双向链表为空，则查找order+2的双向链表，直到查找到。假设查找到了第n个双向链表(n>order)，由于查找到的连续物理内存页的数量大于order，因此将该block一分为二，将后半部分block挂载到2^(n-1)的双向链表上，将前半部分再一分为二，将前半部分的后半部分挂载到2^(n-2)的双向链表上，将前半部分的前半部分再一分为二。。。直到与请求的order相等为止。如图四。

在图四中，假如要申请order为1的页，但buddy System中只有order为5的页。分配示意图如下：

图4. Allocate Pages

 注： 从buddy的空闲页面组织方式中，可以得出，有时候即使buddy 系统中有连续的2^N个空闲页面，对2^N个空闲页面的申请也不一定会成功。这里（http://lwn.net/Articles/368869/）有一个例子，可以说明这一点。

4.       释放页到buddy System

当非空闲的页被进程释放后，需要把页放回到伙伴系统中。由于block是作为一个整体被申请的，因此其释放也是以block为单位。若该block有2ⁿ个连续的物理页，在释放的时候，根据buddy_index = page_index^(1<<n)查找该block的order为n的伙伴。若查找到伙伴，则将两个order为n的block合并为一个order为n+1的block。同时再查找order为n+1 block的伙伴，若找到则两个order为n+1的block继续合并…直到其不能合并为止，插入到最终order的双向链表的最前端。释放的迭代过程是分配页的逆过程.

5.       冷热页

对于multi-processors，由于多个core共享存储器，进程并发执行。在一个core上运行的进程需要从某个zone的伙伴系统中申请页必须首先锁住该zone，这样其他core上跑的进程需要申请页的时候就需要等待该zone的锁。为了提高buddy system的性能，Linux提出了冷热页的概念。冷热页是每CPU的。在每个core上对每个zone都维护了一条双向链表。该链表上链接的都是单个页，当进程申请order为0的页是，就需要先从该cpu的冷热页链表上去拿页。关于冷热页的详细介绍，请猛击：认识Linux/ARM 中的冷热页

6.       关于Fall-back zone lists

当内存管理单元在某个zone分配可用内存页的时候，如果该zone中的空闲内存不足，则会到候补zone中进行分配。候补zone不止一个，特别是对于NUMA的存储架构。因此对于候补zone也有一个列表，排在最前面的作为第一候补，依照排队的顺序优先级逐步降低。关于fall-back zone lists的详细介绍，请猛击：How Linux/ARM initialize fallback-zone-lists

==全文完==