浅析linux内核内存管理之buddy system

Linux采用著名的伙伴系统(buddy system)算法来解决外碎片问题。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续的页框。对1024个页框的最大请求对应着4MB大小的连续RAM块。每个块的第一个页框的物理地址是该块大小的整数倍。例如，大小为16个页框的块，其起始地址是16*2^12的倍数。内核试图把大小为b的一对空闲伙伴块合并为一个大小为2b的单独块。满足以下条件的两个块称为伙伴：

两个块具有相同的大小，记作b他们的物理地址是连续的第一块的第一个页框的物理地址是2*b*2^12的倍数该算法是迭代的，如果它成功合并所释放的块，它会试图合并2b的块，以再次试图形成更大的块

核心数据结构

实际上，每个管理区都关系到mem_map元素的子集，子集中的第一个元素和元素个数分别由管理区描述符的zone_mem_map和size字段指定。包含有11个元素，元素类型为free_area的一个数组，每个元素对应一种块大小。该数组存放在描述符的free_area字段中。

[html]view plaincopy

structfree_area{structlist_headfree_list;unsignedlongnr_free;};

我们考虑管理区描述符中free_area数组的第k个元素，它标识所有大小为2^k的空闲块。这个元素的free_list字段是双向循环链表的头，这个双向循环链表集中了大小为2^k页的空闲块对应的页描述符。更精确的说，该链表包含每个空闲页块(大小为2^k)的起始页框的页描述符；指向链表中相邻元素的指针存放在页描述符的lru字段中。除了链表头外，free_area数组的第k个元素同样包含字段nr_free，它指定了大小为2^k页的空闲块的个数。当然，如果没有大小为2^k的空闲页框块，则nr_free等于0且free_list为空(free_list的两个指针都指向它自己的free_list字段)。最后，一个2^k的空闲页块的第一个页的描述符的private字段存放了块的order，也就是数字k。正是由于这个字段，当页块被释放时，内核可以确定这个块的伙伴是否也空闲，如果是的话，它可以把两个块结合成大小为2^(k+1)页的单一块。

从buddy system分配pages

page allocator是buddy system的前端，buddy system进行实际的页管理与分配，下面分析buddy system的页分配函数：

[html]view plaincopy

458staticintrmqueue_bulk(structzone*zone,unsignedintorder,459unsignedlongcount,structlist_head*list)460{461unsignedlongflags;462inti;463intallocated=0;464structpage*page;465466spin_lock_irqsave(&zone->lock,flags);467for(i=0;i<count;++i){468page=__rmqueue(zone,order);469if(page==NULL)470break;471allocated++;472list_add_tail(&page->lru,list);473}474spin_unlock_irqrestore(&zone->lock,flags);475returnallocated;476}

主要调用了__rmqueue函数:

[html]view plaincopy

431staticstructpage*__rmqueue(structzone*zone,unsignedintorder)432{433structfree_area*area;434unsignedintcurrent_order;435structpage*page;436437for(current_order=order;current_order<MAX_ORDER;++current_order){438area=zone->free_area+current_order;439if(list_empty(&area->free_list))440continue;441442page=list_entry(area->free_list.next,structpage,lru);443list_del(&page->lru);444rmv_page_order(page);445area->nr_free–;446zone->free_pages-=1UL<<order;447returnexpand(zone,page,order,current_order,area);448}449450returnNULL;451}

187staticinlinevoidrmv_page_order(structpage*page)188{189__ClearPagePrivate(page);190page->private=0;191}

减少指定free_area上的空闲page块的计数减少管理器的空闲page数如果从比指定的order高的order的free_area分配，则会产生一些伙伴，把伙伴放到低于分配的order的free_area链表中

分析expand实现：

[html]view plaincopy

368expand(structzone*zone,structpage*page,369intlow,inthigh,structfree_area*area)370{371unsignedlongsize=1<<high;372373while(high>low){374area–;375high–;376size>>=1;377BUG_ON(bad_range(zone,&page[size]));378list_add(&page[size].lru,&area->free_list);379area->nr_free++;380set_page_order(&page[size],high);381}382returnpage;383}

比如之前需要从order为2的分配，但是order为2的free_area的free_list没有page块了，则去order为3的链表上找，如果此时order为3的链表上也没有空闲page块，则到order为4的链表上去找，如果此时恰巧找到则停止。这样获得了一个有16个page的page块。但是只请求了4个page，此时那些多余的page要放到order为2，order为3的链表上。看程序，首先获得size，也就是这里说的16，在我的例子里，high为4，low为2。area–也就是获得order为3的那个free_area；high–，此时为3；size>>=1，此时size为8；将刚才那个16个page的page块的后8个page组成块放到order为3的链表上，增加order为3上的块计数，

[html]view plaincopy

182staticinlinevoidset_page_order(structpage*page,intorder){183page->private=order;184__SetPagePrivate(page);185}

设置这个有8个page的page块的第一个page的页描述符的private字段存放order值，下一个循环照此原理，最后反回给page allocator的是刚才那16个page的块的最前面的4个page组成的page块的第一个page的页描述符的地址。

释放pages到buddy system

[html]view plaincopy

308free_pages_bulk(structzone*zone,intcount,309structlist_head*list,unsignedintorder)310{311unsignedlongflags;312structpage*base,*page=NULL;313intret=0;314315base=zone->zone_mem_map;316spin_lock_irqsave(&zone->lock,flags);317zone->all_unreclaimable=0;318zone->pages_scanned=0;319while(!list_empty(list)&&count–){320page=list_entry(list->prev,structpage,lru);321/*havetodeleteitas__free_pages_bulklistmanipulates*/322list_del(&page->lru);323__free_pages_bulk(page,base,zone,order);324ret++;325}326spin_unlock_irqrestore(&zone->lock,flags);327returnret;328}

主要是调用了__free_pages_bulk函数：

[html]view plaincopy

236staticinlinevoid__free_pages_bulk(structpage*page,structpage*base,237structzone*zone,unsignedintorder)238{239unsignedlongpage_idx;240structpage*coalesced;241intorder_size=1<<order;242243if(unlikely(order))244destroy_compound_page(page,order);245246page_idx=page-base;247248BUG_ON(page_idx&(order_size-1));249BUG_ON(bad_range(zone,page));250251zone->free_pages+=order_size;252while(order<MAX_ORDER-1){253structfree_area*area;254structpage*buddy;255intbuddy_idx;256257buddy_idx=(page_idx^(1<<order));258buddy=base+buddy_idx;259if(bad_range(zone,buddy))260break;261if(!page_is_buddy(buddy,order))262break;263/*Movethebuddyuponelevel.*/264list_del(&buddy->lru);265area=zone->free_area+order;266area->nr_free–;267rmv_page_order(buddy);268page_idx&=buddy_idx;269order++;270}271coalesced=base+page_idx;272set_page_order(coalesced,order);273list_add(&coalesced->lru,&zone->free_area[order].free_list);274zone->free_area[order].nr_free++;275}

page_idx局部变量包含块中第一个页框的下标，这是相对管理区中的第一个页框而言的。zone_mem_map是指向管理区第一个页描述符的指针。buddy_idx是page_idx的伙伴的下标这个是buddy_idx是怎样算出来的呢，可以举一个例子[html]view plaincopy

例如对于0order,(0,1),(2,3),(3,4)…,已知2,则伙伴就是3.对于1order,(0/1,2/3),(4/5,6/7),(8/9,10/11),已知2/3,则伙伴是0/1.

如果现在order=1,并且是4/5这个块，现在要找伙伴6/7这个块，那么4为0100，与1<<1即0010异或，得0110,即6如果现在order=1,并且是6/7这个块，现在要找伙伴4/5这个块，那么6为0110，与1<<1即0010异或，得0100,即4所以ULK3上说使用(1<<order)掩码的异或(XOR)转换page_idx第order位的值。因此，如果这个位原先是0，buddy_idx就等于page_idx+order_size;相反，如果这个位原先是1，buddy_idx就等于page_idx-order_sizepage_idx &= buddy_idx可以通过刚才的例子看出这个是获得两个兄弟前面的那个兄弟[html]view plaincopy

202staticinlineintpage_is_buddy(structpage*page,intorder)203{204if(PagePrivate(page)&&205(page_order(page)==order)&&206!PageReserved(page)&&207page_count(page)==0)208return1;209return0;210}

检查两个page块是否是兄弟

注意这里是个while循环，page块释放到buddy system后，如果能与其他page块合并，则一层层向上找伙伴，然后合并成更大的，再向上找伙伴，实在找不到了就停止了！

人生难免遇风雨,天空晴朗有阴云,别因雨水湿透衣衫而难过,

相关文章：

你感兴趣的文章：

标签云：