关于伙伴系统里伙伴块的定位

　著名的管理连续页面分配的内存分配算法:伙伴算法。

　　　　基本原理貌似还是很简单。但是细节问题... 很恼火... 下面就是关于在合并伙伴块中有关定位伙伴块的一些问题。

在mm/page_alloc.c文件中的__free_pages_ok()函数。
只写出有关兄弟块定位的代码.简化如下:

参数: struct page *page释放块的第一个页面。unsigned int order:释放块的规模,2^order个页面。

unsigned long page_idx, mask;

struct page *base;

struct page *buddy1, buddy2;

zone_t  *zone;

mask = (!0UL) << order;

zone = page_zone(page);

base = zone->zone_mem_map;

page_idx = page - base;

buddy1 = base + (page_idx ^-mask);

buddy2 = base + page_idx;

从上可以以及其后的代码可以知道.buddy2一定是刚刚释放的页面块。buddy1一定是buddy2的在空闲链表.

为何如此就能够确定两个兄弟块的位置?

首先来看以看兄弟块的第一个页面的页描述符在所属区域的偏移与order的关系.

不妨假大小为order的兄弟块中的第一个(即为与较低地址的)的偏移为x(计算方式如上代码

page - zone->zone_mem_map)。则其兄弟的偏移为x + 1 << order。由兄弟块的划分可以得出结论:

x & (1 << order) = 0. 故,若偏移为x的兄弟块位于左边(较低地址处),则x ^ (1 << order) 即为其右边兄弟块的偏移值。

这正是上面代码计算buddy1的方法.只不过形式是page_idx ^ -mask。而mask = (~0UL) << order。

-mask = ~mask + 1 = 1 << order。

由此分析就清楚定位兄弟块的原理。

isn't it a very brilliant way?!

that's it!!!