作者 |赵青窕

审校 |孙淑娟

内存的合理利用一直是系统的头等大事。目前系统中，除了采用Buddy和slab管理内存外，还会采用内存水线检测处理，PCP机制，CMA机制等进行内存的优化。在本文中，我们将从Buddy算法中内存的申请和释放，来探索内存的奥秘。

基本概念

zone：有的地方把zone称为管理区，每个node下会划分成不同的zone。有的系统会划分成3个zone区，有的会划分成2个zone区。zone区的个数会因平台，内核，系统的位数等有差异。

free_area：每个zone区根据2的order次方(order的范围从0到MAX_ORDER)进一步划分，划分后的每个小区域通过free_area[order]表示。

如下图红色方框中所示，按照红色方框从左到右分别是node，zone和free_area。

水线：每个zone存在三个水线，若当前zone中空闲页高于WMARK_HIGH，则当前zone区的空闲内存较多；若空闲页低于WMARK_LOW，则交换守护进程开始将内存交换到磁盘上；若空闲页低于WMARK_MIN，则内存回收系统还需要大量回收内存。

order：每个zone区根据order，把内存按照2的order继续划分为不同的area。

PCP链表：该链表中的每一个成员大小均是2的0次方个页面，每次申请和释放1个页面，都会优先考虑PCP。当PCP为空时，会从Buddy中申请；当PCP中页面比较多，超过限制时，会把页面释放到Buddy中。

内存申请

比较常用的内存申请函数是kmalloc，当申请的内存大于KMALLOC_MAX_CACHE_SIZE时，会通过函数kmalloc_large从Buddy中申请内存，否则从slab中申请内存。本文中暂不分析从slab申请内存的情况。

kmalloc_large函数实现如下，Buddy算法中，内存的分配和释放均离不开order，我们可以看到，在该函数内部通过size来计算出对应的order，就很好地把Buddy和slab连接在一起了。

函数kmalloc_order_trace会调用函数alloc_pages，进而调用函数struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid, nodemask_t *nodemask)来实现内存的分配。实际上，Buddy提供的对外申请内存函数是alloc_pages，但其内部实现大部分情况下均是通过__alloc_pages_nodemask来实现。该函数分三步进行处理，分别如下：

1.内存分配上下文结构

内存分析上下文采用结构体struct alloc_context来表示，其结构体定义如下：

各个成员含义如下：

从上面的结构体struct alloc_context的说明可以看出，该结构体具体细化了内存分配的各种需求，其具体实现如下图中红色方框所示：

2.快速分配

在完成第一步后，就可以通过函数get_page_from_freelist进行一次快速分配。该函数才是内存分配真正的开始位置，接下来我将详细说明该过程，为了简化描述，同时为了让大家容易理解，暂时不考虑CPUSET的情况。

该函数本质就是从preferred_zone开始，遍历zonelist，其每一次遍历时，处理流程如下：

每个node节点会对脏页数进行限制，当超过限制后，将无法申请具有__GFP_WRITE标志的内存块，需要跳出当前zone区，转而扫描下一个zone区，其内核处理代码如下图所示，图中进行了标注，方便大家理解。

前面小节中有提到每个zone中存在三个水线，在内存申请时，默认采用WMARK_LOW，使用函数zone_watermark_fast进行水线判断。

假如通过水线检测，发现内存不够，则会判断当前申请内存的请求是否采用ALLOC_NO_WATERMARKS，若采用，则说明当前剩余内存多少与当前申请没有任何关系，会调用rmqueue进行内存分配；若没有ALLOC_NO_WATERMARKS声明，则进行下一步reclaim操作；

假如通过水线检测，发现当前还有足够内存，则调用函数rmqueue进行内存分配。

reclaim操作首先是通过函数zone_allows_reclaim来判断当前的node是否支撑reclaim操作，如果不支持，就退出当前循环，执行下一个循环操作；若支持，就调用node_reclaim执行内存回收的工作。

当函数node_reclaim返回值是NODE_RECLAIM_NOSCAN或者NODE_RECLAIM_FULL时，表示当前虽然内存不够，但我无能为力了。这种情况下，只能退出循环，执行下一个操作；当返回值是其余的情况时，就会重新进行水位检测，若此时内存足够，则调用rmqueue进行内存分配，否则退出循环，执行下一个循环操作。

假如当前系统使用的是非NUMA，则不会进行reclaim操作，当水位线检测发现内存不够时，会跳出循环，尝试下一个zone；假如当前系统是NUMA，才会进行上述描述中的判断，来决定是否进行内存回收。

在内存分配时，分两种情况进行处理，分别是order= 0及order != 0。

当order = 0时，会首先从PCP链表中进行内存申请，其具体流程如下：

当order != 0，即要申请多页，下面是其处理过程，根据实际情况调用__rmqueue_smallest，__rmqueue_cma或者__rmqueue进行内存的分配。

对于设置了ALLOC_HARDER的情况，先尝试通过函数__rmqueue_smallest来分配MIGRATE_HIGHATOMIC类型的内存块，具体实现就是从zone->free_area[order]中根据需要的内存类型进行分配。该函数实现比较简单，就是遍历free_area以便找到合适的内存块，下图是__rmqueue_smallest的实现，增加了注释方便大家理解。

