Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1624975
  • 博文数量: 511
  • 博客积分: 967
  • 博客等级: 准尉
  • 技术积分: 2560
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-06 14:19
文章分类

全部博文(511)

文章存档

2016年(11)

2015年(61)

2014年(257)

2013年(63)

2012年(119)

分类: Android平台

2014-01-24 11:11:32

基本概念:

         关于伙伴系统算法的原理还是比较好理解的,这里不作复数。直接看下关键数据结构。


[html] view plaincopy
  1. struct zone {  
  2. ~~snip  
  3.          struct free_area   free_area[MAX_ORDER];        //每一阶以一个元素保存,平台最大11阶。  
  4. ~~snip  
  5. };  
可以看到每个zone都有它自己的free_area,效果如下图:


相关信息可以从/proc/buddyinfo读取到,各个值含义依次为节点号, zone类型,后面的值表示从0阶开始各个阶空闲的页数:


[html] view plaincopy
  1. #cat/proc/buddyinfo  
  2. Node0, zone   Normal     70    27  
  3.      33   148     47     13     7      2  
  4.   2     1      1  
  5. Node0, zone  HighMem      0     1      1      2     2      0      0     0  
  6.   0     0      0  


[html] view plaincopy
  1. struct free_area {  
  2.     /*同样阶数保存到一个链表上 */  
  3.     struct list_head    free_list[MIGRATE_TYPES];  
  4.     /*当前空闲页块的数目。*/  
  5.     unsigned long       nr_free;  
  6. };  

效果如下图:


MIGRATE_TYPES是作为反碎片的一种机制,专有名叫迁移类型。大概的原理就是将伙伴系统的内存页分为几种类型,有可移动,不可移动,可回收等,同一类型的页放在一个区域,如不可回收的页不能放在可移动类型区域,这样对可以移动区域,伙伴系统就可以回收了。

[html] view plaincopy
  1. enum {  
  2.     MIGRATE_UNMOVABLE,  
  3.     MIGRATE_RECLAIMABLE,  
  4.     MIGRATE_MOVABLE,  
  5.     MIGRATE_PCPTYPES,   /* the number of types on the pcp lists */  
  6.     MIGRATE_RESERVE = MIGRATE_PCPTYPES,  
  7. #ifdef CONFIG_CMA  
  8.     MIGRATE_CMA,  
  9. #endif  
  10.     MIGRATE_ISOLATE,    /* can't allocate from here */  
  11.     MIGRATE_TYPES  
  12. };  

MIGRATE_UNMOVABLE:不可移动页,在内存中有固定位置,不能移动。核心内核分配的大部分内存属于此类。

MIGRATE_RECLAIMABLE:可回收页,不能移动,但能删除。Kswapd内核线程会操作次区域。

MIGRATE_MOVABLE:可移动又可回收页,用户空间程序使用此类,通过页表映射实现,如果应用程序虚拟地址空间有变化,只要变化页表就可以了。

MIGRATE_RESERVE: 当系统内存相当少而且比较紧急时,才用到此区域。

MIGRATE_CMA:这个是为了避免预留大块内存实现的,当需要大块内存的时候如audio/camera等,它可以被使用;当小内存申请需要时,它也可以被使用,避免了pmem/ion的弊端,不过似乎要基于DMA。后面打算用一篇文章来分析cma.

MIGRATE_ISOLATE: NUMA系统上使用,我们用UMA,不管它。

当某个迁移类型的内存不足时,会向另外一个迁移类型去要内存。这个跟zone的申请机制很像!下面结构规定了当前迁移类型不够时下一个使用的类型,如MIGRATE_UNMOVABLE的使用顺序是: MIGRATE_RECLAIMABLE  -> MIGRATE_RECLAIMABLE -> MIGRATE_MOVABLE -> MIGRATE_RESERVE.


[html] view plaincopy
  1. static int fallbacks[MIGRATE_TYPES][4] = {  
  2.     [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,     MIGRATE_RESERVE },  
  3.     [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,     MIGRATE_RESERVE },  
  4. #ifdef CONFIG_CMA  
  5.     [MIGRATE_MOVABLE]     = { MIGRATE_CMA,         MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },  
  6.     [MIGRATE_CMA]         = { MIGRATE_RESERVE }, /* Never used */  
  7. #else  
  8.     [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE,   MIGRATE_RESERVE },  
  9. #endif  
  10.     [MIGRATE_RESERVE]     = { MIGRATE_RESERVE }, /* Never used */  
  11.     [MIGRATE_ISOLATE]     = { MIGRATE_RESERVE }, /* Never used */  
  12. };  



迁移类型的信息可以从/proc/pagetypeinfo读到: 

