本文共 2603 字，大约阅读时间需要 8 分钟。

对于一段连续内存块，我们这里假设为1024个页[0, 1023]。 |------------------------------------------------------| |0-------234-------------345------------678--------1023| 我们首先看看查找buddy算法，查找buddy需要一个pfn和其order。查找函数是__find_buddy_index()。算法实现非常简单：static inline unsigned long__find_buddy_index(unsigned long page_idx, unsigned int order){ return page_idx ^ (1 << order);}这里： * 1) Any buddy B1 will have an order O twin B2 which satisfies * the following equation: *     B2 = B1 ^ (1 << O) * For example, if the starting buddy (buddy2) is #8 its order * 1 buddy is #10: *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10 * * 2) Any buddy B will have an order O+1 parent P which * satisfies the following equation: *     P = B & ~(1 << O)什么意思呢？1. 任何B1的伙伴(order=O)B2，都满足下面等式： B2 = B1 ^ (1 << O) 比如说，8(order=1)的伙伴是10.2. 任何B的O+1的伙伴满足下面关系式： P = B & ~(1 << O)这些可能不好理解。我们假设上面有1024个页。很简单，B1[0, 511]和B2[512，1023]是order=9伙伴。B1因为是9阶的，其想要并入相等的页才能成为一个order=10的页，只能是连续的两个512页。这个时候，我们称B1和B2为伙伴，B1是B2的伙伴，当然B2也是B1的伙伴。利用上面的公式也可以得到B1和B2是伙伴关系。其实，还有一点，0到511之间的任意一个数字，只要O为9，其按照上面公式后，伙伴仍是B2中的某一数字。B1=2,B2=514 O=9B1=5,B2=517 O=9B1=200,B2=712 O=9B1=1300,B2=1812 O=9B1=800,B2=288 O=9而O+1则为：B1=2,B2=1026 O=10B1=5,B2=1029 O=10B1=200,B2=1224 O=10B1=1300,B2=276 O=10 而一般我们是这样的，如果pfn=2，并且O=为2，则说明以pfn开始的连续2^2个页是空闲的。这样就是2-5这四个页空闲。如果pfn为234，order为3，则234-241这8个页是空闲的。再比如，pfn为200，order为9，这说明有512个空闲页，起始页为200，终止页为200+512-1即为711，注意，上面给出的200的伙伴为712.也就是说，如果200开始有512个页空闲，那么下次合并时，这512个页会以712开始页帧进行合并。当然这里说的是O为9.一般来说，这里说的不会这么极端。 对于buddy的检查主要由函数page_is_buddy()处理，其实现如下：/* * This function checks whether a page is free && is the buddy * we can do coalesce a page and its buddy if * (a) the buddy is not in a hole && * (b) the buddy is in the buddy system && * (c) a page and its buddy have the same order && * (d) a page and its buddy are in the same zone. * * For recording whether a page is in the buddy system, we set ->_mapcount -2. * Setting, clearing, and testing _mapcount -2 is serialized by zone->lock. * * For recording page's order, we use page_private(page). */static inline int page_is_buddy(struct page *page, struct page *buddy,        int order){ if (!pfn_valid_within(page_to_pfn(buddy)))  return 0;  if (page_zone_id(page) != page_zone_id(buddy))  return 0;  if (page_is_guard(buddy) && page_order(buddy) == order) {  VM_BUG_ON(page_count(buddy) != 0);  return 1; }  if (PageBuddy(buddy) && page_order(buddy) == order) {  VM_BUG_ON(page_count(buddy) != 0);  return 1; } return 0;} 需要注意BUDDY的几个条件，即同一个zone，连续的物理内存在同一个块中。当然也要是同一个order。需要注意，我们对页使用的是页帧pfn号，不是页的虚拟地址。这里需要转换一下。在page给出的buddy相吻合情况下，返回1，否则返回0.当然最后需要注意，buddy是空闲内存，如果已经使用了，那就不叫buddy了。所以上面的页_count计数应该为-1.    

转载地址：http://bzhti.baihongyu.com/