kvm with mmu notifier v18

Hello,

this is an update of the patch to test kvm on mmu notifier v18. I'll post the mmu notifier v18 tomorrow after some more review but I can post the kvm side in the meantime (which works with the previous v17 as well if anyone wants to test).

This has a relevant fix for kvm_unmap_rmapp: rmap_remove while deleting the current spte from the desc array, can overwrite the deleted current spte with the last spte in the desc array in turn reodering it. So if we restart rmap_next from the sptes after the deleted current spte, we may miss the later sptes that have been moved in the slot of the current spte. We've to teardown the whole desc array so the fix was to simply pick from the first entry and wait the others to come down.

I also wonder if the update_pte done outside the mmu_lock is safe without mmu notifiers, or if the below changes are required regardless (I think they are). I cleaned up the fix but I probably need to extract it from this patch.

arch/x86/kvm/mmu.c +4 -0

+
+static int kvm_age_rmapp(struct kvm *kvm, unsigned long *rmapp)
+{
+	u64 *spte;

arch/x86/kvm/mmu.c +5 -0

+		}
+		spte = rmap_next(kvm, rmapp, spte);
+	}
+	return young;
+}

arch/x86/kvm/mmu.c +15 -10

@@ -1626,18 +1744,20 @@ static bool last_updated_pte_accessed(struct kvm_vcpu *vcpu)
 	return !!(spte && (*spte & shadow_accessed_mask));
 }
 
