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

April 13th, 2015 by JasonLe's Tech 1,713 views

前面主体函数慢速分配函数最后都会调用到get_page_from_freelist()函数,区别在于主体函数是直接调用,而慢速分配是通过回收page,或者交换到swap分区的方式从已经满了的zone里面回收空闲的page。

这个函数可以看做buddy system 的前置函数,通过传入order与flag判断当前的内存是否可以分配一块内核,如果可以转入buffered_rmqueue()进行,如果实在没有的话,就只能返回NULL了。

static struct page *
get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
                 struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
                 struct zone *preferred_zone, int classzone_idx, int migratetype)
{
         struct zoneref *z;
         struct page *page = NULL;
         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 */
         bool consider_zone_dirty = (alloc_flags & ALLOC_WMARK_LOW) &&
                                 (gfp_mask & __GFP_WRITE);
         int nr_fair_skipped = 0;
         bool zonelist_rescan;

上面这个声明头,安装了zlc,也就是zonelist_cache还有判断zone_dirty的位,包括是否进行fairness分配等。

zonelist_scan:
        zonelist_rescan = false;
        for_each_zone_zonelist_nodemask(zone, z, zonelist,
                                                high_zoneidx, nodemask) {
                 unsigned long mark;

                 if (IS_ENABLED(CONFIG_NUMA) && zlc_active &&
                         !zlc_zone_worth_trying(zonelist, z, allowednodes))
                                 continue;
                 if (cpusets_enabled() &&
                         (alloc_flags & ALLOC_CPUSET) &&
                         !cpuset_zone_allowed(zone, gfp_mask))
                                 continue;
                 if (alloc_flags & ALLOC_FAIR) {
                        if (!zone_local(preferred_zone, zone))
                                 break;
                        if (test_bit(ZONE_FAIR_DEPLETED, &zone->flags)) {
                                 nr_fair_skipped++;
                                 continue;
                         }
                 }

                 if (consider_zone_dirty && !zone_dirty_ok(zone))
                         continue;

上面的这个段有一个zonelist_scan段,因为扫描空闲的zonelist可能会出现找不到page,所以kernel会使用goto重新扫描遍历zonelist寻找合适page。

for_each_zone_zonelist_nodemask()是一个宏函数,用来进行zonelist的遍历,我们之前结合内存结构分析过NUMA架构中存在多个pg_list,而high_zoneidx则是遍历的边界,也就是说如果high_zoneidx为ZONE_NORMAL,那么遍历的zone区域就是ZONE_DMA、ZONE_NORMAL。而zone的区域都是通过enmu来声明的。

                 mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
                 if (!zone_watermark_ok(zone, order, mark,
                                        classzone_idx, alloc_flags)) {
                         int ret;

                         BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
                         if (alloc_flags & ALLOC_NO_WATERMARKS)
                                 goto try_this_zone;

                         if (IS_ENABLED(CONFIG_NUMA) &&
                                         !did_zlc_setup && nr_online_nodes > 1) {

                                 allowednodes = zlc_setup(zonelist, alloc_flags);
                                 zlc_active = 1;
                                 did_zlc_setup = 1;
                         }

                         if (zone_reclaim_mode == 0 ||
                             !zone_allows_reclaim(preferred_zone, zone))
                                 goto this_zone_full;

                         if (IS_ENABLED(CONFIG_NUMA) && zlc_active &&
                                 !zlc_zone_worth_trying(zonelist, z, allowednodes))
                                 continue;

上面这些代码都是存在于遍历zonelist的循环中,如果当前的watermark使能,而且zone_watermark_ok()判断在当前的watermark下是否可以分配内存。如果可以分配内存则跳入最后的try_this_zone段。

在下面会提到。如果这里分配page失败,也就意味内存不足,需要进行page回收:zone_reclaim(),上面这段代码还包括一些其他判断,如果在nodemask中指定了在当前节点分配page,而同时当前node又不满足分配的需求,这里只能返回this_zone_full段。

 ret = zone_reclaim(zone, gfp_mask, order);
 switch (ret) {
      case ZONE_RECLAIM_NOSCAN:
              continue;
      case ZONE_RECLAIM_FULL:
              continue;
      default:
              if (zone_watermark_ok(zone, order, mark,
                      classzone_idx, alloc_flags))
                   goto try_this_zone;

              if (((alloc_flags & ALLOC_WMARK_MASK) == ALLOC_WMARK_MIN) ||
                   ret == ZONE_RECLAIM_SOME)
                   goto this_zone_full;

              continue;
           }
     }

如果运行到这里,说明此刻空闲内存不足,需要使用zone_reclaim()进行内存回收,回收的情况通过ret来确定。如果结果是ZONE_RECLAIM_NOSCAN,说明并没有进行回收,那么直接尝试下一个zone,如果结果是ZONE_RECLAIM_FULL,说明虽然进行了回收但是并没有回收到,默认的情况则是没有回收到足够多的内存。后两种情况均跳入default处。

这里需要再次判断是否分配的内存在watermark以下,如果可以的话,跳入try_this_zone。第二个if是为了判断分配的mask是否是最小值,这里涉及到ZONE_RECLAIM_SOME,不太清楚,需要继续看。

这里需要声明的是ALLOC_WMARK_MIN指的是当前的内存空闲量已经很低,我们可以将内存看成一桶水,用掉内存的相当于用掉的水,所以越用越少。我们查看代码,发现使用watermark的话,会主要的存在以下几个标志位:

#define ALLOC_WMARK_MIN         WMARK_MIN
#define ALLOC_WMARK_LOW         WMARK_LOW
#define ALLOC_WMARK_HIGH        WMARK_HIGH
#define ALLOC_NO_WATERMARKS     0x04 /* don't check watermarks at all */

大致分为MIN、LOW、HIGH三个watermark标志。当系统当前node节点内存非常少的时候,就会启用ALLOC_NO_WATERMARKS标志。

try_this_zone:
                 page = buffered_rmqueue(preferred_zone, zone, order,
                                                 gfp_mask, migratetype);
                 if (page)
                         break;

上面这个段就是如果系统找到空闲的page,会跳到这里,这个函数就是buddy system的前置函数。

 this_zone_full:
                 if (IS_ENABLED(CONFIG_NUMA) && zlc_active)
                         zlc_mark_zone_full(zonelist, z);
         }

上面这个段说明当前zone的空闲内存不足,那么标记它。这样下次分配时可以直接将其忽略。

