bootmem分配器使用的數(shù)據(jù)結(jié)構(gòu)

目錄

3.6引導(dǎo)內(nèi)存分配器

3.6.1bootmem分配器 3.6.2memblock分配器 3.6.3物理內(nèi)存信息

3.6 引導(dǎo)內(nèi)存分配器

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

早期使用的引導(dǎo)內(nèi)存分配器是 bootmem，目前正在使用 memblock 取代 bootmem。如果開啟配置宏 CONFIG_NO_BOOTMEM，memblock 就會(huì)取代 bootmem。為了保證兼容性，bootmem 和 memblock 提供了相同的接口。

3.6.1 bootmem 分配器

bootmem 分配器使用的數(shù)據(jù)結(jié)構(gòu)如下：

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;

下面解釋結(jié)構(gòu)體 bootmem_data 的成員。

（1）node_min_pfn 是起始物理頁(yè)號(hào)。

（2）node_low_pfn 是結(jié)束物理頁(yè)號(hào)。

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

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

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

每個(gè)內(nèi)存節(jié)點(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）只把低端內(nèi)存添加到 bootmem 分配器，低端內(nèi)存是可以直接映射到內(nèi)核虛擬地址空間的物理內(nèi)存。

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

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

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

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

ARM64 架構(gòu)的內(nèi)核已經(jīng)不使用 bootmem 分配器，但是其他處理器架構(gòu)還在使用 bootmem分配器。

3.6.2 memblock 分配器

1．?dāng)?shù)據(jù)結(jié)構(gòu)

memblock 分配器使用的數(shù)據(jù)結(jié)構(gòu)如下：

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 表示分配內(nèi)存的方式，值為真表示從低地址向上分配，值為假表示從高地址向下分配。

成員 current_limit 是可分配內(nèi)存的最大物理地址。

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

內(nèi)存塊類型的數(shù)據(jù)結(jié)構(gòu)如下：

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

內(nèi)存塊類型使用數(shù)組存放內(nèi)存塊區(qū)域，成員 regions 指向內(nèi)存塊區(qū)域數(shù)組，cnt 是內(nèi)存塊區(qū)域的數(shù)量，max 是數(shù)組的元素個(gè)數(shù)，total_size 是所有內(nèi)存塊區(qū)域的總長(zhǎng)度，name 是內(nèi)存塊類型的名稱。

內(nèi)存塊區(qū)域的數(shù)據(jù)結(jié)構(gòu)如下：

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標(biāo)志位的定義. */ enum {  MEMBLOCK_NONE = 0x0, /* 無特殊要求 */  MEMBLOCK_HOTPLUG = 0x1, /* 可熱插拔區(qū)域 */  MEMBLOCK_MIRROR = 0x2, /* 鏡像區(qū)域 */  MEMBLOCK_NOMAP = 0x4, /* 不添加到內(nèi)核直接映射 */ };

成員 base 是起始物理地址，size 是長(zhǎng)度，nid 是節(jié)點(diǎn)編號(hào)。成員 flags 是標(biāo)志，可以是MEMBLOCK_NONE 或其他標(biāo)志的組合。

（1）MEMBLOCK_NONE 表示沒有特殊要求的區(qū)域。

（2）MEMBLOCK_HOTPLUG 表示可以熱插拔的區(qū)域，即在系統(tǒng)運(yùn)行過程中可以拔出或插入物理內(nèi)存。

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

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

2．初始化

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

ARM64 內(nèi)核初始化 memblock 分配器的過程是：

（1）解析設(shè)備樹二進(jìn)制文件中的節(jié)點(diǎn)“/memory”，把所有物理內(nèi)存范圍添加到 memblock.memory，具體過程參考 3.6.3 節(jié)。

（2）在函數(shù) arm64_memblock_init 中初始化 memblock。

