kvm: Improving directed yield in PLE handler

Currently Pause Loop Exit (PLE) handler is doing directed yield to a random vcpu on pl-exit. We already have filtering while choosing the candidate to yield_to. This change adds more checks while choosing a candidate to yield_to.

On a large vcpu guests, there is a high probability of yielding to the same vcpu who had recently done a pause-loop exit. Such a yield can lead to the vcpu spinning again.

The patchset keeps track of the pause loop exit and gives chance to a vcpu which has:

(a) Not done pause loop exit at all (probably he is preempted lock-holder)

(b) vcpu skipped in last iteration because it did pause loop exit, and probably has become eligible now (next eligible lock holder)

This concept also helps in cpu relax interception cases which use same handler.

Changes since v2:
- Move ple structure to common code (Avi)
- rename pause_loop_exited to cpu_relax_intercepted (Avi)
- add config HAVE_KVM_CPU_RELAX_INTERCEPT (Avi)
- Drop superfluous curly braces (Ingo)

Changes since v1:
- Add more documentation for structure and algorithm and Rename plo ==> ple (Rik).
- change dy_eligible initial value to false. (otherwise very first directed yield will not be skipped. (Nikunj)
- fixup signoff/from issue

Future enhancements:
(1) Currently we have a boolean to decide on eligibility of vcpu. It would be nice if I get feedback on guest (>32 vcpu) whether we can improve better with integer counter. (with counter = say f(log n )).

(2) We have not considered system load during iteration of vcpu. With that information we can limit the scan and also decide whether schedule() is better. [ I am able to use #kicked vcpus to decide on this But may be there are better ideas like information from global loadavg.]

(3) We can exploit this further with PV patches since it also knows about next eligible lock-holder.

Summary: There is a very good improvement for moderate / no over-commit scenario
for kvm based guest on PLE machine.

Results: kernbench improves by around 30%, 6% for 1x,2x
ebizzy improves by around 87%, 23% for 1x,2x

Links
V1: https://lkml.org/lkml/2012/7/9/32

V2: https://lkml.org/lkml/2012/7/10/392

Raghavendra K T (3):
config: Add config to support ple or cpu relax optimzation kvm : Note down when cpu relax intercepted or pause loop exited kvm : Choose a better candidate for directed yield

---
 arch/s390/kvm/Kconfig    |    1 +
 arch/x86/kvm/Kconfig     |    1 +
 include/linux/kvm_host.h |   12 ++++++++++++
 virt/kvm/Kconfig         |    3 +++
 virt/kvm/kvm_main.c      |   38 ++++++++++++++++++++++++++++++++++++++
 5 files changed, 55 insertions(+), 0 deletions(-)

From: Raghavendra K T <[email protected]>

---

 arch/s390/kvm/Kconfig |    1 +
 arch/x86/kvm/Kconfig  |    1 +
 virt/kvm/Kconfig      |    3 +++
 3 files changed, 5 insertions(+), 0 deletions(-)

index 78eb984..a6e2677 100644
@@ -21,6 +21,7 @@ config KVM
 	depends on HAVE_KVM && EXPERIMENTAL
 	select PREEMPT_NOTIFIERS
 	select ANON_INODES
+	select HAVE_KVM_CPU_RELAX_INTERCEPT
 	---help---
 	  Support hosting paravirtualized guest machines using the SIE
 	  virtualization capability on the mainframe. This should work

index a28f338..45c044f 100644
@@ -37,6 +37,7 @@ config KVM
 	select TASK_DELAY_ACCT
 	select PERF_EVENTS
 	select HAVE_KVM_MSI
+	select HAVE_KVM_CPU_RELAX_INTERCEPT
 	---help---
 	  Support hosting fully virtualized guest machines using hardware
 	  virtualization extensions.  You will need a fairly recent

index 28694f4..d01b24b 100644
@@ -21,3 +21,6 @@ config KVM_ASYNC_PF
 
 config HAVE_KVM_MSI
        bool
+
+config HAVE_KVM_CPU_RELAX_INTERCEPT
+       bool

From: Raghavendra K T <[email protected]>

Noting pause loop exited or cpu relax intercepted vcpu helps in filtering right candidate to yield. Wrong selection of vcpu; i.e., a vcpu that just did a pl-exit or cpu relax intercepted may contribute to performance degradation.

---
v2 patches were

 include/linux/kvm_host.h |   12 ++++++++++++
 virt/kvm/kvm_main.c      |    4 ++++
 2 files changed, 16 insertions(+), 0 deletions(-)

index c446435..4ec1cf0 100644
@@ -183,6 +183,18 @@ struct kvm_vcpu {
 	} async_pf;
 #endif
 
+#ifdef CONFIG_HAVE_KVM_CPU_RELAX_INTERCEPT
+	/*
+	 * Cpu relax intercept or pause loop exit optimization
+	 * cpu_relax_intercepted: set when a vcpu does a pause loop exit
+	 *  or cpu relax intercepted.
+	 * dy_eligible: indicates whether vcpu is eligible for directed yield.
+	 */
+	struct {
+		bool cpu_relax_intercepted;
+		bool dy_eligible;
+	} ple;
+#endif
 	struct kvm_vcpu_arch arch;
 };
 

index 7e14068..4ec0120 100644
@@ -235,6 +235,8 @@ int kvm_vcpu_init(struct kvm_vcpu *vcpu, struct kvm *kvm, unsigned id)
 		goto fail;
 	}
 	vcpu->run = page_address(page);
