3.2.4 Buddy System(伙伴系统)

3.2.4.1 算法思路

对于内存管理，一个最基础的需求就是对连续内存页面的分配与释放，而在对内存页面的分配与释放过程中，需要解决的一个重要问题就是如何避免内存出现大量的碎片。例如对于一个有4个页面的系统，系统发起了两次请求，每次申请一个页面，系统可以有如下两种分配策略：

在方案一中，剩下的两个页面被隔离开了，如果系统接下来想要申请两个连续页面，那么请求就会失败；而方案二中，被分配的两个页面是挨着的，系统还可以成功地申请两个连续的页面。不管实际上物理内存页面的数量如何，一个优秀的内存分配器都应该采用方案二这种方式来工作，尽可能地将可用页面保留成连续的区域。

这种碎片被称为外部碎片（External Fragmentation），与之相对应的是内部碎片（Internal Fragmentation），指在页内分配对象时造成的浪费，这在后续介绍Slab Allocator时会提及。

Linux内核使用Buddy System来负责连续页面的分配与释放，内核将连续的内存页面按照固定的数量进行分组，对于任何一个分组，合法的页面数量是 2^n 且 0<=n<=10, 大小相等且相邻的两个分组是彼此的Buddy, 例如下图中，当 n=1 时，组的页面数量是2, 此时 Group 1 与 Group 2 互为Buddy, 但Group 1 与 Group 3 由于隔开了，就不是Buddy.

我们定义Buddy这个概念的目的是在内存分配与释放的过程中，能够动态地维护尽可能长的连续内存。例如上图中，如果 Group1 与 Group 2 都被释放回来后，系统就将会对两个Buddy进行合并，形成一个数量更大的组Group 4, 这也是两个Buddy必须相邻的原因。在分配内存时，Buddy System 会首先根据请求的页面数量确定目标分组，如果请求的连续内存数量是k, 那么Buddy System 将选择满足 2^n >= k 的最小的数字n 对应的那个分组，如果Buddy System 中没有对应的分组，那么系统将会将更大的分组劈开形成一对Buddy, 然后看劈开后的分组是否适合，如果不行的话就继续劈开，直到到达合适的大小为止。下图演示了一个Buddy System 从64页连续内存中分配8页的过程：

系统本来只有一个64 页的分组，完成此次分配之后，系统中可用的分组如下：一个8页分组、一个16页分组、以及一个32页的分组，即图中红色方框的部分。由于每个分组的页数都满足 2^n, 为了避免分配页面时出现碎片，Buddy System要求分配时请求的页面数量也必须满足 2^n 的数字大小，如果实际请求的数字 k 不满足2的n次方的话，Buddy System会分配大于等于 k 的最小的2的某次方的那个数字进行分配，例如如果系统请求的页面数量是7, 那么系统实际上会分配8个页面。

当释放内存时，Buddy System 会查看释放分组的Buddy 是否空闲，如果空闲的话便会合并两个分组形成一个更大的分组，并递归该操作直到当前分组的Buddy 繁忙（指被分配出去还未释放）或已经形成最大数量的分组为止。例如上图中，如果系统释放刚刚分配回去的8 个页面的话，Buddy System 又会自底向上地合并所有的分组，最终又形成一个64页的分组。

由此可知，图2中的Group 2与 Group 3虽然数量相等且相邻，但他们并不是Buddy, 根据Buddy System 中对于分组数量的规定，两个分组如何可合并的话，那么第一个分组的首地址必然是合并后组内页面数量的整数倍。如果将Group 2与Group 3合并，将得到一个页数是4的分组，因此Group 2的起始地址应该是4的整数倍，但Group 2的起始地址是2, 因此Group 2与Group 3不会有合并的机会。

Buddy System是内存管理的基础，其分配的对象的连续的物理页面，这是一个比较大的粒度，内核会在Buddy System 之上构建更加精细的内存分配机制提供给程序使用，这就是后续将要介绍的Slab系统。

3.2.4.2 数据结构

Buddy System从 zone 中分配内存，zone 中使用一个数组来管理不同大小的Buddy, 该字段定义如下：

/* file: include/linux/mmzone.h */

struct zone {
    /* free areas of different sizes */
    struct free_area free_area[MAX_ORDER];
}

