bootmem分配器使用的數據結構

目錄

3.6引導內存分配器

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

3.6 引導內存分配器

在內核初始化的過(guò)程中需要分配內存，內核提供了臨時(shí)的引導內存分配器，在頁(yè)分配器和塊分配器初始化完畢后，把空閑的物理頁(yè)交給頁(yè)分配器管理，丟棄引導內存分配器。

早期使用的引導內存分配器是 bootmem，目前正在使用 memblock 取代 bootmem。如果開(kāi)啟配置宏 CONFIG_NO_BOOTMEM，memblock 就會(huì )取代 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 是起始物理頁(yè)號。

（2）node_low_pfn 是結束物理頁(yè)號。

（3）node_bootmem_map 指向一個(gè)位圖，每個(gè)物理頁(yè)對應一位，如果物理頁(yè)被分配，把對應的位設置為 1。

（4）last_end_off 是上次分配的內存塊的結束位置后面一個(gè)字節的偏移。

（5）hint_idx 的字面意思是“暗示的索引”，是上次分配的內存塊的結束位置后面的物理頁(yè)在位圖中的索引，下次優(yōu)先考慮從這個(gè)物理頁(yè)開(kāi)始分配。

每個(gè)內存節點(diǎn)有一個(gè) bootmem_data 實(shí)例：

include/linux/mmzone.h typedef struct pglist_data {  … #ifndef CONFIG_NO_BOOTMEM  struct bootmem_data *bdata; #endif  … } pg_data_t;

bootmem 分配器的算法如下。

（1）只把低端內存添加到 bootmem 分配器，低端內存是可以直接映射到內核虛擬地址空間的物理內存。

（2）使用一個(gè)位圖記錄哪些物理頁(yè)被分配，如果物理頁(yè)被分配，把這個(gè)物理頁(yè)對應的位設置成 1。

（3）采用最先適配算法，掃描位圖，找到第一個(gè)足夠大的空閑內存塊。

（4）為了支持分配小于一頁(yè)的內存塊，記錄上次分配的內存塊的結束位置后面一個(gè)字節的偏移和后面一頁(yè)的索引，下次分配時(shí)，從上次分配的位置后面開(kāi)始嘗試。如果上次分配的最后一個(gè)物理頁(yè)的剩余空間足夠，可以直接在這個(gè)物理頁(yè)上分配內存。

bootmem 分配器對外提供的分配內存的函數是 alloc_bootmem 及其變體，釋放內存的函數是 free_bootmem。分配內存的核心函數是源文件“mm/bootmem.c”中的函數 alloc_bootmem_bdata。

ARM64 架構的內核已經(jīng)不使用 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 是可分配內存的最大物理地址。

接下來(lái)是 3 種內存塊：memory 是內存類(lèi)型（包括已分配的內存和未分配的內存），reserved 是預留類(lèi)型（已分配的內存），physmem 是物理內存類(lèi)型。物理內存類(lèi)型和內存類(lèi)型的區別是：內存類(lèi)型是物理內存類(lèi)型的子集，在引導內核時(shí)可以使用內核參數“mem=nn[KMG]”指定可用內存的大小，導致內核不能看見(jiàn)所有內存；物理內存類(lèi)型總是包含所有內存范圍，內存類(lèi)型只包含內核參數“mem=”指定的可用內存范圍。

內存塊類(lèi)型的數據結構如下：

include/linux/memblock.h struct memblock_type {  unsigned long cnt; /* 區域數量 */  unsigned long max; /* 已分配數組的大小 */  phys_addr_t total_size; /* 所有區域的長(cháng)度 */  struct memblock_region *regions;  char *name; };

內存塊類(lèi)型使用數組存放內存塊區域，成員 regions 指向內存塊區域數組，cnt 是內存塊區域的數量，max 是數組的元素個(gè)數，total_size 是所有內存塊區域的總長(cháng)度，name 是內存塊類(lèi)型的名稱(chēng)。

內存塊區域的數據結構如下：

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, /* 無(wú)特殊要求 */  MEMBLOCK_HOTPLUG = 0x1, /* 可熱插拔區域 */  MEMBLOCK_MIRROR = 0x2, /* 鏡像區域 */  MEMBLOCK_NOMAP = 0x4, /* 不添加到內核直接映射 */ };

成員 base 是起始物理地址，size 是長(cháng)度，nid 是節點(diǎn)編號。成員 flags 是標志，可以是MEMBLOCK_NONE 或其他標志的組合。

（1）MEMBLOCK_NONE 表示沒(méi)有特殊要求的區域。

