Re: [Qemu-devel] [PATCH v3 4/5] qom: replace object property list with GHashTable

[Pavel Fedin]

 Hello!

> -----Original Message-----
> From: Daniel P. Berrange [mailto:address@hidden
> Sent: Thursday, October 08, 2015 5:09 PM
> To: address@hidden
> Cc: Andreas Färber; Pavel Fedin; Daniel P. Berrange
> Subject: [PATCH v3 4/5] qom: replace object property list with GHashTable
> 
> From: Pavel Fedin <address@hidden>
> 
> 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: Daniel P. Berrange <address@hidden>
> ---
>  include/qom/object.h | 10 ++++--
>  qom/object.c         | 94 
> +++++++++++++++++++++++++++++++---------------------
>  2 files changed, 63 insertions(+), 41 deletions(-)
> 
> diff --git a/include/qom/object.h b/include/qom/object.h
> index 71503af..7645f5f 100644
> --- a/include/qom/object.h
> +++ b/include/qom/object.h
> @@ -344,8 +344,6 @@ typedef struct ObjectProperty
>      ObjectPropertyResolve *resolve;
>      ObjectPropertyRelease *release;
>      void *opaque;
> -
> -    QTAILQ_ENTRY(ObjectProperty) node;
>  } ObjectProperty;
> 
>  /**
> @@ -405,7 +403,7 @@ struct Object
>      /*< private >*/
>      ObjectClass *class;
>      ObjectFree *free;
> -    QTAILQ_HEAD(, ObjectProperty) properties;
> +    GHashTable *properties;
>      uint32_t ref;
>      Object *parent;
>  };
> @@ -1511,6 +1509,9 @@ void object_property_set_description(Object *obj, const 
> char *name,
>   * Call @fn passing each child of @obj and @opaque to it, until @fn returns
>   * non-zero.
>   *
> + * It is forbidden to add or remove children from @obj from the @fn
> + * callback.
> + *
>   * Returns: The last value returned by @fn, or 0 if there is no child.
>   */
>  int object_child_foreach(Object *obj, int (*fn)(Object *child, void *opaque),
> @@ -1526,6 +1527,9 @@ int object_child_foreach(Object *obj, int (*fn)(Object 
> *child, void
> *opaque),
>   * non-zero. Calls recursively, all child nodes of @obj will also be passed
>   * all the way down to the leaf nodes of the tree. Depth first ordering.
>   *
> + * It is forbidden to add or remove children from @obj (or its
> + * child nodes) from the @fn callback.
> + *
>   * Returns: The last value returned by @fn, or 0 if there is no child.
>   */
>  int object_child_foreach_recursive(Object *obj,
> diff --git a/qom/object.c b/qom/object.c
> index f8b27af..7cec1c9 100644
> --- a/qom/object.c
> +++ b/qom/object.c
> @@ -326,6 +326,16 @@ static void object_post_init_with_type(Object *obj, 
> TypeImpl *ti)
>      }
>  }
> 
> +static void property_free(gpointer data)
> +{
> +    ObjectProperty *prop = data;
> +
> +    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 +350,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_free);
>      object_init_with_type(obj, type);
>      object_post_init_with_type(obj, type);
>  }
> @@ -359,29 +370,35 @@ static inline bool 
> object_property_is_child(ObjectProperty *prop)
> 
>  static void object_property_del_all(Object *obj)
>  {
> -    while (!QTAILQ_EMPTY(&obj->properties)) {
> -        ObjectProperty *prop = QTAILQ_FIRST(&obj->properties);
> -
> -        QTAILQ_REMOVE(&obj->properties, prop, node);
> +    ObjectProperty *prop;
> +    GHashTableIter iter;
> +    gpointer key, value;
> 
> +    g_hash_table_iter_init(&iter, obj->properties);
> +    while (g_hash_table_iter_next(&iter, &key, &value)) {
> +        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);
>      }
> +
> +    g_hash_table_unref(obj->properties);
>  }
> 
>  static void object_property_del_child(Object *obj, Object *child, Error 
> **errp)
>  {
>      ObjectProperty *prop;
> +    GHashTableIter iter;
> +    gpointer key, value;
> 
> -    QTAILQ_FOREACH(prop, &obj->properties, node) {
> +    g_hash_table_iter_init(&iter, obj->properties);
> +    while (g_hash_table_iter_next(&iter, &key, &value)) {
> +        prop = value;
>          if (object_property_is_child(prop) && prop->opaque == child) {
> -            object_property_del(obj, prop->name, errp);
> +            if (prop->release) {
> +                prop->release(obj, prop->name, prop->opaque);
> +            }
> +            g_hash_table_iter_remove(&iter);
>              break;
>          }
>      }
> @@ -779,10 +796,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 +898,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));
> @@ -898,7 +915,7 @@ object_property_add(Object *obj, const char *name, const 
> char *type,
>      prop->release = release;
>      prop->opaque = opaque;
> 
> -    QTAILQ_INSERT_TAIL(&obj->properties, prop, node);
> +    g_hash_table_insert(obj->properties, prop->name, prop);
>      return prop;
>  }
> 
> @@ -907,10 +924,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);
> @@ -922,11 +938,13 @@ void object_property_foreach(Object *obj,
>                               Error **errp,
>                               void *opaque)
>  {
> -    ObjectProperty *prop;
>      Error *local_err = NULL;
> +    GHashTableIter props;
> +    gpointer key, value;
> 
> -    QTAILQ_FOREACH(prop, &obj->properties, node) {
> -        iter(obj, prop, &local_err, opaque);
> +    g_hash_table_iter_init(&props, obj->properties);
> +    while (g_hash_table_iter_next(&props, &key, &value)) {
> +        iter(obj, value, &local_err, opaque);
>          if (local_err) {
>              error_propagate(errp, local_err);
>              return;
> @@ -936,21 +954,17 @@ void object_property_foreach(Object *obj,
> 
>  void object_property_del(Object *obj, const char *name, Error **errp)
>  {
> -    ObjectProperty *prop = object_property_find(obj, name, errp);
> -    if (prop == NULL) {
> +    ObjectProperty *prop = g_hash_table_lookup(obj->properties, name);
> +
> +    if (!prop) {
> +        error_setg(errp, "Property '.%s' not found", 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);
> +    g_hash_table_remove(obj->properties, name);
>  }
> 
>  void object_property_get(Object *obj, Visitor *v, const char *name,
> @@ -1470,11 +1484,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;
>          }
> @@ -1558,11 +1574,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)) {
> --
> 2.4.3

 Signed-off-by: Pavel Fedin <address@hidden>

Kind regards,
Pavel Fedin
Expert Engineer
Samsung Electronics Research center Russia