在内存管理的上下文中, 初始化(initialization)可以有多种含义. 在许多CPU上, 必须显式设置适用于Linux内核的内存模型. 例如在x86_32上需要切换到保护模式, 然后内核才能检测到可用内存和寄存器.

而我们今天要讲的bootmem分配器就是系统初始化阶段使用的内存分配器.

为什么要使用bootmem分配器，内存管理不是有buddy系统和slab分配器吗？由于在系统初始化的时候需要执行一些内存管理，内存分配的任务，这个时候buddy系统，slab分配器等并没有被初始化好，此时就引入了一种内存管理器bootmem分配器在系统初始化的时候进行内存管理与分配，当buddy系统和slab分配器初始化好后，在mem_init()中对bootmem分配器进行释放，内存管理与分配由buddy系统，slab分配器等进行接管。

bootmem分配器使用一个bitmap来标记物理页是否被占用，分配的时候按照第一适应的原则，从bitmap中进行查找，如果这位为1，表示已经被占用，否则表示未被占用。为什么系统运行的时候不使用bootmem分配器呢？bootmem分配器每次在bitmap中进行线性搜索，效率非常低，而且在内存的起始端留下许多小的空闲碎片，在需要非常大的内存块的时候，检查位图这一过程就显得代价很高。bootmem分配器是用于在启动阶段分配内存的，对该分配器的需求集中于简单性方面，而不是性能和通用性.

一、前景回顾

1.1 Linux内存管理的层次结构

Linux把物理内存划分为三个层次来管理

为了支持NUMA模型，也即CPU对不同内存单元的访问时间可能不同，此时系统的物理内存被划分为几个节点(node), 一个node对应一个内存簇bank，即每个内存簇被认为是一个节点

首先, 内存被划分为结点. 每个节点关联到系统中的一个处理器, 内核中表示为pg_data_t的实例. 系统中每个节点被链接到一个以NULL结尾的pgdat_list链表中<而其中的每个节点利用pg_data_tnode_next字段链接到下一节．而对于PC这种UMA结构的机器来说, 只使用了一个成为contig_page_data的静态pg_data_t结构.

接着各个节点又被划分为内存管理区域, 一个管理区域通过struct zone_struct描述, 其被定义为zone_t, 用以表示内存的某个范围, 低端范围的16MB被描述为ZONE_DMA, 某些工业标准体系结构中的(ISA)设备需要用到它, 然后是可直接映射到内核的普通内存域ZONE_NORMAL,最后是超出了内核段的物理地址域ZONE_HIGHMEM, 被称为高端内存.　是系统中预留的可用内存空间, 不能被内核直接映射.

最后页帧(page frame)代表了系统内存的最小单位, 堆内存中的每个页都会创建一个struct page的一个实例. 传统上，把内存视为连续的字节，即内存为字节数组，内存单元的编号(地址)可作为字节数组的索引. 分页管理时，将若干字节视为一页，比如4K byte. 此时，内存变成了连续的页，即内存为页数组，每一页物理内存叫页帧，以页为单位对内存进行编号，该编号可作为页数组的索引，又称为页帧号.

1.2 start_kernel启动过程

在初始化过程中, 还必须建立内存管理的数据结构, 以及很多事务. 因为内核在内存管理完全初始化之前就需要使用内存. 在系统启动过程期间, 使用了额外的简化悉尼股市的内存管理模块, 然后在初始化完成后, 将旧的模块丢弃掉.

首先我们来看看start_kernel是如何初始化系统的, start_kerne定义在init/main.c?v=4.7, line 479

其代码很复杂, 我们只截取出其中与内存管理初始化相关的部分, 如下所示

asmlinkage __visible void __init start_kernel(void)

{

setup_arch(&command_line);

mm_init_cpumask(&init_mm);

setup_per_cpu_areas();

build_all_zonelists(NULL, NULL);

page_alloc_init();

/*

* These use large bootmem allocations and must precede

* mem_init();

* kmem_cache_init();

*/

mm_init();

kmem_cache_init_late();

kmemleak_init();

setup_per_cpu_pageset();

rest_init();

}

1.3 setup_arch设置

二、引导内存分配器bootmem概述

由于硬件配置多种多样, 所以在编译时就静态初始化所有的内核存储结构是不现实的.

bootmem分配器是系统启动初期的内存分配方式，在耳熟能详的伙伴系统建立前内存都是利用bootmem分配器来分配的，伙伴系统框架建立起来后，bootmem会过度到伙伴系统.

2.1 初始化阶段的引导内存分配器bootmem