MAX_ORDER 的值是 11, 也就是说，Buddy System 一次能够分配的最大连续页面是 210=1024 个，即4M的连续内存。数组 free_area 每个索引 i 存放的就是大小为 2i 页面数量的分组，这样可以提升Buddy System分配内存时查找分组的效率。数据结构 free_area 的定义如下：

/* file: include/linux/mmzone.h */

struct free_area {
    struct list_head free_list[MIGRATE_TYPES];
    unsigned long nr_free;
};

free_area 中的空闲分组按照 MIGRATE_TYPES 进行了分组，每种类型都保存在一个双向链表中，这里我们将关注点放在Buddy System算法的实现上，不展开讨论 MIGRATE_TYPES.

分配内存时还需要很多标记类参数，例如指定目标 zone （是从 DMA 请求内存还是 NORMAL)、分配到的内存是否要全部置零、如果内存不足，是否可以触发内存回收机制等等，这些标记都定义在 include/linux/gfp.h 中，例如：

/* file: include/linux/gfp.h */

#define ___GFP_DMA      0x01u
#define ___GFP_HIGHMEM      0x02u
#define ___GFP_DMA32        0x04u
#define ___GFP_MOVABLE      0x08u
#define ___GFP_RECLAIMABLE  0x10u
#define ___GFP_HIGH     0x20u
#define ___GFP_IO       0x40u
#define ___GFP_FS       0x80u
#define ___GFP_ZERO     0x100u
#define ___GFP_ATOMIC       0x200u

/* 通过位运算将不同的标记组合起来 */
#define GFP_ATOMIC  (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
#define GFP_KERNEL  (__GFP_RECLAIM | __GFP_IO | __GFP_FS)
#define GFP_KERNEL_ACCOUNT (GFP_KERNEL | __GFP_ACCOUNT)
#define GFP_NOWAIT  (__GFP_KSWAPD_RECLAIM)

源文件中对每个标记位的作用都有详细的说明，这里不再一一讨论。特别指出的是，GFP是Get Free Page的简称，这些标记叫着GFP Flags, 他们控制着Buddy System分配内存时的行为。

3.2.4.3 分配内存

入口函数

涉及物理内存分配的主要代码在文件 include/linux/gpf.h 与 mm/page_alloc.c 中，本节的代码也都是摘自这两个文件。

内存分配的入口函数有很多，我们来看一个典型的入口函数申明：

/* file: include/linux/gfp.h */

static inline struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)
{
    return alloc_pages_node(numa_node_id(), gfp_mask, order);
}

函数接收两个参数，一个是 GFP Mask, 另一个用来指定页面数量：参数 order 表示需要申请 2^order 个连续页面。该函数是NUMA架构下的入口函数之一，其首先通过函数 numa_node_id 找到当前CPU所在的NUMA Node, 即定位目标 pglist_data 对象，然后调用 alloc_pages_node 函数进行内存分配。不管入口函数是哪个，最终都会调用到 __alloc_pages:

/* file: include/linux/gfp.h */

static inline struct page *
__alloc_pages(gfp_t gfp_mask, unsigned int order, int preferred_nid)
{
    return __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL);
}

总而言之，内核在向Buddy System申请内存时需要提供如下信息：

• 如果在NUMA架构下，需要指定目标Node

• 页面数量

• GFP Flags, 用来控制Buddy System的各种行为

函数 __alloc_pages_nodemask 是Buddy System 的核心，包含三部分：

1. 准备内存分配的上下文，即初始化各种参数并将其封装到数据结构 alloc_context 中

2. 尝试通过快速路径（fastpath）分配内存，快速路径表示系统能够直接满足内存分配请求

3. 尝试通过慢速路径（slowpath）分配内存，表示当前系统无法满足内存分配请求，系统会暂时挂起内存分配操作，并通过回收内存、规整（compact）内存、或者通过 OOM Killer 杀死某些进程回首内存之后，再尝试内存分配操作

函数的总体逻辑如下：

/* file: mm/page_alloc.c */

struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
                                    int preferred_nid, nodemask_t *nodemask)
{
  struct page *page;
  unsigned int alloc_flags = ALLOC_WMARK_LOW;
  gfp_t alloc_mask; /* The gfp_t that was actually used for allocation */
  struct alloc_context ac = {};

  /* 1. 第一步，准备内存分配的上下文 */
  if (!prepare_alloc_pages(gfp_mask, order, preferred_nid, nodemask, &ac,
                           &alloc_mask, &alloc_flags))
    return NULL;


  /* 2. 快速路径分配内存 */
  page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
  if (likely(page))
    /* 如果快速路径分配成功，则直接返回 */
    goto out;


  /* 3. 慢速路径分配内存 */
  page = __alloc_pages_slowpath(alloc_mask, order, &ac);

 out:

  return page;
}

