关于linux:深度剖析-Linux-伙伴系统的设计与实现

61次阅读

共计 48883 个字符,预计需要花费 123 分钟才能阅读完成。

在上篇文章《深刻了解 Linux 物理内存调配全链路实现》中,笔者为大家具体介绍了 Linux 内存调配在内核中的整个链路实现:

然而当内核执行到 get_page_from_freelist 函数,筹备进入搭档零碎执行具体内存调配动作的相干逻辑,笔者思考到文章篇幅的起因,并没有过多的着墨,算是留下了一个小尾巴。

那么本文笔者就为大家残缺地介绍一下搭档零碎这部分的内容,咱们将基于内核 5.4 版本的源码来具体的讨论一下搭档零碎在内核中的设计与实现。

1. 搭档零碎的外围数据结构

如上图所示,内核会为 NUMA 节点中的每个物理内存区域 zone 调配一个搭档零碎用于治理该物理内存区域 zone 里的闲暇内存页。

而搭档零碎的外围数据结构就封装在 struct zone 里,对于 struct zone 构造体的具体介绍感兴趣的敌人能够回看下笔者之前的文章《深刻了解 Linux 物理内存治理》中第五大节“5. 内核如何治理 NUMA 节点中的物理内存区域”的内容。

在本大节中,咱们聚焦于搭档零碎相干的数据结构介绍~~

struct zone {
    // 被搭档零碎所治理的物理内存页个数
    atomic_long_t       managed_pages;
    // 搭档零碎的外围数据结构
    struct free_area    free_area[MAX_ORDER];
}

struct zone 构造中的 managed_pages 用于示意该内存区域内被搭档零碎所治理的物理内存页数量。

而 managed_pages 的计算形式之前也介绍过了,它是通过 present_pages(不蕴含内存空洞)减去内核为应答紧急情况而预留的物理内存页 reserved_pages 失去的。

从这里能够看出搭档零碎所治理的闲暇物理内存页并不蕴含紧急预留内存

搭档零碎的真正外围数据结构就是这个 struct free_area 类型的数组 free_area[MAX_ORDER]。MAX_ORDER 就是笔者在《深刻了解 Linux 物理内存调配全链路实现》“的第一大节 “1. 内核物理内存调配接口”中介绍的调配阶 order 的最大值减 1。

搭档零碎所调配的物理内存页全部都是物理上间断的,并且只能调配 2 的整数幂个页,这里的整数幂在内核中称之为调配阶 order。

在咱们调用物理内存调配接口时,均须要指定这个调配阶 order,意思是从搭档零碎申请多少个物理内存页,假如咱们指定调配阶为 order,那么就会从搭档零碎中申请 2 的 order 次幂个物理内存页。

搭档零碎会将物理内存区域中的闲暇内存依据调配阶 order 划分出不同尺寸的内存块,并将这些不同尺寸的内存块别离用一个双向链表组织起来。

比方:调配阶 order 为 0 时,对应的内存块就是一个 page。调配阶 order 为 1 时,对应的内存块就是 2 个 pages。顺次类推,当调配阶 order 为 n 时,对应的内存块就是 2 的 order 次幂个 pages。

MAX_ORDER – 1 就是内核中规定的调配阶 order 的最大值,定义在 /include/linux/mmzone.h 文件中,最大调配阶 MAX_ORDER – 1 = 10,也就是说一次,最多只能从搭档零碎中申请 1024 个内存页,对应 4M 大小的间断物理内存。

/* Free memory management - zoned buddy allocator.  */
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11

数组 free_area[MAX_ORDER] 中的索引示意的就是调配阶 order,用于指定对应双向链表组织治理的内存块蕴含多少个 page。

咱们能够通过 cat /proc/buddyinfo 命令来查看 NUMA 节点中不同内存区域 zone 的搭档零碎以后状态:

上图展现了不同内存区域搭档零碎的 free_area[MAX_ORDER] 数组中,不同调配阶对应的内存块个数,从左到右顺次是 0 阶,1 阶,……..,10 阶对应的双向链表中蕴含的内存块个数。

以上内容展现的只是搭档零碎的一个根本骨架,有了这个根本骨架之后,上面笔者持续依照一步一图的形式,来为大家揭开搭档零碎的残缺样貌。

咱们先从 free_area[MAX_ORDER] 数组的类型 struct free_area 构造开始谈起~~~

struct free_area {struct list_head    free_list[MIGRATE_TYPES];
    unsigned long        nr_free;
};
struct list_head {
    // 双向链表
    struct list_head *next, *prev;
};

依据前边的内容咱们晓得 free_area[MAX_ORDER] 数组形容的只是搭档零碎的一个根本骨架,数组中的每一个元素对立组织存储了雷同尺寸的内存块。内存块的尺寸分为 0 阶,1 阶,……..,10 阶,一共 MAX_ORDER 个尺寸。

struct free_area 次要形容的就是雷同尺寸的内存块在搭档零碎中的组织构造,nr_free 则示意的是该尺寸的内存块在以后搭档零碎中的个数,这个值会随着内存的调配而缩小,随着内存的回收而减少。

留神:nr_free 示意的可不是闲暇内存页 page 的个数,而是 闲暇内存块 的个数,对于 0 阶的内存块来说 nr_free 的确示意的是单个内存页 page 的个数,因为 0 阶内存块是由一个 page 组成的,然而对于 1 阶内存块来说,nr_free 则示意的是 2 个 page 汇合的个数,以此类推对于 n 阶内存块来说,nr_free 示意的是 2 的 n 次方 page 汇合的个数

这些雷同尺寸的内存块在 struct free_area 构造中是通过 struct list_head 构造类型的双向链表对立组织起来的。

按理来说,内核只须要将这些雷同尺寸的内存块在 struct free_area 中用一个双向链表串联起来就行了。

然而咱们从源码中却看到内核是用多个双向链表来组织这些雷同尺寸的内存块的,这些双向链表组成一个数组 free_list[MIGRATE_TYPES],该数组中双向链表的个数为 MIGRATE_TYPES。

咱们从 MIGRATE_TYPES 的字面意思上能够看出,内核会依据物理内存页的迁徙类型将这些雷同尺寸的内存块近一步通过不同的双向链表从新组织起来。

free_area 是将雷同尺寸的内存块组织起来,free_list 是在 free_area 的根底上近一步依据页面的迁徙类型将这些雷同尺寸的内存块划分到不同的双向链表中治理

而物理内存页面的迁徙类型 MIGRATE_TYPES 定义在 /include/linux/mmzone.h 文件中:

enum migratetype {
    MIGRATE_UNMOVABLE, // 不可挪动
    MIGRATE_MOVABLE,   // 可挪动
    MIGRATE_RECLAIMABLE, // 可回收
    MIGRATE_PCPTYPES,    // 属于 CPU 高速缓存中的类型,PCP 是 per_cpu_pageset 的缩写
    MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, // 紧急内存
#ifdef CONFIG_CMA
    MIGRATE_CMA, // 预留的间断内存 CMA
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    MIGRATE_ISOLATE,    /* can't allocate from here */
#endif
    MIGRATE_TYPES // 不代表任何区域,只是单纯示意一共有多少个迁徙类型
};

MIGRATE_UNMOVABLE 示意不可挪动的页面类型,这种类型的物理内存页面是固定的不能随便挪动,内核所须要的外围内存大多数是从 MIGRATE_UNMOVABLE 类型的页面中进行调配,这部分内存个别位于内核虚拟地址空间中的间接映射区。

在内核虚拟地址空间的间接映射区中,虚拟内存地址与物理内存地址都是间接映射的,虚拟内存地址通过减去一个固定的偏移量就能够间接失去物理内存地址,因为这种间接映射的关系,所以这部分内存是不能挪动的,因为一旦挪动虚拟内存地址就会发生变化,这样一来虚拟内存地址减去固定的偏移失去的物理内存地址就不一样了。

MIGRATE_MOVABLE 示意能够挪动的内存页类型,这种页面类型个别用于在过程用户空间中调配,因为在用户空间中虚拟内存与物理内存都是通过页表来动静映射的,物理页挪动之后,只须要扭转页表中的映射关系即可,而虚拟内存地址并不需要扭转。所有对过程来说都是通明的。

MIGRATE_RECLAIMABLE 示意不能挪动,然而能够间接回收的页面类型,比方后面提到的文件缓存页,它们就能够间接被回收掉,当再次须要的时候能够从磁盘中持续读取生成。或者一些生命周期比拟短的内存页,比方 DMA 缓存区中的内存页也是能够被间接回收掉。

MIGRATE_PCPTYPES 则示意 CPU 高速缓存中的页面类型,PCP 是 per_cpu_pageset 的缩写,每个 CPU 对应一个 per_cpu_pageset 构造,外面蕴含了高速缓存中的冷页和热页。这部分的具体内容感兴趣的能够回看下笔者的这篇文章《深刻了解 Linux 物理内存治理》中的“5.7 物理内存区域中的冷热页”大节。

MIGRATE_CMA 示意属于 CMA 区域中的内存页类型,CMA 的全称是 contiguous memory allocator,顾名思义它是一个调配间断物理内存页面的分配器用于调配间断的物理内存。

大家可能好奇了,咱们这节讲到的搭档零碎调配的不也是间断的物理内存吗?为什么又会多出个 CMA 呢?

起因还是前边咱们屡次提到的内存碎片对内存调配的微小影响,随着零碎的长时间运行,不可避免的会产生内存碎片,这些内存碎片会导致在内存短缺的状况下却仍然找不到一片足够大的间断物理内存,搭档零碎在这种状况下就会失败,而间断的物理内存调配对于内核来说又是刚需,比方:一些 DMA 设施只能拜访间断的物理内存,内核对于大页的反对也须要间断的物理内存。

所以为了解决这个问题,内核会在零碎刚刚启动的时候,这时内存还很短缺,先预留一部分间断的物理内存,这部分物理内存就是 CMA 区域,这部分内存能够被过程失常的应用,当有间断内存调配需要时,内核会通过页面回收或者迁徙的形式将这部分内存腾出来给 CMA 调配。

CMA 的初始化是在搭档零碎初始化之前就曾经实现的

MIGRATE_ISOLATE 则是一个虚构区域,用于逾越 NUMA 节点挪动物理内存页,内核能够将物理内存页挪动到应用该页最频繁的 CPU 所在的 NUMA 节点中。

在介绍完这些物理页面的迁徙类型 MIGRATE_TYPES 之后,大家可能不禁有疑难,内核为啥会设定这么多的页面迁徙类型呢?

答案还是为了解决后面咱们重复提到的内存碎片问题,当零碎长时间运行之后,随着不同尺寸内存的调配和开释,就会引起内存碎片,这些碎片会导致内核在明明还有足够内存的前提下,依然无奈找到一块足够大的间断内存调配。如下图所示:

上图中显示的这 7 个闲暇的内存页以碎片的模式存在于内存中,这就导致明明还有 7 个闲暇的内存页,然而最大的间断内存区域只有 1 个内存页,当内核想要申请 2 个间断的内存页时就会导致失败。

很长时间以来,物理内存碎片始终是 Linux 操作系统的弱点,所以内核在 2.6.24 版本中引入了以下形式来防止内存碎片。

如果这些内存页是能够迁徙的,内核就会将闲暇的内存页迁徙至一起,已调配的内存页迁徙至一起,造成了一整块足够大的间断内存区域。

如果这些内存页是能够回收的,内核也能够通过回收页面的形式,整顿出一块足够大的闲暇间断内存区域。

在咱们分明了以上介绍的基础知识之后,再回过头来看搭档零碎的这些外围数据结构,是不是就变得容易了解了~~

struct zone {
    // 被搭档零碎所治理的物理页数
    atomic_long_t       managed_pages;
    // 搭档零碎的外围数据结构
    struct free_area    free_area[MAX_ORDER];
}

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

首先搭档零碎会将物理内存区域 zone 中的闲暇内存页依照调配阶 order 将雷同尺寸的内存块组织在 free_area[MAX_ORDER] 数组中:

随后在 struct free_area 构造中搭档零碎近一步依据这些雷同尺寸内存块的页面迁徙类型 MIGRATE_TYPES,将雷同迁徙类型的物理页面组织在 free_list[MIGRATE_TYPES] 数组中,最终造成了残缺的搭档系统结构:

咱们能够通过 cat /proc/pagetypeinfo 命令能够查看以后各个内存区域中的搭档零碎中不同页面迁徙类型以及不同 order 尺寸的内存块个数。

page block order 示意零碎中反对的巨型页对应的调配阶,pages per block 示意巨型页中蕴含的 pages 个数。

