内存学习（七）：伙伴分配器（正式版）3-阿里云开发者社区

伙伴分配器

4-每处理器页集合

内核针对分配单页做了性能优化，为了减少处理器之间的锁竞争，在内存区域增加1个每处理器页集合。

include/linux/mmzone.h
    struct zone {
          …
          struct per_cpu_pageset __percpu *pageset;  /* 在每个处理器上有一个页集合 */
          …
    } ____cacheline_internodealigned_in_smp;
   struct per_cpu_pageset {
          struct per_cpu_pages pcp;
          …
    };
   struct per_cpu_pages {
          int count;      /* 链表里面页的数量 */
          int high;       /* 如果页的数量达到高水线，需要返还给伙伴分配器 */
          int batch;      /* 批量添加或删除的页数量 */
         struct list_head lists[MIGRATE_PCPTYPES]; /* 每种迁移类型一个页链表 */
    };

内存区域在每个处理器上有一个页集合，页集合中每种迁移类型有一个页链表。页集合有高水线和批量值，页集合中的页数量不能超过高水线。申请单页加入页链表，或者从页链表返还给伙伴分配器，都是采用批量操作，一次操作的页数量是批量值。

默认的批量值batch的计算方法如下。

（1）batch = zone->managed_pages / 1024，其中zone->managed_pages是内存区域中由伙伴分配器管理的页数量。
（2）如果batch超过(512 * 1024) / PAGE_SIZE，那么把batch设置为(512 * 1024) / PAGE_SIZE，其中PAGE_SIZE是页长度。
（3）batch = batch / 4。
（4）如果batch小于1，那么把batch设置为1。
（5）batch = rounddown_pow_of_two(batch * 1.5) − 1，其中rounddown_pow_of_two()用来把数值向下对齐到2的n次幂。

默认的高水线是批量值的6倍。

可以通过文件“/proc/sys/vm/percpu_pagelist_fraction”修改比例值，最小值是8，默认值是0。高水线等于（伙伴分配器管理的页数量 / 比例值），同时把批量值设置为高水线的1/4。

从某个内存区域申请某种迁移类型的单页时，从当前处理器的页集合中该迁移类型的页链表分配页，如果页链表是空的，先批量申请页加入页链表，然后分配一页。

缓存热页是指刚刚访问过物理页，物理页的数据还在处理器的缓存中。如果要申请缓存热页，从页链表首部分配页；如果要申请缓存冷页，从页链表尾部分配页。

释放单页时，把页加入当前处理器的页集合中。如果释放缓存热页，加入页链表首部；如果释放缓存冷页，加入页链表尾部。如果页集合中的页数量大于或等于高水线，那么批量返还给伙伴分配器。

5-分配页

1．分配接口

页分配器提供了以下分配页的接口。

（1）alloc_pages(gfp_mask, order)请求分配一个阶数为order的页块，返回一个page实例。
（2）alloc_page(gfp_mask)是函数alloc_pages在阶数为0情况下的简化形式，只分配一页。
（3）__get_free_pages(gfp_mask, order)对函数alloc_pages做了封装，只能从低端内存区域分配页，并且返回虚拟地址。
（4）__get_free_page(gfp_mask)是函数__get_free_pages在阶数为0情况下的简化形式，只分配一页。
（5）get_zeroed_page(gfp_mask)是函数__get_free_pages在为参数gfp_mask设置了标志位__GFP_ZERO且阶数为0情况下的简化形式，只分配一页，并且用零初始化。

2．分配标志位

2．分配标志位分配页的函数都带一个分配标志位参数，分配标志位分为以下5类（标志位名称中的GFP是Get Free Pages的缩写）。

（1）区域修饰符：指定从哪个区域类型分配页，第二节已经描述了根据分配标志得到首选区域类型的方法。

__GFP_DMA：从DMA区域分配页。
__GFP_HIGHMEM：从高端内存区域分配页。
__GFP_DMA32：从DMA32区域分配页。
__GFP_MOVABLE：从可移动区域分配页。

（2）页移动性和位置提示：指定页的迁移类型和从哪些内存节点分配页。

__GFP_MOVABLE：申请可移动页，也是区域修饰符。
__GFP_RECLAIMABLE：申请可回收页。
__GFP_WRITE：指明调用者打算写物理页。只要有可能，把这些页分布到本地节点的所有区域，避免所有脏页在一个内存区域。
__GFP_HARDWALL：实施cpuset内存分配策略。cpuset是控制组（cgroup）的一个子系统，提供了把处理器和内存节点的集合分配给一组进程的机制，即允许进程在哪些处理器上运行和从哪些内存节点申请页。
__GFP_THISNODE：强制从指定节点分配页。
__GFP_ACCOUNT：把分配的页记账到内核内存控制组。

（3）水线修饰符。

__GFP_HIGH：指明调用者是高优先级的，为了使系统能向前推进，必须准许这个请求。例如，创建一个I/O上下文，把脏页回写到存储设备。
__GFP_ATOMIC：指明调用者是高优先级的，不能回收页或者睡眠。典型的例子是中断处理程序。
__GFP_MEMALLOC：允许访问所有内存。只能在调用者承诺“给我少量紧急保留内存使用，我可以释放更多的内存”的时候使用。
__GFP_NOMEMALLOC：禁止访问紧急保留内存，如果这个标志位和__GFP_MEMALLOC同时被设置，优先级比后者高。

