Posts Tagged ‘Memory’

物理内存管理:请求PFN慢速分配实现(2)

April 6th, 2015

之前分析了请求Physical Frame Number的主体函数 。当主体函数中的get_page_from_freelist() 分配失败后,自动进入 __alloc_pages_slowpath()进行慢速分配,首先会降低分配物理页框的条件。

检查请求分配的order阶数,如果超过了MAX_ORDER,则说明可能出现错误,返回空值。之后会检查传入慢速分配函数的参数gfp_mask是否指定GFP_THISNODE 和开启了NUMA,这个表示不能进行内存回收。如果成立则直接跳转到nopage。

经过上面的检查,系统开始正式分配空闲page frame,首先kernel通过wake_all_kswapds()唤醒每个zone所属node的kswapd守护进程(在kswapd没有在禁止的情况下),回收不经常使用的page frame。当将不经常使用的page frame回收以后,使用gfp_to_alloc_flags()对分配标志进行调整,稍微降低分配标准,以便再一次使用get_page_from_freelist()函数进行page frame 分配。

__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
         struct zonelist *zonelist, enum zone_type high_zoneidx,
         nodemask_t *nodemask, struct zone *preferred_zone,
         int classzone_idx, int migratetype)
{
         const gfp_t wait = gfp_mask & __GFP_WAIT;
         struct page *page = NULL;
         int alloc_flags;
         unsigned long pages_reclaimed = 0;
         unsigned long did_some_progress;
         enum migrate_mode migration_mode = MIGRATE_ASYNC;
         bool deferred_compaction = false;
         int contended_compaction = COMPACT_CONTENDED_NONE;

         if (order >= MAX_ORDER) {
                 WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
                 return NULL;
         }

         if (IS_ENABLED(CONFIG_NUMA) &&
             (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
                 goto nopage;

retry:
         if (!(gfp_mask & __GFP_NO_KSWAPD))
                 wake_all_kswapds(order, zonelist, high_zoneidx,
                                 preferred_zone, nodemask);

         alloc_flags = gfp_to_alloc_flags(gfp_mask);

         if (!(alloc_flags & ALLOC_CPUSET) && !nodemask) {
                 struct zoneref *preferred_zoneref;
                 preferred_zoneref = first_zones_zonelist(zonelist, high_zoneidx,
                                 NULL, &preferred_zone);
                 classzone_idx = zonelist_zone_idx(preferred_zoneref);
         }

         page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
                         high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
                         preferred_zone, classzone_idx, migratetype);
         if (page)
                 goto got_pg;
....

如果page不为空,则说明内存申请成功,否则继续进行慢速page frame分配。
如果设置了ALLOC_NO_WATERMARKS标志,那么此时会忽略水印,并此时进入__alloc_pages_high_priority()。这个函数内部会至少会再次调用get_page_from_freelist(),如果设置了__GFP_NOFAIL标志,则不断的循环等待并尝试进行内存分配。

__alloc_pages_high_priority()

         if (!wait) {
                 WARN_ON_ONCE(gfp_mask & __GFP_NOFAIL);
                 goto nopage;
         }

         /* Avoid recursion of direct reclaim */
         if (current->flags & PF_MEMALLOC)
                 goto nopage;

         /* Avoid allocations with no watermarks from looping endlessly */
         if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
                 goto nopage;

判断wait,如果调用者希望原子分配内存,则不能等待内存回收,返回NULL,如果当前进程就是内存回收进程(PF_MEMALLOC),则直接跳出,如果当前进程已经die,而且系统没有设置不准失败的位,直接返回nopage。否则如果当前进程设置了不准失败(__GFP_NOFAIL),则死循环继续分配,等待其他线程释放一点点内存。

page = __alloc_pages_direct_compact(gfp_mask, order, zonelist,
                                         high_zoneidx, nodemask, alloc_flags,
                                         preferred_zone,
                                         classzone_idx, migratetype,
                                         migration_mode, &contended_compaction,
                                         &deferred_compaction);
if (page)
        goto got_pg;

kernel尝试压缩内存。这样可以将一些小的外部碎片合并成大页面,这样也许能够满足内存分配要求。内存压缩是通过页面迁移实现的,第一次调用的时候,是非同步的。第二次调用则是同步方式。

page = __alloc_pages_direct_reclaim(gfp_mask, order,
                                zonelist, high_zoneidx,
                                nodemask,
                                alloc_flags, preferred_zone,
                                migratetype, &did_some_progress);
if (page)
        goto got_pg;

上面这个函数是真正的慢速分配的核心,它最终调用try_to_free_pages()回收一些最近很少用的页,然后将其写回磁盘上的交换区,以便在物理内存中腾出更多的空间。最终内核会再次调用get_page_from_freelist()尝试分配内存。

__perform_reclaim()函数中返回一个unsigned long *did_some_progress变量,标示是否成功分配page。如果这个变量进入下面代码

pages_reclaimed += did_some_progress;
         if (should_alloc_retry(gfp_mask, order, did_some_progress,
                                                 pages_reclaimed)) {

                 if (!did_some_progress) {
                         page = __alloc_pages_may_oom(gfp_mask, order, zonelist,
                                                 high_zoneidx, nodemask,
                                                 preferred_zone, classzone_idx,
                                                 migratetype,&did_some_progress);
                         if (page)
                                 goto got_pg;
                         if (!did_some_progress)
                                 goto nopage;
                 }
         } else {
                 page = __alloc_pages_direct_compact(gfp_mask, order, zonelist,
                                         high_zoneidx, nodemask, alloc_flags,
                                         preferred_zone,
                                         classzone_idx, migratetype,
                                         migration_mode, &contended_compaction,
                                         &deferred_compaction);
                 if (page)
                         goto got_pg;
         }

上面代码,可以看出系统还在尽量分配代码,判定是否重新执行__alloc_pages_direct_compact(),这次属于同步操作。如果判定不用执行该函数,也就意味着,kernel开始怀疑是否发生了OOM(out of memory)。如果当前请求内存的进程发生了OOM,也就是说该进程试图拥有过多的内存,那么此时内核会调用OOM killer杀死它。并且跳转到restart处,重新进行内存分配。

最后就是两个goto跳转函数:

nopage:
         warn_alloc_failed(gfp_mask, order, NULL);
         return page;
got_pg:
         if (kmemcheck_enabled)
                 kmemcheck_pagealloc_alloc(page, order, gfp_mask);

         return page;

nopage顾名思义就是没有足够的page frame 来alloc,got_pg就是系统分配到了page,我们跳转到__alloc_pages_direct_compact()和__alloc_pages_direct_reclaim()中看到都是先进行page的回收,然后再在get_page_from_freelist()中完成的,它根据伙伴算法分配所需大小的页框。

最后留下了代码段,不是特别明确,还需要继续看代码

2755         /* Checks for THP-specific high-order allocations */
2756         if ((gfp_mask & GFP_TRANSHUGE) == GFP_TRANSHUGE) {
...
2791         if ((gfp_mask & GFP_TRANSHUGE) != GFP_TRANSHUGE ||
2792                                                 (current->flags & PF_KTHREAD))
2793                 migration_mode = MIGRATE_SYNC_LIGHT;

 

 

 

参考:

http://lxr.free-electrons.com/source/mm/page_alloc.c#L2639

 

物理内存管理:请求PFN函数主体实现(1)

March 24th, 2015

物理内存管理:请求PFN函数层次结构分析 这篇文章中,我分析了分配页框的函数结构,其中是上层页框分配的核心,这个函数比起alloc_pages()多一个参数nid,如果传入的nid < 0 ,那么在当前内存节点上分配physical frame。

这里需要阐述的是Linux的内存管理针对的就是NUMA结构,如果当前系统只有一个节点,那么默认调用numa_node_id()返回这个唯一节点。

309 static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
310                                                 unsigned int order)
311 {
312         /* Unknown node is current node */
313         if (nid < 0)
314                 nid = numa_node_id();
315 
316         return __alloc_pages(gfp_mask, order, node_zonelist(nid, gfp_mask));
317 }

而在__alloc_pages()函数中,根据nid与gfp_mask可以得到一个适当的zonelist链表,我们知道每个内存节点下面都会默认存在三个zonelist区域:ZONE_DMA/ZONE_NORMAL/ZONE_HIGHMEM ,而node_zonelist(nid, gfp_mask)就是选择合适的内存链表区域zonelist。

因为存在三个zonelist区域,联系之前的struct pglist_data结构成员struct zonelist node_zonelists[MAX_ZONELISTS],MAX_ZONELISTS最大值就是2,可以看出分配只能分配当前节点和备用节点。

581 /*
582  * The NUMA zonelists are doubled because we need zonelists that restrict the
583  * allocations to a single node for __GFP_THISNODE.
584  *
585  * [0]  : Zonelist with fallback
586  * [1]  : No fallback (__GFP_THISNODE)
587  */
588 #define MAX_ZONELISTS 2

而__alloc_pages()函数内部又封装了__alloc_pages_nodemask()函数,这个函数是页框分配的主体[2],

struct page *
2857 __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
2858                         struct zonelist *zonelist, nodemask_t *nodemask)
2859 {
2860         enum zone_type high_zoneidx = gfp_zone(gfp_mask);
2861         struct zone *preferred_zone;
2862         struct zoneref *preferred_zoneref;
2863         struct page *page = NULL;
2864         int migratetype = gfpflags_to_migratetype(gfp_mask);
2865         unsigned int cpuset_mems_cookie;
2866         int alloc_flags = ALLOC_WMARK_LOW|ALLOC_CPUSET|ALLOC_FAIR;
2867         int classzone_idx;
2868 
2869         gfp_mask &= gfp_allowed_mask;
2870 
2871         lockdep_trace_alloc(gfp_mask);
2872 
2873         might_sleep_if(gfp_mask & __GFP_WAIT);
2874 
2875         if (should_fail_alloc_page(gfp_mask, order))
2876                 return NULL;
...
2883         if (unlikely(!zonelist->_zonerefs->zone))
2884                 return NULL;
....
2889 retry_cpuset:
2890         cpuset_mems_cookie = read_mems_allowed_begin();
2891 
2892         /* The preferred zone is used for statistics later */
2893         preferred_zoneref = first_zones_zonelist(zonelist, high_zoneidx,
2894                                 nodemask ? : &cpuset_current_mems_allowed,
2895                                 &preferred_zone);
2896         if (!preferred_zone)
2897                 goto out;
2898         classzone_idx = zonelist_zone_idx(preferred_zoneref);
2899 
2900         /* First allocation attempt */
2901         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
2902                         zonelist, high_zoneidx, alloc_flags,
2903                         preferred_zone, classzone_idx, migratetype);
2904         if (unlikely(!page)) {
....
2910                 gfp_mask = memalloc_noio_flags(gfp_mask);
2911                 page = __alloc_pages_slowpath(gfp_mask, order,
2912                                 zonelist, high_zoneidx, nodemask,
2913                                 preferred_zone, classzone_idx, migratetype);
2914         }
2915 
2916         trace_mm_page_alloc(page, order, gfp_mask, migratetype);
2917 
2918 out:
....
2925         if (unlikely(!page && read_mems_allowed_retry(cpuset_mems_cookie)))
2926                 goto retry_cpuset;
2927 
2928         return page;
2929 }

分析代码,我们可以看到,gfp_zone()根据gfp_mask选取适当类型的zone index。然后经过几项检查,通过zonelist->_zonerefs->zone判断zonelist是否为空,在这里至少要存在一个可用的zone,然后使用上述的zone index,通过first_zones_zonelist()来分配一个内存管理区。

如果前面分配成功,则进入get_page_from_freelist()函数,这个函数可以看成伙伴算法的前置函数,如果伙伴系统存在空位,那么利用伙伴系统进行分配内存,如果分配不成功就进入__alloc_pages_slowpath()慢速分配,这个时候内核要放宽分配的条件,回收系统内存,然后总会分配出一块page。

 

 

这里我们要说明下likely()与unlikely()的用法,这两个宏只是提高代码执行概率,是的gcc在编译时,将哪个代码段提前,哪个代码段推后,从而提高效率,不会对值有修改,例如if (unlikely(!zonelist->_zonerefs->zone))表示的就是当zonelist->_zonerefs->zone为空时,执行return NULL操作[1],虽然这个return不太可能发生。

在代码中我们还发现了cpuset_mems_cookie = read_mems_allowed_begin();语句,看到名字,我们就知道这个与cgroup有关,也就是说与cpuset子系统相关,cpuset子系统负责cpu节点与内存节点的分配,如果没有指定nodemask,则使用cpuset_current_mems_allowed允许的节点。我们看到在out域下,有一个if (unlikely(!page && read_mems_allowed_retry(cpuset_mems_cookie)))
发现目前kernel对于cgroup机制中出现page分配失败,就会怀疑是否cpuset_mems_cookie出现修改,如果出现修改,则重试。

 

 