好了,当初咱们曾经分明了搭档零碎的数据结构全貌,接下来笔者会在这个根底上持续为大家介绍搭档零碎的外围工作原理~~

2. 到底什么是搭档

咱们后面始终在谈搭档零碎,那么搭档这个概念到底在内核中是什么意思呢?其实上面这张搭档零碎的结构图曾经把搭档的概念很清晰的表达出来了。

搭档在咱们日常生活中含意就是如影随行的好敌人,在内核中也是如此,内核中的搭档指的是大小雷同并且在物理内存上是间断的两个或者多个 page

比方在上图中,free_area[1] 中组织的是调配阶 order = 1 的内存块,内存块中蕴含了两个间断的闲暇 page。这两个闲暇 page 就是搭档。

free_area[10] 中组织的是调配阶 order = 10 的内存块,内存块中蕴含了 1024 个间断的闲暇 page。这 1024 个闲暇 page 就是搭档。

再比方上图中的 page0 和 page 1 是搭档,page2 到 page 5 是搭档,page6 和 page7 又是搭档。然而 page0 和 page2 就不能成为搭档,因为它们的物理内存是不间断的。同时 (page0 到 page3) 和 (page4 到 page7) 所组成的两个内存块又能形成一个搭档。搭档必须是大小雷同并且在物理内存上是间断的两个或者多个 page

3. 搭档零碎的内存调配原理

在《深刻了解 Linux 物理内存调配全链路实现》一文中的第二大节 ” 2. 物理内存调配内核源码实现 “,笔者介绍了如下四个内存调配的接口,内核能够通过这些接口向搭档零碎申请内存:

struct page *alloc_pages(gfp_t gfp, unsigned int order)
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
unsigned long get_zeroed_page(gfp_t gfp_mask)
unsigned long __get_dma_pages(gfp_t gfp_mask, unsigned int order)

首先咱们能够依据内存调配接口函数中的 gfp_t gfp_mask,找到内存调配指定的 NUMA 节点和物理内存区域 zone,而后找到物理内存区域 zone 对应的搭档零碎。

随后内核通过接口中指定的调配阶 order,能够定位到搭档零碎的 free_area[order] 数组,其中寄存的就是调配阶为 order 的全副内存块。

最初内核进一步通过 gfp_t gfp_mask 掩码中指定的页面迁徙类型 MIGRATE_TYPE,定位到 free_list[MIGRATE_TYPE],这里寄存的就是合乎内存调配要求的所有内存块。通过遍历这个双向链表就能够轻松取得要调配的内存。

比方咱们向内核申请 (2 ^ (order – 1),2 ^ order ] 之间大小的内存,并且这块内存咱们指定的迁徙类型为 MIGRATE_MOVABLE 时,内核会依照 2 ^ order 个内存页进行申请。

随后内核会依据 order 找到搭档零碎中的 free_area[order] 对应的 free_area 构造,并进一步依据页面迁徙类型定位到对应的 free_list[MIGRATE_MOVABLE],如果该迁徙类型的 free_list 中没有闲暇的内存块时,内核会进一步到上一级链表也就是 free_area[order + 1] 中寻找。

如果 free_area[order + 1] 中对应的 free_list[MIGRATE_MOVABLE] 链表中还是没有,则持续循环到更高一级 free_area[order + 2] 寻找,直到在 free_area[order + n] 中的 free_list[MIGRATE_MOVABLE] 链表中找到闲暇的内存块。

然而此时咱们在 free_area[order + n] 链表中找到的闲暇内存块的尺寸是 2 ^ (order + n) 大小,而咱们须要的是 2 ^ order 尺寸的内存块,于是内核会将这 2 ^ (order + n) 大小的内存块逐级减半决裂,将每一次决裂后的内存块插入到相应的 free_area 数组里对应的 free_list[MIGRATE_MOVABLE] 链表中,并将最初决裂出的 2 ^ order 尺寸的内存块调配给过程应用。

上面笔者举一个具体的例子来为大家阐明搭档零碎的整个内存调配过程:

为了清晰地给大家展示搭档零碎的内存调配过程,咱们临时疏忽 MIGRATE_TYPES 相干的组织构造

咱们假如以后搭档零碎中只有 order = 3 的闲暇链表 free_area[3],其余剩下的调配阶 order 对应的闲暇链表中均是空的。free_area[3] 中仅有一个闲暇的内存块,其中蕴含了间断的 8 个 page。

当初咱们向搭档零碎申请一个 page 大小的内存(对应的调配阶 order = 0),那么内核会在搭档零碎中首先查看 order = 0 对应的闲暇链表 free_area[0] 中是否有闲暇内存块可供调配。

随后内核会依据前边介绍的内存调配逻辑,持续降级到 free_area[1] , free_area[2] 链表中寻找闲暇内存块,直到查找到 free_area[3] 发现有一个可供调配的内存块。这个内存块中蕴含了 8 个 间断的闲暇 page,然而咱们只有一个 page 就够了,那该怎么办呢?

于是内核先将 free_area[3] 中的这个闲暇内存块从链表中摘下,而后减半决裂成两个内存块,决裂进去的这两个内存块别离蕴含 4 个 page(调配阶 order = 2)。

上图决裂出的两个内存块,黄色的代表原有内存块的前半部分,绿色代表原有内存块的后半局部。

随后内核会将决裂出的后半局部(图中绿色局部,order = 2),插入到 free_rea[2] 链表中。

前半部分(图中黄色局部,order = 2)持续减半决裂,决裂进去的这两个内存块别离蕴含 2 个 page(调配阶 order = 1)。如下图中第 4 步所示,前半部分为黄色,后半部分为紫色。同理依照前边的决裂逻辑,内核会将后半局部内存块(紫色局部,调配阶 order = 1)插入到 free_area[1] 链表中。

前半部分(图中黄色局部,order = 1)在上图中的第 6 步持续减半决裂,决裂进去的这两个内存块别离蕴含 1 个 page(调配阶 order = 0),前半部分为青色,后半部分为黄色。

后半局部插入到 frea_area[0] 链表中,前半部分返回给过程,这时内存调配胜利,流程完结。

以上流程就是搭档零碎的 外围 内存调配过程,上面咱们再把内存页面的迁徙属性 MIGRATE_TYPES 思考进来,来看一下残缺的搭档零碎内存调配流程:

当初咱们加上了内存 MIGRATE_TYPES 的组织构造,其实调配流程还是和外围流程一样的,只不过下面提到的那些高阶 order 的减半决裂情景都产生在各个 free_area[order] 中固定的 free_list[MIGRATE_TYPE] 里罢了。

比方咱们要求调配的内存迁徙属性要求是 MIGRATE_MOVABLE 类型,那么减半决裂流程别离产生在 free_area[2],free_area[1],free_area[0] 对应的 free_list[MIGRATE_MOVABLE] 中,多了一个 free_list 的维度,仅此而已。

不过笔者这里想重点着墨的中央是内存调配的一种异样情景,比方咱们想要调配特定迁徙类型的内存,然而以后搭档零碎所有 free_area[order] 里对应的 free_list[MIGRATE_TYPE] 均无奈满足内存调配的需要(没有足够特定迁徙类型的闲暇内存块)。那么这种场景下内核会怎么解决呢?

其实同样的问题咱们在《深刻了解 Linux 物理内存治理》一文中也遇到过,过后笔者介绍内存 NUMA 架构的时候提到,如果以后 NUMA 节点无奈满足内存调配时,内核会逾越 NUMA 节点从其余节点上分配内存。

typedef struct pglist_data {
    // NUMA 节点中的物理内存区域个数
    int nr_zones; 
    // NUMA 节点中的物理内存区域
    struct zone node_zones[MAX_NR_ZONES];
    // NUMA 节点的备用列表
    struct zonelist node_zonelists[MAX_ZONELISTS];
} pg_data_t;

每个 NUMA 节点的 struct pglist_data 构造中都会蕴含一个 node_zonelists,其中蕴含了以后 NUMA 节点以及备用 NUMA 节点的所有内存区域以及对应的搭档零碎,以后 NUMA 节点内存不足时,内核会从 node_zonelists 中的备用 NUMA 节点中分配内存。

这里也是同样的情理,当搭档零碎中指定的迁徙列表 free_list[MIGRATE_TYPE] 无奈满足内存调配需要时,内核依据不同迁徙类型定义了不同的 fallback 规定:

/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
 *
 * The other migratetypes do not have fallbacks.
 */
static int fallbacks[MIGRATE_TYPES][3] = {[MIGRATE_UNMOVABLE]   = {MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES},
    [MIGRATE_MOVABLE]     = {MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES},
    [MIGRATE_RECLAIMABLE] = {MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES},
};

比方:MIGRATE_UNMOVABLE 类型的 free_list 内存不足时,内核会 fallback 到 MIGRATE_RECLAIMABLE 中去获取,如果还是有余,则再次降级到 MIGRATE_MOVABLE 中获取,如果依然无奈满足内存调配,才会失败退出。

失常的调配流程先是从低阶到高阶顺次查找闲暇内存块,而后将高阶中的内存块顺次减半决裂到低阶 free_list 链表中。

内存调配 fallback 流程则刚好是相同的,它是先从备用 fallback 类型的迁徙列表中的 最高阶 开始查找,找到一块闲暇内存块之后,先迁徙到最后指定的 free_list[MIGRATE_TYPE] 链表中,而后在指定的 free_list[MIGRATE_TYPE] 链表执行减半决裂。

内核这里的 fallback 策略是:如果无奈防止调配迁徙类型不同的内存块,那么就调配一个尽可能大的内存块(从最高阶开始查找),防止向其余链表引入内存碎片。

笔者还是以上边的例子阐明,当咱们向搭档零碎申请 MIGRATE_UNMOVABLE 迁徙类型的内存时,假如内核在搭档零碎中的 free_area[0] 到 free_area[10] 中的所有 free_list[MIGRATE_UNMOVABLE] 链表中均无奈找到一个闲暇的内存块。

那么就会 fallback 到 MIGRATE_RECLAIMABLE 类型,从最高阶 free_area[10] 中的 free_list[MIGRATE_RECLAIMABLE] 链表开始查找,如果找到一个闲暇的内存块,则首先会迁徙到对应的 order 的 free_list[MIGRATE_UNMOVABLE] 链表,而后流程持续回到外围流程,在各个 free_area[order] 对应的 free_list[MIGRATE_UNMOVABLE] 链表中执行减半决裂。

这里大家只须要了解一下 fallback 的大略流程,具体内容笔者会在前面介绍搭档零碎实现的章节具体解析~~~

4. 搭档零碎的内存回收原理

内存有调配就会有开释,本大节咱们就来看下如何将内存块开释回搭档零碎中。在上个大节中笔者为大家介绍了搭档零碎内存调配的残缺流程,外围就是从高阶 free_list 中寻找闲暇内存块,而后顺次减半决裂。

搭档零碎中的内存回收刚好和内存调配的过程相同,外围则是从低阶 free_list 中寻找开释内存块的搭档,如果没有搭档则将要开释的内存块插入到对应调配阶 order 的 free_list 中。如果存在搭档,则将开释内存块与它的搭档合并,作为一个新的内存块持续到更高阶的 free_list 中循环反复上述过程,直到不能合并为止。

搭档的概念咱们曾经在本文《2. 到底什么是搭档》大节中介绍过了,外围就是两个搭档内存块必须是大小雷同并且在物理内存上是间断的。

上面笔者还是举一个具体的例子来为大家展示搭档零碎内存回收的过程:

为了清晰地给大家展示搭档零碎的内存回收过程,咱们临时疏忽 MIGRATE_TYPES 相干的组织构造

假如以后搭档零碎的状态如上图所示,当初咱们须要向搭档零碎开释一个内存页(order = 0),编号为 10。

这里笔者先来解释下上图搭档零碎中所治理的物理内存页后边编号的含意:咱们晓得搭档零碎中所治理的全副是间断的物理内存,既然是间断的,那么每个内存页 page 都会有一个固定的偏移(相似数组中的下标)。

这一点咱们在前边的文章《深刻了解 Linux 物理内存治理》的“4.2 NUMA 节点描述符 pglist_data 构造”大节中曾经介绍过了,在每个 NUMA 节点中,内核通过一个 node_mem_map 数组来组织节点内的物理内存页 page。

typedef struct pglist_data {
    // NUMA 节点 id
    int node_id;
    // 指向 NUMA 节点内治理所有物理页 page 的数组
    struct page *node_mem_map;
}

上图搭档零碎中所治理的内存页 page 只是被搭档零碎组织之后的视图,上面是物理内存页在物理内存上的实在视图(蕴含要被开释的内存页 10):