（4）回收修饰符。

__GFP_IO：允许读写存储设备。
__GFP_FS：允许向下调用到底层文件系统。当文件系统申请页的时候，如果内存严重不足，直接回收页，把脏页回写到存储设备，调用文件系统的函数，可能导致死锁。为了避免死锁，文件系统申请页的时候应该清除这个标志位。
__GFP_DIRECT_RECLAIM：调用者可以直接回收页。
__GFP_KSWAPD_RECLAIM：当空闲页数达到低水线的时候，调用者想要唤醒页回收线程kswapd，即异步回收页。
__GFP_RECLAIM：允许直接回收页和异步回收页。
__GFP_REPEAT：允许重试，重试多次以后放弃，分配可能失败。
__GFP_NOFAIL：必须无限次重试，因为调用者不能处理分配失败。
__GFP_NORETRY：不要重试，当直接回收页和内存碎片整理不能使分配成功的时候，应该放弃。

（5）行动修饰符。

__GFP_COLD：调用者不期望分配的页很快被使用，尽可能分配缓存冷页（数据不在处理器的缓存中）。
__GFP_NOWARN：如果分配失败，不要打印警告信息。
__GFP_COMP：把分配的页块组成复合页（compound page）。
__GFP_ZERO：把页用零初始化。

3．标志位组合

因为这些标志位总是组合使用，所以内核定义了一些标志位组合。常用的标志位组合如下。

（1）GFP_ATOMIC：原子分配，分配内核使用的页，不能睡眠。调用者是高优先级的，允许异步回收页。

#define GFP_ATOMIC   (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)

（2）GFP_KERNEL：分配内核使用的页，可能睡眠。从低端内存区域分配页，允许异步回收页和直接回收页，允许读写存储设备，允许调用到底层文件系统。

#define GFP_KERNEL   (__GFP_RECLAIM | __GFP_IO | __GFP_FS)

（3）GFP_NOWAIT：分配内核使用的页，不能等待。允许异步回收页，不允许直接回收页，不允许读写存储设备，不允许调用到底层文件系统。

#define GFP_NOWAIT   (__GFP_KSWAPD_RECLAIM)

（4）GFP_NOIO：不允许读写存储设备，允许异步回收页和直接回收页。请尽量避免直接使用这个标志位，应该使用函数memalloc_noio_save和memalloc_noio_restore标记一个不能读写存储设备的范围，前者设置进程标志位PF_MEMALLOC_NOIO，后者清除进程标志位PF_MEMALLOC_NOIO。

#define GFP_NOIO   (__GFP_RECLAIM)

（5）GFP_NOFS：不允许调用到底层文件系统，允许异步回收页和直接回收页，允许读写存储设备。请尽量避免直接使用这个标志位，应该使用函数memalloc_nofs_save和memalloc_nofs_restore标记一个不能调用到文件系统的范围，前者设置进程标志位PF_MEMALLOC_NOFS，后者清除进程标志位PF_MEMALLOC_NOFS。

#define GFP_NOFS   (__GFP_RECLAIM | __GFP_IO)

（6）GFP_USER：分配用户空间使用的页，内核或硬件也可以直接访问，从普通区域分配，允许异步回收页和直接回收页，允许读写存储设备，允许调用到文件系统，允许实施cpuset内存分配策略。

#define GFP_USER   (__GFP_RECLAIM | __GFP_IO | __GFP_FS | __GFP_HARDWALL)

（7）GFP_HIGHUSER：分配用户空间使用的页，内核不需要直接访问，从高端内存区域分配，物理页在使用的过程中不可以移动。

#define GFP_HIGHUSER   (GFP_USER | __GFP_HIGHMEM)

（8）GFP_HIGHUSER_MOVABLE：分配用户空间使用的页，内核不需要直接访问，物理页可以通过页回收或页迁移技术移动。

#define GFP_HIGHUSER_MOVABLE   (GFP_HIGHUSER | __GFP_MOVABLE)

（9）GFP_TRANSHUGE_LIGHT：分配用户空间使用的巨型页，把分配的页块组成复合页，禁止使用紧急保留内存，禁止打印警告信息，不允许异步回收页和直接回收页。

#define GFP_TRANSHUGE_LIGHT   ((GFP_HIGHUSER_MOVABLE | __GFP_COMP | \
                  __GFP_NOMEMALLOC | __GFP_NOWARN) & ~__GFP_RECLAIM)

（10）GFP_TRANSHUGE：分配用户空间使用的巨型页，和GFP_TRANSHUGE_LIGHT的区别是允许直接回收页。

#define GFP_TRANSHUGE   (GFP_TRANSHUGE_LIGHT | __GFP_DIRECT_RECLAIM)

4．复合页

如果设置了标志位__GFP_COMP并且分配了一个阶数大于0的页块，页分配器会把页块组成复合页（compound page）。复合页最常见的用处是创建巨型页。

复合页的第一页叫首页（head page），其他页都叫尾页（tail page）。一个由n阶页块组成的复合页的结构如图所示。

