泰晓科技 -- 聚焦 Linux - 追本溯源,见微知著!
网站地址:https://tinylab.org

儿童Linux系统,可打字编程学数理化
请稍侯

memblock 内存分配器原理和代码分析

Jinyu Tang 创作于 2022/08/30

Author: tjytimi tjytimi@163.com Date: 2022/07/10 Revisor: Falcon falcon@tinylab.org; walimis walimis@walimis.org Project: RISC-V Linux 内核剖析 Sponsor: PLCT Lab, ISCAS

前言

本文分析 memblock 内存分配器源码,依次对其功能、主要结构体、主要接口函数及内核启动过程中 memblock 主要行为进行分析梳理。内核版本为 Linux 5.17。分析调试时使用 Linux Labricsv64/virt 虚拟板。

memblock 主要功能

memblock 内存页帧分配器是 Linux 启动早期内存管理器,在伙伴系统(Buddy System)接管内存管理之前为系统提供内存分配、预留等功能。

memblock 将系统启动时获取的可用内存范围(如从设备树中获取的内存范围)纳入管理,为内核启动阶段内存分配需求提供服务,直到 memblock 分配器将内存管理权移交给伙伴系统。同时 memblock 分配器也维护预留内存(reserved memory),使其不会被分配器直接用于分配,保证其不被非预留者使用。

memblock 管理结构体

内核中定义了一个 memblock 实体,作为 memblock 分配器管理载体,其类型为 struct memblock

memblock 分配器管理结构共有三层,从顶向下分别为 struct memblock , struct memblock_type , struct memblock_region ,三层结构关系如下图所示,可结合代码理解。下面将详细分析。

第一层:struct memblock

第一层 struct memblock 结构体描述分配器整体特性,定义如下:

// include/linux/memblock.h : 84
/**
 * struct memblock - memblock allocator metadata
 * @bottom_up: is bottom up direction?
 * @current_limit: physical address of the current allocation limit
 * @memory: usable memory regions
 * @reserved: reserved memory regions
 */
struct memblock {
	bool bottom_up;  /* is bottom up direction? */
	phys_addr_t current_limit;
	struct memblock_type memory;
	struct memblock_type reserved;
};

  • bottom_up 描述了分配器管理内存是否从底向上,取 true 代表从底向上,取 false 则反之。

  • current_limit 描述了分配器管理物理内存的最大值。

  • memory 描述了分配器管理的可用内存,此元素为第二层结构 struct memblock_type 类型,接下来将进行说明。

  • reserved 描述了分配器管理的预留内存,包括内核代码段等不可被分配器直接分配的内存。此元素也为第二层结构 struct memblock_type 类型。

第二层:struct memblock_type

第二层 struct memblock_type 结构体用于维护特定内存类型集合,定义如下:

// include/linux/memblock.h : 68
/**
 * struct memblock_type - collection of memory regions of certain type
 * @cnt: number of regions
 * @max: size of the allocated array
 * @total_size: size of all regions
 * @regions: array of regions
 * @name: the memory type symbolic name
 */
struct memblock_type {
	unsigned long cnt;
	unsigned long max;
	phys_addr_t total_size;
	struct memblock_region *regions;
	char *name;
};

  • cnt 记录了结构体中含有的内存区块数量。

  • max 结构体中为 regions 数组分配的数量,当需要维护内存区域数目超过 max 后 ,则会倍增 regions 的内存空间。

  • total_size 累计该类型内存集合中包含的物理内存数目。

  • regions 为内存区块数组,描述该集合下管理的所有内存区块,每个数组元素代表一块内存区域,可通过索引获取对应区块。此元素为第三层结构 struct memblock_region 类型,接下来将进行说明。注意区块是按照内存升序或降序排列(由上一层结构中 bottom_up 决定),且相邻数组元素所描述内存必不连续(连续会合并为一个数组元素)。

  • name 为内存类型集合名字,如名为 memory 代表可用内存集合,reserved 代码预留内存集合。

