当我们申请分配页的时候，页分配器首先尝试使用低水线分配页。如果使用低水线分配失败，说明内存轻微不足，页分配器将会唤醒内存节点的页回收内核线程，异步回收页，然后尝试使用最低水线分配页。如果使用最低水线分配失败，说明内存严重不足，页分配器会直接回收。

        针对不同的物理页，采用不同的回收策略：交换支持的页和存储设备支持的文件页。

        那我们根据什么的原则选择回收物理页呢？
        Linux 内核使用 LRU（Least Recently Used，最近最少使用）算法选择最近最少使用的物理页。

        回收物理页的时候，如果物理页被映射到进程的虚拟地址空间，那么需要从页表中删除虚拟页到物理页的映射。如何知道物理页被映射到哪些虚拟页？

        需要通过反向映射的数据结构，虚拟页到物理页时正向映射，物理页到虚拟页时反向映射。

一、数据结构

1.LRU（最近最少使用）链表

        页回收算法使用 LRU 算法选择回收的页。每个内存节点的 pglist_data 实例就有一个成员 lruvec，称为 LRU 向量，LRU 向量包含 5 条 LRU 双向链表，内核根据页面类型（匿名和文件）与活跃性（活跃与不活跃），分成5中类型的LRU链表。        

        不活动匿名页 LRU 链表，用来链接不活动的匿名页，即最近访问频率低的匿名页；
        活动匿名页 LRU 链表，用来链接活动的匿名页，即最近访问频率高的匿名页；
        不活动文件页 LRU 链表，用来链接不活动的文件页，即最近访问频率低的文件页；
        活动文件页 LRU 链表，用来链接活动的文件页，即最近访问频率高的文件页；
        不可回收 LRU 链表，用来链接使用 mlock 锁定在内存中、不允许回收的物理页。

struct lruvec结构定义如下：

在 LRU 链表中，物理页的页描述符特征：
        页描述符设置 PG_lru 标志位，表示物理页在 LRU 链表中；
        页描述符通过成员 lru 加入 LRU 链表；
        如果是交换支持的物理页，页描述符会设置 PG_swapbacked 标志位；
        如果是活动的物理页，页描述符会设置 PG_active 标志位；
        如果是不可回收的物理页，页描述符会设置 PG_unevictable 标志位。

        每条 LRU 链表中的物理页按访问时间从大到小排序，链表首部的物理页的访问时间离当前最近，物理页从 LRU 链表首部加入，页回收算法从活动 LRU 链表的尾部取物理页回收，从活动 LRU 链表的尾部取物理页并移动到不活动的 LRU 链表中。

如何确定页的活动程序？
        如果是页表映射的匿名页或文件页，根据页表项中的访问标志位确定页的活动程度。
        如果是没有页表映射的文件页，进程通过系统调用read或write访问文件，文件系统在文件的页缓存中查找文件页，为文件页的页描述符设置访问标志位就可以。

举例说明

• 页表映射的匿名页场景：
  某进程通过malloc分配一块内存（匿名页），页表映射该匿名页。当 CPU 访问该内存地址时，硬件会自动将页表项中的访问标志位（如A标志）置位，系统通过检测该标志位的状态，判断该匿名页的活动程度（近期是否被访问过）。

• 无页表映射的文件页场景：
  进程调用read系统调用读取文件内容，文件系统在页缓存中查找对应的文件页。若找到，会为该文件页的页描述符设置访问标志位；若未找到，先加载文件数据到页缓存再设置标志位。后续系统根据该标志位，判断文件页的活动程度，决定是否参与 LRU 回收等操作。

 以下是各数据结构的关系：

2.反向映射

        回收页表映射的匿名页或文件页的时候，需要从页表中删除映射，内核需要知道物理页被映射到哪些进程的虚拟地址空间，需要实现物理页到虚拟页的反向映射。

1.页描述符当中的反向映射重要成员如下：

