0%

Linux内核内存管理 - Memblock和Buddy System(1)

Posted on In , 总字数：2.6k Valine:

这是<Linux内核内存管理>系列的第四篇

第一篇为内核内存管理过程知识点的的简单梳理

第二篇介绍了内核的数据结构

第三篇介绍了从内核第一行代码加载到跳转到C代码前的内存处理。

第四篇概览了初始化C代码中的内存处理

概述

参考内核文档，系统初始化早期是不能使用我们常用的 kmalloc ，vmalloc 等函数，这是因为此时对应的功能还没初始化好。

尽管如此，早期初始化仍然需要分配内存。因此早期内核提供了基于bitmap的Bootmem分配器，后续逐渐演进成了现在的Memblock。
Memblock或者早期的Bootmem并不能适应系统运行时的各种复杂场景（多线程、碎片等）。因此在内核启动到一定阶段后，内存管理的工作会交由伙伴系统(Buddy System)接管。

当然也并非是仅由伙伴系统管理。除了伙伴系统来以页为单位进行内存分配，还会有SLAB系统的某种（一般是SLUB）来实现对小内存分配的管理。

Memblock

Memblock将系统中的内存分为一系列不同类型的连续区域。主要有以下几个类型：

  • memory：用于描述当前内核可用的物理内存。
  • reserved: 用于描述不可用内存（已分配）。
  • physmem：特殊体系结构才有，此处不表。

Memblock使用以上概念对内核启动早期内存分配进行管理。

数据结构

Memblock的内存主要数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct memblock_region {
	phys_addr_t base;
	phys_addr_t size;
	enum memblock_flags flags;
#ifdef CONFIG_NUMA
	int nid;
#endif
};
struct memblock_type {
	unsigned long cnt;
	unsigned long max;
	phys_addr_t total_size;
	struct memblock_region *regions;
	char *name;
};
struct memblock {
	bool bottom_up;  /* is bottom up direction? */
	phys_addr_t current_limit;
	struct memblock_type memory;
	struct memblock_type reserved;
};
  • memblock_region: 代表一段物理内存区域。
    • base：表示区域物理起始物理地址
    • size：表示区域大小
    • flags：区域标记，主要有（HOTPLUG, MIRROR, NOMAP），分别表示区域是否是热插拔，镜像区域和是否加入到内核直接映射区。
    • nid: 如果开启了NUMA（Non Unified Memory Access）
  • memblock_type: 表示某种内存类型的集合。如前文所述，目前主要有Memory和Reserved。
    • cnt：表示该memblock_type的个数
    • max: 此type内区域的数量（即regions链表的元素个数）
    • total_size: 此类内存区域内存的总大小
    • regions：所有此类区域内存的链表
    • name: 该类型的符号名
  • memblock: 管理整个Memblock的数据结构
    • bottom_up: 内存分配的方向，是否从底向上
    • current_limit：Memblock分配器管理的物理内存地址的上限
    • memory: memory类型
    • reserved: memory类型

一张图说明以上结构的关系：

分配和释放

Memblock分配和释放函数主要有以下：

  • memblock_alloc: 分配内存，主要有(memblock_alloc_range_nid, memblock_alloc_raw, memblock_alloc_from等)
  • memblock_add: 分配内存区域
  • memblock_add_node: 在指定NUMA上分配内存区域
  • memblock_add_range: 在指定NUMA区域内分配指定类型和FLAG标记的内存区域
  • memblock_remove: 删除一个内存区域
  • memblock_remove_range: 删除一个指定类型的内存区域
  • memblock_remove_region: 删除指定内存区域
  • memblock_free: 删除内存区域， 主要有(memblock_free_early, memblock_free_early_nid等)
  • memblock_reserve: 将指定区域设定为保留区域

以上API名称很像，但其实最终只是对其中某几个API的封装。

分配

从如下alloc系函数调用关系可以看到，最终调用到memblock_add_range。

Memblock分配函数

