伙伴分配器
3-根据可移动性分组
在系统长时间运行后，物理内存可能出现很多碎片，可用物理页很多，但是最大的连续物理内存可能只有一页。
内存碎片对用户程序不是问题，因为用户程序可以通过页表把连续的虚拟页映射到不连续的物理页。
**但是内存碎片对内核是一个问题，因为内核使用直接映射的虚拟地址空间，连续的虚拟页必须映射到连续的物理页。**内存碎片是伙伴分配器的一个弱点。
为了预防内存碎片，内核根据可移动性把物理页分为3种类型。
- （1）不可移动页：位置必须固定，不能移动，直接映射到内核虚拟地址空间的页属于这一类。
- （2）可移动页：使用页表映射的页属于这一类，可以移动到其他位置，然后修改页表映射。
- （3）可回收页：不能移动，但可以回收，需要数据的时候可以重新从数据源获取。后备存储设备支持的页属于这一类。
内核把具有相同可移动性的页分组。为什么这种方法可以减少碎片？
- 试想：如果不可移动页出现在可移动内存区域的中间，会阻止可移动内存区域合并。这种方法把不可移动页聚集在一起，可以防止不可移动页出现在可移动内存区域的中间。
内核定义了以下迁移类型：
include/linux/mmzone.h enum migratetype { MIGRATE_UNMOVABLE, /* 不可移动 */ MIGRATE_MOVABLE, /* 可移动 */ MIGRATE_RECLAIMABLE, /* 可回收 */ MIGRATE_PCPTYPES, /* 定义内存区域的每处理器页集合中链表的数量 */ MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, /* 高阶原子分配，即阶数大于0，并且分配页时不能睡眠等待 */ #ifdef CONFIG_CMA MIGRATE_CMA, /* 连续内存分配器 */ #endif #ifdef CONFIG_MEMORY_ISOLATION MIGRATE_ISOLATE, /* 隔离，不能从这里分配 */ #endif MIGRATE_TYPES };
前面3种是真正的迁移类型，后面的迁移类型都有特殊用途：
- MIGRATE_HIGHATOMIC用于高阶原子分配（参考3.7.5节的“对高阶原子分配的优化处理”）,
- MIGRATE_CMA用于连续内存分配器（参考3.20节）,
- MIGRATE_ISOLATE用来隔离物理页（由连续内存分配器、内存热插拔和从内存硬件错误恢复等功能使用）。
对伙伴分配器的数据结构的主要调整是把空闲链表拆分成每种迁移类型一条空闲链表。
include/linux/mmzone.h struct free_area { struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free; };
只有当物理内存足够大且每种迁移类型有足够多的物理页时，根据可移动性分组才有意义。全局变量page_group_by_mobility_disabled表示是否禁用根据可移动性分组。
- vm_total_pages是所有内存区域里面高水线以上的物理页总数，
- pageblock_order是按可移动性分组的阶数，
- pageblock_nr_pages是pageblock_order对应的页数。
如果所有内存区域里面高水线以上的物理页总数小于（pageblock_nr_pages * 迁移类型数量），那么禁用根据可移动性分组。
mm/page_alloc.c void __ref build_all_zonelists(pg_data_t *pgdat, struct zone *zone) { … if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES)) page_group_by_mobility_disabled = 1; else page_group_by_mobility_disabled = 0; … }
pageblock_order是按可移动性分组的阶数，简称分组阶数，可以理解为一种迁移类型的一个页块的最小长度。
如果内核支持巨型页，那么pageblock_order是巨型页的阶数，否则pageblock_order是伙伴分配器的最大分配阶。
include/linux/pageblock-flags.h #ifdef CONFIG_HUGETLB_PAGE #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE /* 巨型页长度是可变的 */ extern unsigned int pageblock_order; #else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */ /* 巨型页长度是固定的 */ #define pageblock_order HUGETLB_PAGE_ORDER #endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */ #else /* CONFIG_HUGETLB_PAGE */ /* 如果编译内核时没有开启巨型页，按伙伴分配器的最大分配阶分组 */ #define pageblock_order (MAX_ORDER-1) #endif /* CONFIG_HUGETLB_PAGE */ #define pageblock_nr_pages (1UL << pageblock_order)
申请页时，可以使用标志__GFP_MOVABLE指定申请可移动页，使用标志__GFP_RECLAIMABLE指定申请可回收页，如果没有指定这两个标志，表示申请不可移动页。函数gfpflags_to_migratetype用来把分配标志转换成迁移类型：
include/linux/gfp.h /* 把分配标志转换成迁移类型 */ #define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE) #define GFP_MOVABLE_SHIFT 3 static inline int gfpflags_to_migratetype(const gfp_t gfp_flags) { … if (unlikely(page_group_by_mobility_disabled)) return MIGRATE_UNMOVABLE; /* 根据可移动性分组 */ return (gfp_flags & GFP_MOVABLE_MASK) >> GFP_MOVABLE_SHIFT; }
如果禁用根据可移动性分组，那么总是申请不可移动页。
申请某种迁移类型的页时，如果这种迁移类型的页用完了，可以从其他迁移类型盗用（steal）物理页。内核定义了每种迁移类型的备用类型优先级列表：
mm/page_alloc.c static int fallbacks[MIGRATE_TYPES][4] = { [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_TYPES }, [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_TYPES }, [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES }, #ifdef CONFIG_CMA [MIGRATE_CMA] = { MIGRATE_TYPES }, /* 从不使用 */ #endif #ifdef CONFIG_MEMORY_ISOLATION [MIGRATE_ISOLATE] = { MIGRATE_TYPES }, /* 从不使用 */ #endif };
- 不可移动类型的备用类型按优先级从高到低是：可回收类型和可移动类型。
- 可回收类型的备用类型按优先级从高到低是：不可移动类型和可移动类型。
- 可移动类型的备用类型按优先级从高到低是：可回收类型和不可移动类型。
- 如果需要从备用类型盗用物理页，那么从最大的页块开始盗用，以避免产生碎片。
mm/page_alloc.c static inline bool __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype) { … /* 在备用类型的页块链表中查找最大的页块 */ for (current_order = MAX_ORDER-1; current_order >= order && current_order <= MAX_ORDER-1; --current_order) { area = &(zone->free_area[current_order]); fallback_mt = find_suitable_fallback(area, current_order, start_migratetype, false, &can_steal); … } … }
释放物理页的时候，需要把物理页插入物理页所属迁移类型的空闲链表，内核怎么知道物理页的迁移类型？内存区域的zone结构体的成员pageblock_flags指向页块标志位图，页块的大小是分组阶数pageblock_order，我们把这种页块称为分组页块。
include/linux/mmzone.h struct zone { … #ifndef CONFIG_SPARSEMEM /* * 分组页块的标志参考文件pageblock-flags.h。 * 如果使用稀疏内存模型，这个位图在结构体mem_section中。 */ unsigned long *pageblock_flags; #endif /* CONFIG_SPARSEMEM */ … } ____cacheline_internodealigned_in_smp;
每个分组页块在位图中占用4位，其中3位用来存放页块的迁移类型。
include/linux/pageblock-flags.h /* 影响一个页块的位索引 */ enum pageblock_bits { PB_migrate, PB_migrate_end = PB_migrate + 3 - 1, /* 迁移类型需要3位 */ PB_migrate_skip, /* 如果被设置，内存碎片整理跳过这个页块。*/ NR_PAGEBLOCK_BITS };
函数set_pageblock_migratetype()用来在页块标志位图中设置页块的迁移类型，函数get_pageblock_migratetype()用来获取页块的迁移类型。
内核在初始化时，把所有页块初始化为可移动类型，其他迁移类型的页是盗用产生的。
mm/page_alloc.c free_area_init_core() -> free_area_init_core() -> memmap_init() -> memmap_init_zone() void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone, unsigned long start_pfn, enum memmap_context context) { … for (pfn = start_pfn; pfn < end_pfn; pfn++) { … if (! (pfn & (pageblock_nr_pages - 1))) { /* 如果是分组页块的第一页 */ struct page *page = pfn_to_page(pfn); __init_single_page(page, pfn, zone, nid); set_pageblock_migratetype(page, MIGRATE_MOVABLE); } else { __init_single_pfn(pfn, zone, nid); } } }
可以通过文件“/proc/pagetypeinfo”查看各种迁移类型的页的分布情况。
参考来自前辈的书籍：《Linux内核深度解析》
