bootmem分配器使用的数据结构

目录

3.6引导内存分配器

3.6.1bootmem分配器 3.6.2memblock分配器 3.6.3物理内存信息

3.6 引导内存分配器

在内核初始化的过程中需要分配内存，内核提供了临时的引导内存分配器，在页分配器和块分配器初始化完毕后，把空闲的物理页交给页分配器管理，丢弃引导内存分配器。

早期使用的引导内存分配器是 bootmem，目前正在使用 memblock 取代 bootmem。如果开启配置宏 CONFIG_NO_BOOTMEM，memblock 就会取代 bootmem。为了保证兼容性，bootmem 和 memblock 提供了相同的接口。

3.6.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 的字面意思是“暗示的索引”，是上次分配的内存块的结束位置后面的物理页在位图中的索引，下次优先考虑从这个物理页开始分配。

每个内存节点有一个 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分配器。

3.6.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，具体过程参考 3.6.3 节。

（2）在函数 arm64_memblock_init 中初始化 memblock。

函数 arm64_memblock_init 的主要代码如下：

start_kernel() ->setup_arch() -> arm64_memblock_init() arch/arm64/mm/init.c1 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); 146 3.6 引导内存分配器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 中。

第 25 行代码，把内核镜像占用的物理内存范围添加到 memblock.reserved 中。

第 28 行代码，从设备树二进制文件中的内存保留区域（memory reserve map，对应设备树源文件的字段“/memreserve/”）和节点“/reserved-memory”读取保留的物理内存范围，添加到 memblock.reserved 中。

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_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.6.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>;  }; };

“/”是根节点。

属性“#address-cells”定义一个地址的单元数量，属性“#size-cells”定义一个长度的单元数量。单元（cell）是一个 32 位数值，属性“#address-cells = <2>”表示一个地址由两个单元组成，即地址是一个 64 位数值；属性“#size-cells = <2>”表示一个长度由两个单元组成，即长度是一个 64 位数值。

“memory”节点描述物理内存布局，“@”后面的设备地址用来区分名字相同的节点，如果节点有属性“reg”，那么设备地址必须是属性“reg”的第一个地址。如果有多块内存，可以使用多个“memory”节点来描述，也可以使用一个“memory”节点的属性“reg”的地址/长度列表来描述。

属性“device_type”定义设备类型，“memory”节点的属性“device_type”的值必须是“memory”。

属性“reg”定义物理内存范围，值是一个地址/长度列表，每个地址包含的单元数量是由根节点的属性“#address-cells”定义的，每个长度包含的单元数量是由根节点的属性“#size-cells”定义的。在上面的例子中，第一个物理内存范围的起始地址是“0x000000000x80000000”，长度是“0 0x80000000”，即起始地址是 2GB，长度是 2GB；第二个物理内存范围的起始地址是“0x00000008 0x80000000”，长度是“0 0x80000000”，即起始地址是34GB，长度是 2GB。

内核在初始化的时候调用函数 early_init_dt_scan_nodes 以解析设备树二进制文件，从而得到物理内存信息。

start_kernel() ->setup_arch() ->setup_machine_fdt() ->early_init_dt_scan() ->early_init_dt_scan_nodes() drivers/of/fdt.c1 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 负责解析“memory”节点，其主要代码如下：

drivers/of/fdt.c1 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; 1617 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.cvoid __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
",  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
",  base, base + size);  return;  }  if (base + size - 1 > MAX_MEMBLOCK_ADDR) {  pr_warning("Ignoring memory range 0x%llx - 0x%llx
", ((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
",  base, base + size);  return;  }  if (base < phys_offset) {  pr_warning("Ignoring memory range 0x%llx - 0x%llx
",  base, phys_offset);  size -= phys_offset - base;  base = phys_offset;  } memblock_add(base, size); }

函数 early_init_dt_add_memory_arch 对起始地址和长度做了检查以后，调用函数memblock_add 把物理内存范围添加到 memblock.memory 中。