一篇让你弄明白Linux内核内存管理-内存碎片整理(实现流程)
我们知道内存是以页框为单位，每个页框大小默认是4K（大页除外），而在系统运行时间长后就会出现内存碎片，内存碎片的意思就是一段空闲页框中，会有零散的一些正在使用的页框，导致此段页框被这些正在使用的零散页框分为一小段一小段连续页框，这样当需要大段连续页框时就没办法分配了，这些空闲页框就成了一些碎片，不能合并起来作为一段大的空闲页框使用，如下图：
白色的为空闲页框，而有斜线的为已经在使用的页框，在这个图中，空闲页框都是零散的，它们没办法组成一块连续的空闲页框，它们只能单个单个进行分配，当内核需要分配连续页框时则没办法从这里分配。为了解决这个问题，内核实现了内存碎片整理功能，其原理很简单，就是从这块内存区段的前面扫描可移动的页框，从内存区段后面向前扫描空闲的页框，两边扫描结束后，将可移动的页框放入到空闲页框中，最后最理想的结果就如下图：
这样移动之后就把前面的页框整理为了一大段连续的物理页框了，当然这只是理想情况，因为并不是所有页框都可以进行移动，像内核使用的页框大部分都不能够移动，而用户进程的页框大部分是可以移动了。
一、内存碎片整理
对于内存碎片整理来说，只会正对三种类型的页进行整理，分别是：MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE、MIGRATE_CMA。并且内存碎片整理是耗费一定的内存、CPU和IO的。
在内存碎片整理中，可以移动的页框有MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE与MIGRATE_CMA这三种类型的页框，而因为内存碎片整理分为同步和异步，在异步过程中，只会移动MIGRATE_MOVABLE和MIGRATE_CMA这两种类型的页框。因为这两种类型的页框处理，是不会涉及到IO操作的。而在同步过程中，这三种类型的页框都会进行移动，因为MIGRATE_RECLAIMABLE基本上都是文件页，在移动过程中，有可能要将脏页回写，会涉及到IO操作，也就是在同步过程中，是会涉及到IO操作的。
【文章福利】小编推荐自己的Linux内核技术交流群:【891587639】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！前100名进群领取，额外赠送一份价值699的内核资料包（含视频教程、电子书、实战项目及代码)
二、内存碎片整理模式
内存碎片整理分为三种模式，三种模式耗费的资源和对整个系统的压力不一样，如下：
异步模式：内存碎片整理最常用的模式，在此模式中不会进行阻塞(但是时间片到了可以进行主动调度)，也就是此种模式不会对文件页进行处理，文件页用于映射文件数据使用，这种模式也是对整体系统压力较小的模式。
轻同步模式：当异步模式整理不了更多内存时，有两种情况下会使用轻同步模式再次整理内存：1.明确表示分配的不是透明大页的情况下；2.当前进程是内核线程的情况下。这个模式中允许大多数操作进行阻塞(比如隔离了太多页，需要阻塞等待一段时间)。这种模式会处理匿名页和文件页，但是不会对脏文件页执行回写操作，而当处理的页正在回写时，也不会等待其回写结束。
同步模式：所有操作都可以进行阻塞，并且会等待处理的页回写结束，并会对文件页、匿名页进行回写到磁盘，所以导致最耗费系统资源，对系统造成的压力最大。它会在三种情况下发生：1.从cma中分配内存时；2.调用alloc_contig_range()尝试分配一段指定了开始页框号和结束页框号的连续页框时；3.通过写入1到sysfs中的/vm/compact_memory文件手动实现同步内存碎片整理。
在内存不足以分配连续页框后导致内存碎片整理时，首先会进行异步的内存碎片整理，如果异步的内存碎片整理后还是不能够获取连续的页框(这种情况发生在很多离散的页的类型是MIGRATE_RECLAIMABLE)，并且gfp_mask明确表示不处理透明大页的情况或者该进程是个内核线程时，则进行轻同步的内存碎片整理。
在kswapd中，永远只进行异步的内存碎片整理，不会进行同步的内存碎片整理，并且在kswapd中会跳过标记了PB_migrate_skip的pageblock。相反非kswapd中的内存碎片整理，当推迟次数超过了推迟阀值时，会将pageblock的PB_migrate_skip标记清除，也就是会扫描之前有PB_migrate_skip标记的pageblock。
在同步内存碎片整理时，会忽略所有标记了PB_migrate_skip的pageblock，强制对这段内存中所有pageblock进行扫描(当然除了MIGRATE_UNMOVEABLE的pageblock)。
异步是用得最多的，它整理的速度最快，因为它只处理MIGRATE_MOVABLE和MIGRATE_CMA两种类型，并且不处理脏页和阻塞的情况，遇到需要阻塞的情况就返回。而轻同步的情况是在异步无法有效的整理足够内存时使用，它会处理MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE、MIGRATE_CMA三种类型的页框，在一些阻塞情况也会等待阻塞完成(比如磁盘设备回写繁忙，待移动的页正在回写)，但是它不会对脏文件页进行回写操作。同步整理的情况就是在轻同步的基础上会对脏文件页进行回写操作。
这里需要说明一下，非文件映射页也是有可能被当成脏页的，当它加入swapcache后会被标记为脏页，不过在内存碎片整理时，即使匿名页被标记为脏页也不会被回写，它只有在内存回收时才会对脏匿名页进行回写到swap分区。在脏匿名页进行回写到swap分区后，基本上此匿名页占用的页框也快被释放到伙伴系统中作为空闲页框了。
三、内存碎片整理算法
先说一下内存碎片整理的算法，首先，内存碎片整理是以zone为单位的，而zone中又以pageblock为单位。在内存碎片整理开始前，会在zone的头和尾各设置一个指针，头指针从头向尾扫描可移动的页，而尾指针从尾向头扫描空闲的页，当他们相遇时终止整理。下图就是简要的说明图：
初始时内存状态(默认所有正在使用的页框都为可移动)：
从头扫描可移动页框：
从尾扫描空闲页框：
结果：
但是实际情况并不是与上面图示的情况完全一致。头指针每次扫描一个符合要求的pageblock里的所有页框，当pageblock不为MIGRATE_MOVABLE、MIGRATE_CMA、MIGRATE_RECLAIMABLE时会跳过这些pageblock，当扫描完这个pageblock后有可移动的页框时，会变为尾指针以pageblock为单位向前扫描可移动页框数量的空闲页框，但是在pageblock中也是从开始页框向结束页框进行扫描，最后会将前面的页框内容复制到这些空闲页框中。
需要注意，扫描可移动页框是要先判断pageblock的类型是否符合，符合的pageblock才在里面找可移动的页框，当扫描了一个符合的pageblock后本次扫描可移动页框会停止，转到扫描空闲页框。而扫描空闲页框时也会根据pageblock进行扫描，只是从最后一个pageblock向前扫描，而在每个pageblock里面，也是从此pageblock开始页框向pageblock结束页框进行扫描。当需要的空闲页框数量=扫描到的一个pageblock中可移动的页框数量时，则会停止。
四、内存碎片整理发生时机
现在再来说说什么时候会进行内存碎片整理。它会在四个地方调用到：
内核从伙伴系统以min阀值获取连续页框，但是连续页框又不足时。
当需要从指定地方获取连续页框，但是中间有页框正在使用时。
因为内存短缺导致kswapd被唤醒时，在进行内存回收之后会进行内存碎片整理。
将1写入sysfs中的/vm/compact_memory时，系统会对所有zone进行内存碎片整理。
而内存碎片整理是一个相当耗费资源的事情，它并不会经常会执行，即使因为内存短缺导致代码中经常调用到内存碎片整理函数，它也会根据调用次数选择性地忽略一些执行请求，见内存碎片整理推迟。
系统判定是否执行内存碎片整理的标准是
在分配页框过程中，zone显示是有足够的空闲页框供于本次分配的，但是伙伴系统链表中又没有连续页框段用于本次分配。原因就是过多分散的空闲页框，它们没办法组成一块连续页框存放在伙伴系统的链表中。
在kswapd唤醒后会对zone的页框阀值进行检查，如果可用页框少于高阀值则会进行内存回收，每次进行内存回收之后会进行内存碎片整理。
即使满足标准，也不一定会执行内存碎片整理，具体见后面的内存碎片整理推迟和compact_zone()函数。
内存碎片整理结束时机
在内存碎片整理中，一次zone的内存碎片整理结束条件有三条：
可移动页框扫描的位置是否已经超过了空闲页框扫描的位置，超过则结束整理，并且会重置zone->compact_cached_free_pfn和zone->compact_cached_migrate_pfn，并且不是kswap时，会设置zone->compact_blockskip_flush为真
zone的空闲页框数量满足了 (zone的low阀值 + 1<<order + zone的保留页框) 条件。
判断伙伴系统中是否有比order值大的空闲连续页框块，有则结束整理，如果order为-1，则忽略此条件
不过有例外，通过写入到/proc/sys/vm/compact_memory进行强制内存碎片整理的情况，则判断条件只有第1条。对于zone来说，可移动页扫描和空闲页扫描交汇，也就是第一种情况时，才算是对zone进行了一次完整的内存碎片整理，这个完整的内存碎片整理并不代表一次内存碎片整理就能实现，也有可能是对zone进行多次内存碎片整理才达到的，因为每次内存碎片整理结束时机还有另外两种。当zone达到一次完整的内存碎片整理时，会重置两个扫描的起始为zone的第一个页和最后一个页，并且不是处于kswap中时，会设置zone->compact_blockskip_flush为真，这个zone->compact_blockskip_flush在kswapd准备睡眠时，会将zone的所有pageblock的PB_migrate_skip标志清除。
五、内存碎片整理推迟
内存碎片整理虽然是针对每个zone的，但是执行的时候传入的是一个zonelist，这样就会有一种情况，就是可能某个zone刚进行过内存碎片整理，而系统因为内存不足又进行了内存碎片整理，导致这个刚进行内存碎片整理的zone又要执行内存碎片整理，为了避免这种情况，内核会为每个zone做一个整理推迟计数，这个计数是每个zone都会有的，在struct zone里：
compact_considered：称为内存碎片整理推迟计数器，每次zone的内存碎片整理推迟了，此值会+1
compact_defer_shift：称为内存碎片整理推迟阀值，内存碎片整理推迟计数器达到 1 << compact_defer_shift 后，就不能对zone进行内存碎片整理推迟了。
compact_order_failed：称为内存碎片整理失败最大order值，记录着此zone进行内存碎片整理失败时使用的最大的order值
当一个zone要进行内存碎片整理时，首先会判断本次整理需不需要推迟，如果本次内存碎片整理使用的order值小于zone内存碎片整理失败最大order值时，不用进行推迟，可以直接进行内存碎片整理；但是当order值大于zone内存碎片整理失败最大order值时，会增加内存碎片整理推迟计数器，当内存碎片整理推迟计数器未达到内存碎片整理推迟阀值，则会跳过本次内存碎片整理，如果达到了，那就需要进行内存碎片整理。也就是当order小于zone内存碎片整理失败最大order值时，不用进行推迟，而order大于zone内存碎片整理失败最大order值时，才考虑是否进行推迟。
在对一个zone进行内存碎片整理时，结果一般分为三种：
整理结束后，zone的空闲页框数量达到了 (low阀值 + 1 << order + 保留的页框数量)，这种情况就称为内存碎片整理半成功
整理结束后，顺利从zone中获取到链入1 << order个连续页框，这种情况称为内存碎片整理成功
整理结束后，zone的空闲页框数量没达到 (low阀值 + 1 << order + 保留的页框数量)，这种情况称为内存碎片整理失败
当内存碎片整理实现半成功时，如果使用的order大于等于zone的内存碎片整理失败最大order值，则将内存碎片整理失败最大order值设置为本次内存碎片整理使用的order值+1。
当内存碎片整理实现成功时，重置内存碎片整理推迟计数器和内存碎片整理推迟阀值计数为0并且如果使用的order大于等于zone的内存碎片整理失败最大order值，则将内存碎片整理失败最大order值设置为本次内存碎片整理使用的order值+1。
当内存碎片整理失败时，在轻同步和同步模式下，会对内存碎片整理推迟阀值计数+1，因为计算内存碎片整理推迟量时，是使用1 << zone->compact_defer_shift计算的，所以这个+1，实际上是让原来的推迟量*2。 如上，代码中只有一个地方会让zone重置推迟计数器，就是在内存碎片整理完成后，从此zone中分配到2^order个连续页框，那么就会重置zone->compact_considered和zone->compact_defer_shift为0，但zone->compact_order_failed并不会被重置也永远不会被重置。
六、内存碎片整理扫描起始位置与pageblock的跳过
在系统初始化过程中，就会将zone的可移动页扫描起始位置设置为zone的第一个页框，而空闲页扫描起始位置设置为zone的最后一个页框，这两个数值保存在struct zone中的：
每次对zone进行内存碎片整理，都是使用这两个值初始化本次内存碎片整理的可移动页扫描起始位置和空闲页扫描起始位置。
对于保存可移动页扫描起始位置，同步和异步是分开保存到。这两个值在初始化时会被设置为zone的结束页框和开始页框，之后从内存碎片整理开始到pageblock结束时，都没有隔离出页的情况下，会被更新为pageblock结束页框。
之前说了，内存是以一个一个连续的pageblock组织起来的，当进行内存碎片整理时，一次扫描是以一个pageblock为单位，比如系统正在对zone进行内存碎片整理，首先，会从可移动页框开始位置向后扫描一个pageblock，得到一些可移动页框，然后空闲页框从开始位置向前扫描一个pageblock，得到一些空闲页框，然后将可移动页框移动到空闲页框中，之后再继续循环扫描。对一个pageblock进行扫描后，如果无法从此pageblock隔离出一个要求的页框，这时候就会将此pageblock标记为跳过，主要通过设置pageblock在zone的pageblock位图中的PB_migrate_skip标志实现的。而标记之后会有两种情况：
本次内存碎片整理在之前的pageblock已经隔离出了此种页框(可移动页/空闲页)，这种情况就是设置pageblock的PB_migrate_skip标记。
本次内存碎片整理在之前的pageblock中没有隔离出过此种页框(可移动页/空闲页)，说明之前的pageblock都被标记了跳过，这种情况不止设置pageblock的PB_migrate_skip标记，还会设置对于的内存碎片整理扫描起始位置。
对于第二种情况，以扫描可移动页为例子，本次内存碎片整理可移动页扫描是从zone的第一个页框开始，扫描完一个pageblock后，没有隔离出可移动页框，则标记此pageblock的跳过标记PB_migrate_skip，然后将zone->compact_cached_migrate_pfn设置为此pageblock的结束页框，这样，在下次对此zone进行内存碎片整理时，就会直接从此pageblock的下一个pageblock开始，把此pageblock跳过了。同理，对于空闲页扫描也是一样。如下图：
在贴着扫描起始位置的pageblock被连续标记为跳过时，就会将扫描起始位置设置到这段连续被标记为跳过的pageblock的最后一个一页，而当从pageblock隔离出需要页框时，pageblock就不会被标记为跳过，之后又有pageblock被标记跳过时，就不会修正扫描起始位置了，因为中间有pageblock隔离出了页框。本次整理结束后，如上图，修正了可移动页扫描起始位置和空闲页扫描起始位置，当下一次对此zone进行内存碎片整理时，则从这两个位置开始：
可以看到，再次对此zone进行内存碎片整理时，就会从修正后的扫描起始位置开始，并且扫描过程中会跳过被标记了跳过的pageblock。
如果一直这样，那不是那些被标记为跳过的pageblock在进行内存碎片整理时都会被跳过，然后一直不能够对它们进行扫描？实际上并不是，当进行同步内存碎片整理时，都会设置忽略pageblock的PB_migrate_skip标记，也就是会对跳过的pageblock进行扫描。但是仅仅只有在同步内存碎片整理时才对跳过的pageblock进行扫描也不行，毕竟同步内存碎片整理只是一些特殊情况下才会使用。所以，在一些情况下，内核会将zone的所有pageblock的PB_migrate_skip清除，也就是之后的内存碎片整理扫描，又会从最开始的状态开始进行，
有以下两种情况会发生，如下：
在可移动页扫描和空闲页扫描碰头时，会设置zone->compact_blockskip_flush标志，此标志会导致kswapd准备睡眠时，对此zone的所有pageblock清除PB_migrate_skip
在非kswapd调用中，如果此zone的推迟次数达到最大值时(zone->compact_defer_shift == COMPACT_MAX_DEFER_SHIFT并且zone->compact_considered >= 1UL << zone->compact_defer_shift)导致的内存碎片整理，则清除zone所有pageblock的PB_migrate_skip
第一种情况，这个对zone的所有pageblock的PB_migrate_skip清除的工作是异步的，而第二种情况，则是同步的。
总结来说，就是zone完成了一次完整内存碎片整理(两个扫描相会)和此zone内存碎片整理推迟次数达到最大值这两种情况下，会清除zone所有pageblock的PB_migrate_skip。而清除时，都会将两个扫描起始位置重置为zone的开始页框和结束页框位置。
七、实现代码
先看看内存碎片整理控制结构struct compact_control，当需要进行内存碎片整理时，总是需要初始化一个这个结构:
结构体中每个成员变量的作用都在注释中写明了。
实际上无论唤醒kswapd执行内存碎片整理还是连续页框不足执行内存碎片整理，它们的入口都是alloc_pages()函数，因为kswapd不是间断性自动唤醒，而是在分配页框时页框不足的情况下被主动唤醒，在内存足够的情况下，kswapd是不会被唤醒的，而分配页框的函数入口就是alloc_pages()，会在此函数里面判断页框是否足够。所以从alloc_pages往下跟，可以看到内存碎片整理的代码主要函数是try_to_compact_pages()，在这个函数中，需要传入一个zonelist，然后对zonelist中的每个zone都进行内存碎片整理：
在此函数中，遍历zonlist中的每个zone，对每个zone都进行内存碎片整理处理，在内存碎片整理处理中，第一件首要事情就是判断此zone的内存碎片整理是否需要推迟，不需要推迟可以进行内存碎片整理的两个情况是：
本次内存碎片整理使用的order值小于zone->compact_order_failed。
如果order值大于zone->compact_order_failed，那么对zone的内存碎片整理推迟计数器++，如果zone的内存碎片整理推迟计数器++后数值大于等于了(1 << zone的内存碎片整理最大推迟计数)，那么也会对zone进行内存碎片整理。但是这种情况会清除zone所有pageblock的PB_migrate_skip标志和重置扫描起始位置。
在上述两种情况下，可以对此zone进行内存碎片整理，之后，compact_zone_order()，这个函数里主要初始化一个struct compact_control结构体，然后调用compact_zone()：
这里面又调用了compact_zone()，这个函数里首先会在此判断是否进行内存碎片整理，有三种情况：
COMPACT_PARTICAL: 此zone内存足够用于分配要求的2^order个页框，不用进行内存碎片整理。
COMPACT_SKIPPED: 此zone内存不足以进行内存碎片整理，判断条件是此zone的空闲页框数量少于 zone的低阀值 + (2 << order)。
COMPACT_CONTINUE: 此zone可以进行内存碎片整理。
所以，对一个zone能否进行内存碎片整理有两个判断，一个是是否需要推迟的判断，一个是zone的内存页数量是否满足进行内存碎片整理。
判断完zone能否进行内存碎片整理后，还需要判断是否要重置所有pageblock的PB_migrate_skip和扫描起始位置，只有当不处于kswapd内存碎片整理时，并且zone的内存碎片整理推迟次数超过了最大值的情况下，才会重置。之后会初始化可移动页框扫描和空闲页框扫描的起始位置，这个位置就是使用zone->compact_cached_migrate_pfn和zone->compact_cached_free_pfn决定，需要注意同步和异步的可移动页扫描使用的是不同的位置。之后如上面所说，循环扫描pageblock，对每个pageblock进行可移动页的扫描和空闲页的扫描，将可移动页的数据和页描述符复制到空闲页中，最后就将已经完成移动的可移动页释放掉，如下：
八、隔离可移动页框
每次进行隔离可移动页框是以一个pageblock为单位，也就是从一个pageblock中将可以移动页进行隔离，最多也就只能隔离出一个pageblock中的所有页框，主要实现函数为isolate_migratepages()：
到这里，已经完成了从一个pageblock获取可移动页框，并放入struct compact_control中的migratepages链表中。从之前的代码看，当调用isolate_migratepages()将一个pageblock的可移动页隔离出来之后，会调用到migrate_pages()进行可移动页框的移动，之后就是详细说明此函数。
九、可移动页框的移动
我们先看看migrate_pages()函数原型：
比较重要的两个参数是
new_page_t new: 是一个函数指针，指向获取空闲页框的函数
free_page_t free: 也是一个函数指针，指向释放空闲页框的函数
我们要先看看这两个指针指向的函数，这两个函数指针分别指向compaction_alloc()和compaction_free()，compaction_alloc()是我们主要分析的函数，如下：
代码很简单，主要还是里面的isolate_freepages()函数，在这个函数中，会从cc->free_pfn开始向前扫描空闲页框，但是注意以pageblock向前扫描，但是在pageblock内部是从前向后扫描的，最后遇到cc->migrate_pfn后或者cc->nr_freepages >= cc->nr_migratepages的情况下会停止，如下：
这里结束就是从一个pageblock中获取到了空闲页框，最后会返回在此pageblock中总共获得的空闲页框数量。这里看完了compaction_alloc()中的调用过程，再看看compaction_free()的调用过程，这个函数主要用于当从compaction_alloc()获取一个空闲页框用于移动时，但是因为某些原因失败，就要把这个空闲页框重新放回cc->freepages链表中，实现也很简单：
看完了compaction_alloc()和compaction_free()，现在看最主要的函数migrate_pages()此函数就是用于将隔离出来的可移动页框进行移动到空闲页框中，在里面每进行一个页框的处理前，都会先判断当前进程是否需要调度，然后再进行处理：
大页的情况下有些我暂时还没看懂，这里就先分析常规页的情况，常规页的情况的处理主要是umap_and_move()函数，具体看函数实现吧，如下：
这里面，调用传入的compaction_alloc()函数获取扫描到的空闲页框中的一个页框，之后最重要的就是会调用__unmap_and_move()函数进行将page的页描述符数据和页内数据移动到new_page上，调用结束，如果迁移成功了，则会将旧页释放到伙伴系统中的每CPU页高速缓存中。
十、触发内存页迁移
注意区分内存页迁移和内存碎片整理，内存页迁移是将内存页数据copy到另一个内存页的方法（同时保证内存页属性不变，映射到此内存页的进程也会映射到新的内存页），内存页迁移是可以跨zone和node的。 而内存碎片整理是使用的内存页迁移的方式进行的，它只会在当前zone中执行。 在内核中，以下行为会触发内存页面迁移
CMA：CMA（Contiguous Memory Allocator）内存区域是kernel用于预留给设备做dma使用的，因为有一些设备在做DMA时，必须需要连续足够长的物理内存，所以kernel支持在启动阶段设置CMA区域的长度。但是系统会在CMA区域的内存在没有被设备使用时，将其当做MIGRATE_MOVEABLE分配出去（也必须保证一定是MOVEABLE的），当内核模块调用dma_alloc_coherent()需要更多的CMA内存时，就会对已经分配出去的page做内存迁移操作，将这段物理内存释放回CMA区域。
/proc/sys/vm/compact_memory：这个文件允许用户主动去做内存碎片整理的，可以通过echo 1主动让kernel进行内存碎片整理。
alloc_page：就是当连续内存不足时，就会触发内存迁移。
设置transparent hugepage可用数量：transparent hugepage中文是透明大页，意思是用户不需要显式地告诉kernel，程序需要使用大页，而是程序能够自己向kernel申请到大页。mmap()+MAP_HUGEPAGE这个flag。不过前提是用户需要提前先设置好系统中可供使用的大页数量，echo <nums> > /sys/kernel/mm/hugepages/hugepages-<size>/nr_hugepages。在用户这样设置的过程中，就会可能进行页迁移。