[1] http://blog.csdn.net/npy_lp/article/details/7175517

[2]http://lxr.free-electrons.com/source/mm/page_alloc.c#L2857

物理内存管理:请求PFN函数层次结构分析

March 13th, 2015

http://www.lizhaozhong.info/archives/1254

上篇讲到的伙伴系统是alloc_pages()族函数运行的基础,下面我来简单说明下alloc_pages()的结构。

alloc_pages()函数下存在五个子函数,他们最后都会调用到alloc_pages(),唯一的区别就是传入的参数不同。

1.alloc_pages()

这个宏用来分配2的order次方个连续的页框,如果申请成功返回第一个所分配页框的描述符地址,这个地址是全局唯一的!申请失败的话返回NULL。

#define alloc_pages(gfp_mask, order) \
                alloc_pages_node(numa_node_id(), gfp_mask, order)

2.alloc_page()

这个函数是alloc_pages的特殊情况,它只分配一个页框,也就是order等于0。

#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

3.__get_free_pages()

这个函数可以申请长为2的order次方大小的连续页框,但是它返回的是这段连续页框中第一个页所对应的线性地址(区别页框的描述符地址)。该函数内部仍然调用了alloc_pages(),并利用page_address()将页描述符地址转换为线性地址。

unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
{
        struct page *page;
        VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
        page = alloc_pages(gfp_mask, order);
        if (!page)
                return 0;
        return (unsigned long) page_address(page);
}