（1）首页设置标志PG_head。
（2）第一个尾页的成员compound_mapcount表示复合页的映射计数，即多少个虚拟页映射到这个物理页，初始值是−1。这个成员和成员mapping组成一个联合体，占用相同的位置，其他尾页把成员mapping设置为一个有毒的地址。
（3）第一个尾页的成员compound_dtor存放复合页释放函数数组的索引，成员compound_order存放复合页的阶数n。这两个成员和成员lru.prev占用相同的位置。
（4）所有尾页的成员compound_head存放首页的地址，并且把最低位设置为1。这个成员和成员lru.next占用相同的位置。

判断一个页是复合页的成员的方法是：页设置了标志位PG_head（针对首页），或者页的成员compound_head的最低位是1（针对尾页）。

结构体page中复合页的成员如下：

include/linux/mm_types.h
    struct page {
          unsigned long flags;
          union {
              struct address_space *mapping;
              atomic_t compound_mapcount;   /* 映射计数，第一个尾页 */
              /* page_deferred_list().next    -- 第二个尾页 */
          };
          …
          union {
              struct list_head lru;
              /* 复合页的尾页 */
              struct {
                  unsigned long compound_head; /* 首页的地址，并且设置最低位 */
                  /* 第一个尾页 */
    #ifdef CONFIG_64BIT
                  unsigned int compound_dtor;  /* 复合页释放函数数组的索引 */
                  unsigned int compound_order; /* 复合页的阶数 */
    #else
                  unsigned short int compound_dtor;
                  unsigned short int compound_order;
    #endif
            };
        };
        …
    }；

5．对高阶原子分配的优化处理

高阶原子分配：阶数大于0，并且调用者设置了分配标志位__GFP_ATOMIC，要求不能睡眠。
页分配器对高阶原子分配做了优化处理，增加了高阶原子类型（MIGRATE_HIGHATOMIC），在内存区域的结构体中增加1个成员“nr_reserved_highatomic”，用来记录高阶原子类型的总页数，并且限制其数量：zone->nr_reserved_highatomic < (zone->managed_pages / 100) + pageblock_nr_pages，即必须小于（伙伴分配器管理的总页数 / 100 + 分组阶数对应的页数）。

include/linux/mmzone.h
    struct zone {
          …
          unsigned long nr_reserved_highatomic;
          …
    } ____cacheline_internodealigned_in_smp;

执行高阶原子分配时，先从高阶原子类型分配页，如果分配失败，从调用者指定的迁移类型分配页。分配成功以后，如果内存区域中高阶原子类型的总页数小于限制，并且页块的迁移类型不是高阶原子类型、隔离类型和CMA迁移类型，那么把页块的迁移类型转换为高阶原子类型，并且把页块中没有分配出去的页移到高阶原子类型的空闲链表中。

当内存严重不足时，直接回收页以后仍然分配失败，针对高阶原子类型的页数超过pageblock_nr_pages的目标区域，把高阶原子类型的页块转换成申请的迁移类型，然后重试分配，其代码如下：

mm/page_alloc.c
    static inline struct page *
    __alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
              unsigned int alloc_flags, const struct alloc_context *ac,
              unsigned long *did_some_progress)
    {
        struct page *page = NULL;
        bool drained = false;
       *did_some_progress = __perform_reclaim(gfp_mask, order, ac); /* 直接回收页 */
        if (unlikely(! (*did_some_progress)))
              return NULL;
   retry:
        page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
       if (! page && ! drained) {
              /* 把高阶原子类型的页块转换成申请的迁移类型 */
              unreserve_highatomic_pageblock(ac, false);
              drain_all_pages(NULL);
              drained = true;
              goto retry;
        }
       return page;
    }

如果直接回收页没有进展超过16次，那么针对目标区域，不再为高阶原子分配保留页，把高阶原子类型的页块转换成申请的迁移类型，其代码如下：

mm/page_alloc.c
    static inline bool
    should_reclaim_retry(gfp_t gfp_mask, unsigned order,
                    struct alloc_context *ac, int alloc_flags,
                    bool did_some_progress, int *no_progress_loops)
    {
        …
        if (did_some_progress && order <= PAGE_ALLOC_COSTLY_ORDER)
              *no_progress_loops = 0;
        else
              (*no_progress_loops)++;
       if (*no_progress_loops > MAX_RECLAIM_RETRIES) {
              /* 在调用内存耗尽杀手之前，用完为高阶原子分配保留的页 */
              return unreserve_highatomic_pageblock(ac, true);
        }
        …
    }

6．核心函数的实现

所有分配页的函数最终都会调用到函数__alloc_pages_nodemask，这个函数被称为分区的伙伴分配器的心脏。

1-__alloc_pages_nodemask

函数原型如下：

struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
                  struct zonelist *zonelist, nodemask_t *nodemask);

参数如下。

（1）gfp_mask：分配标志位。
（2）order：阶数。
（3）zonelist：首选内存节点的备用区域列表。如果指定了标志位__GFP_THISNODE，选择pg_data_t.node_zonelists[ZONELIST_NOFALLBACK]，否则选择pg_data_t.node_zonelists [ZONELIST_FALLBACK]。
（4）nodemask：允许从哪些内存节点分配页，如果调用者没有要求，可以传入空指针。