第三层:struct memblock_region

第三层 struct memblock_region 结构体代表被管理的内存区块,定义如下:

// include/linux/memblock.h : 52
/**
 * struct memblock_region - represents a memory region
 * @base: base address of the region
 * @size: size of the region
 * @flags: memory region attributes
 * @nid: NUMA node id
 */
struct memblock_region {
	phys_addr_t base;
	phys_addr_t size;
	enum memblock_flags flags;
#ifdef CONFIG_NUMA
	int nid;
#endif
};

  • base 区块起始地址。

  • size 区块的大小。

  • flags 区块类型标志,如普通型,热插拔型等。

  • nid 在 NUMA 内存系统中标识节点号。

以上介绍了 memblock 的三层结构,其中前两层在源码中已经定义。第三层 region 内存区块则是在内核启动过程中,内核调用相关接口函数动态添加。

memblock 主要接口函数分析

memblock 系统提供相关接口供内核使用,包括内存区块的添加、预留、内存申请等功能。本文将对以下五个关键接口函数进行分析,其余函数可举一反三:

  • memblock_add 将内存区块添加到可用内存集合。通过此函数可展示 memblock 添加区块的思路。

  • memblock_reserve 将内存区块添加到预留内存集合。

  • for_each_reserved_mem_range 遍历预留内存区块。通过此函数可展示 memblock 遍历区块的逻辑和思路。

  • memblock_phys_alloc 用于申请 memblock 中的物理内存。

  • memblock_alloc 用于申请 memblock 的内存并返回虚拟地址。可供内核申请内存是 memblock 价值实现的关键。

memblock_add

memblock_add 函数将目标区块添加到可用内存的集合中,函数如下:

//mm/memblock.c : 694
int __init_memblock memblock_add(phys_addr_t base, phys_addr_t size)
{
	phys_addr_t end = base + size - 1;

	memblock_dbg("%s: [%pa-%pa] %pS\n", __func__,
		     &base, &end, (void *)_RET_IP_);

	return memblock_add_range(&memblock.memory, base, size, MAX_NUMNODES, 0);
}

可见其主要调用 memblock_add_range 实现, memblock_add_range 函数将目标区块添加到第一个参数 type 指定的管理集合中, memblock_add 调用 memblock_add_range 时将第一个参数设置为全局的 memblock.memorymemblock_add_range 函数定义如下:

//mm/memblock.c : 573
static int __init_memblock memblock_add_range(struct memblock_type *type,
				phys_addr_t base, phys_addr_t size,
				int nid, enum memblock_flags flags)
{
	bool insert = false;
	phys_addr_t obase = base;
	phys_addr_t end = base + memblock_cap_size(base, &size);
	int idx, nr_new;
	struct memblock_region *rgn;

	if (!size)
		return 0;

	/* special case for empty array */
	if (type->regions[0].size == 0) {
		WARN_ON(type->cnt != 1 || type->total_size);
		type->regions[0].base = base;
		type->regions[0].size = size;
		type->regions[0].flags = flags;
		memblock_set_region_node(&type->regions[0], nid);
		type->total_size = size;
		return 0;
	}
repeat:
	/*
	 * The following is executed twice.  Once with %false @insert and
	 * then with %true.  The first counts the number of regions needed
	 * to accommodate the new area.  The second actually inserts them.
	 */
	base = obase;
	nr_new = 0;

	for_each_memblock_type(idx, type, rgn) {
		phys_addr_t rbase = rgn->base;
		phys_addr_t rend = rbase + rgn->size;

		if (rbase >= end)
			break;
		if (rend <= base)
			continue;
		/*
		 * @rgn overlaps.  If it separates the lower part of new
		 * area, insert that portion.
		 */
		if (rbase > base) {
#ifdef CONFIG_NUMA
			WARN_ON(nid != memblock_get_region_node(rgn));
#endif
			WARN_ON(flags != rgn->flags);
			nr_new++;
			if (insert)
				memblock_insert_region(type, idx++, base,
						       rbase - base, nid,
						       flags);
		}
		/* area below @rend is dealt with, forget about it */
		base = min(rend, end);
	}

	/* insert the remaining portion */
	if (base < end) {
		nr_new++;
		if (insert)
			memblock_insert_region(type, idx, base, end - base,
					       nid, flags);
	}

	if (!nr_new)
		return 0;

	/*
	 * If this was the first round, resize array and repeat for actual
	 * insertions; otherwise, merge and return.
	 */
	if (!insert) {
		while (type->cnt + nr_new > type->max)
			if (memblock_double_array(type, obase, size) < 0)
				return -ENOMEM;
		insert = true;
		goto repeat;
	} else {
		memblock_merge_regions(type);
		return 0;
	}
}

