Linux内核剖析之内存管理

2.2 伙伴系统

频繁的请求和释放不同大小的连续页框，必然导致在已分配页框的块内分散了许多小块的空闲页框。由此产生的问题是：即使有足够的空闲页框可以满足请求，但当要分配一个大块的连续页框时，无法满足请求。这就是著名的内存管理问题：外碎片问题。

linux采用伙伴系统算法来解决外碎片的问题。

把所有的空闲页框分组为11个块链表。每个块链表包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续的页框。每个块的第一个页框的物理地址必须是该块大小的整数倍。例如，大小为16个页框的块，其起始地址为16x212的倍数。

算法原理：

通过一个简单的例子说明该算法的工作原理——

假设请求一个256个页框的块，先在256个页框的链表内检查是否有一个空闲的块。如果没有这样的块，算法会查找下一个更大的块，在512个页框的链表中找一个空闲块。如果存在这样的块，内核就把512的页框分成两半，一半用作满足请求，另一半插入256个页框的链表中。如果512个页框的块链表也没有空闲块，就继续找更大的块，1024个页框的块。如果这样的块存在，内核把1024个页框的256个页框用作请求，然后从剩余的768个中拿出512个插入512个页框的链表中，把最后256个插入256个页框的链表中。

页框块的释放过程：

内核试图把大小为b的一对空闲伙伴块合并为一个大小为2b的单独块。

满足以下条件的两个块成为伙伴：

两个块具有相同的大小：b；它们的物理地址连续。

第一个页框的物理地址为2xbx212的倍数。

该算法是迭代的，如果成功合并所释放的块，它会试图合并2b的块。

数据结构：

分配块：

