从零到负一

【LM10】伙伴系统基本信息

硬核技术 Linux内核 Linux_5_0 ARMv8_64 Linux内存管理
2023/05/10

终于到伙伴系统了，不容易啊。在之前的笔记中我已多次提到伙伴系统，从这篇笔记开始，我们来仔细看看伙伴系统是如何实现以及工作的吧。

什么是伙伴系统

我这里偷懒，就直接上维基百科的解释了，

The buddy memory allocation technique is a memory allocation algorithm that divides memory into partitions to try to satisfy a memory request as suitably as possible. This system makes use of splitting memory into halves to try to give a best fit. According to Donald Knuth, the buddy system was invented in 1963 by Harry Markowitz, and was first described by Kenneth C. Knowlton (published 1965). The Buddy memory allocation is relatively easy to implement. It supports limited but efficient splitting and coalescing of memory blocks.

简单来说，伙伴系统就是通过将大的内存分成一块一块的，并尽量用大小最合适的内存块来满足分配的需求。在Linux的内核中，伙伴系统将内存空间划分成一块一块的大小为2^n * page的内存块，其中n = [0, 10]。并且相同n的内存块通过链表连接起来。当需要进行内存分配时，Linux内核就会从这些链表中找到最合适内存块，并且将剩下的内存块拆分并插入到更小的n对应的链表中。比如我们需要分配20个页，那么Linux内核就会去n = 5的链表中找空闲的内存块。至于剩下的12个页（2 ^ 5 - 20），则会被拆分成更小的页并插入相应的链表中（当然，实际代码要复杂得多）。

相关结构体

在【LM09】Memblock到伙伴系统的切换中，我着重介绍了zonelist以及相关的结构体，这里我就不做过多分析了，我们来看看zone相关的几个结构体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// include/linux/mmzone.h

enum migratetype {
    MIGRATE_UNMOVABLE,                           // 不可移动页，内核中通过线性映射的区域都是不可移动的 
    MIGRATE_MOVABLE,                             // 可移动页
    MIGRATE_RECLAIMABLE,                         // 可回收页
    /* the number of types on the pcp lists */
    MIGRATE_PCPTYPES,    
    MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
    /*
     * MIGRATE_CMA migration type is designed to mimic the way
     * ZONE_MOVABLE works.  Only movable pages can be allocated
     * from MIGRATE_CMA pageblocks and page allocator never
     * implicitly change migration type of MIGRATE_CMA pageblock.
     *
     * The way to use it is to change migratetype of a range of
     * pageblocks to MIGRATE_CMA which can be done by
     * __free_pageblock_cma() function.  What is important though
     * is that a range of pageblocks must be aligned to
     * MAX_ORDER_NR_PAGES should biggest page be bigger then
     * a single pageblock.
     */
    MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    MIGRATE_ISOLATE,    /* can't allocate from here */
#endif
    MIGRATE_TYPES
};

struct free_area {
    struct list_head free_list[MIGRATE_TYPES];
	// 内存块的数量 
    unsigned long nr_free;
};

struct zone {
    /* Read-mostly fields */

    /* zone watermarks, access with *_wmark_pages(zone) macros */
    unsigned long _watermark[NR_WMARK];
    unsigned long watermark_boost;
    ...
    ... 
    /* free areas of different sizes */
    struct free_area free_area[MAX_ORDER];
    ... 
	... 
	// 伙伴系统管理的page数量
	atomic_long_t managed_pages;
	... 
	... 
    /* Zone statistics */
    atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS];
}

这里主要关注zone中的watermark以及free_area和migratetype。参考下图关于free_area的示意图（该图来自bin的技术小屋），

ALLOC_*掩码和watermarks

Linux在管理内存时，有个很重要的概念是水位线（watermarks）。watermarks决定了内存分配的流程以及处理方式，这里我简单介绍下watermarks，下面内容主要来自一步一图带你深入理解 Linux 物理内存管理中的5.2 物理内存区域中的水位线以及深入理解 Linux 物理内存分配全链路实现中的3.1 内存分配行为标识掩码 ALLOC_*。

1
2
3
4
5
6
7
8
9
10
11
12
13
// ./include/linux/mmzone.h

