[RFC PATCH 0/2] KVM: dirty logging optimization

[RFC PATCH 0/2] KVM: dirty logging optimization

[Takuya Yoshikawa]

Hi,

Yesterday, I tried to read mmu code but soon came back to dirty logging!
  -- My brain's tlb flush seems to have a serious bug!

Soon after that, I reached to this patch set.


What I thought was that I might be able to improve KVM's interactivity
in the future if I can suppress write protection for hot frame buffer
regions by using hint from user land:  This may help us solve the
interactivity problems on the TODO lists in KVM wiki.

 - Just scaling up frame rate will soon suffer from many page faults.
 - Scaling down may result in bad response.


For live-migration, it may be possible to do fine grained get dirty log.


I want to know about this patch's relationship with your O(1) write
protection plan. Is it possible to co-exist?

If so, I will do some performance test.

 - I'm not sure in which conditions this hack has advantages yet.

Any comments will be appriciated!

  Takuya

[RFC PATCH 1/2] KVM: count the number of dirty bits for each memslot

[Takuya Yoshikawa]

This patch introduces the counter to hold the number of dirty bits in each
memslot. We will use this to optimize dirty logging later.

Signed-off-by: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
---
 arch/x86/kvm/x86.c       |    9 +++------
 include/linux/kvm_host.h |    1 +
 virt/kvm/kvm_main.c      |    6 +++++-
 3 files changed, 9 insertions(+), 7 deletions(-)

diff --git a/arch/x86/kvm/x86.c b/arch/x86/kvm/x86.c
index 410d2d1..038d719 100644
--- a/arch/x86/kvm/x86.c
+++ b/arch/x86/kvm/x86.c
@@ -3199,10 +3199,9 @@ static int kvm_vm_ioctl_reinject(struct kvm *kvm,
 int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 				      struct kvm_dirty_log *log)
 {
-	int r, i;
+	int r;
 	struct kvm_memory_slot *memslot;
 	unsigned long n;
-	unsigned long is_dirty = 0;
 
 	mutex_lock(&kvm->slots_lock);
 
@@ -3217,11 +3216,8 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 
 	n = kvm_dirty_bitmap_bytes(memslot);
 
-	for (i = 0; !is_dirty && i < n/sizeof(long); i++)
-		is_dirty = memslot->dirty_bitmap[i];
-
 	/* If nothing is dirty, don't bother messing with page tables. */
-	if (is_dirty) {
+	if (memslot->num_dirty_bits) {
 		struct kvm_memslots *slots, *old_slots;
 		unsigned long *dirty_bitmap;
 
@@ -3236,6 +3232,7 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 			goto out;
 		memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
 		slots->memslots[log->slot].dirty_bitmap = dirty_bitmap;
+		slots->memslots[log->slot].num_dirty_bits = 0;
 		slots->generation++;
 
 		old_slots = kvm->memslots;
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 2d63f2c..07aebf0 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -152,6 +152,7 @@ struct kvm_memory_slot {
 	unsigned long *rmap;
 	unsigned long *dirty_bitmap;
 	unsigned long *dirty_bitmap_head;
+	unsigned long num_dirty_bits;
 	struct {
 		unsigned long rmap_pde;
 		int write_count;
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 339dd43..0a0521b 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -565,6 +565,7 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot)
 		return -ENOMEM;
 
 	memslot->dirty_bitmap_head = memslot->dirty_bitmap;
+	memslot->num_dirty_bits = 0;
 	return 0;
 }
 
@@ -1388,7 +1389,10 @@ void mark_page_dirty_in_slot(struct kvm *kvm, struct kvm_memory_slot *memslot,
 	if (memslot && memslot->dirty_bitmap) {
 		unsigned long rel_gfn = gfn - memslot->base_gfn;
 
-		generic___set_le_bit(rel_gfn, memslot->dirty_bitmap);
+		if (!generic_test_le_bit(rel_gfn, memslot->dirty_bitmap)) {
+			generic___set_le_bit(rel_gfn, memslot->dirty_bitmap);
+			memslot->num_dirty_bits++;
+		}
 	}
 }
 
-- 
1.7.1

[RFC PATCH 2/2] KVM: selective write protection using dirty bitmap

[Takuya Yoshikawa]

Lai Jiangshan once tried to rewrite kvm_mmu_slot_remove_write_access() using
rmap: "kvm: rework remove-write-access for a slot"
      http://www.spinics.net/lists/kvm/msg35871.html

One problem pointed out there was that this approach might hurt cache locality
and make things slow down.

But if we restrict the story to dirty logging, we notice that only small
portion of pages are actually needed to be write protected.

For example, I have confirmed that even when we are playing with tools like
x11perf, dirty ratio of the frame buffer bitmap is almost always less than 10%.

In the case of live-migration, we will see more sparseness in the usual
workload because the RAM size is really big.

So this patch uses his approach with small modification to use switched out
dirty bitmap as a hint to restrict the rmap travel.

We can also use this to selectively write protect pages to reduce unwanted page
faults in the future.

Signed-off-by: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
Cc: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 arch/x86/include/asm/kvm_host.h |    2 ++
 arch/x86/kvm/mmu.c              |   39 +++++++++++++++++++++++++++++++++++++++
 arch/x86/kvm/x86.c              |   27 ++++++++++++++++++++++++---
 3 files changed, 65 insertions(+), 3 deletions(-)

diff --git a/arch/x86/include/asm/kvm_host.h b/arch/x86/include/asm/kvm_host.h
index b04c0fa..bc170e4 100644
--- a/arch/x86/include/asm/kvm_host.h
+++ b/arch/x86/include/asm/kvm_host.h
@@ -617,6 +617,8 @@ void kvm_mmu_set_mask_ptes(u64 user_mask, u64 accessed_mask,
 
 int kvm_mmu_reset_context(struct kvm_vcpu *vcpu);
 void kvm_mmu_slot_remove_write_access(struct kvm *kvm, int slot);
+void kvm_mmu_slot_remove_write_access_mask(struct kvm *kvm,
+		struct kvm_memory_slot *memslot, unsigned long *dirty_bitmap);
 void kvm_mmu_zap_all(struct kvm *kvm);
 unsigned int kvm_mmu_calculate_mmu_pages(struct kvm *kvm);
 void kvm_mmu_change_mmu_pages(struct kvm *kvm, unsigned int kvm_nr_mmu_pages);
diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c
index bdb9fa9..3506a64 100644
--- a/arch/x86/kvm/mmu.c
+++ b/arch/x86/kvm/mmu.c
@@ -3454,6 +3454,45 @@ void kvm_mmu_slot_remove_write_access(struct kvm *kvm, int slot)
 	kvm_flush_remote_tlbs(kvm);
 }
 
+static void rmapp_remove_write_access(struct kvm *kvm, unsigned long *rmapp)
+{
+	u64 *spte = rmap_next(kvm, rmapp, NULL);
+
+	while (spte) {
+		/* avoid RMW */
+		if (is_writable_pte(*spte))
+			*spte &= ~PT_WRITABLE_MASK;
+		spte = rmap_next(kvm, rmapp, spte);
+	}
+}
+
+/*
+ * Write protect the pages set dirty in a given bitmap.
+ */
+void kvm_mmu_slot_remove_write_access_mask(struct kvm *kvm,
+					   struct kvm_memory_slot *memslot,
+					   unsigned long *dirty_bitmap)
+{
+	int i;
+	unsigned long gfn_offset;
+
+	for_each_set_bit(gfn_offset, dirty_bitmap, memslot->npages) {
+		rmapp_remove_write_access(kvm, &memslot->rmap[gfn_offset]);
+
+		for (i = 0; i < KVM_NR_PAGE_SIZES - 1; i++) {
+			unsigned long gfn = memslot->base_gfn + gfn_offset;
+			unsigned long huge = KVM_PAGES_PER_HPAGE(i + 2);
+			int idx = gfn / huge - memslot->base_gfn / huge;
+
+			if (!(gfn_offset || (gfn % huge)))
+				break;
+			rmapp_remove_write_access(kvm,
+					&memslot->lpage_info[i][idx].rmap_pde);
+		}
+	}
+	kvm_flush_remote_tlbs(kvm);
+}
+
 void kvm_mmu_zap_all(struct kvm *kvm)
 {
 	struct kvm_mmu_page *sp, *node;
diff --git a/arch/x86/kvm/x86.c b/arch/x86/kvm/x86.c
index 038d719..3556b4d 100644
--- a/arch/x86/kvm/x86.c
+++ b/arch/x86/kvm/x86.c
@@ -3194,12 +3194,27 @@ static int kvm_vm_ioctl_reinject(struct kvm *kvm,
 }
 
 /*
+ * Check the dirty bit ratio of a given memslot.
+ *   0: clean
+ *   1: sparse
+ *   2: dense
+ */
+static int dirty_bitmap_density(struct kvm_memory_slot *memslot)
+{
+	if (!memslot->num_dirty_bits)
+		return 0;
+	if (memslot->num_dirty_bits < memslot->npages / 128)
+		return 1;
+	return 2;
+}
+
+/*
  * Get (and clear) the dirty memory log for a memory slot.
  */
 int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 				      struct kvm_dirty_log *log)
 {
-	int r;
+	int r, density;
 	struct kvm_memory_slot *memslot;
 	unsigned long n;
 
@@ -3217,7 +3232,8 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 	n = kvm_dirty_bitmap_bytes(memslot);
 
 	/* If nothing is dirty, don't bother messing with page tables. */
-	if (memslot->num_dirty_bits) {
+	density = dirty_bitmap_density(memslot);
+	if (density) {
 		struct kvm_memslots *slots, *old_slots;
 		unsigned long *dirty_bitmap;
 
@@ -3242,7 +3258,12 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 		kfree(old_slots);
 
 		spin_lock(&kvm->mmu_lock);
-		kvm_mmu_slot_remove_write_access(kvm, log->slot);
+		if (density == 2)
+			kvm_mmu_slot_remove_write_access(kvm, log->slot);
+		else
+			kvm_mmu_slot_remove_write_access_mask(kvm,
+						&slots->memslots[log->slot],
+						dirty_bitmap);
 		spin_unlock(&kvm->mmu_lock);
 
 		r = -EFAULT;
-- 
1.7.1

Re: [RFC PATCH 1/2] KVM: count the number of dirty bits for each memslot

[Avi Kivity]

On 11/18/2010 07:14 AM, Takuya Yoshikawa wrote:
> This patch introduces the counter to hold the number of dirty bits in each
> memslot. We will use this to optimize dirty logging later.
>
>
> @@ -3217,11 +3216,8 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
>
>   	n = kvm_dirty_bitmap_bytes(memslot);
>
> -	for (i = 0; !is_dirty&&  i<  n/sizeof(long); i++)
> -		is_dirty = memslot->dirty_bitmap[i];
> -

This can already be an improvement.
> @@ -152,6 +152,7 @@ struct kvm_memory_slot {
>   	unsigned long *rmap;
>   	unsigned long *dirty_bitmap;
>   	unsigned long *dirty_bitmap_head;
> +	unsigned long num_dirty_bits;

The bits themselves are not dirty; only the pages are dirty.

(+ we usually use 'nr' for 'number')



-- 
error compiling committee.c: too many arguments to function

Re: [RFC PATCH 2/2] KVM: selective write protection using dirty bitmap

[Avi Kivity]

On 11/18/2010 07:15 AM, Takuya Yoshikawa wrote:
> Lai Jiangshan once tried to rewrite kvm_mmu_slot_remove_write_access() using
> rmap: "kvm: rework remove-write-access for a slot"
>        http://www.spinics.net/lists/kvm/msg35871.html
>
> One problem pointed out there was that this approach might hurt cache locality
> and make things slow down.
>
> But if we restrict the story to dirty logging, we notice that only small
> portion of pages are actually needed to be write protected.
>
> For example, I have confirmed that even when we are playing with tools like
> x11perf, dirty ratio of the frame buffer bitmap is almost always less than 10%.
>
> In the case of live-migration, we will see more sparseness in the usual
> workload because the RAM size is really big.
>
> So this patch uses his approach with small modification to use switched out
> dirty bitmap as a hint to restrict the rmap travel.
>
> We can also use this to selectively write protect pages to reduce unwanted page
> faults in the future.
>

Looks like a good approach.  Any measurements?

>
> +static void rmapp_remove_write_access(struct kvm *kvm, unsigned long *rmapp)
> +{
> +	u64 *spte = rmap_next(kvm, rmapp, NULL);
> +
> +	while (spte) {
> +		/* avoid RMW */
> +		if (is_writable_pte(*spte))
> +			*spte&= ~PT_WRITABLE_MASK;

This is racy, *spte can be modified concurrently by hardware.

update_spte() can be used for this.

> +		spte = rmap_next(kvm, rmapp, spte);
> +	}
> +}
> +
> +/*
> + * Write protect the pages set dirty in a given bitmap.
> + */
> +void kvm_mmu_slot_remove_write_access_mask(struct kvm *kvm,
> +					   struct kvm_memory_slot *memslot,
> +					   unsigned long *dirty_bitmap)
> +{
> +	int i;
> +	unsigned long gfn_offset;
> +
> +	for_each_set_bit(gfn_offset, dirty_bitmap, memslot->npages) {
> +		rmapp_remove_write_access(kvm,&memslot->rmap[gfn_offset]);
> +
> +		for (i = 0; i<  KVM_NR_PAGE_SIZES - 1; i++) {
> +			unsigned long gfn = memslot->base_gfn + gfn_offset;
> +			unsigned long huge = KVM_PAGES_PER_HPAGE(i + 2);
> +			int idx = gfn / huge - memslot->base_gfn / huge;

Better to use a shift than a division here.

> +
> +			if (!(gfn_offset || (gfn % huge)))
> +				break;

Why?

> +			rmapp_remove_write_access(kvm,
> +					&memslot->lpage_info[i][idx].rmap_pde);
> +		}
> +	}
> +	kvm_flush_remote_tlbs(kvm);
> +}
> +
>   void kvm_mmu_zap_all(struct kvm *kvm)
>   {
>   	struct kvm_mmu_page *sp, *node;
> diff --git a/arch/x86/kvm/x86.c b/arch/x86/kvm/x86.c
> index 038d719..3556b4d 100644
> --- a/arch/x86/kvm/x86.c
> +++ b/arch/x86/kvm/x86.c
> @@ -3194,12 +3194,27 @@ static int kvm_vm_ioctl_reinject(struct kvm *kvm,
>   }
>
>   /*
> + * Check the dirty bit ratio of a given memslot.
> + *   0: clean
> + *   1: sparse
> + *   2: dense
> + */
> +static int dirty_bitmap_density(struct kvm_memory_slot *memslot)
> +{
> +	if (!memslot->num_dirty_bits)
> +		return 0;
> +	if (memslot->num_dirty_bits<  memslot->npages / 128)
> +		return 1;
> +	return 2;
> +}

Use an enum please.

> +
> +/*
>    * Get (and clear) the dirty memory log for a memory slot.
>    */
>   int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
>   				      struct kvm_dirty_log *log)
>   {
> -	int r;
> +	int r, density;
>   	struct kvm_memory_slot *memslot;
>   	unsigned long n;
>
> @@ -3217,7 +3232,8 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
>   	n = kvm_dirty_bitmap_bytes(memslot);
>
>   	/* If nothing is dirty, don't bother messing with page tables. */
> -	if (memslot->num_dirty_bits) {
> +	density = dirty_bitmap_density(memslot);
> +	if (density) {
>   		struct kvm_memslots *slots, *old_slots;
>   		unsigned long *dirty_bitmap;
>
> @@ -3242,7 +3258,12 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
>   		kfree(old_slots);
>
>   		spin_lock(&kvm->mmu_lock);
> -		kvm_mmu_slot_remove_write_access(kvm, log->slot);
> +		if (density == 2)
> +			kvm_mmu_slot_remove_write_access(kvm, log->slot);
> +		else
> +			kvm_mmu_slot_remove_write_access_mask(kvm,
> +						&slots->memslots[log->slot],
> +						dirty_bitmap);
>   		spin_unlock(&kvm->mmu_lock);

wrt. O(1) write protection: hard to tell if the two methods can 
coexist.  For direct mapped shadow pages (i.e. ep/npt) I think we can 
use the mask to speed up clearing of an individual sp's sptes.

-- 
error compiling committee.c: too many arguments to function

Re: [RFC PATCH 1/2] KVM: count the number of dirty bits for each memslot

[Jan Kiszka]

Am 18.11.2010 13:54, Avi Kivity wrote:
> On 11/18/2010 07:14 AM, Takuya Yoshikawa wrote:
>> This patch introduces the counter to hold the number of dirty bits in
>> each
>> memslot. We will use this to optimize dirty logging later.
>>
>>
>> @@ -3217,11 +3216,8 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
>>
>>       n = kvm_dirty_bitmap_bytes(memslot);
>>
>> -    for (i = 0; !is_dirty&&  i<  n/sizeof(long); i++)
>> -        is_dirty = memslot->dirty_bitmap[i];
>> -
> 
> This can already be an improvement.

/Me wonders if it wouldn't make sense to expand this optimization to the
user space interface as well, i.e. signaling "there are no dirty pages"
via some flag instead of writing zeros in a bitmap. Of course, this
means supporting both interfaces for a longer period.

Jan

-- 
Siemens AG, Corporate Technology, CT T DE IT 1
Corporate Competence Center Embedded Linux

Re: [RFC PATCH 1/2] KVM: count the number of dirty bits for each memslot

[Avi Kivity]

On 11/18/2010 03:10 PM, Jan Kiszka wrote:
> Am 18.11.2010 13:54, Avi Kivity wrote:
> >  On 11/18/2010 07:14 AM, Takuya Yoshikawa wrote:
> >>  This patch introduces the counter to hold the number of dirty bits in
> >>  each
> >>  memslot. We will use this to optimize dirty logging later.
> >>
> >>
> >>  @@ -3217,11 +3216,8 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
> >>
> >>        n = kvm_dirty_bitmap_bytes(memslot);
> >>
> >>  -    for (i = 0; !is_dirty&&   i<   n/sizeof(long); i++)
> >>  -        is_dirty = memslot->dirty_bitmap[i];
> >>  -
> >
> >  This can already be an improvement.
>
> /Me wonders if it wouldn't make sense to expand this optimization to the
> user space interface as well, i.e. signaling "there are no dirty pages"
> via some flag instead of writing zeros in a bitmap. Of course, this
> means supporting both interfaces for a longer period.

An 8MB framebuffer is 2K bits, or 256 bytes wide.  Comparing 256 cache 
hot bytes against zero is not worth a new interface.

Larger memory slots are very unlikely to be always unmodified.

-- 
error compiling committee.c: too many arguments to function

Re: [RFC PATCH 2/2] KVM: selective write protection using dirty bitmap

[Takuya Yoshikawa]

(2010/11/18 22:06), Avi Kivity wrote:
> On 11/18/2010 07:15 AM, Takuya Yoshikawa wrote:

>>
>> We can also use this to selectively write protect pages to reduce unwanted page
>> faults in the future.
>>
>
> Looks like a good approach. Any measurements?
>

OK, I'll do some tests to select a right approach.

Personally, and some as a job if possible, I'm planning various things.


a) Frame buffer: small bitmap size (my hobby now)

    Performance:
      Both function level and guest side measurements is necessary. *1
      For interactivity, qemu side intelligence may be needed.
      Note: qemu side dirty bitmap optimization by Kemari team is pending now.

    Correctness:
      I doubt qemu side but I'm not good at device level VGA details yet, sorry.

    *1) I once tried to update dirty bitmap without srcu sync by using
        atomic_clear_mask() word by word. This seemed to be working and
        get_dirty_log() was not bad. But when I tested x11perf inside the guest,
        the numbers were worse than the original implementation (LOCK_PREFIX
        might do bad things to the cache and srcu reader side suffered, I guess).

        Good SRCU!


b) Live-migration: large bitmap size (my target is ~4GB RAM now)

    Performance:
      Scalability is important in both RAM size and number of dirty pages point
      of view. We need to achieve this goal without sacrificing the low workload
      case.

    Correctness:
      I'm trying to make live-migration fail in the condition of without mst's fix
      by multi threaded high work load. SMP is necessary.


>
>> +
>> + if (!(gfn_offset || (gfn % huge)))
>> + break;
>
> Why?

I preserved these lines from Lai's original.
 >> http://www.spinics.net/lists/kvm/msg35871.html

But OK, I found some duplication probably. I'll fix.


>
> wrt. O(1) write protection: hard to tell if the two methods can coexist. For direct mapped shadow pages (i.e. ep/npt) I think we can use the mask to speed up clearing of an individual sp's sptes.
>

OK, I'll test both with and without NPT.
The result may lead us to the right direction.



Takuya