作者|赵清瑶点评|SunShujuanKernel内存管理比较复杂，主要包括Buddy算法、vmalloc管理、slab算法、kmapper以及初始化阶段物理内存管理相关的两个模块memblock和bootmem。除了以上模块外，还有内存迁移、水线检测、kmemleak、内存信息统计、PCP等辅助内容。本文重点介绍Buddy算法（又称伙伴算法），它以页面为单位进行管理。Buddy算法介绍目前，内核中的Buddy算法是通过下图所示的方式来管理内存的。我把Buddy算法分为三个部分如下图所示。第一区，核心数据结构是structzone；区域二，核心数据结构为structfree_areafree_area[MAX_ORDER]；在区域三中，页面链表是核心内容。接下来，我将详细介绍这三个部分，并通过分配功能来解释Buddy的工作细节。图1Buddy框架1.zone通常用zone来表示不同的内存管理区域，即将内存分成不同的组，每个组就是一个zone。在内核中，每个区域由结构体structzone表示，其主要成员如下：structzone{unsignedlongwatermark[NR_WMARK];unsignedlongzone_start_pfn;无符号长管理页面；无符号长spanned_pa??ges；unsignedlongpresent_pages;structfree_areafree_area[MAX_ORDER];constchar*name;structpglist_data*zone_pgdat;}标识内存水线成员unsignedlongwatermark[NR_WMARK]，其中NR_WMARK定义如下：enumzone_watermarks{WMARK_MIN,WMARK_LOW,WMARK_HIGH,NR_WMARK};从上面的定义我们可以看出，每个区域有3条水线。如果当前zone中的freepages高于WMARK_HIGH，那么当前zone中的freememory更多；如果空闲页面低于WMARK_LOW，交换守护进程开始将内存交换到磁盘；如果freepage低于WMARK_MIN，内存回收系统需要回收大量内存。使用Buddy申请内存时，会进行水线判断，进行相应的操作；与伙伴系统管理相关的成员unsignedlongzone_start_pfn；无符号长管理页面；无符号长spanned_pa??ges；unsignedlongpresent_pages;structfree_areafree_area[MAX_ORDER]topfour一个是对应zone区域的页码信息。free_area是partner算法中的关键成员，也是area1和area2连接的关键成员。每个zone区域会被分成MAX_ORDER组，数组free_area中的每个成员代表一个组。成员constchar*name指定对应zone的名称，通常为dma、Normal或highmem，其中highmem在64位系统中不会出现；下面是典型的32位系统中的zone划分方式：ZONE_DMA(0~16M)：DMA内存分配区；ZONE_NORMAL(16MB~896MB)：普通映射内存区；ZONE_HIGHMEM(896MB~)：高端内存区，不能永久映射到内核地址空间的页面；内核一般不用，如果要用，通过kmap做动态映射；指向zone区域中node对应的指针成员structpglist_data*zone_pgdat，node是内存管理中的重要成员。对于UMA架构，只有一个节点，所有的zone都属于同一个节点，但是对于NUMA架构，有多个不同的节点，每个节点又划分为不同的zone。所有zone区域也一起组织在structpglist_data中。2、在free_area和page链表的内存管理和分配过程中，有一个重要的参数order。当我们使用kmalloc申请大内存时，最后会调用函数__alloc_pages_nodemask来申请内存。这个函数需要一个参数顺序。当order=0时，表示申请的内存大小为1（20）页；当order=1时，表示申请的内存大小为2（21）页。在Buddy算法中，内存按照2的次方（即2order，order的范围从0到MAX_ORDER）被分成不同的组，每个组由对应的free_area[order]表示，例如，free_area[0]对应的是由20个内存块大小的pageblock组成的组，free_area[1]对应的是由21个内存块大小的pageblock组成的组，结构体structzone使用了图中的free_area成员1.Area1和Area2串联。结构体structfree_area定义如下（不同平台或不同内核会有差异，但核心思想是一样的）：structfree_area{structlist_headfree_list[MIGRATE_TYPES];无符号长nr_free；};从结构上可以看出，每个free_area是根据MIGRATE_TYPES划分成不同的group，每个group通过链表free_list将相同类型的pageblock连接在一起，这样free_list就连接了图1中的area2和area3，从而间接地将区域1和区域3连接在一起。结构structpage比较复杂，有一个成员structlist_headlru，通过它把图1中3区的pageblock和2区对应的free_list链接起来。Buddy内存分配的核心思想通过一个例子。当通过Buddy（即order=0）分配一个物理页时，会从对应zone（暂且不考虑PCP）的free_area[0]所管理的区域中分配一个page，该page将从free_area[0]从链表中移除；当free_area[0]上没有可用的物理页时，Buddy会去free_area[1]上查找，如果有可用的物理页，则从free_area[1]的链表中移除该页块，同时，该页block被拆分成两块，一块插入free_area[0]，另一块传递给内存请求者；如果free_area[1]上没有可用的页面，则继续向上查找。如下图2所示，没有order=0对应的页块，所以拆分出一个order=1的页块，一半返回给order=1的链表，一半返回给请求者.如果order=1没有需要的pageblock，则在内存分配过程中会从order=3开始继续查找，直到找到pageblock或者遍历所有的order。图2物理页分配示意图实际上，在整个内存分配过程中，会出现很多特殊情况。Buddy算法在进行内存分配时，会根据水线设置进行内存回收或唤醒内核线程kswapd，或使用CPU的冷热页面队列进行内存分配，或进行页面移动等。如果你尝试过移动页面，kswapd调出了一些页面，也进行了内存回收，但是仍然没有可以分配的内存，那么就会触发out_of_memory。总之，这些特殊情况的处理离不开图1所示的Buddy框架，下图是根据我本地代码使用kmalloc申请大内存时的调用流程（使用kmalloc申请时没有使用buddy对于小内存）。最关键的内存分配函数是prepare_alloc_pages、get_page_from_freelist、rmqueue和__alloc_pages_slowpath。感兴趣的朋友可以结合图1所示的框架来查看这些功能的具体实现。当一个物理页面被释放给系统时，会通过structpage推导出该页面对应的zone区域（例如该页面属于NORMAL区域）和对应的页面类型，然后根据对应的顺序（即如图1中区域3的部分进行合并），最后将合并后的块插入到新的顺序中，继续合并过程，直到无法合并或者已经合并到最大命令。例如，当被释放的物理页面得到其属于NORMAL区域的free_area[0]时，此时可以将free_area[0]中的页面与被释放的页面合并，这样合并后的页面就可以添加到free_area[1].此合并操作将一直持续到合并完成。这个过程其实就是图2的逆过程。总结内存管理比较复杂。本文主要介绍Buddy的核心思想，但这只是内存管理的冰山一角，却是比较基础和核心的内容。因此，了解Buddy的整体架构是非常有必要的。作者介绍社区编辑赵庆尧，从事驱动开发多年。他的研究兴趣包括安全操作系统和网络安全，并发表了与网络相关的专利。
