2

因为是先写到记事本里，再粘上来，但不知为什么数据没粘全，所以再粘一遍
很抱歉

今日读BUDDY内存分配算法，算法确实很不错，但LINUX在初始化BUDDY算法的数据结构时很低效。
我先打个比喻：给你一个大碗，里面装满了大米，现在让你大米转移到
另一个碗里，你是把米从一个碗直接倒到另一个碗里，还是把米一粒一粒从一个碗放到另一个碗里？答案是明确的，直接倒。
而linux在初始化BUDDY算法的数据结构时却选择了类似把米从一个碗一粒一粒放到另一个碗里方法。
好了，看看系统是如何初始化BUDDY算法的数据结构的。
BUDDY在回收页面时一般用free_pages(),free_page(),它们都要实现伙伴的合并。而且最多9－order次合并。

在mem_init()中，通过对所有的动态内存进行逐页扫描，并调用free_page()来把空页一页一页的插入BUDDY中。

事实上，动态内存就那么几大块，所以完全可以用一个递归函数用很少的
次数就可完成工作。
我写了一个：
buddy_init( start_addr,end_addr, order)
//start_addr,end_addr为要释放的内存块首尾,order为要插入的BUDDY槽号
{unsigned long mask=(~0ul)<
page *  start,end;  //中间以order为边界的大块的首尾地址

if(order==0)
{free_page(start_addr);　return; }  //递归出口，即只有一页要求释放

//求出start,end;
start=(start_addr+(1< end= end_addr&mask;

for(tmp=start;tmp {free_pages(tmp,order); //中间以order为边界的大块的释放
}

if(start_addr!=start) //若相等，则说明没有左零头，不用再递归
buddy_init(start_addr,start,order-1);
if(end_addr!=end)　//若相等，则说明没有右零头，不用再递归
buddy_init(end,end_addr,order-1);

｝


函数写的不严密，但其思想是尽量用free_pages()来大块大块的释放，
因为这样一次最多可释放512页，比一页一页效率高多了。　　　　　　
--------------------next---------------------
我很久以前也看过buddy算法,也用它写过程序,只是没看过它的初始化的情况,只是好像有一点你没有注意(不知道是不是我记错了),例如你的start=(start_addr+(1"<<"order)-1)&mask;是不是应该在1"<<"order)后面来个PAGE_SHIFT,当然这是小事.至于你说的低效的问题.也许是.对了,你看过他的初始化程序,那么最初系统是不是全部按照order从9,8..开始往下排列.也就是先排9order的,零星的排8,再零星的排7...
ps:会不会是系统初始化的时候,怕某块物理内存坏了,造成内存空间的不连续性,所以要一页一页的插入合并阿?
ps2:你说的打不出某些程序,那是因为这个社区大概是为了安全或者别的编码之类的原因,把一些特殊字符解释错了吧,比如你在两个>之外加一对引号就能正常输入你的程序了.[/Color]　　　　　　
--------------------next---------------------
blueflame:
还是你经验丰富呀，把没显示出来的东西看到了。
我现在也明白过来了：用查看源代码直接读此页的html文本，你是不是这样做的？

free_page()释放一页时，它会从order0开始，改相应的map标记，然后看能不能向上合并（就是通过map的相应位来判断其伙伴在不在），若不可以，它就插入order0，然后返回;若可以，它会和伙伴合并，再向order1里试插入，若还可以合并，则以此推，直到order9，才算结束。
所以若用free_page()初始化化BUDDY时，会发生大量的合并，（因为此时的动态内存是大块连续的，所以最后，除左右零头外，都是属于order9的块）

但若用free_pages(),则因为直接把order9的块分离出来插入order9，所以根本不存在合并现象.至于左右零头，它们会再分解，插入相应的槽中，也不会发生合并现象，因为试图合并，必然失败。

至于说是检查物理内存是否损坏，我想可以分离出来，不要因为要扫描每页物理内存，就“顺便”初始化BUDDY，总之，用free_page()代价太大，（不过确实很
省心，不用另写代码了）　　　　　　
--------------------next---------------------
今天读了＜＜深入理解linux内核＞＞(第一版，2.2内核）的slab分配器原理。
书中讲的kmem_cache_t,kmem_slab_t原理都非常清楚，但一到
kmem_bufctl_t时，让人弄不清它到底如何同前两个结构配合。（当然，这不是作者的过，而是2.2版本对算法实现的不完美）。
最后，我不得不看源代码（2.4.18版本），发现对”对象描述符“的实现有了很大的改进：
1。若SLAB描述符在SLAB内部，它由2.2版本在SLAB的尾部改到首部，且后面紧跟对象描述符。
2。对象描述符原则上可在内部或外部，但linux只把它放在内部，不再放在外部，所以不用记录对象描述符的地址，通过kmem_cache_t,kmem_slab_t，及对象的地址便可算出对象描述符的地址，而且对象描述符的作用更加简单，只是把空对象链起来；已分配的对象的对象描述符没有什么作用了。

我为弄清它，还看了understanding linux kernel第2版，还有情景分析。发现情景分析基本上就是代码，所以讲的不好，书中只有两个图，图2.8画的是2.2版本的情况，图2.9则不知它要表达什么。所以我建议大家看buddy和slab算法时，看understanding linux kernel 第一版和第2版，比较着看，真是讲得很好，它中的图做的很精细，对理解算法很有帮助。

看看不同版本，想想linux的成长过程，不也是很有启发意义的吗？　　　　　　
--------------------next---------------------
昨天发了关于slab算法的帖子，晚上睡觉又想了想，发现有点问题，所以一大早就爬起来，又分析了源代码。
所以做以下更正：

对象描述符在linux2.4中还是可内可外的，只是它和slab描述符如影随形。即它总是紧跟在slab描述符后面，因此，只要知道slab描述符的地址，便可算出对象描述符的地址。
总之，slab描述符在外，它就在外，slab描述符在内，它就在内；
当slab描述符在内时，放在slab区的开始处，即跟在着色区的后面。
当slab描述符在外时，因为不同的cache的slab区放的对象个数不同，所以一个slab所需要的对象描述符的个数是不同的，通过计算可得到“slab描述符加对象描述符数组”所需的内存大小，这便是分配slab描述符时的真正大小。所以在外的slab描述符可能分布在cache_sizes的不同cache中。　　　　　　
--------------------next---------------------
blueflame:
谢谢你的关心。其实过去的一个月我都在看linux，整天的看，有时也看得很烦，当烦的时候，我就下载一部电影看看，或睡上一觉，也就没什么了。
我把学习Linux分成三个阶段：第一阶段是从整体上把linux的各种重要数据结构
和各部分之间的关系及工作机理从思想上想通，再辅之以学习系统编程（我把它称为完成linux的总体设计）就目前来看，到下学期开学就可完成；第二阶段是把linux再从头到尾过一遍，主要完成源代码的分析（我把它称为物理设计）；我估计需2个月。第三阶段基本上就是不断跟踪Linux内核的发展，并有能力做一点修改。
请问你网络方面参考了什么书？
你打算怎么攻克它？

(笑也不争春，只把春来报，待到山花烂漫时，她在从中笑）　　　　　　
--------------------next---------------------