[Qemu-devel] [PATCH v5 0/9] XBZRLE delta for live migration of large memory apps

[Qemu-devel] [PATCH v5 0/9] XBZRLE delta for live migration of large memory apps

[Orit Wasserman]

Changes from v4:
1) Rebase
2) divide patch into 9 patches
3) move memory allocation into cache_insert

By using XBZRLE (Xor Binary Zero Run-Length-Encoding) we can reduce VM downtime
and total live-migration time of VMs running memory write intensive workloads
typical of large enterprise applications such as SAP ERP Systems, and generally
speaking for any application with a sparse memory update pattern.

On the sender side XBZRLE is used as a compact delta encoding of page updates,
retrieving the old page content from an LRU cache (default size of 64 MB). The
receiving side uses the existing page content and XBZRLE to decode the new page
content.

Work was originally based on research results published VEE 2011: Evaluation of
Delta Compression Techniques for Efficient Live Migration of Large Virtual
Machines by Benoit, Svard, Tordsson and Elmroth. Additionally the delta encoder
XBRLE was improved further using XBZRLE instead.

XBZRLE has a sustained bandwidth of 2-2.5 GB/s for typical workloads making it
ideal for in-line, real-time encoding such as is needed for live-migration.

A typical usage scenario:
    {qemu} migrate_set_cachesize 256m
    {qemu} migrate -x -d tcp:destination.host:4444
    {qemu} info migrate
    ...
    transferred ram-duplicate: A kbytes
    transferred ram-duplicate: B pages
    transferred ram-normal: C kbytes
    transferred ram-normal: D pages
    transferred ram-xbrle: E kbytes
    transferred ram-xbrle: F pages
    overflow ram-xbrle: G pages
    cache-hit ram-xbrle: H pages
    cache-lookup ram-xbrle: J pages

Testing: live migration with XBZRLE completed in 110 seconds, without live
migration was not able to complete.

A simple synthetic memory r/w load generator:
..    include <stdlib.h>
..    include <stdio.h>
..    int main()
..    {
..        char *buf = (char *) calloc(4096, 4096);
..        while (1) {
..            int i;
..            for (i = 0; i < 4096 * 4; i++) {
..                buf[i * 4096 / 4]++;
..            }
..            printf(".");
..        }
..    }

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>

 arch_init.c       |  546 +++++++++++++++++++++++++++++++++++++++++++++++++----
 block-migration.c |    4 +-
 hmp-commands.hx   |   34 +++-
 hw/hw.h           |    4 +-
 migration.c       |   51 +++++-
 migration.h       |   19 ++
 qmp-commands.hx   |   44 ++++-
 savevm.c          |   11 +-
 sysemu.h          |    4 +-
 9 files changed, 653 insertions(+), 64 deletions(-)

-- 
1.7.6.5

[Qemu-devel] [PATCH v5 1/9] Add cache handling functions

[Orit Wasserman]

Add page caching mechanism.
The pages are stored in the cache ordered by their address.

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 arch_init.c |  183 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 183 insertions(+), 0 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index d4c92b0..fdda277 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -28,6 +28,7 @@
 #include <sys/types.h>
 #include <sys/mman.h>
 #endif
+#include <assert.h>
 #include "config.h"
 #include "monitor.h"
 #include "sysemu.h"
@@ -42,6 +43,14 @@
 #include "gdbstub.h"
 #include "hw/smbios.h"
 
+#ifdef DEBUG_ARCH_INIT
+#define DPRINTF(fmt, ...) \
+    do { fprintf(stdout, "arch_init: " fmt, ## __VA_ARGS__); } while (0)
+#else
+#define DPRINTF(fmt, ...) \
+    do { } while (0)
+#endif
+
 #ifdef TARGET_SPARC
 int graphic_width = 1024;
 int graphic_height = 768;
@@ -94,6 +103,180 @@ const uint32_t arch_type = QEMU_ARCH;
 #define RAM_SAVE_FLAG_EOS      0x10
 #define RAM_SAVE_FLAG_CONTINUE 0x20
 
+/***********************************************************/
+/* Page cache for storing previous pages as basis for XBRLE compression */
+#define CACHE_N_WAY 2 /* 2-way assossiative cache */
+
+typedef struct CacheItem {
+    ram_addr_t it_addr;
+    unsigned long it_age;
+    uint8_t *it_data;
+} CacheItem;
+
+typedef struct CacheBucket {
+    CacheItem bkt_item[CACHE_N_WAY];
+} CacheBucket;
+
+static CacheBucket *page_cache;
+static int64_t cache_num_buckets;
+static uint64_t cache_max_item_age;
+static int64_t cache_num_items;
+
+static void cache_init(ssize_t num_buckets);
+static void cache_fini(void);
+static int cache_is_cached(ram_addr_t addr);
+static int cache_get_oldest(CacheBucket *buck);
+static int cache_get_newest(CacheBucket *buck, ram_addr_t addr);
+static void cache_insert(ram_addr_t id, uint8_t *pdata);
+static unsigned long cache_get_cache_pos(ram_addr_t address);
+static CacheItem *cache_item_get(unsigned long pos, int item);
+
+/***********************************************************/
+/* XBRLE (Xor Based Run-Length Encoding) */
+typedef struct XBRLEHeader {
+    uint8_t xh_flags;
+    uint16_t xh_len;
+    uint32_t xh_cksum;
+} XBRLEHeader;
+
+/***********************************************************/
+/* XBRLE page cache implementation */
+static CacheItem *cache_item_get(unsigned long pos, int item)
+{
+    assert(page_cache);
+    return &page_cache[pos].bkt_item[item];
+}
+
+static void cache_init(int64_t num_bytes)
+{
+    int i;
+
+    cache_num_items = 0;
+    cache_max_item_age = 0;
+    cache_num_buckets = num_bytes / (TARGET_PAGE_SIZE * CACHE_N_WAY);
+    assert(cache_num_buckets);
+    DPRINTF("Setting cache buckets to %lu\n", cache_num_buckets);
+
+    assert(!page_cache);
+    page_cache = (CacheBucket *)g_malloc0((cache_num_buckets) *
+            sizeof(CacheBucket));
+
+    for (i = 0; i < cache_num_buckets; i++) {
+        int j;
+        for (j = 0; j < CACHE_N_WAY; j++) {
+            CacheItem *it = cache_item_get(i, j);
+            it->it_data = NULL;
+            it->it_age = 0;
+            it->it_addr = -1;
+        }
+    }
+}
+
+static void cache_fini(void)
+{
+    int i;
+
+    assert(page_cache);
+
+    for (i = 0; i < cache_num_buckets; i++) {
+        int j;
+        for (j = 0; j < CACHE_N_WAY; j++) {
+            CacheItem *it = cache_item_get(i, j);
+            g_free(it->it_data);
+            it->it_data = 0;
+        }
+    }
+
+    g_free(page_cache);
+    page_cache = NULL;
+}
+
+static unsigned long cache_get_cache_pos(ram_addr_t address)
+{
+    unsigned long pos;
+
+    assert(cache_num_buckets);
+    pos = (address/TARGET_PAGE_SIZE) & (cache_num_buckets - 1);
+    return pos;
+}
+
+static int cache_get_newest(CacheBucket *buck, ram_addr_t addr)
+{
+    unsigned long big = 0;
+    int big_pos = -1;
+    int j;
+
+    assert(page_cache);
+
+    for (j = 0; j < CACHE_N_WAY; j++) {
+        CacheItem *it = &buck->bkt_item[j];
+
+        if (it->it_addr != addr) {
+            continue;
+        }
+
+        if (!j || it->it_age > big) {
+            big = it->it_age;
+            big_pos = j;
+        }
+    }
+
+    return big_pos;
+}
+
+static int cache_get_oldest(CacheBucket *buck)
+{
+    unsigned long small = 0;
+    int small_pos = -1;
+    int j;
+
+    assert(page_cache);
+
+    for (j = 0; j < CACHE_N_WAY; j++) {
+        CacheItem *it = &buck->bkt_item[j];
+
+        if (!j || it->it_age <  small) {
+            small = it->it_age;
+            small_pos = j;
+        }
+    }
+
+    return small_pos;
+}
+
+static int cache_is_cached(ram_addr_t addr)
+{
+    unsigned long pos = cache_get_cache_pos(addr);
+
+    assert(page_cache);
+    CacheBucket *bucket = &page_cache[pos];
+    return cache_get_newest(bucket, addr);
+}
+
+static void cache_insert(unsigned long addr, uint8_t *pdata)
+{
+    unsigned long pos;
+    int slot = -1;
+    CacheBucket *bucket;
+
+    pos = cache_get_cache_pos(addr);
+    assert(page_cache);
+    bucket = &page_cache[pos];
+    slot = cache_get_oldest(bucket); /* evict LRU */
+
+    /* actual update of entry */
+    CacheItem *it = cache_item_get(pos, slot);
+    if (!it->it_data) {
+        cache_num_items++;
+    }
+    g_free(it->it_data);
+
+    it->it_data = g_malloc0(TARGET_PAGE_SIZE);
+    memcpy(it->it_data, pdata, TARGET_PAGE_SIZE);
+    it->it_age = ++cache_max_item_age;
+    it->it_addr = addr;
+}
+
 static int is_dup_page(uint8_t *page, uint8_t ch)
 {
     uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch;
-- 
1.7.6.5

[Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

[Orit Wasserman]

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 arch_init.c |   58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 58 insertions(+), 0 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index fdda277..426b34d 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -139,6 +139,9 @@ typedef struct XBRLEHeader {
     uint32_t xh_cksum;
 } XBRLEHeader;
 
+static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen);
+static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen);
+
 /***********************************************************/
 /* XBRLE page cache implementation */
 static CacheItem *cache_item_get(unsigned long pos, int item)
@@ -277,6 +280,61 @@ static void cache_insert(unsigned long addr, uint8_t *pdata)
     it->it_addr = addr;
 }
 
+/* XBRLE (Xor Based Run-Length Encoding) */
+static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen)
+{
+    int d = 0, ch_run = 0, i;
+    uint8_t prev = 0, ch = 0;
+
+    for (i = 0; i <= slen; i++) {
+        if (i != slen) {
+            ch = src[i];
+        }
+
+        if (!i || (i != slen && ch == prev && ch_run < 255)) {
+            ch_run++;
+        } else {
+            if (d+2 > dlen) {
+                return -1;
+            }
+            *dst++ = ch_run;
+            *dst++ = prev;
+            d += 2;
+            ch_run = 1;
+        }
+
+        prev = ch;
+    }
+    return d;
+}
+
+static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen)
+{
+    int d = 0, s;
+
+    for (s = 0; s < slen-1; s += 2) {
+        uint8_t ch_run = src[s];
+        uint8_t ch = src[s+1];
+        while (ch_run--) {
+            if (d == dlen) {
+                return -1;
+            }
+            dst[d] = ch;
+            d++;
+        }
+    }
+    return d;
+}
+
+static void xor_encode(uint8_t *dst, uint8_t *src1, uint8_t *src2)
+{
+    int i;
+
+    for (i = 0; i < TARGET_PAGE_SIZE; i++) {
+        dst[i] = src1[i] ^ src2[i];
+    }
+}
+
 static int is_dup_page(uint8_t *page, uint8_t ch)
 {
     uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch;
-- 
1.7.6.5

[Qemu-devel] [PATCH v5 3/9] Add save_block_hdr function

[Orit Wasserman]

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 arch_init.c |   30 +++++++++++++++---------------
 1 files changed, 15 insertions(+), 15 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index 426b34d..e87dfbc 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -335,6 +335,17 @@ static void xor_encode(uint8_t *dst, uint8_t *src1, uint8_t *src2)
     }
 }
 
+static void save_block_hdr(QEMUFile *f, RAMBlock *block, ram_addr_t offset,
+        int cont, int flag)
+{
+        qemu_put_be64(f, offset | cont | flag);
+        if (!cont) {
+                qemu_put_byte(f, strlen(block->idstr));
+                qemu_put_buffer(f, (uint8_t *)block->idstr,
+                                strlen(block->idstr));
+        }
+}
+
 static int is_dup_page(uint8_t *page, uint8_t ch)
 {
     uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch;
@@ -377,23 +388,12 @@ static int ram_save_block(QEMUFile *f)
             p = block->host + offset;
 
             if (is_dup_page(p, *p)) {
-                qemu_put_be64(f, offset | cont | RAM_SAVE_FLAG_COMPRESS);
-                if (!cont) {
-                    qemu_put_byte(f, strlen(block->idstr));
-                    qemu_put_buffer(f, (uint8_t *)block->idstr,
-                                    strlen(block->idstr));
-                }
+                save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_COMPRESS);
                 qemu_put_byte(f, *p);
                 bytes_sent = 1;
-            } else {
-                qemu_put_be64(f, offset | cont | RAM_SAVE_FLAG_PAGE);
-                if (!cont) {
-                    qemu_put_byte(f, strlen(block->idstr));
-                    qemu_put_buffer(f, (uint8_t *)block->idstr,
-                                    strlen(block->idstr));
-                }
-                qemu_put_buffer(f, p, TARGET_PAGE_SIZE);
-                bytes_sent = TARGET_PAGE_SIZE;
+                save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_PAGE);
+                 qemu_put_buffer(f, p, TARGET_PAGE_SIZE);
+                 bytes_sent = TARGET_PAGE_SIZE;
             }
 
             break;
-- 
1.7.6.5

[Qemu-devel] [PATCH v5 4/9] Add host_from_stream_offset_versioned function

[Orit Wasserman]

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 arch_init.c |   35 +++++++++++++++++++++--------------
 1 files changed, 21 insertions(+), 14 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index e87dfbc..05b8053 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -613,6 +613,23 @@ static inline void *host_from_stream_offset(QEMUFile *f,
     return NULL;
 }
 