4.__get_free_page()

该宏函数可以看作是__get_free_pages()的特殊情况,它用于申请一个单独的页框,然后返回这个单独页的线性地址

#define __get_free_page(gfp_mask) \
        __get_free_pages((gfp_mask),0)

5.get_zeroed_page()

该函数用来获取一个填满0的页框,其中__GFP_ZERO参数用来体现这一点,类似于memset()清零的效果。

unsigned long get_zeroed_page(gfp_t gfp_mask)
{
        return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
}

6.__get_dma_pages()

该宏函数获得的页框用于DMA操作。

#define (gfp_mask, order) \
                __get_free_pages((gfp_mask) | GFP_DMA,(order))

请求页框的标志通过查阅手册,我可以发现有非常多的mask。
如下代码

 13 #define ___GFP_DMA              0x01u
 14 #define ___GFP_HIGHMEM          0x02u
 15 #define ___GFP_DMA32            0x04u
 16 #define ___GFP_MOVABLE          0x08u
 17 #define ___GFP_WAIT             0x10u
 18 #define ___GFP_HIGH             0x20u
 19 #define ___GFP_IO               0x40u
 20 #define ___GFP_FS               0x80u
 21 #define ___GFP_COLD             0x100u
 22 #define ___GFP_NOWARN           0x200u
 23 #define ___GFP_REPEAT           0x400u
 24 #define ___GFP_NOFAIL           0x800u
 25 #define ___GFP_NORETRY          0x1000u
 26 #define ___GFP_MEMALLOC         0x2000u
 27 #define ___GFP_COMP             0x4000u
 28 #define ___GFP_ZERO             0x8000u
 29 #define ___GFP_NOMEMALLOC       0x10000u
 30 #define ___GFP_HARDWALL         0x20000u
 31 #define ___GFP_THISNODE         0x40000u
 32 #define ___GFP_RECLAIMABLE      0x80000u
 33 #define ___GFP_NOTRACK          0x200000u
 34 #define ___GFP_NO_KSWAPD        0x400000u
 35 #define ___GFP_OTHER_NODE       0x800000u
 36 #define ___GFP_WRITE            0x1000000u

