3.2.4 Buddy System(伙伴系统)

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

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

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

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

/* 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)

/* 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);
}

/* 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);
}

/* 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;
}

/* 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) */
};

/* 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
};

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

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

/* 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);
}

/* 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;
}

/* 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;
}

/* 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;
}

/* 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;
}