Skip to contentSkip to conversation

KVM: MMU: rmap_write_protect() hugepage iteration bug

PATCH Marcelo Tosatti 3 participants 11 messages Jun 8, 2008 – Jun 9, 2008

Subsystems (3)
x86 KVM KVM x86
lore
Share & tools
lore

Marcelo Tosatti

author
#0 lore raw

rmap_next() expects the "spte" argument to be NULL whenever there's only one remaining entry in the descriptor. That is, it was not designed to handle changes in the chain while iterating.

This bug cripples rmap_write_protect() so that it won't nuke all writable large mappings to a particular gfn.

Signed-off-by Marcelo Tosatti <[email protected]>
arch/x86/kvm/mmu.c +3 -1
index aaccc40..e11ff17 100644
@@ -632,17 +632,19 @@ static void rmap_write_protect(struct kvm *kvm, u64 gfn)
 	rmapp = gfn_to_rmap(kvm, gfn, 1);
 	spte = rmap_next(kvm, rmapp, NULL);
 	while (spte) {
+		u64 *next_spte;
 		BUG_ON(!spte);
 		BUG_ON(!(*spte & PT_PRESENT_MASK));
 		BUG_ON((*spte & (PT_PAGE_SIZE_MASK|PT_PRESENT_MASK)) != (PT_PAGE_SIZE_MASK|PT_PRESENT_MASK));
 		pgprintk("rmap_write_protect(large): spte %p %llx %lld\n", spte, *spte, gfn);
+		next_spte = rmap_next(kvm, rmapp, spte);
 		if (is_writeble_pte(*spte)) {
 			rmap_remove(kvm, spte);
 			--kvm->stat.lpages;
 			set_shadow_pte(spte, shadow_trap_nonpresent_pte);
 			write_protected = 1;
 		}
-		spte = rmap_next(kvm, rmapp, spte);
+		spte = next_spte;
 	}
 
 	if (write_protected)
#1 lore raw
Quoted 7 lines · Marcelo Tosatti

rmap_next() expects the "spte" argument to be NULL whenever there's only one remaining entry in the descriptor. That is, it was not designed to handle changes in the chain while iterating.

This bug cripples rmap_write_protect() so that it won't nuke all writable large mappings to a particular gfn.

Better than before but the patched version will still not nuke all writeable sptes (I did exactly the same mistake once).

I found out the trouble the hard way with a trace of ksm kprobe wp_notifier faults, and that's this reordering here:

	   desc->shadow_ptes[i] = desc->shadow_ptes[j];
	   desc->shadow_ptes[j] = NULL;

In short there's no way to mix rmap_next and rmap_remove in the same loop as rmap_remove will reorder stuff in the array, so using the next_spte as pointer will lead to missing the sptes after the next_spte that have been reordered in place of the spte just before the next_spte. This was quite subtle issue as it's not immediately evident the first time you read rmap_remove internals.

rmap_remove invocation requires to restart from scratch (or alternatively to avoid restarting from scratch, we'd need to extend the rmap methods to provide that functionality, something like rmap_next_safe that would be robust against rmap_remove if used in the same way you did now with rmap_next).

For now this will fix it for real.

Signed-off-by Andrea Arcangeli <[email protected]>
arch/x86/kvm/mmu.c +3 -2
index aaccc40..9e4622c 100644
@@ -641,8 +641,9 @@ static void rmap_write_protect(struct kvm *kvm, u64 gfn)
 			--kvm->stat.lpages;
 			set_shadow_pte(spte, shadow_trap_nonpresent_pte);
 			write_protected = 1;
-		}
-		spte = rmap_next(kvm, rmapp, spte);
+			spte = rmap_next(kvm, rmapp, NULL);
+		} else
+			spte = rmap_next(kvm, rmapp, spte);
 	}
 
 	if (write_protected)
author
#2 lore raw

Hi Andrea,

Quoted 11 lines · Andrea Arcangeli
Quoted 7 lines · Marcelo Tosatti

rmap_next() expects the "spte" argument to be NULL whenever there's only one remaining entry in the descriptor. That is, it was not designed to handle changes in the chain while iterating.

This bug cripples rmap_write_protect() so that it won't nuke all writable large mappings to a particular gfn.

Better than before but the patched version will still not nuke all writeable sptes (I did exactly the same mistake once).

Why not posting it at the time?

Quoted 5 lines

I found out the trouble the hard way with a trace of ksm kprobe wp_notifier faults, and that's this reordering here:

	   desc->shadow_ptes[i] = desc->shadow_ptes[j];
	   desc->shadow_ptes[j] = NULL;

You're right.

Quoted 7 lines

In short there's no way to mix rmap_next and rmap_remove in the same loop as rmap_remove will reorder stuff in the array, so using the next_spte as pointer will lead to missing the sptes after the next_spte that have been reordered in place of the spte just before the next_spte. This was quite subtle issue as it's not immediately evident the first time you read rmap_remove internals.

Quoted 7 lines

rmap_remove invocation requires to restart from scratch (or alternatively to avoid restarting from scratch, we'd need to extend the rmap methods to provide that functionality, something like rmap_next_safe that would be robust against rmap_remove if used in the same way you did now with rmap_next).

For now this will fix it for real.

This makes no difference since rmap_next() still can't handle the case where rmap_remove() left a single entry in the array and "spte" has been passed as non-NULL:

        while (desc) {
                for (i = 0; i < RMAP_EXT && desc->shadow_ptes[i]; ++i) {
                        if (prev_spte == spte)
                                return desc->shadow_ptes[i];
                        prev_spte = desc->shadow_ptes[i];
                }
                desc = desc->more;
        }

Other than the BUG_ON()'s at the beginning of the while() loop.

How bad you think restarting is? Unless there are workloads with very large hugepage chains most of the data should be cached in L1. Also the fact that a 4K page has just been shadowed inside a large region makes it unlikely for the same chain to be examined again soon.

arch/x86/kvm/mmu.c +0 -0
index aaccc40..d01d098 100644
@@ -640,6 +640,7 @@ static void rmap_write_protect(struct kvm *kvm, u64

gfn)

                        rmap_remove(kvm, spte);
                        --kvm->stat.lpages;
                        set_shadow_pte(spte,shadow_trap_nonpresent_pte);
+                       spte = NULL;
                        write_protected = 1;
                }
                spte = rmap_next(kvm, rmapp, spte);
#3 lore raw
Quoted 5 lines · Marcelo Tosatti

How bad you think restarting is? Unless there are workloads with very large hugepage chains most of the data should be cached in L1. Also the fact that a 4K page has just been shadowed inside a large region makes it unlikely for the same chain to be examined again soon.

Non-pae guests will have a chain entry for every mm_struct, since the large ptes reside in the pgd and that is replicated for every mm_struct. So it's easy to have very long chains.

Signature · 1 line
error compiling committee.c: too many arguments to function
#4 lore raw
Quoted 10 lines · Avi Kivity
Quoted 5 lines · Marcelo Tosatti

How bad you think restarting is? Unless there are workloads with very large hugepage chains most of the data should be cached in L1. Also the fact that a 4K page has just been shadowed inside a large region makes it unlikely for the same chain to be examined again soon.

Non-pae guests will have a chain entry for every mm_struct, since the large ptes reside in the pgd and that is replicated for every mm_struct. So it's easy to have very long chains.

Anyway I applied the patch as a stopgap.

Signature · 1 line
error compiling committee.c: too many arguments to function
#5 lore raw
Quoted 8 lines · Avi Kivity
Quoted 7 lines · Avi Kivity
Quoted 5 lines · Marcelo Tosatti

How bad you think restarting is? Unless there are workloads with very large hugepage chains most of the data should be cached in L1. Also the fact that a 4K page has just been shadowed inside a large region makes it unlikely for the same chain to be examined again soon.

Quoted 6 lines
Quoted 3 lines

Non-pae guests will have a chain entry for every mm_struct, since the large ptes reside in the pgd and that is replicated for every mm_struct. So it's easy to have very long chains.

Anyway I applied the patch as a stopgap.

btw, please send a signoff for 2.6.26.

Signature · 1 line
error compiling committee.c: too many arguments to function
#6 lore raw
In reply to Marcelo Tosatti
Quoted 3 lines · Marcelo Tosatti
Quoted 1 line

writeable sptes (I did exactly the same mistake once).

Why not posting it at the time?

See the comments in the mail I posted a few days ago with subject "[patch] kvm with mmu notifier v18". I posted the incompatibility with rmap_next and rmap_remove in the same loop, the day after I fixed it in ksm.

Quoted 3 lines

This makes no difference since rmap_next() still can't handle the case where rmap_remove() left a single entry in the array and "spte" has been passed as non-NULL:

I don't see the problem, with the fixed code we never pass spte not-NULL after any rmap_remove run.

Quoted 1 line

How bad you think restarting is? Unless there are workloads with very

It probably worth to optimize it with rmap_next_safe in the long run, but it may not be urgent as it may be lost in the noise even if the chains are fairly long. To be sure you could try to profile it and see if rmap_write_protect goes up in the opreport.

Quoted 12 lines
arch/x86/kvm/mmu.c +1 -0
index aaccc40..d01d098 100644
@@ -640,6 +640,7 @@ static void rmap_write_protect(struct kvm *kvm, u64
 gfn)
                        rmap_remove(kvm, spte);
                        --kvm->stat.lpages;
                        set_shadow_pte(spte,shadow_trap_nonpresent_pte);
+                       spte = NULL;
                        write_protected = 1;
                }
Quoted 1 line
                spte = rmap_next(kvm, rmapp, spte);

This is shorter and functionally equivalent to my proposed fix, so you seem to agree this makes a difference by posting this patch, and I sure agree with the above fix too!

author
#7 lore raw
Quoted 10 lines · Andrea Arcangeli
Quoted 3 lines · Marcelo Tosatti
Quoted 1 line

writeable sptes (I did exactly the same mistake once).

Why not posting it at the time?

See the comments in the mail I posted a few days ago with subject "[patch] kvm with mmu notifier v18". I posted the incompatibility with rmap_next and rmap_remove in the same loop, the day after I fixed it in ksm.

Quoted 6 lines
Quoted 3 lines

This makes no difference since rmap_next() still can't handle the case where rmap_remove() left a single entry in the array and "spte" has been passed as non-NULL:

I don't see the problem, with the fixed code we never pass spte not-NULL after any rmap_remove run.

We do. The case is were you have two entries in the array. rmap_remove will first remove the entry at index 0, and move the entry at index 1 to 0.

Then we call "rmap_next()" with a non-NULL spte, which will skip the only remaining entry at index 0. IOW rmap_next() requires the spte argument to be NULL if the array has one valid entry.

Quoted 7 lines
Quoted 2 lines

How bad you think restarting is? Unless there are workloads with very

It probably worth to optimize it with rmap_next_safe in the long run, but it may not be urgent as it may be lost in the noise even if the chains are fairly long. To be sure you could try to profile it and see if rmap_write_protect goes up in the opreport.

Will do.

Quoted 17 lines
Quoted 12 lines
arch/x86/kvm/mmu.c +1 -0
index aaccc40..d01d098 100644
@@ -640,6 +640,7 @@ static void rmap_write_protect(struct kvm *kvm, u64
 gfn)
                        rmap_remove(kvm, spte);
                        --kvm->stat.lpages;
                        set_shadow_pte(spte,shadow_trap_nonpresent_pte);
+                       spte = NULL;
                        write_protected = 1;
                }
Quoted 1 line
                spte = rmap_next(kvm, rmapp, spte);

This is shorter and functionally equivalent to my proposed fix, so you seem to agree this makes a difference by posting this patch, and I sure agree with the above fix too!

#8 lore raw
Quoted 7 lines · Marcelo Tosatti

We do. The case is were you have two entries in the array. rmap_remove will first remove the entry at index 0, and move the entry at index 1 to 0.

Then we call "rmap_next()" with a non-NULL spte, which will skip the only remaining entry at index 0. IOW rmap_next() requires the spte argument to be NULL if the array has one valid entry.

How exactly we could call rmap_next with not-NULL spte after any rmap_remove with your last patch applied?

Quoted 4 lines
Quoted 2 lines

chains are fairly long. To be sure you could try to profile it and see if rmap_write_protect goes up in the opreport.

Will do.

Cool, thanks!

author
#9 lore raw
Quoted 11 lines · Andrea Arcangeli
Quoted 7 lines · Marcelo Tosatti

We do. The case is were you have two entries in the array. rmap_remove will first remove the entry at index 0, and move the entry at index 1 to 0.

Then we call "rmap_next()" with a non-NULL spte, which will skip the only remaining entry at index 0. IOW rmap_next() requires the spte argument to be NULL if the array has one valid entry.

How exactly we could call rmap_next with not-NULL spte after any rmap_remove with your last patch applied?

With the original code.