有了这些基本概念之后,我回过头来在看 page10 开释回搭档零碎的整个过程:

上面的流程须要大家时刻比照内存页在物理内存上的实在视图,不要被搭档零碎的组织视图所烦扰。

因为咱们要开释的内存块只蕴含了一个物理内存页 page10,所以它的调配阶 order = 0,首先内核须要在搭档零碎 free_area[0] 中查找与 page10 大小相等并且间断的内存块(搭档)。

从物理内存的实在视图中咱们能够看到 page11 是 page10 的搭档,于是将 page11 从 free_area[0] 上摘下并与 page10 合并组成一个新的内存块(调配阶 order = 1)。随后内核会在 free_area[1] 中查找新内存块的搭档:

咱们持续比照物理内存页的实在视图,发现在 free_area[1] 中 page8 和 page9 组成的内存块与 page10 和 page11 组成的内存块是搭档,于是持续将这两个内存块(调配阶 order = 1)持续合并成一个新的内存块(调配阶 order = 2)。随后内核会在 free_area[2] 中查找新内存块的搭档:

持续比照物理内存页的实在视图,发现在 free_area[2] 中 page12,page13,page14,page15 组成的内存块与 page8,page9,page10,page11 组成的新内存块是搭档,于是将它们从 free_area[2] 上摘下持续合并成一个新的内存块(调配阶 order = 3),随后内核会在 free_area[3] 中查找新内存块的搭档:

比照物理内存页的实在视图,咱们发现在 free_area[3] 中的内存块(page20 到 page 27)与新合并的内存块(page8 到 page15)尽管大小雷同然而物理上并不间断,所以它们不是搭档,不能在持续向上合并了。于是内核将 page8 到 pag15 组成的内存块(调配阶 order = 3)插入到 free_area[3] 中,至此内存开释过程完结。

到这里对于搭档零碎内存调配以及回收的外围原理笔者就为大家全副介绍完了,内存调配和开释的过程刚好是相同的过程。

内存调配是从高阶先查找到闲暇内存块,而后顺次减半决裂,将决裂后的内存块插入到低阶的 free_list 中,将最初决裂进去的内存块调配给过程。

内存开释是先从低阶开始查找开释内存块的搭档,如果找到,则两两合并成一个新的内存块,随后持续到高阶中去查找新内存块的搭档,直到没有搭档能够合并。

一个是高阶到低阶决裂,一个是低阶到高阶合并。

5. 进入搭档零碎的前奏

当初咱们曾经分明了搭档零碎的所有外围原理,然而干讲原理总感觉 talk is cheap,还是须要 show 一下 code,所以接下来笔者会带大家看一下内核中搭档零碎的实现源码,真刀真枪的来一下。

但真正进入搭档零碎之前,内核还是做了很多铺垫工作,为了给大家解释分明这些内容,咱们还是须要从新回到上篇文章《深刻了解 Linux 物理内存调配全链路实现》“5. __alloc_pages 内存调配流程总览”大节中留下的尾巴,正式来介绍下 get_page_from_freelist 函数。

在上篇文章“3. 物理内存调配内核源码实现”大节中,笔者为大家介绍了 Linux 物理内存调配的残缺流程,咱们晓得物理内存调配总体上分为两个门路,内核首先尝试的是在疾速门路下分配内存,如果不行的话,内核会走慢速门路分配内存。

无论是疾速门路还是慢速门路下的内存调配都须要最终调用 get_page_from_freelist 函数进行最终的内存调配。只不过,不同门路下 get_page_from_freelist 函数的内存调配策略以及须要思考的内存水位线会有所不同,其中慢速门路下的内存调配策略会更加激进一些,这一点咱们在上篇文章的相干章节内容介绍中领会很深。

在每次调用 get_page_from_freelist 函数之前,内核都会依据新的内存调配策略来从新初始化 struct alloc_context 构造,alloc_context 构造体中蕴含了内存调配所须要的所有外围参数。具体初始化过程能够回看上篇文章的“3.3 prepare_alloc_pages”大节的内容。

struct alloc_context {
    // 运行过程 CPU 所在 NUMA 节点以及其所有备用 NUMA 节点中容许内存调配的内存区域
    struct zonelist *zonelist;
    // NUMA 节点状态掩码
    nodemask_t *nodemask;
    // 内存调配优先级最高的内存区域 zone
    struct zoneref *preferred_zoneref;
    // 物理内存页的迁徙类型分为:不可迁徙,可回收,可迁徙类型,避免内存碎片
    int migratetype;

    // 内存调配最高优先级的内存区域 zone
    enum zone_type highest_zoneidx;
    // 是否容许以后 NUMA 节点中的脏页平衡扩散迁徙至其余 NUMA 节点
    bool spread_dirty_pages;
};

这里最外围的两个参数就是 zonelist 和 preferred_zoneref。preferred_zoneref 示意以后本地 NUMA 节点(优先级最高),其中 zonelist 咱们在《深刻了解 Linux 物理内存治理》的“4.3 NUMA 节点物理内存区域的划分”大节中具体介绍过,zonelist 外面蕴含了以后 NUMA 节点在内的所有备用 NUMA 节点的所有物理内存区域,用于以后 NUMA 节点没有足够闲暇内存的状况下进行跨 NUMA 节点调配。

typedef struct pglist_data {
    // NUMA 节点中的物理内存区域个数
    int nr_zones; 
    // NUMA 节点中的物理内存区域
    struct zone node_zones[MAX_NR_ZONES];
    // NUMA 节点的备用列表
    struct zonelist node_zonelists[MAX_ZONELISTS];
} pg_data_t;

struct pglist_data 里的 node_zonelists 是一个选集,而 struct alloc_context 里的 zonelist 是在内存调配过程中,依据指定的内存调配策略从选集 node_zonelists 过滤出来的一个子集(容许进行本次内存调配的所有 NUMA 节点及其内存区域)。

get_page_from_freelist 的外围逻辑其实很简略,就是遍历 struct alloc_context 里的 zonelist,挨个查看各个 NUMA 节点中的物理内存区域是否有足够的闲暇内存能够满足本次的内存调配要求,如果能够满足则进入该物理内存区域的搭档零碎中残缺真正的内存调配动作。

上面咱们先来看一下 get_page_from_freelist 函数的残缺逻辑:

/*
 * get_page_from_freelist goes through the zonelist trying to allocate
 * a page.
 */
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
                        const struct alloc_context *ac)
{
    struct zoneref *z;
    // 以后遍历到的内存区域 zone 援用
    struct zone *zone;
    // 最近遍历的 NUMA 节点
    struct pglist_data *last_pgdat = NULL;
    // 最近遍历的 NUMA 节点中蕴含的脏页数量是否在内核限度范畴内
    bool last_pgdat_dirty_ok = false;
    // 如果须要防止内存碎片,则 no_fallback = true
    bool no_fallback;

retry:
    // 是否须要防止内存碎片
    no_fallback = alloc_flags & ALLOC_NOFRAGMENT;
    z = ac->preferred_zoneref;
    // 开始遍历 zonelist,查找能够满足本次内存调配的物理内存区域 zone
    for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
                    ac->nodemask) {
        // 指向调配胜利之后的内存
        struct page *page;
        // 内存调配过程中设定的水位线
        unsigned long mark;
        // 查看内存区域所在 NUMA 节点是否在过程所容许的 CPU 上
        if (cpusets_enabled() &&
            (alloc_flags & ALLOC_CPUSET) &&
            !__cpuset_zone_allowed(zone, gfp_mask))
                continue;
        // 每个 NUMA 节点中蕴含的脏页数量都有肯定的限度。// 如果本次内存调配是为 page cache 调配的 page,用于写入数据(不久就会变成脏页)// 这里须要查看以后 NUMA 节点的脏页比例是否在限度范畴内容许的
        // 如果没有超过脏页限度则能够进行调配,如果曾经超过 last_pgdat_dirty_ok = false
        if (ac->spread_dirty_pages) {if (last_pgdat != zone->zone_pgdat) {
                last_pgdat = zone->zone_pgdat;
                last_pgdat_dirty_ok = node_dirty_ok(zone->zone_pgdat);
            }

            if (!last_pgdat_dirty_ok)
                continue;
        }

        // 如果内核设置了防止内存碎片标识,在本地节点无奈满足内存调配的状况下(因为须要防止内存碎片)
        // 这轮循环会遍历 remote 节点(跨 NUMA 节点)if (no_fallback && nr_online_nodes > 1 &&
            zone != ac->preferred_zoneref->zone) {
            int local_nid;
            // 如果本地节点分配内存失败是因为防止内存碎片的起因,那么会持续回到本地节点进行 retry 重试同时勾销 ALLOC_NOFRAGMENT(容许引入碎片)local_nid = zone_to_nid(ac->preferred_zoneref->zone);
            if (zone_to_nid(zone) != local_nid) {
                // 内核认为保障本地的局部性会比防止内存碎片更加重要
                alloc_flags &= ~ALLOC_NOFRAGMENT;
                goto retry;
            }
        }
        // 获取本次内存调配须要思考到的内存水位线,疾速门路下是 WMARK_LOW, 慢速门路下是 WMARK_MIN
        mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK);
        // 查看以后遍历到的 zone 里残余的闲暇内存容量是否在指定水位线 mark 之上
        // 残余内存容量在水位线之下返回 false
        if (!zone_watermark_fast(zone, order, mark,
                       ac->highest_zoneidx, alloc_flags,
                       gfp_mask)) {
            int ret;

            // 如果本次内存调配策略是疏忽内存水位线,那么就在本次遍历到的 zone 里尝试分配内存
            if (alloc_flags & ALLOC_NO_WATERMARKS)
                goto try_this_zone;
            // 如果本次内存调配不能疏忽内存水位线的限度,那么就会判断以后 zone 所属 NUMA 节点是否容许进行内存回收
            if (!node_reclaim_enabled() ||
                !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
                // 不容许进行内存回收则持续遍历下一个 NUMA 节点的内存区域
                continue;
            // 针对以后 zone 所在 NUMA 节点进行内存回收
            ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
            switch (ret) {
            case NODE_RECLAIM_NOSCAN:
                // 返回该值示意以后 NUMA 节点没有必要进行回收。比方疾速调配门路下就不解决页面回收的问题
                continue;
            case NODE_RECLAIM_FULL:
                // 返回该值示意通过扫描之后发现以后 NUMA 节点并没有能够回收的内存页
                continue;
            default:
                // 该分支示意以后 NUMA 节点曾经进行了内存回收操作
                // zone_watermark_ok 判断内存回收是否回收了足够的内存是否满足内存调配的须要
                if (zone_watermark_ok(zone, order, mark,
                    ac->highest_zoneidx, alloc_flags))
                    goto try_this_zone;

                continue;
            }
        }

try_this_zone:
        // 这里就是搭档零碎的入口,rmqueue 函数中封装的就是搭档零碎的外围逻辑
        // 从搭档零碎中获取内存
        page = rmqueue(ac->preferred_zoneref->zone, zone, order,
                gfp_mask, alloc_flags, ac->migratetype);
        if (page) {
            // 分配内存胜利,初始化内存页 page
            prep_new_page(page, order, gfp_mask, alloc_flags);
            return page;
        } else {....... 省略 .....}
    }
        
    // 内存调配失败
    return NULL;
}

与本文主题无关的非核心步骤大家通过笔者的正文简略理解即可,上面咱们只介绍与本文主题相干的外围步骤。

尽管 get_page_from_freelist 函数的代码比拟简短,然而其外围逻辑比较简单,骨干框架就是通过 for_next_zone_zonelist_nodemask 来遍历以后 NUMA 节点以及备用节点的所有内存区域(zonelist),而后一一通过 zone_watermark_fast 查看这些内存区域 zone 中的残余闲暇内存容量是否在指定的水位线 mark 之上。如果满足水位线的要求则间接调用 rmqueue 进入搭档零碎分配内存,调配胜利之后通过 prep_new_page 初始化调配好的内存页 page。

如果以后正在遍历的 zone 中残余闲暇内存容量在指定的水位线 mark 之下,就须要通过 node_reclaim 触发内存回收,随后通过 zone_watermark_ok 查看通过内存回收之后,内核是否回收到了足够的内存以满足本次内存调配的须要。如果内存回收到了足够的内存则 zone_watermark_ok = true 随后跳转到 try_this_zone 分支在本内存区域 zone 中分配内存。否则持续遍历下一个 zone。

5.1 获取内存区域 zone 里指定的内存水位线

