剖析Buddy算法中内存的放开和监禁

作者 |赵青窕

审校 |孙淑娟

内存的正当应用不时是系统的头号小事。目前系统中，除了驳回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和网络安保畛域，宣布过网络相关专利。