封面图加载中

[linux内存管理] 第018篇 buddy系统的简介以及初始化

0. 前言 在[linux内存管理] 第013篇 zone的初始化一文中简单剖析了 zone 的初始化流程，也是继 arm64_memblock_init 和 sparse_init 之后有一个内存管理层，而zone 这一层管理层中，所有的物理内存都会被添加到zone 中的成员变量 free_are
  • 本文作者
  • 文章发布日期 2025-01-06 07:31
  • 热度 7
  • 本文共计
  • 预计阅读

0. 前言

在[linux内存管理] 第013篇 zone的初始化一文中简单剖析了 zone 的初始化流程，也是继 arm64_memblock_init 和 sparse_init 之后有一个内存管理层，而zone 这一层管理层中，所有的物理内存都会被添加到zone 中的成员变量 free_area 数组 管理，而它就是buddy 系统管理的核心数据结构。
那什么是伙伴系统呢？(buddy)

伙伴系统基于一种相对简单然而令人吃惊的强大算法.

Linux内核使用二进制伙伴算法来管理和分配物理内存页面, 该算法由Knowlton设计, 后来Knuth又进行了更深刻的描述.

伙伴系统是一个结合了2的方幂个分配器和空闲缓冲区合并计技术的内存分配方案, 其基本思想很简单. 内存被分成含有很多页面的大块, 每一块都是2个页面大小的方幂. 如果找不到想要的块, 一个大块会被分成两部分, 这两部分彼此就成为伙伴. 其中一半被用来分配, 而另一半则空闲. 这些块在以后分配的过程中会继续被二分直至产生一个所需大小的块. 当一个块被最终释放时, 其伙伴将被检测出来, 如果伙伴也空闲则合并两者.

  • 内核如何记住哪些内存块是空闲的
  • 分配空闲页面的方法
  • 影响分配器行为的众多标识位
  • 内存碎片的问题和分配器如何处理碎片

在buddy 系统中， 内存块（page block） 的大小是2 的 order 次幂个pages。 Linux 内核中 order 的最大值用 MAX_ORDER 来 表示，通常是 11 ，也就是最大的物理内存块可以达到 2^{10} pages （4MB） 。

zone 中的 free_area 数组分别管理 2^{0} ~ 2^{10} 的内存块，而每个内存块又根据迁移属性，存放在对应属性的链表中。

本文将该数据结构单独拉出来进行分析，并通过其剖析buddy 系统的管理原理。

1. 数据结构

1.1 struct free_area

系统内存中的每个物理内存页（页帧），都对应于一个struct page实例, 每个内存域都关联了一个struct zone的实例，其中保存了用于管理伙伴数据的主要数数组。

struct zone {
    //...
    struct free_area	free_area[MAX_ORDER];   ///伙伴系统所需的核心数据结构，管理空闲页块(page block)链表的数组

}

struct free_area {
	struct list_head	free_list[MIGRATE_TYPES];  //用于连接空闲页的链表. 页链表包含大小相同的连续内存区
	unsigned long		nr_free;    // 指定了当前内存区中空闲页块的数目
};

zone 的数据结构中有一个 free_area 数据结构，数据结构的大小是MAX_ORDER，根据 CONFIG_FORCE_MAX_ZONEORDER 来确定，如果没有使能该CONFIG，则默认为11。即buddy 算法管理 order 0 ~ 10 ( 2^{0} ~ 2^{10} pages) ，每一个order 都会有一个free_list 对应，而该free_list 管理的是 migrate，每个free_list 有 MIGRATE_TYPES 个链表。

1.1.1 migratetype

/*
 * MIGRATE_UNMOVABLE: 无法移动和检索的类型，用于内核分配的页面、I/O缓冲区、内核堆栈等
 * MIGRATE_MOVABLE:   当需要大的内存时，通过移动当前使用的页面来尽可能防止碎片，用于分配用户内存
 * MIGRATE_RECLAIMABLE:当没有可用内存时使用此类型
 * MIGRATE_PCPTYPES:  per_cpu_pageset, 每CPU页框高速缓存的数据结构中的链表的迁移类型数目
 * MIGRATE_HIGHATOMIC: 减少原子分配请求无法进行高阶页面分配的可能，内核会提前准备一个页面块
 * MIGRATE_CMA:       页面类型由CMA 内存分配器单独管理
 * MIGRATE_ISOLATE:   用于跨越numa节点移动的物理内存页，在大型系统上有益于将物理内存页移动到接近于使用该页最频繁的CPU.
 * MIGRATE_TYPES:     移类型的数目
 **/
