[置顶] 泰晓 RISC-V 实验箱，配套 30+ 讲嵌入式 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 Lab 中 ricsv64/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.memory 。memblock_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 + 1 比 type 中现有总 struct memblock_region 数 type->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_a取memblock.memory，tpye_b取memblock.reserved，遍历可被申请的内存。for_each_mem_range函数使用它时，tpye_a取memblock.memory，tpye_b取NULL，直接遍历memblock.memory可用内存集合区间。for_each_reserved_mem_range函数使用它时，tpye_a取memblock.reserved，tpye_b取NULL，直接遍历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 分配器在对应内存节点中符合要求的内存，找到后返回区间物理地址首地址。具体流程如下：
对
start和end变量进行简单处理，确保由顶向底模式中满足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_all 中 free_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 的生命周期。
猜你喜欢：
- 我要投稿：发表原创技术文章，收获福利、挚友与行业影响力
- 知识星球：独家 Linux 实战经验与技巧，订阅「Linux知识星球」
- 视频频道：泰晓学院，B 站，发布各类 Linux 视频课
- 开源小店：欢迎光临泰晓科技自营店，购物支持泰晓原创
- 技术交流：Linux 用户技术交流微信群，联系微信号：tinylab
| 支付宝打赏 ￥9.68元 | 微信打赏 ￥9.68元 | |
 |  请作者喝杯咖啡吧 |  |
Read Album:
- TinyBPT 和面向 buildroot 的二进制包管理服务（3）：服务端说明
- TinyBPT 和面向 buildroot 的二进制包管理服务（2）：客户端说明
- TinyBPT 和面向 buildroot 的二进制包管理服务（1）：设计简介与框架
- RISC-V Linux 内核及周边技术动态第 118 期
- RISC-V Linux 内核及周边技术动态第 117 期