enum zone_watermarks {
    WMARK_MIN,
    WMARK_LOW,
    WMARK_HIGH,
    NR_WMARK
};

#define min_wmark_pages(z) (z->_watermark[WMARK_MIN] + z->watermark_boost)
#define low_wmark_pages(z) (z->_watermark[WMARK_LOW] + z->watermark_boost)
#define high_wmark_pages(z) (z->_watermark[WMARK_HIGH] + z->watermark_boost)
#define wmark_pages(z, i) (z->_watermark[i] + z->watermark_boost)

在zone结构体中，我们定义了_watermark这个数组以及watermark_boost，后者可以用于动态地调整watermarks。一般来说，

  1. 当zone中的剩余内存空间大于_watermark[WMARK_HIGH]时，内核可以随意地分配内存；
  2. 当zone中的剩余内存空间介于_watermark[WMARK_HIGH]和_watermark[WMARK_LOW]之间时，内核也可以正常地分配内存；
  3. 当zone中的剩余内存空间介于_watermark[WMARK_LOW]和_watermark[WMARK_MIN]之间时，内核分配面临一定的压力，但是还可以满足进程此时的内存分配要求，当给进程分配完内存之后，就会唤醒kswapd进程开始内存回收，直到剩余内存高于_watermark[WMARK_HIGH]为止；
  4. 当zone中的剩余内存空间小于_watermark[WMARK_MIN]，说明此时的内存容量已经非常危险了，如果进程在这时请求内存分配，内核就会进行直接内存回收。

关于watermarks我就点到为止，不再进行更深一步的研究了，下面来看看ALLOC_*掩码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// ./mm/internal.h

/* The ALLOC_WMARK bits are used as an index to zone->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 */

/* Mask to get the watermark bits */
#define ALLOC_WMARK_MASK     (ALLOC_NO_WATERMARKS-1)

/*
 * Only MMU archs have async oom victim reclaim - aka oom_reaper so we
 * cannot assume a reduced access to memory reserves is sufficient for
 * !MMU
 */
#ifdef CONFIG_MMU
#define ALLOC_OOM            0x08
#else
#define ALLOC_OOM            ALLOC_NO_WATERMARKS
#endif

#define ALLOC_HARDER         0x10 /* try to alloc harder */
#define ALLOC_HIGH           0x20 /* __GFP_HIGH set */
#define ALLOC_CPUSET         0x40 /* check for correct cpuset */
#define ALLOC_CMA            0x80 /* allow allocations from CMA areas */
#ifdef CONFIG_ZONE_DMA32
#define ALLOC_NOFRAGMENT     0x100 /* avoid mixing pageblock types */
#else
#define ALLOC_NOFRAGMENT     0x0
#endif
#define ALLOC_KSWAPD         0x200 /* allow waking of kswapd */

之前说了这么多watermarks，现在终于联系在一起了。ALLOC_*掩码中有watermarks以及其它几个内存分配相关的掩码。在伙伴系统进行内存分配时，这些掩码都会影响其行为。

GFP掩码

除了ALLOC_*掩码，在内存分配的过程中，还有个重要的参数就是GFP掩码，这个掩码同样决定了内存分配的行为。虽然这个掩码不在zone的结构体中，我也将其放在这里进行简单地分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// ./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_WRITE       0x100u
#define ___GFP_NOWARN      0x200u
...
...
// 第二层的标志位
#define __GFP_DMA          ((__force gfp_t)___GFP_DMA)
#define __GFP_HIGHMEM      ((__force gfp_t)___GFP_HIGHMEM)
#define __GFP_DMA32        ((__force gfp_t)___GFP_DMA32)
#define __GFP_MOVABLE      ((__force gfp_t)___GFP_MOVABLE)  /* ZONE_MOVABLE allowed */
...
...
// __GFP_XX的组合
#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)
#define GFP_NOIO           (__GFP_RECLAIM)
#define GFP_NOFS           (__GFP_RECLAIM | __GFP_IO)
#define GFP_USER           (__GFP_RECLAIM | __GFP_IO | __GFP_FS | __GFP_HARDWALL)
#define GFP_DMA            __GFP_DMA
#define GFP_DMA32          __GFP_DMA32
...
...

