Linux内存管理之伙伴系统（内存释放）
来源：岁月联盟
时间：2012-01-10
一、上层操作
www.2cto.com
/*用虚拟地址进行释放*/
void free_pages(unsigned long addr, unsigned int order)
{
if (addr != 0) {
VM_BUG_ON(!virt_addr_valid((void *)addr));
__free_pages(virt_to_page((void *)addr), order);/*具体的释放函数*/
}
}
www.2cto.com
/*释放页面*/
void __free_pages(struct page *page, unsigned int order)
{
if (put_page_testzero(page)) {/*count值减一为0时释放*/
/*调试*/
trace_mm_page_free_direct(page, order);
if (order == 0)
free_hot_page(page);/*释放单个页面*/
else
__free_pages_ok(page, order);
}
}
二、释放单个页面
释放单个页面free_hot_page()调用free_hot_cold_page()函数
www.2cto.com
static 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);
/*调试代码*/
kmemcheck_free_shadow(page, 0);
if (PageAnon(page))
page->mapping = NULL;
if (free_pages_check(page))
return;
if (!PageHighMem(page)) {
debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
debug_check_no_obj_freed(page_address(page), PAGE_SIZE);
}
/*x86下为空*/
arch_free_page(page, 0);
/*调试用*/
kernel_map_pages(page, 1, 0);
/*获得zone对应cpu的pcp*/
pcp = &zone_pcp(zone, get_cpu())->pcp;
/*获得页面的migratetype*/
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);
/*
* We only track unmovable, reclaimable and movable on pcp lists.
* Free ISOLATE pages back to the allocator because they are being
* offlined but treat RESERVE as movable pages so we can get those
* areas back if necessary. Otherwise, we may have to free
* excessively into the page allocator
*/
if (migratetype >= MIGRATE_PCPTYPES) {
if (unlikely(migratetype == MIGRATE_ISOLATE)) {
/*释放到伙伴系统*/
free_one_page(zone, page, 0, migratetype);
goto out;
}
migratetype = MIGRATE_MOVABLE;
}
if (cold)/*加入到pcp链表尾部*/
list_add_tail(&page->lru, &pcp->lists[migratetype]);
else/*加入到pcp链表头部*/
list_add(&page->lru, &pcp->lists[migratetype]);
pcp->count++;/*pcp计数加一*/
if (pcp->count >= pcp->high) {/*当pcp中页面数量超过他的最高值时，
释放pcp->batch个页面到伙伴系统中*/
free_pcppages_bulk(zone, pcp->batch, pcp);
pcp->count -= pcp->batch;/*页面数减去释放的页面数量*/
}
out:
local_irq_restore(flags);/*回复中断*/
put_cpu();
}
从pcp中释放页面到伙伴系统中
free_pcppages_bulk()
www.2cto.com
are in same zone, and of same order.
* count is the number of pages to free.
*
* If the zone was previously in an "all pages pinned" state then look to
* see if this freeing clears that state.
*
* And clear the zone's pages_scanned counter, to hold off the "all pages are
* pinned" detection logic.
*/
/*从PCP中释放count个页面到伙伴系统中*/
static void free_pcppages_bulk(struct zone *zone, int count,
struct per_cpu_pages *pcp)
{
int migratetype = 0;
int batch_free = 0;
/*
* 虽然管理区可以按照CPU节点分类，但是也可以跨CPU节点进行内存分配，
* 因此这里需要用自旋锁保护管理区
* 使用每CPU缓存的目的，也是为了减少使用这把锁。
*/
spin_lock(&zone->lock);
/* all_unreclaimable代表了内存紧张程度，释放内存后，将此标志清除*/
zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);
zone->pages_scanned = 0;/* pages_scanned代表最后一次内存紧张以来，页面回收过程已经扫描的页数。
目前正在释放内存，将此清0，待回收过程随后回收时重新计数*/
/*增加管理区空闲页数*/
__mod_zone_page_state(zone, NR_FREE_PAGES, count);
while (count) {
struct page *page;
struct list_head *list;
/*
* Remove pages from lists in a round-robin fashion. A
* batch_free count is maintained that is incremented when an
* empty list is encountered. This is so more pages are freed
* off fuller lists instead of spinning excessively around empty
* lists
*/
do {/*从pcp的三类链表中找出不空的一个，释放*/
batch_free++;/*参看英文注释*/
if (++migratetype == MIGRATE_PCPTYPES)
migratetype = 0;
list = &pcp->lists[migratetype];
} while (list_empty(list));
do {
page = list_entry(list->prev, struct page, lru);
/* must delete as __free_one_page list manipulates */
list_del(&page->lru);
/*释放单个页面到伙伴系统，注意这里的分类回收*/
__free_one_page(page, zone, 0, migratetype);
trace_mm_page_pcpu_drain(page, 0, migratetype);
} while (--count && --batch_free && !list_empty(list));
}
spin_unlock(&zone->lock);
}
三、释放多个页面
释放多个页面__free_pages_ok()函数
www.2cto.com
int i;
int bad = 0;
int wasMlocked = __TestClearPageMlocked(page);
/*调试用，和相关宏有关*/
kmemcheck_free_shadow(page, order);
for (i = 0 ; i < (1 << order) ; ++i)/*页面相关检查*/
bad += free_pages_check(page + i);
if (bad)
return;
if (!PageHighMem(page)) {
debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
debug_check_no_obj_freed(page_address(page),
PAGE_SIZE << order);
}
/*X86体系下为空*/
arch_free_page(page, order);
/*调试，相关宏定义*/
kernel_map_pages(page, 1 << order, 0);
local_irq_save(flags);/*flags的暂存，关中断*/
if (unlikely(wasMlocked))
free_page_mlock(page);
__count_vm_events(PGFREE, 1 << order);
/*传入参数，进行具体的释放工作，将1<<order的页面释放
到伙伴系统中*/
free_one_page(page_zone(page), page, order,
get_pageblock_migratetype(page));/*获得内存块的类型*/
local_irq_restore(flags);/*恢复中断*/
www.2cto.com
static void free_one_page(struct zone *zone, struct page *page, int order,
int migratetype)
{
spin_lock(&zone->lock);/*获得管理区的自旋锁*/
zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);/* 只要是释放了页面，都需要将此两个标志清0，表明内存不再紧张的事实*/
zone->pages_scanned = 0;
/*管理区空闲页面计数*/
__mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
/*释放到指定的伙伴系统类型链表*/
__free_one_page(page, zone, order, migratetype);
spin_unlock(&zone->lock);/*释放锁*/
}
www.2cto.com
etype)
{
unsigned long page_idx;
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));
/* 校验页块是否有效，检查是否有空洞，页块中的页面是否都在同一个zone中 */
VM_BUG_ON(bad_range(zone, page));
while (order < MAX_ORDER-1) {
unsigned long combined_idx;
struct page *buddy;
/*找出page页面的伙伴
查找待释放页块的伙伴,其中伙伴系统中每个块
都有一个对应同样大小的"伙伴块"(由2的指数原理知)*/
buddy = __page_find_buddy(page, page_idx, order);
if (!page_is_buddy(page, buddy, order))/*检查页面是否为伙伴*/
break;
/* Our buddy is free, merge with it and move up one order. */
list_del(&buddy->lru);
zone->free_area[order].nr_free--;
/* 为下面的合并做准备，清除伙伴的PG_buddy标志位，并设置伙伴的private成员为
0 */
rmv_page_order(buddy);
/* 利用伙伴算法公式计算合并后父节点的页块索引*/
/*实际上是这样的，这个要配合上面的找buddy
*算法一起看，找出的buddy时在原来的下标中往上或向下走
*(1<<order个位置
*而这里的函数是找出合并后的新块的首地址
*也就是说如果上面是加，这里的基地址不变
*而如果上面是减，这里往下减1<<order
*其中这里的标号不是物理地址，也不是和mem_map
*直接关联，而是运用于buddy算法，也就是这里的
*构造出来的特定的表示，他使得这里的伙伴的寻找
*和伙伴的合并实现的很巧妙
*/
combined_idx = __find_combined_index(page_idx, order);
page = page + (combined_idx - page_idx);
page_idx = combined_idx;
order++;
}
set_page_order(page, order);/*设置page的私有属性，伙伴系统通过这个值来
确定页面所属的order*/
list_add(&page->lru,
&zone->free_area[order].free_list[migratetype]);/*伙伴系统中每一种order有5中空闲链表*/
zone->free_area[order].nr_free++;/*对应order的空闲块加一*/
}
四、关于伙伴的操作
4.1，查找伙伴
www.2cto.com
static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
/*伙伴的计算原理，
*实际上，使用(1<<order)掩码的异或(XOR)转换page_idx第order位
*的值。因此，如果这个位原来是0，buddy_idx就等于page_idx+order
*相反，如果这个位原先是1，buddy_idx就等于page_idx-order
*此计算出来的伙伴为在mem_map中的下标
*/
unsigned long buddy_idx = page_idx ^ (1 << order);
/*返回伙伴块的页面基址*/
return page + (buddy_idx - page_idx);
}
4.2，检查是否为伙伴
www.2cto.com
static inline int page_is_buddy(struct page *page, struct page *buddy,
int order)
{
if (!pfn_valid_within(page_to_pfn(buddy)))/*验证此buddy的有效性*/
return 0;
if (page_zone_id(page) != page_zone_id(buddy))/*验证page和他的buddy是否在同一个zone中*/
return 0;
/*验证相关位和buddy的order值*/
/* 通过检查PG_buddy 标志位判断buddy是否在伙伴系统中，并且buddy是否在order级的
链表中，page的private成员存放页块所在链表的order。*/
if (PageBuddy(buddy) && page_order(buddy) == order) {
VM_BUG_ON(page_count(buddy) != 0);
return 1;
}
return 0;
}
总结：伙伴系统内存释放或称主要流程
1，如果释放的是单个页面，需要根据页面类型考虑是否释放到伙伴系统中，同时，将其加入到pcp链表中。如果pcp链表中内存过多，调用free_pcppages_bulk()函数将大块内存放回伙伴系统中；
2，如果释放的是多个页面，直接调用__free_one_page()释放到伙伴系统中。
3，释放到伙伴系统中时，需要考虑和伙伴的合并情况。
