KVM: Convert read-only users of vm_list to RCU

Only for walking the list of VMs, we do not need to hold the preemption disabling kvm_lock. Convert stat services, the cpufreq callback and mmu_shrink to RCU. For the latter, special care is required to synchronize its list_move_tail with kvm_destroy_vm.

arch/x86/kvm/mmu.c +0 -0

index b6a9963..e9d0ed8 100644

arch/x86/kvm/mmu.c +3 -1

+		raw_spin_unlock(&kvm_lock);
+	}
 
-	raw_spin_unlock(&kvm_lock);
+	rcu_read_unlock();
 

Quoted 17 lines · Jan Kiszka

Only for walking the list of VMs, we do not need to hold the preemption disabling kvm_lock. Convert stat services, the cpufreq callback and mmu_shrink to RCU. For the latter, special care is required to synchronize its list_move_tail with kvm_destroy_vm.

arch/x86/kvm/mmu.c +1 -1

index b6a9963..e9d0ed8 100644
@@ -3587,9 +3587,9 @@ static int mmu_shrink(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask)
  	if (nr_to_scan == 0)
  		goto out;
 
-	raw_spin_lock(&kvm_lock);
+	rcu_read_lock();
 

arch/x86/kvm/mmu.c static int mmu_shrink(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask) · line 3594

Quoted 4 lines

arch/x86/kvm/mmu.c +1 -1

-	list_for_each_entry(kvm,&vm_list, vm_list) {
+	list_for_each_entry_rcu(kvm,&vm_list, vm_list) {
  		int idx, freed_pages;
  		LIST_HEAD(invalid_list);

Have to #include rculist.h,

and to change all list operations on vm_list
to rcu variants.

arch/x86/kvm/mmu.c static int mmu_shrink(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask) · line 3613

Quoted 12 lines

arch/x86/kvm/mmu.c +4 -2

@@ -3607,10 +3607,14 @@ static int mmu_shrink(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask)
  		spin_unlock(&kvm->mmu_lock);
  		srcu_read_unlock(&kvm->srcu, idx);
  	}
-	if (kvm_freed)
-		list_move_tail(&kvm_freed->vm_list,&vm_list);
+	if (kvm_freed) {
+		raw_spin_lock(&kvm_lock);
+		if (!kvm->deleted)
+			list_move_tail(&kvm_freed->vm_list,&vm_list);

There is no list_move_tail_rcu().

Why check kvm->deleted? it's in the process of being torn down anyway, it doesn't matter if mmu_shrink or kvm_destroy_vm pulls the trigger.

Quoted 13 lines

Quoted 12 lines

@@ -3607,10 +3607,14 @@ static int mmu_shrink(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask)

   		spin_unlock(&kvm->mmu_lock);
   		srcu_read_unlock(&kvm->srcu, idx);
   	}

- if (kvm_freed)
- list_move_tail(&kvm_freed->vm_list,&vm_list);
+ if (kvm_freed) {
+ raw_spin_lock(&kvm_lock);
+ if (!kvm->deleted)
+ list_move_tail(&kvm_freed->vm_list,&vm_list);

Quoted 1 line

There is no list_move_tail_rcu().

...specifically not for this one.

Quoted 3 lines

Why check kvm->deleted? it's in the process of being torn down anyway, it doesn't matter if mmu_shrink or kvm_destroy_vm pulls the trigger.

kvm_destroy_vm removes a vm from the list while mmu_shrink is running. Then mmu_shrink's list_move_tail will re-add that vm to the list tail again (unless already the removal in move_tail produces a crash).

Quoted 13 lines · Jan Kiszka

Quoted 13 lines

Quoted 12 lines

@@ -3607,10 +3607,14 @@ static int mmu_shrink(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask)

   		spin_unlock(&kvm->mmu_lock);
   		srcu_read_unlock(&kvm->srcu, idx);
   	}

- if (kvm_freed)
- list_move_tail(&kvm_freed->vm_list,&vm_list);
+ if (kvm_freed) {
+ raw_spin_lock(&kvm_lock);
+ if (!kvm->deleted)
+ list_move_tail(&kvm_freed->vm_list,&vm_list);

Quoted 3 lines

Quoted 1 line

There is no list_move_tail_rcu().

...specifically not for this one.

Well, we can add one if needed (and if possible).

Quoted 8 lines

Quoted 4 lines

Why check kvm->deleted? it's in the process of being torn down anyway, it doesn't matter if mmu_shrink or kvm_destroy_vm pulls the trigger.

kvm_destroy_vm removes a vm from the list while mmu_shrink is running. Then mmu_shrink's list_move_tail will re-add that vm to the list tail again (unless already the removal in move_tail produces a crash).

It's too subtle. Communication across threads with a variable needs memory barriers (even though they're nops on x86) and documentation.

btw, not even sure if it's legal: you have a mutating call within an rcu read critical section for the same object. If synchronize_rcu() were called there, would it ever terminate?

(not that synchronize_rcu() is a good thing there, better do it with call_rcu()).

Quoted 6 lines

Quoted 4 lines

Quoted 2 lines

There is no list_move_tail_rcu().

...specifically not for this one.

Well, we can add one if needed (and if possible).

I can have a look, at least at the lower hanging fruits.

Quoted 9 lines

Quoted 8 lines

Quoted 4 lines

Why check kvm->deleted? it's in the process of being torn down anyway, it doesn't matter if mmu_shrink or kvm_destroy_vm pulls the trigger.

kvm_destroy_vm removes a vm from the list while mmu_shrink is running. Then mmu_shrink's list_move_tail will re-add that vm to the list tail again (unless already the removal in move_tail produces a crash).

Quoted 2 lines

It's too subtle. Communication across threads with a variable needs memory barriers (even though they're nops on x86) and documentation.

The barriers are provided by this spin lock we acquire for testing are modifying deleted.

Quoted 4 lines

btw, not even sure if it's legal: you have a mutating call within an rcu read critical section for the same object. If synchronize_rcu() were called there, would it ever terminate?

Why not? kvm_destroy_vm is not preventing blocking mmu_shrink to acquire the kvm_lock where we then find the vm deleted and release both kvm_lock and the rcu read "lock" afterwards.

Quoted 3 lines

(not that synchronize_rcu() is a good thing there, better do it with call_rcu()).

What's the benefit? The downside is a bit more complexity as you need an additional callback handler.

Quoted 2 lines

What's the benefit? The downside is a bit more complexity as you need an additional callback handler.

synchronize_rcu() can be very slow (its a systemwide operation), and mmu_shrink() can be called often on a loaded system.

Quoted 4 lines · Avi Kivity

Quoted 2 lines

What's the benefit? The downside is a bit more complexity as you need an additional callback handler.

Quoted 3 lines

synchronize_rcu() can be very slow (its a systemwide operation), and mmu_shrink() can be called often on a loaded system.

In fact this just shows that vm_list is not a good candidate for rcu; rcu is useful where most operations are reads, but if we discount stats, most operations on vm_list are going to be writes.

Quoted 9 lines · Avi Kivity

Quoted 7 lines · Avi Kivity

Quoted 2 lines

What's the benefit? The downside is a bit more complexity as you need an additional callback handler.

synchronize_rcu() can be very slow (its a systemwide operation), and mmu_shrink() can be called often on a loaded system.

Quoted 3 lines

In fact this just shows that vm_list is not a good candidate for rcu; rcu is useful where most operations are reads, but if we discount stats, most operations on vm_list are going to be writes.

Accept for mmu_shrink, which is write but not delete, thus works without that slow synchronize_rcu.

And I don't see the need for call_rcu in the
vm deletion path.

Quoted 14 lines · Jan Kiszka

Quoted 12 lines · Avi Kivity

Quoted 7 lines · Avi Kivity

Quoted 2 lines

What's the benefit? The downside is a bit more complexity as you need an additional callback handler.

synchronize_rcu() can be very slow (its a systemwide operation), and mmu_shrink() can be called often on a loaded system.

In fact this just shows that vm_list is not a good candidate for rcu; rcu is useful where most operations are reads, but if we discount stats, most operations on vm_list are going to be writes.

Quoted 2 lines

Accept for mmu_shrink, which is write but not delete, thus works without that slow synchronize_rcu.

I don't really see how you can implement list_move_rcu(), it has to be atomic or other users will see a partial vm_list.

Quoted 4 lines

Quoted 3 lines

Accept for mmu_shrink, which is write but not delete, thus works without that slow synchronize_rcu.

Quoted 2 lines

I don't really see how you can implement list_move_rcu(), it has to be atomic or other users will see a partial vm_list.

Right, even if we synchronized that step cleanly, rcu-protected users could miss the moving vm during concurrent list walks.

What about using a separate mutex for protecting vm_list instead? Unless I missed some detail, mmu_shrink should allow blocking.

Quoted 7 lines · Jan Kiszka

Quoted 6 lines

Quoted 3 lines

Accept for mmu_shrink, which is write but not delete, thus works without that slow synchronize_rcu.

I don't really see how you can implement list_move_rcu(), it has to be atomic or other users will see a partial vm_list.

Quoted 5 lines

Right, even if we synchronized that step cleanly, rcu-protected users could miss the moving vm during concurrent list walks.

What about using a separate mutex for protecting vm_list instead? Unless I missed some detail, mmu_shrink should allow blocking.

What else does kvm_lock protect?

I think we could simply reduce the amount of time we hold kvm_lock. Pick a vm, ref it, list_move_tail(), unlock, then do the actual shrinking. Of course taking a ref must be done carefully, we might already be in kvm_destroy_vm() at that time.

Quoted 11 lines · Avi Kivity

Quoted 10 lines · Jan Kiszka

Quoted 6 lines

Quoted 3 lines

Accept for mmu_shrink, which is write but not delete, thus works without that slow synchronize_rcu.

I don't really see how you can implement list_move_rcu(), it has to be atomic or other users will see a partial vm_list.

Right, even if we synchronized that step cleanly, rcu-protected users could miss the moving vm during concurrent list walks.

Quoted 4 lines

Quoted 2 lines

What about using a separate mutex for protecting vm_list instead? Unless I missed some detail, mmu_shrink should allow blocking.

What else does kvm_lock protect?

Someone tried to write a locking.txt and stated that it's also protecting enabling/disabling hardware virtualization. But that guy may have overlooked something.

Quoted 6 lines

I think we could simply reduce the amount of time we hold kvm_lock. Pick a vm, ref it, list_move_tail(), unlock, then do the actual shrinking. Of course taking a ref must be done carefully, we might already be in kvm_destroy_vm() at that time.

Plain mutex held across the whole mmu_shrink loop is still simpler and should be sufficient - unless we also have to deal with scalability issues if that handler is able to run concurrently. But based on how we were using kvm_lock so far...

Quoted 12 lines · Jan Kiszka

Quoted 11 lines · Avi Kivity

Quoted 10 lines · Jan Kiszka

Quoted 6 lines

Quoted 3 lines

Accept for mmu_shrink, which is write but not delete, thus works without that slow synchronize_rcu.

I don't really see how you can implement list_move_rcu(), it has to be atomic or other users will see a partial vm_list.

Right, even if we synchronized that step cleanly, rcu-protected users could miss the moving vm during concurrent list walks.

Quoted 8 lines

Quoted 4 lines

Quoted 2 lines

What about using a separate mutex for protecting vm_list instead? Unless I missed some detail, mmu_shrink should allow blocking.

What else does kvm_lock protect?

Someone tried to write a locking.txt and stated that it's also protecting enabling/disabling hardware virtualization. But that guy may have overlooked something.

Right. I guess splitting that lock makes sense.

Quoted 7 lines

Quoted 6 lines

I think we could simply reduce the amount of time we hold kvm_lock. Pick a vm, ref it, list_move_tail(), unlock, then do the actual shrinking. Of course taking a ref must be done carefully, we might already be in kvm_destroy_vm() at that time.

Quoted 4 lines

Plain mutex held across the whole mmu_shrink loop is still simpler and should be sufficient - unless we also have to deal with scalability issues if that handler is able to run concurrently. But based on how we were using kvm_lock so far...

I don't think a mutex would work for kvmclock_cpufreq_notifier(). At the very least, we'd need a preempt_disable() there. At the worst, the notifier won't like sleeping.

Only for walking the list of VMs, we do not need to hold the preemption disabling kvm_lock. Convert stat services, the cpufreq callback and mmu_shrink to RCU. For the latter, special care is required to synchronize its list_move_tail with kvm_destroy_vm.

Signed-off-by Jan Kiszka <[email protected]>

Quoted 5 lines · Jan Kiszka

Only for walking the list of VMs, we do not need to hold the preemption disabling kvm_lock. Convert stat services, the cpufreq callback and mmu_shrink to RCU. For the latter, special care is required to synchronize its list_move_tail with kvm_destroy_vm.

Quoted 1 line

Signed-off-by Jan Kiszka <[email protected]>

Jan,

What is the motivation for this change?