buddy-system-内核物理页管理的实现

很多人看内核物理页的分配都喜欢从__alloc_pages开始看,喜欢从程序的执行流程去看问题,其实可换个思路,从开发或者说实现的角度去理解物理页的分配效果可能更好,所以这篇博客,反其道而行之,基于4.7.2的内核代码, 由内向外解释物理页的分配过程的细节.

binary buddy system allocation 算法

伙伴分配器算法的流程如下:

  1. 如果内存被分配
    1. 寻找一个合适大小的内存(要求是: 大于 requested memory, 同时以\(2^k\)为量纲最小的块, 也就是分配一个满足要求的最小块)
      1. 如果找到了直接分配
      2. 如果没有找到, 需要进行如下尝试
        1. 拆分一个比 requested memory 更大的内存块(比如比之前没找到的\(2^x\)大的\(2^{x+1}\), 分成两半.
        2. 如果拆分出来的一半满足requested memory, 并且不能再分了, 已经是最小的了, 就分配该块.
        3. 重复1, 寻找合适大小的内存块.
        4. 重复这个流程直到找到合适的内存块.
  2. 如果内存被释放
    1. 释放\(2^k\)内存块
    2. 查看内存块的伙伴也就是分配之后的另一半\(2^k\)块是否也free了
    3. 如果是,则会回到2并且重复执行直到所有内存被释放或者有一个伙伴没有被free掉, 无法合并.

内存碎片

内存碎片有两种,一种是External fragmentation和Internal Fragmentation, 前者是因为内存块划分的太小而无法满足大的内存分配的需要, 在这点上内核遇到的大内存块分配其实并不多, 而且通过vmalloc把不连续的物理地址映射成连续的虚拟地址很好的解决了这个问题. 后者的解决方法是引入了slab allocator, 对小内存进行了有效的缓存, 避免了Internal fragmentation的情况.

具体实现

每个struct zone结构有一个struct free_area free_area[MAX_ORDER];的定义, 对应的结构如下.

1
2
3
4
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};

所以整个的空闲块的管理结构如图.

每一个free_area用来存储一种\(2^k\)块,用链表链接,MAX_ORDER表示的允许最大的块就是\(2^{MAX_ORDER}\)大小.

migratetype

图中省略了MIGRATE_TYPES的表示, 仔细观察free_list是一个数组每个代表了一种migratetype, 用于page分配从node之间迁移的, 让内存尽量分配在离CPU近的node上, 这个特性是在2.6.32.25引入的, 同时对外部碎片的现象进行了优化, 这一点是这么理解的, 外部碎片是因为小内存块的分配位置可能占据了某个地方, 导致大的内存块无法分配出来, 比如说如果这个页是一些内核的永久数据可能这个碎片就会一直存在, 但是我们提前从可移动页分配一大块内存来给不可移动页, 那么内存碎片就不会影响到可移动页的分配, 这样就不会让内核初始化的时候分配的一些永久性的内存导致碎片影响了其他内存的分配,下面我们看看迁移类型的具体定义.

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
/*
* PAGE_ALLOC_COSTLY_ORDER is the order at which allocations are deemed
* costly to service. That is between allocation orders which should
* coalesce naturally under reasonable reclaim pressure and those which
* will not.
*/
/* 内核认为超过8个页算是大的内存分配 */
#define PAGE_ALLOC_COSTLY_ORDER 3

enum {
MIGRATE_UNMOVABLE,
MIGRATE_MOVABLE,
MIGRATE_RECLAIMABLE,
MIGRATE_PCPTYPES, /* the number of types on the pcp lists */
MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
/*
* MIGRATE_CMA migration type is designed to mimic the way
* ZONE_MOVABLE works. Only movable pages can be allocated
* from MIGRATE_CMA pageblocks and page allocator never
* implicitly change migration type of MIGRATE_CMA pageblock.
*
* The way to use it is to change migratetype of a range of
* pageblocks to MIGRATE_CMA which can be done by
* __free_pageblock_cma() function. What is important though
* is that a range of pageblocks must be aligned to
* MAX_ORDER_NR_PAGES should biggest page be bigger then
* a single pageblock.
*/
MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
MIGRATE_ISOLATE, /* can't allocate from here */
#endif
MIGRATE_TYPES
};