static struct page *__rmqueue(struct zone *zone, unsigned int order){    struct free_area * area;    unsigned int current_order;    struct page *page;    unsigned int index;        for (current_order = order; current_order < MAX_ORDER; ++current_order) {        area = zone->free_area + current_order;        if (list_empty(&area->free_list))            continue;    //从order开始，搜索第一个满足要求的页框块         page = list_entry(area->free_list.next, struct page, lru);        list_del(&page->lru);    //将找到的页框块的第一个页框描述符从链表删除        index = page - zone->zone_mem_map;        if (current_order != MAX_ORDER-1)            MARK_USED(index, current_order, area);        zone->free_pages -= 1UL << order;      //管理区的内存页框块减少        return expand(zone, page, index, order, current_order, area);          //如果current_order>order，把剩余未分配的页框块，插入合适的链表    ?}    return NULL;} static inline struct page * expand(struct zone *zone, struct page *page, unsigned long index, int low, int high, struct free_area *area){//以前面提到的例子为例    unsigned long size = 1 << high;    while (high > low) {        area--;        high--;        size >>= 1;        BUG_ON(bad_range(zone, &page[size]));        list_add(&page[size].lru, &area->free_list);        MARK_USED(index + size, high, area)；    }    return page;}

static inline void __free_pages_bulk (struct page *page, struct page *base,        struct zone *zone, struct free_area *area, unsigned int order){        unsigned long page_idx, index, mask;         if (order)                destroy_compound_page(page, order);        mask = (~0UL) << order;        page_idx = page - base;   //块中第一个页框的索引号，相对于管理区的首个页框        if (page_idx & ~mask)     //页框块的起始物理地址必须是2orderx212   所以page_idx需要是2order的倍数               BUG();        index = page_idx >> (1 + order);          zone->free_pages += 1 << order;        while (order < MAX_ORDER-1) {                struct page *buddy1, *buddy2;                 BUG_ON(area >= zone->free_area + MAX_ORDER);                if (!__test_and_change_bit(index, area->map))    //检查伙伴块是否已经被分配                /*                                               //???????                * the buddy page is still allocated.                */                        break;                 /* Move the buddy up one level. */                buddy1 = base + (page_idx ^ (1 << order));       //伙伴块的索引号                buddy2 = base + page_idx;                BUG_ON(bad_range(zone, buddy1));                BUG_ON(bad_range(zone, buddy2));                list_del(&buddy1->lru);                mask <<= 1;                order++;                area++;                index >>= 1;                page_idx &= mask;      //合并后块中第一个页框的索引        }        list_add(&(base + page_idx)->lru, &area->free_list);}

struct zone {    struct per_cpu_pageset  pageset[]; }

struct per_cpu_pageset {    int count;          //高速缓存中页框的个数    int low;            //下界，高速缓存需要补充    int high;           //上界，高速缓存需要释放到伙伴系统中    int batch;          //每次添加或释放的个数    struct list_head list   //高速缓存中包含的页框描述符链表}

__va((unsigned long)(page-mem_pag) << 12)

static int pkmap_count[LAST_PKMAP];

void *kmap(struct page *page){    might_sleep();    if (page < highmem_start_page)             return page_address(page);    //不在高端内存中，直接返回映射的线性地址    return kmap_high(page);}

void fastcall *kmap_high(struct page *page){    unsigned long vaddr;    spin_lock(&kmap_lock);    vaddr = (unsigned long)page_address(page);    if (!vaddr)       vaddr = map_new_virtual(page);    pkmap_count[PKMAP_NR(vaddr)]++;    if (pkmap_count[PKMAP_NR(vaddr)] < 2)       BUG();    spin_unlock(&kmap_lock);       return (void*) vaddr;}

static inline unsigned long map_new_virtual(struct page *page){    unsigned long vaddr;    int count; start:    count = LAST_PKMAP;    /* Find an empty entry */    for (;;) {       last_pkmap_nr = (last_pkmap_nr + 1) & LAST_PKMAP_MASK;       if (!last_pkmap_nr) {           flush_all_zero_pkmaps();           count = LAST_PKMAP;       }       if (!pkmap_count[last_pkmap_nr])           break;  /* Found a usable entry */       if (--count)           continue;       /*        * Sleep for somebody else to unmap their entries        */       {           DECLARE_WAITQUEUE(wait, current);            __set_current_state(TASK_UNINTERRUPTIBLE);           add_wait_queue(&pkmap_map_wait, &wait);           spin_unlock(&kmap_lock);           schedule();           remove_wait_queue(&pkmap_map_wait, &wait);           spin_lock(&kmap_lock);           /* Somebody else might have mapped it while we slept */           if (page_address(page))               return (unsigned long)page_address(page);            /* Re-start */              goto start;        }    }    vaddr = PKMAP_ADDR(last_pkmap_nr);    set_pte(&(pkmap_page_table[last_pkmap_nr]), mk_pte(page, kmap_prot));    //建立内核页表    pkmap_count[last_pkmap_nr] = 1;    set_page_address(page, (void *)vaddr);    return vaddr;}

enum km_type {    KM_BOUNCE_READ,    KM_SKB_SUNRPC_DATA,    KM_SKB_DATA_SOFTIRQ,    KM_USER0,    KM_USER1,    KM_BIO_SRC_IRQ,    KM_BIO_DST_IRQ,    KM_PTE0,    KM_PTE1,    KM_IRQ0,    KM_IRQ1,    KM_SOFTIRQ0,    KM_SOFTIRQ1,    KM_TYPE_NR};

void *kmap_atomic(struct page *page, enum km_type type){         enum fixed_addresses idx;    unsigned long vaddr;    /* even !CONFIG_PREEMPT needs this, for in_atomic in do_page_fault */    inc_preempt_count();                     //禁止内核抢占    if (page < highmem_start_page)        return page_address(page);     idx = type + KM_TYPE_NR*smp_processor_id();    vaddr = __fix_to_virt(FIX_KMAP_BEGIN + idx);   //获得线性地址     set_pte(kmap_pte-idx, mk_pte(page, kmap_prot));   //建立页表    __flush_tlb_one(vaddr);    return (void*) vaddr;}

struct vm_struct {    void *addr;              //内存区起始线性地址    unsigned long size;      //内存区的大小加4096（内存区之间安全区的大小）    unsigned long flags;        struct page **pages;     //页描述符指针数组    unsigend int nr_pages;   //指针数组长度（内存区页的个数）    unsigned long phys_addr;  //该字段为0    struct vm_struct  *next;   //指向下一个vm_struct}

void *vmalloc(unsigend long size): void *__vmalloc(unsigned long size, int gfp_mask, pgprot_t prot){     struct vm_struct *area;     struct page **pages;     unsigned int nr_pages, array_size, i;      size = PAGE_ALIGN(size);             //(((addr)+PAGE_SIZE-1)&PAGE_MASK)     if (!size || (size >> PAGE_SHIFT) > num_physpages)         return NULL;      area = get_vm_area(size, VM_ALLOC);       //在VMALLOC_START和 VMALLOC_END之间寻找大小为（szie+4096）的空闲连续地址空间     if (!area)         return NULL;      nr_pages = size >> PAGE_SHIFT;     array_size = (nr_pages * sizeof(struct page *));      area->nr_pages = nr_pages;     area->pages = pages = kmalloc(array_size, (gfp_mask & ~__GFP_HIGHMEM));          if (!area->pages) {         remove_vm_area(area->addr);         kfree(area);         return NULL;     }     memset(area->pages, 0, array_size);      for (i = 0; i < area->nr_pages; i++) {         area->pages[i] = alloc_page(gfp_mask);            //vmalloc基于伙伴系统，  每次从伙伴系统分配一页         if (unlikely(!area->pages[i])) {             /* Successfully allocated i pages, free them in __vunmap() */             area->nr_pages = i;             goto fail;         }    }            if (map_vm_area(area, prot, &pages))             //建立页表         goto fail;    return area->addr; fail:    vfree(area->addr);    return NULL;}