算法如下。

（1）根据分配标志位得到首选区域类型和迁移类型。
（2）执行快速路径，使用低水线尝试第一次分配。
（3）如果快速路径分配失败，那么执行慢速路径。

页分配器定义了以下内部分配标志位：

mm/internal.h
    #define ALLOC_WMARK_MIN      WMARK_MIN  /* 0x00，使用最低水线 */
    #define ALLOC_WMARK_LOW      WMARK_LOW  /* 0x01，使用低水线 */
    #define ALLOC_WMARK_HIGH     WMARK_HIGH /* 0x02，使用高水线 */
    #define ALLOC_NO_WATERMARKS  0x04       /* 完全不检查水线 */
    #define ALLOC_WMARK_MASK  (ALLOC_NO_WATERMARKS-1) /* 得到水线位的掩码 */
    #define ALLOC_HARDER   0x10 /* 试图更努力分配 */
    #define ALLOC_HIGH     0x20 /* 设置了__GFP_HIGH，调用者是高优先级的 */
    #define ALLOC_CPUSET   0x40 /* 检查cpuset 是否允许进程从某个内存节点分配页 */
    #define ALLOC_CMA      0x80 /* 允许从CMA（连续内存分配器）迁移类型分配 */

2-get_page_from_freelist

（1）快速路径。快速路径调用函数get_page_from_freelist，函数的代码如下：

mm/page_alloc.c
    1   static struct page *
    2   get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
    3                              const struct alloc_context *ac)
    4   {
    5   struct zoneref *z = ac->preferred_zoneref;
    6   struct zone *zone;
    7   struct pglist_data *last_pgdat_dirty_limit = NULL;
    8
    9   for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
    10                                        ac->nodemask) {
    11       struct page *page;
    12       unsigned long mark;
    13
    14       if (cpusets_enabled() &&
    15             (alloc_flags & ALLOC_CPUSET) &&
    16             ! __cpuset_zone_allowed(zone, gfp_mask))
    17                  continue;
    18
    19       if (ac->spread_dirty_pages) {
    20             if (last_pgdat_dirty_limit == zone->zone_pgdat)
    21                  continue;
    22
    23             if (! node_dirty_ok(zone->zone_pgdat)) {
    24                  last_pgdat_dirty_limit = zone->zone_pgdat;
    25                  continue;
    26             }
    27       }
    28
    29       mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
    30       if (! zone_watermark_fast(zone, order, mark,
    31                        ac_classzone_idx(ac), alloc_flags)) {
    32             int ret;
    33
    34             BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
    35             if (alloc_flags & ALLOC_NO_WATERMARKS)
    36                  goto try_this_zone;
    37
    38             if (node_reclaim_mode == 0 ||
    39                 ! zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
    40                   continue;
    41
    42             ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
    43             switch (ret) {
    44             case NODE_RECLAIM_NOSCAN:
    45                  /* 没有扫描 */
    46                  continue;
    47             case NODE_RECLAIM_FULL:
    48                  /* 扫描过但是不可回收 */
    49                  continue;
    50             default:
    51                  /* 回收了足够的页，重新检查水线 */
    52                  if (zone_watermark_ok(zone, order, mark,
    53                           ac_classzone_idx(ac), alloc_flags))
    54                       goto try_this_zone;
    55
    56                  continue;
    57             }
    58       }
    59
    60   try_this_zone:
    61       page = rmqueue(ac->preferred_zoneref->zone, zone, order,
    62                  gfp_mask, alloc_flags, ac->migratetype);
    63       if (page) {
    64             prep_new_page(page, order, gfp_mask, alloc_flags);
    65
    66             /* 如果这是一个高阶原子分配，那么检查这个页块是否应该被保留 */
    67             if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
    68                  reserve_highatomic_pageblock(page, zone, order);
    69
    70             return page;
    71       }
    72   }
    73
    74   return NULL;
    75   }

第9行代码，扫描备用区域列表中每个满足条件的区域：“区域类型小于或等于首选区域类型，并且内存节点在节点掩码中的相应位被设置”，处理如下。
第14～17行代码，如果编译了cpuset功能，调用者设置ALLOC_CPUSET要求使用cpuset检查，并且cpuset不允许当前进程从这个内存节点分配页，那么不能从这个区域分配页。
第19～27行代码，如果调用者设置标志位__GFP_WRITE，表示文件系统申请分配一个页缓存页用于写文件，那么检查内存节点的脏页数量是否超过限制。如果超过限制，那么不能从这个区域分配页。
第30行代码，检查水线，如果（区域的空闲页数 − 申请的页数）小于水线，处理如下。
❑ 第35行代码，如果调用者要求不检查水线，那么可以从这个区域分配页。
❑ 第38～40行代码，如果没有开启节点回收功能，或者当前节点和首选节点之间的距离大于回收距离，那么不能从这个区域分配页。
❑ 第42～57行代码，从节点回收没有映射到进程虚拟地址空间的文件页和块分配器申请的页，然后重新检查水线，如果（区域的空闲页数 − 申请的页数）还是小于水线，那么不能从这个区域分配页。
4）第61行代码，从当前区域分配页。
5）第64～68行代码，如果分配成功，调用函数prep_new_page以初始化页。如果是高阶原子分配，并且区域中高阶原子类型的页数没有超过限制，那么把分配的页所属的页块转换为高阶原子类型。

