[v3] migration: Support gtree migration
diff mbox series

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

Commit Message

Auger Eric Oct. 4, 2019, 11:20 a.m. UTC
Introduce support for GTree migration. A custom save/restore
is implemented. Each item is made of a key and a data.

If the key is a pointer to an object, 2 VMSDs 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 must be handled
beforehand, for example in a pre_load method.

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>

---

v2 -> v3:
- do not include glib.h anymore
- introduce VMSTATE_GTREE_DIRECT_KEY_V
- use pre_load to allocate the tree and remove data pointer
- dump the number of nnodes and add checks on get path

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 |  40 ++++
 migration/vmstate-types.c   | 136 ++++++++++++
 tests/test-vmstate.c        | 421 ++++++++++++++++++++++++++++++++++++
 3 files changed, 597 insertions(+)

Comments

Juan Quintela Oct. 4, 2019, 10:34 p.m. UTC | #1
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.
>
> If the key is a pointer to an object, 2 VMSDs 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 must be handled
> beforehand, for example in a pre_load method.
>
> 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>

Overal I like the patch.  I think that I found a minor error.


> +static int put_gtree(QEMUFile *f, void *pv, size_t unused_size,
> +                     const VMStateField *field, QJSON *vmdesc)
> +{
> +    bool direct_key = (!field->start);
> +    const VMStateDescription *key_vmsd = direct_key ? NULL : &field->vmsd[0];
> +    const VMStateDescription *val_vmsd = direct_key ? &field->vmsd[0] :
> +                                                      &field->vmsd[1];
> +    struct put_gtree_data capsule = {f, key_vmsd, val_vmsd, 0};

Please, consider change the last line to:

       struct put_gtree_data capsule = {
           .f = f,
           .key_vmsd = key_vmsd,
           .val_vmsd = val_vmsd,
           .ret = 0};

It makes much easier make changes on the future.

Once here, I think that you are missing on the middle a:

          .vmdesc = vmdesc,

No?  At least you use it on put_gtree_elem, and I don't see any place
where you assign it.  When I did the change is when I noticed that it
was missing.

> +    GTree **pval = pv;
> +    GTree *tree = *pval;
> +    int ret;
> +
> +    qemu_put_be32(f, g_tree_nnodes(tree));
> +    g_tree_foreach(tree, put_gtree_elem, (gpointer)&capsule);
> +    qemu_put_byte(f, false);
> +    ret = capsule.ret;
> +    if (ret) {
> +        error_report("%s : failed to save gtree (%d)", field->name, ret);
> +    }
> +    return ret;
> +}

As said before, with this changes you have my reviewed-by.

Later, Juan.
Peter Xu Oct. 9, 2019, 6:28 a.m. UTC | #2
On Fri, Oct 04, 2019 at 01:20:25PM +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.
> 
> If the key is a pointer to an object, 2 VMSDs 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 must be handled
> beforehand, for example in a pre_load method.
> 
> 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>