enum migratetype {
	MIGRATE_UNMOVABLE,
	MIGRATE_MOVABLE,
	MIGRATE_RECLAIMABLE,
	MIGRATE_PCPTYPES,	/* the number of types on the pcp lists */
	MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, 
#ifdef CONFIG_CMA
	MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	MIGRATE_ISOLATE,	/* can't allocate from here */
#endif
	MIGRATE_TYPES
};

1.1.2 __GFP区域请求标志

在内存的时候，最低有个 4 个标志位用来指定首选的内存区域，在加上一个CMA 区域：

#define __GFP_DMA	((__force gfp_t)___GFP_DMA)
#define __GFP_HIGHMEM	((__force gfp_t)___GFP_HIGHMEM)
#define __GFP_DMA32	((__force gfp_t)___GFP_DMA32)
#define __GFP_MOVABLE	((__force gfp_t)___GFP_MOVABLE)  /* ZONE_MOVABLE allowed */
#define __GFP_CMA	((__force gfp_t)___GFP_CMA)
#define GFP_ZONEMASK	(__GFP_DMA|__GFP_HIGHMEM|__GFP_DMA32|__GFP_MOVABLE)
  • __GFP_DMA ：从 ZONE_DMA 中分配内存；
  • __GFP_HIGHMEM ：优先从 ZONE_HIGHMEM 中分配内存；
  • __GFP_DMA32 ：从 ZONE_DMA32 中分配内存；
  • __GFP_MOVABLE ：页面可以被迁移或者回收，如用于内存规整机制；
  • __GFP_CMA ：用以CMA 分配器申请时使用；
    当然，这些只是管理区请求的修饰符，还有移动修饰符，水位修饰符，页面回收修饰符，行为修饰符等等。

1.2 fallbacks

/* 伙伴系统分配连续内存时，当指定迁移类型所对应的链表中没有空闲内存时，
 * 内核将会按照静态定义的顺序，从其他迁移类型链表中寻找
 * 比如MIGRATE_UNMOVABLE 分配失败，可以从
 * { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
 * steal内存
 */
