Linux伙伴系统

伙伴系统的概述

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>

1. struct zone {  
   
2.     …  
   
3.          …      
   
4.     struct free_area    free_area[MAX_ORDER];  
   
5.     …  
   
6.     …  
   
7. }  

<mmzone.h>

1. struct free_area {  
   
2.     struct list_head    free_list[MIGRATE_TYPES];  
   
3.     unsigned long       nr_free;  
   
4. };  

free_area共有MAX_ORDER个元素，其中第order个元素记录了2^order的空闲块，这些空闲块在free_list中以双向链表的形式组织起来，对于同等大小的空闲块，其类型不同，将组织在不同的free_list中，nr_free记录了该free_area中总共的空闲内存块的数量。MAX_ORDER的默认值为11，这意味着最大内存块的大小为2^10=1024个页框。对于同等大小的内存块，每个内存块的起始页框用于链表的节点进行相连，这些节点对应的着struct page中的lru域

1. struct page {  
   
2.       
   
3.     …  
   
4.     …  
   
5.     struct list_head lru;       /* Pageout list, eg. active_list 
   
6.                      * protected by zone->lru_lock ! 
   
7.                      */  
   
8.     …  
   
9. }  

连接示意图如下：

在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)：这类页不能直接移动，但可以删除，其内容页可以从其他地方重新生成，例如，映射自文件的数据属于这种类型，针对这种页，内核有专门的页面回收处理
  
• 
  可移动页:这类页可以随意移动，用户空间应用程序所用到的页属于该���别。它们通过页表来映射，如果他们复制到新的位置，页表项也会相应的更新，应用程序不会注意到任何改变。

   假如上图中大部分页都是可移动页，而分配出去的四个页都是不可移动页，由于不可移动页插在了其他类型页的中间，就导致了无法从原本空闲的连续内存区中分配较大的内存块。考虑下图的情况:

将可回收页和不可移动页分开，这样虽然在不可移动页的区域当中无法分配大块的连续内存，但是可回收页的区域却没有受其影响，可以分配大块的连续内存。

内核对于迁移类型的定义如下:

<mmzone.h>

1. #define MIGRATE_UNMOVABLE     0   
   
2. #define MIGRATE_RECLAIMABLE   1   
   
3. #define MIGRATE_MOVABLE       2   
   
4. #define MIGRATE_PCPTYPES      3 /* the number of types on the pcp lists */   
   
5. #define MIGRATE_RESERVE       3   
   
6. #define MIGRATE_ISOLATE       4 /* can’t allocate from here */   
   
7. #define MIGRATE_TYPES         5  

前三种类型已经介绍过

MIGRATE_PCPTYPES是per_cpu_pageset，即用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目

MIGRATE_RESERVE是在前三种的列表中都没用可满足分配的内存块时，就可以从MIGRATE_RESERVE分配

MIGRATE_ISOLATE用于跨越NUMA节点移动物理内存页，在大型系统上，它有益于将物理内存页移动到接近于是用该页最频繁地CPU

MIGRATE_TYPES表示迁移类型的数目

当一个指定的迁移类型所对应的链表中没有空闲块时，将会按以下定义的顺序到其他迁移类型的链表中寻找