在上面的代码中，有几个掩码是我们需要重点关注的，它们是__GFP_DMA, __GFP_HIGHMEM和__GFP_DMA32。这几个掩码和zonelist一起决定了zone在内存分配时的优先级。单看这几个掩码，比如设置了__GFP_DMA32，那么内核在分配内存时，会按照ZONE_DMA32 -> ZONE_DMA的顺序分配内存。如果设置了__GFP_HIGHMEM，那么就会按照ZONE_HIGHMEM -> ZONE_NORMAL -> ZONE_DMA32 -> ZONE_DMA的顺序分配内存。如果什么都不设置，那么就默认从ZONE_NORMAL开始进行内存的分配。
除了这几个掩码，Linux内核还定义了大量的其它掩码，我这里直接引用深入理解 Linux 物理内存分配全链路实现总结的掩码（要记住是不可能的，使用的时候再回来看看其说明），

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// ___GFP_RECLAIMABLE    - 用于指定分配的页面是可以回收的；
// ___GFP_MOVABLE        - 用于指定分配的页面是可以移动的，上面两个标志会影响底层的伙伴系统从哪个区域中去获取空闲内存页；
// ___GFP_HIGH           - 表示该内存分配请求是高优先级的，内核急切的需要内存，如果内存分配失败则会给系统带来非常严重的后果，设置该标志通常内存是不允许分配失败
//                           的，如果空闲内存不足，则会从紧急预留内存中分配；
// ___GFP_IO             - 表示内核在分配物理内存的时候可以发起磁盘IO操作。什么意思呢？比如当内核在进行内存分配的时候，发现物理内存不足，这时需要将不经常使用的
//                         内存页置换到SWAP分区或者SWAP文件中，这时就涉及到了IO操作，如果设置了该标志，表示允许内核将不常用的内存页置换出去；
// ___GFP_FS             - 允许内核执行底层文件系统操作，在与VFS虚拟文件系统层相关联的内核子系统中必须禁用该标志，否则可能会引起文件系统操作的循环递归调用，因
//                         为在设置___GFP_FS标志分配内存的情况下，可能会引起更多的文件系统操作，而这些文件系统的操作可能又会进一步产生内存分配行为，这样一直递
//                         归持续下去；
// ___GFP_ZERO           - 在内核分配内存成功之后，将内存页初始化填充字节0；
// ___GFP_ATOMIC         - 该标志的设置表示内存在分配物理内存的时候不允许睡眠必须是原子性地进行内存分配。比如在中断处理程序中，就不能睡眠，因为中断程序不能被重
//                         新调度。同时也不能在持有自旋锁的进程上下文中睡眠，因为可能导致死锁。综上所述这个标志只能用在不能被重新安全调度的进程上下文中；
// ___GFP_DIRECT_RECLAIM - 表示内核在进行内存分配的时候，可以进行直接内存回收。当剩余内存容量低于水位线_watermark[WMARK_MIN]时，说明此时的内存容量已经非
//                         常危险了，如果进程在这时请求内存分配，内核就会进行直接内存回收，直到内存水位线恢复到_watermark[WMARK_HIGH]之上；
// ___GFP_KSWAPD_RECLAIM - 表示内核在分配内存的时候，如果剩余内存容量在_watermark[WMARK_MIN]与_watermark[WMARK_LOW]之间时，内核就会唤醒kswapd进程开始异步内存回收，
//                         直到剩余内存高于_watermark[WMARK_HIGH]为止；
// ___GFP_NOWARN         - 表示当内核分配内存失败时，抑制内核的分配失败错误报告；
// ___GFP_RETRY_MAYFAIL  - 在内核分配内存失败的时候，允许重试，但重试仍然可能失败，重试若干次后停止。与其对应的是___GFP_NORETRY标志表示分配内存失败时不允许重试；
// ___GFP_NOFAIL         - 在内核分配失败时一直重试直到成功为止；
// ___GFP_HARDWALL       - 该标志限制了内核分配内存的行为只能在当前进程分配到的CPU所关联的NUMA节点上进行分配，当进程可以运行的CPU受限时，该标志才会有意义，如果进程允
//                         许在所有CPU上运行则该标志没有意义；
// ___GFP_THISNODE       - 该标志限制了内核分配内存的行为只能在当前NUMA节点或者在指定NUMA节点中分配内存，如果内存分配失败不允许从其他备用NUMA节点中分配内存；
// ___GFP_MEMALLOC       - 允许内核在分配内存时可以从所有内存区域中获取内存，包括从紧急预留内存中获取。但使用该标示时需要保证进程在获得内存之后会很快的释放掉内存不会过
//                         长时间的占用，尤其要警惕避免过多的消耗紧急预留内存区域中的内存；
// ___GFP_NOMEMALLOC     - 标志用于明确禁止内核从紧急预留内存中获取内存。___GFP_NOMEMALLOC标识的优先级要高于___GFP_MEMALLOC；