         if (page) {
                page->pfmemalloc = !!(alloc_flags & ALLOC_NO_WATERMARKS);
                return page;
         }

上面这个已经跳出了遍历zonelist的范围,如果分配到了page,走到这里,系统已经分配了page,设置pfmemalloc 也就意味着目前系统在内存方面有压力,应该保持这个page不被swap出内存,并使得系统换出其他的页。

         if (alloc_flags & ALLOC_FAIR) {
                 alloc_flags &= ~ALLOC_FAIR;
                 if (nr_fair_skipped) {
                         zonelist_rescan = true;
                         reset_alloc_batches(preferred_zone);
                 }
                 if (nr_online_nodes > 1)
                         zonelist_rescan = true;
         }
         if (unlikely(IS_ENABLED(CONFIG_NUMA) && zlc_active)) {
                 /* Disable zlc cache for second zonelist scan */
                 zlc_active = 0;
                 zonelist_rescan = true;
         }

         if (zonelist_rescan)
                goto zonelist_scan;

         return NULL;

走到这里,一般意味着page为NULL,这里我们要考虑到一种情况本地的node,内存分配已经达到饱和,而远端的node还没有被考虑,所以这个时候系统放弃fairness,将远端的node节点纳入到考虑范围。

当然这是在进入慢速分配和唤醒kswapd的前提下,总的来说系统page分配的mechanism顺序是:local node -> remote node -> slowpath -> kswapd ->NULL

这里设置了zonelist_rescan 位,如果这一位为真,则重新扫描所有的内存node节点,包括远端node!

 

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

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

April 6th, 2015 by JasonLe's Tech 1,653 views

之前分析了请求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

 

Recursing with STL

March 31st, 2015 by JasonLe's Tech 1,597 views

最近使用装有节点值的vector容器的前序遍历与中序遍历去构造一颗Binary Tree。

我们都知道先序遍历的顺序是 :中-左-右,中序遍历的顺序是:左-中-右,后续遍历是左-右-中。

举例:

//         1
//        / \
//       2   5
//      / \   \
//     3   4   6

这棵树的先序遍历:1 2 3 4 5 6 中序遍历: 3 2 4 1 5 6 后续:3 4 2 6 5 1 。

众所周知,已知一个树的先序和中序,或者是中序和后续,便可以构造出一棵树,构造的思路是先序的第一个节点就是根,然后查找这个根在中序中的位置,中序遍历中根的位置的左边就是左子树,后面是右子树。然后递归进入到下一层:先序 2 3 4 中序 3 2 4 ,可以看出先序中2是根,然后查找中序2的位置,就得到 3 是 2 的左子树,4是2的右子树,依次recurse。

下面使用STL的方式构造这棵树:已知vector &preorder, vector &inorder是装有先序和中序的vector容器,使用递归就是设置出一个中间状态,对他进行分析,并且函数的参数必须是每次都可以用减小范围的。

STL中,我们都知道有vector::iterator方式来遍历vector元素值,获取这种iterator有两种方式:1)preorder.begin()获取vector中第一个元素的指针。2)begin(preorder),返回的也是vector第一个指针。他们都可以使用*得到值。