1. static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {  
   
2.     [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
   
3.     [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
   
4.     [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },  
   
5.     [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */  
   
6. };  

在start_kernel()–>paging_init()–>zone_sizes_init()–>free_area_init_nodes()–>free_area_init_node()–>free_area_init_core()–>init_currently_empty_zone()–>zone_init_free_lists()中，free_area的相关域都被初始化

1. static void __meminit zone_init_free_lists(struct zone *zone)  


2. {  


3.     int order, t;  


4.     for_each_migratetype_order(order, t) {  


5.         /*链表初始化为空链表*/  


6.         INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);  


7.         /*内存块数量初始化为0*/  


8.         zone->free_area[order].nr_free = 0;  


9.     }  


10. }  

for_each_migratetype_order(order, t)就是两个嵌套的for循环

1. #define for_each_migratetype_order(order, type) \   


2.     for (order = 0; order < MAX_ORDER; order++) \  


3.         for (type = 0; type < MIGRATE_TYPES; type++)  

start_kernel()–>mm_init()–>mem_init()，负责统计所有可用的低端内存和高端内存，并释放到伙伴系统中

<Init_32.c>

1. void __init mem_init(void)  


2. {  


3.     int codesize, reservedpages, datasize, initsize;  


4.     int tmp;  


5.   


6.     pci_iommu_alloc();  


7.   


8. #ifdef CONFIG_FLATMEM   


9.     BUG_ON(!mem_map);  


10. #endif   


11.     /* this will put all low memory onto the freelists */  


12.      /*销毁bootmem分配器，释放bootmem分配器管理的空闲页框和bootmem的位图所占用的页框， 


13.          并计入totalram_pages*/  


14.     totalram_pages += free_all_bootmem();  


15.   


16.     reservedpages = 0;  


17.     for (tmp = 0; tmp < max_low_pfn; tmp++)  


18.         /* 


19.          * Only count reserved RAM pages: 


20.          */  


21.         if (page_is_ram(tmp) && PageReserved(pfn_to_page(tmp)))  


22.             reservedpages++;  


23.   


24.     /*处理高端内存页框*/  


25.     set_highmem_pages_init();  


26.   


27.     codesize =  (unsigned long) &_etext – (unsigned long) &_text;  


28.     datasize =  (unsigned long) &_edata – (unsigned long) &_etext;  


29.     initsize =  (unsigned long) &__init_end – (unsigned long) &__init_begin;  


30.   


31.     printk(KERN_INFO “Memory: %luk/%luk available (%dk kernel code, “  


32.             “%dk reserved, %dk data, %dk init, %ldk highmem)\n”,  


33.         nr_free_pages() << (PAGE_SHIFT-10),  


34.         num_physpages << (PAGE_SHIFT-10),  


35.         codesize >> 10,  


36.         reservedpages << (PAGE_SHIFT-10),  


37.         datasize >> 10,  


38.         initsize >> 10,  


39.         (unsigned long) (totalhigh_pages << (PAGE_SHIFT-10))  


40.            );  


41.   


42.     printk(KERN_INFO “virtual kernel memory layout:\n”  


43.         ”    fixmap  : 0x%08lx – 0x%08lx   (%4ld kB)\n”  


44. #ifdef CONFIG_HIGHMEM   


45.         ”    pkmap   : 0x%08lx – 0x%08lx   (%4ld kB)\n”  


46. #endif   


47.         ”    vmalloc : 0x%08lx – 0x%08lx   (%4ld MB)\n”  


48.         ”    lowmem  : 0x%08lx – 0x%08lx   (%4ld MB)\n”  


49.         ”      .init : 0x%08lx – 0x%08lx   (%4ld kB)\n”  


50.         ”      .data : 0x%08lx – 0x%08lx   (%4ld kB)\n”  


51.         ”      .text : 0x%08lx – 0x%08lx   (%4ld kB)\n”,  


52.         FIXADDR_START, FIXADDR_TOP,  


53.         (FIXADDR_TOP – FIXADDR_START) >> 10,  


54.   


55. #ifdef CONFIG_HIGHMEM   


56.         PKMAP_BASE, PKMAP_BASE+LAST_PKMAP*PAGE_SIZE,  


57.         (LAST_PKMAP*PAGE_SIZE) >> 10,  


58. #endif   


59.   


60.         VMALLOC_START, VMALLOC_END,  


61.         (VMALLOC_END – VMALLOC_START) >> 20,  


62.   


63.         (unsigned long)__va(0), (unsigned long)high_memory,  


64.         ((unsigned long)high_memory – (unsigned long)__va(0)) >> 20,  


65.   


66.         (unsigned long)&__init_begin, (unsigned long)&__init_end,  


67.         ((unsigned long)&__init_end –  


68.          (unsigned long)&__init_begin) >> 10,  


69.   


70.         (unsigned long)&_etext, (unsigned long)&_edata,  


71.         ((unsigned long)&_edata – (unsigned long)&_etext) >> 10,  


72.   


73.         (unsigned long)&_text, (unsigned long)&_etext,  


74.         ((unsigned long)&_etext – (unsigned long)&_text) >> 10);  


75.   


76.     /* 


77.      * Check boundaries twice: Some fundamental inconsistencies can 


78.      * be detected at build time already. 


79.      */  


80. #define __FIXADDR_TOP (-PAGE_SIZE)   


81. #ifdef CONFIG_HIGHMEM   


82.     BUILD_BUG_ON(PKMAP_BASE + LAST_PKMAP*PAGE_SIZE  > FIXADDR_START);  


83.     BUILD_BUG_ON(VMALLOC_END            > PKMAP_BASE);  


84. #endif   


85. #define high_memory (-128UL << 20)   


86.     BUILD_BUG_ON(VMALLOC_START          >= VMALLOC_END);  


87. #undef high_memory   


88. #undef __FIXADDR_TOP   


89.   


90. #ifdef CONFIG_HIGHMEM   


91.     BUG_ON(PKMAP_BASE + LAST_PKMAP*PAGE_SIZE    > FIXADDR_START);  


92.     BUG_ON(VMALLOC_END              > PKMAP_BASE);  


93. #endif   


94.     BUG_ON(VMALLOC_START                >= VMALLOC_END);  


95.     BUG_ON((unsigned long)high_memory       > VMALLOC_START);  


96.   


97.     if (boot_cpu_data.wp_works_ok < 0)  


98.         test_wp_bit();  


99.   


100.     save_pg_dir();  


101.     /*将前3GB线性地址(即用户地址空间)对应的pgd全局目录项清空*/  


102.     zap_low_mappings(true);  


103. }  

free_all_bootmem()的核心函数在<<bootmem allocator>>中已有介绍，这里不再列出

<Highmem_32.c>

1. void __init set_highmem_pages_init(void)  


2. {  


3.     struct zone *zone;  


4.     int nid;  


5.   


6.     for_each_zone(zone) {/*遍历每个管理区*/  


7.         unsigned long zone_start_pfn, zone_end_pfn;  


8.   


9.         if (!is_highmem(zone))/*判断是否是高端内存管理区*/  


10.             continue;  


11.   


12.         /*记录高端内存管理区的起始页框号和结束页框号*/  


13.         zone_start_pfn = zone->zone_start_pfn;  


14.         zone_end_pfn = zone_start_pfn + zone->spanned_pages;  


15.   


16.         nid = zone_to_nid(zone);  


17.         printk(KERN_INFO “Initializing %s for node %d (%08lx:%08lx)\n”,  


18.                 zone->name, nid, zone_start_pfn, zone_end_pfn);  


19.   


20.         /*将高端内存的页框添加到伙伴系统*/  


21.         add_highpages_with_active_regions(nid, zone_start_pfn,  


22.                  zone_end_pfn);  


23.     }  


24.     /*将释放到伙伴系统的高端内存页框数计入totalram_pages*/  


25.     totalram_pages += totalhigh_pages;  


26. }  

1. void __init add_highpages_with_active_regions(int nid, unsigned long start_pfn,  


2.                           unsigned long end_pfn)  


3. {  


4.     struct add_highpages_data data;  


5.   


6.     data.start_pfn = start_pfn;  


7.     data.end_pfn = end_pfn;  


8.   


9.     /*遍历所有的活动区，调用add_highpages_word_fn()来处理每个活动区*/  


10.     work_with_active_regions(nid, add_highpages_work_fn, &data);  


11. }  

1. void __init work_with_active_regions(int nid, work_fn_t work_fn, void *data)  


2. {  


3.     int i;  


4.     int ret;  


5.   


6.     for_each_active_range_index_in_nid(i, nid) {  


7.         ret = work_fn(early_node_map[i].start_pfn,  


8.                   early_node_map[i].end_pfn, data);  


9.         if (ret)  


10.             break;  


11.     }  


12. }

1. static int __init add_highpages_work_fn(unsigned long start_pfn,  


2.                      unsigned long end_pfn, void *datax)  


3. {  


4.     int node_pfn;  


5.     struct page *page;  


6.     unsigned long final_start_pfn, final_end_pfn;  


7.     struct add_highpages_data *data;  


8.   


9.     data = (struct add_highpages_data *)datax;  


10.   


11.     /*得到合理的起始结束页框号*/  


12.     final_start_pfn = max(start_pfn, data->start_pfn);  


13.     final_end_pfn = min(end_pfn, data->end_pfn);  


14.     if (final_start_pfn >= final_end_pfn)  


15.         return 0;  


16.   


17.     /*遍历活动区的页框*/  


18.     for (node_pfn = final_start_pfn; node_pfn < final_end_pfn;  


19.          node_pfn++) {  


20.         if (!pfn_valid(node_pfn))  


21.             continue;  


22.         page = pfn_to_page(node_pfn);  


23.         add_one_highpage_init(page, node_pfn);/*将该页框添加到伙伴系统*/  


24.     }  


25.   


26.     return 0;  


27.   


28. }   

1. static void __init add_one_highpage_init(struct page *page, int pfn)  


2. {  


3.     ClearPageReserved(page);  


4.     init_page_count(page);/*count初始化为1*/  


5.     __free_page(page);     /*释放page到伙伴系统*/  


6.     totalhigh_pages++;      /*高端内存的页数加1*/  


7. }  

__free_page()中涉及到的具体操作在后面介绍伙伴系统释放页面时再做分析

在free_area_init_core()–>memmap_init()(–>memmap_init_zone() )–>set_pageblock_migratetype(),将每个pageblock的起始页框对应的struct zone当中的pageblock_flags代表的位图相关区域标记为可移动的，表示该pageblock为可移动的，也就是说内核初始化伙伴系统时，所有的页都被标记为可移动的

1. void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,  


2.         unsigned long start_pfn, enum memmap_context context)  


3. {  


4.     struct page *page;  


5.     unsigned long end_pfn = start_pfn + size;  


6.     unsigned long pfn;  


7.     struct zone *z;  


8.   


9.     if (highest_memmap_pfn < end_pfn – 1)  


10.         highest_memmap_pfn = end_pfn – 1;  


11.   


12.     z = &NODE_DATA(nid)->node_zones[zone];  


13.     for (pfn = start_pfn; pfn < end_pfn; pfn++) {  


14.         /* 


15.          * There can be holes in boot-time mem_map[]s 


16.          * handed to this function.  They do not 


17.          * exist on hotplugged memory. 


18.          */  


19.         if (context == MEMMAP_EARLY) {  


20.             if (!early_pfn_valid(pfn))  


21.                 continue;  


22.             if (!early_pfn_in_nid(pfn, nid))  


23.                 continue;  


24.         }  


25.         page = pfn_to_page(pfn);  


26.         set_page_links(page, zone, nid, pfn);  


27.         mminit_verify_page_links(page, zone, nid, pfn);  


28.         init_page_count(page);  


29.         reset_page_mapcount(page);  


30.         SetPageReserved(page);  


31.         /* 


32.          * Mark the block movable so that blocks are reserved for 


33.          * movable at startup. This will force kernel allocations 


34.          * to reserve their blocks rather than leaking throughout 


35.          * the address space during boot when many long-lived 


36.          * kernel allocations are made. Later some blocks near 


37.          * the start are marked MIGRATE_RESERVE by 


38.          * setup_zone_migrate_reserve() 


39.          * 


40.          * bitmap is created for zone’s valid pfn range. but memmap 


41.          * can be created for invalid pages (for alignment) 


42.          * check here not to call set_pageblock_migratetype() against 


43.          * pfn out of zone. 


44.          */  


45.          /*如果pfn处在合理的范围，并且该pfn是一个pageblock的起始页框号*/  


46.         if ((z->zone_start_pfn <= pfn)  


47.             && (pfn < z->zone_start_pfn + z->spanned_pages)  


48.             && !(pfn & (pageblock_nr_pages – 1)))  


49.             set_pageblock_migratetype(page, MIGRATE_MOVABLE);/*将页框对应的位图域标记为可移动的*/  


50.   


51.         INIT_LIST_HEAD(&page->lru);  


52. #ifdef WANT_PAGE_VIRTUAL   


53.         /* The shift won’t overflow because ZONE_NORMAL is below 4G. */  


54.         if (!is_highmem_idx(zone))  


55.             set_page_address(page, __va(pfn << PAGE_SHIFT));  


56. #endif   


57.     }  


58. } 

1. static void set_pageblock_migratetype(struct page *page, int migratetype)  


2. {  


3.   


4.     /*如果没有开启移动性分类，则所有页都要标记为不可移动的*/  


5.     if (unlikely(page_group_by_mobility_disabled))  


6.         migratetype = MIGRATE_UNMOVABLE;  


7.       


8.     set_pageblock_flags_group(page, (unsigned long)migratetype,  


9.                     PB_migrate, PB_migrate_end);  


10. }  

1. void set_pageblock_flags_group(struct page *page, unsigned long flags,  


2.                     int start_bitidx, int end_bitidx)  


3. {  


4.     struct zone *zone;  


5.     unsigned long *bitmap;  


6.     unsigned long pfn, bitidx;  


7.     unsigned long value = 1;  


8.   


9.     zone = page_zone(page);  


10.     pfn = page_to_pfn(page);  


11.     /*得到位图的起始地址，即zone->pageblock_flags*/  


12.     bitmap = get_pageblock_bitmap(zone, pfn);  


13.     /*得到pfn对应的位图区域的偏移量*/  


14.     bitidx = pfn_to_bitidx(zone, pfn);  


15.     VM_BUG_ON(pfn < zone->zone_start_pfn);  


16.     VM_BUG_ON(pfn >= zone->zone_start_pfn + zone->spanned_pages);  


17.   


18.     /*每个页都需要3个bit来表征其移动性，也就是从start_bitidx到end_bitidx共3位*/  


19.     for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)  


20.         if (flags & value)/*通过flags和value相与确定相关的位是否为1*/  


21.             __set_bit(bitidx + start_bitidx, bitmap);  


22.         else  


23.             __clear_bit(bitidx + start_bitidx, bitmap);  


24. }  

