ggaaooppeenngg

为什么计算机科学是无限的但生命是有限的

vmalloc-非连续内存的分配

发表于 更新于 Disqus：

主要结构

为了解决外部碎片的问题, 需要有一种手段可以分配非连续的页映射到一段连续的虚拟地址上. 这就是vmalloc的目的, 本文基于4.7.2的代码对vmalloc的实现进行分析.

这里要提到一个重要的结构体

1
2
3
4
5
6
7
8
9
10
11
struct vm_struct {
	struct vm_struct	*next;
	void			*addr;
	unsigned long		size;
	unsigned long		flags;
	struct page		**pages;
	unsigned int		nr_pages;
	phys_addr_t		phys_addr;
	const void		*caller;
};

这个结构用于描述每一段映射的内存.

比起32位的结构, 64位结构有更大的寻址空间, 可以通过查看Documentation/x86/x86_64/mm.txt 获得64位的内存映射, 比起32位的变化就是跨度变大了很多.

直接映射是64TB, 有一个1TB的空洞, 接着就是32TB的vmalloc空间,以VMALLOC_START(64TB+1TB)开始,VMALLOC_END(64TB+1TB+32TB)结尾.

原来的32位时, 内核的虚拟空间只有1G, 直接映射的区间占896MB, 隔了一个8MB的空洞, 再接着是vmalloc的映射区, 大小一般是128MB.

vmalloc和物理映射的空洞主要是一个安全区, 如果越过了这个hole说明程序有问题存在非法的访问.

vm_struct的组织是通过链表实现的,
其中next指向下一个vm_struct, addr指向的是虚拟地址, size对应分配的内存的大小,在有guard page(也就是flag的VM_NO_GUARD没有设置的话)的时候会多出一个PAGE_SIZE的大小(但没有映射内存), pages是页的地址, nr_pages是页的数量, phy_addr这个字段一般为0,当用于ioremap的时候会用到, caller是调用者的地址.

上面说了, 每个vm_struct代表的区间之间会有一PAGE_SIZE大小的分隔,也是为了能够方便检查非法越界的情况.

这是32位的一张分布图, 整体结构没变, 就是64位的区间变大了.

vmap_area用于代表虚拟地址的区间, 和vm_struct是有对应关系的.
list 是按地址排序存的线性链表节点.
rb_node 是按地址存的红黑树节点.
这两个值都是在插入的时候修改的.
也就是为了方便搜索,它既存在红黑树上也存在链表里面.

1
2
3
4
5
6
7
8
9
10
11
12
struct vmap_area {
	unsigned long va_start;
	unsigned long va_end;
	unsigned long flags;
	struct rb_node rb_node;         /* address sorted rbtree */
	struct list_head list;          /* address sorted list */
	struct llist_node purge_list;    /* "lazy purge" list */
	struct vm_struct *vm;
	struct rcu_head rcu_head;
};


vmap_area 虚拟地址的管理

接下了说一下调用过程, 首先vmalloc会调用__vmalloc_node_flags,这是一层封装,指定了GFP的flag, 接着调用__vmalloc_node,它通过指定搜寻的区域(VMALLOC_START,VMALLOC_END)调用了__vmalloc_node_range, 然后通过__get_vm_area_node寻找合适的虚拟内存空间,并且分配vm_struct,最后调用__vmalloc_area_node根据vm_struct分配具体的物理页并在页表中建立虚拟地址的映射.

__get_vm_area_node 对size进行对齐, 分配vmap_area的内存, 然后增加一个PAGE_SIZE的guard page, 接着就是寻找一段合适的虚拟地址的区间来分配给vmap_area并且用它来初始化vm_struct.

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
static struct vm_struct *__get_vm_area_node(unsigned long size,
		unsigned long align, unsigned long flags, unsigned long start,
		unsigned long end, int node, gfp_t gfp_mask, const void *caller)
{
	struct vmap_area *va;
	struct vm_struct *area;

	BUG_ON(in_interrupt());
	if (flags & VM_IOREMAP)
		align = 1ul << clamp_t(int, fls_long(size),
				       PAGE_SHIFT, IOREMAP_MAX_ORDER);

	size = PAGE_ALIGN(size);
	if (unlikely(!size))
		return NULL;

	/* 分配vm_struct
	 * 并且初始化全0
	 */
	area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
	if (unlikely(!area))
		return NULL;
    /* 如果没有标记，size要多算一个guard page用于分隔 */
	if (!(flags & VM_NO_GUARD))
		size += PAGE_SIZE;
	/* 分配vmap_area */
	va = alloc_vmap_area(size, align, start, end, node, gfp_mask);
	if (IS_ERR(va)) {
		kfree(area);
		return NULL;
	}

	/* 初始化 */
	setup_vmalloc_vm(area, va, flags, caller);

	return area;
}

