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

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

[David Gibson]

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.

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 <david@gibson.dropbear.id.au>
Cc: Bharata B Rao <bharata@linux.vnet.ibm.com>
---
 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);
 
     g_assert(type);
 
     drc->type = type;
     drc->id = id;
     drc->owner = owner;
-    object_property_add_child(owner, "dr-connector[*]", OBJECT(drc), NULL);
+    object_property_add_child(owner, prop_name, OBJECT(drc), NULL);
     object_property_set_bool(OBJECT(drc), true, "realized", NULL);
+    g_free(prop_name);
 
     /* human-readable name for a DRC to encode into the DT
      * description. this is mainly only used within a guest in place
-- 
2.4.3

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

[Peter Crosthwaite]

On Wed, Sep 9, 2015 at 11:28 PM, David Gibson
<david@gibson.dropbear.id.au> 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.
>
> 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.
>

Does this help? I think it's already queued:

http://lists.nongnu.org/archive/html/qemu-devel/2015-07/msg05790.html

Regards,
Peter

> 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 <david@gibson.dropbear.id.au>
> Cc: Bharata B Rao <bharata@linux.vnet.ibm.com>
> ---
>  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);
>
>      g_assert(type);
>
>      drc->type = type;
>      drc->id = id;
>      drc->owner = owner;
> -    object_property_add_child(owner, "dr-connector[*]", OBJECT(drc), NULL);
> +    object_property_add_child(owner, prop_name, OBJECT(drc), NULL);
>      object_property_set_bool(OBJECT(drc), true, "realized", NULL);
> +    g_free(prop_name);
>
>      /* human-readable name for a DRC to encode into the DT
>       * description. this is mainly only used within a guest in place
> --
> 2.4.3
>
>

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

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 1619 bytes --]

On Thu, Sep 10, 2015 at 01:42:57AM -0700, Peter Crosthwaite wrote:
> On Wed, Sep 9, 2015 at 11:28 PM, David Gibson
> <david@gibson.dropbear.id.au> 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.
> >
> > 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.
> >
> 
> Does this help? I think it's already queued:
> 
>
>http://lists.nongnu.org/archive/html/qemu-devel/2015-07/msg05790.html


It doesn't help our case; it's basically a fix for a different
instance of the same problem.

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

[-- Attachment #2: Type: application/pgp-signature, Size: 819 bytes --]

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

[Paolo Bonzini]

On 10/09/2015 08:28, 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.

That must consume quite some memory... I would guess 1K per object.

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

Thanks, I agree that even O(n^2) is crappy.  We need to add a hash table
for properties, so that [*] is O(n^2) and the optimized case is O(n).

Paolo

> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
> Cc: Bharata B Rao <bharata@linux.vnet.ibm.com>
> ---
>  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);
>  
>      g_assert(type);
>  
>      drc->type = type;
>      drc->id = id;
>      drc->owner = owner;
> -    object_property_add_child(owner, "dr-connector[*]", OBJECT(drc), NULL);
> +    object_property_add_child(owner, prop_name, OBJECT(drc), NULL);
>      object_property_set_bool(OBJECT(drc), true, "realized", NULL);
> +    g_free(prop_name);
>  
>      /* human-readable name for a DRC to encode into the DT
>       * description. this is mainly only used within a guest in place
> 

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 <david@gibson.dropbear.id.au>
> Cc: Bharata B Rao <bharata@linux.vnet.ibm.com>
> ---
>  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.

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

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 2683 bytes --]

On Fri, Sep 11, 2015 at 02:43:43PM +0200, Paolo Bonzini wrote:
> 
> 
> On 10/09/2015 08:28, 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.
> 
> That must consume quite some memory... I would guess 1K per object.

So, Bharata was right, it's only ~32k objects even for maxmem=4T.  I'm
not quite sure how I messed up my arithmetic there.

But still, yeah, it's a lot of objects :/.  Medium term I think we
should avoid creating so many objects for the connectors.  I'm
thinking a "connector array" object that handles a whole range of
connector indices them with a single QOM object should be possible.

> > 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.
> 
> Thanks, I agree that even O(n^2) is crappy.  We need to add a hash table
> for properties, so that [*] is O(n^2) and the optimized case is
> O(n).

Right, so I had the impression that QOM isn't really built for
handling thousands of objects under one parent.  I don't have a wide
enough view to know if that's a reasonable goal for it ever to handle
well.  Using a hash table at every node might be pretty expensive in
memory for nodes with only a handful of children.

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

[-- Attachment #2: Type: application/pgp-signature, Size: 819 bytes --]

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

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 3746 bytes --]

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 <david@gibson.dropbear.id.au>
> > Cc: Bharata B Rao <bharata@linux.vnet.ibm.com>
> > ---
> >  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

[-- Attachment #2: Type: application/pgp-signature, Size: 819 bytes --]