diff mbox

[06/11] Add xbzrle_encode_buffer and xbzrle_decode_buffer functions

Message ID 1343227834-5400-8-git-send-email-owasserm@redhat.com
State New
Headers show

Commit Message

Orit Wasserman July 25, 2012, 2:50 p.m. UTC 
For performance we are encoding long word at a time.
For nzrun we use long-word-at-a-time NULL-detection tricks from strcmp():
using ((lword - 0x0101010101010101) & (~lword) & 0x8080808080808080) test
to find out if any byte in the long word is zero.

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>
Signed-off-by: Eric Blake <eblake@redhat.com>
---
 migration.h |    4 ++
 savevm.c    |  159 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 163 insertions(+), 0 deletions(-)

Comments

Eric Blake July 26, 2012, 9:58 p.m. UTC | #1 
On 07/25/2012 08:50 AM, Orit Wasserman wrote:
> For performance we are encoding long word at a time.
> For nzrun we use long-word-at-a-time NULL-detection tricks from strcmp():

[Technically, 'NUL' is the byte with value 0x00, 'NULL' is the pointer
with typical value 0x00000000 or 0x0000000000000000, depending on
whether you are 32-bit or 64-bit.  But it's not worth rewriting this
commit message just to delete an 'L']

> using ((lword - 0x0101010101010101) & (~lword) & 0x8080808080808080) test
> to find out if any byte in the long word is zero.
> 
> 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>
> Signed-off-by: Eric Blake <eblake@redhat.com>
> ---

> +int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)

> +
> +        memcpy(dst + d , src + i, count);

I think coding style prefers no space before ','.  But if the patch
checker didn't warn...
Mitsyanko Igor Aug. 15, 2012, 4:22 p.m. UTC | #2 
This patch broke master build, it causes compilation error with gcc 4.6.1:

/home/mackross/eclipse_linux_cdt_space/qemu_exynos4/savevm.c: In 
function ‘xbzrle_encode_buffer’:
/home/mackross/eclipse_linux_cdt_space/qemu_exynos4/savevm.c:2476:13: 
error: overflow in implicit constant conversion [-Werror=overflow]
cc1: all warnings being treated as errors

make[1]: *** [savevm.o] Error 1
make[1]: *** Waiting for unfinished jobs....
make: *** [subdir-arm-softmmu] Error 2



On 07/25/2012 06:50 PM, Orit Wasserman wrote:
> For performance we are encoding long word at a time.
> For nzrun we use long-word-at-a-time NULL-detection tricks from strcmp():
> using ((lword - 0x0101010101010101) & (~lword) & 0x8080808080808080) test
> to find out if any byte in the long word is zero.
>
> 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>
> Signed-off-by: Eric Blake <eblake@redhat.com>
> ---
>   migration.h |    4 ++
>   savevm.c    |  159 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>   2 files changed, 163 insertions(+), 0 deletions(-)
>
> diff --git a/migration.h b/migration.h
> index 713aae0..743c366 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 6e82b2d..c5fd13f 100644
> --- a/savevm.c
> +++ b/savevm.c
> @@ -2392,3 +2392,162 @@ 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--;
> +        }
> +
> +        /* 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++;
> +            }
> +        }
> +
> +        /* 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--;
> +        }
> +
> +        /* word at a time for speed, use of 32-bit long okay */
> +        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;
> +}
>
Eric Blake Aug. 15, 2012, 4:36 p.m. UTC | #3 
On 08/15/2012 10:22 AM, Igor Mitsyanko wrote:
> This patch broke master build, it causes compilation error with gcc 4.6.1:
> 
> /home/mackross/eclipse_linux_cdt_space/qemu_exynos4/savevm.c: In
> function ‘xbzrle_encode_buffer’:
> /home/mackross/eclipse_linux_cdt_space/qemu_exynos4/savevm.c:2476:13:
> error: overflow in implicit constant conversion [-Werror=overflow]
> cc1: all warnings being treated as errors

You're the third to notice:
https://lists.gnu.org/archive/html/qemu-devel/2012-08/msg02446.html
https://lists.gnu.org/archive/html/qemu-devel/2012-08/msg02736.html

and it's already in the ppc PULL request:
https://lists.gnu.org/archive/html/qemu-devel/2012-08/msg02755.html
diff mbox

Patch

diff --git a/migration.h b/migration.h
index 713aae0..743c366 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 6e82b2d..c5fd13f 100644
--- a/savevm.c
+++ b/savevm.c
@@ -2392,3 +2392,162 @@  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--;
+        }
+
+        /* 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++;
+            }
+        }
+
+        /* 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--;
+        }
+
+        /* word at a time for speed, use of 32-bit long okay */
+        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;
+}