这里简单解释一下:

  1. MIGRATE_UNMOVABLE
    这种类型的页的位置是固定不变的, 不可以移动, 内核中大部分数据是这样的.
  2. MIGRATE_MOVABLE
    不能够直接移动,但是可以删除,而内容则可以从某些源重新生成.如文件数据映射的页面则归属此类.
  3. MIGRATE_RECLAIMABLE
    可以移动。分配给用户态程序运行的用户空间页面则为该类.由于是通过页面映射而得,将其复制到新位置后,更新映射表项,重新映射,应用程序是不感知的.
  4. MIGRATE_PCPTYPES
    是一个分界数,小于这个数的都是在pcplist上的.
  5. MIGRATE_CMA
    连续内存分配,用于避免预留大块内存导致系统可用内存减少而实现的,即当驱动不使用内存时,将其分配给用户使用,而需要时则通过回收或者迁移的方式将内存腾出来。
  6. MIGRATE_ISOLATE
    表示NUMA不能夸node迁移page, 让cpu和节点之间保持亲和性.
  7. MIGRATE_TYPES
    分界数, 低于这个才是迁移类型.

实现概要

实际上的合并对应的是通过小块合并成大块从下级的free_area的链表中移除, 然后添加到上一层free_area当中. 拆分则相反, 从上级free_area当中删除大块, 并且拆分成两个小块, 加入到下层free_area的list当中, 当然, 如果有一块符合需求就直接分配了. 这就是整个物理页分配的核心内容.

分配

整个算法的入口是__rmqueue, 从伙伴分配器中分配对应\( 2^{order} \) 的物理块.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* Do the hard work of removing an element from the buddy allocator.
* Call me with the zone->lock already held.
*/
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
{
struct page *page;

page = __rmqueue_smallest(zone, order, migratetype);
if (unlikely(!page)) {
if (migratetype == MIGRATE_MOVABLE)
page = __rmqueue_cma_fallback(zone, order); /* MOVABLE的失败优先从cma迁移 */

if (!page)
page = __rmqueue_fallback(zone, order, migratetype); /* 失败的话会从其他备选迁移类型当中迁移page */
}

trace_mm_page_alloc_zone_locked(page, order, migratetype);
return page;
}

分配失败退化的行为在后面讨论,先看主要路径, 算法主要体现在__rmqueue_smallest这个函数上, 依次从order开始向上寻找free_area并从list当中取出page块.

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
/*
* Go through the free lists for the given migratetype and remove
* the smallest available page from the freelists
*/
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;

/* Find a page of the appropriate size in the preferred list */
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
area = &(zone->free_area[current_order]);
page = list_first_entry_or_null(&area->free_list[migratetype],
struct page, lru);
if (!page)
continue; /* 如果失败就尝试更大的块 */
list_del(&page->lru); /* 这个lru取决他的上下文,比如在这里就是free_list */
rmv_page_order(page); /* 设置flags */
area->nr_free--; /* free计数器-1 */
expand(zone, page, order, current_order, area, migratetype);
set_pcppage_migratetype(page, migratetype);/* 设置page的migratetype */
return page;
}
return NULL;
}

从下往上找到合适的块以后再从上往下进行拆分, 这依赖于expand函数完成:

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
/*
* The order of subdivision here is critical for the IO subsystem.
* Please do not alter this order without good reasons and regression
* testing. Specifically, as large blocks of memory are subdivided,
* the order in which smaller blocks are delivered depends on the order
* they're subdivided in this function. This is the primary factor
* influencing the order in which pages are delivered to the IO
* subsystem according to empirical testing, and this is also justified
* by considering the behavior of a buddy system containing a single
* large block of memory acted on by a series of small allocations.
* This behavior is a critical factor in sglist merging's success.
*
* -- nyc
*/
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_PAGE(bad_range(zone, &page[size]), &page[size]);
/* guardpage TODO */
if (IS_ENABLED(CONFIG_DEBUG_PAGEALLOC) &&
debug_guardpage_enabled() &&
high < debug_guardpage_minorder()) {
/*
* Mark as guard pages (or page), that will allow to
* merge back to allocator when buddy will be freed.
* Corresponding page table entries will not be touched,
* pages will stay not present in virtual address space
*/
set_page_guard(zone, &page[size], high, migratetype);
continue;
}
list_add(&page[size].lru, &area->free_list[migratetype]); /* 把page放到area的free_list里面, 这个page是一个数组形式的 比如之前是8 这里变成4,那么后半部分会被留下来,前半部分会继续用于迭代 */
area->nr_free++; /* 空闲块计数器+1 */
set_page_order(&page[size], high); /* 相当于page->private = high 表示自己属于order为high的阶的block中 */
}
}