假如通过上面的__rmqueue_smallest没有找到合适的内存块，在申请内存时，使用标志__GFP_CMA申请的MIGRATE_MOVABLE，则再次使用函数__rmqueue_cma申请内存，实际上__rmqueue_cma内部是调用__rmqueue_smallest(zone, order, MIGRATE_CMA)实现的。

若上面的两步__rmqueue_smallest，__rmqueue_cma均失败，则会调用__rmqueue。该函数内部实际上也是通过__rmqueue_smallest实现的，当__rmqueue_smallest只会从指定的migtatetype中进行分配，当分配失败后，会通过函数__rmqueue_fallback从后备fallbacks中找到一个迁移类型页块，将其迁移到目标迁移类型中后重新进行分配。

至此快速分配结束，若已经分配到内存，则会退出分配流程，否则进行下一步操作：慢速分配。

3.慢速分配

慢速分配是通过函数__alloc_pages_slowpath来实现的。从快速分配发现无法分配到需要的内存，紧接着内核通过慢速分配对内存进行整理，尝试找到合适的内存。其整理过程包含：

这四种方式都会伴随着调用函数get_page_from_freelist来进行内存分配。

至此内存分配函数就完成了。从上面的描述可以看出，当内存足够时，通常情况下快速分配就足够了。只有在内存不够时，会进行慢速分配，慢速分配里面进行内存回收，整理等操作后再进行分配。若此时还没有足够的内存可以分配，说明内存耗尽，可能是因为内存泄漏导致内存不足，这个时候就需要去定位内存泄漏问题了。

内存释放

Buddy中内存释放入口函数是free_pages。该函数的实现如下，从下面的函数中可以看出最后是通过free_unref_page或者__free_pages_ok来实现的，其余的部分均合法性判断。

函数free_pages 接受两个参数，分别是虚拟地址和需要释放的页面数，该函数内部利用virt_to_page把虚拟地址转化成Buddy算法需要的struct page结构体。

__free_pages函数先将对应的struct page->_refcount减去1，之后检测_refcount是否为0，若为0，继续进行释放操作，否则不进行内存释放操作。通过该函数__free_pages可以看到，不管是否进行了内存释放操作，该函数都可以正常退出且没有返回值。假如内存释放操作异常，就会引发内存泄漏问题，且代码中没有任何日志和错误码，这种泄漏通常很难排查。

free_the_page是真正的内存释放函数，该函数根据order的不同，分别进行两种不同的处理：

接下来我们分别来了解这两种情况的处理方式。

1.order为0的情况

函数内存会根据order是否为0来进行相应的操作，对于order = 0的情况，此处是调用函数free_unref_page。有些内核中会调用函数free_hot_cold_page(page, false)来实现，但不管调用哪一个函数，其内部均是进行相应的判断后，通过把page插入PCP链表相应位置处实现。实际上内核在把内存释放到PCP链表时，会进行PCP链表成员个数pcp->count的判断，当pcp->count >= pcp->high时，会调用函数free_pcppages_bulk释放一部分PCP中的页面到 Buddy 子系统中。

此处我们需要注意，并不是所有order = 0的内存全部释放到PCP链表中，在结构体struct page中有个成员index，该成员指明了该部分内存的类型，若类型为MIGRATE_ISOLATE，则其内存(实际上是一个页面)会释放到Buddy中，若类型对应的数据大于或等于MIGRATE_PCPTYPES，则释放到类型为MIGRATE_MOVABLE的PCP链表中，其余的释放到对应类型的PCP链表中。下图是order= 0时的核心处理代码，图中已经标注了各个关键地方，供大家参考。

2.order不为0的情况

当order不为0时，会通过函数__free_pages_ok调用free_one_page来实现。其核心代码如下图所示，图中对代码进行了标注，从其代码我们可以发现其实现是通过while循环来查找可以合并的页块，查找的方式就是按照order的次序挨个查找，其整个流程就是查找--->确认--->删除--->合并。

此时，我们来思考一个问题，有些特殊内存区是无法进行合并的，在内核代码中特别表明了如下注释：

其对应的代码处理如下图所示，其代码主要目的有两点，其一是保证可以充分地进行页块的合并，从而尽量减少内存碎片化；其二是保证特殊用途的内存块不受影响。

最后根据实际情况，通过函数list_add(&page->lru, &zone->free_area[order].free_list[migratetype])或者函数list_add_tail(&page->lru,&zone->free_area[order].free_list[migratetype])把合并后的page添加到对应的链表中。

总结

不同平台，不同内核版本的系统，在内存处理上或许会存在或多或少的差异，但其核心思想是相同的。通过本文，我们可以详细地了解Buddy中内存申请和释放的处理方式，以及当内存不足时，Buddy是如何处理的。

作者介绍

赵青窕，社区编辑，从事多年驱动开发。研究兴趣包含安全OS和网络安全领域，发表过网络相关专利。