[Qemu-devel] [PATCHv3 0/9] buffer_is_zero / migration optimizations

[Qemu-devel] [PATCHv3 0/9] buffer_is_zero / migration optimizations

[Peter Lieven]

this is v3 of my patch series with various optimizations in
zero buffer checking and migration tweaks.

thanks especially to Eric Blake for reviewing.

v3:
 - remove asserts, inline functions and add a check
   function if buffer_find_nonzero_offset() can be used.
 - use above check function in buffer_is_zero() and
   find_next_bit().
 - use buffer_is_nonzero_offset() directly to find
   zero pages. we know that all requirements are met
   for memory pages.
 - fix C89 violation in buffer_is_zero().
 - avoid derefencing p in ram_save_block() if we already
   know the page is zero.
 - fix initialization of last_offset in reset_ram_globals().
 - avoid skipping pages with offset == 0 in bulk stage in
   migration_bitmap_find_and_reset_dirty().
 - compared to v1 check for zero pages also after bulk
   ram migration as there are guests (e.g. Windows) which
   zero out large amount of memory while running.

v2:
 - fix description, add trivial zero check and add asserts 
   to buffer_find_nonzero_offset.
 - add a constant for the unroll factor of buffer_find_nonzero_offset
 - replace is_dup_page() by buffer_is_zero()
 - added test results to xbzrle patch
 - optimize descriptions

Peter Lieven (9):
  move vector definitions to qemu-common.h
  cutils: add a function to find non-zero content in a buffer
  buffer_is_zero: use vector optimizations if possible
  bitops: use vector algorithm to optimize find_next_bit()
  migration: search for zero instead of dup pages
  migration: add an indicator for bulk state of ram migration
  migration: do not sent zero pages in bulk stage
  migration: do not search dirty pages in bulk stage
  migration: use XBZRLE only after bulk stage

 arch_init.c           |   62 ++++++++++++++++++-------------------------------
 include/qemu-common.h |   27 +++++++++++++++++++++
 util/bitops.c         |   22 +++++++++++++++---
 util/cutils.c         |   55 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 123 insertions(+), 43 deletions(-)

-- 
1.7.9.5

[Qemu-devel] [PATCHv3 1/9] move vector definitions to qemu-common.h

[Peter Lieven]

vector optimizations will now be used at various places
not just in is_dup_page() in arch_init.c

this patch also adds a zero splat vector.

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 arch_init.c           |   20 --------------------
 include/qemu-common.h |   24 ++++++++++++++++++++++++
 2 files changed, 24 insertions(+), 20 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index 98e2bc6..1b71912 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -114,26 +114,6 @@ const uint32_t arch_type = QEMU_ARCH;
 #define RAM_SAVE_FLAG_CONTINUE 0x20
 #define RAM_SAVE_FLAG_XBZRLE   0x40
 
-#ifdef __ALTIVEC__
-#include <altivec.h>
-#define VECTYPE        vector unsigned char
-#define SPLAT(p)       vec_splat(vec_ld(0, p), 0)
-#define ALL_EQ(v1, v2) vec_all_eq(v1, v2)
-/* altivec.h may redefine the bool macro as vector type.
- * Reset it to POSIX semantics. */
-#undef bool
-#define bool _Bool
-#elif defined __SSE2__
-#include <emmintrin.h>
-#define VECTYPE        __m128i
-#define SPLAT(p)       _mm_set1_epi8(*(p))
-#define ALL_EQ(v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF)
-#else
-#define VECTYPE        unsigned long
-#define SPLAT(p)       (*(p) * (~0UL / 255))
-#define ALL_EQ(v1, v2) ((v1) == (v2))
-#endif
-
 
 static struct defconfig_file {
     const char *filename;
diff --git a/include/qemu-common.h b/include/qemu-common.h
index 7754ee2..e76ade3 100644
--- a/include/qemu-common.h
+++ b/include/qemu-common.h
@@ -448,4 +448,28 @@ int uleb128_decode_small(const uint8_t *in, uint32_t *n);
 
 void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size);
 