struct page {  
    unsigned long flags;  
    struct {  
        struct list_head lru;  
        struct address_space *mapping;  
        pgoff_t index;  
    };  
};  

• flags：
  用于记录页面的原子标志，描述页面的各种状态（如是否为脏页、是否被锁定、是否可回收等）。这些标志可能被异步更新，内核通过检测这些标志来执行页面相关操作（如页面回收、写回磁盘等）。

• lru：
  类型为 struct list_head，是页面加入 LRU（最近最少使用）链表的节点。内核通过 LRU 链表管理内存页面，区分活跃页面（常被访问）和非活跃页面（可回收），用于内存回收策略，例如将非活跃页面换出到磁盘。

• mapping：
  指向 struct address_space（或通过位操作隐式指向 struct anon_vma），用于管理页面的映射关系：（见讲解【A】）

  • 若为 文件映射页，mapping 指向文件对应的 address_space，关联文件的页缓存；
  • 若为 匿名页（如堆、栈内存），通过指针低位标志转换，实际关联 anon_vma，用于反向映射管理（追踪哪些虚拟内存区域映射了该物理页）。

• index：
  类型为 pgoff_t，表示页面在映射中的偏移（单位为页）：

  • 对 文件映射页，index 是页面数据在文件内的页偏移；
  • 对 匿名页，index 是该物理页对应的虚拟页在虚拟内存区域（VMA）中的页偏移，用于定位虚拟内存与物理页的映射关系。

2.anon_vma重要成员如下：

        struct anon_vma 是 RMAP 机制中用于管理匿名内存映射区域的关键数据结构，在连接物理页面的 page 数据结构和虚拟内存区域的 vm_area_struct（VMA）中扮演着核心角色。当进程创建匿名内存映射（比如通过 malloc 分配内存，在缺页异常时创建的匿名页面）时，anon_vma 就开始发挥作用。

struct anon_vma {
    struct anon_vma *root;         /* Root of this anon_vma tree */
    struct rw_semaphore rwsem;     /* W: modification, R: walking the list */
    atomic_t refcount;             /* 引用计数，记录当前有多少个VMA引用了该anon_vma */
    unsigned degree;               /* Count of child anon_vmas and VMAs which points to this anon_vma */
    struct anon_vma *parent;       /* Parent of this anon_vma */
    struct rb_root_cached rb_root; /* Interval tree of private "related" vmas */
};

从定义来看，struct anon_vma 包含多个重要字段：

        其中，refcount 字段用于引用计数，它记录着当前有多少个 VMA 引用了该 anon_vma。当一个新的 VMA 与该 anon_vma 建立关联时，refcount 会增加；反之，当 VMA 与 anon_vma 解除关联时，refcount 减少。当 refcount 变为 0 时，说明没有 VMA 再引用这个 anon_vma，此时就可以对 anon_vma 进行回收。

rb_root 字段是一个红黑树的根节点，通过这个红黑树，anon_vma 可以高效地管理和查找与它相关的 VMA。在实际场景中，当系统需要查找所有引用某个匿名页面的 VMA 时，就可以通过 page 结构中的 mapping 指针找到对应的 anon_vma，然后遍历 anon_vma 的红黑树，快速获取所有相关的 VMA，大大提高查找效率。

3.anon_vma_chain

        struct anon_vma_chain 是连接 vm_area_struct（VMA） 和 anon_vma 的桥梁，在 RMAP 机制中起着不可或缺的枢纽作用。它主要用于维护 VMA 和 anon_vma 之间的关联关系，使得内核能够方便地从 VMA 找到对应的 anon_vma，反之亦然。

struct list_head anon_vma_chain;

        也就是说匿名映射的时候struct list_head anon_vma_chain;这个字段也同时跟红黑树一起把vm_area_struct加入到同一个anon_vma中，以下是不同的作用：

        在匿名映射中，红黑树和链表都用于将 vm_area_struct 加入到同一个 anon_vma 中，但它们的作用有所不同：

