[PATCH 2/2] kvm: adaptive halt-polling toggle

[David Matlack <dmatlack@google.com>]

This patch removes almost all of the overhead of polling for idle VCPUs
by disabling polling for long halts. The length of the previous halt
is used as a predictor for the current halt:

  if (length of previous halt < halt_poll_ns): poll for halt_poll_ns
  else: don't poll

This tends to work well in practice. For VMs running Message Passing
workloads, all halts are short and so the VCPU should always poll. When
a VCPU is idle, all halts are long and so the VCPU should never halt.
Experimental results on an IvyBridge host show adaptive toggling gets
close to the best of both worlds.

                           no-poll     always-poll    adaptive-toggle
---------------------------------------------------------------------
Idle (nohz) VCPU %c0       0.12        0.32           0.15
Idle (250HZ) VCPU %c0      1.22        6.35           1.27
TCP_RR latency             39 us       25 us          25 us

(3.16 Linux guest, halt_poll_ns=200000)

The big win is with ticking operating systems. Running the linux guest
with nohz=off (and HZ=250), we save 5% CPU/second and get close to
no-polling overhead levels by using the adaptive toggle. The savings
should be even higher for higher frequency ticks.

Signed-off-by: David Matlack <dmatlack@google.com>
---
 include/trace/events/kvm.h |  23 ++++++----
 virt/kvm/kvm_main.c        | 110 ++++++++++++++++++++++++++++++++++-----------
 2 files changed, 97 insertions(+), 36 deletions(-)

diff --git a/include/trace/events/kvm.h b/include/trace/events/kvm.h
index a44062d..34e0b11 100644
--- a/include/trace/events/kvm.h
+++ b/include/trace/events/kvm.h
@@ -38,22 +38,27 @@ TRACE_EVENT(kvm_userspace_exit,
 );
 
 TRACE_EVENT(kvm_vcpu_wakeup,
-	    TP_PROTO(__u64 ns, bool waited),
-	    TP_ARGS(ns, waited),
+	TP_PROTO(bool poll, bool success, __u64 poll_ns, __u64 wait_ns),
+	TP_ARGS(poll, success, poll_ns, wait_ns),
 
 	TP_STRUCT__entry(
-		__field(	__u64,		ns		)
-		__field(	bool,		waited		)
+		__field(	 bool,		poll		)
+		__field(	 bool,		success		)
+		__field(	__u64,		poll_ns		)
+		__field(	__u64,		wait_ns		)
 	),
 
 	TP_fast_assign(
-		__entry->ns		= ns;
-		__entry->waited		= waited;
+		__entry->poll		= poll;
+		__entry->success	= success;
+		__entry->poll_ns	= poll_ns;
+		__entry->wait_ns	= wait_ns;
 	),
 
-	TP_printk("%s time %lld ns",
-		  __entry->waited ? "wait" : "poll",
-		  __entry->ns)
+	TP_printk("%s %s, poll ns %lld, wait ns %lld",
+		  __entry->poll ? "poll" : "wait",
+		  __entry->success ? "success" : "fail",
+		  __entry->poll_ns, __entry->wait_ns)
 );
 
 #if defined(CONFIG_HAVE_KVM_IRQFD)
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 977ffb1..3a66694 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -66,7 +66,8 @@
 MODULE_AUTHOR("Qumranet");
 MODULE_LICENSE("GPL");
 
-static unsigned int halt_poll_ns;
+/* The maximum amount of time a vcpu will poll for interrupts while halted. */
+static unsigned int halt_poll_ns = 200000;
 module_param(halt_poll_ns, uint, S_IRUGO | S_IWUSR);
 
 /*
@@ -1907,6 +1908,7 @@ void kvm_vcpu_mark_page_dirty(struct kvm_vcpu *vcpu, gfn_t gfn)
 }
 EXPORT_SYMBOL_GPL(kvm_vcpu_mark_page_dirty);
 
+/* This sets KVM_REQ_UNHALT if an interrupt arrives. */
 static int kvm_vcpu_check_block(struct kvm_vcpu *vcpu)
 {
 	if (kvm_arch_vcpu_runnable(vcpu)) {
@@ -1921,47 +1923,101 @@ static int kvm_vcpu_check_block(struct kvm_vcpu *vcpu)
 	return 0;
 }
 
-/*
- * The vCPU has executed a HLT instruction with in-kernel mode enabled.
- */
-void kvm_vcpu_block(struct kvm_vcpu *vcpu)
+static void
+update_vcpu_block_predictor(struct kvm_vcpu *vcpu, u64 poll_ns, u64 wait_ns)
 {
-	ktime_t start, cur;
-	DEFINE_WAIT(wait);
-	bool waited = false;
-
-	start = cur = ktime_get();
-	if (vcpu->halt_poll_ns) {
-		ktime_t stop = ktime_add_ns(ktime_get(), vcpu->halt_poll_ns);
-
-		do {
-			/*
-			 * This sets KVM_REQ_UNHALT if an interrupt
-			 * arrives.
-			 */
-			if (kvm_vcpu_check_block(vcpu) < 0) {
-				++vcpu->stat.halt_successful_poll;
-				goto out;
-			}
-			cur = ktime_get();
-		} while (single_task_running() && ktime_before(cur, stop));
+	u64 block_ns = poll_ns + wait_ns;
+
+	if (block_ns <= vcpu->halt_poll_ns)
+		return;
+
+	if (block_ns < halt_poll_ns)
+		/* we had a short block and our poll time is too small */
+		vcpu->halt_poll_ns = halt_poll_ns;
+	else
+		/* we had a long block. disable polling. */
+		vcpu->halt_poll_ns = 0;
+}
+
+static bool kvm_vcpu_try_poll(struct kvm_vcpu *vcpu, u64 *poll_ns)
+{
+	bool done = false;
+	ktime_t deadline;
+	ktime_t start;
+
+	start = ktime_get();
+	deadline = ktime_add_ns(start, vcpu->halt_poll_ns);
+
+	while (single_task_running() && ktime_before(ktime_get(), deadline)) {
+		if (kvm_vcpu_check_block(vcpu) < 0) {
+			++vcpu->stat.halt_successful_poll;
+			done = true;
+			break;
+		}
 	}
 
+	*poll_ns = ktime_to_ns(ktime_sub(ktime_get(), start));
+	return done;
+}
+
+static void kvm_vcpu_wait(struct kvm_vcpu *vcpu, u64 *wait_ns)
+{
+	DEFINE_WAIT(wait);
+	ktime_t start;
+
+	start = ktime_get();
+
 	for (;;) {
 		prepare_to_wait(&vcpu->wq, &wait, TASK_INTERRUPTIBLE);
 
 		if (kvm_vcpu_check_block(vcpu) < 0)
 			break;
 
-		waited = true;
 		schedule();
 	}
 
 	finish_wait(&vcpu->wq, &wait);
-	cur = ktime_get();
+
+	*wait_ns = ktime_to_ns(ktime_sub(ktime_get(), start));
+}
+
+void __kvm_vcpu_block(struct kvm_vcpu *vcpu)
+{
+	bool prediction_success = false;
+	u64 poll_ns = 0;
+	u64 wait_ns = 0;
+
+	if (vcpu->halt_poll_ns && kvm_vcpu_try_poll(vcpu, &poll_ns)) {
+		prediction_success = true;
+		goto out;
+	}
+
+	kvm_vcpu_wait(vcpu, &wait_ns);
+
+	if (!vcpu->halt_poll_ns && wait_ns > halt_poll_ns)
+		prediction_success = true;
 
 out:
-	trace_kvm_vcpu_wakeup(ktime_to_ns(cur) - ktime_to_ns(start), waited);
+	trace_kvm_vcpu_wakeup(vcpu->halt_poll_ns, prediction_success,
+			      poll_ns, wait_ns);
+
+	update_vcpu_block_predictor(vcpu, poll_ns, wait_ns);
+}
+
+/*
+ * The vCPU has executed a HLT instruction with in-kernel mode enabled.
+ */
+void kvm_vcpu_block(struct kvm_vcpu *vcpu)
+{
+	/*
+	 * kvm_vcpu_block can be called more than once between vcpu resumes.
+	 * All calls except the first will always return immediately. We don't
+	 * want those calls to affect poll/wait prediction, so we return here.
+	 */
+	if (kvm_vcpu_check_block(vcpu) < 0)
+		return;
+
+	__kvm_vcpu_block(vcpu);
 }
 EXPORT_SYMBOL_GPL(kvm_vcpu_block);
 
-- 
2.5.0.457.gab17608