Mostly looks sane to me (with Juan's comment fixed).  Some more
trivial comments below.

> +/*
> + * For migrating a GTree whose key is a pointer to _key_type and the
> + * value, a pointer to _val_type
> + * The target tree must have been properly initialized
> + * _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
> + */
> +#define VMSTATE_GTREE_V(_field, _state, _version, _vmsd,                       \
> +                        _key_type, _val_type)                                  \
> +{                                                                              \
> +    .name         = (stringify(_field)),                                       \
> +    .version_id   = (_version),                                                \
> +    .vmsd         = (_vmsd),                                                   \
> +    .info         = &vmstate_info_gtree,                                       \
> +    .start        = sizeof(_key_type),                                         \

Nitpick: Are we reusing the "start" field to store the size just to
avoid defining new field in VMStateField?  If so, not sure whether we
can start to use unions to both keep VMStateField small while keep the
code clean.  Like:

  union {
    struct {
      size_t key_size;
      size_t value_size;
    };
    struct {
      size_t start;
      size_t size;
    };
  }

?

This can of course also be done on top of this patch no matter what.

[...]

> +static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
> +{
> +    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
> +    QEMUFile *f = capsule->f;
> +    int ret;
> +
> +    qemu_put_byte(f, true);
> +
> +    /* put the key */
> +    if (!capsule->key_vmsd) {
> +        qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */

This is special code path for direct key case.  Can we simply define
VMSTATE_GTREE_DIRECT_KEY_V() somehow better so that it just uses the
VMSTATE_UINT32_V() as the key vmsd?  Then iiuc vmstate_save_state()
could work well with that too.

Also, should we avoid using UINT in all cases?  But of course if we
start to use VMSTATE_UINT32_V then we don't have this issue.

Thanks,

> +    } else {
> +        ret = vmstate_save_state(f, capsule->key_vmsd, key, capsule->vmdesc);
> +        if (ret) {
> +            capsule->ret = ret;
> +            return true;
> +        }
> +    }
> +
> +    /* put the data */
> +    ret = vmstate_save_state(f, capsule->val_vmsd, value, capsule->vmdesc);
> +    if (ret) {
> +        capsule->ret = ret;
> +        return true;
> +    }
> +    return false;
> +}
Dr. David Alan Gilbert Oct. 9, 2019, 9:57 a.m. UTC | #3
* 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.
> 
> If the key is a pointer to an object, 2 VMSDs 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 must be handled
> beforehand, for example in a pre_load method.
> 
> 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>

Yes I think this is nice; only thing I'd add (other than Juan and
Peter's comments) is perhaps some tracing for when it all goes horribly
wrong!

Dave

> ---
> 
> v2 -> v3:
> - do not include glib.h anymore
> - introduce VMSTATE_GTREE_DIRECT_KEY_V
> - use pre_load to allocate the tree and remove data pointer
> - dump the number of nnodes and add checks on get path
> 
> 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 |  40 ++++
>  migration/vmstate-types.c   | 136 ++++++++++++
>  tests/test-vmstate.c        | 421 ++++++++++++++++++++++++++++++++++++
>  3 files changed, 597 insertions(+)
> 
> diff --git a/include/migration/vmstate.h b/include/migration/vmstate.h
> index 1fbfd099dd..98e5305d30 100644
> --- a/include/migration/vmstate.h
> +++ b/include/migration/vmstate.h
> @@ -224,6 +224,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 +755,45 @@ extern const VMStateInfo vmstate_info_qtailq;
>      .start        = offsetof(_type, _next),                              \
>  }
>  
> +/*
> + * For migrating a GTree whose key is a pointer to _key_type and the
> + * value, a pointer to _val_type
> + * The target tree must have been properly initialized
> + * _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
> + */
> +#define VMSTATE_GTREE_V(_field, _state, _version, _vmsd,                       \
> +                        _key_type, _val_type)                                  \
> +{                                                                              \
> +    .name         = (stringify(_field)),                                       \
> +    .version_id   = (_version),                                                \
> +    .vmsd         = (_vmsd),                                                   \
> +    .info         = &vmstate_info_gtree,                                       \
> +    .start        = sizeof(_key_type),                                         \
> +    .size         = sizeof(_val_type),                                         \
> +    .offset       = offsetof(_state, _field),                                  \
> +}
> +
> +/*
> + * For migrating a GTree whose key is a uint32 and the value a pointer
> + * to _val_type
> + * The target tree must have been properly initialized
> + * _vmsd: data vmsd
> + * _val_type: type of the value
> + */
> +#define VMSTATE_GTREE_DIRECT_KEY_V(_field, _state, _version, _vmsd, _val_type) \
> +{                                                                              \
> +    .name         = (stringify(_field)),                                       \
> +    .version_id   = (_version),                                                \
> +    .vmsd         = (_vmsd),                                                   \
> +    .info         = &vmstate_info_gtree,                                       \
> +    .start        = 0,                                                         \
> +    .size         = sizeof(_val_type),                                         \
> +    .offset       = offsetof(_state, _field),                                  \
> +}
> +
>  /* _f : field name
>     _f_n : num of elements field_name
>     _n : num of elements
> diff --git a/migration/vmstate-types.c b/migration/vmstate-types.c
> index bee658a1b2..cba8e660fe 100644
> --- a/migration/vmstate-types.c
> +++ b/migration/vmstate-types.c
> @@ -691,3 +691,139 @@ const VMStateInfo vmstate_info_qtailq = {
>      .get  = get_qtailq,
>      .put  = put_qtailq,
>  };
> +
> +struct put_gtree_data {
> +    QEMUFile *f;
> +    const VMStateDescription *key_vmsd;
> +    const VMStateDescription *val_vmsd;
> +    QJSON *vmdesc;
> +    int ret;
> +};
> +
> +static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
> +{
> +    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
> +    QEMUFile *f = capsule->f;
> +    int ret;
> +
> +    qemu_put_byte(f, true);
> +
> +    /* put the key */
> +    if (!capsule->key_vmsd) {
> +        qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
> +    } else {
> +        ret = vmstate_save_state(f, capsule->key_vmsd, key, capsule->vmdesc);
> +        if (ret) {
> +            capsule->ret = ret;
> +            return true;
> +        }
> +    }
> +
> +    /* put the data */
> +    ret = vmstate_save_state(f, capsule->val_vmsd, value, capsule->vmdesc);
> +    if (ret) {
> +        capsule->ret = ret;
> +        return true;
> +    }
> +    return false;
> +}
> +
> +static int put_gtree(QEMUFile *f, void *pv, size_t unused_size,
> +                     const VMStateField *field, QJSON *vmdesc)
> +{
> +    bool direct_key = (!field->start);
> +    const VMStateDescription *key_vmsd = direct_key ? NULL : &field->vmsd[0];
> +    const VMStateDescription *val_vmsd = direct_key ? &field->vmsd[0] :
> +                                                      &field->vmsd[1];
> +    struct put_gtree_data capsule = {f, key_vmsd, val_vmsd, 0};
> +    GTree **pval = pv;
> +    GTree *tree = *pval;
> +    int ret;
> +
> +    qemu_put_be32(f, g_tree_nnodes(tree));
> +    g_tree_foreach(tree, put_gtree_elem, (gpointer)&capsule);
> +    qemu_put_byte(f, false);
> +    ret = capsule.ret;
> +    if (ret) {
> +        error_report("%s : failed to save gtree (%d)", field->name, ret);
> +    }
> +    return ret;
> +}
> +
> +static int get_gtree(QEMUFile *f, void *pv, size_t unused_size,
> +                     const VMStateField *field)
> +{
> +    bool direct_key = (!field->start);
> +    const VMStateDescription *key_vmsd = direct_key ? NULL : &field->vmsd[0];
> +    const VMStateDescription *val_vmsd = direct_key ? &field->vmsd[0] :
> +                                                      &field->vmsd[1];
> +    int version_id = field->version_id;
> +    size_t key_size = field->start;
> +    size_t val_size = field->size;
> +    int nnodes, count = 0;
> +    GTree **pval = pv;
> +    GTree *tree = *pval;
> +    void *key, *val;
> +    int ret = 0;
> +
> +    /* in case of direct key, the key vmsd can be {}, ie. check fields */
> +    if (!direct_key && version_id > key_vmsd->version_id) {
> +        error_report("%s %s",  key_vmsd->name, "too new");
> +        return -EINVAL;
> +    }
> +    if (!direct_key && version_id < key_vmsd->minimum_version_id) {
> +        error_report("%s %s",  key_vmsd->name, "too old");
> +        return -EINVAL;
> +    }
> +    if (version_id > val_vmsd->version_id) {
> +        error_report("%s %s",  val_vmsd->name, "too new");
> +        return -EINVAL;
> +    }
> +    if (version_id < val_vmsd->minimum_version_id) {
> +        error_report("%s %s",  val_vmsd->name, "too old");
> +        return -EINVAL;
> +    }
> +
> +    nnodes = qemu_get_be32(f);
> +
> +    while (qemu_get_byte(f)) {
> +        if ((++count) > nnodes) {
> +            ret = -EINVAL;
> +            break;
> +        }
> +        if (direct_key) {
> +            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) {
> +                error_report("%s : failed to load %s (%d)",
> +                             field->name, key_vmsd->name, ret);
> +                g_free(key);
> +                return ret;
> +            }
> +        }
> +        val = g_malloc0(val_size);
> +        ret = vmstate_load_state(f, val_vmsd, val, version_id);
> +        if (ret) {
> +            error_report("%s : failed to load %s (%d)",
> +                         field->name, val_vmsd->name, ret);
> +            g_free(key);
> +            g_free(val);
> +            return ret;
> +        }
> +        g_tree_insert(tree, key, val);
> +    }
> +    if (count != nnodes) {
> +        error_report("%s inconsistent stream when loading the gtree",
> +                     field->name);
> +    }
> +    return ret;
> +}
> +
> +
> +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..0a1d976a19 100644
> --- a/tests/test-vmstate.c
> +++ b/tests/test-vmstate.c
> @@ -812,6 +812,423 @@ 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);
> +}
> +
> +static void destroy_domain(gpointer data)
> +{
> +    TestGTreeDomain *domain = (TestGTreeDomain *)data;
> +
> +    g_tree_destroy(domain->mappings);
> +    g_free(domain);
> +}
> +
> +static int domain_preload(void *opaque)
> +{
> +    TestGTreeDomain *domain = opaque;
> +
> +    domain->mappings = g_tree_new_full((GCompareDataFunc)interval_cmp,
> +                                       NULL, g_free, g_free);
> +    return 0;
> +}
> +
> +static int iommu_preload(void *opaque)
> +{
> +    TestGTreeIOMMU *iommu = opaque;
> +
> +    iommu->domains = g_tree_new_full((GCompareDataFunc)int_cmp,
> +                                     NULL, NULL, destroy_domain);
> +    return 0;
> +}
> +
> +static const VMStateDescription vmstate_domain = {
> +    .name = "domain",
> +    .version_id = 1,
> +    .minimum_version_id = 1,
> +    .pre_load = domain_preload,
> +    .fields = (VMStateField[]) {
> +        VMSTATE_INT32(id, TestGTreeDomain),
> +        VMSTATE_GTREE_V(mappings, TestGTreeDomain, 1,
> +                        vmstate_interval_mapping,
> +                        TestGTreeInterval, TestGTreeMapping),
> +        VMSTATE_END_OF_LIST()
> +    }
> +};
> +
> +static const VMStateDescription vmstate_iommu = {
> +    .name = "iommu",
> +    .version_id = 1,
> +    .minimum_version_id = 1,
> +    .pre_load = iommu_preload,
> +    .fields = (VMStateField[]) {
> +        VMSTATE_INT32(id, TestGTreeIOMMU),
> +        VMSTATE_GTREE_DIRECT_KEY_V(domains, TestGTreeIOMMU, 1,
> +                                   &vmstate_domain, TestGTreeDomain),
> +        VMSTATE_END_OF_LIST()
> +    }
> +};
> +
> +uint8_t first_domain_dump[] = {
> +    /* id */
> +    0x00, 0x0, 0x0, 0x6,
> +    0x00, 0x0, 0x0, 0x2, /* 2 mappings */
> +    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);
> +
> +    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,
> +    0x00, 0x0, 0x0, 0x2, /* 2 domains */
> +    0x1,/* start of domain 5 */
> +        0x00, 0x0, 0x0, 0x5, /* key = 5 */
> +        0x00, 0x0, 0x0, 0x5, /* domain1 id */
> +        0x00, 0x0, 0x0, 0x1, /* 1 mapping */
> +        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 */
> +            0x00, 0x0, 0x0, 0x2, /* 2 mappings */
> +            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 +1349,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();
>  
> -- 
> 2.20.1
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK
Auger Eric Oct. 10, 2019, 7:32 a.m. UTC | #4
Hi Juan,