[html] view plaincopy
  1. #cat /proc/pagetypeinfo  
  2. Page block order: 10  
  3. Pages per block:  1024  
  4.   
  5. Free pages count per migrate type at order       0      1      2      3      4  
  6.     5      6      7      8      9     10  
  7. Node    0, zone   Normal, type    Unmovable      1      1      2      0      1  
  8.     0      1      1      1      0      0  
  9. Node    0, zone   Normal, type    Reclaimable      8     18      3      0      0  
  10.     0      0      0      0      0      0  
  11. Node    0, zone   Normal, type      Movable      1      1      0    115     46  
  12.    12      5      0      0      0      0  
  13. Node    0, zone   Normal, type      Reserve      0      0      0      1      0  
  14.     1      1      1      1      1      1  
  15. Node    0, zone   Normal, type      Isolate      0      0      0      0      0  
  16.     0      0      0      0      0      0  
  17. Node    0, zone  HighMem, type    Unmovable      0      0      0      0      0  
  18.     0      0      0      0      0      0  
  19. Node    0, zone  HighMem, type  Reclaimable      0      0      0      0      0  
  20.     0      0      0      0      0      0  
  21. Node    0, zone  HighMem, type      Movable      0      1      0      0      0  
  22.     0      0      0      0      0      0  
  23. Node    0, zone  HighMem, type      Reserve      0      0      1      2      2  
  24.     0      0      0      0      0      0  
  25. Node    0, zone  HighMem, type      Isolate      0      0      0      0      0  
  26.     0      0      0      0      0      0  
  27.   
  28. Number of blocks type     Unmovable  Reclaimable      Movable      Reserve  
  29. Isolate  
  30. Node 0, zone   Normal           13            8          178            2  
  31.      0  
  32. Node 0, zone  HighMem            1            0           14            1  
  33.      0  


初始化:


首先对伙伴系统相关数据结构初始化,有如下调用流程:

start_kernel -> setup_arch ->paging_init -> bootmem_init -> arm_bootmem_free ->

free_area_init_node ->init_currently_empty_zone -> zone_init_free_lists

[html] view plaincopy
  1. static void __meminit zone_init_free_lists(struct zone *zone)  
  2. {  
  3.     int order, t;  
  4.     /*对每种迁移类型每个order初始化free_list和nr_free。*/  
  5.     for_each_migratetype_order(order, t) {  
  6.         INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);  
  7.         zone->free_area[order].nr_free = 0;  
  8.     }  
  9. }  
  10.   
  11. #define for_each_migratetype_order(order, type) \  
  12.     for (order = 0; order < MAX_ORDER; order++) \  
  13.         for (type = 0; type < MIGRATE_TYPES; type++)  
  14.   
  15. 初始化好数据结构之后,先要得到系统当前空闲的可供伙伴系统分配的页,由于在伙伴系统初始化之前使用的是bootmem分配器,所以现在是该释放bootmem分配器所管理的内存部分了。调用流程如下:  
  16.   
  17. start_kernel -> mm_init -> mem_init.  
  18. /*  
  19.  * mem_init() marks the free areas in the mem_map and tells us how much  
  20.  * memory is free.  This is done after various parts of the system have  
  21.  * claimed their memory after the kernel image.  
  22.  */  
  23. void __init mem_init(void)  
  24. {  
  25.     unsigned long reserved_pages, free_pages;  
  26.     struct memblock_region *reg;  
  27.     int i;  
  28.   
  29.     max_mapnr   = pfn_to_page(max_pfn + PHYS_PFN_OFFSET) - mem_map;  
  30.   
  31.     /* this will put all unused low memory onto the freelists */  
  32.     /*标记可以使用的内存页*/  
  33.     free_unused_memmap(&meminfo);  
  34.     /*由bootmem分配器管理的空闲内存部分都会被释放,  
  35. 释放的接口是__free_pages (),后面会说道调用这个接口最终会  
  36. 被放到伙伴系统的free_list上面。另外,bootmem分配器到这里  
  37. 也结束生命了。*/  
  38.     totalram_pages += free_all_bootmem();  
  39.     /*高端内存空闲页也被释放到free_list中。*/  
  40.     free_highpages();  
  41.   
  42.     reserved_pages = free_pages = 0;  
  43.     /*统计当前物理内存空闲页和保留页各有多少。*/  
  44.     for_each_bank(i, &meminfo) {  
  45.         struct membank *bank = &meminfo.bank[i];  
  46.         unsigned int pfn1, pfn2;  
  47.         struct page *page, *end;  
  48.   
  49.         pfn1 = bank_pfn_start(bank);  
  50.         pfn2 = bank_pfn_end(bank);  
  51.   
  52.         page = pfn_to_page(pfn1);  
  53.         end  = pfn_to_page(pfn2 - 1) + 1;  
  54.   
  55.         do {  
  56.             if (PageReserved(page))  
  57.                 reserved_pages++;  
  58.             else if (!page_count(page))  
  59.                 free_pages++;  
  60.             page++;  
  61. #ifdef CONFIG_SPARSEMEM  
  62.             pfn1++;  
  63.             if (!(pfn1 % PAGES_PER_SECTION))  
  64.                 page = pfn_to_page(pfn1);  
  65.         } while (pfn1 < pfn2);  
  66. #else  
  67.         } while (page < end);  
  68. #endif  
  69.     }  
  70.   
  71. /*  
  72.      * Since our memory may not be contiguous, calculate the  
  73.      * real number of pages we have in this system  
  74.      */  
  75.     printk(KERN_INFO "Memory:");  
  76.     num_physpages = 0;  
  77.     for_each_memblock(memory, reg) {  
  78.         unsigned long pages = memblock_region_memory_end_pfn(reg) -  
  79.             memblock_region_memory_base_pfn(reg);  
  80.         num_physpages += pages;  
  81.         printk(" %ldMB", pages >> (20 - PAGE_SHIFT));  
  82.     }  
  83.     printk(" = %luMB total\n", num_physpages >> (20 - PAGE_SHIFT));  
  84.   
  85.     printk(KERN_NOTICE "Memory: %luk/%luk available, %luk reserved, %luK highmem\n",  
  86.         nr_free_pages() << (PAGE_SHIFT-10),  
  87.         free_pages << (PAGE_SHIFT-10),  
  88.         reserved_pages << (PAGE_SHIFT-10),  
  89.         totalhigh_pages << (PAGE_SHIFT-10));  
  90.   
  91. #define MLK(b, t) b, t, ((t) - (b)) >> 10  
  92. #define MLM(b, t) b, t, ((t) - (b)) >> 20  
  93. #define MLK_ROUNDUP(b, t) b, t, DIV_ROUND_UP(((t) - (b)), SZ_1K)  
  94.   
  95. /*打印出各个区域的起始和结束地址。*/  
  96.     printk(KERN_NOTICE "Virtual kernel memory layout:\n"  
  97.             "    vector  : 0x%08lx - 0x%08lx   (%4ld kB)\n"  
  98. #ifdef CONFIG_HAVE_TCM  
  99.             "    DTCM    : 0x%08lx - 0x%08lx   (%4ld kB)\n"  
  100.             "    ITCM    : 0x%08lx - 0x%08lx   (%4ld kB)\n"  
  101. #endif  
  102.             "    fixmap  : 0x%08lx - 0x%08lx   (%4ld kB)\n"  
  103.             "    vmalloc : 0x%08lx - 0x%08lx   (%4ld MB)\n"  
  104.             "    lowmem  : 0x%08lx - 0x%08lx   (%4ld MB)\n"  
  105. #ifdef CONFIG_HIGHMEM  
  106.             "    pkmap   : 0x%08lx - 0x%08lx   (%4ld MB)\n"  
  107. #endif  
  108. #ifdef CONFIG_MODULES  
  109.             "    modules : 0x%08lx - 0x%08lx   (%4ld MB)\n"  
  110. #endif  
  111.             "      .text : 0x%p" " - 0x%p" "   (%4d kB)\n"  
  112.             "      .init : 0x%p" " - 0x%p" "   (%4d kB)\n"  
  113.             "      .data : 0x%p" " - 0x%p" "   (%4d kB)\n"  
  114.             "       .bss : 0x%p" " - 0x%p" "   (%4d kB)\n",  
  115.   
  116.             MLK(UL(CONFIG_VECTORS_BASE), UL(CONFIG_VECTORS_BASE) +  
  117.                 (PAGE_SIZE)),  
  118.             MLK(FIXADDR_START, FIXADDR_TOP),  
  119.             MLM(VMALLOC_START, VMALLOC_END),  
  120.             MLM(PAGE_OFFSET, (unsigned long)high_memory),  
  121. #ifdef CONFIG_HIGHMEM  
  122.             MLM(PKMAP_BASE, (PKMAP_BASE) + (LAST_PKMAP) *  
  123.                 (PAGE_SIZE)),  
  124. #endif  
  125. #ifdef CONFIG_MODULES  
  126.             MLM(MODULES_VADDR, MODULES_END),  
  127. #endif  
  128.   
  129.             MLK_ROUNDUP(_text, _etext),  
  130.             MLK_ROUNDUP(__init_begin, __init_end),  
  131.             MLK_ROUNDUP(_sdata, _edata),  
  132.             MLK_ROUNDUP(__bss_start, __bss_stop));  
  133. ~~snip  
  134. }  

到此,系统空闲的内存都交由伙伴系统管理了!


内存分配:


调用的接口有如下几个:

[html] view plaincopy
  1. #define alloc_pages(gfp_mask, order) \  
  2.         alloc_pages_node(numa_node_id(), gfp_mask, order)  
  3. #define alloc_pages_vma(gfp_mask, order, vma, addr, node)   \  
  4.     alloc_pages(gfp_mask, order)  
  5. #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)  
  6. #define alloc_page_vma(gfp_mask, vma, addr)         \  
  7.     alloc_pages_vma(gfp_mask, 0, vma, addr, numa_node_id())  
  8. #define alloc_page_vma_node(gfp_mask, vma, addr, node)      \  
  9.     alloc_pages_vma(gfp_mask, 0, vma, addr, node)  
不过最终调用的都是__alloc_pages_nodemask()

__alloc_pages_nodemask()


[html] view plaincopy
  1. struct page *  
  2. __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,  
  3.             struct zonelist *zonelist, nodemask_t *nodemask)  
  4. {  
  5.     /*得到分配者所需要的对应zone区域。*/  
  6.     enum zone_type high_zoneidx = gfp_zone(gfp_mask);  
  7.     struct zone *preferred_zone;  
  8.     struct page *page = NULL;  
  9.   
  10.     /*根据分配者存在gfp_mask中的值来得到对应的表示用哪种迁移类型。*/  
  11.     int migratetype = allocflags_to_migratetype(gfp_mask);  
  12.     unsigned int cpuset_mems_cookie;  
  13.   
  14.     gfp_mask &= gfp_allowed_mask;  
  15.   
  16. ~~snip  
  17.     /*第一次尝试快速分配,可能从pcp高速缓存页分配,也可以从free_list上分配。  
  18. 这是最简单的分配状况。*/  
  19.     /* First allocation attempt */  
  20.     page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,  
  21.             zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,  
  22.             preferred_zone, migratetype);  
  23.     /*如果分配失败,则尝试再一次慢速分配,可能需要等页面回收等之后才有可用内存页。*/  
  24.     if (unlikely(!page))  
  25.         page = __alloc_pages_slowpath(gfp_mask, order,  
  26.                 zonelist, high_zoneidx, nodemask,  
  27.                 preferred_zone, migratetype);  
  28. ~snip  
  29.   
  30.     return page;  
  31. }  


get_page_from_freelist():

[html] view plaincopy
  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.     classzone_idx = zone_idx(preferred_zone);  
  15. zonelist_scan:  
  16.     /*  
  17.      * Scan zonelist, looking for a zone with enough free.  
  18.      * See also cpuset_zone_allowed() comment in kernel/cpuset.c.  
  19.      */  
  20.     /*扫描整个zonlist列表,我们是UMA,所以只有一个了。  
  21. 不过还是会在当前zone内存不足的情况下,依次扫描下个zone  
  22. 是否有空闲页。*/  
  23.     for_each_zone_zonelist_nodemask(zone, z, zonelist,  
  24.                         high_zoneidx, nodemask) {  
  25.         /*检查是否在运行的node上分配内存*/  
  26.         if ((alloc_flags & ALLOC_CPUSET) &&  
  27.             !cpuset_zone_allowed_softwall(zone, gfp_mask))  
  28.                 continue;  
  29. ~~snip  
  30.         /*伙伴系统提供了一个水位线机制来合理的分配内存。从名字  
  31. 可以想到,肯定有对应的水位高低之分,高出或者低于肯定有想对应的  
  32. 操作。*/  
  33.         if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {  
  34.             unsigned long mark;  
  35.             int ret;  
  36.       
  37.             mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];  
  38.             /*检查水位线是否正常。*/  
  39.             if (zone_watermark_ok(zone, order, mark,  
  40.                     classzone_idx, alloc_flags))  
  41.                 goto try_this_zone;  
  42.   
  43.         ~~snip  
  44.             /*跑到这里表示水位线不正常了,这里为0  
  45. 表示没有设置页面回收模式。*/  
  46.             if (zone_reclaim_mode == 0)  
  47.                 goto this_zone_full;  
  48.             /*开始回收本zone相应页面,不过函数只针对NUMA,  
  49. UMA直接返回了0.*/  
  50.             ret = zone_reclaim(zone, gfp_mask, order);  
  51.             switch (ret) {  
  52.             case ZONE_RECLAIM_NOSCAN:  
  53.                 /* did not scan */  
  54.                 continue;  
  55.             case ZONE_RECLAIM_FULL:  
  56.                 /* scanned but unreclaimable */  
  57.                 continue;  
  58.             default:  
  59.                 /* did we reclaim enough */  
  60.                 /*回收过后重新判断水位线。*/  
  61.                 if (!zone_watermark_ok(zone, order, mark,  
  62.                         classzone_idx, alloc_flags))  
  63.                 /*不正常则表示此zone已满!*/  
  64.                     goto this_zone_full;  
  65.             }  
  66.         }  
  67. /*跑到这表示此zone可以分配。*/  
  68. try_this_zone:  
  69.         /*根据order的值来决定从pcp还是free_list上分配。*/  
  70.         page = buffered_rmqueue(preferred_zone, zone, order,  
  71.                         gfp_mask, migratetype);  
  72.         if (page)  
  73.             break;  
  74. this_zone_full:  
  75.     ~~snip  
  76.     }  
  77.   
  78. ~~snip  
  79.     return page;  
  80. }  

buffered_rmqueue():

[html] view plaincopy
  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.     /*分配的是pcp冷页还是热页,热页表示也存在硬件高速缓冲中。  
  9. 而冷页没有。一般使用的都是热页。*/  
  10.     int cold = !!(gfp_flags & __GFP_COLD);  
  11.   
  12. again:  
  13.     /*当order为0也就是只分配一页的时候,为了提高效率,  
  14. 直接从pcp中去获取。*/  
  15.     if (likely(order == 0)) {  
  16.         struct per_cpu_pages *pcp;  
  17.         struct list_head *list;  
  18.   
  19.         local_irq_save(flags);  
  20.         /*每个cpu对应一个pcp,pcp名字由来就是  
  21. Per cpu pageset.*/  
  22.         pcp = &this_cpu_ptr(zone->pageset)->pcp;  
  23.         /*从当前迁移类型上得到list,以判断是否有空闲页。*/  
  24.         list = &pcp->lists[migratetype];  
  25.         /*pcp本质上也是从伙伴系统的free list中获得的。*/  
  26.         if (list_empty(list)) {  
  27.             /*从free list上申请batch个页放入pcp备用,最终调用  
  28. 的是__rmqueue()标准申请接口,下面会分析到。*/  
  29.             pcp->count += rmqueue_bulk(zone, 0,  
  30.                     pcp->batch, list,  
  31.                     migratetype, cold);  
  32.             if (unlikely(list_empty(list)))  
  33.                 goto failed;  
  34.         }  
  35.         /*冷页从list最后取,热页从最前面取, 由存放顺序决定。*/  
  36.         if (cold)  
  37.             page = list_entry(list->prev, struct page, lru);  
  38.         else  
  39.             page = list_entry(list->next, struct page, lru);  
  40.         /*被申请掉后从空闲List中移除。*/  
  41.         list_del(&page->lru);  
  42.         pcp->count--;  
  43.     } else {  
  44.         if (unlikely(gfp_flags & __GFP_NOFAIL)) {  
  45.             WARN_ON_ONCE(order > 1);  
  46.         }  
  47.         spin_lock_irqsave(&zone->lock, flags);  
  48.         /*从伙伴系统上的free list申请。*/  
  49.         page = __rmqueue(zone, order, migratetype);  
  50.         spin_unlock(&zone->lock);  
  51.         if (!page)  
  52.             goto failed;  
  53.         __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));  
  54.     }  
  55.     /*重新统计当前zone相关信息。*/  
  56.     __count_zone_vm_events(PGALLOC, zone, 1 << order);  
  57.     zone_statistics(preferred_zone, zone, gfp_flags);  
  58.     local_irq_restore(flags);  
  59.   
  60.     VM_BUG_ON(bad_range(zone, page));  
  61.     /*后续准备工作,如设置一些页相关标志,是否是zero page等。*/  
  62.     if (prep_new_page(page, order, gfp_flags))  
  63.         goto again;  
  64.     return page;  
  65.   
  66. failed:  
  67.     local_irq_restore(flags);  
  68.     return NULL;  
  69. }  
__rmqueue():
[html] view plaincopy
  1. rmqueue_bulk()只是pcp调用__rmqueue()然后设置和pcp相关的一些参数,比较简单,这里不介绍了,直接看__rmqueue().  
  2. static struct page *__rmqueue(struct zone *zone, unsigned int order,  
  3.                         int migratetype)  
  4. {  
  5.     struct page *page;  
  6.   
  7. retry_reserve:  
  8.     /*使用伙伴系统算法分配内存*/  
  9.     page = __rmqueue_smallest(zone, order, migratetype);  
  10.     /*如果失败了,而且当前迁移类型不是RESERVE,  
  11. 那么尝试从下个迁移类型分配。分配次序前面有说明过了,  
  12. 按照fallbacks 定义的顺序,MIGRATE_RESERVE表示很紧急的时候分配  
  13. 如果它还是失败那没戏了。*/  
  14.     if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {  
  15.         page = __rmqueue_fallback(zone, order, migratetype);  
  16.         if (!page) {  
  17.             /*还是失败的话那么只能用MIGRATE_RESERVE 类型的  
  18. 去申请了。*/  
  19.             migratetype = MIGRATE_RESERVE;  
  20.             goto retry_reserve;  
  21.         }  
  22.     }  
  23.   
  24.     trace_mm_page_alloc_zone_locked(page, order, migratetype);  
  25.     return page;  
  26. }  



