分类：
2011-06-28 10:31:17
原文地址：Vi Linux内存 之 伙伴系统（二） 作者：palals
参数：
1) zone：free_area空闲页块链表所在的区。
2) order：在哪一级的链表上申请页块。
static struct page *__rmqueue(struct zone *zone, unsigned int order)
{
struct free_area * area;
unsigned int current_order;
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))
continue;
/* 找到空闲页块，获得页块的第一个页面 */
page = list_entry(area->free_list.next, struct page, lru);
/* 从原链表中删除 */
list_del(&page->lru);
/* 清除此页块的PG_buddy标志位，设置private为0，为后面分解页块做准备 */
rmv_page_order(page);
/* 链表页块数目减一 */
area->nr_free--;
/* 更新zone状态 */
__mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));
/* 分解页块 */
expand(zone, page, order, current_order, area);
return page;
}
return NULL;
}
将一个大页块分解成若干小页块。
参数：
1) zone：页块所在的区。
2) page：待分解大页块的第一个页面。
3) low：申请页块的order。
4) high：待分解页块的order。
5) area：包含待分解页块所在链表的free_area。
static inline void expand(struct zone *zone, struct page *page,
int low, int high, struct free_area *area)
{
/* 初始化size为大页块的大小 */
unsigned long size = 1 << high;
/* 逐步将大页块分解成小页块，举例说明：假设申请256个页面的页块，待分解的是
1024的页块，第一次循环先从1024页块分出一个512的页块，第二次循环再分出一个
256的页块 */
while (high > low) {
/* 指向低一级的free_area */
area--;
/* 当前链表的order */
high--;
/* 当前链表的页块大小 */
size >>= 1;
/* 校验页块是否有效，检查是否有空洞，页块中的页面是否都在同一个zone中 */
VM_BUG_ON(bad_range(zone, &page[size]));
/* 将高地址区的页块加入链表，上例中，第一次循环是512页块，第二次循环是剩
下的256页块 */
list_add(&page[size].lru, &area->free_list);
/* 当前链表的空闲页块计数加一 */
area->nr_free++;
/* 设置页块的PG_buddy标志位（通过此标志位表示页块已经加入到伙伴系统
中），并设置private为当前order */
set_page_order(&page[size], high);
}
}
接下来分析一下释放页块函数__free_one_page。
参数：
1) page：待释放的页块。
2) zone：页块所在的区
3) order：页块所在链表的order。
static inline void __free_one_page(struct page *page,
struct zone *zone, unsigned int order)
{
unsigned long page_idx;
int order_size = 1 << order;
/* 大页面相关，如果内核采用了大页面机制，比如2MB的页面大小，那么就需要由512个4KB的小页
面组合成一个compound大页面，分配时需设置小页面的PG_compound标志位，释放时需要清除
这个标志位。*/
if (unlikely(PageCompound(page)))destroy_compound_page(page, order);
/* 将与伙伴算法无关的高位屏蔽 */
page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
/* 页块索引是否是2order的整数倍 */
VM_BUG_ON(page_idx & (order_size - 1));
/* 校验页块是否有效，检查是否有空洞，页块中的页面是否都在同一个zone中 */
VM_BUG_ON(bad_range(zone, page));
/* 更新zone的空闲页状态 */
__mod_zone_page_state(zone, NR_FREE_PAGES, order_size);
/* 按照伙伴算法合并伙伴 */
while (order < MAX_ORDER-1) {
unsigned long combined_idx;
struct free_area *area;
struct page *buddy;
/* 查找待释放页块的伙伴 */
buddy = __page_find_buddy(page, page_idx, order);
/* 如果伙伴校验失败，说明没有伙伴，退出循环 */
if (!page_is_buddy(page, buddy, order))
break; /* Move the buddy up one level. */
/* 将伙伴从原链表上删除 */
list_del(&buddy->lru);
/* 将这个order级别的空闲页块个数减一 */
area = zone->free_area + order;
area->nr_free--;
/* 为下面的合并做准备，清除伙伴的PG_buddy标志位，并设置伙伴的private成员为
0 */
rmv_page_order(buddy);
/* 利用伙伴算法公式计算合并后父节点的页块索引 */
combined_idx = __find_combined_index(page_idx, order);
/* 获得合并后页块的第一个页面 */
page = page + (combined_idx - page_idx);
/* 更新当前页块索引为父节点的索引 */
page_idx = combined_idx;
/* 继续在上一级order链表中应用伙伴合并算法 */
order++;
}
/* 设置页块的PG_buddy标志位（通过此标志位表示页块已经加入到伙伴系统中），并
设private为当前order */
set_page_order(page, order);
/* 将合并后页块的第一个页面加入到order级链表中 */
list_add(&page->lru, &zone->free_area[order].free_list);
/* 更新链表的空闲页块计数 */
zone->free_area[order].nr_free++;
}
伙伴查找函数__page_find_buddy：
参数：
1) page：给定的页块。
2) page_idx：给定页块的索引。
3) order：页块所在链表的order。
static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
/* 利用伙伴算法公式计算伙伴 */
unsigned long buddy_idx = page_idx ^ (1 << order);
/*比如0和1为伙伴，0为小伙伴，1为大伙伴。buddy_idx大于page_idx时，给出的是小伙
伴，计算出的是大伙伴，buddy_idx小于page_idx时，给出的是大伙伴，计算出的是小
伙伴。*/
return page + (buddy_idx - page_idx);
}
找到伙伴后，还要做一下校验。
参数：
1) page：给定的页块。
2) buddy：伙伴页块的索引。
3) order：页块所在链表的order。
static inline int page_is_buddy(struct page *page, struct page *buddy,
int order)
{
#ifdef CONFIG_HOLES_IN_ZONE
/* 伙伴是否是空洞 */
if (!pfn_valid(page_to_pfn(buddy)))
return 0;
#endif
/* 伙伴是否在同一个zone */
if (page_zone_id(page) != page_zone_id(buddy))
return 0;
/* 通过检查PG_buddy 标志位判断buddy是否在伙伴系统中，并且buddy是否在order级的
链表中，page的private成员存放页块所在链表的order。*/
if (PageBuddy(buddy) && page_order(buddy) == order) {
BUG_ON(page_count(buddy) != 0);
return 1;
}
return 0;
}