+	vcpu->ple.cpu_relax_intercepted = false;
+	vcpu->ple.dy_eligible = false;
 
 	r = kvm_arch_vcpu_init(vcpu);
 	if (r < 0)

@@ -1577,6 +1579,7 @@ void kvm_vcpu_on_spin(struct kvm_vcpu *me)
 	int pass;
 	int i;
 
+	me->ple.cpu_relax_intercepted = true;
 	/*
 	 * We boost the priority of a VCPU that is runnable but not
 	 * currently running, because it got preempted by something

@@ -1602,6 +1605,7 @@ void kvm_vcpu_on_spin(struct kvm_vcpu *me)
 			}
 		}
 	}
+	me->ple.cpu_relax_intercepted = false;
 }
 EXPORT_SYMBOL_GPL(kvm_vcpu_on_spin);
 

[...]

[...]

Yes! I forgot about archs in init function.
How about having
#ifdef CONFIG_HAVE_KVM_CPU_RELAX_INTERCEPT
vcpu->ple.cpu_relax_intercepted = false;
vcpu->ple.dy_eligible = false;
#endif

This would solve all the problem.

currently vcpu_on_spin is used only by x86 and s390. so if some other arch in future uses vcpu_on_spin, I believe they also have to enable CONFIG_HAVE_KVM_CPU_RELAX_INTERCEPT
what do you think?

otherwise we have to add hook everywhere

No, you need to mask all places....

...because this function is compiled no matter if called or not.

As I already said, can you have a look at using access functions?

Yes. will do.

How about moving this struct definition outside the CONFIG. i.e it would be available by default.
If any arch cares to use vcpu_on_spin(), they would get the benefit by default.

This would avoid all the CONFIG magic that we would have to do otherwise.

Thanks and Regards
Srikar

Okay, after discussing with Christian,
- even if ppc uses vcpu_on spin we will still be left with ia64 (though broken currently) and arm (is on way).
- those who want to opt-out of this optimization but still wish to use vcpu_spin, we have flexibility.

So with that in mind I am spinning V4 with CONFIG_HAVE_KVM_CPU_RELAX_INTERCEPT. Let us see how it goes.

From: Raghavendra K T <[email protected]>

Currently, on a large vcpu guests, there is a high probability of yielding to the same vcpu who had recently done a pause-loop exit or cpu relax intercepted. Such a yield can lead to the vcpu spinning again and hence degrade the performance.

The patchset keeps track of the pause loop exit/cpu relax interception and gives chance to a vcpu which:
(a) Has not done pause loop exit or cpu relax intercepted at all (probably he is preempted lock-holder)
(b) Was skipped in last iteration because it did pause loop exit or cpu relax intercepted, and probably has become eligible now (next eligible lock holder)

---
v2 patches were:

 virt/kvm/kvm_main.c |   34 ++++++++++++++++++++++++++++++++++
 1 files changed, 34 insertions(+), 0 deletions(-)

index 4ec0120..50f6e60 100644
@@ -1570,6 +1570,38 @@ bool kvm_vcpu_yield_to(struct kvm_vcpu *target)
 }
 EXPORT_SYMBOL_GPL(kvm_vcpu_yield_to);
 
+/*
+ * Helper that checks whether a VCPU is eligible for directed yield.
+ * Most eligible candidate to yield is decided by following heuristics:
+ *
+ *  (a) VCPU which has not done pl-exit or cpu relax intercepted recently
+ *  (preempted lock holder), indicated by @cpu_relax_intercepted.
+ *  Set at the beiginning and cleared at the end of interception/PLE handler.
+ *
+ *  (b) VCPU which has done pl-exit/ cpu relax intercepted but did not get
+ *  chance last time (mostly it has become eligible now since we have probably
+ *  yielded to lockholder in last iteration. This is done by toggling
+ *  @dy_eligible each time a VCPU checked for eligibility.)
+ *
+ *  Yielding to a recently pl-exited/cpu relax intercepted VCPU before yielding
+ *  to preempted lock-holder could result in wrong VCPU selection and CPU
+ *  burning. Giving priority for a potential lock-holder increases lock
+ *  progress.
+ */
+bool kvm_vcpu_check_and_update_eligible(struct kvm_vcpu *vcpu)
+{
+	bool eligible;
+
+	eligible = !vcpu->ple.cpu_relax_intercepted ||
+			(vcpu->ple.cpu_relax_intercepted &&
+			 vcpu->ple.dy_eligible);
+
+	if (vcpu->ple.cpu_relax_intercepted)
+		vcpu->ple.dy_eligible = !vcpu->ple.dy_eligible;
+
+	return eligible;
+}
+
 void kvm_vcpu_on_spin(struct kvm_vcpu *me)
 {
 	struct kvm *kvm = me->kvm;

@@ -1598,6 +1630,8 @@ void kvm_vcpu_on_spin(struct kvm_vcpu *me)
 				continue;
 			if (waitqueue_active(&vcpu->wq))
 				continue;
+			if (!kvm_vcpu_check_and_update_eligible(vcpu))
+				continue;
 			if (kvm_vcpu_yield_to(vcpu)) {
 				kvm->last_boosted_vcpu = i;
 				yielded = 1;

The patches are tested on x86 only since I don't have access to s390 machine. Please let me know if changes are ok on s390.

From: Raghavendra K T <[email protected]>

Currently, on a large vcpu guests, there is a high probability of yielding to the same vcpu who had recently done a pause-loop exit or cpu relax intercepted. Such a yield can lead to the vcpu spinning again and hence degrade the performance.

The patchset keeps track of the pause loop exit/cpu relax interception and gives chance to a vcpu which:
(a) Has not done pause loop exit or cpu relax intercepted at all (probably he is preempted lock-holder)
(b) Was skipped in last iteration because it did pause loop exit or cpu relax intercepted, and probably has become eligible now (next eligible lock holder)

---
V2 was:

Changelog: Added comment on locking as suggested by Avi

 include/linux/kvm_host.h |    5 +++++
 virt/kvm/kvm_main.c      |   42 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 47 insertions(+), 0 deletions(-)

index 34ce296..952427d 100644
@@ -923,6 +923,11 @@ static inline void kvm_vcpu_set_dy_eligible(struct kvm_vcpu *vcpu, bool val)
 {
 }
 
+static inline bool kvm_vcpu_eligible_for_directed_yield(struct kvm_vcpu *vcpu)
+{
+	return true;
+}
+
 #endif /* CONFIG_HAVE_KVM_CPU_RELAX_INTERCEPT */
 #endif