alloc_vmap_area会缓存上次一次搜索的节点到free_vmap_cache, 这样是认为一般虚拟内存是按顺序连续分配的, 如果通过缓存没有搜索到就要从全局的vmap_area_root开始搜索.

这里说明一下vmap_area的分配过程, 主要是在红黑树中根据所指定的区间寻找合适的点,如果找到一个区间正好包含了vstart,那么在这个区间链表后面寻找合适的空洞进行分配就可以, 也有可能在红黑书上找到的就是空洞就不用接着遍历了, 总之搜索的过程是先红黑书然后再链表.

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/*
 * Allocate a region of KVA of the specified size and alignment, within the
 * vstart and vend.
 */
static struct vmap_area *alloc_vmap_area(unsigned long size,
				unsigned long align,
				unsigned long vstart, unsigned long vend,
				int node, gfp_t gfp_mask)
{
	struct vmap_area *va;
	struct rb_node *n;
	unsigned long addr;
	int purged = 0;
	struct vmap_area *first;

	BUG_ON(!size);
	BUG_ON(offset_in_page(size));
	BUG_ON(!is_power_of_2(align));

	might_sleep_if(gfpflags_allow_blocking(gfp_mask));

	va = kmalloc_node(sizeof(struct vmap_area),
			gfp_mask & GFP_RECLAIM_MASK, node);
	if (unlikely(!va))
		return ERR_PTR(-ENOMEM);

	/*
	 * Only scan the relevant parts containing pointers to other objects
	 * to avoid false negatives.
	 */
	kmemleak_scan_area(&va->rb_node, SIZE_MAX, gfp_mask & GFP_RECLAIM_MASK);

retry:
	spin_lock(&vmap_area_lock);
	/*
	 * Invalidate cache if we have more permissive parameters.
	 * cached_hole_size notes the largest hole noticed _below_
	 * the vmap_area cached in free_vmap_cache: if size fits
	 * into that hole, we want to scan from vstart to reuse
	 * the hole instead of allocating above free_vmap_cache.
	 * Note that __free_vmap_area may update free_vmap_cache
	 * without updating cached_hole_size or cached_align.
	 */
	if (!free_vmap_cache || /* 缓存为空, 并且在下面条件满足的时候不使用缓存 */
			size < cached_hole_size || /* 至少有一个空洞可以复用, 直接从头开始搜索 */
			vstart < cached_vstart || /* 别缓存的起点小 */
			align < cached_align) { /* 对齐大小比缓存的小 */
nocache:
		cached_hole_size = 0;
		free_vmap_cache = NULL;
	}
	/* record if we encounter less permissive parameters */
	cached_vstart = vstart;
	cached_align = align;

	/* find starting point for our search */
	if (free_vmap_cache) { /* 这个地方是用缓存上次搜索的结果, 每次找到以后会存到这里 */
		first = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
		addr = ALIGN(first->va_end, align);
		if (addr < vstart) /* 缓存的末尾对齐之后超出了范围从头开始搜索 */
			goto nocache;
		if (addr + size < addr) /* 整数溢出 */
			goto overflow;

	} else {
		addr = ALIGN(vstart, align);
		if (addr + size < addr)
			goto overflow;

		n = vmap_area_root.rb_node;
		first = NULL;

		while (n) { /* 用对齐之后的vstart正好<=va_ned&&>=va_start的节点 */
			struct vmap_area *tmp;
			tmp = rb_entry(n, struct vmap_area, rb_node);
			if (tmp->va_end >= addr) {
				first = tmp;
				if (tmp->va_start <= addr)
					break;
				n = n->rb_left;
			} else
				n = n->rb_right;
		}

		if (!first)
			goto found;
	}
	/* from the starting point, walk areas until a suitable hole is found */
	while (addr + size > first->va_start && addr + size <= vend) {
		if (addr + cached_hole_size < first->va_start) /* cached_hole_size */
			cached_hole_size = first->va_start - addr; /* 缓存最大的空洞大小 */
		addr = ALIGN(first->va_end, align);
		if (addr + size < addr)
			goto overflow;

		if (list_is_last(&first->list, &vmap_area_list))
			goto found;

		first = list_next_entry(first, list);
	}

found:
	if (addr + size > vend)
		goto overflow;

	va->va_start = addr;
	va->va_end = addr + size;
	va->flags = 0;
	__insert_vmap_area(va); /* 插入到红黑书和链表当中 */
	free_vmap_cache = &va->rb_node;
	spin_unlock(&vmap_area_lock);

	BUG_ON(!IS_ALIGNED(va->va_start, align));
	BUG_ON(va->va_start < vstart);
	BUG_ON(va->va_end > vend);

	return va;

overflow:
	spin_unlock(&vmap_area_lock);
	if (!purged) {
		purge_vmap_area_lazy();
		purged = 1;
		goto retry;
	}

	if (gfpflags_allow_blocking(gfp_mask)) {
		unsigned long freed = 0;
		blocking_notifier_call_chain(&vmap_notify_list, 0, &freed);
		if (freed > 0) {
			purged = 0;
			goto retry;
		}
	}

	if (printk_ratelimit())
		pr_warn("vmap allocation for size %lu failed: use vmalloc=<size> to increase size\n",
			size);
	kfree(va);
	return ERR_PTR(-EBUSY);
}


