===============================》内核新视界文章汇总《===============================

memblock 早期内存分配器详解

1 介绍

memblock 是内核在系统启动早期用于收集和管理物理内存的内存管理器，不同架构从不同地方收集物理内存（设备树，BIOS-e820 等）并添加到 memblock 中进行管理，在伙伴系统（Buddy System）接管内存管理之前为系统提供内存分配、预留等功能。在伙伴系统的接管内存管理时将 memblock中可用的空闲内存全部释放给伙伴系统，并丢弃 memblock 内存分配器。

注意：早期使用的引导内存分配器是bootmem，现在memblock取代了bootmem。

2 提供的接口

首先看看如何使用 memblock，memblock提供的能力可以分为四个部分：

1. 内存添加，移除，预留（memblock_add，memblock_reserve，memblock_remove 等）
2. 内存分配释放（memblock_alloc，memblock_phys_alloc_nid，memblock_free等）
3. 内存域遍历（for_each_memblock_type，for_each_mem_pfn_range等）
4. 其他杂项，包括内存最大限制，对齐调整，分配方向等

上述描述的接口每个部分都有许多变体存在这里取其他核心 API 介绍，其他的都是基于核心 API 的变体。

2.1 内存添加预留接口

（1）memblock_add_range

/* Low level functions */
int memblock_add_range(struct memblock_type *type,phys_addr_t base, phys_addr_t size,int nid, enum memblock_flags flags);所有物理内存添加都会经过该接口，将指定范围的内存添加到指定的 memblock_type 中。type：这里可以向 memory，reserved 和 physmem 添加。nid：对应 numa 节点 id，如果传入 MAX_NUMNODES 则表示没有 numa 节点。flags：对应的该内存区域的 flags，后面介绍。

memblock_add_range 接口有如下衍生：

memblock_add_range-> memblock_add_node-> memblock_add-> memblock_reserve

（2）memblock_add_node

int memblock_add_node(phys_addr_t base, phys_addr_t size, int nid);向 memory 这个 memblock_type 添加内存域，并标记该内存域对应 numa 节点号。memory 这个 type 记录了所有物理内存域。

（3）memblock_add

int memblock_add(phys_addr_t base, phys_addr_t size);同 memblock_add_node 类似，不过 nid 默认为 MAX_NUMNODES，内部检测到 nid = MAX_NUMNODES，会将 nid 重新赋值为 -1（NUMA_NO_NODE），表示没有 numa 节点。

（4）memblock_reserve

int memblock_reserve(phys_addr_t base, phys_addr_t size);向 reseved 这个 memblock_type 添加内存域。reseved 域记录了所有预留内存域，后续内存分配和释放内存给伙伴系统均要从 memory 域避开 reserved 域。

2.2 内存分配释放接口

（1）memblock_alloc_range

phys_addr_t __init memblock_alloc_range(phys_addr_t size, phys_addr_t align,phys_addr_t start, phys_addr_t end,enum memblock_flags flags);内存分配接口，返回分配到的物理地址。size: 要分配的内存大小
align: 分配的内存对齐大小，如果为 0，会报警告，并默认把 align 设置为 SMP_CACHE_BYTES（aarch64: 64 byte）。
start-end: 从哪一个范围内开始分配，当 end 等于 MEMBLOCK_ALLOC_ACCESSIBLE（0） 或者 MEMBLOCK_ALLOC_KASAN（1）时，则会限制能够分配最大地址为 memblock.current_limit（后续介绍）。

该接口主要用于连续内存分配器（Contiguous Memory Allocator，CMA）。
（2）memblock_alloc_base_nid

phys_addr_t memblock_alloc_base_nid(phys_addr_t size,phys_addr_t align, phys_addr_t max_addr,int nid, enum memblock_flags flags);类似于 memblock_alloc_range，不过这里 start 默认为 0，我们只需要传入 max_addr，以及对应numa节点 nid， nid 指明我们从哪一个 numa 节点分配内存。nid = NUMA_NO_NODE（-1）则从任意区域分配。

memblock_alloc_base_nid 具有许多变体

memblock_alloc_base_nid-> memblock_phys_alloc_nid-> memblock_phys_alloc_try_nid-> __memblock_alloc_base-> memblock_alloc_base-> memblock_phys_alloc对于分配接口没有指定 flags 的默认从 MEMBLOCK_NONE 中分配，如果配置了 mirror，则会从首先尝试从 MEMBLOCK_MIRROR（后续介绍） 中分配。* phys_addr_t memblock_phys_alloc_nid(phys_addr_t size, phys_addr_t align, int nid);
该接口主要指定 size, align，nid 分配内存，不过会有一个判断，如果第一次分配不到会检测 flags 中是否有 MEMBLOCK_MIRROR 标记，如果有则会清除该标记重新尝试分配，分配失败返回 0。* phys_addr_t memblock_phys_alloc_try_nid(phys_addr_t size, phys_addr_t align, int nid);
该接口是上述接口的衍生，即通过 memblock_phys_alloc_nid 还是无法分配内存则会将 nid 设置为 NUMA_NO_NODE（-1）尝试从任意 numa 节点分配，只要能够分配到，分配失败返回 0。* phys_addr_t __memblock_alloc_base(phys_addr_t size, phys_addr_t align,phys_addr_t max_addr);
该接口从指定的 size, align，max_addr 进行任意 numa 节点内存分配，分配失败返回 0。* phys_addr_t memblock_alloc_base(phys_addr_t size, phys_addr_t align,phys_addr_t max_addr);
该接口是上述 __memblock_alloc_base 的变体，功能相同，只是分配失败不会返回，而是直接 panic。* phys_addr_t memblock_phys_alloc(phys_addr_t size, phys_addr_t align);
该接口是 memblock_alloc_base 的变体，不用指定 max_addr，而是收内部 memblock.current_limit 的限制。 

（3）memblock_alloc_internal 是一个内存的分配接口，但也是我们常用的分配虚拟地址内存的最底层函数，其作用是返回一个分配到的物理内存对应的虚拟地址，内部与上述直接物理内存分配接口相比有诸多逻辑。