后续我们将主要关注快速路径的分配逻辑。

定位目标zone

想要完成内存分配操作，首先需要找到合适的 zone. 细心的读者可以已经发现，函数 __alloc_pages 中用于指定目标 node 的参数名叫 preferred_nid, 之所以叫 preferred 的原因是当前所选择的目标 node 可能无法满足程序的内存申请，此时系统可能会尝试着从其它 node 进行分配。在讨论 2.4 的数据结构时，我们提到过每个 node 中都保存着所有 node 的所有 zone，相关字段定义如下：

/* file: include/linux/mmzone.h */

typedef struct pglist_data {
  /*
   * node_zonelists contains references to all zones in all nodes.
   * Generally the first zones will be references to this node's
   * node_zones.
   */
  struct zonelist node_zonelists[MAX_ZONELISTS];
}

/*
 * One allocation request operates on a zonelist. A zonelist
 * is a list of zones, the first one is the 'goal' of the
 * allocation, the other zones are fallback zones, in decreasing
 * priority.
 *
 * To speed the reading of the zonelist, the zonerefs contain the zone index
 * of the entry being read. Helper functions to access information given
 * a struct zoneref are
 *
 * zonelist_zone()  - Return the struct zone * for an entry in _zonerefs
 * zonelist_zone_idx()  - Return the index of the zone for an entry
 * zonelist_node_idx()  - Return the index of the node for an entry
 */
  struct zonelist {
    struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
  };

/*
 * This struct contains information about a zone in a zonelist. It is stored
 * here to avoid dereferences into large structures and lookups of tables
 */
struct zoneref {
  struct zone *zone; /* Pointer to actual zone */
  int zone_idx; /* zone_idx(zoneref->zone) */
};

数组 node_zonelists 长度通过 MAX_ZONELISTS 确定：

/* file: include/linux/mmzone.h */

enum {
  ZONELIST_FALLBACK, /* zonelist with fallback */
#ifdef CONFIG_NUMA
  /*
   * The NUMA zonelists are doubled because we need zonelists that
   * restrict the allocations to a single node for __GFP_THISNODE.
   */
  ZONELIST_NOFALLBACK, /* zonelist without fallback (__GFP_THISNODE) */
#endif
  MAX_ZONELISTS
};

在NUMA架构下，该数组包含着两个列表，一个 fallback 列表一个 nofallback 列表，前者包含着系统中所有的 zone, 列表的排列顺序就是Buddy System 分配内存时选择 zone 的优先级顺序，后者仅包含当前 node 的 zone。fallback 的意思是当前 node 的 zone 无法满足要求时，是否需要使用其它 node 中的 zone 来顶替。 zonelist 就是一个 zone 的数组，Buddy System分配内存时就会遍历整个数组，从第一个合适的 zone 中分配内存，zonelist 的长度定义如下：

/* file: include/linux/mmzone.h */

/* zonelist 的最大长度，node 数量乘以每个 node 的分区数量，用于存放整个 fallback 列表 */
#define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES)

两个 zonelist 在系统的启动阶段进行初始化，NUMA 架构下 fallback 列表的构建逻辑是先将所有的 node 按照到当前 node 的“远近程度”排序，然后再将每个 node 的 zone 按照一定顺序排列起来。核心代码如下：

/* file: mm/page_alloc.c */

/*
 * Build zonelists ordered by zone and nodes within zones.
 * This results in conserving DMA zone[s] until all Normal memory is
 * exhausted, but results in overflowing to remote node while memory
 * may still exist in local DMA zone.
 */