从不同分支进到分配函数memblock_add_range，差异仅在与分配时选取的NUMA Node ID、标记（Flag）、类型（Memory还是Reserved）等参数的不同。其具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
static 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;

	/* special case for empty array */
	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_NUMA
			WARN_ON(nid != memblock_get_region_node(rgn));
#endif
			WARN_ON(flags != rgn->flags);
			nr_new++;
			if (insert)
				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);
	}

	if (!nr_new)
		return 0;

	/*
	 * If this was the first round, resize array and repeat for actual
	 * insertions; otherwise, merge and return.
	 */
	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;
	}
}

代码虽长，其实比较容易理解：

  • 首先如果对应类型类型还没有任何内存区域，便直接在对应分配所要求的的内存区域。
  • 如果该类型区域非空，就需要遍历所有内存区域，确定待加入区域是否与已存在区域重合。据此会有三种处理：
    • 如果待加入区域与现存区域无重叠，则直接添加此区域
    • 如果待加入区域与现存区域有重叠且并未被现存区域完整包含，则将待加入区域与现存区域进行合并
    • 如果待加入区域被现存区域完全包含，则不用重新添加该区域

释放

另外可以从如下free系函数调用关系的简图看到，memblock_free*最终调用到memblock_remove_region和memblock_free_pages。

Memblock Free APIs

memblock_remove_region的主要作用是移除对应内存区，其代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r)
{
	type->total_size -= type->regions[r].size;
	memmove(&type->regions[r], &type->regions[r + 1],
		(type->cnt - (r + 1)) * sizeof(type->regions[r]));
	type->cnt--;

	/* Special case for empty arrays */
	if (type->cnt == 0) {
		WARN_ON(type->total_size != 0);
		type->cnt = 1;
		type->regions[0].base = 0;
		type->regions[0].size = 0;
		type->regions[0].flags = 0;
		memblock_set_region_node(&type->regions[0], MAX_NUMNODES);
	}
}

这里的主要作用就是将内存区域从对应类型的区域数组中移除，修改对应类型区域的长度，同时将该区域索引之后的区域依次向前移动一位。

memblock_free_pages的作用则是将对应页释放会给Buddy System：

1
2
3
4
5
6
7
void __init memblock_free_pages(struct page *page, unsigned long pfn,
							unsigned int order)
{
	if (early_page_uninitialised(pfn))
		return;
	__free_pages_core(page, order);
}

物理内存模型

在讲解伙伴系统之前，我们先讲解物理内存模型（Physical Memory Model），这是向伙伴系统过度的基础。简单一点讲，伙伴系统是按页对内存进行管理的，物理内存模型解决的是：

  • 页对应的描述符(struct page)如何与对应物理页匹配。
  • 通过物理页帧号如何快速找到对应的页描述符。
  • 处理内存地址不连续 （存在多个内存节点，或者同个内存节点内有空洞造成的不连续）

Linux系统的物理内存管理模型有三种配置，通过KConfig选择：

  • Flat：平坦内存模型是最简单的内存管理模型，适用于地址连续没有内存空洞的系统，也是Linux最早采用的内存模型。因为被管理的内存地址连续，因此可以方便地使用数组来管理。数组下标也可以直接和页帧号进行关联。
  • Discontiguous：随着处理器系统发展，有了非均匀内存访问模型（NUMA）。为了处理这种需求，内核就有了Discontiguous内存管理模型。这种管理模型因为在对页帧和对应页描述符映射不够有效，且不能很好适应一些嵌入式系统的需求，逐渐被Sparse模型替代。

也可以称为“非一致性内存访问”，但一致性内存往往会跟DMA一致性，Cache一致性等概念混淆。

  • Sparse：目前最常用且适配性最强的内存模型，它还支持内存的热拔插。管理方式如下：

Sparse Memory Model

数据结构

从上图看出，mem_section的数据结构比较简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#ifdef CONFIG_SPARSEMEM_EXTREME
struct mem_section **mem_section;
#else
struct mem_section mem_section[NR_SECTION_ROOTS][SECTIONS_PER_ROOT]
	____cacheline_internodealigned_in_smp;
