[Qemu-devel] [PATCH] xbzrle: don't check the value in the vm ram repeatedly

[Qemu-devel] [PATCH] xbzrle: don't check the value in the vm ram repeatedly

[arei.gonglei]

From: ChenLiang <chenliang88@huawei.com>

xbzrle_encode_buffer checks the value in the ram repeatedly.
It is risk if runs xbzrle_encode_buffer on changing data.
And it is not necessary.

Reported-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
Signed-off-by: ChenLiang <chenliang88@huawei.com>
Signed-off-by: Gonglei <arei.gonglei@huawei.com>
---
 xbzrle.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/xbzrle.c b/xbzrle.c
index fbcb35d..e2c7595 100644
--- a/xbzrle.c
+++ b/xbzrle.c
@@ -82,6 +82,8 @@ int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
         if (d + 2 > dlen) {
             return -1;
         }
+        i++;
+        nzrun_len++;
         /* not aligned to sizeof(long) */
         res = (slen - i) % sizeof(long);
         while (res && old_buf[i] != new_buf[i]) {
@@ -118,6 +120,8 @@ int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
         memcpy(dst + d, nzrun_start, nzrun_len);
         d += nzrun_len;
         nzrun_len = 0;
+        i++;
+        zrun_len++;
     }
 
     return d;
-- 
1.7.12.4

Re: [Qemu-devel] [PATCH] xbzrle: don't check the value in the vm ram repeatedly

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1469 bytes --]

On 03/29/2014 01:52 AM, arei.gonglei@huawei.com wrote:
> From: ChenLiang <chenliang88@huawei.com>
> 
> xbzrle_encode_buffer checks the value in the ram repeatedly.
> It is risk if runs xbzrle_encode_buffer on changing data.
> And it is not necessary.
> 
> Reported-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
> Signed-off-by: ChenLiang <chenliang88@huawei.com>
> Signed-off-by: Gonglei <arei.gonglei@huawei.com>
> ---
>  xbzrle.c | 4 ++++
>  1 file changed, 4 insertions(+)

Insufficient.  Observe what we did at line 52 when looking for the zero-run:

>>         /* word at a time for speed */
>>         if (!res) {
>>             while (i < slen &&
>>                    (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {

This dereferences 8 bytes at new_buf[i] (on a 64-bit machine)...

>>                 i += sizeof(long);
>>                 zrun_len += sizeof(long);
>>             }
>> 
>>             /* go over the rest */
>>             while (i < slen && old_buf[i] == new_buf[i]) {

...and this also dereferences those same bytes.  But your argument is
that new_buf[i] is volatile.

You MUST read new_buf[i] into a temporary variable, and if the first
read found a difference, then the "go over the rest" analysis must be on
that temporary, rather than going back to reading directly from new_buf.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH] xbzrle: don't check the value in the vm ram repeatedly

[陈梁]

> On 03/29/2014 01:52 AM, arei.gonglei@huawei.com wrote:
>> From: ChenLiang <chenliang88@huawei.com>
>> 
>> xbzrle_encode_buffer checks the value in the ram repeatedly.
>> It is risk if runs xbzrle_encode_buffer on changing data.
>> And it is not necessary.
>> 
>> Reported-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
>> Signed-off-by: ChenLiang <chenliang88@huawei.com>
>> Signed-off-by: Gonglei <arei.gonglei@huawei.com>
>> ---
>> xbzrle.c | 4 ++++
>> 1 file changed, 4 insertions(+)
> 
> Insufficient.  Observe what we did at line 52 when looking for the zero-run:
> 
>>>        /* word at a time for speed */
>>>        if (!res) {
>>>            while (i < slen &&
>>>                   (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {
> 
> This dereferences 8 bytes at new_buf[i] (on a 64-bit machine)...
> 
>>>                i += sizeof(long);
>>>                zrun_len += sizeof(long);
>>>            }
>>> 
>>>            /* go over the rest */
>>>            while (i < slen && old_buf[i] == new_buf[i]) {
> 
> ...and this also dereferences those same bytes.  But your argument is
> that new_buf[i] is volatile.
> 
> You MUST read new_buf[i] into a temporary variable, and if the first
> read found a difference, then the "go over the rest" analysis must be on
> that temporary, rather than going back to reading directly from new_buf.
> 
It is ok, we just need to guarantee that the pages in cache are same to the page in dest side. 
Don‘t care about whether they are same to src side. Because the modified pages during this
time will be sent at next time.
> -- 
> Eric Blake   eblake redhat com    +1-919-301-3266
> Libvirt virtualization library http://libvirt.org
> 

Re: [Qemu-devel] [PATCH] xbzrle: don't check the value in the vm ram repeatedly

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2052 bytes --]

On 03/29/2014 08:15 AM, 陈梁 wrote:

>>
>> Insufficient.  Observe what we did at line 52 when looking for the zero-run:
>>
>>>>        /* word at a time for speed */
>>>>        if (!res) {
>>>>            while (i < slen &&
>>>>                   (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {
>>
>> This dereferences 8 bytes at new_buf[i] (on a 64-bit machine)...
>>
>>>>                i += sizeof(long);
>>>>                zrun_len += sizeof(long);
>>>>            }
>>>>
>>>>            /* go over the rest */
>>>>            while (i < slen && old_buf[i] == new_buf[i]) {
>>
>> ...and this also dereferences those same bytes.  But your argument is
>> that new_buf[i] is volatile.
>>
>> You MUST read new_buf[i] into a temporary variable, and if the first
>> read found a difference, then the "go over the rest" analysis must be on
>> that temporary, rather than going back to reading directly from new_buf.
>>
> It is ok, we just need to guarantee that the pages in cache are same to the page in dest side. 
> Don‘t care about whether they are same to src side. Because the modified pages during this
> time will be sent at next time.

No, it is not okay - if you are reading the same bytes from new_buf, and
new_buf is volatile, then you MUST read each byte of new_buf exactly
once.  Consider this sequence:

old_buf contains

00 00 00 00 00 00 00 00

new_buf initially contains

00 00 00 00 00 00 00 01

so the zrun detection spots that the two buffers are different on the
8-byte read.  But then another thread modifies new_buf to be all zeros.
 Now the "go over the rest" loop does 8 reads, expecting to find a
difference, but it can't find one.

You really need to do the "go over the rest" loop on an 8-byte temporary
variable.  Ever since your patch made new_buf be a volatile buffer,
rather than a static copy, you MUST visit each byte of new_buf exactly once.


-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH] xbzrle: don't check the value in the vm ram repeatedly

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1424 bytes --]

On 03/29/2014 09:00 AM, 陈梁 wrote:

>>> You really need to do the "go over the rest" loop on an 8-byte temporary
>>> variable.  Ever since your patch made new_buf be a volatile buffer,
>>> rather than a static copy, you MUST visit each byte of new_buf exactly once.
>>>
>> hmm, thanks. get it. Maybe we can do it like this

> sorry, it should like this
> 
>         /* word at a time for speed */
>         if (!res) {
>             while (i < slen &&
>                    (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {
>                 i += sizeof(long);
>                 zrun_len += sizeof(long);
>             }
> 
>             /* go over the rest */
>             //while (i < slen && old_buf[i] == new_buf[i]) {
>             //    zrun_len++;
>             //    i++;
>             //}
>         }

No, that's not right either.  Once you have made a decision based on
something you have read, you must proceed with that decision.  In the
case, you broke out of the while loop because you found a difference.
Now you must report the location of that difference, as of the time
where you read it and without re-reading from new_buf.  The ONLY viable
solution is to read the contents of new_buf into a temporary, then do
all subsequent actions on that temporary.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH] xbzrle: don't check the value in the vm ram repeatedly

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1314 bytes --]

On 03/29/2014 09:12 AM, 陈梁 wrote:

>        /* word at a time for speed */
>        if (!res) {
>            while (i < slen &&
>                   (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {
>                i += sizeof(long);
>                zrun_len += sizeof(long);
>            }
> 
>            /* go over the rest */
>            //while (i < slen && old_buf[i] == new_buf[i]) {
>            //    zrun_len++;
>            //    i++;
>            //}
>        }
>        i += sizeof(long);
>        nzrun_len += sizeof(long);

That does not produce a minimal compression (it treats all 8 bytes as
different, even if 7 of them were the same).  It might be a viable
solution if the extra overhead of the additional bytes sent over the
wire is less than the overhead saved by not re-checking the temporary
variable to determine a better compression.  But I'm not convinced - it
seems that reading memory into a register, then doing multiple
operations on that cached value, will be a win (that is, minimal
compression matters, because time spent transmitting bytes over the
network is slower than time spent calculating how to avoid bytes to
transmit).

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH] xbzrle: don't check the value in the vm ram repeatedly

[Dr. David Alan Gilbert]

* ???? (chenliang0016@icloud.com) wrote:

> It is ok, we just need to guarantee that the pages in cache are same to the page in dest side. 
> Don??t care about whether they are same to src side. Because the modified pages during this
> time will be sent at next time.

It's an interesting, if unusual, observation; it means we can send
completely bogus data at this point because we know it will get
overwritten later; I think the requirements are:

  1) That we meet the protocol (which seems to require that the run lengths are
     not allowed to be 0)
  2) That we don't get stuck in any loops or go over the end of the page
     (I think this means we have to be careful of those byte loops within
     the word-at-a-time cases)
  3) The page that ends up in our xbzrle cache must match the destination
     page, since the next cycle of xbzrle will use it as reference.

Dave
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK