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

[Bharata B Rao]

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.

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

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.

Regards,
Bharata.