#endif
struct mem_section {
	/*
	 * This is, logically, a pointer to an array of struct
	 * pages.  However, it is stored with some other magic.
	 * (see sparse.c::sparse_init_one_section())
	 *
	 * Additionally during early boot we encode node id of
	 * the location of the section here to guide allocation.
	 * (see sparse.c::memory_present())
	 *
	 * Making it a UL at least makes someone do a cast
	 * before using it wrong.
	 */
	unsigned long section_mem_map;

	struct mem_section_usage *usage;
#ifdef CONFIG_PAGE_EXTENSION
	struct page_ext *page_ext;
	unsigned long pad;
#endif
};
  • section_mem_map: 存的是指向对应struct page表的指针，以及一些标记性栏位（如该section是否是存在的）
  • usage:
  • page_ext:
  • pad:

初始化

Sparse的每个mem_section管理一块连续的内存区域，它由多个物理页组成。mem_section和这些内存区域的映射关系在sparse_init函数建立。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void __init sparse_init(void)
{
	unsigned long pnum_end, pnum_begin, map_count = 1;
	int nid_begin;

	memblocks_present();

	pnum_begin = first_present_section_nr();
	nid_begin = sparse_early_nid(__nr_to_section(pnum_begin));

	/* Setup pageblock_order for HUGETLB_PAGE_SIZE_VARIABLE */
	set_pageblock_order();

	for_each_present_section_nr(pnum_begin + 1, pnum_end) {
		int nid = sparse_early_nid(__nr_to_section(pnum_end));

		if (nid == nid_begin) {
			map_count++;
			continue;
		}
		/* Init node with sections in range [pnum_begin, pnum_end) */
		sparse_init_nid(nid_begin, pnum_begin, pnum_end, map_count);
		nid_begin = nid;
		pnum_begin = pnum_end;
		map_count = 1;
	}
	/* cover the last node */
	sparse_init_nid(nid_begin, pnum_begin, pnum_end, map_count);
	vmemmap_populate_print_last();
}
  • memblocks_present 作用是为Mem Block中标记的memory类型的内存分配mem_section，并对mem_section的section_mem_map自段做Present标记。如下：
1
2
3
4
5
if (!ms->section_mem_map) {
	ms->section_mem_map = sparse_encode_early_nid(nid) |
					SECTION_IS_ONLINE;
	section_mark_present(ms);
}

“分配mem_section”并不准确，当Kconfig不是 _CONFIG_SPARSEMEM_EXTREME_时，mem_section数组是静态定义的。

  • 接着的循环就是遍历所有mem_section，分配struct page，修改mem_sesction的section_mem_map将该mem_section指向的page首地址与其关联。这里提一点是，section_mem_map主要存的是struct page表首地址减去该mem_section首个页的页帧号。这样后续可以快速的进行页帧号与对应struct page的相互转换。如下代码是封装，及页和页帧转换部分：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static unsigned long sparse_encode_mem_map(struct page *mem_map, unsigned long pnum)
{
	unsigned long coded_mem_map =
		(unsigned long)(mem_map - (section_nr_to_pfn(pnum)));
	BUILD_BUG_ON(SECTION_MAP_LAST_BIT > (1UL<<PFN_SECTION_SHIFT));
	BUG_ON(coded_mem_map & ~SECTION_MAP_MASK);
	return coded_mem_map;
}
#define __page_to_pfn(pg)					\
({	const struct page *__pg = (pg);				\
	int __sec = page_to_section(__pg);			\
	(unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec)));	\
})

#define __pfn_to_page(pfn)				\
({	unsigned long __pfn = (pfn);			\
	struct mem_section *__sec = __pfn_to_section(__pfn);	\
	__section_mem_map_addr(__sec) + __pfn;		\
})

小节

本文先介绍到这，后续篇幅接着介绍Buddy System。

Related Posts