memory compaction原理、实现与分析

一

memory compaction简介

随着系统的运行，经过不同用户的分配请求后，页框会变得十分分散，导致此段页框被这些正在使用的零散页框分为一小段一小段非连续页框，这使得在需要分配内存时很难找到物理上连续的页框。

现代处理器不再限于使用传统的4K大小的页框；它们可以在进程的部分地址空间中支持大得多的页(huge pages)。使用巨页会带来真正的性能优势，主要原因是减小了对处理器的转换后备缓冲区（translation lookaside buffer）的压力。但是使用巨页要求系统能够找到物理上连续的内存区域，这些区域不仅要足够大，而且还必须确保按适当方式满足字节对齐的要求。

在一个已经运行了一段时间的系统上会产生大量的不连续的page， 要想找到符合这些高阶(high-order)条件的内存空间非常具有挑战性，memory compaction的作用就是解决high-order内存分配失败问题，与buddy system机制做一个互补。

二

memory compaction原理

内存碎片整理以pageblock为单位。
在内存碎片整理开始前，会在zone的头和尾各设置一个指针，头指针从头向尾扫描可移动的页，而尾指针从尾向头扫描空闲的页，当他们相遇时终止整理。

简单示意图：需要明确的是：实际情况并不是与图示的情况完全一致。头指针每次扫描一个符合要求的pageblock里的所有页框，当pageblock不为MIGRATE_MOVABLE、MIGRATE_CMA、MIGRATE_RECLAIMABLE时会跳过这些pageblock，当扫描完这个pageblock后有可移动的页框时，会变为尾指针以pageblock为单位向前扫描可移动页框数量的空闲页框，但是在pageblock中也是从开始页框向结束页框进行扫描，最后会将前面的页框内容复制到这些空闲页框中。

这里的移动是将页框中的数据copy拷贝到可移动的空闲页框当中，此时原有的movable page变成free page。所以并不是页框自身的移动而是数据的移动。

通过下图的操作就可以分配出一个order = 2或者是order =  3的连续的可用空间，可用于满足更high-order的内存分配。当然，这里展示的流程和真实系统比起来已经大大简化了。实际的内存域会大得多，这意味着扫描的工作量也会大很多，但由此获得的空闲区也可能更大。

比如系统正在对zone进行内存碎片整理，首先，会从可移动页框开始位置向后扫描一个pageblock，得到一些可移动页框，然后空闲页框从开始位置向前扫描一个pageblock，得到一些空闲页框，然后将可移动页框移动到空闲页框中，之后再继续循环扫描。对一个pageblock进行扫描后，如果无法从此pageblock隔离出一个要求的页框，这时候就会将此pageblock标记为跳过(skip)。

假设内存碎片整理可移动页扫描是从zone的第一个页框开始，扫描完一个pageblock后，没有隔离出可移动页框，则标记此pageblock的跳过标记PB_migrate_skip，然后将zone->compact_cached_migrate_pfn设置为此pageblock的结束页框。
这样，在下次对此zone进行内存碎片整理时，就会直接从此pageblock的下一个pageblock开始，把此pageblock跳过了。同理，对于空闲页扫描也是一样。这样就必须更新zone pageblock的起始地址与结束地址：

以上就是内存碎片整理的基本原理了。

三

memory compaction如何实现

3.1、数据结构

在内存碎片整理中，可以移动的页框有MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE与MIGRATE_CMA这三种类型的页框。

而因为内存碎片整理分为同步和异步。在异步过程中，只会移动MIGRATE_MOVABLE和MIGRATE_CMA这两种类型的页框。因为这两种类型的页框处理，是不会涉及到IO操作的。而在同步过程中，这三种类型的页框都会进行移动，因为MIGRATE_RECLAIMABLE基本上都是文件页，在移动过程中，有可能要将脏页回写，会涉及到IO操作，也就是在同步过程中，是会涉及到IO操作的。

1、migrate_mode迁移模式：

enum migrate_mode { MIGRATE_ASYNC, MIGRATE_SYNC_LIGHT, MIGRATE_SYNC,};
2、compact_priority

enum compact_priority { COMPACT_PRIO_SYNC_FULL, MIN_COMPACT_PRIORITY = COMPACT_PRIO_SYNC_FULL, COMPACT_PRIO_SYNC_LIGHT, MIN_COMPACT_COSTLY_PRIORITY = COMPACT_PRIO_SYNC_LIGHT, DEF_COMPACT_PRIORITY = COMPACT_PRIO_SYNC_LIGHT, COMPACT_PRIO_ASYNC, INIT_COMPACT_PRIORITY = COMPACT_PRIO_ASYNC};
3、compact_result用于压缩处理函数的返回值