建立映射

成功分配好vm_struct之后就可以建立映射了.
__vmalloc_area_node的过程首先是分配物理页,调用alloc_kmem_pages,这个函数和alloc_pages不同的是套了一层cgroup的kmem计数器,来限制内存分配, 然后再调用map_vm_area在页表上建立映射,内部调用的是vmap_page_range,指定了vm_struct的start和end, 而vmap_page_range则调用了vmap_page_range_noflush迭代去初始化各级页表. 内核的虚拟地址的映射就全部完成了.

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
/*
 *
 * Set up page tables in kva (addr, end). The ptes shall have prot "prot", and
 * will have pfns corresponding to the "pages" array.
 * 这里的kva指的是kernel virtual address.
 * Ie. pte at addr+N*PAGE_SIZE shall point to pfn corresponding to pages[N]
 */
static int vmap_page_range_noflush(unsigned long start, unsigned long end,
				   pgprot_t prot, struct page **pages)
{
	pgd_t *pgd;
	unsigned long next;
	unsigned long addr = start;
	int err = 0;
	int nr = 0;

	BUG_ON(addr >= end);
	pgd = pgd_offset_k(addr); /* 把虚拟地址hash到pgd */
	do {
		next = pgd_addr_end(addr, end); /* 获取下一个pgd */
		err = vmap_pud_range(pgd, addr, next, prot, pages, &nr); /* 再去初始化 pud pmd pte */
		if (err)
			return err;
	} while (pgd++, addr = next, addr != end);

	return nr;
}


对应的调用关系如图.

释放

释放的入口是vfree, 这个函数首先通过in_interrupt检查是否在中断上下文, 如果是正处于中断中则使用workqueue传入vfree_deferred用workqueue进行释放, 不然就直接调用__vunmap来释放, 它会调用remove_vm_area, 最终调用用unmap_vmap_area重置页表, 然后用free_vmap_area_noflush把vmp_area加入到vmap_purge_list这个链表当中, 放入这个链表之后只有链表长度超过阈值才会尝试调用try_purge_vmap_area_lazy真正释放掉vmap_area,释放过程主要是从红黑树中移除, 然后把自己也给free掉, 这是一个延迟的释放过程, 最后把把vm_struct自己和它管理的物理页全部释放. 调用图如图所示.

总结

vmalloc主要是针对连续地址分配的需求, 涉及两个部分, 一个是虚拟地址的管理以及到物理地址的映射. 其中虚拟地址的管理比较麻烦一点, 用链表红黑树保存了每个vmap_area并且寻找合适的空洞用于分配虚拟地址. 而物理地址的分配之前我的博客已经讲过了, 建立映射只要设置对应的页表项就OK了.

参考

  1. 《LINUX3.0内核源代码分析》第四章: 内存管理

  2. linux内存管理之vmalloc

  3. lkvm