Linux内存管理：(五)反向映射RMAP

文章说明：

• Linux内核版本：5.0

• 架构：ARM64

• 参考资料及图片来源：《奔跑吧Linux内核》

• Linux 5.0内核源码注释仓库地址：

  zhangzihengya/LinuxSourceCode_v5.0_study (github.com)

1. 前置知识：page数据结构中的相关字段

本文主要对反向映射RMAP进行讲解，在讲解之前，我们先了解下page数据结构中与RMAP相关的几个字段：

• mapping：表示页面所指向的地址空间。内核中的地址空间通常有两个不同的地址空间，—个用于文件映射页面，如在读取文件时，地址空间用于将文件的内容数据与装载数据的存储介质区关联起来；另—个用于匿名映射。内核使用一个简单直接的方式实现了“一个指针，两种用途”，mapping成员的最低两位用于判断是否指向匿名映射或KSM页面的地址空间。如果指向匿名页面，那么mapping成员指向匿名页面的地址空间数据结构anon_vma。
• _refcount：表示内核中引用该页面的次数。
  • 当_refcount的值为0时，表示该页面为空闲页面或即将要被释放的页面
  • 当_refcount的值大于0时，表示该页面已经被分配且内核正在使用，暂时不会被释放
• _mapcount：表示这个页面被进程映射的个数，即已经映射了多少个用户PTE。每个用户进 程都拥有各自独立的虚拟空间和一份独立的页表，所以可能出现多个用户进程地址空间同时映射到一个物理页面的情况，RMAP系统就是利用这个特性来实现的。_mapcount主要用于RMAP系统中。
  • 若_mapcount等于-1，表示没有PTE映射到页面
  • 若_mapcount等于0，表示只有父进程映射到页面。匿名页面刚分配时，初始化为0。

2. RMAP的背景

用户进程在使用虚拟内存的过程中，从虚拟内存页面映射到物理内存页面时，PTE保留这个记录，page数据结构中的_mapcount记录有多少个用户PTE映射到物理页面。用户PTE是指用户进程地址空间和物理页面建立映射的PTE，不包括内核地址空间映射物理页面时产生的PTE。有的页面需要迁移，有的页面长时间不使用，需要交换到磁盘。在交换之前，必须找出哪些进程使用这个页面，然后解除这些映射的用户PTE。一个物理页面可以同时被多个进程的虚拟内存映射，但是一个虚拟页面同时只能映射到一个物理页面。

在Linux 2.4内核中，为了确定某一个页面是否被某个进程映射，必须遍历每个进程的页表，因此工作量相当大，效率很低。在Linux2.5内核开发期间，提出了反问映射（Reverse Mapping，RMAP）的概念。

3. RMAP的主要数据结构

RMAP的主要目的是从物理页面的page数据结构中找到有哪些映射的用户PTE，这样页面回收模块就可以很快速和高效地把这个物理页面映射的所有用户PTE都解除并回收这个页面。

为了达到这个目的，内核在页面创建时需要建立RMAP的“钩子”，即建立相关的数据结构，RMAP系统中有两个重要的数据结构：一个是anon_vma，简称AV；另一个是anon_vma_chain，简称AVC。

anon_vma 数据结构：

// 主要用于连接物理页面的 page 数据结构和 VMA 的 vm_area_struct 数据结构
struct anon_vma {
	// 指向 anon_vma 数据结构的根节点
	struct anon_vma *root;		/* Root of this anon_vma tree */
	// 保护 anon_vma 数据结构中链表的读写信号量
	struct rw_semaphore rwsem;	/* W: modification, R: walking the list */
	// 引用计数
	atomic_t refcount;

	...

	// 指向父 anon_vma 数据结构
	struct anon_vma *parent;	/* Parent of this anon_vma */

	// 红黑树根节点。anon_vma 内部有一颗红黑树
	struct rb_root_cached rb_root;
};

anon_vma_chain 数据结构：