end()比较特殊,它返回的是最后元素的下一个元素,也就是一个越界的元素,直接引用会导致数组越界。

auto pos = find(preorder.begin(),preorder.end(),val) 查找当前val的的节点,返回当前val的指针。
distance(preorder.begin(),pos) 直接返回中开始到pos的距离,不包括pos。

//1 2 3 4 5 6
auto Pos = find(pre_order.begin(),pre_order.end(),4);
auto dis = distance(pre_order.begin(),Pos);
cout << dis << "\n";
cout << *next(pre_order.begin(),dis);

我们发现dis = 3,而next是从1开始的3个元素后的下一个元素,也就是val=4的指针。

我们在定义这种迭代器声明的时候,会发现函数参数非常长

TreeNode *buildTree(vector<int>::iterator inorder_first,vector<int>::iterator inorder_end,
		vector<int>::iterator postorder_first,vector<int>::iterator postorder_end)

我们可以使用模板编程极大地简化声明:

template<typename InputIterator>
TreeNode *buildTree(InputIterator inorder_first,InputIterator inorder_end,
		InputIterator postorder_first,InputIterator postorder_end)
{
	if(postorder_first==postorder_end)
		return NULL;
	if(inorder_first==inorder_end)
		return NULL;
	int val = *prev(postorder_end);
	TreeNode *root = new TreeNode(val);

	auto in_rootPos = find(inorder_first,inorder_end,val);
	auto left_size = distance(inorder_first,in_rootPos);

	root->left = buildTree(inorder_first,next(inorder_first,left_size),postorder_first,
		next(postorder_first,left_size));
	root->right = buildTree(next(inorder_first,left_size+1),inorder_end,next(postorder_first,left_size)
		,prev(postorder_end));

	return root;
}

上面的代码是后序遍历与中序遍历组合成一棵树,先序与中序也是类似的。

 

 

参考:
http://www.cplusplus.com/reference/iterator/begin/?kw=begin
http://www.cplusplus.com/reference/iterator/end/?kw=end
http://www.cplusplus.com/reference/iterator/InputIterator/

字符编码浅析

March 26th, 2015 by JasonLe's Tech 1,611 views

