页框回收与交换
概念
内核在为进程服务的过程中会分配大量的页，但是这些页对应的虚拟地址在进程的生命周期里一直会被断断续续的访问，所以当内核同时为大量进程服务时，内存终究会耗尽。所有页框回收就是在内核未耗尽内存之前（因为回收与交换也会使用内存），将在使用过程标记未访问不频繁的部分内存换出到磁盘，释放所占用的内存补给系统，以维持内核的正常运转，待被换出的页对应的虚拟地址再次被访问时，内核又通过缺页系统将换出的页再次分配新的内存进行换入，这样周而复始形成良性的循环。
组成
每个zone中都有一套lru和buddy system
- 页：可回收的页
- 最近使用链表
lru：页描述符的标记和放置使用页的活动与不活动链表，使用过程中通过对页的访问，判断页是否是活动的，从而在活动与非活动链表中来回移动。
- 算法和守护线程：内存分配子系统中的页的直接回收路径与守护线程，他们负责计算应该将什么也标记为可回收状态、回收的数量是多少，然后触发或执行回收过程（扫描非活动链表开始回收）。
- 交换分区：交换分区页高速缓存与交换分区磁盘（或文件），他们负责暂存页引用和存储页的数据。
- 文件和设备：文件页高速缓存与文件（或设备），他们负责暂存页引用和回写脏页数据。
参与页框回收的页类型
| type |
comments |
reclaimed operation |
| 不可回收 |
1. 活动系统中的空闲页
2. 保留页（PG_reserved置位，比如内核镜像页）
3. 内核使用的动态分配的页
4. 进程内核态堆栈页
5. 临时锁定的页（PG_locked置位） |
不允许回收或无需回收 |
| 可交换页 |
1. 用户态进程匿名页
2. tmpfs文件系统的映射页（比如IPC共享内存页）
|
将页交换到交换分区 |
| 可同步页 |
1. 用户态进程映射页
2. 存有磁盘文件数据页且在文件页高速缓存中
3. 块设备缓冲区页
4. 磁盘高速缓存页（索引节点高速缓存） |
必要时，与磁盘同步这些页 |
| 可丢弃页 |
1. 内存高速缓存中未使用的页（比如slab分配器的未使用对象缓存）
2. 目录项高速缓存的未使用页 |
释放这些页，压缩缓存 |
页的转换图
- 每个zone中都有一套
lru和buddy system
- 每个CPU有一套
lru-cache
- 页的转换
+--------------------+
+---->>>-----+--->| inactive lru cache |--->-+
^ ^ +--------------------+ |
| | |
| | v
| +-----+------+ +--------+-----+
| | active lru | | inactive lru |
| +-----+------+ +--------------+
| ^ |
| | |
+---->>>-----+--<<<--+ |
| | |
+---+-------+ +-----+------------+ v
| lru cache | | active lru cache | v
+---+-------+ +-----+------------+ v
^ | |
| | |
| | re-active |
PAGE | +-----<<<<<-------------+
| |
+-----+-----+ start reclaimed | +-----------------+
| buddy sys | +--------<<<<<<------+------->| unevictable lru |
+-----+-----+ | +-----------------+
^ FILE sync v ANON swap
| +----<<----+----->>---+
| | |
| v v
| +-----+-----+ +-----+-----+
| | page cache| | swap cache|
| +-----+-----+ +-----+-----+
| | |
| | reused page |
+----<<<-----+---------<<<---------+
v v
+-----+-----+ +-----+-----+
| file | | swap |
+-----+-----+ +-----+-----+
| |
+---->>----+----<<----+
|
v
+----+----+
|disk dev|
+---------+
-
lru链表分类
| type |
comments |
LRU_INACTIVE_ANON |
非活动的匿名映射页的lru
|
LRU_INACTIVE_FILE |
非活动的文件映射页的lru
|
LRU_ACTIVE_ANON |
活动的匿名映射页的lru
|
LRU_ACTIVE_FILE |
活动的文件映射页的lru
|
LRU_UNEVICTABLE |
不可回收页的lru
|
-
lru的per-CPU缓存分类
页高速缓存
数据结构
页高速缓存核心数据结构是address_space对象，被嵌入在页所有者的索引节点对象中。每个页描述符中使用mapping（索引节点的address_space对象）和index（页大小的磁盘镜像偏移）字段关联到页高速缓存中。
- 基树
struct radix_tree_root address_space.page_tree是基树的根，由深度、节点概念构成。每个节点可以存储64个槽位，如果是叶子节点则存储内容为页描述符，否则为其他的子树节点的指针。假设有页号为0、4、131三页数据，那么在树中的映射为：
+-------+
| h = 2 |
+-------+
| rnode |
+---+---+
|
|
v
+------------------+
| count = 2 |
+------------------+
| 0 | | 2 |...| 63 |
+-+-----+----------+
| |
+-------+ +-------+
| |
v v
+------------------+ +------------------+
| count = 2 | | count = 1 |
+------------------+ +------------------+
| 0 | | 4 |...| 63 | | 0 | | 3 |...| 63 |
+-+-----+----------+ +-------+----------+
| | |
| +-------+ |
| | |
v v v
+-----+ +-----+ +-----+
|page | |page | |page |
+-----+ +-----+ +-----+
-
优先搜索树
-
反向匿名映射
-
操作方法接口
页高速缓存中的页通过const struct address_space_operations *a_ops操作对外部子系统提供操作，主要方法如下：
-
int (*writepage)(struct page *page, struct writeback_control *wbc) 写操作
-
int (*readpage)(struct file *, struct page *) 读操作
-
int (*write_begin)(struct file *, struct address_space *mapping, loff_t pos, unsigned len, unsigned flags, struct page **pagep, void **fsdata) 为写操作做准备
-
int (*write_end)(struct file *, struct address_space *mapping, loff_t pos, unsigned len, unsigned copied, struct page *page, void *fsdata) 完成写操作
内部操作API
| API |
page |
comments |
find_get_page() |
get_page() |
根据偏移查找一页，然后增加页的引用 |
find_get_pages() |
get_page() |
根据起始偏移和请求数量，查找一组连续的页，然后对每一页都增加引用 |
find_lock_page() |
1. get_page()
2. lock_page()
|
根据偏移查找一页，然后增加页的引用，并试图锁定改页（可能发生阻塞） |
add_to_page_cache_lru() |
1. get_page()
2. __SetPageLocked()
3. page.mapping = mapping
4. page.index = offset
5. lru_cache_add()
|
1. 从外部分配新页。
2. 锁定页，因为是新页内容无效，防止其他的路径进行访问
3. 插入到页高速缓存中，并初始化页的高速缓存相关字段
4. 新缓存的可回收的页，插入lru链表中 |
add_to_page_cache() |
/ |
与 add_to_page_cache_lru() 类似，除了不加入lru链表中 |
delete_from_page_cache() |
1. page.mapping = NULL
2. put_page()
|
1. 删除的页必须已锁定
2. 如果页还被页表映射，则要作出调整
3. 从页高速缓存中删除
4. 重置相关字段 |
read_cache_page() |
1. get_page()
2. alloc_page()
3. __SetPageLocked()
4. SetPageUptodate()
5. unlock_page()
6. lru_cache_add()
7. mark_page_accessed()
|
1. 从缓存中查找页
2. 如果没有找到，分配新页，载入数据，标记更新标志，添加到lru链表中
3. 如果找到，等待页的更新操作
4. 标记最近访问标志 |
页标记
如果我们想回写高速缓存中所有的脏页和正在被回写的页，那么依次遍历这个基树中所有的节点是非常耗时的，为了快速搜索脏页，基树中每个非叶子节点都包含一个标记，这样我们可以从顶层节点可以很清楚的知道哪些叶子节点包含脏页，然后跳过没有标记的子树节点，然后往下遍历。向页高速缓存插入页时，不会主动的标记，因为页的状态还是空的；而当从中删除一页时，会自动的清理路径上的各个标记。
-
数据结构
-
ulong radix_tree_node.tag[PAGECACHE_TAG_DIRTY][1] 标记脏页
-
ulong radix_tree_node.tag[PAGECACHE_TAG_WRITEBACK][1] 标记正在回写的页
-
ulong radix_tree_node.tag[PAGECACHE_TAG_TOWRITE][1] to_write ?
-
操作API
| API |
comments |
radix_tree_tag_set() |
设置指定偏移和类型的标记 |
radix_tree_tag_clear() |
清除指定偏移和类型的标记 |
radix_tree_tag_get() |
获取指定偏移和类型的标记 |
set_page_writeback() |
高级应用，当页标志不是回写状态，设置高速缓存中的页标记和页标志为回写，
且如果页标志不是脏页，则清除高速缓存的页标记的脏状态 |
反向匿名映射
概念
反向匿名映射用于通过页描述符快速定位所有映射该页的进程的页表，从解除页与页表的映射。已普通的私有mmap()来说，当在fork()调用dup_mmap()时，原来的vma结构被拷贝一份，且被链接到同一个动态分配的struct anon_vma，然后再增加关联页的引用，并设置到新进程的页表中；在内核无关的进程中试图回收这些共享的页时，就需要通过反向匿名映射找到所有的vma，从而找到所有的页表。
数据结构
匿名线性区是起止是4K对齐的，而页描述符的index存储的是页在vma的页数偏移（参考__page_set_anon_rmap()），通过vma_address()就可以算出页则对应的用户空间的虚拟地址，从而找到页表项，进行映射解除。
rb_root
+----------+
| anon_vma |
+-+---+--+-+
/ ^ \
rb_node / | \ rb_node
+--------------+-+ | +--+-------------+
+---| anon_vma_chain | | | anon_vma_chain |----+
| +--------+-------+ | +--------+-------+ |
| | | | |
| v | v |
| +--------+-------+ | +--------+-------+ |
| | vma_area_struct| ^ | vma_area_struct| |
| +--------+-------+ ^ +--------+-------+ |
| | ^ | |
| v ^ v |
| +--------+--+ | +---+-------+ |
| | mm_struct | | | mm_struct | |
| +--+--------+ | +--------+--+ |
| | | | |
| v | v |
| +--+--+ +-----+ | +-----+ +--+--+ |
| | pgd |--->| pte | | | pte |<---| pgd | |
| +-----+ +-----+ | +-----+ +-----+ |
| | | | |
| v | v |
| +----+--+ |
| | page | |
| +-------+ |
| index | | index |
| +-----+ +-----+ |
|<------------>| |<------------->|
v v v v
+----------+---+--+--+ +--+--+---+-----------+
|//| PAGE |//| |\\| PAGE |\\\\\\\\\\\|
vm_start +----------+------+--+ +--|------+-----------+ vm_start
匿名线性区 匿名线性区
操作API
| API |
struct page |
comment |
page_add_new_anon_rmap() |
|
首次将页添加到反向匿名映射数据结构中 |
page_lock_anon_vma_read() |
|
如果页被映射，则锁住页反向映射的struct anon_vma数据结构，然后返回这个数据结构的指针，关系到rcu问题 |
页框回收
概念
当在从伙伴系统中分配页时，如果分配请求不能得到满足，那么分配将进入慢速分配路径，唤醒交换守护线程（由kswapd_init()初始化），然后从活动的lru向非活动的lru补充可以回收的页，最后在交换分区中分配一个可用的交换标识（由类型和槽位组成），将页在页表中的页号替换为交换标识，并添加到交换页高速缓存中，再解除对应的映射引用，如果页被回写（当前路径直接回写或交换守护线程回写），则就可以释放内核引用（高速缓存或局部缓存），从而完成页的回收（返回到伙伴系统中），最后再次尝试分配请求的页数。
处理流程
- 慢速分配
+---------------+
| alloc_pages() |
+-------+-------+
|
v
+-------+-------+
| ... |
+-------+-------+
|
v
+-------------+------------+
| __alloc_pages_slowpath() |
+-------------+------------+
|
v
+---------------+----------------+
| |
v v
+---------+----------+ +-------+-------+
| wake_all_kswapds() | | ... |
+---------+----------+ +-------+-------+
| |
v v
+-------+-------+ +-------+-------+
| ... | |out_of_memory()|
+-------+-------+ +---------------+
|
v
+----------+-----------+
| try_to_free_pages () |
+----------+-----------+
|
v
| API |
comments |
alloc_pages() |
分配主入口函数 |
__alloc_pages_slowpath() |
当内核在遍历的所有zone后，发现仍然没有满足请求的页可用，就会进入该流程。
先尝试回收非活动的页，如果不行则杀死一个用户进程来回收页，这个是最后的手段。 |
wake_all_kswapds() |
唤醒交换守护线程，尝试从另一个路径回收页，并可以回写已交换的页 |
try_to_free_pages() |
主要是扫描活动lru，将不活动的页移入非活动lru，然后开尝试回收这些页。 |
out_of_memory() |
最后的手段，选择一个内存使用最多、静态优先级最低的进程，将其杀死，从而回收所占用的页。这时一个耗时的过程。 |
- 尝试回收非活动页
+------------------------+ +----------+
| try_to_free_pages() | | kswapd() |
+-----------+------------+ +-----+----+
| |
| v
| +----------------------+ +--------+--------+
| +----<<----| kswapd_shrink_node() |<-----| balance_pgdat() |
| | +----------------------+ +-----------------+
v v
+-------+--------+ +-------+-------+
| shrink_zones() |--------->| shrink_node() |---+
+-------+--------+ +---------------+ |
| |
v v
+------------+-------------+ +----------+----------+ +---------------+
| wakeup_flusher_threads() | | shrink_node_memcg() |------->| shrink_list() |
+------------+-------------+ +----------+----------+ +-------+-------+
| | |
v v v
+ +-------+-------+ +----------+-----------+
| shrink_slab() | | shrink_active_list() |
+---------------+ +----------+-----------+
|
v
+-----------------+ +----------+-----------+
| lru_add_drain() |<------|shrink_inactive_list()|
+--------+--------+ +----------------------+
|
v
+---------+----------+
| shrink_page_list() |
+---------+----------+
|
v
+------------+-------------+
| putback_inactive_pages() |
+------------+-------------+
|
v
+------------+--------------+
| free_hot_cold_page_list() |
+------------+--------------+
| API |
comments |
try_to_free_pages() |
构造回收控制参数，以一种优先级多次扫描各个zone，直到回收到足够的页。
优先级越低，说明回收的压力越大，越会采取一些特殊措施，比如尝试写磁盘，为了尽快从分配函数返回，本来这个工作应该守护线程来做的。 |
shrink_zones() |
开始遍历请求node上的按优先级排序的所有zone（可以包括其他node的zone），调用shrink_node()开始回收 |
shrink_node() |
调用shrink_node_memcg()和shrink_slab()开始尝试回收当前zone，
然后调用should_continue_reclaim()检查是否当前的zone需要继续尝试回收。 |
should_continue_reclaim() |
判断是否应该再次尝试，比如还有一定的满足某个阈值的非活动页，则可以再次尝试。 |
shrink_slab() |
扫描注册的其他可回收函数，尝试回收，注意此处并不是扫描kmem_cache中的slab，而是其他高速缓存，比如目录对象高速缓存 |
shrink_node_memcg() |
遍历当前zone上的所有可回收的活动lru
|
shrink_list() |
判断阈值是否扫描活动lru，然后扫描非活动lru开始扫描 |
shrink_active_list() |
扫描非活动页，然后补充到非活动的lru里 |
shrink_inactive_list() |
扫描非活动lru开始尝试回收，没有回收的再次移入活动lru里，并释放回收的页 |
lru_add_drain() |
将各个lru缓存的页刷新到对应的lru链表中 |
shrink_page_list() |
尝试回收，执行解除映射、尝试写出到磁盘等工作，返回可以不能立即回收的页 |
putback_inactive_pages() |
按条件将不能回收的页再次移动到适当的lru里 |
free_hot_cold_page_list() |
释放最后不能回到lru的页，比如尝试回收时正在被其他路径使用，在调用putback_inactive_pages()时又被put_page()遗弃的页 |
- 周期压缩
SLAB占用的页
在kmem_cache初始化之后，注册（见start_cpu_timer()函数）一个延迟工作队列，定时的调用cache_reap()函数进行slab空闲对象链表的回收。
+--------------+
| cache_reap() |
+--------------+
- 杀死进程回收占用页
如果交换分区已满或所有的slab都被压缩之后，还是没有可用的页，那么内核调用select_bad_process()尝试按以下规则选出一个拥有大量的页、静态优先级低、不拥有root权限、不直接访问硬件的进程，然后杀死这个进程，回收他占用的页。
+-----------------+
| out_of_memory() |
+-----------------+
交换子系统
概念
交换主要用于回收页框时，存储在磁盘中没有映像的页的内容，从而可以回收该页。过程如下：
当内核在物理内存紧张的时候，内核内存回收机制将用户进程的特定的部分物理页通过交换分区写入磁盘或文件（比如在alloc_pages()时触发交换机制），然后将该页在交换分区的标记写入原页表项代替页号，并将页表项的驻留内存属性清零，当再次访问该页对应的虚拟地址时，CPU发现页表项驻留内存属性没有设置（内核通过pte_present()为假进行判断），则发生交换缺页，内核分配新页给进程并通过页表项携带的交换标记从磁盘将数据读入新页，从而完成缺页异常，并且如果仅有当前进程使用该页，则从交换分区删除该页。由于被交换出的物理页，可能会在短期又会发生缺页，这极有可能是由于几个进程共享该页导致，所以为了不频繁的读写磁盘影响性能，所有在交换分区之上构建了交换页高速缓存，在交换的换入换出中都先操作缓存，然后再周期的将没有被任何人引用的页写入磁盘。
组成
- 交换页高速缓存
交换页高速缓存就是基树
- 交换分区
内核用一个静态数组存储所有交换分区的描述符swap_info_struct的指针，这些描述都有一个优先级，然后同等级的描述符被链接在优先级链表swap_avail_head的同一个节点之下。每个文件或设备都被初始化为4K大小的块（称之为页槽），并在描述符中有与之对应的引用计数（swap_info_strcut.swap_map[]）。内核调用sys_swapon()来初始化一个交换分区，初始化完成之后可用页槽计数为0、不可用的为SWAP_MAP_BAD。每个交换分区的第一个页槽都用于存放交换分区的元数据（使用mkswap系统调用初始化），所有为了辨别，则将0号页槽的引用计数初始化为SWAP_MAP_BAD。
swap_avail_head plist_node
+----+ +-----+ +-----+
| |------->| |----->| |
+----+ +--+--+ +-----+
|
|
swap_info[] v
+----+ +--+--+ swap_file* +----+----+----+----+----+----+----+
| |------->| |---------------->| | | | | | | |
+----+ +-----+ swap_map[] +----+----+----+----+----+----+----+
| | | |---------------->| | | | | | | |
+----+ +--+--+ +----+----+----+----+----+----+----+
| | | swap_info_struct*
+----+ |
| | v
+----+ +--+--+
| |------->| |
+----+ +-----+
| |
+-----+
swap_info_struct*
- 交换标识符
交换标识符标识在交换分区中页的位置，由交换描述符在swap_info[]数组中的位置（标识类型）偏移一定位数后，或上描述符中文件页槽位置（标识偏移）组成。
0 63
+------------+----------+
| 57 bit | 7 bit |
+------------+----------+
|<- offset ->|<- type ->|
| API |
comments |
swap_entry() |
合成交换标识符 |
swap_type() |
获取标识符的类型 |
swap_offset() |
获取标识符的偏移 |
- 换出页标识符
换出页标识符通过交换标识符转换而来，因为这个标识符要设置在页表中，所以不能简单的将type和offset组合了事，应该匹配页表项本身的一些标志位（和CPU架构相关）。X86架构如下：
0 63
+-------+-------------+-------+--------+
|1 bit | 8 bit | 5 bit | 50 bit |
+-------+-------------+-------+--------+
|present| other flags | type | offset |
| API |
comments |
pte_to_swp_entry() |
换出页标识符转换为交换标识符 |
swp_entry_to_pte() |
交换标识符转换为换出页标识符 |
交换分区的操作
| API |
comments |
get_swap_page() |
用于在所有可用的交换分区中获取一个空闲页槽，在增加对页槽的引用后，以交换标识符的形式返回给调用者。在扫描可用的槽位时，优先使用优先级高的（值越小优先级越高）交换分区，然后再以轮训的方式使用同优先级的交换分区，直到找到可用槽位或没有任何可用交换分区为止。 |
swap_free() |
释放交换标识符对应的页槽，当页槽因为为0时，调整所在交换分区的属性 |
交换流程
- 简介
交换子系统的核心入口函数为shrink_page_list()，它被页分配函数和交换守护线程调用。在扫描非活动链表后，内核将可能被回收的页从非活动lru链表中剥离到局部的一个链表中，然后扫描这个链表，尝试回收里面的页，然后将本次不能回收的页按照页的属性和状态再次的移动到各个lru链表中，使用这种方式可以有效的减少对lru链表的并发访问。在整个回收的过程中，必须对处理的页进行trylock_page()加锁，如果不能加锁，说明其他路径正在使用该页（大都是磁盘系统正在回写该页，因为正在回写的页会临时的放置在非活动的lru链表中），因此不能回收这样的页。
- 核心流程
流程图说明
- 双线表示主干逻辑
- YES和NO表示条件(或调用)成功或失败
- active 表示暂时不会能被回收且需要激活页，极有可能在尝试回收后加入到活动的lru链表中
- unevictable 表示这个页从此不能回收，加入到LRU_UNEVICTABLE类型的lru链表中
- keep old status 表示暂时不会能被回收且需要但不需要激活页，极有可能在尝试回收后加入到非活动的lru链表中
+--------------------+
| shrink_page_list() |
+---------++---------+
||
vv
+-------++------+ NO +--------+
| trylock_page()|--------->| active |
+-------++------+ +--------+
||
|| YES
vv
+--------++--------+ NO +-------------+
| page_evictable() |------->| unevictable |
+--------++--------+ +-------------+
||
|| YES
vv
+-------++------+ NO +-----------------+
| page_mapped() |--------->| keep old status |
+-------++------+ +-------+---------+
|| ^
|| YES |
vv |
+--------++-------+ YES |
| PageWriteback() |-------->>>------+
+--------++-------+ ^
|| |
|| |
vv | PAGEREF_KEEP
+--------++------+ NO +-------+-----------------+
| force reclaim? |---->>----| page_check_references() |
+--------++------+ +-----------+----------+--+
|| | |
||YES PAGEREF_RECLAIM v | PAGEREF_ACTIVATE
++------------<<<--------------+ |
|| |
vv |
+--------++--------+ +---------------+ v +--------+
| PageAnon() and |--->>---| add_to_swap() |-->>--+---->>| active |
| !PageSwapCache() | NO +-------+-------+ NO ^ +--------+
+------------------+ | |
|| | |
|| NO | |
++-------------------------+ +---------+
|| ^ SWAP_FAIL
vv |
+-------++------+ +------------+---+ SWAP_AGAIN +-----------------+
| page_mapped() |---->>----| try_to_unmap() |----+------->>--| keep old status |
+-------++------+ YES +------------+---+ ^ +-----------------+
|| | |
|| NO SWAP_SUCCESS v |
++------------------------------+ |
|| |
vv | PAGE_KEEP
+------++-----+ +--------------------+------+ +--------+
| PageDirty() |----->>---->| async to pageout() by blk |---->>----------| active |
+------++-----+ YES +--+-----+------------------+ PAGE_ACTIVATE +--------+
|| | |
|| NO | | +-------------------+
|| PAGE_CLEAR | | PAGE_SUCCESS | PageWriteback() | +-----------------+
++--------<<<----------+ +------>>>------| or PageDirty() |-->>--| keep old status |
|| | or !trylock_page()| NO +-----------------+
|| +---------+---------+
|| |
|| YES v
++--------<<<------------------------------<<<---------+
||
vv
+---------++---------+ YES +-----------------------+ NO +--------+
| page_has_private() |------->| try_to_release_page() |------->| active |
+---------++---------+ +-----------+-----------+ +--------+
|| |
|| NO |
|| YES |
++------------------<<<---------+
||
||
|| +----------------------------+
vv +---->| __delete_from_swap_cache() |----->+
+---------++---------+ | +----------------------------+ | NO +-----------------+
| __remove_mapping() |------->+ |------>| keep old status |
+---------++---------+ | +----------------------------+ | +-----------------+
|| +---->| __delete_from_page_cache() |----->+
|| YES +----------------------------+
||
||
+----------++---------------+
| free_hot_cold_page_list() |
+----------++---------------+
- 函数说明
| API |
struct page |
comments |
trylock_page() |
page->flags \= PG_locked |
不阻塞，试图锁定页 |
page_evictable() |
/ |
1. 检查页关联映射的地址空间address_space->flags 是否设置AS_UNEVICTABLE标志，或者页描述符page->flags是否设置PG_mlocked标志。
2. 因为在用户调用系统函数创建一个映射页时可以指定该虚拟地址空间或文件内容映射的页可以不被换出到磁盘。（参见mlock()系统调用） |
page_mapped() |
/ |
检查页描述符的page->_mapcount映射计数字段是否大于-1，从而判断是否被映射。（该计数器的初始值为-1） |
PageWriteback() |
/ |
检查页描述符的page->flags是否设置PG_writeback标志，从而判断页是否正在通过VFS文件系统正在排队回写数据，因为上次回收页时执行的pageout()是异步的，在为成功回写之前，页描述符一直停留在非活动链表中，这样不必浪费资源时刻关注这些成功回写的、可以释放的页 |
page_check_references() |
1. page->flags \= PG_referenced
2. page->flags \= PG_swapbacked
|
如果上层调用不是强迫回收当前状态是非活动的页，那么在明确回收之前，会调用此函数再次检测页是否最近又被访问过，从而在最近下个时刻避免不必要的缺页处理 |
PageAnon() |
/ |
检查页描述符page->mapping是否设置PAGE_MAPPING_ANON，从而判断是否是匿名映射 |
PageSwapCache() |
/ |
检查页描述符page->flags是否设置PG_swapcache，从而判断是否已经添加到交换高速缓存中（前提是页必须是匿名页），只有匿名页被添加到缓存中才能被换出 |
add_to_swap() |
1. page->flags \= PG_swapcache
2. page->_refcount += 1
|
将匿名映射页添加到交换高速缓存中。
1. 如果有多个交换分区，使用优先级高的交换分区，然后分配一个页槽并它的增加引用计数，然后将这个槽位和交换分区的位置组合成交换标识符。
2. 将交换标识符和页作为键值添加到交换分区对应的页高速缓存中（一棵基树）。
3. 如果所有的交换分区槽位不足，则可能失败。 |
try_to_unmap() |
1. page->_refcount -= 1
2. page->_mapcount -= 1
|
尝试解除映射，这里有一个关键条件：如果没有其他路径使用该页，那么page->_refcount = page->_mapcount + 2(因为页在lru链表和局部链表中，他们各有一个内核引用；且每个页的映射引用有一个内核引用)。
1. 如果是匿名页，则遍历反向匿名映射中的节点，尝试解除页在进程的页表中的映射，并将交换标识符设置到页表。
2. 如果是文件映射，则遍历地址空间中的优先级树中的节点，尝试解除每个文件描述符对齐的引用（猜的？）。 |
PageDirty() |
/ |
检查页描述符page->flags是否设置PG_dirty，从而判断是否为脏页（页的内容是否改变过）。
1. 作为匿名页，如果自从上次换入，页的内容都为改变过，且页还在交换分区中，则不必再写磁盘，直接尝试回收。
2. 作为文件页，与匿名页一样。 |
pageout() |
1. page->flags \= PG_writeback
2. page->flags \= PG_reclaim 3. page->_refcount += 1
|
使用页对应的地址空间（匿名页是交换分区抽象的VFS方法集合，文件页则是对应的文件系统的VFS方法集合）的方法分配一个块缓存排队写出请求到磁盘，然后将页写出，这个过程是异步的。
1. 在写出请求之前设置对应的页高速缓存的脏标记（只有脏页、非写出的页才需要请求写出）。
2. 请求之后设置页描述符的PG_writebace、PG_reclaim标志。
3. 在请求写出的方法中，如果请求成功，则标记页高速缓存的写出标记，同时清除脏标记。 |
page_has_private() |
page->_refcount -= 1 |
判断页在写磁盘队列中是否有元数据缓存（在这里仅文件映射有）。如果页完成写，那么存储在page->flags中的PG_private标记被清除。 |
try_to_release_page() |
/ |
尝试释放写页到磁盘时关联的元数据缓存 |
__remove_mapping() |
/ |
如果写磁盘异步的完成，在这里就被检查到，然后解除可回写到磁盘的页在相应的页高速缓存的引用 |
__delete_from_file_cache() |
/ |
直接从文件页高速缓存释放占用的节点 |
__delete_from_swap_cache() |
/ |
直接从交换页高速缓存释放占用的节点 |
free_hot_cold_page_list() |
/ |
在页被解除所有的引用后，使用该函数将其直接释放到伙伴系统中 |
换出与换入举例
先举例一种情景：当两个进程的匿名映射共享同一个物理页，并已准备将两个进程的匿名映射解除映射换出他们引用的物理页。假设开始时shrink_page_list()已完成add_to_swap()调用，在解除其中一个进程的映射后，这个进程立马又调用do_swap_page()进行换入操作。在这个过程中观察交换槽位引用、交换页高速缓存、页描述符、页表项的竞争时序情况：
| file |
comments |
mapcount |
页的映射计数 |
refcount |
页的引用计数，在不考虑其内核引用时，进程匿名页的mapcount == refcount
|
swapcount |
交换槽位的引用，如果进程的页被交换，那么该计数为进程数量，或再加一（如果还仍被高速缓存引用的话） |
- 初始化状态，有进程请求换出页（假设不是两个匿名页的宿主进程）操作相关结构，在调用
add_to_swap()后，调用try_to_unmap()之前。从换出进程的视角观察：
+-----+-----+-----+
| 1 | 2 | 3 | swap slot
+-----+--+--+-----+
|
+-----+--+--+-----+
| 1 | 2 | 3 | swap cache
+-----+--+--+-----+
|
+-------+
+-----+ |
| pte | v
+-----+------>+--+--+ +-----+
|page |<-----| lru |
+-----+------>+-----+ +-----+
| pte |
+-----+
1. mapcount = 2
2. refcount = 4 ，由于操作换出的页还被`lru`引用和高速缓存引用
3. swapcount = 1 ，暂时只被高速缓存引用
- 解除引用
try_to_unmap()后，在写页pageout()之前发生缺页do_swap_page() ，从各自的视角来看 ：
task swapping out | task' swapping in
|
+-----+-----+-----+ | +-----+-----+-----+
| 1 | 2 | 3 | swap slot | | 1 | 2 | 3 |
+-----+--+--+-----+ | +-----+--+--+-----+
| | |
+---------->+ | +---------->+
| | | | |
| +-----+--+--+-----+ | | +-----+--+--+-----+
| | 1 | 2 | 3 | swap cache | | | 1 | 2 | 3 |
| +-----+--+--+-----+ ============> | +-----+--+--+-----+
| | | | |
| +-------+ | | +-------+
| +-----+ | | | +-----+ |
+--| pte | v | +--| pte | v
| +-----+ +--+--+ +-----+ | +-----+ +--+--+
| |page |<-----| lru | | |page |
| +-----+ +-----+ +-----+ | +-----+------>+-----+
+--| pte'| | | val |
+-----+ | +-----+
|
1. mapcount = 0 | 1. mapcount = 0
2. refcount = 2 | 2. refcount = 3
3. swapcount = 3 | 3. swapcount = 3
解除引用之后，交换槽位计数增加到页表项对其的引用计数，而引用计数被清零。页的引用计数减少了映射计数，但如果没有其他路径引用这个页，那么一定是为2，因为仅高速缓存和lru对其有引用，这也是很多相关的函数中的表达式有加减2的判断。但是解除映射释放页表锁之后，pageout()之前；缺页do_swap_page()可以进入lookup_swap_cache()流程，并从高速缓存查找到页，并用局部变量(上图中用val表示)引用了页。但是由于换出shrink_page_list()持有这个页的锁，缺页下一步了的lock_page()会阻塞挂起（这也是页锁的重要作用），那么这个缺页进程的页表项还是引用页槽，而不是将页号设置到页表，然后解除对页槽的引用。
- 在执行
pageout()时（缺页进程正在被挂起），is_page_cache_freeable()检查页的引用计数时，发现了缺页进程的存在，所以写出不会发生，进而页在本次也不会被回收掉，然后调用unlock_page()唤醒缺页进程，继续尝试回收下一个进程。而缺页进程完成页表的设置和页槽引用的释放等。从内核的视角观察：
+-----+-----+-----+
| 1 | 2 | 3 | swap slot
+-----+--+--+-----+
|
+---------->+
| |
| +-----+--+--+-----+
| | 1 | 2 | 3 | swap cache
| +-----+--+--+-----+
| |
| +-------+
| +-----+ |
| | pte | v
| +-----+------>+--+--+ +-----+
| |page |<-----| lru |
| +-----+ +-----+ +-----+
+--| pte'|
+-----+
1. mapcount = 1 ，只换入了一次
2. refcount = 3 ，除了会被`lru`引用和换入页表项引用外，还会被高速缓存一直引用，因为有换出的进程还未换入。只有swapcount为1时，即仅高速缓存引用时，才会解除与页的映射。
3. swapcount = 2 ，只被高速缓存引用和另一个已解除映射的页表项引用