// 起枢纽的作用，比如连接父子进程间的 struct anon_vma 数据结构
struct anon_vma_chain {
	// 指向 VMA。可以指向父进程的 VMA，也可以指向子进程的 VMA，具体情况需要具体分析
	struct vm_area_struct *vma;
	// 指向 anon_vma 数据结构。可以指向父进程的 anon_vma，也可以指向子进程的 anon_vma，具体情况需要具体分析
	struct anon_vma *anon_vma;
	// 链表节点，通常把 anon_vma_chain 添加到 vma->anon_vma_chain 链表中
	struct list_head same_vma;   /* locked by mmap_sem & page_table_lock */
	// 红黑树节点，通常把 anon_vma_chain 添加到 anon_vma->rb_root 的红黑树中
	struct rb_node rb;			/* locked by anon_vma->rwsem */
	...
};

4. 父进程产生匿名页面

父进程为自己的进程地址空间VMA分配物理内存时，通常会产生匿名页面。例如：

用户态malloc()分配虚拟内存
    → 用户进程写内存
    	→ 内核发生缺页异常
    		→ do_anonymous_page()

父进程产生匿名页面时的状态如下图所示：

• 父进程的每个VMA中有一个anon_vma数据结构（下文用AVp来表示），vma->anon_vma指向AVp
• 和VMAp相关的物理页面page->mapping都指向AVp
• 有一个anon_vma_chain数据结构,其中avc->vma指向VMAp，avc->av指向AVp
• 把anon_vma_chain添加到VMAp->anon_vma_chain链表中
• 把anon_vma_chain添加到AVp->anon_vma红黑树中

5. 根据父进程创建子进程

父进程通过fork()系统调用创建子进程时，子进程会复制父进程的VMA数据结构的内容，并且会复制父进程的PTE内容到子进程的页表中，实现父、子进程共享页表。多个不同子进程中的虚拟页面会同时映射到同一个物理页面。另外，多个不相干的进程的虚拟页面可以通过KSM机制映射到同—个物理页面中，这里暂时只讨论前者。为了实现RMAP系统，在子进程复制父进程的VMA时，需要添加RMAP“钩子”。

父进程通过fork调用创建子进程时，RMAP机制的流程如下图所示：

为了使读者有更真切的理解，下文将根据流程图围绕源代码进行讲解这个过程：

父进程fork子进程->do_fork()->copy_process()->copy_mm()->dup_mm()->dup_mmap()

// 复制父进程的地址空间
static __latent_entropy int dup_mmap(struct mm_struct *mm,
					struct mm_struct *oldmm)
{
	...
	// 遍历父进程所有的 VMA
	for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) {
		struct file *file;

		...
		// 新建一个临时用的 VMA 数据结构 tmp，复制父进程 VMA 数据结构的内容到 tmp
		tmp = vm_area_dup(mpnt);
		...
		tmp->vm_mm = mm;
		...
		// anon_vma_fork() 为子进程创建相应的 anon_vma 数据结构
		} else if (anon_vma_fork(tmp, mpnt))
		...

		// 把 tmp 添加到子进程的红黑树中
		__vma_link_rb(mm, tmp, rb_link, rb_parent);
		...
			// 复制父进程的 PTE 到子进程页表中
			retval = copy_page_range(mm, oldmm, mpnt);

		...
}

父进程fork子进程->do_fork()->copy_process()->copy_mm()->dup_mm()->dup_mmap()->anon_vma_fork

// 主要作用是把 VMA 绑定到子进程的 anon_vma 数据结构中
// 参数 vma 表示子进程的 VMA
// 参数 pvma 表示父进程的 VMA
int anon_vma_fork(struct vm_area_struct *vma, struct vm_area_struct *pvma)
{
	...
	// 若父进程没有 anon_vma 数据结构，就不需要绑定了
	if (!pvma->anon_vma)
		return 0;

	// anon_vma_clone() 函数：
    // 遍历父进程VMA中的anon_vma_chain链表寻找anon_vma_chain实例，这里称这个实例为pavc；
    // 分配一个新的anon_vma_chain数据结构，这里称为anon_vma_chain枢纽；
    // 通过pavc找到父进程VMA中的anon_vma；
    // 把这个anon_vma_chain枢纽挂入子进程的VMA的anon_vma_chain链表中，同时把anon_vma_chain枢纽添加到属于父进程的anon_vma->rb_root的红黑树中，使子进程和父进程的VMA之间有一个联系的纽带；
	error = anon_vma_clone(vma, pvma);
	if (error)
		return error;

	// 若子进程的 VMA 已经创建了 anon_vma 数据结构，说明绑定已经完成
	if (vma->anon_vma)
		return 0;

	// 分配属于子进程的 anon_vma 和 anon_vma_chain
	anon_vma = anon_vma_alloc();
	...
	// get_anon_vma() 增加 anon_vma 数据结构中的 refcount，注意这里增加的是父进程的 anon_vma 中的引用计数
	get_anon_vma(anon_vma->root);
	...
	// 把 anon_vma_chain 挂入子进程的 vma->anon_vma_chain 链表中，同时把 anon_vma_chain 加入子进程的 anon_vma->rb_root 红黑树中
	// 至此，子进程的 VMA 和父进程的 VMA 之间的纽带建立成功
	anon_vma_chain_link(vma, avc, anon_vma);
	...
}