• 红黑树：anon_vma 中的红黑树（以 rb_root 为根）提供了按地址进行高效查找的能力。通过将 vm_area_struct 的 rb 节点插入到红黑树中，内核可以根据虚拟地址快速定位到对应的 vm_area_struct，时间复杂度为 O(logN)。
• 链表：anon_vma 维护的链表（通过 vm_area_struct 的 anon_vma_chain 连接）则方便进行顺序遍历。当需要对所有关联的 vm_area_struct 进行统一操作（如统计内存使用情况、合并相邻的 vm_area_struct 等）时，遍历链表比遍历红黑树更加高效。

4.struct vm_area_struct

        struct vm_area_struct 用于描述进程地址空间中的一段虚拟内存区域，是进程虚拟内存管理的重要数据结构，在反向映射 机制中也有着关键作用，它记录了虚拟内存区域的起始地址、结束地址、访问权限、所属的内存描述符等重要信息，与 反向映射 相关的字段主要有 anon_vma_chain 和 anon_vma。

struct vm_area_struct {
    unsigned long vm_start;         // 虚拟内存区域的起始地址
    unsigned long vm_end;           // 虚拟内存区域的结束地址
    struct mm_struct *vm_mm;       // 指向所属的内存描述符
    struct vm_area_struct *vm_next; // 指向下一个虚拟内存区域
    pgprot_t vm_page_prot;         // 页面保护标志
    unsigned long vm_flags;        // 虚拟内存区域的标志
    struct list_head anon_vma_chain; // 用于链接anon_vma_chain节点，通过这个链表可以找到与该VMA相关的所有anon_vma_chain
    struct anon_vma *anon_vma;     // 指向该VMA对应的anon_vma
    // 其他字段...
};

        在进程运行过程中，当发生缺页异常需要创建新的匿名页面时，内核会为该页面所在的 VMA 分配一个 anon_vma，并通过 anon_vma_chain 将 VMA 和 anon_vma 连接起来。例如，当一个进程调用 malloc 分配内存时，会在进程的地址空间中创建一个新的 VMA 来管理这块内存，同时为这个 VMA 关联一个 anon_vma，并通过 anon_vma_chain 建立两者之间的联系。这样，在后续的内存操作中，如页面回收、迁移等，就可以通过 VMA 的这些字段快速找到相关的 anon_vma 和其他关联信息，从而高效地完成内存管理任务。

        其中vm_area_struct结构体中有一个重要的字段shared,如下：

struct {
		struct rb_node rb;
		unsigned long rb_subtree_last;
	} shared;

        当这个区域属于文件映射的时候，那么shared字段中的rb节点就会被加入到文件页缓存address_space的i_mmap字段的红黑树中；如果是匿名映射，该字段就会加入到anon_vma的rb_root中。这确实是一个很优雅的操作！

 【A】

1. 对于匿名页

        当一个物理页是匿名页（例如堆、栈等没有文件支持的内存页）时：

        mapping字段指向一个struct anon_vma结构体。这个结构体用于管理匿名页的反向映射关系。

        通过struct anon_vma，内核可以找到所有映射到该物理页的虚拟内存区域（vm_area_struct）。这在处理页面换入 / 换出等操作时非常重要。

2. 对于有文件支持的页

        当一个物理页是有文件支持的页（例如从文件读取到内存中的页）时：

        mapping字段指向对应的struct address_space结构体。这个结构体用于表示文件在内存中的缓存。

        struct address_space包含了文件的页缓存（radix - tree或高版本的xarray等机制用于快速查找文件中的页），通过它可以找到物理页page结构体进而找到实际物理地址。同时也有i_mapp字段，是一颗红黑树管理所有映射该文件的vm_area_struct，详解见文件页的反向映射。

利用指针的位操作

        这种灵活的指向是通过利用指针在内存中的对齐特性来实现的。在许多体系结构中，指针是按字（通常是 4 字节或 8 字节）对齐的，这意味着指针的最低几位通常是 0。

        Linux 内核利用这一点，使用指针的最低几位来存储额外的信息（页映射标志），同时保持指针的主要部分仍然能够正确地指向目标结构。