（2）MEMBLOCK_HOTPLUG 表示可以熱插拔的區域，即在系統運行過(guò)程中可以拔出或插入物理內存。

（3）MEMBLOCK_MIRROR 表示鏡像的區域。內存鏡像是內存冗余技術(shù)的一種，工作原理與硬盤(pán)的熱備份類(lèi)似，將內存數據做兩個(gè)復制，分別放在主內存和鏡像內存中。

（4）MEMBLOCK_NOMAP 表示不添加到內核直接映射區域（即線(xiàn)性映射區域）。

2．初始化

源文件“mm/memblock.c”定義了全局變量 memblock，把成員 bottom_up 初始化為假，表示從高地址向下分配。

ARM64 內核初始化 memblock 分配器的過(guò)程是：

（1）解析設備樹(shù)二進(jìn)制文件中的節點(diǎn)“/memory”，把所有物理內存范圍添加到 memblock.memory，具體過(guò)程參考 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 解析設備樹(shù)二進(jìn)制文件中節點(diǎn)“/chosen”的屬性“l(fā)inux,usable-memory-range”，得到可用內存的范圍，把超出這個(gè)范圍的物理內存范圍從 memblock.memory 中刪除。

第 7 行和第 8 行代碼，全局變量 memstart_addr 記錄內存的起始物理地址。

第 10～17 行代碼，把線(xiàn)性映射區域不能覆蓋的物理內存范圍從 memblock.memory 中刪除。

第 19～22 行代碼，設備樹(shù)二進(jìn)制文件中節點(diǎn)“/chosen”的屬性“bootargs”指定的命令行中，可以使用參數“mem”指定可用內存的大小。如果指定了內存的大小，那么把超過(guò)可用長(cháng)度的物理內存范圍從 memblock.memory 中刪除。因為內核鏡像可以被加載到內存的高地址部分，并且內核鏡像必須是可以通過(guò)線(xiàn)性映射區域訪(fǎng)問(wèn)的，所以需要把內核鏡像占用的物理內存范圍重新添加到 memblock.memory 中。

第 25 行代碼，把內核鏡像占用的物理內存范圍添加到 memblock.reserved 中。

第 28 行代碼，從設備樹(shù)二進(jìn)制文件中的內存保留區域（memory reserve map，對應設備樹(shù)源文件的字段“/memreserve/”）和節點(diǎn)“/reserved-memory”讀取保留的物理內存范圍，添加到 memblock.reserved 中。

3．編程接口

memblock 分配器對外提供的接口如下。

（1）memblock_add：添加新的內存塊區域到 memblock.memory 中。

（2）memblock_remove：刪除內存塊區域。

（3）memblock_alloc：分配內存。

（4）memblock_free：釋放內存。

為了兼容 bootmem 分配器，memblock 分配器也實(shí)現了 bootmem 分配器提供的接口。如果開(kāi)啟配置宏 CONFIG_NO_BOOTMEM，memblock 分配器就完全替代了 bootmem 分配器。

4．算法

memblock 分配器把所有內存添加到 memblock.memory 中，把分配出去的內存塊添加到 memblock.reserved 中。內存塊類(lèi)型中的內存塊區域數組按起始物理地址從小到大排序。

函數 memblock_alloc 負責分配內存，把主要工作委托給函數 memblock_alloc_range_nid，算法如下。

（1）調用函數 memblock_find_in_range_node 以找到?jīng)]有分配的內存塊區域，默認從高地址向下分配。

函數 memblock_find_in_range_node 有兩層循環(huán)，外層循環(huán)從高到低遍歷 memblock.memory的內存塊區域數組；針對每個(gè)內存塊區域 M1，執行內層循環(huán)，從高到低遍歷 memblock.reserved的內存塊區域數組。針對每個(gè)內存塊區域 M2，目標區域是內存塊區域 M2 和前一個(gè)內存塊區域之間的區域，如果目標區域屬于內存塊區域 M1，并且長(cháng)度大于或等于請求分配的長(cháng)度，那么可以從目標區域分配內存。

（2）調用函數 memblock_reserve，把分配出去的內存塊區域添加到 memblock.reserved 中。

函數 memblock_free 負責釋放內存，只需要把內存塊區域從 memblock.reserved 中刪除。

3.6.3 物理內存信息

在內核初始化的過(guò)程中，引導內存分配器負責分配內存，問(wèn)題是：引導內存分配器怎么知道內存的大小和物理地址范圍？

