Paravirt-spinlock implementation for KVM guests (Version 0)

Add KVM hypercall for yielding vcpu timeslice.

Signed-off-by Srivatsa Vaddagiri<[email protected]>

---
  arch/x86/include/asm/kvm_para.h |    1 +
  arch/x86/kvm/x86.c              |    7 ++++++-
  include/linux/kvm.h             |    1 +
  include/linux/kvm_para.h        |    1 +
  4 files changed, 9 insertions(+), 1 deletion(-)

Index: current/arch/x86/include/asm/kvm_para.h
===================================================================

arch/x86/include/asm/kvm_para.h +1 -0

@@ -16,6 +16,7 @@
  #define KVM_FEATURE_CLOCKSOURCE		0
  #define KVM_FEATURE_NOP_IO_DELAY	1
  #define KVM_FEATURE_MMU_OP		2
+#define KVM_FEATURE_YIELD		4
  /* This indicates that the new set of kvmclock msrs
   * are available. The use of 0x11 and 0x12 is deprecated
   */

Index: current/arch/x86/kvm/x86.c
===================================================================

arch/x86/kvm/x86.c +6 -1

@@ -1618,6 +1618,7 @@ int kvm_dev_ioctl_check_extension(long e
  	case KVM_CAP_PCI_SEGMENT:
  	case KVM_CAP_DEBUGREGS:
  	case KVM_CAP_X86_ROBUST_SINGLESTEP:
+	case KVM_CAP_YIELD_HYPERCALL:
  		r = 1;
  		break;
  	case KVM_CAP_COALESCED_MMIO:

@@ -1993,7 +1994,8 @@ static void do_cpuid_ent(struct kvm_cpui
  		entry->eax = (1<<  KVM_FEATURE_CLOCKSOURCE) |
  			     (1<<  KVM_FEATURE_NOP_IO_DELAY) |
  			     (1<<  KVM_FEATURE_CLOCKSOURCE2) |
-			     (1<<  KVM_FEATURE_CLOCKSOURCE_STABLE_BIT);
+			     (1<<  KVM_FEATURE_CLOCKSOURCE_STABLE_BIT) |
+			     (1<<  KVM_FEATURE_YIELD);
  		entry->ebx = 0;
  		entry->ecx = 0;
  		entry->edx = 0;

@@ -4245,6 +4247,9 @@ int kvm_emulate_hypercall(struct kvm_vcp
  	case KVM_HC_MMU_OP:
  		r = kvm_pv_mmu_op(vcpu, a0, hc_gpa(vcpu, a1, a2),&ret);
  		break;
+	case KVM_HC_YIELD:
+		ret = 0;
+		yield();
  	default:
  		ret = -KVM_ENOSYS;
  		break;

Index: current/include/linux/kvm.h
===================================================================

include/linux/kvm.h +1 -0

@@ -524,6 +524,7 @@ struct kvm_enable_cap {
  #define KVM_CAP_PPC_OSI 52
  #define KVM_CAP_PPC_UNSET_IRQ 53
  #define KVM_CAP_ENABLE_CAP 54
+#define KVM_CAP_YIELD_HYPERCALL	55
 
  #ifdef KVM_CAP_IRQ_ROUTING
 

Index: current/include/linux/kvm_para.h
===================================================================

include/linux/kvm_para.h +1 -0

@@ -17,6 +17,7 @@
 
  #define KVM_HC_VAPIC_POLL_IRQ		1
  #define KVM_HC_MMU_OP			2
+#define KVM_HC_YIELD                    3
 
  /*
   * hypercalls use architecture specific

Quoted 1 line · Srivatsa Vaddagiri

Add KVM hypercall for yielding vcpu timeslice.

Can you do a directed yield?

Quoted 3 lines · Jeremy Fitzhardinge

Quoted 1 line · Srivatsa Vaddagiri

Add KVM hypercall for yielding vcpu timeslice.

Can you do a directed yield?

We don't have that support yet in Linux scheduler.

Also I feel it would be more
useful when the target vcpu and yielding vcpu are on the same physical cpu, rather than when they are on separate cpus. With latter, yielding (or donating) timeslice need not ensure that target vcpu runs immediately

and also I suspect fairness issues needs to be tackled as well (large number of waiters shouldn't boot a lock-holders time slice too much that it gets a larger share).

Quoted 2 lines

Quoted 1 line

Can you do a directed yield?

We don't have that support yet in Linux scheduler.

If you think it's useful, it would be good to design it into the interface, and fall back to ordinary yield if the host doesn't support it.

A big advantage of directed yield vs yield is that you conserve resources within a VM; a simple yield will cause the guest to drop its share of cpu to other guest.

Quoted 10 lines · Avi Kivity

Quoted 2 lines

Quoted 1 line

Can you do a directed yield?

We don't have that support yet in Linux scheduler.

If you think it's useful, it would be good to design it into the interface, and fall back to ordinary yield if the host doesn't support it.

A big advantage of directed yield vs yield is that you conserve resources within a VM; a simple yield will cause the guest to drop its share of cpu to other guest.

Hmm .. I see possibility of modifying yield to reclaim its "lost" timeslice when its scheduled next as well. Basically remember what timeslice we have given up and add that as its "bonus" when it runs next. That would keep the dynamics of yield donation/reclaim local to the (physical) cpu and IMHO is less complex than dealing with directed yield between tasks located across different physical cpus. That would also address the fairness issue with yield you are pointing at?

Quoted 1 line · Srivatsa Vaddagiri

Add KVM hypercall for yielding vcpu timeslice.

Can you do a directed yield?

Quoted 5 lines · Jeremy Fitzhardinge

Quoted 1 line · Srivatsa Vaddagiri

Add KVM hypercall for yielding vcpu timeslice.

Can you do a directed yield?

A problem with directed yield is figuring out who to yield to. One idea is to look for a random vcpu that is not running and donate some runtime to it. In the best case, it's the lock holder and we cause it to start running. Middle case it's not the lock holder, but we lose enough runtime to stop running, so at least we don't waste cpu. Worst case we continue running not having woken the lock holder. Spin again, yield again hoping to find the right vcpu.

Quoted 8 lines

A problem with directed yield is figuring out who to yield to. One idea is to look for a random vcpu that is not running and donate some runtime to it. In the best case, it's the lock holder and we cause it to start running. Middle case it's not the lock holder, but we lose enough runtime to stop running, so at least we don't waste cpu. Worst case we continue running not having woken the lock holder. Spin again, yield again hoping to find the right vcpu.

It's been quite some time, but played with directed yielding for Xen[1] and we were looking to model the POWER directed yield (H_CONFER) where the lock holding vcpu was indiciated in the spinlock. When acquiring the lock, record the vcpu id. When another vcpu attempts to acquire the lock if it can't it can yield its time to the lock holder.

Quoted 5 lines · Jeremy Fitzhardinge

Quoted 1 line · Srivatsa Vaddagiri

Add KVM hypercall for yielding vcpu timeslice.

Can you do a directed yield?

A problem with directed yield is figuring out who to yield to. One idea is to look for a random vcpu that is not running and donate some runtime to it. In the best case, it's the lock holder and we cause it to start running. Middle case it's not the lock holder, but we lose enough runtime to stop running, so at least we don't waste cpu. Worst case we continue running not having woken the lock holder. Spin again, yield again hoping to find the right vcpu.

Paravirtual spinlock implementation for KVM guests, based heavily on Xen guest's spinlock implementation.

arch/x86/kernel/kvm.c +7 -0

+
+static struct spinlock_stats
+{
+	u64 taken;
+	u32 taken_slow;
+
+	u64 released;

arch/x86/kernel/kvm.c +54 -0

+struct kvm_spinlock {
+	unsigned char lock;		/* 0 ->  free; 1 ->  locked */
+	unsigned short spinners;	/* count of waiting cpus */
+};
+
+/*
+ * Mark a cpu as interested in a lock.  Returns the CPU's previous
+ * lock of interest, in case we got preempted by an interrupt.
+ */
+static inline void spinning_lock(struct kvm_spinlock *pl)
+{
+	asm(LOCK_PREFIX " incw %0"
+	    : "+m" (pl->spinners) : : "memory");
+}
+
+/*
+ * Mark a cpu as no longer interested in a lock.  Restores previous
+ * lock of interest (NULL for none).
+ */
+static inline void unspinning_lock(struct kvm_spinlock *pl)
+{
+	asm(LOCK_PREFIX " decw %0"
+	    : "+m" (pl->spinners) : : "memory");
+}
+
+static int kvm_spin_is_locked(struct arch_spinlock *lock)
+{
+	struct kvm_spinlock *sl = (struct kvm_spinlock *)lock;
+
+	return sl->lock != 0;
+}
+
+static int kvm_spin_is_contended(struct arch_spinlock *lock)
+{
+	struct kvm_spinlock *sl = (struct kvm_spinlock *)lock;
+
+	/* Not strictly true; this is only the count of contended
+	   lock-takers entering the slow path. */
+	return sl->spinners != 0;
+}
+
+static int kvm_spin_trylock(struct arch_spinlock *lock)
+{
+	struct kvm_spinlock *sl = (struct kvm_spinlock *)lock;
+	u8 old = 1;
+
+	asm("xchgb %b0,%1"
+	    : "+q" (old), "+m" (sl->lock) : : "memory");
+
+	return old == 0;
+}
+
+static noinline int kvm_spin_lock_slow(struct arch_spinlock *lock)
+{

Quoted 15 lines · Srivatsa Vaddagiri

Paravirtual spinlock implementation for KVM guests, based heavily on Xen guest's spinlock implementation.

arch/x86/kernel/kvm.c +11 -0

+
+static struct spinlock_stats
+{
+    u64 taken;
+    u32 taken_slow;
+
+    u64 released;
+
+#define HISTO_BUCKETS    30
+    u32 histo_spin_total[HISTO_BUCKETS+1];
+    u32 histo_spin_spinning[HISTO_BUCKETS+1];

arch/x86/kernel/kvm.c void __init kvm_guest_init(void) · line 263

Quoted 6 lines

arch/x86/kernel/kvm.c +6 -0

+    u32 histo_spin_blocked[HISTO_BUCKETS+1];
+
+    u64 time_total;
+    u64 time_spinning;
+    u64 time_blocked;
+} spinlock_stats;

Could these be replaced by tracepoints when starting to spin/stopping spinning etc? Then userspace can reconstruct the histogram as well as see which locks are involved and what call paths.

Quoted 16 lines · Avi Kivity

Quoted 15 lines · Srivatsa Vaddagiri

Paravirtual spinlock implementation for KVM guests, based heavily on Xen guest's spinlock implementation.

arch/x86/kernel/kvm.c +11 -0

+
+static struct spinlock_stats
+{
+    u64 taken;
+    u32 taken_slow;
+
+    u64 released;
+
+#define HISTO_BUCKETS    30
+    u32 histo_spin_total[HISTO_BUCKETS+1];
+    u32 histo_spin_spinning[HISTO_BUCKETS+1];

Quoted 8 lines

arch/x86/kernel/kvm.c void __init kvm_guest_init(void) · line 263

Quoted 6 lines

arch/x86/kernel/kvm.c +6 -0

+    u32 histo_spin_blocked[HISTO_BUCKETS+1];
+
+    u64 time_total;
+    u64 time_spinning;
+    u64 time_blocked;
+} spinlock_stats;

Could these be replaced by tracepoints when starting to spin/stopping spinning etc? Then userspace can reconstruct the histogram as well as see which locks are involved and what call paths.

Unfortunately not; the tracing code uses spinlocks.

(TBH I haven't actually tried, but I did give the code an eyeball to this end.)

Quoted 26 lines · Jeremy Fitzhardinge

Quoted 24 lines · Avi Kivity

Quoted 11 lines · Srivatsa Vaddagiri

Paravirtual spinlock implementation for KVM guests, based heavily on Xen guest's spinlock implementation.

arch/x86/kernel/kvm.c +7 -0

+
+static struct spinlock_stats
+{
+    u64 taken;
+    u32 taken_slow;
+
+    u64 released;

arch/x86/kernel/kvm.c void __init kvm_guest_init(void) · line 263

Quoted 10 lines

arch/x86/kernel/kvm.c +10 -0

+
+#define HISTO_BUCKETS    30
+    u32 histo_spin_total[HISTO_BUCKETS+1];
+    u32 histo_spin_spinning[HISTO_BUCKETS+1];
+    u32 histo_spin_blocked[HISTO_BUCKETS+1];
+
+    u64 time_total;
+    u64 time_spinning;
+    u64 time_blocked;
+} spinlock_stats;

Could these be replaced by tracepoints when starting to spin/stopping spinning etc? Then userspace can reconstruct the histogram as well as see which locks are involved and what call paths.

Quoted 3 lines

Unfortunately not; the tracing code uses spinlocks.

(TBH I haven't actually tried, but I did give the code an eyeball to this end.)

Hm. The tracing code already uses a specialized lock (arch_spinlock_t), perhaps we can make this lock avoid the tracing?

It's really sad, btw, there's all those nice lockless ring buffers and then a spinlock for ftrace_vbprintk(), instead of a per-cpu buffer.

This patch-series implements paravirt-spinlock implementation for KVM guests, based heavily on Xen's implementation.

I tried to refactor Xen's spinlock
implementation to make it common for both Xen and KVM - but found that few differences between Xen and KVM (Xen has the ability to block on a particular event/irq for example) _and_ the fact that the guest kernel can be compiled to support both Xen and KVM hypervisors (CONFIG_XEN and CONFIG_KVM_GUEST can both be turned on) makes the "common" code a eye-sore. There will have to be:

	if (xen) {
		...
	} else if (kvm) {
		..
	}

or possibly:

alternative(NOP, some_xen_specific_call, ....)

type of code in the common implementation.

For the time-being, I have made this KVM-specific only. At somepoint in future, I hope this can be made common between Xen/KVM.

More background and results for this patch below:

What is the Problem being solved?
=================================

Guest operating system can be preempted by hypervisor at any arbitrary point. There is no mechanism (that I know of) where guest OS can disable preemption for certain periods of time. One noticeable effect of this is with regard to locking. Lets say one virtual-cpu of a guest (VCPUA) grabs a spinlock and before it could relinquish the lock is preempted by hypervisor. The time-of-preemption (when the virtual cpu is off the cpu) can be quite large. In that period, if another of guest OS's virtual cpu (VCPUB) tries grabbing the same lock, it could end up spin-waiting a _long_ time, burning cycles unnecessarily. To add to the woes, VCPUB may actually be waiting for VCPUA to yield before it can run on the same (physical) cpu. This is termed as the "lock-holder preemption" (LHP) problem. The effect of it can be quite serious. For ex:
http://lkml.org/lkml/2010/4/11/108 reported 80% performance degradation because of an issue attributed to LHP problem.

Solutions
=========

There are several solutions to this problem.

a. Realize that a lock-holder could have been preempted, and avoid spin-waiting
too long. Instead, yield cycles (to the lock-holder perhaps). This is a common solution adopted by most paravirtualized-guests (Xen, s390, powerpc).

b. Avoid preempting a lock-holder while its holding a (spin-) lock.

In this scheme, guest OS can hint (set some flag in memory shared with hypervisor) whenever its holding a lock and hypervisor could defer preempting the guest vcpu when its holding a lock. With this scheme, we should never have a lock-acquiring vcpu spin on a preempted vcpu to release its lock. If ever it spins, its because somebody *currently running* is holding the lock - and hence it won't have to spin-wait too long. IOW we are pro-actively trying to prevent the LHP problem from occuring in the first place. This should improve job turnaround time for some workloads. [1] has some results based on this approach.

c. Share run-status of vcpu with guests. This could be used to optimize
routines like mutex_spin_on_owner().

Hypervisor could share run-status of vcpus in guest kernel memory. This would allow us to optimize routines like mutex_spin_on_owner() - we don't spin-wait if we relaize that the target vcpu has been preempted.

a) and c) are about dealing with the LHP problem, while b) is about preventing the problem from happening.

Scenario A:

	W/o patch		W/ Patch		Difference
	Avg  (std-dev)		Avg. (std-dev)

1:	273.270  (1.051)	251.613 (1.155)		7.9%
2:	541.343  (57.317)	443.400 (2.832)		18.1%
3:	819.160  (9.218)	642.393 (2.646)		21.6%

4: 1020.493 (34.743) 839.327 (0.658) 17.8%

Scenario B:

1: 276.947 (0.644) 248.397 (1.563) 10.3%
2: 500.723 (5.694) 438.957 (6.112) 12.33%
3: 725.687 (5.267) 641.317 (3.902) 11.62%
4: 973.910 (21.712) 836.853 (2.754) 14.07%

Scenario C:

1:	564.610  (12.055)    	420.510 (2.598)		25.52%
2:	750.867  (5.139)	618.570 (2.914)		17.61%
3:	950.150  (13.496)      	813.803 (1.872)		14.35%

4: 1125.027 (5.337) 1007.63 (5.707) 10.43%

IMO this is good improvement with the patchset applied.

Quoted 14 lines

I tried to refactor Xen's spinlock
implementation to make it common for both Xen and KVM - but found that few differences between Xen and KVM (Xen has the ability to block on a particular event/irq for example) _and_ the fact that the guest kernel can be compiled to support both Xen and KVM hypervisors (CONFIG_XEN and CONFIG_KVM_GUEST can both be turned on) makes the "common" code a eye-sore. There will have to be:

	if (xen) {
		...
	} else if (kvm) {
		..
	}

Quoted 5 lines

or possibly:

alternative(NOP, some_xen_specific_call, ....)

type of code in the common implementation.

No, that doesn't look like a good approach. It suggests the apparently commonality isn't really there.

Quoted 2 lines

For the time-being, I have made this KVM-specific only. At somepoint in future, I hope this can be made common between Xen/KVM.

Did you see the patch series I posted a couple of weeks ago to revamp pv spinlocks? Specifically, I dropped the notion of pv spinlocks in which the entire spinlock implementation is replaced, and added pv ticketlocks where the ticketlock algorithm is always used for the fastpath, but it calls out to pvop calls for the slowpath (a long spin, or unlocking a lock with waiters). It significantly reduces the amount of hypervisor-specific code.

You can see the current patches in

git://git.kernel.org/pub/scm/linux/kernel/git/jeremy/xen.git
xen/pvticketlock-git

That's not actually the real problem. It's *a* problem, but insignificant compared to the ticketlock-specific "next-in-line vcpu scheduler bunfight" problem - lock holder preemption is a misnomer. Fortunately the solutions to both are (nearly) the same.

See Thomas Friebel's talk "Prevent Guests from Spinning Around
(http://www.xen.org/files/xensummitboston08/LHP.pdf).

Quoted 11 lines

b. Avoid preempting a lock-holder while its holding a (spin-) lock.

In this scheme, guest OS can hint (set some flag in memory shared with hypervisor) whenever its holding a lock and hypervisor could defer preempting the guest vcpu when its holding a lock. With this scheme, we should never have a lock-acquiring vcpu spin on a preempted vcpu to release its lock. If ever it spins, its because somebody *currently running* is holding the lock - and hence it won't have to spin-wait too long. IOW we are pro-actively trying to prevent the LHP problem from occuring in the first place. This should improve job turnaround time for some workloads. [1] has some results based on this approach.

This doesn't actually help the problem mentioned above, because it's not a problem with the lock holder getting preempted, but what happens once the lock has been released.

This patch-series implements paravirt-spinlock implementation for KVM guests, based heavily on Xen's implementation. I tried to refactor Xen's spinlock implementation to make it common for both Xen and KVM - but found that few differences between Xen and KVM (Xen has the ability to block on a particular event/irq for example) _and_ the fact that the guest kernel can be compiled to support both Xen and KVM hypervisors (CONFIG_XEN and CONFIG_KVM_GUEST can both be turned on) makes the "common" code a eye-sore. There will have to be:

	if (xen) {
		...
	} else if (kvm) {
		..
	}

or possibly:

alternative(NOP, some_xen_specific_call, ....)

Quoted 15 lines · Srivatsa Vaddagiri

This patch-series implements paravirt-spinlock implementation for KVM guests, based heavily on Xen's implementation. I tried to refactor Xen's spinlock implementation to make it common for both Xen and KVM - but found that few differences between Xen and KVM (Xen has the ability to block on a particular event/irq for example) _and_ the fact that the guest kernel can be compiled to support both Xen and KVM hypervisors (CONFIG_XEN and CONFIG_KVM_GUEST can both be turned on) makes the "common" code a eye-sore. There will have to be:

	if (xen) {
		...
	} else if (kvm) {
		..
	}

Quoted 3 lines

or possibly:

alternative(NOP, some_xen_specific_call, ....)

Why not utilize the pvops path?

This patch-series implements paravirt-spinlock implementation for KVM guests, based heavily on Xen's implementation. I tried to refactor Xen's spinlock implementation to make it common for both Xen and KVM - but found that few differences between Xen and KVM (Xen has the ability to block on a particular event/irq for example) _and_ the fact that the guest kernel can be compiled to support both Xen and KVM hypervisors (CONFIG_XEN and CONFIG_KVM_GUEST can both be turned on) makes the "common" code a eye-sore. There will have to be:

	if (xen) {
		...
	} else if (kvm) {
		..
	}

or possibly:

alternative(NOP, some_xen_specific_call, ....)

type of code in the common implementation.