6. 子进程发生写时复制

如果子进程的VMA发生写时复制，那么page->mmapmg指针指向子进程VMA对应的anon_vma数据结构。在do_wp_page()函数中处理写时复制的情况。流程如下图所示：

子进程和父进程共享的匿名页面，子进程的VMA发生写时复制
    ->缺页中断发生
	  ->handle_pte_fault()
	    ->do_wp_page()
		  ->wp_page_copy()
			->分配一个新的匿名页面
			  ->page_add_new_anon_rmap()
				->__page_set_anon_rmap()使用子进程的anon_vma来设置page->mapping

子进程发生写时复制时，RMAP机制的流程如下图所示：

7. RMAP的应用

RMAP的典型应用场景如下：

• kswapd内核线程为了回收页面，需要断开所有映射到该匿名页面的用户PTE
• 页面迁移时，需要断开所有映射到匿名页面的用户PTE

RMAP的核心函数是try_to_unmap()，内核中的其他模块会调用此函数来断开一个页面的所有映射：

bool try_to_unmap(struct page *page, enum ttu_flags flags)
{
	struct rmap_walk_control rwc = {
		.rmap_one = try_to_unmap_one,
		.arg = (void *)flags,
		.done = page_mapcount_is_zero,
		.anon_lock = page_lock_anon_vma_read,
	};

	...

	if (flags & TTU_RMAP_LOCKED)
		rmap_walk_locked(page, &rwc);
	else
		rmap_walk(page, &rwc);

	// 判断 page 的 _mapcount:
	// 若 _mapcount 为 -1，说明所有映射到这个页面的用户 PTE 都已经解除完毕，因此返回 true
	// 否则返回 true
	return !page_mapcount(page) ? true : false;
}

rmap_walk_control 数据结构：

// 用于统一管理 unmap 操作
struct rmap_walk_control {
	void *arg;
	// 表示具体断开某个 VMA 上映射的 PTE
	bool (*rmap_one)(struct page *page, struct vm_area_struct *vma,
					unsigned long addr, void *arg);
	// 表示判断一个页面是否断开成功
	int (*done)(struct page *page);
	// 实现一个锁机制
	struct anon_vma *(*anon_lock)(struct page *page);
	// 表示跳过无效的 VMA
	bool (*invalid_vma)(struct vm_area_struct *vma, void *arg);
};

以匿名页面为例来介绍RMAP的应用：

try_to_unmap()->rmap_walk()->rmap_walk_anon()

// 断开一个匿名页面的所有映射
// 参数 page 表示需要解除映射的物理页面的 page 数据结构
// 参数 rwc 表示 rmap_walk_control 数据结构
// 参数 locked 表示是否已经加锁
static void rmap_walk_anon(struct page *page, struct rmap_walk_control *rwc,
		bool locked)
{
	...

	if (locked) {
		// 若 locked 已经加锁
		// 调用 page_anon_vma() 函数来获取 anon_vma 数据结构
		anon_vma = page_anon_vma(page);
		/* anon_vma disappear under us? */
		VM_BUG_ON_PAGE(!anon_vma, page);
	} else {
		// 若 locked 没有加锁
		// rmap_walk_anon_lock() 函数除了要取回 anon_vma 数据结构外，还会申请一个锁
		anon_vma = rmap_walk_anon_lock(page, rwc);
	}
	...
	// 遍历 anon_vma->rb_root 红黑树中的 anon_vma_chain，从 anon_vma_chain 中可以
	// 得到相应的 VMA，然后调用 rmap_one() 来解除用户 PTE
	anon_vma_interval_tree_foreach(avc, &anon_vma->rb_root,
			pgoff_start, pgoff_end) {
		...
	}

	...
}