get_page_from_freelist 函数中的内存调配逻辑是要思考内存水位线的,满足内存调配要求的物理内存区域 zone 中的残余闲暇内存容量必须在指定内存水位线之上。否则内核则认为内存不足不能进行内存调配。

在上篇文章《深刻了解 Linux 物理内存调配全链路实现》中的“3.2 内存调配的心脏 __alloc_pages”大节的介绍中,咱们晓得在疾速门路下,内存调配策略中的水位线设置为 WMARK_LOW:

    // 内存区域中的残余内存须要在 WMARK_LOW 水位线之上能力进行内存调配,否则失败(首次尝试疾速内存调配)unsigned int alloc_flags = ALLOC_WMARK_LOW;

在上篇文章“4. 内存慢速调配入口 alloc_pages_slowpath”大节的介绍中,咱们晓得在慢速门路下,内存调配策略中的水位线又被调整为了 WMARK_MIN:

    // 在慢速内存调配门路中,会进一步放宽对内存调配的限度,将内存调配水位线调低到 WMARK_MIN
    // 也就是说内存区域中的残余内存须要在 WMARK_MIN 水位线之上就能够进行内存调配了
    unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;

如果内存调配依然失败,则内核会将内存调配策略中的水位线调整为 ALLOC_NO_WATERMARKS,示意再内存调配时,能够疏忽水位线的限度,再一次进行重试。

不同的内存水位线会影响到内存调配逻辑,所以在通过 for_next_zone_zonelist_nodemask 遍历 NUMA 节点中的物理内存区域的一开始就须要获取该内存区域指定水位线的具体数值,内核通过 wmark_pages 宏来获取:

#define wmark_pages(z, i) (z->_watermark[i] + z->watermark_boost)
struct zone {
    // 物理内存区域中的水位线
    unsigned long _watermark[NR_WMARK];
    // 优化内存碎片对内存调配的影响,能够动静扭转内存区域的基准水位线。unsigned long watermark_boost;
}

对于内存区域 zone 中水位线的相干内容介绍,大家能够回看下笔者之前的文章《深刻了解 Linux 物理内存治理》中“5.2 物理内存区域中的水位线”大节。

5.2 查看 zone 中残余内存容量是否满足水位线要求

在咱们通过 wmark_pages 获取到以后内存区域 zone 的指定水位线 mark 之后,咱们就须要近一步判断以后 zone 中残余的闲暇内存容量是否在水位线 mark 之上,这是保障内存调配顺利进行的必要条件。

内核中判断水位线的逻辑封装在 zone_watermark_fast 和 __zone_watermark_ok 函数中,其中外围逻辑在 __zone_watermark_ok 里,zone_watermark_fast 只是用来疾速检测调配阶 order = 0 状况下的相干水位线状况。

上面咱们先来看下 zone_watermark_fast 的逻辑:

static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
                unsigned long mark, int highest_zoneidx,
                unsigned int alloc_flags, gfp_t gfp_mask)
{
    long free_pages;
    // 获取以后内存区域中所有闲暇的物理内存页
    free_pages = zone_page_state(z, NR_FREE_PAGES);

    // 疾速查看调配阶 order = 0 状况下相干水位线,闲暇内存须要刨除掉为 highatomic 预留的紧急内存
    if (!order) {
        long usable_free;
        long reserved;
        // 可供本次内存调配应用的符合要求的实在可用内存,初始为 free_pages
        // free_pages 为闲暇内存页的选集其中也包含了不能为本次内存调配提供内存的闲暇内存
        usable_free = free_pages;
        // 获取本次不能应用的闲暇内存页数量
        reserved = __zone_watermark_unusable_free(z, 0, alloc_flags);

        // 计算真正可供内存调配的闲暇页数量:闲暇内存页选集 - 不能应用的闲暇页
        usable_free -= min(usable_free, reserved);
        // 如果可用的闲暇内存页数量大于内存水位线与预留内存之和
        // 那么示意物理内存区域中的可用闲暇内存可能满足本次内存调配的须要
        if (usable_free > mark + z->lowmem_reserve[highest_zoneidx])
            return true;
    }
    // 近一步查看内存区域搭档零碎中是否有足够的 order 阶的内存块可供调配
    if (__zone_watermark_ok(z, order, mark, highest_zoneidx, alloc_flags,
                    free_pages))
        return true;

        ........ 省略无关代码 .......

    // 水位线查看失败
    return false;
}

首先会通过 zone_page_state 来获取以后 zone 中残余闲暇内存页的总体容量 free_pages。

笔者在《深刻了解 Linux 物理内存治理》的“5. 内核如何治理 NUMA 节点中的物理内存区域”大节中为大家介绍 struct zone 构造体的时候提过,每个内存区域 zone 里有一个 vm_stat 用来寄存与 zone 相干的各种统计变量。

struct zone {
    // 该内存区域内存应用的统计信息
    atomic_long_t       vm_stat[NR_VM_ZONE_STAT_ITEMS];
} 

内核能够通过 zone_page_state 来拜访 vm_stat 从而获取对应的统计量,free_pages 就是其中的一个统计变量。然而这里大家须要留神的是 free_pages 示意的以后 zone 里残余闲暇内存页的一个总量,是一个选集的概念。其中还包含了内存区域的预留内存 lowmem_reserve 以及为 highatomic 预留的紧急内存。这些预留内存都有本人特定的用处,一般内存的申请不会用到预留内存。

流程如果进入到 if (!order) 分支的话示意本次内存调配只是申请一个(order = 0)闲暇的内存页,在这里会疾速的检测相干水位线状况是否满足,如果满足就会疾速返回。

这里波及到两个重要的局部变量,笔者须要向大家交代一下:

  • usable_free:示意可供本次内存调配应用的闲暇内存页总量。前边咱们提到 free_pages 示意的是残余闲暇内存页的一个选集,里边还包含很多不能进行一般内存调配的闲暇内存页,比方预留内存和紧急内存。
  • reserved:示意本次内存调配不能应用到的闲暇内存页数量,这一部分的内存页数量计算是通过 __zone_watermark_unusable_free 函数实现的。最初应用 free_pages 减去 reserved 就能够失去真正的 usable_free。
static inline long __zone_watermark_unusable_free(struct zone *z,
                unsigned int order, unsigned int alloc_flags)
{
    // ALLOC_HARDER 的设置示意能够应用 high-atomic 紧急预留内存
    const bool alloc_harder = (alloc_flags & (ALLOC_HARDER|ALLOC_OOM));
    long unusable_free = (1 << order) - 1;
    // 如果没有设置 ALLOC_HARDER 则不能应用  high_atomic 紧急预留内存
    if (likely(!alloc_harder))
        // 不可用内存的数量须要统计上 high-atomic 这部分内存
        unusable_free += z->nr_reserved_highatomic;

#ifdef CONFIG_CMA
    // 如果没有设置 ALLOC_CMA 则示意本次内存调配不能从 CMA 区域获取
    if (!(alloc_flags & ALLOC_CMA))
        // 不可用内存的数量须要统计上 CMA 区域中的闲暇内存页
        unusable_free += zone_page_state(z, NR_FREE_CMA_PAGES);
#endif
    // 返回不可用内存的数量,示意本次内存调配不能应用的内存容量
    return unusable_free;
}

如果 usable_free > mark + z->lowmem_reserve[highest_zoneidx] 条件为 true 示意以后可用残余内存页容量在水位线 mark 之上,能够进行内存调配,返回 true。

咱们在《深刻了解 Linux 物理内存治理》的 ” 5.2 物理内存区域中的水位线 ” 大节中介绍水位线相干的计算逻辑的时候提过,水位线的计算是须要刨去 lowmem_reserve 预留内存的,也就是水位线的值并不蕴含 lowmem_reserve 内存在内。

所以这里在判断可用内存是否满足水位线的关系时须要加上这部分 lowmem_reserve,能力失去正确的后果。

如果本次内存调配申请的是高阶内存块(order > 0),则会进入 __zone_watermark_ok 函数中,近一步判断搭档零碎中是否有足够的高阶内存块可能满足 order 阶的内存调配:

bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
             int highest_zoneidx, unsigned int alloc_flags,
             long free_pages)
{
    // 保障内存调配顺利进行的最低水位线
    long min = mark;
    int o;
    const bool alloc_harder = (alloc_flags & (ALLOC_HARDER|ALLOC_OOM));

    // 获取真正可用的残余闲暇内存页数量
    free_pages -= __zone_watermark_unusable_free(z, order, alloc_flags);

    // 如果设置了 ALLOC_HIGH 则水位线升高二分之一,使内存调配更加致力激进一些
    if (alloc_flags & ALLOC_HIGH)
        min -= min / 2;

    if (unlikely(alloc_harder)) {
        // 在要进行 OOM 的状况下内存调配会比一般的  ALLOC_HARDER 策略更加致力激进一些,所以这里水位线会升高二分之一
        if (alloc_flags & ALLOC_OOM)
            min -= min / 2;
        else
            // ALLOC_HARDER 策略下水位线只会升高四分之一 
            min -= min / 4;
    }

    // 查看以后可用残余内存是否在指定水位线之上。// 内存的调配必须保障可用残余内存容量在指定水位线之上,否则不能进行内存调配
    if (free_pages <= min + z->lowmem_reserve[highest_zoneidx])
        return false;

    // 流程走到这里,对应内存调配阶 order = 0 的状况下就曾经 OK 了
    // 残余闲暇内存在水位线之上,那么必定可能调配一页进去
    if (!order)
        return true;

    // 然而对于 high-order 的内存调配,这里还须要近一步查看搭档零碎
    // 依据搭档零碎内存调配的原理,这里须要查看高阶 free_list 中是否有足够的闲暇内存块可供调配 
    for (o = order; o < MAX_ORDER; o++) {
        // 从以后调配阶 order 对应的 free_area 中查看是否有足够的内存块
        struct free_area *area = &z->free_area[o];
        int mt;
        // 如果以后 free_area 中的 nr_free = 0 示意对应 free_list 中没有适合的闲暇内存块
        // 那么持续到高阶 free_area 中查找
        if (!area->nr_free)
            continue;
         // 查看 free_area 中所有的迁徙类型 free_list 是否有足够的内存块
        for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {if (!free_area_empty(area, mt))
                return true;
        }

#ifdef CONFIG_CMA
       // 如果内存调配指定须要从 CMA 区域中调配间断内存
       // 那么就须要查看 MIGRATE_CMA 对应的 free_list 是否是空
        if ((alloc_flags & ALLOC_CMA) &&
            !free_area_empty(area, MIGRATE_CMA)) {return true;}
#endif
        // 如果设置了 ALLOC_HARDER,则示意能够从 HIGHATOMIC 区中的紧急预留内存中调配,查看对应 free_list
        if (alloc_harder && !free_area_empty(area, MIGRATE_HIGHATOMIC))
            return true;
    }
    // 搭档零碎中的残余内存块无奈满足 order 阶的内存调配
    return false;
}

在 __zone_watermark_ok 函数的开始须要计算出真正可用的残余内存 free_pages。

    // 获取真正可用的残余闲暇内存页数量
    free_pages -= __zone_watermark_unusable_free(z, order, alloc_flags);

紧接着内核会依据 ALLOC_HIGH 以及 ALLOC_HARDER 标识来决定是否升高水位线的要求。在《深刻了解 Linux 物理内存调配全链路实现》一文中的“3.1 内存调配行为标识掩码 ALLOC_”大节中笔者曾具体的为大家介绍过这些 ALLOC_ 相干的掩码,过后笔者提了一句,当内存调配策略设置为 ALLOC_HIGH 或者 ALLOC_HARDER 时,会使内存调配更加的激进,致力一些。

过后大家可能会比拟懵,怎么才算是激进?怎么才算是致力呢?

其实答案就在这里,当内存调配策略 alloc_flags 设置了 ALLOC_HARDER 时,水位线的要求会升高原来的四分之一,相当于放款了内存调配的限度。比原来更加致力使内存调配胜利。

当内存调配策略 alloc_flags 设置了 ALLOC_HIGH 时,水位线的要求会升高原来的二分之一,相当于更近一步放款了内存调配的限度。比原来更加激进些。

在调整完水位线之后,还是一样的逻辑,须要判断以后可用残余内存容量是否在水位线之上,如果是,则水位线查看结束合乎内存调配的要求。如果不是,则返回 false 不能进行内存调配。

// 内存的调配必须保障可用残余内存容量在指定水位线之上,否则不能进行内存调配
free_pages <= min + z->lowmem_reserve[highest_zoneidx])

在水位线 OK 之后,对于 order = 0 的内存调配情景下,就曾经 OK 了,能够释怀间接进行内存调配了。