此函数较长,但逻辑并不复杂,其主要流程为:

  • 当前类型集合为空时,即 type->regions[0].size == 0,直接将区域起始地址,大小等填入第一个 regions 中,并记录总大小 total_size 完成添加,直接返回 0 。否则进入 reapeat 标号处代码执行。

  • 当前类型集合不为空时执行 repeat 标号后代码,其中注释说明很详细,将会执行两次,第一次 insert 为假,memblock_insert_region 函数不会执行,仅对需要插入的区块计数,第二次执行 memblock_insert_region 完成实际插入功能。目的是保证数组 regions 足够容纳所需插入区块数。 repeat 标号后代码主要逻辑如下:

    • 使用 for_each_memblock_type 循环,遍历已存在区块,获取存在区块起始地址 rbase 和结束地址 rend

    • 若新区块在当前遍历区块之前,即 rbase >= end,则可确定不会重叠,要插入位置为当前区块之前,直接退出循环,将在第二次进行插入流程。

    • 若新区块在当前遍历区块之后,即 rend <= base,进入下一个循环,继续看后面区块是否与新区块重叠。

    • 若新区块与当前区块有重叠,且重叠之前有不重叠部分,即 rbase > base,则需将新区块前面未和原有区块重叠的那部分插入,并后移新区块起始地址 base,即 base = min(rend, end)

    • 完全遍历已存在区域后,判断新区块尾部是否有超过原有区块部分,即 base < end,若有则这部分也要插入集合。

    • 插入工作完成后,调用 memblock_merge_regions 函数将地址相邻的区块合并为一个区块。该函数遍历所有存在的区块,如相邻则合并。

关于 memblock_add_range 函数提的 patch

分析此函数时,感觉此处任何情况均要循环搜索两次并不是很好,提了个 patch 如下,目前已进入 linux-next 仓库:

对于一个向 type 中插入的内存范围,最差情况是其范围覆盖了 type->cnt 个已经存在的离散区域,这会需要 type->cnt + 1 个在 type->regions 中的空闲 struct memblock_region 供插入时使用,所以如果 type->cnt * 2 + 1type 中现有总 struct memblock_regiontype->max 要小,则可在 repeat 标号前将 insert 设为 1,直接插入待插区域,不用预先计算所需空闲区块数量。且由于 memblock_add_range 函数最后还有合并相邻区块操作,type->cnt 在每次插入后增长很慢甚至可能降低,所以此修改能够避免很多不必要的 repeat 操作。

diff --git a/mm/memblock.c b/mm/memblock.c
index e4f03a6e8e56e..16f006521afad 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -593,6 +593,17 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 		type->total_size = size;
 		return 0;
 	}
