diff --git a/arch/x86/include/asm/kvm_host.h b/arch/x86/include/asm/kvm_host.h
index a3f637f..089ad0e 100644
--- a/arch/x86/include/asm/kvm_host.h
+++ b/arch/x86/include/asm/kvm_host.h
@@ -394,6 +394,7 @@ struct kvm_arch{
 	 * Hash table of struct kvm_mmu_page.
 	 */
 	struct list_head active_mmu_pages;
+	struct kvm_mmu_page *scan_hand;
 	struct list_head assigned_dev_head;
 	struct iommu_domain *iommu_domain;
 	int iommu_flags;
diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c
index f76d086..3715242 100644
--- a/arch/x86/kvm/mmu.c
+++ b/arch/x86/kvm/mmu.c
@@ -869,6 +869,8 @@ static int is_empty_shadow_page(u64 *spt)
 static void kvm_mmu_free_page(struct kvm *kvm, struct kvm_mmu_page *sp)
 {
 	ASSERT(is_empty_shadow_page(sp->spt));
+	if (kvm->arch.scan_hand == sp)
+		kvm->arch.scan_hand = NULL;
 	list_del(&sp->link);
 	__free_page(virt_to_page(sp->spt));
 	__free_page(virt_to_page(sp->gfns));
@@ -1490,6 +1492,71 @@ static int kvm_mmu_zap_page(struct kvm *kvm, struct kvm_mmu_page *sp)
 	return ret;
 }
 
+static int kvm_mmu_test_and_clear_pte_active(struct kvm_mmu_page *sp)
+{
+	struct kvm_pte_chain *pte_chain;
+	struct hlist_node *node;
+	int i, accessed = 0;
+
+	if (!sp->multimapped) {
+		if (!sp->parent_pte) {
+			if (!sp->root_count)
+				return 0;
+			else
+				return 1;
+		}
+		if (*sp->parent_pte & PT_ACCESSED_MASK) {
+			clear_bit(PT_ACCESSED_SHIFT,
+				  (unsigned long *)sp->parent_pte);
+			return 1;
+		} else
+			return 0;
+	}
+	/* Multimapped */
+	hlist_for_each_entry(pte_chain, node, &sp->parent_ptes, link)
+		for (i = 0; i < NR_PTE_CHAIN_ENTRIES; ++i) {
+			if (!pte_chain->parent_ptes[i])
+				break;
+			if (*pte_chain->parent_ptes[i] &
+			    PT_ACCESSED_MASK) {
+				clear_bit(PT_ACCESSED_SHIFT,
+				    (unsigned long *)
+				    pte_chain->parent_ptes[i]);
+				accessed++;
+			}
+		}
+	if (!accessed)
+		return 0;
+	else
+		return 1;
+}
+
+static struct kvm_mmu_page *kvm_mmu_get_inactive_page(struct kvm *kvm)
+{
+	struct kvm_mmu_page *sp, *prev = NULL;
+	int c = (kvm->arch.n_alloc_mmu_pages - kvm->arch.n_free_mmu_pages) / 4;
+
+	if (kvm->arch.scan_hand)
+		sp = kvm->arch.scan_hand;
+	else
+		sp = container_of(kvm->arch.active_mmu_pages.prev,
+				 struct kvm_mmu_page, link);
+
+	list_for_each_entry_reverse(sp, &kvm->arch.active_mmu_pages, link) {
+		if (!kvm_mmu_test_and_clear_pte_active(sp))
+			return sp;
+		if (!prev && sp->role.level == PT_PAGE_TABLE_LEVEL)
+			prev = sp;
+		else
+			kvm->arch.scan_hand = sp;
+		if (!--c)
+			break;
+	}
+
+	return prev ? prev : container_of(kvm->arch.active_mmu_pages.prev,
+					  struct kvm_mmu_page, link);
+}
+
 /*
  * Changing the number of mmu pages allocated to the vm
  * Note: if kvm_nr_mmu_pages is too small, you will get dead lock
@@ -1511,8 +1578,7 @@ void kvm_mmu_change_mmu_pages(struct kvm *kvm, unsigned int kvm_nr_mmu_pages)
 		while (used_pages > kvm_nr_mmu_pages) {
 			struct kvm_mmu_page *page;
 
-			page = container_of(kvm->arch.active_mmu_pages.prev,
-					    struct kvm_mmu_page, link);
+			page = kvm_mmu_get_inactive_page(kvm);
 			kvm_mmu_zap_page(kvm, page);
 			used_pages--;
 		}
@@ -2712,8 +2778,7 @@ void __kvm_mmu_free_some_pages(struct kvm_vcpu *vcpu)
 	       !list_empty(&vcpu->kvm->arch.active_mmu_pages)) {
 		struct kvm_mmu_page *sp;
 
-		sp = container_of(vcpu->kvm->arch.active_mmu_pages.prev,
-				  struct kvm_mmu_page, link);
+		sp = kvm_mmu_get_inactive_page(vcpu->kvm);
 		kvm_mmu_zap_page(vcpu->kvm, sp);
 		++vcpu->kvm->stat.mmu_recycled;
 	}
@@ -2871,8 +2936,7 @@ static void kvm_mmu_remove_one_alloc_mmu_page(struct kvm *kvm)
 {
 	struct kvm_mmu_page *page;
 
-	page = container_of(kvm->arch.active_mmu_pages.prev,
-			    struct kvm_mmu_page, link);
+	page = kvm_mmu_get_inactive_page(kvm);
 	kvm_mmu_zap_page(kvm, page);
 }
 
diff --git a/arch/x86/kvm/x86.c b/arch/x86/kvm/x86.c
index 8b3a169..ccd5bea 100644
--- a/arch/x86/kvm/x86.c
+++ b/arch/x86/kvm/x86.c
@@ -4782,6 +4782,7 @@ struct  kvm *kvm_arch_create_vm(void)
 		return ERR_PTR(-ENOMEM);
 
 	INIT_LIST_HEAD(&kvm->arch.active_mmu_pages);
+	kvm->arch.scan_hand = NULL;
 	INIT_LIST_HEAD(&kvm->arch.assigned_dev_head);
 
 	/* Reserve bit 0 of irq_sources_bitmap for userspace irq source */
