From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47738) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZbIm4-0007ni-BZ for qemu-devel@nongnu.org; Sun, 13 Sep 2015 21:41:41 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZbIm0-0001o2-AM for qemu-devel@nongnu.org; Sun, 13 Sep 2015 21:41:40 -0400 Date: Mon, 14 Sep 2015 11:32:06 +1000 From: David Gibson Message-ID: <20150914013206.GB2547@voom.fritz.box> References: <1441866505-10842-1-git-send-email-david@gibson.dropbear.id.au> <20150911161206.GM17433@in.ibm.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="Bn2rw/3z4jIqBvZU" Content-Disposition: inline In-Reply-To: <20150911161206.GM17433@in.ibm.com> Subject: Re: [Qemu-devel] [RFC PATCH] spapr: Reduce creation of LMB DR connectors from O(n^3) to O(n^2) List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Bharata B Rao Cc: aik@ozlabs.ru, qemu-ppc@nongnu.org, agraf@suse.de, qemu-devel@nongnu.org --Bn2rw/3z4jIqBvZU Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Sep 11, 2015 at 09:42:06PM +0530, Bharata B Rao wrote: > On Thu, Sep 10, 2015 at 04:28:25PM +1000, David Gibson wrote: > > The dynamic reconfiguration (hotplug) code for the pseries machine type > > uses a "DR connector" QOM object for each resource it will be possible > > to hotplug. Each of these is added to its owner using > > object_property_add_child(owner, "dr-connector[*], ...); > >=20 > > This works ok for most cases, but gets ugly when allowing large amounts= of > > hotplugged RAM. For RAM, there's a DR connector object for every 256MB= of > > potential memory. So if maxmem=3D2T, for example, there are >250,000 o= bjects > > under the same parent. >=20 > There is one LMB DRC object for every 256MB, so with 2T maxmem, there wil= l be > max 8192 LMB DRC objects. Oops, that's embarrasing, I messed up my arithmetic. You're right, only 8192 objects for a 2T guest. Still rather a lot. > > The QOM interfaces aren't really designed for this. In particular > > object_property_add() has O(n^2) time complexity (in the number of exis= ting > > children) for the [*] case. First it has a linear search through array > > indices to find a free slot, each of which is attempted to a recursive = call > > to object_property_add() with a specific [N]. Those calls are O(n) bec= ause > > there's a linear search through all properties to check for duplicates. > >=20 > > For the specific case of DR connectors, we already have a sufficiently > > unique index, so we don't need to use the [*] special behaviour. That = lets > > us reduce the total time for creating the DR objects from O(n^3) to O(n= ^2). > >=20 > > O(n^2) is still kind of crappy, but it's enough to reduce the startup t= ime > > of qemu with maxmem=3D2T from ~20 minutes to ~4 seconds. > >=20 > > Signed-off-by: David Gibson > > Cc: Bharata B Rao > > --- > > hw/ppc/spapr_drc.c | 4 +++- > > 1 file changed, 3 insertions(+), 1 deletion(-) > >=20 > > diff --git a/hw/ppc/spapr_drc.c b/hw/ppc/spapr_drc.c > > index c1f664f..4cf3a9b 100644 > > --- a/hw/ppc/spapr_drc.c > > +++ b/hw/ppc/spapr_drc.c > > @@ -463,14 +463,16 @@ sPAPRDRConnector *spapr_dr_connector_new(Object *= owner, > > { > > sPAPRDRConnector *drc =3D > > SPAPR_DR_CONNECTOR(object_new(TYPE_SPAPR_DR_CONNECTOR)); > > + char *prop_name =3D g_strdup_printf("dr-connector[%"PRIu32"]", id); >=20 > This works only if memory hotplug alone is present. If CPU hotplug is also > present, the lookup of DRC object for LMB DRC fails from ibm,cas call when > the guest is booting. Bother. > I don't fully understand why it fails, but the object lookup doesn't seem= to > like duplicate names that we end up having here. With the above change, we > can have duplicate prop_name under the same owner object (spapr machine > object) due to both CPU and LMB DRC objects coming under the same parent. So.. arguably having both types of connector under the same parent is a mistake. But in the short term, we should be able to fix that by using the DRC index, instead of just the id as the property array index. It means the indices won't be contiguous, but having something meaningful in there is probably still better than the arbitrary index that [*] will give us. Especially since, confusingly, the will look like they're the LMB ID *until* you add CPU hotplug, and then they'll get offset, maybe, depending on whether CPU or memory gets constructed first. Revised patch coming shortly. --=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 --Bn2rw/3z4jIqBvZU Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQIcBAEBAgAGBQJV9iOWAAoJEGw4ysog2bOSEGQQAMnet0zIjrUuJXs0AqL1IBve LW5Gbr3LvbNEN5R7X3cHRwqOtwN8igIlTI023LDoj+0fk4qyJORZwgh2UjvNehk1 UQVzF2uMAmmanB2xqE4d3pr6S20LxQgzclEaNsHZvdTdJPAFBlcclKRrdg8NrsDM UTPfeSJ4gO5sOERazm+qfDd+7IdReVQklTQ64geOB/X5JpdrtP15KJobNA0wA9p1 HysUwrAOkTmFM6N1ouycQLFLEmJ6kDEX6LfRsKuui4XWctKie4LkPQBJ6uHk0kck CqKULRG8zP/oDu+YvXIRK/W2r+xlRiQ/sN93hWLX3Fdo3KUbumfKejdSykzKOFxE iOa4f9wY0qx+IinW6c6+OhuSSAAiR2WEssoLhkzmN2sQETYuJA7ioM3UgLhKXLZy OEZ+Jpm3utnsjh/oAtzn4Qift5/4YElpkiWhwye2oBoWbVXsG7ezibDoJZ8nydtK HRHl4/qh5vXjb7w4RU2fpIsEN7C6rEOIT7Ipxzj5b/bHvnjLsckU04SUxZGl+hgP trSBSMfia6/gEUPIVFAMZ+pZW+WJPYMvFY9Nt3j7aKIWppw866/rhXUbfcnOylgm YqvF2/sD0afjsxpEiVkukiR7/1qB3u28qSDg59gCTZ4eoTR7Nt4lG1hmJSpzz+NO F0jZVDZSuab+swnMVu0m =bG22 -----END PGP SIGNATURE----- --Bn2rw/3z4jIqBvZU--