[Qemu-devel] [PATCH v2] qobject: Replace property list with GHashTable

[Qemu-devel] [PATCH v2] qobject: Replace property list with GHashTable

[Pavel Fedin]

ARM GICv3 systems with large number of CPUs create lots of IRQ pins. Since
every pin is represented as a property, number of these properties becomes
very large. Every property add first makes sure there's no duplicates.
Traversing the list becomes very slow, therefore qemu initialization takes
significant time (several seconds for e. g. 16 CPUs).

This patch replaces list with GHashTable, making lookup very fast. The only
drawback is that object_child_foreach() and object_child_foreach_recursive()
cannot modify their objects during traversal, since GHashTableIter does not
have modify-safe version. However, the code seems not to modify objects via
these functions.

Signed-off-by: Pavel Fedin <p.fedin@samsung.com>
---
v1 => v2:
- Fixed stupid bug in object_unparent(), use correct object
---
 include/qom/object.h |  4 +--
 qmp.c                |  8 +++--
 qom/object.c         | 98 +++++++++++++++++++++++-----------------------------
 vl.c                 |  4 ++-
 4 files changed, 54 insertions(+), 60 deletions(-)

diff --git a/include/qom/object.h b/include/qom/object.h
index be7280c..b100923 100644
--- a/include/qom/object.h
+++ b/include/qom/object.h
@@ -345,7 +345,7 @@ typedef struct ObjectProperty
     ObjectPropertyRelease *release;
     void *opaque;
 
-    QTAILQ_ENTRY(ObjectProperty) node;
+    Object *obj;
 } ObjectProperty;
 
 /**
@@ -405,7 +405,7 @@ struct Object
     /*< private >*/
     ObjectClass *class;
     ObjectFree *free;
-    QTAILQ_HEAD(, ObjectProperty) properties;
+    GHashTable *properties;
     uint32_t ref;
     Object *parent;
 };
diff --git a/qmp.c b/qmp.c
index 057a7cb..683f427 100644
--- a/qmp.c
+++ b/qmp.c
@@ -207,6 +207,7 @@ ObjectPropertyInfoList *qmp_qom_list(const char *path, Error **errp)
     Object *obj;
     bool ambiguous = false;
     ObjectPropertyInfoList *props = NULL;
+    GHashTableIter iter;
     ObjectProperty *prop;
 
     obj = object_resolve_path(path, &ambiguous);
@@ -220,7 +221,8 @@ ObjectPropertyInfoList *qmp_qom_list(const char *path, Error **errp)
         return NULL;
     }
 
