From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49421) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZjgPL-0004Wh-Dt for qemu-devel@nongnu.org; Wed, 07 Oct 2015 00:32:53 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZjgPI-0002eG-27 for qemu-devel@nongnu.org; Wed, 07 Oct 2015 00:32:51 -0400 Received: from ozlabs.org ([103.22.144.67]:46365) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZjgPH-0002dW-Fb for qemu-devel@nongnu.org; Wed, 07 Oct 2015 00:32:47 -0400 Date: Wed, 7 Oct 2015 10:55:04 +1100 From: David Gibson Message-ID: <20151006235504.GP3861@voom.fritz.box> References: <016801d10034$6356fe40$2a04fac0$@samsung.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="1LW0Rr0Uq98qh6Rv" Content-Disposition: inline In-Reply-To: <016801d10034$6356fe40$2a04fac0$@samsung.com> Subject: Re: [Qemu-devel] [PATCH] qobject: Replace property list with GHashTable List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Pavel Fedin Cc: 'Paolo Bonzini' , qemu-devel@nongnu.org --1LW0Rr0Uq98qh6Rv Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Tue, Oct 06, 2015 at 03:41:56PM +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). >=20 > 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 modify their objects during traversal, since GHashTableIter does n= ot > have modify-safe version. However, the code seems not to modify objects v= ia > these functions. Hmm.. modifying a child object internally should be fine, shouldn't it? IIUC only trying to remove it, change the key or the pointer to the value should be problematic. > Signed-off-by: Pavel Fedin > --- > include/qom/object.h | 4 +-- > qmp.c | 8 +++-- > qom/object.c | 98 +++++++++++++++++++++++-----------------------= ------ > vl.c | 4 ++- > 4 files changed, 54 insertions(+), 60 deletions(-) >=20 > 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; > =20 > - QTAILQ_ENTRY(ObjectProperty) node; > + Object *obj; What is the new obj pointer here for? > } ObjectProperty; > =20 > /** > @@ -405,7 +405,7 @@ struct Object > /*< private >*/ > ObjectClass *class; > ObjectFree *free; > - QTAILQ_HEAD(, ObjectProperty) properties; > + GHashTable *properties; How much extra memory does each Object take with no (or few) properties by using a hash table rather than a simple list here? > 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 =3D false; > ObjectPropertyInfoList *props =3D NULL; > + GHashTableIter iter; > ObjectProperty *prop; > =20 > obj =3D object_resolve_path(path, &ambiguous); > @@ -220,7 +221,8 @@ ObjectPropertyInfoList *qmp_qom_list(const char *path= , Error **errp) > return NULL; > } > =20 > - 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 =3D g_malloc0(sizeof(*entry)); > =20 > entry->value =3D g_malloc0(sizeof(ObjectPropertyInfo)); > @@ -499,6 +501,7 @@ DevicePropertyInfoList *qmp_device_list_properties(co= nst char *typename, > { > ObjectClass *klass; > Object *obj; > + GHashTableIter iter; > ObjectProperty *prop; > DevicePropertyInfoList *prop_list =3D NULL; > =20 > @@ -517,7 +520,8 @@ DevicePropertyInfoList *qmp_device_list_properties(co= nst char *typename, > =20 > obj =3D object_new(typename); > =20 > - 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; > =20 > 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) > } > } > =20 > +static void property_destroy(gpointer data) > +{ > + ObjectProperty *prop =3D 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 =3D data; > @@ -340,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, 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(ObjectP= roperty *prop) > return strstart(prop->type, "child<", NULL); > } > =20 > -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 =3D QTAILQ_FIRST(&obj->properties); > - > - QTAILQ_REMOVE(&obj->properties, prop, node); > + ObjectProperty *prop =3D value; > =20 > - 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 =3D=3D child)= { > - object_property_del(obj, prop->name, errp); > - break; > - } > - } > + return object_property_is_child(prop) && prop->opaque =3D=3D child; > } > =20 > 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); Ugh. Iterating through the whole hash table to delete a member is pretty nasty, buy I guess you have to because you're essentially deleting by value rather than by key. I suppose it's no worse than the current path. > } > } > =20 > @@ -410,7 +404,7 @@ static void object_finalize(void *data) > Object *obj =3D data; > TypeImpl *ti =3D obj->class->type; > =20 > - object_property_del_all(obj); > + g_hash_table_unref(obj->properties); > object_deinit(obj, ti); > =20 > g_assert(obj->ref =3D=3D 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 =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 > @@ -879,13 +875,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)); > @@ -897,8 +891,9 @@ object_property_add(Object *obj, const char *name, co= nst char *type, > prop->set =3D set; > prop->release =3D release; > prop->opaque =3D opaque; > + prop->obj =3D obj; > =20 > - QTAILQ_INSERT_TAIL(&obj->properties, prop, node); > + g_hash_table_insert(obj->properties, prop->name, prop); > return prop; > } > =20 > @@ -907,10 +902,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); > @@ -919,21 +913,11 @@ ObjectProperty *object_property_find(Object *obj, c= onst char *name, > =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) { > + if (g_hash_table_remove(obj->properties, 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); > + error_setg(errp, "Property '.%s' not found", name); > } > =20 > 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 =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; > } > @@ -1541,11 +1527,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)) { > 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) > =20 > static int machine_help_func(QemuOpts *opts, MachineState *machine) > { > + GHashTableIter iter; > ObjectProperty *prop; > =20 > if (!qemu_opt_has_help_opt(opts)) { > return 0; > } > =20 > - 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; > } --=20 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 --1LW0Rr0Uq98qh6Rv Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQIcBAEBAgAGBQJWFF9YAAoJEGw4ysog2bOSzGsP/3LvIVqYcBvFFy73FNKZa2SB 3vPYKAhXCe2ResCIiDkbQEl0rFDEAwrDy9ZovfUy0yUZ+78yz01jqxpDLm407Goi d6ZDrBlEG3wkEaKT+VlMzFbP7g6dKDUrIfHGB+10ef4oxFXlyOciy7OeC9ooibuF LGXhTHFc9TEKe4BnsewaQpYAlsJoGcwAb+JA9USZeOXXZt7R1XMyRl89UdsTUcvm 7J9LVhQyfxSp1UUu0WW79cVbLIrWoooT9Q7ZBywcyjDsKZs2UBkN9nOCFTfdryoy OnM2gWWp8IYKNifpM1eR1ItdF3qIBzYO0PrOVWDOKKT3yRS8ZgKsegy0baMJuan8 L1VdWMzAyEaMJuVFXXmhUAFsWfbvCIRYi8U0ZgD+VDwwg+lzC3Zz9dIAwyG3eQ/W oNLuBYA5S77cUoCt9P20dH4gEl4mwvYRCuXyUulfvsal6z6SRezZoQHMxSe8yyUZ bUTxGd+GaMigZI6BFsRZ8ZIAPXq7/ulZjIX1tgwZGAu+5amCmRBw83YonuaukzWK OhER6GW+Z++TK5rXPst7pkJSgMPgVzV0vHTHZBdEqwJyxLVulS4uB1k7H2kLAsBx MMrwjLk3+Dx37BEK2zJMSzks4e3+JP8wNgsqPfWIAbUPyuOLdDLGJRKFIg4TOqPE HgTYJidpHTkBPa5mOv8x =Czmi -----END PGP SIGNATURE----- --1LW0Rr0Uq98qh6Rv--