函數(shù) 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 引導(dǎo)內(nèi)存分配器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嚴(yán)格對(duì)齊 */ 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 行代碼，調(diào)用函數(shù) fdt_enforce_memory_region 解析設(shè)備樹二進(jìn)制文件中節(jié)點(diǎn)“/chosen”的屬性“l(fā)inux,usable-memory-range”，得到可用內(nèi)存的范圍，把超出這個(gè)范圍的物理內(nèi)存范圍從 memblock.memory 中刪除。

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

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

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

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

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

3．編程接口

memblock 分配器對(duì)外提供的接口如下。

（1）memblock_add：添加新的內(nèi)存塊區(qū)域到 memblock.memory 中。

（2）memblock_remove：刪除內(nèi)存塊區(qū)域。

（3）memblock_alloc：分配內(nèi)存。

（4）memblock_free：釋放內(nèi)存。

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

4．算法

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

函數(shù) memblock_alloc 負(fù)責(zé)分配內(nèi)存，把主要工作委托給函數(shù) memblock_alloc_range_nid，算法如下。

（1）調(diào)用函數(shù) memblock_find_in_range_node 以找到?jīng)]有分配的內(nèi)存塊區(qū)域，默認(rèn)從高地址向下分配。

函數(shù) memblock_find_in_range_node 有兩層循環(huán)，外層循環(huán)從高到低遍歷 memblock.memory的內(nèi)存塊區(qū)域數(shù)組；針對(duì)每個(gè)內(nèi)存塊區(qū)域 M1，執(zhí)行內(nèi)層循環(huán)，從高到低遍歷 memblock.reserved的內(nèi)存塊區(qū)域數(shù)組。針對(duì)每個(gè)內(nèi)存塊區(qū)域 M2，目標(biāo)區(qū)域是內(nèi)存塊區(qū)域 M2 和前一個(gè)內(nèi)存塊區(qū)域之間的區(qū)域，如果目標(biāo)區(qū)域?qū)儆趦?nèi)存塊區(qū)域 M1，并且長(zhǎng)度大于或等于請(qǐng)求分配的長(zhǎng)度，那么可以從目標(biāo)區(qū)域分配內(nèi)存。

（2）調(diào)用函數(shù) memblock_reserve，把分配出去的內(nèi)存塊區(qū)域添加到 memblock.reserved 中。

函數(shù) memblock_free 負(fù)責(zé)釋放內(nèi)存，只需要把內(nèi)存塊區(qū)域從 memblock.reserved 中刪除。

3.6.3 物理內(nèi)存信息

在內(nèi)核初始化的過程中，引導(dǎo)內(nèi)存分配器負(fù)責(zé)分配內(nèi)存，問題是：引導(dǎo)內(nèi)存分配器怎么知道內(nèi)存的大小和物理地址范圍？

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

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

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

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

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

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

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

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

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

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 /* 調(diào)用函數(shù)early_init_dt_add_memory_arch設(shè)置內(nèi)存 */ 8 of_scan_flat_dt(early_init_dt_scan_memory, NULL); 9 }

第 5 行代碼，調(diào)用函數(shù) early_init_dt_scan_root，解析根節(jié)點(diǎn)的屬性“#address-cells”得到地址的單元數(shù)量，保存在全局變量 dt_root_addr_cells 中；解析根節(jié)點(diǎn)的屬性“#size-cells”得到長(zhǎng)度的單元數(shù)量，保存在全局變量 dt_root_size_cells 中。

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

函數(shù) early_init_dt_scan_memory 負(fù)責(zé)解析“memory”節(jié)點(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" 節(jié)點(diǎn) */ 10 if (type == NULL) { 11 /* 如果沒有屬性“device_type”，判斷節(jié)點(diǎn)名稱是不是“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 行代碼，解析節(jié)點(diǎn)的屬性“device_type”。

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

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

第 26～37 行代碼，解析出每塊內(nèi)存的起始地址和大小后，調(diào)用函數(shù) early_init_dt_add_memory_arch。

函數(shù) 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); }

函數(shù) early_init_dt_add_memory_arch 對(duì)起始地址和長(zhǎng)度做了檢查以后，調(diào)用函數(shù)memblock_add 把物理內(nèi)存范圍添加到 memblock.memory 中。