expand 就是向下一层的free_area留一半, 然后接着用另一半进行迭代.

举个例子说明分配的过程:

假设当前需要从zone当中分配一个order为1的page, 就会从下往上找到一个可以分配的块.

从1开始迭代到2, 发现2有可以分配的\(2^3\)page, 然后进入expand, 进行拆分.

拆分以后一半用于分配一半进入了同一层的free_list当中,如图所示, 核心流程非常简洁明了.

现在再重新回到__rmqueue,分析这个函数后半部分的fallback行为是如何迁移的.
首先如果编译选项带了CMA就会有具体内容, 其实就是再尝试从MIGRATE_CMA当中再分配一次page.

1
2
3
4
5
6
7
8
9
10
#ifdef CONFIG_CMA
static struct page *__rmqueue_cma_fallback(struct zone *zone,
unsigned int order)
{
return __rmqueue_smallest(zone, order, MIGRATE_CMA);
}
#else
static inline struct page *__rmqueue_cma_fallback(struct zone *zone,
unsigned int order) { return NULL; }
#endif

之后是一般性的退化流程是__rmqueue_fallback这个函数.
说这个函数之前需要看一张表.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/*
* This array describes the order lists are fallen back to when
* the free lists for the desirable migrate type are depleted
*/
static int fallbacks[MIGRATE_TYPES][4] = {
[MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_TYPES },
[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_TYPES },
[MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
#ifdef CONFIG_CMA
[MIGRATE_CMA] = { MIGRATE_TYPES }, /* Never used */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
[MIGRATE_ISOLATE] = { MIGRATE_TYPES }, /* Never used */
#endif
};

这张表描述的是当一种类型无法满足时退化选择的迁移类型的一个顺序.接下来看函数的实现.

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

/* Remove an element from the buddy allocator from the fallback list */
static inline struct page *
__rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
{
struct free_area *area;
unsigned int current_order;
struct page *page;
int fallback_mt;
bool can_steal;

/* Find the largest possible block of pages in the other list */
for (current_order = MAX_ORDER-1;
current_order >= order && current_order <= MAX_ORDER-1;
--current_order) {
area = &(zone->free_area[current_order]);
/* 遍历fallback table 找到合适的fallback migratetype 要综合考虑: 是否有超过一定阈值的空闲页,并且是可以退化的页类型 */
fallback_mt = find_suitable_fallback(area, current_order,
start_migratetype, false, &can_steal);
if (fallback_mt == -1)
continue;

page = list_first_entry(&area->free_list[fallback_mt],
struct page, lru);
/* 从对应迁类型中"偷取"page TODO:具体如何迁移的 我感觉应该是很抽象的迁移就可以了 */
if (can_steal)
steal_suitable_fallback(zone, page, start_migratetype);

/* Remove the page from the freelists */
area->nr_free--;
list_del(&page->lru);
rmv_page_order(page);

expand(zone, page, order, current_order, area,
start_migratetype);
/*
* The pcppage_migratetype may differ from pageblock's
* migratetype depending on the decisions in
* find_suitable_fallback(). This is OK as long as it does not
* differ for MIGRATE_CMA pageblocks. Those can be used as
* fallback only via special __rmqueue_cma_fallback() function
*/
set_pcppage_migratetype(page, start_migratetype);

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

return page;
}

return NULL;
}

和主要分配路径不同的事, 迭代器是从最大的阶数开始迭代的,这个代表的意思是说我尽量多迁移一点空间给你, 不然你还要迁移的时候我又分配一小块空间给你, 你的碎片间接导致了我的碎片产生, 所以从大到小开始迭代.

整个核心部分分析完以后, 按照从里向外分析的思路,这是基于__rmqueu的一套更高层次的函数, 再倒回来看alloc_pages的实现会发现非常容易理解.首先__alloc_pages调用__alloc_pages_nodemask. 这里补充一个结构体.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* Structure for holding the mostly immutable allocation parameters passed
* between functions involved in allocations, including the alloc_pages*
* family of functions.
*
* nodemask, migratetype and high_zoneidx are initialized only once in
* __alloc_pages_nodemask() and then never change.
*
* zonelist, preferred_zone and classzone_idx are set first in
* __alloc_pages_nodemask() for the fast path, and might be later changed
* in __alloc_pages_slowpath(). All other functions pass the whole strucure
* by a const pointer.
*/
struct alloc_context {
struct zonelist *zonelist;
nodemask_t *nodemask;
struct zoneref *preferred_zoneref;
int migratetype;
enum zone_type high_zoneidx;
bool spread_dirty_pages;
};

这个结构体主要是一些内存分配的参数, 因为从上到下的调用都一直有用到这几个参数所以合成一个context向下传递.

__alloc_pages_nodemask第一步会检查cpusets的功能是否打开, 这个是一个cgroup的子模块, 如果没有设置nodemask就会用cpusets配置的cpuset_current_mems_allowed来限制在哪个node上分配, 这个也是在NUMA结构当中才会有用的. 之后会用到might_sleep_if,判断gfp_mask & __GFP_DIRECT_RECLAIM), 表示当前内存压力比较大需要直接回收内存, 会循环睡眠同步等待页可用, 而might_sleep_if是一个debug函数,标记当前函数在iftrue的时候表示可能会进入睡眠, 如果当前调用进入了一个不可睡眠的上下文就会报错. should_fail_alloc_page会做一些预检查, 一些无法分配的条件会直接报错.
接着获取read_mems_allowed_begin,这个会拿到current当前进程的cpusets允许的节点分配掩码, 这个结果的读取通过顺序锁(seqcount_t)进行, 如果在分配page期间这个值发生了改变(通过read_mems_allowed_retry判断), 那么读操作需要重新进行尝试.
调用first_zones_zonelist会从zonelist这个表示分配page的zone的优先顺序链表里获取第一个zoneref, zoneref是一个链表节点用于迭代之后的zone选项.
接着就会调用关键函数get_page_from_freelist从而分配到页.
分配完页如果失败会调用__alloc_pages_slowpath唤起swapd进程进行页回收从而获取可用的页, 再尝试调用get_page_from_free_list.
函数的调用图如下.

