Re: [Qemu-devel] [PATCH] XBRLE page delta compression for live migration of large memory apps
> From: Stefan Hajnoczi [mailto:stefa...@gmail.com] > Sent: Wednesday, June 22, 2011 3:26 PM > > On Wed, Jun 22, 2011 at 1:01 PM, Anthony Liguori > wrote: > >> > >> By using XBRLE (Xor Based Run-Length-Encoding) we can > reduce required > >> bandwidth for transfering of dirty memory pages during > live migration > >> migrate_set_cachesize > >> migrate -x > > > > By how much? See "Evaluation of delta compression techniques for efficient live migration of large virtual machines" (http://portal.acm.org/citation.cfm?id=1952698) subsection 5.2.3: In the final test, a VM running a SAP Central Instance ERP system was migrated over Gigabit Ethernet. With XBRLE, the total migration time was reduced from 235 s to 139 s, the suspension time was reduced from 3 s to 0.2 s, and the ping downtime from 5 s to 1 s... > > > > This is a change to the live migration protocol, it would > also require > > documentation and an understanding of how it affects compatibility. The default behavior (i.e. using the -x migrate option) has not changed thus still compatible with previous qemu versions. When initiating a migration with XBRLE the remote peer must also support XBRLE else migration will fail. With regards to documentation please advise. > > > > The patch really needs to be split into logical pieces too. > It's a bit too > > big for a meaningful review. > > Two places where you could consider splitting the patch is the caching > and the sampling. Are they necessary for correctness and could they > be submitted as follow-up patches to a core patch which does just the > XBRLE? Some changes were done to reduce code size: (1) Sampling code - which was used for early detection that the page changed so much thus XBRLE not applicable - has been replaced with a simple check that the XBRLE delta does not overflow a 1/3 of a page size (4096 bytes). (2) Check-summing/page-logging code - existing only under debug compile ifdef option - was removed. (3) XBRLE migration statistics - were replaced with a detailed 'info migrate' output - vital for tracking the XBRLE operation. (4) 2-way associative cache - was not separated from the XBRLE code as the cache is a fundamental part of XBRLE implementation (XBRLE updates are the difference between the new page and the old cached page on the sender side). Currently I don't see howto split the code into smaller meaningful pieces - for now I have re-submitted a single patch with correction. (see separate email [PATCH v2]). > > Also, whenever there are heuristics and use of floating point then > there is some magic going on. It may be necessary and give a huge > performance boost but needs explanation so it is not a black box or > fragile mechanism once it has been merged upstream. The code mentioned (which was responsible for sampling page to test it for being eligible for XBRLE encoding) has been removed. > > Stefan Aidan
Re: [Qemu-devel] [PATCH] XBRLE page delta compression for live migration of large memory apps
On Wed, Jun 22, 2011 at 1:01 PM, Anthony Liguori wrote: > On 05/22/2011 07:00 AM, Shribman, Aidan wrote: >> >> Subject: [PATCH] XBRLE page delta compression for live migration of large >> memory apps >> From: Aidan Shribman >> >> By using XBRLE (Xor Based Run-Length-Encoding) we can reduce required >> bandwidth for transfering of dirty memory pages during live migration >> migrate_set_cachesize >> migrate -x >> Qemu host: Ubuntu 10.10 >> Testing: live migration (w and w/o XBRLE) tested successfully. > > By how much? > > This is a change to the live migration protocol, it would also require > documentation and an understanding of how it affects compatibility. > > The patch really needs to be split into logical pieces too. It's a bit too > big for a meaningful review. Two places where you could consider splitting the patch is the caching and the sampling. Are they necessary for correctness and could they be submitted as follow-up patches to a core patch which does just the XBRLE? Also, whenever there are heuristics and use of floating point then there is some magic going on. It may be necessary and give a huge performance boost but needs explanation so it is not a black box or fragile mechanism once it has been merged upstream. Stefan
Re: [Qemu-devel] [PATCH] XBRLE page delta compression for live migration of large memory apps
On 05/22/2011 07:00 AM, Shribman, Aidan wrote:
Subject: [PATCH] XBRLE page delta compression for live migration of large
memory apps
From: Aidan Shribman
By using XBRLE (Xor Based Run-Length-Encoding) we can reduce required
bandwidth for transfering of dirty memory pages during live migration
migrate_set_cachesize
migrate -x
Qemu host: Ubuntu 10.10
Testing: live migration (w and w/o XBRLE) tested successfully.
By how much?
This is a change to the live migration protocol, it would also require
documentation and an understanding of how it affects compatibility.
The patch really needs to be split into logical pieces too. It's a bit
too big for a meaningful review.
Regards,
Anthony Liguori
Signed-off-by: Benoit Hudzia
Signed-off-by: Petter Svard
Signed-off-by: Aidan Shribman
---
arch_init.c | 647 +
block-migration.c |3 +-
hmp-commands.hx | 36 +++-
hw/hw.h |3 +-
migration-exec.c |6 +-
migration-fd.c|6 +-
migration-tcp.c |6 +-
migration-unix.c |6 +-
migration.c | 33 +++-
migration.h | 23 ++-
qmp-commands.hx | 43 +++-
savevm.c | 13 +-
sysemu.h |3 +-
13 files changed, 749 insertions(+), 79 deletions(-)
diff --git a/arch_init.c b/arch_init.c
index 4486925..069cd67 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -27,6 +27,7 @@
#include
#include
#endif
+#include
#include "config.h"
#include "monitor.h"
#include "sysemu.h"
@@ -41,6 +42,24 @@
#include "gdbstub.h"
#include "hw/smbios.h"
+//#define DEBUG_ARCH_INIT
+#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
+
+//#define DEBUG_ARCH_INIT_CKSUM
+#ifdef DEBUG_ARCH_INIT_CKSUM
+#define PAGE_LOG(addr, pdata, fmt, ...) \
+do { page_log(addr, pdata, fmt, ## __VA_ARGS__); } while (0)
+#else
+#define PAGE_LOG(addr, pdata, fmt, ...) \
+do { } while (0)
+#endif
+
#ifdef TARGET_SPARC
int graphic_width = 1024;
int graphic_height = 768;
@@ -88,6 +107,402 @@ 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_XBRLE0x40
+
+/***/
+/* 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);
+
+/***/
+/* 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;
+uint16_t xh_len;
+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);
+#ifdef DEBUG_ARCH_INIT_CKSUM
+static uint32_t page_cksum(uint8_t *buf);
+static void page_log(ram_addr_t addr, uint8_t *pdata, const char *fmt, ...);
+#endif
+
+/***/
+/* benchmarking */
+typedef struct BenchInfo {
+uint64_t normal_pages;
+uint64_t xbrle_pages;
+uint64_t xbrle_bytes;
+uint64_t xbrle_pages_aborted;
+uint64_t dup_pages;
+uint64_t iterations;
+} BenchInfo;
+
+static BenchInfo bench;
+
+/***/
+/* XBRLE page cache implementation */
+static CacheItem *cache_item_get(unsigned long pos, int item)
+{
+assert(page_cache);
+return&page_cache[pos].bkt_item[item];
+}
+
+#ifdef DEBUG_ARCH_INIT_CKSUM
+static int64_t cache_max_items(void)
+{
+
Re: [Qemu-devel] [PATCH] XBRLE page delta compression for live migration of large memory apps
The proposed patch slipped by with no apparent response - kindly provide
feedback,
Aidan
> -Original Message-
> From: qemu-devel-bounces+aidan.shribman=sap@nongnu.org
> [mailto:qemu-devel-bounces+aidan.shribman=sap@nongnu.org]
> On Behalf Of Shribman, Aidan
> Sent: Sunday, May 22, 2011 3:01 PM
> To: qemu-devel@nongnu.org
> Subject: [Qemu-devel] [PATCH] XBRLE page delta compression
> for live migration of large memory apps
>
> Subject: [PATCH] XBRLE page delta compression for live
> migration of large memory apps
> From: Aidan Shribman
>
> By using XBRLE (Xor Based Run-Length-Encoding) we can reduce required
> bandwidth for transfering of dirty memory pages during live migration
> migrate_set_cachesize
> migrate -x
> Qemu host: Ubuntu 10.10
> Testing: live migration (w and w/o XBRLE) tested successfully.
>
> Signed-off-by: Benoit Hudzia
> Signed-off-by: Petter Svard
> Signed-off-by: Aidan Shribman
>
> ---
>
> arch_init.c | 647
> +
> block-migration.c |3 +-
> hmp-commands.hx | 36 +++-
> hw/hw.h |3 +-
> migration-exec.c |6 +-
> migration-fd.c|6 +-
> migration-tcp.c |6 +-
> migration-unix.c |6 +-
> migration.c | 33 +++-
> migration.h | 23 ++-
> qmp-commands.hx | 43 +++-
> savevm.c | 13 +-
> sysemu.h |3 +-
> 13 files changed, 749 insertions(+), 79 deletions(-)
>
> diff --git a/arch_init.c b/arch_init.c
> index 4486925..069cd67 100644
> --- a/arch_init.c
> +++ b/arch_init.c
> @@ -27,6 +27,7 @@
> #include
> #include
> #endif
> +#include
> #include "config.h"
> #include "monitor.h"
> #include "sysemu.h"
> @@ -41,6 +42,24 @@
> #include "gdbstub.h"
> #include "hw/smbios.h"
>
> +//#define DEBUG_ARCH_INIT
> +#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
> +
> +//#define DEBUG_ARCH_INIT_CKSUM
> +#ifdef DEBUG_ARCH_INIT_CKSUM
> +#define PAGE_LOG(addr, pdata, fmt, ...) \
> +do { page_log(addr, pdata, fmt, ## __VA_ARGS__); } while (0)
> +#else
> +#define PAGE_LOG(addr, pdata, fmt, ...) \
> +do { } while (0)
> +#endif
> +
> #ifdef TARGET_SPARC
> int graphic_width = 1024;
> int graphic_height = 768;
> @@ -88,6 +107,402 @@ 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_XBRLE0x40
> +
> +/***/
> +/* 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);
> +
> +/***/
> +/* 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;
> +uint16_t xh_len;
> +uint32_t xh_cksum;
> +} XBRLEHeader;
> +
> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst,
> int dlen);
> +static int rle_decode(uint8
[Qemu-devel] [PATCH] XBRLE page delta compression for live migration of large memory apps
Subject: [PATCH] XBRLE page delta compression for live migration of large
memory apps
From: Aidan Shribman
By using XBRLE (Xor Based Run-Length-Encoding) we can reduce required
bandwidth for transfering of dirty memory pages during live migration
migrate_set_cachesize
migrate -x
Qemu host: Ubuntu 10.10
Testing: live migration (w and w/o XBRLE) tested successfully.
Signed-off-by: Benoit Hudzia
Signed-off-by: Petter Svard
Signed-off-by: Aidan Shribman
---
arch_init.c | 647 +
block-migration.c |3 +-
hmp-commands.hx | 36 +++-
hw/hw.h |3 +-
migration-exec.c |6 +-
migration-fd.c|6 +-
migration-tcp.c |6 +-
migration-unix.c |6 +-
migration.c | 33 +++-
migration.h | 23 ++-
qmp-commands.hx | 43 +++-
savevm.c | 13 +-
sysemu.h |3 +-
13 files changed, 749 insertions(+), 79 deletions(-)
diff --git a/arch_init.c b/arch_init.c
index 4486925..069cd67 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -27,6 +27,7 @@
#include
#include
#endif
+#include
#include "config.h"
#include "monitor.h"
#include "sysemu.h"
@@ -41,6 +42,24 @@
#include "gdbstub.h"
#include "hw/smbios.h"
+//#define DEBUG_ARCH_INIT
+#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
+
+//#define DEBUG_ARCH_INIT_CKSUM
+#ifdef DEBUG_ARCH_INIT_CKSUM
+#define PAGE_LOG(addr, pdata, fmt, ...) \
+do { page_log(addr, pdata, fmt, ## __VA_ARGS__); } while (0)
+#else
+#define PAGE_LOG(addr, pdata, fmt, ...) \
+do { } while (0)
+#endif
+
#ifdef TARGET_SPARC
int graphic_width = 1024;
int graphic_height = 768;
@@ -88,6 +107,402 @@ 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_XBRLE0x40
+
+/***/
+/* 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);
+
+/***/
+/* 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;
+uint16_t xh_len;
+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);
+#ifdef DEBUG_ARCH_INIT_CKSUM
+static uint32_t page_cksum(uint8_t *buf);
+static void page_log(ram_addr_t addr, uint8_t *pdata, const char *fmt, ...);
+#endif
+
+/***/
+/* benchmarking */
+typedef struct BenchInfo {
+uint64_t normal_pages;
+uint64_t xbrle_pages;
+uint64_t xbrle_bytes;
+uint64_t xbrle_pages_aborted;
+uint64_t dup_pages;
+uint64_t iterations;
+} BenchInfo;
+
+static BenchInfo bench;
+
+/***/
+/* XBRLE page cache implementation */
+static CacheItem *cache_item_get(unsigned long pos, int item)
+{
+assert(page_cache);
+return &page_cache[pos].bkt_item[item];
+}
+
+#ifdef DEBUG_ARCH_INIT_CKSUM
+static int64_t cache_max_items(void)
+{
+return cache_num_buckets * CACHE_N_WAY;
+}
+#endif /* DEBUG_ARCH_INIT_CKSUM */
+
+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 %ld\n", cache_num_buc