+static inline void *host_from_stream_offset_versioned(int version_id,
+        QEMUFile *f, ram_addr_t offset, int flags)
+{
+        void *host;
+        if (version_id == 3) {
+                host = qemu_get_ram_ptr(offset);
+        } else {
+                host = host_from_stream_offset(f, offset, flags);
+        }
+        if (!host) {
+            fprintf(stderr, "Failed to convert RAM address to host"
+                    " for offset 0x%lX!\n", offset);
+            abort();
+        }
+        return host;
+}
+
 int ram_load(QEMUFile *f, void *opaque, int version_id)
 {
     ram_addr_t addr;
@@ -669,17 +686,10 @@ int ram_load(QEMUFile *f, void *opaque, int version_id)
         }
 
         if (flags & RAM_SAVE_FLAG_COMPRESS) {
-            void *host;
             uint8_t ch;
 
-            if (version_id == 3)
-                host = qemu_get_ram_ptr(addr);
-            else
-                host = host_from_stream_offset(f, addr, flags);
-            if (!host) {
-                return -EINVAL;
-            }
-
+            host = host_from_stream_offset_versioned(version_id,
+                                                     f, addr, flags);
             ch = qemu_get_byte(f);
             memset(host, ch, TARGET_PAGE_SIZE);
 #ifndef _WIN32
@@ -691,11 +701,8 @@ int ram_load(QEMUFile *f, void *opaque, int version_id)
         } else if (flags & RAM_SAVE_FLAG_PAGE) {
             void *host;
 
-            if (version_id == 3)
-                host = qemu_get_ram_ptr(addr);
-            else
-                host = host_from_stream_offset(f, addr, flags);
-
+            host = host_from_stream_offset_versioned(version_id,
+                                                     f, addr, flags);
             qemu_get_buffer(f, host, TARGET_PAGE_SIZE);
         }
         error = qemu_file_get_error(f);
-- 
1.7.6.5

[Qemu-devel] [PATCH v5 5/9] Add XBRLE to ram_save_block and ram_save_live

[Orit Wasserman]

Add migration state to store XBRLE params (enablement and cache size).
In the outgoing check to see if the page is cached and
send compressed page by using save_xbrle_page function.
In the incoming migration check to see if RAM_SAVE_FLAG_XBRLE is set
 decompress the page (by using load_xbrle function).

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 arch_init.c |  173 +++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 files changed, 163 insertions(+), 10 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index 05b8053..6b839a1 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -102,6 +102,7 @@ const uint32_t arch_type = QEMU_ARCH;
 #define RAM_SAVE_FLAG_PAGE     0x08
 #define RAM_SAVE_FLAG_EOS      0x10
 #define RAM_SAVE_FLAG_CONTINUE 0x20
+#define RAM_SAVE_FLAG_XBRLE    0x40
 
 /***********************************************************/
 /* Page cache for storing previous pages as basis for XBRLE compression */
@@ -132,6 +133,22 @@ static unsigned long cache_get_cache_pos(ram_addr_t address);
 static CacheItem *cache_item_get(unsigned long pos, int item);
 
 /***********************************************************/
+/* RAM Migration State */
+typedef struct ArchMigrationState {
+    int use_xbrle;
+    int64_t xbrle_cache_size;
+} ArchMigrationState;
+
+static ArchMigrationState arch_mig_state;
+
+void arch_set_params(int blk_enable, int shared_base, int use_xbrle,
+                     int64_t xbrle_cache_size, void *opaque)
+{
+    arch_mig_state.use_xbrle = use_xbrle;
+    arch_mig_state.xbrle_cache_size = xbrle_cache_size;
+}
+
+/***********************************************************/
 /* XBRLE (Xor Based Run-Length Encoding) */
 typedef struct XBRLEHeader {
     uint8_t xh_flags;
@@ -346,6 +363,55 @@ static void save_block_hdr(QEMUFile *f, RAMBlock *block, ram_addr_t offset,
         }
 }
 
+#define ENCODING_FLAG_XBRLE 0x1
+
+static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
+        ram_addr_t current_addr, RAMBlock *block, ram_addr_t offset, int cont)
+{
+    int cache_location = -1, slot = -1, encoded_len = 0, bytes_sent = 0;
+    XBRLEHeader hdr = {0};
+    CacheItem *it;
+    uint8_t *xor_buf = NULL, *xbrle_buf = NULL;
+
+    /* get location */
+    slot = cache_is_cached(current_addr);
+    if (slot == -1) {
+        goto done;
+    }
+    cache_location = cache_get_cache_pos(current_addr);
+
+    /* abort if page changed too much */
+    it = cache_item_get(cache_location, slot);
+
+    /* XOR encoding */
+    xor_buf = (uint8_t *) g_malloc0(TARGET_PAGE_SIZE);
+    xor_encode(xor_buf, it->it_data, current_data);
+
+    /* XBRLE (XOR+RLE) encoding (if we can ensure a 1/3 ratio) */
+    xbrle_buf = (uint8_t *) g_malloc0(TARGET_PAGE_SIZE);
+    encoded_len = rle_encode(xor_buf, TARGET_PAGE_SIZE, xbrle_buf,
+            TARGET_PAGE_SIZE/3);
+
+    if (encoded_len < 0) {
+        DPRINTF("XBRLE encoding oeverflow - sending uncompressed\n");
+        goto done;
+    }
+
+    hdr.xh_len = encoded_len;
+    hdr.xh_flags |= ENCODING_FLAG_XBRLE;
+
+    /* Send XBRLE compressed page */
+    save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_XBRLE);
+    qemu_put_buffer(f, (uint8_t *) &hdr, sizeof(hdr));
+    qemu_put_buffer(f, xbrle_buf, encoded_len);
+    bytes_sent = encoded_len + sizeof(hdr);
+
+done:
+    g_free(xor_buf);
+    g_free(xbrle_buf);
+    return bytes_sent;
+}
+
 static int is_dup_page(uint8_t *page, uint8_t ch)
 {
     uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch;
@@ -364,7 +430,7 @@ static int is_dup_page(uint8_t *page, uint8_t ch)
 static RAMBlock *last_block;
 static ram_addr_t last_offset;
 
-static int ram_save_block(QEMUFile *f)
+static int ram_save_block(QEMUFile *f, int stage)
 {
     RAMBlock *block = last_block;
     ram_addr_t offset = last_offset;
@@ -391,10 +457,18 @@ static int ram_save_block(QEMUFile *f)
                 save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_COMPRESS);
                 qemu_put_byte(f, *p);
                 bytes_sent = 1;
+            } else if (stage == 2 && arch_mig_state.use_xbrle) {
+                bytes_sent = save_xbrle_page(f, p, current_addr, block,
+                    offset, cont);
+            }
+            if (!bytes_sent) {
                 save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_PAGE);
                  qemu_put_buffer(f, p, TARGET_PAGE_SIZE);
                  bytes_sent = TARGET_PAGE_SIZE;
             }
+            if (arch_mig_state.use_xbrle) {
+                cache_insert(current_addr, p);
+            }
 
             break;
         }
@@ -501,6 +575,10 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
 
     if (stage < 0) {
         cpu_physical_memory_set_dirty_tracking(0);
+        if (arch_mig_state.use_xbrle) {
+            cache_fini();
+        }
+
         return 0;
     }
 
@@ -516,6 +594,10 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
         last_offset = 0;
         sort_ram_list();
 
+        if (arch_mig_state.use_xbrle) {
+            cache_init(arch_mig_state.xbrle_cache_size);
+        }
+
         /* Make sure all dirty bits are set */
         QLIST_FOREACH(block, &ram_list.blocks, next) {
             for (addr = block->offset; addr < block->offset + block->length;
@@ -545,7 +627,7 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
     while ((ret = qemu_file_rate_limit(f)) == 0) {
         int bytes_sent;
 
-        bytes_sent = ram_save_block(f);
+        bytes_sent = ram_save_block(f, stage);
         bytes_transferred += bytes_sent;
         if (bytes_sent == 0) { /* no more blocks */
             break;
@@ -570,19 +652,71 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
         int bytes_sent;
 
         /* flush all remaining blocks regardless of rate limiting */
-        while ((bytes_sent = ram_save_block(f)) != 0) {
+        while ((bytes_sent = ram_save_block(f, stage)) != 0) {
             bytes_transferred += bytes_sent;
         }
         cpu_physical_memory_set_dirty_tracking(0);
+        if (arch_mig_state.use_xbrle) {
+            cache_fini();
+        }
     }
 
     qemu_put_be64(f, RAM_SAVE_FLAG_EOS);
 
     expected_time = ram_save_remaining() * TARGET_PAGE_SIZE / bwidth;
 
+    DPRINTF("ram_save_live: expected(%ld) <= max(%ld)?\n", expected_time,
+        migrate_max_downtime());
+
     return (stage == 2) && (expected_time <= migrate_max_downtime());
 }
 
+static int load_xbrle(QEMUFile *f, ram_addr_t addr, void *host)
+{
+    int ret, rc = -1;
+    uint8_t *prev_page, *xor_buf = NULL, *xbrle_buf = NULL;
+    XBRLEHeader hdr = {0};
+
+    /* extract RLE header */
+    qemu_get_buffer(f, (uint8_t *) &hdr, sizeof(hdr));
+    if (!(hdr.xh_flags & ENCODING_FLAG_XBRLE)) {
+        fprintf(stderr, "Failed to load XBRLE page - wrong compression!\n");
+        goto done;
+    }
+
+    if (hdr.xh_len > TARGET_PAGE_SIZE) {
+        fprintf(stderr, "Failed to load XBRLE page - len overflow!\n");
+        goto done;
+    }
+
+    /* load data and decode */
+    xbrle_buf = (uint8_t *) g_malloc0(TARGET_PAGE_SIZE);
+    qemu_get_buffer(f, xbrle_buf, hdr.xh_len);
+
+    /* decode RLE */
+    xor_buf = (uint8_t *) g_malloc0(TARGET_PAGE_SIZE);
+    ret = rle_decode(xbrle_buf, hdr.xh_len, xor_buf, TARGET_PAGE_SIZE);
+    if (ret == -1) {
+        fprintf(stderr, "Failed to load XBRLE page - decode error!\n");
+        goto done;
+    }
+
+    if (ret != TARGET_PAGE_SIZE) {
+        fprintf(stderr, "Failed to load XBRLE page - size %d expected %d!\n",
+            ret, TARGET_PAGE_SIZE);
+        goto done;
+    }
+
+    /* decode XOR delta */
+    prev_page = host;
+    xor_encode(prev_page, prev_page, xor_buf);
+    rc = 0;
+done:
+    g_free(xor_buf);
+    g_free(xbrle_buf);
+    return rc;
+}
+
 static inline void *host_from_stream_offset(QEMUFile *f,
                                             ram_addr_t offset,
                                             int flags)
@@ -633,14 +767,18 @@ static inline void *host_from_stream_offset_versioned(int version_id,
 int ram_load(QEMUFile *f, void *opaque, int version_id)
 {
     ram_addr_t addr;
-    int flags;
+    int flags, ret = 0;
     int error;
+    static uint64_t seq_iter;
+
+    seq_iter++;
 
     if (version_id < 3 || version_id > 4) {
         return -EINVAL;
     }
 
     do {
+        void *host;
         addr = qemu_get_be64(f);
 
         flags = addr & ~TARGET_PAGE_MASK;
@@ -649,7 +787,8 @@ int ram_load(QEMUFile *f, void *opaque, int version_id)
         if (flags & RAM_SAVE_FLAG_MEM_SIZE) {
             if (version_id == 3) {
                 if (addr != ram_bytes_total()) {
-                    return -EINVAL;
+                    ret =  -EINVAL;
+                    goto done;
                 }
             } else {
                 /* Synchronize RAM block list */
@@ -668,8 +807,10 @@ int ram_load(QEMUFile *f, void *opaque, int version_id)
 
                     QLIST_FOREACH(block, &ram_list.blocks, next) {
                         if (!strncmp(id, block->idstr, sizeof(id))) {
-                            if (block->length != length)
-                                return -EINVAL;
+                            if (block->length != length) {
+                                ret =  -EINVAL;
+                                goto done;
+                            }
                             break;
                         }
                     }
@@ -677,7 +818,8 @@ int ram_load(QEMUFile *f, void *opaque, int version_id)
                     if (!block) {
                         fprintf(stderr, "Unknown ramblock \"%s\", cannot "
                                 "accept migration\n", id);
-                        return -EINVAL;
+                        ret = -EINVAL;
+                        goto done;
                     }
 
                     total_ram_bytes -= length;
@@ -704,14 +846,25 @@ int ram_load(QEMUFile *f, void *opaque, int version_id)
             host = host_from_stream_offset_versioned(version_id,
                                                      f, addr, flags);
             qemu_get_buffer(f, host, TARGET_PAGE_SIZE);
+        } else if (flags & RAM_SAVE_FLAG_XBRLE) {
+            host = host_from_stream_offset_versioned(version_id,
+                            f, addr, flags);
+            if (load_xbrle(f, addr, host) < 0) {
+                ret = -EINVAL;
+                goto done;
+            }
         }
         error = qemu_file_get_error(f);
         if (error) {
-            return error;
+            ret = error;
+            goto done;
         }
     } while (!(flags & RAM_SAVE_FLAG_EOS));
 
-    return 0;
+done:
+    DPRINTF("Completed load of VM with exit code %d seq iteration %ld\n",
+            ret, seq_iter);
+    return ret;
 }
 
 #ifdef HAS_AUDIO
-- 
1.7.6.5

[Qemu-devel] [PATCH v5 6/9] Add xbrle parameters to MigrationState

[Orit Wasserman]

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 block-migration.c |    4 +++-
 hw/hw.h           |    4 +++-
 migration.c       |   15 +++++++++++++--
 migration.h       |    3 +++
 savevm.c          |   11 +++++++----
 sysemu.h          |    4 +++-
 6 files changed, 32 insertions(+), 9 deletions(-)

diff --git a/block-migration.c b/block-migration.c
index 2b7edbc..60f2d62 100644
--- a/block-migration.c
+++ b/block-migration.c
@@ -706,7 +706,9 @@ static int block_load(QEMUFile *f, void *opaque, int version_id)
     return 0;
 }
 
-static void block_set_params(int blk_enable, int shared_base, void *opaque)
+static void block_set_params(int blk_enable, int shared_base,
+                             int use_xbrle, int64_t xbrle_cache_size,
+                             void *opaque)
 {
     block_mig_state.blk_enable = blk_enable;
     block_mig_state.shared_base = shared_base;
diff --git a/hw/hw.h b/hw/hw.h
index efa04d1..ab0b92c 100644
--- a/hw/hw.h
+++ b/hw/hw.h
@@ -245,7 +245,9 @@ static inline void qemu_get_sbe64s(QEMUFile *f, int64_t *pv)
 int64_t qemu_ftell(QEMUFile *f);
 int64_t qemu_fseek(QEMUFile *f, int64_t pos, int whence);
 
-typedef void SaveSetParamsHandler(int blk_enable, int shared, void * opaque);
+typedef void SaveSetParamsHandler(int blk_enable, int shared,
+                                  int use_xbrle, int64_t xbrle_cache_size,
+                                  void *opaque);
 typedef void SaveStateHandler(QEMUFile *f, void *opaque);
 typedef int SaveLiveStateHandler(Monitor *mon, QEMUFile *f, int stage,
                                  void *opaque);
diff --git a/migration.c b/migration.c
index 412fdfe..ed47958 100644
--- a/migration.c
+++ b/migration.c
@@ -41,6 +41,11 @@ enum {
 
 #define MAX_THROTTLE  (32 << 20)      /* Migration speed throttling */
 
+/* Migration XBRLE cache size */
+#define DEFAULT_MIGRATE_CACHE_SIZE (64 * 1024 * 1024)
+
+static int64_t migrate_cache_size = DEFAULT_MIGRATE_CACHE_SIZE;
+
 static NotifierList migration_state_notifiers =
     NOTIFIER_LIST_INITIALIZER(migration_state_notifiers);
 
@@ -365,7 +370,8 @@ void migrate_fd_connect(MigrationState *s)
                                       migrate_fd_close);
 
     DPRINTF("beginning savevm\n");
-    ret = qemu_savevm_state_begin(s->mon, s->file, s->blk, s->shared);
+    ret = qemu_savevm_state_begin(s->mon, s->file, s->blk, s->shared,
+                                  s->use_xbrle, s->xbrle_cache_size);
     if (ret < 0) {
         DPRINTF("failed, %d\n", ret);
         migrate_fd_error(s);
@@ -375,6 +381,8 @@ void migrate_fd_connect(MigrationState *s)
 }
 
 static MigrationState *migrate_init(Monitor *mon, int detach, int blk, int inc)
+static MigrationState *migrate_init(Monitor *mon, int detach, int blk, int inc,
+                                    int use_xbrle, int64_t xbrle_cache_size)
 {
     MigrationState *s = migrate_get_current();
     int64_t bandwidth_limit = s->bandwidth_limit;
@@ -383,6 +391,8 @@ static MigrationState *migrate_init(Monitor *mon, int detach, int blk, int inc)
     s->bandwidth_limit = bandwidth_limit;
     s->blk = blk;
     s->shared = inc;
+    s->use_xbrle = use_xbrle;
+    s->xbrle_cache_size = xbrle_cache_size;
 
     /* s->mon is used for two things:
        - pass fd in fd migration
@@ -418,6 +428,7 @@ int do_migrate(Monitor *mon, const QDict *qdict, QObject **ret_data)
     int detach = qdict_get_try_bool(qdict, "detach", 0);
     int blk = qdict_get_try_bool(qdict, "blk", 0);
     int inc = qdict_get_try_bool(qdict, "inc", 0);
+    int use_xbrle = qdict_get_try_bool(qdict, "xbrle", 0);
     const char *uri = qdict_get_str(qdict, "uri");
     int ret;
 
@@ -436,7 +447,7 @@ int do_migrate(Monitor *mon, const QDict *qdict, QObject **ret_data)
         return -1;
     }
 
-    s = migrate_init(mon, detach, blk, inc);
+    s = migrate_init(mon, detach, blk, inc, use_xbrle, migrate_cache_size);
 
     if (strstart(uri, "tcp:", &p)) {
         ret = tcp_start_outgoing_migration(s, p);
diff --git a/migration.h b/migration.h
index 372b066..592af6a 100644
--- a/migration.h
+++ b/migration.h
@@ -34,6 +34,9 @@ struct MigrationState
     void *opaque;
     int blk;
     int shared;
+    int use_xbrle;
+    int64_t xbrle_cache_size;
+
 };
 
 void process_incoming_migration(QEMUFile *f);
diff --git a/savevm.c b/savevm.c
index f153c25..3650f56 100644
--- a/savevm.c
+++ b/savevm.c
@@ -1277,7 +1277,8 @@ int register_savevm(DeviceState *dev,
                     void *opaque)
 {
     return register_savevm_live(dev, idstr, instance_id, version_id,
-                                NULL, NULL, save_state, load_state, opaque);
+                                arch_set_params, NULL, save_state,
+                                load_state, opaque);
 }
 
 void unregister_savevm(DeviceState *dev, const char *idstr, void *opaque)
@@ -1554,7 +1555,8 @@ bool qemu_savevm_state_blocked(Monitor *mon)
 }
 
 int qemu_savevm_state_begin(Monitor *mon, QEMUFile *f, int blk_enable,
-                            int shared)
+                            int shared, int use_xbrle,
+                            int64_t xbrle_cache_size)
 {
     SaveStateEntry *se;
     int ret;
@@ -1563,7 +1565,8 @@ int qemu_savevm_state_begin(Monitor *mon, QEMUFile *f, int blk_enable,
         if(se->set_params == NULL) {
             continue;
 	}
-	se->set_params(blk_enable, shared, se->opaque);
+        se->set_params(blk_enable, shared, use_xbrle, xbrle_cache_size,
+                       se->opaque);
     }
     
     qemu_put_be32(f, QEMU_VM_FILE_MAGIC);
@@ -1707,7 +1710,7 @@ static int qemu_savevm_state(Monitor *mon, QEMUFile *f)
         goto out;
     }
 
-    ret = qemu_savevm_state_begin(mon, f, 0, 0);
+    ret = qemu_savevm_state_begin(mon, f, 0, 0, 0, 0);
     if (ret < 0)
         goto out;
 
diff --git a/sysemu.h b/sysemu.h
index 3806901..78e1074 100644
--- a/sysemu.h
+++ b/sysemu.h
@@ -67,7 +67,8 @@ void qemu_announce_self(void);
 
 bool qemu_savevm_state_blocked(Monitor *mon);
 int qemu_savevm_state_begin(Monitor *mon, QEMUFile *f, int blk_enable,
-                            int shared);
+                            int shared, int use_xbrle,
+                            int64_t xbrle_cache_size);
 int qemu_savevm_state_iterate(Monitor *mon, QEMUFile *f);
 int qemu_savevm_state_complete(Monitor *mon, QEMUFile *f);
 void qemu_savevm_state_cancel(Monitor *mon, QEMUFile *f);
@@ -174,4 +175,5 @@ void register_devices(void);
 void add_boot_device_path(int32_t bootindex, DeviceState *dev,
                           const char *suffix);
 char *get_boot_devices_list(uint32_t *size);
+
 #endif
-- 
1.7.6.5

[Qemu-devel] [PATCH v5 7/9] Add set_cachesize to change XBRLE cache size

[Orit Wasserman]

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 migration.c |   25 ++++++++++++++++++++++++-
 migration.h |    7 +++++++
 2 files changed, 31 insertions(+), 1 deletions(-)

diff --git a/migration.c b/migration.c
index ed47958..3d88cdd 100644
--- a/migration.c
+++ b/migration.c
@@ -380,7 +380,30 @@ void migrate_fd_connect(MigrationState *s)
     migrate_fd_put_ready(s);
 }
 
-static MigrationState *migrate_init(Monitor *mon, int detach, int blk, int inc)
+void do_migrate_set_cachesize(Monitor *mon, const QDict *qdict)
+{
+    ssize_t bytes;
+    const char *value = qdict_get_str(qdict, "value");
+
+    bytes = strtosz(value, NULL);
+    if (bytes < 0) {
+        monitor_printf(mon, "invalid cache size: %s\n", value);
+        return;
+    }
+
+    /* On 32-bit hosts, QEMU is limited by virtual address space */
+    if (bytes > (2047 << 20) && HOST_LONG_BITS == 32) {
+        monitor_printf(mon, "cache can't exceed 2047 MB RAM limit on host\n");
+        return;
+    }
+    if (bytes != (uint64_t) bytes) {
+        monitor_printf(mon, "cache size too large\n");
+        return;
+    }
+
+    migrate_cache_size = bytes;
+}
+
 static MigrationState *migrate_init(Monitor *mon, int detach, int blk, int inc,
                                     int use_xbrle, int64_t xbrle_cache_size)
 {
diff --git a/migration.h b/migration.h
index 592af6a..6de09c8 100644
--- a/migration.h
+++ b/migration.h
@@ -98,4 +98,11 @@ void migrate_add_blocker(Error *reason);
  */
 void migrate_del_blocker(Error *reason);
 
+void do_migrate_set_cachesize(Monitor *mon, const QDict *qdict);
+
+void arch_set_params(int blk_enable, int shared_base,
+        int use_xbrle, int64_t xbrle_cache_size, void *opaque);
+
+int xbrle_mig_active(void);
+
 #endif
-- 
1.7.6.5

[Qemu-devel] [PATCH v5 8/9] QMP commands changes

[Orit Wasserman]

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 hmp-commands.hx |   34 ++++++++++++++++++++++++++--------
 qmp-commands.hx |   44 +++++++++++++++++++++++++++++++++++++-------
 2 files changed, 63 insertions(+), 15 deletions(-)

diff --git a/hmp-commands.hx b/hmp-commands.hx
index 14838b7..952d5cd 100644
--- a/hmp-commands.hx
+++ b/hmp-commands.hx
@@ -746,24 +746,29 @@ ETEXI
 
     {
         .name       = "migrate",
-        .args_type  = "detach:-d,blk:-b,inc:-i,uri:s",
-        .params     = "[-d] [-b] [-i] uri",
-        .help       = "migrate to URI (using -d to not wait for completion)"
-		      "\n\t\t\t -b for migration without shared storage with"
-		      " full copy of disk\n\t\t\t -i for migration without "
-		      "shared storage with incremental copy of disk "
-		      "(base image shared between src and destination)",
+        .args_type  = "detach:-d,blk:-b,inc:-i,xbrle:-x,uri:s",
+        .params     = "[-d] [-b] [-i] [-x] uri",
+        .help       = "migrate to URI"
+                      "\n\t -d to not wait for completion"
+                      "\n\t -b for migration without shared storage with"
+                      " full copy of disk"
+                      "\n\t -i for migration without"
+                      " shared storage with incremental copy of disk"
+                      " (base image shared between source and destination)"
+                      "\n\t -x to use XBRLE page delta compression",
         .user_print = monitor_user_noop,	
 	.mhandler.cmd_new = do_migrate,
     },
 
 
 STEXI
-@item migrate [-d] [-b] [-i] @var{uri}
+@item migrate [-d] [-b] [-i] [-x] @var{uri}
 @findex migrate
 Migrate to @var{uri} (using -d to not wait for completion).
 	-b for migration with full copy of disk
 	-i for migration with incremental copy of disk (base image is shared)
+	-x to use XBRLE page delta compression
+
 ETEXI
 
     {
@@ -781,6 +786,19 @@ Cancel the current VM migration.
 ETEXI
 
     {
+        .name       = "migrate_set_cachesize",
+        .args_type  = "value:s",
+        .params     = "value",
+        .help       = "set cache size (in MB) for XBRLE migrations",
+        .mhandler.cmd = do_migrate_set_cachesize,
+    },
+
+STEXI
+@item migrate_set_cachesize @var{value}
+Set cache size (in MB) for xbrle migrations.
+ETEXI
+
+    {
         .name       = "migrate_set_speed",
         .args_type  = "value:o",
         .params     = "value",
diff --git a/qmp-commands.hx b/qmp-commands.hx
index 7e3f4b9..34bdfe9 100644
--- a/qmp-commands.hx
+++ b/qmp-commands.hx
@@ -430,13 +430,16 @@ EQMP
 
     {
         .name       = "migrate",
-        .args_type  = "detach:-d,blk:-b,inc:-i,uri:s",
-        .params     = "[-d] [-b] [-i] uri",
-        .help       = "migrate to URI (using -d to not wait for completion)"
-		      "\n\t\t\t -b for migration without shared storage with"
-		      " full copy of disk\n\t\t\t -i for migration without "
-		      "shared storage with incremental copy of disk "
-		      "(base image shared between src and destination)",
+        .args_type  = "detach:-d,blk:-b,inc:-i,xbrle:-x,uri:s",
+        .params     = "[-d] [-b] [-i] [-x] uri",
+        .help       = "migrate to URI"
+                      "\n\t -d to not wait for completion"
+                      "\n\t -b for migration without shared storage with"
+                      " full copy of disk"
+                      "\n\t -i for migration without"
+                      " shared storage with incremental copy of disk"
+                      " (base image shared between source and destination)"
+                      "\n\t -x to use XBRLE page delta compression",
         .user_print = monitor_user_noop,	
 	.mhandler.cmd_new = do_migrate,
     },
@@ -452,6 +455,7 @@ Arguments:
 - "blk": block migration, full disk copy (json-bool, optional)
 - "inc": incremental disk copy (json-bool, optional)
 - "uri": Destination URI (json-string)
+- "xbrle": to use XBRLE page delta compression
 
 Example:
 
@@ -490,6 +494,32 @@ Example:
 EQMP
 
     {
+        .name       = "migrate_set_cachesize",
+        .args_type  = "value:s",
+        .params     = "value",
+        .help       = "set cache size (in MB) for xbrle migrations",
+        .mhandler.cmd = do_migrate_set_cachesize,
+    },
+
+SQMP
+migrate_set_cachesize
+---------------------
+
+Set cache size to be used by XBRLE migration
+
+Arguments:
+
+- "value": cache size in bytes (json-number)
+
+Example:
+
+-> { "execute": "migrate_set_cachesize", "arguments": { "value": 500M } }
+<- { "return": {} }
+
+
+EQMP
+
+    {
         .name       = "migrate_set_speed",
         .args_type  = "value:o",
         .mhandler.cmd_new = qmp_marshal_input_migrate_set_speed,
-- 
1.7.6.5

[Qemu-devel] [PATCH v5 9/9] Add XBRLE statistics information

[Orit Wasserman]

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 arch_init.c |   67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 migration.c |   11 +++++++++
 migration.h |    9 ++++++++
 3 files changed, 87 insertions(+), 0 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index 6b839a1..037d8ba 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -149,6 +149,65 @@ void arch_set_params(int blk_enable, int shared_base, int use_xbrle,
 }
 
 /***********************************************************/
+/* accounting */
+typedef struct AccountingInfo {
+    uint64_t dup_pages;
+    uint64_t norm_pages;
+    uint64_t xbrle_bytes;
+    uint64_t xbrle_pages;
+    uint64_t xbrle_overflow;
+    uint64_t xbrle_cache_miss;
+    uint64_t iterations;
+} AccountingInfo;
+
+static AccountingInfo acct_info;
+
+static void acct_clear(void)
+{
+    bzero(&acct_info, sizeof(acct_info));
+}
+
+uint64_t dup_mig_bytes_transferred(void)
+{
+    return acct_info.dup_pages;
+}
+
+uint64_t dup_mig_pages_transferred(void)
+{
+    return acct_info.dup_pages;
+}
+
+uint64_t norm_mig_bytes_transferred(void)
+{
+    return acct_info.norm_pages * TARGET_PAGE_SIZE;
+}
+
+uint64_t norm_mig_pages_transferred(void)
+{
+    return acct_info.norm_pages;
+}
+
+uint64_t xbrle_mig_bytes_transferred(void)
+{
+    return acct_info.xbrle_bytes;
+}
+
+uint64_t xbrle_mig_pages_transferred(void)
+{
+    return acct_info.xbrle_pages;
+}
+
+uint64_t xbrle_mig_pages_overflow(void)
+{
+    return acct_info.xbrle_overflow;
+}
+
+uint64_t xbrle_mig_pages_cache_miss(void)
+{
+    return acct_info.xbrle_cache_miss;
+}
+
+/***********************************************************/
 /* XBRLE (Xor Based Run-Length Encoding) */
 typedef struct XBRLEHeader {
     uint8_t xh_flags;
@@ -376,6 +435,7 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
     /* get location */
     slot = cache_is_cached(current_addr);
     if (slot == -1) {
+        acct_info.xbrle_cache_miss++;
         goto done;
     }
     cache_location = cache_get_cache_pos(current_addr);
@@ -394,6 +454,7 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
 
     if (encoded_len < 0) {
         DPRINTF("XBRLE encoding oeverflow - sending uncompressed\n");
+        acct_info.xbrle_overflow++;
         goto done;
     }
 
@@ -404,7 +465,9 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
     save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_XBRLE);
     qemu_put_buffer(f, (uint8_t *) &hdr, sizeof(hdr));
     qemu_put_buffer(f, xbrle_buf, encoded_len);
+    acct_info.xbrle_pages++;
     bytes_sent = encoded_len + sizeof(hdr);
+    acct_info.xbrle_bytes += bytes_sent;
 
 done:
     g_free(xor_buf);
@@ -457,6 +520,7 @@ static int ram_save_block(QEMUFile *f, int stage)
                 save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_COMPRESS);
                 qemu_put_byte(f, *p);
                 bytes_sent = 1;
+                acct_info.dup_pages++;
             } else if (stage == 2 && arch_mig_state.use_xbrle) {
                 bytes_sent = save_xbrle_page(f, p, current_addr, block,
                     offset, cont);
@@ -465,6 +529,7 @@ static int ram_save_block(QEMUFile *f, int stage)
                 save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_PAGE);
                  qemu_put_buffer(f, p, TARGET_PAGE_SIZE);
                  bytes_sent = TARGET_PAGE_SIZE;
+                 acct_info.norm_pages++;
             }
             if (arch_mig_state.use_xbrle) {
                 cache_insert(current_addr, p);
@@ -596,6 +661,7 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
 
         if (arch_mig_state.use_xbrle) {
             cache_init(arch_mig_state.xbrle_cache_size);
+            acct_clear();
         }
 
         /* Make sure all dirty bits are set */
@@ -629,6 +695,7 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
 
         bytes_sent = ram_save_block(f, stage);
         bytes_transferred += bytes_sent;
+        acct_info.iterations++;
         if (bytes_sent == 0) { /* no more blocks */
             break;
         }
diff --git a/migration.c b/migration.c
index 3d88cdd..383ceef 100644
--- a/migration.c
+++ b/migration.c
@@ -141,6 +141,17 @@ MigrationInfo *qmp_query_migrate(Error **errp)
             info->disk->remaining = blk_mig_bytes_remaining();
             info->disk->total = blk_mig_bytes_total();
         }
+
+       if (s->use_xbrle) {
+            info->has_xbrle = true;
+            info->cache = g_malloc0(sizeof(*info->cache));
+            info->cache->dup_pages = dup_mig_pages_transferred();
+            info->cache->norm_pages = norm_mig_pages_transferred();
+            info->cache->xbrle_bytes  = xbrle_mig_bytes_transferred();
+            info->cache->xbrle_pages  = xbrle_mig_pages_transferred();
+            info->cache->xbrle_overflow = xbrle_mig_pages_overflow();
+            info->cache->xbrle_cache_miss = xbrle_mig_pages_cache_miss();
+        }
         break;
     case MIG_STATE_COMPLETED:
         info->has_status = true;
diff --git a/migration.h b/migration.h
index 6de09c8..dd06ef6 100644
--- a/migration.h
+++ b/migration.h
@@ -81,6 +81,15 @@ uint64_t ram_bytes_remaining(void);
 uint64_t ram_bytes_transferred(void);
 uint64_t ram_bytes_total(void);
 
+uint64_t dup_mig_bytes_transferred(void);
+uint64_t dup_mig_pages_transferred(void);
+uint64_t norm_mig_bytes_transferred(void);
+uint64_t norm_mig_pages_transferred(void);
+uint64_t xbrle_mig_bytes_transferred(void);
+uint64_t xbrle_mig_pages_transferred(void);
+uint64_t xbrle_mig_pages_overflow(void);
+uint64_t xbrle_mig_pages_cache_miss(void);
+
 int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque);
 int ram_load(QEMUFile *f, void *opaque, int version_id);
 
-- 
1.7.6.5

Re: [Qemu-devel] [PATCH v5 8/9] QMP commands changes

[Stefan Hajnoczi]

On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote:
> +        .args_type  = "detach:-d,blk:-b,inc:-i,xbrle:-x,uri:s",
> +        .params     = "[-d] [-b] [-i] [-x] uri",
> +        .help       = "migrate to URI"
> +                      "\n\t -d to not wait for completion"
> +                      "\n\t -b for migration without shared storage with"
> +                      " full copy of disk"
> +                      "\n\t -i for migration without"
> +                      " shared storage with incremental copy of disk"
> +                      " (base image shared between source and destination)"
> +                      "\n\t -x to use XBRLE page delta compression",

It's too bad that this algorithm is user-visible and needs to be
expicitly enabled/disabled.  I think it would be useful in a much
wider range of cases if the trade-offs were understood well enough so
that QEMU can include a threshold or heuristic which chooses the
migration algorithm behind the scenes.

I'm afraid that locking XBRLE behind an explicit option means we're
merging dead code.  What do you think?

Stefan

Re: [Qemu-devel] [PATCH v5 8/9] QMP commands changes

[Orit Wasserman]

On 01/03/2012 05:47 PM, Stefan Hajnoczi wrote:
> On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote:
>> +        .args_type  = "detach:-d,blk:-b,inc:-i,xbrle:-x,uri:s",
>> +        .params     = "[-d] [-b] [-i] [-x] uri",
>> +        .help       = "migrate to URI"
>> +                      "\n\t -d to not wait for completion"
>> +                      "\n\t -b for migration without shared storage with"
>> +                      " full copy of disk"
>> +                      "\n\t -i for migration without"
>> +                      " shared storage with incremental copy of disk"
>> +                      " (base image shared between source and destination)"
>> +                      "\n\t -x to use XBRLE page delta compression",
> 
> It's too bad that this algorithm is user-visible and needs to be
> expicitly enabled/disabled.  I think it would be useful in a much
> wider range of cases if the trade-offs were understood well enough so
> that QEMU can include a threshold or heuristic which chooses the
> migration algorithm behind the scenes.

I agree that an automatic switching on/off XBRLE is very desirable. 
At the first phase we merge it as a user option, and the in the next phase will be adding
the part that switch it on/off.
> 
> I'm afraid that locking XBRLE behind an explicit option means we're
> merging dead code.  What do you think?

Even as a user option this option will be useful , in many cases users are aware of 
their workload and can set this option on.

Orit
> 
> Stefan

Re: [Qemu-devel] [PATCH v5 8/9] QMP commands changes

[Stefan Hajnoczi]

On Tue, Jan 3, 2012 at 3:57 PM, Orit Wasserman <owasserm@redhat.com> wrote:
> On 01/03/2012 05:47 PM, Stefan Hajnoczi wrote:
>> On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote:
>>> +        .args_type  = "detach:-d,blk:-b,inc:-i,xbrle:-x,uri:s",
>>> +        .params     = "[-d] [-b] [-i] [-x] uri",
>>> +        .help       = "migrate to URI"
>>> +                      "\n\t -d to not wait for completion"
>>> +                      "\n\t -b for migration without shared storage with"
>>> +                      " full copy of disk"
>>> +                      "\n\t -i for migration without"
>>> +                      " shared storage with incremental copy of disk"
>>> +                      " (base image shared between source and destination)"
>>> +                      "\n\t -x to use XBRLE page delta compression",
>>
>> It's too bad that this algorithm is user-visible and needs to be
>> expicitly enabled/disabled.  I think it would be useful in a much
>> wider range of cases if the trade-offs were understood well enough so
>> that QEMU can include a threshold or heuristic which chooses the
>> migration algorithm behind the scenes.
>
> I agree that an automatic switching on/off XBRLE is very desirable.
> At the first phase we merge it as a user option, and the in the next phase will be adding
> the part that switch it on/off.

Okay, if there's an intent to do that next phase then great.  I'll
take a look at this series and review it soon.

Stefan

Re: [Qemu-devel] [PATCH v5 0/9] XBZRLE delta for live migration of large memory apps

[Anthony Liguori]

On 01/03/2012 09:34 AM, Orit Wasserman wrote:
> Changes from v4:
> 1) Rebase
> 2) divide patch into 9 patches
> 3) move memory allocation into cache_insert
>
> By using XBZRLE (Xor Binary Zero Run-Length-Encoding) we can reduce VM downtime
> and total live-migration time of VMs running memory write intensive workloads
> typical of large enterprise applications such as SAP ERP Systems, and generally
> speaking for any application with a sparse memory update pattern.
>
> On the sender side XBZRLE is used as a compact delta encoding of page updates,
> retrieving the old page content from an LRU cache (default size of 64 MB). The
> receiving side uses the existing page content and XBZRLE to decode the new page
> content.
>
> Work was originally based on research results published VEE 2011: Evaluation of
> Delta Compression Techniques for Efficient Live Migration of Large Virtual
> Machines by Benoit, Svard, Tordsson and Elmroth. Additionally the delta encoder
> XBRLE was improved further using XBZRLE instead.
>
> XBZRLE has a sustained bandwidth of 2-2.5 GB/s for typical workloads making it
> ideal for in-line, real-time encoding such as is needed for live-migration.
>
> A typical usage scenario:
>      {qemu} migrate_set_cachesize 256m

How does one intelligently choose a cache size?  How bad is it to choose the 
wrong cache size?

>      {qemu} migrate -x -d tcp:destination.host:4444

We need to make this a negotiated feature, not a requirement for the user to 
figure out.

Please go back to the previous thread for more details on this.

Regards,

Anthony Liguori

>      {qemu} info migrate
>      ...
>      transferred ram-duplicate: A kbytes
>      transferred ram-duplicate: B pages
>      transferred ram-normal: C kbytes
>      transferred ram-normal: D pages
>      transferred ram-xbrle: E kbytes
>      transferred ram-xbrle: F pages
>      overflow ram-xbrle: G pages
>      cache-hit ram-xbrle: H pages
>      cache-lookup ram-xbrle: J pages
>
> Testing: live migration with XBZRLE completed in 110 seconds, without live
> migration was not able to complete.
>
> A simple synthetic memory r/w load generator:
> ..    include<stdlib.h>
> ..    include<stdio.h>
> ..    int main()
> ..    {
> ..        char *buf = (char *) calloc(4096, 4096);
> ..        while (1) {
> ..            int i;
> ..            for (i = 0; i<  4096 * 4; i++) {
> ..                buf[i * 4096 / 4]++;
> ..            }
> ..            printf(".");
> ..        }
> ..    }
>
> 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>
>
>   arch_init.c       |  546 +++++++++++++++++++++++++++++++++++++++++++++++++----
>   block-migration.c |    4 +-
>   hmp-commands.hx   |   34 +++-
>   hw/hw.h           |    4 +-
>   migration.c       |   51 +++++-
>   migration.h       |   19 ++
>   qmp-commands.hx   |   44 ++++-
>   savevm.c          |   11 +-
>   sysemu.h          |    4 +-
>   9 files changed, 653 insertions(+), 64 deletions(-)
>

Re: [Qemu-devel] [PATCH v5 0/9] XBZRLE delta for live migration of large memory apps

[Orit Wasserman]

On 01/03/2012 06:32 PM, Anthony Liguori wrote:
> On 01/03/2012 09:34 AM, Orit Wasserman wrote:
>> Changes from v4:
>> 1) Rebase
>> 2) divide patch into 9 patches
>> 3) move memory allocation into cache_insert
>>
>> By using XBZRLE (Xor Binary Zero Run-Length-Encoding) we can reduce VM downtime
>> and total live-migration time of VMs running memory write intensive workloads
>> typical of large enterprise applications such as SAP ERP Systems, and generally
>> speaking for any application with a sparse memory update pattern.
>>
>> On the sender side XBZRLE is used as a compact delta encoding of page updates,
>> retrieving the old page content from an LRU cache (default size of 64 MB). The
>> receiving side uses the existing page content and XBZRLE to decode the new page
>> content.
>>
>> Work was originally based on research results published VEE 2011: Evaluation of
>> Delta Compression Techniques for Efficient Live Migration of Large Virtual
>> Machines by Benoit, Svard, Tordsson and Elmroth. Additionally the delta encoder
>> XBRLE was improved further using XBZRLE instead.
>>
>> XBZRLE has a sustained bandwidth of 2-2.5 GB/s for typical workloads making it
>> ideal for in-line, real-time encoding such as is needed for live-migration.
>>
>> A typical usage scenario:
>>      {qemu} migrate_set_cachesize 256m
> 
> How does one intelligently choose a cache size?  How bad is it to choose the wrong cache size?

If the cache you chose is was too big than you just wasted some memory (probably small amount for extra 100M it is around 12K).
If the cache is too small than you are not using the full capability , if you will enlarge the cache
you can compress more pages. you still get performance benefits but you will get more if had chosen bigger cache. 
> 
>>      {qemu} migrate -x -d tcp:destination.host:4444
> 
> We need to make this a negotiated feature, not a requirement for the user to figure out.
> 
> Please go back to the previous thread for more details on this.

I will update the patch for the feature to be negotiable. 
> 
> Regards,
> 
> Anthony Liguori
> 
>>      {qemu} info migrate
>>      ...
>>      transferred ram-duplicate: A kbytes
>>      transferred ram-duplicate: B pages
>>      transferred ram-normal: C kbytes
>>      transferred ram-normal: D pages
>>      transferred ram-xbrle: E kbytes
>>      transferred ram-xbrle: F pages
>>      overflow ram-xbrle: G pages
>>      cache-hit ram-xbrle: H pages
>>      cache-lookup ram-xbrle: J pages
>>
>> Testing: live migration with XBZRLE completed in 110 seconds, without live
>> migration was not able to complete.
>>
>> A simple synthetic memory r/w load generator:
>> ..    include<stdlib.h>
>> ..    include<stdio.h>
>> ..    int main()
>> ..    {
>> ..        char *buf = (char *) calloc(4096, 4096);
>> ..        while (1) {
>> ..            int i;
>> ..            for (i = 0; i<  4096 * 4; i++) {
>> ..                buf[i * 4096 / 4]++;
>> ..            }
>> ..            printf(".");
>> ..        }
>> ..    }
>>
>> 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>
>>
>>   arch_init.c       |  546 +++++++++++++++++++++++++++++++++++++++++++++++++----
>>   block-migration.c |    4 +-
>>   hmp-commands.hx   |   34 +++-
>>   hw/hw.h           |    4 +-
>>   migration.c       |   51 +++++-
>>   migration.h       |   19 ++
>>   qmp-commands.hx   |   44 ++++-
>>   savevm.c          |   11 +-
>>   sysemu.h          |    4 +-
>>   9 files changed, 653 insertions(+), 64 deletions(-)
>>
> 

Re: [Qemu-devel] [PATCH v5 1/9] Add cache handling functions

[Anthony Liguori]

On 01/03/2012 09:34 AM, Orit Wasserman wrote:
> Add page caching mechanism.
> The pages are stored in the cache ordered by their address.
>
> Signed-off-by: Orit Wasserman<owasserm@redhat.com>
> ---
>   arch_init.c |  183 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>   1 files changed, 183 insertions(+), 0 deletions(-)
>
> diff --git a/arch_init.c b/arch_init.c
> index d4c92b0..fdda277 100644
> --- a/arch_init.c
> +++ b/arch_init.c
> @@ -28,6 +28,7 @@
>   #include<sys/types.h>
>   #include<sys/mman.h>
>   #endif
> +#include<assert.h>
>   #include "config.h"
>   #include "monitor.h"
>   #include "sysemu.h"
> @@ -42,6 +43,14 @@
>   #include "gdbstub.h"
>   #include "hw/smbios.h"
>
> +#ifdef DEBUG_ARCH_INIT
> +#define DPRINTF(fmt, ...) \
> +    do { fprintf(stdout, "arch_init: " fmt, ## __VA_ARGS__); } while (0)
> +#else
> +#define DPRINTF(fmt, ...) \
> +    do { } while (0)
> +#endif
> +
>   #ifdef TARGET_SPARC
>   int graphic_width = 1024;
>   int graphic_height = 768;
> @@ -94,6 +103,180 @@ const uint32_t arch_type = QEMU_ARCH;
>   #define RAM_SAVE_FLAG_EOS      0x10
>   #define RAM_SAVE_FLAG_CONTINUE 0x20
>
> +/***********************************************************/
> +/* Page cache for storing previous pages as basis for XBRLE compression */
> +#define CACHE_N_WAY 2 /* 2-way assossiative cache */

Is there any reason we can't just use a GCache for this?

http://developer.gnome.org/glib/stable/glib-Caches.html

Regards,

Anthony Liguori

Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

[Anthony Liguori]

On 01/03/2012 09:34 AM, Orit Wasserman wrote:
> Signed-off-by: Orit Wasserman<owasserm@redhat.com>
> ---
>   arch_init.c |   58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>   1 files changed, 58 insertions(+), 0 deletions(-)
>
> diff --git a/arch_init.c b/arch_init.c
> index fdda277..426b34d 100644
> --- a/arch_init.c
> +++ b/arch_init.c
> @@ -139,6 +139,9 @@ typedef struct XBRLEHeader {
>       uint32_t xh_cksum;
>   } XBRLEHeader;
>
> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen);
> +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen);
> +
>   /***********************************************************/
>   /* XBRLE page cache implementation */
>   static CacheItem *cache_item_get(unsigned long pos, int item)
> @@ -277,6 +280,61 @@ static void cache_insert(unsigned long addr, uint8_t *pdata)
>       it->it_addr = addr;
>   }
>
> +/* XBRLE (Xor Based Run-Length Encoding) */
> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen)
> +{
> +    int d = 0, ch_run = 0, i;
> +    uint8_t prev = 0, ch = 0;
> +
> +    for (i = 0; i<= slen; i++) {
> +        if (i != slen) {
> +            ch = src[i];
> +        }
> +
> +        if (!i || (i != slen&&  ch == prev&&  ch_run<  255)) {
> +            ch_run++;
> +        } else {
> +            if (d+2>  dlen) {
> +                return -1;
> +            }
> +            *dst++ = ch_run;
> +            *dst++ = prev;
> +            d += 2;
> +            ch_run = 1;
> +        }
> +
> +        prev = ch;
> +    }
> +    return d;
> +}
> +
> +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen)
> +{
> +    int d = 0, s;
> +
> +    for (s = 0; s<  slen-1; s += 2) {
> +        uint8_t ch_run = src[s];
> +        uint8_t ch = src[s+1];
> +        while (ch_run--) {
> +            if (d == dlen) {
> +                return -1;
> +            }
> +            dst[d] = ch;
> +            d++;
> +        }
> +    }
> +    return d;
> +}
> +
> +static void xor_encode(uint8_t *dst, uint8_t *src1, uint8_t *src2)
> +{
> +    int i;
> +
> +    for (i = 0; i<  TARGET_PAGE_SIZE; i++) {
> +        dst[i] = src1[i] ^ src2[i];
> +    }
> +}
> +

I don't think any of these need to be in arch_init.c.  It would be nicer to make 
a xbzrle.c file for this stuff.

Regards,

Anthony Liguori

>   static int is_dup_page(uint8_t *page, uint8_t ch)
>   {
>       uint32_t val = ch<<  24 | ch<<  16 | ch<<  8 | ch;

Re: [Qemu-devel] [PATCH v5 1/9] Add cache handling functions

[Orit Wasserman]

On 01/03/2012 09:54 PM, Anthony Liguori wrote:
> On 01/03/2012 09:34 AM, Orit Wasserman wrote:
>> Add page caching mechanism.
>> The pages are stored in the cache ordered by their address.
>>
>> Signed-off-by: Orit Wasserman<owasserm@redhat.com>
>> ---
>>   arch_init.c |  183 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>   1 files changed, 183 insertions(+), 0 deletions(-)
>>
>> diff --git a/arch_init.c b/arch_init.c
>> index d4c92b0..fdda277 100644
>> --- a/arch_init.c
>> +++ b/arch_init.c
>> @@ -28,6 +28,7 @@
>>   #include<sys/types.h>
>>   #include<sys/mman.h>
>>   #endif
>> +#include<assert.h>
>>   #include "config.h"
>>   #include "monitor.h"
>>   #include "sysemu.h"
>> @@ -42,6 +43,14 @@
>>   #include "gdbstub.h"
>>   #include "hw/smbios.h"
>>
>> +#ifdef DEBUG_ARCH_INIT
>> +#define DPRINTF(fmt, ...) \
>> +    do { fprintf(stdout, "arch_init: " fmt, ## __VA_ARGS__); } while (0)
>> +#else
>> +#define DPRINTF(fmt, ...) \
>> +    do { } while (0)
>> +#endif
>> +
>>   #ifdef TARGET_SPARC
>>   int graphic_width = 1024;
>>   int graphic_height = 768;
>> @@ -94,6 +103,180 @@ const uint32_t arch_type = QEMU_ARCH;
>>   #define RAM_SAVE_FLAG_EOS      0x10
>>   #define RAM_SAVE_FLAG_CONTINUE 0x20
>>
>> +/***********************************************************/
>> +/* Page cache for storing previous pages as basis for XBRLE compression */
>> +#define CACHE_N_WAY 2 /* 2-way assossiative cache */
> 
> Is there any reason we can't just use a GCache for this?
> 
> http://developer.gnome.org/glib/stable/glib-Caches.html
I'm not familiar with I will check.
Is it 2-way associative cache ?

Orit
> 
> Regards,
> 
> Anthony Liguori

Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

[Orit Wasserman]

On 01/03/2012 09:57 PM, Anthony Liguori wrote:
> On 01/03/2012 09:34 AM, Orit Wasserman wrote:
>> Signed-off-by: Orit Wasserman<owasserm@redhat.com>
>> ---
>>   arch_init.c |   58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>   1 files changed, 58 insertions(+), 0 deletions(-)
>>
>> diff --git a/arch_init.c b/arch_init.c
>> index fdda277..426b34d 100644
>> --- a/arch_init.c
>> +++ b/arch_init.c
>> @@ -139,6 +139,9 @@ typedef struct XBRLEHeader {
>>       uint32_t xh_cksum;
>>   } XBRLEHeader;
>>
>> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen);
>> +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen);
>> +
>>   /***********************************************************/
>>   /* XBRLE page cache implementation */
>>   static CacheItem *cache_item_get(unsigned long pos, int item)
>> @@ -277,6 +280,61 @@ static void cache_insert(unsigned long addr, uint8_t *pdata)
>>       it->it_addr = addr;
>>   }
>>
>> +/* XBRLE (Xor Based Run-Length Encoding) */
>> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen)
>> +{
>> +    int d = 0, ch_run = 0, i;
>> +    uint8_t prev = 0, ch = 0;
>> +
>> +    for (i = 0; i<= slen; i++) {
>> +        if (i != slen) {
>> +            ch = src[i];
>> +        }
>> +
>> +        if (!i || (i != slen&&  ch == prev&&  ch_run<  255)) {
>> +            ch_run++;
>> +        } else {
>> +            if (d+2>  dlen) {
>> +                return -1;
>> +            }
>> +            *dst++ = ch_run;
>> +            *dst++ = prev;
>> +            d += 2;
>> +            ch_run = 1;
>> +        }
>> +
>> +        prev = ch;
>> +    }
>> +    return d;
>> +}
>> +
>> +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen)
>> +{
>> +    int d = 0, s;
>> +
>> +    for (s = 0; s<  slen-1; s += 2) {
>> +        uint8_t ch_run = src[s];
>> +        uint8_t ch = src[s+1];
>> +        while (ch_run--) {
>> +            if (d == dlen) {
>> +                return -1;
>> +            }
>> +            dst[d] = ch;
>> +            d++;
>> +        }
>> +    }
>> +    return d;
>> +}
>> +
>> +static void xor_encode(uint8_t *dst, uint8_t *src1, uint8_t *src2)
>> +{
>> +    int i;
>> +
>> +    for (i = 0; i<  TARGET_PAGE_SIZE; i++) {
>> +        dst[i] = src1[i] ^ src2[i];
>> +    }
>> +}
>> +
> 
> I don't think any of these need to be in arch_init.c.  It would be nicer to make a xbzrle.c file for this stuff.
> 

I will fix it.

> Regards,
> 
> Anthony Liguori
> 
>>   static int is_dup_page(uint8_t *page, uint8_t ch)
>>   {
>>       uint32_t val = ch<<  24 | ch<<  16 | ch<<  8 | ch;
> 
> 

Re: [Qemu-devel] [PATCH v5 1/9] Add cache handling functions

[Stefan Hajnoczi]

On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote:
> +static unsigned long cache_get_cache_pos(ram_addr_t address)
> +{
> +    unsigned long pos;
> +
> +    assert(cache_num_buckets);
> +    pos = (address/TARGET_PAGE_SIZE) & (cache_num_buckets - 1);

Where do we guarantee that cache_num_buckets is a power of 2?

> +static void cache_insert(unsigned long addr, uint8_t *pdata)
> +{
> +    unsigned long pos;
> +    int slot = -1;
> +    CacheBucket *bucket;
> +
> +    pos = cache_get_cache_pos(addr);
> +    assert(page_cache);
> +    bucket = &page_cache[pos];
> +    slot = cache_get_oldest(bucket); /* evict LRU */
> +
> +    /* actual update of entry */
> +    CacheItem *it = cache_item_get(pos, slot);
> +    if (!it->it_data) {
> +        cache_num_items++;
> +    }
> +    g_free(it->it_data);
> +
> +    it->it_data = g_malloc0(TARGET_PAGE_SIZE);
> +    memcpy(it->it_data, pdata, TARGET_PAGE_SIZE);

If we're evicting an entry:
1. Free existing data.
2. Allocate new data.
3. Zero new data.
4. Memcpy pdata into new data.

That does a bunch of extra work.  How about:
1. Memcpy pdata over old data.

So:
if (!it->it_data) {
    cache_num_items++;
    it->it_data = g_malloc(TARGET_PAGE_SIZE);
}
memcpy(it->it_data, pdata, TARGET_PAGE_SIZE);

Re: [Qemu-devel] [PATCH v5 4/9] Add host_from_stream_offset_versioned function

[Stefan Hajnoczi]

On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote:
> +static inline void *host_from_stream_offset_versioned(int version_id,
> +        QEMUFile *f, ram_addr_t offset, int flags)
> +{
> +        void *host;
> +        if (version_id == 3) {
> +                host = qemu_get_ram_ptr(offset);
> +        } else {
> +                host = host_from_stream_offset(f, offset, flags);
> +        }
> +        if (!host) {
> +            fprintf(stderr, "Failed to convert RAM address to host"
> +                    " for offset 0x%lX!\n", offset);
> +            abort();
> +        }

Please use RAM_ADDR_FMT instead of %lX.

Aborting isn't ideal but I guess there is nothing else we can do at this point.

Stefan

Re: [Qemu-devel] [PATCH v5 5/9] Add XBRLE to ram_save_block and ram_save_live

[Stefan Hajnoczi]

On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote:
> +    /* XOR encoding */
> +    xor_buf = (uint8_t *) g_malloc0(TARGET_PAGE_SIZE);

Is this an old version of the code?  I remember pointing out all the
useless zeroing in a previous revision.  If the next line is going to
memcpy or overwrite the entire buffer, please don't zero it first -
especially when the buffer isn't just a small struct.

Stefan

Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

[Avi Kivity]

On 01/03/2012 05:34 PM, Orit Wasserman wrote:
>  
> +/* XBRLE (Xor Based Run-Length Encoding) */
> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen)
> +{
> +    int d = 0, ch_run = 0, i;
> +    uint8_t prev = 0, ch = 0;
> +
> +    for (i = 0; i <= slen; i++) {
> +        if (i != slen) {
> +            ch = src[i];
> +        }
> +
> +        if (!i || (i != slen && ch == prev && ch_run < 255)) {
> +            ch_run++;
> +        } else {
> +            if (d+2 > dlen) {
> +                return -1;
> +            }
> +            *dst++ = ch_run;
> +            *dst++ = prev;
> +            d += 2;
> +            ch_run = 1;
> +        }
> +
> +        prev = ch;
> +    }
> +    return d;
> +}
> +

I think we should specialize this for out case, where we expect runs of
zeros (so no need to encode the repeated byte) and runs of non-repeating
nonzeros.  I propose this encoding:

  page = zrun
       | zrun nzrun
       | zrun nzrun page

  zrun = length

  nzrun = length byte...

  length = uleb128 encoded integer

take for example a xor-encoded page:

  { 1000*0, 1, 2, 3, 4, 3092*0 }

representing a page that had a single 32-bit write in the middle.  The
current encoding would generate

  ff 00 ff 00 ff 00 eb 00 01 01 01 02 01 03 01 04 ff 00 ff 00 ff 00 ff
00 ff 00 ff 00ff 00 ff 00 ff 00 ff 00 ff 00 ff 00 20 00

while the zrle encoding generates

 e8 07 04 01 02 03 04 94 18

(e8 07 = uleb128 encoding for 1000)

-- 
error compiling committee.c: too many arguments to function

Re: [Qemu-devel] [PATCH v5 0/9] XBZRLE delta for live migration of large memory apps

[Avi Kivity]

On 01/03/2012 05:34 PM, Orit Wasserman wrote:
> 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>
>

Looks like the original authorship (From: ) and signoffs were lost in
the actual patches.

-- 
error compiling committee.c: too many arguments to function

Re: [Qemu-devel] [PATCH v5 1/9] Add cache handling functions

[Orit Wasserman]

On 01/04/2012 01:46 PM, Stefan Hajnoczi wrote:
> On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote:
>> +static unsigned long cache_get_cache_pos(ram_addr_t address)
>> +{
>> +    unsigned long pos;
>> +
>> +    assert(cache_num_buckets);
>> +    pos = (address/TARGET_PAGE_SIZE) & (cache_num_buckets - 1);
> 
> Where do we guarantee that cache_num_buckets is a power of 2?

We should do it  to when setting cache size , I will add the check.
> 
>> +static void cache_insert(unsigned long addr, uint8_t *pdata)
>> +{
>> +    unsigned long pos;
>> +    int slot = -1;
>> +    CacheBucket *bucket;
>> +
>> +    pos = cache_get_cache_pos(addr);
>> +    assert(page_cache);
>> +    bucket = &page_cache[pos];
>> +    slot = cache_get_oldest(bucket); /* evict LRU */
>> +
>> +    /* actual update of entry */
>> +    CacheItem *it = cache_item_get(pos, slot);
>> +    if (!it->it_data) {
>> +        cache_num_items++;
>> +    }
>> +    g_free(it->it_data);
>> +
>> +    it->it_data = g_malloc0(TARGET_PAGE_SIZE);
>> +    memcpy(it->it_data, pdata, TARGET_PAGE_SIZE);
> 
> If we're evicting an entry:
> 1. Free existing data.
> 2. Allocate new data.
> 3. Zero new data.
> 4. Memcpy pdata into new data.
> 
> That does a bunch of extra work.  How about:
> 1. Memcpy pdata over old data.

I noticed it too , i will fix it in next version.
> 
> So:
> if (!it->it_data) {
>     cache_num_items++;
>     it->it_data = g_malloc(TARGET_PAGE_SIZE);
> }
> memcpy(it->it_data, pdata, TARGET_PAGE_SIZE);

Re: [Qemu-devel] [PATCH v5 5/9] Add XBRLE to ram_save_block and ram_save_live

[Orit Wasserman]

On 01/04/2012 02:14 PM, Stefan Hajnoczi wrote:
> On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote:
>> +    /* XOR encoding */
>> +    xor_buf = (uint8_t *) g_malloc0(TARGET_PAGE_SIZE);
> 
> Is this an old version of the code?  I remember pointing out all the
> useless zeroing in a previous revision.  If the next line is going to
> memcpy or overwrite the entire buffer, please don't zero it first -
> especially when the buffer isn't just a small struct.

I will fix it 
> 
> Stefan

Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

[Stefan Hajnoczi]

On Wed, Jan 4, 2012 at 12:59 PM, Avi Kivity <avi@redhat.com> wrote:
> On 01/03/2012 05:34 PM, Orit Wasserman wrote:
>>
>> +/* XBRLE (Xor Based Run-Length Encoding) */
>> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen)
>> +{
>> +    int d = 0, ch_run = 0, i;
>> +    uint8_t prev = 0, ch = 0;
>> +
>> +    for (i = 0; i <= slen; i++) {
>> +        if (i != slen) {
>> +            ch = src[i];
>> +        }
>> +
>> +        if (!i || (i != slen && ch == prev && ch_run < 255)) {
>> +            ch_run++;
>> +        } else {
>> +            if (d+2 > dlen) {
>> +                return -1;
>> +            }
>> +            *dst++ = ch_run;
>> +            *dst++ = prev;
>> +            d += 2;
>> +            ch_run = 1;
>> +        }
>> +
>> +        prev = ch;
>> +    }
>> +    return d;
>> +}
>> +
>
> I think we should specialize this for out case, where we expect runs of
> zeros (so no need to encode the repeated byte) and runs of non-repeating
> nonzeros.  I propose this encoding:
>
>  page = zrun
>       | zrun nzrun
>       | zrun nzrun page
>
>  zrun = length
>
>  nzrun = length byte...
>
>  length = uleb128 encoded integer
>
> take for example a xor-encoded page:
>
>  { 1000*0, 1, 2, 3, 4, 3092*0 }
>
> representing a page that had a single 32-bit write in the middle.  The
> current encoding would generate
>
>  ff 00 ff 00 ff 00 eb 00 01 01 01 02 01 03 01 04 ff 00 ff 00 ff 00 ff
> 00 ff 00 ff 00ff 00 ff 00 ff 00 ff 00 ff 00 ff 00 20 00
>
> while the zrle encoding generates
>
>  e8 07 04 01 02 03 04 94 18
>
> (e8 07 = uleb128 encoding for 1000)

Had to look up the Unsigned Little-Endian Base 128 encoding, but it's
a nice idea and simple to implement (though we probably want to
constrain ULEB128 to max 32-bit or 64-bit in practice; we don't want
arbitrarily long integers).

http://en.wikipedia.org/wiki/LEB128

Stefan

Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

[Avi Kivity]

On 01/04/2012 03:35 PM, Stefan Hajnoczi wrote:
> > I think we should specialize this for out case, where we expect runs of
> > zeros (so no need to encode the repeated byte) and runs of non-repeating
> > nonzeros.  I propose this encoding:
> >
> >  page = zrun
> >       | zrun nzrun
> >       | zrun nzrun page
> >
> >  zrun = length
> >
> >  nzrun = length byte...
> >
> >  length = uleb128 encoded integer
> >
> > take for example a xor-encoded page:
> >
> >  { 1000*0, 1, 2, 3, 4, 3092*0 }
> >
> > representing a page that had a single 32-bit write in the middle.  The
> > current encoding would generate
> >
> >  ff 00 ff 00 ff 00 eb 00 01 01 01 02 01 03 01 04 ff 00 ff 00 ff 00 ff
> > 00 ff 00 ff 00ff 00 ff 00 ff 00 ff 00 ff 00 ff 00 20 00
> >
> > while the zrle encoding generates
> >
> >  e8 07 04 01 02 03 04 94 18
> >
> > (e8 07 = uleb128 encoding for 1000)
>
> Had to look up the Unsigned Little-Endian Base 128 encoding, but it's
> a nice idea and simple to implement (though we probably want to
> constrain ULEB128 to max 32-bit or 64-bit in practice; we don't want
> arbitrarily long integers).
>
> http://en.wikipedia.org/wiki/LEB128
>

Sorry, should have provided the URL.  And yes, for this use we're
limited to TARGET_PAGE_BITS, so having 13-bit encoders/decoders would
suffice:

   int uleb128_encode_small(uint8_t *out, uint32_t n)
   {
       if (n < 0x80) {
           *out++ = n;
           return 1;
       } else {
           *out++ = (n & 0x7f) | 0x80;
           *out++ = n >> 7;
       }
   }

   int uleb128_decode_small(const uint128 *in, uint32_t *n)
   {
       if (!(*in & 0x80)) {
           *n = *in++;
           return 1;
       } else {
           *n = *in++ & 0x7f;
           *n |= *in++ << 7;
           return 2;
       }
   }

-- 
error compiling committee.c: too many arguments to function

Re: [Qemu-devel] [PATCH v5 0/9] XBZRLE delta for live migration of large memory apps

[Orit Wasserman]

On 01/04/2012 03:02 PM, Avi Kivity wrote:
> On 01/03/2012 05:34 PM, Orit Wasserman wrote:
>> 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>
>>
> 
> Looks like the original authorship (From: ) and signoffs were lost in
> the actual patches.
> 
I will fix it in next patch.

Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

[Paolo Bonzini]

On 01/04/2012 10:31 AM, Orit Wasserman wrote:
>> >  I don't think any of these need to be in arch_init.c.  It would be nicer to make a xbzrle.c file for this stuff.
>> >
> I will fix it.
>

Or just move everything migration-related from arch_init.c to saveram.c.

Paolo

Re: [Qemu-devel] [PATCH v5 4/9] Add host_from_stream_offset_versioned function

[Michael Roth]

On 01/04/2012 06:00 AM, Stefan Hajnoczi wrote:
> On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman<owasserm@redhat.com>  wrote:
>> +static inline void *host_from_stream_offset_versioned(int version_id,
>> +        QEMUFile *f, ram_addr_t offset, int flags)
>> +{
>> +        void *host;
>> +        if (version_id == 3) {
>> +                host = qemu_get_ram_ptr(offset);
>> +        } else {
>> +                host = host_from_stream_offset(f, offset, flags);
>> +        }
>> +        if (!host) {
>> +            fprintf(stderr, "Failed to convert RAM address to host"
>> +                    " for offset 0x%lX!\n", offset);
>> +            abort();
>> +        }
>
> Please use RAM_ADDR_FMT instead of %lX.
>
> Aborting isn't ideal but I guess there is nothing else we can do at this point.
>

Currently we we return -EINVAL to qemu_loadvm_state() when !host, which 
prints potentially useful warnings and exits gracefully for migration, 
and for savevm we print the warnings and fire up the main_loop with 
vcpus paused...

Not sure what the rationale is for the latter, but it may have some 
utility (debugging maybe?).

In any case, since the error paths are covered in some fashion I don't 
think we should resort to aborting here, maybe just print the warnings 
and check for NULL return in the callers as before.

> Stefan
>

Re: [Qemu-devel] [PATCH v5 6/9] Add xbrle parameters to MigrationState

[Michael Roth]

On 01/03/2012 09:34 AM, Orit Wasserman wrote:
> Signed-off-by: Orit Wasserman<owasserm@redhat.com>
> ---
>   block-migration.c |    4 +++-
>   hw/hw.h           |    4 +++-
>   migration.c       |   15 +++++++++++++--
>   migration.h       |    3 +++
>   savevm.c          |   11 +++++++----
>   sysemu.h          |    4 +++-
>   6 files changed, 32 insertions(+), 9 deletions(-)
>
> diff --git a/block-migration.c b/block-migration.c
> index 2b7edbc..60f2d62 100644
> --- a/block-migration.c
> +++ b/block-migration.c
> @@ -706,7 +706,9 @@ static int block_load(QEMUFile *f, void *opaque, int version_id)
>       return 0;
>   }
>
> -static void block_set_params(int blk_enable, int shared_base, void *opaque)
> +static void block_set_params(int blk_enable, int shared_base,
> +                             int use_xbrle, int64_t xbrle_cache_size,
> +                             void *opaque)
>   {
>       block_mig_state.blk_enable = blk_enable;
>       block_mig_state.shared_base = shared_base;
> diff --git a/hw/hw.h b/hw/hw.h
> index efa04d1..ab0b92c 100644
> --- a/hw/hw.h
> +++ b/hw/hw.h
> @@ -245,7 +245,9 @@ static inline void qemu_get_sbe64s(QEMUFile *f, int64_t *pv)
>   int64_t qemu_ftell(QEMUFile *f);
>   int64_t qemu_fseek(QEMUFile *f, int64_t pos, int whence);
>
> -typedef void SaveSetParamsHandler(int blk_enable, int shared, void * opaque);
> +typedef void SaveSetParamsHandler(int blk_enable, int shared,
> +                                  int use_xbrle, int64_t xbrle_cache_size,
> +                                  void *opaque);

This is probably gonna keep changing...xbrle, post-copy, alternative 
migration protocols...

Maybe you could just pull in 15/21 from Isaku's postcopy series and add 
the fields there?

>   typedef void SaveStateHandler(QEMUFile *f, void *opaque);
>   typedef int SaveLiveStateHandler(Monitor *mon, QEMUFile *f, int stage,
>                                    void *opaque);
> diff --git a/migration.c b/migration.c
> index 412fdfe..ed47958 100644
> --- a/migration.c
> +++ b/migration.c
> @@ -41,6 +41,11 @@ enum {
>
>   #define MAX_THROTTLE  (32<<  20)      /* Migration speed throttling */
>
> +/* Migration XBRLE cache size */
> +#define DEFAULT_MIGRATE_CACHE_SIZE (64 * 1024 * 1024)
> +
> +static int64_t migrate_cache_size = DEFAULT_MIGRATE_CACHE_SIZE;
> +
>   static NotifierList migration_state_notifiers =
>       NOTIFIER_LIST_INITIALIZER(migration_state_notifiers);
>
> @@ -365,7 +370,8 @@ void migrate_fd_connect(MigrationState *s)
>                                         migrate_fd_close);
>
>       DPRINTF("beginning savevm\n");
> -    ret = qemu_savevm_state_begin(s->mon, s->file, s->blk, s->shared);
> +    ret = qemu_savevm_state_begin(s->mon, s->file, s->blk, s->shared,
> +                                  s->use_xbrle, s->xbrle_cache_size);
>       if (ret<  0) {
>           DPRINTF("failed, %d\n", ret);
>           migrate_fd_error(s);
> @@ -375,6 +381,8 @@ void migrate_fd_connect(MigrationState *s)
>   }
>
>   static MigrationState *migrate_init(Monitor *mon, int detach, int blk, int inc)
> +static MigrationState *migrate_init(Monitor *mon, int detach, int blk, int inc,
> +                                    int use_xbrle, int64_t xbrle_cache_size)
>   {
>       MigrationState *s = migrate_get_current();
>       int64_t bandwidth_limit = s->bandwidth_limit;
> @@ -383,6 +391,8 @@ static MigrationState *migrate_init(Monitor *mon, int detach, int blk, int inc)
>       s->bandwidth_limit = bandwidth_limit;
>       s->blk = blk;
>       s->shared = inc;
> +    s->use_xbrle = use_xbrle;
> +    s->xbrle_cache_size = xbrle_cache_size;
>
>       /* s->mon is used for two things:
>          - pass fd in fd migration
> @@ -418,6 +428,7 @@ int do_migrate(Monitor *mon, const QDict *qdict, QObject **ret_data)
>       int detach = qdict_get_try_bool(qdict, "detach", 0);
>       int blk = qdict_get_try_bool(qdict, "blk", 0);
>       int inc = qdict_get_try_bool(qdict, "inc", 0);
> +    int use_xbrle = qdict_get_try_bool(qdict, "xbrle", 0);
>       const char *uri = qdict_get_str(qdict, "uri");
>       int ret;
>
> @@ -436,7 +447,7 @@ int do_migrate(Monitor *mon, const QDict *qdict, QObject **ret_data)
>           return -1;
>       }
>
> -    s = migrate_init(mon, detach, blk, inc);
> +    s = migrate_init(mon, detach, blk, inc, use_xbrle, migrate_cache_size);
>
>       if (strstart(uri, "tcp:",&p)) {
>           ret = tcp_start_outgoing_migration(s, p);
> diff --git a/migration.h b/migration.h
> index 372b066..592af6a 100644
> --- a/migration.h
> +++ b/migration.h
> @@ -34,6 +34,9 @@ struct MigrationState
>       void *opaque;
>       int blk;
>       int shared;
> +    int use_xbrle;
> +    int64_t xbrle_cache_size;
> +
>   };
>
>   void process_incoming_migration(QEMUFile *f);
> diff --git a/savevm.c b/savevm.c
> index f153c25..3650f56 100644
> --- a/savevm.c
> +++ b/savevm.c
> @@ -1277,7 +1277,8 @@ int register_savevm(DeviceState *dev,
>                       void *opaque)
>   {
>       return register_savevm_live(dev, idstr, instance_id, version_id,
> -                                NULL, NULL, save_state, load_state, opaque);
> +                                arch_set_params, NULL, save_state,
> +                                load_state, opaque);
>   }
>
>   void unregister_savevm(DeviceState *dev, const char *idstr, void *opaque)
> @@ -1554,7 +1555,8 @@ bool qemu_savevm_state_blocked(Monitor *mon)
>   }
>
>   int qemu_savevm_state_begin(Monitor *mon, QEMUFile *f, int blk_enable,
> -                            int shared)
> +                            int shared, int use_xbrle,
> +                            int64_t xbrle_cache_size)
>   {
>       SaveStateEntry *se;
>       int ret;
> @@ -1563,7 +1565,8 @@ int qemu_savevm_state_begin(Monitor *mon, QEMUFile *f, int blk_enable,
>           if(se->set_params == NULL) {
>               continue;
>   	}
> -	se->set_params(blk_enable, shared, se->opaque);
> +        se->set_params(blk_enable, shared, use_xbrle, xbrle_cache_size,
> +                       se->opaque);
>       }
>
>       qemu_put_be32(f, QEMU_VM_FILE_MAGIC);
> @@ -1707,7 +1710,7 @@ static int qemu_savevm_state(Monitor *mon, QEMUFile *f)
>           goto out;
>       }
>
> -    ret = qemu_savevm_state_begin(mon, f, 0, 0);
> +    ret = qemu_savevm_state_begin(mon, f, 0, 0, 0, 0);
>       if (ret<  0)
>           goto out;
>
> diff --git a/sysemu.h b/sysemu.h
> index 3806901..78e1074 100644
> --- a/sysemu.h
> +++ b/sysemu.h
> @@ -67,7 +67,8 @@ void qemu_announce_self(void);
>
>   bool qemu_savevm_state_blocked(Monitor *mon);
>   int qemu_savevm_state_begin(Monitor *mon, QEMUFile *f, int blk_enable,
> -                            int shared);
> +                            int shared, int use_xbrle,
> +                            int64_t xbrle_cache_size);
>   int qemu_savevm_state_iterate(Monitor *mon, QEMUFile *f);
>   int qemu_savevm_state_complete(Monitor *mon, QEMUFile *f);
>   void qemu_savevm_state_cancel(Monitor *mon, QEMUFile *f);
> @@ -174,4 +175,5 @@ void register_devices(void);
>   void add_boot_device_path(int32_t bootindex, DeviceState *dev,
>                             const char *suffix);
>   char *get_boot_devices_list(uint32_t *size);
> +
>   #endif

Re: [Qemu-devel] [PATCH v5 1/9] Add cache handling functions

[Michael Roth]

On 01/04/2012 03:29 AM, Orit Wasserman wrote:
> On 01/03/2012 09:54 PM, Anthony Liguori wrote:
>> On 01/03/2012 09:34 AM, Orit Wasserman wrote:
>>> Add page caching mechanism.
>>> The pages are stored in the cache ordered by their address.
>>>
>>> Signed-off-by: Orit Wasserman<owasserm@redhat.com>
>>> ---
>>>    arch_init.c |  183 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>    1 files changed, 183 insertions(+), 0 deletions(-)
>>>
>>> diff --git a/arch_init.c b/arch_init.c
>>> index d4c92b0..fdda277 100644
>>> --- a/arch_init.c
>>> +++ b/arch_init.c
>>> @@ -28,6 +28,7 @@
>>>    #include<sys/types.h>
>>>    #include<sys/mman.h>
>>>    #endif
>>> +#include<assert.h>
>>>    #include "config.h"
>>>    #include "monitor.h"
>>>    #include "sysemu.h"
>>> @@ -42,6 +43,14 @@
>>>    #include "gdbstub.h"
>>>    #include "hw/smbios.h"
>>>
>>> +#ifdef DEBUG_ARCH_INIT
>>> +#define DPRINTF(fmt, ...) \
>>> +    do { fprintf(stdout, "arch_init: " fmt, ## __VA_ARGS__); } while (0)
>>> +#else
>>> +#define DPRINTF(fmt, ...) \
>>> +    do { } while (0)
>>> +#endif
>>> +
>>>    #ifdef TARGET_SPARC
>>>    int graphic_width = 1024;
>>>    int graphic_height = 768;
>>> @@ -94,6 +103,180 @@ const uint32_t arch_type = QEMU_ARCH;
>>>    #define RAM_SAVE_FLAG_EOS      0x10
>>>    #define RAM_SAVE_FLAG_CONTINUE 0x20
>>>
>>> +/***********************************************************/
>>> +/* Page cache for storing previous pages as basis for XBRLE compression */
>>> +#define CACHE_N_WAY 2 /* 2-way assossiative cache */
>>
>> Is there any reason we can't just use a GCache for this?
>>
>> http://developer.gnome.org/glib/stable/glib-Caches.html
> I'm not familiar with I will check.
> Is it 2-way associative cache ?

Not quite...it's a very loose wrapper around GHashTable, which appears 
to be fully associative in nature. It also doesn't seem to allow you to 
do a lookup without destroying the table entry =\ (unless you do 
something hacky like an extra insert beforehand to jack up the 
refcount). If you go this route you're probably better off looking at 
GHashTable directly.

>
> Orit
>>
>> Regards,
>>
>> Anthony Liguori
>
>

Re: [Qemu-devel] [PATCH v5 9/9] Add XBRLE statistics information

[Michael Roth]

On 01/03/2012 09:34 AM, Orit Wasserman wrote:
> Signed-off-by: Orit Wasserman<owasserm@redhat.com>
> ---
>   arch_init.c |   67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>   migration.c |   11 +++++++++
>   migration.h |    9 ++++++++
>   3 files changed, 87 insertions(+), 0 deletions(-)
>
> diff --git a/arch_init.c b/arch_init.c
> index 6b839a1..037d8ba 100644
> --- a/arch_init.c
> +++ b/arch_init.c
> @@ -149,6 +149,65 @@ void arch_set_params(int blk_enable, int shared_base, int use_xbrle,
>   }
>
>   /***********************************************************/
> +/* accounting */
> +typedef struct AccountingInfo {
> +    uint64_t dup_pages;
> +    uint64_t norm_pages;
> +    uint64_t xbrle_bytes;
> +    uint64_t xbrle_pages;
> +    uint64_t xbrle_overflow;
> +    uint64_t xbrle_cache_miss;
> +    uint64_t iterations;
> +} AccountingInfo;
> +
> +static AccountingInfo acct_info;
> +
> +static void acct_clear(void)
> +{
> +    bzero(&acct_info, sizeof(acct_info));
> +}
> +
> +uint64_t dup_mig_bytes_transferred(void)
> +{
> +    return acct_info.dup_pages;

* TARGET_PAGE_SIZE ?

> +}
> +
> +uint64_t dup_mig_pages_transferred(void)
> +{
> +    return acct_info.dup_pages;
> +}
> +
> +uint64_t norm_mig_bytes_transferred(void)
> +{
> +    return acct_info.norm_pages * TARGET_PAGE_SIZE;
> +}
> +
> +uint64_t norm_mig_pages_transferred(void)
> +{
> +    return acct_info.norm_pages;
> +}
> +
> +uint64_t xbrle_mig_bytes_transferred(void)
> +{
> +    return acct_info.xbrle_bytes;
> +}
> +
> +uint64_t xbrle_mig_pages_transferred(void)
> +{
> +    return acct_info.xbrle_pages;
> +}
> +
> +uint64_t xbrle_mig_pages_overflow(void)
> +{
> +    return acct_info.xbrle_overflow;
> +}
> +
> +uint64_t xbrle_mig_pages_cache_miss(void)
> +{
> +    return acct_info.xbrle_cache_miss;
> +}
> +
> +/***********************************************************/
>   /* XBRLE (Xor Based Run-Length Encoding) */
>   typedef struct XBRLEHeader {
>       uint8_t xh_flags;
> @@ -376,6 +435,7 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
>       /* get location */
>       slot = cache_is_cached(current_addr);
>       if (slot == -1) {
> +        acct_info.xbrle_cache_miss++;
>           goto done;
>       }
>       cache_location = cache_get_cache_pos(current_addr);
> @@ -394,6 +454,7 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
>
>       if (encoded_len<  0) {
>           DPRINTF("XBRLE encoding oeverflow - sending uncompressed\n");

*overflow

> +        acct_info.xbrle_overflow++;
>           goto done;
>       }
>
> @@ -404,7 +465,9 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
>       save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_XBRLE);
>       qemu_put_buffer(f, (uint8_t *)&hdr, sizeof(hdr));
>       qemu_put_buffer(f, xbrle_buf, encoded_len);
> +    acct_info.xbrle_pages++;
>       bytes_sent = encoded_len + sizeof(hdr);
> +    acct_info.xbrle_bytes += bytes_sent;
>
>   done:
>       g_free(xor_buf);
> @@ -457,6 +520,7 @@ static int ram_save_block(QEMUFile *f, int stage)
>                   save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_COMPRESS);
>                   qemu_put_byte(f, *p);
>                   bytes_sent = 1;
> +                acct_info.dup_pages++;
>               } else if (stage == 2&&  arch_mig_state.use_xbrle) {
>                   bytes_sent = save_xbrle_page(f, p, current_addr, block,
>                       offset, cont);
> @@ -465,6 +529,7 @@ static int ram_save_block(QEMUFile *f, int stage)
>                   save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_PAGE);
>                    qemu_put_buffer(f, p, TARGET_PAGE_SIZE);
>                    bytes_sent = TARGET_PAGE_SIZE;
> +                 acct_info.norm_pages++;
>               }
>               if (arch_mig_state.use_xbrle) {
>                   cache_insert(current_addr, p);
> @@ -596,6 +661,7 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
>
>           if (arch_mig_state.use_xbrle) {
>               cache_init(arch_mig_state.xbrle_cache_size);
> +            acct_clear();
>           }
>
>           /* Make sure all dirty bits are set */
> @@ -629,6 +695,7 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
>
>           bytes_sent = ram_save_block(f, stage);
>           bytes_transferred += bytes_sent;
> +        acct_info.iterations++;
>           if (bytes_sent == 0) { /* no more blocks */
>               break;
>           }
> diff --git a/migration.c b/migration.c
> index 3d88cdd..383ceef 100644
> --- a/migration.c
> +++ b/migration.c
> @@ -141,6 +141,17 @@ MigrationInfo *qmp_query_migrate(Error **errp)
>               info->disk->remaining = blk_mig_bytes_remaining();
>               info->disk->total = blk_mig_bytes_total();
>           }
> +
> +       if (s->use_xbrle) {
> +            info->has_xbrle = true;
> +            info->cache = g_malloc0(sizeof(*info->cache));
> +            info->cache->dup_pages = dup_mig_pages_transferred();
> +            info->cache->norm_pages = norm_mig_pages_transferred();
> +            info->cache->xbrle_bytes  = xbrle_mig_bytes_transferred();
> +            info->cache->xbrle_pages  = xbrle_mig_pages_transferred();
> +            info->cache->xbrle_overflow = xbrle_mig_pages_overflow();
> +            info->cache->xbrle_cache_miss = xbrle_mig_pages_cache_miss();
> +        }

Hmm, I'm not seeing where you added the has_xbrle/cache fields to 
MigrationInfo? Are you missing your qapi-schema.json diff?

Also, I think the dup/norm stats are generally useful and don't appear 
to be dependent on xbrle having been used, so maybe just the xbrle_* 
fields should be filtered based on s->use_xbrle? And hang 
dup_pages/norm_pages off of info directly?

>           break;
>       case MIG_STATE_COMPLETED:
>           info->has_status = true;
> diff --git a/migration.h b/migration.h
> index 6de09c8..dd06ef6 100644
> --- a/migration.h
> +++ b/migration.h
> @@ -81,6 +81,15 @@ uint64_t ram_bytes_remaining(void);
>   uint64_t ram_bytes_transferred(void);
>   uint64_t ram_bytes_total(void);
>
> +uint64_t dup_mig_bytes_transferred(void);
> +uint64_t dup_mig_pages_transferred(void);
> +uint64_t norm_mig_bytes_transferred(void);
> +uint64_t norm_mig_pages_transferred(void);
> +uint64_t xbrle_mig_bytes_transferred(void);
> +uint64_t xbrle_mig_pages_transferred(void);
> +uint64_t xbrle_mig_pages_overflow(void);
> +uint64_t xbrle_mig_pages_cache_miss(void);
> +
>   int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque);
>   int ram_load(QEMUFile *f, void *opaque, int version_id);
>

Re: [Qemu-devel] [PATCH v5 9/9] Add XBRLE statistics information

[Blue Swirl]

On Tue, Jan 3, 2012 at 15:34, Orit Wasserman <owasserm@redhat.com> wrote:
>
> Signed-off-by: Orit Wasserman <owasserm@redhat.com>
> ---
>  arch_init.c |   67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  migration.c |   11 +++++++++
>  migration.h |    9 ++++++++
>  3 files changed, 87 insertions(+), 0 deletions(-)
>
> diff --git a/arch_init.c b/arch_init.c
> index 6b839a1..037d8ba 100644
> --- a/arch_init.c
> +++ b/arch_init.c
> @@ -149,6 +149,65 @@ void arch_set_params(int blk_enable, int shared_base, int use_xbrle,
>  }
>
>  /***********************************************************/
> +/* accounting */
> +typedef struct AccountingInfo {
> +    uint64_t dup_pages;
> +    uint64_t norm_pages;
> +    uint64_t xbrle_bytes;
> +    uint64_t xbrle_pages;
> +    uint64_t xbrle_overflow;
> +    uint64_t xbrle_cache_miss;
> +    uint64_t iterations;
> +} AccountingInfo;
> +
> +static AccountingInfo acct_info;
> +
> +static void acct_clear(void)
> +{
> +    bzero(&acct_info, sizeof(acct_info));

Please use memset(), bzero() is deprecated.

> +}
> +
> +uint64_t dup_mig_bytes_transferred(void)
> +{
> +    return acct_info.dup_pages;
> +}
> +
> +uint64_t dup_mig_pages_transferred(void)
> +{
> +    return acct_info.dup_pages;
> +}
> +
> +uint64_t norm_mig_bytes_transferred(void)
> +{
> +    return acct_info.norm_pages * TARGET_PAGE_SIZE;
> +}
> +
> +uint64_t norm_mig_pages_transferred(void)
> +{
> +    return acct_info.norm_pages;
> +}
> +
> +uint64_t xbrle_mig_bytes_transferred(void)
> +{
> +    return acct_info.xbrle_bytes;
> +}
> +
> +uint64_t xbrle_mig_pages_transferred(void)
> +{
> +    return acct_info.xbrle_pages;
> +}
> +
> +uint64_t xbrle_mig_pages_overflow(void)
> +{
> +    return acct_info.xbrle_overflow;
> +}
> +
> +uint64_t xbrle_mig_pages_cache_miss(void)
> +{
> +    return acct_info.xbrle_cache_miss;
> +}
> +
> +/***********************************************************/
>  /* XBRLE (Xor Based Run-Length Encoding) */
>  typedef struct XBRLEHeader {
>     uint8_t xh_flags;
> @@ -376,6 +435,7 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
>     /* get location */
>     slot = cache_is_cached(current_addr);
>     if (slot == -1) {
> +        acct_info.xbrle_cache_miss++;
>         goto done;
>     }
>     cache_location = cache_get_cache_pos(current_addr);
> @@ -394,6 +454,7 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
>
>     if (encoded_len < 0) {
>         DPRINTF("XBRLE encoding oeverflow - sending uncompressed\n");
> +        acct_info.xbrle_overflow++;
>         goto done;
>     }
>
> @@ -404,7 +465,9 @@ static int save_xbrle_page(QEMUFile *f, uint8_t *current_data,
>     save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_XBRLE);
>     qemu_put_buffer(f, (uint8_t *) &hdr, sizeof(hdr));
>     qemu_put_buffer(f, xbrle_buf, encoded_len);
> +    acct_info.xbrle_pages++;
>     bytes_sent = encoded_len + sizeof(hdr);
> +    acct_info.xbrle_bytes += bytes_sent;
>
>  done:
>     g_free(xor_buf);
> @@ -457,6 +520,7 @@ static int ram_save_block(QEMUFile *f, int stage)
>                 save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_COMPRESS);
>                 qemu_put_byte(f, *p);
>                 bytes_sent = 1;
> +                acct_info.dup_pages++;
>             } else if (stage == 2 && arch_mig_state.use_xbrle) {
>                 bytes_sent = save_xbrle_page(f, p, current_addr, block,
>                     offset, cont);
> @@ -465,6 +529,7 @@ static int ram_save_block(QEMUFile *f, int stage)
>                 save_block_hdr(f, block, offset, cont, RAM_SAVE_FLAG_PAGE);
>                  qemu_put_buffer(f, p, TARGET_PAGE_SIZE);
>                  bytes_sent = TARGET_PAGE_SIZE;
> +                 acct_info.norm_pages++;
>             }
>             if (arch_mig_state.use_xbrle) {
>                 cache_insert(current_addr, p);
> @@ -596,6 +661,7 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
>
>         if (arch_mig_state.use_xbrle) {
>             cache_init(arch_mig_state.xbrle_cache_size);
> +            acct_clear();
>         }
>
>         /* Make sure all dirty bits are set */
> @@ -629,6 +695,7 @@ int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque)
>
>         bytes_sent = ram_save_block(f, stage);
>         bytes_transferred += bytes_sent;
> +        acct_info.iterations++;
>         if (bytes_sent == 0) { /* no more blocks */
>             break;
>         }
> diff --git a/migration.c b/migration.c
> index 3d88cdd..383ceef 100644
> --- a/migration.c
> +++ b/migration.c
> @@ -141,6 +141,17 @@ MigrationInfo *qmp_query_migrate(Error **errp)
>             info->disk->remaining = blk_mig_bytes_remaining();
>             info->disk->total = blk_mig_bytes_total();
>         }
> +
> +       if (s->use_xbrle) {
> +            info->has_xbrle = true;
> +            info->cache = g_malloc0(sizeof(*info->cache));
> +            info->cache->dup_pages = dup_mig_pages_transferred();
> +            info->cache->norm_pages = norm_mig_pages_transferred();
> +            info->cache->xbrle_bytes  = xbrle_mig_bytes_transferred();
> +            info->cache->xbrle_pages  = xbrle_mig_pages_transferred();
> +            info->cache->xbrle_overflow = xbrle_mig_pages_overflow();
> +            info->cache->xbrle_cache_miss = xbrle_mig_pages_cache_miss();
> +        }
>         break;
>     case MIG_STATE_COMPLETED:
>         info->has_status = true;
> diff --git a/migration.h b/migration.h
> index 6de09c8..dd06ef6 100644
> --- a/migration.h
> +++ b/migration.h
> @@ -81,6 +81,15 @@ uint64_t ram_bytes_remaining(void);
>  uint64_t ram_bytes_transferred(void);
>  uint64_t ram_bytes_total(void);
>
> +uint64_t dup_mig_bytes_transferred(void);
> +uint64_t dup_mig_pages_transferred(void);
> +uint64_t norm_mig_bytes_transferred(void);
> +uint64_t norm_mig_pages_transferred(void);
> +uint64_t xbrle_mig_bytes_transferred(void);
> +uint64_t xbrle_mig_pages_transferred(void);
> +uint64_t xbrle_mig_pages_overflow(void);
> +uint64_t xbrle_mig_pages_cache_miss(void);
> +
>  int ram_save_live(Monitor *mon, QEMUFile *f, int stage, void *opaque);
>  int ram_load(QEMUFile *f, void *opaque, int version_id);
>
> --
> 1.7.6.5
>

[Qemu-devel] [PATCH v5 1/9] Add cache handling functions

[Orit Wasserman]

Add page caching mechanism.
The pages are stored in the cache ordered by their address.

Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 arch_init.c |  183 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 183 insertions(+), 0 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index d4c92b0..fdda277 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -28,6 +28,7 @@
 #include <sys/types.h>
 #include <sys/mman.h>
 #endif
+#include <assert.h>
 #include "config.h"
 #include "monitor.h"
 #include "sysemu.h"
@@ -42,6 +43,14 @@
 #include "gdbstub.h"
 #include "hw/smbios.h"
 
+#ifdef DEBUG_ARCH_INIT
+#define DPRINTF(fmt, ...) \
+    do { fprintf(stdout, "arch_init: " fmt, ## __VA_ARGS__); } while (0)
+#else
+#define DPRINTF(fmt, ...) \
+    do { } while (0)
+#endif
+
 #ifdef TARGET_SPARC
 int graphic_width = 1024;
 int graphic_height = 768;
@@ -94,6 +103,180 @@ const uint32_t arch_type = QEMU_ARCH;
 #define RAM_SAVE_FLAG_EOS      0x10
 #define RAM_SAVE_FLAG_CONTINUE 0x20
 
+/***********************************************************/
+/* Page cache for storing previous pages as basis for XBRLE compression */
+#define CACHE_N_WAY 2 /* 2-way assossiative cache */
+
+typedef struct CacheItem {
+    ram_addr_t it_addr;
+    unsigned long it_age;
+    uint8_t *it_data;
+} CacheItem;
+
+typedef struct CacheBucket {
+    CacheItem bkt_item[CACHE_N_WAY];
+} CacheBucket;
+
+static CacheBucket *page_cache;
+static int64_t cache_num_buckets;
+static uint64_t cache_max_item_age;
+static int64_t cache_num_items;
+
+static void cache_init(ssize_t num_buckets);
+static void cache_fini(void);
+static int cache_is_cached(ram_addr_t addr);
+static int cache_get_oldest(CacheBucket *buck);
+static int cache_get_newest(CacheBucket *buck, ram_addr_t addr);
+static void cache_insert(ram_addr_t id, uint8_t *pdata);
+static unsigned long cache_get_cache_pos(ram_addr_t address);
+static CacheItem *cache_item_get(unsigned long pos, int item);
+
+/***********************************************************/
+/* XBRLE (Xor Based Run-Length Encoding) */
+typedef struct XBRLEHeader {
+    uint8_t xh_flags;
+    uint16_t xh_len;
+    uint32_t xh_cksum;
+} XBRLEHeader;
+
+/***********************************************************/
+/* XBRLE page cache implementation */
+static CacheItem *cache_item_get(unsigned long pos, int item)
+{
+    assert(page_cache);
+    return &page_cache[pos].bkt_item[item];
+}
+
+static void cache_init(int64_t num_bytes)
+{
+    int i;
+
+    cache_num_items = 0;
+    cache_max_item_age = 0;
+    cache_num_buckets = num_bytes / (TARGET_PAGE_SIZE * CACHE_N_WAY);
+    assert(cache_num_buckets);
+    DPRINTF("Setting cache buckets to %lu\n", cache_num_buckets);
+
+    assert(!page_cache);
+    page_cache = (CacheBucket *)g_malloc0((cache_num_buckets) *
+            sizeof(CacheBucket));
+
+    for (i = 0; i < cache_num_buckets; i++) {
+        int j;
+        for (j = 0; j < CACHE_N_WAY; j++) {
+            CacheItem *it = cache_item_get(i, j);
+            it->it_data = NULL;
+            it->it_age = 0;
+            it->it_addr = -1;
+        }
+    }
+}
+
+static void cache_fini(void)
+{
+    int i;
+
+    assert(page_cache);
+
+    for (i = 0; i < cache_num_buckets; i++) {
+        int j;
+        for (j = 0; j < CACHE_N_WAY; j++) {
+            CacheItem *it = cache_item_get(i, j);
+            g_free(it->it_data);
+            it->it_data = 0;
+        }
+    }
+
+    g_free(page_cache);
+    page_cache = NULL;
+}
+
+static unsigned long cache_get_cache_pos(ram_addr_t address)
+{
+    unsigned long pos;
+
+    assert(cache_num_buckets);
+    pos = (address/TARGET_PAGE_SIZE) & (cache_num_buckets - 1);
+    return pos;
+}
+
+static int cache_get_newest(CacheBucket *buck, ram_addr_t addr)
+{
+    unsigned long big = 0;
+    int big_pos = -1;
+    int j;
+
+    assert(page_cache);
+
+    for (j = 0; j < CACHE_N_WAY; j++) {
+        CacheItem *it = &buck->bkt_item[j];
+
+        if (it->it_addr != addr) {
+            continue;
+        }
+
+        if (!j || it->it_age > big) {
+            big = it->it_age;
+            big_pos = j;
+        }
+    }
+
+    return big_pos;
+}
+
+static int cache_get_oldest(CacheBucket *buck)
+{
+    unsigned long small = 0;
+    int small_pos = -1;
+    int j;
+
+    assert(page_cache);
+
+    for (j = 0; j < CACHE_N_WAY; j++) {
+        CacheItem *it = &buck->bkt_item[j];
+
+        if (!j || it->it_age <  small) {
+            small = it->it_age;
+            small_pos = j;
+        }
+    }
+
+    return small_pos;
+}
+
+static int cache_is_cached(ram_addr_t addr)
+{
+    unsigned long pos = cache_get_cache_pos(addr);
+
+    assert(page_cache);
+    CacheBucket *bucket = &page_cache[pos];
+    return cache_get_newest(bucket, addr);
+}
+
+static void cache_insert(unsigned long addr, uint8_t *pdata)
+{
+    unsigned long pos;
+    int slot = -1;
+    CacheBucket *bucket;
+
+    pos = cache_get_cache_pos(addr);
+    assert(page_cache);
+    bucket = &page_cache[pos];
+    slot = cache_get_oldest(bucket); /* evict LRU */
+
+    /* actual update of entry */
+    CacheItem *it = cache_item_get(pos, slot);
+    if (!it->it_data) {
+        cache_num_items++;
+    }
+    g_free(it->it_data);
+
+    it->it_data = g_malloc0(TARGET_PAGE_SIZE);
+    memcpy(it->it_data, pdata, TARGET_PAGE_SIZE);
+    it->it_age = ++cache_max_item_age;
+    it->it_addr = addr;
+}
+
 static int is_dup_page(uint8_t *page, uint8_t ch)
 {
     uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch;
-- 
1.7.6.5