页映射标志（PAGE_MAPPING_FLAGS）

        内核定义了一些页映射标志（存储在mapping指针的最低几位）来区分页面类型。

        例如，当这些标志表明页面是匿名页时，内核会将mapping指针解释为指向struct anon_vma，尽管其类型声明是struct address_space *。

        当标志表明页面是有文件支持的页时，mapping指针就正常地指向struct address_space。

具体代码讲解如下：

#include <stdio.h>
#include <stdlib.h>

// 模拟address_space结构体，这里简单定义一个结构体
typedef struct address_space {
    int file_page_data;  // 模拟文件页相关的数据
} AddressSpace;

// 模拟anon_vma结构体，同样简单定义一个结构体
typedef struct anon_vma {
    int anonymous_page_data;  // 模拟匿名页相关的数据
} AnonVma;

// 定义一个宏来获取指针中的标志位（这里简单取最低位作为标志位示例，实际内核更复杂）
#define GET_PAGE_MAPPING_FLAG(ptr) ((unsigned long)(ptr) & 0x1)
// 定义一个宏来设置指针的标志位（设置最低位）
#define SET_PAGE_MAPPING_FLAG(ptr, flag) \
    ((AddressSpace *)((unsigned long)(ptr) | (flag)))

// 模拟的页面结构体，包含一个类似mapping的指针
typedef struct Page {
    AddressSpace *mapping;
    int page_data;  // 页面的其他一些数据
} Page;

int main() {
    // 分配一个模拟的文件页相关的address_space结构体
    AddressSpace *file_page_mapping = (AddressSpace *)malloc(sizeof(AddressSpace));
    file_page_mapping->file_page_data = 100;

    // 分配一个模拟的匿名页相关的anon_vma结构体
    AnonVma *anon_page_mapping = (AnonVma *)malloc(sizeof(AnonVma));
    anon_page_mapping->anonymous_page_data = 200;

    // 创建一个模拟的页面，初始当作文件页
    Page page;
    page.mapping = file_page_mapping;
    page.page_data = 50;

    // 检查页面当前的标志位（应该是文件页标志，这里假设0为文件页标志）
    if (GET_PAGE_MAPPING_FLAG(page.mapping) == 0) {
        printf("当前页面是文件页，文件页数据: %d\n", page.mapping->file_page_data);
    }

    // 现在模拟将页面转换为匿名页，通过设置标志位
    page.mapping = SET_PAGE_MAPPING_FLAG(page.mapping, 1);
    // 再次检查标志位并根据情况处理
    if (GET_PAGE_MAPPING_FLAG(page.mapping) == 1) {
        // 这里进行类型转换，因为我们知道此时它代表的是指向anon_vma的指针
        AnonVma *anon_mapping = (AnonVma *)page.mapping;
        printf("当前页面是匿名页，匿名页数据: %d\n", anon_mapping->anonymous_page_data);
    }

    free(file_page_mapping);
    free(anon_page_mapping);
    return 0;
}

5.文件页的反向映射       

        文件页的反向映射是指在操作系统中，将虚拟内存地址与物理内存地址之间进行映射的过程。它允许操作系统跟踪每个虚拟页到物理页的对应关系。

        通常，操作系统使用页表来管理虚拟内存和物理内存之间的映射关系。每个进程都有自己独立的页表，通过查阅页表，操作系统可以将进程的虚拟地址转换为对应的物理地址。

        反向映射则是根据给定的物理内存地址，找到对应的虚拟内存地址。这样可以在需要时快速找到一个物理页面所属的进程和虚拟地址。

        实现反向映射通常需要一些数据结构支持，比如逆向页表或者其他类似结构。这样，在需要时就可以从给定的物理地址追溯到相应的虚拟地址。

        

        物理页的 mapping 会指向文件对应的 address_space，address_space 的i_mmap 保存了所有的vma。物理页的所有 vma，很容易找到，那不同vma的虚拟地址呢？

        物理页的index 表示物理页在文件内的offset（以page size为单位），vma的vm_pgoff 表示 vma 区域在文件中的偏移量。那么，在不同的vma的虚拟地址= page->index - vma->vm_pgoff + vma->vm_start 。