这是最外层的一个过程, 但是内核往往经过了很多实践才会有这么一套机制, 内核在这一层之前加了一套缓存, 来加速物理页的分配, get_page_from_free_list到伙伴分配器之间还有一层高速缓存. 这个结构是一个percpu结构, 每个cpu独有一份链表缓存分配的页,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct per_cpu_pages {
int count; /* number of pages in the list */
int high; /* high watermark, emptying needed */
int batch; /* chunk size for buddy add/remove */

/* Lists of pages, one per migrate type stored on the pcp-lists */
struct list_head lists[MIGRATE_PCPTYPES];
};

struct per_cpu_pageset {
struct per_cpu_pages pcp;
#ifdef CONFIG_NUMA
s8 expire;
#endif
#ifdef CONFIG_SMP
s8 stat_threshold;
s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];
#endif
};

每个zone都会有一个这个结构用于缓存页的分配, 中文一般就叫高速缓存.

缓存的过程是这样的, 首先通过for_next_zone_zonelist_nodemask遍历每个zone 会选择合适的zone, 选择合适的zone一笔带过但其实考虑了很多因素比如是否满足分配的wartermark, 是否需要均衡到别的zone当中, 是否被cpusets禁止了分配等等, 然后调用buffered_rmqueue这个函数, 这个函数就是构建对buddy分配器裹了一层高速缓存. 这个函数在只分配1页(order=0)的情况下,会判断是不是”冷”页, bool cold = ((gfp_flags & __GFP_COLD) != 0), 冷页的区别是会放到高速缓存的末尾, 相反热页会放到高速缓存的头部. 然后尝试获取高速缓存的page, 如果高速缓存为空就调用rmqueue_bulk分配一段batch大小的页块到高速缓存中继续尝试分配, 而rmqueue_bulk就是循环了batch次分配了order=0的page逐个添加到高速缓存当中. 如果需要分配的order不为0的话还是会直接从buddy-system当中分配不依靠高速缓存. 高速缓存主要是缓存单页的分配.

