RMAP (Reverse MAPping)

RMAP in kernel

Linux 下可以根据 VA 经过页表转换得到 PA。怎么根据 PA 得到对应的 VA 呢？这里便用到了逆向映射。

逆向映射有什么用呢？最重要的，在物理页面换出时，需要更新引用了此页面的 SPTE 来表示 non-present。如何获取对应的物理页面对应的 PTE 呢？内核的做法是：

• 先通过 RMAP 得到 VA，
• 页表以 VA 为 key，得到 PTE 地址，然后进行更新。

如果没有 RMAP 的话需要遍历页表，这样子开销很大。

KVm中EPT逆向映射机制分析 - jack.chen - 博客园

RMAP in KVM / PTE List in KVM

在 KVM 中，逆向映射机制的作用是类似的，但是完成的却不是从 HPA 到对应的 EPT 页表项的定位，而是从 GFN 到对应的 SPTE 的定位。理论上讲根据 GFN 一步步遍历 EPT 也未尝不可，但是效率较低；为了提高效率，就有了当前的逆向映射机制。

RMAP in KVM data structures and macros

struct pte_list_desc KVM

链表里的一个节点。一个节点可以 hold 14 个 PTE。

// 这是为了 fit cache lines
#define PTE_LIST_EXT 14

/*
 * Implement a custom list for tracking a set of related SPTEs, e.g. all the SPTEs that map a
 * given GFN when used in the context of rmaps.  Using a custom list allows KVM
 * to optimize for the common case where many GFNs will have at most a handful
 * of SPTEs pointing at them, i.e. allows packing multiple SPTEs into a small
 * memory footprint, which in turn improves runtime performance by exploiting
 * cache locality.
 *
 * A list is comprised of one or more pte_list_desc objects (descriptors).
 * Each individual descriptor stores up to PTE_LIST_EXT SPTEs.  If a descriptor
 * is full and a new SPTEs needs to be added, a new descriptor is allocated and
 * becomes the head of the list.  This means that by definitions, all tail
 * descriptors are full.
 *
 * Note, the meta data fields are deliberately placed at the start of the
 * structure to optimize the cacheline layout; accessing the descriptor will
 * touch only a single cacheline so long as @spte_count<=6 (or if only the
 * descriptors metadata is accessed).
 */
struct pte_list_desc {
	struct pte_list_desc *more;
	/* The number of PTEs stored in _this_ descriptor. */
    // 相当于一个 index，告诉下一个存哪里，最多为 14
	u32 spte_count;
	/* The number of PTEs stored in all tails of this descriptor. */
	u32 tail_count;
	u64 *sptes[PTE_LIST_EXT];
};

struct kvm_rmap_head KVM

rmap 是 legacy MMU 才有的，不是 TDP MMU 有的。

下面两个地方用到了：

• 每一个 kvm_memory_slot 一个 rmap，这个 rmap 的长度取决于这个 slot 有多少个 page（或 huge page）。每一个元素的类型都是 struct kvm_rmap_head。也就是说，一个 GFN 对应于一个 entry（kvm_rmap_head）。因为一个 kvm_rmap_head 可以存很多 SPTE，所以相当于一个 GFN 对应了许多个 SPTE，这是为啥呢？
• kvm_mmu_page->parent_ptes 里保存了所有指向这个 page table 的 SPTE。

kvm_rmap_head->val 的意义取决于其 bit 0：

• 如果 bit 0 是 0，这个 val 的值就是一个 SPTE 的值，也就是说此时 GFN 和 SPTE 是 1：1 的关系；
• 如果是 1，这个 val 的值指向一个 pte_list_desc，此时至少有两个 SPTE，也就是 GFN 和 SPTE 是 1：N 的关系。

struct kvm_memory_slot {
    //...
	struct kvm_arch_memory_slot arch;
};

struct kvm_arch_memory_slot {
    // KVM_NR_PAGE_SIZES is 3, PG_LEVEL_4K, PG_LEVEL_2M, PG_LEVEL_1G
    // 所以 rmap 是一个二维数组，rmap[KVM_NR_PAGE_SIZES][...]。
    // 每一个 entry 表示一个 GFN 所映射到的所有 SPTEs（这样就不用查 EPT 表来找了）。
	struct kvm_rmap_head *rmap[KVM_NR_PAGE_SIZES];
    //...
};

