|
我看Buddy(伙伴)算法－到底是怎么计算"伙伴"地址的
文章来源:http://gliethttp.cublog.cn
对于order=0,索引0-[0],索引1-[1]是伙伴
索引2-[2],索引3-[3]是伙伴
...
索引2*n-[2*n],索引2*n+1-[2*n+1]是伙伴
对于order=1,[索引0-页地址0,索引1-页地址2]是伙伴
[索引2-页地址4,索引3-页地址6]是伙伴
...
[索引n-页地址2n,索引n+1-页地址2*(n+1)]是伙伴
对于order=2,[索引0-页地址0,索引1-页地址4 ]是伙伴
[索引2-页地址8,索引3-页地址12]是伙伴
...
[索引n-页地址4n,索引n+1-页地址4(n+1)]是伙伴
可以看出,索引号就是对应的相应order下的位图号,
有这样一个规律:"对于每一个伙伴都是以偶号n索引[位图号]开始,以下一个奇数号n+1索引[位图号]结束".
好了,知道这样一个规律之后,我们就可以开始"找朋友"了,armlinux中是这样来"找朋友"的:
1.mask = (~0UL)<<order;//mask=页面指数order的掩码
2.//page_idx=page页在所有页中的页帧号
3.if(page_idx & ~mask)BUG();//page_idx页帧号必须以1<
4.buddy_page_idx = page_idx^-mask;//通过^运算,一下子就找到朋友buddy_page_idx的页帧号了
我们来看看为什么一个^-mask操作之后,就轻松找到了我们需要的伙伴页帧号,先看一下下面的对照表:
order 0 1 2 3 4 5 6 7 8 9
mask -1 -2 -4 -8 -16 -32 -64 -128 -256 -512
-maks 1 2 4 8 16 32 64 128 256 512
~mask 0 1 3 7 15 31 63 127 255 511
1.首先对于if(page_idx & ~mask)首先保证在相应order值下,page_idx页帧号是以1<<order为对齐模式的
2.-mask为1<<order的结果,刚好是对齐模式的边界值
3.page_idx^-mask,因为page_idx是对齐的,所以page_idx在边界值(1<<order)
即:-maks之下的((1<<order)-1)即:~mask空间为全0bit
对于异或操作,比如:
page_idx^0明显等于page_idx,即保留所有含1的位,
page_idx^0x02只改变0x02中是1的bit1位,其他位保留,
-mask中为1的位刚好就是边界位,即:(1<<order),所以-mask仅仅改变边界位所在处的page_idx值,
即仅仅改变page_idx的第order位,而改变之后的结果无非有二,不是1就是0,
比如page_idx的第order位为1[奇数],那么page_idx^-mask之后,page_idx的第order位将置0[-1偶数-刚好就是page_idx的朋友],
page_idx的其它位保持不变,
比如page_idx的第order位为0[偶数],那么page_idx^-mask之后,page_idx的第order位将置1[+1奇数-刚好就是page_idx的朋友],
所有情况就这些,"找朋友"就这样轻松的完成了.[gliethttp]
|