fallback

在free_area的结构体中，我们有多条free_list，并且它们相对都是独立的。因此，在进行内存分配时，如果某一个free_list中没有足够多的内存空间，内核就会按照一定的顺序，去其它free_list中寻找内存空间。这个行为就叫做 - fallback，而这个顺序就定义在fallbacks这个数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// ./mm/page_alloc.c

/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
 */
static int fallbacks[MIGRATE_TYPES][4] = {
	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
#ifdef CONFIG_CMA
	[MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	[MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
#endif
};

关于fallback的基本原理，我会在后面内存分配的函数中再做具体的解释说明。接下来，我们就开始正式进入伙伴系统的分配函数了。

alloc_pages()

在伙伴系统中，alloc_pages()这个函数（宏）是一个很高层的封装函数，我们就从这里开始，看看它是如何一步一步地调用底层函数的。

1
2
3
4
5
6
7
8
9
10
11
12
13
alloc_pages()
|
+--> alloc_pages_node()
    |
    +--> __alloc_pages_node()
         |
         +--> __alloc_pages()
              |
              +--> __alloc_pages_nodemask()
                   |
                   +--> get_page_from_freelist()
                   or
                   +--> __alloc_pages_slowpath()

从上面这段代码可以看出，alloc_pages()基本上就是一路地调用下层函数，直到get_page_from_freelist()或者__alloc_pages_slowpath()函数。后者主要用于内存空间比较紧张的情况，在这种情况下，内存地分配过程会很复杂。前者用于内存空间比较宽裕的情况，这种情况下内存的分配就比较直接简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// ./include/linux/gfp.h 

#define alloc_pages(gfp_mask, order) \
    // numa_node_id()会根据当前CPU的信息确定其nid
    alloc_pages_node(numa_node_id(), gfp_mask, order)

/*
 * Allocate pages, preferring the node given as nid. When nid == NUMA_NO_NODE,
 * prefer the current CPU's closest node. Otherwise node must be valid and
 * online.
 */
static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask, unsigned int order)
{
    // 如果nid == NUMA_NO_NODE，选择离当前CPU最近的node
    if (nid == NUMA_NO_NODE)
        nid = numa_mem_id();

    return __alloc_pages_node(nid, gfp_mask, order);
}

/*
 * Allocate pages, preferring the node given as nid. The node must be valid and
 * online. For more general interface, see alloc_pages_node().
 */
static inline struct page *__alloc_pages_node(int nid, gfp_t gfp_mask, unsigned int order)
{
    // 对nid, gfp_mask进行简单的检查
    VM_BUG_ON(nid < 0 || nid >= MAX_NUMNODES);
    VM_WARN_ON((gfp_mask & __GFP_THISNODE) && !node_online(nid));

    return __alloc_pages(gfp_mask, order, nid);
}

static inline struct page *__alloc_pages(gfp_t gfp_mask, unsigned int order, int preferred_nid)
{
    // 这里的nodemask(最后一个参数) = NULL，因此在对zonelist进行遍历时，没有额外的node的限制
    return __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL);
}

__alloc_pages_nodemask()

这个函数是伙伴系统的核心函数，它的逻辑很简单，

  1. 先将watermarks设置成ALLOC_WMARK_LOW，然后调用get_page_from_freelist()进行正常的内存分配；
  2. 如果步骤1成功，则返回获取的内存空间；
  3. 如果步骤1失败，那么就继续尝试__alloc_pages_slowpath()并返回获取的内存空间。

