rework KVM mmu_shrink() code

First of all, I think "free" is a poor name for this value. In this context, it means, "the number of mmu pages which this kvm instance should be able to allocate." To me, "free" implies much more that the objects are there and ready for use. I think "available" is a much better description, especially when you see how it is calculated.

I think doing this makes the code much more readable. That's borne out by the fact that this patch removes code. "used" also happens to be the number that we need to return back to the slab code when our shrinker gets called. Keeping this value as opposed to free makes the next patch simpler.

So, 'struct kvm' is kzalloc()'d. 'struct kvm_arch' is a structure member (and not a pointer) of 'struct kvm'. That means they start out zeroed. I _think_ they get initialized properly by kvm_mmu_change_mmu_pages(). But, that only happens via kvm ioctls.

I have a suspicion that they values are actually inconsistent until those ioctls get called; "free" and "alloc" are both zero. But, the VM can't really get run until these ioctl()s get called anyway. There are also some checks for negative "used_pages" values which confused me. It might all tie together.

Anyway, another benefit of storing 'used' intead of 'free' is that the values are consistent from the moment the structure is
allocated: no negative "used" value.

Signed-off-by Dave Hansen <[email protected]>

---

 linux-2.6.git-dave/arch/x86/include/asm/kvm_host.h |    2 -
 linux-2.6.git-dave/arch/x86/kvm/mmu.c              |   29 +++++++--------------
 linux-2.6.git-dave/arch/x86/kvm/mmu.h              |    3 +-
 3 files changed, 13 insertions(+), 21 deletions(-)

diff -puN arch/x86/include/asm/kvm_host.h~replace-free-with-used arch/x86/include/asm/kvm_host.h

arch/x86/include/asm/kvm_host.h renamed from arch/x86/include/asm/kvm_host.h~replace-free-with-used +1 -1