3-zone_watermark_fast

函数zone_watermark_fast负责检查区域的空闲页数是否大于水线，其代码如下：

mm/page_alloc.c
    1   static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
    2         unsigned long mark, int classzone_idx, unsigned int alloc_flags)
    3   {
    4    long free_pages = zone_page_state(z, NR_FREE_PAGES);
    5    long cma_pages = 0;
    6
    7   #ifdef CONFIG_CMA
    8    if (! (alloc_flags & ALLOC_CMA))
    9         cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);
    10   #endif
    11
    12    /* 只快速检查0阶 */
    13    if (! order && (free_pages - cma_pages) > mark + z->lowmem_reserve[classzone_idx])
    14         return true;
    15
    16    return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
    17                         free_pages);
    18   }

第7～14行代码，针对0阶执行快速检查。

1）第8行和第9行代码，如果不允许从CMA迁移类型分配，那么不要使用空闲的CMA页，必须把空闲页数减去空闲的CMA页数。
2）第13行代码，如果空闲页数大于（水线 + 低端内存保留页数），即（空闲页数 − 申请的一页）大于等于（水线 + 低端内存保留页数），那么允许从这个区域分配页。
第16行代码，如果是其他情况，那么调用函数__zone_watermark_ok进行检查。

4-__zone_watermark_ok

函数__zone_watermark_ok更加仔细地检查区域的空闲页数是否大于水线，其代码如下：

mm/page_alloc.c
    1   bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
    2               int classzone_idx, unsigned int alloc_flags,
    3               long free_pages)
    4   {
    5    long min = mark;
    6    int o;
    7    const bool alloc_harder = (alloc_flags & ALLOC_HARDER);
    8
    9    free_pages -= (1 << order) - 1;
    10
    11   if (alloc_flags & ALLOC_HIGH)
    12        min -= min / 2;
    13
    14   /* 如果调用者没有要求更努力分配，那么减去为高阶原子分配保留的页数 */
    15   if (likely(! alloc_harder))
    16        free_pages -= z->nr_reserved_highatomic;
    17   else
    18        min -= min / 4;
    19
    20   #ifdef CONFIG_CMA
    21   if (! (alloc_flags & ALLOC_CMA))
    22        free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);
    23   #endif
    24
    25    if (free_pages <= min + z->lowmem_reserve[classzone_idx])
    26         return false;
    27
    28    if (! order)
    29         return true;
    30
    31    /* 对于高阶请求，检查至少有一个合适的页块是空闲的 */
    32    for (o = order; o < MAX_ORDER; o++) {
    33         struct free_area *area = &z->free_area[o];
    34         int mt;
    35
    36         if (! area->nr_free)
    37               continue;
    38
    39         if (alloc_harder)
    40               return true;
    41
    42         for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {
    43               if (! list_empty(&area->free_list[mt]))
    44                    return true;
    45         }
    46
    47   #ifdef CONFIG_CMA
    48         if ((alloc_flags & ALLOC_CMA) &&
    49             ! list_empty(&area->free_list[MIGRATE_CMA])) {
    50               return true;
    51         }
    52   #endif
    53    }
    54    return false;
    55   }

第9行代码，把空闲页数减去申请页数，然后减1。
第12行代码，如果调用者是高优先级的，把水线减半。
第15～18行代码，如果调用者要求更努力分配，把水线减去1/4；如果调用者没有要求更努力分配，把空闲页数减去高阶原子类型的页数。
第21～22行代码，如果不允许从CMA迁移类型分配，那么不能使用空闲的CMA页，把空闲页数减去空闲的CMA页数。
第25行代码，如果（空闲页数 − 申请页数 + 1）小于或等于（水线 + 低端内存保留页数），即（空闲页数 − 申请页数）小于（水线 + 低端内存保留页数），那么不能从这个区域分配页。
第28行代码，如果只申请一页，那么允许从这个区域分配页。
第32～53行代码，如果申请阶数大于0，检查过程如下。
1）第39行代码，如果调用者要求更努力分配，只要有一个阶数大于或等于申请阶数的空闲页块，就允许从这个区域分配页。
2）第42～45行代码，不可移动、可移动和可回收任何一种迁移类型，只要有一个阶数大于或等于申请阶数的空闲页块，就允许从这个区域分配页。
3）第48～51行代码，如果调用者指定从CMA迁移类型分配，CMA迁移类型只要有一个阶数大于或等于申请阶数的空闲页块，就允许从这个区域分配页。
4）其他情况不允许从这个区域分配页。

5-rmqueue

函数rmqueue负责分配页，其代码如下：