前面已经介绍了伙伴系统的原理和Linux伙伴系统的数据结构，现在来看伙伴系统是如何来分配页面的。实际上，伙伴系统分配页面的算法并不复杂，但是由于考虑到分配内存时要尽量减少碎片的产生(涉及迁移机制)以及当内存不足时需要采取各种更为积极的手段，使得内核分配页面的相关函数完整地分析起来比较复杂庞大。在这里，我们只关注分配时最一般的情况，而其他情况的处理在以后单独拿出来讨论。

我们从__alloc_pages_nodemask()这个函数开始分析，所有的分配页面的函数最终都会落到这个函数上面，它是伙伴系统的入口。

1. struct page *  
   
2. __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,  
   
3.             struct zonelist *zonelist, nodemask_t *nodemask)  
   
4. {  
   
5.     /*根据gfp_mask确定分配页所处的管理区*/  
   
6.     enum zone_type high_zoneidx = gfp_zone(gfp_mask);  
   
7.     struct zone *preferred_zone;  
   
8.     struct page *page;  
   
9.     /*根据gfp_mask得到迁移类分配页的型*/  
   
10.     int migratetype = allocflags_to_migratetype(gfp_mask);  
    
11.   
    
12.     gfp_mask &= gfp_allowed_mask;  
    
13.   
    
14.     lockdep_trace_alloc(gfp_mask);  
    
15.   
    
16.     might_sleep_if(gfp_mask & __GFP_WAIT);  
    
17.   
    
18.     if (should_fail_alloc_page(gfp_mask, order))  
    
19.         return NULL;  
    
20.   
    
21.     /* 
    
22.      * Check the zones suitable for the gfp_mask contain at least one 
    
23.      * valid zone. It’s possible to have an empty zonelist as a result 
    
24.      * of GFP_THISNODE and a memoryless node 
    
25.      */  
    
26.     if (unlikely(!zonelist->_zonerefs->zone))  
    
27.         return NULL;  
    
28.   
    
29.     /* The preferred zone is used for statistics later */  
    
30.     /*从zonelist中找到zone_idx与high_zoneidx相同的管理区，也就是之前认定的管理区*/  
    
31.     first_zones_zonelist(zonelist, high_zoneidx, nodemask, &preferred_zone);  
    
32.     if (!preferred_zone)  
    
33.         return NULL;  
    
34.   
    
35.     /* First allocation attempt */  
    
36.     page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,  
    
37.             zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,  
    
38.             preferred_zone, migratetype);  
    
