引导内存分配器（初始化）
在内核初始化的过程中需要分配内存，内核提供了临时的引导内存分配器，在页分配器和块分配器初始化完毕后，把空闲的物理页交给页分配器管理，丢弃引导内存分配器。
早期使用的引导内存分配器是bootmem，目前正在使用memblock取代bootmem。
**
如果开启配置宏CONFIG_NO_BOOTMEM, memblock就会取代bootmem**。为了保证兼容性，bootmem和memblock提供了相同的接口。
（之前也提到过这个，因为在内核的初始化阶段内存分配器还没初始化好，因此内存的分配需要临时的内存分配器。）
前面的五个part，我们知道了内存的布局、映射、架构。
现在开始我们来看看这个内存的分配是怎么玩的。
1-bootmem分配器
bootmem分配器使用的数据结构如下：
include/linux/bootmem.h typedef struct bootmem_data { unsigned long node_min_pfn; unsigned long node_low_pfn; void *node_bootmem_map; unsigned long last_end_off; unsigned long hint_idx; struct list_head list; } bootmem_data_t;
下面解释结构体bootmem_data的成员。
- （1）node_min_pfn是起始物理页号。
- （2）node_low_pfn是结束物理页号。
- （3）node_bootmem_map指向一个位图，每个物理页对应一位，如果物理页被分配，把对应的位设置为1。
- （4）last_end_off是上次分配的内存块的结束位置后面一个字节的偏移。
- （5）hint_idx的字面意思是“暗示的索引”，是上次分配的内存块的结束位置后面的物理页在位图中的索引，下次优先考虑从这个物理页开始分配。
每个内存节点(pglist_data)有一个bootmem_data实例：
include/linux/mmzone.h typedef struct pglist_data { … #ifndef CONFIG_NO_BOOTMEM struct bootmem_data *bdata; #endif … } pg_data_t;
bootmem分配器的算法如下:
- （1）只把低端内存添加到bootmem分配器，低端内存是可以直接映射到内核虚拟地址空间的物理内存。
- （2）使用一个位图记录哪些物理页被分配，如果物理页被分配，把这个物理页对应的位设置成1。
- （3）采用最先适配算法，扫描位图，找到第一个足够大的空闲内存块。
- （4）为了支持分配小于一页的内存块，记录上次分配的内存块的结束位置后面一个字节的偏移和后面一页的索引，下次分配时，从上次分配的位置后面开始尝试。如果上次分配的最后一个物理页的剩余空间足够，可以直接在这个物理页上分配内存。
bootmem分配器对外提供的分配内存的函数是alloc_bootmem及其变体，释放内存的函数是free_bootmem。
分配内存的核心函数是源文件“mm/bootmem.c”中的函数alloc_bootmem_bdata。
ARM64架构的内核已经不使用bootmem分配器，但是其他处理器架构还在使用bootmem分配器。
(那ARM64可能就是使用的memblock)
下面看一下这个memblock分配器。
2-memblock分配器–怎么分配
1．数据结构
memblock分配器使用的数据结构如下：
include/linux/memblock.h struct memblock { bool bottom_up; /* 是从下向上的方向？ */ phys_addr_t current_limit; struct memblock_type memory; struct memblock_type reserved; #ifdef CONFIG_HAVE_MEMBLOCK_PHYS_MAP struct memblock_type physmem; #endif };
成员bottom_up表示分配内存的方式，值为真表示从低地址向上分配，值为假表示从高地址向下分配。
成员current_limit是可分配内存的最大物理地址。
接下来是3种内存块：
- memory是内存类型（包括已分配的内存和未分配的内存）,
- reserved是预留类型（已分配的内存）,
- physmem是物理内存类型。
物理内存类型和内存类型的区别是：
- 内存类型是物理内存类型的子集，在引导内核时可以使用内核参数“mem=nn[KMG]”指定可用内存的大小，导致内核不能看见所有内存；
- 物理内存类型总是包含所有内存范围，内存类型只包含内核参数“mem=”指定的可用内存范围。
内存块类型的数据结构如下：
include/linux/memblock.h struct memblock_type { unsigned long cnt; /* 区域数量 */ unsigned long max; /* 已分配数组的大小 */ phys_addr_t total_size; /* 所有区域的长度 */ struct memblock_region *regions; char *name; };
内存块类型使用数组存放内存块区域，
- 成员regions指向内存块区域数组，
- cnt是内存块区域的数量，
- max是数组的元素个数，
- total_size是所有内存块区域的总长度，
- name是内存块类型的名称。
内存块区域的数据结构如下：
include/linux/memblock.h struct memblock_region { phys_addr_t base; phys_addr_t size; unsigned long flags; #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP int nid; #endif }; /* memblock标志位的定义．*/ enum { MEMBLOCK_NONE = 0x0, /* 无特殊要求 */ MEMBLOCK_HOTPLUG = 0x1, /* 可热插拔区域 */ MEMBLOCK_MIRROR = 0x2, /* 镜像区域 */ MEMBLOCK_NOMAP = 0x4, /* 不添加到内核直接映射 */ };
- 成员base是起始物理地址，
- size是长度，
- nid是节点编号。
- 成员flags是标志，可以是MEMBLOCK_NONE或其他标志的组合。
- （1）MEMBLOCK_NONE表示没有特殊要求的区域。
- （2）MEMBLOCK_HOTPLUG表示可以热插拔的区域，即在系统运行过程中可以拔出或插入物理内存。
- （3）MEMBLOCK_MIRROR表示镜像的区域。内存镜像是内存冗余技术的一种，工作原理与硬盘的热备份类似，将内存数据做两个复制，分别放在主内存和镜像内存中。
- （4）MEMBLOCK_NOMAP表示不添加到内核直接映射区域（即线性映射区域）。
2．初始化
源文件“mm/memblock.c”定义了全局变量memblock，把成员bottom_up初始化为假，表示从高地址向下分配。
ARM64内核初始化memblock分配器的过程是：
- （1）解析设备树二进制文件中的节点“/memory”，把所有物理内存范围添加到memblock. memory，具体过程参考下一节。
- （2）在函数arm64_memblock_init中初始化memblock。
start_kernel() ->setup_arch() -> arm64_memblock_init() arch/arm64/mm/init.c
1-arm64_memblock_init
函数arm64_memblock_init的主要代码如下：
start_kernel() ->setup_arch() -> arm64_memblock_init() arch/arm64/mm/init.c 1 void __init arm64_memblock_init(void) 2 { 3 const s64 linear_region_size = -(s64)PAGE_OFFSET; 4 5 fdt_enforce_memory_region(); 6 7 memstart_addr = round_down(memblock_start_of_DRAM(), 8 ARM64_MEMSTART_ALIGN); 9 10 memblock_remove(max_t(u64, memstart_addr + linear_region_size, 11 __pa_symbol(_end)), ULLONG_MAX); 12 if (memstart_addr + linear_region_size < memblock_end_of_DRAM()) { 13 /* 确保memstart_addr严格对齐 */ 14 memstart_addr = round_up(memblock_end_of_DRAM() - linear_region_size, 15 ARM64_MEMSTART_ALIGN); 16 memblock_remove(0, memstart_addr); 17 } 18 19 if (memory_limit ! = (phys_addr_t)ULLONG_MAX) { 20 memblock_mem_limit_remove_map(memory_limit); 21 memblock_add(__pa_symbol(_text), (u64)(_end - _text)); 22 } 23 24 … 25 memblock_reserve(__pa_symbol(_text), _end - _text); 26 … 27 28 early_init_fdt_scan_reserved_mem(); 29 … 30 }
- 第5行代码，调用函数fdt_enforce_memory_region解析设备树二进制文件中节点“/chosen”的属性“linux, usable-memory-range”，得到可用内存的范围，把超出这个范围的物理内存范围从memblock.memory中删除。
- 第7行和第8行代码，全局变量memstart_addr记录内存的起始物理地址。
- 第10～17行代码，把线性映射区域不能覆盖的物理内存范围从memblock.memory中删除。
- 第19～22行代码，设备树二进制文件中节点“/chosen”的属性“bootargs”指定的命令行中，可以使用参数“mem”指定可用内存的大小。如果指定了内存的大小，那么把超过可用长度的物理内存范围从memblock.memory中删除。
因为内核镜像可以被加载到内存的高地址部分，并且内核镜像必须是可以通过线性映射区域访问的，所以需要把内核镜像占用的物理内存范围重新添加到memblock.memory中。
3．编程接口
memblock分配器对外提供的接口如下。
- （1）memblock_add：添加新的内存块区域到memblock.memory中。
- （2）memblock_remove：删除内存块区域。
- （3）memblock_alloc：分配内存。
- （4）memblock_free：释放内存。
为了兼容bootmem分配器，memblock分配器也实现了bootmem分配器提供的接口。如果开启配置宏CONFIG_NO_BOOTMEM, memblock分配器就完全替代了bootmem分配器。
4．算法
memblock分配器把所有内存添加到memblock.memory中，把分配出去的内存块添加到memblock.reserved中。
内存块类型中的内存块区域数组按起始物理地址从小到大排序。
函数memblock_alloc负责分配内存，把主要工作委托给函数memblock_alloc_range_nid，算法如下。
1-memblock_alloc_range_nid
- （1）调用函数memblock_find_in_range_node以找到没有分配的内存块区域，默认从高地址向下分配。
函数memblock_find_in_range_node有两层循环，外层循环从高到低遍历memblock.memory的内存块区域数组；
针对每个内存块区域M1，执行内层循环，从高到低遍历memblock.reserved的内存块区域数组。
针对每个内存块区域M2，目标区域是内存块区域M2和前一个内存块区域之间的区域，如果目标区域属于内存块区域M1，并且长度大于或等于请求分配的长度，那么可以从目标区域分配内存。 - （2）调用函数memblock_reserve，把分配出去的内存块区域添加到memblock.reserved中。
函数memblock_free负责释放内存，只需要把内存块区域从memblock.reserved中删除。
3-物理内存信息–有多拿来分配
在内核初始化的过程中，引导内存分配器负责分配内存。
问题是：引导内存分配器怎么知道内存的大小和物理地址范围？
ARM64架构使用扁平设备树（Flattened Device Tree, FDT）描述板卡的硬件信息，好处是可以把板卡特定的代码从内核中删除，编译生成通用的板卡无关的内核。
驱动开发者编写设备树源文件（Device Tree Source, DTS），存放在目录“arch/arm64/boot/dts”下，然后使用设备树编译器（Device Tree Compiler,DTC）把设备树源文件转换成设备树二进制文件（Device Tree Blob, DTB），接着把设备树二进制文件写到存储设备上。
设备启动时，引导程序把设备树二进制文件从存储设备读到内存中，引导内核的时候把设备树二进制文件的起始地址传给内核，内核解析设备树二进制文件后得到硬件信息。
设备树源文件是文本文件，扩展名是“.dts”，描述物理内存布局的方法如下：
/ { #address-cells = <2>; #size-cells = <2>; memory@80000000 { device_type = "memory"; reg = <0x00000000 0x80000000 0 0x80000000>, <0x00000008 0x80000000 0 0x80000000>; }; };
“/”是根节点。
1-#address-cells
属性“#address-cells”定义一个地址的单元数量，
属性“#size-cells”定义一个长度的单元数量。
单元（cell）是一个32位数值，
属性“#address-cells = <2>”表示一个地址由两个单元组成，即地址是一个64位数值；
2-#size-cells =<2>
属性“#size-cells =<2>”表示一个长度由两个单元组成，即长度是一个64位数值。
3-memory
“memory”节点描述物理内存布局，“@”后面的设备地址用来区分名字相同的节点，如果节点有属性“reg”，那么设备地址必须是属性“reg”的第一个地址。
如果有多块内存，可以使用多个“memory”节点来描述，也可以使用一个“memory”节点的属性“reg”的地址/长度列表来描述。
4-device_type
属性“device_type”定义设备类型，
“memory”节点的属性“device_type”的值必须是“memory”。
5-reg
属性“reg”定义物理内存范围，值是一个地址/长度列表，每个地址包含的单元数量是由根节点的属性“#address-cells”定义的，每个长度包含的单元数量是由根节点的属性“#size-cells”定义的。
在上面的例子中，
第一个物理内存范围的起始地址是“0x00000000 0x80000000”，长度是“0 0x80000000”，即起始地址是2GB，长度是2GB；
第二个物理内存范围的起始地址是“0x000000080x80000000”，长度是“0 0x80000000”，即起始地址是34GB，长度是2GB。
6-内存信息监测API
内核在初始化的时候调用函数early_init_dt_scan_nodes以解析设备树二进制文件，从而得到物理内存信息。
early_init_dt_scan_nodes
start_kernel() ->setup_arch() ->setup_machine_fdt() ->early_init_dt_scan() ->early_ init_dt_scan_nodes() drivers/of/fdt.c 1 void __init early_init_dt_scan_nodes(void) 2 { 3 … 4 /* 初始化size-cells和address-cells信息 */ 5 of_scan_flat_dt(early_init_dt_scan_root, NULL); 6 7 /* 调用函数early_init_dt_add_memory_arch设置内存 */ 8 of_scan_flat_dt(early_init_dt_scan_memory, NULL); 9 }
- 第5行代码，调用函数early_init_dt_scan_root，解析根节点的属性“#address-cells”得到地址的单元数量，保存在全局变量dt_root_addr_cells中；解析根节点的属性“#size-cells”得到长度的单元数量，保存在全局变量dt_root_size_cells中。
- 第8行代码，调用函数early_init_dt_scan_memory，解析“memory”节点得到物理内存布局。
early_init_dt_scan_memory
函数early_init_dt_scan_memory负责解析“memory”节点，其主要代码如下：
drivers/of/fdt.c 1 int __init early_init_dt_scan_memory(unsigned long node, const char *uname, 2 int depth, void *data) 3 { 4 const char *type = of_get_flat_dt_prop(node, "device_type", NULL); 5 const __be32 *reg, *endp; 6 int l; 7 … 8 9 /* 只扫描 "memory" 节点 */ 10 if (type == NULL) { 11 /* 如果没有属性“device_type”，判断节点名称是不是“memory@0”*/ 12 if (! IS_ENABLED(CONFIG_PPC32) || depth ! = 1 || strcmp(uname, "memory@0") ! = 0) 13 return 0; 14 } else if (strcmp(type, "memory") ! = 0) 15 return 0; 16 17 reg = of_get_flat_dt_prop(node, "linux, usable-memory", &l); 18 if (reg == NULL) 19 reg = of_get_flat_dt_prop(node, "reg", &l); 20 if (reg == NULL) 21 return 0; 22 23 endp = reg + (l / sizeof(__be32)); 24 … 25 26 while ((endp - reg) >= (dt_root_addr_cells + dt_root_size_cells)) { 27 u64 base, size; 28 29 base = dt_mem_next_cell(dt_root_addr_cells, ®); 30 size = dt_mem_next_cell(dt_root_size_cells, ®); 31 32 if (size == 0) 33 continue; 34 … 35 early_init_dt_add_memory_arch(base, size); 36 … 37 } 38 39 return 0; 40 }
- 第4行代码，解析节点的属性“device_type”。
- 第14行代码，如果属性“device_type”的值是“memory”，说明这个节点描述物理内存信息。第
- 17～19行代码，解析属性“linux, usable-memory”，如果不存在，那么解析属性“reg”。这两个属性都用来定义物理内存范围。
- 第26～37行代码，解析出每块内存的起始地址和大小后，调用函数early_init_dt_add_memory_arch。
early_init_dt_add_memory_arch
drivers/of/fdt.c void __init __weak early_init_dt_add_memory_arch(u64 base, u64 size) { const u64 phys_offset = MIN_MEMBLOCK_ADDR; if (! PAGE_ALIGNED(base)) { if (size < PAGE_SIZE - (base & ~PAGE_MASK)) { pr_warn("Ignoring memory block 0x%llx - 0x%llx\n", base, base + size); return; } size -= PAGE_SIZE - (base & ~PAGE_MASK); base = PAGE_ALIGN(base); } size &= PAGE_MASK; if (base > MAX_MEMBLOCK_ADDR) { pr_warning("Ignoring memory block 0x%llx - 0x%llx\n", base, base + size); return; } if (base + size - 1 > MAX_MEMBLOCK_ADDR) { pr_warning("Ignoring memory range 0x%llx - 0x%llx\n", ((u64)MAX_MEMBLOCK_ADDR) + 1, base + size); size = MAX_MEMBLOCK_ADDR - base + 1; } if (base + size < phys_offset) { pr_warning("Ignoring memory block 0x%llx - 0x%llx\n", base, base + size); return; } if (base < phys_offset) { pr_warning("Ignoring memory range 0x%llx - 0x%llx\n", base, phys_offset); size -= phys_offset - base; base = phys_offset; } memblock_add(base, size); }
函数early_init_dt_add_memory_arch对起始地址和长度做了检查以后，调用函数memblock_add把物理内存范围添加到memblock.memory中。