static int fallbacks[MIGRATE_TYPES][3] = {
	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
#ifdef CONFIG_CMA
	[MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	[MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
#endif
};

此前已经出现过一个类似的问题, 即特定的NUMA内存域无法满足分配请求时. 我们需要从其他内存域中选择一个代价最低的内存域完成内存的分配, 因此内核在内存的结点pg_data_t中提供了一个备用内存域列表zonelists.

内核在内存迁移的过程中处理这种情况下的做法是类似的. 提供了一个备用列表fallbacks, 规定了在指定列表中无法满足分配请求时. 接下来应使用哪一种迁移类型

1.3 pageblock_order

#ifdef CONFIG_HUGETLB_PAGE
#define pageblock_order		HUGETLB_PAGE_ORDER
#else
#define pageblock_order		(MAX_ORDER-1)
#endif /* CONFIG_HUGETLB_PAGE */
 
#define pageblock_nr_pages	(1UL << pageblock_order)

对于巨型页的架构体系，pageblock_order 取值与 HUGETLB_PAGE_ORDER，由内核配置。

非巨型页的架构体系，pageblock_order 为 MAX_ORDER -1

对于zone 的扫描都是以pageblock 为单位，通过pageblock_order 指定每个pageblock 拥有的pages 数量，例如MAX_ORDER 为11 时，pageblock_order 为10，pageblock_nr_pages 为1024。

2. mm_init

我们通过前面几篇博文了解到了memblock的初始化 、 SPARSEMEM的初始化 、 zone的初始化 ，进行了内存管理的初始化流程，而经过 bootmem管理、 paging_init 的内核内存映射、 sparse模型创建、zone数据结构和buddy数据结构初始化完成后，start_kernel()会调用 mm_init()函数对内存进行最后的初始化工作，将内存管理从bootmem移交到buddy系统和LRU。

asmlinkage __visible void __init __no_sanitize_address start_kernel(void)
{
    //...
    setup_arch(&command_line);  ///建立固定映射,包括dtb文件映射，IO设备映射
    //...
    //设置node中所有zone的,初始化伙伴系统的相关数据结构
	build_all_zonelists(NULL);
    //...
    //将memblock管理的内存，释放到伙伴系统中去
	mm_init();
    //...
}

static void __init mm_init(void)
{
	/*
	 * page_ext requires contiguous pages,
	 * bigger than MAX_ORDER unless SPARSEMEM.
	 */
	page_ext_init_flatmem();
	init_mem_debugging_and_hardening();
	kfence_alloc_pool();
	report_meminit();
	stack_depot_init();
	mem_init(); //初始化物理内存，加入伙伴系统
	mem_init_print_info();
	/* page_owner must be initialized after buddy is ready */
	page_ext_init_flatmem_late();
	kmem_cache_init();
	kmemleak_init();
	pgtable_init();
	debug_objects_mem_init();
	vmalloc_init();
	/* Should be run before the first non-init thread is created */
	init_espfix_bsp();
	/* Should be run after espfix64 is set up. */
	pti_init();
}

buddy 系统的初始化工作是在 mem_init() 函数中完成，本文也将重点剖析 mem_init() 函数。
mem_init() 函数用来 free memblock，以及free areas最后的初始化工作，而mem_init() 中最重要的非 memblock_free_all() 函数莫属了。

// arch/arm64/mm/init.c
void __init mem_init(void)
{
	if (swiotlb_force == SWIOTLB_FORCE ||
	    max_pfn > PFN_DOWN(arm64_dma_phys_limit))
		swiotlb_init(1);
	else if (!xen_swiotlb_detect())
		swiotlb_force = SWIOTLB_NO_FORCE;

	set_max_mapnr(max_pfn - PHYS_PFN_OFFSET);

	/* this will put all unused low memory onto the freelists */
	memblock_free_all();  //所有未使用页面，都加入伙伴系统的freelists
/*
 * 打印内存布局
 */
	#define MLK(b, t) b, t, ((t) - (b)) >> 10
#define MLM(b, t) b, t, ((t) - (b)) >> 20
#define MLG(b, t) b, t, ((t) - (b)) >> 30
#define MLK_ROUNDUP(b, t) b, t, DIV_ROUND_UP(((t) - (b)), SZ_1K)

	pr_notice("------Virtual kernel memory layout:\n");
#ifdef CONFIG_KASAN
	pr_notice("    kasan   : 0x%16lx - 0x%16lx   (%6ld GB)\n",
		MLG(KASAN_SHADOW_START, KASAN_SHADOW_END));
#endif
	pr_notice("    modules : 0x%16lx - 0x%16lx   (%6ld MB)\n",
		MLM(MODULES_VADDR, MODULES_END));
	pr_notice("    vmalloc : 0x%16lx - 0x%16lx   (%6ld GB)\n",
		MLG(VMALLOC_START, VMALLOC_END));
	pr_notice("      .text : 0x%16llx" " - 0x%16llx" "   (%6lld KB)\n",
		MLK_ROUNDUP((u64)_text, (u64)_etext));
	pr_notice("      .init : 0x%16llx" " - 0x%16llx" "   (%6lld KB)\n",
		MLK_ROUNDUP((u64)__init_begin, (u64)__init_end));
	pr_notice("    .rodata : 0x%16llx" " - 0x%16llx" "   (%6lld KB)\n",
		MLK_ROUNDUP((u64)__start_rodata, (u64)__end_rodata));
	pr_notice("      .data : 0x%16llx" " - 0x%16llx" "   (%6lld KB)\n",
		MLK_ROUNDUP((u64)_sdata, (u64)_edata));
	pr_notice("       .bss : 0x%16llx" " - 0x%16llx" "   (%6lld KB)\n",
		MLK_ROUNDUP((u64)__bss_start, (u64)__bss_stop));
	pr_notice("    fixed   : 0x%16lx - 0x%16lx   (%6ld KB)\n",
		MLK(FIXADDR_START, FIXADDR_TOP));
	pr_notice("    PCI I/O : 0x%16lx - 0x%16lx   (%6ld MB)\n",
		MLM(PCI_IO_START, PCI_IO_END));
#ifdef CONFIG_SPARSEMEM_VMEMMAP
	pr_notice("    vmemmap : 0x%16lx - 0x%16lx   (%6ld GB maximum)\n",
		MLG(VMEMMAP_START, VMEMMAP_START + VMEMMAP_SIZE));
	pr_notice("              0x%16lx - 0x%16lx   (%6ld MB actual)\n",
		MLM((unsigned long)phys_to_page(memblock_start_of_DRAM()),
		    (unsigned long)virt_to_page(high_memory)));
#endif
	pr_notice("    memory  : 0x%16lx - 0x%16lx   (%6ld MB)\n",
		MLM(__phys_to_virt(memblock_start_of_DRAM()),
		    (unsigned long)high_memory));
	pr_notice("    PAGE_OFFSET  : 0x%16lx\n",
		PAGE_OFFSET);
	pr_notice("    _stext : 0x%16llx\n", _stext);
	pr_notice("    PHYS_OFFSET  : 0x%llx\n", PHYS_OFFSET);
	pr_notice("    start memory  : 0x%llx\n",
		memblock_start_of_DRAM());

	pr_notice("      .idmap_text : 0x%16llx" " - 0x%16llx" "	 (%6lld KB)\n",
		MLK_ROUNDUP((u64)__idmap_text_start, (u64)__idmap_text_end));
	pr_notice("---idmap_pg_dir : 0x%16llx\n", idmap_pg_dir);
	pr_notice("---swapper_pg_dir : 0x%16llx\n", swapper_pg_dir);
#undef MLK
#undef MLM
#undef MLK_ROUNDUP


	/*
	 * Check boundaries twice: Some fundamental inconsistencies can be
	 * detected at build time already.
	 */
#ifdef CONFIG_COMPAT
	BUILD_BUG_ON(TASK_SIZE_32 > DEFAULT_MAP_WINDOW_64);
#endif

	/*
	 * Selected page table levels should match when derived from
	 * scratch using the virtual address range and page size.
	 */
	BUILD_BUG_ON(ARM64_HW_PGTABLE_LEVELS(CONFIG_ARM64_VA_BITS) !=
		     CONFIG_PGTABLE_LEVELS);

	if (PAGE_SIZE >= 16384 && get_num_physpages() <= 128) {
		extern int sysctl_overcommit_memory;
		/*
		 * On a machine this small we won't get anywhere without
		 * overcommit, so turn it on by default.
		 */
		sysctl_overcommit_memory = OVERCOMMIT_ALWAYS;
	}
}

2.1 memblock_free_all

 ///释放所有物理页，加入伙伴系统
void __init memblock_free_all(void)
{
	unsigned long pages;

	free_unused_memmap();
	reset_all_zones_managed_pages();

    ///page加入伙伴系统
	pages = free_low_memory_core_early();
	totalram_pages_add(pages);
}

该函数共做了四件事情：

  • free_unused_memmap(): 受CONFIG_SPARSEMEM_VMEMMAP控制，释放没有使用的memmap内存
  • reset_all_zones_managed_pages(): 重置每个zone的managed_pages，因为之前zone初始化一文中得到的managed_pages只是粗略值；
  • free_low_memory_core_early(): 函数对所有内存页面进行初始化，并将内存块放置到合适的order下的链表中，返回值为被管理的总页数；
  • totalram_pages_add(): 将管理的总页数记录到原子变量_totalram_pages 中，调用该函数的还可能出现在hotplug或CMA内存归还到buddy时；

2.2 reset_all_zones_managed_pages

void reset_node_managed_pages(pg_data_t *pgdat)
{
	struct zone *z;

    //遍历node的所有zone
	for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++)
        //重置所有zone的managed_pages为0
		atomic_long_set(&z->managed_pages, 0);
}

void __init reset_all_zones_managed_pages(void)
{
	struct pglist_data *pgdat;

	if (reset_managed_pages_done)
		return;
    
    // 遍历node
	for_each_online_pgdat(pgdat)
		reset_node_managed_pages(pgdat);

	reset_managed_pages_done = 1;
}

2.3 free_low_memory_core_early

static unsigned long __init free_low_memory_core_early(void)
{
	unsigned long count = 0;
	phys_addr_t start, end;
	u64 i;

	// 清除memblock中的热插拔内存区间
	memblock_clear_hotplug(0, -1);
	//初始化保留区内存，避免释放保留区
	memmap_init_reserved_pages();

	/*
	 * We need to use NUMA_NO_NODE instead of NODE_DATA(0)->node_id
	 *  because in some case like Node0 doesn't have RAM installed
	 *  low ram will be on Node1
	 */
	// 遍历memblock中所有空闲的内存区间
	for_each_free_mem_range(i, NUMA_NO_NODE, MEMBLOCK_NONE, &start, &end,
				NULL)
		count += __free_memory_core(start, end);  ///加入伙伴系统

	return count;
}

2.3.1 memmap_init_reserved_pages

static void __init memmap_init_reserved_pages(void)
{
	struct memblock_region *region;
	phys_addr_t start, end;
	u64 i;

	/* initialize struct pages for the reserved regions */
	// 遍历memblock中的reserved内存区域
	for_each_reserved_mem_range(i, &start, &end)
		//初始化保留区
		reserve_bootmem_region(start, end);

	/* and also treat struct pages for the NOMAP regions as PageReserved */
	// 遍历所有的memblock区域
	for_each_mem_region(region) {
		// 如果内存区间为NOMAP类型
		if (memblock_is_nomap(region)) {
			start = region->base;
			end = start + region->size;
			//也初始化并标记
			reserve_bootmem_region(start, end);
		}
	}
}

首先，遍历所有的 memblock.reserved regions，将 regions 下所有的page 标记为 PageReserved ，初始化所有 reserved pages 的 lru；

接着，遍历所有的内存节点，将 regions 中计算出合适的 start、end 带入函数 __free_memory_core() ，并通过此函数进行所有 page 的初始化，并最终将 start之后的 page 以合适的 order 内存存放到buddy 系统中合适order 的链表中，完成buddy 内存的最后初始化工作。

2.3.2 __free_memory_core

/* 加入伙伴系统*/
static void __init __free_pages_memory(unsigned long start, unsigned long end)
{
	int order;
	int count=0;

	while (start < end) {
		order = min(MAX_ORDER - 1UL, __ffs(start));

		while (start + (1UL << order) > end)
			order--;
	    count++;
		if (count%10==0) {
			pr_info("---__free_page_memory:start=0x%llx,order=%ld, ffs()=%ld\n",start, order, __ffs(start));
		}
		memblock_free_pages(pfn_to_page(start), start, order); ///添加2^order个页到伙伴系统

		start += (1UL << order);
	}
}

static unsigned long __init __free_memory_core(phys_addr_t start,
				 phys_addr_t end)
{
	unsigned long start_pfn = PFN_UP(start);
	unsigned long end_pfn = min_t(unsigned long,
				      PFN_DOWN(end), max_low_pfn);

	if (start_pfn >= end_pfn)
		return 0;

	__free_pages_memory(start_pfn, end_pfn);  ///加入伙伴系统

	return end_pfn - start_pfn;
}

根据物理地址找到PFN，记录在start_pfn 和 end_pfn 中

2.3.3 __free_pages_memory

static void __init __free_pages_memory(unsigned long start, unsigned long end)
{
	int order; //用于表示当前内存块的阶数，order=n意味着块大小为2^n页
	int count=0; // 记录释放操作的次数，用于打印日志

	// 遍历从start到end的页帧范围
	while (start < end) {
		// MAX_ORDER: 伙伴系统支持的最大阶数
		// __ffs(start): 计算start的最低有效位，表示从该地址开始，连续对齐的页帧数可以达到的最大阶数
		order = min(MAX_ORDER - 1UL, __ffs(start));

		// 如果当前结束的内存块大小超出范围，减少阶数
		while (start + (1UL << order) > end)
			order--;
	    count++;
		// 每释放10次输出一次日志
		if (count%10==0) {
			pr_info("---__free_page_memory:start=0x%llx,order=%ld, ffs()=%ld\n",start, order, __ffs(start));
		}
		// 将2^order数量的页的内存块释放到伙伴系统中
		memblock_free_pages(pfn_to_page(start), start, order); ///添加2^order个页到伙伴系统

		start += (1UL << order);
	}
}
  • 首先，找到start 对应的 order，__ffs(start) 是计算start 中的转成二进制对应的 第一个为1 的位置。 因为buddy 系统按照 内存块 的大小来 添加到不同的链表 中，其中能容纳单个内存块最大值为 2^{10} 个物理页面，即1024(0x400)个物理页面。假设start 为起始地址为0x63300，说明该地址以0x100 对齐，通过 __ffs() 计算出合适的order 为8，因为 2^{8} 等于0x100。该地址非常适合创建一个 2^{8} 个页面大小的空闲内存块，并添加到order 为8 的buddy 空闲链表中；
  • 接着一个while 循环，如果start 至 end 不够一个order，则寻找合适的order；
  • 接着 memblock_free_pages() ，将PFN 从start 开始的page，到order 之间的pages 清除PageReserved 标记，设置 page 的_refcount 为 0，并通过 __free_pages() 将该page 添加到buddy 系统的链表尾端；
2.3.3.1 memblock_free_pages
void __init memblock_free_pages(struct page *page, unsigned long pfn,
							unsigned int order)
{
	if (early_page_uninitialised(pfn))
		return;
	///加入伙伴系统
	__free_pages_core(page, order);
}
2.3.3.2 __free_pages_core
void __free_pages_core(struct page *page, unsigned int order)
{
	unsigned int nr_pages = 1 << order;	//将order转化成页数，大小为2^order页
	struct page *p = page; // 指向要释放的页的起始地址
	unsigned int loop;

	/*
	 * When initializing the memmap, __init_single_page() sets the refcount
	 * of all pages to 1 ("allocated"/"not free"). We have to set the
	 * refcount of all involved pages to 0.
	 */
	prefetchw(p); // 预读取， 提前加载页结构到写缓冲区，提升性能

	// 遍历nr_pages页
	for (loop = 0; loop < (nr_pages - 1); loop++, p++) {
		prefetchw(p + 1);
		__ClearPageReserved(p); //清除页面的PageReserved标志
		set_page_count(p, 0); //将页的引用计数置为0
	}
	__ClearPageReserved(p);
	set_page_count(p, 0);

	//更新所属区域 (zone) 的 managed_pages 计数器，表示该区域现在有更多的页可供管理。
	atomic_long_add(nr_pages, &page_zone(page)->managed_pages);

	/*
	 * Bypass PCP and place fresh pages right to the tail, primarily
	 * relevant for memory onlining.
	 */
	// 将释放的页加入伙伴系统
	__free_pages_ok(page, order, FPI_TO_TAIL | FPI_SKIP_KASAN_POISON);
}

本文就先分析到此处，后续会再次分析底层实现。到现在我们知道调用__free_pages_ok函数后，空闲内存就加入到了buddy系统里了。

3. 总结

{% tip success %}
buddy 系统初始化的入口函数为 mem_init() ，轮询 memblock.memory 中每个region，将可以实际使用的内存提取出来，获得其start、end 地址，调用 __free_pages_memory() 函数。

而在 __free_pages_memory() 函数中，会将这部分内存以 order 的单位传入 __free_page_core() 函数，实行实际的释放操作。

__free_page_core() 函数中，首先会将该段内存中所有的 page 的PageReserved 标记清除掉，并设置每个page的 _refcount 为0。接着会统计 zone->managed_pages，设置页块的 _refcount 为1，进入最终的释放函数 __free_pages_ok()。

{% endtip %}