然而对于 high-order 的内存调配情景,这里还须要近一步查看搭档零碎是否有足够的闲暇内存块能够满足本次 high-order 的内存调配。

依据本文《3. 搭档零碎的内存调配原理》大节中,为大家介绍的搭档零碎内存调配原理,内核须要从以后调配阶 order 开始始终向高阶 free_area 中查找对应的 free_list 中是否有足够的内存块满足 order 阶的内存调配要求。

  • 如果有,那么水位线相干的校验工作到此结束,内核会间接去搭档零碎中申请 order 阶的内存块。
  • 如果没有,则水位线校验失败,搭档零碎无奈满足本次的内存调配要求。

5.3 内存调配胜利之后初始化 page

通过 zone_watermark_ok 的校验,当初内存水位线合乎内存调配的要求,并且搭档零碎中有足够的闲暇内存块可供内存调配申请,当初能够释怀调用 rmqueue 函数进入搭档零碎进行内存调配了。

rmqueue 函数封装的正是搭档零碎的外围逻辑,这一部分的源码实现笔者放在下一大节中介绍,这里咱们先关注内存调配胜利之后,对于内存页 page 的初始化逻辑。

当通过 rmqueue 函数从搭档零碎中胜利申请到调配阶为 order 大小的内存块时,内核须要调用 prep_new_page 函数初始化这部分内存块,之后能力返回给过程应用。

static void prep_new_page(struct page *page, unsigned int order, gfp_t gfp_flags,
                            unsigned int alloc_flags)
{
    // 初始化 struct page,革除一些页面属性标记
    post_alloc_hook(page, order, gfp_flags);

    // 设置复合页
    if (order && (gfp_flags & __GFP_COMP))
        prep_compound_page(page, order);

    if (alloc_flags & ALLOC_NO_WATERMARKS)
        // 应用 set_page_XXX(page) 办法设置 page 的 PG_XXX 标记位
        set_page_pfmemalloc(page);
    else
         // 应用 clear_page_XXX(page) 办法革除 page 的 PG_XXX 标记位
        clear_page_pfmemalloc(page);
}

5.3.1 初始化 struct page

因为当初咱们拿到的 struct page 构造是刚刚从搭档零碎中申请进去的,外面可能蕴含一些无用的标记(上一次被应用过的,还没清理),所以须要将这些无用标记清理掉,并且在此基础上依据 gfp_flags 掩码对 struct page 进行初始化的筹备工作。

比方通过 set_page_private 将 struct page 里的 private 指针所指向的内容清空,private 指针在内核中的应用比较复杂,它会在不同场景下指向不同的内容。

set_page_private(page, 0);

将页面的应用计数设置为 1,示意以后物理内存页正在被应用。

set_page_refcounted(page);

如果 gfp_flags 掩码中设置了 ___GFP_ZERO,这时就须要将这些 page 初始化为零页。

因为初始化页面的筹备工作和本文的主线内容并没有多大的关联,所以笔者这里只做简略介绍,大家大略理解一下初始化做了哪些筹备工作即可。

5.3.2 设置复合页 compound_page

复合页 compound_page 实质上就是通过两个或者多个物理上间断的内存页 page 组装成的一个在逻辑上看起来比一般内存页 page 更大的页。它底层的依赖实质还是一个一个的一般内存页 page。

咱们都晓得 Linux 治理内存的最小单位是 page,每个 page 形容 4K 大小的物理内存,但在一些内核应用场景中,比方 slab 内存池中,往往会向搭档零碎一次性申请多个一般内存页 page,而后将这些内存页 page 划分为多个大小雷同的小内存块,这些小内存块被 slab 内存池对立治理。

slab 内存池底层其实依赖的是多个一般内存页,然而内核冀望将这多个内存页对立成一个逻辑上的内存页来对立治理,这个逻辑上的内存页就是本大节要介绍的复合页。

而在 Linux 内存治理的架构中都是对立通过 struct page 来治理内存,复合页却是通过两个或者多个物理上间断的内存页 page 组装成的一个逻辑页,那么复合页的治理与一般页的治理如何对立呢?

这就引出了本大节的主题——复合页 compound_page,上面咱们就来看下 Linux 如果通过对立的 struct page 构造来形容这些复合页(compound_page):

尽管复合页(compound_page)是由多个物理上间断的一般 page 组成的,然而在内核的视角里它还是被当做一个非凡内存页来对待。

下图所示,是由 4 个间断的一般内存页 page 组成的一个 compound_page:

组成复合页的第一个 page 咱们称之为首页(Head Page),其余的均称之为尾页(Tail Page)。

咱们来看一下 struct page 中对于形容 compound_page 的相干字段:

      struct page {      
            // 首页 page 中的 flags 会被设置为 PG_head 示意复合页的第一页
            unsigned long flags;    
            // 其余尾页会通过该字段指向首页
            unsigned long compound_head;   
            // 用于开释复合页的析构函数,保留在首页中
            unsigned char compound_dtor;
            // 该复合页有多少个 page 组成,order 还是调配阶的概念,在首页中保留
            // 本例中的 order = 2 示意由 4 个一般页组成
            unsigned char compound_order;
            // 该复合页被多少个过程应用,内存页反向映射的概念,首页中保留
            atomic_t compound_mapcount;
            // 复合页应用计数,首页中保留
            atomic_t compound_pincount;
      }

首页对应的 struct page 构造里的 flags 会被设置为 PG_head,示意这是复合页的第一页。

另外首页中还保留对于复合页的一些额定信息,比方:

  • 用于开释复合页的析构函数会保留在首页 struct page 构造里的 compound_dtor 字段中
  • 复合页的调配阶 order 会保留在首页中的 compound_order 中以及用于批示复合页的援用计数 compound_pincount,以及复合页的反向映射个数(该复合页被多少个过程的页表所映射)compound_mapcount 均在首页中保留。

对于 struct page 的 flags 字段的介绍,以及内存页反向映射原理,大家能够回看下笔者《深刻了解 Linux 物理内存治理》中的“6.4 物理内存页属性和状态的标记位 flag”和“6.1 匿名页的反向映射”大节。

复合页中的所有尾页都会通过其对应的 struct page 构造中的 compound_head 指向首页,这样通过首页和尾页就组装成了一个残缺的复合页 compound_page。

在咱们了解了 compound_page 的组织构造之后,咱们在回过头来看 “6.3 内存调配胜利之后初始化 page” 大节中的 prep_new_page 函数:

当内核向搭档零碎申请复合页 compound_page 的时候,会在 gfp_flags 掩码中设置 __GFP_COMP 标识,表次本次内存调配要调配一个复合页,复合页中的 page 个数由调配阶 order 决定。

当内核向搭档零碎申请了 2 ^ order 个内存页 page 时,大家留神在搭档零碎的视角中内存还是一页一页的,搭档零碎并不知道有复合页的存在,当咱们申请胜利之后,须要在 prep_new_page 函数中将这 2 ^ order 个内存页 page 依照后面介绍的逻辑组装成一个 复合页 compound_page。

void prep_compound_page(struct page *page, unsigned int order)
{
    int i;
    int nr_pages = 1 << order;
    // 设置首页 page 中的 flags 为 PG_head
    __SetPageHead(page);
    // 首页之后的 page 全副是尾页,循环遍历设置尾页
    for (i = 1; i < nr_pages; i++)
        prep_compound_tail(page, i);
    // 最初设置首页相干属性
    prep_compound_head(page, order);
}
static void prep_compound_tail(struct page *head, int tail_idx)
{
    // 因为复合页中的 page 全副是间断的,间接应用偏移即可取得对应尾页
    struct page *p = head + tail_idx;
    // 设置尾页标识
    p->mapping = TAIL_MAPPING;
    // 尾页 page 构造中的 compound_head 指向首页
    set_compound_head(p, head);
}
static __always_inline void set_compound_head(struct page *page, struct page *head)
{WRITE_ONCE(page->compound_head, (unsigned long)head + 1);
}
static void prep_compound_head(struct page *page, unsigned int order)
{
    // 设置首页相干属性
    set_compound_page_dtor(page, COMPOUND_PAGE_DTOR);
    set_compound_order(page, order);
    atomic_set(compound_mapcount_ptr(page), -1);
    atomic_set(compound_pincount_ptr(page), 0);
}

6. 搭档零碎的实现

当初内核通过前边介绍的 get_page_from_freelist 函数,循环遍历 zonelist 终于找到了合乎内存调配条件的物理内存区域 zone。接下来就会通过 rmqueue 函数进入到该物理内存区域 zone 对应的搭档零碎中理论调配物理内存。

/*
 * Allocate a page from the given zone. Use pcplists for order-0 allocations.
 */
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)时,内核首先会从 CPU 高速缓存列表 pcplist 中间接调配,而不会走搭档零碎,进步内存调配速度
        page = rmqueue_pcplist(preferred_zone, zone, gfp_flags,
                    migratetype, alloc_flags);
        goto out;
    }
    // 加锁并敞开中断,避免并发拜访
    spin_lock_irqsave(&zone->lock, flags);

    // 当申请页面超过一个(order > 0)时,则从搭档零碎中进行调配
    do {
        page = NULL;
        if (alloc_flags & ALLOC_HARDER) {
            // 如果设置了 ALLOC_HARDER 调配策略,则从搭档零碎的 HIGHATOMIC 迁徙类型的 freelist 中获取
            page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
        }
        if (!page)
            // 从搭档零碎中申请调配阶 order 大小的物理内存块
            page = __rmqueue(zone, order, migratetype, alloc_flags);
    } while (page && check_new_pages(page, order));
    // 解锁
    spin_unlock(&zone->lock);
    if (!page)
        goto failed;
    // 从新统计内存区域中的相干统计指标
    zone_statistics(preferred_zone, zone);
    // 关上中断
    local_irq_restore(flags);

out:
    return page;

failed:
    // 调配失败
    local_irq_restore(flags);
    return NULL;
}

6.1 从 CPU 高速缓存列表中获取内存页

内核对只调配一页物理内存的状况做了非凡解决,当只申请一页内存时,内核会借助 CPU 高速缓存冷热页列表 pcplist 减速内存调配的解决,此时调配的内存页将来自于 pcplist 而不是搭档零碎。

pcp 是 per_cpu_pageset 的缩写,内核会为每个 CPU 调配一个高速缓存列表,对于这部分内容,笔者曾经在《深刻了解 Linux 物理内存治理》一文中的“5.7 物理内存区域中的冷热页”大节十分具体的为大家介绍过了,遗记的同学能够在回看下。

在 NUMA 内存架构下,每个物理内存区域都归属于一个特定的 NUMA 节点,NUMA 节点中蕴含了一个或者多个 CPU,NUMA 节点中的每个内存区域会关联到一个特定的 CPU 上.

而每个 CPU 都有本人独立的高速缓存,所以每个 CPU 对应一个 per_cpu_pageset 构造,用于治理这个 CPU 高速缓存中的冷热页。

所谓的热页就是曾经加载进 CPU 高速缓存中的物理内存页,所谓的冷页就是还未加载进 CPU 高速缓存中的物理内存页,冷页是热页的后备选项

每个 CPU 都能够拜访零碎中的所有物理内存页,只管访问速度不同,因而特定的物理内存区域 struct zone 不仅要思考到所属 NUMA 节点中相干的 CPU,还须要关照到零碎中的其余 CPU。

在 Linux 内核中,零碎会常常申请和开释单个页面。如果针对每个 CPU,都为其事后调配一个用于缓存单个内存页面的高速缓存页列表,用于满足本地 CPU 收回的单页内存申请,就能晋升零碎的性能。所以在 struct zone 构造中持有了零碎中所有 CPU 的高速缓存页列表 per_cpu_pageset。

struct zone {struct per_cpu_pages    __percpu *per_cpu_pageset;}
struct per_cpu_pages {
    int count;      /* pcplist 里的页面总数 */
    int high;       /* pcplist 里的高水位线,count 超过 high 时,内核会开释 batch 个页面到搭档零碎中 */
    int batch;      /* pcplist 里的页面来自于搭档零碎,batch 定义了每次从搭档零碎获取或者偿还多少个页面 */
    
    // CPU 高速缓存列表 pcplist,每个迁徙类型对应一个 pcplist
    struct list_head lists[NR_PCP_LISTS];
};

当内核尝试从 pcplist 中获取一个物理内存页时,会首先获取运行以后过程的 CPU 对应的高速缓存列表 pcplist。而后依据指定的具体页面迁徙类型 migratetype 获取对应迁徙类型的 pcplist。

当获取到符合条件的 pcplist 之后,内核会调用 __rmqueue_pcplist 从 pcplist 中摘下一个物理内存页返回。

