Linux内部使用页框来管理物理内存,在实际应用中,经常需要分配一组连续的页框,而频繁地申请和释放不同大小的连续页框,必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样,即使这些页框是空闲的,但要分配一个大块的连续页框就可能无法满足。

Linux采用了伙伴系统来解决上述难题。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请1024个连续页框,对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。例如,大小为16个页框的块,其起始地址是16×212的倍数。内存中的空闲页框组织形式如下图:

 

假设要申请一个256个页框的块,先从256个页框的链表中查找空闲块,如果没有,就去512个页框的链表中找,找到了则将页框块分为2个256个页框的块,一个分配给应用,另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块,继续向1024个页框的链表查找,如果仍然没有,则返回错误。

页框块在释放时,内核会主动将两个互为伙伴的页框块合并为一个较大的页框块,成功后会试图寻找伙伴并合并为更大的内存块,直至块的大小超过上限或者没有伙伴为止。互为伙伴的两个内存块必须符合以下条件:

1、两个块具有相同的大小;

2、两个块的物理地址连续;

3、第一个快的物理地址是两个块大小的整数倍。

如果不太理解,可以参考下图:

 

在上图中,128K大小的AL和AR互为伙伴,CRL和CRR也互为伙伴。

每一个内存节点(NUMA)的每一个内存区(ZONE_DMA、ZONE_NORMAL、ZONE_MEMHIGH)都存在一个伙伴系统,所有这些伙伴系统通过fallback链表连接起来。通过读取/proc/buddyinfo文件可以获知系统当前伙伴系统的工作状况(因为分配给虚拟机的内存不足1G,所以没有HIGHMEM内存区):

 

经典的伙伴系统算法能够在很大程度上减少内存碎片,但是它的缺点也很明显,它仅寄希望于释放内存时的合并操作而不管分配内存时的策略。考虑下述情况,假设内存区有32个页框,并且分配了4个保留的内存块(如下图),那么以后最大可分配的连续内存块大小仅能为8,因为伙伴系统只能处理2的幂次方的内存块大小。如果这几个内存块长时间不能被释放,那情况就更糟了。

 

为了解决这个问题,Linux 2.6.24及后续版本引入了MIGRATE_TYPE的概念。对于每种大小的内存块链表,内核根据待申请内存的“可移动性”将其分为以下几种类型:

?View Code C
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MIGRATE_UNMOVABLE 0
#define MIGRATE_RECLAIMABLE 1
#define MIGRATE_MOVABLE 2
#define MIGRATE_PCPTYPES 3 /* the number of types on the pcp lists */
#define MIGRATE_RESERVE 3
#define MIGRATE_ISOLATE 4 /* can't allocate from here */
#define MIGRATE_TYPES 5

//在经典伙伴系统中,每种大小的内存块只有一个链表:
struct free_area {
  struct list_head    free_list;
  unsigned long       *map;
};

//而在最新的Linux伙伴系统中,每种大小的内存块按照MIGRATE_TYPE被存放在不同的链表中了:
struct free_area {
  struct list_head    free_list[MIGRATE_TYPES];
  unsigned long       nr_free;
};

在调用内核函数__alloc_pages()分配页框时的第一个参数gfp_flags用来指定内存分配策略,默认情况下是不可移动的(MIGRATE_UNMOVABLE),如果指定了__GFP_MOVEABLE和__GFP_RECLAIMABLE标识,则分别表示要申请的内存是可移动的(MIGRATE_MOVABLE)和可回收的(MIGRATE_RECLAIMABLE)。函数allocflags_to_migratetype()用于将gfp_flags转换为freelist的索引。

但是如果申请者指定了gfp_flags,但对应的freelist没有可用的内存块怎么办?内核采用了一种类似于在不同内存区中分配内存的策略——提供一个fallbacks,当指定类型的链表内存块不足时,可根据预定策略从其他链表中分配,并且如果分配的内存区较大的话,直接把满足申请大小的2的幂次方的内存块转移到资源匮乏的链表中,一次转移一大块可以避免给来源链表引入碎片。

系统启动时会根据物理内存的大小初始化伙伴系统,因为如果物理内存太小的话没有必要使用MIGRATE_TYPES机制,所以内核需要一个量度。pageblock_order被认为是一个“大”的幂值,而pageblock_nr_pages则代表相应页面数。这两个变量在include/linux/pageblock-flags.h中被定义如下:

?View Code C
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifdef CONFIG_HUGETLB_PAGE 

#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE

/* Huge page sizes are variable */
extern int pageblock_order;

#else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */   

/* Huge pages are a constant size */
#define pageblock_order         HUGETLB_PAGE_ORDER

#endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */

#else /* CONFIG_HUGETLB_PAGE */

/* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
#define pageblock_order         (MAX_ORDER-1)

#endif /* CONFIG_HUGETLB_PAGE */

#define pageblock_nr_pages      (1UL << pageblock_order)

由以上代码可以看出,如果启用了扩展分页,那么pageblock_order就会被定义为HUGETLB_PAGE_ORDER(随处理器架构不同而不同)。在x86系统上,因为HUGETLB_PAGE_ORDER等于10,MAX_ORDER-1也等于10,所以pageblock_order的值通常为10,pageblock_nr_pages就等于1024。关于CONFIG_HUGETLB_PAGE的更多信息见内核文档/Documentations/vm/hugetlbpage.txt。

这样一来,内核在初始化伙伴系统时就有迹可循了。build_all_zonelists函数会检测物理内存是否充足,如果内存不足就将page_group_by_mobility_disabled置为1。memmap_init_zone函数会在内存子系统启动时将所有的内存块标记为Movable(调用set_pageblock_migratetype函数)并放在MIGRATE_MOVABLE链表中。

最后,通过读取/proc/pagetypeinfo文件可以查看各个类型链表的详细信息:

?View Code BASH
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[ari@fedora linux-3.0.1]$ cat /proc/pagetypeinfo 
Page block order: 10
Pages per block:  1024

Free pages count per migrate type at order       0      1      2      3      4      5      6      7      8      9     10 
Node    0, zone      DMA, type    Unmovable      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type  Reclaimable      7      4      8      3      2      2      1      0      0      0      0 
Node    0, zone      DMA, type      Movable      4      1      1      0      3      7      2      1      0      0      0 
Node    0, zone      DMA, type      Reserve      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone   Normal, type    Unmovable    172     15     15      0      0      0      0      0      0      0      0 
Node    0, zone   Normal, type  Reclaimable     24     36      8      1      0      0      0      0      0      0      0 
Node    0, zone   Normal, type      Movable      0   2264   2559     98      0      0      0      0      0      0      0 
Node    0, zone   Normal, type      Reserve      0      0      3      2      3      3      1      2      0      1      0 
Node    0, zone   Normal, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 

Number of blocks type     Unmovable  Reclaimable      Movable      Reserve      Isolate 
Node 0, zone      DMA            0            0            4            0            0 
Node 0, zone   Normal            9            7          171            1            0

Linux伙伴系统源码解析

Linux中伙伴系统实现代码位于mm/page_alloc.c,现将主要函数列出来(点击下面展开代码):

?View Code C
 

其中涉及的函数比较多,现将它们的调用关系列出来:

分配内存:(alloc_pages -> alloc_pages_current -> __alloc_pages_nodemask -> get_page_from_freelist -> buffered_rmqueue ->) rmqueue_bulk -> __rmqueue -> __rmqueue_smallest, __rmqueue_fallback -> expand

释放内存:free_pages -> __free_pages -> __free_pages_ok -> free_one_page -> __free_one_page -> __find_buddy_index, page_is_buddy

分配内存调用链中括号内的函数并没有在以上列出,它们有的不在alloc_pages.c中。
以上函数大多为包装函数,其中伙伴系统的核心是分配页框的__rmqueue_smallest、__rmqueue_fallback、expand以及释放页框的__free_one_page、__find_buddy_index。

下面把这几个函数单独拿出来,并以注释的形式来说明:

?View Code C
 
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
/* 
 * 这个函数负责寻找页框号为page_idx, 大小为order的伙伴,这个函数的实质是转换
 * page_idx第order位的值。因此,如果这个位原来是0,伙伴页框号就等于page_idx + order_size;
 * 相反,如果这个位原来是1,伙伴页框号就等于page_idx - order_size;
 * 举个例子,页框号为4,大小为4的伙伴页框号等于 0100 ^ 0100 = 0;
 * 页框号为8,大小为4的伙伴页框号等于 1000 ^ 0100 = 12;
 */