struct kvm_mmu_page {
    //...
	union {
        // 里面保存的是指向这个 PT 的所有的 parent pte
        // 为什么会有多个呢？
		struct kvm_rmap_head parent_ptes;
		tdp_ptep_t ptep;
	};
    //...
}

struct kvm_rmap_head {
    // 去除 bit 0 后，这个值是一个指针，指向一个 struct pte_list_desc 结构体
	unsigned long val;
};

pte_list_remove() / pte_list_add() KVM

rmap_head 指向很多个 pte_list_desc，一个 pte_list_desc 又有很多个 SPTE，此函数的目的就是把一个 SPTE 加入（或删除）到 rmap_head 指向的 list 里。

// Returns the number of pointers in the rmap chain, not counting the new one.
static int pte_list_add(struct kvm_mmu_memory_cache *cache, u64 *spte, struct kvm_rmap_head *rmap_head)
{
	struct pte_list_desc *desc;
	int count = 0;

    // 如果没有值，那么就把 SPTE 赋予它，合理
	if (!rmap_head->val) {
		rmap_head->val = (unsigned long)spte;
    // 如果有值但是 bit 0 是 0
    // 创建一个新的 desc，这个 desc 是第一个 desc
	} else if (!(rmap_head->val & 1)) {
		desc = kvm_mmu_memory_cache_alloc(cache);
        // 之前 val 表示一个 spte 值，我们把它保存起来
		desc->sptes[0] = (u64 *)rmap_head->val;
		desc->sptes[1] = spte;
		desc->spte_count = 2;
		desc->tail_count = 0;
        // 置上 1，表示 val 指向一个 desc，而不是一个 spte 的值
		rmap_head->val = (unsigned long)desc | 1;
		++count;
    // 如果有 
	} else {
        // 去掉这一位，之后 val 变成了指针，拿到这个指针指向的 desc
		desc = (struct pte_list_desc *)(rmap_head->val & ~1ul);
		count = desc->tail_count + desc->spte_count;

		/*
		 * If the previous head is full, allocate a new head descriptor
		 * as tail descriptors are always kept full.
		 */
		if (desc->spte_count == PTE_LIST_EXT) {
			desc = kvm_mmu_memory_cache_alloc(cache);
            // 在链表头插入，而不是链表尾
			desc->more = (struct pte_list_desc *)(rmap_head->val & ~1ul);
			desc->spte_count = 0;
            // 这个 entry 后面的所有 entries 的 count 数量
			desc->tail_count = count;
            // rmap_head 永远指向第一个 desc 的位置
            // 链表后面的 entry 由 desc->more 串联
			rmap_head->val = (unsigned long)desc | 1;
		}
		desc->sptes[desc->spte_count++] = spte;
	}
	return count;
}

static void pte_list_remove(struct kvm *kvm, u64 *spte, struct kvm_rmap_head *rmap_head)
{
	struct pte_list_desc *desc;
	int i;

    // checking...
    // 如果第一个 bit 没有被置上，那么表示一个 PTE
    // simply zero it
	if (!(rmap_head->val & 1)) {
        // checking...
		rmap_head->val = 0;
    // 这是一个指针，指向一系列的 pte_list_desc
    // 一个一个找 SPTE，找到的话就 remove
	} else {
		desc = (struct pte_list_desc *)(rmap_head->val & ~1ul);
		while (desc) {
			for (i = 0; i < desc->spte_count; ++i) {
				if (desc->sptes[i] == spte) {
					pte_list_desc_remove_entry(kvm, rmap_head, desc, i);
					return;
				}
			}
			desc = desc->more;
		}
        // checking...
	}
}

// 要从 rmap_head 指向的 list 里的 pte_list_desc remove 第 i 个
// remove 的算法是这样的，把 desc 的第 i 个 SPTE 置成第一个 pte_list_desc
// 的最后一个 SPTE 值，同时将此 SPTE 值置空，完成交换。
static void pte_list_desc_remove_entry(struct kvm *kvm,
				       struct kvm_rmap_head *rmap_head,
				       struct pte_list_desc *desc, int i)
{
	struct pte_list_desc *head_desc = (struct pte_list_desc *)(rmap_head->val & ~1ul);
	int j = head_desc->spte_count - 1;

    // checking...
	desc->sptes[i] = head_desc->sptes[j];
	head_desc->sptes[j] = NULL;
	head_desc->spte_count--;
    // 如果 head_desc 的数量不是 0，那么返回
	if (head_desc->spte_count)
		return;