mm/page_alloc.c
    1   static inline
    2   struct page *rmqueue(struct zone *preferred_zone,
    3               struct zone *zone, unsigned int order,
    4               gfp_t gfp_flags, unsigned int alloc_flags,
    5               int migratetype)
    6   {
    7    unsigned long flags;
    8    struct page *page;
    9
    10   if (likely(order == 0)) {
    11        page = rmqueue_pcplist(preferred_zone, zone, order,
    12                   gfp_flags, migratetype);
    13        goto out;
    14   }
    15
    16   /* 如果申请阶数大于1，不要试图无限次重试。*/
    17   WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
    18   spin_lock_irqsave(&zone->lock, flags);
    19
    20   do {
    21        page = NULL;
    22        if (alloc_flags & ALLOC_HARDER) {
    23              page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
    24              …
    25        }
    26        if (! page)
    27              page = __rmqueue(zone, order, migratetype);
    28   } while (page && check_new_pages(page, order));
    29   spin_unlock(&zone->lock);
    30   if (! page)
    31        goto failed;
    32   …
    33   local_irq_restore(flags);
    34
    35  out:
    36   VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
    37   return page;
    38
    39  failed:
    40   local_irq_restore(flags);
    41   return NULL;
    42  }

第10～14行代码，如果申请阶数是0，那么从每处理器页集合分配页。如果申请阶数大于0，处理过程如下。
1）第22行和第23行代码，如果调用者要求更努力分配，先尝试从高阶原子类型分配页。
2）第27行代码，从指定迁移类型分配页。

6-rmqueue_pcplist

函数rmqueue_pcplist负责从内存区域的每处理器页集合分配页，把主要工作委托给函数__rmqueue_pcplist。函数__rmqueue_pcplist的代码如下：

mm/page_alloc.c
    1   static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
    2               bool cold, struct per_cpu_pages *pcp,
    3               struct list_head *list)
    4   {
    5   struct page *page;
    6
    7   do {
    8        if (list_empty(list)) {
    9              pcp->count += rmqueue_bulk(zone, 0,
    10                       pcp->batch, list,
    11                       migratetype, cold);
    12             if (unlikely(list_empty(list)))
    13                  return NULL;
    14       }
    15
    16       if (cold)
    17             page = list_last_entry(list, struct page, lru);
    18       else
    19             page = list_first_entry(list, struct page, lru);
    20
    21       list_del(&page->lru);
    22       pcp->count--;
    23   } while (check_new_pcp(page));
    24
    25   return page;
    26  }

第8～11行代码，如果每处理器页集合中指定迁移类型的链表是空的，那么批量申请页加入链表。
第16～19行代码，分配一页，如果调用者指定标志位__GFP_COLD要求分配缓存冷页，就从链表尾部分配一页，否则从链表首部分配一页。

7-__rmqueue

函数__rmqueue的处理过程如下。

1）从指定迁移类型分配页，如果分配成功，那么处理结束。
2）如果指定迁移类型是可移动类型，那么从CMA类型盗用页。
3）从备用迁移类型盗用页。

mm/page_alloc.c
    static struct page *__rmqueue(struct zone *zone, unsigned int order,
                        int migratetype)
    {
          struct page *page;
   retry:
          page = __rmqueue_smallest(zone, order, migratetype);
          if (unlikely(! page)) {
                if (migratetype == MIGRATE_MOVABLE)
                      page = __rmqueue_cma_fallback(zone, order);
               if (! page && __rmqueue_fallback(zone, order, migratetype))
                      goto retry;
          }
         …
          return page;
    }

8-__rmqueue_smallest

函数__rmqueue_smallest从申请阶数到最大分配阶数逐个尝试：

如果指定迁移类型的空闲链表不是空的，从链表取出第一个页块；
如果页块阶数比申请阶数大，那么重复分裂页块，把后一半插入低一阶的空闲链表，直到获得一个大小为申请阶数的页块。

mm/page_alloc.c
    static inline
    struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
                              int migratetype)
    {
          unsigned int current_order;
          struct free_area *area;
          struct page *page;
          /* 在首选迁移类型的空闲链表中查找长度合适的页块 */
          for (current_order = order; current_order < MAX_ORDER; ++current_order) {
              area = &(zone->free_area[current_order]);
              page = list_first_entry_or_null(&area->free_list[migratetype],
                                        struct page, lru);
              if (! page)
                    continue;
              list_del(&page->lru);
              rmv_page_order(page);
              area->nr_free--;
              expand(zone, page, order, current_order, area, migratetype);
              set_pcppage_migratetype(page, migratetype);
              return page;
          }
          return NULL;
    }

9-__rmqueue_fallback

函数__rmqueue_fallback负责从备用迁移类型盗用页，从最大分配阶向下到申请阶数逐个尝试，依次查看备用类型优先级列表中的每种迁移类型是否有空闲页块，如果有，就从这种迁移类型盗用页。

mm/page_alloc.c
    static inline bool
    __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
    {
        struct free_area *area;
        unsigned int current_order;
        struct page *page;
        int fallback_mt;
        bool can_steal;
        /* 在备用迁移类型的空闲链表中找到最大的页块 */
        for (current_order = MAX_ORDER-1;
                      current_order >= order && current_order <= MAX_ORDER-1;
                      --current_order) {
              area = &(zone->free_area[current_order]);
              fallback_mt = find_suitable_fallback(area, current_order,
                      start_migratetype, false, &can_steal);
              if (fallback_mt == -1)
                    continue;
             page = list_first_entry(&area->free_list[fallback_mt],
                                    struct page, lru);
             steal_suitable_fallback(zone, page, start_migratetype,
                                            can_steal);
              ...
              return true;
        }
        return false;
    }

