精华内容
下载资源
问答
  • linux将内核划分为内存域,内核提供了所谓的内存域修饰符,来指定从哪个内存域分配所需的页。 [cpp] view plain copy #define __GFP_DMA ((__force gfp_t)0x01u)   #...

    伙伴系统中用于分配页的函数如下:

    alloc_pages(mask,order)分配2^order页并返回一个struct page的实例,表示分配的内存块的起始页。alloc_page(mask)是前者在order=0情况下的简化形式,只分配一页。

    get_zeroed_page(mask)分配一页并返回一个page实例,页对应的内存填充0(所有其他函数分配之后的内容是未定义的)。

    __get_free_pages(mask,order)和__get_free_page(mask)的工作方式与上述函数相同,但返回分配内存块的虚拟地址,而不是page实例。

    get_dma_pages(gfp_mask,order)用来获得适用于DMA的页。

    在空闲内存无法满足请求以至于分配失败的情况下,所有上述函数都返回空指针 (alloc_pages和alloc_page)或者0(get_zeroed_page、__get_free_pages和 __get_free_page)。因此内核在各次分配之后必须检查返回的结果。这种惯例与设计得很好的用户层应用程序没有什么不同,但在内核中忽略检查 将会导致严重得多的故障。

    前述所有函数中使用的mask参数的语义是什么?linux将内核划分为内存域,内核提供了所谓的内存域修饰符,来指定从哪个内存域分配所需的页。

    1. #define __GFP_DMA   ((__force gfp_t)0x01u)  
    2. #define __GFP_HIGHMEM   ((__force gfp_t)0x02u)  
    3. #define __GFP_DMA32 ((__force gfp_t)0x04u)  
    除了内存域修饰符之外,掩码中还可以设置一些标志,这些额外的标志并不限制从哪个物理内存段分配内存,但确实可以改变分配器的行为。
    1. #define __GFP_WAIT  ((__force gfp_t)0x10u)  //表示分配内存的请求可以中断。也就是说,调度器在该请求期间可随意选择另一个过程执行,或者该请求可以被另一个更重要的事件中断。  
    2. #define __GFP_HIGH  ((__force gfp_t)0x20u)  //如果请求非常重要,则设置__GFP_HIGH,即内核急切的需要内存时。在分配内存失败可能给内核带来严重得后果时,一般会设置该标志  
    3. #define __GFP_IO    ((__force gfp_t)0x40u)  //在查找空闲内存期间内核可以进行I/O操作。这意味着如果内核在内存分配期间换出页,那么仅当设置该标志时,才能将选择的页写入磁盘。  
    4. #define __GFP_FS    ((__force gfp_t)0x80u)  //允许内核执行VFS操作  
    5. #define __GFP_COLD  ((__force gfp_t)0x100u) //如果需要分配不在CPU高速缓存中的“冷”页时,则设置__GFP_COLD。  
    6. #define __GFP_NOWARN    ((__force gfp_t)0x200u) //在分配失败时禁止内核故障警告。  
    7. #define __GFP_REPEAT    ((__force gfp_t)0x400u) //在分配失败后自动重试,但在尝试若干次之后会停止。  
    8. #define __GFP_NOFAIL    ((__force gfp_t)0x800u) //在分配失败后一直重试,直至成功。  
    9. #define __GFP_NORETRY   ((__force gfp_t)0x1000u)//不重试,可能失败  
    10. #define __GFP_COMP  ((__force gfp_t)0x4000u)//增加复合页元数据  
    11. #define __GFP_ZERO  ((__force gfp_t)0x8000u)//在分配成功时,将返回填充字节0的页。  
    12. #define __GFP_NOMEMALLOC ((__force gfp_t)0x10000u) //不适用紧急分配链表  
    13. #define __GFP_HARDWALL   ((__force gfp_t)0x20000u) // 只在NUMA系统上有意义。它限制只在分配到当前进程的各个CPU所关联的结点分配内存。如果进程允许在所有的CPU上运行(默认情况下),该标志是没有 意义的。只有进程可以运行的CPU受限时,该标志才有意义。  
    14. #define __GFP_THISNODE  ((__force gfp_t)0x40000u)//页只在NUMA系统上有意义,如果设置该比特位,则内存分配失败的情况下不允许使用其他结点作为备用,需要保证在当前结点或者明确指定的结点上成功分配内存。  
    15. #define __GFP_RECLAIMABLE ((__force gfp_t)0x80000u) //将分配的内存标记为可回收  
    16. #define __GFP_MOVABLE   ((__force gfp_t)0x100000u)  //将分配的内存标记为可移动  
    17.   
    18. #define __GFP_BITS_SHIFT 21 /* Room for 21 __GFP_FOO bits */  
    19. #define __GFP_BITS_MASK ((__force gfp_t)((1 << __GFP_BITS_SHIFT) - 1))  
    20.   
    21. /* This equals 0, but use constants in case they ever change */  
    22. #define GFP_NOWAIT  (GFP_ATOMIC & ~__GFP_HIGH)  
    由于这些标志总是组合使用,内核做了一些分组,包含了用于各种标准情形的适当地标志。
    1. #define GFP_ATOMIC  (__GFP_HIGH)//用于原子分配,在任何情况下都不能中断,可能使用紧急分配链表中的内存  
    2. #define GFP_NOIO    (__GFP_WAIT)//明确禁止IO操作,但可以被中断  
    3. #define GFP_NOFS    (__GFP_WAIT | __GFP_IO)//明确禁止访问VFS层操作,但可以被中断  
    4. #define GFP_KERNEL  (__GFP_WAIT | __GFP_IO | __GFP_FS)//内核分配的默认配置  
    5. #define GFP_TEMPORARY   (__GFP_WAIT | __GFP_IO | __GFP_FS | \  
    6.              __GFP_RECLAIMABLE)  
    7. #define GFP_USER    (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL)//用户分配的默认配置  
    8. #define GFP_HIGHUSER    (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL | \  
    9.              __GFP_HIGHMEM)//是GFP_USER的一个扩展,页用于用户空间,它允许分配无法直接映射的高端内存,使用高端内存页是没有坏处的,因为用户过程的地址空间总是通过非线性页表组织的  
    10. #define GFP_HIGHUSER_MOVABLE    (__GFP_WAIT | __GFP_IO | __GFP_FS | \  
    11.                  __GFP_HARDWALL | __GFP_HIGHMEM | \  
    12.                  __GFP_MOVABLE)//类似于GFP_HIGHUSER,但分配是在虚拟内存域ZONE_MOVABLE中进行  
    13. #define GFP_NOFS_PAGECACHE  (__GFP_WAIT | __GFP_IO | __GFP_MOVABLE)  
    14. #define GFP_USER_PAGECACHE  (__GFP_WAIT | __GFP_IO | __GFP_FS | \  
    15.                  __GFP_HARDWALL | __GFP_MOVABLE)  
    16. #define GFP_HIGHUSER_PAGECACHE  (__GFP_WAIT | __GFP_IO | __GFP_FS | \  
    17.                  __GFP_HARDWALL | __GFP_HIGHMEM | \  
    18.                  __GFP_MOVABLE)  
    19.   
    20. #ifdef CONFIG_NUMA  
    21. #define GFP_THISNODE    (__GFP_THISNODE | __GFP_NOWARN | __GFP_NORETRY)  
    22. #else  
    23. #define GFP_THISNODE    ((__force gfp_t)0)  
    24. #endif  
    25.   
    26. /* This mask makes up all the page movable related flags */  
    27. #define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE)  
    28.   
    29. /* Control page allocator reclaim behavior */  
    30. #define GFP_RECLAIM_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS|\  
    31.             __GFP_NOWARN|__GFP_REPEAT|__GFP_NOFAIL|\  
    32.             __GFP_NORETRY|__GFP_NOMEMALLOC)  
    33.   
    34. /* Control allocation constraints */  
    35. #define GFP_CONSTRAINT_MASK (__GFP_HARDWALL|__GFP_THISNODE)  
    36.   
    37. /* Do not use these with a slab allocator */  
    38. #define GFP_SLAB_BUG_MASK (__GFP_DMA32|__GFP_HIGHMEM|~__GFP_BITS_MASK)  
    39.   
    40. /* Flag - indicates that the buffer will be suitable for DMA.  Ignored on some 
    41.    platforms, used as appropriate on others */  
    42.   
    43. #define GFP_DMA     __GFP_DMA  
    44.   
    45. /* 4GB DMA on some platforms */  
    46. #define GFP_DMA32   __GFP_DMA32  
    1. #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)  
    1. #define __get_free_page(gfp_mask) \  
    2.         __get_free_pages((gfp_mask),0)  
    1. #define __get_dma_pages(gfp_mask, order) \  
    2.         __get_free_pages((gfp_mask) | GFP_DMA,(order))  
    1. fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)  
    2. {  
    3.     struct page * page;  
    4.     page = alloc_pages(gfp_mask, order);  
    5.     if (!page)  
    6.         return 0;  
    7.     return (unsigned long) page_address(page);  
    8. }  
    1. #define alloc_pages(gfp_mask, order) \  
    2.         alloc_pages_node(numa_node_id(), gfp_mask, order)  
    根据上面的代码,可以得出各个分配函数之间的关系如下图所示:


    主要的函数是alloc_pages_node。alloc_pages_node源代码的详细分析如下:

    1. static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,  
    2.                         unsigned int order)  
    3. {  
    4.     if (unlikely(order >= MAX_ORDER))//执行一个检查,避免分配过大的内存块  
    5.         return NULL;  
    6.   
    7.     /* Unknown node is current node */  
    8.     if (nid < 0)//如果指定负的结点ID(不存在),内核自动地使用当前执行CPU对应的结点ID。  
    9.         nid = numa_node_id();  
    10.   
    11.     return __alloc_pages(gfp_mask, order,  
    12.         NODE_DATA(nid)->node_zonelists + gfp_zone(gfp_mask));//接下来的工作委托给__alloc_pages,只需传递一组适当地参数,请注意,gfp_zone用于选择分配内存的内存域。  
    13. }  
    1. static inline enum zone_type gfp_zone(gfp_t flags)//本函数比较好理解,就是根据指定的标志确定内存域  
    2. {  
    3.     int base = 0;  
    4.   
    5. #ifdef CONFIG_NUMA  
    6.     if (flags & __GFP_THISNODE)  
    7.         base = MAX_NR_ZONES;  
    8. #endif  
    9.   
    10. #ifdef CONFIG_ZONE_DMA  
    11.     if (flags & __GFP_DMA)  
    12.         return base + ZONE_DMA;  
    13. #endif  
    14. #ifdef CONFIG_ZONE_DMA32  
    15.     if (flags & __GFP_DMA32)  
    16.         return base + ZONE_DMA32;  
    17. #endif  
    18.     if ((flags & (__GFP_HIGHMEM | __GFP_MOVABLE)) ==  
    19.             (__GFP_HIGHMEM | __GFP_MOVABLE))  
    20.         return base + ZONE_MOVABLE;  
    21. #ifdef CONFIG_HIGHMEM  
    22.     if (flags & __GFP_HIGHMEM)  
    23.         return base + ZONE_HIGHMEM;  
    24. #endif  
    25.     return base + ZONE_NORMAL;  
    26. }  
    __alloc_pages源代码详细分析如下:
    1. struct page * fastcall  
    2. __alloc_pages(gfp_t gfp_mask, unsigned int order,  
    3. <pre>       struct zonelist *zonelist)//<span style="text- align: justify; " lang="EN-US">gfp_mask</span>< span style="text-align: justify; ">是一些标志位,用来制定如何寻找空闲页框,< span style="text-align: justify; " lang="EN-US">order</span>& lt;span style="text-align: justify; ">用来表示所需物理块的大小,从空闲链表中获取</span& gt;<span style="text-align: justify; " lang="EN-US">2^order< /span><span style="text-align: justify; ">页内存,< span style="text-align: justify; ">在管理区链表</span>< span style="text-align: justify; " lang="EN-US">zonelist</span& gt;<span style="text-align: justify; ">中依次查找每个区,从中找到满足要求的区< /span></span></span></pre> {const gfp_t wait = gfp_mask & __GFP_WAIT;//gfp_mask是申请内存时用到的控制字,这一句 就是为了检测我们的控制字里面是否有__GPF_WAIT这个属性struct zone **z;//<span style="text- align:justify">管理区结构 体</span>struct page *page;struct reclaim_state reclaim_state;struct task_struct *p =  
    4.  current;int do_retry;int alloc_flags;int did_some_progress;might_sleep_if(wait);// 如果在gfp_mask中设置了__GFP_WAIT位,表明内核可以阻塞当前进程,来等待空闲页面。在分配开始之前即阻塞,目的是为了等待其它进程释放 更多的页面if (should_fail_alloc_page(gfp_mask, order))//通过简单算法在真正分配前检查分配是否会失 败,避免进入真正的分配程序后浪费系统时间return NULL;restart:z  
    5.  = zonelist->zones; //zonelist 是struct node中的一个成员,它表示系统内所有normal内存页区的连接链表,<span style="text- align:justify; text-indent:28px">首先 让</span><span style="text-align:justify; text- indent:28px" lang="EN-US">z</span><span style="text- align:justify; text-indent:28px">指向第一个管理区</span>if  
    6.  (unlikely(*z == NULL)) {// 如果发现头指针为空,即没有指向struct zone的有效指针,我们就直接返回错误 /* * Happens if we have an empty zonelist as a result of * GFP_THISNODE being used on a memoryless node */return NULL;}page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,zonelist,  
    7.  ALLOC_WMARK_LOW|ALLOC_CPUSET);//get_page_from_freelist 以指定的watermark来分配页面。<span style="text-indent:21pt">每个zone struct中定义 了三个watermark:pages_min, pages_low, pages_high,表示zone中应保持的空闲页面的阈 值。</span><span style="text-indent:21pt"> get_page_from_freelist函数通过设置Alloc  
    8.  flags来选择watermark。</span><span style="text-indent:21pt"></span>if (page)// 首先以pages_low watermark分配页面,如果分配成功,则跳转到 got_pggoto got_pg;/* * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and * __GFP_NOWARN set) should not cause reclaim since the subsystem  
    9.  * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim * using a larger set of nodes after it has established that the * allowed per node queues are empty and that nodes are * over allocated. */if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)//如果pages_low watermark分配失败的话,检查gfp_mask,如果GFP_THISNODE标志被设置,表明不能重试,因此跳转到nopage,返回失败goto  
    10.  nopage;for (z = zonelist->zones; *z; z++)wakeup_kswapd(*z, order);// 否则调用kswapd对zonelist中的所有zone进行页面回收,期待能将一些闲置页面交换到文件系统中 /* * OK, we're below the kswapd watermark and have kicked background * reclaim. Now things get more complex, so set up alloc_flags according  
    11.  * to how we want to proceed. * * The caller may dip into page reserves a bit more if the caller * cannot run direct reclaim, or if the caller has realtime scheduling * policy or is asking for __GFP_HIGH memory. GFP_ATOMIC requests will * set both ALLOC_HARDER  
    12.  (!wait) and ALLOC_HIGH (__GFP_HIGH). */alloc_flags = ALLOC_WMARK_MIN;// 设置alloc_flags的值,以page_min watermark来分配内存 if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)//假若进程是非中 断处理程序的实时进程,或者该进程不能被阻塞,那么这个时候,我要在最低阈值的标准的基础上,再次降低阈值 alloc_flags |= ALLOC_HARDER;if  
    13.  (gfp_mask & __GFP_HIGH)//<span style="text- align:justify">允许使用保留页面</span><span style="text- align:justify" lang="EN-US">__GFP_HIGH</span>alloc_flags |= ALLOC_HIGH;if (wait)alloc_flags |= ALLOC_CPUSET;/* * Go through the zonelist again. Let __GFP_HIGH and allocations  
    14.  * coming from realtime tasks go deeper into reserves. * * This is the last chance, in general, before the goto nopage. * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc. * See also cpuset_zone_allowed() comment in kernel/cpuset.c. */page = get_page_from_freelist(gfp_mask,  
    15.  order, zonelist, alloc_flags);// 以指定的watermark来分配页面,详细讨论见下文if (page)//分配成功,就进入got_pggoto got_pg; /* This allocation should allow future memory freeing. */rebalance://上面的 第二次分配失败 if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))// 如果当前进程允许本次申请的内存可以被释放,并且不处于软硬中断的状态,我们不顾忌必须保留最小空闲内存页,强行分配&&  
    16.  !in_interrupt()) {if (!(gfp_mask & __GFP_NOMEMALLOC)) {// 如果gfp_mask设置不需要保留紧急内存区域,以不设watermark再次分配页面 nofail_alloc:/* go through the zonelist yet again, ignoring mins * /page = get_page_from_freelist(gfp_mask, order,zonelist, ALLOC_NO_WATERMARKS); //以不设watermark进行第三次分配if  
    17.  (page)// 第三次分配成功goto got_pg;if (gfp_mask & __GFP_NOFAIL) {//第三次分配失败,如果 gfp_mask设置了__GFP_NOFAIL,则不断重试,直到分配成功 congestion_wait(WRITE, HZ/50);goto nofail_alloc;}}goto nopage;} /* Atomic allocations - we can't balance anything */if (!wait) //<span style="text-align:justify; text-indent:28px">原子分配,不允许阻塞,则只 能返回失败信号,分配失败</span>goto  
    18.  nopage;cond_resched();// 重新调度之后,试图释放一些不常用的页面/* We now go into synchronous reclaim * /cpuset_memory_pressure_bump();//开始进行同步内存回收p->flags |= PF_MEMALLOC;// 进程的标志位设置为PF_MEMALLOCreclaim_state.reclaimed_slab = 0;//对于不再活跃的SLAB也给回收掉 p->reclaim_state = &reclaim_state;//改变进程回收的状态did_some_progress  
    19.  = try_to_free_pages(zonelist->zones, order, gfp_mask);// 该函数选择最近不十分活跃的页,将其写到交换区,在物理内存中腾出空间p->reclaim_state = NULL;p-> flags &= ~PF_MEMALLOC;cond_resched(); if (order != 0)drain_all_local_pages(); if (likely(did_some_progress)) {//<span style="background- color:rgb(240,243,250)">调度之后,如果确实释放了一部分页面,则重新分配页面</span>page  
    20.  = get_page_from_freelist(gfp_mask, order,zonelist, alloc_flags);if (page)goto got_pg;} else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {//如果内核可能执行影响VFS层的调用而又没有设置GFP_NORETRY,那么调用OOM killerif (!try_set_zone_oom(zonelist)) {schedule_timeout_uninterruptible(1);goto  
    21.  restart;}/* * Go through the zonelist yet one more time, keep * very high watermark here, this is only to catch * a parallel oom killing, we must fail if we're still * under heavy pressure. */page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,zonelist,  
    22.  ALLOC_WMARK_HIGH|ALLOC_CPUSET);if (page) {clear_zonelist_oom(zonelist);goto got_pg;}/* The OOM killer will not help higher order allocs so fail */if (order > PAGE_ALLOC_COSTLY_ORDER) {// 杀死一个进程未必立即出现多余2^PAGE_ALLOC_CODTLY_ORDER页的连续内存区,因此如果当前要分配如此大的内存区,那么内核会饶恕所 选择的进程,不执行杀死进程的任务,而是承认失败并跳转到nopageclear_zonelist_oom(zonelist);goto  
    23.  nopage;}out_of_memory(zonelist, gfp_mask, order);// 选择一个内核认为犯有分配过多内存“罪行”的进程,并杀死该进程。这有很大几率腾出较多的空闲页,然后跳转到标号restart,重试分配内存的操作 clear_zonelist_oom(zonelist);goto restart;}/* * Don't let big-order allocations loop unless the caller explicitly * requests that. Wait  
    24.  for some write requests to complete then retry. * * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order * <= 3, but that may not be true in other implementations. *///如果设置了__GFP_NORETRY,或内核不允许可能影响VFS层的操作do_retry = 0;if (!(gfp_mask & __GFP_NORETRY))  
    25.  {// 没有设置__GFP_NORETRYif ((order <= PAGE_ALLOC_COSTLY_ORDER) ||(gfp_mask & amp; __GFP_REPEAT))//如果分配长度小于2^PAGE_ALLOC_COSTLY_ORDER或设置了__GFP_REPEAT,则 内核进入无限循环do_retry = 1;if (gfp_mask & __GFP_NOFAIL)//如果设置了不允许分配失败,内核也会 进入无限循环do_retry = 1;}if (do_retry) {congestion_wait(WRITE,  
    26.  HZ/50);goto rebalance;}nopage:if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {printk(KERN_WARNING "%s: page allocation failure."" order:%d, mode:0x%x\n",p->comm, order, gfp_mask);dump_stack();show_mem();}got_pg:return page;}  
    27. <pre></pre>  
    28. <p><span style="font-size:18px">get_page_from_freelist源代码的详细分析如下:</span></p>  
    29. <p></p>  
    30. <pre name="code" class="cpp">static struct page *  
    31. get_page_from_freelist(gfp_t gfp_mask, unsigned int order,  
    32.         struct zonelist *zonelist, int alloc_flags)  
    33. {  
    34.     struct zone **z;//管理区结构体  
    35.     struct page *page = NULL;  
    36.     int classzone_idx = zone_idx(zonelist->zones[0]);//#define zone_idx(zone)        ((zone) - (zone)->zone_pgdat->node_zones) 获取管理区的编号  
    37.     struct zone *zone;  
    38.     nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */  
    39.     int zlc_active = 0;     /* set if using zonelist_cache */  
    40.     int did_zlc_setup = 0;      /* just call zlc_setup() one time */  
    41.     enum zone_type highest_zoneidx = -1; /* Gets set for policy zonelists */  
    42.   
    43. zonelist_scan:  
    44.     /* 
    45.      * Scan zonelist, looking for a zone with enough free. 
    46.      * See also cpuset_zone_allowed() comment in kernel/cpuset.c. 
    47.      */  
    48.     z = zonelist->zones;//让z指向第一个管理区  
    49.     //<span style="word- wrap: break-word; text-indent: 28px; background- color: rgb(245, 247, 248); " lang="EN-US"><span style="word- wrap: break-word; "> </span></span><span style="word- wrap: break-word; text-indent: 28px; background- color: rgb(245, 247, 248); ">在允许的节点中,遍历满足要求的管理区</span>  
    50.     do {  
    51.         /* 
    52.          * In NUMA, this could be a policy zonelist which contains 
    53.          * zones that may not be allowed by the current gfp_mask. 
    54.          * Check the zone is allowed by the current flags 
    55.          */  
    56.         if (unlikely(alloc_should_filter_zonelist(zonelist))) {//根据zonelist->zlcache_ptr来确定是否需要过滤掉此内存区链表,关于过滤的条件还不是很清楚,请指教  
    57.             if (highest_zoneidx == -1)  
    58.                 highest_zoneidx = gfp_zone(gfp_mask);//gfp_zone用于指定分配内存的内存域  
    59.             if (zone_idx(*z) > highest_zoneidx)//首先考虑利用上面指定的内存域,对于一些分配代价高于指定内存域的内存域先不考虑  
    60.                 continue;  
    61.         }  
    62.   
    63.         if (NUMA_BUILD && zlc_active &&//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">是第一遍分配,在其他管理区中分配页面时需要考虑其页面是否充足</span>  
    64.             !zlc_zone_worth_trying(zonelist, z, allowednodes))//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">该管理区页面不是很充足,考虑下一个管理区</span>  
    65.                 continue;  
    66.         zone = *z;  
    67.         if ((alloc_flags & ALLOC_CPUSET) &&  
    68.             !cpuset_zone_allowed_softwall(zone, gfp_mask))//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">当前分配标志不允许在该管理区中分配页面</span>  
    69.                 goto try_next_zone;  
    70.   
    71.         if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">分配时需要考虑watermark</span>  
    72.             unsigned long mark;//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">根据分配标志,确定使用哪一个watermark</span>  
    73.             if (alloc_flags & ALLOC_WMARK_MIN)  
    74.                 mark = zone->pages_min;  
    75.             else if (alloc_flags & ALLOC_WMARK_LOW)  
    76.                 mark = zone->pages_low;  
    77.             else  
    78.                 mark = zone->pages_high;  
    79.             if (!zone_watermark_ok(zone, order, mark,  
    80.                     classzone_idx, alloc_flags)) {//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">该管理区的可用内存不可以满足本次分配的要求</span>  
    81.                 if (!zone_reclaim_mode ||//但不满足分配要求时,如果此内存域不能回收内存或者是回收不到可用内存时,就会跳转到this_zone_full  
    82.                     !zone_reclaim(zone, gfp_mask, order))  
    83.                     goto this_zone_full;  
    84.             }  
    85.         }  
    86.   
    87.         page = buffered_rmqueue(zonelist, zone, order, gfp_mask);//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">调用伙伴系统的分配函数</span>  
    88.         if (page)//<span style="word- wrap: break-word; text-indent: 28px; background- color: rgb(245, 247, 248); " lang="EN-US"><span style="word- wrap: break-word; "> </span></span><span style="word- wrap: break-word; text-indent: 28px; background- color: rgb(245, 247, 248); ">从伙伴系统分配成功,退出</span>  
    89.             break;  
    90. this_zone_full:  
    91.         if (NUMA_BUILD)  
    92.             zlc_mark_zone_full(zonelist, z);//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">标记该管理区空间不足,下次分配时将略过本管理区,避免浪费太多时间</span>  
    93. try_next_zone:  
    94.         if (NUMA_BUILD && !did_zlc_setup) {//<span style="text-indent: 28px; background-color: rgb(245, 247, 248); ">当前管理区内存不足,需要加大在其他区中的分配力度</span>  
    95.             /* we do zlc_setup after the first zone is tried */  
    96.             allowednodes = zlc_setup(zonelist, alloc_flags);  
    97.             zlc_active = 1;  
    98.             did_zlc_setup = 1;  
    99.         }  
    100.     } while (*(++z) != NULL);  
    101.   
    102.     if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {//<span style="word- wrap: break-word; text-indent: 28px; background- color: rgb(245, 247, 248); " lang="EN-US"><span style="word- wrap: break-word; "> </span></span><span style="word- wrap: break-word; text-indent: 28px; background- color: rgb(245, 247, 248); ">第一遍分配不成功,则取 消</span><span style="word-wrap: break-word; text- indent: 28px; background-color: rgb(245, 247, 248); " lang="EN-US">& lt;span style="word-wrap: break-word; ">zlc_active</span>< /span><span style="word-wrap: break-word; text- indent: 28px; background-color: rgb(245, 247, 248); ">,这样会尽量从其他节点中分配内 存</span>  
    103.         /* Disable zlc cache for second zonelist scan */  
    104.         zlc_active = 0;  
    105.         goto zonelist_scan;  
    106.     }  
    107.     return page;  
    108. }  
    109. </pre>  
    110. <p><span style="font-size:18px; color:#ff0000">关于上面一段代码中zlc_active的作用不明白,还望理解的人指点一下。</span></p>  
    111. <p></p>  
    112. <pre name="code" class="cpp">struct zonelist {  
    113.     struct zonelist_cache *zlcache_ptr;          // NULL or &zlcache  
    114.     struct zone *zones[MAX_ZONES_PER_ZONELIST + 1];      // NULL delimited  
    115. #ifdef CONFIG_NUMA  
    116.     struct zonelist_cache zlcache;               // optional ...  
    117. #endif  
    118. };</pre><br>  
    119. <pre name="code" class="cpp">struct zonelist_cache {  
    120.     unsigned short z_to_n[MAX_ZONES_PER_ZONELIST];      /* zone->nid */  
    121.     DECLARE_BITMAP(fullzones, MAX_ZONES_PER_ZONELIST);  /* zone full? */  
    122.     unsigned long last_full_zap;        /* when last zap'd (jiffies) */  
    123. };</pre><br>  
    124. <span style="font-size:18px">zone_watermark_ok源代码详细分析如下:</span><br>  
    125. <p></p>  
    126. <p></p>  
    127. <pre name="code" class="cpp">int zone_watermark_ok(struct zone *z, int order, unsigned long mark,  
    128.               int classzone_idx, int alloc_flags)  
    129. {  
    130.     /* free_pages my go negative - that's OK */  
    131.     long min = mark;  
    132.     long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;//zone_page_state用来访问每个内存域的统计量,在此处,得到的是空闲页的数目  
    133.     int o;  
    134.   
    135.     if (alloc_flags & ALLOC_HIGH)//设置了ALLOC_HIGH之后,将最小值标记减少一半  
    136.         min -= min / 2;  
    137.     if (alloc_flags & ALLOC_HARDER)//设置了ALLOC_HARDER之后,将最小值标记减少1/4  
    138.         min -= min / 4;  
    139.   
    140.     if (free_pages <= min + z->lowmem_reserve[classzone_idx])//检查空闲页的数目是否小于最小值与lowmem_reserve中制定的紧急分配值之和,如果小于则不进行内存分配  
    141.         return 0;  
    142.     for (o = 0; o < order; o++) {//如果不小于,则代码遍历所有小于当前阶的分配阶  
    143.         /* At the next order, this order's pages become unavailable */  
    144.         free_pages -= z->free_area[o].nr_free << o;//从free_pages减去当前分配阶的所有空闲页  
    145.   
    146.         /* Require fewer higher order pages to be free */  
    147.         min >>= 1;// 每升高一阶,所需空闲页的最小值减半,<span style="background- color: rgb(245, 247, 248); ">因为阶数越高,每一个块中包含的页面就越多。我们假设初始水线是2^n,那么对阶数0 来说,min的值就应当是2^n,对阶数为1来说,min的值就应当除以2变为2^(n-1),因为对于阶数1来说,每个块包含的页面数为 2</span>  
    148.   
    149.         if (free_pages <= min)//如果内核遍历所有的低端内存域之后,发现内存不足,则不进行内存分配  
    150.             return 0;  
    151.     }  
    152.     return 1;  
    153. }  
    154. </pre><span style="font-size:18px">buffered_rmqueue源代码详细分析如下:</span>  
    155. <p></p>  
    156. <p></p>  
    157. <pre name="code" class="cpp">static struct page *buffered_rmqueue(struct zonelist *zonelist,  
    158.             struct zone *zone, int order, gfp_t gfp_flags)  
    159. {  
    160.     unsigned long flags;  
    161.     struct page *page;  
    162.     int cold = !!(gfp_flags & __GFP_COLD);//如果分配参数指定了__GFP_COLD标志,则设置cold标志,两次取反操作确保cold是0或者1,why?请指教  
    163.     int cpu;  
    164.     int migratetype = allocflags_to_migratetype(gfp_flags);//根据gfp_flags获得迁移类型  
    165.   
    166. again:  
    167.     cpu  = get_cpu();//获取本CPU  
    168.     if (likely(order == 0)) {//分配单页,需要管理每CPU页面缓存  
    169.         struct per_cpu_pages *pcp;  
    170.   
    171.         pcp = &zone_pcp(zone, cpu)->pcp[cold];//取得本CPU的页面缓存对象  
    172.         local_irq_save(flags);//这里需要关中断,因为内存回收过程可能发送核间中断,强制每个核从每CPU缓存中释放页面。而且中断处理函数也会分配单页。  
    173.         if (!pcp->count) {//缓存为空,需要扩大缓存的大小  
    174.             pcp->count = rmqueue_bulk(zone, 0,  
    175.                     pcp->batch, &pcp->list, migratetype);//从伙伴系统中摘除一批页面到缓存中,补充的页面个数由每CPU缓存的batch字段指定  
    176.             if (unlikely(!pcp->count))//如果缓存仍然为空,那么说明伙伴系统中页面也没有了,分配失败  
    177.                 goto failed;  
    178.         }  
    179.   
    180.         /* Find a page of the appropriate migrate type */  
    181.         list_for_each_entry(page, &pcp->list, lru)//遍历每CPU缓存中的所有页,检查是否有指定类型的迁移类型的页可用  
    182.             if (page_private(page) == migratetype)  
    183.                 break;  
    184.   
    185.         /* Allocate more to the pcp list if necessary */  
    186.         if (unlikely(&page->lru == &pcp->list)) {  
    187.             pcp->count += rmqueue_bulk(zone, 0,  
    188.                     pcp->batch, &pcp->list, migratetype);  
    189.             page = list_entry(pcp->list.next, struct page, lru);  
    190.         }  
    191.   
    192.         list_del(&page->lru);//将页面从每CPU缓存链表中取出,并将每CPU缓存计数减1  
    193.         pcp->count--;  
    194.     } else {  
    195.         spin_lock_irqsave(&zone->lock, flags);  
    196.         page = __rmqueue(zone, order, migratetype);  
    197.         spin_unlock(&zone->lock);  
    198.         if (!page)  
    199.             goto failed;  
    200.     }  
    201.   
    202.     __count_zone_vm_events(PGALLOC, zone, 1 << order);  
    203.     zone_statistics(zonelist, zone);  
    204.     local_irq_restore(flags);  
    205.     put_cpu();  
    206.   
    207.     VM_BUG_ON(bad_range(zone, page));  
    208.     if (prep_new_page(page, order, gfp_flags))  
    209.         goto again;  
    210.     return page;  
    211.   
    212. failed:  
    213.     local_irq_restore(flags);  
    214.     put_cpu();  
    215.     return NULL;  
    216. }</pre><span style="color:rgb(255,0,0); font-family:Arial; font-size:18px; line-height:26px"> 我也知道有很多的细节都没有分析到位,但是我也没有办法,曾经想着把里面涉及到的每一个函数都分析到位,但是那样的话自己相当的痛苦,因为那样的结果就是 很多天都没有办法前进一点,会让人相当的有挫败感,最后只能选择大概先都过一遍,因为自己是一个内核的初学者,而内核前后的关联又很大,也只能先过一遍, 到后面我会重新回来看我写得博客,能增进一些分析就增进一些分析。如果您认为上面确实有很重要的地方我没有分析到,希望您指 点。</span><br>  
    217. <br>  
    218. <br>  
    219. <p></p>  
    220. <br>  
    221. <p></p>  
    222. <p><br>  
    223. </p>  
    224. <br>  
    225. <br>  
    226. <br>  
    227. <br>  
    228. <br>  
    229. <br>  
    230. <br>  
    231. <br>  
    232. <br>  
    233. <p></p> 

    转载于:https://my.oschina.net/u/174242/blog/76832

    展开全文
  • linux内存伙伴算法(三:分配页)

    千次阅读 2012-09-04 11:20:53
    伙伴系统中用于分配页的函数如下: alloc_pages(mask,order)分配2^order页并返回一个struct page的实例,表示分配的内存块的起始页。alloc_page(mask)是前者在order=0情况下的简化形式,只分配一页。 get_zeroed_...

    伙伴系统中用于分配页的函数如下:

    alloc_pages(mask,order)分配2^order页并返回一个struct page的实例,表示分配的内存块的起始页。alloc_page(mask)是前者在order=0情况下的简化形式,只分配一页。

    get_zeroed_page(mask)分配一页并返回一个page实例,页对应的内存填充0(所有其他函数分配之后的内容是未定义的)。

    __get_free_pages(mask,order)和__get_free_page(mask)的工作方式与上述函数相同,但返回分配内存块的虚拟地址,而不是page实例。

    get_dma_pages(gfp_mask,order)用来获得适用于DMA的页。

    在空闲内存无法满足请求以至于分配失败的情况下,所有上述函数都返回空指针(alloc_pages和alloc_page)或者0(get_zeroed_page、__get_free_pages和__get_free_page)。因此内核在各次分配之后必须检查返回的结果。这种惯例与设计得很好的用户层应用程序没有什么不同,但在内核中忽略检查将会导致严重得多的故障。

    前述所有函数中使用的mask参数的语义是什么?linux将内核划分为内存域,内核提供了所谓的内存域修饰符,来指定从哪个内存域分配所需的页。

    #define __GFP_DMA	((__force gfp_t)0x01u)
    #define __GFP_HIGHMEM	((__force gfp_t)0x02u)
    #define __GFP_DMA32	((__force gfp_t)0x04u)
    
    除了内存域修饰符之外,掩码中还可以设置一些标志,这些额外的标志并不限制从哪个物理内存段分配内存,但确实可以改变分配器的行为。

    #define __GFP_WAIT	((__force gfp_t)0x10u)	//表示分配内存的请求可以中断。也就是说,调度器在该请求期间可随意选择另一个过程执行,或者该请求可以被另一个更重要的事件中断。
    #define __GFP_HIGH	((__force gfp_t)0x20u)	//如果请求非常重要,则设置__GFP_HIGH,即内核急切的需要内存时。在分配内存失败可能给内核带来严重得后果时,一般会设置该标志
    #define __GFP_IO	((__force gfp_t)0x40u)	//在查找空闲内存期间内核可以进行I/O操作。这意味着如果内核在内存分配期间换出页,那么仅当设置该标志时,才能将选择的页写入磁盘。
    #define __GFP_FS	((__force gfp_t)0x80u)	//允许内核执行VFS操作
    #define __GFP_COLD	((__force gfp_t)0x100u)	//如果需要分配不在CPU高速缓存中的“冷”页时,则设置__GFP_COLD。
    #define __GFP_NOWARN	((__force gfp_t)0x200u)	//在分配失败时禁止内核故障警告。
    #define __GFP_REPEAT	((__force gfp_t)0x400u)	//在分配失败后自动重试,但在尝试若干次之后会停止。
    #define __GFP_NOFAIL	((__force gfp_t)0x800u)	//在分配失败后一直重试,直至成功。
    #define __GFP_NORETRY	((__force gfp_t)0x1000u)//不重试,可能失败
    #define __GFP_COMP	((__force gfp_t)0x4000u)//增加复合页元数据
    #define __GFP_ZERO	((__force gfp_t)0x8000u)//在分配成功时,将返回填充字节0的页。
    #define __GFP_NOMEMALLOC ((__force gfp_t)0x10000u) //不适用紧急分配链表
    #define __GFP_HARDWALL   ((__force gfp_t)0x20000u) //只在NUMA系统上有意义。它限制只在分配到当前进程的各个CPU所关联的结点分配内存。如果进程允许在所有的CPU上运行(默认情况下),该标志是没有意义的。只有进程可以运行的CPU受限时,该标志才有意义。
    #define __GFP_THISNODE	((__force gfp_t)0x40000u)//页只在NUMA系统上有意义,如果设置该比特位,则内存分配失败的情况下不允许使用其他结点作为备用,需要保证在当前结点或者明确指定的结点上成功分配内存。
    #define __GFP_RECLAIMABLE ((__force gfp_t)0x80000u) //将分配的内存标记为可回收
    #define __GFP_MOVABLE	((__force gfp_t)0x100000u)  //将分配的内存标记为可移动
    
    #define __GFP_BITS_SHIFT 21	/* Room for 21 __GFP_FOO bits */
    #define __GFP_BITS_MASK ((__force gfp_t)((1 << __GFP_BITS_SHIFT) - 1))
    
    /* This equals 0, but use constants in case they ever change */
    #define GFP_NOWAIT	(GFP_ATOMIC & ~__GFP_HIGH)
    由于这些标志总是组合使用,内核做了一些分组,包含了用于各种标准情形的适当地标志。

    #define GFP_ATOMIC	(__GFP_HIGH)//用于原子分配,在任何情况下都不能中断,可能使用紧急分配链表中的内存
    #define GFP_NOIO	(__GFP_WAIT)//明确禁止IO操作,但可以被中断
    #define GFP_NOFS	(__GFP_WAIT | __GFP_IO)//明确禁止访问VFS层操作,但可以被中断
    #define GFP_KERNEL	(__GFP_WAIT | __GFP_IO | __GFP_FS)//内核分配的默认配置
    #define GFP_TEMPORARY	(__GFP_WAIT | __GFP_IO | __GFP_FS | \
    			 __GFP_RECLAIMABLE)
    #define GFP_USER	(__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL)//用户分配的默认配置
    #define GFP_HIGHUSER	(__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL | \
    			 __GFP_HIGHMEM)//是GFP_USER的一个扩展,页用于用户空间,它允许分配无法直接映射的高端内存,使用高端内存页是没有坏处的,因为用户过程的地址空间总是通过非线性页表组织的
    #define GFP_HIGHUSER_MOVABLE	(__GFP_WAIT | __GFP_IO | __GFP_FS | \
    				 __GFP_HARDWALL | __GFP_HIGHMEM | \
    				 __GFP_MOVABLE)//类似于GFP_HIGHUSER,但分配是在虚拟内存域ZONE_MOVABLE中进行
    #define GFP_NOFS_PAGECACHE	(__GFP_WAIT | __GFP_IO | __GFP_MOVABLE)
    #define GFP_USER_PAGECACHE	(__GFP_WAIT | __GFP_IO | __GFP_FS | \
    				 __GFP_HARDWALL | __GFP_MOVABLE)
    #define GFP_HIGHUSER_PAGECACHE	(__GFP_WAIT | __GFP_IO | __GFP_FS | \
    				 __GFP_HARDWALL | __GFP_HIGHMEM | \
    				 __GFP_MOVABLE)
    
    #ifdef CONFIG_NUMA
    #define GFP_THISNODE	(__GFP_THISNODE | __GFP_NOWARN | __GFP_NORETRY)
    #else
    #define GFP_THISNODE	((__force gfp_t)0)
    #endif
    
    /* This mask makes up all the page movable related flags */
    #define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE)
    
    /* Control page allocator reclaim behavior */
    #define GFP_RECLAIM_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS|\
    			__GFP_NOWARN|__GFP_REPEAT|__GFP_NOFAIL|\
    			__GFP_NORETRY|__GFP_NOMEMALLOC)
    
    /* Control allocation constraints */
    #define GFP_CONSTRAINT_MASK (__GFP_HARDWALL|__GFP_THISNODE)
    
    /* Do not use these with a slab allocator */
    #define GFP_SLAB_BUG_MASK (__GFP_DMA32|__GFP_HIGHMEM|~__GFP_BITS_MASK)
    
    /* Flag - indicates that the buffer will be suitable for DMA.  Ignored on some
       platforms, used as appropriate on others */
    
    #define GFP_DMA		__GFP_DMA
    
    /* 4GB DMA on some platforms */
    #define GFP_DMA32	__GFP_DMA32
    #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)
    #define __get_free_page(gfp_mask) \
    		__get_free_pages((gfp_mask),0)
    #define __get_dma_pages(gfp_mask, order) \
    		__get_free_pages((gfp_mask) | GFP_DMA,(order))
    fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
    {
    	struct page * page;
    	page = alloc_pages(gfp_mask, order);
    	if (!page)
    		return 0;
    	return (unsigned long) page_address(page);
    }
    #define alloc_pages(gfp_mask, order) \
    		alloc_pages_node(numa_node_id(), gfp_mask, order)
    根据上面的代码,可以得出各个分配函数之间的关系如下图所示:


    主要的函数是alloc_pages_node。alloc_pages_node源代码的详细分析如下:

    static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
    						unsigned int order)
    {
    	if (unlikely(order >= MAX_ORDER))//执行一个检查,避免分配过大的内存块
    		return NULL;
    
    	/* Unknown node is current node */
    	if (nid < 0)//如果指定负的结点ID(不存在),内核自动地使用当前执行CPU对应的结点ID。
    		nid = numa_node_id();
    
    	return __alloc_pages(gfp_mask, order,
    		NODE_DATA(nid)->node_zonelists + gfp_zone(gfp_mask));//接下来的工作委托给__alloc_pages,只需传递一组适当地参数,请注意,gfp_zone用于选择分配内存的内存域。
    }

    static inline enum zone_type gfp_zone(gfp_t flags)//本函数比较好理解,就是根据指定的标志确定内存域
    {
    	int base = 0;
    
    #ifdef CONFIG_NUMA
    	if (flags & __GFP_THISNODE)
    		base = MAX_NR_ZONES;
    #endif
    
    #ifdef CONFIG_ZONE_DMA
    	if (flags & __GFP_DMA)
    		return base + ZONE_DMA;
    #endif
    #ifdef CONFIG_ZONE_DMA32
    	if (flags & __GFP_DMA32)
    		return base + ZONE_DMA32;
    #endif
    	if ((flags & (__GFP_HIGHMEM | __GFP_MOVABLE)) ==
    			(__GFP_HIGHMEM | __GFP_MOVABLE))
    		return base + ZONE_MOVABLE;
    #ifdef CONFIG_HIGHMEM
    	if (flags & __GFP_HIGHMEM)
    		return base + ZONE_HIGHMEM;
    #endif
    	return base + ZONE_NORMAL;
    }

    __alloc_pages源代码详细分析如下:

    __alloc_pages(gfp_t gfp_mask, unsigned int order,
    		struct zonelist *zonelist)//gfp_mask是一些标志位,用来制定如何寻找空闲页框,order用来表示所需物理块的大小,从空闲链表中获取2^order页内存,在管理区链表zonelist中依次查找每个区,从中找到满足要求的区
    {
    	const gfp_t wait = gfp_mask & __GFP_WAIT;//gfp_mask是申请内存时用到的控制字,这一句就是为了检测我们的控制字里面是否有__GPF_WAIT这个属性
    	struct zone **z;//管理区结构体
    	struct page *page;
    	struct reclaim_state reclaim_state;
    	struct task_struct *p = current;
    	int do_retry;
    	int alloc_flags;
    	int did_some_progress;
    
    	might_sleep_if(wait);//如果在gfp_mask中设置了__GFP_WAIT位,表明内核可以阻塞当前进程,来等待空闲页面。在分配开始之前即阻塞,目的是为了等待其它进程释放更多的页面
    
    	if (should_fail_alloc_page(gfp_mask, order))//通过简单算法在真正分配前检查分配是否会失败,避免进入真正的分配程序后浪费系统时间
    		return NULL;
    
    restart:
    	z = zonelist->zones;//zonelist是struct node中的一个成员,它表示系统内所有normal内存页区的连接链表,首先让z指向第一个管理区
    
    	if (unlikely(*z == NULL)) {//如果发现头指针为空,即没有指向struct zone的有效指针,我们就直接返回错误
    		/*
    		 * Happens if we have an empty zonelist as a result of
    		 * GFP_THISNODE being used on a memoryless node
    		 */
    		return NULL;
    	}
    
    	page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
    				zonelist,ALLOC_WMARK_LOW|ALLOC_CPUSET);
    //get_page_from_freelist以指定的watermark来分配页面。每个zone struct中定义了三个watermark:pages_min, pages_low, pages_high,表示zone中应保持的空闲页面的阈值。get_page_from_freelist函数通过设置Alloc flags来选择watermark。
    	if (page)//首先以pages_low watermark分配页面,如果分配成功,则跳转到got_pg
    		goto got_pg;
    
    	/*
    	 * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
    	 * __GFP_NOWARN set) should not cause reclaim since the subsystem
    	 * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
    	 * using a larger set of nodes after it has established that the
    	 * allowed per node queues are empty and that nodes are
    	 * over allocated.
    	 */
    	if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)//如果pages_low watermark分配失败的话,检查gfp_mask,如果GFP_THISNODE标志被设置,表明不能重试,因此跳转到nopage,返回失败goto nopage
    		goto nopage;
    
    	for (z = zonelist->zones; *z; z++)//否则调用kswapd对zonelist中的所有zone进行页面回收,期待能将一些闲置页面交换到文件系统中
    		wakeup_kswapd(*z, order);
    
    	/*
    	 * OK, we're below the kswapd watermark and have kicked background
    	 * reclaim. Now things get more complex, so set up alloc_flags according
    	 * to how we want to proceed.
    	 *
    	 * The caller may dip into page reserves a bit more if the caller
    	 * cannot run direct reclaim, or if the caller has realtime scheduling
    	 * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
    	 * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
    	 */
    	alloc_flags = ALLOC_WMARK_MIN;//设置alloc_flags的值,以page_min watermark来分配内存
    	if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)//假若进程是非中断处理程序的实时进程,或者该进程不能被阻塞,那么这个时候,我要在最低阈值的标准的基础上,再次降低阈值
    		alloc_flags |= ALLOC_HARDER;
    	if (gfp_mask & __GFP_HIGH))//允许使用保留页面
    		alloc_flags |= ALLOC_HIGH;
    	if (wait)
    		alloc_flags |= ALLOC_CPUSET;
    
    	/*
    	 * Go through the zonelist again. Let __GFP_HIGH and allocations
    	 * coming from realtime tasks go deeper into reserves.
    	 *
    	 * This is the last chance, in general, before the goto nopage.
    	 * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
    	 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
    	 */
    	page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);//以指定的watermark来分配页面,详细讨论见下文
    	if (page)//分配成功,就进入got_pg
    		goto got_pg;
    
    	/* This allocation should allow future memory freeing. */
    
    rebalance://上面的第二次分配失败
    	if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
    			&& !in_interrupt()) {//如果当前进程允许本次申请的内存可以被释放,并且不处于软硬中断的状态,我们不顾忌必须保留最小空闲内存页,强行分配
    		if (!(gfp_mask & __GFP_NOMEMALLOC)) {//如果gfp_mask设置不需要保留紧急内存区域,以不设watermark再次分配页面
    nofail_alloc:
    			/* go through the zonelist yet again, ignoring mins */
    			page = get_page_from_freelist(gfp_mask, order,
    				zonelist, ALLOC_NO_WATERMARKS);//以不设watermark进行第三次分配
    			if (page)//第三次分配成功
    				goto got_pg;
    			if (gfp_mask & __GFP_NOFAIL) {//第三次分配失败,如果gfp_mask设置了__GFP_NOFAIL,则不断重试,直到分配成功
    				congestion_wait(WRITE, HZ/50);
    				goto nofail_alloc;
    			}
    		}
    		goto nopage;
    	}
    
    	/* Atomic allocations - we can't balance anything */
    	if (!wait)//原子分配,不允许阻塞,则只能返回失败信号,分配失败
    		goto nopage;
    
    	cond_resched();//重新调度之后,试图释放一些不常用的页面
    
    	/* We now go into synchronous reclaim */
    	cpuset_memory_pressure_bump();//开始进行同步内存回收
    	p->flags |= PF_MEMALLOC;//进程的标志位设置为PF_MEMALLOC
    	reclaim_state.reclaimed_slab = 0;//对于不再活跃的SLAB也给回收掉
    	p->reclaim_state = &reclaim_state;//改变进程回收的状态
    
    	did_some_progress = try_to_free_pages(zonelist->zones, order, gfp_mask);//该函数选择最近不十分活跃的页,将其写到交换区,在物理内存中腾出空间
    
    	p->reclaim_state = NULL;
    	p->flags &= ~PF_MEMALLOC;
    
    	cond_resched();
    
    	if (order != 0)
    		drain_all_local_pages();
    
    	if (likely(did_some_progress)) {//调度之后,如果确实释放了一部分页面,则重新分配页面
    		page = get_page_from_freelist(gfp_mask, order,
    						zonelist, alloc_flags);
    		if (page)
    			goto got_pg;
    	} else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {//如果内核可能执行影响VFS层的调用而又没有设置GFP_NORETRY,那么调用OOM killer
    		if (!try_set_zone_oom(zonelist)) {
    			schedule_timeout_uninterruptible(1);
    			goto restart;
    		}
    
    		/*
    		 * Go through the zonelist yet one more time, keep
    		 * very high watermark here, this is only to catch
    		 * a parallel oom killing, we must fail if we're still
    		 * under heavy pressure.
    		 */
    		page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
    				zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);
    		if (page) {
    			clear_zonelist_oom(zonelist);
    			goto got_pg;
    		}
    
    		/* The OOM killer will not help higher order allocs so fail */
    		if (order > PAGE_ALLOC_COSTLY_ORDER) {//杀死一个进程未必立即出现多余2^PAGE_ALLOC_CODTLY_ORDER页的连续内存区,因此如果当前要分配如此大的内存区,那么内核会饶恕所选择的进程,不执行杀死进程的任务,而是承认失败并跳转到nopage
    			clear_zonelist_oom(zonelist);
    			goto nopage;
    		}
    
    		out_of_memory(zonelist, gfp_mask, order);//选择一个内核认为犯有分配过多内存“罪行”的进程,并杀死该进程。这有很大几率腾出较多的空闲页,然后跳转到标号restart,重试分配内存的操作
    		clear_zonelist_oom(zonelist);
    		goto restart;
    	}
    
    	/*
    	 * Don't let big-order allocations loop unless the caller explicitly
    	 * requests that.  Wait for some write requests to complete then retry.
    	 *
    	 * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
    	 * <= 3, but that may not be true in other implementations.
    	 */
    	//如果设置了__GFP_NORETRY,或内核不允许可能影响VFS层的操作
    	do_retry = 0;
    	if (!(gfp_mask & __GFP_NORETRY)) {//没有设置__GFP_NORETRY
    		if ((order <= PAGE_ALLOC_COSTLY_ORDER) ||
    						(gfp_mask & __GFP_REPEAT))//如果分配长度小于2^PAGE_ALLOC_COSTLY_ORDER或设置了__GFP_REPEAT,则内核进入无限循环
    			do_retry = 1;
    		if (gfp_mask & __GFP_NOFAIL)//如果设置了不允许分配失败,内核也会进入无限循环
    			do_retry = 1;
    	}
    	if (do_retry) {
    		congestion_wait(WRITE, HZ/50);
    		goto rebalance;
    	}
    
    nopage:
    	if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
    		printk(KERN_WARNING "%s: page allocation failure."
    			" order:%d, mode:0x%x\n",
    			p->comm, order, gfp_mask);
    		dump_stack();
    		show_mem();
    	}
    got_pg:
    	return page;
    }

    get_page_from_freelist源代码的详细分析如下:

    static struct page *
    get_page_from_freelist(gfp_t gfp_mask, unsigned int order,
    		struct zonelist *zonelist, int alloc_flags)
    {
    	struct zone **z;//管理区结构体
    	struct page *page = NULL;
    	int classzone_idx = zone_idx(zonelist->zones[0]);//#define zone_idx(zone)        ((zone) - (zone)->zone_pgdat->node_zones) 获取管理区的编号
    	struct zone *zone;
    	nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
    	int zlc_active = 0;		/* set if using zonelist_cache */
    	int did_zlc_setup = 0;		/* just call zlc_setup() one time */
    	enum zone_type highest_zoneidx = -1; /* Gets set for policy zonelists */
    
    zonelist_scan:
    	/*
    	 * Scan zonelist, looking for a zone with enough free.
    	 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
    	 */
    	z = zonelist->zones;//让z指向第一个管理区
    	// 在允许的节点中,遍历满足要求的管理区
    	do {
    		/*
    		 * In NUMA, this could be a policy zonelist which contains
    		 * zones that may not be allowed by the current gfp_mask.
    		 * Check the zone is allowed by the current flags
    		 */
    		if (unlikely(alloc_should_filter_zonelist(zonelist))) {//根据zonelist->zlcache_ptr来确定是否需要过滤掉此内存区链表,关于过滤的条件还不是很清楚,请指教
    			if (highest_zoneidx == -1)
    				highest_zoneidx = gfp_zone(gfp_mask);//gfp_zone用于指定分配内存的内存域
    			if (zone_idx(*z) > highest_zoneidx)//首先考虑利用上面指定的内存域,对于一些分配代价高于指定内存域的内存域先不考虑
    				continue;
    		}
    
    		if (NUMA_BUILD && zlc_active &&//是第一遍分配,在其他管理区中分配页面时需要考虑其页面是否充足
    			!zlc_zone_worth_trying(zonelist, z, allowednodes))//该管理区页面不是很充足,考虑下一个管理区
    				continue;
    		zone = *z;
    		if ((alloc_flags & ALLOC_CPUSET) &&
    			!cpuset_zone_allowed_softwall(zone, gfp_mask))//当前分配标志不允许在该管理区中分配页面
    				goto try_next_zone;
    
    		if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {//分配时需要考虑watermark
    			unsigned long mark;//根据分配标志,确定使用哪一个watermark
    			if (alloc_flags & ALLOC_WMARK_MIN)
    				mark = zone->pages_min;
    			else if (alloc_flags & ALLOC_WMARK_LOW)
    				mark = zone->pages_low;
    			else
    				mark = zone->pages_high;
    			if (!zone_watermark_ok(zone, order, mark,
    				    classzone_idx, alloc_flags)) {//该管理区的可用内存不可以满足本次分配的要求
    				if (!zone_reclaim_mode ||//但不满足分配要求时,如果此内存域不能回收内存或者是回收不到可用内存时,就会跳转到this_zone_full
    				    !zone_reclaim(zone, gfp_mask, order))
    					goto this_zone_full;
    			}
    		}
    
    		page = buffered_rmqueue(zonelist, zone, order, gfp_mask);//调用伙伴系统的分配函数
    		if (page)// 从伙伴系统分配成功,退出
    			break;
    this_zone_full:
    		if (NUMA_BUILD)
    			zlc_mark_zone_full(zonelist, z);//标记该管理区空间不足,下次分配时将略过本管理区,避免浪费太多时间
    try_next_zone:
    		if (NUMA_BUILD && !did_zlc_setup) {//当前管理区内存不足,需要加大在其他区中的分配力度
    			/* we do zlc_setup after the first zone is tried */
    			allowednodes = zlc_setup(zonelist, alloc_flags);
    			zlc_active = 1;
    			did_zlc_setup = 1;
    		}
    	} while (*(++z) != NULL);
    
    	if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {// 第一遍分配不成功,则取消zlc_active,这样会尽量从其他节点中分配内存
    		/* Disable zlc cache for second zonelist scan */
    		zlc_active = 0;
    		goto zonelist_scan;
    	}
    	return page;
    }

    关于上面一段代码中zlc_active的作用不明白,还望理解的人指点一下。

    struct zonelist {
    	struct zonelist_cache *zlcache_ptr;		     // NULL or &zlcache
    	struct zone *zones[MAX_ZONES_PER_ZONELIST + 1];      // NULL delimited
    #ifdef CONFIG_NUMA
    	struct zonelist_cache zlcache;			     // optional ...
    #endif
    };

    struct zonelist_cache {
    	unsigned short z_to_n[MAX_ZONES_PER_ZONELIST];		/* zone->nid */
    	DECLARE_BITMAP(fullzones, MAX_ZONES_PER_ZONELIST);	/* zone full? */
    	unsigned long last_full_zap;		/* when last zap'd (jiffies) */
    };

    zone_watermark_ok源代码详细分析如下:

    int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
    		      int classzone_idx, int alloc_flags)
    {
    	/* free_pages my go negative - that's OK */
    	long min = mark;
    	long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;//zone_page_state用来访问每个内存域的统计量,在此处,得到的是空闲页的数目
    	int o;
    
    	if (alloc_flags & ALLOC_HIGH)//设置了ALLOC_HIGH之后,将最小值标记减少一半
    		min -= min / 2;
    	if (alloc_flags & ALLOC_HARDER)//设置了ALLOC_HARDER之后,将最小值标记减少1/4
    		min -= min / 4;
    
    	if (free_pages <= min + z->lowmem_reserve[classzone_idx])//检查空闲页的数目是否小于最小值与lowmem_reserve中制定的紧急分配值之和,如果小于则不进行内存分配
    		return 0;
    	for (o = 0; o < order; o++) {//如果不小于,则代码遍历所有小于当前阶的分配阶
    		/* At the next order, this order's pages become unavailable */
    		free_pages -= z->free_area[o].nr_free << o;//从free_pages减去当前分配阶的所有空闲页
    
    		/* Require fewer higher order pages to be free */
    		min >>= 1;//每升高一阶,所需空闲页的最小值减半,因为阶数越高,每一个块中包含的页面就越多。我们假设初始水线是2^n,那么对阶数0来说,min的值就应当是2^n,对阶数为1来说,min的值就应当除以2变为2^(n-1),因为对于阶数1来说,每个块包含的页面数为2
    
    		if (free_pages <= min)//如果内核遍历所有的低端内存域之后,发现内存不足,则不进行内存分配
    			return 0;
    	}
    	return 1;
    }

    buffered_rmqueue源代码详细分析如下:

    static struct page *buffered_rmqueue(struct zonelist *zonelist,
    			struct zone *zone, int order, gfp_t gfp_flags)
    {
    	unsigned long flags;
    	struct page *page;
    	int cold = !!(gfp_flags & __GFP_COLD);//如果分配参数指定了__GFP_COLD标志,则设置cold标志,两次取反操作确保cold是0或者1,why?请指教
    	int cpu;
    	int migratetype = allocflags_to_migratetype(gfp_flags);//根据gfp_flags获得迁移类型
    
    again:
    	cpu  = get_cpu();//获取本CPU
    	if (likely(order == 0)) {//分配单页,需要管理每CPU页面缓存
    		struct per_cpu_pages *pcp;
    
    		pcp = &zone_pcp(zone, cpu)->pcp[cold];//取得本CPU的页面缓存对象
    		local_irq_save(flags);//这里需要关中断,因为内存回收过程可能发送核间中断,强制每个核从每CPU缓存中释放页面。而且中断处理函数也会分配单页。
    		if (!pcp->count) {//缓存为空,需要扩大缓存的大小
    			pcp->count = rmqueue_bulk(zone, 0,
    					pcp->batch, &pcp->list, migratetype);//从伙伴系统中摘除一批页面到缓存中,补充的页面个数由每CPU缓存的batch字段指定
    			if (unlikely(!pcp->count))//如果缓存仍然为空,那么说明伙伴系统中页面也没有了,分配失败
    				goto failed;
    		}
    
    		/* Find a page of the appropriate migrate type */
    		list_for_each_entry(page, &pcp->list, lru)//遍历每CPU缓存中的所有页,检查是否有指定类型的迁移类型的页可用
    			if (page_private(page) == migratetype)
    				break;
    
    		/* Allocate more to the pcp list if necessary */
    		if (unlikely(&page->lru == &pcp->list)) {
    			pcp->count += rmqueue_bulk(zone, 0,
    					pcp->batch, &pcp->list, migratetype);
    			page = list_entry(pcp->list.next, struct page, lru);
    		}
    
    		list_del(&page->lru);//将页面从每CPU缓存链表中取出,并将每CPU缓存计数减1
    		pcp->count--;
    	} else {
    		spin_lock_irqsave(&zone->lock, flags);
    		page = __rmqueue(zone, order, migratetype);
    		spin_unlock(&zone->lock);
    		if (!page)
    			goto failed;
    	}
    
    	__count_zone_vm_events(PGALLOC, zone, 1 << order);
    	zone_statistics(zonelist, zone);
    	local_irq_restore(flags);
    	put_cpu();
    
    	VM_BUG_ON(bad_range(zone, page));
    	if (prep_new_page(page, order, gfp_flags))
    		goto again;
    	return page;
    
    failed:
    	local_irq_restore(flags);
    	put_cpu();
    	return NULL;
    }

    我也知道有很多的细节都没有分析到位,但是我也没有办法,曾经想着把里面涉及到的每一个函数都分析到位,但是那样的话自己相当的痛苦,因为那样的结果就是很多天都没有办法前进一点,会让人相当的有挫败感,最后只能选择大概先都过一遍,因为自己是一个内核的初学者,而内核前后的关联又很大,也只能先过一遍,到后面我会重新回来看我写得博客,能增进一些分析就增进一些分析。如果您认为上面确实有很重要的地方我没有分析到,希望您指点。





    展开全文
  • linux内存伙伴算法(四:释放页)

    千次阅读 2012-09-07 10:43:31
    if (reserved)//如果在需要释放的一段内存中有需要保留的内存页,那么该段内存就不能释放 return; if (!PageHighMem(page))//判断页是否在高端内存域中 debug_check_no_locks_freed(page_address(page),PAGE_...

    __free_pages源代码详细分析如下:

    fastcall void __free_pages(struct page *page, unsigned int order)
    {
    	if (put_page_testzero(page)) {//一般来说,只有当页面的引用计数变为0时,才会释放该页,此处进行页面引用计数的判断
    		if (order == 0)//如果是释放单个页面,则释放到管理区的每CPU页面缓存中,以加快单页分配速度
    			free_hot_page(page);
    		else
    			__free_pages_ok(page, order);//否则直接释放到伙伴系统中 
    	}
    }
    void fastcall free_hot_page(struct page *page)
    {
    	free_hot_cold_page(page, 0);
    }
    free_hot_cold_page源代码详细分析如下:
    
    static void fastcall free_hot_cold_page(struct page *page, int cold)
    {
    	struct zone *zone = page_zone(page);//找到页面所属的管理区
    	struct per_cpu_pages *pcp;//为等下访问冷热区做准备,pcp是一个中间变量
    	unsigned long flags;
    
    	if (PageAnon(page))//说明page->mapping的第0位是1,说明该页是匿名页
    		page->mapping = NULL;//则使page->mapping指向NULL
    	if (free_pages_check(page))//这个函数就是检测page的flag和mapping,_count,_mapcount这几个成员,如果有误,就会进行相应的处理
    		return;
    
    	if (!PageHighMem(page))//如果该内存页不在高端内存域
    		debug_check_no_locks_freed(page_address(page), PAGE_SIZE);//则调试相关代码
    	arch_free_page(page, 0);//只有配置了HAVE_ARCH_FREE_PAGE才会起作用
    	kernel_map_pages(page, 1, 0);
    
    	pcp = &zone_pcp(zone, get_cpu())->pcp[cold];//获得本页区的当前cpu,然后找到对应的热区的高速缓存内存,用pcp指针指向它
    	local_irq_save(flags);//禁止irq中断
    	__count_vm_event(PGFREE);//统计本CPU上的页面释放次数
    	list_add(&page->lru, &pcp->list);//把page的lru挂在pcp->list上,挂在pcp->list前面
    	set_page_private(page, get_pageblock_migratetype(page));//获取页面的迁移类型,并将其保存在page->private中
    	pcp->count++;//更新当前CPU页面缓存计数
    	if (pcp->count >= pcp->high) {//页面缓存中保留的页面太多,超过上限了
    		free_pages_bulk(zone, pcp->batch, &pcp->list, 0);//将页面缓存中的页面释放一部分到伙伴系统中
    		pcp->count -= pcp->batch;//更新当前CPU中页面缓存计数
    	}
    	local_irq_restore(flags);//恢复中断
    	put_cpu();//preempt_enable()是抢占使能
    }
    
    free_pages_bulk源代码详细分析如下:
    static void free_pages_bulk(struct zone *zone, int count,
    					struct list_head *list, int order)
    {
    	spin_lock(&zone->lock);//上锁
    	zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);//在释放页之前,先将内存区中页不可回收的标志清除
    	zone->pages_scanned = 0;//在上一次成功换出页之后,已扫描页计数器
    	while (count--) {//循环,直到把count个页面全部释放
    		struct page *page;
    
    		VM_BUG_ON(list_empty(list));
    		page = list_entry(list->prev, struct page, lru);//通过pcp->list找到第一个lru,再通过lru成员找到对应的struct page
    		/* have to delete it as __free_one_page list manipulates */
    		list_del(&page->lru);//lru取出后,pcp->list链表就不再指向它了,就要从链表里面移除
    		__free_one_page(page, zone, order);//这是释放函数的主体,下面会详细讨论
    	}
    	spin_unlock(&zone->lock);//解锁
    }
    
    _free_pages_ok源代码详细分析如下:
    static void __free_pages_ok(struct page *page, unsigned int order)
    {
    	unsigned long flags;
    	int i;
    	int reserved = 0;
    
    	for (i = 0 ; i < (1 << order) ; ++i)
    		reserved += free_pages_check(page + i);//在释放页之前,还得先用free_pages_check函数检查页是否有错误,如果有错误就要进行相应的处理,如果没有错误,还需要记录所有页面中需要保留的页面数
    	if (reserved)//如果在需要释放的一段内存中有需要保留的内存页,那么该段内存就不能释放
    		return;
    
    	if (!PageHighMem(page))//判断页是否在高端内存域中
    		debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);//调试用的相关代码,还不理解,还望指点!
    	arch_free_page(page, order);//只有配置了HAVE_ARCH_FREE_PAGE才会起作用,也不理解,还望指点
    	kernel_map_pages(page, 1 << order, 0);
    
    	local_irq_save(flags);//禁止中断
    	__count_vm_events(PGFREE, 1 << order);//统计本CPU上释放的页数
    	free_one_page(page_zone(page), page, order);//释放函数的主体__free_one_page的封装
    	local_irq_restore(flags);//恢复中断
    }
    
    static void free_one_page(struct zone *zone, struct page *page, int order)
    {
    	spin_lock(&zone->lock);//获得管理区得自旋锁
    	zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);//在释放之前,先将内存区中页的不可回收标志清除
    	zone->pages_scanned = 0;//初始化在上一次成功换出页之后,已扫描页的数目。目前正在释放内存,将此清0,待回收过程随后回收时重新计数
    	__free_one_page(page, zone, order);//释放函数的主体
    	spin_unlock(&zone->lock);//解锁,有关锁的机制,自己还没有看到,后面的Blog会详细分析
    }
    
    __free_one_page源代码详细分析如下:
    static inline void __free_one_page(struct page *page,
    		struct zone *zone, unsigned int order)
    {
    	unsigned long page_idx;
    	int order_size = 1 << order;
    	int migratetype = get_pageblock_migratetype(page);
    
    	if (unlikely(PageCompound(page)))//要释放的页是巨页的一部分
    		destroy_compound_page(page, order);//解决巨页标志,如果巨页标志有问题,则退出
    
    	page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);//获取该页得页帧号,并保证该值在一定的范围之内
    
    	VM_BUG_ON(page_idx & (order_size - 1));//如果被释放的页不是所释放阶的第一个页,则说明参数有误
    	VM_BUG_ON(bad_range(zone, page));//检查页面是否处于zone之中
    
    	__mod_zone_page_state(zone, NR_FREE_PAGES, order_size);
    	while (order < MAX_ORDER-1) {//释放页以后,当前页面可能与前后的空闲页组成更大的空闲页面,直到放到最大阶的伙伴系统中
    		unsigned long combined_idx;
    		struct page *buddy;
    
    		buddy = __page_find_buddy(page, page_idx, order);//找到与当前页属于同一个阶的伙伴系统页面的索引
    		if (!page_is_buddy(page, buddy, order))//判断预期的伙伴页面是否与当前页处于同一个管理区,并且是否处于空闲状态。如果不是,则不能与该页合并为大的伙伴,退出
    			break;		/* Move the buddy up one level. */
    
    		list_del(&buddy->lru);//如果能够合并,则将伙伴页从伙伴系统中摘除
    		zone->free_area[order].nr_free--;//同时减少当前阶中的空闲页计数
    		rmv_page_order(buddy);//清除伙伴页的伙伴标志,因为该页会被合并
    		combined_idx = __find_combined_index(page_idx, order);//计算合并内存块的索引
    		page = page + (combined_idx - page_idx);//得到新的页面起始地址
    		page_idx = combined_idx;//为下一轮循环做准备
    		order++;//为下一轮循环做准备
    	}
    	set_page_order(page, order);//设置伙伴页中第一个空闲页的阶
    	list_add(&page->lru,
    		&zone->free_area[order].free_list[migratetype]);//将当前页面合并到空闲链表的最后,尽量避免将它分配出去
    	zone->free_area[order].nr_free++;
    }
    
    
    我只是一个内核的初学者,如果有哪些地方说的不对或是不准确,请指正;如果你有什么问题希望能提出来,一起分析讨论一下,以求共同进步。谢谢!
    
    
    
    
    
    
    
    
    展开全文
  • 从内核版本2.6.10开始提供一个通用的框架,用于将上述信息转换为伙伴系统预期的 结点和内存域数据结构。在这以前,各个体系结构必须自行建立相关结构。现在,体系结构相关代码只需要建立前述的简单结构,将繁重的...

    体系结构相关代码需要在启动期间建立以下信息:

    1.系统中各个内存域的页帧边界,保存在max_zone_pfn中

    2.个结点页帧的分配情况,保存在全局变量early_node_map中。

    从内核版本2.6.10开始提供一个通用的框架,用于将上述信息转换为伙伴系统预期的 结点和内存域数据结构。在这以前,各个体系结构必须自行建立相关结构。现在,体系结构相关代码只需要建立前述的简单结构,将繁重的工作留给 free_area_init_nodes即可。图1给出了该过程概述,图2给出了free_area_init_nodes的代码流程图。

                                                                                            图1:free_area_init_nodes过程概述

                                              图2:free_area_init_nodes代码流程图

    free_area_init_nodes的源代码的详细分析如下:

    1. void __init free_area_init_nodes(unsigned long *max_zone_pfn)  
    2. {  
    3.     unsigned long nid;  
    4.     enum zone_type i;  
    5.   
    6.     /* Sort early_node_map as initialisation assumes it is sorted */  
    7.     sort_node_map();//排序使得后续的任务稍微容易些,排序本身并不特别复杂  
    8.   
    9.     /* Record where the zone boundaries are */  
    10.     memset(arch_zone_lowest_possible_pfn, 0,  
    11.                 sizeof(arch_zone_lowest_possible_pfn));//全局数组arch_zone_lowest_possible_pfn用来存储各个内存域可使用的最低内存页帧编号  
    12.     memset(arch_zone_highest_possible_pfn, 0,  
    13.             sizeof(arch_zone_highest_possible_pfn));//全局数组arch_zone_highest_possible_pfn用来存储各个内存域可使用的最高内存页帧编号  
    14.     arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();//辅助函数find_min_pfn_with_active_regions用于找到注册的最低内存域中可用的编号最小的页帧  
    15.   
    16.     arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];//max_zone_pfn记录了各个内存域包含的最大页帧号  
    17.     for (i = 1; i < MAX_NR_ZONES; i++) {//依次遍历,确定各个内存域的边界  
    18.         if (i == ZONE_MOVABLE)//由于ZONE_MOVABLE是一个虚拟内存域,不与真正的硬件内存域关联,该内存域的边界总是设置为0,如后面的代码所示  
    19.             continue;  
    20.         arch_zone_lowest_possible_pfn[i] =  
    21.             arch_zone_highest_possible_pfn[i-1];//第n个内存域的最小页帧,即前一个(第n-1个)内存域的最大页帧  
    22.         arch_zone_highest_possible_pfn[i] =  
    23.             max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);//不出意外,当前内存域的最大页帧由max_zone_pfn给出  
    24.     }  
    25.     arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;  
    26.     arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;  
    27.   
    28.     /* Find the PFNs that ZONE_MOVABLE begins at in each node */  
    29.     memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));  
    30.     find_zone_movable_pfns_for_nodes(zone_movable_pfn);//用于计算进入ZONE_MOVABLE的内存数量,详细分析见下文  
    31.   
    32.     /* Print out the zone ranges */  
    33.     printk("Zone PFN ranges:\n");  
    34.     for (i = 0; i < MAX_NR_ZONES; i++) {//将各个内存域的最大、最小页帧号显示出来  
    35.         if (i == ZONE_MOVABLE)  
    36.             continue;  
    37.         printk("  %-8s %8lu -> %8lu\n",  
    38.                 zone_names[i],  
    39.                 arch_zone_lowest_possible_pfn[i],  
    40.                 arch_zone_highest_possible_pfn[i]);  
    41.     }  
    42.   
    43.     /* Print out the PFNs ZONE_MOVABLE begins at in each node */  
    44.     printk("Movable zone start PFN for each node\n");  
    45.     for (i = 0; i < MAX_NUMNODES; i++) {  
    46.         if (zone_movable_pfn[i])//对每个结点来说,zone_movable_pfn[node_id]表示ZONE_MOVABLE在movable_zone内存域中所取得内存的起始地址。内核确保这些页将用于满足符合ZONE_MOVABLE职责的内存分配  
    47.             printk("  Node %d: %lu\n", i, zone_movable_pfn[i]);  
    48.     }  
    49.   
    50.     /* Print out the early_node_map[] */  
    51.     printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);  
    52.     for (i = 0; i < nr_nodemap_entries; i++)//显示各个内存域的分配情况  
    53.         printk("  %3d: %8lu -> %8lu\n", early_node_map[i].nid,  
    54.                         early_node_map[i].start_pfn,  
    55.                         early_node_map[i].end_pfn);  
    56.   
    57.     /* Initialise every node */  
    58.     setup_nr_node_ids();  
    59.     for_each_online_node(nid) {//代码遍历所有的活动结点,并分别对各个结点调用free_area_init_node建立数据结构,该函数需要结点第一个可用的页帧作为一个参数,而find_min_pfn_for_node则从early_node_map数组提取该信息  
    60.         pg_data_t *pgdat = NODE_DATA(nid);  
    61.         free_area_init_node(nid, pgdat, NULL,  
    62.                 find_min_pfn_for_node(nid), NULL);  
    63.   
    64.         /* Any memory on that node */  
    65.         if (pgdat->node_present_pages)// 根据node_present_pages字段判断结点具有内存,则在结点位图中设置N_HIGH_MEMORY标志,该标志只表示结点上存在普通或高端 内存,因此check_for_regular_memory进一步检查低于ZONE_HIGHMEM的内存域中是否有内存,并据此在结点位图中相应地设 置N_NORMAL_MEMORY  
    66.             node_set_state(nid, N_HIGH_MEMORY);  
    67.         check_for_regular_memory(pgdat);  
    68.     }  
    69. }  

    free_area_init_node源代码详细分析:

    1. void __meminit free_area_init_node(int nid, struct pglist_data *pgdat,  
    2.         unsigned long *zones_size, unsigned long node_start_pfn,  
    3.         unsigned long *zholes_size)  
    4. {  
    5.     pgdat->node_id = nid;  
    6.     pgdat->node_start_pfn = node_start_pfn;  
    7.     calculate_node_totalpages(pgdat, zones_size, zholes_size);//首先累计各个内存域的页数,计算结点中页的总数。对连续内存模型而言,这可以通过zone_sizes_init完成,但calculate_node_totalpages还考虑了内存空洞  
    8.   
    9.     alloc_node_mem_map(pgdat);//分配了该节点的页面描述符数组[pgdat->node_mem_map数组的内存分配]   
    10.   
    11.     free_area_init_core(pgdat, zones_size, zholes_size);//对该节点的每个区[DMA,NORMAL,HIGH]的的结构进行初始化  
    12. }  
    calculate_node_totalpages源代码详细分析:
    1. static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,  
    2.         unsigned long *zones_size, unsigned long *zholes_size)  
    3. {  
    4.     unsigned long realtotalpages, totalpages = 0;  
    5.     enum zone_type i;  
    6.   
    7.     for (i = 0; i < MAX_NR_ZONES; i++)  
    8.         totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,  
    9.                                 zones_size);//累计计算各个内存域包含空洞的内存总页数  
    10.     pgdat->node_spanned_pages = totalpages;  
    11.   
    12.     realtotalpages = totalpages;  
    13.     for (i = 0; i < MAX_NR_ZONES; i++)  
    14.         realtotalpages -=  
    15.             zone_absent_pages_in_node(pgdat->node_id, i,  
    16.                                 zholes_size)//;以包含空洞的内存总页数累计减去各个内存域中空洞的数量,就可以得出实际可用的内存页数  
    17.     pgdat->node_present_pages = realtotalpages;  
    18.     printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,  
    19.                             realtotalpages);  
    20. }  
    alloc_node_mem_map源代码详细分析:
    1. static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)  
    2. {  
    3.     /* Skip empty nodes */  
    4.     if (!pgdat->node_spanned_pages)//如果内存结点没有没存页,直接返回  
    5.         return;  
    6.   
    7. #ifdef CONFIG_FLAT_NODE_MEM_MAP  
    8.     /* ia64 gets its own node_mem_map, before this, without bootmem */  
    9.     if (!pgdat->node_mem_map) {//如果还没有为结点分配mem_map,则需要为结点分配mem_map  
    10.         unsigned long size, start, end;  
    11.         struct page *map;  
    12.   
    13.         /* 
    14.          * The zone's endpoints aren't required to be MAX_ORDER 
    15.          * aligned but the node_mem_map endpoints must be in order 
    16.          * for the buddy allocator to function correctly. 
    17.          */  
    18.         start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);//确定起点,以MAX_ORDER_NR_PAGES的大小对齐  
    19.         end = pgdat->node_start_pfn + pgdat->node_spanned_pages;//计算结束点  
    20.         end = ALIGN(end, MAX_ORDER_NR_PAGES);//以MAX_ORDER_NR_PAGES对齐,与上面的功能一致,将内存映射对齐到伙伴系统的最大分配阶  
    21.         size =  (end - start) * sizeof(struct page);//计算所需内存的大小  
    22.         map = alloc_remap(pgdat->node_id, size);//为内存映射分配内存  
    23.         if (!map)//如果分配不成功,则使用普通的自举内存分配器进行分配  
    24.             map = alloc_bootmem_node(pgdat, size);  
    25.         pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);  
    26.     }  
    27. #ifndef CONFIG_NEED_MULTIPLE_NODES  
    28.     /* 
    29.      * With no DISCONTIG, the global mem_map is just set as node 0's 
    30.      */  
    31.     if (pgdat == NODE_DATA(0)) {  
    32.         mem_map = NODE_DATA(0)->node_mem_map;  
    33. #ifdef CONFIG_ARCH_POPULATES_NODE_MAP  
    34.         if (page_to_pfn(mem_map) != pgdat->node_start_pfn)  
    35.             mem_map -= (pgdat->node_start_pfn - ARCH_PFN_OFFSET);  
    36. #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */  
    37.     }  
    38. #endif  
    39. #endif /* CONFIG_FLAT_NODE_MEM_MAP */  
    40. }  

    free_area_init_core源代码详细分析:

    1. static void __meminit free_area_init_core(struct pglist_data *pgdat,  
    2.         unsigned long *zones_size, unsigned long *zholes_size)  
    3. {  
    4.     enum zone_type j;  
    5.     int nid = pgdat->node_id;  
    6.     unsigned long zone_start_pfn = pgdat->node_start_pfn;  
    7.     int ret;  
    8.   
    9.     pgdat_resize_init(pgdat);  
    10.     pgdat->nr_zones = 0;  
    11.     init_waitqueue_head(&pgdat->kswapd_wait);  
    12.     pgdat->kswapd_max_order = 0;  
    13.       
    14.     for (j = 0; j < MAX_NR_ZONES; j++) {  
    15.         struct zone *zone = pgdat->node_zones + j;  
    16.         unsigned long size, realsize, memmap_pages;  
    17.   
    18.         size = zone_spanned_pages_in_node(nid, j, zones_size);//内存域跨域的页数  
    19.         realsize = size - zone_absent_pages_in_node(nid, j,  
    20.                                 zholes_size);//内存域的可用长度,可通过跨域的页数减去空洞覆盖的页数而得到  
    21.   
    22.         /* 
    23.          * Adjust realsize so that it accounts for how much memory 
    24.          * is used by this zone for memmap. This affects the watermark 
    25.          * and per-cpu initialisations 
    26.          */  
    27.         memmap_pages = (size * sizeof(struct page)) >> PAGE_SHIFT;//用于内存映射需要的页数  
    28.         if (realsize >= memmap_pages) {如果内存域的可用长度大于用于内存映射需要的页数  
    29.             realsize -= memmap_pages;//则将需要映射的页数分配出去  
    30.             printk(KERN_DEBUG  
    31.                 "  %s zone: %lu pages used for memmap\n",  
    32.                 zone_names[j], memmap_pages);  
    33.         } else//否则,显示警告信息,可用内存不足  
    34.             printk(KERN_WARNING  
    35.                 "  %s zone: %lu pages exceeds realsize %lu\n",  
    36.                 zone_names[j], memmap_pages, realsize);  
    37.   
    38.         /* Account for reserved pages */  
    39.         if (j == 0 && realsize > dma_reserve) {  
    40.             realsize -= dma_reserve;  
    41.             printk(KERN_DEBUG "  %s zone: %lu pages reserved\n",  
    42.                     zone_names[0], dma_reserve);  
    43.         }//除去用于保留的内存页  
    44.   
    45.         if (!is_highmem_idx(j))  
    46.             nr_kernel_pages += realsize;//nr_kernel_pages表示不包含高端内存的系统内存共有的内存页面数,用于统计所有一致映射的页  
    47.         nr_all_pages += realsize;  
    48.   
    49.         zone->spanned_pages = size;//跨域的内存页  
    50.         zone->present_pages = realsize;//经过一系列初始化之后,还可使用的内存页  
    51. #ifdef CONFIG_NUMA  
    52.         zone->node = nid;  
    53.         zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)/ 100;//这句话不理解,请指教  
    54.         zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;//这句话不理解,请指教  
    55. #endif  
    56.         zone->name = zone_names[j];  
    57.         spin_lock_init(&zone->lock);//关于锁机制,自己还没有学到,后面会详细介绍锁机制  
    58.         spin_lock_init(&zone->lru_lock);  
    59.         zone_seqlock_init(zone);  
    60.         zone->zone_pgdat = pgdat;  
    61.   
    62.         zone->prev_priority = DEF_PRIORITY;  
    63.   
    64.         zone_pcp_init(zone);//初始化该内存域的per_cpu缓存  
    65.         INIT_LIST_HEAD(&zone->active_list);  
    66.         INIT_LIST_HEAD(&zone->inactive_list);  
    67.         zone->nr_scan_active = 0;  
    68.         zone->nr_scan_inactive = 0;  
    69.         zap_zone_vm_stats(zone);  
    70.         zone->flags = 0;  
    71.         if (!size)  
    72.             continue;  
    73.   
    74.         set_pageblock_order(pageblock_default_order());  
    75.         setup_usemap(pgdat, zone, size);  
    76.         ret = init_currently_empty_zone(zone, zone_start_pfn,  
    77.                         size, MEMMAP_EARLY);//init_currently_empty_zone用于初始化free_area列表,并将属于该内存域的所有page实例都设置为初始默认值  
    78.         BUG_ON(ret);  
    79.         zone_start_pfn += size;  
    80.     }  
    81. }  
    check_for_regular_memory源代码详细分析:
    1. static void check_for_regular_memory(pg_data_t *pgdat)  
    2. {  
    3. #ifdef CONFIG_HIGHMEM  
    4.     enum zone_type zone_type;  
    5.   
    6.     for (zone_type = 0; zone_type <= ZONE_NORMAL; zone_type++) {//进一步检查低于ZONE_HIGHMEM的内存域中是否有内存  
    7.   
    8.         struct zone *zone = &pgdat->node_zones[zone_type];  
    9.         if (zone->present_pages)  
    10.             node_set_state(zone_to_nid(zone), N_NORMAL_MEMORY);//并根据上面的检查在结点位图中相应地设置N_NORMAL_MEMORY  
    11.   
    12.     }  
    13. #endif 

    14. }

    转载于:https://my.oschina.net/u/174242/blog/76833

    展开全文
  • 从内核版本2.6.10开始提供一个通用的框架,用于将上述信息转换为伙伴系统预期的结点和内存域数据结构。在这以前,各个体系结构必须自行建立相关结构。现在,体系结构相关代码只需要建立前述的简单结构,将繁重的工作...
  • 详细描述了linux内存管理中伙伴算法的技术原理,对了解内存管理很有帮助
  • 提起buddy system相信很多人不会陌生,它是一种经典的内存分配算法,大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现,而仅仅是将该算法抽象提取出来,同时给出一份及其简洁的源码实现,以便...
  • 本节,我将介绍linux系统物理内存分配时所用到的技术——伙伴系统和slab缓存。 伙伴系统 使用场景:内核中很多时候要求分配连续页,为快速检测内存中的连续区域,内核采用了一种技术:伙伴系统。 原理:系统中...
  • Linux伙伴算法

    2018-03-08 13:09:00
    Linux内存管理伙伴算法 伙伴算法 Linux内核内存管理的任务包括: 遵从CPU的MMU(Memory Management Unit)机制 合理、有效、快速地管理内存 实现内存保护机制 实现虚拟内存 共享 重定位 Linux...
  • 为了避免出现这种情况,Linux内核中引入了伙伴系统算法(Buddy system)。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请...
  • 使用伙伴算法可以有效地缓解该问题。伙伴关系机制是操作系统中的一种动态存储管理算法。在进行内存分配时,该算法通过不断平分较大的空闲内存块来获得较小的空闲内存块,直到获得所需要的内存块;在进行内存回收时,...
  • linux没有采用分段机制,所以逻辑地址和虚拟地址(线性地址)(在用户态,内核态逻辑地址专指下文说的线性偏移前的地址)是一个概念。物理地址自不必提。内核的虚拟地址和物理地址,大部分只差一...
  • 网上能够找到的关于Linux内存分配伙伴算法的介绍不是很多,而且大多是进行较为抽象的介绍。为了能够让初学者能够快速建立起伙伴算法中提及的空闲链表、位图与内存间的对应关系,我做了以下几张图片,希望能够给初学...
  • 在系统初始化进行到伙伴系统分配器能够承担内存管理的责任后,必须停用bootmem分配器,毕竟不能同时用两个分配器管理内存。在UMA和NUMA系统上,停用分别由free_all_bootmem和free_all_bootmem_node完成(前面的博客...
  • 1.前言 本文所述关于内存管理的系列文章主要是对陈莉君老师所讲述的内存管理知识讲座的整理。 本讲座主要分三个主题展开对内存管理...Linux伙伴算法将所有的空闲页面分成MAX_ORDER+1(MAX_ORDER默认大小为11)个...
  • 为了避免出现这种情况,Linux内核中引入了伙伴系统算法(Buddy system)。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请...
  • 伙伴系统 基于一种相对简单而令人吃惊的强大算法,它结合了优秀内存分配器的两个关键特性:速度和效率。Linux内核中采用了一种同时适用于32位和64位系统的 内存分页模型,对于32位系统来说,两级页表足够用了,而在...
  • Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有两...
  • linux内存管理——伙伴关系算法

    千次阅读 2012-11-21 23:38:48
     Linux伙伴算法把所有的空闲页面分为10个块组,每组中块的大小是2的幂次方个页面,例如,第0组中块的大小都为20 (1个页面),第1组中块的大小为都为21(2个页面),第9组中块的大小都为29(512个页面)。...
  • 1.伙伴系统算法的提出 内核应该为分配一组连续的页框而建立一种健壮、高效的分配策略。为此,必须解决著名的内存,也就是所谓的外锁片问题(external fragmentation)。频繁的请求和释放不同大小的一组连续页框,...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 376
精华内容 150
关键字:

linux内存伙伴算法

linux 订阅