	/*
	 * The head descriptor is empty.  If there are no tail descriptors,
	 * nullify the rmap head to mark the list as emtpy, else point the rmap
	 * head at the next descriptor, i.e. the new head.
	 */
    // 从 1 减到了 0，不太可能吧？
	if (!head_desc->more)
		rmap_head->val = 0;
	else
        // 让 head 指向下一个。
		rmap_head->val = (unsigned long)head_desc->more | 1;
    // 无论哪种情况，head_desc 都不需要了，所以释放掉
	mmu_free_pte_list_desc(head_desc);
}

kvm_mmu_page->parent_ptes KVM

里面保存的是指向这个 PT 的所有的 parent ptes。为什么会有多个呢？

parent_ptes 的作用，引入的意义：

• 删除一个 page table，如何保证指向这个 page table 的 SPTE 也得到更新呢，可以通过 kvm_mmu_page->parent_ptes。

什么时候会对 parent_ptes 进行更新：

• unlink 的时候，需要把 SPTE 从其 link 的 PT 的 parent_ptes 里删除掉。
• link 的时候，需要把 SPTE 加入到其所要 link 的 PTE 的 parent_ptes 里。
• PTE syncing.

下面我们分这些情况进行讨论：

kvm_mmu_unlink_parents() / drop_parent_pte() / mmu_page_remove_parent_pte() KVM

把传入的 sp 和其所有指向它的 parent SPTEs 解除 link。

// 注意，这个函数不是 zap 一个 guest page，而是 zap 一个 MMU page
// 里面可能有 512 个 entries 哦。所以刚开始就要先把这个 MMU page
// 的所有 parent 都 unlink 掉。
__kvm_mmu_prepare_zap_page
    kvm_mmu_unlink_parents
static void kvm_mmu_unlink_parents(struct kvm *kvm, struct kvm_mmu_page *sp)
{
	u64 *sptep;
	struct rmap_iterator iter;

	while ((sptep = rmap_get_first(&sp->parent_ptes, &iter)))
		drop_parent_pte(kvm, sp, sptep);
}

做了两件事：

• 从 sp 的角度触发，删除其持有的 parent_ptes 里删除其指定的父 parent_pte；
• 从 parent_pte 角度，将其置空，让其不再指向 sp。

static void drop_parent_pte(struct kvm *kvm, struct kvm_mmu_page *sp, u64 *parent_pte)
{
	mmu_page_remove_parent_pte(kvm, sp, parent_pte);
	mmu_spte_clear_no_track(parent_pte);
}

mmu_page_remove_parent_pte() 这个函数很简单，只是 sp 这个 table 所保留的 parent_ptes 里删除指定的 parent_pte entry。

static void mmu_page_remove_parent_pte(struct kvm *kvm, struct kvm_mmu_page *sp, u64 *parent_pte)
{
	pte_list_remove(kvm, parent_pte, &sp->parent_ptes);
}

mmu_page_add_parent_pte() KVM

非常简单的函数。当要 link 一个 SPTE 和 PT 时，把这个 SPTE 加入到 PT 的 parent_ptes 里面，十分合理。

__link_shadow_page
    mmu_page_add_parent_pte
static void mmu_page_add_parent_pte(struct kvm_mmu_memory_cache *cache,
				    struct kvm_mmu_page *sp, u64 *parent_pte)
{
	if (!parent_pte)
		return;

	pte_list_add(cache, parent_pte, &sp->parent_ptes);
}

kvm_mmu_mark_parents_unsync() KVM

PTE syncing.

make_spte
    mmu_try_to_unsync_pages
        kvm_unsync_page
            kvm_mmu_mark_parents_unsync
                for_each_rmap_spte(&sp->parent_ptes, &iter, sptep)
            		mark_unsync(sptep);
static void kvm_mmu_mark_parents_unsync(struct kvm_mmu_page *sp)
{
	u64 *sptep;
	struct rmap_iterator iter;

	for_each_rmap_spte(&sp->parent_ptes, &iter, sptep) {
		mark_unsync(sptep);
	}
}

RMAP in KVM functions / kvm_arch_memory_slot->rmap KVM

rmap 在 KVM 中的初始化：

__kvm_set_memory_region
    kvm_set_memslot
        kvm_prepare_memory_region
            kvm_arch_prepare_memory_region
                kvm_alloc_memslot_metadata
                    memslot_rmap_alloc
                        for (i = 0; i < KVM_NR_PAGE_SIZES; ++i)
                            slot->arch.rmap[i] = __vcalloc(lpages, sz, GFP_KERNEL_ACCOUNT);

