Linux 引導內存分配器
linux 內存三大分配器：引導內存分配器，夥伴分配器，slab 分配器
一、引導內存分配器
1. 引導內存分配器的作用因爲內核裏面有很多內存結構體，不可能在靜態編譯階段就靜態初始化所有的這些內存結構體。另外，在系統啓動過程中，系統啓動後的物理內存分配器本身也需要初始化，如夥伴分配器，那麼夥伴分配器如何獲取內存來初始化自己呢 ？爲了達到這個目標，我們先實現一個滿足要求的但是可能效率不高的笨傢伙，引導內存分配器。用它來負責系統初始化初期的內存管理, 最重要的, 用它來初始化我們內存的數據結構, 直到我們真正的內存管理器被初始化完成並能投入使用, 我們將舊的內存管理器丟掉。
2. 引導內存分配器的原理在 Linux 內核中使用 struct bootmem_data 來描述一個引導內存分配，其節點結構下的一個成員，也就是說每一個節點都有一個引導內存分配。 引導內存分配使用 struct bootmem_data 結構中的 node_bootmem_map 這個 bitmap 來呈現 memory 的狀態，一個 bit 代表一個物理頁框，也就是用 struct page，如果一個 bit 爲 1，表示該 page 已經被分配了，如果 bit 是 0，則表示該 page 未被分配。爲了能夠滿足比一個 page 還小的內存塊的分配，引導內存分配器會使用 last_pos 來記住上次分配所使用的 PFN 以及上次分配所使用的 page 內的偏移: last_offset, 下次分配的時候結合 last_pos 和 last_offset 將細小的內存塊分配儘量集中在相同的 page 中。
3 引導內存分配器的缺點儘管引導內存分配器不會造成嚴重的內存碎片，但是每次分配過程需要線性掃描搜索內存來滿足當前的分配。因爲是檢查 bitmap，所以代價比較昂貴，尤其是最先適配（first fit）算法傾向將小塊內存放置在物理內存開頭，但是這些內存區域在分配大塊內存時，也需要掃描，所以該過程十分浪費。所以早期內存分配器在系統啓動後就被棄用的原因。
4.bootmem 和 memblock 的比較但是 bootmem 也有很多問題. 最明顯的就是外碎片的問題, 因此內核維護了 memblock 內存分配器, 同時用 memblock 實現了一份 bootmem 相同的兼容 API, 即 nobootmem, Memblock 以前被定義爲 Logical Memory Block(邏輯內存塊), 但根據 Yinghai Lu 的補丁, 它被重命名爲 memblock. 並最終替代 bootmem 成爲初始化階段的內存管理器。 bootmem 是通過位圖來管理，位圖存在地地址段, 而 memblock 是在高地址管理內存, 維護兩個鏈表, 即 memory 和 reserved。 memory 鏈表維護系統的內存信息 (在初始化階段通過 bios 獲取的), 對於任何內存分配, 先去查找 memory 鏈表, 然後在 reserve 鏈表上記錄 (新增一個節點，或者合併) bootmem 和 memblock 都是就近查找可用的內存， bootmem 是從低到高找， memblock 是從高往低找。 在 boot 傳遞給 kernel memory bank 相關信息後，kernel 這邊會以 memblcok 的方式保存這些信息，當夥伴系統沒有起來之前，在內核中也是要有一套機制來管理 memory 的申請和釋放。linux 內核可以通過宏定義選擇 nobootmem 或者 bootmem 來在夥伴起來之前管理內存。這兩種機制對提供的 API 是一致的，因此對用戶是透明的
5.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;//最後一次分配的頁面內的偏移量（字節）;如果爲0，則使用的頁面已滿
unsigned long hint_idx;//最後一次分配的物理頁，下次優先考慮從這個物理頁分配
struct list_head list;//按內存地址排序鏈表頭
} bootmem_data_t;bootmem 接口函數： 1）bootmem 分配內存函數：alloc_bootmem 2）bootmem 釋放內存函數：free_bootmem
#define alloc_bootmem(x) \
__alloc_bootmem(x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)
void __init free_bootmem(unsigned long physaddr, unsigned long size)
{
unsigned long start, end;
kmemleak_free_part_phys(physaddr, size);//釋放映射的內存
start = PFN_UP(physaddr);//查找到起始位置的物理頁
end = PFN_DOWN(physaddr + size);//查找到結束爲止的物理頁
mark_bootmem(start, end, 0, 0);//把釋放的物理頁對應的位清零
}6.memblock 結構解析 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
};
struct memblock_type {
unsigned long cnt;//區域數量
unsigned long max;//分配區域的大小
phys_addr_t total_size;//所有區域的大小
struct memblock_region *regions;//區域數組指向區域數組
char *name;//內存類型符號名
};
struct memblock_region {
phys_addr_t base;//起始物理地址
phys_addr_t size;//長度
enum memblock_flags flags;//內存區域標誌屬性
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
int nid;//節點編號
#endif
};
//內存區域標誌屬性定義
enum memblock_flags {
MEMBLOCK_NONE = 0x0,//表示沒有特殊要求區域
MEMBLOCK_HOTPLUG = 0x1,//表示可以熱插拔的區域
MEMBLOCK_MIRROR = 0x2,//表示鏡像的區域，將內存數據做兩份複製，分配放在主內存和鏡像內存中
MEMBLOCK_NOMAP = 0x4,//表示不添加到內核直接映射區域，即線性映射區
};memblock 體系的結構：
int __init_memblock memblock_add(phys_addr_t base, phys_addr_t size)
{
phys_addr_t end = base + size - 1;
memblock_dbg("memblock_add: [%pa-%pa] %pF\n",
&base, &end, (void *)_RET_IP_);
//直接調用memblock_add_range將內存區塊添加到memblock.memory進行管理
return memblock_add_range(&memblock.memory, base, size, MAX_NUMNODES, 0);
}我們繼續追 memblock_add_range：
int __init_memblock memblock_add_range(struct memblock_type *type,
phys_addr_t base, phys_addr_t size,
int nid, enum memblock_flags flags)
{
bool insert = false;
phys_addr_t obase = base;
phys_addr_t end = base + memblock_cap_size(base, &size);
int idx, nr_new;
struct memblock_region *rgn;
if (!size)
return 0;
if (type->regions[0].size == 0) {
WARN_ON(type->cnt != 1 || type->total_size);
type->regions[0].base = base;
type->regions[0].size = size;
type->regions[0].flags = flags;
memblock_set_region_node(&type->regions[0], nid);
type->total_size = size;
return 0;
}
repeat:
/*
* The following is executed twice. Once with %false @insert and
* then with %true. The first counts the number of regions needed
* to accommodate the new area. The second actually inserts them.
*/
base = obase;
nr_new = 0;
//遍歷所有內存塊，與新的內存塊比較
for_each_memblock_type(idx, type, rgn) {
phys_addr_t rbase = rgn->base;
phys_addr_t rend = rbase + rgn->size;
if (rbase >= end)//新加入的內存塊的結束地址已經到了則遍歷結束
break;
if (rend <= base)//即加入的內存塊的起始地址還沒到則遍歷下一塊
continue;
/*
* @rgn overlaps. If it separates the lower part of new
* area, insert that portion.
*/
//如果新加入的內存起始地址已經到了，但是還沒到遍歷的內存則插入
if (rbase > base) {
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
WARN_ON(nid != memblock_get_region_node(rgn));
#endif
WARN_ON(flags != rgn->flags);
nr_new++;
if (insert)
//添加內存區域，也就是填充struct memblock_region而已
memblock_insert_region(type, idx++, base,
rbase - base, nid,
flags);
}
/* area below @rend is dealt with, forget about it */
base = min(rend, end);
}
/* insert the remaining portion */
if (base < end) {
nr_new++;
if (insert)
memblock_insert_region(type, idx, base, end - base,
nid, flags);
}
//如果需要加入的內存塊個數爲0則返回，不需要第二次遍歷執行加入操作
if (!nr_new)
return 0;
/*
* If this was the first round, resize array and repeat for actual
* insertions; otherwise, merge and return.
*/
//第一次會進入，判斷內存區域塊是否達到上限，是則退出，否則回到repeat
//因爲insert參數原因，第一次沒有真正插入，第二次纔會真正的插入
if (!insert) {
while (type->cnt + nr_new > type->max)
if (memblock_double_array(type, obase, size) < 0)
return -ENOMEM;
insert = true;
goto repeat;
} else {
memblock_merge_regions(type);//合併相鄰且沒有縫隙的內存區域
return 0;
}
}2）memblock 刪除內存區域函數: memblock_remove
int __init_memblock memblock_remove(phys_addr_t base, phys_addr_t size)
{
phys_addr_t end = base + size - 1;
memblock_dbg("memblock_remove: [%pa-%pa] %pS\n",
&base, &end, (void *)_RET_IP_);
return memblock_remove_range(&memblock.memory, base, size);
}memblock_remove_range：
static int __init_memblock memblock_remove_range(struct memblock_type *type,
phys_addr_t base, phys_addr_t size)
{
int start_rgn, end_rgn;
int i, ret;
//要刪除的內存區域內存區內的內存塊存在重疊部分，把這部分需要獨立出來
ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
if (ret)
return ret;
//根據要刪除內存區的索引號，刪除內存區塊
for (i = end_rgn - 1; i >= start_rgn; i--)
memblock_remove_region(type, i);
return 0;
}3）memblock 分配內存函數: memblock_alloc
phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
{
return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
}
phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
{
phys_addr_t alloc;
alloc = __memblock_alloc_base(size, align, max_addr);
if (alloc == 0)
panic("ERROR: Failed to allocate %pa bytes below %pa.\n",
&size, &max_addr);
return alloc;
}
phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
{
return memblock_alloc_base_nid(size, align, max_addr, NUMA_NO_NODE,
MEMBLOCK_NONE);
}
phys_addr_t __init memblock_alloc_base_nid(phys_addr_t size,
phys_addr_t align, phys_addr_t max_addr,
int nid, enum memblock_flags flags)
{
return memblock_alloc_range_nid(size, align, 0, max_addr, nid, flags);
}
static phys_addr_t __init memblock_alloc_range_nid(phys_addr_t size,
phys_addr_t align, phys_addr_t start,
phys_addr_t end, int nid,
enum memblock_flags flags)
{
phys_addr_t found;
if (!align)
align = SMP_CACHE_BYTES;
//在給定範圍和節點內找一塊空區域
found = memblock_find_in_range_node(size, align, start, end, nid,
flags);
//memblock_reserve是把找到的空區域添加到memblock.reserved中，表示已經用了
if (found && !memblock_reserve(found, size)) {
/*
* The min_count is set to 0 so that memblock allocations are
* never reported as leaks.
*/
//一個內存塊分配物理內存的通知
kmemleak_alloc_phys(found, size, 0, 0);
return found;
}
return 0;
}4）memblock 釋放內存函數: memblock_free
int __init_memblock memblock_free(phys_addr_t base, phys_addr_t size)
{
phys_addr_t end = base + size - 1;
memblock_dbg(" memblock_free: [%pa-%pa] %pF\n",
&base, &end, (void *)_RET_IP_);
//通知釋放部分內存塊
kmemleak_free_part_phys(base, size);
return memblock_remove_range(&memblock.reserved, base, size);
}
static int __init_memblock memblock_remove_range(struct memblock_type *type,
phys_addr_t base, phys_addr_t size)
{
int start_rgn, end_rgn;
int i, ret;
//要刪除的內存區域內存區內的內存塊存在重疊部分，把這部分需要獨立出來
ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
if (ret)
return ret;
//根據要刪除內存區的索引號，刪除內存區塊
for (i = end_rgn - 1; i >= start_rgn; i--)
memblock_remove_region(type, i);
return 0;
}7.memblock 啓動流程 1）解析設備樹中的 / memory，把所有物理內存添加到 memblock 2）在 memblock_init 中初始化 memblock linux 啓動從 init/main.c 文件的 start_kernel 函數開始，然後從文件 setup_arch（arch/arm64/kernel/setup.c 文件中）函數檢測處理器類型，初始化處理器和內存，其中的 arm64_memblock_init（arch/arm64/mm/init.c 文件中）函數就是 arm64 架構的 memblock 初始化流程。
void __init arm64_memblock_init(void)
{
const s64 linear_region_size = -(s64)PAGE_OFFSET;
/* Handle linux,usable-memory-range property */
//解析設備樹文件的內存節點
fdt_enforce_memory_region();
/* Remove memory above our supported physical address size */
//刪除超出我們支持的物理地址大小的內存
memblock_remove(1ULL << PHYS_MASK_SHIFT, ULLONG_MAX);
/*
* Ensure that the linear region takes up exactly half of the kernel
* virtual address space. This way, we can distinguish a linear address
* from a kernel/module/vmalloc address by testing a single bit.
*/
BUILD_BUG_ON(linear_region_size != BIT(VA_BITS - 1));
/*
* Select a suitable value for the base of physical memory.
*/
//全局變量memstart_addr記錄了內存的起始物理地址
memstart_addr = round_down(memblock_start_of_DRAM(),
ARM64_MEMSTART_ALIGN);
/*
* Remove the memory that we will not be able to cover with the
* linear mapping. Take care not to clip the kernel which may be
* high in memory.
*/
//把線性映射區無法覆蓋的物理內存範圍從memblock中刪除
memblock_remove(max_t(u64, memstart_addr + linear_region_size,
__pa_symbol(_end)), ULLONG_MAX);
if (memstart_addr + linear_region_size < memblock_end_of_DRAM()) {
/* ensure that memstart_addr remains sufficiently aligned */
memstart_addr = round_up(memblock_end_of_DRAM() - linear_region_size,
ARM64_MEMSTART_ALIGN);
memblock_remove(0, memstart_addr);
}
/*
* Apply the memory limit if it was set. Since the kernel may be loaded
* high up in memory, add back the kernel region that must be accessible
* via the linear mapping.
*/
//如果設置了內存限制，要根據限制使用內存
if (memory_limit != PHYS_ADDR_MAX) {
memblock_mem_limit_remove_map(memory_limit);//把超出限制的內存移除
memblock_add(__pa_symbol(_text), (u64)(_end - _text));//添加可以使用的內存
}
if (IS_ENABLED(CONFIG_BLK_DEV_INITRD) && initrd_start) {
/*
* Add back the memory we just removed if it results in the
* initrd to become inaccessible via the linear mapping.
* Otherwise, this is a no-op
*/
u64 base = initrd_start & PAGE_MASK;
u64 size = PAGE_ALIGN(initrd_end) - base;
/*
* We can only add back the initrd memory if we don't end up
* with more memory than we can address via the linear mapping.
* It is up to the bootloader to position the kernel and the
* initrd reasonably close to each other (i.e., within 32 GB of
* each other) so that all granule/#levels combinations can
* always access both.
*/
if (WARN(base < memblock_start_of_DRAM() ||
base + size > memblock_start_of_DRAM() +
linear_region_size,
"initrd not fully accessible via the linear mapping -- please check your bootloader ...\n")) {
initrd_start = 0;
} else {
memblock_remove(base, size); /* clear MEMBLOCK_ flags */
memblock_add(base, size);
memblock_reserve(base, size);
}
}
if (IS_ENABLED(CONFIG_RANDOMIZE_BASE)) {
extern u16 memstart_offset_seed;
u64 range = linear_region_size -
(memblock_end_of_DRAM() - memblock_start_of_DRAM());
/*
* If the size of the linear region exceeds, by a sufficient
* margin, the size of the region that the available physical
* memory spans, randomize the linear region as well.
*/
if (memstart_offset_seed > 0 && range >= ARM64_MEMSTART_ALIGN) {
range /= ARM64_MEMSTART_ALIGN;
memstart_addr -= ARM64_MEMSTART_ALIGN *
((range * memstart_offset_seed) >> 16);
}
}
/*
* Register the kernel text, kernel data, initrd, and initial
* pagetables with memblock.
*/
//把內核鏡像佔用的內存添加到memblock的預留區中，表示預留了不再分配出去
memblock_reserve(__pa_symbol(_text), _end - _text);
#ifdef CONFIG_BLK_DEV_INITRD
if (initrd_start) {
memblock_reserve(initrd_start, initrd_end - initrd_start);
/* the generic initrd code expects virtual addresses */
initrd_start = __phys_to_virt(initrd_start);
initrd_end = __phys_to_virt(initrd_end);
}
#endif
//掃描設備樹中的保留內存區域並添加到memblock的預留區域中
early_init_fdt_scan_reserved_mem();
/* 4GB maximum for 32-bit only capable devices */
if (IS_ENABLED(CONFIG_ZONE_DMA32))
arm64_dma_phys_limit = max_zone_dma_phys();
else
arm64_dma_phys_limit = PHYS_MASK + 1;
reserve_crashkernel();
reserve_elfcorehdr();
high_memory = __va(memblock_end_of_DRAM() - 1) + 1;
dma_contiguous_reserve(arm64_dma_phys_limit);
memblock_allow_resize();
}最後，引導內存分配器退休，會將物理內存填充到夥伴分配器中，移交給夥伴分配器進行管理。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3utaHTPMJZbTfNUBNRBkgA