在启动过程期间, 尽管内存管理尚未初始化, 但是内核仍然需要分配内存以创建各种数据结构. 因此在系统启动过程期间, 内核使用了一个额外的简化形式的内存管理模块引导内存分配器(boot memory allocator–bootmem分配器), 用于在启动阶段早期分配内存, 而在系统初始化完成后, 该分配器被内核抛弃, 然后初始化了一套新的更加完善的内存分配器.

显然, 对该内存分配器的需求集中于简单性方面,　而不是性能和通用性, 它仅用于初始化阶段. 因此内核开发者决定实现一个最先适配(first-first)分配器用于在启动阶段管理内存. 这是可能想到的最简单的方式.

引导内存分配器(boot memory allocator–bootmem分配器)基于最先适配(first-first)分配器的原理(这儿是很多系统的内存分配所使用的原理), 使用一个位图来管理页, 以位图代替原来的空闲链表结构来表示存储空间, 位图的比特位的数目与系统中物理内存页面数目相同. 若位图中某一位是1, 则标识该页面已经被分配(已用页), 否则表示未被占有(未用页).

在需要分配内存时, 分配器逐位的扫描位图, 直至找到一个能提供足够连续页的位置, 即所谓的最先最佳(first-best)或最先适配位置.

该分配机制通过记录上一次分配的页面帧号(PFN)结束时的偏移量来实现分配大小小于一页的空间, 连续的小的空闲空间将被合并存储在一页上.

2.2 为什么需要bootmem

2.3 为什么在系统运行时抛弃bootmem

当系统运行时, 为何不继续使用bootmem分配机制呢?

其中一个关键原因在于 : 但它每次分配都必须从头扫描位图, 每次通过对内存域进行线性搜索来实现分配.

其次首先适应算法容易在内存的起始断留下许多小的空闲碎片, 在需要分配较大的空间页时,　检查位图的成本将是非常高的.

引导内存分配器bootmem分配器简单却非常低效,　因此在内核完全初始化之后,　不能将该分配器继续欧诺个与内存管理,　而伙伴系统(连同slab, slub或者slob分配器)是一个好很多的备选方案．

三、引导内存分配器数据结构

内核用bootmem_data表示引导内存区域

即使是初始化用的最先适配分配器也必须使用一些数据结构存, 内核为系统中每一个结点都提供了一个struct bootmem_data结构的实例, 用于bootmem的内存管理. 它含有引导内存分配器给结点分配内存时所需的信息. 当然, 这时候内存管理还没有初始化, 因而该结构所需的内存是无法动态分配的, 必须在编译时分配给内核.

在UMA系统上该分配的实现与CPU无关, 而NUMA系统内存结点与CPU相关联, 因此采用了特定体系结构的解决方法.

【bootmem_data描述内存引导区】

bootmem_data的结构定义在include/linux/bootmem.h?v=4.7, line 28, 其定义如下所示

#ifndef CONFIG_NO_BOOTMEM

/*

* node_bootmem_map is a map pointer - the bits represent all physical

* memory pages (including holes) on the node.

*/

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;

extern bootmem_data_t bootmem_node_data[];

#endif

bootmem的位图建立在从start_pfn开始的地方, 也就是说, 内核映像终点_end上方的地方. 这个位图用来管理低区（例如小于 896MB), 因为在0到896MB的范围内, 有些页面可能保留, 有些页面可能有空洞, 因此, 建立这个位图的目的就是要搞清楚哪一些物理页面是可以动态分配的

node_bootmem_map就是一个指向位图的指针. node_min_pfn表示存放bootmem位图的第一个页面(即内核映像结束处的第一个页面)

node_low_pfn 表示物理内存的顶点, 最高不超过896MB

四、初始化引导分配器

系统是从start_kernel开始启动的, 在启动过程中通过调用体系结构相关的setup_arch函数, 来获取初始化引导内存分配器所需的参数信息, 各种体系结构都有对应的函数来获取这些信息, 在获取信息完成后, 内核首先初始化了bootmem自身, 然后接着又用bootmem分配和初始化了内存结点和管理域, 因此初始化bootmem的工作主要分成两步

初始化bootmem自身的数据结构

用bootmem初始化内存结点管理域

bootmem分配器的初始化是一个特定于体系结构的过程, 此外还取决于系统的内存布局

系统是从start_kernel开始启动的, 在启动过程中通过调用体系结构相关的setup_arch函数, 来获取初始化引导内存分配器所需的参数信息, 各种体系结构都有对应的函数来获取这些信息.