/* Lock and remove page from the per-cpu list */
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 高速缓存列表 pcplist
    pcp = &this_cpu_ptr(zone->pageset)->pcp;
    // 获取指定页面迁徙类型的 pcplist
    list = &pcp->lists[migratetype];
    // 从指定迁徙类型的 pcplist 中移除一个页面,用于内存调配
    page = __rmqueue_pcplist(zone,  migratetype, alloc_flags, pcp, list);
    if (page) {
        // 统计内存区域内的相干信息
        zone_statistics(preferred_zone, zone);
    }
    // 开中断
    local_irq_restore(flags);
    return page;
}

pcplist 中缓存的内存页面其实全副来自于搭档零碎,当 pcplist 中的页面数量 count 为 0(示意此时 pcplist 里没有缓存的页面)时,内核会调用 rmqueue_bulk 从搭档零碎中获取 batch 个物理页面增加到 pcplist,从搭档零碎中获取页面的过程参照本文 “3. 搭档零碎的内存调配原理 ” 大节中的内容。

随后内核会将 pcplist 中的第一个物理内存页从链表中摘下返回,count 计数减一。

/* Remove page from the per-cpu list, caller must protect the list */
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 {
        // 如果以后 pcplist 中的页面为空,那么则从搭档零碎中获取 batch 个页面放入 pcplist 中
        if (list_empty(list)) {
            pcp->count += rmqueue_bulk(zone, 0,
                    pcp->batch, list,
                    migratetype, alloc_flags);
            if (unlikely(list_empty(list)))
                return NULL;
        }
        // 获取 pcplist 上的第一个物理页面
        page = list_first_entry(list, struct page, lru);
        // 将该物理页面从 pcplist 中摘除
        list_del(&page->lru);
        // pcplist 中的 count  减一
        pcp->count--;
    } while (check_new_pcp(page));

    return page;
}

6.2 从搭档零碎中获取内存页

在本文 “3. 搭档零碎的内存调配原理 ” 大节中笔者具体为大家介绍了搭档零碎的整个内存调配原理,那么在本大节中,咱们将正式进入搭档零碎中,来看下搭档零碎在内核中是如何实现的。

在后面介绍的 rmqueue 函数中,波及到搭档零碎入口函数的有两个:

  • __rmqueue_smallest 函数次要是封装了整个搭档零碎对于内存调配的外围流程,该函数中的代码正是“3. 搭档零碎的内存调配原理”大节所讲的核心内容。
  • __rmqueue 函数封装的是搭档零碎的整个残缺流程,底层调用了 __rmqueue_smallest 函数,它次要实现的是当搭档零碎 free_area 中对应的迁徙列表 free_list[MIGRATE_TYPE] 无奈满足内存调配需要时,内存调配在搭档零碎中的 fallback 流程。这一点笔者也在“3. 搭档零碎的内存调配原理”大节中具体介绍过了。

当咱们向内核申请的内存页超过一页(order > 0)时,内核就会进入搭档零碎中为咱们申请内存。

如果内存调配策略 alloc_flags 指定了 ALLOC_HARDER 时,就会调用 __rmqueue_smallest 间接进入搭档零碎,从 free_list[MIGRATE_HIGHATOMIC] 链表中调配 order 大小的物理内存块。

如果调配失败或者 alloc_flags 没有指定 ALLOC_HARDER 则会通过 __rmqueue 进入搭档零碎,这里会解决调配失败之后的 fallback 逻辑。

/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
 *
 * The other migratetypes do not have fallbacks.
 */
static int fallbacks[MIGRATE_TYPES][3] = {[MIGRATE_UNMOVABLE]   = {MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES},
    [MIGRATE_MOVABLE]     = {MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES},
    [MIGRATE_RECLAIMABLE] = {MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES},
};

6.2.1 __rmqueue_smallest 搭档零碎的外围实现

咱们还是以“3. 搭档零碎的内存调配原理”大节中,介绍搭档零碎内存调配外围原理时,所举的示例为大家分析搭档零碎的外围源码实现。

假如以后搭档零碎中只有 order = 3 的闲暇链表 free_area[3],其中只有一个闲暇的内存块,蕴含了间断的 8 个 page。其余剩下的调配阶 order 对应的闲暇链表中均是空的。

当初咱们向搭档零碎申请一个 page 大小的内存(对应的调配阶 order = 0),通过后面的介绍咱们晓得当申请一个 page 大小的内存时,内核是从 pcplist 中进行调配的,然而这里笔者为了不便给大家介绍搭档零碎,所以咱们临时让它走搭档零碎的流程。

内核会在搭档零碎中从以后调配阶 order 开始,顺次遍历 free_area[order] 里对应的指定页面迁徙类型 free_list[MIGRATE_TYPE] 链表,直到找到一个适合尺寸的内存块为止。

在本示例中,内核会在搭档零碎中首先查看 order = 0 对应的闲暇链表 free_area[0] 中是否有闲暇内存块可供调配。如果有,则将该闲暇内存块从 free_area[0] 摘下返回,内存调配胜利。

如果没有,随后内核会依据前边介绍的内存调配逻辑,持续降级到 free_area[1] , free_area[2] 链表中寻找闲暇内存块,直到查找到 free_area[3] 发现有一个可供调配的内存块。这个内存块中蕴含了 8 个间断的闲暇 page,而后将这 8 个 间断的闲暇 page 组成的内存块顺次进行减半决裂,将每次决裂进去的后半局部内存块插入到对应尺寸的 free_area 中,如下图所示:

/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
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;

    /* 从以后调配阶 order 开始在搭档零碎对应的  free_area[order]  里查找适合尺寸的内存块 */
    for (current_order = order; current_order < MAX_ORDER; ++current_order) {// 获取以后 order 在搭档零碎中对应的 free_area[order] 
        // 对应上图 free_area[3]
        area = &(zone->free_area[current_order]);
        // 从 free_area[order] 中对应的 free_list[MIGRATE_TYPE] 链表中获取闲暇内存块
        page = get_page_from_free_area(area, migratetype);
        if (!page)
            // 如果以后 free_area[order] 中没有闲暇内存块则持续向上查找
            // 对应上图 free_area[0],free_area[1],free_area[2]
            continue;
        // 如果在以后 free_area[order] 中找到闲暇内存块,则从 free_list[MIGRATE_TYPE] 链表中摘除
        // 对应上图步骤 1:将内存块从 free_area[3] 中摘除
        del_page_from_free_area(page, area);
        // 将摘下来的内存块进行减半决裂并插入对应的尺寸的 free_area 中
        // 对应上图步骤 [2,3], [4,5], [6,7]
        expand(zone, page, order, current_order, area, migratetype);
        // 设置页面的迁徙类型
        set_pcppage_migratetype(page, migratetype);
        // 内存调配胜利返回,对应上图步骤 8
        return page;
    }
    // 内存调配失败返回 null
    return NULL;
}

上面咱们来看下减半决裂过程的实现,expand 函数中的参数在本节示例中:low = 指定调配阶 order = 0,high = 最初遍历到的调配阶 order = 3。

static inline void expand(struct zone *zone, struct page *page,
    int low, int high, struct free_area *area,
    int migratetype)
{
    // size = 8,示意以后要进行减半决裂的内存块是由 8 个间断 page 组成的。// 刚刚从 free_area[3] 上摘下
    unsigned long size = 1 << high;

    // 顺次进行减半决裂,直到决裂出指定 order 的内存块进去
    // 对应上图中的步骤 2,4,6
    // 初始 high = 3 ,low = 0 
    while (high > low) {// free_area 要降到下一阶,此时变为 free_area[2]
        area--;
        // 调配阶要降级 high = 2
        high--;
        // 内存块尺寸要减半,由 8 变成 4,示意要决裂出由 4 个间断 page 组成的两个内存块。// 参考上图中的步骤 2
        size >>= 1;
        // 标记为爱护页,当其搭档被开释时,容许合并,参见《4. 搭档零碎的内存回收原理》大节
        if (set_page_guard(zone, &page[size], high, migratetype))
            continue;
        // 将本次减半决裂进去的第二个内存块插入到对应 free_area[high] 中
        // 参见上图步骤 3,5,7
        add_to_free_area(&page[size], area, migratetype);
        // 设置内存块的调配阶 high
        set_page_order(&page[size], high);

        // 本次决裂进去的第一个内存块持续循环进行减半决裂直到 high = low 
        // 即曾经决裂进去了指定 order 尺寸的内存块无需在进行决裂了,间接返回
        // 参见上图步骤 2,4,6
    }
}

6.2.2 __rmqueue 搭档零碎的 fallback 实现

当咱们向内核申请的内存页面超过一页(order > 0),并且内存调配策略 alloc_flags 中并没有设置 ALLOC_HARDER 的时候,内存调配流程就会进入 __rmqueue 走惯例的搭档零碎调配流程。

static __always_inline struct page *
__rmqueue(struct zone *zone, unsigned int order, int migratetype,
                        unsigned int alloc_flags)
{
    struct page *page;

retry:
    // 首先进入搭档零碎到指定页面迁徙类型的 free_list[migratetype] 获取闲暇内存块
    // 这里走的就是上大节中介绍的搭档系统核心流程
    page = __rmqueue_smallest(zone, order, migratetype);
    if (unlikely(!page)) {

      ..... 当搭档零碎中没有足够指定迁徙类型 migratetype 的闲暇内存块时,就会进入这个分支 .....

         // 如果迁徙类型是 MIGRATE_MOVABLE 则优先 fallback 到 CMA 区中分配内存
        if (migratetype == MIGRATE_MOVABLE)
            page = __rmqueue_cma_fallback(zone, order);
        // 走惯例的搭档零碎 fallback 流程,外围原理参见《3. 搭档零碎的内存调配原理》大节
        if (!page && __rmqueue_fallback(zone, order, migratetype,
                                alloc_flags))
            goto retry;
    }
    // 内存调配胜利
    return page;
}

从上述 __rmqueue 函数的源码实现中咱们能够看出,该函数解决了搭档零碎内存调配的异样流程,即调用 __rmqueue_smallest 进入搭档零碎分配内存时,发现搭档零碎各个调配阶 free_area[order] 中对应的迁徙列表 free_list[MIGRATE_TYPE] 无奈满足内存调配需要时,__rmqueue_smallest 函数就会返回 null,搭档零碎内存调配失败。

随后内核就会进入搭档零碎的 fallback 流程,这里对 MIGRATE_MOVABLE 迁徙类型做了一下非凡解决,当搭档零碎中 free_list[MIGRATE_MOVABLE] 没有足够闲暇内存块时,会优先降级到 CMA 区域内进行调配。

static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone,
                    unsigned int order)
{return __rmqueue_smallest(zone, order, MIGRATE_CMA);
}

如果咱们指定的页面迁徙类型并非 MIGRATE_MOVABLE 或者降级 CMA 之后依然调配失败,内核就会进入 __rmqueue_fallback 走惯例的 fallback 流程,该函数封装的正是笔者在“3. 搭档零碎的内存调配原理”大节的后半局部介绍的 fallback 逻辑:

在 __rmqueue_fallback 函数中,内核会依据事后定义的相干 fallback 规定开启内存调配的 fallback 流程。fallback 规定在内核中用一个 int 类型的二维数组示意,其中第一维示意须要进行 fallback 的页面迁徙类型,第二维示意 fallback 的优先级。后续内核会依照这个优先级 fallback 到具体的 free_list[fallback_migratetype] 中去分配内存。

static int fallbacks[MIGRATE_TYPES][3] = {[MIGRATE_UNMOVABLE]   = {MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES},
    [MIGRATE_MOVABLE]     = {MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES},
    [MIGRATE_RECLAIMABLE] = {MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES},
};

比方:MIGRATE_UNMOVABLE 类型的 free_list 内存不足时,内核会 fallback 到 MIGRATE_RECLAIMABLE 中去获取,如果还是有余,则再次降级到 MIGRATE_MOVABLE 中获取,如果依然无奈满足内存调配,才会失败退出。