static void * __init memblock_alloc_internal(phys_addr_t size, phys_addr_t align,phys_addr_t min_addr, phys_addr_t max_addr,int nid)从指定的 size，align，min_addr，max_addr，nid 进行内存分配，如果成功分配则会返回物理内存对应的虚拟地址，如果失败返回 NULL。首先因为该接口是我们内核中最常用的普通内存分配接口，所以不需要指定 flags，而是默认从 MEMBLOCK_NONE 或者 MEMBLOCK_MIRROR 中选择。其次 nid 如果指定为 MAX_NUMNODES/NUMA_NO_NODE 则从任意 numa 节点分配，如果制定了 nid，则从对应 numa 节点分配，如果分配不到会回退为 nid = NUMA_NO_NODE（-1）再次尝试分配。max_addr 最大不能超过 memblock.current_limit 限制。如果 slab 在这时可用了，那么会直接从 slab 中分配（不过出现这种情况已经不正确了，内核会在这里发出一次警告）。如果通过上述逻辑还是分配不到内存还会判断 min_addr 是否为 0，不为零还会修改 min_addr = 0再次进行尝试分配。同样的到这里内存还是没有还会继续判断 flags 是否等于 MEMBLOCK_MIRROR，是则会修改 flags = MEMBLOCK_NONE，再次去尝试分配。

memblock_alloc_internal被封装为如下接口

memblock_alloc_internal-> memblock_alloc_try_nid_raw// 该接口返回的分配的虚拟地址，如果失败返回 NULL，并且对应分配的内存区域数据未作任何处理-> memblock_alloc_try_nid_nopanic// 和上述接口一样，不过会对分配的内存进行 memset，把内存区域清为 0。-> memblock_alloc_try_nid// 和 memblock_alloc_try_nid_raw 类似，不过分配不到会直接 panic。

对于 memblock_alloc_try_nid_nopanic 有如下常用变体：

static inline void * __init memblock_alloc_nopanic(phys_addr_t size,phys_addr_t align)
static inline void * __init memblock_alloc_low_nopanic(phys_addr_t size,phys_addr_t align)
static inline void * __init memblock_alloc_from_nopanic(phys_addr_t size,phys_addr_t align,phys_addr_t min_addr)
static inline void * __init memblock_alloc_node_nopanic(phys_addr_t size,int nid)

对于 memblock_alloc_try_nid有如下变体，也是我们最常见的变体：

static inline void * __init memblock_alloc(phys_addr_t size,  phys_addr_t align)
static inline void * __init memblock_alloc_from(phys_addr_t size,phys_addr_t align,phys_addr_t min_addr)
static inline void * __init memblock_alloc_low(phys_addr_t size,phys_addr_t align)
static inline void * __init memblock_alloc_node(phys_addr_t size,phys_addr_t align, int nid)

到这里基本把分配接口全部介绍完了，还有少许变体没有介绍，可以自行查看代码。

对于分配接口，内核只提供了一个 memblock_free接口用于释放分配的内存。

int memblock_free(phys_addr_t base, phys_addr_t size);

2.3 内存域遍历

该部分主要为系统提供了遍历这种内存域的方法。比如遍历所有可用内存域，对每个可用内存域进行虚拟内存映射等。

其中 for_each_mem_range，for_each_mem_range_rev属于内部使用遍历方式，其作用是正向或者逆向遍历 memory 域，并把每个找到的 memory 域和每一个 reserved域比较，避开 reserved域。主要用于遍历剩余的空闲内存域，下面介绍。

（1）for_each_free_mem_range

#define for_each_free_mem_range(i, nid, flags, p_start, p_end, p_nid)	\for_each_mem_range(i, &memblock.memory, &memblock.reserved,	\nid, flags, p_start, p_end, p_nid)指定要遍历的 nid，flags，返回每一个空闲域对应的 start，end，nid。

（2）for_each_free_mem_range_reverse
for_each_free_mem_range的反向遍历操作。
（3）for_each_memblock

#define for_each_memblock(memblock_type, region)					\for (region = memblock.memblock_type.regions;					\region < (memblock.memblock_type.regions + memblock.memblock_type.cnt);	\region++)遍历指定的 memblock_type 域，可以是 memory，reserved，physmem。返回对应的每一个 region。

（4）for_each_memblock_type

#define for_each_memblock_type(i, memblock_type, rgn)			\for (i = 0, rgn = &memblock_type->regions[0];			\i < memblock_type->cnt;					\i++, rgn = &memblock_type->regions[i])和 for_each_memblock 类似，唯一不同是多了一个 i，用于描述当前 region 的 index，作用是在域的合并分离时可以修改 i，用于重新操作当前域。

（5）for_each_mem_pfn_range

#define for_each_mem_pfn_range(i, nid, p_start, p_end, p_nid)		\for (i = -1, __next_mem_pfn_range(&i, nid, p_start, p_end, p_nid); \i >= 0; __next_mem_pfn_range(&i, nid, p_start, p_end, p_nid))逻辑类似于 for_each_memblock(memory, rgn) 。不过会返回每一个 region 的 start_pfn，end_pfn 和 nid。
__next_mem_pfn_range 内部会对每一个 region 的起始地址和结束地址进行 pfn 转换，方便伙伴系统内部使用（因为伙伴系统管理内存是按照 page 对齐的，所以对内存起始和结束地址都是需要 page 对齐的。）

2.4 其他杂项

这里包含大量杂项功能，包括标记内存域的 flags 属性，设置是自底向上分配还是自顶向下分配，标记是否允许扩容 region，对内存域调整对齐，限制内存域的最大分配地址等。

（1）memblock_mark_hotplug，memblock_mark_mirror，memblock_mark_nomap

标记某一段内存域为对应的 flags 属性。比如 memblock_mark_nomap 可以标记内存为 nomap，那么在遍历内存域进行内存映射时时可以跳过 nomap 标记的区域。

（2）memblock_free_all，reset_node_managed_pages，reset_all_zones_managed_pages

释放可用空闲内存到伙伴系统，以及一些助手程序。

（3）memblock_set_bottom_up

设置从底部还是顶部开始分配内存。

（4）memblock_phys_mem_size

总的物理内存大小

（5）memblock_reserved_size

总的预留物理内存大小

（5）memblock_start_of_DRAM，memblock_end_of_DRAM

物理内存域的起始与结束。

（6）memblock_enforce_memory_limit

强制限制内存的最大总量

（7）memblock_cap_memory_range

调整内存的使用范围

（8）memblock_mem_limit_remove_map

限制内存的最大总量并调整内存范围为 [0 - max_addr]

（9）memblock_set_current_limit

设置当前能分配的最大地址范围

（10）memblock_trim_memory

调整每个 region 的对齐

至此大部分接口介绍完毕，中间还存一些未介绍的，但是都比较简单一看就知道含义。

3 内部数据结构

首先来看一张网络上的结构数据图：

3.1 struct memblock

首先有一个全局的 struct memblock 结构体用于管理所有 memblock 元数据。

struct memblock {bool bottom_up;  /* is bottom up direction? */phys_addr_t current_limit;struct memblock_type memory;struct memblock_type reserved;
#ifdef CONFIG_HAVE_MEMBLOCK_PHYS_MAPstruct memblock_type physmem;
#endif
};

• bottom_up

​ 用于表示当前从内存底部开始分配还是从内存的顶部开始分配。

• current_limit

​ 表示当前分配内存的最大物理地址限制，默认时 PHYS_MAX_ADDR，即没有限制，可以通过 memblock_set_current_limit来修改该变量。

• struct memblock_type memory

​ 用于管理当前系统中所有内存的集合。

• struct memblock_type reserved

​ 用于管理当前系统中所有预留的内存集合。（reserved 应该是 memory 的子集）

• struct memblock_type physmem;

​ 该内存域由 CONFIG_HAVE_MEMBLOCK_PHYS_MAP 宏控制，目前主要用于 s390 的 crash dump 功能使用，后续不再介绍该域。

通过上述定义，从系统中收集到的所有内存都会添加到 memory 内存域中，而一些被分配出去（memblock_alloc），驱动预留（cma，dma_alloc_from_contiguous）, 内核数据（.text，.data，dtb，initrd等等）的这些内存域则会被添加到 reserved 内存域中，后续从 memory 域释放给伙伴系统的可用空闲内存需要全部避开 reserved 域的内存。

3.2 strcut memblock_type

struct memblock_type管理了一种类型的内存域集合，目前定义了的内存域集合包括memory，reserved,physmem。

结构体如下：

struct memblock_type {unsigned long cnt;unsigned long max;phys_addr_t total_size;struct memblock_region *regions;char *name;
};

• cnt
  ​ 记录了当前内存域集合中已保存的最大数量region。（所有域遍历均以这个值为终点或者起点）
• max
  ​ 当前内存域集合中能保存的最大数量 region。
• total_size
  ​ 当前内存域集合的总内存大小。
• regions
  ​ 内存域集合的实例数组，所有内存域均按照地址从大到小的顺序依次存放在 region 数组中，后续虚拟内存映射完成后，可以使用 memblock_allow_resize来允许动态调整 regions 的数组大小。
• name
  ​ 该内存域的名称，主要用于打印信息（“memory”，“reserved”，“physmem”）。

3.3 struct memblock_region

该结构体是每一个内存区域的实际存放数据结构，在 memblock_type 中使用数组来定义该结构。

struct memblock_region {phys_addr_t base;phys_addr_t size;enum memblock_flags flags;
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAPint nid;
#endif
};

• base
  ​ 该内存区域的起始物理地址
• size
  ​ 该内存区域的大小
• flags
  ​ 该内存区域的 flags 标记，用于标识当前区域的属性（后续介绍）
• nid
  ​ 当系统支持 NUMA 时，该 nid 就是该内存区域对应的 numa 节点号，在进行内存分配时可以指定 nid 来为就近 cpu 分配内存，也用于释放可用空闲内存到伙伴系统时为伙伴系统系统 nid 标识。

3.4 enum memblock_flags

该结构体用于标识一个内存区域的属性

enum memblock_flags {MEMBLOCK_NONE		= 0x0,	/* No special request */MEMBLOCK_HOTPLUG	= 0x1,	/* hotpluggable region */MEMBLOCK_MIRROR		= 0x2,	/* mirrored region */MEMBLOCK_NOMAP		= 0x4,	/* don't add to kernel direct mapping */
};

• MEMBLOCK_NONE
  ​ 这个是每个区域的默认值，也表示该区域没有特殊要求。
• MEMBLOCK_HOTPLUG
  ​ 表示可以热插拔的区域，即在系统运行过程中可以拔出或插入物理内存。
• MEMBLOCK_MIRROR
  ​ 表示镜像的区域。内存镜像是内存冗余技术的一种，工作原理与硬盘的热备份类似，将内存数据做两个复制，分别放在主内存和镜像内存中。
• MEMBLOCK_NOMAP
  ​ 表示不添加到内核直接映射区域（即线性映射区域）

3.5 静态数据结构定义

memblock的数据结构使用静态定义，即系统启动之后即可直接使用 memblock 的 API 进行内存管理，而不需要单独的初始化过程，全局数据部分定义如下：

#define INIT_MEMBLOCK_REGIONS			128
#define INIT_PHYSMEM_REGIONS			4#ifndef INIT_MEMBLOCK_RESERVED_REGIONS
# define INIT_MEMBLOCK_RESERVED_REGIONS		INIT_MEMBLOCK_REGIONS
#endifstatic struct memblock_region memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS] __initdata_memblock;
static struct memblock_region memblock_reserved_init_regions[INIT_MEMBLOCK_RESERVED_REGIONS] __initdata_memblock;struct memblock memblock __initdata_memblock = {.memory.regions		= memblock_memory_init_regions,.memory.cnt		= 1,	/* empty dummy entry */.memory.max		= INIT_MEMBLOCK_REGIONS,.memory.name		= "memory",.reserved.regions	= memblock_reserved_init_regions,.reserved.cnt		= 1,	/* empty dummy entry */.reserved.max		= INIT_MEMBLOCK_RESERVED_REGIONS,.reserved.name		= "reserved",#ifdef CONFIG_HAVE_MEMBLOCK_PHYS_MAP.physmem.regions	= memblock_physmem_init_regions,.physmem.cnt		= 1,	/* empty dummy entry */.physmem.max		= INIT_PHYSMEM_REGIONS,.physmem.name		= "physmem",
#endif.bottom_up		= false,.current_limit		= MEMBLOCK_ALLOC_ANYWHERE,
};

可以看到全局定义了一个 memblock，使用 memory 内存域类型为例：

首先 cnt 为 1，标识当前系统目前已有的内存域为 1 个。（该 cnt = 1 是一个特例，后续合并，分离，移除均会对 cnt = 1 时进行特殊判断，作用也是为了方便打印，和内部处理合并，分离的逻辑简化）

接着 max 为 INIT_MEMBLOCK_REGIONS，INIT_MEMBLOCK_REGIONS 从上面可知默认为 128，即系统中默认开始有一个 struct memblock_region region[128]的数组，后续如何 region 可以被动态的拓展。memblock_physmem_init_regions 就是上面这个数组的定义，直接挂载在 regions 上。

4 核心算法逻辑

对于 memblock需要完成的任务，可以把memblock的核心内部功能分为以下 4 个部分：

1. 合并，裁剪
   添加到系统的内存需要验证是否重合，是否超出物理限制，相对应的需要对相交的，连续的内存进行 region 合并，对于超出物理限制的或者最大地址限制进行裁剪地址范围。
2. 分离，隔离
   从系统内存中移除的内存需要对 region 进行分离，对特定内存范围进行 flags 标识时需要对其内存隔离。
3. 动态拓展 region 数组
   当系统中 regions 数组已接近用完时，我们要尽量保证不能让其分配失败，所以可以通过动态拓展的方式，从现有的可用空闲内存中分配一段内存来拓展数组大小，原理是先申请比原先大两倍的数组空间，并将原来的数组数据拷贝到新的数组空间中，并重新把该数组空间挂回原来的 regions 上，当然原有的数组区域会根据配置来判断是否需要释放到伙伴系统。
4. 内存域的遍历
   有效的寻找一块合适的内存，涉及到对内存域遍历的方式，尤其是从 memory 中排除 reserved 的遍历。

4.1 合并与裁剪

首先看看触发合并的地点:

memblock_set_node-> memblock_merge_regionsmemblock_add_range-> memblock_merge_regionsmemblock_mark_**
memblock_clear_**-> memblock_setclr_flag-> memblock_merge_regions

可以看到当手动标记一段内存范围的属性，添加内存到 memblock_type，标记和清除一段内存域属性时会触发合并操作，代码如下：

static void __init_memblock memblock_merge_regions(struct memblock_type *type)
{int i = 0;/* cnt never goes below 1 */while (i < type->cnt - 1) {struct memblock_region *this = &type->regions[i];struct memblock_region *next = &type->regions[i + 1];if (this->base + this->size != next->base ||memblock_get_region_node(this) !=memblock_get_region_node(next) ||this->flags != next->flags) {BUG_ON(this->base + this->size > next->base);i++;continue;}this->size += next->size;/* move forward from next + 1, index of which is i + 2 */memmove(next, next + 1, (type->cnt - (i + 2)) * sizeof(*next));type->cnt--;}
}

首先是会根据 cnt 遍历当前内存类型中所有内存域，并检查当前范围和下一个内存范围是否刚好连续，检查当前范围 nid 和下一个 nid 是否相同，检查当前范围属性和下一个范围属性是否相同，如果三个条件全部满足则会触发 memmove 操作，否则 continue 继续下一个的比较。

memmove 主要是将下一个域连其后续所有 region 一同向前拷贝一个 region 地址，从而完成一次 region 合并。

可以看到 memmove 是对一大段内存进行拷贝，甚至拷贝次数不止一次，所有触发 merge 的时机需要注意。

触发裁剪的地方：
memblock_cap_size 该函数主要用于检测范围是否超过 PHYS_ADDR_MAX 限制。

static inline phys_addr_t memblock_cap_size(phys_addr_t base, phys_addr_t *size)
{return *size = min(*size, PHYS_ADDR_MAX - base);
}

在四个地方会调用 memblock_cap_size 来检测，并调整 size 大小。

memblock_add_range
memblock_isolate_range（隔离）
memblock_is_region_memory
memblock_is_region_reserved

4.2 分离与隔离

分离与隔离是一起完成的，调用 memblock_isolate_range 函数完成，调用点如下：

memblock_set_node
memblock_remove_rangememblock_mark_**
memblock_clear_**-> memblock_setclr_flagmemblock_cap_memory_range （调整内存可用范围，会触发 remove 逻辑，移除超过设置范围的内存域）

其触发点和 4.1中的差不多只是一个实在添加时触发合并，一个是在移除时触发合并。

static int __init_memblock memblock_isolate_range(struct memblock_type *type,phys_addr_t base, phys_addr_t size,int *start_rgn, int *end_rgn)
{phys_addr_t end = base + memblock_cap_size(base, &size);int idx;struct memblock_region *rgn;*start_rgn = *end_rgn = 0;if (!size)return 0;/* we'll create at most two more regions */while (type->cnt + 2 > type->max) -------------------------------------（1）if (memblock_double_array(type, base, size) < 0)return -ENOMEM;for_each_memblock_type(idx, type, rgn) { ------------------------------（2）phys_addr_t rbase = rgn->base;phys_addr_t rend = rbase + rgn->size;if (rbase >= end)break;if (rend <= base)continue;if (rbase < base) {/** @rgn intersects from below.  Split and continue* to process the next region - the new top half.*/rgn->base = base;rgn->size -= base - rbase;type->total_size -= base - rbase;memblock_insert_region(type, idx, rbase, base - rbase,memblock_get_region_node(rgn),rgn->flags);} else if (rend > end) {/** @rgn intersects from above.  Split and redo the* current region - the new bottom half.*/rgn->base = end;rgn->size -= end - rbase;type->total_size -= end - rbase;memblock_insert_region(type, idx--, rbase, end - rbase,memblock_get_region_node(rgn),rgn->flags);} else {/* @rgn is fully contained, record it */if (!*end_rgn)*start_rgn = idx;*end_rgn = idx + 1;}}return 0;
}

（1）首先分离一段内存域会增加 region 的使用数量，所以这里首先会判断 cnt + 2 是否大于了 max，如果超过 max 则数组不够，我们需要触发拓展数组逻辑。

（2）和合并一样依次遍历所有的 memblock_type，检查当前 region 与传入 base，size 之间的范围关系，分为两个部分：

如果是在当前 region base 下方相交，则对当前 region 更新 base 和 size，并把原有的 region 的 base和调整后的 size 通过 memblock_insert_region 重新插入 memblock_type 中，memblock_insert_region中会触发 memmove 来移动后续所有region域。

如果是在当前 region base 的上方相交，则更新当前 region 为下一个域的起始，那么把原有的 region 重新插入内存域后还是 idx–，重新对当前域进行调整。

4.3 动态拓展 region 数组

通过上面可知，如果数组可用数量不足，会通过memblock_double_array触发数组扩展逻辑，代码比较长，这里贴出部分重要的逻辑：

static int __init_memblock memblock_double_array(struct memblock_type *type,phys_addr_t new_area_start,phys_addr_t new_area_size)
{int use_slab = slab_is_available();int *in_slab;/* We don't allow resizing until we know about the reserved regions* of memory that aren't suitable for allocation*/if (!memblock_can_resize) --------------------------------------------（1）return -1;/** We need to allocated new one align to PAGE_SIZE,*   so we can free them completely later.*/old_alloc_size = PAGE_ALIGN(old_size); -------------------------------（2）new_alloc_size = PAGE_ALIGN(new_size);/** We need to allocated new one align to PAGE_SIZE,*   so we can free them completely later.*/old_alloc_size = PAGE_ALIGN(old_size);new_alloc_size = PAGE_ALIGN(new_size);/* Try to find some space for it.** WARNING: We assume that either slab_is_available() and we use it or* we use MEMBLOCK for allocations. That means that this is unsafe to* use when bootmem is currently active (unless bootmem itself is* implemented on top of MEMBLOCK which isn't the case yet)** This should however not be an issue for now, as we currently only* call into MEMBLOCK while it's still active, or much later when slab* is active for memory hotplug operations*/if (use_slab) {new_array = kmalloc(new_size, GFP_KERNEL); -------------------------（3）addr = new_array ? __pa(new_array) : 0;} else {/* only exclude range when trying to double reserved.regions */if (type != &memblock.reserved)new_area_start = new_area_size = 0;addr = memblock_find_in_range(new_area_start + new_area_size,memblock.current_limit,new_alloc_size, PAGE_SIZE); -------------------------（4）if (!addr && new_area_size)addr = memblock_find_in_range(0,min(new_area_start, memblock.current_limit),new_alloc_size, PAGE_SIZE);new_array = addr ? __va(addr) : NULL;}/** Found space, we now need to move the array over before we add the* reserved region since it may be our reserved array itself that is* full.*/memcpy(new_array, type->regions, old_size);memset(new_array + type->max, 0, old_size); ----------------------------（5）old_array = type->regions;type->regions = new_array;type->max <<= 1;/* Free old array. We needn't free it if the array is the static one */if (*in_slab) ----------------------------------------------------------（6）kfree(old_array);else if (old_array != memblock_memory_init_regions &&old_array != memblock_reserved_init_regions)memblock_free(__pa(old_array), old_alloc_size);/** Reserve the new array if that comes from the memblock.  Otherwise, we* needn't do it*/if (!use_slab)BUG_ON(memblock_reserve(addr, new_alloc_size)); -------------------（7）/* Update slab flag */*in_slab = use_slab;return 0;
}

（1）首先外部需要使用 memblock_allow_resize来标记 memblock_can_resize为 true，表明线性映射区域已经映射好了，可以安全的把物理内存转换为虚拟地址来访问，如果没有设置该变量，表明外部还允许访问线性映射区域

（2）对原有的数组大小和新数组大小进行 page 对其，方便后续可以将完整一页数据释放回伙伴系统，避免产生随便内存无法被使用。

（3）当此时系统 slab 已经可用时，我们直接通过 kmalloc 申请内存。理论上这种情况是不会发生的，应该和兼容 bootmem 有关。

（4）如果 slab 不可用，那我们直接从自己的可用空闲内存中申请分配一段内存来用，如果分配到了则通过 __va将物理地址转换为一个虚拟地址，以便可以正确访问。

（5）完成老数组到新数组的拷贝动作。

（6）对于原有数组，如果原有数组已经是从 slab 分配的了，那我们直接使用 kfree 来释放老数组。如果老数组既不是 slab 分配的，也不是静态定义的数组，那么我们调用 memblock_free 来释放老数组。

（7）相应的，如果新数组是从 memblock 中找到的，那么我们需要把这段内存通过 memblock_reserved 添加到预留内存中。（这部分逻辑其实就是 memblock_alloc 的内部逻辑）

4.4 内存域的遍历

内存域的遍历除了传统的数组遍历形式以外，内核还实现了类似于迭代器的形式，使用 __next_mem_range和__next_mem_range_rev来从 type_a 中取出下一个 region元素并且每个取出的 region 需要完全避开 type_b 中定义的所有 region，其中 rev 是反向操作，部分代码如下：

