(一)--伙伴系统的概述

Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下，避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题，采用slab解决内部碎片的问题，在这里我们先讨论外部碎片问题。避免外部碎片的方法有两种：一种是之前介绍过的利用非连续内存的分配；另外一种则是用一种有效的方法来监视内存，保证在内核只要申请一小块内存的情况下，不会从大块的连续空闲内存中截取一段过来，从而保证了大块内存的连续性和完整性。显然，前者不能成为解决问题的普遍方法，一来用来映射非连续内存线性地址空间有限，二来每次映射都要改写内核的页表，进而就要刷新TLB，这使得分配的速度大打折扣，这对于要频繁申请内存的内核显然是无法忍受的。因此Linux采用后者来解决外部碎片的问题，也就是著名的伙伴系统。
 
什么是伙伴系统？
      伙伴系统的宗旨就是用最小的内存块来满足内核的对于内存的请求。在最初，只有一个块，也就是整个内存，假如为1M大小，而允许的最小块为64K，那么当我们申请一块200K大小的内存时，就要先将1M的块分裂成两等分，各为512K，这两分之间的关系就称为伙伴，然后再将第一个512K的内存块分裂成两等分，各位256K，将第一个256K的内存块分配给内存，这样就是一个分配的过程。下面我们结合示意图来了解伙伴系统分配和回收内存块的过程。

1 初始化时，系统拥有1M的连续内存，允许的最小的内存块为64K，图中白色的部分为空闲的内存块，着色的代表分配出去了的内存块。

2 程序A申请一块大小为34K的内存，对应的order为0，即2^0=1个最小内存块
 
   2.1 系统中不存在order 0(64K)的内存块，因此order 4(1M)的内存块分裂成两个order 3的内存块(512K)
 
   2.2 仍然没有order 0的内存块，因此order 3的内存块分裂成两个order 2的内存块(256K)
 
   2.3 仍然没有order 0的内存块，因此order 2的内存块分裂成两个order 1的内存块(128K)
 
   2.4 仍然没有order 0的内存块，因此order 1的内存块分裂成两个order 0的内存块(64K)
 
   2.5 找到了order 0的内存块，将其中的一个分配给程序A，现在伙伴系统的内存为一个order 0的内存块，一个order 1的内存块，一个order 2的内存块以及一个order 3的内存块
 
3 程序B申请一块大小为66K的内存，对应的order为1，即2^1=2个最小内存块，由于系统中正好存在一个order 1的内存块，所以直接用来分配
 
4 程序C申请一块大小为35K的内存，对应的order为0，同样由于系统中正好存在一个order 0的内存块，直接用来分配
 
5 程序D申请一块大小为67K的内存，对应的order为1
 
   5.1 系统中不存在order 1的内存块，于是将order 2的内存块分裂成两块order 1的内存块
 
   5.2 找到order 1的内存块，进行分配
 
6 程序B释放了它申请的内存，即一个order 1的内存块
 
7 程序D释放了它申请的内存
 
   7.1 一个order 1的内存块回收到内存当中
 
   7.2由于该内存块的伙伴也是空闲的，因此两个order 1的内存块合并成一个order 2的内存块
 
8 程序A释放了它申请的内存，即一个order 0的内存块
 
9 程序C释放了它申请的内存    
 
   9.1 一个order 0的内存块被释放
 
   9.2 两个order 0伙伴块都是空闲的，进行合并，生成一个order 1的内存块m
 
   9.3 两个order 1伙伴块都是空闲的，进行合并，生成一个order 2的内存块
 
   9.4 两个order 2伙伴块都是空闲的，进行合并，生成一个order 3的内存块
 
   9.5 两个order 3伙伴块都是空闲的，进行合并，生成一个order 4的内存块
 
(二) 相关的数据结构
     在前面的文章中已经简单的介绍过struct zone这个结构，对于每个管理区都有自己的struct zone，而struct zone中的struct free_area则是用来描述该管理区伙伴系统的空闲内存块的
 
<mmzone.h>
 
[cpp]
struct zone {  
    ...  
         ...      
    struct free_area    free_area[MAX_ORDER];  
    ...  
    ...  
}  
 
<mmzone.h>
 
[cpp]
struct free_area {  
    struct list_head    free_list[MIGRATE_TYPES];  
    unsigned long       nr_free;  
};  
 
free_area共有MAX_ORDER个元素，其中第order个元素记录了2^order的空闲块，这些空闲块在free_list中以双向链表的形式组织起来，对于同等大小的空闲块，其类型不同，将组织在不同的free_list中，nr_free记录了该free_area中总共的空闲内存块的数量。MAX_ORDER的默认值为11，这意味着最大内存块的大小为2^10=1024个页框。对于同等大小的内存块，每个内存块的起始页框用于链表的节点进行相连，这些节点对应的着struct page中的lru域
 
[cpp]
struct page {  
       
    ...  
    ...  
    struct list_head lru;       /* Pageout list, eg. active_list 
                     * protected by zone->lru_lock ! 
                     */  
    ...  
}

连接示意图如下：

在2.6.24之前的内核版本中，free_area结构中只有一个free_list数组，而从2.6.24开始，free_area结构中存有MIGRATE_TYPES个free_list,这些数组是根据页框的移动性来划分的，为什么要进行这样的划分呢?实际上也是为了减少碎片而提出的，我们考虑下面的情况：

图中一共有32个页，只分配出了4个页框，但是能够分配的最大连续内存也只有8个页框(因为伙伴系统分配出去的内存必须是2的整数次幂个页框)，内核解决这种问题的办法就是将不同类型的页进行分组。分配出去的页面可分为三种类型：
 
不可移动页(Non-movable pages)：这类页在内存当中有固定的位置，不能移动。内核的核心分配的内存大多属于这种类型
可回收页(Reclaimable pages)：这类页不能直接移动，但可以删除，其内容页可以从其他地方重新生成，例如，映射自文件的数据属于这种类型，针对这种页，内核有专门的页面回收处理
可移动页(Movable pages):这类页可以随意移动，用户空间应用程序所用到的页属于该类别。它们通过页表来映射，如果他们复制到新的位置，页表项也会相应的更新，应用程序不会注意到任何改变。
   假如上图中大部分页都是可移动页，而分配出去的四个页都是不可移动页，由于不可移动页插在了其他类型页的中间，就导致了无法从原本空闲的连续内存区中分配较大的内存块。考虑下图的情况:

将可回收页和不可移动页分开，这样虽然在不可移动页的区域当中无法分配大块的连续内存，但是可回收页的区域却没有受其影响，可以分配大块的连续内存。
 
内核对于迁移类型的定义如下:
 
<mmzone.h>
 
[cpp]
#define MIGRATE_UNMOVABLE     0  
#define MIGRATE_RECLAIMABLE   1  
#define MIGRATE_MOVABLE       2  
#define MIGRATE_PCPTYPES      3 /* the number of types on the pcp lists */  
#define MIGRATE_RESERVE       3  
#define MIGRATE_ISOLATE       4 /* can't allocate from here */  
#define MIGRATE_TYPES         5  
 
前三种类型已经介绍过
 
MIGRATE_PCPTYPES是per_cpu_pageset，即用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目
 
MIGRATE_RESERVE是在前三种的列表中都没用可满足分配的内存块时，就可以从MIGRATE_RESERVE分配
 
MIGRATE_ISOLATE用于跨越NUMA节点移动物理内存页，在大型系统上，它有益于将物理内存页移动到接近于是用该页最频繁地CPU
 