static inline unsigned long
__find_buddy_index(unsigned long page_idx, unsigned int order)
{
	return page_idx ^ (1 << order);
}

/*
 * 释放一个内存块,已知它的大小、首页框指针、MIGRATE_TYPE及内存管理区描述符
 */
static inline void __free_one_page(struct page *page,
		struct zone *zone, unsigned int order,
		int migratetype)
{
	unsigned long page_idx;
	unsigned long combined_idx;
	unsigned long uninitialized_var(buddy_idx);
	struct page *buddy;

	/* 检查待释放内存块的合法性 */
	if (unlikely(PageCompound(page)))
		if (unlikely(destroy_compound_page(page, order)))
			return;

	VM_BUG_ON(migratetype == -1);

	/* 得到内存块第一个页框的页框号 */
	page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);

	VM_BUG_ON(page_idx & ((1 << order) - 1));
	VM_BUG_ON(bad_range(zone, page));

	/* 
	 * 为此内存块寻找伙伴块并试图合并
	 * 合并成功后继续寻找试图合成更大的内存块
	 */
	while (order < MAX_ORDER-1) {
		buddy_idx = __find_buddy_index(page_idx, order);	/* 寻找伙伴块的页框号 */
		buddy = page + (buddy_idx - page_idx);			/* 得到伙伴块首页框指针 */
		if (!page_is_buddy(page, buddy, order))			/* 检查是否是伙伴块(合法性、大小、可用性等) */
			break;

		/* 找到了可合并的伙伴块 */
		list_del(&buddy->lru);					/* 将伙伴块从它原来的链表上移除 */
		zone->free_area[order].nr_free--;			/* 伙伴块order链表可用内存块数减一 */
		rmv_page_order(buddy);					/* 清除伙伴块首页框的order值 */
		combined_idx = buddy_idx & page_idx;			/* 合并后的内存块首页框号 */
		page = page + (combined_idx - page_idx);		/* 得到合并后的内存块首页框地址 */
		page_idx = combined_idx;				/* 将page_idx设为合并后的内存块首页框框好,以进行迭代操作 */
		order++;						/* 将order提高一个等级 */
	}
	set_page_order(page, order);

	/*
	 * 如果最后合并成的内存块不是最大的,那就检查更高order的伙伴内存块是否空闲。
	 * 如果是,那么就有可能在当前内存块的伙伴块被释放后会和此更高order的伙伴内存块继续合并,
	 * 因为存在这种可能性,所以我们把当前的内存块插入到链表的尾部,这样马上被分配出去的
	 * 可能性就会降低,继续合并为更大内存块的可能性就会提高了。
	 * 如果不太好理解,就看个例子。现在经过合并已经得到了一个首页框号为4,大小为4的内存块,
	 * 但是它的伙伴————首页框号为0大小为4的内存块正在使用,因此无法合并。再假设首页框号为0的内存块被释放了,
	 * 那么它们就能合并成一个首页框号为0,大小为8的内存块,再查看这个大内存块是否有可合并的伙伴块,如果有,
	 * 就说明现在应该把当前内存块“藏”起来等待继续合并成更大的内存块了。
	 */
	if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
		struct page *higher_page, *higher_buddy;
		combined_idx = buddy_idx & page_idx;
		higher_page = page + (combined_idx - page_idx);
		buddy_idx = __find_buddy_index(combined_idx, order + 1);
		higher_buddy = page + (buddy_idx - combined_idx);
		if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
			list_add_tail(&page->lru,
				&zone->free_area[order].free_list[migratetype]);
			goto out;
		}
	}

	/* 不符合上述条件,添加到链表首部等待下次分配 */
	list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
out:
	zone->free_area[order].nr_free++;	/* 添加到链表的空闲块数加1 */
}

/*
 * 当为了满足2的h次方个页框的请求而有必要使用2的k次方个页框的块时(h < k),就分配前面的2的h次方个
 * 页框,而把后面2的k次方 - 2的h次方个页框循环再分配给free_area链表中下标在k到h之间的元素。
 * 例如为了分配256个页框大小的内存块而必须要从1024页框大小的内存块链表上取,那么就把这些内存块中的前256个分配出去,最后
 * 512个内存块插入到order为9的链表中,中间的256个内存块插入到order为8的内链表中。
 */
