Skip to contentSkip to conversation

migration/xbzrle: make xbzrle_encode_buffer little easier

PATCH In review Wei Yang 4 participants 11 messages Jun 10, 2019 – Jun 12, 2019

lore
Share & tools
lore

Wei Yang

author
#0 lore raw

cover migration/xbzrle: make xbzrle_encode_buffer little easier

Current xbzrle_encode_buffer() do everything in a big loop, which is a little difficult for audience to catch the logic.

We can refine the logic with:

* get the length of a run
* encode it

At the same time, I found the encoding and decoding function has some extra pointer operation. Removing this could save some code space.

Wei Yang (2):
cutils: remove one unnecessary pointer operation migration/xbzrle: make xbzrle_encode_buffer little easier to read

 migration/xbzrle.c | 153 +++++++++++++++++++++------------------------
 util/cutils.c      |   8 +--
 2 files changed, 77 insertions(+), 84 deletions(-)
Signature · 1 line
2.19.1
author
#1 lore raw

PATCH 1/2 cutils: remove one unnecessary pointer operation

Since we will not operate on the next address pointed by out, it is not necessary to do addition on it.

After removing the operation, the function size reduced 16/18 bytes.

---
 util/cutils.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
util/cutils.c +4 -4
index 9aacc422ca..1933a68da5 100644
@@ -754,11 +754,11 @@ int uleb128_encode_small(uint8_t *out, uint32_t n)
 {
     g_assert(n <= 0x3fff);
     if (n < 0x80) {
-        *out++ = n;
+        *out = n;
         return 1;
     } else {
         *out++ = (n & 0x7f) | 0x80;
-        *out++ = n >> 7;
+        *out = n >> 7;
         return 2;
     }
 }
@@ -766,7 +766,7 @@ int uleb128_encode_small(uint8_t *out, uint32_t n)
 int uleb128_decode_small(const uint8_t *in, uint32_t *n)
 {
     if (!(*in & 0x80)) {
-        *n = *in++;
+        *n = *in;
         return 1;
     } else {
         *n = *in++ & 0x7f;
@@ -774,7 +774,7 @@ int uleb128_decode_small(const uint8_t *in, uint32_t *n)
         if (*in & 0x80) {
             return -1;
         }
-        *n |= *in++ << 7;
+        *n |= *in << 7;
         return 2;
     }
 }
Signature · 1 line
2.19.1
Reviewed-by on v1 1/2
#2 lore raw

Re: [Qemu-devel] [PATCH 1/2] cutils: remove one unnecessary pointer operation

Quoted 4 lines · * Wei Yang ([email protected]) wrote:

Since we will not operate on the next address pointed by out, it is not necessary to do addition on it.

After removing the operation, the function size reduced 16/18 bytes.

For me with a -O3 it didn't make any difference - the compiler was already smart enough to spot it, but it is correct.

Quoted 44 lines
---
 util/cutils.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
util/cutils.c +4 -4
index 9aacc422ca..1933a68da5 100644
@@ -754,11 +754,11 @@ int uleb128_encode_small(uint8_t *out, uint32_t n)
 {
     g_assert(n <= 0x3fff);
     if (n < 0x80) {
-        *out++ = n;
+        *out = n;
         return 1;
     } else {
         *out++ = (n & 0x7f) | 0x80;
-        *out++ = n >> 7;
+        *out = n >> 7;
         return 2;
     }
 }
@@ -766,7 +766,7 @@ int uleb128_encode_small(uint8_t *out, uint32_t n)
 int uleb128_decode_small(const uint8_t *in, uint32_t *n)
 {
     if (!(*in & 0x80)) {
-        *n = *in++;
+        *n = *in;
         return 1;
     } else {
         *n = *in++ & 0x7f;
@@ -774,7 +774,7 @@ int uleb128_decode_small(const uint8_t *in, uint32_t *n)
         if (*in & 0x80) {
             return -1;
         }
-        *n |= *in++ << 7;
+        *n |= *in << 7;
         return 2;
     }
 }
Signature · 1 line
2.19.1

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

#3 lore raw

Re: [Qemu-devel] [PATCH 1/2] cutils: remove one unnecessary pointer operation

Quoted 9 lines · Dr. David Alan Gilbert
Quoted 4 lines · * Wei Yang ([email protected]) wrote:

Since we will not operate on the next address pointed by out, it is not necessary to do addition on it.

After removing the operation, the function size reduced 16/18 bytes.

For me with a -O3 it didn't make any difference - the compiler was already smart enough to spot it, but it is correct.

Ah, you are right.

Quoted 49 lines
Quoted 44 lines
---
 util/cutils.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
util/cutils.c +4 -4
index 9aacc422ca..1933a68da5 100644
@@ -754,11 +754,11 @@ int uleb128_encode_small(uint8_t *out, uint32_t n)
 {
     g_assert(n <= 0x3fff);
     if (n < 0x80) {
-        *out++ = n;
+        *out = n;
         return 1;
     } else {
         *out++ = (n & 0x7f) | 0x80;
-        *out++ = n >> 7;
+        *out = n >> 7;
         return 2;
     }
 }
@@ -766,7 +766,7 @@ int uleb128_encode_small(uint8_t *out, uint32_t n)
 int uleb128_decode_small(const uint8_t *in, uint32_t *n)
 {
     if (!(*in & 0x80)) {
-        *n = *in++;
+        *n = *in;
         return 1;
     } else {
         *n = *in++ & 0x7f;
@@ -774,7 +774,7 @@ int uleb128_decode_small(const uint8_t *in, uint32_t *n)
         if (*in & 0x80) {
             return -1;
         }
-        *n |= *in++ << 7;
+        *n |= *in << 7;
         return 2;
     }
 }
Signature · 1 line
2.19.1

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

Signature · 2 lines
Wei Yang
Help you, Help me
Reviewed-by on v1 1/2
#4 lore raw

Re: [Qemu-devel] [PATCH 1/2] cutils: remove one unnecessary pointer operation

In reply to Wei Yang
Quoted 6 lines · Wei Yang

Since we will not operate on the next address pointed by out, it is not necessary to do addition on it.

After removing the operation, the function size reduced 16/18 bytes.

Included. I agree with David that the compiler should detect that, but also agreed that it shouldn't be there in the first place.

author
#5 lore raw

PATCH 2/2 migration/xbzrle: make xbzrle_encode_buffer little easier to read

In reply to Wei Yang

The encoding process could be described below:

for [content]
get length of a run
encode this run

By refactoring the code with this logic, it maybe a little easier to understand.

---
 migration/xbzrle.c | 153 +++++++++++++++++++++------------------------
 1 file changed, 73 insertions(+), 80 deletions(-)
migration/xbzrle.c +73 -80
index 1ba482ded9..25c69708ec 100644
@@ -14,6 +14,59 @@
 #include "qemu/cutils.h"
 #include "xbzrle.h"
 
+static int next_run(uint8_t *old_buf, uint8_t *new_buf, int off, int slen,
+                    bool zrun)
+{
+    uint32_t len = 0;
+    long res;
+
+    res = (slen - off) % sizeof(long);
+
+    /* first unaligned bytes */
+    while (res) {
+        uint8_t xor = old_buf[off + len] ^ new_buf[off + len];
+
+        if (!(zrun ^ !!xor)) {
+            break;
+        }
+        len++;
+        res--;
+    }
+
+    if (res) {
+        return len;
+    }
+
+    /* word at a time for speed, use of 32-bit long okay */
+    while (off + len < slen) {
+        /* truncation to 32-bit long okay */
+        unsigned long mask = (unsigned long)0x0101010101010101ULL;
+        long xor = (*(long *)(old_buf + off + len)) ^
+                   (*(long *)(new_buf + off + len));
+
+        if (zrun && !(zrun ^ !!xor)) {
+            break;
+        } else if (!zrun && ((xor - mask) & ~xor & (mask << 7))) {
+            break;
+        }
+
+        len += sizeof(long);
+    }
+
+    /* go over the rest */
+    while (off + len < slen) {
+        uint8_t xor = old_buf[off + len] ^ new_buf[off + len];
+
+        if (!(zrun ^ !!xor)) {
+            break;
+        }
+
+        len++;
+    }
+
+    return len;
+}
+
 /*
   page = zrun nzrun
        | zrun nzrun page
@@ -27,103 +80,43 @@
 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;
-    uint8_t *nzrun_start = NULL;
+    bool zrun = true;
+    int len, src_off = 0, dst_off = 0;
 
     g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) %
                sizeof(long)));
 
-    while (i < slen) {
+    for (; src_off < slen; src_off += len, zrun = !zrun) {
         /* overflow */
-        if (d + 2 > dlen) {
+        if (dst_off + 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--;
-        }
+        len = next_run(old_buf, new_buf, src_off, slen, zrun);
 
-        /* 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);
+        if (zrun) {
+            /* buffer unchanged */
+            if (len == slen) {
+                return 0;
             }
-
-            /* go over the rest */
-            while (i < slen && old_buf[i] == new_buf[i]) {
-                zrun_len++;
-                i++;
+            /* skip last zero run */
+            if (src_off + len == slen) {
+                return dst_off;
             }
         }
 
-        /* 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 */
-            unsigned long mask = (unsigned long)0x0101010101010101ULL;
-            while (i < slen) {
-                unsigned long xor;
-                xor = *(unsigned long *)(old_buf + i)
-                    ^ *(unsigned 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);
-                }
+        dst_off += uleb128_encode_small(dst + dst_off, len);
+        if (!zrun) {
+            /* overflow */
+            if (dst_off + len > dlen) {
+                return -1;
             }
+            memcpy(dst + dst_off, new_buf + src_off, len);
+            dst_off += len;
         }
-
-        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;
+    return dst_off;
 }
 
 int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)
Signature · 1 line
2.19.1
#6 lore raw

Re: [Qemu-devel] [PATCH 2/2] migration/xbzrle: make xbzrle_encode_buffer little easier to read

Quoted 43 lines · * Wei Yang ([email protected]) wrote:

The encoding process could be described below:

for [content]
get length of a run
encode this run

By refactoring the code with this logic, it maybe a little easier to understand.

---
 migration/xbzrle.c | 153 +++++++++++++++++++++------------------------
 1 file changed, 73 insertions(+), 80 deletions(-)
migration/xbzrle.c +21 -0
index 1ba482ded9..25c69708ec 100644
@@ -14,6 +14,59 @@
 #include "qemu/cutils.h"
 #include "xbzrle.h"
 
+static int next_run(uint8_t *old_buf, uint8_t *new_buf, int off, int slen,
+                    bool zrun)
+{
+    uint32_t len = 0;
+    long res;
+
+    res = (slen - off) % sizeof(long);
+
+    /* first unaligned bytes */
+    while (res) {
+        uint8_t xor = old_buf[off + len] ^ new_buf[off + len];
+
+        if (!(zrun ^ !!xor)) {
+            break;
+        }
+        len++;
+        res--;
+    }
+
+    if (res) {
+        return len;

migration/xbzrle.c line 47

Quoted 10 lines
migration/xbzrle.c +10 -0
+    }
+
+    /* word at a time for speed, use of 32-bit long okay */
+    while (off + len < slen) {
+        /* truncation to 32-bit long okay */
+        unsigned long mask = (unsigned long)0x0101010101010101ULL;
+        long xor = (*(long *)(old_buf + off + len)) ^
+                   (*(long *)(new_buf + off + len));
+
+        if (zrun && !(zrun ^ !!xor)) {

Are lines like this really making it easier to read?

Juan: Opinion?

Dave

Quoted 154 lines
migration/xbzrle.c +22 -0
+            break;
+        } else if (!zrun && ((xor - mask) & ~xor & (mask << 7))) {
 
 
+            break;
+        }
+
+        len += sizeof(long);
+    }
+
+    /* go over the rest */
+    while (off + len < slen) {
+        uint8_t xor = old_buf[off + len] ^ new_buf[off + len];
+
+        if (!(zrun ^ !!xor)) {
+            break;
+        }
+
+        len++;
+    }
+
+    return len;
+}
+
 /*

page = zrun nzrun
| zrun nzrun page

migration/xbzrle.c +20 -80
@@ -27,103 +80,43 @@
 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;
-    uint8_t *nzrun_start = NULL;
+    bool zrun = true;
+    int len, src_off = 0, dst_off = 0;
 
     g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) %
                sizeof(long)));
 
-    while (i < slen) {
+    for (; src_off < slen; src_off += len, zrun = !zrun) {
         /* overflow */
-        if (d + 2 > dlen) {
+        if (dst_off + 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--;
-        }
+        len = next_run(old_buf, new_buf, src_off, slen, zrun);
 
-        /* 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);
+        if (zrun) {
+            /* buffer unchanged */
+            if (len == slen) {
+                return 0;
             }
-
-            /* go over the rest */
-            while (i < slen && old_buf[i] == new_buf[i]) {
-                zrun_len++;
-                i++;
+            /* skip last zero run */
+            if (src_off + len == slen) {
+                return dst_off;
             }
         }
 
-        /* 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 */
-            unsigned long mask = (unsigned long)0x0101010101010101ULL;
-            while (i < slen) {
-                unsigned long xor;
-                xor = *(unsigned long *)(old_buf + i)
-                    ^ *(unsigned 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);
-                }
+        dst_off += uleb128_encode_small(dst + dst_off, len);
+        if (!zrun) {
+            /* overflow */
+            if (dst_off + len > dlen) {
+                return -1;
             }
+            memcpy(dst + dst_off, new_buf + src_off, len);
+            dst_off += len;
         }
-
-        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;
+    return dst_off;
 }
 
 int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)
Signature · 1 line
2.19.1

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

author
#7 lore raw

Re: [Qemu-devel] [PATCH 2/2] migration/xbzrle: make xbzrle_encode_buffer little easier to read

Quoted 48 lines · Dr. David Alan Gilbert
Quoted 47 lines · * Wei Yang ([email protected]) wrote:

The encoding process could be described below:

for [content]
get length of a run
encode this run

By refactoring the code with this logic, it maybe a little easier to understand.

---
 migration/xbzrle.c | 153 +++++++++++++++++++++------------------------
 1 file changed, 73 insertions(+), 80 deletions(-)
migration/xbzrle.c +25 -0
index 1ba482ded9..25c69708ec 100644
@@ -14,6 +14,59 @@
 #include "qemu/cutils.h"
 #include "xbzrle.h"
 
+static int next_run(uint8_t *old_buf, uint8_t *new_buf, int off, int slen,
+                    bool zrun)
+{
+    uint32_t len = 0;
+    long res;
+
+    res = (slen - off) % sizeof(long);
+
+    /* first unaligned bytes */
+    while (res) {
+        uint8_t xor = old_buf[off + len] ^ new_buf[off + len];
+
+        if (!(zrun ^ !!xor)) {
+            break;
+        }
+        len++;
+        res--;
+    }
+
+    if (res) {
+        return len;
+    }
+
+    /* word at a time for speed, use of 32-bit long okay */
+    while (off + len < slen) {
Quoted 9 lines

migration/xbzrle.c line 47

Quoted 6 lines
migration/xbzrle.c +6 -0
+        /* truncation to 32-bit long okay */
+        unsigned long mask = (unsigned long)0x0101010101010101ULL;
+        long xor = (*(long *)(old_buf + off + len)) ^
+                   (*(long *)(new_buf + off + len));
+
+        if (zrun && !(zrun ^ !!xor)) {

Are lines like this really making it easier to read?

Yep, this may took some time to understand. Let me put a chart to explain.

We have two choices for both zrun and xor, so we have 4 combinations:

    xor |  0 (no change) |  !0 (changed) 
 zrun   |                |

-------+----------------+--------------
1 | * | x
-------+----------------+--------------
0 | x | *

We can see the situation with '*' is the one we are looking for. And those situations could be expressed with (zrun ^ xor). Since we need to convert xor to something like boolean, so xor is converted to !!xor.

But yes, you are right. This part is not as easy as original one. In case you don't like this, we can change it back to the original version.

Quoted 4 lines

Juan: Opinion?

Dave

Signature · 2 lines
Wei Yang
Help you, Help me
author
#8 lore raw

Re: [Qemu-devel] [PATCH 2/2] migration/xbzrle: make xbzrle_encode_buffer little easier to read

In reply to Dr. David Alan Gilbert
Quoted 48 lines · Dr. David Alan Gilbert
Quoted 47 lines · * Wei Yang ([email protected]) wrote:

The encoding process could be described below:

for [content]
get length of a run
encode this run

By refactoring the code with this logic, it maybe a little easier to understand.

---
 migration/xbzrle.c | 153 +++++++++++++++++++++------------------------
 1 file changed, 73 insertions(+), 80 deletions(-)
migration/xbzrle.c +25 -0
index 1ba482ded9..25c69708ec 100644
@@ -14,6 +14,59 @@
 #include "qemu/cutils.h"
 #include "xbzrle.h"
 
+static int next_run(uint8_t *old_buf, uint8_t *new_buf, int off, int slen,
+                    bool zrun)
+{
+    uint32_t len = 0;
+    long res;
+
+    res = (slen - off) % sizeof(long);
+
+    /* first unaligned bytes */
+    while (res) {
+        uint8_t xor = old_buf[off + len] ^ new_buf[off + len];
+
+        if (!(zrun ^ !!xor)) {
+            break;
+        }
+        len++;
+        res--;
+    }
+
+    if (res) {
+        return len;
+    }
+
+    /* word at a time for speed, use of 32-bit long okay */
+    while (off + len < slen) {
Quoted 9 lines

migration/xbzrle.c line 47

Quoted 6 lines
migration/xbzrle.c +6 -0
+        /* truncation to 32-bit long okay */
+        unsigned long mask = (unsigned long)0x0101010101010101ULL;
+        long xor = (*(long *)(old_buf + off + len)) ^
+                   (*(long *)(new_buf + off + len));
+
+        if (zrun && !(zrun ^ !!xor)) {

Are lines like this really making it easier to read?

BTW, this line could be simplified to

        if (!(zrun ^ !!xor)) {
Quoted 4 lines

Juan: Opinion?

Dave

Signature · 2 lines
Wei Yang
Help you, Help me
#9 lore raw

Re: [Qemu-devel] [PATCH 2/2] migration/xbzrle: make xbzrle_encode_buffer little easier to read

In reply to Dr. David Alan Gilbert
Quoted 7 lines · Dr. David Alan Gilbert
Quoted 6 lines · * Wei Yang ([email protected]) wrote:

The encoding process could be described below:

for [content]
get length of a run
encode this run

Quoted 7 lines
Quoted 3 lines

By refactoring the code with this logic, it maybe a little easier to understand.

Are lines like this really making it easier to read?

Juan: Opinion?

Code is easier to understand .....

For values that I understand the code. I need to take a big breath and will take a deep look at it and see if it really does the same.

Later, Juan.

#10 lore raw

Re: [Qemu-devel] [PATCH 2/2] migration/xbzrle: make xbzrle_encode_buffer little easier to read

Quoted 12 lines · Juan Quintela
Quoted 11 lines · Dr. David Alan Gilbert
Quoted 9 lines · * Wei Yang ([email protected]) wrote:

The encoding process could be described below:

for [content]
get length of a run
encode this run

By refactoring the code with this logic, it maybe a little easier to understand.

Quoted 9 lines
Quoted 3 lines

Are lines like this really making it easier to read?

Juan: Opinion?

Code is easier to understand .....

For values that I understand the code. I need to take a big breath and will take a deep look at it and see if it really does the same.

Haha, thanks for your feedback.

Quoted 1 line

Later, Juan.

Signature · 2 lines
Wei Yang
Help you, Help me