Re: [Qemu-devel] [RFC PATCH] spapr: Reduce creation of LMB DR connectors from O(n^3) to O(n^2)
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 pgpuCe9zmrnOx.pgp Description: PGP signature
Re: [Qemu-devel] [RFC PATCH] spapr: Reduce creation of LMB DR connectors from O(n^3) to O(n^2)
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> > Cc: Bharata B Rao > > --- > > 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 pgpBB3Z0cYIW8.pgp Description: PGP signature
Re: [Qemu-devel] [RFC PATCH] spapr: Reduce creation of LMB DR connectors from O(n^3) to O(n^2)
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> Cc: Bharata B Rao > --- > 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)
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> Cc: Bharata B Rao > --- > 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)
On Wed, Sep 9, 2015 at 11:28 PM, David Gibsonwrote: > 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 > Cc: Bharata B Rao > --- > 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)
On Thu, Sep 10, 2015 at 01:42:57AM -0700, Peter Crosthwaite wrote: > On Wed, Sep 9, 2015 at 11:28 PM, 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. > > > > 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 pgpLtokSOqyqB.pgp Description: PGP signature
[Qemu-devel] [RFC PATCH] spapr: Reduce creation of LMB DR connectors from O(n^3) to O(n^2)
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 GibsonCc: Bharata B Rao --- 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