enum compact_result { /* For more detailed tracepoint output - internal to compaction */ COMPACT_NOT_SUITABLE_ZONE,//trace用于调试输出或内部使用 /* * compaction didn't start as it was not possible or direct reclaim * was more suitable */ COMPACT_SKIPPED,//跳过压缩，因为无法执行压缩或直接回收更合适 /* compaction didn't start as it was deferred due to past failures */ COMPACT_DEFERRED,
/* compaction not active last round */ COMPACT_INACTIVE = COMPACT_DEFERRED,
/* For more detailed tracepoint output - internal to compaction */ COMPACT_NO_SUITABLE_PAGE, /* compaction should continue to another pageblock */ COMPACT_CONTINUE,
/* * The full zone was compacted scanned but wasn't successfull to compact * suitable pages. */ COMPACT_COMPLETE,//已完成所有区域的压缩，但是尚未确保可以通过压缩分配的页面 /* * direct compaction has scanned part of the zone but wasn't successfull * to compact suitable pages. */ COMPACT_PARTIAL_SKIPPED,
/* compaction terminated prematurely due to lock contentions */ COMPACT_CONTENDED,
/* * direct compaction terminated after concluding that the allocation * should now succeed */ COMPACT_SUCCESS,//在确保可分配页面安全后，直接压缩结束};

4、compact_control需要进行内存碎片整理时，总是需要初始化该结构体

struct compact_control { /* 扫描到的空闲页的页的链表 */ struct list_head freepages; /* List of free pages to migrate to */ /* 扫描到的可移动的页的链表 */ struct list_head migratepages; /* List of pages being migrated */ /* 空闲页链表中的页数量 */ unsigned long nr_freepages; /* Number of isolated free pages */ /* 可移动页链表中的页数量 */ unsigned long nr_migratepages; /* Number of pages to migrate */ /* 空闲页框扫描所在页框号 */ unsigned long free_pfn; /* isolate_freepages search base */ /* 可移动页框扫描所在页框号 */ unsigned long migrate_pfn; /* isolate_migratepages search base */ /* 内存碎片整理使用的模式: 同步，轻同步，异步 */ enum migrate_mode mode; /* Async or sync migration mode */ /* 是否忽略pageblock的PB_migrate_skip标志对需要跳过的pageblock进行扫描 ，并且也不会对pageblock设置跳过 * 只有两种情况会使用 * 1.调用alloc_contig_range()尝试分配一段指定了开始页框号和结束页框号的连续页框时； * 2.通过写入1到sysfs中的/vm/compact_memory文件手动实现同步内存碎片整理。 */ bool ignore_skip_hint; /* Scan blocks even if marked skip */ /* 本次内存碎片整理是否隔离到了空闲页框，会影响zone的空闲页扫描起始位置 */ bool finished_update_free; /* True when the zone cached pfns are * no longer being updated */ /* 本次内存碎片整理是否隔离到了可移动页框，会影响zone的可移动页扫描起始位置 */ bool finished_update_migrate; /* 申请内存时需要的页框的order值 */ int order; /* order a direct compactor needs */ const gfp_t gfp_mask; /* gfp mask of a direct compactor */ /* 扫描的管理区 */ struct zone *zone; /* 保存结果，比如异步模式下是否因为需要阻塞而结束了本次内存碎片整理 */ int contended; /* Signal need_sched() or lock * contention detected during * compaction */};

5、Node zone 扫描推迟

struct zone{ ..... unsigned int compact_considered; unsigned int compact_defer_shift; int compact_order_failed; ......} 当一个zone要进行内存碎片整理时，首先会判断本次整理需不需要推迟，如果本次内存碎片整理使用的order值小于zone内存碎片整理失败最大order值compact_order_failed时，不用进行推迟，可以直接进行内存碎片整理；
当order值大于zone内存碎片整理失败最大order值compact_order_failed，会增加内存碎片整理推迟计数器compact_considered，如果内存碎片整理推迟计数器compact_considered未达到内存碎片整理推迟阀值defer_limit，则会跳过本次内存碎片整理，如果达到了，那就需要进行内存碎片整理。

总结：也就是当order小于zone内存碎片整理失败最大order值时，不用进行推迟，而order大于zone内存碎片整理失败最大order值时，才考虑是否进行推迟,此时推迟就是continue扫描node当中的下一个zone区域，这里并不是想下文一下设置zone SKIP标志。
6、Pageblock skip

3.2、源码分析

• 内存分配不足时触发direct compact整理内存
  
• Kswapd内存回收后唤醒kcompactd内核线程执行compact操作，获取连续内存
  

• 手动设置echo 1 > /proc/sys/vm/compact_memory
  
  
  

重点分析5个关键函数：

1、compaction_suitable

/* 判断该zone是否可以做内存碎片压缩整理 */enum compact_result compaction_suitable(struct zone *zone, int order, unsigned int alloc_flags, int classzone_idx){ enum compact_result ret; int fragindex; /* * 根据watermask判断zone中离散的page是否满足2^order的内存分配请求，如果满足则继续对zone进行内存的compact整理zone的内存碎片 * 说明该zone时可以做内存碎片的压缩整理的。 */ ret = __compaction_suitable(zone, order, alloc_flags, classzone_idx,zone_page_state(zone, NR_FREE_PAGES));
/* 如果return返回值为COMPACT_CONTINUE，且order > PAGE_ALLOC_COSTLY_ORDER(3)则进入一下判断当中 */ if (ret == COMPACT_CONTINUE