MIGRATE_TYPES表示迁移类型的数目
当一个指定的迁移类型所对应的链表中没有空闲块时，将会按以下定义的顺序到其他迁移类型的链表中寻找: 
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {  
    [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
    [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
    [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },  
    [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */  
};

(三) linux内核对伙伴系统的改进--migrate_type

linux底层使用伙伴系统-buddy管理物理内存，buddy可以被证明是一种很有效的内存管理方式，但是它也拥有很多缺点，其中碎片避免的不完备性 --仅仅寄托于释放时的合并操作而不考虑分配时的策略，这也许是它最大的不足，linux2.6内核的后期版本对这个问题进行了改进，大大避免了碎片的泛 滥。在linux中，buddy是通过下列数据结构表示的(2.6的早期内核): 
struct free_area {
    struct list_head    free_list;
    unsigned long        *map;
};
系统中10个free_area组成一个数组，每一个free_area包含一个链表，每一个链表上链接有空闲内存页面块。后来引入了MIGRATE_TYPE，于是free_area结构体就成了：
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long        nr_free;
};
每一个free_area包含多个链表，其中每一个链表中的内存页面按照其自身是否可以释放或者迁移被归为一类，于是凡是请求“不可迁移”页面的分配请求 全部在free_list[MIGRATE_UNMOVABLE]这条链表上分配，和老版本一样，系统中有10个free_area代表大小为2的N次幂 个不同页面的集合。这种归类可以最小化内存碎片。
     buddy系统本身就有效的防止了碎片，然而还不够。
buddy主要体现在：1.互为buddy的页面块不可能共存于一个free_area链表，它们总是倾向于合并；2.一个free_area的链表中的 页面order相同，但是它们肯定彼此不互为buddy，这些页面用于该order大小需求的页面分配。但是buddy的碎片防止机制寄托于内存使用者会 及时释放掉内存的情况，如果使用者长期不释放内存，或者说在使用者还没有释放内存的这一段时间期间，碎片将是存在的，并且可能还会导致很大的问题，比如在 物理内存中间分配了一页面，然而仅因为分配的这一个页面不可移动，在它被释放之前，系统可用的最大的连续物理内存就只有不到一半物理内存总大小了。究其根 源，这种问题的根源在于buddy系统仅仅释放页面时的合并操作防止了碎片的产生，不管页面从哪里被分配，只要它能有效被释放，碎片就是可以避免的，也就 是说，buddy系统对于分配并没有更多的约束，仅仅满足在10个free_area中从小到大的顺序扫描即可。
     既然找到了buddy的问题，那么只要对分配动作采取一定的约束，碎片就可以进一步避免了。
最简单而又不引入过多复杂性的办法就是将页面按照“可移动”属性分类，将不可移动的页面分为一类，将可以移动的页面分为一类，它们各自占据一块足够大的连 续物理空间，不可移动的页面分配需求则尽量在它自己的页面类中分配，可移动的页面也一样，这样一来，不可移动的页面的不可移动性仅仅影响它自身的类别而不 会导致一个不可移动的页面两边都是可移动的页面。这就是MIGRATE_TYPE被引入的目的。MIGRATE_TYPE限制了内存页面的分配地点从而避 免碎片，而不再仅仅寄希望于它们被释放时通过合并避免碎片。
     可以说MIGRATE_TYPE仅仅是一种防止碎片的策略，不应该因为它的存在而影响到内存分配的结果，也就是说，如果在一个MIGRATE_TYPE链 表中没有内存可以分配了，那么也还是可以从别的链表中“暂时抢”一些的。另外，还有一个问题，内核载初始化的时候如何为“不可移动类”或者“可移动类”页 面指定初始大小呢？也就是说，一开始，系统的free_area中的这些类别链表的页面各该是多少个呢？事实上，内核从来没有指定过初始大小，而是一开始 将所有页面都归到“可移动”组当中，而别的组全部都是空的，等到真的有不可移动页面需求的时候再从可移动组中拨一批给不可移动组链表，想一下这也是合理 的，毕竟只是一些“不可移动”的页面造成了内存的长期碎片化，如果没有这些长期使用的不可移动页面，碎片的问题是不大的。这个从 __rmqueue_fallback函数中可以看出，系统的内存子系统拥有一个fallbacks序列，该序列展示了一个分配序列，也就是如果一个 migratetype链表中如果分配不到内存的话，下一个应该在哪个migratetype链表中分配。从__rmqueue_fallback可以看 出，如果从要求的migratetype空闲链表中分配不到内存的话，并不是在根据fallbacks序列在“下一个”链表中仅仅分配到自己本次所需的就 完事了，而是一次性从fallbacks序列中指示的链表中转移足够多的页面到分配时要求的migratetype链表，毕竟该种类型的空闲链表已经没有 页面了，确实需要补充了，并且如果补充的页面太少，那么就会给转移的源migratetype类型组造成碎片，只有一次性分配一大块内存，才不至于引入碎 片。
static struct page *__rmqueue_fallback(struct zone *zone, int order,
                        int start_migratetype)
{
    struct free_area * area;
    int current_order;
    struct page *page;
    int migratetype, i;
    //尽量一次性拨出尽可能多的内存页面给“该”migratetype的free_area链表
    for (current_order = MAX_ORDER-1; current_order >= order; --current_order) {
        for (i = 0; i < MIGRATE_TYPES - 1; i++) {
            migratetype = fallbacks[start_migratetype][i];
            if (migratetype == MIGRATE_RESERVE)  //不允许占用保留内存
                continue;
            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);
            area->nr_free--;
            ...
            list_del(&page->lru);
            rmv_page_order(page);
            __mod_zone_page_state(zone, NR_FREE_PAGES, -(1UL << order));
            if (current_order == pageblock_order)
                set_pageblock_migratetype(page,    start_migratetype);
            //将除去本次自己要用的page[order]之外的其它页面全部补充进该area的migratetype空闲链表
            expand(zone, page, order, current_order, area, migratetype);
            return page;
        }
    }
    return __rmqueue_smallest(zone, order, MIGRATE_RESERVE);
}
     另外，还有一种类似的机制用于避免碎片，那就是使用ZONE的概念，新构造出一个虚拟的ZONE--ZONE_MOVABLE，所谓的虚拟就是它并不和任 何物理内存区间相关联，而是可以附着在任何的物理zone上，用户可以通过命令行参数指定用于“可移动”或者“不可移动”的内存的大小，从而也就规定了虚 拟的ZONE_MOVABLE的大小。一般的最终比较高的物理内存区域用于可移动的虚拟zone(ZONE_MOVABLE)分配，这是因为低地址内存更 多的用于dma或者isa或者内核数据结构(一一线性映射)等，而高内存则一般用于用户进程(可以交换到交换空间...)