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);
 