39.     if (unlikely(!page))  
    
40.         /*第一次分配失败的话则会用通过一条低速路径来进行第二次分配，包括唤醒页换出守护进程等等*/  
    
41.         page = __alloc_pages_slowpath(gfp_mask, order,  
    
42.                 zonelist, high_zoneidx, nodemask,  
    
43.                 preferred_zone, migratetype);  
    
44.   
    
45.     trace_mm_page_alloc(page, order, gfp_mask, migratetype);  
    
46.     return page;  
    
47. }  

• 首先要做的就是找到指定的分配管理区，管理区的编号保存在high_zoneidx中
  
• 然后就是尝试第一次分配，流程是从指定的管理区开始扫描管理区–>找到充足的管理区–>从指定的迁移类型链表中分配内存–>如果在指定迁移类型中找不到则到其他的迁移类型中去寻找
  
• 如果第二步在各个区域都找不到可以满足分配的内存了，那么说明管理区的内存已经确实不够了，于是开始启用一条慢速的途径来分配，包括尝试去换出一些不经常使用的页等等，内核会在这次分配中表现得更为积极，其中的细节涉及到了其他一些复杂的东西，以后再做分析

1. static struct page *  
   
2. get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,  
   
3.         struct zonelist *zonelist, int high_zoneidx, int alloc_flags,  
   