void __init_memblock __next_mem_range_rev(u64 *idx, int nid,enum memblock_flags flags,struct memblock_type *type_a,struct memblock_type *type_b,phys_addr_t *out_start,phys_addr_t *out_end, int *out_nid)
{int idx_a = *idx & 0xffffffff;int idx_b = *idx >> 32;if (WARN_ONCE(nid == MAX_NUMNODES, "Usage of MAX_NUMNODES is deprecated. Use NUMA_NO_NODE instead\n"))nid = NUMA_NO_NODE; // nid = MAX_NUMNODES 时，修正 nid 为 -1 for (; idx_a >= 0; idx_a--) {struct memblock_region *m = &type_a->regions[idx_a];phys_addr_t m_start = m->base;phys_addr_t m_end = m->base + m->size;int m_nid = memblock_get_region_node(m);/* only memory regions are associated with nodes, check it */if (nid != NUMA_NO_NODE && nid != m_nid) //如果 nid 不等于 -1 也不与当前域匹配则跳过该域continue;/* skip hotpluggable memory regions if needed */if (movable_node_is_enabled() && memblock_is_hotpluggable(m)) // 可拔插内存被激活并且是可拔插内存跳过continue;/* if we want mirror memory skip non-mirror memory regions */if ((flags & MEMBLOCK_MIRROR) && !memblock_is_mirror(m)) // 如果 flags mirror 但该域不是 mirror 则跳过continue;/* skip nomap memory unless we were asked for it explicitly */if (!(flags & MEMBLOCK_NOMAP) && memblock_is_nomap(m)) // 如前面所说，nomap 属性不参与遍历，除非指定 falgs 要遍历该区域。continue;。。。。。。	/* scan areas before each reservation */for (; idx_b >= 0; idx_b--) { // 对 type_b （reserved）进行遍历，上面找到的内存域要完全避开这个遍历的所有regionstruct memblock_region *r;phys_addr_t r_start;phys_addr_t r_end;r = &type_b->regions[idx_b];r_start = idx_b ? r[-1].base + r[-1].size : 0;r_end = idx_b < type_b->cnt ?r->base : PHYS_ADDR_MAX;/** if idx_b advanced past idx_a,* break out to advance idx_a*/if (r_end <= m_start)break;/* if the two regions intersect, we're done */if (m_end > r_start) {if (out_start)*out_start = max(m_start, r_start);if (out_end)*out_end = min(m_end, r_end);if (out_nid)*out_nid = m_nid;if (m_start >= r_start)idx_a--;elseidx_b--;*idx = (u32)idx_a | (u64)idx_b << 32;return;}}}/* signal end of iteration */*idx = ULLONG_MAX;
}

有了上述实现，则可以封装多种遍历结构，如 for_each_free_mem_range，for_each_free_mem_range_reverse。

4.5 memblock 分配内存的核心 memblock_find_in_range_node

如上：
另一个重要的遍历方式是 memblock_find_in_range_node，也是分配内存的核心 API。
该函数从指定范围，nid 和 flags 进行遍历，如果遍历返回的地址范围满足我们需要的 size 和 align 则返回这个内存域对应的地址，比如自顶向下分配时：返回地址 = reg->end - aling(size)

phys_addr_t __init_memblock memblock_find_in_range_node(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 kernel_end, ret;/* pump up @end */if (end == MEMBLOCK_ALLOC_ACCESSIBLE ||end == MEMBLOCK_ALLOC_KASAN)end = memblock.current_limit; // 首先验证与调整能分配的最大地址/* avoid allocating the first page */start = max_t(phys_addr_t, start, PAGE_SIZE); // 分配的最小地址必须大于等于 PAGE_SIZE（不能是 0 地址）end = max(start, end);kernel_end = __pa_symbol(_end); // 线性映射不能访问低于内核本身的地址，这里获取到 _end 对应的虚拟地址/** try bottom-up allocation only when bottom-up mode* is set and @end is above the kernel image.*/if (memblock_bottom_up() && end > kernel_end) { // 从底部分配并且 end 大于内核的 _end 地址，则从底部开始分配，任意条件不满足则只能从顶部开始往下分配。phys_addr_t bottom_up_start;/* make sure we will allocate above the kernel */bottom_up_start = max(start, kernel_end);/* ok, try bottom-up allocation first */ret = __memblock_find_range_bottom_up(bottom_up_start, end,size, align, nid, flags); ------（1）if (ret)return ret;/** we always limit bottom-up allocation above the kernel,* but top-down allocation doesn't have the limit, so* retrying top-down allocation may succeed when bottom-up* allocation failed.** bottom-up allocation is expected to be fail very rarely,* so we use WARN_ONCE() here to see the stack trace if* fail happens.*/WARN_ONCE(IS_ENABLED(CONFIG_MEMORY_HOTREMOVE),"memblock: bottom-up allocation failed, memory hotremove may be affected\n");}return __memblock_find_range_top_down(start, end, size, align, nid,flags); ----------------------------（1）
}

其中 memblock_bottom_up 来判断自底向上寻找还是自顶向下寻找。其中如果自底向上寻找最小地址需要 kernel_end（kernel_end = __pa_symbol(_end)）,原因为内核有时候不支持线性映射小于内核占用物理地址的低位。 也就是要求 bootlaoder 加载内核镜像尽量靠近物理内存的底部。

（1）__memblock_find_range_top_down 和 __memblock_find_range_bottom_up 一个自顶向下分配，一个自底向上分配，基本逻辑相同只是调用的遍历方式，它的最底层调用 for_each_free_mem_range或者for_each_free_mem_range_reverse。
这里以 __memblock_find_range_top_down 为例：