ARM64 架構使用扁平設備樹(shù)（Flattened Device Tree，FDT）描述板卡的硬件信息，好處是可以把板卡特定的代碼從內核中刪除，編譯生成通用的板卡無(wú)關(guān)的內核。驅動(dòng)開(kāi)發(fā)者編寫(xiě)設備樹(shù)源文件（Device Tree Source，DTS），存放在目錄“arch/arm64/boot/dts”下，然后使用設備樹(shù)編譯器（Device Tree Compiler，DTC）把設備樹(shù)源文件轉換成設備樹(shù)二進(jìn)制文件（Device Tree Blob，DTB），接著(zhù)把設備樹(shù)二進(jìn)制文件寫(xiě)到存儲設備上。設備啟動(dòng)時(shí)，引導程序把設備樹(shù)二進(jìn)制文件從存儲設備讀到內存中，引導內核的時(shí)候把設備樹(shù)二進(jìn)制文件的起始地址傳給內核，內核解析設備樹(shù)二進(jìn)制文件后得到硬件信息。

設備樹(shù)源文件是文本文件，擴展名是“.dts”，描述物理內存布局的方法如下：

/ {  #address-cells = <2>;  #size-cells = <2>;  memory@80000000 {  device_type = "memory";  reg = <0x00000000 0x80000000 0 0x80000000>,  <0x00000008 0x80000000 0 0x80000000>;  }; };

“/”是根節點(diǎn)。

屬性“#address-cells”定義一個(gè)地址的單元數量，屬性“#size-cells”定義一個(gè)長(cháng)度的單元數量。單元（cell）是一個(gè) 32 位數值，屬性“#address-cells = <2>”表示一個(gè)地址由兩個(gè)單元組成，即地址是一個(gè) 64 位數值；屬性“#size-cells = <2>”表示一個(gè)長(cháng)度由兩個(gè)單元組成，即長(cháng)度是一個(gè) 64 位數值。

“memory”節點(diǎn)描述物理內存布局，“@”后面的設備地址用來(lái)區分名字相同的節點(diǎn)，如果節點(diǎn)有屬性“reg”，那么設備地址必須是屬性“reg”的第一個(gè)地址。如果有多塊內存，可以使用多個(gè)“memory”節點(diǎn)來(lái)描述，也可以使用一個(gè)“memory”節點(diǎn)的屬性“reg”的地址/長(cháng)度列表來(lái)描述。

屬性“device_type”定義設備類(lèi)型，“memory”節點(diǎn)的屬性“device_type”的值必須是“memory”。

屬性“reg”定義物理內存范圍，值是一個(gè)地址/長(cháng)度列表，每個(gè)地址包含的單元數量是由根節點(diǎn)的屬性“#address-cells”定義的，每個(gè)長(cháng)度包含的單元數量是由根節點(diǎn)的屬性“#size-cells”定義的。在上面的例子中，第一個(gè)物理內存范圍的起始地址是“0x000000000x80000000”，長(cháng)度是“0 0x80000000”，即起始地址是 2GB，長(cháng)度是 2GB；第二個(gè)物理內存范圍的起始地址是“0x00000008 0x80000000”，長(cháng)度是“0 0x80000000”，即起始地址是34GB，長(cháng)度是 2GB。

內核在初始化的時(shí)候調用函數 early_init_dt_scan_nodes 以解析設備樹(shù)二進(jìn)制文件，從而得到物理內存信息。

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，解析根節點(diǎn)的屬性“#address-cells”得到地址的單元數量，保存在全局變量 dt_root_addr_cells 中；解析根節點(diǎn)的屬性“#size-cells”得到長(cháng)度的單元數量，保存在全局變量 dt_root_size_cells 中。

第 8 行代碼，調用函數 early_init_dt_scan_memory，解析“memory”節點(diǎn)得到物理內存布局。

函數 early_init_dt_scan_memory 負責解析“memory”節點(diǎn)，其主要代碼如下：

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" 節點(diǎn) */ 10 if (type == NULL) { 11 /* 如果沒(méi)有屬性“device_type”，判斷節點(diǎn)名稱(chēng)是不是“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 行代碼，解析節點(diǎn)的屬性“device_type”。

第 14 行代碼，如果屬性“device_type”的值是“memory”，說(shuō)明這個(gè)節點(diǎn)描述物理內存信息。

第 17～19 行代碼，解析屬性“l(fā)inux,usable-memory”，如果不存在，那么解析屬性“reg”。這兩個(gè)屬性都用來(lái)定義物理內存范圍。

第 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 對起始地址和長(cháng)度做了檢查以后，調用函數memblock_add 把物理內存范圍添加到 memblock.memory 中。