7. 慢速路径

如果使用低水线分配失败，那么执行慢速路径，慢速路径是在函数__alloc_pages_slowpath中实现的，执行流程如图所示，主要步骤如下。

1）如果允许异步回收页，那么针对每个目标区域，唤醒区域所属内存节点的页回收线程。
2）使用最低水线尝试分配。
3）针对申请阶数大于0：如果允许直接回收页，那么执行异步模式的内存碎片整理，然后尝试分配。
4）如果调用者承诺“给我少量紧急保留内存使用，我可以释放更多的内存”，那么在忽略水线的情况下尝试分配。
5）直接回收页，然后尝试分配。
6）针对申请阶数大于0：执行同步模式的内存碎片整理，然后尝试分配。
7）如果多次尝试直接回收页和同步模式的内存碎片整理，仍然分配失败，那么使用杀伤力比较大的内存耗尽杀手选择一个进程杀死，然后尝试分配。

页分配器认为阶数大于3是昂贵的分配，有些地方做了特殊处理。

1-__alloc_pages_slowpath

函数__alloc_pages_slowpath的主要代码如下：

mm/page_alloc.c
    static inline struct page *
    __alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
                                struct alloc_context *ac)
    {
          bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
          const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
          struct page *page = NULL;
          unsigned int alloc_flags;
          unsigned long did_some_progress;
          enum compact_priority compact_priority;
          enum compact_result compact_result;
          int compaction_retries;
          int no_progress_loops;
          unsigned long alloc_start = jiffies;
          unsigned int stall_timeout = 10 * HZ;
          unsigned int cpuset_mems_cookie;
         /* 申请阶数不能超过页分配器支持的最大分配阶 */
          if (order >= MAX_ORDER) {
                WARN_ON_ONCE(! (gfp_mask & __GFP_NOWARN));
                return NULL;
          }
         ...
    retry_cpuset:
          compaction_retries = 0;
          no_progress_loops = 0;
          compact_priority = DEF_COMPACT_PRIORITY;
          /*
          * 后面可能检查cpuset是否允许当前进程从哪些内存节点申请页，
          * 需要读当前进程的成员mems_allowed。使用顺序锁保护
          */
          cpuset_mems_cookie = read_mems_allowed_begin();
         /* 把分配标志位转换成内部分配标志位 */
          alloc_flags = gfp_to_alloc_flags(gfp_mask);
         /* 获取首选的内存区域 */
          ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
                            ac->high_zoneidx, ac->nodemask);
          if (! ac->preferred_zoneref->zone)
                goto nopage;
         /* 异步回收页，唤醒页回收线程 */
          if (gfp_mask & __GFP_KSWAPD_RECLAIM)
                wake_all_kswapds(order, ac);
         /* 使用最低水线分配页 */
          page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
          if (page)
                goto got_pg;
         /*
          * 针对申请阶数大于0，如果满足以下3个条件。
          * （1）允许直接回收页。
          * （2）申请阶数大于3，或者指定迁移类型不是可移动类型。
    * （3）调用者没有承诺“给我少量紧急保留内存使用，我可以释放更多的内存”。
    * 那么执行异步模式的内存碎片整理
    */
  if (can_direct_reclaim &&
              (costly_order ||
                (order > 0 && ac->migratetype ! = MIGRATE_MOVABLE))
              && ! gfp_pfmemalloc_allowed(gfp_mask)) {
        page = __alloc_pages_direct_compact(gfp_mask, order,
                            alloc_flags, ac,
                            INIT_COMPACT_PRIORITY,
                            &compact_result);
        if (page)
              goto got_pg;
       /* 申请阶数大于3，并且调用者要求不要重试 */
        if (costly_order && (gfp_mask & __GFP_NORETRY)) {
              /*
                * 同步模式的内存碎片整理最近失败了，所以内存碎片整理被延迟执行，
                * 没必要继续尝试分配
                */
              if (compact_result == COMPACT_DEFERRED)
                    goto nopage;
              /*
                * 同步模式的内存碎片整理代价太大，继续使用异步模式的
                * 内存碎片整理
                */
              compact_priority = INIT_COMPACT_PRIORITY;
        }
  }