4.1 IA-32的初始化

在使用bootmem, 内核在setup_arch函数中通过setup_memory来分析检测到的内存区, 以找到低端内存区中最大的页帧号。由于高端内存处理太麻烦，由此对bootmem分配器无用。全局变量max_low_pfn保存了可映射的最高页的编号。内核会在启动日志中报告找到的内存的数量。

五、bootmem分配内存接口

bootmem提供了各种函数用于在初始化期间分配内存.

尽管mm/bootmem.c中提供了一些了的内存分配函数，但是这些函数大多数以__下划线开头, 这个标识告诉我们尽量不要使用他们, 他们过于底层, 往往是不安全的, 因此特定于某个体系架构的代码并没有直接调用它们，而是通过linux/bootmem.h提供的一系列的宏

5.1 NUMA结构的分配函数

首先我们讲解一下子在UMA系统中, 可供使用的函数.

5.1.1 从ZONE_NORMAL区域分配函数

下面列出的这些函数可以从ZONE_NORMAL内存域分配指向大小的内存

这些函数的定义在include/linux/bootmem.h

http://lxr.free-electrons.com/source/include/linux/bootmem.h?v=4.7#L122

#define alloc_bootmem(x) \

__alloc_bootmem(x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)

#define alloc_bootmem_align(x, align) \

__alloc_bootmem(x, align, BOOTMEM_LOW_LIMIT)

#define alloc_bootmem_nopanic(x) \

__alloc_bootmem_nopanic(x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)

#define alloc_bootmem_pages(x) \

__alloc_bootmem(x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)

#define alloc_bootmem_pages_nopanic(x) \

__alloc_bootmem_nopanic(x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)

5.1.2 从ZONE_DMA区域分配函数

下面的函数可以从ZONE_DMA中分配内存

这些函数的定义在include/linux/bootmem.h

#define alloc_bootmem_low(x) \

__alloc_bootmem_low(x, SMP_CACHE_BYTES, 0)

#define alloc_bootmem_low_pages_nopanic(x) \

__alloc_bootmem_low_nopanic(x, PAGE_SIZE, 0)

#define alloc_bootmem_low_pages(x) \

__alloc_bootmem_low(x, PAGE_SIZE, 0)

5.1.3 函数实现方式

通过分析我们可以看到alloc_bootmem_nopanic的底层实现函数__alloc_bootmem_nopanic实现了一套最基础的内存分配函数, 而___alloc_bootmem函数则通过___alloc_bootmem_nopanic函数实现, 它首先通过___alloc_bootmem_nopanic函数分配内存，但是一旦内存分配失败，系统将通过panic("Out of memory")抛出信息，并停止运行, 其他的内存分配函数除了都是基于alloc_bootmem_nopanic族的函数, 都是基于__alloc_bootmem的. 那么所有的函数都是间接的基于___alloc_bootmem_nopanic实现的

static void * __init ___alloc_bootmem(unsigned long size, unsigned long align,

unsigned long goal, unsigned long limit)

{

void *mem = ___alloc_bootmem_nopanic(size, align, goal, limit);

if (mem)

return mem;

/*

* Whoops, we cannot satisfy the allocation request.

*/

pr_alert("bootmem alloc of %lu bytes failed!\n", size);

panic("Out of memory");

return NULL;

}

所有这些分配函数最后都是间接的通过___alloc_bootmem_nopanic函数来完成内存分配的, 该函数定义在mm/bootmem.c?v=4.7, line 632

static void * __init ___alloc_bootmem_nopanic(unsigned long size,

unsigned long align,

unsigned long goal,

unsigned long limit)

{

void *ptr;

restart:

ptr = alloc_bootmem_core(size, align, goal, limit);

if (ptr)

return ptr;

if (goal) {

goal = 0;

goto restart;

}

return NULL;

}

5.2 NUMA结构下的分配函数

5.2.1 分配函数接口

在NUMA系统上, 基本的API是相同的, 但是函数增加了_node后缀, 与UMA系统的函数相比, 还需要一些额外的参数, 用于指定内存分配的结点.

这些函数定义在include/linux/bootmem.h和mm/bootmem.c

// http://lxr.free-electrons.com/source/include/linux/bootmem.h?v=4.7#L132

#define alloc_bootmem_node(pgdat, x) \

__alloc_bootmem_node(pgdat, x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)

#define alloc_bootmem_node_nopanic(pgdat, x) \

__alloc_bootmem_node_nopanic(pgdat, x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)

#define alloc_bootmem_pages_node(pgdat, x) \