On 10/5/19 12:34 AM, 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.
>>
>> If the key is a pointer to an object, 2 VMSDs 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 must be handled
>> beforehand, for example in a pre_load method.
>>
>> 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>
> 
> Overal I like the patch.  I think that I found a minor error.
> 
> 
>> +static int put_gtree(QEMUFile *f, void *pv, size_t unused_size,
>> +                     const VMStateField *field, QJSON *vmdesc)
>> +{
>> +    bool direct_key = (!field->start);
>> +    const VMStateDescription *key_vmsd = direct_key ? NULL : &field->vmsd[0];
>> +    const VMStateDescription *val_vmsd = direct_key ? &field->vmsd[0] :
>> +                                                      &field->vmsd[1];
>> +    struct put_gtree_data capsule = {f, key_vmsd, val_vmsd, 0};
> 
> Please, consider change the last line to:
> 
>        struct put_gtree_data capsule = {
>            .f = f,
>            .key_vmsd = key_vmsd,
>            .val_vmsd = val_vmsd,
>            .ret = 0};
> 
> It makes much easier make changes on the future.
> 
> Once here, I think that you are missing on the middle a:
> 
>           .vmdesc = vmdesc,
> 
> No?  At least you use it on put_gtree_elem, and I don't see any place
> where you assign it.  When I did the change is when I noticed that it
> was missing.

You are completely right. Thank you for catching this.

Eric
> 
>> +    GTree **pval = pv;
>> +    GTree *tree = *pval;
>> +    int ret;
>> +
>> +    qemu_put_be32(f, g_tree_nnodes(tree));
>> +    g_tree_foreach(tree, put_gtree_elem, (gpointer)&capsule);
>> +    qemu_put_byte(f, false);
>> +    ret = capsule.ret;
>> +    if (ret) {
>> +        error_report("%s : failed to save gtree (%d)", field->name, ret);
>> +    }
>> +    return ret;
>> +}
> 
> As said before, with this changes you have my reviewed-by.
> 
> Later, Juan.
>
Auger Eric Oct. 10, 2019, 7:57 a.m. UTC | #5
Hi Peter,