+/* vector definitions */
+#ifdef __ALTIVEC__
+#include <altivec.h>
+#define VECTYPE        vector unsigned char
+#define SPLAT(p)       vec_splat(vec_ld(0, p), 0)
+#define ZERO_SPLAT     vec_splat(vec_ld(0, 0), 0)
+#define ALL_EQ(v1, v2) vec_all_eq(v1, v2)
+/* altivec.h may redefine the bool macro as vector type.
+ * Reset it to POSIX semantics. */
+#undef bool
+#define bool _Bool
+#elif defined __SSE2__
+#include <emmintrin.h>
+#define VECTYPE        __m128i
+#define SPLAT(p)       _mm_set1_epi8(*(p))
+#define ZERO_SPLAT     _mm_setzero_si128()
+#define ALL_EQ(v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF)
+#else
+#define VECTYPE        unsigned long
+#define SPLAT(p)       (*(p) * (~0UL / 255))
+#define ZERO_SPLAT     0x0UL
+#define ALL_EQ(v1, v2) ((v1) == (v2))
+#endif
+
 #endif
-- 
1.7.9.5

[Qemu-devel] [PATCHv3 2/9] cutils: add a function to find non-zero content in a buffer

[Peter Lieven]

this adds buffer_find_nonzero_offset() which is a SSE2/Altives
optimized function that searches for non-zero content in a
buffer.

due to the optimizations used in the function there are restrictions
on buffer address and search length. the function
can_use_buffer_find_nonzero_content() can be used to check if
the function can be used safely.

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 include/qemu-common.h |    3 +++
 util/cutils.c         |   50 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 53 insertions(+)

diff --git a/include/qemu-common.h b/include/qemu-common.h
index e76ade3..ebbaf71 100644
--- a/include/qemu-common.h
+++ b/include/qemu-common.h
@@ -362,6 +362,9 @@ size_t qemu_iovec_from_buf(QEMUIOVector *qiov, size_t offset,
 size_t qemu_iovec_memset(QEMUIOVector *qiov, size_t offset,
                          int fillc, size_t bytes);
 
+#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8
+inline bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len);
+inline size_t buffer_find_nonzero_offset(const void *buf, size_t len);
 bool buffer_is_zero(const void *buf, size_t len);
 
 void qemu_progress_init(int enabled, float min_skip);
diff --git a/util/cutils.c b/util/cutils.c
index 1439da4..6d079ac 100644
--- a/util/cutils.c
+++ b/util/cutils.c
@@ -143,6 +143,56 @@ int qemu_fdatasync(int fd)
 }
 
 /*
+ * Searches for an area with non-zero content in a buffer
+ *
+ * Attention! The len must be a multiple of 8 * sizeof(VECTYPE) 
+ * and addr must be a multiple of sizeof(VECTYPE) due to 
+ * restriction of optimizations in this function.
+ * 
+ * can_use_buffer_find_nonzero_offset() can be used to check
+ * these requirements.
+ * 
+ * The return value is the offset of the non-zero area rounded
+ * down to 8 * sizeof(VECTYPE). If the buffer is all zero 
+ * the return value is equal to len.
+ */
+
+inline size_t buffer_find_nonzero_offset(const void *buf, size_t len)
+{
+    VECTYPE *p = (VECTYPE *)buf;
+    VECTYPE zero = ZERO_SPLAT;
+    size_t i;
+    
+    if (*((const long *) buf)) {
+        return 0;
+    }
+
+    for (i = 0; i < len / sizeof(VECTYPE); 
+            i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
+        VECTYPE tmp0 = p[i + 0] | p[i + 1];
+        VECTYPE tmp1 = p[i + 2] | p[i + 3];
+        VECTYPE tmp2 = p[i + 4] | p[i + 5];
+        VECTYPE tmp3 = p[i + 6] | p[i + 7];
+        VECTYPE tmp01 = tmp0 | tmp1;
+        VECTYPE tmp23 = tmp2 | tmp3;
+        if (!ALL_EQ(tmp01 | tmp23, zero)) {
+            break;
+        }
+    }
+    return i * sizeof(VECTYPE);
+}
+
+inline bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len)
+{
+    if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 
+                * sizeof(VECTYPE)) == 0 
+            && ((uintptr_t) buf) % sizeof(VECTYPE) == 0) {
+        return true;
+    }
+    return false;
+}
+
+/*
  * Checks if a buffer is all zeroes
  *
  * Attention! The len must be a multiple of 4 * sizeof(long) due to
-- 
1.7.9.5

[Qemu-devel] [PATCHv3 3/9] buffer_is_zero: use vector optimizations if possible

[Peter Lieven]

performance gain on SSE2 is approx. 20-25%. altivec
is not tested. performance for unsigned long arithmetic
is unchanged.

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 util/cutils.c |    5 +++++
 1 file changed, 5 insertions(+)

diff --git a/util/cutils.c b/util/cutils.c
index 6d079ac..52205a2 100644
--- a/util/cutils.c
+++ b/util/cutils.c
@@ -210,6 +210,11 @@ bool buffer_is_zero(const void *buf, size_t len)
     long d0, d1, d2, d3;
     const long * const data = buf;
 
+    /* use vector optimized zero check if possible */
+    if (can_use_buffer_find_nonzero_offset(buf,len)) {
+        return buffer_find_nonzero_offset(buf, len)==len;
+    }
+
     assert(len % (4 * sizeof(long)) == 0);
     len /= sizeof(long);
 
-- 
1.7.9.5

[Qemu-devel] [PATCHv3 4/9] bitops: use vector algorithm to optimize find_next_bit()

[Peter Lieven]

this patch adds the usage of buffer_find_nonzero_offset()
to skip large areas of zeroes.

compared to loop unrolling presented in an earlier
patch this adds another 50% performance benefit for
skipping large areas of zeroes. loop unrolling alone
added close to 100% speedup.

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 util/bitops.c |   22 +++++++++++++++++++---
 1 file changed, 19 insertions(+), 3 deletions(-)

diff --git a/util/bitops.c b/util/bitops.c
index e72237a..8ea79ae 100644
--- a/util/bitops.c
+++ b/util/bitops.c
@@ -42,10 +42,26 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
         size -= BITS_PER_LONG;
         result += BITS_PER_LONG;
     }
-    while (size & ~(BITS_PER_LONG-1)) {
-        if ((tmp = *(p++))) {
-            goto found_middle;
+    while (size >= BITS_PER_LONG) {
+        if ((tmp = *p)) {
+             goto found_middle;
+        }
+        if (can_use_buffer_find_nonzero_offset(p, size / BITS_PER_BYTE)) {
+            size_t tmp2 =
+                buffer_find_nonzero_offset(p, size / BITS_PER_BYTE);
+            result += tmp2 * BITS_PER_BYTE;
+            size -= tmp2 * BITS_PER_BYTE;
+            p += tmp2 / sizeof(unsigned long);
+            if (!size) {
+                return result;
+            }
+            if (tmp2) {
+                if ((tmp = *p)) {
+                    goto found_middle;
+                }
+            }
         }
+        p++;
         result += BITS_PER_LONG;
         size -= BITS_PER_LONG;
     }
-- 
1.7.9.5

[Qemu-devel] [PATCHv3 5/9] migration: search for zero instead of dup pages

[Peter Lieven]

virtually all dup pages are zero pages. remove
the special is_dup_page() function and use the
optimized buffer_find_nonzero_offset() function
instead.

here buffer_find_nonzero_offset() is used directly
to avoid the unnecssary additional checks in
buffer_is_zero().

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 arch_init.c |   17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index 1b71912..6806727 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -144,19 +144,10 @@ int qemu_read_default_config_files(bool userconfig)
     return 0;
 }
 
-static int is_dup_page(uint8_t *page)
+static inline bool is_zero_page(uint8_t *p)
 {
-    VECTYPE *p = (VECTYPE *)page;
-    VECTYPE val = SPLAT(page);
-    int i;
-
-    for (i = 0; i < TARGET_PAGE_SIZE / sizeof(VECTYPE); i++) {
-        if (!ALL_EQ(val, p[i])) {
-            return 0;
-        }
-    }
-
-    return 1;
+    return 
+     buffer_find_nonzero_offset(p, TARGET_PAGE_SIZE) == TARGET_PAGE_SIZE;
 }
 
 /* struct contains XBZRLE cache and a static page
@@ -443,7 +434,7 @@ static int ram_save_block(QEMUFile *f, bool last_stage)
 
             /* In doubt sent page as normal */
             bytes_sent = -1;
-            if (is_dup_page(p)) {
+            if (is_zero_page(p)) {
                 acct_info.dup_pages++;
                 bytes_sent = save_block_hdr(f, block, offset, cont,
                                             RAM_SAVE_FLAG_COMPRESS);
-- 
1.7.9.5

[Qemu-devel] [PATCHv3 6/9] migration: add an indicator for bulk state of ram migration

[Peter Lieven]

the first round of ram transfer is special since all pages
are dirty and thus all memory pages are transferred to
the target. this patch adds a boolean variable to track
this stage.

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 arch_init.c |    3 +++
 1 file changed, 3 insertions(+)

diff --git a/arch_init.c b/arch_init.c
index 6806727..2b59454 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -317,6 +317,7 @@ static ram_addr_t last_offset;
 static unsigned long *migration_bitmap;
 static uint64_t migration_dirty_pages;
 static uint32_t last_version;
+static bool ram_bulk_stage;
 
 static inline
 ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr,
@@ -424,6 +425,7 @@ static int ram_save_block(QEMUFile *f, bool last_stage)
             if (!block) {
                 block = QTAILQ_FIRST(&ram_list.blocks);
                 complete_round = true;
+                ram_bulk_stage = false;
             }
         } else {
             uint8_t *p;
@@ -527,6 +529,7 @@ static void reset_ram_globals(void)
     last_sent_block = NULL;
     last_offset = 0;
     last_version = ram_list.version;
+    ram_bulk_stage = true;
 }
 
 #define MAX_WAIT 50 /* ms, half buffered_file limit */
-- 
1.7.9.5

[Qemu-devel] [PATCHv3 7/9] migration: do not sent zero pages in bulk stage

[Peter Lieven]

during bulk stage of ram migration if a page is a
zero page do not send it at all.
the memory at the destination reads as zero anyway.

even if there is an madvise with QEMU_MADV_DONTNEED
at the target upon receipt of a zero page I have observed
that the target starts swapping if the memory is overcommitted.
it seems that the pages are dropped asynchronously.

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 arch_init.c |   10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index 2b59454..c2cb40a 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -438,10 +438,12 @@ static int ram_save_block(QEMUFile *f, bool last_stage)
             bytes_sent = -1;
             if (is_zero_page(p)) {
                 acct_info.dup_pages++;
-                bytes_sent = save_block_hdr(f, block, offset, cont,
-                                            RAM_SAVE_FLAG_COMPRESS);
-                qemu_put_byte(f, *p);
-                bytes_sent += 1;
+                if (!ram_bulk_stage) {
+                    bytes_sent = save_block_hdr(f, block, offset, cont,
+                                                RAM_SAVE_FLAG_COMPRESS);
+                    qemu_put_byte(f, 0);
+                }
+                bytes_sent++;
             } else if (migrate_use_xbzrle()) {
                 current_addr = block->offset + offset;
                 bytes_sent = save_xbzrle_page(f, p, current_addr, block,
-- 
1.7.9.5

[Qemu-devel] [PATCHv3 8/9] migration: do not search dirty pages in bulk stage

[Peter Lieven]

avoid searching for dirty pages just increment the
page offset. all pages are dirty anyway.

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 arch_init.c |   10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index c2cb40a..4718d39 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -327,8 +327,14 @@ ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr,
     unsigned long nr = base + (start >> TARGET_PAGE_BITS);
     unsigned long size = base + (int128_get64(mr->size) >> TARGET_PAGE_BITS);
 
-    unsigned long next = find_next_bit(migration_bitmap, size, nr);
-
+    unsigned long next;
+    
+    if (ram_bulk_stage && nr > base) {
+        next = nr + 1;
+    } else {
+        next = find_next_bit(migration_bitmap, size, nr);
+    }
+    
     if (next < size) {
         clear_bit(next, migration_bitmap);
         migration_dirty_pages--;
-- 
1.7.9.5

[Qemu-devel] [PATCHv3 9/9] migration: use XBZRLE only after bulk stage

[Peter Lieven]

at the beginning of migration all pages are marked dirty and
in the first round a bulk migration of all pages is performed.

currently all these pages are copied to the page cache regardless
if there are frequently updated or not. this doesn't make sense
since most of these pages are never transferred again.

this patch changes the XBZRLE transfer to only be used after
the bulk stage has been completed. that means a page is added
to the page cache the second time it is transferred and XBZRLE
can benefit from the third time of transfer.

since the page cache is likely smaller than the number of pages
its also likely that in the second round the page is missing in the
cache due to collisions in the bulk phase.

on the other hand a lot of unnecessary mallocs, memdups and frees
are saved.

the following results have been taken earlier while executing
the test program from docs/xbzrle.txt. (+) with the patch and (-)
without. (thanks to Eric Blake for reformatting and comments)

+ total time: 22185 milliseconds
- total time: 22410 milliseconds

Shaved 0.3 seconds, better than 1%!

+ downtime: 29 milliseconds
- downtime: 21 milliseconds

Not sure why downtime seemed worse, but probably not the end of the world.

+ transferred ram: 706034 kbytes
- transferred ram: 721318 kbytes

Fewer bytes sent - good.

+ remaining ram: 0 kbytes
- remaining ram: 0 kbytes
+ total ram: 1057216 kbytes
- total ram: 1057216 kbytes
+ duplicate: 108556 pages
- duplicate: 105553 pages
+ normal: 175146 pages
- normal: 179589 pages
+ normal bytes: 700584 kbytes
- normal bytes: 718356 kbytes

Fewer normal bytes...

+ cache size: 67108864 bytes
- cache size: 67108864 bytes
+ xbzrle transferred: 3127 kbytes
- xbzrle transferred: 630 kbytes

...and more compressed pages sent - good.

+ xbzrle pages: 117811 pages
- xbzrle pages: 21527 pages
+ xbzrle cache miss: 18750
- xbzrle cache miss: 179589

And very good improvement on the cache miss rate.

+ xbzrle overflow : 0
- xbzrle overflow : 0

Signed-off-by: Peter Lieven <pl@kamp.de>
---
 arch_init.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch_init.c b/arch_init.c
index 4718d39..4e89783 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -450,7 +450,7 @@ static int ram_save_block(QEMUFile *f, bool last_stage)
                     qemu_put_byte(f, 0);
                 }
                 bytes_sent++;
-            } else if (migrate_use_xbzrle()) {
+            } else if (!ram_bulk_stage && migrate_use_xbzrle()) {
                 current_addr = block->offset + offset;
                 bytes_sent = save_xbzrle_page(f, p, current_addr, block,
                                               offset, cont, last_stage);
-- 
1.7.9.5

Re: [Qemu-devel] [PATCHv3 1/9] move vector definitions to qemu-common.h

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> vector optimizations will now be used at various places
> not just in is_dup_page() in arch_init.c
> 
> this patch also adds a zero splat vector.
> 
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---
>  arch_init.c           |   20 --------------------
>  include/qemu-common.h |   24 ++++++++++++++++++++++++
>  2 files changed, 24 insertions(+), 20 deletions(-)

Appears to be unchanged from v2.  You can reduce a reviewer's time
commitment by adjusting the commit message to add in reviewed-by: lines
from the earlier review where the patch is merely reposted unchanged as
part of a larger series; conversely, if you carry forward reviewed-by
comments, be sure to drop all reviewed-by lines on the commits where you
make substantial fixes.  That way, people who looked at v2 know where to
concentrate efforts when reviewing v3.  At any rate:

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

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 2/9] cutils: add a function to find non-zero content in a buffer

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> this adds buffer_find_nonzero_offset() which is a SSE2/Altives

s/Altives/Altivec/

> optimized function that searches for non-zero content in a
> buffer.
> 
> due to the optimizations used in the function there are restrictions
> on buffer address and search length. the function
> can_use_buffer_find_nonzero_content() can be used to check if
> the function can be used safely.
> 
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---
>  include/qemu-common.h |    3 +++
>  util/cutils.c         |   50 +++++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 53 insertions(+)

> +inline bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len);
> +inline size_t buffer_find_nonzero_offset(const void *buf, size_t len);

Ouch.  It is okay to add a 'static inline' function, but then the
implementation must live in this header.  Otherwise, the function must
not be inline, or you risk linker errors.

> +++ b/util/cutils.c
> @@ -143,6 +143,56 @@ int qemu_fdatasync(int fd)
>  }
>  
>  /*
> + * Searches for an area with non-zero content in a buffer
> + *
> + * Attention! The len must be a multiple of 8 * sizeof(VECTYPE) 

Should we call out BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR instead of a
magic number here?  But I'm okay with leaving it as-is.

> + * and addr must be a multiple of sizeof(VECTYPE) due to 

Trailing whitespace (here, and on several other lines).  Please run your
series through scripts/checkpatch.pl before submitting v4.

> + * restriction of optimizations in this function.
> + * 
> + * can_use_buffer_find_nonzero_offset() can be used to check
> + * these requirements.
> + * 
> + * The return value is the offset of the non-zero area rounded
> + * down to 8 * sizeof(VECTYPE). If the buffer is all zero 

Same comment on this use of '8'.

> + * the return value is equal to len.
> + */
> +
> +inline size_t buffer_find_nonzero_offset(const void *buf, size_t len)

s/inline// (or move it to a 'static inline' definition in the .h)

> +{
> +    VECTYPE *p = (VECTYPE *)buf;
> +    VECTYPE zero = ZERO_SPLAT;
> +    size_t i;
> +    

You copied the 'Attention! ...' message from buffer_is_zero, which
currently asserts that its condition is held.  Therefore, consistency
would argue that you should assert your preconditions here, even if it
adds more to the code size.  But this is something where a maintainer
might have a better opinion on whether to keep the code robust with an
assert(), or whether the faster operation without sanity checking is
more appropriate (in which case a followup to remove the assert from
buffer_is_zero would make sense).

>   * Checks if a buffer is all zeroes
>   *
>   * Attention! The len must be a multiple of 4 * sizeof(long) due to
> 

Cleaning up whitespace is trivial; but the incorrect use of 'inline'
requires a v4.

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 3/9] buffer_is_zero: use vector optimizations if possible

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> performance gain on SSE2 is approx. 20-25%. altivec
> is not tested. performance for unsigned long arithmetic
> is unchanged.
> 
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---
>  util/cutils.c |    5 +++++
>  1 file changed, 5 insertions(+)
> 
> diff --git a/util/cutils.c b/util/cutils.c
> index 6d079ac..52205a2 100644
> --- a/util/cutils.c
> +++ b/util/cutils.c
> @@ -210,6 +210,11 @@ bool buffer_is_zero(const void *buf, size_t len)
>      long d0, d1, d2, d3;
>      const long * const data = buf;
>  
> +    /* use vector optimized zero check if possible */
> +    if (can_use_buffer_find_nonzero_offset(buf,len)) {

Space after comma.

> +        return buffer_find_nonzero_offset(buf, len)==len;

And still missing spaces around the '==', even though I pointed it out
in v2.  Run your series through checkpatch.pl.

As whitespace cleanups are trivial, you can send v4 with:

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

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 2/9] cutils: add a function to find non-zero content in a buffer

[Peter Lieven]

Am 21.03.2013 um 19:12 schrieb Eric Blake <eblake@redhat.com>:

> On 03/21/2013 09:57 AM, Peter Lieven wrote:
>> this adds buffer_find_nonzero_offset() which is a SSE2/Altives
> 
> s/Altives/Altivec/
> 
>> optimized function that searches for non-zero content in a
>> buffer.
>> 
>> due to the optimizations used in the function there are restrictions
>> on buffer address and search length. the function
>> can_use_buffer_find_nonzero_content() can be used to check if
>> the function can be used safely.
>> 
>> Signed-off-by: Peter Lieven <pl@kamp.de>
>> ---
>> include/qemu-common.h |    3 +++
>> util/cutils.c         |   50 +++++++++++++++++++++++++++++++++++++++++++++++++
>> 2 files changed, 53 insertions(+)
> 
>> +inline bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len);
>> +inline size_t buffer_find_nonzero_offset(const void *buf, size_t len);
> 
> Ouch.  It is okay to add a 'static inline' function, but then the
> implementation must live in this header.  Otherwise, the function must
> not be inline, or you risk linker errors.

Sorry, i was not aware. 

> 
>> +++ b/util/cutils.c
>> @@ -143,6 +143,56 @@ int qemu_fdatasync(int fd)
>> }
>> 
>> /*
>> + * Searches for an area with non-zero content in a buffer
>> + *
>> + * Attention! The len must be a multiple of 8 * sizeof(VECTYPE) 
> 
> Should we call out BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR instead of a
> magic number here?  But I'm okay with leaving it as-is.
> 
>> + * and addr must be a multiple of sizeof(VECTYPE) due to 
> 
> Trailing whitespace (here, and on several other lines).  Please run your
> series through scripts/checkpatch.pl before submitting v4.

thanks for the pointer.

> 
>> + * restriction of optimizations in this function.
>> + * 
>> + * can_use_buffer_find_nonzero_offset() can be used to check
>> + * these requirements.
>> + * 
>> + * The return value is the offset of the non-zero area rounded
>> + * down to 8 * sizeof(VECTYPE). If the buffer is all zero 
> 
> Same comment on this use of '8'.
> 
>> + * the return value is equal to len.
>> + */
>> +
>> +inline size_t buffer_find_nonzero_offset(const void *buf, size_t len)
> 
> s/inline// (or move it to a 'static inline' definition in the .h)

I would move at least the can_use_buffer_find_nonzero_offset() function
completely into the header and rely the compiler inlineing
buffer_find_nonzero_offset().

> 
>> +{
>> +    VECTYPE *p = (VECTYPE *)buf;
>> +    VECTYPE zero = ZERO_SPLAT;
>> +    size_t i;
>> +    
> 
> You copied the 'Attention! ...' message from buffer_is_zero, which
> currently asserts that its condition is held.  Therefore, consistency
> would argue that you should assert your preconditions here, even if it
> adds more to the code size.  But this is something where a maintainer
> might have a better opinion on whether to keep the code robust with an
> assert(), or whether the faster operation without sanity checking is
> more appropriate (in which case a followup to remove the assert from
> buffer_is_zero would make sense).

I would appreciate feedback on this from the maintainers. My concern
with buffer_find_nonzero_offset() is that it is used for checking millions
of 4KByte pages. buffer_is_zero is used for larger objects in the bdrv
context, afaik.



> 
>>  * Checks if a buffer is all zeroes
>>  *
>>  * Attention! The len must be a multiple of 4 * sizeof(long) due to
>> 
> 
> Cleaning up whitespace is trivial; but the incorrect use of 'inline'
> requires a v4.
> 
> -- 
> Eric Blake   eblake redhat com    +1-919-301-3266
> Libvirt virtualization library http://libvirt.org
> 

Re: [Qemu-devel] [PATCHv3 4/9] bitops: use vector algorithm to optimize find_next_bit()

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> this patch adds the usage of buffer_find_nonzero_offset()
> to skip large areas of zeroes.
> 
> compared to loop unrolling presented in an earlier
> patch this adds another 50% performance benefit for
> skipping large areas of zeroes. loop unrolling alone
> added close to 100% speedup.
> 
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---
>  util/bitops.c |   22 +++++++++++++++++++---
>  1 file changed, 19 insertions(+), 3 deletions(-)

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

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 5/9] migration: search for zero instead of dup pages

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> virtually all dup pages are zero pages. remove
> the special is_dup_page() function and use the
> optimized buffer_find_nonzero_offset() function
> instead.
> 
> here buffer_find_nonzero_offset() is used directly
> to avoid the unnecssary additional checks in
> buffer_is_zero().
> 
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---

> -    return 1;
> +    return 
> +     buffer_find_nonzero_offset(p, TARGET_PAGE_SIZE) == TARGET_PAGE_SIZE;

Unusual layout.  I would have written:

    return buffer_find_nonzero_offset(p, TARGET_PAGE_SIZE) ==
        TARGET_PAGE_SIZE;

>  /* struct contains XBZRLE cache and a static page
> @@ -443,7 +434,7 @@ static int ram_save_block(QEMUFile *f, bool last_stage)
>  
>              /* In doubt sent page as normal */
>              bytes_sent = -1;
> -            if (is_dup_page(p)) {
> +            if (is_zero_page(p)) {
>                  acct_info.dup_pages++;
>                  bytes_sent = save_block_hdr(f, block, offset, cont,
>                                              RAM_SAVE_FLAG_COMPRESS);

I would move the change for qemu_put_byte(f, 0) out of patch 7 into this
patch, since this is the first point where you know the byte to send is 0.

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 7/9] migration: do not sent zero pages in bulk stage

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> during bulk stage of ram migration if a page is a
> zero page do not send it at all.
> the memory at the destination reads as zero anyway.
> 
> even if there is an madvise with QEMU_MADV_DONTNEED
> at the target upon receipt of a zero page I have observed
> that the target starts swapping if the memory is overcommitted.
> it seems that the pages are dropped asynchronously.
> 
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---
>  arch_init.c |   10 ++++++----
>  1 file changed, 6 insertions(+), 4 deletions(-)

>              if (is_zero_page(p)) {
>                  acct_info.dup_pages++;
> -                bytes_sent = save_block_hdr(f, block, offset, cont,
> -                                            RAM_SAVE_FLAG_COMPRESS);
> -                qemu_put_byte(f, *p);
> -                bytes_sent += 1;
> +                if (!ram_bulk_stage) {
> +                    bytes_sent = save_block_hdr(f, block, offset, cont,
> +                                                RAM_SAVE_FLAG_COMPRESS);
> +                    qemu_put_byte(f, 0);
> +                }
> +                bytes_sent++;

Logic is STILL wrong.  I pointed out in v2 that bytes_sent should not be
incremented if you are not sending the page, so it needs to be inside
the 'if (!ram_bulk_stage)'.

Do we want to add a new migration statistic counter of how many zero
pages we omitted sending during the bulk stage?

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 6/9] migration: add an indicator for bulk state of ram migration

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> the first round of ram transfer is special since all pages
> are dirty and thus all memory pages are transferred to
> the target. this patch adds a boolean variable to track
> this stage.
> 
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---
>  arch_init.c |    3 +++
>  1 file changed, 3 insertions(+)

Prior review still stands.

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 8/9] migration: do not search dirty pages in bulk stage

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> avoid searching for dirty pages just increment the
> page offset. all pages are dirty anyway.
> 
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---
>  arch_init.c |   10 ++++++++--
>  1 file changed, 8 insertions(+), 2 deletions(-)

Prior review still stands.

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 9/9] migration: use XBZRLE only after bulk stage

[Eric Blake]

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

On 03/21/2013 09:57 AM, Peter Lieven wrote:
> at the beginning of migration all pages are marked dirty and
> in the first round a bulk migration of all pages is performed.
> 
> currently all these pages are copied to the page cache regardless
> if there are frequently updated or not. this doesn't make sense

s/if there/of whether they/

> since most of these pages are never transferred again.
> 
> this patch changes the XBZRLE transfer to only be used after
> the bulk stage has been completed. that means a page is added
> to the page cache the second time it is transferred and XBZRLE
> can benefit from the third time of transfer.
> 
> since the page cache is likely smaller than the number of pages
> its also likely that in the second round the page is missing in the

s/its/it's/

> cache due to collisions in the bulk phase.
> 
> on the other hand a lot of unnecessary mallocs, memdups and frees
> are saved.
> 
...
> Signed-off-by: Peter Lieven <pl@kamp.de>
> ---
>  arch_init.c |    2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)

Prior review still stands (touching up typos in a commit message
generally does not invalidate carrying forward a reviewed-by comment).

-- 
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: 621 bytes --]

Re: [Qemu-devel] [PATCHv3 7/9] migration: do not sent zero pages in bulk stage

[Peter Lieven]

Am 21.03.2013 um 20:26 schrieb Eric Blake <eblake@redhat.com>:

> On 03/21/2013 09:57 AM, Peter Lieven wrote:
>> during bulk stage of ram migration if a page is a
>> zero page do not send it at all.
>> the memory at the destination reads as zero anyway.
>> 
>> even if there is an madvise with QEMU_MADV_DONTNEED
>> at the target upon receipt of a zero page I have observed
>> that the target starts swapping if the memory is overcommitted.
>> it seems that the pages are dropped asynchronously.
>> 
>> Signed-off-by: Peter Lieven <pl@kamp.de>
>> ---
>> arch_init.c |   10 ++++++----
>> 1 file changed, 6 insertions(+), 4 deletions(-)
> 
>>             if (is_zero_page(p)) {
>>                 acct_info.dup_pages++;
>> -                bytes_sent = save_block_hdr(f, block, offset, cont,
>> -                                            RAM_SAVE_FLAG_COMPRESS);
>> -                qemu_put_byte(f, *p);
>> -                bytes_sent += 1;
>> +                if (!ram_bulk_stage) {
>> +                    bytes_sent = save_block_hdr(f, block, offset, cont,
>> +                                                RAM_SAVE_FLAG_COMPRESS);
>> +                    qemu_put_byte(f, 0);
>> +                }
>> +                bytes_sent++;
> 
> Logic is STILL wrong.  I pointed out in v2 that bytes_sent should not be
> incremented if you are not sending the page, so it needs to be inside
> the 'if (!ram_bulk_stage)'.

If its inside then bytes_sent will be -1 at the end if we skip a page. This would lead
to the raw page being sent. This way it is 0 what I think is correct.

> 
> Do we want to add a new migration statistic counter of how many zero
> pages we omitted sending during the bulk stage?

You mean sth like skipped zero pages?

I was also thinking of renaming dup_pages into zero_pages in the statistics,
but this could break someone relying on it so I left it as is.

Peter


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

Re: [Qemu-devel] [PATCHv3 8/9] migration: do not search dirty pages in bulk stage

[Peter Lieven]

Am 21.03.2013 um 20:27 schrieb Eric Blake <eblake@redhat.com>:

> On 03/21/2013 09:57 AM, Peter Lieven wrote:
>> avoid searching for dirty pages just increment the
>> page offset. all pages are dirty anyway.
>> 
>> Signed-off-by: Peter Lieven <pl@kamp.de>
>> ---
>> arch_init.c |   10 ++++++++--
>> 1 file changed, 8 insertions(+), 2 deletions(-)
> 
> Prior review still stands.

I changed the logic a little bit.

a) last_offset is initialized to 0 again.
b) for the case last_offset == 0 in bulk ram migration the search
is not skipped resulting in offset == 0 if the page is dirty (first call
to this function with last_offset==0) and offset==1 when its called
the second time (page is no longer dirty).
Afterwards offset is calculated as last_offset + 1.

Peter


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