Re: [Qemu-ppc] [RFC PATCH] spapr: Reduce creation of LMB DR connectors from O(n^3) to O(n^2)

[David Gibson]

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[*], ...);
> > 
> > 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=2T, for example, there are >250,000 objects
> > under the same parent.
> 
> There is one LMB DRC object for every 256MB, so with 2T maxmem, there will 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 existing
> > 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) because
> > there's a linear search through all properties to check for duplicates.
> > 
> > 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).
> > 
> > O(n^2) is still kind of crappy, but it's enough to reduce the startup time
> > of qemu with maxmem=2T from ~20 minutes to ~4 seconds.
> > 
> > Signed-off-by: David Gibson <address@hidden>
> > Cc: Bharata B Rao <address@hidden>
> > ---
> >  hw/ppc/spapr_drc.c | 4 +++-
> >  1 file changed, 3 insertions(+), 1 deletion(-)
> > 
> > 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 =
> >          SPAPR_DR_CONNECTOR(object_new(TYPE_SPAPR_DR_CONNECTOR));
> > +    char *prop_name = g_strdup_printf("dr-connector[%"PRIu32"]", id);
> 
> 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.

-- 
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

pgpxQfU5cwyxi.pgp
Description: PGP signature