static inline void expand(struct zone *zone, struct page *page,
	int low, int high, struct free_area *area,
	int migratetype)
{
	unsigned long size = 1 << high;

	while (high > low) {
		area--;
		high--;
		size >>= 1;
		VM_BUG_ON(bad_range(zone, &page[size]));
		list_add(&page[size].lru, &area->free_list[migratetype]);
		area->nr_free++;
		set_page_order(&page[size], high);
	}
}

/*
 * 依次遍历满足所需order的链表并从第一个非空闲链表中分配页框
 */
static inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
						int migratetype)
{
	unsigned int current_order;
	struct free_area * area;
	struct page *page;

	/* 从指定order的链表开始遍历,如果遍历到MAX_ORDER-1了还未找到空闲块就放弃 */
	for (current_order = order; current_order < MAX_ORDER; ++current_order) {
		area = &(zone->free_area[current_order]);
		if (list_empty(&area->free_list[migratetype]))		/* 该链表中是否有空闲内存块? */
			continue;

		page = list_entry(area->free_list[migratetype].next,	/* 得到第一个空闲内存块首页框地址 */
							struct page, lru);
		list_del(&page->lru);					/* 将内存块从该链表中摘掉 */
		rmv_page_order(page);					/* 删除原来的order标识 */
		area->nr_free--;					/* 当前链表空闲块数递减 */
		expand(zone, page, order, current_order, area, migratetype); 	/* 将内存块中的多余部分分配给order更低的链表 */
		return page;
	}

	return NULL;
}

static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
	[MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* 未用 */

/*
 * __rmqueue函数调用__rmqueue_smallest函数分配失败了,这就意味着指定MIGRATE_TYPE的链表中没有足够大的空闲内存块了。
 * 这时候__rmqueue会继续尝试调用__rmqueue_fallback来分配,即从其他MIGRATE_TYPE的链表中分配。
 * 分配策略由fallbacks数组指定。
 */
static inline struct page *
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
{
	struct free_area * area;
	int current_order;
	struct page *page;
	int migratetype, i;

	/* 从其他MIGRATE_TYPE的链表中最大的内存块开始寻找 */
	for (current_order = MAX_ORDER-1; current_order >= order;
						--current_order) {
		for (i = 0; i < MIGRATE_TYPES - 1; i++) {
			migratetype = fallbacks[start_migratetype][i];

			/* 此时MIGRATE_RESERVE将被忽略,因为如果确实需要从MIGRATE_RESERVED分配内存时,
			 * __rmqueue函数会以MIGRATE_RESERVED为参数再次调用__rmqueue_smallest */
			if (migratetype == MIGRATE_RESERVE)
				continue;

			area = &(zone->free_area[current_order]);
			if (list_empty(&area->free_list[migratetype]))
				continue;

			/* 得到空闲块首页框的地址 */
			page = list_entry(area->free_list[migratetype].next,
					struct page, lru);
			area->nr_free--;

			/*
			 * 如果这是一个相对较大的内存块,或者待分配内存块是可移动的,
			 * 就把这个内存块整个转移到资源不足的链表中
			 */
			if (unlikely(current_order >= (pageblock_order >> 1)) ||
					start_migratetype == MIGRATE_RECLAIMABLE ||
					page_group_by_mobility_disabled) {
				unsigned long pages;

				/* 
				 * 把从page起始往后的pageblock_nr_pages个内存页框中空闲的内存块
				 * 转移到资源不足的链表中
				 */
				pages = move_freepages_block(zone, page,
								start_migratetype);

				/* 如果这块内存区的大半页框是空闲的,就重新给它设置MIGRATE_TYPE */
				if (pages >= (1 << (pageblock_order-1)) ||
						page_group_by_mobility_disabled)
					set_pageblock_migratetype(page,
								start_migratetype);

				/* 注意现在migratetype已经成了start_migratetype */
				migratetype = start_migratetype;
			}

			/* 将page从freelist链表中摘除 */
			list_del(&page->lru);
			rmv_page_order(page);

			/* 如果current_order >= pageblock_order,还是设置内存块的MIGRATE_TYPE */
			if (current_order >= pageblock_order)
				change_pageblock_range(page, current_order,
							start_migratetype);

			/* 最后将内存块中的多余部分分配给order更低的链表 */
			expand(zone, page, order, current_order, area, migratetype);

			trace_mm_page_alloc_extfrag(page, order, current_order,
				start_migratetype, migratetype);

			return page;
		}
	}

	return NULL;
}