From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37277) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Zz9Wy-0003Jn-Hl for qemu-devel@nongnu.org; Wed, 18 Nov 2015 15:40:42 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Zz9Ww-0005dK-Sn for qemu-devel@nongnu.org; Wed, 18 Nov 2015 15:40:40 -0500 Received: from mx2.suse.de ([195.135.220.15]:49563) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Zz9Ww-0005d9-KC for qemu-devel@nongnu.org; Wed, 18 Nov 2015 15:40:38 -0500 From: =?UTF-8?q?Andreas=20F=C3=A4rber?= Date: Wed, 18 Nov 2015 21:39:36 +0100 Message-Id: <1447879178-5440-9-git-send-email-afaerber@suse.de> In-Reply-To: <1447879178-5440-1-git-send-email-afaerber@suse.de> References: <1447879178-5440-1-git-send-email-afaerber@suse.de> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: [Qemu-devel] [PULL 08/10] qom: Replace object property list with GHashTable List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: Pavel Fedin , =?UTF-8?q?Andreas=20F=C3=A4rber?= From: Pavel Fedin ARM GICv3 systems with large number of CPUs create lots of IRQ pins. Sinc= e every pin is represented as a property, number of these properties become= s very large. Every property add first makes sure there's no duplicates. Traversing the list becomes very slow, therefore QEMU initialization take= s significant time (several seconds for e. g. 16 CPUs). This patch replaces list with GHashTable, making lookup very fast. The on= ly drawback is that object_child_foreach() and object_child_foreach_recursiv= e() cannot add or remove properties during traversal, since GHashTableIter do= es not have modify-safe version. However, the code seems not to modify objec= ts via these functions. Signed-off-by: Pavel Fedin Signed-off-by: Daniel P. Berrange Tested-by: Pavel Fedin [AF: Fixed object_property_del_{all,child}() issues] Reviewed-by: Daniel P. Berrange Signed-off-by: Andreas F=C3=A4rber --- include/qom/object.h | 10 +++-- qom/object.c | 120 ++++++++++++++++++++++++++++++++-------------= ------ 2 files changed, 83 insertions(+), 47 deletions(-) diff --git a/include/qom/object.h b/include/qom/object.h index 9f70314..f172fea 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; =20 /** @@ -405,7 +403,7 @@ struct Object /*< private >*/ ObjectClass *class; ObjectFree *free; - QTAILQ_HEAD(, ObjectProperty) properties; + GHashTable *properties; uint32_t ref; Object *parent; }; @@ -1537,6 +1535,9 @@ void object_property_set_description(Object *obj, c= onst char *name, * Call @fn passing each child of @obj and @opaque to it, until @fn retu= rns * 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 *opa= que), @@ -1552,6 +1553,9 @@ int object_child_foreach(Object *obj, int (*fn)(Obj= ect *child, void *opaque), * non-zero. Calls recursively, all child nodes of @obj will also be pas= sed * 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 1c926ce..19e7561 100644 --- a/qom/object.c +++ b/qom/object.c @@ -68,7 +68,7 @@ struct TypeImpl }; =20 struct ObjectPropertyIterator { - ObjectProperty *next; + GHashTableIter iter; }; =20 static Type type_interface; @@ -330,6 +330,16 @@ static void object_post_init_with_type(Object *obj, = TypeImpl *ti) } } =20 +static void object_property_free(gpointer data) +{ + ObjectProperty *prop =3D 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 =3D data; @@ -344,7 +354,8 @@ void object_initialize_with_type(void *data, size_t s= ize, TypeImpl *type) memset(obj, 0, type->instance_size); obj->class =3D type->class; object_ref(obj); - QTAILQ_INIT(&obj->properties); + obj->properties =3D g_hash_table_new_full(g_str_hash, g_str_equal, + NULL, object_property_free); object_init_with_type(obj, type); object_post_init_with_type(obj, type); } @@ -363,29 +374,51 @@ static inline bool object_property_is_child(ObjectP= roperty *prop) =20 static void object_property_del_all(Object *obj) { - while (!QTAILQ_EMPTY(&obj->properties)) { - ObjectProperty *prop =3D QTAILQ_FIRST(&obj->properties); - - QTAILQ_REMOVE(&obj->properties, prop, node); - - if (prop->release) { - prop->release(obj, prop->name, prop->opaque); + ObjectProperty *prop; + GHashTableIter iter; + gpointer key, value; + bool released; + + do { + released =3D false; + g_hash_table_iter_init(&iter, obj->properties); + while (g_hash_table_iter_next(&iter, &key, &value)) { + prop =3D value; + if (prop->release) { + prop->release(obj, prop->name, prop->opaque); + prop->release =3D NULL; + released =3D true; + break; + } + g_hash_table_iter_remove(&iter); } + } while (released); =20 - g_free(prop->name); - g_free(prop->type); - g_free(prop->description); - g_free(prop); - } + g_hash_table_unref(obj->properties); } =20 static void object_property_del_child(Object *obj, Object *child, Error = **errp) { ObjectProperty *prop; + GHashTableIter iter; + gpointer key, value; =20 - QTAILQ_FOREACH(prop, &obj->properties, node) { + g_hash_table_iter_init(&iter, obj->properties); + while (g_hash_table_iter_next(&iter, &key, &value)) { + prop =3D value; + if (object_property_is_child(prop) && prop->opaque =3D=3D child)= { + if (prop->release) { + prop->release(obj, prop->name, prop->opaque); + prop->release =3D NULL; + } + break; + } + } + g_hash_table_iter_init(&iter, obj->properties); + while (g_hash_table_iter_next(&iter, &key, &value)) { + prop =3D value; if (object_property_is_child(prop) && prop->opaque =3D=3D child)= { - object_property_del(obj, prop->name, errp); + g_hash_table_iter_remove(&iter); break; } } @@ -783,10 +816,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 =3D 0; =20 - 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 =3D prop->opaque; =20 @@ -883,13 +918,11 @@ object_property_add(Object *obj, const char *name, = const char *type, return ret; } =20 - QTAILQ_FOREACH(prop, &obj->properties, node) { - if (strcmp(prop->name, name) =3D=3D 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; } =20 prop =3D g_malloc0(sizeof(*prop)); @@ -902,7 +935,7 @@ object_property_add(Object *obj, const char *name, co= nst char *type, prop->release =3D release; prop->opaque =3D opaque; =20 - QTAILQ_INSERT_TAIL(&obj->properties, prop, node); + g_hash_table_insert(obj->properties, prop->name, prop); return prop; } =20 @@ -911,10 +944,9 @@ ObjectProperty *object_property_find(Object *obj, co= nst char *name, { ObjectProperty *prop; =20 - QTAILQ_FOREACH(prop, &obj->properties, node) { - if (strcmp(prop->name, name) =3D=3D 0) { - return prop; - } + prop =3D g_hash_table_lookup(obj->properties, name); + if (prop) { + return prop; } =20 error_setg(errp, "Property '.%s' not found", name); @@ -924,7 +956,7 @@ ObjectProperty *object_property_find(Object *obj, con= st char *name, ObjectPropertyIterator *object_property_iter_init(Object *obj) { ObjectPropertyIterator *ret =3D g_new0(ObjectPropertyIterator, 1); - ret->next =3D QTAILQ_FIRST(&obj->properties); + g_hash_table_iter_init(&ret->iter, obj->properties); return ret; } =20 @@ -938,30 +970,26 @@ void object_property_iter_free(ObjectPropertyIterat= or *iter) =20 ObjectProperty *object_property_iter_next(ObjectPropertyIterator *iter) { - ObjectProperty *ret =3D iter->next; - if (ret) { - iter->next =3D QTAILQ_NEXT(iter->next, node); + gpointer key, val; + if (!g_hash_table_iter_next(&iter->iter, &key, &val)) { + return NULL; } - return ret; + return val; } =20 void object_property_del(Object *obj, const char *name, Error **errp) { - ObjectProperty *prop =3D object_property_find(obj, name, errp); - if (prop =3D=3D NULL) { + ObjectProperty *prop =3D g_hash_table_lookup(obj->properties, name); + + if (!prop) { + error_setg(errp, "Property '.%s' not found", name); return; } =20 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); } =20 void object_property_get(Object *obj, Visitor *v, const char *name, @@ -1481,11 +1509,13 @@ void object_property_add_const_link(Object *obj, = const char *name, gchar *object_get_canonical_path_component(Object *obj) { ObjectProperty *prop =3D NULL; + GHashTableIter iter; =20 g_assert(obj); g_assert(obj->parent !=3D NULL); =20 - 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; } @@ -1569,11 +1599,13 @@ static Object *object_resolve_partial_path(Object= *parent, bool *ambiguous) { Object *obj; + GHashTableIter iter; ObjectProperty *prop; =20 obj =3D object_resolve_abs_path(parent, parts, typename, 0); =20 - 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; =20 if (!object_property_is_child(prop)) { --=20 2.6.2