使用最多的莫过于___GFP_DMA,___GFP_HIGHMEM,___GFP_DMA32。
当我们在写内核模块的时候,我们会用到kmalloc()函数,里面的标志位最多的应该就是GFP_KERNEL、GFP_USER和GFP_ATOMIC。这三个参数经过层层解析被系统解析为

106 #define GFP_ATOMIC      (__GFP_HIGH)
109 #define GFP_KERNEL      (__GFP_WAIT | __GFP_IO | __GFP_FS)
112 #define GFP_USER        (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL)

系统中也会按照内存zone的区域分配,总的分配顺序是HIGHMEM、NORMAL、DMA ,如果API指定分配区域,系统就按照指定区域分配。

总的函数调用关系:

get_zeroed_page()      __get_free_page()   __get_dma_pages()
      |                        |                   |
      |                        |                   |
      |----------------------------------------------
 __get_free_pages()     alloc_page()
      |                        |
      |-------------------------
alloc_pages()
      |
alloc_pages_node()
      |
__alloc_pages()
      |
__alloc_pages_nodemask()

通过上面的结构表示,alloc_pages_node()是上述API的核心,而__alloc_pages_nodemask()为页框分配的心脏!

 

参考:

http://www.cnblogs.com/hanyan225/archive/2011/07/28/2119628.html

http://lxr.free-electrons.com/source/include/linux/gfp.h

IA32下高端内存页框(ZONE_HIGHMEM)永久内核映射的分析与实现

March 6th, 2015

一、背景

在AMD64平台下,可用的线性地址空间远远大于目前安装的RAM大小,所以在这种体系中,ZONE_HIGHMEM总是空的。

而在32位平台上,Linux设计者必须找到一种方式允许内核使用所有4GB的RAM,如果IA32支持PAE的话,则使内核可以支持64GB的RAM。

IA32架构下,之所以有这些约束,主要是为了兼容前代固有的硬件架构(i386),例如DMA直接读取,i386 内存大于900MB的情况。

ZONE_HIGHMEM属于高于896MB的内存区域,需要通过高端内存页框分配的方式映射到内核线性地址空间,从而使得内核可以对高端内存进行访问。而低于896MB直接通过(PAGE_OFFSET)偏移映射到物理内存上。详细查看http://www.lizhaozhong.info/archives/1193

二、原理

高端内存页框分配alloc_pages()函数返回的是page frame 页描述符(page description)的线性地址,因为这些页描述符地址一旦被分配,便不再改变,所以他是全局唯一的。这些页描述符在free_area_init_nodes()初始化时,已建立好。

注:free_area_init_nodes()之前的初始化与体系结构相关,当系统调用这个函数后,开始初始化每个pg_data_t的结构体,便于体系结构再无相关,http://lxr.free-electrons.com/source/mm/page_alloc.c#L5386。。

页描述符我们可以想象成系统将所有内存按照4k等分划分形成的数组下标。所有的page descriptor组成一个大的连续的数组 ,每个节点起始地址存放在 struct page *node_mem_map中,因此如果知道了page descriptor的地址pd,pd-node_mem_map就得到了pd是哪个page frame的描述符,也可以知道这个页描述符是否高于896MB。

 

已知alloc_pages()函数分配一个page descriptor的线性地址,可由它得到它所描述的物理页是整个内存的第几页:

假设是第N个物理页,那么这个物理页的物理地址是physAddr = N << PAGE_SHIFT   ,一般情况PAGE_SHIFT   为12 也就是4k。在得知该物理页的物理地址是physAddr后,就可以视physAddr的大小得到它的虚拟地址,然后对这个虚拟地址进行判断:

1.physAddr < 896M  对应虚拟地址是 physAddr + PAGE_OFFSET   (PAGE_OFFSET=3G)
2.physAddr >= 896M 对应虚拟地址不是静态映射的,通过内核的高端虚拟地址映射得到一个虚拟地址(也就是内核页表映射)。

在得到该页的虚拟地址之后,内核就可以正常访问这个物理页了。

所以,我们可以将physAddr高于896M的这128M看做成为一个内核页表,这个内核页表在paging_init()初始化完成。

三、实现

内核采取三种不同的机制将page frame映射到高端内存:永久内核映射、临时内核映射、非连续内存分配。

alloc_page()函数集返回的是全是struct page* 类型的数据,返回的也都是page descriptor的线性地址。然后系统要判断该page descriptor是否是highmem,也就是void *kmap(struct page *page)
http://lxr.free-electrons.com/source/arch/x86/mm/highmem_32.c#L6 。

 

系统调用PageHighMem(page),判断当前page是否是highmem,如果是返回kmap_high(page)。如果不是返回page_address(page)  http://lxr.free-electrons.com/source/mm/highmem.c#L412

 

void *kmap(struct page *page)
{
         might_sleep();
         if (!PageHighMem(page))
                 return page_address(page);
         return kmap_high(page);
}
void *page_address(const struct page *page)
{
         unsigned long flags;
         void *ret;
         struct page_address_slot *pas;

         if (!PageHighMem(page))
                 return lowmem_page_address(page);

         pas = page_slot(page);
         ret = NULL;
         spin_lock_irqsave(&pas->lock, flags);
         if (!list_empty(&pas->lh)) {
                 struct page_address_map *pam;

                 list_for_each_entry(pam, &pas->lh, list) {
                         if (pam->page == page) {
                                 ret = pam->virtual;
                                 goto done;
                         }
                 }
         }
 done:
         spin_unlock_irqrestore(&pas->lock, flags);
         return ret;
}

在page_address()函数中,我们要再次检查该page是否属于HIGHMEM,如果不属于,则直接计算偏移量__va(PFN_PHYS(page_to_pfn(page)))。

而pas = page_slot(page);之后的代码,是在永久映射中,系统为了方便查找,建立了一个page_address_htable散列表,系统可以很快的对于已经存放在散列表中的永久映射的page descriptor的线性地址进行查找,如果找到就返回内核线性地址,否则为NULL。

如果判断该page属于HIGHMEM,进入kmap_high(page) http://lxr.free-electrons.com/source/mm/highmem.c#L279

void *kmap_high(struct page *page)
{
         unsigned long vaddr;

/*
* For highmem pages, we can't trust "virtual" until
* after we have the lock.
*/
         lock_kmap();
         vaddr = (unsigned long)page_address(page);
         if (!vaddr)
                 vaddr = map_new_virtual(page);
         pkmap_count[PKMAP_NR(vaddr)]++;
         BUG_ON(pkmap_count[PKMAP_NR(vaddr)] < 2);
         unlock_kmap();
         return (void*) vaddr;
}

虽然判断了HIGHMEM,调用这个函数,但是我们不能信任,仍需要再次检查,顺便检查是否在page_address_htable散列表中存在该page,如果不存在,则进行映射( map_new_virtual(page)),然后将pkmap_count数组中,这个page引用+1,然会内核就可以正常使用这个高端内存的线性地址了。

map_new_virtual()函数是进行HIGHMEM映射的核心函数,其中for(;;)循环是寻找可用的内核页表项进行高端内存页框映射,这里涉及到了页表color问题,主要为了提速查找效率。

当系统找到可用的页表项时,从line261~line268就是核心

  • 以PKMAP_BASE为基址last_pkmap_nr为偏移在永久映射区创建内核线性地址vaddr
  • 将vaddr加入pkmap_page_table
  • 引用赋值为1,之后有可能会++
  • 然后将该内核线性地址vaddr加入page,并返回内核线性地址