gfn_to_rmap() KVM

这个 gfn 在 kvm_memory_slot 里的第几个 page，相同的其在 rmap 数据里的 index 也是这个，这个函数很多地方在使用。

• split 一个 private spt 的时候，要移除掉给定的 SPTE，此时需要也需要移除掉对应 rmap 里的项。
• 要 write protect 一个 GFN 的时候，我们会用到 rmap 来快速定位到 translate 这个 GFN 过程中所有级 PSE （rmap 第一级有三个 level 的 list）并且置上 protect。（rmap_write_protect()）

static struct kvm_rmap_head *gfn_to_rmap(gfn_t gfn, int level, const struct kvm_memory_slot *slot)
{
	unsigned long idx;

	idx = gfn_to_index(gfn, slot->base_gfn, level);
	return &slot->arch.rmap[level - PG_LEVEL_4K][idx];
}

rmap_remove() KVM

• 给定 SPTE，先找到映射到其的 GFN（这一步反而是容易的，因为 SP 保存了这个 shadow MMU page 所映射的 base GFN）。
• 再从 kvm_memory_slot 的 rmap 里删除此 GFN 到 SPTE 的映射。

drop_spte
    rmap_remove
static void rmap_remove(struct kvm *kvm, u64 *spte, u64 old_spte)
{
	struct kvm_memslots *slots;
	struct kvm_memory_slot *slot;
	struct kvm_mmu_page *sp;
	gfn_t gfn;
	struct kvm_rmap_head *rmap_head;

	sp = sptep_to_sp(spte);
	gfn = kvm_mmu_page_get_gfn(sp, spte_index(spte));

	slots = kvm_memslots_for_spte_role(kvm, sp->role);
	slot = __gfn_to_memslot(slots, gfn);

    // 找到 gfn 对应的 rmap 项
	rmap_head = gfn_to_rmap(gfn, sp->role.level, slot);

    // 把 gfn -> spte 的映射从其中 remove 掉
	pte_list_remove(kvm, spte, rmap_head);
	if (is_private_sp(sp))
		static_call(kvm_x86_drop_private_spte)(kvm, gfn, sp->role.level, spte_to_pfn(old_spte));
}

KVm中EPT逆向映射机制分析 - jack.chen - 博客园

RMAP iterator/walker in KVM

分为两部分：

• 第一部分是宏观的，specific to kvm_memory_slot->rmap 的每一个 GFN 到其 rmap_head 的，是为了遍历给定 GFN 区间内的 rmap_head；
• 第二部分是微观的，给定一个 rmap_head，遍历里面的所有的 SPTE for_each_rmap_spte()。

RMAP iterator/walker specific to kvm_memory_slot->rmap / Iteration over all the rmap_heads

因为一个 kvm_memory_slot 为每一个 GFN 都有一个 RMAP entry，所以 RMAP iterator 的作用是在一个 slot 内 iterate 指定 GFN 区间的所有 RMAP。

struct slot_rmap_walk_iterator KVM

struct slot_rmap_walk_iterator {
    // 输入
    // 要在哪一个 slot 里 iterate
	const struct kvm_memory_slot *slot;
    // 开始的 gfn
	gfn_t start_gfn;
    // 结束的 gfn
	gfn_t end_gfn;
	int start_level;
	int end_level;

    // 输出
    // 当前的 GFN
	gfn_t gfn;
    // 当前的 GFN 对应的 rmap
	struct kvm_rmap_head *rmap;
    // 当前的 level
	int level;

    // 私有，表示 end_gfn 所对应的 rmap
	struct kvm_rmap_head *end_rmap;
};

rmap_walk_init_level() KVM

static void rmap_walk_init_level(struct slot_rmap_walk_iterator *iterator, int level)
{
	iterator->level = level;
	iterator->gfn = iterator->start_gfn;
	iterator->rmap = gfn_to_rmap(iterator->gfn, level, iterator->slot);
	iterator->end_rmap = gfn_to_rmap(iterator->end_gfn, level, iterator->slot);
}

slot_rmap_walk_init() KVM

static void slot_rmap_walk_init(struct slot_rmap_walk_iterator *iterator,
				const struct kvm_memory_slot *slot,
				int start_level, int end_level,
				gfn_t start_gfn, gfn_t end_gfn)
{
    // 初始化输入变量
	iterator->slot = slot;
	iterator->start_level = start_level;
	iterator->end_level = end_level;
	iterator->start_gfn = start_gfn;
	iterator->end_gfn = end_gfn;

    // 初始化输出和私有变量
	rmap_walk_init_level(iterator, iterator->start_level);
}

