[置顶] 泰晓 RISC-V 实验箱,配套 30+ 讲嵌入式 Linux 系统开发公开课
memblock 内存分配器原理和代码分析
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 的二进制包管理服务(1):设计简介与框架
- RISC-V Linux 内核及周边技术动态第 118 期
- RISC-V Linux 内核及周边技术动态第 117 期
- 实时分析工具 rtla timerlat 介绍(二):延迟测试原理
- 实时分析工具 rtla timerlat 介绍(一):交叉编译及使用