__alloc_bootmem_node(pgdat, x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)

#define alloc_bootmem_pages_node_nopanic(pgdat, x) \

__alloc_bootmem_node_nopanic(pgdat, x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)

// http://lxr.free-electrons.com/source/include/linux/bootmem.h?v=4.7#L147

__alloc_bootmem_low(x, PAGE_SIZE, 0)

#define alloc_bootmem_low_pages_node(pgdat, x) \

__alloc_bootmem_low_node(pgdat, x, PAGE_SIZE, 0)

5.2.2 函数实现方式

NUMA结构下这些分配接口的实现方式与UMA结构下类似, 这些都是__alloc_bootmem_node或者__alloc_bootmem_node_nopanic, 而___alloc_bootmem_node函数则先通过___alloc_bootmem_node_nopanic分配内存空间, 如果出错则打印panic("Out of memory"), 并终止

void * __init ___alloc_bootmem_node(pg_data_t *pgdat, unsigned long size,

unsigned long align, unsigned long goal,

unsigned long limit)

{

void *ptr;

ptr = ___alloc_bootmem_node_nopanic(pgdat, size, align, goal, 0);

if (ptr)

return ptr;

pr_alert("bootmem alloc of %lu bytes failed!\n", size);

panic("Out of memory");

return NULL;

}

那么我们现在就进入分配函数的核心___alloc_bootmem_node_nopanic, 它定义在mm/nobootmem.c?v=4.7, line 317

void * __init ___alloc_bootmem_node_nopanic(pg_data_t *pgdat,

unsigned long size, unsigned long align,

unsigned long goal, unsigned long limit)

{

void *ptr;

if (WARN_ON_ONCE(slab_is_available()))

return kzalloc(size, GFP_NOWAIT);

again:

/* do not panic in alloc_bootmem_bdata() */

if (limit && goal + size > limit)

limit = 0;

ptr = alloc_bootmem_bdata(pgdat->bdata, size, align, goal, limit);

if (ptr)

return ptr;

ptr = alloc_bootmem_core(size, align, goal, limit);

if (ptr)

return ptr;

if (goal) {

goal = 0;

goto again;

}

return NULL;

}

我们可以看到UMA下底层的分配函数___alloc_bootmem_nopanic与NUMA下的函数___alloc_bootmem_node_nopanic实现方式基本类似. 参数也基本相同

5.3 __alloc_memory_core进行内存分配

__alloc_memory_core函数的功能相对而言很广泛(在启动期间不需要太高的效率), 该函数基于最先适配算法, 但是该分配器不仅可以分配整个内存页, 还能分配页的一部分. 它遍历所有的bootmem list然后找到一个合适的内存区域, 然后通过 alloc_bootmem_bdata来完成分配

该函数主要执行如下操作

list_for_each_entry从goal开始扫描为图, 查找满足分配请求的空闲内存区

然后通过alloc_bootmem_bdata完成内存的分配

如果目标页紧接着上一次分配的页即last_end_off, 则内核会判断所需的内存(包括对齐数据所需的内存)是否能够在上一页分配或者从上一页开始分配

新分配的页在位图中对应位置设置为1,, 如果该页未完全分配, 则相应的偏移量保存在bootmem_data->last_end_off中; 否则, 该值设为0

六、bootmem释放内存

内核提供了free_bootmem函数来释放内存

它需要两个参数：需要释放的内存区的起始地址和长度。不出意外，NUMA系统上等价函数的名称为free_bootmem_node，它需要一个额外的参数来指定结点

// http://lxr.free-electrons.com/source/mm/bootmem.c?v=4.7#L422

void free_bootmem(unsigned long addr, unsigned long size);

void free_bootmem_node(pg_data_t *pgdat, unsigned long addr, unsigned long size);

七、停用bootmem

在系统初始化进行到伙伴系统分配器能够承担内存管理的责任后，必须停用bootmem分配器，毕竟不能同时用两个分配器管理内存。在UMA和NUMA系统上，停用是由free_all_bootmem完成。在伙伴系统建立之后，特定于体系结构的初始化代码需要调用这个函数

首先扫描bootmem分配器的页位图，释放每个未用的页。到伙伴系统的接口是__free_pages_bootmem函数，该函数对每个空闲页调用。该函数内部依赖于标准函数__free_page。它使得这些页并入伙伴系统的数据结构，在其中作为空闲页管理，可用于分配。

在页位图已经完全扫描之后，它占据的内存空间也必须释放。此后，只有伙伴系统可用于内存分配。