static phys_addr_t __init_memblock
__memblock_find_range_top_down(phys_addr_t start, phys_addr_t end,phys_addr_t size, phys_addr_t align, int nid,enum memblock_flags flags)
{phys_addr_t this_start, this_end, cand;u64 i;for_each_free_mem_range_reverse(i, nid, flags, &this_start, &this_end,NULL) { // 遍历可用内存域中的空闲内存（也就是避开 reserved 域的内存）this_start = clamp(this_start, start, end);this_end = clamp(this_end, start, end);// 下面判断 size 对齐后是否在内存域大小范围内，在范围内则成功找到一块可分配内存，// 不满足则继续遍历下一块内存域，进行相同比较。// ps：如果这里返回了找到的地址，那么后面会调用 memblock_reserved 把// 这块内存预留到 resreved 域中，之后调用的函数在这里进行遍历则不会再// 找到该内存块了，除非调用 memblock_free 把这段内存从 reserved 域中移除。if (this_end < size) continue;cand = round_down(this_end - size, align);if (cand >= this_start)return cand;}return 0;
}

5 memblock 在 arm64 启动中应用

下面从 arm64 的启动流程中看看内核如何使用 memblock，以及最后如何释放内存到伙伴系统。

5.1 内存的第一步扫描与添加

首先是 arm64 寻找内存并添加到 memblock 中：

setup_arch-> setup_machine_fdt-> early_init_dt_scan_nodes-> early_init_dt_scan_memory-> early_init_dt_add_memory_arch-> early_init_dt_mark_hotplug_memory_arch

首先是在 early_init_dt_scan_memory中

int __init early_init_dt_scan_memory(unsigned long node, const char *uname,int depth, void *data)
{const char *type = of_get_flat_dt_prop(node, "device_type", NULL); ------（1）const __be32 *reg, *endp;int l;bool hotpluggable;/* We are scanning "memory" nodes only */if (type == NULL || strcmp(type, "memory") != 0) ------------------------（2）return 0;reg = of_get_flat_dt_prop(node, "linux,usable-memory", &l); -------------（3）if (reg == NULL)reg = of_get_flat_dt_prop(node, "reg", &l);if (reg == NULL)return 0;endp = reg + (l / sizeof(__be32));hotpluggable = of_get_flat_dt_prop(node, "hotpluggable", NULL); ---------（4）pr_debug("memory scan node %s, reg size %d,\n", uname, l);while ((endp - reg) >= (dt_root_addr_cells + dt_root_size_cells)) {u64 base, size;base = dt_mem_next_cell(dt_root_addr_cells, &reg);size = dt_mem_next_cell(dt_root_size_cells, &reg);if (size == 0)continue;pr_debug(" - %llx ,  %llx\n", (unsigned long long)base,(unsigned long long)size);early_init_dt_add_memory_arch(base, size); -------------------------（5）if (!hotpluggable)continue;if (early_init_dt_mark_hotplug_memory_arch(base, size)) ------------（6）pr_warn("failed to mark hotplug range 0x%llx - 0x%llx\n",base, base + size);}return 0;
}

（1）（2）首先在设备树寻找到 “device_type” 属性节点，并判断设备节点类型是否是 “memory”，如果是，则说明是一个内存描述节点，这里就可以继续向下对其解析。可能不止一个 device_type = “memory” 节点，由上层调用寻找，如果找到则调用一次 early_init_dt_scan_memory 来解析当前节点。

（3）在同节点下寻找 "linux,usable-memory"属性节点，如果有则可以从这个属性中取出内存区域描述，如果没有则寻找 “reg” 属性，从"reg"中取出内存描述。

（4）如果该属性节点标记了 “hotpluggable” 属性，则该节点中所有内存域都是可拔插的，我们需要标记内存域为 MEMBLOCK_HOTPLUG。

（5）early_init_dt_add_memory_arch 中会对当前内存域的 base， size，进行校验，如果通过则使用 memblock_add 添加到 memblock 中。

（6）如果该节点标记了 “hotpluggable”，那么调用 memblock_mark_hotplug 来标记内存域为 MEMBLOCK_HOTPLUG。

5.2 efi_init 中对内存的扫描与预留

当支持 efi 时会调用 efi_init 来对进行进一步调整。

首先是 efi_init 从设备树中获取到 efi_fdt_params 参数，也就是相应的 efi 表项地址。

接着调用 reserve_regions 来重新添加和预留内存。

static __init void reserve_regions(void)
{efi_memory_desc_t *md;u64 paddr, npages, size;if (efi_enabled(EFI_DBG))pr_info("Processing EFI memory map:\n");/** Discard memblocks discovered so far: if there are any at this* point, they originate from memory nodes in the DT, and UEFI* uses its own memory map instead.*/memblock_dump_all();memblock_remove(0, PHYS_ADDR_MAX); // 首先移除所有之前设备树中添加的内存。for_each_efi_memory_desc(md) { // 从 efi.memmap 中扫描内存paddr = md->phys_addr;npages = md->num_pages;if (efi_enabled(EFI_DBG)) {char buf[64];pr_info("  0x%012llx-0x%012llx %s\n",paddr, paddr + (npages << EFI_PAGE_SHIFT) - 1,efi_md_typeattr_format(buf, sizeof(buf), md));}memrange_efi_to_native(&paddr, &npages);size = npages << PAGE_SHIFT;if (is_memory(md)) {early_init_dt_add_memory_arch(paddr, size); // 调用 memblock_add添加内存if (!is_usable_memory(md))memblock_mark_nomap(paddr, size); // 标记内存不能线性映射/* keep ACPI reclaim memory intact for kexec etc. */if (md->type == EFI_ACPI_RECLAIM_MEMORY)memblock_reserve(paddr, size); // 特殊用途内存，直接对内存进行预留}}
}

完成上述扫描后，efi_init 调用 memblock_reserve ，预留 efi 表项中的地址范围。

if (uefi_init() < 0) {efi_memmap_unmap();return;
}reserve_regions();
efi_esrt_init();memblock_reserve(params.mmap & PAGE_MASK,PAGE_ALIGN(params.mmap_size +(params.mmap & ~PAGE_MASK)));

至此完成了 arm64 内存的所有扫描和添加完成。

5.3 arm64_memblock_init进一步的内存预留与整理

首先看看代码

void __init arm64_memblock_init(void)
{const s64 linear_region_size = -(s64)PAGE_OFFSET; ------------------（1）/* Handle linux,usable-memory-range property */fdt_enforce_memory_region(); ---------------------------------------（2）/* Remove memory above our supported physical address size */memblock_remove(1ULL << PHYS_MASK_SHIFT, ULLONG_MAX); --------------（3）/** 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 = round_down(memblock_start_of_DRAM(),ARM64_MEMSTART_ALIGN); -----------------------------（4）/** 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_remove(max_t(u64, memstart_addr + linear_region_size,__pa_symbol(_end)), ULLONG_MAX); --------------------------（5）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); -----------------------------（6）}/** 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) { -------------------------------（7）memblock_mem_limit_remove_map(memory_limit);memblock_add(__pa_symbol(_text), (u64)(_end - _text));}if (IS_ENABLED(CONFIG_BLK_DEV_INITRD) && phys_initrd_size) { --------（8）/** 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 = phys_initrd_start & PAGE_MASK;u64 size = PAGE_ALIGN(phys_initrd_size);/** 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)) { -----------------------------（9）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_reserve(__pa_symbol(_text), _end - _text); ------------------（10）if (IS_ENABLED(CONFIG_BLK_DEV_INITRD) && phys_initrd_size) {/* the generic initrd code expects virtual addresses */initrd_start = __phys_to_virt(phys_initrd_start);initrd_end = initrd_start + phys_initrd_size;}early_init_fdt_scan_reserved_mem(); -----------------------------------（11）/* 4GB maximum for 32-bit only capable devices */if (IS_ENABLED(CONFIG_ZONE_DMA32))arm64_dma_phys_limit = max_zone_dma_phys();elsearm64_dma_phys_limit = PHYS_MASK + 1;reserve_crashkernel(); -----------------------------------------------（12）reserve_elfcorehdr(); ------------------------------------------------（13）high_memory = __va(memblock_end_of_DRAM() - 1) + 1;dma_contiguous_reserve(arm64_dma_phys_limit); ------------------------（14）
}