下面直接看代码吧，注释已经很详细了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// ./mm/page_alloc.c

/*
 * This is the 'heart' of the zoned buddy allocator.
 */
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 = { };

    /*
     * There are several places where we assume that the order value is sane
     * so bail out early if the request is out of bound.
     */
    if (unlikely(order >= MAX_ORDER)) {
        WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
        return NULL;
    }

    // gfp_mask需要在gfp_allowed_mask的范围内 - 后者默认为(__GFP_BITS_MASK & ~(__GFP_RECLAIM|__GFP_IO|__GFP_FS))
    gfp_mask &= gfp_allowed_mask;
    alloc_mask = gfp_mask;
    // ------------------------------------------------------------------------------------------------ (1)
    // 参考下面prepare_alloc_pages()函数的分析
    if (!prepare_alloc_pages(gfp_mask, order, preferred_nid, nodemask, &ac, &alloc_mask, &alloc_flags))
        return NULL;
    // ------------------------------------------------------------------------------------------------ (2)
    // 获取ac->zonelist中优先级小于等于ac->high_zoneidx、且在指定Node（也可以不指定）中最高优先级的zoneref
    finalise_ac(gfp_mask, &ac);

    /*
     * Forbid the first pass from falling back to types that fragment
     * memory until all local zones are considered.
     */
    // 避免内存碎片化的相关分配标识设置，可暂时忽略
    alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp_mask);

    /* First allocation attempt */
    // ------------------------------------------------------------------------------------------------ (3)
    // 第一次尝试进行内存分配，此时的watermarks为ALLOC_WMARK_LOW
    page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
    if (likely(page))
        goto out;
    
    // 如果执行到这里就说明上面的内存分配失败了，我们需要通过__alloc_pages_slowpath()再次尝试内存的分配
    /*
     * Apply scoped allocation constraints. This is mainly about GFP_NOFS
     * resp. GFP_NOIO which has to be inherited for all allocation requests
     * from a particular context which has been marked by
     * memalloc_no{fs,io}_{save,restore}.
     */
    // 清除GFP掩码中的(__GFP_IO | __GFP_FS)
    alloc_mask = current_gfp_context(gfp_mask);
    ac.spread_dirty_pages = false;

    /*
     * Restore the original nodemask if it was potentially replaced with
     * &cpuset_current_mems_allowed to optimize the fast-path attempt.
     */
    if (unlikely(ac.nodemask != nodemask))
        ac.nodemask = nodemask;
    
    // 再次尝试分配内存，既然第一次分配失败了，说明内存空间可能出现不足的情况。因此在这里
    // 会做更多的工作比如回收内存等，之后再进行内存的分配
    page = __alloc_pages_slowpath(alloc_mask, order, &ac);

    // 到这里说明内存分配已经成功，做一点收尾工作就可以返回了
out:
    if (memcg_kmem_enabled() && (gfp_mask & __GFP_ACCOUNT) && page &&
        unlikely(memcg_kmem_charge(page, gfp_mask, order) != 0)) {
        __free_pages(page, order);
        page = NULL;
    }

    trace_mm_page_alloc(page, order, alloc_mask, ac.migratetype);

    return page;
}

至此，伙伴系统的基础以及内存分配的基本流程已经介绍完了，在之后的几篇笔记中，我会详细地记录内存的分配和回收。

参考资料

  1. 一步一图带你深入理解 Linux 物理内存管理
  2. 深入理解 Linux 物理内存分配全链路实现
  3. 深度剖析 Linux 伙伴系统的设计与实现
CATALOG
  1. 1. 什么是伙伴系统
  2. 2. 相关结构体
    1. 2.1. ALLOC_*掩码和watermarks
    2. 2.2. GFP掩码
    3. 2.3. fallback
  3. 3. alloc_pages()
    1. 3.1. __alloc_pages_nodemask()
  4. 4. 参考资料
Total : 19
2024
2023
2022
美股 投资理财 Linux内核 Linux_5_0 ARMv8_64 Linux内存管理
股海浮沉 硬核技术 个人随笔