static void build_zonelists(pg_data_t *pgdat)
{
    static int node_order[MAX_NUMNODES];
    int node, load, nr_nodes = 0;
    nodemask_t used_mask = NODE_MASK_NONE;
    int local_node, prev_node;

    /* NUMA-aware ordering of nodes */
    local_node = pgdat->node_id;
    load = nr_online_nodes;
    prev_node = local_node;

    memset(node_order, 0, sizeof(node_order));
    /* find_next_best_node 会寻找下一个距离 local_node 最近的 node */
    while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
        /*
         * We don't want to pressure a particular node.
         * So adding penalty to the first node in same
         * distance group to make it round-robin.
         */
        if (node_distance(local_node, node) !=
            node_distance(local_node, prev_node))
            node_load[node] = load;

        node_order[nr_nodes++] = node;
        prev_node = node;
        load--;
    }

    build_zonelists_in_node_order(pgdat, node_order, nr_nodes);
    build_thisnode_zonelists(pgdat);
}

函数 find_next_best_node 会寻找下一个距离 localnode 最近的 node, 这样通过 while 循环就可以将所有的 node 按照“距离（Distance）”排好序。“距离（Distance）”是NUMA架构下CPU访问其它节点的内存耗时的一个度量单位，两个CPU 节点距离越远，访问起来越耗时，因此构建 fallback 列表时，需要按照距离由近到远对所有的 node 进行排序。例如下图中，三个CPU 的 fallback 顺序依次是：

• Node 1: 1 -> 2 -> 3

• Node 2: 2 -> 1 -> 3

• Node 3: 3 -> 1 -> 2

对 node 排好序之后，通过函数 build_zonelists_in_node_order 来构建当前 node 的 fallback 列表：

/* file: mm/page_alloc.c */

static void build_zonelists_in_node_order(pg_data_t *pgdat, int *node_order,
                                          unsigned nr_nodes)
{
    struct zoneref *zonerefs;
    int i;

    /* 拿到当前 node 的 fallback 列表 */
    zonerefs = pgdat->node_zonelists[ZONELIST_FALLBACK]._zonerefs;

    for (i = 0; i < nr_nodes; i++) {
        int nr_zones;

        /* 获取到对应的 node */
        pg_data_t *node = NODE_DATA(node_order[i]);

        /* 将 node 中的各个分区按照由高到低的顺序放入 zonerefs 中，放入顺序为：Movable -> Normal -> DMA */
        nr_zones = build_zonerefs_node(node, zonerefs);
        zonerefs += nr_zones;
    }
    zonerefs->zone = NULL;
    zonerefs->zone_idx = 0;
}

分配内存时的遍历逻辑在函数 get_page_from_freelist 中（该函数也是快速路径分配的入口函数），通过宏 for_next_zone_zonelist_nodemask 来完成，找到合适的 zone 了之后，系统通过函数 rmqueue 来完成内存分配。

内存分配

快速路径（fastpath）下分配内存的核心逻辑在函数 rmqueue 中，函数的主体代码如下：

/* file: mm/page_alloc.c */

static inline struct page *rmqueue(struct zone *preferred_zone,
                                   struct zone *zone, unsigned int order,
                                   gfp_t gfp_flags, unsigned int alloc_flags,
                                   int migratetype)
{
  unsigned long flags;
  struct page *page;

  if (likely(order == 0)) {
    /* 对于 order=0 的情况，尝试从 per_cpu_pageset 中分配内存 */
    if (!IS_ENABLED(CONFIG_CMA) || alloc_flags & ALLOC_CMA ||
        migratetype != MIGRATE_MOVABLE) {
      page = rmqueue_pcplist(preferred_zone, zone, gfp_flags,
                             migratetype, alloc_flags);
      goto out;
    }
  }

  /* 访问 zone 时需要加锁 */
  spin_lock_irqsave(&zone->lock, flags);

  do {
    page = NULL;
    if (order > 0 && alloc_flags & ALLOC_HARDER) {
      /* 从 zone 的free area中分配内存，free area 就是Buddy System 中用来存放各种 order 的内存页面的地方 */
      page = __rmqueue_smallest(zone, order,
                                MIGRATE_HIGHATOMIC);
    }
    /* 如果还没有分配到内存，则尝试通过 fallback 列表分配内存 */
    if (!page)
      page = __rmqueue(zone, order, migratetype, alloc_flags);
  } while (page && check_new_pages(page, order));
  /* 释放锁 */
  spin_unlock(&zone->lock);
  if (!page)
    goto failed;
  local_irq_restore(flags);

 out:
  return page;

 failed:
  local_irq_restore(flags);
  return NULL;
}

总体来说，函数的逻辑根据 order 的大小分为两部分：