+
+	/*
+	 * The worst case is when new range overlaps all existing regions,
+	 * then we'll need type->cnt + 1 empty regions in @type. So if
+	 * type->cnt * 2 + 1 is less than type->max, we know
+	 * that there is enough empty regions in @type, and we can insert
+	 * regions directly.
+	 */
+	if (type->cnt * 2 + 1 < type->max)
+		insert = true;
+
 repeat:
 	/*
 	 * The following is executed twice.  Once with %false @insert and

memblock_reserve

memblock_reserve 函数将目标区块添加到预留内存集合中,函数如下:

//mm/memblock.c : 838
int __init_memblock memblock_reserve(phys_addr_t base, phys_addr_t size)
{
	phys_addr_t end = base + size - 1;

	memblock_dbg("%s: [%pa-%pa] %pS\n", __func__,
		     &base, &end, (void *)_RET_IP_);

	return memblock_add_range(&memblock.reserved, base, size, MAX_NUMNODES, 0);
}

可见其和 memblock_add 函数类似,均是调用 memblock_add_range 实现,不再赘述,区别仅仅在于第一个参数是预留内存区域的集合(memblock.reserved)。

for_each_reserved_mem_range

for_each_reserved_mem_range 遍历预留内存区域,通过以下宏可知,其本质上是一个循环,循环中调用 __next_mem_range 函数获取区间。

//include/linux/memblock.h : 244

#define for_each_reserved_mem_range(i, p_start, p_end)			\
__for_each_mem_range(i, &memblock.reserved, NULL, NUMA_NO_NODE,	\
			     MEMBLOCK_NONE, p_start, p_end, NULL)


//include/linux/memblock.h : 183
#define __for_each_mem_range(i, type_a, type_b, nid, flags,		\
			   p_start, p_end, p_nid)			\
	for (i = 0, __next_mem_range(&i, nid, flags, type_a, type_b,	\
				     p_start, p_end, p_nid);		\
	     i != (u64)ULLONG_MAX;					\
	     __next_mem_range(&i, nid, flags, type_a, type_b,		\
			      p_start, p_end, p_nid))

__next_mem_range 函数的功能是给出类型为 type_a 集合中排除 type_b 集合后的可用区间。

故此函数在多处遍历时被使用:

  • for_each_free_mem_range 函数使用它时,tpye_amemblock.memorytpye_bmemblock.reserved ,遍历可被申请的内存。

  • for_each_mem_range 函数使用它时,tpye_amemblock.memorytpye_bNULL ,直接遍历 memblock.memory 可用内存集合区间。

  • for_each_reserved_mem_range 函数使用它时,tpye_amemblock.reservedtpye_bNULL ,直接遍历 memblock.reserved 预留内存集合区间。

memblock_phys_alloc

memblock_phys_alloc 用于申请 memblock 中的物理内存。其直接调用 memblock_find_in_range_node 函数实现功能。memblock_find_in_range_node 代码如下:

//mm/memblock.c : 1424

static phys_addr_t __init_memblock memblock_find_in_range_node(phys_addr_t size,
					phys_addr_t align, phys_addr_t start,
					phys_addr_t end, int nid,
					enum memblock_flags flags)
{
	/* pump up @end */
	if (end == MEMBLOCK_ALLOC_ACCESSIBLE ||
	    end == MEMBLOCK_ALLOC_NOLEAKTRACE)
		end = memblock.current_limit;

	/* avoid allocating the first page */
	start = max_t(phys_addr_t, start, PAGE_SIZE);
	end = max(start, end);

	if (memblock_bottom_up())
		return __memblock_find_range_bottom_up(start, end, size, align,
						       nid, flags);
	else
		return __memblock_find_range_top_down(start, end, size, align,
						      nid, flags);
}

memblock_find_in_range_node 函数寻找 memblock 分配器在对应内存节点中符合要求的内存,找到后返回区间物理地址首地址。具体流程如下:

  • startend 变量进行简单处理,确保由顶向底模式中满足 start 小于 end ,同时保证不会分配第一个页帧。

  • 如果 memblock_bottom_up 为真, 调用 __memblock_find_range_bottom_up 函数搜索大小为 size 的合适内存区间。__memblock_find_range_bottom_up 函数调用前述 for_each_free_mem_range 顺序遍历 memblock 可用内存,发现合适大小区块后返回物理地址。

  • 反之,调用 ` __memblock_find_range_top_down ` 函数,其逻辑和 __memblock_find_range_bottom_up 类似,仅是遍历时方向相反。