4.         struct zone *preferred_zone, int migratetype)  
   
5. {  
   
6.     struct zoneref *z;  
   
7.     struct page *page = NULL;  
   
8.     int classzone_idx;  
   
9.     struct zone *zone;  
   
10.     nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */  
    
11.     int zlc_active = 0;     /* set if using zonelist_cache */  
    
12.     int did_zlc_setup = 0;      /* just call zlc_setup() one time */  
    
13.   
    
14.     /*获取管理区的编号*/  
    
15.     classzone_idx = zone_idx(preferred_zone);  
    
16. zonelist_scan:  
    
17.     /* 
    
18.      * Scan zonelist, looking for a zone with enough free. 
    
19.      * See also cpuset_zone_allowed() comment in kernel/cpuset.c. 
    
20.      */  
    
21.     /*从认定的管理区开始遍历，直到找到一个拥有足够空间的管理区， 
    
22.       例如，如果high_zoneidx对应的ZONE_HIGHMEM，则遍历顺序为HIGHMEM–>NORMAL–>DMA， 
    
23.       如果high_zoneidx对应ZONE_NORMAL，则遍历顺序为NORMAL–>DMA*/  
    
24.     for_each_zone_zonelist_nodemask(zone, z, zonelist,  
    
25.                         high_zoneidx, nodemask) {  
    
26.         if (NUMA_BUILD && zlc_active &&  
    
27.             !zlc_zone_worth_trying(zonelist, z, allowednodes))  
    
28.                 continue;  
    
29.   
    
30.         /*检查给定的内存域是否属于该进程允许运行的CPU*/  
    
31.         if ((alloc_flags & ALLOC_CPUSET) &&  
    
32.             !cpuset_zone_allowed_softwall(zone, gfp_mask))  
    
33.                 goto try_next_zone;  
    
34.   
    
35.         BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);  
    
36.         if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {  
    
37.             unsigned long mark;  
    
38.             int ret;  
    
39.               
    
40.             /*通过alloc_flags来确定是使用何种水印，pages_min?pages_low?pages_high? 
    
41.               选择了一种水印，就要求分配后的空闲不低于该水印才能进行分配*/  
    
42.             mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];  
    
43.   
    
44.             /*如果管理区的水位线处于正常水平，则在该管理区进行分配*/  
    
45.             if (zone_watermark_ok(zone, order, mark,  
    
46.                     classzone_idx, alloc_flags))  
    
47.                 goto try_this_zone;  
    
48.   
    
49.             if (zone_reclaim_mode == 0)  
    
50.                 goto this_zone_full;  
    
51.   
    
52.             /*下面这部分都是针对NUMA架构的申请页面回收*/  
    
53.             ret = zone_reclaim(zone, gfp_mask, order);  
    
54.             switch (ret) {  
    
55.             case ZONE_RECLAIM_NOSCAN:/*没有进行回收*/  
    
56.                 /* did not scan */  
    
57.                 goto try_next_zone;  
    
58.             case ZONE_RECLAIM_FULL:  /*没有找到可回收的页面*/  
    
59.                 /* scanned but unreclaimable */  
    
60.                 goto this_zone_full;  
    
61.             default:  
    
62.                 /* did we reclaim enough */  
    
63.                 if (!zone_watermark_ok(zone, order, mark,  
    
64.                         classzone_idx, alloc_flags))  
    
65.                     goto this_zone_full;  
    
66.             }  
    
67.         }  
    
68.   
    
69. try_this_zone:/*分配2^order个页*/  
    
70.         page = buffered_rmqueue(preferred_zone, zone, order,  
    
71.                         gfp_mask, migratetype);  
    
72.         if (page)  
    
73.             break;  
    
74. this_zone_full:  
    
75.         if (NUMA_BUILD)  
    
76.             zlc_mark_zone_full(zonelist, z);  
    
77. try_next_zone:  
    
78.         if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {  
    
79.             /* 
    
80.              * we do zlc_setup after the first zone is tried but only 
    
81.              * if there are multiple nodes make it worthwhile 
    
82.              */  
    
83.             allowednodes = zlc_setup(zonelist, alloc_flags);  
    
84.             zlc_active = 1;  
    
85.             did_zlc_setup = 1;  
    
86.         }  
    
87.     }  
    
88.   
    
89.     if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {  
    
90.         /* Disable zlc cache for second zonelist scan */  
    
91.         zlc_active = 0;  
    
92.         goto zonelist_scan;  
    
93.     }  
    
94.     return page;  
    
95. }  

• 从指定的管理区开始按照zonelist中定义的顺序来遍历管理区
  
• 如果该管理区的水位线正常，则调用buffered_rmqueue()在该管理区中分配
  
• 如果管理区的水位线过低，则在NUMA架构下会申请页面回收

1. static inline  
   
2. struct page *buffered_rmqueue(struct zone *preferred_zone,  
   
3.             struct zone *zone, int order, gfp_t gfp_flags,  
   
4.             int migratetype)  
   
5. {  
   
6.     unsigned long flags;  
   
7.     struct page *page;  
   
8.     int cold = !!(gfp_flags & __GFP_COLD);  
   
9.     int cpu;  
   
10.   
    
11. again:  
    
12.     cpu  = get_cpu();  
    
13.     if (likely(order == 0)) {/*order为0，即要求分配一个页*/  
    
14.         struct per_cpu_pages *pcp;  
    
15.         struct list_head *list;  
    
16.   
    
17.         pcp = &zone_pcp(zone, cpu)->pcp;/*获取本地CPU对应的pcp*/  
    
18.         list = &pcp->lists[migratetype];/*获取和迁移类型对应的链表*/  
    
19.         local_irq_save(flags);  
    
20.   
    
21.         /*如果链表为空，则表示没有可分配的页，需要从伙伴系统中分配2^batch个页给list*/  
    
22.         if (list_empty(list)) {  
    
23.             pcp->count += rmqueue_bulk(zone, 0,  
    
24.                     pcp->batch, list,  
    
25.                     migratetype, cold);  
    
26.             if (unlikely(list_empty(list)))  
    
27.                 goto failed;  
    
28.         }  
    
29.   
    
30.         if (cold)/*如果是需要冷页，则从链表的尾部获取*/  
    
31.             page = list_entry(list->prev, struct page, lru);  
    
32.         else     /*如果是需要热页，则从链表的头部获取*/  
    
33.             page = list_entry(list->next, struct page, lru);  
    
34.           
    
35.         list_del(&page->lru);  
    
36.         pcp->count–;  
    
37.     } else {  
    
38.         if (unlikely(gfp_flags & __GFP_NOFAIL)) {  
    
39.             /* 
    
40.              * __GFP_NOFAIL is not to be used in new code. 
    
41.              * 
    
42.              * All __GFP_NOFAIL callers should be fixed so that they 
    
43.              * properly detect and handle allocation failures. 
    
44.              * 
    
45.              * We most definitely don’t want callers attempting to 
    
46.              * allocate greater than order-1 page units with 
    
47.              * __GFP_NOFAIL. 
    
48.              */  
    
49.             WARN_ON_ONCE(order > 1);  
    
50.         }  
    
51.         spin_lock_irqsave(&zone->lock, flags);  
    
52.         /*从管理区的伙伴系统中选择合适的内存块进行分配*/  
    
53.         page = __rmqueue(zone, order, migratetype);  
    
54.         spin_unlock(&zone->lock);  
    
55.         if (!page)  
    
56.             goto failed;  
    
57.         __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));  
    
58.     }  
    
59.   
    
60.     __count_zone_vm_events(PGALLOC, zone, 1 << order);  
    
61.     zone_statistics(preferred_zone, zone);  
    
62.     local_irq_restore(flags);  
    
63.     put_cpu();  
    
64.   
    
65.     VM_BUG_ON(bad_range(zone, page));  
    
66.     if (prep_new_page(page, order, gfp_flags))  
    
67.         goto again;  
    
68.     return page;  
    
69.   
    
70. failed:  
    
71.     local_irq_restore(flags);  
    
72.     put_cpu();  
    
73.     return NULL;  
    
74. }  

• 该函数分两种情况进行处理，一种是只要求分配单个页框，另一种是要求分配多个连续页框
  
• 对于单个页面，内核选择从每CPU页框高速缓存中分配，它的核心描述结构也是MIGRATE_TYPES个链表，只不过链表中的元素都是单个页。这些页分为热页和冷页，所谓热页就是还处在CPU高速缓存中的页，相反，冷页就是不存在于高速缓存中的页。对于单个页框的申请，分配热页可以提高效率。需要注意的是，越靠近链表头的页越热，越靠近链表尾的页越冷，因为每次释放单个页框的时候，页框是插入到链表的头部的，也就是说靠近头部的页框是最近才释放的，因此最有可能存在于高速缓存当中
  
• 对于连续的页框分配，通过调用__rmqueue()来完成分配

1. static struct page *__rmqueue(struct zone *zone, unsigned int order,  
   
2.                         int migratetype)  
   
3. {  
   
4.     struct page *page;  
   
5.   
   
6. retry_reserve:  
   
7.       
   
8.     page = __rmqueue_smallest(zone, order, migratetype);  
   
9.   
   
10.     /*如果分配失败并且迁移类型不是MIGRATE_RESERVE(如果是MIGRATE_RESERVE， 
    
11.       则表明已经没有其他的迁移类型可供选择了)*/  
    
12.     if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {  
    
13.         page = __rmqueue_fallback(zone, order, migratetype);  
    
14.   
    
15.         /* 
    
16.          * Use MIGRATE_RESERVE rather than fail an allocation. goto 
    
17.          * is used because __rmqueue_smallest is an inline function 
    
18.          * and we want just one call site 
    
19.          */  
    
20.         if (!page) {  
    
21.             migratetype = MIGRATE_RESERVE;  
    
22.             goto retry_reserve;  
    
23.         }  
    
24.     }  
    
25.   
    
26.     trace_mm_page_alloc_zone_locked(page, order, migratetype);  
    
27.     return page;  
    
28. }  
    
29. </span>  

• 首先按照指定的迁移类型，调用__rmqueue_smallest()来分配对应的内存块,该函数是伙伴系统的算法体现
  
• 如果分配失败，则说明指定的迁移类型中没有充足的内存来满足分配，这时就要按fallbacks中定义的顺序从其他的迁移链表中寻找了，__rmqueue_fallback()函数较为复杂，体现了利用迁移类型来避免碎片的思想，后面单独拿出来分析

1. static inline  
   
2. struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,  
   
3.                         int migratetype)  
   
4. {  
   
5.     unsigned int current_order;  
   
6.     struct free_area * area;  
   
7.     struct page *page;  
   
8.   
   
9.     /* Find a page of the appropriate size in the preferred list */  
   
10.     for (current_order = order; current_order < MAX_ORDER; ++current_order) {  
    
11.   
    
12.         /*获取和现在的阶数对应的free_area*/  
    
13.         area = &(zone->free_area[current_order]);  
    
14.   
    
15.         /*和迁移类型对应的free_list为空则不执行下面的内容*/  
    
16.         if (list_empty(&area->free_list[migratetype]))  
    
17.             continue;  
    
18.           
    
19.         /*得到满足要求的页块中的第一个页描述符*/  
    
20.         page = list_entry(area->free_list[migratetype].next,  
    
21.                             struct page, lru);  
    
22.         list_del(&page->lru);  
    
23.         rmv_page_order(page);/*将page的private域设为0*/  
    
24.         area->nr_free–;         /*内存块数减1*/  
    
25.           
    
26.         /*进行拆分(在current_order>order的情况下)*/  
    
27.         expand(zone, page, order, current_order, area, migratetype);  
    
28.         return page;  
    
29.     }  
    
30.   
    
31.     return NULL;  
    
32. }  

1. static inline void expand(struct zone *zone, struct page *page,  
   
2.     int low, int high, struct free_area *area,  
   
3.     int migratetype)  
   
4. {  
   
5.     unsigned long size = 1 << high;/*order为high的页块对应的页框数*/  
   
6.   
   
7.     /*申请的order为low,实际分配的块对应的order为high 
   
8.       如果high大于low则要将大块进行拆分，并且将拆分后的伙伴块添加到下一级order的块链表中去*/  
   
9.     while (high > low) {  
   
10.         area–;/*area减1得到下一级order对应的area*/  
    
11.         high–;/*high减1表明进行了一次拆分*/  
    
12.         size >>= 1;/*拆分一次size就要除以2*/  
    
13.         VM_BUG_ON(bad_range(zone, &page[size]));  
    
14.   
    
15.         /*通过size来定位拆分后的伙伴块的起始页框描述符， 
    
16.         并将其作为第一个块添加到下一级order的块链表中*/  
    
17.         list_add(&page[size].lru, &area->free_list[migratetype]);  
    
18.         area->nr_free++;/*该order区域的块数加1*/  
    
19.         set_page_order(&page[size], high);/*设定private域为high*/  
    
20.     }  
    
21. }  
    
22.   
    
23.    

只需要注意一点，一个块的定位可以由块首的起始页对应的描述符和order(size)来定位，因此只需要将一个块的第一个页描述符链入相应的链表就可以了。

      可以看到，落脚点是__free_pages()这个函数，它执行的工作的流程图如下图所示

下面是该函数的具体代码

1. void __free_pages(struct page *page, unsigned int order)  
   
2. {  
   
3.     if (put_page_testzero(page)) {/*判断页没有被使用*/  
   
4.         trace_mm_page_free_direct(page, order);  
   
5.         if (order == 0)/*单页则释放到每CPU页框高速缓存中*/  
   
6.             free_hot_page(page);  
   
7.         else           /*多页则释放到伙伴系统*/  
   
8.             __free_pages_ok(page, order);  
   
9.     }  
   
10. }  

从2.6.32.25开始，linux在伙伴管理系统中引入迁移类型(migrate type)这么一个概念，用于避免系统在长期运行过程中产生碎片。关于迁移类型的一些概念在介绍伙伴系统的数据结构的时候有提到过(见<<Linux伙伴系统(一)>>)，不过考虑到它较为复杂，因此在解析分配页的过程中没有介绍迁移类型是如何工作的，在这里将这部分拿出来单独作为一个部分进行分析。

在分析具体的代码前，再来说一下为什么要引入迁移类型。我们都知道伙伴系统是针对于解决外碎片的问题而提出的，那么为什么还要引入这样一个概念来避免碎片呢？我们注意到，碎片一般是指散布在内存中的小块内存，由于它们已经被分配并且插入在大块内存中，而导致无法分配大块的连续内存。而伙伴系统把内存分配出去后，要再回收回来并且重新组成大块内存，这样一个过程必须建立两个伙伴块必须都是空闲的这样一个基础之上，如果其中有一个伙伴不是空闲的，甚至是其中的一个页不是空闲的，都会导致无法分配一块连续的大块内存。我们再引用之前上过的一个例子来看这个问题:

图中，如果15对应的页是空闲的，那么伙伴系统可以分配出连续的16个页框，而由于15这一个页框被分配出去了，导致最多只能分配出8个连续的页框。假如这个页还会被回收回伙伴系统，那么至少在这段时间内产生了碎片，而如果更糟的，如果这个页用来存储一些内核永久性的数据而不会被回收回来，那么碎片将永远无法消除，这意味着15这个页所处的最大内存块永远无法被连续的分配出去了。假如上图中被分配出去的页都是不可移动的页，那么就可以拿出一段内存，专门用于分配不可移动页，虽然在这段内存中有碎片，但是避免了碎片散布到其他类型的内存中。在系统中所有的内存都被标识为可移动的！也就是说一开始其他类型都没有属于自己的内存，而当要分配这些类型的内存时，就要从可移动类型的内存中夺取一部分过来，这样可以根据实际情况来分配其他类型的内存。现在我们就来看看伙伴系统分配页时，当指定的迁移类型的内存不足时，系统是如何做的

1. /* Remove an element from the buddy allocator from the fallback list */  


2. static inline struct page *  


3. __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)  


