[v6,27/29] KVM: Optimize overlapping memslots check

Commit Message

Maciej S. Szmigiero Nov. 30, 2021, 9:41 p.m. UTC

From: "Maciej S. Szmigiero" <[e-mail]>

Do a quick lookup for possibly overlapping gfns when creating or moving
a memslot instead of performing a linear scan of the whole memslot set.

Signed-off-by: Maciej S. Szmigiero <[e-mail]>
[sean: tweaked params to avoid churn in future cleanup]
Signed-off-by: Sean Christopherson <[e-mail]>
---
 virt/kvm/kvm_main.c | 35 +++++++++++++++++++++--------------
 1 file changed, 21 insertions(+), 14 deletions(-)

Comments

Sean Christopherson Dec. 1, 2021, 3:08 a.m. UTC | #1

On Tue, Nov 30, 2021, Maciej S. Szmigiero wrote:
> From: "Maciej S. Szmigiero" <[e-mail]>
> 
> Do a quick lookup for possibly overlapping gfns when creating or moving
> a memslot instead of performing a linear scan of the whole memslot set.
> 
> Signed-off-by: Maciej S. Szmigiero <[e-mail]>
> [sean: tweaked params to avoid churn in future cleanup]
> Signed-off-by: Sean Christopherson <[e-mail]>
> ---
>  virt/kvm/kvm_main.c | 35 +++++++++++++++++++++--------------
>  1 file changed, 21 insertions(+), 14 deletions(-)
> 
> diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
> index 086f18969bc3..52117f65bc5b 100644
> --- a/virt/kvm/kvm_main.c
> +++ b/virt/kvm/kvm_main.c
> @@ -1817,6 +1817,18 @@ static int kvm_set_memslot(struct kvm *kvm,
>  	return 0;
>  }
>  
> +static bool kvm_check_memslot_overlap(struct kvm_memslots *slots, int id,
> +				      gfn_t start, gfn_t end)
> +{
> +	struct kvm_memslot_iter iter;
> +
> +	kvm_for_each_memslot_in_gfn_range(&iter, slots, start, end)

The for loop needs curly braces, per coding-style.rst:

Also, use braces when a loop contains more than a single simple statement:

.. code-block:: c

        while (condition) {
                if (test)
                        do_something();
        }

With that,

Reviewed-by: Sean Christopherson <[e-mail]>

Maciej S. Szmigiero Dec. 1, 2021, 3:45 p.m. UTC | #2

On 01.12.2021 04:08, Sean Christopherson wrote:
> On Tue, Nov 30, 2021, Maciej S. Szmigiero wrote:
>> From: "Maciej S. Szmigiero" <[e-mail]>
>>
>> Do a quick lookup for possibly overlapping gfns when creating or moving
>> a memslot instead of performing a linear scan of the whole memslot set.
>>
>> Signed-off-by: Maciej S. Szmigiero <[e-mail]>
>> [sean: tweaked params to avoid churn in future cleanup]
>> Signed-off-by: Sean Christopherson <[e-mail]>
>> ---
>>   virt/kvm/kvm_main.c | 35 +++++++++++++++++++++--------------
>>   1 file changed, 21 insertions(+), 14 deletions(-)
>>
>> diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
>> index 086f18969bc3..52117f65bc5b 100644
>> --- a/virt/kvm/kvm_main.c
>> +++ b/virt/kvm/kvm_main.c
>> @@ -1817,6 +1817,18 @@ static int kvm_set_memslot(struct kvm *kvm,
>>   	return 0;
>>   }
>>   
>> +static bool kvm_check_memslot_overlap(struct kvm_memslots *slots, int id,
>> +				      gfn_t start, gfn_t end)
>> +{
>> +	struct kvm_memslot_iter iter;
>> +
>> +	kvm_for_each_memslot_in_gfn_range(&iter, slots, start, end)
> 
> The for loop needs curly braces, per coding-style.rst:
> 
> Also, use braces when a loop contains more than a single simple statement:
> 
> .. code-block:: c
> 
>          while (condition) {
>                  if (test)
>                          do_something();
>          }
> 
> With that,
> 
> Reviewed-by: Sean Christopherson <[e-mail]>
> 

Will add these braces (and your R-b, too).

Thanks,
Maciej

Patch

diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 086f18969bc3..52117f65bc5b 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -1817,6 +1817,18 @@  static int kvm_set_memslot(struct kvm *kvm,
 	return 0;
 }
 
+static bool kvm_check_memslot_overlap(struct kvm_memslots *slots, int id,
+				      gfn_t start, gfn_t end)
+{
+	struct kvm_memslot_iter iter;
+
+	kvm_for_each_memslot_in_gfn_range(&iter, slots, start, end)
+		if (kvm_memslot_iter_slot(&iter)->id != id)
+			return true;
+
+	return false;
+}
+
 /*
  * Allocate some memory and give it an address in the guest physical address
  * space.
@@ -1828,8 +1840,9 @@  static int kvm_set_memslot(struct kvm *kvm,
 int __kvm_set_memory_region(struct kvm *kvm,
 			    const struct kvm_userspace_memory_region *mem)
 {
-	struct kvm_memory_slot *old, *tmp;
+	struct kvm_memory_slot *old;
 	struct kvm_memory_slot new;
+	struct kvm_memslots *slots;
 	enum kvm_mr_change change;
 	int as_id, id;
 	int r;
@@ -1858,11 +1871,13 @@  int __kvm_set_memory_region(struct kvm *kvm,
 	if (mem->guest_phys_addr + mem->memory_size < mem->guest_phys_addr)
 		return -EINVAL;
 
+	slots = __kvm_memslots(kvm, as_id);
+
 	/*
 	 * Note, the old memslot (and the pointer itself!) may be invalidated
 	 * and/or destroyed by kvm_set_memslot().
 	 */
-	old = id_to_memslot(__kvm_memslots(kvm, as_id), id);
+	old = id_to_memslot(slots, id);
 
 	if (!mem->memory_size) {
 		if (!old || !old->npages)
@@ -1911,18 +1926,10 @@  int __kvm_set_memory_region(struct kvm *kvm,
 			return 0;
 	}
 
-	if ((change == KVM_MR_CREATE) || (change == KVM_MR_MOVE)) {
-		int bkt;
-
-		/* Check for overlaps */
-		kvm_for_each_memslot(tmp, bkt, __kvm_memslots(kvm, as_id)) {
-			if (tmp->id == id)
-				continue;
-			if (!((new.base_gfn + new.npages <= tmp->base_gfn) ||
-			      (new.base_gfn >= tmp->base_gfn + tmp->npages)))
-				return -EEXIST;
-		}
-	}
+	if ((change == KVM_MR_CREATE || change == KVM_MR_MOVE) &&
+	    kvm_check_memslot_overlap(slots, id, new.base_gfn,
+				      new.base_gfn + new.npages))
+		return -EEXIST;
 
 	return kvm_set_memslot(kvm, old, &new, change);
 }