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 中。

審核編輯 ：李倩