4. {  


5.     struct free_area * area;  


6.     int current_order;  


7.     struct page *page;  


8.     int migratetype, i;  


9.   


10.     /* Find the largest possible block of pages in the other list */  


11.     /*从最大的内存块链表开始遍历阶数,内核倾向于尽量找到大的内存块来满足分配*/  


12.     for (current_order = MAX_ORDER-1; current_order >= order;  


13.                         –current_order) {   


14.         for (i = 0; i < MIGRATE_TYPES – 1; i++) {/*根据fallbacks中定义的顺序遍历后面的迁移类型*/  


15.             migratetype = fallbacks[start_migratetype][i];  


16.   


17.             /* MIGRATE_RESERVE handled later if necessary */  


18.             if (migratetype == MIGRATE_RESERVE)  


19.                 continue;  


20.   


21.             area = &(zone->free_area[current_order]);  


22.             if (list_empty(&area->free_list[migratetype]))  


23.                 continue;  


24.   


25.             /*取块首的页*/  


26.             page = list_entry(area->free_list[migratetype].next,  


27.                     struct page, lru);  


28.             area->nr_free–;  


29.   


30.             /* 


31.              * If breaking a large block of pages, move all free 


32.              * pages to the preferred allocation list. If falling 


33.              * back for a reclaimable kernel allocation, be more 


34.              * agressive about taking ownership of free pages 


35.              */  


36.              /*pageblock_order定义着内核认为的大块内存究竟是多大*/  


37.              /*如果    1.当前得到的块是一个比较大的块，即阶数大于pageblock_order/2=5 


38.                   或者 2.之前指定的迁移类型为可回收页 


39.                   或者 3.没有启用迁移分组机制*/  


40.             if (unlikely(current_order >= (pageblock_order >> 1)) ||  


41.                     start_migratetype == MIGRATE_RECLAIMABLE ||  


42.                     page_group_by_mobility_disabled) {  


43.                 unsigned long pages;  


44.                   


45.                 /*试图将当前页所处的最大内存块移到之前指定的迁移类型对应的链表中， 


46.                 只有空闲页才会移动，所以真正可移动的页数pages可能小于2^pageblock_order*/  


47.                 pages = move_freepages_block(zone, page,  


48.                                 start_migratetype);  


49.   


50.                 /* Claim the whole block if over half of it is free */  


51.                 /*移动的页面数大于大内存块的一半，则修改整个块的迁移类型*/  


52.                 if (pages >= (1 << (pageblock_order-1)) ||  


53.                         page_group_by_mobility_disabled)  


54.                     set_pageblock_migratetype(page,  


55.                                 start_migratetype);  


56.   


57.                 migratetype = start_migratetype;  


58.             }  


59.   


60.             /* Remove the page from the freelists */  


61.             list_del(&page->lru);  


62.             rmv_page_order(page);  


63.   


64.             /* Take ownership for orders >= pageblock_order */  


65.             /*如果current_order大于等于10，则将超出的部分的迁移类型设为start_migratetype*/  


66.             if (current_order >= pageblock_order)  


67.                 change_pageblock_range(page, current_order,  


68.                             start_migratetype);  


69.             /*拆分，这里注意的是如果之前改变了migratetype,则会将拆分的伙伴块添加到新的迁移类型链表中*/  


70.             expand(zone, page, order, current_order, area, migratetype);  


71.   


72.             trace_mm_page_alloc_extfrag(page, order, current_order,  


73.                 start_migratetype, migratetype);  


74.   


75.             return page;  


76.         }  


77.     }  


78.   


79.     return NULL;  


80. }  

首先我们看到的不寻常的一点就是，for循环优先遍历大的内存块，也就是说优先分配大内存块，这似乎和伙伴系统优先分配小内存块的原则相违背，但是仔细想想这样做其实就是为了避免在新的迁移类型中引入碎片。如何说？现在假如A类型内存不足，向B类型求援，假设只从B中分配一块最适合的小块，OK，那么过会儿又请求分配A类型内存，又得向B类型求援，这样来来回回从B类型中一点一点的分配内存将会导致B类型的内存四处都散布碎片，如果这些内存一直得不到释放……内核已经不敢想象了……B类型可能会因为A类型而引入的碎片导致其再也分配不出大的内存块了。出于这种原因，内核选择直接分配一块最大的内存块给A，你们爱怎么打怎么闹随便你们，反正都是在A类型中进行，只要不拖累我B类型就可以了

当请求分配的内存比较大时或者最初的请求类型为可回收类型时，会表现得更加积极，也就是我前面所说的将对应的最大内存块搬到最初的请求类型对应的链表中。我的理解是，这里判断一个比较大的内存类型的条件是用来和前面优先遍历大内存块的for循环相呼应的，也就是说假如得到的内存块是一个比较小的内存块，那就说明该内存类型自己也没有大块可分配的连续内存了，因此就不执行搬迁工作。而对于可回收类型的内存要执行搬迁是因为在一些时候，内核可能会非常频繁地申请小块可回收类型的内存。

当搬迁的内存的大于大块内存的一半时，将彻底将这块内存化为己有，也就是说将这片大块内存区对应的页类型标识位图区域标识成最初申请的内存类型。

用<<深入Linux内核架构>>上的一段话作为总结，“实际上，在启动期间分配可移动内存区的情况较少，那么分配器有很高的几率分配长度最大的内存区，并将其从可移动列表转换到不可移动列表。由于分配的内存区长度是最大的，因此不会向可移动内存中引入碎片。总而言之，这种做法避免了启动期间内核分配的内存(经常在系统的整个运行时间都不释放)散布到物理内存各处，从而使其他类型的内存分配免受碎片的干扰，这也是页可移动性分组框架的最重要目标之一”