retry:
  /* 确保页回收线程在我们循环的时候不会意外地睡眠 */
  if (gfp_mask & __GFP_KSWAPD_RECLAIM)
          wake_all_kswapds(order, ac);
 /*
    * 如果调用者承诺“给我少量紧急保留内存使用，我可以释放更多的内存”，
    * 则忽略水线
    */
  if (gfp_pfmemalloc_allowed(gfp_mask))
          alloc_flags = ALLOC_NO_WATERMARKS;
 /*
    * 如果调用者没有要求使用cpuset，或者要求忽略水线，那么重新获取区域列表
    */
  if (! (alloc_flags & ALLOC_CPUSET) || (alloc_flags & ALLOC_NO_WATERMARKS)) {
          ac->zonelist = node_zonelist(numa_node_id(), gfp_mask);
          ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
                        ac->high_zoneidx, ac->nodemask);
  }
 /* 使用可能调整过的区域列表和分配标志尝试 */
  page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
  if (page)
          goto got_pg;
 /* 调用者不愿意等待，不允许直接回收页，那么放弃 */
  if (! can_direct_reclaim)
          goto nopage;
 …
    /*
      * 直接回收页的时候给进程设置了标志位PF_MEMALLOC，在直接回收页的过程中
      * 可能申请页，为了防止直接回收递归，这里发现进程设置了标志位PF_MEMALLOC，
      * 立即放弃
      */
    if (current->flags & PF_MEMALLOC)
          goto nopage;
   /* 直接回收页 */
    page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,
                                &did_some_progress);
    if (page)
          goto got_pg;
   /* 针对申请阶数大于0，执行同步模式的内存碎片整理 */
    page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
                      compact_priority, &compact_result);
    if (page)
          goto got_pg;
   /* 如果调用者要求不要重试，那么放弃 */
    if (gfp_mask & __GFP_NORETRY)
          goto nopage;
   /* 如果申请阶数大于3，并且调用者没有要求重试，那么放弃 */
    if (costly_order && ! (gfp_mask & __GFP_REPEAT))
          goto nopage;
    /* 检查重新尝试回收页是否有意义 */
    if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
                      did_some_progress > 0, &no_progress_loops))
          goto retry;
   /*
      * 申请阶数大于0：判断是否应该重试内存碎片整理。
      * did_some_progress > 0表示直接回收页有进展。
      * 如果直接回收页没有进展，那么重试内存碎片整理没有意义，
      * 因为内存碎片整理的当前实现依赖足够多的空闲页
      */
    if (did_some_progress > 0 &&
              should_compact_retry(ac, order, alloc_flags,
                  compact_result, &compact_priority,
                  &compaction_retries))
          goto retry;
   /* 如果cpuset修改了允许当前进程从哪些内存节点申请页，那么需要重试 */
    if (read_mems_allowed_retry(cpuset_mems_cookie))
          goto retry_cpuset;
   /* 使用内存耗尽杀手选择一个进程杀死 */
    page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
    if (page)
          goto got_pg;
   /*
      * 如果当前进程正在被内存耗尽杀手杀死，并且忽略水线或者不允许使用
      * 紧急保留内存，那么不要无限循环
      */
    if (test_thread_flag(TIF_MEMDIE) &&
          (alloc_flags == ALLOC_NO_WATERMARKS ||
            (gfp_mask & __GFP_NOMEMALLOC)))
                goto nopage;
         /* 如果内存耗尽杀手取得进展，那么重试 */
          if (did_some_progress) {
                no_progress_loops = 0;
                goto retry;
          }
   nopage:
          /* 如果cpuset修改了允许当前进程从哪些内存节点申请页，那么需要重试 */
          if (read_mems_allowed_retry(cpuset_mems_cookie))
                goto retry_cpuset;
         /* 确保不能失败的请求没有漏掉，总是重试 */
          if (gfp_mask & __GFP_NOFAIL) {
                /* 同时要求不能失败和不能直接回收页，是错误用法 */
              if (WARN_ON_ONCE(! can_direct_reclaim))
                    goto fail;
             …
             /*
                * 先使用标志位ALLOC_HARDER|ALLOC_CPUSET尝试分配，
                * 如果分配失败，那么使用标志位ALLOC_HARDER尝试分配
                */
              page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_HARDER, ac);
              if (page)
                      goto got_pg;
             cond_resched();
              goto retry;
          }
    fail:
          warn_alloc(gfp_mask, ac->nodemask,
                    "page allocation failure: order:%u", order);
    got_pg:
          return page;
    }

2-gfp_to_alloc_flags

页分配器使用函数gfp_to_alloc_flags把分配标志位转换成内部分配标志位，其代码如下：

mm/page_alloc.c
    static inline unsigned int
    gfp_to_alloc_flags(gfp_t gfp_mask)
    {
        /* 使用最低水线，并且检查cpuset是否允许当前进程从某个内存节点分配页 */
        unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
       /* 假设__GFP_HIGH和ALLOC_HIGH相同，为了节省一个if分支 */
        BUILD_BUG_ON(__GFP_HIGH ! = (__force gfp_t) ALLOC_HIGH);
        alloc_flags |= (__force int) (gfp_mask & __GFP_HIGH);
       if (gfp_mask & __GFP_ATOMIC) {/* 原子分配 */
              /*
                * 原子分配：
                * 如果没有要求禁止使用紧急保留内存，那么需要更努力地分配。
                * 如果要求禁止使用紧急保留内存，那么不需要更努力地分配
                */
              if (! (gfp_mask & __GFP_NOMEMALLOC))
                      alloc_flags |= ALLOC_HARDER;
             /* 对于原子分配，忽略cpuset。*/
              alloc_flags &= ~ALLOC_CPUSET;
        } else if (unlikely(rt_task(current)) && ! in_interrupt())
                        /* 如果当前进程是实时进程，并且没有被中断抢占，那么需要更努力地分配 */
              alloc_flags |= ALLOC_HARDER;
   #ifdef CONFIG_CMA
        /* 可移动类型可以从CMA类型盗用页 */
        if (gfpflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)
                alloc_flags |= ALLOC_CMA;
    #endif
        return alloc_flags;
    }

参考来自前辈的书籍：《Linux内核深度解析》

内存学习（七）：伙伴分配器（正式版）3