linux内核笔记（七）伙伴系统（Buddy System）
伙伴系统
在内核初始化完成后，内存管理的责任由伙伴系统（Buddy System）承担。它是基于一种相对简单效率的算法的高效的内存管理技术，一直到最新版本都还在使用。
伙伴系统的基本思想是将内存或资源分成大小相等的块（称为伙伴），每个块可以被分配给一个进程或线程使用。当一个进程或线程请求内存或资源时，系统会搜索一个空闲的伙伴来满足请求，如果找到了一个空闲的伙伴，系统会将其分配给请求者，并更新伙伴的状态为已分配。如果没有找到空闲的伙伴，系统会将一个较大的伙伴分裂成两个较小的伙伴，直到找到一个空闲的伙伴来满足请求。当释放内存或资源时，系统会将其归还给伙伴池，并合并相邻的空闲伙伴以减少碎片化。
伙伴系统的结构
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
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11 /* 默认最大阶11 11阶下每块内存有2^11个页 */
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
struct zone {
...
struct free_area free_area[MAX_ORDER];
/*
* 此域下page的迁移类型的位图，通过
* set_pageblock_migratetype(struct page *page, int migratetype)
* 函数设置
*/
unsigned long *pageblock_flags;
...
}
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
/* 不同迁移类型的内存页，将页按照迁移类型区分，有助于减少内存碎片化 */
#define MIGRATE_UNMOVABLE 0 /* 不可移动 */
#define MIGRATE_RECLAIMABLE 1 /* 可重生成（从文件或其他源） */
#define MIGRATE_MOVABLE 2 /* 可移动 */
#define MIGRATE_PCPTYPES 3
#define MIGRATE_RESERVE 3 /* 预留，其他类型的页被耗尽时兜底使用 */
#define MIGRATE_ISOLATE 4
#define MIGRATE_TYPES 5
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free; /* 空闲页块的数目 每块 = 2^order 个页 */
};
使用cat /proc/buddyinfo命令查看当前系统中的伙伴内存各阶状态（默认11阶）
1
2
3
4
$> cat /proc/buddyinfo
Node 0, zone DMA 1 0 0 1 2 1 1 0 1 1 3
Node 0, zone DMA32 3 5 3 5 4 3 3 3 3 2 743
Node 0, zone Normal 2 2 1 0 3 5 4 4 5 5 231
当某个特定迁移类型的内存页不够用时，会从其他内存结点/类型的备用内存页中分配，使用cat /proc/pagetypeinfo命令查看当前系统各个域内不同迁移类型的各阶内存状态，在内核初始化的paging_init函数中，会将所有页帧都设置为MIGRATE_MOVABLE
1
2
3
4
5
6
7
8
9
/*
* 各类型的备用类型列表顺序，备用结点的顺序已在`__build_all_zonelists()`函数中初始化过
*/
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 },
};
伙伴系统的API
内存分配函数
| alloc_pages(gfp_mask, order) | 分配$2^{order}$个页 返回起始page |
| alloc_page(mask) | = alloc_pages(mask, 0) |
| __get_free_page(gfp_mask, order) | = page_address(alloc_pages(gfp_mask, order)) 返回虚拟地址 |
| __get_free_page(gfp_mask) | = __get_free_page(gfp_mask, 0) |
| __get_dma_pages(gfp_mask, order) | = __get_free_pages((gfp_mask) | GFP_DMA, (order)) |
| get_zeroed_page(gfp_t gfp_mask) | = __get_free_pages(gfp_mask | __GFP_ZERO, 0) 分配1页填充0内存 返回page |
内存释放函数
| __free_pages(page, order) | 将从page实例开始的$2^{order}$页返回给内存管理子系统 |
| free_pages(addr, order) | = __free_pages(virt_to_page((void *)addr), order) |
gfp_mask掩码
gpf 为get_free_page的简写，代表获取空闲页的请求，gpf_mask用来标志一次请求中的特殊要求，例如需要dma内存区以高优先级获取一块内存且禁止睡眠等待。 带__前缀的定义通常会组合起来一起使用，例如在gfp.h中的以下组合：
| GFP_NOWAIT | (GFP_ATOMIC & ~__GFP_HIGH) | 普通请求 实际上就是0 |
| GFP_ATOMIC | (__GFP_HIGH) | 原子分配高优先级请求，不可中断 |
| GFP_NOIO | (__GFP_WAIT) | 不允许IO操作 |
| GFP_NOFS | (__GFP_WAIT | __GFP_IO) | 可以等待和IO操作不能有文件系统操作 |
| GFP_KERNEL | (__GFP_WAIT | __GFP_IO | __GFP_FS) | 内核常规分配 |
| GFP_USER | (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL) | 用户态常规则分配 |
| GFP_HIGHUSER | (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL | __GFP_HIGHMEM) | 用户态高端内存分配 |
api的底层实现
通过使用gfp_mask掩码和各个分配函数，内核提供了一种非常灵活的内存分配体系，所有分配接口函数都可以追溯到的基本函数__alloc_pages_nodemask，所有释放函数都可以追溯到__free_one_page函数。
内存分配
__alloc_pages_nodemask函数是内核分配内存的入口函数，其主要逻辑是根据掩码找到合适的zone并调用get_page_from_freelist尝试快速分配和__alloc_pages_slowpath函数尽更努力的态度(也更慢)去分配内存，其中涉及到内存回收逻辑。
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
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist, nodemask_t *nodemask)
{
enum zone_type high_zoneidx = gfp_zone(gfp_mask);
struct zone *preferred_zone;
struct page *page;
/* 从掩码中匹配迁移类型 */
int migratetype = allocflags_to_migratetype(gfp_mask);
gfp_mask &= gfp_allowed_mask;
lockdep_trace_alloc(gfp_mask);
/* 调试宏，用来检测是否存在带锁情况下的线程sleep */
might_sleep_if(gfp_mask & __GFP_WAIT);
if (should_fail_alloc_page(gfp_mask, order))
return NULL;
if (unlikely(!zonelist->_zonerefs->zone))
return NULL;
/* NUMA系统下保护当前内存节点的访问 */
get_mems_allowed();
/* 找到在可用节点下的第一个可用类型的zone 通过preferred_zone返回 */
first_zones_zonelist(zonelist, high_zoneidx,
nodemask ? : &cpuset_current_mems_allowed,
&preferred_zone);
if (!preferred_zone) {
put_mems_allowed();
return NULL;
}
/* 第一次分配内存，尝试快速找到空闲内存并分配 */
page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,
preferred_zone, migratetype);
/* 快速分配失败，尝试页面交换出块设备、页面回收、页面压缩、甚至是通kill掉其他进程来尝试内存分配 */
if (unlikely(!page))
page = __alloc_pages_slowpath(gfp_mask, order,
zonelist, high_zoneidx, nodemask,
preferred_zone, migratetype);
/* 对应上面的内存节点访问保护 解除此保护 */
put_mems_allowed();
/* 追踪内存分配记录 用来调试优化内核 */
trace_mm_page_alloc(page, order, gfp_mask, migratetype);
return page;
}
尝试第一次快速分配
get_page_from_freelist的核心逻辑是遍历所有zone和node，根据掩码判断zone的负载是否满足需求（通过zone_watermark_ok函数），在此期间标记那些已满无法使用的内存zone，针对可用的内存zone通过buffered_rmqueue函数分配内存
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
static struct page *
get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
struct zone *preferred_zone, int migratetype)
{
struct zoneref *z;
struct page *page = NULL;
int classzone_idx;
struct zone *zone;
nodemask_t *allowednodes = NULL;
int zlc_active = 0;
int did_zlc_setup = 0;
classzone_idx = zone_idx(preferred_zone);
zonelist_scan:
/* 遍历 zonelist,找到一个具有需求大小的空闲内存页的zone */
for_each_zone_zonelist_nodemask(zone, z, zonelist,
high_zoneidx, nodemask) {
/* 如果是NUMA系统，看下当前zone是否值得尝试分配（结点与cpu匹配、zone的内存负载情况） */
if (NUMA_BUILD && zlc_active &&
!zlc_zone_worth_trying(zonelist, z, allowednodes))
continue;
if ((alloc_flags & ALLOC_CPUSET) &&
!cpuset_zone_allowed_softwall(zone, gfp_mask))
goto try_next_zone;
BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
unsigned long mark;
int ret;
/* 检查zone的水印是否满足分配需求，并尝试在此zone分配 */
mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
if (zone_watermark_ok(zone, order, mark,
classzone_idx, alloc_flags))
goto try_this_zone;
/* 负载较高，回收zone内存 */
if (zone_reclaim_mode == 0)
goto this_zone_full;
ret = zone_reclaim(zone, gfp_mask, order);
switch (ret) {
case ZONE_RECLAIM_NOSCAN:
goto try_next_zone;
case ZONE_RECLAIM_FULL:
goto this_zone_full;
default:
if (!zone_watermark_ok(zone, order, mark,
classzone_idx, alloc_flags))
goto this_zone_full;
}
}
try_this_zone:
/* 从zone中分配order阶的migratetype类型内存页 */
page = buffered_rmqueue(preferred_zone, zone, order,
gfp_mask, migratetype);
if (page)
break;
this_zone_full:
/* 标记此zone已满，避免后续的分配与回收尝试 */
if (NUMA_BUILD)
zlc_mark_zone_full(zonelist, z);
try_next_zone:
if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {
allowednodes = zlc_setup(zonelist, alloc_flags);
zlc_active = 1;
did_zlc_setup = 1;
}
}
if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
/* numa系统 换个可用的节点 继续尝试 */
zlc_active = 0;
goto zonelist_scan;
}
return page;
}
zone_watermark_ok将工作交给了__zone_watermark_ok，后者判断zone的空闲页数量是否在水印以下
1
2
3
4
5
6
enum zone_watermarks {
WMARK_MIN,
WMARK_LOW,
WMARK_HIGH,
NR_WMARK
};
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
/* 使用zone的哪个水印 */
#define ALLOC_WMARK_MIN WMARK_MIN
#define ALLOC_WMARK_LOW WMARK_LOW
#define ALLOC_WMARK_HIGH WMARK_HIGH
#define ALLOC_NO_WATERMARKS 0x04 /* 不检查水印 */
#define ALLOC_HARDER 0x10 /* 放宽限制 */
#define ALLOC_HIGH 0x20 /* 更进一步放宽限制 如果掩码中配置了__GFP_HIGH */
#define ALLOC_CPUSET 0x40
static bool __zone_watermark_ok(struct zone *z, int order, unsigned long mark,
int classzone_idx, int alloc_flags, long free_pages)
{
long min = mark;
int o;
/* 根据水印和分配的内存的大小，判断分配后空闲内存页是否满足要求 */
free_pages -= (1 << order) + 1;
if (alloc_flags & ALLOC_HIGH)
min -= min / 2;
if (alloc_flags & ALLOC_HARDER)
min -= min / 4;
if (free_pages <= min + z->lowmem_reserve[classzone_idx])
return false;
for (o = 0; o < order; o++) {
free_pages -= z->free_area[o].nr_free << o;
min >>= 1;
if (free_pages <= min)
return false;
}
return true;
}
buffered_rmqueue根据分配阶判断从zone的cpu缓存中直接分配（如果分配阶是0），还是从zone中的free_area分配，后者将工作委托给__rmqueue函数，如果拿到了内存页，再通过prep_new_page函数检查分配的页是否正常（flag、引用计数等），然后为其初始化，如果掩码中有复合页位，还会初始化复合页属性。
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
static inline
struct page *buffered_rmqueue(struct zone *preferred_zone,
struct zone *zone, int order, gfp_t gfp_flags,
int migratetype)
{
unsigned long flags;
struct page *page;
int cold = !!(gfp_flags & __GFP_COLD);
again:
if (likely(order == 0)) {
/* 如果只分配一页，从cpu缓存中直接分配 */
struct per_cpu_pages *pcp;
struct list_head *list;
/* 中止中断 */
local_irq_save(flags);
pcp = &this_cpu_ptr(zone->pageset)->pcp;
list = &pcp->lists[migratetype];
if (list_empty(list)) {
/* cpu缓存页用完 从zone->free_area中重建一批 */
pcp->count += rmqueue_bulk(zone, 0,
pcp->batch, list,
migratetype, cold);
if (unlikely(list_empty(list)))
goto failed;
}
/* 头是热页 尾是冷页 按需分配 */
if (cold)
page = list_entry(list->prev, struct page, lru);
else
page = list_entry(list->next, struct page, lru);
list_del(&page->lru);
pcp->count--;
} else {
if (unlikely(gfp_flags & __GFP_NOFAIL)) {
WARN_ON_ONCE(order > 1);
}
spin_lock_irqsave(&zone->lock, flags);
/* 直接在free_area中分配内存页 */
page = __rmqueue(zone, order, migratetype);
spin_unlock(&zone->lock);
if (!page)
goto failed;
__mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));
}
__count_zone_vm_events(PGALLOC, zone, 1 << order);
zone_statistics(preferred_zone, zone, gfp_flags);
/* 恢复中断机制 */
local_irq_restore(flags);
VM_BUG_ON(bad_range(zone, page));
/* 准备新页 */
if (prep_new_page(page, order, gfp_flags))
goto again;
return page;
failed:
local_irq_restore(flags);
return NULL;
}
__rmqueue根据从伙伴系统管理的内存页中移除并返回需求的内存页，如果不能拿到需求的迁移类型的内存页，通过文首中的fallbacks数组尝试备用迁移类型中的内存空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
{
struct page *page;
retry_reserve:
/* 从需求阶向上遍历内存阶，尝试移除内存 */
page = __rmqueue_smallest(zone, order, migratetype);
if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
/* 尝试备用迁移类型 */
page = __rmqueue_fallback(zone, order, migratetype);
if (!page) {
/* 仍然没拿到 使用紧急预留类型的内存空间 */
migratetype = MIGRATE_RESERVE;
goto retry_reserve;
}
}
/* 跟踪内存直接从伙伴系统分配的事件 */
trace_mm_page_alloc_zone_locked(page, order, migratetype);
return 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
/* 遍历zone->free_area中指定迁移类型的内存阶，返回符合需求的最小内存页 */
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;
/* 从指定阶开始向上遍历，（内存空间由小至大）*/
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);
area->nr_free--;
/* 伙伴系统分配的的核心思想，如果实际分配的内存阶大于需求的内存阶，将大阶拆分成多个小阶 */
expand(zone, page, order, current_order, area, migratetype);
return page;
}
return NULL;
}
假设需求2个连续的内存页，顺利找到了可用的内存，但处于伙伴系统的3阶中，此块内存是$2^3=8$个页，所以需要将这个内存页拆分成符合需求2个页以避免内存浪费，伙伴系统将这个3阶内存拆分成2个2阶内存页，将1个2阶内存页放回至free_area[2]中，将1个1阶内存页放回至free_area[0]中，然后返回剩余的$2^3-2^2-2^1=2$个页。 上述逻辑在expand函数中实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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);
}
}
回到__rmqueue函数，如果在指定的迁移类型中没有找到足够需求大小的内存（__rmqueue_smallest函数返回了null），在去备用zone分配内存之前，先尝试本zone的其他迁移类型的内存。
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
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;
/* 注意这里是从最大阶开始遍历的，上来就拿大块内存，避免在备用的迁移类型中的free_list中分配给源迁移类型的内存以造成内存碎片 */
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 不在此函数处理，返回为空 交由上游__rmqueue处理，最终委托给__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;
pages = move_freepages_block(zone, page,
start_migratetype);
if (pages >= (1 << (pageblock_order-1)) ||
page_group_by_mobility_disabled)
set_pageblock_migratetype(page,
start_migratetype);
migratetype = start_migratetype;
}
/* 从伙伴系统中移除此内存 */
list_del(&page->lru);
rmv_page_order(page);
/* 将>=pageblock_order的内存迁移至源迁移类型free_list中去 */
if (current_order >= pageblock_order)
change_pageblock_range(page, current_order,
start_migratetype);
/* 拆分大阶转小阶 */
expand(zone, page, order, current_order, area, migratetype);
trace_mm_page_alloc_extfrag(page, order, current_order,
start_migratetype, migratetype);
return page;
}
}
return NULL;
}
再次回到buffered_rmqueue函数，不管是在cpu缓存还是在zone的指定/备用迁移类型中拿到的内存，在真正返回给进程用之前，还需要初始化一些page的数据，如果内存分配请求掩码中还指定了复合页标志__GFP_COMP，还需要做些额外的处理。
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
static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
{
int i;
for (i = 0; i < (1 << order); i++) {
struct page *p = page + i;
/* 检查页码的引用计数/flag等是否正常 */
if (unlikely(check_new_page(p)))
return 1;
}
/* 初始化page数据 */
set_page_private(page, 0);
set_page_refcounted(page);
arch_alloc_page(page, order);
kernel_map_pages(page, 1 << order, 1);
/* 设置了__GFP_ZERO标志，则将内存清零 */
if (gfp_flags & __GFP_ZERO)
prep_zero_page(page, order, gfp_flags);
/* 处理复合页 */
if (order && (gfp_flags & __GFP_COMP))
prep_compound_page(page, order);
return 0;
}
复合页是一个连续的物理内存块，由多个较小的连续页组成，相比普通的页，复合页有以下几个优点
- 高效的内存分配：复合页允许内核分配大的连续内存块，这对于某些内核数据结构（如内核堆栈）和需要大缓冲区的设备驱动程序至关重要。
- 减少碎片化：通过将内存分配到较大的块中，复合页减少了内存碎片化，当分配和释放小的、不连续的内存块时，就会出现内存碎片化现象，从而导致内存浪费。
- 提高性能：复合页可以通过减少映射内存所需的页表条目（PTE）的数量来提高性能，这反过来又减少了页面错误和TLB缺失的数量。
- 简化的内存管理：复合页面通过允许内核将较大的内存块作为一个单元而不是单个页面来管理，从而简化了内存管理。
组成复合页的所有页的page实例的private字段，包括首页在内，都指向首页。指向复合页析构函数free_compound_pages的指针保存在lru.next，而分配阶保存在lru.prev。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void prep_compound_page(struct page *page, unsigned long order)
{
int i;
int nr_pages = 1 << order;
/* 设置page的lru->next */
set_compound_page_dtor(page, free_compound_page);
/* 设置page的lru->prev */
set_compound_order(page, order);
/* 设置flags与first_page */
__SetPageHead(page);
for (i = 1; i < nr_pages; i++) {
struct page *p = page + i;
__SetPageTail(p);
p->first_page = page;
}
}
至此，尝试在空闲内存快速分配的逻辑就完成了，那么如果在遍历完所有的node、zone、迁移类型后，仍然没有找到合适的内存块，但此次内存分配又比较重要不能失败（比如内核管理）那么就只能。
尝试一切办法尽最大可能分配
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
static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist, enum zone_type high_zoneidx,
nodemask_t *nodemask, struct zone *preferred_zone,
int migratetype)
{
const gfp_t wait = gfp_mask & __GFP_WAIT;
struct page *page = NULL;
int alloc_flags;
unsigned long pages_reclaimed = 0;
unsigned long did_some_progress;
bool sync_migration = false;
/* 避免回收最大阶的内存，不可能成功 */
if (order >= MAX_ORDER) {
WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
return NULL;
}
/*
* GFP_THISNODE ( __GFP_THISNODE & __GFP_NORETRY &__GFP_NOWARN)
* 如果掩码中有以上几个选项，也不用回收内存再分配
*/
if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
goto nopage;
restart:
/* 唤醒所有kswapd线程去扫描和回收内存页 */
if (!(gfp_mask & __GFP_NO_KSWAPD))
wake_all_kswapd(order, zonelist, high_zoneidx,
zone_idx(preferred_zone));
/* 根据进程类型（是否实时进程）与掩码 获取分配标志（水印级别、分配力度） */
alloc_flags = gfp_to_alloc_flags(gfp_mask);
/* 没有指定cpu与结点的情况下 找到最合敌的zone */
if (!(alloc_flags & ALLOC_CPUSET) && !nodemask)
first_zones_zonelist(zonelist, high_zoneidx, NULL,
&preferred_zone);
rebalance:
/* 尝试分配内存 */
page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
preferred_zone, migratetype);
if (page)
goto got_pg;
/* 在取消水印检查的情况下尝试分配内存 */
if (alloc_flags & ALLOC_NO_WATERMARKS) {
page = __alloc_pages_high_priority(gfp_mask, order,
zonelist, high_zoneidx, nodemask,
preferred_zone, migratetype);
if (page)
goto got_pg;
}
/* 如果掩码不等待，直接返回失败 */
if (!wait)
goto nopage;
/* 如果已经回收过了，返回失败 */
if (current->flags & PF_MEMALLOC)
goto nopage;
/* 避免死循环 */
if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
goto nopage;
/* 尝试压缩内存 */
page = __alloc_pages_direct_compact(gfp_mask, order,
zonelist, high_zoneidx,
nodemask,
alloc_flags, preferred_zone,
migratetype, &did_some_progress,
sync_migration);
if (page)
goto got_pg;
sync_migration = !(gfp_mask & __GFP_NO_KSWAPD);
/* 尝试回收内存 */
page = __alloc_pages_direct_reclaim(gfp_mask, order,
zonelist, high_zoneidx,
nodemask,
alloc_flags, preferred_zone,
migratetype, &did_some_progress);
if (page)
goto got_pg;
/* 回收没起到效果，进行oom_killer找出合适的进程杀死以释放内存 */
if (!did_some_progress) {
if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
if (oom_killer_disabled)
goto nopage;
page = __alloc_pages_may_oom(gfp_mask, order,
zonelist, high_zoneidx,
nodemask, preferred_zone,
migratetype);
if (page)
goto got_pg;
if (!(gfp_mask & __GFP_NOFAIL)) {
/* 如果此次分配的内存阶比较高，杀死其他进程并没能带来帮助，因此直接失败 */
if (order > PAGE_ALLOC_COSTLY_ORDER)
goto nopage;
/* 如果是dma这种稀有内存 直接失败*/
if (high_zoneidx < ZONE_NORMAL)
goto nopage;
}
goto restart;
}
}
/* 回收起到了效果 尝试重新分配 */
pages_reclaimed += did_some_progress;
if (should_alloc_retry(gfp_mask, order, pages_reclaimed)) {
/* 如果zone有写入 先等待一下再重新分配 */
wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
goto rebalance;
} else {
/* 最后尝试在回收之后再次压缩并尝试分配*/
page = __alloc_pages_direct_compact(gfp_mask, order,
zonelist, high_zoneidx,
nodemask,
alloc_flags, preferred_zone,
migratetype, &did_some_progress,
sync_migration);
if (page)
goto got_pg;
}
nopage:
if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
unsigned int filter = SHOW_MEM_FILTER_NODES;
/* 记录失败信息 */
if (!(gfp_mask & __GFP_NOMEMALLOC))
if (test_thread_flag(TIF_MEMDIE) ||
(current->flags & (PF_MEMALLOC | PF_EXITING)))
filter &= ~SHOW_MEM_FILTER_NODES;
if (in_interrupt() || !wait)
filter &= ~SHOW_MEM_FILTER_NODES;
pr_warning("%s: page allocation failure. order:%d, mode:0x%x\n",
current->comm, order, gfp_mask);
dump_stack();
if (!should_suppress_show_mem())
show_mem(filter);
}
return page;
got_pg:
/* 检查内存 */
if (kmemcheck_enabled)
kmemcheck_pagealloc_alloc(page, order, gfp_mask);
return page;
}
伙伴系统分配内存的源码至此完结🎉，接下来进入内存的释放。
内存释放
free_pages函数比较简单，主要逻辑是检测页是否可被归还，然后根据页的大小归还给cpu缓存或伙伴系统。
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
void __free_pages(struct page *page, unsigned int order)
{
/* 将page引用计数-1 并检测是否为0 */
if (put_page_testzero(page)) {
/* 如果仅有一页，优先归还到cpu缓存 */
if (order == 0)
free_hot_cold_page(page, 0);
else
__free_pages_ok(page, order);
}
}
void free_hot_cold_page(struct page *page, int cold)
{
struct zone *zone = page_zone(page);
struct per_cpu_pages *pcp;
unsigned long flags;
int migratetype;
int wasMlocked = __TestClearPageMlocked(page);
if (!free_pages_prepare(page, 0))
return;
migratetype = get_pageblock_migratetype(page);
set_page_private(page, migratetype);
local_irq_save(flags);
if (unlikely(wasMlocked))
free_page_mlock(page);
__count_vm_event(PGFREE);
/* 只将迁移类型为 MIGRATE_UNMOVABLE/MIGRATE_RECLAIMABLE/MIGRATE_MOVABLE的内存页归还给cpu缓存 */
if (migratetype >= MIGRATE_PCPTYPES) {
if (unlikely(migratetype == MIGRATE_ISOLATE)) {
free_one_page(zone, page, 0, migratetype);
goto out;
}
migratetype = MIGRATE_MOVABLE;
}
pcp = &this_cpu_ptr(zone->pageset)->pcp;
/* 冷页放到链尾，热页放到页头 */
if (cold)
list_add_tail(&page->lru, &pcp->lists[migratetype]);
else
list_add(&page->lru, &pcp->lists[migratetype]);
pcp->count++;
if (pcp->count >= pcp->high) {
/* 如果缓存队列超出水印了，将batch批量的页归还给伙伴系统 */
free_pcppages_bulk(zone, pcp->batch, pcp);
pcp->count -= pcp->batch;
}
out:
local_irq_restore(flags);
}
__free_pages_ok函数做出了一系列校验，最终将释放内存的任务委托给了free_one_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
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;
/* 如果是复合页，destroy_compound_page将复合页的属性去除 并返回坏页的数量 */
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));
/* 从order开始遍历到最大阶 尝试合并buddy页 */
while (order < MAX_ORDER-1) {
/* 找到能与当前页合并buddy的页索引 page_idx ^ (1 << order) */
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--;
rmv_page_order(buddy);
/* 计算合并后伙伴块的首页索引 */
combined_idx = buddy_idx & page_idx;
page = page + (combined_idx - page_idx);
page_idx = combined_idx;
order++;
}
/* 设置合并后新伙伴块的首页标志 */
set_page_order(page, order);
/* 对于非最大阶的内存，检查其下一阶的伙伴是否空闲，如果是则将其放到链尾 以提高给后面释放的内存合并可能性 */
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;
}
}
/* 将新伙伴块 添加到free_area中 这里是放到链头后面 相比链尾 能被更快使用*/ */
list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
out:
zone->free_area[order].nr_free++;
}
__find_buddy_index函数的实现很简单却很巧妙：return page_idx ^ (1 << order)，通过异或运算将伙伴系统特性与连续内存页的性质快速找出page_idx在order+1阶的伙伴的页帧号。
page_idx是将要释放的伙伴系统块的首页页帧号，而页帧号在整个伙伴系统中是连续的。
图片为了简单只示意结构，真正的free_lsit中包含大量的页，不只上图所示中的4个页。
伙伴系统的各阶内存中的页帧号在二进制下的特性，其中同色代表互为伙伴块。
可得出，在order-1阶想匹配page_idx的伙伴页的页帧号以合并一个order阶的伙伴块，（为色块pfn匹配括号中的另一色块的pfn）只需将page_idx的第order位上的值取反即可。 另一个有意思是的寻找的伙伴块有可能在左也有可能在右，那么如何找到合并后的首页页帧号呢？根据上面的图不难发现，伙伴块最左侧的页帧第order位总是0，可轻松通过位与运算获取，即代码中的combined_idx = buddy_idx & page_idx。
本文由作者按照 CC BY 4.0 进行授权