-    QTAILQ_FOREACH(prop, &obj->properties, node) {
+    g_hash_table_iter_init(&iter, obj->properties);
+    while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) {
         ObjectPropertyInfoList *entry = g_malloc0(sizeof(*entry));
 
         entry->value = g_malloc0(sizeof(ObjectPropertyInfo));
@@ -499,6 +501,7 @@ DevicePropertyInfoList *qmp_device_list_properties(const char *typename,
 {
     ObjectClass *klass;
     Object *obj;
+    GHashTableIter iter;
     ObjectProperty *prop;
     DevicePropertyInfoList *prop_list = NULL;
 
@@ -517,7 +520,8 @@ DevicePropertyInfoList *qmp_device_list_properties(const char *typename,
 
     obj = object_new(typename);
 
-    QTAILQ_FOREACH(prop, &obj->properties, node) {
+    g_hash_table_iter_init(&iter, obj->properties);
+    while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) {
         DevicePropertyInfo *info;
         DevicePropertyInfoList *entry;
 
diff --git a/qom/object.c b/qom/object.c
index 4805328..1c7c42a 100644
--- a/qom/object.c
+++ b/qom/object.c
@@ -326,6 +326,20 @@ static void object_post_init_with_type(Object *obj, TypeImpl *ti)
     }
 }
 
+static void property_destroy(gpointer data)
+{
+    ObjectProperty *prop = data;
+
+    if (prop->release) {
+        prop->release(prop->obj, prop->name, prop->opaque);
+    }
+
+    g_free(prop->name);
+    g_free(prop->type);
+    g_free(prop->description);
+    g_free(prop);
+}
+
 void object_initialize_with_type(void *data, size_t size, TypeImpl *type)
 {
     Object *obj = data;
@@ -340,7 +354,8 @@ void object_initialize_with_type(void *data, size_t size, TypeImpl *type)
     memset(obj, 0, type->instance_size);
     obj->class = type->class;
     object_ref(obj);
-    QTAILQ_INIT(&obj->properties);
+    obj->properties = g_hash_table_new_full(g_str_hash, g_str_equal,
+                                            NULL, property_destroy);
     object_init_with_type(obj, type);
     object_post_init_with_type(obj, type);
 }
@@ -357,40 +372,19 @@ static inline bool object_property_is_child(ObjectProperty *prop)
     return strstart(prop->type, "child<", NULL);
 }
 
-static void object_property_del_all(Object *obj)
+static gboolean object_property_del_child(gpointer key, gpointer value,
+                                          gpointer child)
 {
-    while (!QTAILQ_EMPTY(&obj->properties)) {
-        ObjectProperty *prop = QTAILQ_FIRST(&obj->properties);
-
-        QTAILQ_REMOVE(&obj->properties, prop, node);
+    ObjectProperty *prop = value;
 
-        if (prop->release) {
-            prop->release(obj, prop->name, prop->opaque);
-        }
-
-        g_free(prop->name);
-        g_free(prop->type);
-        g_free(prop->description);
-        g_free(prop);
-    }
-}
-
-static void object_property_del_child(Object *obj, Object *child, Error **errp)
-{
-    ObjectProperty *prop;
-
-    QTAILQ_FOREACH(prop, &obj->properties, node) {
-        if (object_property_is_child(prop) && prop->opaque == child) {
-            object_property_del(obj, prop->name, errp);
-            break;
-        }
-    }
+    return object_property_is_child(prop) && prop->opaque == child;
 }
 
 void object_unparent(Object *obj)
 {
     if (obj->parent) {
-        object_property_del_child(obj->parent, obj, NULL);
+        g_hash_table_foreach_remove(obj->parent->properties,
+                                    object_property_del_child, obj);
     }
 }
 
@@ -410,7 +404,7 @@ static void object_finalize(void *data)
     Object *obj = data;
     TypeImpl *ti = obj->class->type;
 
-    object_property_del_all(obj);
+    g_hash_table_unref(obj->properties);
     object_deinit(obj, ti);
 
     g_assert(obj->ref == 0);
@@ -779,10 +773,12 @@ static int do_object_child_foreach(Object *obj,
                                    int (*fn)(Object *child, void *opaque),
                                    void *opaque, bool recurse)
 {
-    ObjectProperty *prop, *next;
+    GHashTableIter iter;
+    ObjectProperty *prop;
     int ret = 0;
 
-    QTAILQ_FOREACH_SAFE(prop, &obj->properties, node, next) {
+    g_hash_table_iter_init(&iter, obj->properties);
+    while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) {
         if (object_property_is_child(prop)) {
             Object *child = prop->opaque;
 
@@ -879,13 +875,11 @@ object_property_add(Object *obj, const char *name, const char *type,
         return ret;
     }
 
-    QTAILQ_FOREACH(prop, &obj->properties, node) {
-        if (strcmp(prop->name, name) == 0) {
-            error_setg(errp, "attempt to add duplicate property '%s'"
+    if (g_hash_table_contains(obj->properties, name)) {
+        error_setg(errp, "attempt to add duplicate property '%s'"
                        " to object (type '%s')", name,
                        object_get_typename(obj));
-            return NULL;
-        }
+        return NULL;
     }
 
     prop = g_malloc0(sizeof(*prop));
@@ -897,8 +891,9 @@ object_property_add(Object *obj, const char *name, const char *type,
     prop->set = set;
     prop->release = release;
     prop->opaque = opaque;
+    prop->obj = obj;
 
-    QTAILQ_INSERT_TAIL(&obj->properties, prop, node);
+    g_hash_table_insert(obj->properties, prop->name, prop);
     return prop;
 }
 
@@ -907,10 +902,9 @@ ObjectProperty *object_property_find(Object *obj, const char *name,
 {
     ObjectProperty *prop;
 
-    QTAILQ_FOREACH(prop, &obj->properties, node) {
-        if (strcmp(prop->name, name) == 0) {
-            return prop;
-        }
+    prop = g_hash_table_lookup(obj->properties, name);
+    if (prop) {
+        return prop;
     }
 
     error_setg(errp, "Property '.%s' not found", name);
@@ -919,21 +913,11 @@ ObjectProperty *object_property_find(Object *obj, const char *name,
 
 void object_property_del(Object *obj, const char *name, Error **errp)
 {
-    ObjectProperty *prop = object_property_find(obj, name, errp);
-    if (prop == NULL) {
+    if (g_hash_table_remove(obj->properties, name)) {
         return;
     }
 
-    if (prop->release) {
-        prop->release(obj, name, prop->opaque);
-    }
-
-    QTAILQ_REMOVE(&obj->properties, prop, node);
-
-    g_free(prop->name);
-    g_free(prop->type);
-    g_free(prop->description);
-    g_free(prop);
+    error_setg(errp, "Property '.%s' not found", name);
 }
 
 void object_property_get(Object *obj, Visitor *v, const char *name,
@@ -1453,11 +1437,13 @@ void object_property_add_const_link(Object *obj, const char *name,
 gchar *object_get_canonical_path_component(Object *obj)
 {
     ObjectProperty *prop = NULL;
+    GHashTableIter iter;
 
     g_assert(obj);
     g_assert(obj->parent != NULL);
 
-    QTAILQ_FOREACH(prop, &obj->parent->properties, node) {
+    g_hash_table_iter_init(&iter, obj->parent->properties);
+    while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) {
         if (!object_property_is_child(prop)) {
             continue;
         }
@@ -1541,11 +1527,13 @@ static Object *object_resolve_partial_path(Object *parent,
                                               bool *ambiguous)
 {
     Object *obj;
+    GHashTableIter iter;
     ObjectProperty *prop;
 
     obj = object_resolve_abs_path(parent, parts, typename, 0);
 
-    QTAILQ_FOREACH(prop, &parent->properties, node) {
+    g_hash_table_iter_init(&iter, parent->properties);
+    while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) {
         Object *found;
 
         if (!object_property_is_child(prop)) {
diff --git a/vl.c b/vl.c
index e211f6a..7065d5f 100644
--- a/vl.c
+++ b/vl.c
@@ -1506,13 +1506,15 @@ MachineInfoList *qmp_query_machines(Error **errp)
 
 static int machine_help_func(QemuOpts *opts, MachineState *machine)
 {
+    GHashTableIter iter;
     ObjectProperty *prop;
 
     if (!qemu_opt_has_help_opt(opts)) {
         return 0;
     }
 
-    QTAILQ_FOREACH(prop, &OBJECT(machine)->properties, node) {
+    g_hash_table_iter_init(&iter, OBJECT(machine)->properties);
+    while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) {
         if (!prop->set) {
             continue;
         }
-- 
1.9.5.msysgit.0

Re: [Qemu-devel] [PATCH v2] qobject: Replace property list with GHashTable

[Daniel P. Berrange]

Nit-pick on subject line - s/qobject/qom/ and also copy
Andreas Färber on the patch, since he's the primary
maintainer of the QOM subsystem.

On Tue, Oct 06, 2015 at 04:48:53PM +0300, Pavel Fedin wrote:
> ARM GICv3 systems with large number of CPUs create lots of IRQ pins. Since
> every pin is represented as a property, number of these properties becomes
> very large. Every property add first makes sure there's no duplicates.
> Traversing the list becomes very slow, therefore qemu initialization takes
> significant time (several seconds for e. g. 16 CPUs).
> 
> This patch replaces list with GHashTable, making lookup very fast. The only
> drawback is that object_child_foreach() and object_child_foreach_recursive()
> cannot modify their objects during traversal, since GHashTableIter does not
> have modify-safe version. However, the code seems not to modify objects via
> these functions.
> 
> Signed-off-by: Pavel Fedin <p.fedin@samsung.com>
> ---
> v1 => v2:
> - Fixed stupid bug in object_unparent(), use correct object
> ---
>  include/qom/object.h |  4 +--
>  qmp.c                |  8 +++--
>  qom/object.c         | 98 +++++++++++++++++++++++-----------------------------
>  vl.c                 |  4 ++-
>  4 files changed, 54 insertions(+), 60 deletions(-)
> 
> diff --git a/include/qom/object.h b/include/qom/object.h
> index be7280c..b100923 100644
> --- a/include/qom/object.h
> +++ b/include/qom/object.h
> @@ -345,7 +345,7 @@ typedef struct ObjectProperty
>      ObjectPropertyRelease *release;
>      void *opaque;
>  
> -    QTAILQ_ENTRY(ObjectProperty) node;
> +    Object *obj;

I have a patch which adds property registration against the
class, so requiring ObjectProperty to have a back-poointer
to an object instance is not desirable.

> diff --git a/qom/object.c b/qom/object.c
> index 4805328..1c7c42a 100644
> --- a/qom/object.c
> +++ b/qom/object.c
> @@ -326,6 +326,20 @@ static void object_post_init_with_type(Object *obj, TypeImpl *ti)
>      }
>  }
>  
> +static void property_destroy(gpointer data)
> +{
> +    ObjectProperty *prop = data;
> +
> +    if (prop->release) {
> +        prop->release(prop->obj, prop->name, prop->opaque);
> +    }

Instead of calling the release() callback here, use a hash iterator
to call it from the object_finalize() method, before unref'ing the
hash table, and also call it from objecT_property_del directly. That
way you don't need to store the Object * back pointer in the
ObjectProperty struct.

> +
> +    g_free(prop->name);
> +    g_free(prop->type);
> +    g_free(prop->description);
> +    g_free(prop);
> +}

> @@ -410,7 +404,7 @@ static void object_finalize(void *data)
>      Object *obj = data;
>      TypeImpl *ti = obj->class->type;
>  
> -    object_property_del_all(obj);
> +    g_hash_table_unref(obj->properties);
>      object_deinit(obj, ti);
>  
>      g_assert(obj->ref == 0);

>  void object_property_del(Object *obj, const char *name, Error **errp)
>  {
> -    ObjectProperty *prop = object_property_find(obj, name, errp);
> -    if (prop == NULL) {
> +    if (g_hash_table_remove(obj->properties, name)) {
>          return;
>      }
>  
> -    if (prop->release) {
> -        prop->release(obj, name, prop->opaque);
> -    }
> -
> -    QTAILQ_REMOVE(&obj->properties, prop, node);
> -
> -    g_free(prop->name);
> -    g_free(prop->type);
> -    g_free(prop->description);
> -    g_free(prop);
> +    error_setg(errp, "Property '.%s' not found", name);
>  }

Overall I think this is a good improvement to make

Regards,
Daniel
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org       -o-       http://live.gnome.org/gtk-vnc :|