</pre>
<pre>217 static inline unsigned long map_new_virtual(struct page *page)
218 {
...
224 start:
225         count = get_pkmap_entries_count(color);
226         /* Find an empty entry */
227         for (;;) {
228                 last_pkmap_nr = get_next_pkmap_nr(color);
229                 if (no_more_pkmaps(last_pkmap_nr, color)) {
230                         flush_all_zero_pkmaps();
231                         count = get_pkmap_entries_count(color);
232                 }
233                 if (!pkmap_count[last_pkmap_nr])
234                         break;  /* Found a usable entry */
235                 if (--count)
236                         continue;
237
238                 /*
239                  * Sleep for somebody else to unmap their entries
240                  */
241                 {
242                         DECLARE_WAITQUEUE(wait, current);
243                         wait_queue_head_t *pkmap_map_wait =
244                                 get_pkmap_wait_queue_head(color);
246                         __set_current_state(TASK_UNINTERRUPTIBLE);
247                         add_wait_queue(pkmap_map_wait, &wait);
248                         unlock_kmap();
249                         schedule();
250                         remove_wait_queue(pkmap_map_wait, &wait);
251                         lock_kmap();
253                         /* Somebody else might have mapped it while we slept */
254                         if (page_address(page))
255                                 return (unsigned long)page_address(page);
256
257                         /* Re-start */
258                         goto start;
259                 }
260         }
261         vaddr = PKMAP_ADDR(last_pkmap_nr);
262         set_pte_at(&init_mm, vaddr,
263                    &(pkmap_page_table[last_pkmap_nr]), mk_pte(page, kmap_prot));
264
265         pkmap_count[last_pkmap_nr] = 1;
266         set_page_address(page, (void *)vaddr);
268         return vaddr;

中间line241~259 内核考虑一种情况:如果这个PKMAP都已经被映射,最少的count都是>=1的,那么需要将当前的映射操作阻塞,然后加入等待队列,然后主动让出cpu被调度,直到PKMAP中存在count=0的页表项存在,唤醒,重新执行一次。

pkmap_count引用的可能值:0/1/>1。

0意味着该内核页表项未被映射高端内存,是可用的

1意味着虽然未被映射高端内存,但是需要unmapped,如果没有任何可用的页表项了,需要调用flush_all_zero_pkmaps()刷新pkmap_count,并置零。

>1意味着该页表项被使用。

 

参考:

http://repo.hackerzvoice.net/depot_madchat/ebooks/Mem_virtuelle/linux-mm/zonealloc.html#INITIALIZE

http://blog.csdn.net/lcw_202/article/details/5955783

https://www.kernel.org/doc/gorman/html/understand/understand006.html#sec: Mapping addresses to struct pages

物理内存管理:伙伴系统数据结构分析

March 4th, 2015

伙伴系统(buddy system)在物理内存管理中占有重要地位。

我们知道物理内存被分为三大部分:DMA、NORMAL、HIGHMEN三个区域。每个内存域都有一个struct zone的实例。而这个struct zone 的实例又被struct pglist_data管理。具体看http://www.lizhaozhong.info/archives/1184

page frame <==> struct page

struct zone 这个结构体非常庞大,总的来说分成三部分,每一部分由 ZONE_PADDING(_pad1_)这种标示分割。我们可以通过struct zone 下的unsigned long zone_start_pfn 找到某个特定的page!但是这种page frame,我们无法知道空闲页框的布局,不利于分配page frame。

具体zone定义:http://lxr.free-electrons.com/source/include/linux/mmzone.h#L327

为了尽量分配连续的page frame,避免外部碎片的产生,伙伴系统(buddy system)满足这个需求。
每个内存域(struct zone)的实例都有free_area数组,这个数组大小是11,也就是说空闲区域有0-10阶的page frame 块链表。比如free_area[3]所对应的页框块链表中,每个节点对应8个连续的页框(2的3次方)。

#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
struct zone{
........
476         ZONE_PADDING(_pad1_)
477
478         /* Write-intensive fields used from the page allocator */
479         spinlock_t              lock;
480
481         /* free areas of different sizes */
482         struct free_area        free_area[MAX_ORDER];
483
484         /* zone flags, see below */
485         unsigned long           flags;
486
487         ZONE_PADDING(_pad2_)
......
}

而struct free_area如下http://lxr.free-electrons.com/source/include/linux/mmzone.h#L92

 92 struct free_area {
 93         struct list_head        free_list[MIGRATE_TYPES];
 94         unsigned long           nr_free;
 95 };

通过声明看到free_list是一个链表数组。nr_free表示当前链表中空闲页框块的数目,比如free_area[3]中nr_free的值为5,表示有5个大小为8的页框块,那么总的页框数目为40。

具体概述上面buddy system结构就是:
buddy

在/proc中我们可以查看到每个阶空闲大小的PFN数量(注:本机使用的是AMD64系统,在AMD64中没有ZONE_HIGHMEN,ZONE_DMA寻值为16M,ZONE_DMA32寻值为0-4GiB,在32为机器上DMA32为0)

[root@localhost cgroup_unified]# cat /proc/buddyinfo
Node 0, zone      DMA      8      7      6      5      4      2      1      2      2      3      0
Node 0, zone    DMA32   1059   1278   9282   1868   1611    260     52     20      7      2      1

在struct list_head free_list[MIGRATE_TYPES]中,我们发现每个阶都带有一个MIGRATE_TYPES标志,通过这种方式,系统又把每个阶的空闲page更加详细的分割,具体类型有不可移动,移动,保留等。

 38 #define MIGRATE_UNMOVABLE     0
 39 #define MIGRATE_RECLAIMABLE   1
 40 #define MIGRATE_MOVABLE       2
 41 #define MIGRATE_PCPTYPES      3 /* the number of types on the pcp lists */
 42 #define MIGRATE_RESERVE       3
 43 #define MIGRATE_ISOLATE       4 /* can't allocate from here */
 44 #define MIGRATE_TYPES         5

这是为了更大限度的满足连续物理页框的需要,如果要分配一种MIGRATE_UNMOVABLE类型的页框,而两边的页框是可以移动的,这样就限制了连续大页框的分配,产生了外部碎片。
使用MIGRATE_TYPES策略后,不可移动的页面的不可移动性仅仅影响它自身的类别而不会导致一个不可移动的页面两边都是可移动的页面。这就是MIGRATE_TYPE被引入的目的。

MIGRATE_TYPE限制了内存页面的分配地点从而避免碎片,而不再仅仅寄希望于它们被释放时通过合并避免碎片[1]。

这种策略在proc中也可以查看:

[root@localhost cgroup_unified]# cat /proc/pagetypeinfo
Page block order: 9
Pages per block:  512

Free pages count per migrate type at order       0      1      2      3      4      5      6      7      8      9     10
Node    0, zone      DMA, type    Unmovable      1      4      4      1      1      1      1      1      0      0      0
Node    0, zone      DMA, type  Reclaimable      5      1      1      0      0      0      0      1      1      1      0
Node    0, zone      DMA, type      Movable      2      0      2      4      3      1      0      0      1      1      0
Node    0, zone      DMA, type      Reserve      0      0      0      0      0      0      0      0      0      1      0
Node    0, zone      DMA, type      Isolate      0      0      0      0      0      0      0      0      0      0      0
Node    0, zone    DMA32, type    Unmovable      1      0      8      1     17     15      5      0      0      0      0
Node    0, zone    DMA32, type  Reclaimable   1041    162      1      0      1      1      1      1      1      0      0
Node    0, zone    DMA32, type      Movable    698     78      7   1221   1194    232     45     20      6      0      0
Node    0, zone    DMA32, type      Reserve      0      0      0      0      0      0      0      0      0      1      1
Node    0, zone    DMA32, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 

Number of blocks type     Unmovable  Reclaimable      Movable      Reserve      Isolate
Node 0, zone      DMA            1            2            4            1            0
Node 0, zone    DMA32           89           93         1216            2            0

参考:

[1] http://blog.csdn.net/dog250/article/details/6108028