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的概念。对于每种大小的内存块链表，内核根据待申请内存的“可移动性”将其分为以下几种类型：
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中被定义如下：
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文件可以查看各个类型链表的详细信息：
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，现将主要函数列出来(点击下面展开代码)：
其中涉及的函数比较多，现将它们的调用关系列出来：
分配内存：(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。
下面把这几个函数单独拿出来，并以注释的形式来说明：
/*
* 这个函数负责寻找页框号为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;
}