最近在linux与windows上面做切换,经常会遇到乱码问题,又联想起很多因为字符解析失败,最后debug出来是因为字符编码的问题后,准备仔细研究这一块奇怪的东东。

我主要是使用汉语,所以与我们息息相关的编码时gb2312、GBK和UTF系列。

GB2312是最早的汉语标准,但是最大的问题是收录的汉字太少,导致许多复杂的函数无法在机器中表示。之后Microsoft使用GB2312未使用的编码空间,拓展了收录的字符数。

但是真正的国家标准是GB18030,它收录了7万多个汉字,目前的国内软件都必须支持这个字符集。

我们都知道ASCII码在电脑中用1 byte来表示,比如 strlen(“l123”),就返回一个字符长度4,而汉字在电脑中使用2 byte来表示,也就是strlen(“李123”)返回5!

如果在一个页面中存在多种语言,那在我们看来就是一堆乱码!所以unicode出现了,但是unicode又会分成很多字符标准:

  • utf-16 的实现是每个字符有2 byte来表示,但是这种编码方式没有运用在浏览器中。

在windows中使用宽字符进行表示,也是说下面代码虽然有汉字,但是每个s元素都是2 byte,最后的len也还是4!

wchar_t s[10];
int len=0;

wcscpy(s, L“李123”);
len = wcslen(s);

wchar_t 其实是 unsigned short,一个 16-bit,C 语言所有的 strxxx 都有相对应的 wcsxxx,字符串前面加上 L,代表宽字符。

  • utf-16 的实现是每个字符由4 byte来表示,太占空间,没有人使用。
  • utf-8是我们现在通用的一种字符表示编码,每个字符是可变长度的。

每个字可能是 1~6个bytes (2003年后删减剩下 1~4 个 bytes)

  1. US-ASCII (0 ~ 127) : 1-byte
  2. 部分各国字母: 2-byte (例如希腊字母,西里尔字母…)
  3. 其它常用字 : 3-byte (大部分的汉字)
  4. 极少用字 : 4~6-byte (包含罕见汉字 ,麻将牌…)

也就是说平时的英文数字大概一个字符一个byte,而汉字 3 byte。

unicode上面这幅图表示的是utf8的表示方式[1],我们可以看到电脑在寻找这个字符由几个byte主要是看byte 1,有几个1 就有几个byte。

strlen("李123")

上面的代码使用unicode的话就会返回6!下面来分析下大小端与字符编码的关系:

我们都知道小端就是low byte在前,high byte在后,典型使用这种方式就是x86架构。

  • 在GB2312中 李123 = e6 9d 8e 31 32 33,那么他在小端机器中,文档中打开也是这个样子:e6 9d 8e 31 32 33
  • 在utf-16中 李123 = 67 4e  00 31 00 32 00 33 在文档中打开:4e 67 31 00 32 00 33 00。因为他是以两个byte为一个单位。
  • 在utf-8中 李123=e6 9d 8e 31 32 33 在文档中打开也是:e6 9d 8e 31 32 33

所以基于上述知识,我们知道在notepad打开一个文档,有时候会读取BOM!BOM 位于文档的开头位置

  • FE FF 开头 ->UTF-16 Big Endian
  • FF FE 开头 ->UTF-16 Little Endian
  • EF BB BF 开头 -> UTF-8
  • 都不是,看系统默认编码 (GB2312?)

所以我们在代码读取文档的时候,要小心BOM的存在,BOM 可以告诉你后续内容的编码方式,有时候必须跳过 BOM,不要把 BOM 当成内容一起处理。

在Linux 中解决代码转换问题:iconv,而一些特定的语言例如python使用 str.encode(‘utf-8’)。

I18N:所有的语言都写在外部txt,方便做本地适配,代码也不用重新编译。

 

[1] http://en.wikipedia.org/wiki/UTF-8

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

March 24th, 2015 by JasonLe's Tech 1,851 views

物理内存管理:请求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