1. 关键变量含义

• page->index：物理页在文件内的偏移量，单位是页大小。例如文件大小 8KB（2 页），若 page->index = 1，代表该物理页对应文件内第 1 个页单位（4KB 处）。
• vma->vm_pgoff：vm_area_struct（VMA）区域在文件中的起始偏移量，同样以页大小为单位。比如 VMA 从文件第 2 页开始映射，vm_pgoff = 2。
• vma->vm_start：VMA 在进程虚拟地址空间中的起始地址。

2. 公式逻辑拆解

公式 虚拟地址 = page->index - vma->vm_pgoff + vma->vm_start 的本质是 “通过文件偏移关系，推导虚拟地址”：

 

• 计算相对页偏移：page->index - vma->vm_pgoff 表示物理页在当前 VMA 区域内的相对页偏移。例如：
  • 文件中某物理页偏移 page->index = 5，VMA 从文件偏移 vm_pgoff = 3 开始映射。
  • 则该页在 VMA 内的相对页偏移为 5 - 3 = 2（即 VMA 区域内第 2 个页单位）。
• 转换为虚拟地址：将相对页偏移转换为虚拟地址，需加上 VMA 的起始虚拟地址 vma->vm_start。假设页大小 4KB，vma->vm_start = 0x100000，则最终虚拟地址为：
  0x100000 + (2 * 4KB) = 0x102000。

二、发起页回收  

        申请分配页的时候，页分配器首先尝试使用低水位线分配页，如果使用低水位线分配失败，说明内存轻微不足，页分配器将会唤醒所有符合分配条件的内存节点的页回收线程，异步回收页，然后尝试使用最低水位线分配页。如果分配失败，说明内存严重不足，页分配器将会直接回收页。如果直接回收页失败，那么判断是否应该重新尝试回收页。

 具体源码分析如下：

1.直接回收

        针对备用区域列表中符合分配条件的每个内存区域，调用函数 shrink_node 来回收内存区域所属的内存节点中的页。回收页是以内存节点为单位执行的，函数 shrink_node 负责回收内存节点中的页。

        直接内存回收发生在慢速分配当中，首先唤醒所有 node 结点的 kswap 内核线程，然后才会调用 get_page_from_freelist () 尝试用 min 阀值从 zonelist 的 zone 中获取 连续页框，如果失败，对 zonelist 的 zone 进行异步压缩，异步压缩之后再次调用 get_page_from_freelist () 尝试用 min 阀值从 zonelist 的 zone 中获取连续页框，如是还是失败，就会进入到直接内存回收。

        在进行直接内存回收时，进程是有可能加入到 node 的 pgdat->pfmemalloc_wait 这个等待队列中，当 kswap 进行内存回收之后，如果 node 空闲内存达到平衡状态，那么就会唤醒 pgdat->pfmemalloc_wait 中的进程，其实也是加入到 pgdat->pfmemalloc_wait 这个等待队列的进程，自身就不会进行直接内存回收，而是让 kswapd 进行，之后 kswapd 会唤醒它们即可。

2.异步回收

         每个内存节点有一个页回收线程，如果内存节点的所有内存区域的空闲页数小于高水线，页回收线程就反复尝试回收页，调用函数 shrink_node 以回收内存节点中的页。

3.判断是否应该重试回收页  

        函数 should_reclaim_retry 判断是否应该重试回收页，如果直接回收 16 次全都失败，或者即使回收所有可回收的页，也还是无法满足水线，则应该放弃重试回收。

https://github.com/0voice