所以调整后的走高速缓存的主流程就如下图所示.

释放

还是从伙伴系统的最内部实现向外说, 释放对应的是__free_one_page, 指定释放\(2^{order}\)的物理页块, 地址为page, 可以说释放过程是拆分过程的一个逆过程.

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
/*
* Freeing function for a buddy system allocator.
*
* The concept of a buddy system is to maintain direct-mapped table
* (containing bit values) for memory blocks of various "orders".
* The bottom level table contains the map for the smallest allocatable
* units of memory (here, pages), and each level above it describes
* pairs of units from the levels below, hence, "buddies".
* At a high level, all that happens here is marking the table entry
* at the bottom level available, and propagating the changes upward
* as necessary, plus some accounting needed to play nicely with other
* parts of the VM system.
* At each level, we keep a list of pages, which are heads of continuous
* free pages of length of (1 << order) and marked with _mapcount
* PAGE_BUDDY_MAPCOUNT_VALUE. Page's order is recorded in page_private(page)
* field.
* So when we are allocating or freeing one, we can derive the state of the
* other. That is, if we allocate a small block, and both were
* free, the remainder of the region must be split into blocks.
* If a block is freed, and its buddy is also free, then this
* triggers coalescing into a block of larger size.
*
* -- nyc
*/

static inline void __free_one_page(struct page *page, /* 把page加回到free_list里面 */
unsigned long pfn,
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;
unsigned int max_order;

max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1); /* 获取最大的阶数 */

VM_BUG_ON(!zone_is_initialized(zone)); /* 检查wait_table是否存在来表示zone是否初始化过 里面用到了双感叹号表示强制1或者0 */
VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);

VM_BUG_ON(migratetype == -1);
if (likely(!is_migrate_isolate(migratetype))) /* 是isolate类型 */
__mod_zone_freepage_state(zone, 1 << order, migratetype);

page_idx = pfn & ((1 << MAX_ORDER) - 1); /* 获取page的下标 */

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

continue_merging:
while (order < max_order - 1) {
buddy_idx = __find_buddy_index(page_idx, order);/* 获取buddy的下标 */
buddy = page + (buddy_idx - page_idx); /* 根据相对距离得到buddy page */
if (!page_is_buddy(page, buddy, order)) /* 如果不是buddy就结束合并 */
goto done_merging;
/*
* Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
* merge with it and move up one order.
*/
if (page_is_guard(buddy)) {
clear_page_guard(zone, buddy, order, migratetype);
} else {
/* 把buddy从free_area当中移除 */
list_del(&buddy->lru);
zone->free_area[order].nr_free--;
rmv_page_order(buddy);
}
combined_idx = buddy_idx & page_idx;
page = page + (combined_idx - page_idx);
page_idx = combined_idx;
order++; /* 向上合并 */
}
if (max_order < MAX_ORDER) {
/* If we are here, it means order is >= pageblock_order.
* We want to prevent merge between freepages on isolate
* pageblock and normal pageblock. Without this, pageblock
* isolation could cause incorrect freepage or CMA accounting.
*
* We don't want to hit this code for the more frequent
* low-order merging.
*/
/* 在这里说明已经超出了pageblock的order, 可能在不同的migratetype的block边界了,这里再检查一次是不是isolate, 不允许节点间迁移的page, 如果是的话就要结束合并的迭代,不然继续向上合并 */
if (unlikely(has_isolate_pageblock(zone))) {
int buddy_mt;

buddy_idx = __find_buddy_index(page_idx, order);
buddy = page + (buddy_idx - page_idx);
buddy_mt = get_pageblock_migratetype(buddy);

if (migratetype != buddy_mt
&& (is_migrate_isolate(migratetype) ||
is_migrate_isolate(buddy_mt)))
goto done_merging;
}
max_order++;
goto continue_merging;
}

