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

[David Gibson]

On Tue, Oct 06, 2015 at 03:02:17PM +0200, Laszlo Ersek wrote:
> David,
> 
> On 10/06/15 14:41, 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 <address@hidden>
> > ---
> >  include/qom/object.h |  4 +--
> >  qmp.c                |  8 +++--
> >  qom/object.c         | 98 
> > +++++++++++++++++++++++-----------------------------
> >  vl.c                 |  4 ++-
> >  4 files changed, 54 insertions(+), 60 deletions(-)
> 
> Shouldn't this help similarly with the problem that 94649d423e worked
> around? (Although that patch has standalone merits of course.)

Yes it will.  The change to hash table would reduce my nasty O(n^3) case
to O(n^2) without 94649d423e, and to O(n) with it..

> 
> Thanks
> Laszlo
> 
> > 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..9649243 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->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;
> >          }
> > 
> 
> 

-- 
David Gibson                    | I'll have my music baroque, and my code
david AT gibson.dropbear.id.au  | minimalist, thank you.  NOT _the_ _other_
                                | _way_ _around_!
http://www.ozlabs.org/~dgibson

signature.asc
Description: PGP signature