Linux内存管理之伙伴算法
上文我们讲到快速分配和慢速分配，接下来会详细讲解这两种分配情况，我们先来看下快速分配：
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
const struct alloc_context *ac)
{
for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx, ac->nodemask)
{
if (!zone_watermark_fast(zone, order, mark, ac_classzone_idx(ac), alloc_flags))
{
ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
switch (ret) {
case NODE_RECLAIM_NOSCAN:
continue;
case NODE_RECLAIM_FULL:
continue;
default:
if (zone_watermark_ok(zone, order, mark, ac_classzone_idx(ac), alloc_flags))
goto try_this_zone;
continue;
}
}
try_this_zone: //本zone正常水位
page = rmqueue(ac->preferred_zoneref->zone, zone, order, gfp_mask, alloc_flags, ac->migratetype);
}
return NULL;
}首先遍历当前zone，按照HIGHMEM->NORMAL的方向进行遍历，判断当前zone是否能够进行内存分配的条件是首先判断free memory是否满足low water mark水位值，如果不满足则进行一次快速的内存回收操作，然后再次检测是否满足low water mark，如果还是不能满足，相同步骤遍历下一个zone，满足的话进入正常的分配情况，即rmqueue函数，这也是伙伴系统的核心。
Buddy 分配算法
在看函数前，我们先看下算法，因为我一直认为有了“道”的理解才好进一步理解“术”。
假设这是一段连续的页框，阴影部分表示已经被使用的页框，现在需要申请一个连续的5个页框。这个时候，在这段内存上不能找到连续的5个空闲的页框，就会去另一段内存上去寻找5个连续的页框，这样子，久而久之就形成了页框的浪费。为了避免出现这种情况，Linux内核中引入了伙伴系统算法(Buddy system)。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍，如图：
假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。
从上面可以知道Buddy算法一直在对页框做拆开合并拆开合并的动作。Buddy算法牛逼就牛逼在运用了世界上任何正整数都可以由2^n的和组成。这也是Buddy算法管理空闲页表的本质。空闲内存的信息我们可以通过以下命令获取：
也可以通过echo m > /proc/sysrq-trigger来观察buddy状态，与/proc/buddyinfo的信息是一致的：
Buddy 分配函数
static inline
struct page *rmqueue(struct zone *preferred_zone,
struct zone *zone, unsigned int order,
gfp_t gfp_flags, unsigned int alloc_flags,
int migratetype)
{
if (likely(order == 0)) { //如果order=0则从pcp中分配
page = rmqueue_pcplist(preferred_zone, zone, order, gfp_flags, migratetype);
}
do {
page = NULL;
if (alloc_flags & ALLOC_HARDER) {//如果分配标志中设置了ALLOC_HARDER，则从free_list[MIGRATE_HIGHATOMIC]的链表中进行页面分配
page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
}
if (!page) //前两个条件都不满足，则在正常的free_list[MIGRATE_*]中进行分配
page = __rmqueue(zone, order, migratetype);
} while (page && check_new_pages(page, order));
......
}可以看出伙伴系统在页面进行分配的时候，有以下四个步骤：
- 如果申请的是order = 0的页面，直接选择从pcp中进行分配，并直接退出；
- order > 0时，如果分配标志中设置了ALLOC_HARDER，则从free_list[MIGRATE_HIGHATOMIC]的链表中进行页面分配，分配成功则返回；
- 前两个条件都不满足，则在正常的free_list[MIGRATE_*]中进行分配，分配成功则直接则返回；
- 如果3中分配失败了，则查找后备类型fallbacks[MIGRATE_TYPES][4]，并将查找到的页面移动到所需的MIGRATE类型中，移动成功后，重新尝试分配；
「__rmqueue_smallest:」
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]); //得到指定order的area
page = list_first_entry_or_null(&area->free_list[migratetype],
struct page, lru);
if (!page) //如果area指定类型的伙伴系统链表为空
continue; //查找下一个order
list_del(&page->lru); //从伙伴系统中删除
rmv_page_order(page); //移除page中order的变量
area->nr_free--; //空闲块数减一
expand(zone, page, order, current_order, area, migratetype);//查找到页表之后，从对应的链表中拆分合并
set_pcppage_migratetype(page, migratetype);
return page;
}
return NULL;
}即：
- 从申请的order大小开始查找目标MIGRATE类型链表中页表，如果没有找到，则从更大的order中查找，直到MAX_ORDER；
- 查找到页表之后，从对应的链表中删除掉，并调用expand函数进行处理；
「__rmqueue：」
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
{
page = __rmqueue_smallest(zone, order, migratetype);//从指定order开始从小到达遍历,优先从指定的迁移类型链表中分配页面
if (unlikely(!page)) {
if (migratetype == MIGRATE_MOVABLE)
page = __rmqueue_cma_fallback(zone, order);
if (!page && __rmqueue_fallback(zone, order, migratetype))//从备用fallbacks中找到一个迁移类型页面块，将其移动到目标类型中，并重新进行分配。
goto retry;
}
return page;
}可以看出在正常的free_list[MIGRATE_*]分配失败后，会查找后备类型fallbacks[MIGRATE_TYPES][4]，并将查找到的页面移动到所需的MIGRATE类型中，移动成功后，重新尝试分配；
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
};__rmqueue_fallback完成的主要工作就是从后备fallbacks中找到一个迁移类型页面块，将其移动到目标类型中，并重新进行分配。
以上就是伙伴系统的分配过程。