-static void mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
-					  const u8 *new, int bytes)
+static int mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
+					 const u8 *new, int bytes,
+					 gfn_t *_gfn, pfn_t *_pfn,
+					 int *_mmu_seq, int *_largepage)
 {
 	gfn_t gfn;
 	int r;
 	u64 gpte = 0;
 	pfn_t pfn;
-
-	vcpu->arch.update_pte.largepage = 0;
+	int mmu_seq;
+	int largepage;
 
 	if (bytes != 4 && bytes != 8)
-		return;
+		return 0;
 
 	/*
 	 * Assume that the pte write on a page table of the same type

@@ -1650,7 +1770,7 @@ static void mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
 		if ((bytes == 4) && (gpa % 4 == 0)) {
 			r = kvm_read_guest(vcpu->kvm, gpa & ~(u64)7, &gpte, 8);
 			if (r)
-				return;
+				return 0;
 			memcpy((void *)&gpte + (gpa % 8), new, 4);
 		} else if ((bytes == 8) && (gpa % 8 == 0)) {
 			memcpy((void *)&gpte, new, 8);

@@ -1660,23 +1780,30 @@ static void mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
 			memcpy((void *)&gpte, new, 4);
 	}
 	if (!is_present_pte(gpte))
-		return;
+		return 0;
 	gfn = (gpte & PT64_BASE_ADDR_MASK) >> PAGE_SHIFT;
 
+	largepage = 0;
 	down_read(&current->mm->mmap_sem);
 	if (is_large_pte(gpte) && is_largepage_backed(vcpu, gfn)) {
 		gfn &= ~(KVM_PAGES_PER_HPAGE-1);
-		vcpu->arch.update_pte.largepage = 1;
+		largepage = 1;
 	}
+	mmu_seq = atomic_read(&vcpu->kvm->arch.mmu_notifier_seq);
+	/* implicit mb(), we'll read before PT lock is unlocked */
 	pfn = gfn_to_pfn(vcpu->kvm, gfn);
 	up_read(&current->mm->mmap_sem);
 
-	if (is_error_pfn(pfn)) {
+	if (unlikely(is_error_pfn(pfn))) {
 		kvm_release_pfn_clean(pfn);
-		return;
+		return 0;
 	}

Review

Quoted 3 lines

(quoted diff) +2 -0

+		if (_young) {
+			young = !!_young;

young = 1?

Review

Quoted 2 lines

(quoted diff) +1 -0

+			set_shadow_pte(spte, _spte & ~PT_ACCESSED_MASK);

This can theoretically lose the dirty bit. We don't track it now, so that's okay.

One day we want to sort the slots according to size. We'll need better locking then (rcu, likely).

Review

Quoted 9 lines

@@ -1235,9 +1340,9 @@ static void mmu_free_roots(struct kvm_vcpu *vcpu)

(quoted diff) +2 -1

 	int i;
 	struct kvm_mmu_page *sp;
 -	if (!VALID_PAGE(vcpu->arch.mmu.root_hpa))
-		return;
 	spin_lock(&vcpu->kvm->mmu_lock);
+	if (!VALID_PAGE(vcpu->arch.mmu.root_hpa))
+		goto out;

vcpu-> stuff is protected by the vcpu mutex.

Alternatively, we can replace this with follow_page() in update_pte(). Probably best to defer it, though.

Please move the registration to virt/kvm/kvm_main.c, and provide stubs for non-x86. This is definitely something that we want to do cross-arch (except s390 which have it in hardware).

Quoted 3 lines

One day we want to sort the slots according to size. We'll need better locking then (rcu, likely).

I think it's more interesting to sort them on their start/end gfn address, prio_tree would be the optimal structure for me to use in the mmu notifier invalidates as I could ask the prio tree to show me in O(log(N)) (N number of slots) all the slots that overlap with the invalidated start/end range. However I'm afraid there aren't enough slots for this to matter... but OTOH there aren't frequent modifications either, so it may be a microoptimization (if there were frequent modifications with such a small number of slots it likely would be slower than a list).

Quoted 13 lines

Review

Quoted 11 lines

@@ -1235,9 +1340,9 @@ static void mmu_free_roots(struct kvm_vcpu *vcpu)

(quoted diff) +2 -1

 	int i;
 	struct kvm_mmu_page *sp;
 -	if (!VALID_PAGE(vcpu->arch.mmu.root_hpa))
-		return;
 	spin_lock(&vcpu->kvm->mmu_lock);
+	if (!VALID_PAGE(vcpu->arch.mmu.root_hpa))
+		goto out;

vcpu-> stuff is protected by the vcpu mutex.

That was to run it in ->release but I'm undoing as I'm removing release.

Quoted 2 lines

Please move the registration to virt/kvm/kvm_main.c, and provide stubs for non-x86. This is definitely something that we want to do cross-arch (except s390 which have it in hardware).

Sorry but I did this originally in kvm/kvm_main.c and I got complains from s390 that didn't want the common code polluted with non-s390 needed stuff. so what should I do?

Quoted 5 lines · Andrea Arcangeli

Quoted 4 lines

One day we want to sort the slots according to size. We'll need better locking then (rcu, likely).

Quoted 10 lines

I think it's more interesting to sort them on their start/end gfn address, prio_tree would be the optimal structure for me to use in the mmu notifier invalidates as I could ask the prio tree to show me in O(log(N)) (N number of slots) all the slots that overlap with the invalidated start/end range. However I'm afraid there aren't enough slots for this to matter... but OTOH there aren't frequent modifications either, so it may be a microoptimization (if there were frequent modifications with such a small number of slots it likely would be slower than a list).

There are only two interesting slots, 1G-end_of_mem and 0-pci_hole. A sorted array gives an average of less than two lookups to find the slot, with the smallest possible constant. Any other algorithm will give more lookups with a far higher constant.

Sometimes linear search is the best algorithm.

Surely ->release can't happen while vcpus are still running?

x86, ia64, and ppc all need mmu notifiers as well as other new architectures, so this better be in common code. We can #ifdef it so s390 doesn't suffer a performance impact.

I forgot, last round: EPT doesn't have PT_ACCESSED_MASK, so you're reading (and clearing) some random bit. We can easily qualify the test by looking at shadow_accessed_mask; if zero, the hardware doesn't have a young bit.

There's a bigger question of what to do in the case of EPT. We can always return true, or return true and also unmap. The first means we lie to the vm, the second means we take unnecessary exits to maintain age information.

Quoted 18 lines · Avi Kivity

Quoted 14 lines · Andrea Arcangeli

Quoted 3 lines

One day we want to sort the slots according to size. We'll need better locking then (rcu, likely).

I think it's more interesting to sort them on their start/end gfn address, prio_tree would be the optimal structure for me to use in the mmu notifier invalidates as I could ask the prio tree to show me in O(log(N)) (N number of slots) all the slots that overlap with the invalidated start/end range. However I'm afraid there aren't enough slots for this to matter... but OTOH there aren't frequent modifications either, so it may be a microoptimization (if there were frequent modifications with such a small number of slots it likely would be slower than a list).

There are only two interesting slots, 1G-end_of_mem and 0-pci_hole. A sorted array gives an average of less than two lookups to find the slot, with the smallest possible constant. Any other algorithm will give more lookups with a far higher constant.

Quoted 2 lines

Sometimes linear search is the best algorithm.

But we can't break the loop after the first match! I think you're not taking into account the aliasing done with overlapping gfn in the memslots (which is not forbidden apparently and you planned to obsolete the explicit aliasing logic with it)

. Only prio_tree can
reduce the number of walks in the most optimal way because of the gfn overlaps and search by start-end address. Sorting by size won't be useful because we can't break the loop after the first found match. If prio tree is too heavyweight the next best would be sorting with a single-index tree like rbtree by start address as it'll at least eliminate all the memslots that have a start address higher than the end of the invalidate range. But prio_tree will eliminate them all in O(log(N)) so on the paper prio_tree is best (but perhaps in practice rbtree is better, dunno).

Quoted 4 lines

I forgot, last round: EPT doesn't have PT_ACCESSED_MASK, so you're reading (and clearing) some random bit. We can easily qualify the test by looking at shadow_accessed_mask; if zero, the hardware doesn't have a young bit.

There's a bigger question of what to do in the case of EPT. We can always return true, or return true and also unmap. The first means we lie to the vm, the second means we take unnecessary exits to maintain age information.

If there's no access bit (and we can't use the guest pte access bit because EPT represent a physical page and not a guest pte anymore) we're forced to return 0 without doing anything at all. Returning 1 is unsafe as it'd pin the page in host ram.

If there's no access bit all we can do is to wait the VM to unmap the page, mark the spte not present during the invalidate_page mmu notifier, and wait the guest to trigger a minor fault from swapcache.

For the gfn->hva (the common case) we can break immediately. For the hva->gfn, in general we cannot, but we can add an "unaliased" flag to the

memslot and set it for slots which do not have aliases. That makes the loop terminate soon again.

Any pointer-based data structure is bound to be much slower than a list with such a small number of elements.

btw, on 64-bit userspace we can arrange the entire physical address space in a contiguous region (some of it unmapped) and have just one slot for the guest.

Okay. It's sad, but I don't see any choice.

If anyone from Intel is listening, please give us an accessed bit (and a dirty bit, too).

Quoted 2 lines

memslot and set it for slots which do not have aliases. That makes the loop terminate soon again.

So we need to make sure that aliases (gart-like) aren't common, or if we've an alias on ram we go back to scanning the whole list all the time.

Quoted 2 lines

Any pointer-based data structure is bound to be much slower than a list with such a small number of elements.

Tree can only be slower than a list if there is the bitflag to signal there is no alias so the list will break the loop always at the first step. If you remove that bitflag, tree lookup can't be slower than walking the entire list, even if there are only 3/4 elements queued. Only the no_alias bitflag allows the list to be faster.

Quoted 2 lines

btw, on 64-bit userspace we can arrange the entire physical address space in a contiguous region (some of it unmapped) and have just one slot for the guest.

I thought mmio regions would need to be separated for 64bit too? I mean what's the point of the memslots in the first place if there's only one for the whole physical address space?

Quoted 4 lines

Okay. It's sad, but I don't see any choice.

If anyone from Intel is listening, please give us an accessed bit (and a dirty bit, too).

Seconded.

The other thing we could do would be to mark the spte invalid, and return 1, and then at the second ->clear_test_young if the spte is still invalid, we return 0. That way we would limit the accessed bit refresh to a kvm page fault without tearing down the linux pte (so follow_page would be enough then). While if we return 0, if the linux pte is already old, the page will be unmapped and go in swapcache and follow_page won't be enough and get_user_pages will have to call do_swap_page minor fault.

However to do the above, we would need to track with rmap non present sptes, and that'd require changes to the kvm rmap logic. so initially returning 0 is simpler.

latest version, I removed ->release already before posting the last one because by the time vm destroy runs no more guest mode can run, so sptes are irrelevant and no cpu can follow the secondary tlb anymore because no cpu can be in guest mode for the 'mm', even if sptes are actually destroyed later. The previous patch was taking a kvm mutex in release under mmu_lock and that's forbidden, so it's simpler to remove the release debug knob for now (you suggested to use kvm_reload_remote_mmus in the future that shouldn't take sleeping locks). The only reason for having a real ->release would be to avoid any risk w.r.t. to tlb speculative accesses to gart alias with different cache protocol (I doubt this is a realistic worry but anyway it's not big deal to implement a ->release).

Signed-off-by Andrea Arcangeli <[email protected]>

arch/x86/kvm/mmu.c +28 -11

+static int mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
+					 const u8 *new, int bytes,
+					 gfn_t *_gfn, pfn_t *_pfn,
+					 int *_mmu_seq, int *_largepage)
 {
 	gfn_t gfn;
 	int r;
 	u64 gpte = 0;
 	pfn_t pfn;
-
-	vcpu->arch.update_pte.largepage = 0;
+	int mmu_seq;
+	int largepage;
 
 	if (bytes != 4 && bytes != 8)
-		return;
+		return 0;
 
 	/*
 	 * Assume that the pte write on a page table of the same type

@@ -1650,7 +1770,7 @@ static void mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
 		if ((bytes == 4) && (gpa % 4 == 0)) {
 			r = kvm_read_guest(vcpu->kvm, gpa & ~(u64)7, &gpte, 8);
 			if (r)
-				return;
+				return 0;
 			memcpy((void *)&gpte + (gpa % 8), new, 4);
 		} else if ((bytes == 8) && (gpa % 8 == 0)) {
 			memcpy((void *)&gpte, new, 8);

@@ -1660,23 +1780,30 @@ static void mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
 			memcpy((void *)&gpte, new, 4);
 	}
 	if (!is_present_pte(gpte))
-		return;
+		return 0;
 	gfn = (gpte & PT64_BASE_ADDR_MASK) >> PAGE_SHIFT;
 
+	largepage = 0;
 	down_read(&current->mm->mmap_sem);
 	if (is_large_pte(gpte) && is_largepage_backed(vcpu, gfn)) {
 		gfn &= ~(KVM_PAGES_PER_HPAGE-1);
-		vcpu->arch.update_pte.largepage = 1;
+		largepage = 1;
 	}
+	mmu_seq = atomic_read(&vcpu->kvm->arch.mmu_notifier_seq);
+	/* implicit mb(), we'll read before PT lock is unlocked */
 	pfn = gfn_to_pfn(vcpu->kvm, gfn);
 	up_read(&current->mm->mmap_sem);
 
-	if (is_error_pfn(pfn)) {
+	if (unlikely(is_error_pfn(pfn))) {
 		kvm_release_pfn_clean(pfn);
-		return;
+		return 0;
 	}
-	vcpu->arch.update_pte.gfn = gfn;
-	vcpu->arch.update_pte.pfn = pfn;
+
+	*_gfn = gfn;
+	*_pfn = pfn;
+	*_mmu_seq = mmu_seq;
+	*_largepage = largepage;
+	return 1;
 }
 
 static void kvm_mmu_access_page(struct kvm_vcpu *vcpu, gfn_t gfn)

@@ -1711,9 +1838,24 @@ void kvm_mmu_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
 	int npte;
 	int r;
 
+	int update_pte;
+	gfn_t gpte_gfn;
+	pfn_t pfn;
+	int mmu_seq;
+	int largepage;
+
 	pgprintk("%s: gpa %llx bytes %d\n", __func__, gpa, bytes);
-	mmu_guess_page_from_pte_write(vcpu, gpa, new, bytes);
+	update_pte = mmu_guess_page_from_pte_write(vcpu, gpa, new, bytes,

Hi Andrea,

Quoted 100 lines · Andrea Arcangeli

latest version, I removed ->release already before posting the last one because by the time vm destroy runs no more guest mode can run, so sptes are irrelevant and no cpu can follow the secondary tlb anymore because no cpu can be in guest mode for the 'mm', even if sptes are actually destroyed later. The previous patch was taking a kvm mutex in release under mmu_lock and that's forbidden, so it's simpler to remove the release debug knob for now (you suggested to use kvm_reload_remote_mmus in the future that shouldn't take sleeping locks). The only reason for having a real ->release would be to avoid any risk w.r.t. to tlb speculative accesses to gart alias with different cache protocol (I doubt this is a realistic worry but anyway it's not big deal to implement a ->release).

Signed-off-by Andrea Arcangeli <[email protected]>

arch/x86/kvm/mmu.c +33 -11

+static int mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
+					 const u8 *new, int bytes,
+					 gfn_t *_gfn, pfn_t *_pfn,
+					 int *_mmu_seq, int *_largepage)
 {
 	gfn_t gfn;
 	int r;
 	u64 gpte = 0;
 	pfn_t pfn;
-
-	vcpu->arch.update_pte.largepage = 0;
+	int mmu_seq;
+	int largepage;
 
 	if (bytes != 4 && bytes != 8)
-		return;
+		return 0;
 
 	/*
 	 * Assume that the pte write on a page table of the same type

@@ -1650,7 +1770,7 @@ static void mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
 		if ((bytes == 4) && (gpa % 4 == 0)) {
 			r = kvm_read_guest(vcpu->kvm, gpa & ~(u64)7, &gpte, 8);
 			if (r)
-				return;
+				return 0;
 			memcpy((void *)&gpte + (gpa % 8), new, 4);
 		} else if ((bytes == 8) && (gpa % 8 == 0)) {
 			memcpy((void *)&gpte, new, 8);

@@ -1660,23 +1780,30 @@ static void mmu_guess_page_from_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
 			memcpy((void *)&gpte, new, 4);
 	}
 	if (!is_present_pte(gpte))
-		return;
+		return 0;
 	gfn = (gpte & PT64_BASE_ADDR_MASK) >> PAGE_SHIFT;
 
+	largepage = 0;
 	down_read(&current->mm->mmap_sem);
 	if (is_large_pte(gpte) && is_largepage_backed(vcpu, gfn)) {
 		gfn &= ~(KVM_PAGES_PER_HPAGE-1);
-		vcpu->arch.update_pte.largepage = 1;
+		largepage = 1;
 	}
+	mmu_seq = atomic_read(&vcpu->kvm->arch.mmu_notifier_seq);
+	/* implicit mb(), we'll read before PT lock is unlocked */
 	pfn = gfn_to_pfn(vcpu->kvm, gfn);
 	up_read(&current->mm->mmap_sem);
 
-	if (is_error_pfn(pfn)) {
+	if (unlikely(is_error_pfn(pfn))) {
 		kvm_release_pfn_clean(pfn);
-		return;
+		return 0;
 	}
-	vcpu->arch.update_pte.gfn = gfn;
-	vcpu->arch.update_pte.pfn = pfn;
+
+	*_gfn = gfn;
+	*_pfn = pfn;
+	*_mmu_seq = mmu_seq;
+	*_largepage = largepage;
+	return 1;
 }
 
 static void kvm_mmu_access_page(struct kvm_vcpu *vcpu, gfn_t gfn)

@@ -1711,9 +1838,24 @@ void kvm_mmu_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
 	int npte;
 	int r;
 
+	int update_pte;
+	gfn_t gpte_gfn;
+	pfn_t pfn;
+	int mmu_seq;
+	int largepage;
+
 	pgprintk("%s: gpa %llx bytes %d\n", __func__, gpa, bytes);
-	mmu_guess_page_from_pte_write(vcpu, gpa, new, bytes);
+	update_pte = mmu_guess_page_from_pte_write(vcpu, gpa, new, bytes,
+						   &gpte_gfn, &pfn,
+						   &mmu_seq, &largepage);
 	spin_lock(&vcpu->kvm->mmu_lock);
+	if (update_pte) {
+		BUG_ON(!is_error_pfn(vcpu->arch.update_pte.pfn));
+		vcpu->arch.update_pte.gfn = gpte_gfn;

arch/x86/kvm/mmu.c void kvm_mmu_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa, · line 1858

Quoted 4 lines

arch/x86/kvm/mmu.c +4 -0

+		vcpu->arch.update_pte.pfn = pfn;
+		vcpu->arch.update_pte.mmu_seq = mmu_seq;
+		vcpu->arch.update_pte.largepage = largepage;
+	}

I don't get this. mmu_lock protects the shadow page tables, reverse mappings and associated lists. vcpu->arch.update_pte is a per-vcpu structure, so it does not need locking by itself.