From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:35979) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZlyqI-0000K0-2A for qemu-devel@nongnu.org; Tue, 13 Oct 2015 08:38:14 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZlyqB-0004Qo-Iz for qemu-devel@nongnu.org; Tue, 13 Oct 2015 08:38:09 -0400 Received: from mx1.redhat.com ([209.132.183.28]:44266) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZlyqB-0004Qa-BX for qemu-devel@nongnu.org; Tue, 13 Oct 2015 08:38:03 -0400 From: "Daniel P. Berrange" Date: Tue, 13 Oct 2015 13:37:45 +0100 Message-Id: <1444739866-14798-7-git-send-email-berrange@redhat.com> In-Reply-To: <1444739866-14798-1-git-send-email-berrange@redhat.com> References: <1444739866-14798-1-git-send-email-berrange@redhat.com> Subject: [Qemu-devel] [PATCH v4 6/7] 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 , Markus Armbruster , Paolo Bonzini , =?UTF-8?q?Andreas=20F=C3=A4rber?= From: 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: Daniel P. Berrange Signed-off-by: Pavel Fedin --- include/qom/object.h | 10 ++++-- qom/object.c | 98 ++++++++++++++++++++++++++++++---------------------- 2 files changed, 64 insertions(+), 44 deletions(-) diff --git a/include/qom/object.h b/include/qom/object.h index 761ffec..2a54515 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; }; @@ -1538,6 +1536,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), @@ -1553,6 +1554,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 7dace59..dd01652 100644 --- a/qom/object.c +++ b/qom/object.c @@ -68,7 +68,7 @@ struct TypeImpl }; struct ObjectPropertyIterator { - ObjectProperty *next; + GHashTableIter iter; }; static Type type_interface; @@ -330,6 +330,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; @@ -344,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_free); object_init_with_type(obj, type); object_post_init_with_type(obj, type); } @@ -363,29 +374,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; } } @@ -783,10 +800,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; @@ -883,13 +902,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)); @@ -902,7 +919,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; } @@ -911,10 +928,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); @@ -924,7 +940,7 @@ ObjectProperty *object_property_find(Object *obj, const char *name, ObjectPropertyIterator *object_property_iter_init(Object *obj) { ObjectPropertyIterator *ret = g_new0(ObjectPropertyIterator, 1); - ret->next = QTAILQ_FIRST(&obj->properties); + g_hash_table_iter_init(&ret->iter, obj->properties); return ret; } @@ -940,31 +956,27 @@ void object_property_iter_free(ObjectPropertyIterator *iter) ObjectProperty *object_property_iter_next(ObjectPropertyIterator *iter) { - ObjectProperty *ret = iter->next; - if (ret) { - iter->next = QTAILQ_NEXT(iter->next, node); + gpointer key, val; + if (!g_hash_table_iter_next(&iter->iter, &key, &val)) { + return NULL; } - return ret; + return val; } 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, @@ -1484,11 +1496,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; } @@ -1572,11 +1586,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