Use cmpxchg for pte updates on walk_addr()

PATCH Applied Marcelo Tosatti 3 participants 9 messages Dec 6, 2007 – Dec 9, 2007 2 messages not in the archive KVM

Share & tools

Marcelo Tosatti

author

2007-12-06 15:04 UTC #0 lore raw

PATCH 1/1 Use cmpxchg for pte updates on walk_addr()

In preparation for multi-threaded guest pte walking, use cmpxchg() when updating guest pte's. This guarantees that the assignment of the dirty bit can't be lost if two CPU's are faulting the same address simultaneously.

In case of pte update via write emulation, no synchronization is necessary since its the guest responsability.

Signed-off-by Marcelo Tosatti <[email protected]>

drivers/kvm/paging_tmpl.h +20 -2

index b24bc7c..593073a 100644
@@ -78,6 +78,23 @@ static gfn_t gpte_to_gfn_pde(pt_element_t gpte)
 	return (gpte & PT_DIR_BASE_ADDR_MASK) >> PAGE_SHIFT;
 }
 
+static inline void FNAME(kvm_cmpxchg_guest_pte)(struct kvm *kvm,
+			 gfn_t table_gfn, unsigned index, pt_element_t new_bits)
+{
+	pt_element_t pte;
+	pt_element_t *table;
+	struct page *page;
+
+	page = gfn_to_page(kvm, table_gfn);
+	table = kmap_atomic(page, KM_USER0);
+
+	do {
+ 		pte = table[index];
+	} while (cmpxchg(&table[index], pte, pte | new_bits) != pte);
+
+	kunmap_atomic(page, KM_USER0);
+}
+
 /*
  * Fetch a guest pte for a guest virtual address
  */

@@ -136,7 +153,8 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 		if (!(pte & PT_ACCESSED_MASK)) {
 			mark_page_dirty(vcpu->kvm, table_gfn);
 			pte |= PT_ACCESSED_MASK;
-			kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
+			FNAME(kvm_cmpxchg_guest_pte)
+				(vcpu->kvm, table_gfn, index, pte);
 		}
 
 		if (walker->level == PT_PAGE_TABLE_LEVEL) {

@@ -161,7 +179,7 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 	if (write_fault && !is_dirty_pte(pte)) {
 		mark_page_dirty(vcpu->kvm, table_gfn);
 		pte |= PT_DIRTY_MASK;
-		kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
+		FNAME(kvm_cmpxchg_guest_pte)(vcpu->kvm, table_gfn, index, pte);
 		kvm_mmu_pte_write(vcpu, pte_gpa, (u8 *)&pte, sizeof(pte));
 	}

drivers/kvm/x86.c +3 -0

index c70ac33..edba8ce 100644
@@ -1510,6 +1510,9 @@ static int emulator_write_phys(struct kvm_vcpu *vcpu, gpa_t gpa,
 {
 	int ret;
 
+	/* No need for kvm_cmpxchg_guest_pte here, its the guest 
+ 	 * responsability to synchronize pte updates and page faults.
+	 */
 	ret = kvm_write_guest(vcpu->kvm, gpa, val, bytes);
 	if (ret < 0)
 		return 0;

-------------------------------------------------------------------------
SF.Net email is sponsored by: The Future of Linux Business White Paper from Novell. From the desktop to the data center, Linux is going mainstream. Let it simplify your IT future.
http://altfarm.mediaplex.com/ad/ck/8857-50307-18918-4

Avi Kivity

2007-12-06 15:24 UTC #1 lore raw

Quoted 16 lines · Marcelo Tosatti

In preparation for multi-threaded guest pte walking, use cmpxchg() when updating guest pte's. This guarantees that the assignment of the dirty bit can't be lost if two CPU's are faulting the same address simultaneously.
In case of pte update via write emulation, no synchronization is necessary since its the guest responsability.
Signed-off-by Marcelo Tosatti <[email protected]>
drivers/kvm/paging_tmpl.h +0 -0
index b24bc7c..593073a 100644

drivers/kvm/paging_tmpl.h static gfn_t gpte_to_gfn_pde(pt_element_t gpte) · line 83

Quoted 6 lines

drivers/kvm/paging_tmpl.h +2 -0

@@ -78,6 +78,23 @@ static gfn_t gpte_to_gfn_pde(pt_element_t gpte)
 	return (gpte & PT_DIR_BASE_ADDR_MASK) >> PAGE_SHIFT;
 }
 
+static inline void FNAME(kvm_cmpxchg_guest_pte)(struct kvm *kvm,
+			 gfn_t table_gfn, unsigned index, pt_element_t new_bits)

You can drop the kvm_ prefix since this is static.

Quoted 5 lines

drivers/kvm/paging_tmpl.h +5 -0

+{
+	pt_element_t pte;
+	pt_element_t *table;
+	struct page *page;
+

drivers/kvm/paging_tmpl.h static gfn_t gpte_to_gfn_pde(pt_element_t gpte)

Quoted 10 lines

drivers/kvm/paging_tmpl.h +9 -0

+	page = gfn_to_page(kvm, table_gfn);
+	table = kmap_atomic(page, KM_USER0);
+
+	do {
+ 		pte = table[index];
+	} while (cmpxchg(&table[index], pte, pte | new_bits) != pte);
+
+	kunmap_atomic(page, KM_USER0);
+}

I don't think cmpxchg() handles 64-bits on i386; you need cmpxchg64().

What happens if the guest changed the pte under our feet (say, one vcpu accesses the page, the other vcpu swaps it out, setting the pte to zero)? We end up modifying the new pte. So we need to compare against the original pte, and abort the walk if we fail to set the bit.

Quoted 5 lines

drivers/kvm/x86.c +0 -0
index c70ac33..edba8ce 100644

drivers/kvm/x86.c static int emulator_write_phys(struct kvm_vcpu *vcpu, gpa_t gpa, · line 1518

Quoted 9 lines

drivers/kvm/x86.c +3 -0

@@ -1510,6 +1510,9 @@ static int emulator_write_phys(struct kvm_vcpu *vcpu, gpa_t gpa,
 {
 	int ret;
 
+	/* No need for kvm_cmpxchg_guest_pte here, its the guest 
+ 	 * responsability to synchronize pte updates and page faults.
+	 */
 	ret = kvm_write_guest(vcpu->kvm, gpa, val, bytes);
 	if (ret < 0)
 		return 0;

Hmm. What if an i386 pae guest carefully uses cmpxchg8b to atomically set a pte? kvm_write_guest() doesn't guarantee atomicity, so an intended atomic write can be seen splitted by the guest walker doing a concurrent walk.

Signature · 8 lines

error compiling committee.c: too many arguments to function


-------------------------------------------------------------------------
SF.Net email is sponsored by: The Future of Linux Business White Paper
from Novell.  From the desktop to the data center, Linux is going
mainstream.  Let it simplify your IT future.
http://altfarm.mediaplex.com/ad/ck/8857-50307-18918-4

A message that is not in the archive (sent off-list or not yet received): 47581418.8000506-atKUWr5tajBWk0Htik3J/[email protected]

Marcelo Tosatti

author

2007-12-07 02:32 UTC #3 lore raw

Quoted 44 lines · Avi Kivity

Quoted 16 lines · Marcelo Tosatti
In preparation for multi-threaded guest pte walking, use cmpxchg() when updating guest pte's. This guarantees that the assignment of the dirty bit can't be lost if two CPU's are faulting the same address simultaneously.
In case of pte update via write emulation, no synchronization is necessary since its the guest responsability.
Signed-off-by Marcelo Tosatti <[email protected]>
drivers/kvm/paging_tmpl.h +0 -0
index b24bc7c..593073a 100644
drivers/kvm/paging_tmpl.h static gfn_t gpte_to_gfn_pde(pt_element_t gpte) · line 83
Quoted 6 lines
drivers/kvm/paging_tmpl.h +2 -0
@@ -78,6 +78,23 @@ static gfn_t gpte_to_gfn_pde(pt_element_t gpte)
 	return (gpte & PT_DIR_BASE_ADDR_MASK) >> PAGE_SHIFT;
 }
 
+static inline void FNAME(kvm_cmpxchg_guest_pte)(struct kvm *kvm,
+			 gfn_t table_gfn, unsigned index, pt_element_t new_bits)
 
You can drop the kvm_ prefix since this is static.
Quoted 5 lines
drivers/kvm/paging_tmpl.h +5 -0
+{
+	pt_element_t pte;
+	pt_element_t *table;
+	struct page *page;
+
drivers/kvm/paging_tmpl.h static gfn_t gpte_to_gfn_pde(pt_element_t gpte) · line 98
Quoted 10 lines
drivers/kvm/paging_tmpl.h +9 -0
+	page = gfn_to_page(kvm, table_gfn);
+	table = kmap_atomic(page, KM_USER0);
+
+	do {
+ 		pte = table[index];
+	} while (cmpxchg(&table[index], pte, pte | new_bits) != pte);
+
+	kunmap_atomic(page, KM_USER0);
+}
 
I don't think cmpxchg() handles 64-bits on i386; you need cmpxchg64().

Quoted 4 lines

What happens if the guest changed the pte under our feet (say, one vcpu accesses the page, the other vcpu swaps it out, setting the pte to zero)? We end up modifying the new pte. So we need to compare against the original pte, and abort the walk if we fail to set the bit.

Right, patch at end of the message restarts the process if the pte changes under the walker. The goto is pretty ugly, but I fail to see any elegant way of doing that. Ideas?

Quoted 8 lines

drivers/kvm/x86.c +0 -0

index c70ac33..edba8ce 100644
@@ -1510,6 +1510,9 @@ static int emulator_write_phys(struct kvm_vcpu *vcpu, gpa_t gpa,
 {
 	int ret;

Quoted 11 lines

drivers/kvm/x86.c static int emulator_write_phys(struct kvm_vcpu *vcpu, gpa_t gpa, · line 1518
Quoted 6 lines
drivers/kvm/x86.c +3 -0
+	/* No need for kvm_cmpxchg_guest_pte here, its the guest 
+ 	 * responsability to synchronize pte updates and page faults.
+	 */
 	ret = kvm_write_guest(vcpu->kvm, gpa, val, bytes);
 	if (ret < 0)
 		return 0;
Hmm. What if an i386 pae guest carefully uses cmpxchg8b to atomically set a pte? kvm_write_guest() doesn't guarantee atomicity, so an intended atomic write can be seen splitted by the guest walker doing a concurrent walk.

True, an atomic write is needed... a separate patch for that seems more appropriate.

drivers/kvm/paging_tmpl.h +31 -4

index b24bc7c..a39f8a6 100644
@@ -34,7 +34,9 @@
 	#define PT_LEVEL_BITS PT64_LEVEL_BITS
 	#ifdef CONFIG_X86_64
 	#define PT_MAX_FULL_LEVELS 4
+	#define CMPXCHG cmpxchg
 	#else
+	#define CMPXCHG cmpxchg64
 	#define PT_MAX_FULL_LEVELS 2
 	#endif
 #elif PTTYPE == 32

@@ -48,6 +50,7 @@
 	#define PT_LEVEL_MASK(level) PT32_LEVEL_MASK(level)
 	#define PT_LEVEL_BITS PT32_LEVEL_BITS
 	#define PT_MAX_FULL_LEVELS 2
+	#define CMPXCHG cmpxchg
 #else
 	#error Invalid PTTYPE value
 #endif

@@ -78,6 +81,24 @@ static gfn_t gpte_to_gfn_pde(pt_element_t gpte)
 	return (gpte & PT_DIR_BASE_ADDR_MASK) >> PAGE_SHIFT;
 }
 
+static inline bool FNAME(cmpxchg_gpte)(struct kvm *kvm,
+			 gfn_t table_gfn, unsigned index, 
+			 pt_element_t orig_pte, pt_element_t new_pte)
+{
+	pt_element_t ret;
+	pt_element_t *table;
+	struct page *page;
+
+	page = gfn_to_page(kvm, table_gfn);
+	table = kmap_atomic(page, KM_USER0);
+	
+	ret = CMPXCHG(&table[index], orig_pte, new_pte);
+
+	kunmap_atomic(page, KM_USER0);
+
+	return (ret != orig_pte);
+}
+
 /*
  * Fetch a guest pte for a guest virtual address
  */

@@ -91,6 +112,7 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 	gpa_t pte_gpa;
 
 	pgprintk("%s: addr %lx\n", __FUNCTION__, addr);
+walk:
 	walker->level = vcpu->mmu.root_level;
 	pte = vcpu->cr3;
 #if PTTYPE == 64

@@ -135,8 +157,9 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 
 		if (!(pte & PT_ACCESSED_MASK)) {
 			mark_page_dirty(vcpu->kvm, table_gfn);
-			pte |= PT_ACCESSED_MASK;
-			kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
+			if (FNAME(cmpxchg_gpte)(vcpu->kvm, table_gfn, 
+			    index, pte, pte|PT_ACCESSED_MASK))
+				goto walk;
 		}
 
 		if (walker->level == PT_PAGE_TABLE_LEVEL) {

@@ -159,9 +182,13 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 	}
 
 	if (write_fault && !is_dirty_pte(pte)) {
+		bool ret;
 		mark_page_dirty(vcpu->kvm, table_gfn);
-		pte |= PT_DIRTY_MASK;
-		kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
+		ret = FNAME(cmpxchg_gpte)(vcpu->kvm, table_gfn, index, pte,
+		       	    pte|PT_DIRTY_MASK);
+		if (ret)
+			goto walk;
+			
 		kvm_mmu_pte_write(vcpu, pte_gpa, (u8 *)&pte, sizeof(pte));
 	}

-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php

Avi Kivity

2007-12-07 05:06 UTC #4 lore raw

Quoted 5 lines · Marcelo Tosatti

Right, patch at end of the message restarts the process if the pte changes under the walker. The goto is pretty ugly, but I fail to see any elegant way of doing that. Ideas?

goto is fine for that. But there's a subtle livelock here: suppose vcpu 0 is in guest mode with continuously updating a memory location. vcpu 1 is faulting with that memory location acting as a pte. While we're in kernel mode, we aren't responding to signals like we should; so we need to abort the walk and let the guest retry; that way we go through the signal_pending() check.

However, this is an intrusive change, so let's start with the goto and drop it later in favor or an abort.

Quoted 17 lines

Quoted 4 lines
Quoted 4 lines
(quoted diff) +0 -0
@@ -1510,6 +1510,9 @@ static int emulator_write_phys(struct kvm_vcpu *vcpu, gpa_t gpa,
 {
 	int ret;
 
Quoted 12 lines
Review static int emulator_write_phys(struct kvm_vcpu *vcpu, gpa_t gpa, · line 1518
Quoted 7 lines
(quoted diff) +3 -0
+	/* No need for kvm_cmpxchg_guest_pte here, its the guest 
+ 	 * responsability to synchronize pte updates and page faults.
+	 */
 	ret = kvm_write_guest(vcpu->kvm, gpa, val, bytes);
 	if (ret < 0)
 		return 0;
Hmm. What if an i386 pae guest carefully uses cmpxchg8b to atomically set a pte? kvm_write_guest() doesn't guarantee atomicity, so an intended atomic write can be seen splitted by the guest walker doing a concurrent walk.

Quoted 5 lines

True, an atomic write is needed... a separate patch for that seems more appropriate.

Yes.

Quoted 6 lines

drivers/kvm/paging_tmpl.h +5 -0

+static inline bool FNAME(cmpxchg_gpte)(struct kvm *kvm,
+			 gfn_t table_gfn, unsigned index, 
+			 pt_element_t orig_pte, pt_element_t new_pte)
+{
+	pt_element_t ret;

drivers/kvm/paging_tmpl.h static gfn_t gpte_to_gfn_pde(pt_element_t gpte) · line 98

Quoted 10 lines

drivers/kvm/paging_tmpl.h +10 -0

+	pt_element_t *table;
+	struct page *page;
+
+	page = gfn_to_page(kvm, table_gfn);
+	table = kmap_atomic(page, KM_USER0);
+	
+	ret = CMPXCHG(&table[index], orig_pte, new_pte);
+
+	kunmap_atomic(page, KM_USER0);
+

Missing kvm_release_page_dirty() here. May also move mark_page_dirty() here.

No need to force inlining.

Quoted 15 lines

drivers/kvm/paging_tmpl.h +4 -0

+	return (ret != orig_pte);
+}
+
 /*
  * Fetch a guest pte for a guest virtual address
  */

@@ -91,6 +112,7 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 	gpa_t pte_gpa;
 
 	pgprintk("%s: addr %lx\n", __FUNCTION__, addr);
+walk:
 	walker->level = vcpu->mmu.root_level;
 	pte = vcpu->cr3;
 #if PTTYPE == 64

drivers/kvm/paging_tmpl.h static int FNAME(walk_addr)(struct guest_walker *walker, · line 163

Quoted 9 lines

drivers/kvm/paging_tmpl.h +3 -2

@@ -135,8 +157,9 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 
 		if (!(pte & PT_ACCESSED_MASK)) {
 			mark_page_dirty(vcpu->kvm, table_gfn);
-			pte |= PT_ACCESSED_MASK;
-			kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
+			if (FNAME(cmpxchg_gpte)(vcpu->kvm, table_gfn, 
+			    index, pte, pte|PT_ACCESSED_MASK))
+				goto walk;

We lose the accessed bit in the local variable pte here. Not sure if it matters but let's play it safe.

Quoted 6 lines

(quoted diff) +0 -0

drivers/kvm/paging_tmpl.h +0 -0

 		if (walker->level == PT_PAGE_TABLE_LEVEL) {

@@ -159,9 +182,13 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 	}

drivers/kvm/paging_tmpl.h static int FNAME(walk_addr)(struct guest_walker *walker, · line 191

Quoted 10 lines

drivers/kvm/paging_tmpl.h +6 -2

 	if (write_fault && !is_dirty_pte(pte)) {
+		bool ret;
 		mark_page_dirty(vcpu->kvm, table_gfn);
-		pte |= PT_DIRTY_MASK;
-		kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
+		ret = FNAME(cmpxchg_gpte)(vcpu->kvm, table_gfn, index, pte,
+		       	    pte|PT_DIRTY_MASK);
+		if (ret)
+			goto walk;
+

Again we lose a bit in pte. That ends up in walker->pte and is quite important.

Signature · 9 lines

Any sufficiently difficult bug is indistinguishable from a feature.


-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php

A message that is not in the archive (sent off-list or not yet received): 4758D4D2.8090208-atKUWr5tajBWk0Htik3J/[email protected]

Marcelo Tosatti

author

2007-12-07 12:56 UTC #6 lore raw

Quoted 7 lines · Avi Kivity

Quoted 5 lines · Marcelo Tosatti
Right, patch at end of the message restarts the process if the pte changes under the walker. The goto is pretty ugly, but I fail to see any elegant way of doing that. Ideas?

Quoted 6 lines

goto is fine for that. But there's a subtle livelock here: suppose vcpu 0 is in guest mode with continuously updating a memory location. vcpu 1 is faulting with that memory location acting as a pte. While we're in kernel mode, we aren't responding to signals like we should; so we need to abort the walk and let the guest retry; that way we go through the signal_pending() check.

I see that possibility, but why on earth would the guest be continuously updating a pagetable entry ?

Quoted 41 lines

However, this is an intrusive change, so let's start with the goto and drop it later in favor or an abort.
Quoted 18 lines
Quoted 5 lines
Quoted 5 lines
(quoted diff) +0 -0
@@ -1510,6 +1510,9 @@ static int emulator_write_phys(struct kvm_vcpu 
 *vcpu, gpa_t gpa,
 {
 	int ret;
 
Quoted 12 lines
Quoted 7 lines
(quoted diff) +3 -0
+	/* No need for kvm_cmpxchg_guest_pte here, its the guest 
+ 	 * responsability to synchronize pte updates and page faults.
+	 */
 	ret = kvm_write_guest(vcpu->kvm, gpa, val, bytes);
 	if (ret < 0)
		return 0;
Hmm. What if an i386 pae guest carefully uses cmpxchg8b to atomically set a pte? kvm_write_guest() doesn't guarantee atomicity, so an intended atomic write can be seen splitted by the guest walker doing a concurrent walk.
Quoted 5 lines
True, an atomic write is needed... a separate patch for that seems more appropriate.
Yes.
Quoted 11 lines
(quoted diff) +11 -0
+static inline bool FNAME(cmpxchg_gpte)(struct kvm *kvm,
+			 gfn_t table_gfn, unsigned index, 
+			 pt_element_t orig_pte, pt_element_t new_pte)
+{
+	pt_element_t ret;
+	pt_element_t *table;
+	struct page *page;
+
+	page = gfn_to_page(kvm, table_gfn);
+	table = kmap_atomic(page, KM_USER0);
+	

Quoted 8 lines

Review
Quoted 5 lines
(quoted diff) +4 -0
+	ret = CMPXCHG(&table[index], orig_pte, new_pte);
+
+	kunmap_atomic(page, KM_USER0);
+
Missing kvm_release_page_dirty() here. May also move mark_page_dirty() here.

I prefer leaving that for later when the locking for mark_page_dirty() gets sorted out...

Quoted 1 line

No need to force inlining.

Alright.

Quoted 37 lines

Quoted 16 lines

(quoted diff) +3 -0

+	return (ret != orig_pte);
+}
+

/*
* Fetch a guest pte for a guest virtual address
*/

(quoted diff) +1 -0

@@ -91,6 +112,7 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 	gpa_t pte_gpa;
 
 	pgprintk("%s: addr %lx\n", __FUNCTION__, addr);
+walk:
 	walker->level = vcpu->mmu.root_level;
 	pte = vcpu->cr3;
 #if PTTYPE == 64

@@ -135,8 +157,9 @@ static int FNAME(walk_addr)(struct guest_walker 
 *walker,

Review static int FNAME(walk_addr)(struct guest_walker · line 165

Quoted 10 lines

(quoted diff) +3 -2

 
 		if (!(pte & PT_ACCESSED_MASK)) {
 			mark_page_dirty(vcpu->kvm, table_gfn);
-			pte |= PT_ACCESSED_MASK;
-			kvm_write_guest(vcpu->kvm, pte_gpa, &pte, 
 sizeof(pte));
+			if (FNAME(cmpxchg_gpte)(vcpu->kvm, table_gfn, 
+			    index, pte, pte|PT_ACCESSED_MASK))
+				goto walk;

We lose the accessed bit in the local variable pte here. Not sure if it matters but let's play it safe.

Quoted 7 lines

		}

		if (walker->level == PT_PAGE_TABLE_LEVEL) {

(quoted diff) +0 -0

@@ -159,9 +182,13 @@ static int FNAME(walk_addr)(struct guest_walker 
 *walker,
 	}

Quoted 13 lines

Review static int FNAME(walk_addr)(struct guest_walker · line 192
Quoted 10 lines
(quoted diff) +6 -2
 	if (write_fault && !is_dirty_pte(pte)) {
+		bool ret;
 		mark_page_dirty(vcpu->kvm, table_gfn);
-		pte |= PT_DIRTY_MASK;
-		kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
+		ret = FNAME(cmpxchg_gpte)(vcpu->kvm, table_gfn, index, pte,
+		       	    pte|PT_DIRTY_MASK);
+		if (ret)
+			goto walk;
+	
Again we lose a bit in pte. That ends up in walker->pte and is quite important.

Oops!

Updated patch:

drivers/kvm/paging_tmpl.h +32 -2

index b24bc7c..2e54b02 100644
@@ -34,7 +34,9 @@
 	#define PT_LEVEL_BITS PT64_LEVEL_BITS
 	#ifdef CONFIG_X86_64
 	#define PT_MAX_FULL_LEVELS 4
+	#define CMPXCHG cmpxchg
 	#else
+	#define CMPXCHG cmpxchg64
 	#define PT_MAX_FULL_LEVELS 2
 	#endif
 #elif PTTYPE == 32

@@ -48,6 +50,7 @@
 	#define PT_LEVEL_MASK(level) PT32_LEVEL_MASK(level)
 	#define PT_LEVEL_BITS PT32_LEVEL_BITS
 	#define PT_MAX_FULL_LEVELS 2
+	#define CMPXCHG cmpxchg
 #else
 	#error Invalid PTTYPE value
 #endif

@@ -78,6 +81,26 @@ static gfn_t gpte_to_gfn_pde(pt_element_t gpte)
 	return (gpte & PT_DIR_BASE_ADDR_MASK) >> PAGE_SHIFT;
 }
 
+static bool FNAME(cmpxchg_gpte)(struct kvm *kvm,
+			 gfn_t table_gfn, unsigned index, 
+			 pt_element_t orig_pte, pt_element_t new_pte)
+{
+	pt_element_t ret;
+	pt_element_t *table;
+	struct page *page;
+
+	page = gfn_to_page(kvm, table_gfn);
+	table = kmap_atomic(page, KM_USER0);
+	
+	ret = CMPXCHG(&table[index], orig_pte, new_pte);
+
+	kunmap_atomic(page, KM_USER0);
+
+	kvm_release_page_dirty(page);
+
+	return (ret != orig_pte);
+}
+
 /*
  * Fetch a guest pte for a guest virtual address
  */

@@ -91,6 +114,7 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 	gpa_t pte_gpa;
 
 	pgprintk("%s: addr %lx\n", __FUNCTION__, addr);
+walk:
 	walker->level = vcpu->mmu.root_level;
 	pte = vcpu->cr3;
 #if PTTYPE == 64

@@ -135,8 +159,10 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 
 		if (!(pte & PT_ACCESSED_MASK)) {
 			mark_page_dirty(vcpu->kvm, table_gfn);
+			if (FNAME(cmpxchg_gpte)(vcpu->kvm, table_gfn, 
+			    index, pte, pte|PT_ACCESSED_MASK))
+				goto walk;
 			pte |= PT_ACCESSED_MASK;
-			kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
 		}
 
 		if (walker->level == PT_PAGE_TABLE_LEVEL) {

@@ -159,9 +185,13 @@ static int FNAME(walk_addr)(struct guest_walker *walker,
 	}
 
 	if (write_fault && !is_dirty_pte(pte)) {
+		bool ret;
 		mark_page_dirty(vcpu->kvm, table_gfn);
+		ret = FNAME(cmpxchg_gpte)(vcpu->kvm, table_gfn, index, pte,
+		       	    pte|PT_DIRTY_MASK);
+		if (ret)
+			goto walk;
 		pte |= PT_DIRTY_MASK;
-		kvm_write_guest(vcpu->kvm, pte_gpa, &pte, sizeof(pte));
 		kvm_mmu_pte_write(vcpu, pte_gpa, (u8 *)&pte, sizeof(pte));
 	}

Andrea Arcangeli

2007-12-07 17:54 UTC #7 lore raw

Quoted 2 lines · Marcelo Tosatti

I see that possibility, but why on earth would the guest be continuously updating a pagetable entry ?

If I understood correctly this would be just to be more robust against malicious guests that could try to create unkillable tight loops in host kernel mode with -smp > 1. Not sure if timings would allow it though. With numa archs if the guest cpu is lucky and has the pte in its direct connected ram, and the walker cpu instead need to access it remotely, such starvation could probably materialize.

Avi Kivity

Applied

2007-12-09 08:38 UTC #8 lore raw

In reply to Marcelo Tosatti

Quoted 6 lines · Marcelo Tosatti

Oops!
Updated patch:

Applied, thanks.

drivers/kvm/paging_tmpl.h line 41

Quoted 9 lines

drivers/kvm/paging_tmpl.h +2 -0

 	#define PT_LEVEL_BITS PT64_LEVEL_BITS
 	#ifdef CONFIG_X86_64
 	#define PT_MAX_FULL_LEVELS 4
+	#define CMPXCHG cmpxchg
 	#else
+	#define CMPXCHG cmpxchg64
 	#define PT_MAX_FULL_LEVELS 2
 	#endif

I updated the #undef block at the end of paging_tmpl.h to account for the new define, otherwise it wouldn't compile cleanly on i386 due to CMPXCHG being redefined.

I picked up the patch description and signoff from the first version of this patch, but please keep them with the patch next time.

Signature · 9 lines

Do not meddle in the internals of kernels, for they are subtle and quick to panic.


-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php

Marcelo Tosatti

author

2007-12-07 22:47 UTC #9 lore raw

In reply to a message not in the archive

Quoted 35 lines · Avi Kivity

Quoted 5 lines · Marcelo Tosatti
Right, patch at end of the message restarts the process if the pte changes under the walker. The goto is pretty ugly, but I fail to see any elegant way of doing that. Ideas?
goto is fine for that. But there's a subtle livelock here: suppose vcpu 0 is in guest mode with continuously updating a memory location. vcpu 1 is faulting with that memory location acting as a pte. While we're in kernel mode, we aren't responding to signals like we should; so we need to abort the walk and let the guest retry; that way we go through the signal_pending() check.
However, this is an intrusive change, so let's start with the goto and drop it later in favor or an abort.
Quoted 18 lines
Quoted 17 lines
Quoted 10 lines
(quoted diff) +3 -0
@@ -1510,6 +1510,9 @@ static int emulator_write_phys(struct kvm_vcpu 
 *vcpu, gpa_t gpa,
 {
 	int ret;
 
+	/* No need for kvm_cmpxchg_guest_pte here, its the guest 
+ 	 * responsability to synchronize pte updates and page faults.
+	 */
 	ret = kvm_write_guest(vcpu->kvm, gpa, val, bytes);
 	if (ret < 0)
Quoted 2 lines
		return 0;
Hmm. What if an i386 pae guest carefully uses cmpxchg8b to atomically set a pte? kvm_write_guest() doesn't guarantee atomicity, so an intended atomic write can be seen splitted by the guest walker doing a concurrent walk.

Quoted 7 lines

Quoted 5 lines
True, an atomic write is needed... a separate patch for that seems more appropriate.
Yes.

Hi Avi,

How about the following

drivers/kvm/x86.c +29 -0

index c70ac33..8678651 100644
@@ -25,6 +25,7 @@
 #include <linux/vmalloc.h>
 #include <linux/module.h>
 #include <linux/mman.h>
+#include <linux/highmem.h>
 
 #include <asm/uaccess.h>
 #include <asm/msr.h>

@@ -1589,6 +1590,34 @@ static int emulator_cmpxchg_emulated(unsigned long addr,
 		reported = 1;
 		printk(KERN_WARNING "kvm: emulating exchange as write\n");
 	}
+
+	/* guests cmpxchg8b have to be emulated atomically */
+	if (bytes == 8) {
+		gpa_t gpa = vcpu->mmu.gva_to_gpa(vcpu, addr);
+		struct page *page;
+		char *addr;
+		u64 *val;
+
+		if (gpa == UNMAPPED_GVA ||
+	    	   (gpa & PAGE_MASK) == APIC_DEFAULT_PHYS_BASE)
+			goto emul_write;
+
+		val = (u64 *)new;
+		page = gfn_to_page(vcpu->kvm, gpa >> PAGE_SHIFT);
+		addr = kmap_atomic(page, KM_USER0);
+		addr += offset_in_page(gpa);
+
+#ifdef CONFIG_X86_64
+		set_64bit((unsigned long *)addr, *val);
+#else
+		set_64bit((unsigned long long *)addr, *val);
+#endif
+		kunmap_atomic(page, KM_USER0);
+		kvm_release_page_dirty(page);
+			
+	}
+
+emul_write:
 	return emulator_write_emulated(addr, new, bytes, vcpu);
 }

Avi Kivity

2007-12-09 08:47 UTC #10 lore raw

Quoted 66 lines · Marcelo Tosatti

Quoted 38 lines · Avi Kivity
Quoted 6 lines · Marcelo Tosatti
Right, patch at end of the message restarts the process if the pte changes under the walker. The goto is pretty ugly, but I fail to see any elegant way of doing that. Ideas?
goto is fine for that. But there's a subtle livelock here: suppose vcpu 0 is in guest mode with continuously updating a memory location. vcpu 1 is faulting with that memory location acting as a pte. While we're in kernel mode, we aren't responding to signals like we should; so we need to abort the walk and let the guest retry; that way we go through the signal_pending() check.
However, this is an intrusive change, so let's start with the goto and drop it later in favor or an abort.
Quoted 19 lines
Quoted 19 lines
Quoted 10 lines
(quoted diff) +3 -0
@@ -1510,6 +1510,9 @@ static int emulator_write_phys(struct kvm_vcpu 
 *vcpu, gpa_t gpa,
 {
 	int ret;
 
+	/* No need for kvm_cmpxchg_guest_pte here, its the guest 
+ 	 * responsability to synchronize pte updates and page faults.
+	 */
 	ret = kvm_write_guest(vcpu->kvm, gpa, val, bytes);
 	if (ret < 0)
Quoted 3 lines
		return 0;
Hmm. What if an i386 pae guest carefully uses cmpxchg8b to atomically set a pte? kvm_write_guest() doesn't guarantee atomicity, so an intended atomic write can be seen splitted by the guest walker doing a concurrent walk.
Quoted 8 lines
Quoted 6 lines
True, an atomic write is needed... a separate patch for that seems more appropriate.
Yes.
Hi Avi,
How about the following
drivers/kvm/x86.c +1 -0
index c70ac33..8678651 100644
@@ -25,6 +25,7 @@
 #include <linux/vmalloc.h>
 #include <linux/module.h>
 #include <linux/mman.h>
+#include <linux/highmem.h>
 
 #include <asm/uaccess.h>
 #include <asm/msr.h>

drivers/kvm/x86.c static int emulator_cmpxchg_emulated(unsigned long addr, · line 1596

Quoted 7 lines

drivers/kvm/x86.c +3 -0

@@ -1589,6 +1590,34 @@ static int emulator_cmpxchg_emulated(unsigned long addr,
 		reported = 1;
 		printk(KERN_WARNING "kvm: emulating exchange as write\n");
 	}
+
+	/* guests cmpxchg8b have to be emulated atomically */
+	if (bytes == 8) {

It's only needed on i386, as 8-byte copy_to_user should be atomic on x86_64.

Signature · 9 lines

Do not meddle in the internals of kernels, for they are subtle and quick to panic.


-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php