分类： LINUX
2011-10-14 14:40:50
1. 内存管理之内存分配
Linux为了实现内存分配的高效、防止大量碎片产生，最终产生了当前的内存分配的层次结构：buddy allocator/slob allocator/memory poll，其层次关系如下图。
Buddy Allocator
Buddy 是为了避免系统在频繁申请、释放不同大小的页框组导致的内存外碎片。道理很简单，频繁的申请释放，很有可能导致无法申请一组大的连续内存，虽然系统当前确实有这么大的剩余内存。
Buddy的分配思想很简单，将管理区的每种可用内存划分成order为0、1、2…..n的连续内存块，分配时在大小最接近的块中分配，然后将这个块分裂放入低order块组中；在内存释放时，再大小相关的伙伴块合并，放入高order块组中。当然为了保证合并后的内存块就是之前分裂的那个大块，同时满足以下3个条件的两个块才被合并：
l 两个块相同的大小，记为b
l 他们的物理地址连续
l 第一块的第一个页框的物理地址为 的倍数（保证合并块的顺序）
下面来看看buddy allocator在Linux下的实现。
/* Find a page of the appropriate size in the preferred list */
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
area = &(zone->free_area[current_order]);
if (list_empty(&area->free_list[migratetype]))
continue;
page = list_entry(area->free_list[migratetype].next,
struct page, lru);
list_del(&page->lru);
rmv_page_order(page);
area->nr_free--; // count of mem-block of this order
expand(zone, page, order, current_order, area, migratetype); // 维护buddy结构
return page;
}
接下来看看分配中最重要的函数，它维护者buddy的分配结构。
static inline void expand(struct zone *zone, struct page *page,
int low, int high, struct free_area *area,
int migratetype)
{
unsigned long size = 1 << high;
while (high > low) { // 如果一个块需要被分裂，则将它为分配的块放入低级的
//快组中
area--;
high--;
size >>= 1;
VM_BUG_ON(bad_range(zone, &page[size]));
list_add(&page[size].lru, &area->free_list[migratetype]); // 将分裂后的小块加入到小
//块order对应的组中，并计数+1
area->nr_free++;
set_page_order(&page[size], high); //page[size] 为分裂后小块的第一个页，将其order
// 设置为 high，
}
}
这样就成功的将分裂后的块迁移到了相应的组中，在这里Kernel充分利用了内存结构的特点，使用page[size]就获得的分裂的第一个页框（在一个块组中，所有页都是连续的）
接下来就是伙伴页的释放合并了。
static inline void __free_one_page(struct page *page,
struct zone *zone, unsigned int order,
int migratetype)
{
……
while (order < MAX_ORDER-1) {
buddy = __page_find_buddy(page, page_idx, order); // 见下面的函数说明
if (!page_is_buddy(page, buddy, order)) // 这里只是检查buddy页是否有确有buddy，
// 且他们的order是否相等
break;
/* Our buddy is free, merge with it and move up one order. */
list_del(&buddy->lru);
zone->free_area[order].nr_free--;
rmv_page_order(buddy); //将buddy从现有的area上移除，
combined_idx = __find_combined_index(page_idx, order);
page = page + (combined_idx - page_idx);
page_idx = combined_idx; // 页合并，
order++; // 继续查看是否有更高级的order可用作合并
}
set_page_order(page, order);
/*
* If this is not the largest possible page, check if the buddy
* of the next-highest order is free. If it is, it's possible
* that pages are being freed that will coalesce soon. In case,
* that is happening, add the free page to the tail of the list
* so it's less likely to be used soon and more likely to be merged
* as a higher order page
*/
if ((order < MAX_ORDER-1) && pfn_valid_within(page_to_pfn(buddy))) {
struct page *higher_page, *higher_buddy;
combined_idx = __find_combined_index(page_idx, order);
higher_page = page + combined_idx - page_idx;
higher_buddy = __page_find_buddy(higher_page, combined_idx, order + 1);
if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
list_add_tail(&page->lru,
&zone->free_area[order].free_list[migratetype]);
goto out;
}
}
list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
// 在这里kernel巧妙的保证了2*b*4k的要求，其使用页的物理页帧号和其order，用orderMask 异或 物理页帧的低order位及得到当前页的buddy
static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
unsigned long buddy_idx = page_idx ^ (1 << order);
return page + (buddy_idx - page_idx);
}
这样就实现了buddy块的合并，nice，我们又有大的连续物理内存可用了。
另外，为了加快页框的分配，Linux还加入了冷热页的告诉缓存，用以快速的分配单个页框。当然了，冷热页的分配也是基于buddy，从buddy里面进行分配。。
这样，最底层的页框分配就结束了，无论思想还是代码都很简单，紧凑。
Slab allocator
Buddy实现了以页为单位的大块物理内存的分配，但在实际的使用过程中，我们大多时候很少一次分配这么大的以页为单位的内存块，更多的是任意长度的存储单元。Kernel使用Slab分配器很好的解决了这个问题。为了分析slab，还得引入高速缓存（cache），具体描述就不多讲了。
Slab分配器的组成可以简单的描述如下。
待续……