static __always_inline bool
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype,
                        unsigned int alloc_flags)
{
    // 最终会 fall back 到搭档零碎的哪个 free_area 中分配内存
    struct free_area *area;
    // fallback 和失常的调配流程正好相同,是从最高阶的 free_area[MAX_ORDER - 1] 开始查找闲暇内存块
    int current_order;
    // 最后指定的内存调配阶
    int min_order = order;
    struct page *page;
    // 最终计算出 fallback 到哪个页面迁徙类型 free_list 上
    int fallback_mt;
    // 是否能够从 free_list[fallback] 中窃取内存块到 free_list[start_migratetype]  中
    // start_migratetype 示意咱们最后指定的页面迁徙类型
    bool can_steal;
    
    // 如果设置了 ALLOC_NOFRAGMENT 示意不心愿引入内存碎片
    // 在这种状况下内核会更加偏向于调配一个尽可能大的内存块,防止向其余链表引入内存碎片
    if (alloc_flags & ALLOC_NOFRAGMENT)
        // pageblock_order 用于定义零碎反对的巨型页对应的调配阶
        // 默认为最大调配阶 - 1 = 9
        min_order = pageblock_order;

    // fallback 内存调配流程从最高阶 free_area 开始查找闲暇内存块(页面迁徙类型为 fallback 类型)for (current_order = MAX_ORDER - 1; current_order >= min_order;
                --current_order) {
        // 获取搭档零碎中最高阶的 free_area
        area = &(zone->free_area[current_order]);
        // 依照上述的内存调配 fallback 规定查找最合适的 fallback 迁徙类型
        fallback_mt = find_suitable_fallback(area, current_order,
                start_migratetype, false, &can_steal);
        // 如果没有适合的 fallback_mt,则持续降级到下一个调配阶 free_area 中查找
        if (fallback_mt == -1)
            continue;

        // can_steal 会在 find_suitable_fallback 的过程中被设置
        // 当咱们指定的页面迁徙类型为 MIGRATE_MOVABLE 并且无奈从其余 fallback 迁徙类型列表中窃取页面 can_steal = false 时
        // 内核会更加偏向于 fallback 调配最小的可用页面,即尺寸和指定 order 最靠近的页面数量而不是尺寸最大的
        // 因为这里的条件是调配可挪动的页面类型,人造能够防止永恒内存碎片,无需依照最大的尺寸调配
        if (!can_steal && start_migratetype == MIGRATE_MOVABLE
                    && current_order > order)
            goto find_smallest;
        // can_steal = true,则开始从 free_list[fallback] 列表中窃取页面
        goto do_steal;
    }

    return false;

find_smallest:
    // 该分支目标在于寻找尺寸最贴近指定 order 大小的最小可用页面
    // 从指定 order 开始 fallback
    for (current_order = order; current_order < MAX_ORDER;
                            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)
            break;
    }

do_steal:
    // 从上述流程获取到的搭档零碎 free_area 中获取 free_list[fallback_mt]
    page = get_page_from_free_area(area, fallback_mt);
    // 从 free_list[fallback_mt] 中窃取页面到 free_list[start_migratetype] 中
    steal_suitable_fallback(zone, page, alloc_flags, start_migratetype,
                                can_steal);
    // 返回到 __rmqueue 函数中进行 retry 重试流程,此时 free_list[start_migratetype] 中曾经有足够的内存页面可供调配了
    return true;

}

从上述内存调配 fallback 源码实现中,咱们能够看出内存调配 fallback 流程正好和失常的调配流程相同:

  • 搭档零碎失常内存调配流程先是从低阶到高阶顺次查找闲暇内存块,而后将高阶中的内存块顺次减半决裂到低阶 free_list 链表中。
  • 搭档零碎 fallback 内存调配流程则是先从最高阶开始查找,找到一块闲暇内存块之后,先迁徙到最后指定的 free_list[start_migratetype] 链表中,而后在指定的 free_list[start_migratetype] 链表中执行减半决裂。

6.2.3 fallback 外围逻辑实现

本大节咱们来看下内核定义的 fallback 规定具体的流程实现,fallback 规定定义如下,笔者在之前的章节中曾经屡次提到过了,这里不在反复解释,咱们重点关注它的 fallback 流程实现。

static int fallbacks[MIGRATE_TYPES][3] = {[MIGRATE_UNMOVABLE]   = {MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES},
    [MIGRATE_MOVABLE]     = {MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES},
    [MIGRATE_RECLAIMABLE] = {MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES},
};

find_suitable_fallback 函数中封装了页面迁徙类型整个的 fallback 过程:

  1. fallback 规定定义在 fallbacksMIGRATE_TYPES 二维数组中,第一维示意要进行 fallback 的页面迁徙类型 migratetype。第二维 migratetype 迁徙类型能够 fallback 到哪些迁徙类型中,这些能够 fallback 的页面迁徙类型依照优先级排列。
  2. 该函数的外围逻辑是在 for (i = 0;; i++) 循环中依照 fallbacksmigratetype 数组定义的 fallback 优先级,顺次在 free_area[order] 中对应的 free_list[fallback] 列表中查找是否有闲暇的内存块。
  1. 如果以后 free_list[fallback] 列表中没有闲暇内存块,则持续在 for 循环中降级到下一个 fallback 页面迁徙类型中去查找,也就是 for 循环中的 fallbacksmigratetype。直到找到闲暇内存块为止,否则返回 -1。
int find_suitable_fallback(struct free_area *area, unsigned int order,
            int migratetype, bool only_stealable, bool *can_steal)
{
    int i;
    // 最终选取的 fallback 页面迁徙类型
    int fallback_mt;
    // 以后 free_area[order] 中以无闲暇页面,则返回失败
    if (area->nr_free == 0)
        return -1;

    *can_steal = false;
    // 依照 fallback 优先级,循环在 free_list[fallback] 中查问是否有闲暇内存块
    for (i = 0;; i++) {
        // 依照优先级获取 fallback 页面迁徙类型
        fallback_mt = fallbacks[migratetype][i];
        if (fallback_mt == MIGRATE_TYPES)
            break;
        // 如果以后 free_list[fallback]  为空则持续循环降级查找
        if (free_area_empty(area, fallback_mt))
            continue;
        // 判断是否能够从 free_list[fallback] 窃取页面到指定 free_list[migratetype] 中
        if (can_steal_fallback(order, migratetype))
            *can_steal = true;

        if (!only_stealable)
            return fallback_mt;

        if (*can_steal)
            return fallback_mt;
    }

    return -1;
}
// 这里窃取页面的目标是从 fallback 类型的 freelist 中拿到一个高阶的大内存块
// 之所以要窃取尽可能大的内存块是为了防止引入内存碎片
// 但 MIGRATE_MOVABLE 类型的页面自身就能够防止永恒内存碎片
// 所以 fallback MIGRATE_MOVABLE 类型的页面时,会跳转到 find_smallest 分支只须要抉择一个适合的 fallback 内存块即可
static bool can_steal_fallback(unsigned int order, int start_mt)
{if (order >= pageblock_order)
        return true;

    if (order >= pageblock_order / 2 ||
        start_mt == MIGRATE_RECLAIMABLE ||
        start_mt == MIGRATE_UNMOVABLE ||
        page_group_by_mobility_disabled)
        return true;
    // 跳转到 find_smallest 分支抉择一个适合的 fallback 内存块
    return false;
}

can_steal_fallback 函数中定义了是否能够从 free_list[fallback] 窃取页面到指定 free_list[migratetype] 中,逻辑如下:

  1. 如果咱们指定的内存调配阶 order 大于等于 pageblock_order,则返回 true。pageblock_order 示意零碎中反对的巨型页对应的调配阶,默认为搭档零碎中的最大调配阶减一,咱们能够通过 cat /proc/pagetypeinfo 命令查看。
  1. 如果咱们指定的页面迁徙类型为 MIGRATE_RECLAIMABLE 或者 MIGRATE_UNMOVABLE,则不论咱们要申请的页面尺寸有多大,内核都会容许窃取页面 can_steal = true,因为它们最终会 fallback 到 MIGRATE_MOVABLE 可挪动页面类型中,这样造成内存碎片的状况会少一些。
  2. 当内核全局变量 page_group_by_mobility_disabled 设置为 1 时,则所有物理内存页面都是不可挪动的,这时内核也容许窃取页面。

在零碎初始化期间,所有页都被标记为 MIGRATE_MOVABLE 可挪动的页面类型,其余的页面迁徙类型都是起初通过 __rmqueue_fallback 窃取 产生的。而是否可能窃取 fallback 迁徙类型列表中的页面,就是本大节介绍的内容。

7. 内存开释源码实现

在《深刻了解 Linux 物理内存调配全链路实现》中的“1. 内核物理内存调配接口”大节中咱们介绍了内核调配物理内存的相干接口:

struct page *alloc_pages(gfp_t gfp, unsigned int order)
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
unsigned long get_zeroed_page(gfp_t gfp_mask)
unsigned long __get_dma_pages(gfp_t gfp_mask, unsigned int order)

内核开释物理内存的相干接口,这也是本大节的重点:

void __free_pages(struct page *page, unsigned int order);
void free_pages(unsigned long addr, unsigned int order);
  • __free_pages:同 alloc_pages 函数对应,用于开释 2 的 order 次幂个内存页,开释的物理内存区域起始地址由该区域中的第一个 page 实例指针示意,也就是参数里的 struct page *page 指针。
void __free_pages(struct page *page, unsigned int order)
{if (put_page_testzero(page))
        free_the_page(page, order);
}
  • free_pages:同 __get_free_pages 函数对应,与 __free_pages 函数的区别是在开释物理内存时,应用了虚拟内存地址而不是 page 指针。
void free_pages(unsigned long addr, unsigned int order)
{if (addr != 0) {
        // 校验虚拟内存地址 addr 的有效性
        VM_BUG_ON(!virt_addr_valid((void *)addr));
        // 将虚拟内存地址 addr 转换为 page,最终还是调用 __free_pages
        __free_pages(virt_to_page((void *)addr), order);
    }
}

在咱们开释内存时须要十分审慎小心,只能开释属于你本人的页,传递了谬误的 struct page 指针或者谬误的虚拟内存地址,或者传递错了 order 值都可能会导致系统的解体。在内核空间中,内核是齐全信赖本人的,这点和用户空间不同。

另外内核也提供了 __free_page 和 free_page 两个宏,专门用于开释单个物理内存页。

#define __free_page(page) __free_pages((page), 0)
#define free_page(addr) free_pages((addr), 0)

咱们能够看出无论是内核定义的这些用于开释内存的宏或是辅助函数,它们最终会调用 __free_pages,这里正是开释内存的外围所在。

static inline void free_the_page(struct page *page, unsigned int order)
{if (order == 0)     
        // 如果开释一页的话,则间接开释到 CPU 高速缓存列表 pcplist 中
        free_unref_page(page);
    else
        // 如果开释多页的话,则进入搭档零碎回收这部分内存
        __free_pages_ok(page, order);
}

从这里咱们看到搭档零碎回收内存的流程和搭档零碎分配内存的流程是一样的,在最开始首先都会查看本次开释或者调配的是否只是一个物理内存页(order = 0),如果是则间接开释到 CPU 高速缓存列表 pcplist 中。如果不是则将内存开释回搭档零碎中。

struct zone {struct per_cpu_pages    __percpu *per_cpu_pageset;}

struct per_cpu_pages {
    int count;      /* pcplist 里的页面总数 */
    int high;       /* pcplist 里的高水位线,count 超过 high 时,内核会开释 batch 个页面到搭档零碎中 */
    int batch;      /* pcplist 里的页面来自于搭档零碎,batch 定义了每次从搭档零碎获取或者偿还多少个页面 */
    
    // CPU 高速缓存列表 pcplist,每个迁徙类型对应一个 pcplist
    struct list_head lists[NR_PCP_LISTS];
};

7.1 开释内存至 CPU 高速缓存列表 pcplist 中

/*
 * Free a 0-order page
 */
void free_unref_page(struct page *page)
{
    unsigned long flags;
    // 获取要开释的物理内存页对应的物理页号 pfn
    unsigned long pfn = page_to_pfn(page);
    // 敞开中断
    local_irq_save(flags);
    // 开释物理内存页至 pcplist 中
    free_unref_page_commit(page, pfn);
    // 开启中断
    local_irq_restore(flags);
}

首先内核会通过 page_to_pfn 函数获取要开释内存页对应的物理页号,而物理页号 pfn 的计算逻辑会依据内存模型的不同而不同,对于 page_to_pfn 在不同内存模型下的计算逻辑,大家能够回看下笔者之前文章《深刻了解 Linux 物理内存治理》中的“2. 从 CPU 角度看物理内存模型”大节。

最初通过 free_unref_page_commit 函数将内存页开释至 CPU 高速缓存列表 pcplist 中,这里大家须要留神的是在开释的过程中是不会响应中断的。

