Patchwork [v15,6/9] Add xbzrle_encode_buffer and xbzrle_decode_buffer functions

login
register
mail settings
Submitter Orit Wasserman
Date July 5, 2012, 12:51 p.m.
Message ID <1341492709-13897-7-git-send-email-owasserm@redhat.com>
Download mbox | patch
Permalink /patch/169157/
State New
Headers show

Comments

Orit Wasserman - July 5, 2012, 12:51 p.m.
Signed-off-by: Benoit Hudzia <benoit.hudzia@sap.com>
Signed-off-by: Petter Svard <petters@cs.umu.se>
Signed-off-by: Aidan Shribman <aidan.shribman@sap.com>
Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 migration.h |    4 ++
 savevm.c    |  157 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 161 insertions(+), 0 deletions(-)
Eric Blake - July 5, 2012, 1:55 p.m.
On 07/05/2012 06:51 AM, Orit Wasserman wrote:

This commit message is a bit sparse.  I'd document at least the fact
that our nzrun detection code in xbzrle_encode_buffer borrows
long-word-at-a-time NUL-detection tricks from strcmp(), as it is not an
intuitive trick known by all developers.

> Signed-off-by: Benoit Hudzia <benoit.hudzia@sap.com>
> Signed-off-by: Petter Svard <petters@cs.umu.se>
> Signed-off-by: Aidan Shribman <aidan.shribman@sap.com>
> Signed-off-by: Orit Wasserman <owasserm@redhat.com>

I think I touched this one heavily enough that it warrants adding:

Signed-off-by: Eric Blake <eblake@redhat.com>

Other than the commit message, I'm happy with this patch contents now.
Still some nits, though:

> +
> +         /* not aligned to sizeof(long) */
> +        res = (slen - i) % sizeof(long);

Comment indentation is off.

> +        while (res && old_buf[i] == new_buf[i]) {
> +            zrun_len++;
> +            i++;
> +            res--;
> +        }
> +
> +        if (!res) {

A comment here might help:

/* word at a time for speed */

> +            while (i < slen &&
> +                   (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {

On re-reading this, I'm worried whether it violates strict C99 aliasing
rules; I'm hoping the compiler doesn't mis-optimize it based on a
loophole of us using questionable semantics.  In practice, I'm confident
that we are only doing aligned reads (otherwise I wouldn't have
suggested this line in the first place), which is why I'm personally
okay with it even if it technically violates C99.  However, I'm open to
suggestions from anyone else on the list on how to better express the
notion of intentionally accessing a long at a time from an aligned
offset into a byte array, if that will help us avoid even theoretical
problems.

> +            nzrun_len++;
> +            res--;
> +        }
> +
> +        if (!res) {
> +            /* truncation to 32-bit long okay */

Again, a longer comment might help:

/* word at a time for speed, use of 32-bit long okay */

> +            long mask = 0x0101010101010101ULL;
> +            while (i < slen) {
> +                xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i);

Same potential strict aliasing problems as for zrun detection.
Orit Wasserman - July 5, 2012, 6:01 p.m.
On 07/05/2012 04:55 PM, Eric Blake wrote:
> On 07/05/2012 06:51 AM, Orit Wasserman wrote:
> 
> This commit message is a bit sparse.  I'd document at least the fact
> that our nzrun detection code in xbzrle_encode_buffer borrows
> long-word-at-a-time NUL-detection tricks from strcmp(), as it is not an
> intuitive trick known by all developers.
> 
>> Signed-off-by: Benoit Hudzia <benoit.hudzia@sap.com>
>> Signed-off-by: Petter Svard <petters@cs.umu.se>
>> Signed-off-by: Aidan Shribman <aidan.shribman@sap.com>
>> Signed-off-by: Orit Wasserman <owasserm@redhat.com>
> 
> I think I touched this one heavily enough that it warrants adding:
> 
> Signed-off-by: Eric Blake <eblake@redhat.com>
> 
Of course
Orit
> Other than the commit message, I'm happy with this patch contents now.
> Still some nits, though:
> 
>> +
>> +         /* not aligned to sizeof(long) */
>> +        res = (slen - i) % sizeof(long);
> 
> Comment indentation is off.
> 
>> +        while (res && old_buf[i] == new_buf[i]) {
>> +            zrun_len++;
>> +            i++;
>> +            res--;
>> +        }
>> +
>> +        if (!res) {
> 
> A comment here might help:
> 
> /* word at a time for speed */
> 
>> +            while (i < slen &&
>> +                   (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {
> 
> On re-reading this, I'm worried whether it violates strict C99 aliasing
> rules; I'm hoping the compiler doesn't mis-optimize it based on a
> loophole of us using questionable semantics.  In practice, I'm confident
> that we are only doing aligned reads (otherwise I wouldn't have
> suggested this line in the first place), which is why I'm personally
> okay with it even if it technically violates C99.  However, I'm open to
> suggestions from anyone else on the list on how to better express the
> notion of intentionally accessing a long at a time from an aligned
> offset into a byte array, if that will help us avoid even theoretical
> problems.
This is a very interesting question ....

Orit
> 
>> +            nzrun_len++;
>> +            res--;
>> +        }
>> +
>> +        if (!res) {
>> +            /* truncation to 32-bit long okay */
> 
> Again, a longer comment might help:
> 
> /* word at a time for speed, use of 32-bit long okay */
> 
>> +            long mask = 0x0101010101010101ULL;
>> +            while (i < slen) {
>> +                xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i);
> 
> Same potential strict aliasing problems as for zrun detection.
>

Patch

diff --git a/migration.h b/migration.h
index acc0b94..c46af82 100644
--- a/migration.h
+++ b/migration.h
@@ -100,4 +100,8 @@  void migrate_add_blocker(Error *reason);
  */
 void migrate_del_blocker(Error *reason);
 
+int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
+                         uint8_t *dst, int dlen);
+int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen);
+
 #endif
diff --git a/savevm.c b/savevm.c
index a15c163..1534cbd 100644
--- a/savevm.c
+++ b/savevm.c
@@ -2385,3 +2385,160 @@  void vmstate_register_ram_global(MemoryRegion *mr)
 {
     vmstate_register_ram(mr, NULL);
 }
+
+/*
+  page = zrun nzrun
+       | zrun nzrun page
+
+  zrun = length
+
+  nzrun = length byte...
+
+  length = uleb128 encoded integer
+ */
+int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
+                         uint8_t *dst, int dlen)
+{
+    uint32_t zrun_len = 0, nzrun_len = 0;
+    int d = 0, i = 0;
+    long res, xor;
+    uint8_t *nzrun_start = NULL;
+
+    g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) %
+               sizeof(long)));
+
+    while (i < slen) {
+        /* overflow */
+        if (d + 2 > dlen) {
+            return -1;
+        }
+
+         /* not aligned to sizeof(long) */
+        res = (slen - i) % sizeof(long);
+        while (res && old_buf[i] == new_buf[i]) {
+            zrun_len++;
+            i++;
+            res--;
+        }
+
+        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++;
+            }
+        }
+
+        /* buffer unchanged */
+        if (zrun_len == slen) {
+            return 0;
+        }
+
+        /* skip last zero run */
+        if (i == slen) {
+            return d;
+        }
+
+        d += uleb128_encode_small(dst + d, zrun_len);
+
+        zrun_len = 0;
+        nzrun_start = new_buf + i;
+
+        /* overflow */
+        if (d + 2 > dlen) {
+            return -1;
+        }
+        /* not aligned to sizeof(long) */
+        res = (slen - i) % sizeof(long);
+        while (res && old_buf[i] != new_buf[i]) {
+            i++;
+            nzrun_len++;
+            res--;
+        }
+
+        if (!res) {
+            /* truncation to 32-bit long okay */
+            long mask = 0x0101010101010101ULL;
+            while (i < slen) {
+                xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i);
+                if ((xor - mask) & ~xor & (mask << 7)) {
+                    /* found the end of an nzrun within the current long */
+                    while (old_buf[i] != new_buf[i]) {
+                        nzrun_len++;
+                        i++;
+                    }
+                    break;
+                } else {
+                    i += sizeof(long);
+                    nzrun_len += sizeof(long);
+                }
+            }
+        }
+
+        d += uleb128_encode_small(dst + d, nzrun_len);
+        /* overflow */
+        if (d + nzrun_len > dlen) {
+            return -1;
+        }
+        memcpy(dst + d, nzrun_start, nzrun_len);
+        d += nzrun_len;
+        nzrun_len = 0;
+    }
+
+    return d;
+}
+
+int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)
+{
+    int i = 0, d = 0;
+    int ret;
+    uint32_t count = 0;
+
+    while (i < slen) {
+
+        /* zrun */
+        if ((slen - i) < 2) {
+            return -1;
+        }
+
+        ret = uleb128_decode_small(src + i, &count);
+        if (ret < 0 || (i && !count)) {
+            return -1;
+        }
+        i += ret;
+        d += count;
+
+        /* overflow */
+        if (d > dlen) {
+            return -1;
+        }
+
+        /* nzrun */
+        if ((slen - i) < 2) {
+            return -1;
+        }
+
+        ret = uleb128_decode_small(src + i, &count);
+        if (ret < 0 || !count) {
+            return -1;
+        }
+        i += ret;
+
+        /* overflow */
+        if (d + count > dlen || i + count > slen) {
+            return -1;
+        }
+
+        memcpy(dst + d , src + i, count);
+        d += count;
+        i += count;
+    }
+
+    return d;
+}