linux内存管理之伙伴系统分析(三)

再来看一个多页面的释放操作,调用__free_pages_ok(),代码如下:

//释放的起始页面:page

//页面个数:2^order

void __free_pages_ok(struct page *page, unsigned int order)

{

                              //声时并初始化一个链表

                              LIST_HEAD(list);

                              int i;

 

                              arch_free_page(page, order);

 

                              mod_page_state(pgfree, 1 << order);

                              for (i = 0 ; i < (1 << order) ; ++i)

                                 free_pages_check(__FUNCTION__, page + i);

                              list_add(&page->lru, &list);

                              kernel_map_pages(page, 1<

                              free_pages_bulk(page_zone(page), 1, &list, order);

}

它的核心处理都是在free_pages_bulk()完成的

//cout:释放的次数

//order:每次释放2^order个页面

//例如:要释放x个单页面,count = x order=0

//释放2^x大小的连续页面 count = 1 order = x

static int

free_pages_bulk(struct zone *zone, int count,

                                 struct list_head *list, unsigned int order)

{

                              unsigned long flags;

                              struct free_area *area;

                              struct page *base, *page = NULL;

                              int ret = 0;

 

                              base = zone->zone_mem_map;

                              //找到要释放大小页面的空闲链

                              area = zone->free_area + order;

                              spin_lock_irqsave(&zone->lock, flags);

                              zone->all_unreclaimable = 0;

                              zone->pages_scanned = 0;

                              //如果页面释放完了,或者循环次数已尽

                              while (!list_empty(list) && count--) {

                                 page = list_entry(list->prev, struct page, lru);

                                 /* have to delete it as __free_pages_bulk list manipulates */

                                 list_del(&page->lru);

                                 __free_pages_bulk(page, base, zone, area, order);

                                 ret++;

                              }

                              spin_unlock_irqrestore(&zone->lock, flags);

                              return ret;

}

调用__free_pages_bulk(),代码如下:

参数含义:

Page:要释放的超始page

Base:对应zone的页数组的首地址

Zone:

Area:将页面释放到此空闲区

Order:释放的连续空闲区大小

static inline void __free_pages_bulk (struct page *page, struct page *base,

                                 struct zone *zone, struct free_area *area, unsigned int order)

{

                              unsigned long page_idx, index, mask;

 

                              if (order)

                                 destroy_compound_page(page, order);

                              //假设order = 3

                              //mask = 1111 1000

                              mask = (~0UL) << order;

                              //取得页在zone中页数组中的序号

                              page_idx = page - base;

                              //~mask:0000 0111

                              //判断page_idx是不是order位对齐的

                              //结合前面alloc所分析的,不难得出在2^order大小空闲区中.

                              //空闲块的首地址必须是2^order的倍数

                              if (page_idx & ~mask)

                                 BUG();

                              //得到page在链表中的分配位图对应位,前面已经介绍过

                              index = page_idx >> (1 + order);

                             

                              //更新zone 的空闲区统计计数

                              zone->free_pages += 1 << order;

                              //循环,合并内存

                              while (order < MAX_ORDER-1) {

                                 struct page *buddy1, *buddy2;

 

                                 BUG_ON(area >= zone->free_area + MAX_ORDER);

       //判断相邻块是否空闲.前面说过,为0的时候,是两者都空闲或//两者都分配出去了

                                 if (!__test_and_change_bit(index, area->map))

                                     /*

                                      * the buddy page is still allocated.

                                      */

                                     break;

 

                                 /* Move the buddy up one level. */

                              //相邻块是空闲的

                                 //它的邻居块

                                 buddy1 = base + (page_idx ^ (1 << order));

                                 //它自已

                                 buddy2 = base + page_idx;

                                 //判断是否超过zone所允许的page范围

                                 BUG_ON(bad_range(zone, buddy1));

                                 BUG_ON(bad_range(zone, buddy2));

                                 //将其从现有的空闲链中脱落

                                 list_del(&buddy1->lru);

                                 //到它的上一级,判断是否有能合并的内存块

                                 mask <<= 1;

                                 order++;

                                 area++;

                                 index >>= 1;

                                 page_idx &= mask;

                              }

                              list_add(&(base + page_idx)->lru, &area->free_list);}

 

 

 

如上图所示(标记为阴影的代表空闲块),此时系统将第4个单页表释放到伙伴系统.

首先,它会到相应大小的(2^0)的空闲链表入队.判断相邻块的空闲情况,此时,因为第三个是空闲的,所以可以合并为一块2^1的空闲块.继续判断2^1链中相邻块是否是空闲的,上图中可以将2^1的两个块合成一个大块,然后继续判断2^2中是否可以继续合并,依次类推.

上述代码中,涉及到几个位操作,分析如下:

1:得到相邻块的的起始page:

buddy1 = base + (page_idx ^ (1 << order))

如下图示:

 

根据上面的分析,可得知page_idx本身就是order位对齐的,所以,它的低order位为零.此外,再根据0与任何数异或值不变,1与数异或都相反的规律,我们可以得知,位运算结果只跟order+1位有关.据此就可以计算出它的“伙伴块”

2:得到高一级空闲链的首空闲块序号：

mask <<= 1;

page_idx &= mask;

只要按着高一级链表的order位对齐就行了

3:得到空闲块在高一级链表中对应的分配位图位

index >>= 1;

在前面分析过对应位的计算方法，在高一级空闲链中的位对应当前除二

其实这一个过程在操作系统设计中也叫“内存拼凑”，就是把剩余小内存，拼成连续的大内存，以满足某些程序的需要。

总结：

Linux采用页面为基本对应进行大内存的管理，其中2。6内核新加的pcp结构缓解了单页面频繁分配与释放对内存造成的压力。但是，内存分配与释放是很费时间的操作，特别是内存释放，要引发内存拼凑，因此，在编写程序的时候，尽量避免大内存的频繁操作。但仔细一想，linux内存管理还是有很多不如人意的地方：比如说释放内存的时候，效率十分低下，所以，很多公司在做嵌入式开发的时候，都自己修改了大页面的管理算法