static void free_unref_page_commit(struct page *page, unsigned long pfn)
{
    // 获取内存页所在物理内存区域 zone
    struct zone *zone = page_zone(page);
    // 运行以后过程的 CPU 高速缓存列表 pcplist
    struct per_cpu_pages *pcp;

    // 页面的迁徙类型
    int migratetype;
    migratetype = get_pcppage_migratetype(page);
    
    // 内核这里只会将 UNMOVABLE,MOVABLE,RECLAIMABLE 这三种页面迁徙类型放入 pcplist 中,其余的迁徙类型均开释回搭档零碎
    if (migratetype >= MIGRATE_PCPTYPES) {if (unlikely(is_migrate_isolate(migratetype))) {
            // 开释回搭档零碎
            free_one_page(zone, page, pfn, 0, migratetype);
            return;
        }
        // 内核这里会将 HIGHATOMIC 类型页面当做 MIGRATE_MOVABLE 类型解决
        migratetype = MIGRATE_MOVABLE;
    }
    // 获取运行以后过程的 CPU 高速缓存列表 pcplist
    pcp = &this_cpu_ptr(zone->pageset)->pcp;
    // 将要开释的物理内存页增加到 pcplist 中
    list_add(&page->lru, &pcp->lists[migratetype]);
    // pcplist 页面计数加一
    pcp->count++;
    // 如果 pcp 中的页面总数超过了 high 水位线,则将 pcp 中的 batch 个页面开释回搭档零碎中
    if (pcp->count >= pcp->high) {unsigned long batch = READ_ONCE(pcp->batch);
        // 开释 batch 个页面回搭档零碎中
        free_pcppages_bulk(zone, batch, pcp);
    }
}

这里笔者须要强调的是,内核只会将 UNMOVABLE,MOVABLE,RECLAIMABLE 这三种页面迁徙类型放入 CPU 高速缓存列表 pcplist 中,其余的迁徙类型均需开释回搭档零碎。

enum migratetype {
    MIGRATE_UNMOVABLE, // 不可挪动
    MIGRATE_MOVABLE,   // 可挪动
    MIGRATE_RECLAIMABLE, // 可回收
    MIGRATE_PCPTYPES,   // 属于 CPU 高速缓存中的类型,PCP 是 per_cpu_pageset 的缩写
    MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, // 紧急内存
#ifdef CONFIG_CMA
    MIGRATE_CMA, // 预留的间断内存 CMA
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    MIGRATE_ISOLATE,    /* can't allocate from here */
#endif
    MIGRATE_TYPES // 不代表任何区域,只是单纯的标识迁徙类型这个枚举
};

对于页面迁徙类型的介绍,可回看本文 “1. 搭档零碎的外围数据结构 ” 大节的内容。

通过 this_cpu_ptr 获取运行以后过程的 CPU 高速缓存列表 pcplist,而后将要开释的物理内存页增加到对应迁徙类型的 pcp->lists[migratetype]。

在 CPU 高速缓存列表 per_cpu_pages 中,每个迁徙类型对应一个 pcplist。

如果以后 pcplist 中的页面数量 count 超过了规定的水位线 high 的值,阐明当初 pcplist 中的页面太多了,须要从 pcplist 中开释 batch 个物理页面到搭档零碎中。这个过程称之为 惰性合并

依据本文 “4. 搭档零碎的内存回收原理 ” 大节介绍的内容,咱们晓得,单内存页间接开释回搭档零碎会产生很多合并的动作,这里的惰性合并策略阻止了大量的有效合并操作

7.2 搭档零碎回收内存源码实现

当咱们要开释的内存页超过一页(order > 0)时,内核会将这些内存页回收至搭档零碎中,开释内存时搭档零碎的入口函数为 __free_pages_ok:

static void __free_pages_ok(struct page *page, unsigned int order)
{
    unsigned long flags;
    int migratetype;
    // 获取开释内存页对应的物理页号 pfn
    unsigned long pfn = page_to_pfn(page);
    // 在将内存页回收至搭档零碎之前,须要将内存页 page 相干的无用属性清理一下
    if (!free_pages_prepare(page, order, true))
        return;
    // 获取页面迁徙类型,后续会将内存页开释至搭档零碎中的 free_list[migratetype] 中
    migratetype = get_pfnblock_migratetype(page, pfn);
    // 关中断
    local_irq_save(flags);
    // 进入搭档零碎,开释内存
    free_one_page(page_zone(page), page, pfn, order, migratetype);
    // 开中断
    local_irq_restore(flags);
}

__free_pages_ok 函数的逻辑比拟容易了解,外围就是在将内存页回收至搭档零碎之前,须要将这些内存页的 page 构造清理一下,将无用的属性至空,将清理之后洁净的 page 构造回收至搭档零碎中。这里大家须要留神的是在搭档零碎回收内存的时候也是不响应中断的。

static void free_one_page(struct zone *zone,
                struct page *page, unsigned long pfn,
                unsigned int order,
                int migratetype)
{
    // 加锁
    spin_lock(&zone->lock);
    // 正式进入搭档零碎回收内存,《4. 搭档零碎的内存回收原理》大节介绍的逻辑全副封装在这里
    __free_one_page(page, pfn, zone, order, migratetype);
    // 开释锁
    spin_unlock(&zone->lock);
}

之前咱们在 “4. 搭档零碎的内存回收原理 ” 大节中介绍的搭档零碎内存回收的全副逻辑就封装在 __free_one_page 函数中,笔者这里倡议大家在看上面相干源码实现的内容之前再去回顾下 5.3 大节的内容。

上面咱们还是以 5.3 大节中所举的具体例子来分析内核如何将内存开释回搭档零碎中的残缺实现过程。

在开始之前,笔者还是先把以后搭档零碎中闲暇内存页的实在物理视图给大家贴出来不便大家比照,前面在查找须要合并的搭档的时候须要拿这张图来做比照能力清晰的了解:

以下是零碎中闲暇内存页在以后搭档零碎中的组织视图,当初咱们须要将 page10 开释回搭档零碎中:

通过“4. 搭档零碎的内存回收原理”大节的内容介绍咱们晓得,在将内存块开释回搭档零碎时,内核须要从内存块的以后阶(本例中 order = 0)开始在搭档零碎 free_area[order] 中查找可能合并的搭档。

搭档的定义笔者曾经在“2. 到底什么是搭档”大节中具体为大家介绍过了,搭档的外围就是两个尺寸大小雷同并且在物理上间断的两个闲暇内存块,内存块能够由一个物理内存页组成的也能够是由多个物理内存页组成的。

如果在以后阶 free_area[order] 中找到了搭档,则将开释的内存块和它的搭档内存块两两合并成一个新的内存块,随后持续到高阶中去查找新内存块的搭档,直到没有搭档能够合并为止。

/*
 * Freeing function for a buddy system allocator.
 */
static inline void __free_one_page(struct page *page,
        unsigned long pfn,
        struct zone *zone, unsigned int order,
        int migratetype)
{
    // 开释内存块与其搭档内存块合并之后新内存块的 pfn
    unsigned long combined_pfn;
    // 搭档内存块的 pfn
    unsigned long uninitialized_var(buddy_pfn);
    // 搭档内存块的首页 page 指针
    struct page *buddy;
    // 搭档零碎中的最大调配阶
    unsigned int max_order;
    
continue_merging:
    // 从开释内存块的以后调配阶开始始终向高阶合并内存块,直到不能合并为止
    // 在本例中以后调配阶 order = 0,咱们要开释 page10 
    while (order < max_order - 1) {// 在 free_area[order] 中查找搭档内存块的 pfn
        // 上图步骤一中搭档的 pfn 为 11
        // 上图步骤二中搭档的 pfn 为 8
        // 上图步骤三中搭档的 pfn 为 12
        buddy_pfn = __find_buddy_pfn(pfn, order);
        // 依据偏移 buddy_pfn - pfn 计算搭档内存块中的首页 page 地址
        // 步骤一搭档首页为 page11,步骤二搭档首页为 page8,步骤三搭档首页为 page12 
        buddy = page + (buddy_pfn - pfn);
        // 查看搭档 pfn 的有效性
        if (!pfn_valid_within(buddy_pfn))
            // 有效进行合并
            goto done_merging;
        // 依照后面介绍的搭档定义查看是否为搭档
        if (!page_is_buddy(page, buddy, order))
            // 不是搭档进行合并
            goto done_merging;
        // 将搭档内存块从以后 free_area[order] 列表中摘下,比照步骤一到步骤四
        del_page_from_free_area(buddy, &zone->free_area[order]);
        // 合并后新内存块首页 page 的 pfn
        combined_pfn = buddy_pfn & pfn;
        // 合并后新内存块首页 page 指针
        page = page + (combined_pfn - pfn);
        // 以合并后的新内存块为根底持续向高阶 free_area 合并
        pfn = combined_pfn;
        // 持续向高阶 free_area 合并,直到不能合并为止
        order++;
    }
    
done_merging:
    // 示意在以后搭档零碎 free_area[order] 中没有找到搭档内存块,进行合并
    // 设置内存块的调配阶 order,存储在第一个 page 构造中的 private 属性中
    set_page_order(page, order);
    // 将最终合并的内存块插入到搭档零碎对应的 free_are[order] 中,上图中步骤五
    add_to_free_area(page, &zone->free_area[order], migratetype);

}

依据上图展现的在内存开释过程中被开释内存块从以后阶 free_area[order] 开始查找其搭档并顺次向高阶 free_area 合并的过程以及联合笔者源码中提供的具体正文,整个内存开释的过程还是不难理解的。

这里笔者想重点来讲的是,内核如何在 free_area 链表中查找搭档内存块,以及如何判断两个内存块是否为伙伴关系。上面咱们来一起看下这部分内容:

7.3 如何查找搭档

static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{return page_pfn ^ (1 << order);
}

内核会通过 __find_buddy_pfn 函数依据以后开释内存块的 pfn,以及以后开释内存块的调配阶 order 来确定其搭档内存块的 pfn。

首先通过 1 << order 左移操作确定要查找搭档内存块的调配阶,因为伙伴关系最重要的一点就是它们必须是大小相等的两个内存块。而后奇妙地通过与要开释内存块的 pfn 进行异或操作就失去了搭档内存块的 pfn。

7.4 如何判断两个内存块是否是搭档

另外一个重要的辅助函数就是 page_is_buddy,内核通过该函数来判断给定两个内存块是否为伙伴关系。笔者在 “2. 到底什么是搭档 ” 大节中明确的给出了搭档的定义,page_is_buddy 就是相干的内核实现:

  1. 搭档零碎所治理的内存页必须是可用的,不能处于内存空洞中,通过 page_is_guard 函数判断。
  2. 搭档必须是闲暇的内存块,这些内存块必须存在于搭档零碎中,组成内存块的内存页 page 构造中的 flag 标记设置了 PG_buddy 标记。通过 PageBuddy 判断这些内存页是否在搭档零碎中。
  3. 两个互为搭档的内存块必须领有雷同的调配阶 order,也就是它们之间的大小尺寸必须统一。通过 page_order(buddy) == order 判断
  4. 互为伙伴关系的内存块必须处于雷同的物理内存区域 zone 中。通过 page_zone_id(page) == page_zone_id(buddy) 判断。

同时满足上述四点的两个内存块即为伙伴关系,上面是内核中对于判断是否为伙伴关系的源码实现:

static inline int page_is_buddy(struct page *page, struct page *buddy,
                            unsigned int order)
{if (page_is_guard(buddy) && page_order(buddy) == order) {if (page_zone_id(page) != page_zone_id(buddy))
            return 0;

        return 1;
    }

    if (PageBuddy(buddy) && page_order(buddy) == order) {if (page_zone_id(page) != page_zone_id(buddy))
            return 0;

        return 1;
    }
    return 0;
}

总结

在本文的结尾,笔者首先为大家介绍了搭档零碎的外围数据结构,目标是在介绍外围原理之前,先为大家构建起搭档零碎的整个骨架。从整体上先认识一下搭档零碎的全局样貌。

而后又为大家论述了搭档零碎中的这个搭档到底是什么概念,以及如何通过 __find_buddy_pfn 来查找内存块的搭档。如果通过 page_is_buddy 来判断两个内存块是否为伙伴关系。

在咱们明确了搭档零碎的这些基本概念以及全局框架结构之后,笔者具体分析了搭档零碎的内存调配原理及其实现,其中重点着墨了从高阶 freelist 链表到低阶 freelist 链表的减半决裂过程实现,以及内存调配失败之后,搭档零碎的 fallback 过程实现。

最初又具体分析了搭档零碎内存回收的原理以及实现,其中重点着墨了从低阶 freelist 到高阶 freelist 的合并过程。

好了,到这里对于搭档零碎的全部内容就完结了,感激大家的收看,咱们下篇文章见~~~

正文完
 0