memblock_alloc

memblock_alloc 用于申请 memblock 中的内存并返回虚拟地址。函数调用关系如下:


memblock_alloc
	- memblock_alloc_try_nid
		- memblock_alloc_internal
			- kzalloc_node (exec it if slab is enable and then return)
			- memblock_alloc_range_nid
				- memblock_find_in_range_node
			- phys_to_virt

可见 memblock_alloc 函数和 memblock_phy_alloc 函数均是调用 memblock_find_in_range_node 实现物理内存的分配,不同的是 memblock_alloc 会在分配后调用了 phys_to_virt 函数将物理地址转换成虚拟地址。对 RISC-V 架构来说,此处转化为线性映射关系。

另外,调用 memblock_alloc_range_nid 之前会检查是否启用了 slab 分配器,如果已启用,说明 memblock 已将管理权移交给伙伴系统(移交部分下文会详细说明)。这时会直接调用 kzalloc_node 从 slab 分配器分配内存。

memblock 在内核启动过程中的主要行为

memblock 在系统启动后提供内存管理功能,这些功能依赖于上节所述接口函数。

按照时间顺序,memblock 依次进行可用内存初始化,预留内存初始化,为内核提供内存管理服务,释放和移交管理权等流程。以下将分别进行分析。

memblock 可用内存初始化

内核启动后,执行 start_kernel 函数,该函数中 setup_arch 函数对特定架构进行初始化。在 RISC-V 中该函数中会调用 parse_dtb 解析设备树,parse_dtb 函数与 memblock 相关的分支如下:

- parse_dtb
    - early_init_dt_scan
        - early_init_dt_scan_nodes
            - early_init_dt_scan_memory
		        - early_init_dt_add_memory_arch
                	- memblock_add

可见最终会调用上节所述 memblock_add 函数将可用内存写入 memblock 全局变量中,使可用内存区域受 memblock 分配器管理。

memblock 预留内存初始化

将需要保留的内存添加进预留内存类型集合(memblock.reserved),使得后续使用 memblock 分配内存时,避开预留内存。例如,在分页系统初始化过程中会调用 memblock_reserve 函数将内核程序在内存中的范围保留,保证其不会被覆盖,调用关系如下:

    - paging_init
      - setup_bootmem()
        - memblock_reserve(vmlinux_start, vmlinux_end - vmlinux_start)

类似的,其他预留内存的地方(如设备树中设置的预留内存)也均是通过调用 memblock_reserve 接口函数实现。 关于预留内存的使用,将会在后续分析驱动相关的 ioremap 文章中举例说明。

memblock 的使用

当 memblock 系统完成初始化后,需要申请内存时内核会通过 memblock 系统。

如在 RISC-V 架构下 setup_vm_final 函数调用 create_pgd_mapping 函数建立页全局目录时,会调用 alloc_pgd_next 获取一个页面作为页表。alloc_pgd_next 实际是调用 memblock_phys_alloc 函数从 memblock 分配器中获取一个空闲页面。又如 setup_log_buf 中申请存放日志的内存时,会调用 memblock_alloc 获得一块内存的虚拟地址。

memblock 释放和移交管理权流程

当内核完成部分初始化功能,并继续启动到要建立以后内核都将使用内存管理系统时,就到了 memblock 向伙伴系统移交控制权的时候了。mm_init 函数负责建立内存管理系统。该函数会调用 memblock_free_all 函数,此函数完成 memblock 释放并移交管理权的流程。相关流程如下:

- mm_init
    - mem_init
        - memblock_free_all

memblock_free_all 的代码如下:

//mm/memblock.c : 2108
void __init memblock_free_all(void)
{
	unsigned long pages;

	free_unused_memmap();
	reset_all_zones_managed_pages();

	pages = free_low_memory_core_early();
	totalram_pages_add(pages);
}

memblock_free_allfree_low_memory_core_early 函数具体实现释放和移交功能,函数返回空闲页帧数目。memblock_free_all 最后调用 totalram_pages_add 函数将页帧数目 pages 加到全局页面数目 _totalram_pages 变量中。

free_low_memory_core_early 函数主要流程如下:

free_low_memory_core_early
	- memmap_init_reserved_pages
    - __free_memory_core
  • memmap_init_reserved_pages 函数负责预留内存的移交功能,保证后续伙伴系统也不会使用预留内存。

  • __free_memory_core 函数负责可用内存移交功能,完成最终的管理权限移交。

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 */
	for_each_reserved_mem_range(i, &start, &end)
		reserve_bootmem_region(start, end);

	/* and also treat struct pages for the NOMAP regions as PageReserved */
	for_each_mem_region(region) {
		if (memblock_is_nomap(region)) {
			start = region->base;
			end = start + region->size;
			reserve_bootmem_region(start, end);
		}
	}
}

函数遍历 memblock 中保留类型集合中所有区块及标志为 MEMBLOCK_NOMAP 的可用内存区块,对每个区块调用 reserve_bootmem_region 函数。reserve_bootmem_region 找到对应区块的页描述符(struct page),使用 __SetPageReserved(page) 宏将页面设置为保留,后续伙伴系统将不会分配此页面。

__free_memory_core 函数主要流程如下:

__free_memory_core
    - __free_pages_memory
        - memblock_free_pages
            - __free_pages_core
                - __ClearPageReserved
		        -  set_page_count(p, 0)
                - __free_pages_ok

函数最终会调用 __free_pages_core 函数,主要完成以下工作:

  • 调用 __ClearPageReserved 函数使页帧被内核可用。

  • 调用 set_page_count 将页引用计数器置零。

  • 调用 __free_pages_ok 函数页面添加进伙伴系统。

至此, memblock 系统完成其使命,后续页面管理由伙伴系统负责。

需要补充说明的是,已经被 memblock 分配的内存没有显式的移交给伙伴系统。这是由于在初始化页帧结构时,会将页面引用计数置位。已分配内存不会调用 __free_memory_core 将页面引用计数复位,从而保证了伙伴系统不会使用这部分内存。

具体在 RISC-V 架构下,通过如下调用链设置:

setup_arch
	- misc_mem_init
		- zone_sizes_init
			- free_area_init
				- memmap_init
					- memmap_init_zone_range
						- memmap_init_range
							- __init_single_page
								- init_page_count

其中 init_page_count 函数将页面计数置位。


/*
 * Setup the page count before being freed into the page allocator for
 * the first time (boot or memory hotplug)
 */

static inline void init_page_count(struct page *page)
{
	set_page_count(page, 1);
}

若伙伴系统运行后希望释放 memblock 分配的某块内存,则应使用 memblock_free_late 函数,这个函数本质也调用了上述 __free_pages_core 函数。注意不可调用 memblock_free,该函数注释已明确说明其不负责将内存释放进伙伴系统。


/**
 * memblock_free - free boot memory allocation
 * @ptr: starting address of the  boot memory allocation
 * @size: size of the boot memory block in bytes
 *
 * Free boot memory block previously allocated by memblock_alloc_xx() API.
 * The freeing memory will not be released to the buddy allocator.
 */
void __init_memblock memblock_free(void *ptr, size_t size)
{
	if (ptr)
		memblock_phys_free(__pa(ptr), size);
}

总结

本文分析了 memblock 内存分配器主要功能、主要结构体和接口函数及内核启动过程中 memblock 的生命周期。



Read Album:

Read Related:

Read Latest: