[v2] migration: Support gtree migration
diff mbox series

Message ID 20191003145431.21154-1-eric.auger@redhat.com
State New
Headers show
Series
  • [v2] migration: Support gtree migration
Related show

Commit Message

Auger Eric Oct. 3, 2019, 2:54 p.m. UTC
Introduce support for GTree migration. A custom save/restore
is implemented. Each item is made of a key and a data. For that
reason, 2 VMSD objects are passed into the GTree VMStateField.

When putting the items, the tree is traversed in sorted order by
g_tree_foreach.

On the get() path, gtrees must be allocated using the proper
key compare, key destroy and value destroy. This can be done
externally of automatically. If done automatically, the set of
functions must be stored within the VMStateField in a new opaque
pointer.

Automatic allocation is needed for complex state save/restore.
For instance the virtio-iommu uses a gtree of domain and each
domain has a gtree of mappings.

Special care was taken about direct key (ie. when the key is not
a pointer to an object but is directly a value).

Tests are added to test save/dump of structs containing gtrees
including the virtio-iommu domain/mappings scenario.

Signed-off-by: Eric Auger <eric.auger@redhat.com>

---

v1 -> v2:
- fix compilation issues reported by robots
- fixed init of VMSD array
- direct key now dumped as a 32b
- removed useless cast from/to pointer
---
 include/migration/vmstate.h |  31 +++
 migration/trace-events      |   6 +
 migration/vmstate-types.c   | 133 +++++++++++
 tests/test-vmstate.c        | 427 ++++++++++++++++++++++++++++++++++++
 4 files changed, 597 insertions(+)

Comments

Daniel P. Berrangé Oct. 3, 2019, 2:58 p.m. UTC | #1
On Thu, Oct 03, 2019 at 04:54:31PM +0200, Eric Auger wrote:
> Introduce support for GTree migration. A custom save/restore
> is implemented. Each item is made of a key and a data. For that
> reason, 2 VMSD objects are passed into the GTree VMStateField.
> 
> When putting the items, the tree is traversed in sorted order by
> g_tree_foreach.
> 
> On the get() path, gtrees must be allocated using the proper
> key compare, key destroy and value destroy. This can be done
> externally of automatically. If done automatically, the set of
> functions must be stored within the VMStateField in a new opaque
> pointer.
> 
> Automatic allocation is needed for complex state save/restore.
> For instance the virtio-iommu uses a gtree of domain and each
> domain has a gtree of mappings.
> 
> Special care was taken about direct key (ie. when the key is not
> a pointer to an object but is directly a value).
> 
> Tests are added to test save/dump of structs containing gtrees
> including the virtio-iommu domain/mappings scenario.
> 
> Signed-off-by: Eric Auger <eric.auger@redhat.com>
> 
> ---
> 
> diff --git a/migration/vmstate-types.c b/migration/vmstate-types.c
> index bee658a1b2..06c4663de6 100644
> --- a/migration/vmstate-types.c
> +++ b/migration/vmstate-types.c
> @@ -17,6 +17,7 @@
>  #include "qemu/error-report.h"
>  #include "qemu/queue.h"
>  #include "trace.h"
> +#include <glib.h>

Not required, everything in QEMU includes this already.


Regards,
Daniel
Juan Quintela Oct. 3, 2019, 4:14 p.m. UTC | #2
Eric Auger <eric.auger@redhat.com> wrote:
> Introduce support for GTree migration. A custom save/restore
> is implemented. Each item is made of a key and a data. For that
> reason, 2 VMSD objects are passed into the GTree VMStateField.
>
> When putting the items, the tree is traversed in sorted order by
> g_tree_foreach.
>
> On the get() path, gtrees must be allocated using the proper
> key compare, key destroy and value destroy. This can be done
> externally of automatically. If done automatically, the set of
             ^^

or.

> functions must be stored within the VMStateField in a new opaque
> pointer.

I am not fully convinced that the automatic mode is needed.  Especially
the ->data field.  I *fear* it being abused for other cases.

> Automatic allocation is needed for complex state save/restore.
> For instance the virtio-iommu uses a gtree of domain and each
> domain has a gtree of mappings.

There is a pre_load() function for the VMState that creates this.  it
can be used to initualize the field value, no?  That way the data part
is not needed.  I think this will make the code less complex, what do
you think?

> Special care was taken about direct key (ie. when the key is not
> a pointer to an object but is directly a value).

I am wondering if for this, it is better to add two VMSTATE (at least at
the macro level).  SIMPLE_TREE, and TREE, or whataver oyou want to call
it.  But I haven't fully looked into it.

The other general "consideration" that I have is that there is neither
of:
- marker between elements
- number of elements
- total size/size of elements.

That makes completelly impractical to "walk" the migration stream
without understanding exactyl what is there.  (Now, to be fair, there
are other parts of qemu that are like that.  PCI cames to mind.)

> Tests are added to test save/dump of structs containing gtrees
> including the virtio-iommu domain/mappings scenario.

Really nice to have the tests.  Thanks.

> Signed-off-by: Eric Auger <eric.auger@redhat.com>


> diff --git a/include/migration/vmstate.h b/include/migration/vmstate.h
> index 1fbfd099dd..4d9698eaab 100644
> --- a/include/migration/vmstate.h
> +++ b/include/migration/vmstate.h
> @@ -171,6 +171,7 @@ struct VMStateField {
>      int version_id;
>      int struct_version_id;
>      bool (*field_exists)(void *opaque, int version_id);
> +    void *data;
>  };

This is the bit that I don't really like :p

>  
> +typedef struct GTreeInitData {
> +    GCompareDataFunc key_compare_func;
> +    gpointer key_compare_data;
> +    GDestroyNotify key_destroy_func;
> +    GDestroyNotify value_destroy_func;
> +} GTreeInitData;

My understanding is that if you do this on the pre_load() function, you
don't need this at all.

> diff --git a/migration/vmstate-types.c b/migration/vmstate-types.c
> index bee658a1b2..06c4663de6 100644
> --- a/migration/vmstate-types.c
> +++ b/migration/vmstate-types.c
> @@ -17,6 +17,7 @@
>  #include "qemu/error-report.h"
>  #include "qemu/queue.h"
>  #include "trace.h"
> +#include <glib.h>
>  
>  /* bool */
>  
> @@ -691,3 +692,135 @@ const VMStateInfo vmstate_info_qtailq = {
>      .get  = get_qtailq,
>      .put  = put_qtailq,
>  };
> +
> +struct put_gtree_data {
> +    QEMUFile *f;
> +    const VMStateField *field;
> +    QJSON *vmdesc;
> +};
> +
> +static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
> +{
> +    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
> +    const VMStateField *field = capsule->field;
> +    QEMUFile *f = capsule->f;
> +    const VMStateDescription *key_vmsd = &field->vmsd[0];
> +    const VMStateDescription *data_vmsd = &field->vmsd[1];
> +
> +    qemu_put_byte(f, true);

Ok.  there is a marker O:-)

> +
> +    /* put the key */
> +    if (!key_vmsd->fields) {
> +        qemu_put_be32(f, GPOINTER_TO_UINT(key));
> +    } else {
> +        if (vmstate_save_state(f, key_vmsd, key, capsule->vmdesc)) {
> +            return true;
> +        }
> +    }

But it is magic to know if it is a simple or complex key.


> +    if (field->data) {
> +        init_data = (GTreeInitData *)field->data;
> +        tree = g_tree_new_full(init_data->key_compare_func,
> +                               init_data->key_compare_data,
> +                               init_data->key_destroy_func,
> +                               init_data->value_destroy_func);
> +        *pval = tree;
> +    } else {
> +        /* tree is externally allocated */
> +        tree = *pval;
> +    }

This can be simplified while we are at it.

> +    while (qemu_get_byte(f)) {

If we get out of sync, for any reason, we have no way to recover.  The
only way to recover is that we don't get a "false" in this position.


Later, Juan.
Auger Eric Oct. 3, 2019, 7:30 p.m. UTC | #3
Hi Juan,

On 10/3/19 6:14 PM, Juan Quintela wrote:
> Eric Auger <eric.auger@redhat.com> wrote:
>> Introduce support for GTree migration. A custom save/restore
>> is implemented. Each item is made of a key and a data. For that
>> reason, 2 VMSD objects are passed into the GTree VMStateField.
>>
>> When putting the items, the tree is traversed in sorted order by
>> g_tree_foreach.
>>
>> On the get() path, gtrees must be allocated using the proper
>> key compare, key destroy and value destroy. This can be done
>> externally of automatically. If done automatically, the set of
>              ^^
> 
> or.
> 
>> functions must be stored within the VMStateField in a new opaque
>> pointer.
> 
> I am not fully convinced that the automatic mode is needed.  Especially
> the ->data field.  I *fear* it being abused for other cases.
OK. I implemented your suggestion, ie. using preload and it does the
job. So I don't need that field anymore.
> 
>> Automatic allocation is needed for complex state save/restore.
>> For instance the virtio-iommu uses a gtree of domain and each
>> domain has a gtree of mappings.
> 
> There is a pre_load() function for the VMState that creates this.  it
> can be used to initualize the field value, no?  That way the data part
> is not needed.  I think this will make the code less complex, what do
> you think?
agreed
> 
>> Special care was taken about direct key (ie. when the key is not
>> a pointer to an object but is directly a value).
> 
> I am wondering if for this, it is better to add two VMSTATE (at least at
> the macro level).  SIMPLE_TREE, and TREE, or whataver oyou want to call
> it.  But I haven't fully looked into it.
I don't have a strong opinion here. At the moment I test the
key_vmsd->field and if it is NULL this means the key is a direct one.

Otherwise we could have 2 macros, a single info, but 2 different field
names. the name would allow to know the nature of the key.
> 
> The other general "consideration" that I have is that there is neither
> of:
> - marker between elements
so we have one
> - number of elements
you don't have it
> - total size/size of elements.
you just have the size of the key and the size of the value at the
moment. I could easily add the number of nodes.
> 
> That makes completelly impractical to "walk" the migration stream
> without understanding exactyl what is there.  (Now, to be fair, there
> are other parts of qemu that are like that.  PCI cames to mind.)
> 
>> Tests are added to test save/dump of structs containing gtrees
>> including the virtio-iommu domain/mappings scenario.
> 
> Really nice to have the tests.  Thanks.


> 
>> Signed-off-by: Eric Auger <eric.auger@redhat.com>
> 
> 
>> diff --git a/include/migration/vmstate.h b/include/migration/vmstate.h
>> index 1fbfd099dd..4d9698eaab 100644
>> --- a/include/migration/vmstate.h
>> +++ b/include/migration/vmstate.h
>> @@ -171,6 +171,7 @@ struct VMStateField {
>>      int version_id;
>>      int struct_version_id;
>>      bool (*field_exists)(void *opaque, int version_id);
>> +    void *data;
>>  };
> 
> This is the bit that I don't really like :p
> 
>>  
>> +typedef struct GTreeInitData {
>> +    GCompareDataFunc key_compare_func;
>> +    gpointer key_compare_data;
>> +    GDestroyNotify key_destroy_func;
>> +    GDestroyNotify value_destroy_func;
>> +} GTreeInitData;
> 
> My understanding is that if you do this on the pre_load() function, you
> don't need this at all.
yep
> 
>> diff --git a/migration/vmstate-types.c b/migration/vmstate-types.c
>> index bee658a1b2..06c4663de6 100644
>> --- a/migration/vmstate-types.c
>> +++ b/migration/vmstate-types.c
>> @@ -17,6 +17,7 @@
>>  #include "qemu/error-report.h"
>>  #include "qemu/queue.h"
>>  #include "trace.h"
>> +#include <glib.h>
>>  
>>  /* bool */
>>  
>> @@ -691,3 +692,135 @@ const VMStateInfo vmstate_info_qtailq = {
>>      .get  = get_qtailq,
>>      .put  = put_qtailq,
>>  };
>> +
>> +struct put_gtree_data {
>> +    QEMUFile *f;
>> +    const VMStateField *field;
>> +    QJSON *vmdesc;
>> +};
>> +
>> +static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
>> +{
>> +    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
>> +    const VMStateField *field = capsule->field;
>> +    QEMUFile *f = capsule->f;
>> +    const VMStateDescription *key_vmsd = &field->vmsd[0];
>> +    const VMStateDescription *data_vmsd = &field->vmsd[1];
>> +
>> +    qemu_put_byte(f, true);
> 
> Ok.  there is a marker O:-)
yep
> 
>> +
>> +    /* put the key */
>> +    if (!key_vmsd->fields) {
>> +        qemu_put_be32(f, GPOINTER_TO_UINT(key));
>> +    } else {
>> +        if (vmstate_save_state(f, key_vmsd, key, capsule->vmdesc)) {
>> +            return true;
>> +        }
>> +    }
> 
> But it is magic to know if it is a simple or complex key.
key_vmsd->fields is used
this means you set

static const VMStateDescription vmstate_id_domain[2] = {
    {}, VMSTATE_DOMAIN /* direct key, value */
};


> 
> 
>> +    if (field->data) {
>> +        init_data = (GTreeInitData *)field->data;
>> +        tree = g_tree_new_full(init_data->key_compare_func,
>> +                               init_data->key_compare_data,
>> +                               init_data->key_destroy_func,
>> +                               init_data->value_destroy_func);
>> +        *pval = tree;
>> +    } else {
>> +        /* tree is externally allocated */
>> +        tree = *pval;
>> +    }
> 
> This can be simplified while we are at it.
yep, only the else block remains
> 
>> +    while (qemu_get_byte(f)) {
> 
> If we get out of sync, for any reason, we have no way to recover.  The
> only way to recover is that we don't get a "false" in this position.
adding the number of nodes should do the job
> 
> 
> Later, Juan.
> 

So I think I will respin with the following modifications:
- use preload
- introduce 2 different macros
- encode/decode & test the number of nodes

Thank you for the quick feedbacks!

Eric

Patch
diff mbox series

diff --git a/include/migration/vmstate.h b/include/migration/vmstate.h
index 1fbfd099dd..4d9698eaab 100644
--- a/include/migration/vmstate.h
+++ b/include/migration/vmstate.h
@@ -171,6 +171,7 @@  struct VMStateField {
     int version_id;
     int struct_version_id;
     bool (*field_exists)(void *opaque, int version_id);
+    void *data;
 };
 
 struct VMStateDescription {
@@ -224,6 +225,7 @@  extern const VMStateInfo vmstate_info_unused_buffer;
 extern const VMStateInfo vmstate_info_tmp;
 extern const VMStateInfo vmstate_info_bitmap;
 extern const VMStateInfo vmstate_info_qtailq;
+extern const VMStateInfo vmstate_info_gtree;
 
 #define type_check_2darray(t1,t2,n,m) ((t1(*)[n][m])0 - (t2*)0)
 /*
@@ -754,6 +756,35 @@  extern const VMStateInfo vmstate_info_qtailq;
     .start        = offsetof(_type, _next),                              \
 }
 
+typedef struct GTreeInitData {
+    GCompareDataFunc key_compare_func;
+    gpointer key_compare_data;
+    GDestroyNotify key_destroy_func;
+    GDestroyNotify value_destroy_func;
+} GTreeInitData;
+
+/*
+ * For migrating a GTree.
+ * _vmsd: Start address of the 2 element array containing the key vmsd
+ *        and the data vmsd
+ * _key_type: type of the key
+ * _val_type: type of the value
+ * _data: pointer to a GTreeInitData struct
+ * if _data is NULL, the target tree must have been properly initialized
+ */
+#define VMSTATE_GTREE_V(_field, _state, _version, _vmsd,                       \
+                        _key_type, _val_type, _data)                           \
+{                                                                              \
+    .name         = (stringify(_field)),                                       \
+    .version_id   = (_version),                                                \
+    .vmsd         = (_vmsd),                                                   \
+    .info         = &vmstate_info_gtree,                                       \
+    .start        = sizeof(_key_type),                                         \
+    .size         = sizeof(_val_type),                                         \
+    .offset       = offsetof(_state, _field),                                  \
+    .data         = (_data)                                                    \
+}
+
 /* _f : field name
    _f_n : num of elements field_name
    _n : num of elements
diff --git a/migration/trace-events b/migration/trace-events
index 858d415d56..3e2775bd3b 100644
--- a/migration/trace-events
+++ b/migration/trace-events
@@ -71,6 +71,12 @@  get_qtailq_end(const char *name, const char *reason, int val) "%s %s/%d"
 put_qtailq(const char *name, int version_id) "%s v%d"
 put_qtailq_end(const char *name, const char *reason) "%s %s"
 
+get_gtree(const char *key_name, const char *val_name, int version) "%s/%s %d"
+get_gtree_fail(const char *key_name, const char *reason, int val) "%s %s/%d"
+get_gtree_succeed(const char *key_name, const char *val_name, const char *reason, int val) "%s/%s %s/%d"
+put_gtree(const char *key_name, int key_version, const char *val_name, int val_version) "%s(%d)/%s(%d)"
+put_gtree_end(const char *key_name, const char *val_name, const char *reason) "%s/%s %s"
+
 # qemu-file.c
 qemu_file_fclose(void) ""
 
diff --git a/migration/vmstate-types.c b/migration/vmstate-types.c
index bee658a1b2..06c4663de6 100644
--- a/migration/vmstate-types.c
+++ b/migration/vmstate-types.c
@@ -17,6 +17,7 @@ 
 #include "qemu/error-report.h"
 #include "qemu/queue.h"
 #include "trace.h"
+#include <glib.h>
 
 /* bool */
 
@@ -691,3 +692,135 @@  const VMStateInfo vmstate_info_qtailq = {
     .get  = get_qtailq,
     .put  = put_qtailq,
 };
+
+struct put_gtree_data {
+    QEMUFile *f;
+    const VMStateField *field;
+    QJSON *vmdesc;
+};
+
+static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
+{
+    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
+    const VMStateField *field = capsule->field;
+    QEMUFile *f = capsule->f;
+    const VMStateDescription *key_vmsd = &field->vmsd[0];
+    const VMStateDescription *data_vmsd = &field->vmsd[1];
+
+    qemu_put_byte(f, true);
+
+    /* put the key */
+    if (!key_vmsd->fields) {
+        qemu_put_be32(f, GPOINTER_TO_UINT(key));
+    } else {
+        if (vmstate_save_state(f, key_vmsd, key, capsule->vmdesc)) {
+            return true;
+        }
+    }
+
+    /* put the data */
+    if (vmstate_save_state(f, data_vmsd, value, capsule->vmdesc)) {
+        return true;
+    }
+    return false;
+}
+
+static int put_gtree(QEMUFile *f, void *pv, size_t unused_size,
+                     const VMStateField *field, QJSON *vmdesc)
+{
+    const VMStateDescription *key_vmsd = &field->vmsd[0];
+    const VMStateDescription *val_vmsd = &field->vmsd[1];
+    struct put_gtree_data capsule = {f, field, vmdesc};
+    GTree **pval = pv;
+    GTree *tree = *pval;
+
+    trace_put_gtree(key_vmsd->name, key_vmsd->version_id,
+                    val_vmsd->name, val_vmsd->version_id);
+    g_tree_foreach(tree, put_gtree_elem, (gpointer)&capsule);
+    qemu_put_byte(f, false);
+
+    trace_put_gtree_end(key_vmsd->name, val_vmsd->name, "end");
+    return 0;
+}
+
+static int get_gtree(QEMUFile *f, void *pv, size_t unused_size,
+                     const VMStateField *field)
+{
+    const VMStateDescription *key_vmsd = &field->vmsd[0];
+    const VMStateDescription *val_vmsd = &field->vmsd[1];
+    int version_id = field->version_id;
+    size_t key_size = field->start;
+    size_t val_size = field->size;
+    GTreeInitData *init_data;
+    GTree **pval = pv;
+    void *key, *val;
+    GTree *tree;
+    int ret;
+
+    /* in case of direct key, the key vmsd can be {}, ie. check fields */
+    trace_get_gtree(key_vmsd->name, val_vmsd->name, version_id);
+    if (key_vmsd->fields && version_id > key_vmsd->version_id) {
+        error_report("%s %s",  key_vmsd->name, "too new");
+        trace_get_gtree_fail(key_vmsd->name, "too new", -EINVAL);
+        return -EINVAL;
+    }
+    if (key_vmsd->fields && version_id < key_vmsd->minimum_version_id) {
+        error_report("%s %s",  key_vmsd->name, "too old");
+        trace_get_gtree_fail(key_vmsd->name, "too old", -EINVAL);
+        return -EINVAL;
+    }
+    if (version_id > val_vmsd->version_id) {
+        error_report("%s %s",  val_vmsd->name, "too new");
+        trace_get_gtree_fail(val_vmsd->name, "too new", -EINVAL);
+        return -EINVAL;
+    }
+    if (version_id < val_vmsd->minimum_version_id) {
+        error_report("%s %s",  val_vmsd->name, "too old");
+        trace_get_gtree_fail(val_vmsd->name, "too old", -EINVAL);
+        return -EINVAL;
+    }
+
+    if (field->data) {
+        init_data = (GTreeInitData *)field->data;
+        tree = g_tree_new_full(init_data->key_compare_func,
+                               init_data->key_compare_data,
+                               init_data->key_destroy_func,
+                               init_data->value_destroy_func);
+        *pval = tree;
+    } else {
+        /* tree is externally allocated */
+        tree = *pval;
+    }
+
+    while (qemu_get_byte(f)) {
+        if (!key_vmsd->fields) {
+            key = GUINT_TO_POINTER(qemu_get_be32(f));
+        } else {
+            key = g_malloc0(key_size);
+            ret = vmstate_load_state(f, key_vmsd, key, version_id);
+        }
+        if (ret) {
+            g_free(key);
+            trace_get_gtree_fail(key_vmsd->name, "saving state", ret);
+            return ret;
+        }
+        val = g_malloc0(val_size);
+        ret = vmstate_load_state(f, val_vmsd, val, version_id);
+        if (ret) {
+            g_free(key);
+            g_free(val);
+            trace_get_gtree_fail(val_vmsd->name, "saving state", ret);
+            return ret;
+        }
+        g_tree_insert(tree, key, val);
+    }
+    trace_get_gtree_succeed(key_vmsd->name, val_vmsd->name, "end", 0);
+    return 0;
+}
+
+
+const VMStateInfo vmstate_info_gtree = {
+    .name = "gtree",
+    .get  = get_gtree,
+    .put  = put_gtree,
+};
diff --git a/tests/test-vmstate.c b/tests/test-vmstate.c
index e80c4c6143..ee8d9132a4 100644
--- a/tests/test-vmstate.c
+++ b/tests/test-vmstate.c
@@ -33,6 +33,7 @@ 
 #include "qemu/coroutine.h"
 #include "qemu/module.h"
 #include "io/channel-file.h"
+#include <glib.h>
 
 static char temp_file[] = "/tmp/vmst.test.XXXXXX";
 static int temp_fd;
@@ -812,6 +813,428 @@  static void test_load_q(void)
     qemu_fclose(fload);
 }
 
+/* interval (key) */
+typedef struct TestGTreeInterval {
+    uint64_t low;
+    uint64_t high;
+} TestGTreeInterval;
+
+#define VMSTATE_INTERVAL                               \
+{                                                      \
+    .name = "interval",                                \
+    .version_id = 1,                                   \
+    .minimum_version_id = 1,                           \
+    .fields = (VMStateField[]) {                       \
+        VMSTATE_UINT64(low, TestGTreeInterval),        \
+        VMSTATE_UINT64(high, TestGTreeInterval),       \
+        VMSTATE_END_OF_LIST()                          \
+    }                                                  \
+}
+
+/* mapping (value) */
+typedef struct TestGTreeMapping {
+    uint64_t phys_addr;
+    uint32_t flags;
+} TestGTreeMapping;
+
+#define VMSTATE_MAPPING                               \
+{                                                     \
+    .name = "mapping",                                \
+    .version_id = 1,                                  \
+    .minimum_version_id = 1,                          \
+    .fields = (VMStateField[]) {                      \
+        VMSTATE_UINT64(phys_addr, TestGTreeMapping),  \
+        VMSTATE_UINT32(flags, TestGTreeMapping),      \
+        VMSTATE_END_OF_LIST()                         \
+    },                                                \
+}
+
+static const VMStateDescription vmstate_interval_mapping[2] = {
+    VMSTATE_INTERVAL, /* key   */
+    VMSTATE_MAPPING   /* value */
+};
+
+typedef struct TestGTreeDomain {
+    int32_t  id;
+    GTree    *mappings;
+} TestGTreeDomain;
+
+typedef struct TestGTreeIOMMU {
+    int32_t  id;
+    GTree    *domains;
+} TestGTreeIOMMU;
+
+/* Interval comparison function */
+static gint interval_cmp(gconstpointer a, gconstpointer b, gpointer user_data)
+{
+    TestGTreeInterval *inta = (TestGTreeInterval *)a;
+    TestGTreeInterval *intb = (TestGTreeInterval *)b;
+
+    if (inta->high < intb->low) {
+        return -1;
+    } else if (intb->high < inta->low) {
+        return 1;
+    } else {
+        return 0;
+    }
+}
+
+/* ID comparison function */
+static gint int_cmp(gconstpointer a, gconstpointer b, gpointer user_data)
+{
+    uint ua = GPOINTER_TO_UINT(a);
+    uint ub = GPOINTER_TO_UINT(b);
+    return (ua > ub) - (ua < ub);
+}
+
+/* init data for interval/mapping binary tree */
+GTreeInitData gtree_interval_mapping_init = {
+    .key_compare_func = interval_cmp,
+    .key_compare_data = NULL,
+    .key_destroy_func = g_free,
+    .value_destroy_func = g_free
+};
+
+static void destroy_domain(gpointer data)
+{
+    TestGTreeDomain *domain = (TestGTreeDomain *)data;
+
+    g_tree_destroy(domain->mappings);
+    g_free(domain);
+}
+
+/* init data for id (direct key)/domain binary tree */
+GTreeInitData gtree_id_domain_init = {
+    .key_compare_func = int_cmp,
+    .key_compare_data = NULL,
+    .key_destroy_func = NULL,
+    .value_destroy_func = destroy_domain
+};
+
+#define VMSTATE_DOMAIN                                       \
+{                                                            \
+    .name = "domain",                                        \
+    .version_id = 1,                                         \
+    .minimum_version_id = 1,                                 \
+    .fields = (VMStateField[]) {                             \
+        VMSTATE_INT32(id, TestGTreeDomain),                  \
+        VMSTATE_GTREE_V(mappings, TestGTreeDomain, 1,        \
+                        vmstate_interval_mapping,            \
+                        TestGTreeInterval, TestGTreeMapping, \
+                        &gtree_interval_mapping_init),       \
+        VMSTATE_END_OF_LIST()                                \
+    }                                                        \
+}
+static const VMStateDescription vmstate_domain = VMSTATE_DOMAIN;
+
+static const VMStateDescription vmstate_id_domain[2] = {
+    {}, VMSTATE_DOMAIN /* direct key, value */
+};
+
+static const VMStateDescription vmstate_iommu = {
+    .name = "iommu",
+    .version_id = 1,
+    .minimum_version_id = 1,
+    .fields = (VMStateField[]) {
+        VMSTATE_INT32(id, TestGTreeIOMMU),
+        VMSTATE_GTREE_V(domains, TestGTreeIOMMU, 1,
+                        vmstate_id_domain,
+                        NULL, TestGTreeDomain,
+                        &gtree_id_domain_init),
+        VMSTATE_END_OF_LIST()
+    }
+};
+
+uint8_t first_domain_dump[] = {
+    /* id */
+    0x00, 0x0, 0x0, 0x6,
+    0x1, /* start of a */
+    /* a */
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1F, 0xFF,
+    /* map_a */
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xa0, 0x00,
+    0x00, 0x00, 0x00, 0x01,
+    0x1, /* start of b */
+    /* b */
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4F, 0xFF,
+    /* map_b */
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x02,
+    0x0, /* end of gtree */
+    QEMU_VM_EOF, /* just to ensure we won't get EOF reported prematurely */
+};
+
+static TestGTreeDomain *create_first_domain(void)
+{
+    TestGTreeDomain *domain;
+    TestGTreeMapping *map_a, *map_b;
+    TestGTreeInterval *a, *b;
+
+    domain = g_malloc0(sizeof(TestGTreeDomain));
+    domain->id = 6;
+
+    a = g_malloc0(sizeof(TestGTreeInterval));
+    a->low = 0x1000;
+    a->high = 0x1FFF;
+
+    b = g_malloc0(sizeof(TestGTreeInterval));
+    b->low = 0x4000;
+    b->high = 0x4FFF;
+
+    map_a = g_malloc0(sizeof(TestGTreeMapping));
+    map_a->phys_addr = 0xa000;
+    map_a->flags = 1;
+
+    map_b = g_malloc0(sizeof(TestGTreeMapping));
+    map_b->phys_addr = 0xe0000;
+    map_b->flags = 2;
+
+    domain->mappings = g_tree_new_full((GCompareDataFunc)interval_cmp, NULL,
+                                        (GDestroyNotify)g_free,
+                                        (GDestroyNotify)g_free);
+    g_tree_insert(domain->mappings, a, map_a);
+    g_tree_insert(domain->mappings, b, map_b);
+    return domain;
+}
+
+static void test_gtree_save_domain(void)
+{
+    TestGTreeDomain *first_domain = create_first_domain();
+
+    save_vmstate(&vmstate_domain, first_domain);
+    compare_vmstate(first_domain_dump, sizeof(first_domain_dump));
+    destroy_domain(first_domain);
+}
+
+struct match_node_data {
+    GTree *tree;
+    gpointer key;
+    gpointer value;
+};
+
+struct tree_cmp_data {
+    GTree *tree1;
+    GTree *tree2;
+    GTraverseFunc match_node;
+};
+
+static gboolean match_interval_mapping_node(gpointer key,
+                                            gpointer value, gpointer data)
+{
+    TestGTreeMapping *map_a, *map_b;
+    TestGTreeInterval *a, *b;
+    struct match_node_data *d = (struct match_node_data *)data;
+    char *str = g_strdup_printf("dest");
+
+    g_free(str);
+    a = (TestGTreeInterval *)key;
+    b = (TestGTreeInterval *)d->key;
+
+    map_a = (TestGTreeMapping *)value;
+    map_b = (TestGTreeMapping *)d->value;
+
+    assert(a->low == b->low);
+    assert(a->high == b->high);
+    assert(map_a->phys_addr == map_b->phys_addr);
+    assert(map_a->flags == map_b->flags);
+    g_tree_remove(d->tree, key);
+    return true;
+}
+
+static gboolean diff_tree(gpointer key, gpointer value, gpointer data)
+{
+    struct tree_cmp_data *tp = (struct tree_cmp_data *)data;
+    struct match_node_data d = {tp->tree2, key, value};
+
+    g_tree_foreach(tp->tree2, tp->match_node, &d);
+    g_tree_remove(tp->tree1, key);
+    return false;
+}
+
+static void compare_trees(GTree *tree1, GTree *tree2,
+                          GTraverseFunc function)
+{
+    struct tree_cmp_data tp = {tree1, tree2, function};
+
+    g_tree_foreach(tree1, diff_tree, &tp);
+    assert(g_tree_nnodes(tree1) == 0);
+    assert(g_tree_nnodes(tree2) == 0);
+}
+
+static void diff_domain(TestGTreeDomain *d1, TestGTreeDomain *d2)
+{
+    assert(d1->id == d2->id);
+    compare_trees(d1->mappings, d2->mappings, match_interval_mapping_node);
+}
+
+static gboolean match_domain_node(gpointer key, gpointer value, gpointer data)
+{
+    uint64_t id1, id2;
+    TestGTreeDomain *d1, *d2;
+    struct match_node_data *d = (struct match_node_data *)data;
+
+    id1 = (uint64_t)key;
+    id2 = (uint64_t)d->key;
+    d1 = (TestGTreeDomain *)value;
+    d2 = (TestGTreeDomain *)d->value;
+    assert(id1 == id2);
+    diff_domain(d1, d2);
+    g_tree_remove(d->tree, key);
+    return true;
+}
+
+static void diff_iommu(TestGTreeIOMMU *iommu1, TestGTreeIOMMU *iommu2)
+{
+    assert(iommu1->id == iommu2->id);
+    compare_trees(iommu1->domains, iommu2->domains, match_domain_node);
+}
+
+static void test_gtree_load_domain(void)
+{
+    TestGTreeDomain *dest_domain = g_malloc0(sizeof(TestGTreeDomain));
+    TestGTreeDomain *orig_domain = create_first_domain();
+    QEMUFile *fload, *fsave;
+    char eof;
+
+    fsave = open_test_file(true);
+    qemu_put_buffer(fsave, first_domain_dump, sizeof(first_domain_dump));
+    g_assert(!qemu_file_get_error(fsave));
+    qemu_fclose(fsave);
+
+    fload = open_test_file(false);
+    dest_domain->mappings = g_tree_new_full((GCompareDataFunc)interval_cmp,
+                                            NULL,
+                                            (GDestroyNotify)g_free,
+                                            (GDestroyNotify)g_free);
+
+    vmstate_load_state(fload, &vmstate_domain, dest_domain, 1);
+    eof = qemu_get_byte(fload);
+    g_assert(!qemu_file_get_error(fload));
+    g_assert_cmpint(orig_domain->id, ==, dest_domain->id);
+    g_assert_cmpint(eof, ==, QEMU_VM_EOF);
+
+    diff_domain(orig_domain, dest_domain);
+    destroy_domain(orig_domain);
+    destroy_domain(dest_domain);
+    qemu_fclose(fload);
+}
+
+uint8_t iommu_dump[] = {
+    /* iommu id */
+    0x00, 0x0, 0x0, 0x7,
+    0x1,/* start of domain 5 */
+        0x00, 0x0, 0x0, 0x5, /* key = 5 */
+        0x00, 0x0, 0x0, 0x5, /* domain1 id */
+        0x1, /* start of mappings */
+            /* c */
+            0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x01, 0xFF, 0xFF, 0xFF,
+            /* map_c */
+            0x00, 0x00, 0x00, 0x00, 0x0F, 0x00, 0x00, 0x00,
+            0x00, 0x0, 0x0, 0x3,
+            0x0, /* end of domain1 mappings*/
+    0x1,/* start of domain 6 */
+        0x00, 0x0, 0x0, 0x6, /* key = 6 */
+        0x00, 0x0, 0x0, 0x6, /* domain6 id */
+            0x1, /* start of a */
+            /* a */
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1F, 0xFF,
+            /* map_a */
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xa0, 0x00,
+            0x00, 0x00, 0x00, 0x01,
+            0x1, /* start of b */
+            /* b */
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4F, 0xFF,
+            /* map_b */
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x02,
+            0x0, /* end of domain6 mappings*/
+    0x0, /* end of domains */
+    QEMU_VM_EOF, /* just to ensure we won't get EOF reported prematurely */
+};
+
+static TestGTreeIOMMU *create_iommu(void)
+{
+    TestGTreeIOMMU *iommu = g_malloc0(sizeof(TestGTreeIOMMU));
+    TestGTreeDomain *first_domain = create_first_domain();
+    TestGTreeDomain *second_domain;
+    TestGTreeMapping *map_c;
+    TestGTreeInterval *c;
+
+    iommu->id = 7;
+    iommu->domains = g_tree_new_full((GCompareDataFunc)int_cmp, NULL,
+                                     NULL,
+                                     destroy_domain);
+
+    second_domain = g_malloc0(sizeof(TestGTreeDomain));
+    second_domain->id = 5;
+    second_domain->mappings = g_tree_new_full((GCompareDataFunc)interval_cmp,
+                                              NULL,
+                                              (GDestroyNotify)g_free,
+                                              (GDestroyNotify)g_free);
+
+    g_tree_insert(iommu->domains, GUINT_TO_POINTER(6), first_domain);
+    g_tree_insert(iommu->domains, GUINT_TO_POINTER(5), second_domain);
+
+    c = g_malloc0(sizeof(TestGTreeInterval));
+    c->low = 0x1000000;
+    c->high = 0x1FFFFFF;
+
+    map_c = g_malloc0(sizeof(TestGTreeMapping));
+    map_c->phys_addr = 0xF000000;
+    map_c->flags = 0x3;
+
+    g_tree_insert(second_domain->mappings, c, map_c);
+    return iommu;
+}
+
+static void destroy_iommu(TestGTreeIOMMU *iommu)
+{
+    g_tree_destroy(iommu->domains);
+    g_free(iommu);
+}
+
+static void test_gtree_save_iommu(void)
+{
+    TestGTreeIOMMU *iommu = create_iommu();
+
+    save_vmstate(&vmstate_iommu, iommu);
+    compare_vmstate(iommu_dump, sizeof(iommu_dump));
+    destroy_iommu(iommu);
+}
+
+static void test_gtree_load_iommu(void)
+{
+    TestGTreeIOMMU *dest_iommu = g_malloc0(sizeof(TestGTreeIOMMU));
+    TestGTreeIOMMU *orig_iommu = create_iommu();
+    QEMUFile *fsave, *fload;
+    char eof;
+    int ret;
+
+    fsave = open_test_file(true);
+    qemu_put_buffer(fsave, iommu_dump, sizeof(iommu_dump));
+    g_assert(!qemu_file_get_error(fsave));
+    qemu_fclose(fsave);
+
+    fload = open_test_file(false);
+    vmstate_load_state(fload, &vmstate_iommu, dest_iommu, 1);
+    ret = qemu_file_get_error(fload);
+    eof = qemu_get_byte(fload);
+    ret = qemu_file_get_error(fload);
+    g_assert(!ret);
+    g_assert_cmpint(orig_iommu->id, ==, dest_iommu->id);
+    g_assert_cmpint(eof, ==, QEMU_VM_EOF);
+
+    diff_iommu(orig_iommu, dest_iommu);
+    destroy_iommu(orig_iommu);
+    destroy_iommu(dest_iommu);
+    qemu_fclose(fload);
+}
+
 typedef struct TmpTestStruct {
     TestStruct *parent;
     int64_t diff;
@@ -932,6 +1355,10 @@  int main(int argc, char **argv)
                     test_arr_ptr_prim_0_load);
     g_test_add_func("/vmstate/qtailq/save/saveq", test_save_q);
     g_test_add_func("/vmstate/qtailq/load/loadq", test_load_q);
+    g_test_add_func("/vmstate/gtree/save/savedomain", test_gtree_save_domain);
+    g_test_add_func("/vmstate/gtree/load/loaddomain", test_gtree_load_domain);
+    g_test_add_func("/vmstate/gtree/save/saveiommu", test_gtree_save_iommu);
+    g_test_add_func("/vmstate/gtree/load/loadiommu", test_gtree_load_iommu);
     g_test_add_func("/vmstate/tmp_struct", test_tmp_struct);
     g_test_run();