done_merging:
set_page_order(page, order);/* 结束合并自后设置合并之后的阶数 */

/*
* If this is not the largest possible page, check if the buddy
* of the next-highest order is free. If it is, it's possible
* that pages are being freed that will coalesce soon. In case,
* that is happening, add the free page to the tail of the list
* so it's less likely to be used soon and more likely to be merged
* as a higher order page
*/
if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) { /* 这个条件判断没有合并到最大块, 内核认为很有可能接下来这个块和其他free的块合并, 从减少碎片的角度来说会更倾向于放到链表的末尾, 让这个块的free状态保持久一点, 更有机会被合并成更大的块 */
struct page *higher_page, *higher_buddy;
combined_idx = buddy_idx & page_idx; /* 合并后的idx */
higher_page = page + (combined_idx - page_idx); /* 合并后的page */
buddy_idx = __find_buddy_index(combined_idx, order + 1); /* 向上寻找buddy */
higher_buddy = higher_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]);
/* 把page加入到对应的order当中 */
out:
zone->free_area[order].nr_free++; /* free_area nr_free 空闲块加1 */
}

这个函数就是从order开始迭代不断寻找自己的buddy, 寻找buddy的函数是__find_buddy_index, 首先要说的是page是以数组的形式存放在mem_map当中, 整个page是可以通过index线性索引的.要找到自己的buddy只要在对应的order位进行抑或即可.

1
2
3
4
5
6
7
static inline unsigned long
__find_buddy_index(unsigned long page_idx, unsigned int order)
{
/* idx 抑或 2^order order那位是0, 那么buddy应该是1
* order那位是1, 那么buddy应该是0 */
return page_idx ^ (1 << order);
}

然后层层递归把低层的free_area中的page块向高层移动,最后有一个优化, 内核认为刚释放的page很可能相关的buddy页也会释放, 所以把刚释放的页放到末尾让他更晚被分配出去从而得到更多的机会被合并成大块.

现在再从外层看物理页的分配.

入口函数是__free_pages, 其实知道了分配的过程对于释放的过程可以说是轻而易举就能理解的.首先这个函数put_page_testzero会减少引用计数, 如果到达0才真正执行释放操作.释放路径有两个一个是order为0和不为0的情况, 为0很好理解, 需要交回到高速缓存即可, 如果高速缓存满了再交回给buddy system, 不为0说明也没有缓存过,就直接调用free_one_page,这个函数会调用__free_one_page,最终还给buddy system. 所以这里主要看一下代缓存的路径, 先是调用free_hot_cold_page, 指定是热页也就是添加到高速缓存的头,如果计数器超过阈值pcp->count >= pcp->high调用free_pcppages_bulk交还给buddy system, 这个函数可以遍历高速缓存中的migratetype,然后根据指定的count从高速缓存中交还给buddy system的页, 当前路径是整个batch个的页都会还回去.

带高速缓存的释放的调用图如图所示.

总结

伙伴分配器的确是一个非常简洁的算法(我认为可以递归表示和迭代表示算法都美妙无比), 但是内核对于这样一个简单的算法也结合了很多实际工程的内容还有一些优化,比如迁移类型还有冷热页的标记和高速缓存等等. 充分理解内核的物理页分配对于接下来理解slab分配起和内核虚拟内存的相关内容有很好的帮助作用. 文末给出了许多参考链接, 我结合了前人的知识进行总结, 并且基于最新的4.7.2的内核重新走了一遍分析之路, 做了解释和补充, 对自己的学习是一个积累, 同时希望对大家有帮助.

参考

  1. 迁移类型 实现反碎片
  2. 页面迁移
  3. LVMM 的Physical Page Allocation 章节
  4. Linux 物理页面分配
  5. 顺序锁