启动期间的内存管理之引导分配器bootmem--Linux内存管理(十)

2022-10-28 16:47:36

在内存管理的上下文中, 初始化(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分配器是用于在启动阶段分配内存的，对该分配器的需求集中于简单性方面，而不是性能和通用性.

2. 引导内存分配器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分配器)是一个好很多的备选方案．

3 引导内存分配器数据结构

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

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

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

3.1 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
字段 描述
node_min_pfn 节点起始地址
node_low_pfn 低端内存最后一个page的页帧号
node_bootmem_map 指向内存中位图bitmap所在的位置
last_end_off 分配的最后一个页内的偏移，如果该页完全使用，则offset为0
hint_idx
list

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

  • node_bootmem_map就是一个指向位图的指针. node_min_pfn表示存放bootmem位图的第一个页面(即内核映像结束处的第一个页面)
  • node_low_pfn 表示物理内存的顶点, 最高不超过896MB

4 初始化引导分配器

系统是从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保存了可映射的最高页的编号。内核会在启动日志中报告找到的内存的数量。

5 bootmem分配内存接口

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

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

5.1 NUMA结构的分配函数

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

5.1.1 从ZONE_NORMAL区域分配函数

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

函数 描述 定义
alloc_bootmem(size) 按照指定大小在ZONE_NORMAL内存域分配函数. 数据是对齐的, 这使得内存或者从可适用于L1高速缓存的理想位置开始 alloc_bootmem
__alloc_bootmem
___alloc_bootmem
alloc_bootmem_align(x, align) 同alloc_bootmem函数, 按照指定大小在ZONE_NORMAL内存域分配函数, 并按照align进行数据对齐 alloc_bootmem_align
基于__alloc_bootmem实现
alloc_bootmem_pages(size)) 同alloc_bootmem函数, 按照指定大小在ZONE_NORMAL内存域分配函数, 其中_page只是指定数据的对其方式从页边界(__pages)开始 alloc_bootmem_pages
基于__alloc_bootmem实现
alloc_bootmem_nopanic(size) alloc_bootmem_nopanic是最基础的通用的，一个用来尽力而为分配内存的函数，它通过list_for_each_entry在全局链表bdata_list中分配内存. alloc_bootmem和alloc_bootmem_nopanic类似，它的底层实现首先通过alloc_bootmem_nopanic函数分配内存，但是一旦内存分配失败，系统将通过panic(“Out of memory”)抛出信息，并停止运行 alloc_bootmem_nopanic
__alloc_bootmem_nopanic
___alloc_bootmem_nopanic

table th:nth-of-type(1){
width: 30%;
}

这些函数的定义在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中分配内存

函数 描述 定义
alloc_bootmem_low(size) 按照指定大小在ZONE_DMA内存域分配函数. 类似于alloc_bootmem, 数据是对齐的 alloc_bootmem_low_pages_nopanic
底层基于___alloc_bootmem
alloc_bootmem_low_pages_nopanic(size) 按照指定大小在ZONE_DMA内存域分配函数. 类似于alloc_bootmem_pages, 数据在页边界对齐, 并且错误后不输出panic alloc_bootmem_low_pages_nopanic
底层基于__alloc_bootmem_low_nopanic
alloc_bootmem_low_pages(size) 按照指定大小在ZONE_DMA内存域分配函数. 类似于alloc_bootmem_pages, 数据在页边界对齐 alloc_bootmem_low_pages
底层基于__alloc_bootmem_low_nopanic

这些函数的定义在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_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实现方式基本类似. 参数也基本相同

参数 描述
pgdat 要分配的结点， 在UMA结构中, 它被缺省掉了, 因此其默认值是contig_page_data
size 要分配的内存区域大小
align 要求对齐的字节数. 如果分配的空间比较小, 就用SMP_CACHE_BYTES， 它一般是硬件一级高速缓存的对齐方式, 而PAGE_SIZE则表示要在页边界对齐
goal 最佳分配的起始地址, 一般设置(normal)BOOTMEM_LOW_LIMIT / (low)ARCH_LOW_ADDRESS_LIMIT

5.2 __alloc_memory_core进行内存分配

函数 描述 定义
alloc_bootmem_bdata - mm/bootmem.c?v=4.7, line 500
alloc_bootmem_core - mm/bootmem.c, line 607

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

该函数主要执行如下操作

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

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

    1. 如果目标页紧接着上一次分配的页即last_end_off, 则内核会判断所需的内存(包括对齐数据所需的内存)是否能够在上一页分配或者从上一页开始分配
    2. 新分配的页在位图中对应位置设置为1,, 如果该页未完全分配, 则相应的偏移量保存在bootmem_data->last_end_off中; 否则, 该值设为0

6 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);

7 停用bootmem

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

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

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

上一篇：【LeetCode】107. Binary Tree Level Order Traversal II (2 solutions)


下一篇：Ownership qualifiers of Objective-C: In Details