@@ -380,7 +380,7 @@ struct kvm_mem_aliases {
 struct kvm_arch {
 	struct kvm_mem_aliases *aliases;
 
-	unsigned int n_free_mmu_pages;
+	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;
 	unsigned int n_max_mmu_pages;
 	atomic_t invlpg_counter;

diff -puN arch/x86/kvm/mmu.c~replace-free-with-used arch/x86/kvm/mmu.c

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~replace-free-with-used +5 -11

@@ -898,7 +898,7 @@ static void kvm_mmu_free_page(struct kvm
 	__free_page(virt_to_page(sp->spt));
 	__free_page(virt_to_page(sp->gfns));
 	kfree(sp);
-	++kvm->arch.n_free_mmu_pages;
+	--kvm->arch.n_used_mmu_pages;
 }
 
 static unsigned kvm_page_table_hashfn(gfn_t gfn)

@@ -919,7 +919,7 @@ static struct kvm_mmu_page *kvm_mmu_allo
 	bitmap_zero(sp->slot_bitmap, KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS);
 	sp->multimapped = 0;
 	sp->parent_pte = parent_pte;
-	--vcpu->kvm->arch.n_free_mmu_pages;
+	++vcpu->kvm->arch.n_used_mmu_pages;
 	return sp;
 }
 

@@ -1516,39 +1516,30 @@ static int kvm_mmu_zap_page(struct kvm *
 
 /*
  * Changing the number of mmu pages allocated to the vm
- * Note: if kvm_nr_mmu_pages is too small, you will get dead lock
+ * Note: if goal_nr_mmu_pages is too small, you will get dead lock
  */
-void kvm_mmu_change_mmu_pages(struct kvm *kvm, unsigned int kvm_nr_mmu_pages)
+void kvm_mmu_change_mmu_pages(struct kvm *kvm, unsigned int goal_nr_mmu_pages)
 {
-	int used_pages;
-
-	used_pages = kvm->arch.n_max_mmu_pages - kvm_mmu_available_pages(kvm);
-	used_pages = max(0, used_pages);
-
 	/*
 	 * If we set the number of mmu pages to be smaller be than the
 	 * number of actived pages , we must to free some mmu pages before we
 	 * change the value
 	 */
 
-	if (used_pages > kvm_nr_mmu_pages) {
-		while (used_pages > kvm_nr_mmu_pages &&
+	if (kvm->arch.n_used_mmu_pages > goal_nr_mmu_pages) {

arch/x86/kvm/mmu.c static int kvm_mmu_zap_page(struct kvm * · line 1537

Quoted 13 lines

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~replace-free-with-used +4 -4

-     if (used_pages > kvm_nr_mmu_pages) {
-             while (used_pages > kvm_nr_mmu_pages &&
+     if (kvm->arch.n_used_mmu_pages > goal_nr_mmu_pages) {
+             while (kvm->arch.n_used_mmu_pages > goal_nr_mmu_pages &&
                      !list_empty(&kvm->arch.active_mmu_pages)) {
                      struct kvm_mmu_page *page;
 
                      page = container_of(kvm->arch.active_mmu_pages.prev,
                                          struct kvm_mmu_page, link);
-                     used_pages -= kvm_mmu_zap_page(kvm, page);
-                     used_pages--;
+                     kvm->arch.n_used_mmu_pages -= kvm_mmu_zap_page(kvm, page);
+                     kvm->arch.n_used_mmu_pages--;

kvm->arch.n_used_mmu_pages is deaccounted for in kvm_mmu_zap_page -> kvm_mmu_free_page
already.

Note: this is the real meat of the patch set. It can be applied up to this point, and everything will probably be improved, at least a bit.

Of slab shrinkers, the VM code says:

* Note that 'shrink' will be passed nr_to_scan == 0 when the VM is
* querying the cache size, so a fastpath for that case is appropriate.

and it *means* it. Look at how it calls the shrinkers:

	nr_before = (*shrinker->shrink)(0, gfp_mask);
	shrink_ret = (*shrinker->shrink)(this_scan, gfp_mask);

So, if you do anything stupid in your shrinker, the VM will doubly punish you.

The mmu_shrink() function takes the global kvm_lock, then acquires every VM's kvm->mmu_lock in sequence. If we have 100 VMs, then we're going to take 101 locks. We do it twice, so each call takes 202 locks. If we're under memory pressure, we can have each cpu trying to do this. It can get really hairy, and we've seen lock spinning in mmu_shrink() be the dominant entry in profiles.

This is guaranteed to optimize at least half of those lock aquisitions away. It removes the need to take any of the locks when simply trying to count objects.

Signed-off-by Dave Hansen<[email protected]>

---

  linux-2.6.git-dave/arch/x86/kvm/mmu.c |   33 +++++++++++++++++++++++----------
  1 file changed, 23 insertions(+), 10 deletions(-)

diff -puN arch/x86/kvm/mmu.c~make_global_used_value arch/x86/kvm/mmu.c

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make_global_used_value +0 -0

@@ -891,6 +891,19 @@ static int is_empty_shadow_page(u64 *spt
  }

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make_global_used_value +2 -0

+}
+
 

arch/x86/kvm/mmu.c static int is_empty_shadow_page(u64 *spt · line 900

Quoted 8 lines · Dave Hansen

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make_global_used_value +7 -0

+/*
+ * This value is the sum of all of the kvm instances's
+ * kvm->arch.n_used_mmu_pages values.  We need a global,
+ * aggregate version in order to make the slab shrinker
+ * faster
+ */
+static unsigned int kvm_total_used_mmu_pages;

The variable needs to be at the top of the file.

arch/x86/kvm/mmu.c static int is_empty_shadow_page(u64 *spt · line 904

Quoted 5 lines

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make_global_used_value +4 -0

+static inline void kvm_mod_used_mmu_pages(struct kvm *kvm, int nr)
+{
+	kvm->arch.n_used_mmu_pages += nr;
+	kvm_total_used_mmu_pages += nr;

Needs an atomic operation, since there's no global lock here. To avoid bouncing this cacheline around, make the variable percpu and make readers take a sum across all cpus. Side benefit is that you no longer need an atomic but a local_t, which is considerably cheaper.

Quoted 13 lines

arch/x86/kvm/mmu.c static int is_empty_shadow_page(u64 *spt · line 904

Quoted 8 lines

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make_global_used_value +4 -0

+static inline void kvm_mod_used_mmu_pages(struct kvm *kvm, int nr)
+{
+	kvm->arch.n_used_mmu_pages += nr;
+	kvm_total_used_mmu_pages += nr;

Needs an atomic operation, since there's no global lock here. To avoid bouncing this cacheline around, make the variable percpu and make readers take a sum across all cpus. Side benefit is that you no longer need an atomic but a local_t, which is considerably cheaper.

That's a good point. All of the modifications are done under locks, but the fast path isn't any more. I'll fix it up.

arch/x86/kvm/mmu.c static int is_empty_shadow_page(u64 *spt · line 904

Quoted 5 lines

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make_global_used_value +4 -0

+static inline void kvm_mod_used_mmu_pages(struct kvm *kvm, int nr)
+{
+     kvm->arch.n_used_mmu_pages += nr;
+     kvm_total_used_mmu_pages += nr;

Needs an atomic operation, since there's no global lock here. To avoid bouncing this cacheline around, make the variable percpu and make readers take a sum across all cpus. Side benefit is that you no longer need an atomic but a local_t, which is considerably cheaper.

Quoted 11 lines · Avi Kivity

arch/x86/kvm/mmu.c static int is_empty_shadow_page(u64 *spt · line 904

Quoted 6 lines

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make_global_used_value +4 -0

+static inline void kvm_mod_used_mmu_pages(struct kvm *kvm, int nr)
+{
+     kvm->arch.n_used_mmu_pages += nr;
+     kvm_total_used_mmu_pages += nr;

Needs an atomic operation, since there's no global lock here. To avoid bouncing this cacheline around, make the variable percpu and make readers take a sum across all cpus. Side benefit is that you no longer need an atomic but a local_t, which is considerably cheaper.

We do have the stuff in:

include/linux/percpu_counter.h

the downside being that they're not precise and they're *HUGE* according to the comment. :)

It's actually fairly difficult to do a counter which is precise, scalable, and works well for small CPU counts when NR_CPUS is large. Do you mind if we just stick with a plain atomic_t for now?

mmu_shrink() is effectively single-threaded since the global kvm_lock is held over the entire function.

I beleive its only use here is for synchronization of the vm_list. Instead of using the kvm_lock to ensure consistency of the list, we instead obtain a kvm_get_kvm() reference. This keeps the kvm object on the vm_list while we shrink it.

Since we don't need the lock to maintain the list any more, we can drop it. We'll reacquire it if we need to get another object off.

This leads to a larger number of atomic ops, but reduces lock hold times: the typical latency vs. throughput debate.

diff -puN kernel/profile.c~optimize_shrinker-3 kernel/profile.c

kernel/profile.c renamed from kernel/profile.c~optimize_shrinker-3 +2 -0

@@ -314,6 +314,8 @@ void profile_hits(int type, void *__pc,
  	if (prof_on != type || !prof_buffer)
  		return;
  	pc = min((pc - (unsigned long)_stext)>>  prof_shift, prof_len - 1);
+	if ((pc == prof_len - 1)&&  printk_ratelimit())
+		printk("profile_hits(%d, %p, %d)\n", type, __pc, nr_hits);
  	i = primary = (pc&  (NR_PROFILE_GRP - 1))<<  PROFILE_GRPSHIFT;
  	secondary = (~(pc<<  1)&  (NR_PROFILE_GRP - 1))<<  PROFILE_GRPSHIFT;
  	cpu = get_cpu();

_

In a previous patch, we removed the 'nr_to_scan' tracking. It was not being used to track the number of objects scanned, so we stopped using it entirely. Here, we strart using it again.

The theory here is simple; if we already have the refcount and the kvm->mmu_lock, then we should do as much work as possible under the lock. The downside is that we're less fair about the KVM instances from which we reclaim. Each call to mmu_shrink() will tend to "pick on" one instance, after which it gets moved to the end of the list and left alone for a while.

If mmu_shrink() has already done a significant amount of scanning, the use of 'nr_to_scan' inside shrink_kvm_mmu() will also ensure that we do not over-reclaim when we have already done a lot of work in this call.

In the end, this patch defines a "scan" as:
1. An attempt to acquire a refcount on a 'struct kvm'
2. freeing a kvm mmu page

This would probably be most ideal if we can expose some of the work done by kvm_mmu_remove_some_alloc_mmu_pages() as also counting as scanning, but I think we have churned enough for the moment.

Signed-off-by Dave Hansen<[email protected]>

---

  linux-2.6.git-dave/arch/x86/kvm/mmu.c |   11 ++++++-----
  1 file changed, 6 insertions(+), 5 deletions(-)

diff -puN arch/x86/kvm/mmu.c~make-shrinker-more-aggressive arch/x86/kvm/mmu.c

Quoted 5 lines · Dave Hansen

In a previous patch, we removed the 'nr_to_scan' tracking. It was not being used to track the number of objects scanned, so we stopped using it entirely. Here, we strart using it again.

Quoted 8 lines

The theory here is simple; if we already have the refcount and the kvm->mmu_lock, then we should do as much work as possible under the lock. The downside is that we're less fair about the KVM instances from which we reclaim. Each call to mmu_shrink() will tend to "pick on" one instance, after which it gets moved to the end of the list and left alone for a while.

That also increases the latency hit, as well as a potential fault storm, on that instance. Spreading out is less efficient, but smoother.

Quoted 9 lines

If mmu_shrink() has already done a significant amount of scanning, the use of 'nr_to_scan' inside shrink_kvm_mmu() will also ensure that we do not over-reclaim when we have already done a lot of work in this call.

In the end, this patch defines a "scan" as:
1. An attempt to acquire a refcount on a 'struct kvm'
2. freeing a kvm mmu page

Quoted 4 lines

This would probably be most ideal if we can expose some of the work done by kvm_mmu_remove_some_alloc_mmu_pages() as also counting as scanning, but I think we have churned enough for the moment.

It usually removes one page.

Quoted 5 lines

diff -puN arch/x86/kvm/mmu.c~make-shrinker-more-aggressive arch/x86/kvm/mmu.c

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make-shrinker-more-aggressive +0 -0

@@ -2935,8 +2935,10 @@ static int shrink_kvm_mmu(struct kvm *kv
 

arch/x86/kvm/mmu.c static int shrink_kvm_mmu(struct kvm *kv · line 2942

Quoted 9 lines

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make-shrinker-more-aggressive +4 -2

  	idx = srcu_read_lock(&kvm->srcu);
  	spin_lock(&kvm->mmu_lock);
-	if (kvm->arch.n_used_mmu_pages>  0)
-		freed_pages = kvm_mmu_remove_some_alloc_mmu_pages(kvm);
+	while (nr_to_scan>  0&&  kvm->arch.n_used_mmu_pages>  0) {
+		freed_pages += kvm_mmu_remove_some_alloc_mmu_pages(kvm);
+		nr_to_scan--;
+	}
 

What tree are you patching?

Quoted 15 lines

Quoted 15 lines

If mmu_shrink() has already done a significant amount of scanning, the use of 'nr_to_scan' inside shrink_kvm_mmu() will also ensure that we do not over-reclaim when we have already done a lot of work in this call.

In the end, this patch defines a "scan" as:
1. An attempt to acquire a refcount on a 'struct kvm'
2. freeing a kvm mmu page

This would probably be most ideal if we can expose some of the work done by kvm_mmu_remove_some_alloc_mmu_pages() as also counting as scanning, but I think we have churned enough for the moment.

Quoted 2 lines

It usually removes one page.

Does it always just go right now and free it, or is there any real scanning that has to go on?

Quoted 5 lines

Quoted 5 lines

diff -puN arch/x86/kvm/mmu.c~make-shrinker-more-aggressive arch/x86/kvm/mmu.c

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make-shrinker-more-aggressive +0 -0

@@ -2935,8 +2935,10 @@ static int shrink_kvm_mmu(struct kvm *kv
 

Quoted 12 lines

arch/x86/kvm/mmu.c static int shrink_kvm_mmu(struct kvm *kv

Quoted 10 lines

arch/x86/kvm/mmu.c renamed from arch/x86/kvm/mmu.c~make-shrinker-more-aggressive +4 -2

   	idx = srcu_read_lock(&kvm->srcu);
   	spin_lock(&kvm->mmu_lock);
-	if (kvm->arch.n_used_mmu_pages>   0)
-		freed_pages = kvm_mmu_remove_some_alloc_mmu_pages(kvm);
+	while (nr_to_scan>   0&&   kvm->arch.n_used_mmu_pages>   0) {
+		freed_pages += kvm_mmu_remove_some_alloc_mmu_pages(kvm);
+		nr_to_scan--;
+	}
 
 

What tree are you patching?

These applied to Linus's latest as of yesterday.

Quoted 15 lines · Avi Kivity

Quoted 5 lines · Dave Hansen

In a previous patch, we removed the 'nr_to_scan' tracking. It was not being used to track the number of objects scanned, so we stopped using it entirely. Here, we strart using it again.

Quoted 8 lines

The theory here is simple; if we already have the refcount and the kvm->mmu_lock, then we should do as much work as possible under the lock. The downside is that we're less fair about the KVM instances from which we reclaim. Each call to mmu_shrink() will tend to "pick on" one instance, after which it gets moved to the end of the list and left alone for a while.

Quoted 2 lines

That also increases the latency hit, as well as a potential fault storm, on that instance. Spreading out is less efficient, but smoother.

This is probably something that we need to go back and actually measure. My suspicion is that, when memory fills up and this shrinker is getting called a lot, it will be naturally fair. That list gets shuffled around enough, and mmu_shrink() called often enough that no VMs get picked on too unfairly.

I'll go back and see if I can quantify this a bit, though.

Quoted 21 lines · Dave Hansen

Quoted 16 lines · Avi Kivity

Quoted 5 lines · Dave Hansen

In a previous patch, we removed the 'nr_to_scan' tracking. It was not being used to track the number of objects scanned, so we stopped using it entirely. Here, we strart using it again.

Quoted 9 lines

The theory here is simple; if we already have the refcount and the kvm->mmu_lock, then we should do as much work as possible under the lock. The downside is that we're less fair about the KVM instances from which we reclaim. Each call to mmu_shrink() will tend to "pick on" one instance, after which it gets moved to the end of the list and left alone for a while.

Quoted 3 lines

That also increases the latency hit, as well as a potential fault storm, on that instance. Spreading out is less efficient, but smoother.

Quoted 8 lines

This is probably something that we need to go back and actually measure. My suspicion is that, when memory fills up and this shrinker is getting called a lot, it will be naturally fair. That list gets shuffled around enough, and mmu_shrink() called often enough that no VMs get picked on too unfairly.

I'll go back and see if I can quantify this a bit, though.

The shrink _query_ (mmu_shrink() with nr_to_scan=0) code is called really, really often. Like 5,000-10,000 times a second during lots of VM pressure. But, it's almost never called on to actually shrink anything.

Over the 20 minutes or so that I tested, I saw about 700k calls to mmu_shrink(). But, only 6 (yes, six) calls that had a non-zero nr_to_scan. I'm not sure whether this is because of the .seeks argument to the shrinker or what, but the slab code stays far, far away from making mmu_shrink() do much real work.

That changes a few things. I bet all the contention we were seeing was just from nr_to_scan=0 calls and not from actual shrink operations. Perhaps we should just stop this set after patch 4.

Quoted 4 lines

That changes a few things. I bet all the contention we were seeing was just from nr_to_scan=0 calls and not from actual shrink operations. Perhaps we should just stop this set after patch 4.

At the very least, we should re-measure things.

Quoted 5 lines · Avi Kivity

Quoted 5 lines

That changes a few things. I bet all the contention we were seeing was just from nr_to_scan=0 calls and not from actual shrink operations. Perhaps we should just stop this set after patch 4.

Quoted 2 lines

At the very least, we should re-measure things.

Sure. I'll go back to the folks that found this in the first place and see how these patches affect the contention we were seeing.

Quoted 5 lines · Dave Hansen

Quoted 4 lines · Avi Kivity

Quoted 4 lines

That changes a few things. I bet all the contention we were seeing was just from nr_to_scan=0 calls and not from actual shrink operations. Perhaps we should just stop this set after patch 4.

Quoted 4 lines

Quoted 2 lines

At the very least, we should re-measure things.

Sure. I'll go back to the folks that found this in the first place and see how these patches affect the contention we were seeing.

Dave, how did those tests go?

Quoted 3 lines

Dave, how did those tests go?

Still waiting on the folks that found this in the first place to reproduce it and see if the patches help. I'll go nudge them some more.

This is a big RFC for the moment. These need a bunch more runtime testing.

--

We've seen contention in the mmu_shrink() function.

This patch
set reworks it to hopefully be more scalable to large numbers of CPUs, as well as large numbers of running VMs.

The patches are ordered with increasing invasiveness.

These seem to boot and run fine. I'm running about 40 VMs at once, while doing "echo 3> /proc/sys/vm/drop_caches", and killing/restarting VMs constantly.

Seems to be relatively stable, and seems to keep the numbers of kvm_mmu_page_header objects down.

Quoted 4 lines · Dave Hansen

These seem to boot and run fine. I'm running about 40 VMs at once, while doing "echo 3> /proc/sys/vm/drop_caches", and killing/restarting VMs constantly.

Will drop_caches actually shrink the kvm caches too? If so we probably need to add that to autotest since it's a really good stress test for the mmu.

Quoted 3 lines

Seems to be relatively stable, and seems to keep the numbers of kvm_mmu_page_header objects down.

That's no necessarily a good thing, those things are expensive to recreate. Of course, when we do need to reclaim them, that should be efficient.

We also do a very bad job of selecting which page to reclaim. We need to start using the accessed bit on sptes that point to shadow page tables, and then look those up and reclaim unreferenced pages sooner. With shadow paging there can be tons of unsync pages that are basically unused and can be reclaimed at no cost to future runtime.

Quoted 7 lines · Avi Kivity

Quoted 5 lines · Dave Hansen

These seem to boot and run fine. I'm running about 40 VMs at
once, while doing "echo 3> /proc/sys/vm/drop_caches", and
killing/restarting VMs constantly.

Quoted 4 lines

Will drop_caches actually shrink the kvm caches too? If so we probably need to add that to autotest since it's a really good stress test for the mmu.

I'm completely sure.

I crashed my machines several times this way
during testing.