1. 当order = 0, 即申请的内存页数等于1时，系统会从每个CPU的缓存页面中分配内存

2. 当order > 0, 即申请的内存页数大于1时，系统会从 zone 中分配内存

之所以这样区别对待，是因为 zone 是共享的数据结构，在多核系统中会面临巨大的竞争，通过代码也可以发现，当通过 zone 分配内存时需要对 zone->lock 加锁。而根据实际经验，人们发现系统对于 order=0 的内存分配请求是出现频次最高的，为了提升性能，系统就为每个CPU 建立了一个“缓存池”，也就是前文讨论 zone 的数据结构时提到的字段 struct per_cpu_pageset __percpu *pageset;, 内核将其称为 pcplist, 即 per cpu pages list, 从 pcplist 分配内存的函数是 rmqueue_pcplist:

/* file: mm/page_alloc.c */

static struct page *rmqueue_pcplist(struct zone *preferred_zone,
                                    struct zone *zone, gfp_t gfp_flags,
                                    int migratetype, unsigned int alloc_flags)
{
  struct per_cpu_pages *pcp;
  struct list_head *list;
  struct page *page;
  unsigned long flags;

  local_irq_save(flags);
  /* 获取到当前CPU 的 pageset */
  pcp = &this_cpu_ptr(zone->pageset)->pcp;
  /* 拿到 pageset 中对应类型的内存列表 */
  list = &pcp->lists[migratetype];
  page = __rmqueue_pcplist(zone, migratetype, alloc_flags, pcp, list);
  if (page) {
    __count_zid_vm_events(PGALLOC, page_zonenum(page), 1);
    zone_statistics(preferred_zone, zone);
  }
  local_irq_restore(flags);
  return page;
}

static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
                                      unsigned int alloc_flags,
                                      struct per_cpu_pages *pcp,
                                      struct list_head *list)
{
  struct page *page;

  do {
    /* 如果目标列表为空，则通过 Buddy System 为该列表补充内存，然后再进行分配 */
    if (list_empty(list)) {
      pcp->count +=
        rmqueue_bulk(zone, 0, READ_ONCE(pcp->batch),
                     list, migratetype, alloc_flags);
      if (unlikely(list_empty(list)))
        return NULL;
    }

    /* 将对应内存列表的第一个内存页作为结果返回 */
    page = list_first_entry(list, struct page, lru);
    list_del(&page->lru);
    pcp->count--;
  } while (check_new_pcp(page));

  return page;
}

整个逻辑非常直观，就是找到当前CPU 的内存“缓存池”，然后从取出一页 migratetype 对应的内存即可。值得一提的是如果 migratetype 对应的内存列表为空，那么系统会通过 Buddy System 为该列表补充内存，该逻辑通过函数 rmqueue_bulk 完成，这里不再深入。

如果 order>0, 则通过函数 __rmqueue_smallest 从 zone 中分配内存，Buddy System 的算法实现也包含在该函数中：

/* file: mm/page_alloc.c */

static __always_inline struct page *
__rmqueue_smallest(struct zone *zone, unsigned int order, int migratetype)
{
  unsigned int current_order;
  struct free_area *area;
  struct page *page;

  /* Find a page of the appropriate size in the preferred list */
  for (current_order = order; current_order < MAX_ORDER;
       ++current_order) {
    area = &(zone->free_area[current_order]);
    /* include/linux/mmzone.h: 作用是从 area->free_list[migratetype] 列表中拿到第一个元素，也就是一个连续 2^order 个物理页面 */
    page = get_page_from_free_area(area, migratetype);
    /* 如果没有对应大小的free list, 则尝试下一个 order 的列表 */
    if (!page)
      continue;
    del_page_from_free_list(page, zone, current_order);
    /* 如果 order ！= current_order, 则需要按照Buddy Algorithm将更大的连续内存劈开成更小的Buddy并插入到对应的 free area 列表中，该逻辑在 expand 函数中完成 */
    expand(zone, page, order, current_order, migratetype);
    set_pcppage_migratetype(page, migratetype);
    return page;
  }

  return NULL;
}

函数通过 for 循环遍历 zone->free_area, 找到能够满足请求的最小的Buddy并从中分配内存，如果实际的Buddy 列表大小大于请求的 order, 则通过 expand 对其进行拆分并将未分配的内存存入对应 order 的Buddy列表中，整个算法思路与前文讨论的一样。