（1）线性映射区域的大小。

（2）fdt_enforce_memory_region 扫描设备树中 “linux,usable-memory-range” 节点，如果有，说明需要调整内存可用范围，将解析出的内存范围使用 memblock_cap_memory_range 来调整内存范围。

（3）这里将超过 PA (48bit)范围的物理范围移除，我们不可能访问超过处理器限制的物理内存范围。

（4）获取到物理内存的起始地址。

（5）移除从物理内存起始 + 线性地址最大大小的范围，这一段也是我们不能映射的范围。

（6）同样的物理地址大小线性映射范围也需要调整。

（7）如果命令行通过 “mem=xxx” 这种限制了能使用的最大内存。那么这里调用 memblock_mem_limit_remove_map 来限制最大内存大小，并调整内存范围。

（8）如果支持 BLK_DEV_INITRD 并且我们加载了 initrd rams，那么 initrd 的内存需要预留出来。

（9）CONFIG_RANDOMIZE_BASE TODO

（10）内核本身占用的物理地址必须预留出来。

（11）与驱动设备的预留相关，主要有设备树中通过"reserved-memory"，“dma” 等等属性标记的内存，cma 预留的内存，在设备树顶部使用 /memreserve/ 标记的内存。

（12）预留 crash dump 使用的内存。

（13）预留 efi core 头部的内存。

（14）最后预留 dma contiguous 可用的内存。

至此内存的预留调整全部完整，后续就可以直接使用 memblock_alloc 来进一步初始化流程了。

5.4 paging_init 使用 memblock 分配内存进行各项设置

void __init paging_init(void)
{pgd_t *pgdp = pgd_set_fixmap(__pa_symbol(swapper_pg_dir));map_kernel(pgdp); ------------------------------------------（1）map_mem(pgdp); ---------------------------------------------（2）pgd_clear_fixmap();cpu_replace_ttbr1(lm_alias(swapper_pg_dir)); ----------------（3）init_mm.pgd = swapper_pg_dir;memblock_free(__pa_symbol(init_pg_dir),__pa_symbol(init_pg_end) - __pa_symbol(init_pg_dir)); ----（4）memblock_allow_resize();
}

（1）使用 memblock_alloc 为映射 kernel 的文本段，数据等分配内存。

（2）使用 for_each_memblock 遍历所有可用内存域，并且全部映射到线性映射区域，避开 nomap 域，期间同样使用 memblock_alloc 来为中间页表分配内存。

（3）完成了内核与内存的映射后，我们就可以将原来的 init_pg_dir 替换为现在真正的工作页表 swapper_pg_dir。

（4）init_pg_dir 占用的内存不再使用，直接释放到 memblock 中。

（5）此时线性映射区域已经可以访问，标记memblock 可以拓展内存域数组。

接着在后续的扫描设备树以及 bootmem_init 中会使用 memblock 来分配内存。

bootmem_init 主要流程如下：

bootmem_init-> early_memtest-> arm64_numa_init-> arm64_memory_present-> zone_sizes_init

early_memtest 遍历所有可用内存域，并进行内存读写测试，如果有测试失败的内存块会使用 memblock_reserve 来进行预留。

arm64_numa_init 会扫描内存的 numa 节点信息，并将 numa 节点号标记到 memblock 中对应的内存域中。

arm64_memory_present 会为 struct page 等结构域进行映射，并使用 memblock 分配期间的内存。

zone_sizes_init 会对 zone 区进行调整和分区和初始化。

5.5 memblock_free_all 释放内存到伙伴系统

在 start_kernel 中当前期一些准备工作完成后，在 mem_init 中会将 memblock 中剩余的可用空闲内存释放给伙伴系统，核心逻辑为 memblock_free_all 。

使用 for_each_free_mem_range 遍历所有可用空闲内存，并按照 page 使用 __free_memory_core 释放到 buddy 中。

至此，memblock 工作基本全部完成，后续有伙伴系统和 slab 接管内存管理，而 memblock 中残余不使用的数据也会通过 free_initmem 和 memblock_discard 释放到伙伴系统中，一点不浪费。

其中需要注意内核中使用 pfn_valid 来判断一个 pfn 是否是一个合理可用物理地址，对其arm64 内部使用了 memblock_is_map_memory 来判断内存是否合法，所以，对于 arm64 memblock 中 __initmemblock 标记的数据不会被释放到伙伴系统，因为我们还需要 memblock 中定义的数据来判断内存是否合法。