slot_rmap_walk_okay() KVM

表示能 iterate 能继续下去的条件，一旦不 okay 了，iteration 就结束了。

okay 的条件是当前 rmap 是有值的。

static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator)
{
	return !!iterator->rmap;
}

slot_rmap_walk_next() KVM

static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
{
	while (++iterator->rmap <= iterator->end_rmap) {
        // 因为一个 page 可能不是 4K 大小，所以据此来找到下一个 GFN
		iterator->gfn += (1UL << KVM_HPAGE_GFN_SHIFT(iterator->level));
        // 如果这个 gfn 对应的 rmap 存着值不为空，那么返回
		if (iterator->rmap->val)
			return;
	}

    // iteration 已经结束，因为 rmap 被我们置为 NULL 了
	if (++iterator->level > iterator->end_level) {
		iterator->rmap = NULL;
		return;
	}

    // 迭代过一轮了，重新开始
	rmap_walk_init_level(iterator, iterator->level);
}

for_each_slot_rmap_range() KVM

#define for_each_slot_rmap_range(_slot_, _start_level_, _end_level_,	\
	   _start_gfn, _end_gfn, _iter_)				\
	for (slot_rmap_walk_init(_iter_, _slot_, _start_level_,		\
				 _end_level_, _start_gfn, _end_gfn);	\
	     slot_rmap_walk_okay(_iter_);				\
	     slot_rmap_walk_next(_iter_))

Iteration inside a rmap_head list

struct rmap_iterator

/*
 * Used by the following functions to iterate through the sptes linked by a
 * rmap.  All fields are private and not assumed to be used outside.
 */
struct rmap_iterator {
	/* private fields */
	struct pte_list_desc *desc;	/* holds the sptep if not NULL */
	int pos;			/* index of the sptep */
};

rmap_get_first() KVM

拿到 rmap_head 中的第一个个 SPTE。

/*
 * Iteration must be started by this function.  This should also be used after
 * removing/dropping sptes from the rmap link because in such cases the
 * information in the iterator may not be valid.
 *
 * Returns sptep if found, NULL otherwise.
 */
static u64 *rmap_get_first(struct kvm_rmap_head *rmap_head, struct rmap_iterator *iter)
{
	u64 *sptep;

    // 啥也没有，那就啥也不返回
	if (!rmap_head->val)
		return NULL;

    // val 只是一个 PTE value
    // sptep 指向这个值并返回
	if (!(rmap_head->val & 1)) {
		iter->desc = NULL;
		sptep = (u64 *)rmap_head->val;
		goto out;
	}

    // 第一个 desc 的第一个 pos
	iter->desc = (struct pte_list_desc *)(rmap_head->val & ~1ul);
	iter->pos = 0;
	sptep = iter->desc->sptes[iter->pos];
out:
    // SPTE 要么是 shadow present 的，要么是 private zapped 的，不能是其他的
	WARN_ON_ONCE(!is_shadow_present_pte(*sptep) && !is_private_zapped_spte(*sptep));
	return sptep;
}

rmap_get_next() KVM

找到下一个 SPTE，并不复杂。

static u64 *rmap_get_next(struct rmap_iterator *iter)
{
	u64 *sptep;

	if (iter->desc) {
        // 这个 desc 还没有迭代完，找下一个 SPTE
		if (iter->pos < PTE_LIST_EXT - 1) {
			++iter->pos;
			sptep = iter->desc->sptes[iter->pos];
			if (sptep)
				goto out;
		}

        // 迭代完了，找下一个 desc
		iter->desc = iter->desc->more;

		if (iter->desc) {
			iter->pos = 0;
			/* desc->sptes[0] cannot be NULL */
			sptep = iter->desc->sptes[iter->pos];
			goto out;
		}
	}

	return NULL;
out:
    // 我们必须保证这是个 shadow present 的
	BUG_ON(!is_shadow_present_pte(*sptep));
	return sptep;
}

for_each_rmap_spte() KVM

遍历一遍 rmap_head 里所有的 SPTE。

#define for_each_rmap_spte(_rmap_head_, _iter_, _spte_)			\
	for (_spte_ = rmap_get_first(_rmap_head_, _iter_);		\
	     _spte_; _spte_ = rmap_get_next(_iter_))