On 10/9/19 8:28 AM, Peter Xu wrote:
> On Fri, Oct 04, 2019 at 01:20:25PM +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.
>>
>> If the key is a pointer to an object, 2 VMSDs 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 must be handled
>> beforehand, for example in a pre_load method.
>>
>> 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>
> 
> Mostly looks sane to me (with Juan's comment fixed).  Some more
> trivial comments below.
> 
>> +/*
>> + * For migrating a GTree whose key is a pointer to _key_type and the
>> + * value, a pointer to _val_type
>> + * The target tree must have been properly initialized
>> + * _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
>> + */
>> +#define VMSTATE_GTREE_V(_field, _state, _version, _vmsd,                       \
>> +                        _key_type, _val_type)                                  \
>> +{                                                                              \
>> +    .name         = (stringify(_field)),                                       \
>> +    .version_id   = (_version),                                                \
>> +    .vmsd         = (_vmsd),                                                   \
>> +    .info         = &vmstate_info_gtree,                                       \
>> +    .start        = sizeof(_key_type),                                         \
> 
> Nitpick: Are we reusing the "start" field to store the size just to
> avoid defining new field in VMStateField?  If so, not sure whether we
> can start to use unions to both keep VMStateField small while keep the
> code clean.  Like:
> 
>   union {
>     struct {
>       size_t key_size;
>       size_t value_size;
>     };
>     struct {
>       size_t start;
>       size_t size;
>     };
>   }
Indeed that's the usage. I don't have a strong preference. Juan, Dave,
what do you prefer? keep it as it is or introduce unions?

> 
> ?
> 
> This can of course also be done on top of this patch no matter what.
> 
> [...]
> 
>> +static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
>> +{
>> +    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
>> +    QEMUFile *f = capsule->f;
>> +    int ret;
>> +
>> +    qemu_put_byte(f, true);
>> +
>> +    /* put the key */
>> +    if (!capsule->key_vmsd) {
>> +        qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
> 
> This is special code path for direct key case.  Can we simply define
> VMSTATE_GTREE_DIRECT_KEY_V() somehow better so that it just uses the
> VMSTATE_UINT32_V() as the key vmsd?  Then iiuc vmstate_save_state()
> could work well with that too.
if the key_vmsd is a VMSTATE_UINT32_V then I understand
vmstate_save_state(f, capsule->key_vmsd, key, capsule->vmdesc)
expects key to be a pointer to a uint32. But in that case of direct key,
it is a uint32. I don't figure out how to use vmstate_save_state in your
proposal.

> 
> Also, should we avoid using UINT in all cases?  But of course if we
> start to use VMSTATE_UINT32_V then we don't have this issue.
Depending on the clarification of above point, maybe I can rename
VMSTATE_GTREE_DIRECT_KEY_V into VMSTATE_GTREE_DIRECT_UINT_KEY_V

direct keys seem to be more common for hash tables actually.
https://developer.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-new-full

There are stand conversion macros to/from int, uint, size
https://developer.gnome.org/glib/stable/glib-Type-Conversion-Macros.html

Thanks

Eric

> 
> Thanks,
> 
>> +    } else {
>> +        ret = vmstate_save_state(f, capsule->key_vmsd, key, capsule->vmdesc);
>> +        if (ret) {
>> +            capsule->ret = ret;
>> +            return true;
>> +        }
>> +    }
>> +
>> +    /* put the data */
>> +    ret = vmstate_save_state(f, capsule->val_vmsd, value, capsule->vmdesc);
>> +    if (ret) {
>> +        capsule->ret = ret;
>> +        return true;
>> +    }
>> +    return false;
>> +}
>
Peter Xu Oct. 10, 2019, 11:35 a.m. UTC | #6
On Thu, Oct 10, 2019 at 09:57:01AM +0200, Auger Eric wrote:
> >> +static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
> >> +{
> >> +    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
> >> +    QEMUFile *f = capsule->f;
> >> +    int ret;
> >> +
> >> +    qemu_put_byte(f, true);
> >> +
> >> +    /* put the key */
> >> +    if (!capsule->key_vmsd) {
> >> +        qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
> > 
> > This is special code path for direct key case.  Can we simply define
> > VMSTATE_GTREE_DIRECT_KEY_V() somehow better so that it just uses the
> > VMSTATE_UINT32_V() as the key vmsd?  Then iiuc vmstate_save_state()
> > could work well with that too.
> if the key_vmsd is a VMSTATE_UINT32_V then I understand
> vmstate_save_state(f, capsule->key_vmsd, key, capsule->vmdesc)
> expects key to be a pointer to a uint32. But in that case of direct key,
> it is a uint32. I don't figure out how to use vmstate_save_state in your
> proposal.

Ah I see the point.  And indeed I can't think of a better way now
(e.g., maybe I will always try to use GTrees with malloc()ed keys to
be simple when I want to migrate a gtree, but yeah that's not a reason
to refuse this patch :).

Though we should be very careful on defining vmsds for GTrees in the
future with the help of this patch, and we must have the type (either
direct or not) to match the real usage of the tree otherwise QEMU can
potentially unreference the constant as a pointer.

> 
> > 
> > Also, should we avoid using UINT in all cases?  But of course if we
> > start to use VMSTATE_UINT32_V then we don't have this issue.
> Depending on the clarification of above point, maybe I can rename
> VMSTATE_GTREE_DIRECT_KEY_V into VMSTATE_GTREE_DIRECT_UINT_KEY_V
> 
> direct keys seem to be more common for hash tables actually.
> https://developer.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-new-full
> 
> There are stand conversion macros to/from int, uint, size
> https://developer.gnome.org/glib/stable/glib-Type-Conversion-Macros.html

Yeh it's fine to use direct keys.  Though my question was more about
"unsigned int" - here when we put, we cast a pointer into unsigned
int, which can be 2/4 bytes, IIUC.  I'm thinking whether at least we
should use direct cast (e.g., (uint32_t)ptr) to replace
GPOINTER_TO_UINT() to make sure it's 4 bytes.  Futher, maybe we should
start with uint64_t here in the migration stream, otherwise we should
probably drop the high 32 bits if we migrate a gtree whose key is 64
bits long (and since we're working with migration we won't be able to
change that in the future for compatibility reasons...).

Summary:

Maybe we can replace:

    qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */

To:

    qemu_put_be64(f, (uint64_t)key); /* direct key */

And apply similar thing to get() side?

Thanks,
Auger Eric Oct. 10, 2019, 12:11 p.m. UTC | #7
Hi Peter,

On 10/10/19 1:35 PM, Peter Xu wrote:
> On Thu, Oct 10, 2019 at 09:57:01AM +0200, Auger Eric wrote:
>>>> +static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
>>>> +{
>>>> +    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
>>>> +    QEMUFile *f = capsule->f;
>>>> +    int ret;
>>>> +
>>>> +    qemu_put_byte(f, true);
>>>> +
>>>> +    /* put the key */
>>>> +    if (!capsule->key_vmsd) {
>>>> +        qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
>>>
>>> This is special code path for direct key case.  Can we simply define
>>> VMSTATE_GTREE_DIRECT_KEY_V() somehow better so that it just uses the
>>> VMSTATE_UINT32_V() as the key vmsd?  Then iiuc vmstate_save_state()
>>> could work well with that too.
>> if the key_vmsd is a VMSTATE_UINT32_V then I understand
>> vmstate_save_state(f, capsule->key_vmsd, key, capsule->vmdesc)
>> expects key to be a pointer to a uint32. But in that case of direct key,
>> it is a uint32. I don't figure out how to use vmstate_save_state in your
>> proposal.
> 
> Ah I see the point.  And indeed I can't think of a better way now
> (e.g., maybe I will always try to use GTrees with malloc()ed keys to
> be simple when I want to migrate a gtree, but yeah that's not a reason
> to refuse this patch :).
> 
> Though we should be very careful on defining vmsds for GTrees in the
> future with the help of this patch, and we must have the type (either
> direct or not) to match the real usage of the tree otherwise QEMU can
> potentially unreference the constant as a pointer.
> 
>>
>>>
>>> Also, should we avoid using UINT in all cases?  But of course if we
>>> start to use VMSTATE_UINT32_V then we don't have this issue.
>> Depending on the clarification of above point, maybe I can rename
>> VMSTATE_GTREE_DIRECT_KEY_V into VMSTATE_GTREE_DIRECT_UINT_KEY_V
>>
>> direct keys seem to be more common for hash tables actually.
>> https://developer.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-new-full
>>
>> There are stand conversion macros to/from int, uint, size
>> https://developer.gnome.org/glib/stable/glib-Type-Conversion-Macros.html
> 
> Yeh it's fine to use direct keys.  Though my question was more about
> "unsigned int" - here when we put, we cast a pointer into unsigned
> int, which can be 2/4 bytes, IIUC.  I'm thinking whether at least we
> should use direct cast (e.g., (uint32_t)ptr) to replace
> GPOINTER_TO_UINT() to make sure it's 4 bytes.  Futher, maybe we should
> start with uint64_t here in the migration stream, otherwise we should
> probably drop the high 32 bits if we migrate a gtree whose key is 64
> bits long (and since we're working with migration we won't be able to
> change that in the future for compatibility reasons...).
> 
> Summary:
> 
> Maybe we can replace:
> 
>     qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
> 
> To:
> 
>     qemu_put_be64(f, (uint64_t)key); /* direct key */
> 
> And apply similar thing to get() side?

This was my first idea as well but I got stuck with a mingw compilation
issues if I remember correctly, trying to cast pointers to a wrong sized
uint. This got removed by using the GPOINTER_TO_UINT conversion functions.

Thanks

Eric
> 
> Thanks,
>
Peter Xu Oct. 10, 2019, 12:35 p.m. UTC | #8
On Thu, Oct 10, 2019 at 02:11:46PM +0200, Auger Eric wrote:
> >>> Also, should we avoid using UINT in all cases?  But of course if we
> >>> start to use VMSTATE_UINT32_V then we don't have this issue.
> >> Depending on the clarification of above point, maybe I can rename
> >> VMSTATE_GTREE_DIRECT_KEY_V into VMSTATE_GTREE_DIRECT_UINT_KEY_V
> >>
> >> direct keys seem to be more common for hash tables actually.
> >> https://developer.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-new-full
> >>
> >> There are stand conversion macros to/from int, uint, size
> >> https://developer.gnome.org/glib/stable/glib-Type-Conversion-Macros.html
> > 
> > Yeh it's fine to use direct keys.  Though my question was more about
> > "unsigned int" - here when we put, we cast a pointer into unsigned
> > int, which can be 2/4 bytes, IIUC.  I'm thinking whether at least we
> > should use direct cast (e.g., (uint32_t)ptr) to replace
> > GPOINTER_TO_UINT() to make sure it's 4 bytes.  Futher, maybe we should
> > start with uint64_t here in the migration stream, otherwise we should
> > probably drop the high 32 bits if we migrate a gtree whose key is 64
> > bits long (and since we're working with migration we won't be able to
> > change that in the future for compatibility reasons...).
> > 
> > Summary:
> > 
> > Maybe we can replace:
> > 
> >     qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
> > 
> > To:
> > 
> >     qemu_put_be64(f, (uint64_t)key); /* direct key */
> > 
> > And apply similar thing to get() side?
> 
> This was my first idea as well but I got stuck with a mingw compilation
> issues if I remember correctly, trying to cast pointers to a wrong sized
> uint. This got removed by using the GPOINTER_TO_UINT conversion functions.

#define GPOINTER_TO_UINT(p) ((guint) (gulong) (p))

Could "(uint64_t)(uintptr_t)pointer" do the work?

Thanks,
Auger Eric Oct. 10, 2019, 6:52 p.m. UTC | #9
Hi peter,

On 10/10/19 2:35 PM, Peter Xu wrote:
> On Thu, Oct 10, 2019 at 02:11:46PM +0200, Auger Eric wrote:
>>>>> Also, should we avoid using UINT in all cases?  But of course if we
>>>>> start to use VMSTATE_UINT32_V then we don't have this issue.
>>>> Depending on the clarification of above point, maybe I can rename
>>>> VMSTATE_GTREE_DIRECT_KEY_V into VMSTATE_GTREE_DIRECT_UINT_KEY_V
>>>>
>>>> direct keys seem to be more common for hash tables actually.
>>>> https://developer.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-new-full
>>>>
>>>> There are stand conversion macros to/from int, uint, size
>>>> https://developer.gnome.org/glib/stable/glib-Type-Conversion-Macros.html
>>>
>>> Yeh it's fine to use direct keys.  Though my question was more about
>>> "unsigned int" - here when we put, we cast a pointer into unsigned
>>> int, which can be 2/4 bytes, IIUC.  I'm thinking whether at least we
>>> should use direct cast (e.g., (uint32_t)ptr) to replace
>>> GPOINTER_TO_UINT() to make sure it's 4 bytes.  Futher, maybe we should
>>> start with uint64_t here in the migration stream, otherwise we should
>>> probably drop the high 32 bits if we migrate a gtree whose key is 64
>>> bits long (and since we're working with migration we won't be able to
>>> change that in the future for compatibility reasons...).
>>>
>>> Summary:
>>>
>>> Maybe we can replace:
>>>
>>>     qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
>>>
>>> To:
>>>
>>>     qemu_put_be64(f, (uint64_t)key); /* direct key */
>>>
>>> And apply similar thing to get() side?
>>
>> This was my first idea as well but I got stuck with a mingw compilation
>> issues if I remember correctly, trying to cast pointers to a wrong sized
>> uint. This got removed by using the GPOINTER_TO_UINT conversion functions.
> 
> #define GPOINTER_TO_UINT(p) ((guint) (gulong) (p))
> 
> Could "(uint64_t)(uintptr_t)pointer" do the work?
the problem rather is on the get side, when you cast the uint64_t value
into the pointer. it does not compile with

make docker-test-mingw@fedora


/tmp/qemu-test/src/migration/vmstate-types.c:800:19: error: cast to
pointer from integer of different size [-Werror=int-to-pointer-cast]
             key = (void *)(uint64_t)qemu_get_be64(f);

I would be tempted to rename the macro to emphasize the key is an
uint32. It should cover most of the use cases, no?

Thanks

Eric


> 
> Thanks,
>
Dr. David Alan Gilbert Oct. 10, 2019, 6:53 p.m. UTC | #10
* Auger Eric (eric.auger@redhat.com) wrote:
> Hi peter,
> 
> On 10/10/19 2:35 PM, Peter Xu wrote:
> > On Thu, Oct 10, 2019 at 02:11:46PM +0200, Auger Eric wrote:
> >>>>> Also, should we avoid using UINT in all cases?  But of course if we
> >>>>> start to use VMSTATE_UINT32_V then we don't have this issue.
> >>>> Depending on the clarification of above point, maybe I can rename
> >>>> VMSTATE_GTREE_DIRECT_KEY_V into VMSTATE_GTREE_DIRECT_UINT_KEY_V
> >>>>
> >>>> direct keys seem to be more common for hash tables actually.
> >>>> https://developer.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-new-full
> >>>>
> >>>> There are stand conversion macros to/from int, uint, size
> >>>> https://developer.gnome.org/glib/stable/glib-Type-Conversion-Macros.html
> >>>
> >>> Yeh it's fine to use direct keys.  Though my question was more about
> >>> "unsigned int" - here when we put, we cast a pointer into unsigned
> >>> int, which can be 2/4 bytes, IIUC.  I'm thinking whether at least we
> >>> should use direct cast (e.g., (uint32_t)ptr) to replace
> >>> GPOINTER_TO_UINT() to make sure it's 4 bytes.  Futher, maybe we should
> >>> start with uint64_t here in the migration stream, otherwise we should
> >>> probably drop the high 32 bits if we migrate a gtree whose key is 64
> >>> bits long (and since we're working with migration we won't be able to
> >>> change that in the future for compatibility reasons...).
> >>>
> >>> Summary:
> >>>
> >>> Maybe we can replace:
> >>>
> >>>     qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
> >>>
> >>> To:
> >>>
> >>>     qemu_put_be64(f, (uint64_t)key); /* direct key */
> >>>
> >>> And apply similar thing to get() side?
> >>
> >> This was my first idea as well but I got stuck with a mingw compilation
> >> issues if I remember correctly, trying to cast pointers to a wrong sized
> >> uint. This got removed by using the GPOINTER_TO_UINT conversion functions.
> > 
> > #define GPOINTER_TO_UINT(p) ((guint) (gulong) (p))
> > 
> > Could "(uint64_t)(uintptr_t)pointer" do the work?
> the problem rather is on the get side, when you cast the uint64_t value
> into the pointer. it does not compile with
> 
> make docker-test-mingw@fedora
> 
> 
> /tmp/qemu-test/src/migration/vmstate-types.c:800:19: error: cast to
> pointer from integer of different size [-Werror=int-to-pointer-cast]
>              key = (void *)(uint64_t)qemu_get_be64(f);
> 
> I would be tempted to rename the macro to emphasize the key is an
> uint32. It should cover most of the use cases, no?

Try:
    (void *)(uintptr_t)qemu_get_be64(f)


> 
> Thanks
> 
> Eric
> 
> 
> > 
> > Thanks,
> > 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK
Auger Eric Oct. 10, 2019, 7:42 p.m. UTC | #11
Hi,

On 10/10/19 8:53 PM, Dr. David Alan Gilbert wrote:
> * Auger Eric (eric.auger@redhat.com) wrote:
>> Hi peter,
>>
>> On 10/10/19 2:35 PM, Peter Xu wrote:
>>> On Thu, Oct 10, 2019 at 02:11:46PM +0200, Auger Eric wrote:
>>>>>>> Also, should we avoid using UINT in all cases?  But of course if we
>>>>>>> start to use VMSTATE_UINT32_V then we don't have this issue.
>>>>>> Depending on the clarification of above point, maybe I can rename
>>>>>> VMSTATE_GTREE_DIRECT_KEY_V into VMSTATE_GTREE_DIRECT_UINT_KEY_V
>>>>>>
>>>>>> direct keys seem to be more common for hash tables actually.
>>>>>> https://developer.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-new-full
>>>>>>
>>>>>> There are stand conversion macros to/from int, uint, size
>>>>>> https://developer.gnome.org/glib/stable/glib-Type-Conversion-Macros.html
>>>>>
>>>>> Yeh it's fine to use direct keys.  Though my question was more about
>>>>> "unsigned int" - here when we put, we cast a pointer into unsigned
>>>>> int, which can be 2/4 bytes, IIUC.  I'm thinking whether at least we
>>>>> should use direct cast (e.g., (uint32_t)ptr) to replace
>>>>> GPOINTER_TO_UINT() to make sure it's 4 bytes.  Futher, maybe we should
>>>>> start with uint64_t here in the migration stream, otherwise we should
>>>>> probably drop the high 32 bits if we migrate a gtree whose key is 64
>>>>> bits long (and since we're working with migration we won't be able to
>>>>> change that in the future for compatibility reasons...).
>>>>>
>>>>> Summary:
>>>>>
>>>>> Maybe we can replace:
>>>>>
>>>>>     qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
>>>>>
>>>>> To:
>>>>>
>>>>>     qemu_put_be64(f, (uint64_t)key); /* direct key */
>>>>>
>>>>> And apply similar thing to get() side?
>>>>
>>>> This was my first idea as well but I got stuck with a mingw compilation
>>>> issues if I remember correctly, trying to cast pointers to a wrong sized
>>>> uint. This got removed by using the GPOINTER_TO_UINT conversion functions.
>>>
>>> #define GPOINTER_TO_UINT(p) ((guint) (gulong) (p))
>>>
>>> Could "(uint64_t)(uintptr_t)pointer" do the work?
>> the problem rather is on the get side, when you cast the uint64_t value
>> into the pointer. it does not compile with
>>
>> make docker-test-mingw@fedora
>>
>>
>> /tmp/qemu-test/src/migration/vmstate-types.c:800:19: error: cast to
>> pointer from integer of different size [-Werror=int-to-pointer-cast]
>>              key = (void *)(uint64_t)qemu_get_be64(f);
>>
>> I would be tempted to rename the macro to emphasize the key is an
>> uint32. It should cover most of the use cases, no?
> 
> Try:
>     (void *)(uintptr_t)qemu_get_be64(f)
This indeed compiles with mingw. Thanks to both of you for the hint. I
was not familiar with uintptr_t.

Thanks

Eric
> 
> 
>>
>> Thanks
>>
>> Eric
>>
>>
>>>
>>> Thanks,
>>>
> --
> Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK
>

Patch
diff mbox series

diff --git a/include/migration/vmstate.h b/include/migration/vmstate.h
index 1fbfd099dd..98e5305d30 100644
--- a/include/migration/vmstate.h
+++ b/include/migration/vmstate.h
@@ -224,6 +224,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 +755,45 @@  extern const VMStateInfo vmstate_info_qtailq;
     .start        = offsetof(_type, _next),                              \
 }
 
+/*
+ * For migrating a GTree whose key is a pointer to _key_type and the
+ * value, a pointer to _val_type
+ * The target tree must have been properly initialized
+ * _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
+ */
+#define VMSTATE_GTREE_V(_field, _state, _version, _vmsd,                       \
+                        _key_type, _val_type)                                  \
+{                                                                              \
+    .name         = (stringify(_field)),                                       \
+    .version_id   = (_version),                                                \
+    .vmsd         = (_vmsd),                                                   \
+    .info         = &vmstate_info_gtree,                                       \
+    .start        = sizeof(_key_type),                                         \
+    .size         = sizeof(_val_type),                                         \
+    .offset       = offsetof(_state, _field),                                  \
+}
+
+/*
+ * For migrating a GTree whose key is a uint32 and the value a pointer
+ * to _val_type
+ * The target tree must have been properly initialized
+ * _vmsd: data vmsd
+ * _val_type: type of the value
+ */
+#define VMSTATE_GTREE_DIRECT_KEY_V(_field, _state, _version, _vmsd, _val_type) \
+{                                                                              \
+    .name         = (stringify(_field)),                                       \
+    .version_id   = (_version),                                                \
+    .vmsd         = (_vmsd),                                                   \
+    .info         = &vmstate_info_gtree,                                       \
+    .start        = 0,                                                         \
+    .size         = sizeof(_val_type),                                         \
+    .offset       = offsetof(_state, _field),                                  \
+}
+
 /* _f : field name
    _f_n : num of elements field_name
    _n : num of elements
diff --git a/migration/vmstate-types.c b/migration/vmstate-types.c
index bee658a1b2..cba8e660fe 100644
--- a/migration/vmstate-types.c
+++ b/migration/vmstate-types.c
@@ -691,3 +691,139 @@  const VMStateInfo vmstate_info_qtailq = {
     .get  = get_qtailq,
     .put  = put_qtailq,
 };
+
+struct put_gtree_data {
+    QEMUFile *f;
+    const VMStateDescription *key_vmsd;
+    const VMStateDescription *val_vmsd;
+    QJSON *vmdesc;
+    int ret;
+};
+
+static gboolean put_gtree_elem(gpointer key, gpointer value, gpointer data)
+{
+    struct put_gtree_data *capsule = (struct put_gtree_data *)data;
+    QEMUFile *f = capsule->f;
+    int ret;
+
+    qemu_put_byte(f, true);
+
+    /* put the key */
+    if (!capsule->key_vmsd) {
+        qemu_put_be32(f, GPOINTER_TO_UINT(key)); /* direct key */
+    } else {
+        ret = vmstate_save_state(f, capsule->key_vmsd, key, capsule->vmdesc);
+        if (ret) {
+            capsule->ret = ret;
+            return true;
+        }
+    }
+
+    /* put the data */
+    ret = vmstate_save_state(f, capsule->val_vmsd, value, capsule->vmdesc);
+    if (ret) {
+        capsule->ret = ret;
+        return true;
+    }
+    return false;
+}
+
+static int put_gtree(QEMUFile *f, void *pv, size_t unused_size,
+                     const VMStateField *field, QJSON *vmdesc)
+{
+    bool direct_key = (!field->start);
+    const VMStateDescription *key_vmsd = direct_key ? NULL : &field->vmsd[0];
+    const VMStateDescription *val_vmsd = direct_key ? &field->vmsd[0] :
+                                                      &field->vmsd[1];
+    struct put_gtree_data capsule = {f, key_vmsd, val_vmsd, 0};
+    GTree **pval = pv;
+    GTree *tree = *pval;
+    int ret;
+
+    qemu_put_be32(f, g_tree_nnodes(tree));
+    g_tree_foreach(tree, put_gtree_elem, (gpointer)&capsule);
+    qemu_put_byte(f, false);
+    ret = capsule.ret;
+    if (ret) {
+        error_report("%s : failed to save gtree (%d)", field->name, ret);
+    }
+    return ret;
+}
+
+static int get_gtree(QEMUFile *f, void *pv, size_t unused_size,
+                     const VMStateField *field)
+{
+    bool direct_key = (!field->start);
+    const VMStateDescription *key_vmsd = direct_key ? NULL : &field->vmsd[0];
+    const VMStateDescription *val_vmsd = direct_key ? &field->vmsd[0] :
+                                                      &field->vmsd[1];
+    int version_id = field->version_id;
+    size_t key_size = field->start;
+    size_t val_size = field->size;
+    int nnodes, count = 0;
+    GTree **pval = pv;
+    GTree *tree = *pval;
+    void *key, *val;
+    int ret = 0;
+
+    /* in case of direct key, the key vmsd can be {}, ie. check fields */
+    if (!direct_key && version_id > key_vmsd->version_id) {
+        error_report("%s %s",  key_vmsd->name, "too new");
+        return -EINVAL;
+    }
+    if (!direct_key && version_id < key_vmsd->minimum_version_id) {
+        error_report("%s %s",  key_vmsd->name, "too old");
+        return -EINVAL;
+    }
+    if (version_id > val_vmsd->version_id) {
+        error_report("%s %s",  val_vmsd->name, "too new");
+        return -EINVAL;
+    }
+    if (version_id < val_vmsd->minimum_version_id) {
+        error_report("%s %s",  val_vmsd->name, "too old");
+        return -EINVAL;
+    }
+
+    nnodes = qemu_get_be32(f);
+
+    while (qemu_get_byte(f)) {
+        if ((++count) > nnodes) {
+            ret = -EINVAL;
+            break;
+        }
+        if (direct_key) {
+            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) {
+                error_report("%s : failed to load %s (%d)",
+                             field->name, key_vmsd->name, ret);
+                g_free(key);
+                return ret;
+            }
+        }
+        val = g_malloc0(val_size);
+        ret = vmstate_load_state(f, val_vmsd, val, version_id);
+        if (ret) {
+            error_report("%s : failed to load %s (%d)",
+                         field->name, val_vmsd->name, ret);
+            g_free(key);
+            g_free(val);
+            return ret;
+        }
+        g_tree_insert(tree, key, val);
+    }
+    if (count != nnodes) {
+        error_report("%s inconsistent stream when loading the gtree",
+                     field->name);
+    }
+    return ret;
+}
+
+
+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..0a1d976a19 100644
--- a/tests/test-vmstate.c
+++ b/tests/test-vmstate.c
@@ -812,6 +812,423 @@  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);
+}
+
+static void destroy_domain(gpointer data)
+{
+    TestGTreeDomain *domain = (TestGTreeDomain *)data;
+
+    g_tree_destroy(domain->mappings);
+    g_free(domain);
+}
+
+static int domain_preload(void *opaque)
+{
+    TestGTreeDomain *domain = opaque;
+
+    domain->mappings = g_tree_new_full((GCompareDataFunc)interval_cmp,
+                                       NULL, g_free, g_free);
+    return 0;
+}
+
+static int iommu_preload(void *opaque)
+{
+    TestGTreeIOMMU *iommu = opaque;
+
+    iommu->domains = g_tree_new_full((GCompareDataFunc)int_cmp,
+                                     NULL, NULL, destroy_domain);
+    return 0;
+}
+
+static const VMStateDescription vmstate_domain = {
+    .name = "domain",
+    .version_id = 1,
+    .minimum_version_id = 1,
+    .pre_load = domain_preload,
+    .fields = (VMStateField[]) {
+        VMSTATE_INT32(id, TestGTreeDomain),
+        VMSTATE_GTREE_V(mappings, TestGTreeDomain, 1,
+                        vmstate_interval_mapping,
+                        TestGTreeInterval, TestGTreeMapping),
+        VMSTATE_END_OF_LIST()
+    }
+};
+
+static const VMStateDescription vmstate_iommu = {
+    .name = "iommu",
+    .version_id = 1,
+    .minimum_version_id = 1,
+    .pre_load = iommu_preload,
+    .fields = (VMStateField[]) {
+        VMSTATE_INT32(id, TestGTreeIOMMU),
+        VMSTATE_GTREE_DIRECT_KEY_V(domains, TestGTreeIOMMU, 1,
+                                   &vmstate_domain, TestGTreeDomain),
+        VMSTATE_END_OF_LIST()
+    }
+};
+
+uint8_t first_domain_dump[] = {
+    /* id */
+    0x00, 0x0, 0x0, 0x6,
+    0x00, 0x0, 0x0, 0x2, /* 2 mappings */
+    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);
+
+    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,
+    0x00, 0x0, 0x0, 0x2, /* 2 domains */
+    0x1,/* start of domain 5 */
+        0x00, 0x0, 0x0, 0x5, /* key = 5 */
+        0x00, 0x0, 0x0, 0x5, /* domain1 id */
+        0x00, 0x0, 0x0, 0x1, /* 1 mapping */
+        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 */
+            0x00, 0x0, 0x0, 0x2, /* 2 mappings */
+            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 +1349,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();