__rmqueue_smallest():
[html] view plaincopy
  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.     /*buddy算法还是很容易理解的。从当前要申请的order开始查找,  
  9. 只有大于order的有空闲页,那就成功了!*/  
  10.     /* Find a page of the appropriate size in the preferred list */  
  11.     for (current_order = order; current_order < MAX_ORDER; ++current_order) {  
  12.         /*取得当前order对应的free_area*/  
  13.         area = &(zone->free_area[current_order]);  
  14.         /*没有空闲页则查找更大的order。*/  
  15.         if (list_empty(&area->free_list[migratetype]))  
  16.             continue;  
  17.         /*跑到这里表示已经找到,取出free_list中的一页。*/  
  18.         page = list_entry(area->free_list[migratetype].next,  
  19.                             struct page, lru);  
  20.         /*从free_list中删掉。*/  
  21.         list_del(&page->lru);  
  22.         rmv_page_order(page);  
  23.         /*空闲页减少。*/  
  24.         area->nr_free--;  
  25.         /*拆分合并此order,因为一部分被使用了,剩下一部分还空闲着,  
  26. 会被安排到低于当前找到order的free_list上,重新排列buddy内存布局*/  
  27.         expand(zone, page, order, current_order, area, migratetype);  
  28.         return page;  
  29.     }  
  30.   
  31.     return NULL;  
  32. }  



expand():

[html] view plaincopy
  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;  
  6.     /*low和high分别表示要申请的order和现在找到的order*/  
  7.     while (high > low) {  
  8.         /*使用低一阶的area, order小一阶, size也减半*/  
  9.         area--;  
  10.         high--;  
  11.         size >>= 1;  
  12.         VM_BUG_ON(bad_range(zone, &page[size]));  
  13.         /*从size开始的page插入到当前area的freelist中*/  
  14.         list_add(&page[size].lru, &area->free_list[migratetype]);  
  15.         area->nr_free++;  
  16.         /*保存当前order当struct page中。*/  
  17.         set_page_order(&page[size], high);  
  18.     }  
  19. }  

所以如果第一次分配就成功,buddy算法流程相当简单的。如果当前迁移类型分配失败,

那么就要从下一个迁移类型上去分配了!来看__rmqueue_fallback().
__rmqueue_fallback():
[html] view plaincopy
  1. static inline struct page *  
  2. __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)  
  3. {  
  4.     struct free_area * area;  
  5.     int current_order;  
  6.     struct page *page;  
  7.     int migratetype, i;  
  8.     /*从最高阶开始搜索,大块内存申请/分割可以避免更少的碎片。*/  
  9.     /* Find the largest possible block of pages in the other list */  
  10.     for (current_order = MAX_ORDER-1; current_order >= order;  
  11.                         --current_order) {  
  12.         for (i = 0;; i++) {  
  13.             /*得到数组中指定顺序的迁移类型。*/  
  14.             migratetype = fallbacks[start_migratetype][i];  
  15.             /*保留内存晚点操作。*/  
  16.             /* MIGRATE_RESERVE handled later if necessary */  
  17.             if (migratetype == MIGRATE_RESERVE)  
  18.                 break;  
  19.             /*取得area,判断list,为空表示当前迁移类型也没有空闲页。*/  
  20.             area = &(zone->free_area[current_order]);  
  21.             if (list_empty(&area->free_list[migratetype]))  
  22.                 continue;  
  23.   
  24.             page = list_entry(area->free_list[migratetype].next,  
  25.                     struct page, lru);  
  26.             area->nr_free--;  
  27.   
  28.             /*  
  29.              * If breaking a large block of pages, move all free  
  30.             /*当前不是cma迁移类型,或者order比一个pageblock的order的  
  31. 一半要大,或者是可回收类型,或者定义了迁移策略时,移动内存页到先前申请的迁移类型中去。*/     
  32.             if (!is_migrate_cma(migratetype) &&  
  33.                 (unlikely(current_order >= pageblock_order / 2) ||  
  34.                  start_migratetype == MIGRATE_RECLAIMABLE ||  
  35.                  page_group_by_mobility_disabled)) {  
  36.                 int pages;  
  37.                 /*移动空闲页到先前迁移类型中去。*/  
  38.                 pages = move_freepages_block(zone, page,  
  39.                                 start_migratetype);  
  40.                 /*当当前内存块大部分已经迁移到先前类型中或者定义了迁移策略时,  
  41. 那么就将这一整块全部迁移过去。*/  
  42.                 /* Claim the whole block if over half of it is free */  
  43.                 if (pages >= (1 << (pageblock_order-1)) ||  
  44.                         page_group_by_mobility_disabled)  
  45.                     set_pageblock_migratetype(page,  
  46.                                 start_migratetype);  
  47.   
  48.                 migratetype = start_migratetype;  
  49.             }  
  50.   
  51.             /* Remove the page from the freelists */  
  52.             list_del(&page->lru);  
  53.             rmv_page_order(page);  
  54.               
  55.             /* Take ownership for orders >= pageblock_order */  
  56.             if (current_order >= pageblock_order &&  
  57.                 !is_migrate_cma(migratetype))  
  58.                 change_pageblock_range(page, current_order,  
  59.                             start_migratetype);  
  60.             /*拆分/合并*/  
  61.             expand(zone, page, order, current_order, area,  
  62.                    is_migrate_cma(migratetype)  
  63.                  ? migratetype : start_migratetype);  
  64.   
  65.             trace_mm_page_alloc_extfrag(page, order, current_order,  
  66.                 start_migratetype, migratetype);  
  67.   
  68.             return page;  
  69.         }  
  70.     }  
  71.     return NULL;  
  72. }  

以上的内存分配都是基于分配比较顺利的情况,如果分配依然失败,那么只能使用慢速分配机制了!so 继续看__alloc_pages_slowpath().

__alloc_pages_slowpath():

[html] view plaincopy
  1. static inline struct page *  
  2. __alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,  
  3.     struct zonelist *zonelist, enum zone_type high_zoneidx,  
  4.     nodemask_t *nodemask, struct zone *preferred_zone,  
  5.     int migratetype)  
  6. {  
  7.     const gfp_t wait = gfp_mask & __GFP_WAIT;  
  8.     struct page *page = NULL;  
  9.     int alloc_flags;  
  10.     unsigned long pages_reclaimed = 0;  
  11.     unsigned long did_some_progress;  
  12.     bool sync_migration = false;  
  13.     bool deferred_compaction = false;  
  14. ~~snip  
  15. restart:  
  16.     /*如果没有禁止内存回收的话就唤醒交换线程来进行内存页面回收, 写回或  
  17. 换出很少使用的页到磁盘上。*/  
  18.     if (!(gfp_mask & __GFP_NO_KSWAPD))  
  19.         wake_all_kswapd(order, zonelist, high_zoneidx,  
  20.                         zone_idx(preferred_zone));  
  21.   
  22. /*为了更积极地尝试分配,将水位线降低以便更有可能分配成功。*/  
  23.     alloc_flags = gfp_to_alloc_flags(gfp_mask);  
  24.   
  25.     /*  
  26.      * Find the true preferred zone if the allocation is unconstrained by  
  27.      * cpusets.  
  28.      */  
  29.     if (!(alloc_flags & ALLOC_CPUSET) && !nodemask)  
  30.         first_zones_zonelist(zonelist, high_zoneidx, NULL,  
  31.                     &preferred_zone);  
  32.   
  33. rebalance:  
  34.     /*降低水位线之后重新尝试分配。*/  
  35.     /* This is the last chance, in general, before the goto nopage. */  
  36.     page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,  
  37.             high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,  
  38.             preferred_zone, migratetype);  
  39.     if (page)  
  40.         goto got_pg;  
  41.     /*如果不考虑水位线,那么继续尝试分配。如果定义了__GFP_NOFAIL,  
  42. 那么此函数会不断尝试分配,直到成功。*/  
  43.     /* Allocate without watermarks if the context allows */  
  44.     if (alloc_flags & ALLOC_NO_WATERMARKS) {  
  45.         page = __alloc_pages_high_priority(gfp_mask, order,  
  46.                 zonelist, high_zoneidx, nodemask,  
  47.                 preferred_zone, migratetype);  
  48.         if (page)  
  49.             goto got_pg;  
  50.     }  
  51.     /*没定义等待,如在中断上下文中需要原子份额配,所以直接返回失败。*/  
  52.     /* Atomic allocations - we can't balance anything */  
  53.     if (!wait)  
  54.         goto nopage;  
  55.     /*分配器自身需要更多内存,避免递归调用。*/  
  56.     /* Avoid recursion of direct reclaim */  
  57.     if (current->flags & PF_MEMALLOC)  
  58.         goto nopage;  
  59.     /*oom killer选中的线程才会设置TIF_MEMDIE标志,当然如果不允许失败的  
  60. 话那就循环等待其他线程释放内存。*/  
  61.     /* Avoid allocations with no watermarks from looping endlessly */  
  62.     if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))  
  63.         goto nopage;  
  64.   
  65. /*尝试压缩内存再尝试分配。*/  
  66.     page = __alloc_pages_direct_compact(gfp_mask, order,  
  67.                     zonelist, high_zoneidx,  
  68.                     nodemask,  
  69.                     alloc_flags, preferred_zone,  
  70.                     migratetype, sync_migration,  
  71.                     &deferred_compaction,  
  72.                     &did_some_progress);  
  73.     if (page)  
  74.         goto got_pg;  
  75. ~~snip  
  76.     /*自己直接去回收内存,然后尝试分配。*/  
  77.     /* Try direct reclaim and then allocating */  
  78.     page = __alloc_pages_direct_reclaim(gfp_mask, order,  
  79.                     zonelist, high_zoneidx,  
  80.                     nodemask,  
  81.                     alloc_flags, preferred_zone,  
  82.                     migratetype, &did_some_progress);  
  83.     if (page)  
  84.         goto got_pg;  
  85.   
  86. /*如果还是失败的话那就使用oom killer杀掉一些线程,再尝试分配。*/  
  87.     if (!did_some_progress) {  
  88.         if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {  
  89.             if (oom_killer_disabled)  
  90.                 goto nopage;  
  91.             /* Coredumps can quickly deplete all memory reserves */  
  92.             if ((current->flags & PF_DUMPCORE) &&  
  93.                 !(gfp_mask & __GFP_NOFAIL))  
  94.                 goto nopage;  
  95.             page = __alloc_pages_may_oom(gfp_mask, order,  
  96.                     zonelist, high_zoneidx,  
  97.                     nodemask, preferred_zone,  
  98.                     migratetype);  
  99.             if (page)  
  100.                 goto got_pg;  
  101.   
  102.             if (!(gfp_mask & __GFP_NOFAIL)) {  
  103.                 /*  
  104.                  * The oom killer is not called for high-order  
  105.                  * allocations that may fail, so if no progress  
  106.                  * is being made, there are no other options and  
  107.                  * retrying is unlikely to help.  
  108.                  */  
  109.                 if (order > PAGE_ALLOC_COSTLY_ORDER)  
  110.                     goto nopage;  
  111.                 /*  
  112.                  * The oom killer is not called for lowmem  
  113.                  * allocations to prevent needlessly killing  
  114.                  * innocent tasks.  
  115.                  */  
  116.                 if (high_zoneidx < ZONE_NORMAL)  
  117.                     goto nopage;  
  118.             }  
  119.   
  120.             goto restart;  
  121.         }  
  122.     }  
  123.     /*是否需要等待一会再尝试重新分配?*/  
  124.     /* Check if we should retry the allocation */  
  125.     pages_reclaimed += did_some_progress;  
  126.     if (should_alloc_retry(gfp_mask, order, did_some_progress,  
  127.                         pages_reclaimed)) {  
  128.         /* Wait for some write requests to complete then retry */  
  129.         wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);  
  130.         goto rebalance;  
  131.     } else {  
  132.         /*在做过内存回收之后再使用内存压缩分配试试看。*/  
  133.         page = __alloc_pages_direct_compact(gfp_mask, order,  
  134.                     zonelist, high_zoneidx,  
  135.                     nodemask,  
  136.                     alloc_flags, preferred_zone,  
  137.                     migratetype, sync_migration,  
  138.                     &deferred_compaction,  
  139.                     &did_some_progress);  
  140.         if (page)  
  141.             goto got_pg;  
  142.     }  
  143. /*到这里表示真分配失败了,打印警告信息。*/  
  144. nopage:  
  145.     warn_alloc_failed(gfp_mask, order, NULL);  
  146.     return page;  
  147. got_pg:  
  148.     if (kmemcheck_enabled)  
  149.         kmemcheck_pagealloc_alloc(page, order, gfp_mask);  
  150.     return page;  
  151.   
  152. }  

内存分配一波三折,小结一下:

1.      先尝试快速分配,其中会从不同的zone以及迁移类型上去尝试,失败的话就进入慢速分配,里面会再划分单页面从pcp上分配以及多页面从伙伴系统中分配。

2.      尝试慢速分配,一般流程就是唤醒内存页面回收线程,然后尝试低水位分配 -> 忽略水位分配 -> 压缩内存分配 -> 直接回收内存分配 -> oom killer杀死线程分配 -> 压缩内存分配。

内存释放:

         关于内存释放,使用的最终公共接口为__free_pages, 流程部分还是比较清晰的,

这里不对代码作具体分析了。分单页和多页释放。

单页:释放到pcp缓冲中,如果pcp中的空闲页面数过多,就会移动一部分到伙伴系统中。

多页:释放多页到伙伴系统,当当前的释放页面数和相邻的空闲页面数相同时,那就将两者合并,然后放到更高一阶的order链表上面,依次循环执行次操作直到不能合并为止。

  

阅读(1083) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~